[한권떼기] 운영체제 04번째. CPU 스케쥴링

**본 글의 일부분은 서적 'Operating Systems: Three Easy Pieces by Remzi H.Arpaci-Dusseau, Andrea C.Arpaci-Dusseau', 'Operation System Concepts Abraham Silberschatz 외 2' 내의 이미지와 내용을 포함하고 있습니다

 

CPU 스케쥴링

CPU 스케쥴링은 실행하고자 대기하고 있는 프로세스들 중에서 어떤 프로세스에게 CPU 자원을 줘서 실행시킬지 정하는 것

 

프로세스는 항상 CPU만 사용하는 것이 아니라 I/O 작업도 같이 함

(ex. 계산기는 CPU를 한번 가져오면 오래 쓰지만, 에디터는 CPU를 쓰는 시간이 짧고 빈도가 높음)

 

프로세스가 자발적으로 I/O를 호출하거나, 종료될 때 (non-preemptive)

또는 너무 오래 실행하거나 입출력 처리가 완료되어 CPU가 프로세스에게 간섭하는 경우에 (preemptive) 

이 스케쥴링 방식이 필요하게 됨

 

스케쥴링 평가 기준

CPU utilization: 얼마나 CPU를 바쁘게 썼는지에 대한 활용도 퍼센트 값

Throughput: 일정 시간동안 총 몇 개의 프로세스를 처리했는지의 개수

Turnaround time: 프로세스가 대기 큐에 들어오고 나서부터 완전히 끝난 때까지의 시간 차이

Waiting time: 프로세스가 대기 큐에서 기다린 시간의 총 합

Response time: 처음 요청했던 시각부터 첫번째 스케쥴이 될 때까지의 시간 차이

 

 

스케쥴링 방식의 종류 

FIFO (First Come First Served)

특징: 먼저 들어온 것이 먼저 나감

문제점

CPU burst time이 긴 프로세스를 먼저 실행하면 다른 프로세스가 지체됨

 

SJF (Shortest Job First)

특징: 대기 중인 큐에서 가장 짧은 걸 먼저 수행

문제점

실제로는 프로세스들이 아무때나 들어올 수 있기 때문에, 어떤 Job이 가장 짧은지 알아내기 어려움

따라서 동시에 Job이 한꺼번에 들어오지 않는 이상, non-preemitive 특징 때문에 짧은 프로세스가 계속 대기하는 문제가 생김

 

STCF
(Shortest Time-to-Completion First = Preemitive Shortest Job First = Shortest Remaining Time First)

특징: SJF의 non-preemitive로 인한 문제를 해결하여 언제든 완료까지 남은 시간이 더 짧은 Job이 들어오면 실행하던걸 중지시키고 그 Job을 수행

 

RR(Round Robin) 스케쥴링

특징:

타임 퀀텀를 정해놓고 그 타임 퀀텀만큼 번갈아가면서 CPU를 쓰게 함. 타임 퀀텀을 소진하면 다시 큐에 enqueue 됨.

타임 퀀텀이 짧으면 context switching 때문에 오버헤드로 잡아먹는 시간이 늘어나고,

타임 퀀텀이 길면 response time이 나빠지게 됨

그러면 타임 퀀텀을 어느정도로 하면 좋을까?
리눅스에서는 타임 퀀텀을 수십ms ~ 수백ms 정도를 타임 퀀텀으로 두고 있습니다.

문제점

fair하지만 turnaround time(수행 완료까지의 시간)을 두고 봤을 때에는 성능이 좋지 않음

 

 

CPU 스케쥴링과 I/O

만약 위의 RR 스케쥴링에서 프로세스가 I/O를 쓰게 된다면 아래처럼 수행됨

 

1. 프로세스가 I/O job을 수행하고자 함

2. job은 blocked되고, I/O작업이 끝날때까지 blocked 상태로 대기함

3. 스케쥴러는 다른 프로세스에게 CPU을 줌

4. I/O 작업이 다 끝나면 interrupt로 알려줌

5. OS가 프로세스를 blocked에서 ready 상태로 변경함

 

 

MLFQ (Multilevel Feedback Queue)

MLFQ의 목적은 CPU burst time을 모르는 상태에서 얼마나 CPU를 쓰는지 예측하고, 그걸 바탕으로 우선순위를 정해서 스케쥴링의 효율성을 올리는 것

MLFQ를 통해서 I/O intensive job, CPU intensive job 이 섞여있는 환경에서 CPU를 조금만 쓰는 애를 높은 우선순위로 두면 효율이 좋아짐

 

MLFQ의 수행 순서

규칙1. 우선순위가 높은 프로세스를 먼저 수행

규칙2. 우선순위가 같다면 RR 알고리즘으로 동작

규칙3. 먼저 들어오면 가장 높은 우선순위에서 시작

규칙4. 주어진 타임퀀텀을 다 쓰면 다음 우선순위의 큐로 넘어감

규칙5. 일정 시간 지나면 모든 job을 가장 높은 우선순위 큐로 올림