Scheduling

FIFO (First in, First out)

FIFO(First-in-First-out,선입선출) 또는 FCFS(First-Come-First-Served,FCFS) 스케쥴링이다.

말그대로 먼저 도착한 process부터 cpu를 할당받는 것이다.

FIFO방식의 가장 큰 문제점은 작업 실행 시간이 긴 process가 먼저 왔을때, 뒤에 있는 process들이 이를 끝나기를 기다려야 한다는 점이다. 이를 convoy effect라고 부른다.

SJF(Shortest Job First)

가장 짧은 실행 시간을 가진 작업을 먼저 실행시킨다.

FIFO에서 가지는 convoy-effect문제를 해결할 수 있으나, 모든 작업이 동시에 도착한다는 가정하에서다. 즉 긴 작업이 짧은 작업보다 먼저 도착한다면 여전히 convoy-effect문제가 발생할 수도 있다.

예를 들면 위처럼 작업시간이 긴 A라는 process가 먼저 도착했고, 그 뒤에 작업 시간이 짧은 B,C가 도착하였다. SJF는 비선점형이므로, A가 끝날떄까지 기다려야 한다.

위의 FIFO와 SJF는 비선점형 scheduler로 각 작업이 종료될떄까지 계속 수행된다. 이제부터 정리할 스케쥴링 알고리즘은 선점형 방식으로 작업이 종료되기 전에 다른 작업으로 전환이 가능하다

STCF (Shortest Time-to-Completion First)

SJF 스케쥴링 알고리즘에 선점기능을 추가한 알고리즘이다. 즉 새로운 작업이 도착하면 현재 실행중인 작업의 잔여 실행시간과 새로운 작업의 작업 실행 시간을 비교해서 , 더 짧은 작업을 스케쥴링한다.

STCF 방식은 스케쥴링 평가 기준이 단지 반환 시간 하나라면 좋은 알고리즘이겠지만, 응답 시간 (response time) 측면에서는 성능이 떨어질 수 있다.

응답시간 = 작업이 처음으로 도착하는 시점 - 작업이 처음으로 스케쥴 될 시점

• STCF,SJF,FCFS 방식은 모두 작업의 실행시간을 사전에 알고 있다고 가정한다.

Round Robin

응답 시간 문제를 해결하기 위해서 Round Robin 스케쥴링 알고리즘이 도입되었다. Round Robin 방식은 마찬가지로 선점형 스케쥴러로 일정시간 동안 작업을 실행 한후에 다음 작업으로 전환한다. 이떄 작업이 실행되는 일정 시간을 time slice , scheduling quantum이라 부른다.

위 figure와 같이 SJF 방식은 응답시간이 좋지 않다 반면 Round robin 방식은 매 time slice 마다 context switching을 통해서 응답시간을 빠르게 해준다. 하지만 반환 시간이라는 기준으로 보았을떄, round robin은 SJF 방식보다 좋지 않다.

time slice의 길이가 round robin 성능에 중요한 영향을 끼치는데, 너무 짧게 설정하면 context switching overhead가 커지나, 응답시간은 빨리질것이다.

입출력 연산시 scheduling

Disk I/O와 같은 작업시에 해당 process는 blocked되고, 다른 process가 scheduling 알고리즘에 따라 스케쥴링되고 cpu를 할당받는다. 입출력 완료시에는 다시 process는 준비 상태가 된다. 즉 입출력 연산과 cpu 사용을 병렬화하여 시스템 사용률을 향상시키는 방법을 사용하고 있다.

MLFQ

앞서 STCF 알고리즘은 작업의 실행시간을 필요로 하는데 이 실행시간을 실제로는 운영체제가 미리 알 수가 없고, 평균 응답 시간은 Round Robin 방식에 의해 떨어진다. 반면 RR 알고리즘은 작업의 실행시간을 필요로 하진 않고 평균 응답 시간도 짧지만 반환 시간은 매우 느리다라는 단점을 가지고 있었다.

MLFQ는 작업의 실행시간을 미리 알지 않으면서도 , 응답시간을 최소화하고 동시에 반환 시간을 최소화하기 위한 알고리즘이다.

MLFQ 규칙

• MLFQ는 여러 개의 Queue 로 구성되며 , 각각 다른 우선순위에 배정되며, 실행 준비가 된 process는 이 중 하나의 큐에 존재한다.

• 우선순위가 더 높은 process가 먼저 수행되며, 우선순위가 같다면 (같은 queue에 있다면) Round-Robin 알고리즘을 적용한다.

• 일단 process가 실행 준비상태가 되면 , 최상위 (가장 우선 순위가 높은) queue에 배치된다.

• process가 지정된 queue에서 배정받은 시간 (time quantuam값) 을 소진하면 작업의 우선 순위는 감소한다.

• 일정 주기 S 가 지난 후에 시스템의 모든 process는 최상위 queue로 이동된다.

MLFQ는 process가 I/O작업을 많이 수행하는 I/O bound process 인지 또는 cpu 만 길게 사용하는 cpu-bound process 인지에 대한 사전 정보 없이, 작업의 실행을 관찰하고 그에따라 우선순위가 지정되는 알고리즘을 가지고 있다.

예를 들면 i/o bound process는 응답시간이 중요한데, time quantuam값을 소진하기 전에 cpu를 양도하면 같은 queue에 배치된다. 즉 우선순위가 높은 상태로 유지가 되는 반면, cpu bound process는 점차적으로 time quantuam값을 소진하고 낮은 우선순위를 가진 queue에 배치된다.

그렇다고 cpu bound process가 starvation되는 것은 아니다. 규칙 5번쨰를 보면 일정 주기 S가 지난 후에는 cpu-bound process나 i/o bound process모두 최상위 queue로 이동되기 떄문이다.

위와 같이 MLFQ를 사용하는 경우에 사용자 작업은 가장 높은 우선순위를 얻지 못하게 하고 중요한 운영체제 작업을 위해 높은 우선순위는 예약해둔다.

사용자 작업도 우선순위를 변경할 수 있는데, linux에서는 nice 명령어를 통해서 우선순위를 변경할 수 있다.

MLFQ는 BSD UNIX와 Solaris , Window 운영체제등을 포함한 다양한 운영체제에서 기본 스케쥴러로 사용되고 있다.