Chapter 4. Scheduling

1. Queue

OS는 제한된 Resource를 프로세스들에게 적절히 분배하기 위해 스케줄링을 활용한다. 이때 프로세스들은 PCB 형태로 3가지 큐에 존재한다.

• Job Queue : 시스템 내에 존재하는 모든 프로세스의 집합
• Ready Queue : 메모리에 적재되있고, CPU를 할당 받기 전까지 기다리는 프로세스 집합
• Device Queue : Device I/O 작업을 완료할때까지 기다리는 프로세스의 집합

[그림 1] 스케줄링 큐

2. Scheduler

1. Long-term Scheduler

= Job Scheduler

프로그램을 실행시키고 디스크에서 메모리로 로드할 프로세스를 선택한다. 즉, 프로세스 상태를 New에서 Ready로 바꿀 프로세스를 선택하는것과 동일하다. 이때, 모든 프로세스들을 New에서 Ready로 바꾸면 다음과 같은 문제가 발생한다.

• 사용이 적은 프로세스들 또한 메모리에 적재되어, 메모리 공간의 낭비가 발생한다.
• 많은 프로세스들이 CPU를 할당 받기 전까지 오랫동안 대기하는 문제가 발생한다. 
• 메모리를 많이 사용하여 그만큼, Disk와 Memory 사이의 Swap이 자주 발생하여 성능의 문제가 발생한다.

 

2. Short-term Scheduler

= CPU Scheduler

Ready Queue에 존재하는 프로세스 중 어떤 프로세스 상태를 Ready에서 Running으로 바꿀지 결정한다. 즉, 어떤 프로세스에게 CPU를 할당 할지를 결정한다.

 

3. Medium-term Scheduler

= Swapper

프로세스 상태가 wait에서 ready로 넘어가지 못하거나 혹은 ready에서 running 상태로 넘어가지 못 할 경우 실행은 되지 않고 메모리만 차지하는 비효율적인 상황이 발생한다. 이러한 프로세스를 하드디스크로 쫓아내고(Swap-out), 이후 다시 상황이 좋아지면 Swap in을 통해 다시 메모리로 로드하는 스케줄링 기법이다. LRU와 같은 메모리의 Victime Frame을 선정하는 스케줄링이 포함된다.

3. CPU Scheduler

1. FCFS [First Come First Served]

CPU를 먼저 요청하는 process가 CPU를 먼저 할당 받는 방식이다. 일단 CPU를 잡으면 작업이 완료될 때까지 CPU를 반환하지 않는다. 할당된 CPU가 반활될 때만 스케줄링이 일어난다. 즉, 비선점형 스케줄링이다. 하지만 CPU 소요시간이 긴 프로세스가 먼저 도달하면 다른 모든 프로세스가 오랫동안 기다리는 convoy effect 문제가 발생한다.

 

2. SJF [Shortest Job First]

프로세스 도착 순서에 상관 없이 CPU burst time이 가장 짧은 프로세스에게 CPU를 먼저 할당하는 방식이다. 비선점형 스케줄링으로 먼저 실행된 태스크가 있다면 해당 태스크 완료 후에 스케줄링이 일어난다. 즉, 중간에 CPU burst time이 더 적은 태스크가 생겨도 스케줄링이 일어나지 않는다.

FCFS의 Convoy effect 문제를 해결하고 응답성이 좀 더 빨라졌지만 'Starvation'의 문제가 존재한다. 극단적으로 CPU 사용이 짧은 태스크를 선호하여, 만약 사용시간이 긴 태스크는 거의 영원히 CPU를 할당받지 못하는 문제가 생긴다.

[그림 2] SJF

 

 3. SRTF [Shortest remaining time first]

CPU burst time이 가장 짧은 프로세스에게 CPU를 먼저 할당한다. 선점형 방식으로, 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 Context Swiching이 발생한다. 즉, 태스크가 완료될 때, 새로운 태스크가 생길때마다 스케줄링이 일어나 SJF보다 응답성이 우수한 장점이 있다. 물론 잦은 Context Switching으로 오버헤드가 발생한다.

