운영체제 스터디 5주차 - CPU 스케쥴링

Basic Concepts

CPU 스케쥴링은 멀티 프로그래밍(여러 개의 프로세스를 동시에 돌려서 궁극적으로 CPU의 활용도를 높이는 것)의 가장 기초적인 부분. 대부분의 프로세스의 작업은 CPU burst보다는 I/O burst 시간이 더 길다. 이는 프로세스가 I/O 처리를 위해 대기 상태에 들어가는 상황이 많다는 뜻이다. 만약 멀티 프로그래밍을 하지 않는다면 이 대기 시간 동안 CPU가 놀게 되므로 CPU 사용률이 급격히 떨어진다. 멀티 프로그래밍은 이 유휴 시간 동안 컨텍스트 스위칭 등으로 CPU가 프로세스를 계속해서 돌리게 하여 CPU의 가동률을 올린다.

 

CPU 스케쥴링이란 유휴 상태가 되었을 때 어떤 프로세스로 컨텍스트 스위칭할 것인지 선택하는 과정이라고 볼 수 있다.

 

Preemptive vs Non-preemptive

스케쥴링에는 선점형(Preemptive)와 비선점형(Non-preemptive) 방식이 있다. 비선점형 스케쥴링은 CPU에 있는 프로세스가 끝날 때까지 기다려야 한다는 것이고(스케쥴러가 CPU에 올라와 있는 프로세스를 못 쫓아내고 프로세스가 끝나고 자발적으로 release 될 때까지 기다려야 한다는 뜻), 선점형 방식은 스케쥴러가 다른 프로세스를 위해 현재 돌아가고 있는 프로세스를 강제로 쫓아낼 수 있다.

 

Dispatcher

스케쥴러가 어떤 프로세스로 교체해야 할지 고른다면, 실제 교체를 진행하는 것은 dispatcher가 수행하게 된다. Dispatcher의 역할은 1) 다른 프로세스로 컨텍스트 교체 2) 유저모드로 바꾸기 3) 새로운 프로세스의 적당한 위치로 resume시키는 것(프로그램 카운터 얘기)이다. Dispatcher가 동작하는 시간(문맥 교환을 하는 물리적인 시간, P0의 pcb를 어디엔가 저장하고 P1의 pcb를 불러오는 시간) 동안에는 CPU가 놀게 되는데 이 놀게되는 시간을 Dispatcher Latency라고 부르며 이 시간을 줄이는 것이 중요하다.

 

 

Scheduling Criteria & Algorithms

스케쥴링 평가 기준을 5가지로 볼 수 있다. 1) CPU 활용도 2) Throughput(처리량) 3) Turnaround Time(프로세스를 처리하는데 총 얼마의 시간이 걸리는가) 4) Waiting Time(Reay Queue에서 있는 시간이 얼마인가) 5) Respinse time (반응하기까지 얼마의 시간이 걸리는가)

 

알고리즘은 아래와 같다.

 

1. FCFS (First-Come, First-Served)

먼저 온 프로세스를 먼저 처리해주는 방식이다. 가장 간단하게 구현할 수 있다는 장점이 있다. 하지만 어떤 작업이 먼저 오느냐(특히 CPU 작업 시간이 긴 CPU-bound이 앞으로 올 수록)에 따라 총 혹은 평균 Waiting time이 극단적으로 달라진다. CPU-bound 작업 하나와 I/O작업 여러 개인 다이나믹한 상황에서 CPU를 잠깐만 사용해도 되는 I/O bound 작업들은 CPU-bound 작업 하나 때문에 길게 기다려야 한다. (이를 호송 효과 혹은 convoy effect라고 함) Turnaround time도 굉장히 요동치는 경향. 이는 FCFS가 기본적으로 비선점형 스케쥴링 알고리즘이기 때문.

 

2. SJF (Shortest-Job-First)

각 프로세스 별로 가장 짧은 CPU-burst time이 남은 프로세스를 택해서 할당하는 방식(남은 시간이 만약 같다면 FCFS로 처리)이다. 이때 남은 CPU burst time은 과거를 봤을 때 얼마나 CPU를 선점했는지를 지수평균을 내어 계산한다(== 최근에 많이 사용했다면 평균을 더 증가시키는 방향으로 가중치를 주는 방식).

이 알고리즘은 확률적으로 보았을 때 최적화된 선택지인데(probably optimal) burst 시간이 긴 프로세스가 뒤로 밀려나서 발생하는 증감되는 waiting time 보다 짧은 burst time을 가진 프로세스가 앞으로 와서 차감되는 waiting time이 더 크기 때문이다.

SJF는 비선점형일 수도 있고, 선점형일 수도 있다. 하나의 프로세스를 진행하는 중에 ready queue에 들어온 프로세스의 남은 버스트 타임이 더 짧은 상황에서 그냥 이전 꺼 진행할 수도 있고(비선점형), 컨텍스트 스위칭 시킬 수도 있음(선점형).

 

