운영체제 - CPU 스케쥴링(2)
OS를 공부하면서 정리를 한 내용들 입니다.
이번 챕터는 CPU 스케쥴링에 관련해 정리한 챕터입니다.
해당 알고리즘들 중 FCFS와 SJF방식에 대해 정리합니다.
들어가기에 앞서 스케쥴링은 nonpreemptive와 preemptive가 있습니다.
nonpreemptive는 CPU를 강제로 빼앗기지 않고 자진 반납하는 경우preemptive는 CPU를 강제로 빼앗을 수 있는 경우입니다.
스케쥴링 알고리즘
스케쥴링의 알고리즘은 크게 7가지로 구분합니다.
FCFS(First-come First-served)
먼저 도착한 프로세스에게 CPU를 먼저주는 방법입니다.
이것은 nonpreemptive방식으로 먼저 온 프로세스가 다 작업이 끝날 때까지 CPU를 줍니다.
비슷한 예 : 은행
번호표를 뽑고 순서대로 작업을처리하는데 먼저온 고객이 먼저 처리를 받습니다. 시간이 오래걸리더라도 고객을 중간에 내쫓거나 하는 경우는 없습니다.
0초에 다 도착을 했지만 간발의 차로 P1, P2, P3의 순서로 도착을 했다면,
P1에게 CPU를 주고 24초의 시간동안 빼앗지 않습니다.
P2, P3도 그렇게 진행이 됩니다.
Waiting time을 봅시다.
P1이 0초에 도착해서 기다린 시간이 없고,
P2는 P1이 작업을 마치고 CPU를 반환할 때까지 24초,
P3는 P1과 P2의 작업이 마칠때 까지 24+3초 해서 27초가 됩니다.
평균 Waiting time은 (0+24+27)/3 이므로 17초가 됩니다.
그런데 여기서 P1이 맨 뒤로 간다고 가정해봅니다.
가정 P1이 맨뒤로 갔을 때
P2, P3, P1의 순서로 도착을 했습니다.
Wating time을 봅시다.
P2 = 0, P3 = 3, P1 = 6초 입니다.
평균 Waiting time은 (0+3+6)/3 이므로 3초가 됩니다.
이전 케이스보다 훨씬 좋아 졌습니다.
앞에 작업시간이 많은 프로세스가 나오게 된다면 나머지는 전부 기다리게 됩니다.
이렇게 앞에 작업량이 긴 프로세스가 있음으로써 짧은 프로세스들이 기다리는 현상을
Convoy effect라고 합니다.
SJF(Shortest Job First)
각 프로세스의 다음번 CPU burst time을 가지고 스케쥴링에 활용하는 방식입니다.
CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케쥴 합니다.
기다린시간의 측면에서 보았을 때 가장 이상적인(Optimal한) 방법입니다.
nonpreemptive와 preemptive방식 2가지가 있습니다.
Nonpreemptive 버젼
현재 CPU에 줄 서있는 프로세스들 중에서 CPU burst 시간이 가장 짧은 프로세스에게 CPU를 할당해주는데
중간에 더 짧은 시간을 가지는 프로세스가 오더라도 CPU를 자진 반납하기 전까지는 CPU를 빼앗기지 않는 방식 입니다.
preemptive 버젼
현재 CPU에 줄 서있는 프로세스들 중에서 CPU burst 시간이 가장 짧은 프로세스에게 CPU를 할당해주는데
중간에 더 짧은 시간을 가지는 프로세스가 왔을 때 프로세스를 빼앗기는 방식입니다.
위에서 말했던 Optimal한 방식이 이 두가지 중 어떤것이냐 하면 preemptive 버젼이 더 적합합니다.
그렇기 때문에 이 방법을 Shortest-Remaining-Time_First(SRTF)라고도 부릅니다.
-참고 KOCW 이화여자 대학교 반효경 교수님 : 운영체제 강의