[그림 3] SRTF

4. Priority Scheduling

우선순위가 가장 높은 프로세스에게 CPU를 할당한다.

선점형 스케줄링 방식 : 더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU를 선점한다.

비선점형 스케줄링 방식 : 더 높은 우선순위의 프로세스가 도착하면 Ready Queue의 Head에 넣는다.

 

하지만 우선순위가 너무 낮은 프로세스는 오랫동안 CPU를 점유 못하는 Starvation 문제가 발생할 수 있다. 이를 Aging 기법을 이용하여 해결한다. 일정 시간마다 프로세스의 우선순위를 높이는 기법이다. 예를 들어 15분마다 Ready Queue에 존재하는 프로세스의 우선순위를 1씩 증가한다.

 

5. Round Robin Scheduling

FCFS 스케줄링 기반으로 CPU를 프로세스에게 할당하지만, 각 프로세스는 동일한 'time quantum'을 갖는다. 선점형 방식으로 태스크를 수행하다 할당 시간이 되면 ready queue의 제일 뒤에 가서 다시 줄을 선다.

'time quantum'을 가짐으로 시스템의 응답성이 우수하고, 'Convoy Effect', 'Starvation' 문제 역시 해결할 수 있다. 응답성이 우수한 장점으로 현 OS는 시분할 시스템을 위해 RR방식을 사용한다. 물론 다른 방식보다 Context Switching이 자주 발생해 Overhead는 증가한다.

 

이때, time quantum이 너무 크면 FIFO 구조와 동일하고, 너무 작으면 Context Swiching이 자주 발생하여 Overhead가 심해진다. 보통 CPU Burst 의 80%보다 짧아야하는것으로 알려져있다.

 

6. Multilevel Queue Scheduling

프로세스 종류에 따라 여러 종류의 그룹으로 나누고, 해당 그룹에 맞는 우선 순위, 스케줄러를 설정하는 방식을 말한다.

예를 들어, 구글링을 하면서 파일을 다운로드하는 상황을 가정해보자. 구글링 과정에서 UI 결과창이 바로 바로 안 뜨면 사람은 답답해 창을 닫는다. 하지만 뒤에서 진행되는 파일 다운로드는 오래 걸려도 크게 신경을 쓰지 않는다. 보통 foreground는 background보다 응답성을 더욱 중요시 여겨, RR 스케줄링을 사용함과 동시에 우선순위를 높게 둔다. 반면 background에서 수행되는 작업은 FCFS로 구조를 간단하게 진행한다.

즉, 여러개의 큐들을 두고, 프로세스 종류에 맞는 큐로 이동시킨다. 이때 큐에 적합한 스케줄러와 우선순위를 부여한다.

 

하지만 큐 사이의 이동이 불가능 하여, 우선순위가 낮은 큐에서 호출 빈도가 적은 작업은 정말 오랫동안 사용을 못하는 'Starvation' 문제가 발생한다.

[그림 4] Multilevel Queue

7. Multilevel Feedback Queue Scheduling

Multilivel Queue 방식에 추가적으로 프로세스들이 '큐 사이의 이동을' 가능하게 만든 스케줄링이다. 어떤 프로세스가 CPU를 너무 오래 사용하면 낮은 우선순위의 큐로 보낸다. 반면 오랫동안 낮은 우선순위의 큐에서 대기하는 태스크는 높은 우선순위의 큐로 보낸다. 이러한 방식을 통해 'Starvation' 문제를 해결한다.

 

아래 사진을 참조하여 예시를 들어보자. 어떤 프로세스가 time quanum 8 안에 완료되면 괜찮지만 해당 시간을 넘어서면 해당 2배의 time quantum을 갖는 큐로 전송하고 해당 time quantum을 또한 넘어서게 되면 최하단의 FCFS 방식의 스케줄링 큐에 들어가게된다.

[그림 5] Multilevel Feedback Queue