CPU 스케줄링

개요

운영체제가 메모리에 적재한 프로세스 중, 다음에 CPU를 할당할 프로세스를 선택하는 것.

왜 필요한 건가?

CPU는 한 번에 한 프로세스만 실행할 수 있다. 

하지만 프로세스에서는 항상 CPU를 사용하는 것은 아닌데, 입출력 장치를 통해 사용자와의 인터랙션이 진행 중일 때는 프로세스는 CPU를 사용하지 않는다. 하지만 이 때도 프로세스는 CPU를 점유하고 있다. 간단히 말하면 소중한 CPU가 아무것도 하지 않은 채 놀고 있다는 것이다. 이렇게 CPU를 점유하고 사용하지 않는 시간에 다른 프로세스를 실행하면 CPU의 사용률을 높이고 전체 시스템의 성능을 향상시킬 수 있다.

즉, 소중한 자원인 CPU를 최대한 활용하기 위한 기술이 CPU 스케줄링이다.

시스템 종류에 따른 목표

1. Batch System : 많은 처리량
2. Interactive System : 짧은 응답 시간과 대기 시간
3. Real-time System : 마감 기간(Deadline)

 

선점/비선점 스케줄링

선점 스케줄링

• 운영체제가 프로세스에 할당되었던 CPU를 강제로 뺏어올 수 있음(선점 가능)
• 우선순위가 높은 프로세스에 CPU 할당 가능

비선점 스케줄링

• 프로세스가 대기 상태에 들어가거나 종료되지 않고서는 프로세스 전환이 일어나지 않음

 

프로세스의 상태

• New : 프로세스 생성 중
• Ready : CPU 할당 대기 중. 언제든지 CPU를 사용할 수 있는 상태. 메모리 등은 모두 준비됨.
• Running : CPU를 할당받고 명령어를 실행 중
• Blocked : 자신이 요청한 event가 만족되지 않아 기다리고 있는 상태. 명령을 수행할 수 없는 상태. (waiting, sleeping)
• Terminated : 프로세스 실행이 끝난 상태

프로세스 상태 전이

프로세스 상태 전이

• Dispatch
  • 레디큐 맨 앞의 프로세스가 CPU를 점유하는 것. 즉, 준비 상태에서 실행 상태로 바뀌는 것
• Block(I/O or Event wait)
  • 실행 상태의 프로세스가 허가된 시간을 다 쓰기 전에 입출력/이벤트를 처리해야 하는 경우, 프로세스가 CPU를 반납하고 blocked 상태로 바뀌는 것
• wakeup(I/O or Event Completion)
  • 프로세스가 기다리던 입출력/이벤트를 준비 상태로 바꾸는 것
• Interrupt(timer interrupt/timeout)
  • 운영체제가 프로세스에 할당한 시간이 만료되어 준비 상태로 바뀌는 것

 

스케줄링 종류

비선점

1. FCFS(First-Come First-Served)
   • 레디큐에 도착한 순서대로 CPU 할당
   • 작업 완료 시간을 예측하기 용이
   • 긴 프로세스가 앞에오면 매우 비효율적인 스케줄링이 된다
   • convoy effect
     • 긴 프로세스를 다른 모든 프로세스들이 기다림
     • CPU 사용률을 낮추기에 성능 저하 발생

   • 

     출처 - https://rebas.kr/863

2. SJF(Shortest Job First)
   • 수행 시간이 가장 짧은 프로세스를 먼저 스케줄
   • FCFS보다 평균 대기 시간 감소

   • 

     출처 - https://rebas.kr/863

3. HRN(Hightest Response-ratio Next)
   • 수행시간과 대기시간을 고려하여 우선순위를 결정
   • 우선순위 = (수행시간 + 대기시간) / 수행시간
   • 긴 프로세스와 짧은 프로세스간 불평등 보완(SJF 보완)

선점

1. Priority Scheduling
   • 정적/동적으로 우선순위 부여
   • 우선순위 대로 CPU 할당
   • 우선순위가 낮은 프로세스가 무한히 기다리기만 하는 starvation 가능성 있음
   • 오래된 프로세스의 우선순위를 높이는 aging 으로 대응
2. Round Robin  
   • 각 프로세스마다 동일한 CPU 할당 시간을 줌(time quantum)
   • FCFS로 진행됨
   • 할당 시간이 크면 FCFS와 같고, 너무 짧으면 context switch에 의해 오버헤드가 커짐

   • 

     round robin - 위키피디아

   • 

     출처 - https://rebas.kr/863

3. SRT(Shortest Remaining Time Scheduling)
   • SJF를 선점형으로 변형한 스케줄링
   • 실행중인 프로세스의 남은 실행 시간과 레디큐에 도착한 프로세스들의 실행시간을 비교함
   • 남은 실행 시간이 짧은 프로세스에 CPU 할당

   • 

     출처 - https://rebas.kr/863

   • 

     출처 - https://blog.hax0r.info/2020-05-11/process-scheduling-and-techniques/

4. Multilevel Queue(다단계 큐)
   • 여러 개로 레디큐 분할
   • 우선순위가 낮은 큐에 starvation을 우려하여 각 큐마다 적절한 비율로 time quantum 할당.
5. Multilevel Feedback Queue(다단계 피드백 큐)
   
   • 다단계 큐에서 time quantum을 채운 프로세스를 우선순위가 낮은 큐로 이동시킴. time quantum을 못 채운 프로세스는 그대로
   • 입출력 위주의 interrupt가 잦은 프로세스에 우선권을 줌
   • time quantum을 채운 프로세스는 CPU burst process라고 판단하여 뒤에 처리
   • 수행시간이 짧은 프로세스를 먼저 처리하여 평균 turnaround 시간을 줄여줌

 

스케줄러 종류

스케줄러

1. 장기 스케줄러
   • 하드디스크에서 메모리에 적재할 작업(프로세스)를 선별함
   • 작업(job) 스케줄링
2. 단기 스케줄러
   • 레디큐에 준비된 프로세스 중 하나를 선별해 CPU 할당
   • 일반적으로 스케줄러는 이것을 의미함
3. 중기 스케줄러
   • 메모리에 적재된 프로세스가 너무 많아져 하드디스크 입출력이 과다해지면 시스템 성능이 급감함
   • Swapping : 일부 프로세스를 메모리에서 디스크로 보내고(swap-out), 메모리에 여유가 생기면 다시 적재함(swap-in)