3. SRTF (Shortest-Remaining-Time-First)

SRTF는 선점형 SJF라고 볼 수 있다. 뒤에서 기다리는 프로세스의 버스트 시간이 더 짧다면 교체해버리는 방식을 채택. SRTF의 waiting time이 SJF 보다 더 짧은 경향성을 보인다.

 

4. RR (Round Robin)

RR 스케쥴링은 타임 퀀텀이 있는 선점형 FCFS라고 볼 수 있다. 보통 10 milisecond 정도를 주고 먼저 온 프로세스 먼저 처리하게 하고 시간 지나면 쫓아내는 방식. (Ready Queue를 circular queue로 구현 가능) 하나의 time quantum 안에 두 가지의 경우의 수가 발생할 수 있다.

1. 그 안에 프로세스 처리가 모두 끝나는 경우: 프로세스가 자발적으로 CPU를 반납. 스케쥴러는 다음 프로세스를 레디 큐에서 찾는다.
2. 그 안에 프로세스 처리가 끝나지 못하는 경우: 타이머가 OS에 인터럽트를 발생시키고 컨텍스트 스위치가 발생. 원래 처리되고 있었던 프로세스는 레디 큐로 간다.

RR을 사용하게 되면 waiting time이 오히려 더 늘어날 수도 있다. (하지만 다른 알고리즘을 섞어서 쓰면 더 강력해짐) RR은 선점형, 타임 퀀텀에 따른 선점이 일어나는 알고리즘임. 그말은 곧 RR은 타임 퀀텀 사이즈에 따라서 성능이 달라질 수 있다는 말. 문맥 교환 시 dispatch latency가 발생할 수 있으므로 적절히 조절하는 것이 중요. (퀀텀이 무한대가 된다면 FCFS랑 똑같고, 너무 잘게 쪼개면 dispatch latency 가 길어지고 프로세스를 처리할 시간도 부족)

 

5. Priority-base Scheduling

우선순위에 따라 스케쥴링을 처리할 수도 있다. (만약 모든 프로세스의 우선순위가 같다면 FCFS랑 똑같게 되는 것. SJF도 남은 CPU 버스트가 적은 것에 우선순위를 주는 알고리즘이라고 볼 수도 있다.) priority 스케쥴링을 선점형, 비선점형 방식으로 구현할 수 있다.

단, 우선순위 스케쥴링의 경우 starvation 문제가 발생할 수 있다. 어떤 프로세스가 다른 프로세스의 우선순위에 계속해서 밀려 영원히 처리되지 못하는 문제. 이 경우 aging을 적용해서 오래 기다린 프로세스일수록 우선순위가 높아지도록 처리할 수 있음.

 

6. Combining RR & Priority Scheduling

RR 방식과 우선순위 스케쥴링을 혼합하여 사용할 수도 있다. 우선순위를 정하고, 같은 우선순위 안에서는 RR 방식으로 돌리는 것.

이것을 조금 더 발전시킨 것이 MLQ(Multi-Level Queue) 방식. 분리된 레디 큐에 각각의 우선순위를 부여해서 같은 우선순위의 프로세스끼리 모아두어 처리하는 방식이다. 다만 MLQ로 할 경우 특정 우선순위의 큐에 대한 프로세스만 계속 처리되는 부작용이 있을 수 있다.

 

 

MLQ의 단점을 극복하기 위해 나온 것이 MLFQ(Multi-Level Feedback Queue). 각 큐에 퀀텀 타임을 다르게 주고, 만약 퀀텀 타임 내에 처리하지 못했다면 하위 우선순위를 지닌 레디 큐에 넣는 방식으로 feedback을 줘서 기아 문제를 예방하는 것이다.

 

 

Thread Scheduling & Real-Time CPU Scheduling

모던 운영체제에서는 프로세스 단위가 아니라 커널 스레드 단위로 스케쥴링을 적용하지만, 그렇게 할 경우 너무 복잡해지기 때문에 수업에서는 프로세스 단위로 배웠다. 유저 스레드는 소프트웨어의 스레드 라이브러리가 관리해주기 때문에 커널 스레드는 이를 몰라도 된다. 실질적으로 운영체제가 스케쥴링이 하는 것은 커널 스레드라고 보면 된다.

 

실시간 OS란 주어진 시간 내에 어떤 task를 완료할 수 있어야 한다. (따라서 우선순위가 적용되어야 함)

소프트 리얼타임: 크리티컬 프로세스가 non-critical 프로세스보다 먼저 처리되는 것이 보장되지는 않지만 어쨌거나 먼저 처리해주는 것. (ex. 전화 신호를 변환할 때 한 두개의 정보는 놓쳐도 되는 것처럼)

하드 리얼타임: 어떤 태스크가 반드시 데드라인 안에 수행되어야 하는 것.