[OS] CPU Scheduling

 

Preemptive and Nonpreemptive Scheduling

CPU-scheduling은 다음과 같은 네가지 상황에서 일어난다.

1. I/O request나 wait()에 의한 running state -> waiting state

2. Interrupt에 의한 running state -> ready state

3. completion of I/O 와 같은 경우에 의한 waiting state -> ready state

4. 프로세스 종료시.

 

1, 4와 같은 경우에는 프로세스는 무조건 실행할 프로세스를 찾아서 core에 넣어야 한다.

하지만 2, 3번과 같은 경우에는 어떤 프로세스를 넣을지 결정해야 한다.

 

1, 4의 경우에서만 사용할 수 있는, 프로세스 종료시와 waiting state로 변할 경우에 core에 다른 실행 프로세스를 넣어주는 방식은 비선점형 스케줄링 이라 한다.

2, 3과 같은 경우에 다른 프로세스를 core에 넣어서 실행하는 방식을 선점형 스케줄링 이라 한다.

 

비선점형 스케줄링은 커널의 구현이 간단하지만, multiprocess, real-time 구현 시 적합하지 않다.

선점형 스케줄링은 공유자원에 따른 race condition을 막는것에 신경을 써야 한다.

 

Dispatcher

CPU scheduler에 선택된 프로세스에 core의 제어권을 주는 요소이다.

PCB를 적재하고, Context Switch를 유발하므로 최대한 빠른 시간 내에 작동하는 것이 좋다.

 

 

Scheduling Algorithm

FCFS(first come, first serve)

비선점형 스케줄링 기법.

pros - 구현이 쉽다.

cons - 평균 대기시간이 길어진다. I/O bound, CPU bound process를 구별해서 스케줄링 하지 못한다.

 

Shortest-Job-First Scheduling

waiting time의 개념에서 최적인 알고리즘이다.

하지만, 각 프로세스의 CPU burst time을 알 수 없기 때문에, 구현이 불가능하다.

기하급수평균으로 프로세스의 CPU burst time을 예측하는 방법으로 구현해야한다.

 

선점/비선점 둘다 가능한데, process 도착시간을 기준으로 burst time이 적은 프로세스가 core를 선점하도록 하면 선점 스케줄링이 가능하다.

 

Round Robin

FCFS를 기반으로 선점할 수 있도록 만든 알고리즘으로, Time quantum이라는 시분할 단위를 정해 특정 프로세스가 특정 시분할 단위만큼 core에 할당될 수 있도록 한다.

프로세스가 시분할 단위만큼 core에 할당되었다면, ready queue의 마지막으로 다시 보내 처리하도록 하는 알고리즘이다.

 

시분할 단위는 Context Switch time에 따라서 정해져야 한다.

 

Priority Scheduling

SJF가 우선순위 스케줄링의 일종이다.

각각의 프로세서의 기준에 따라 우선순위를 정하고, 우선순위가 높은 순서대로 프로세스를 처리하는 스케줄링 방식이다.

 

Starvation, indefinite block이 발생할 수 있다.

Starvation - 우선순위가 낮은 프로세스가 계속 대기하는 현상.

indefinite block - 우선순위가 높은 프로세스가 blocking 되어 CPU가 계속 대기하는 상황.

 

Aging을 통해 우선순위가 낮은 프로세스가 대기시간에 비례하여 우선순위를 높이는 방법을 고려하면 이 두가지 문제를 해결할 수 있다.

 

마찬가지로 선점/비선점 둘다 가능하다.

 

Multilevel Queue Scheduling

PS + RR로 좋게 구현할 수 있다.

상기에 서술한 PS, RR 전부 단일 큐를 통해 우선순위를 계산하므로, 단일 선형 큐라는 가정에서 우선순위를 계산하는데 O(N), N = queue size가 걸린다.

우선순위에 따른 여러개의 Queue를 두고, 우선순위가 높은 Queue에 있는 프로세스들은 RR로 구현하는 방식이다.

더 확장해서 프로세스의 단위에 따라서 우선순위를 둘 수 있다.

Foreground Process(interactive process)는 RR, Background Process(batch Process)는 FCFS로 구현하는 등의 우선순위 별 스케줄링 기법을 다르게 해서 스케줄링을 최적화 할 수 있다.

 

Multilevel Feedback Queue Scheduling

MQS는 우선순위가 낮은 프로세스가 Starvation이 발생할 수 있다는 문제가 있다.

이는 무조건 Queue가 분리되어있다는 관점에서 나온다.

그러므로 각각의 Queue가 상호작용할 수 있도록 하는 관점에서 MFQS가 나왔다.

 

특정 프로세스가 너무 많은 CPU burst time이 걸린다면, 우선순위를 낮추거나 너무 오래 기다렸다면 우선순위를 높이는 방식으로 구현된다.

 

MFQS는 스케줄링 구현에

1. 큐의 개수

2. 각각의 큐의 스케줄링 알고리즘

3. 높은 우선순위로 프로세스를 올리는 기준

4. 낮은 우선순위로 프로세스를 내리는 기준

5. 어떤 프로세스가 서비스 되고 싶을때, 어떤 대기열에 들어갈지 설정하는 기준

 

이 5개 요소가 전부 고려되어야 하므로 구현하기 어렵다.