CPU가 하나의 프로세스 작업이 끝나면 다음 프로세스 작업을 수행해야 한다. 이 때, 다음 프로세스가 어느 프로세스인지를 선택하는 알고리즘을 CPU Scheduling 알고리즘 이라고 한다. 간단히 생각해보면 먼저 온 프로세스가 먼저 실행되는 것이 가장 좋을 것 같지만, 실제 환경에서는 여러가지 단점들이 존재하기 때문에 반드시 이 방법이 좋다고는 할 수 없다. 그렇므로 여러가지 알고리즘이 존재하는데 오늘은 이 알고리즘들에 대하여 알아보자.
스케줄링의 목적
- 데이터의 처리량을 높이기 위해
- CPU utilization을 높이기 위해
- 응답시간을 빠르게 하기 위해
스케줄링의 타입
우선 처리해야 하는 프로세스들의 대기장소인 Queue에 대하여 간략하게 알아보자.
- Job Queue : 현재 시스템에 있는 모든 프로세스의 집합
- Ready Queue : 현재 메모리 내에 있으면서 CPU를 기다리는 프로세스의 집합
- Device Queue : Device I/O작업을 대기하고 있는 프로세스의 집합
1. 장기 스케줄링(Long-term scheduling)
- 어떤 프로그램을 Ready Queue에 진입시킬것인가에 대한 결정을 함.
장기 스케줄러는 메모리에 동시에 올라가 있는 프로세스의 수를 조절하는 역할을 한다. 장기 스케줄러가 Ready Queue에 어떤 작업들을 올릴지는 여러가지 알고리즘에 의해 결정되는데, 이 알고리즘들은 이후에 살펴볼 것이다.
2. 중기 스케줄링(Medium-term scheduling)
- 메모리에 적재된 프로세스의 수를 관리한다.
메모리에 많은 수의 프로세스가 적재되어 공간이 협소해지게 되면, CPU가 당장 필요한 주소 공간도 부족해진다. 이 경우에 메모리에 적재된 프로세스들이 디스크로 I/O되는 경우가 수시로 발생하게 되어 시스템의 성능이 매우 저하된다.
- 위와 같은 경우에 메모리에 올라와 있는 프로세스 중 일부에서 메모리를 통째로 빼앗아 그 내용을 디스크에 swap-out 시킨다.
- 프로세스를 swap-out 시키는 순서는 당장 CPU를 배정받을 가능성이 없는 suspended(봉쇄된) 상태의 프로세스들 부터이다.
- 장기 스케줄러와 마찬가지로, 메모리에 올라와 있는 프로세스의 수를 조절하는 역할을 한다.
3. 단기 스케줄링(Short-term scheduling)
-
우리가 흔히 dispatcher라고 알고 있는 스케줄러이다.
어떤 프로세스에게 CPU를 할당해 줄 것인지를 결정한다.준비 상태의 프로세스 중에서 어떤 프로세스를 다음 번에 실행 상태로 만들 것인지를 결정한다.
-
특정 Event가 발생할 때마다 단기 스케줄러가 작동하는데 그 Event의 예시로는 다음이 있다.
1. Clock interrupts
2. I/O interrupts
3. Operating System calls
4. Signals
CPU 스케줄링 알고리즘
(대상은 Ready Queue에 있는 프로세스이다.)
✔미리 알고가자
👀Preemptive(선점) VS Nonpreemptive(비선점)란?
'선점'은 프로세스가 CPU를 점유하고 있는 동안 I/O나 다른 인터럽트가 발생한 것도 아니고 모든 작업을 끝내지도 않았는데, 다른 프로세스가 해당 CPU를 강제로 점유할 수 있는 것이다.
'비선점'은 '선점'과 반대이다. 한 프로세스가 한 번 CPU를 점유했다면, 그 프로세스의 I/O나 다른 인터럽트의 발생 또는 프로세스의 종료 전까지 다른 프로세스가 CPU를 점유하지 못하는 것이다.
👏 First Come First Serve(FCFS)
특징
- 프로세스들은 먼저 온 순서대로 CPU를 할당받는다.
- 비선점형(Nonpreemptive)이다.
장점
- 이해하기 쉽고, 코딩하기 쉽다.
- 오직 하나의 linked list를 요구하기 때문에 대기시간을 예측하는데 유용하다.
문제점
- 소요시간이 긴 프로세스가 먼저 도달하면, 시간적 측면에서 효율성이 떨어진다.
- 실제 시스템에서 성능이 떨어진다.
👏 Shortest Job Next (SJN)
특징
- 다른 프로세스가 먼저 도착했어도 CPU사용 시간이 짧은 프로세스에게 먼저 CPU를 할당한다.
- 비선점형(Nonpreemptive)이다.
장점
- 대기시간을 최소화 할 수 있다.
문제점
- 대규모의 job은 우선순위가 뒤로 밀려 CPU를 오래동안 사용하지 못하는 Starvation(굶주림) 현상이 발생한다.
- 프로세스들의 service time을 미리 계산해야 한다는 단점이 있다.
👏 Priority Scheduling
특징
- 우선순위가 가장 높은 프로세스에게 CPU를 할당하는 스케줄링이다. 우선순위는 개발자가 할당해주며 숫자가 작을 수록 우선순위가 높다.
- 프로세스의 중요도를 반영했다는 점에서 의미가 있다.
문제점
- 여전히 굶주림 문제가 발생할 수 있다.
- 우선순위 역전현상이 발생할 수 있다.
해결책
- Starvation 상태의 프로세스의 우선순위를 높여준다.
- 우선순위를 상속해준다.
👏 Round Robin (RR)
특징
- 각 프로세스는 동일한 크기의(길지 않은) CPU 시간 (time quantum) 을 할당받는다.
- 할당된 시간이 지나면, 그 프로세스는 선점당하고 Ready Queue의 제일 마지막에 들어간다.
- time quantum이 q라고 할 때, Ready Queue안에 있는 n개의 프로세스들은 (n-1)q시간 이상을 기다리지 않는다.
장점
- 프로세스가 기다리는 시간이 CPU를 사용한 만큼 증가하므로 공정하다고 할 수 있다.
- 가장 많이 쓰이는 현대의 스케줄링 알고리즘이다.
- CPU사용시간이 랜덤한 프로세스들이 섞여있을 경우에 효율적이다.
문제점?
- time quantum이 너무 커지면 FCFS알고리즘과 다를 바가 없다.
- time quantum이 너무 작아지면, 스케줄러의 목적에는 맞지만, 너무나도 잦은 context switching으로 인해 overhead가 발생한다. 그래서 적당한 time quantum을 설정하는 것이 매우 중요하다.
RR방식이 가능한 이유
프로세스는 자신의 context를 save할 수 있기 때문이다!
👏 Shortest Remaining Time (SRT)
특징
-
SJN방식의 Preemptive 버전이다.
-
새로운 프로세스가 들어왔을 때 현재 프로세스와 들어온 프로세스가 해야할 service time을 비교하여 더 짧은 놈이 선점한다.
문제점
-
스케줄러는 새로운 프로세스가 도착할 때마다 processing time을 계산해야한다.
-
service time이 긴 프로세스가 굶주림 현상을 나타낼 수 있다.
