CPU 스케줄링?
- CPU를 효율적으로 사용하기 위해 운영체제가 CPU의 자원을 어떤 프로세스에게 할당해 줄 지 그 일정을 짜는 것입니다.
- 프로세스는 작업을 진행하기 위해 CPU를 할당받아야 합니다. 하지만 CPU는 하나의 프로세스만 할당이 가능합니다. 따라서 특정 프로세스가 I/O 요청에 의해 대기해야할 경우 CPU는 그저 놀고 있게 됩니다.
- 다중 프로그래밍에서는 이러한 시간을 생산적으로 활용하고자 CPU를 그 프로세스로부터 회수해 다른 프로세스에 할당합니다.
CPU bound vs I/O bound
- 프로세스가 대기 상태에 있다가 CPU를 할당받아 실행하면 CPU burst, 입출력 작업을 하면 I/O burst라고 합니다.
- CPU bound process(CPU 집중 프로세스) : CPU를 많이 사용하여 CPU burst가 많은 프로세스
- I/O bound process(입출력 집중 프로세스) : 입출력을 많이 사용해 I/O burst가 많은 프로세스
- 두 프로세스가 같이 대기상태에 있다면 입출력 집중 프로세스에 먼저 CPU를 할당시키는 것이 더 효율적입니다. 왜냐하면 입출력 집중 프로세스는 CPU를 빠르게 쓰고 입출력 버스트를 하러 나가기 때문에 다른 프로세스가 오래 기다리지 않아도 되기 때문입니다.
비선점형 스케줄링
FCFS (First Come First Served)
- 큐에 도착한 순서대로 CPU를 할당합니다.
- 먼저 큐에 도착한 프로세스의 처리 시간이 길어 CPU 처리 시간이 짧고 더 중요한 작업을 기다리게 할 수도 있습니다.
- 이를 Convoy Effect라고 합니다.
SJF (Shortest Job First)
- 프로세스를 처리 시간이 짧은 순서대로 처리하는 방식입니다.
- 이 방식은 처리 시간이 긴 프로세스들이 짧은 프로세스들이 올때마다 우선 순위가 뒤로 밀려나 영원히 실행되지 않을 수도 있습니다.
- 이를 Starvation 상태라고 합니다.
HRN (Hightest Response-ratio Next)
- SJF 스케줄링 방식에서 발생할 수 있는 기아 상태를 해결하기 위해 고안된 방식입니다.
- 기다린 시간에 비례하여 우선순위를 조금씩 높여 언젠간 실행이 되게 하는 기법을 사용합니다.
- 이를 Aging기법이라고 합니다.
우선순위 (Priority)
- 대기 중인 프로세스들에게 우선순위를 부여하여 우선순위가 높은 순서대로 처리하는 방식입니다.
- 동적 혹은 정적으로 우선순위를 매길 수 있고, 선점형으로도 구현할 수 있습니다.
선점형 스케줄링
SRT (Shortest Remaining Time)
- SJF 스케줄링 방식을 선점 스케줄링 방식으로 변경한 기법입니다.
- 선점 스케줄링 방식이기 때문에 CPU를 점유 중인 프로세스보다 남은 CPU 처리 시간이 짧은 프로세스가 Ready Queue에 들어올 경우 새로 들어온 프로세스가 기존 프로세스의 CPU 점유를 빼앗아 점유할 수 있습니다.
라운드로빈 (Round-Robin)
- FCFS 스케줄링 방식에 선점 스케줄링 방식과 Time Quantum 개념을 추가한 방식입니다.
- Time Quantum이란 타이머와 비슷한 개념으로, 정해진 Time Quantum이 지나면 해당 프로세스를 Ready Queue의 가장 뒤로 보냅니다.
- Time Quantum을 높게 설정하면 FCFS방식과 비슷하게 작동하며 Convoy Effect가 일어나고, Time Quantum을 너무 작게 설정하면 Context Switching이 자주 일어나 오버헤드가 커집니다.
다단계 큐 (Multi-Level Queue)
- 프로세스를 어떤 프로세스냐에 따라서 여러 종류의 그룹으로 나누고, 그룹마다 Queue를 두는 방식입니다.
- 각 큐는 절대적인 우선순위를 가지며 우선순위가 높은 큐에 존재하는 프로세스부터 실행됩니다. 우선순위가 높은 큐가 비어있어야 그 아래 단계의 큐를 실행할 수 있습니다.
- 프로세스가 생성될 때 정해지는 우선순위에 따라서 해당 우선순위에 해당하는 준비 큐에 등록됩니다.
- 작업은 한 큐에서 다른 큐로 옮겨지지 않기 때문에 스케줄링 부담이 적지만 융통성이 떨어집니다.
- 큐 간의 절대적인 우선순위 때문에 startvation이 발생할 수도 있습니다. 이 경우에 큐들 사이에 시간을 나누어 사용할 수도 있습니다.
