CPU 스케쥴링 알고리즘

운영체제의 스케쥴링

운영체제가 프로세스를 실행시키는 ‘정책’ 중
‘고수준’에 해당하는 정책이며,
(저수준은 ‘문맥 교환’이며, 이는 메모리 주소 공간에 대한 밀접한 관련이 있으며
이는 하드웨어와 가깝기에 ‘저수준’이라 표현한다)

‘프로세스’나 ‘쓰레드’의 실행 순서를 결정하는 것을 말한다

이러한 ‘스케쥴링’을 통하여
프로세스나 스레드가 시스템 자원을 효율적이며 공평하게 사용하도록 한다

이러한 스케쥴링은 다양한 종류가 있다

• FCFS(First Come First Served) 또는 FIFO(First In First Out)
• SJF(Shortest Job First)
• SRTF(Shortest Remaining Time First) 또는 STCF(Shortest Time-to-Completion First)
• Round Robin
• Multilevel Queue Scheduling
• Multi-Level Feedback Queue Scheduler 등이 존재한다

또한 이러한 스케쥴링은 ‘선점’ 과 ‘비선점’으로 나눌 수 있는데
CPU가 현재 실행중인 프로세스를 강제로 중단하고,
다른 프로세스로 전환하는지 여부로 구분한다

• 선점(Preemptive) 스케쥴링
  

  CPU를 사용 중인 프로세스를 강제로 중단시키고, 다른 프로세스로 전환 가능
  (ex : Round Robin, Multi-Level Feedback Queue Scheduler)
  (보통 Timer Interrupt 와 같은 하드웨어 인터럽트로 ‘중단’시킨다)
  

• 비선점(Non-Preemptive) 스케쥴링
  

  CPU가 사용 중인 프로세스를 강제로 해제하지 않고
  해당 프로세스가 자발적으로 작업을 완료할 때까지 전환하지 않음
  (ex : FCFS, SJF 등)
  (하드웨어 인터럽트 가 발생되어도, 프로세스가 중단되지 않음)
  (시스템 콜 및 ‘트랩’ 인 경우는 해당 처리 이후, 재개 된다 한다)
  

• 반환 시간?
  

  ‘완료 시간 - 도착 시간’ 을 의미하며,
  스케쥴링의 평가 항목 중 하나
  

FCFS

선입선출 or 선도착선처리 라 불리는 스케쥴링 방법이다
매우 간단하게, 먼저 들어온 프로세스를 ‘먼저 처리’한다

단순하고, 구현이 쉽고, 잘 동작한다

그러나,
가장 먼저 도착한 프로세스의 처리 시간이 매~~우 긴 경우,
그 뒤의 프로세스들의 작업은 아~주 오래 지연된다
(비선점 스케쥴링)

SJF

최단 작업 우선 이라 불리는 방식이다

‘가장 짧은’ 작업 시간을 가진 프로세스를 ‘먼저 처리’한다
모든 작업들이 ‘동시에’ 도착한다 가정한다면,
‘최적’의 알고리즘이라 할 수 있다

그러나 여전히 가장 먼저 도착한 것이 ‘매우 긴’ 처리 시간의 프로세스라면,
위의 문제는 여전히 존재하며,
반대로,
‘매우 긴’ 처리 시간의 프로세스가
그보다 짧은 시간의 프로세스가 계속 입력되어
‘무시’되는 경우가 발생할 수 있음
(이를 ‘기아’(Starvation) 상태라고 부르며
특정한 프로세스가 ‘오랜 시간’동안 원하는 자원을 얻지 못하는 상태를 뜻함)
(비선점 스케쥴링)

SRTF

‘잔여 실행 시간’이 가장 짧은 프로세스를 가장 먼저 실행하는 방식

‘선점 스케쥴링’ 방식이기에,
타이머 인터럽트가 발생하였거나,
새로운 프로세스의 도착 시,
‘남은 작업 소요 시간’을 비교하여
가장 짧은 것부터 먼저 스케쥴링을 한다

실행시간이 적은 프로세스가 빠르게 실행되기에,
평균 대기 시간과 평균 응답 시간이 단축됨

다만 여전히 ‘기아 상태’를 해결하지 못하였으며,
‘문맥 교환’으로 인해 SJF 방식에 비하여 추가적인 오버헤드가 발생함

Round Robin

