CPU 스케쥴링 법칙
FCFS (First-Come, First-Served)
CPU를 사용하기 위해 Process(줄여서 P라고 하겠다.)들은 CPU큐에서 대기하게 된다. P1, P2, P3 중 가장 먼저 도착한 순서대로 CPU를 사용하게 되는데, 이것을 FCFS 법칙 이라고 한다.
도착한 순서가 P1, P2, P3 라고 가정해 보자.
P1이 가장 먼저 도착하여 CPU를 24초동안 사용했다면, P2는 CPU를 이용하기 위해 24초를 기다리게 될 것이다. 그 후 P1이 I/O 처리를 하러 CPU를 나가게 되면, P2 차례가 되는데 CPU를 3초동안 이용했다고 하자. 그럼 P3은(P3의 CPU 사용시간은 3초이다.) 총 P1이 사용한 시간 24초 + P2가 사용한 3초 를 더해서 총 27초를 기다리게 된다. 3초를 사용하기 위해 27초를 기다린 것이다.
그럼 P1, P2, P3가 CPU를 사용하기 위해 기다린 시간의 평균을 내보자면
Average waiting time : (0 + 24 + 27)/3 = 17 로 산출이 된다.
하지만 이 방법이 공평하지만 효율적이지는 않다.마치 화장실 칸이 한칸인데, 맨 처음으로 들어간 사람이 시간을 너무 오래 끌어서 줄이 길어지는 상황이랑 같다.그럼 어떻게 해야 효율적이 될 수 있을까? 기다린 시간을 어떻게 줄여줄 수 있을까?
SJF(Shortest-Job-First)
만약 P2, P3, P1 순으로 도착했다고 가정해 보자.CPU 사용시간은 위에 서술한 시간과 똑같다.(P1 = 24초, P2 = 3초, P3 = 3초)P2는 제일 먼저 도착했으니 기다린 시간이 0초, P3은 3초, P1은 6초를 기다리게된다.CPU를 사용하기 위해 기다린 시간의 평균을 내보자면 Average waiting time : (0 + 3 + 6)/3 = 3 으로 산출이 된다.
FCFS 법칙을 적용했을 때의 17초에 비하면 확연히 줄어든 시간이다. 이렇게 사용시간이 짧은 순서부터 CPU를 사용하게 하는 효율적인 방법을 SJF 법칙이라고 한다. SJF는 minimum average waiting time을 보장한다.
하지만 이 방법도 문제는 있다. Starvation(기아현상) 발생이 가능하다. 이용시간이 긴 P1은 계속 기다려야 하는 것이다. P2, P3의 이용시간이 끝나길 기다리는 사이에 P1보다 이용시간이 짧은 P4가 등장한다면, P1은 다시 뒤로 밀리게 된다. FCFS의 장점이 형평성에 어긋난다.
운영체제는 효율성과 형평성을 모두 고려해야 하기 때문에, 한 방법만을 고수할 수는 없다. 그래서 형평성과 효율성 둘 다를 수용하기 위한 방법이 등장한다. 현재 가장 많이 사용하는 아이디어다.
RR(Round Robin)
이제 P1, P2, P3는 도착한 순서대로 각 프로세스들이 CPU를 얼마나 쓰려고 하는 건 상관 없이, 한번에 사용할 수 있는 시간은 정해져 있다. P1이 CPU를 더 오랫동안 쓰고 싶어하더라도, 시간이 정해져 있기 때문에 할당시간이 지나면 다시 CPU 큐로 대기해야된다. 쓰고 싶어하는 시간이 길면 길수록 CPU 사용시간, 대기시간이 계속 반복된다. 각 프로세스들은 사용하고자 하는 시간에 비례해서 그만큼만 기다리면 되는 것이다.
참고 : kowc강의 - 운영체제(이화여대 반효경 교수님)
