프로세스 스케줄링

스케줄링은 다중 프로그래밍을 가능하게 하는 운영체제의 동작 기법이다.

단일프로세서에서는 한 번에 한 프로세스만 실행할 수 있으므로 프로세스가 CPU를 사용하지 않을 때에는 다른 프로세스를 실행하여 CPU의 효율을 높이는 것을 스케줄링을 통해 실현할 수 있다.

 

스케줄링 알고리즘에는 FIFO, SJF, 우선순위, MLQ 등이 있다.

 

FIFO/FCFS

여러 알고리즘에 쓰이는 FIFO는 굉장히 유명하기 때문에 많은 사람들도 알고 있을 것이다.

먼저 들어온 프로세스를 먼저 처리하는 방식이다. 대표적으로 Queue가 있다.

먼저 들어온 프로세스를 먼저 처리하는 이 방식은 굉장히 직관적이나 중요한 작업을 먼저 처리할 수 없고, 대기시간이 길어질 수 있다. 

Real time 시스템에 부적합하다.

 

SJF(Shortest Job First Scheduling)

SJF는 CPU를 적게 사용하는 프로세스부터 먼저 처리한다. FIFO의 대기시간이 길어지는 문제를 해결할 수 있는 방법이다.

하지만 SJF 방식은 현재 컴퓨터 방식에는 적용하기가 어렵다는 문제가 있다.

SJF 방식을 적용하려면 CPU burst time을 알아야 한다. 하지만 프로세스가 어떤 CPU burst를 가지는지 CPU가 수행하는 동안에는 알 수가 없다. 그렇기 때문에 적용하기가 어려움.

 

SJF에는 두 가지 방식이 있다. preemptive(선점식), non-preemptive(비선점식)

다만 preemptive SJF 방식은 따로 SRT(Shortest Remaining Time Scheduling) 방식이라고 부른다.

 

선점식 방식은 하나의 프로세스가 CPU를 점유하고 있을 때 다른 프로세스가 프로세서를 빼앗을 수 있는 방법을 말한다.

선점식 SJF 방식인 SRT는 현재 처리하고 있는 프로세스보다 더 CPU burst time이 적은 프로세스를 발견하면 그 프로세스로 넘어가 처리한다.

이러한 선점식은 빠른 응답 시간을 요구하는 대화식 시스템에 유용하지만 많은 오버헤드를 초래한다.

 

SJF 방식은 비선점식이므로 이미 할당된 CPU를 프로세스가 강제로 빼앗을 수 없다. 공정한 방식이지만 대화식 시스템에 유용하지 않다.

 

우선순위 스케줄링(Priority Scheduling)

우선순위 스케줄링은 우선순위가 높은 프로세스를 먼저 처리한다.

우선순위는 내부적으로 혹은 외부적으로 정의될 수 있으며 만약 우선순위를 CPU burst로 한다면 우선순위 스케줄링은 곧 SJF처럼 될 수도 있다.

우선순위 스케줄링도 선점식, 비선점식 방식으로 나눌 수 있다.

 

단점으로는 우선순위가 낮은 프로세스는 starvation(indefinite blocking) 상태에 빠질 수 있다. 우선순위가 낮기 때문에 우선순위가 높은 프로세스가 계속 들어온다면 낮은 프로세스는 처리되지 못하고 무한히 기다리는 starvation 상태에 빠지게 되는 것이다.

 

라운드 로빈(RR) 스케줄링

FIFO 스케줄링 기법을 preemptive 기법으로 구현한 스케줄링 방법이다.

FIFO 방식을 그대로 따르되, 시간 할당량(Time Slice)만큼만 번갈아가며 처리한다. 만약 할당량을 다 소비하고도 작업이 끝나지 않은 프로세스는 대기 큐의 맨 뒤로 되돌아간다.

대화식 시분할 시스템에 적합하다.

 

다단계 피드백 큐(Multilevel Feedback Queue) 스케줄링

여러 개의 대기 큐를 두어 짧은 작업이나 입출력 위주의 작업을 먼저 실행시켜서 끝내버리도록 하는 방식이다.

각 큐마다 시간할당량이 다르게 존재하며 낮은 큐일수록 시간할당량이 커진다. 그리고 각 큐마다 RR이나 FCFS등 독자적 스케줄링이 가능하다.

CPU를 시간할당량만큼 사용한 프로세스는 낮은 큐로 이동되며 맨 마지막 큐에 도달하게 되면 RR을 사용하여 모두 처리될때까지 반복한다.

preemptive 방식이다.

 

+MLFQ : MLQ + 큐를 옮겨탈 수 있음

+HRN : 짧으면서도 오래 대기한 것을 우선순위줌.(aging)