[OS] CPU Scheduling

CPU Scheduling 은 멀티프로그래밍 OS 의 기초가 된다. 

최신 OS 에서 실제로 OS에 의해 스케줄링 되는 것은 프로세스가 아닌 kernel-level threads 이다. (kernel-level thread 에 대해서는 Thread 에서 언급 예정)

그렇지만 프로세스 스케줄링과 스레드 스케줄링은 종종 같은 의미로 사용되며, 일반적인 스케줄링 개념을 논의할 때는 보통 프로세스 스케줄링을 사용한다. 

 

Process Concept

process execution 은 CPU execution 과 I/O wai 의 순환으로 구성된다

CPU burst : Cycle of CPU execution

I/O burst : Cycle of I/O wait

process execution 은 CPU burst 로 시작되어 I/O burst 가 따라오고 이 과정이 반복된다.

I/O bound process 는 많은 수의 짧은 CPU bursts

CPU bound process 는 적은 수의 긴 CPU bursts

이 분포는 CPU scheduling 알고리즘을 구현할 때 중요하다

 

Process Scheduler

Process Scheduler 는 다음의 역햘을 한다.

• 실행 준비중인 ready queue 에 있는 프로세스들 중 선택함
• Disipatcher 는 그들 중 하나를 CPU 로 할당함

이때 프로세스에 대해 발생할 수 있는 CPU-scheduling decision들은 아래와 같다.

1. running state -> wait state
2. running state -> ready state
3. wait state -> ready state
4. terminate

 

Non-preemptive scheduling (비선점 스케줄링)

비선점 스케줄링에서 프로세스는  프로세스가 종료되거나 wating state 로 switching 되어 CPU 를 자발적으로 놓아줄 때까지 CPU 를 사용한다. 

1, 4번이 해당한다. 1번의 경우 I/O request 를 처리하기 위해, 4번의 경우 프로세스의 종료로 자발적으로 CPU 를 해제한다.

 

Preemptive scheduling (선점 스케줄링)

선점 스케줄링에서는 실행중인 프로세스를 강제적으로 중단시킬 수 있다.

2, 3 번이 해당하며 1, 4번도 가능하다. 2번의 경우 interrupt 발생이나 time slice 의 만료로, 3번의 경우 I/O 의 완료로 강제로 프로세스가 강제로 중단된다.

거의 모든 최신 OS들은 preemptive scheduling 알고리즘을 사용한다. 하지만, preemptive scheduling 은 race condition 을 야기한다.  

 

Dispatcher

Dispatcher 는 스케줄러에 의해 선택된 프로세스에게 CPU core 의 control 을 주는 모듈이다. 

아래와 같은 역할을 한다.

• switching context
• switching to user mode
• jumping to proper location in the user program to resume that program

Dispatcher 가 한 프로세스를 중지시키고 다른 프로세스를 실행할 때 걸리는 시간을 Dispatch latency 라고 한다. 

 

Scheduling Criteria

CPU scheduling algorithm 을 비교하기 위해 다음과 같은 기준이 사용된다.

CPU utilization

CPU 를 가능한 busy 하게 유지하는 것. idle 이 적을 수록 높은 utilization 을 가

 

Throughput

단위 시간 당 완료되는 프로세스 수

 

Turnaround time

프로세스 생성부터 종료까지 걸린 총 시간. ready queue 대기 시간, CPU 실행 시간, I/O 처리 시 등의 합

 

Waiting time

프로세스가 ready queue 에서 대기한 총 시간. 

 

Response time 

request 제출 후 첫 번째 response 가 생성될 때까지 걸리는 시간. reponse 를 출력하는 시간이 아님

 

 

Scheduling Algorithms

ready queue 에 있는 프로세스들 중 CPU 에 할당할 프로세스를 선택하기 위해 Scheduling Algorithm 을 사용한다. 

First-Come, First-Served Scheduling (FCFS, FIFO)

CPU 에 먼저 요청한 프로세스가 CPU 에 먼저 할당된다

non-preemptive

FCFS 에 의해 스케줄되는 프로세스들은 FIFO queue 에 의해 관리된다

average waiting time 이 상황에 따라서 길어진다.

 

Short-Job-First Scheduling

각 프로세스들의 다음 CPU burst 길이와 관련이 있다.

CPU 가 사용가능할 때, 다음 CPU burst 가 가장 작은 프로세스를 당한다.

주어진 프로세스들에 최소 average waiting time 을 주므로 optimal 함

Preemptive nonpreemptive 모두 가능