SRTF는 충분히 좋은 스케쥴링 방식이지만,
길이 가 긴 프로세스의 ‘응답 시간’이 좋지 못하다는 단점이 있다
(프로세스의 처음 스케쥴링된 시간 - 도착 시간)

라운드 로빈은 이러한 ‘응답 시간’에 대한 문제를 해결하기 위해 등장한
스케쥴링 방식이다

현재 프로세스를 ‘일정 시간(time slice or scheduling quantum)’ 만큼 작업하고 중단한 후,
다음 실행 큐의 작업을 실행하는 방식이다

‘일정 시간’의 길이가 짧아지면 전체 ‘응답 시간’은 줄어들지만,
‘문맥 교환’이 그만큼 자주 일어나게 되어 성능저하가 발생한다

반대로 길이가 길어지면, 전체 ‘응답 시간’이 늘어나므로,
적절한 길이를 정하는 것이 좋다

‘응답 시간’이라는 평가 기준에서 라운드 로빈은 좋은 스케쥴링 방식이다
‘공정’한 정책이지만,
‘반환 시간’이라는 평가 기준에서는 좋지 못한 스케쥴링 방식이다.
(조금만 더하면 끝나는데, 중단하고 다른 거 하러 가네?)

Multilevel Queue Scheduling

여러 개의 큐를 사용하여 ‘프로세스’를 그룹화하고
‘우선 순위’를 부여하여 스케쥴링 하는 방식
각 큐는 서로 다른 우선순위를 가지며,
각 큐마다 다른 스케쥴링 알고리즘이 적용될 수 있음

이로 인하여 다양한 종류의 프로세스에 대하여
효과적인 대응이 가능하다
다만, 설정과 관리가 복잡하다는 점도 있으며,
각각의 우선순위 설정에 따라서 ‘기아 상태’ 역시 발생할 수 있음

각 큐에 들어가는 프로세스의 ‘우선순위’나
큐의 ‘스케쥴링 알고리즘’에 따라서
‘응답 시간’과 ‘반환 시간’이 변화될수도 있음

(보통 낮은 우선순위 큐에는 간단한 (FCFS, Round Robin 등) 스케쥴링이,
높은 우선순위 큐에는 SJF 등과 같은 것이 고려된다고 함)

Multi-Level Feedback Queue Scheduler

현재도 다듬어져 사용되는 운영체제 스케쥴링 방식 중 하나
‘응답 시간’과 ‘반환 시간’의 최적화에 목표가 있음
(RR은 최적의 응답 시간을 가지지만, ‘반환 시간’이 최악에 가까움)
(SJF,SRTF는 ‘반환 시간’이 훌륭하지만, OS가 ‘작업 시간’을 판단하기 어렵다는
문제를 가진다 -> 과거 정보, 통계, 모니터링 등의 방식이 있지만 정확하지는 않음)

기본적으로는 ‘Multilevel Queue Scheduling’ 과 마찬가지로
여러 개의 ‘큐’를 가지며
‘우선순위’를 부과하는 방식이다
(각 큐마다 ‘라운드 로빈’을 이용하여 우선순위가 같다면 응답 시간을 향상 시킴)
(다만 세부적 구현은 다를 수 있다)

다만 각 프로세스의 우선순위를 동적으로 변화시켜,
실행 중 다른 큐로 이동할 수 있음
(이를 통해 기아 상태를 예방하고 응답 시간을 향상하려는 목적)

일반적인 규칙들은 이러하다

• 우선순위가 높은 작업부터 수행
  
• 우선순위가 같은 작업은 Round Robin 방식으로 실행
  
• 처음 들어오는 작업은 가장 높은 우선순위를 가짐
  
• 작업이 CPU에게 지정 받은 일정한 시간을 소진하면
  해당 작업의 우선순위를 감소
  
• 일정 시간이 지나면, 모든 프로세스를 최상위 큐로 이동
  

BSD(Berkeley Software Distribution)

Unix 계열 운영체제로,
4번째 버전인 4BSD 부터 MLFQ 스케쥴링 방식을 적용하였다

nice(Niceness)

Unix 운영체제의 일종의 ‘가중치’ 레벨을 표현하는 방식
(nive Value 혹은 ‘친절함’을 의미??)

-20~19의 값을 프로세스에 설정할 수 있음
낮은 nice 수치를 가질 수록, 더 잘 ‘양보’한다
반대로 높은 nice 수치를 가질 수록, 타인에게 ‘양보’당한다