1. Queue
OS는 제한된 리소스를 프로세스들에게 적절히 분배하기 위해 스케줄링을 활용합니다. 이때 프로세스들은 PCB 형태로 3가지 큐에 존재합니다.
- Job Queue : 시스템 내에 존재하는 모든 프로세스 집합
- Ready Queue : 메모리에 적재되있고 CPU를 할당 받기 전까지 기다리는 프로세스 집합
- Device Queue : Device I/O 작업을 완료할때까지 기다리는 프로세스 집합
2. Scheduler
[1] Long-term Scheduler
= Job Scheduler
프로그램을 실행하고 디스크에서 메모리로 로드할 프로세스를 선택합니다. 즉 프로세스 상태를 New에서 Ready로 바꿀 프로세스를 선택하는것과 동일합니다. 이때, 모든 프로세스들을 New에서 Ready로 바꾸면 다음과 같은 문제가 발생합니다.
- 사용이 적은 프로세스들 또한 메모리에 적재되어 메모리 공간이 낭비됩니다.
- 많은 프로세스들이 CPU를 할당 받기 전까지 오랫동안 대기하는 문제가 발생합니다.
- 메모리를 많이 사용하여 그만큼 디스크와 메모리 사이의 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을 선정하는 스케줄링이 포함됩니다.
CPU Scheduler
[1] FCFS (First Come First Served)
CPU를 먼저 요청하는 프로세스가 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를 할당받지 못하는 문제가 생깁니다.
[3] SRTF (Shortest Remaining Time First)
CPU burst time이 가장 짧은 프로세스에게 CPU를 먼저 할당합니다. 선점형 방식으로, 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 Context Swiching이 발생합니다. 즉, 태스크가 완료될 때 혹은 새로운 태스크가 생길때마다 스케줄링이 일어나 SJF보다 응답성이 우수한 장점이 있습니다. 물론 잦은 Context Switching으로 오버헤드가 발생하며 여기서도 Starvation 문제가 존재합니다.
[4] Priority Scheduling
우선순위가 가장 높은 프로세스에게 CPU를 할당합니다.
-
선점형 스케줄링 방식 : 더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU를 선점합니다.
-
비선점형 스케줄링 방식 : 더 높은 우선순위의 프로세스가 도착하면 Ready Queue의 Head에 넣습니다.
하지만 우선순위가 너무 낮은 프로세스는 오랫동안 CPU를 점유 못하는 Starvation 문제가 발생할 수도 있다. 이를 Aging 기법으로 해결합니다. 일정 시간마다 프로세스의 우선순위를 높이는 기법입니다. 예를 들어 15분마다 Ready Queue에 존재하는 프로세스의 우선순위를 1씩 증가시킵니다.
[5] Round Robin
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' 문제가 발생합니다.
[7] Multilevel Feedback Queue Scheduling
Multilivel Queue 방식에 추가적으로 프로세스들이 '큐 사이의 이동을' 가능하게 만든 스케줄링입니다. 어떤 프로세스가 CPU를 너무 오래 사용하면 낮은 우선순위의 큐로 보냅니다. 반면 오랫동안 낮은 우선순위의 큐에서 대기하는 태스크는 높은 우선순위의 큐로 보냅니다. 이러한 방식을 통해 'Starvation' 문제를 해결합니다.
아래 사진을 참조하여 예시를 들어봅니다. 어떤 프로세스가 time quanum 8 안에 완료되면 괜찮지만 해당 시간을 넘어서면 해당 2배의 time quantum을 갖는 큐로 전송하고 해당 time quantum을 또한 넘어서게 되면 최하단의 FCFS 방식의 스케줄링 큐에 들어가게됩니다.