• Non-preemptive : 프로세스에 CPU 가 할당되면, CPU burst 가 끝날 때까지 바뀌지 않음
• Preemptive : 새로운 프로세스의 CPU burst 길이가 현재 실행중인 프로세스의 남은 시간보다 짧을 때 바뀜. Preeeptive SJF scheduling 은 shortest-remaining-time-firs shceduling 이라고도 불림

하지만 다음 CPU burst 의 길이를 알 방법이 없어 SJF를 실제로 구현할 수 없음

 

Priority Scheduling

각 프로세스마다 priority number (integer) 가 할당됨

CPU 는 높은 우선순위를 가진 프로세스를 할당함

SJF 알고리즘도 priority-scheduling 알고리즘의 한 종류. 우선순위가 CPU burst의 역수

 

시스템마다 높은 정수값이 높은 우선순위를 가리킬 수도, 작은 정수값이 높은 우선순위를 가리킬 수도 있음

Internal priority vs external priority

• Internal : 측정가능한 수량을 사용해 설정. ex) 열린 파일 수, 평균 I/O burst 와 평균 CPU burst 의 비율
• external : os 외부의 기준으로 설정 ex) 프로세스 중요도 등

Preemptive nonpreemptive 모두 가능

프로세스가 ready queue 에 도착할 때, 현재 실행중 인 프로세스의 우선순위를 비교함

• Preeptive scheduling : 현재 실행중인 프로세스의 우선순위보다 높으면 바뀜
• Non-preemptive scheduling : 새로운 프로세스를 ready queue의 head에 넣음

 

starvation(indefinit-blocking) :  낮은 우선순위의 프로세스들이 우선순위에 밀려 실행이 되지 않는 문제

aging : 시스템에서 오래 기다린 프로세스의 우선순위를 점차 늘리는 것

 

Round-Robin Scheduling

time sharing system 을 위해 디자인 됨

FCFS scheduling 에 preemption 을 추가한 알고리즘

프로세스들은 같은 우선순위를 가지며 10~100 ms 의 CPU time 의 작은 단위(time quantum or time slice) 를 가진다.

아래의 순서로 RR scheduling 이 동작함

• 새로운 프로세스는 ready 의 tail 에 추가됨
• CPU scheduler 는 ready queue 의 첫번째 프로세스를 선택해 실행
• CPU burst 가 time slice 보다 작으면, 프로세스는 CPU 가 자발적으로 놓아줌
• CPU burst 가 time slice 보다 크면, CPU 에서 time slice 만큼 프로세스를 실행되고 시간이 끝나면 새로운 프로세스로 교체되고 중지된 프로세스는 ready queue 의 끝에 추가됨. 

ready queue 는 circular queue 처럼 수행됨

 

ready queue 에 n 개의 프로세스가 있고 time slice 가 q 라고 가정하자.

• 각 프로세스는 최대 q 시간 마다 CPU time 의 1/n 을 얻음
• 각 프로세스는 다음 time slice 까지 (n-1)*q 시간 보다 더 기다리면 안됨

 

RR 알고리즘의 성능은 time slice 의 크기에 의해 결정됨

• time slice 가 너무 크면 FIFO 나 FCFS scheduling 처럼 작동
• time slice 가 너무 작으면 많은 context switch 를 발생시켜 overhead 가 커짐.

 

Multilevel Queue Scheduling

ready queue 가 여러 queue 들로 나뉘어짐

프로세스는 프로세스의 property(priority, CPU burst, memory size etc) 에 따라 queue 에 배정됨

각각의 queue 마다 scheduling algorithm 이 존재

 

Priority-based multilevel queue scheduling 

각각의 queue 는 우선순위를 가짐

scheduler 는 queue 들을 실행 준비가 된 thread 를 찰을 때 까지 높은 우선순위에서 낮은 우선순위로 탐색함

 

 

Multilevel Feedback-Queue Scheduling

프로세스에 우선순위가 할당될 때, 큐들 사이로 이동하지 않아 interactive 하거나 I/O-bound 프로세스는 필요할 때 적절한 CPU time 을 사용할 수 없음

Multilevel Feedback-Queue Scheduling 은 다른 우선순위를 가진 큐들 사이로 프로세스들이 이동할 수 있음

프로세스들의 이동은 CPU bursts 의 특징에 의존함

• 프로세스가 CPU time 을 너무 많이 쓰면 낮은 우선순위 큐로 이동함
• I/O bound 나 interactive 프로세스들은 짧은 CPU bursts  을 가지므로 높은 우선순위 큐로 이동함

 

 

참조
Silberschatz_Operating_System_Concepts_10e_2018
광운대 운영체제 강의(안우현 교수, 2021)