[Operating System Concepts] Chapter5 CPU Scheduling

황룡

1. CPU Scheduling
2. Preemptive vs. Non-Preemptive
3. Dispatcher
4. Scheduling Criteria (Turnaround time, Waiting time...)
5. Scheduling algorithm
   • FCFS (First Come First Serve)
   • SJF (Shortest Job First)
   • SRTF(Shortest Remaining Time First ,Preemptive SJF)
   • RR (Round Robin)
6. Extra Scheduling algorithm (Priority-base Scheduling, MLQ, MLFQ)

---

CPU Scheduling

• 여러개의 프로세스가 동시에 메모리에 로드된 프로그램(멀티 프로그래밍)에 있어서 여러개의 프로세스가 로드되어 있고
  CPU가 프로세스를 선점해서 concurrent 하게 실행되는 것을 의미한다.
• CPU 사용량을 늘리기 위해 스케쥴링 전략이 필요하다.

 

• 프로세스 상태가 여러번 변하는데 Running(CPU 소모, 'CPU Burst'), Waiting(대기, 'I/O burst') 중 어떤 것이 많을까?
• 일반적으로 CPU Burst 시간이 적고 I/O bound 시간이 더 많다.
• Ready 상태에 있는 것은 고려하지 않고,  CPU 할당해줄 수 있는 프로세스를 선택하는 것이 스케쥴링의 정수이다.

Burst time of CPU

Preemptive vs. Non-Preemptive

Preemptive(cooperative) : 작업중인 프로세스를 쫓아내고 점유할 수 있다.

Non-Preemptive : 자발적으로 현재 실행되고 있는 프로세스가 종료하기 전까지는 그냥 기다린다.

 

CPU 스케쥴링할 때 고려해야 하는 4가지 경우가 있다.

1. Running → Waiting (I/O 하려고 할 때)
2. Running → Ready (Waiting → Ready)
3. Waiting → Ready
4. Terminate

•  1, 4 는 Non-Preemptive 해서 고민할 이유가 없다.
• 2, 3 은  Preemptive / Non-Preemptive 선택 가능하다. (현대에는 대부분 점유형)

Dispatcher

Dispatcher은 프로세스에게 CPU를 넘겨주는 과정이다. 다음과 같은 작업을 포함한다.

1. 프로세스를 다른 프로세스로 넘겨주는 과정
2. user mode로 변경시키는 과정
3. Jump로 적확한 위치로 넘어가 user program을 실행하는 과정

모든 프로세스의 문맥 교환 시 호출되므로, 최대한 빨리 수행되어야 한다. (오버헤드를 최소화 하기 위함)

• Dispatch latency : PCB0 → PCB1 넘어가는 과정에서 PCB0 상태를 저장하고 PCB1 상태를 복구하는 과정의 시간을 의미한다.
• if Dispatch latency < CPU use time ... : 99퍼 점유율을 가지고 있는 CPU가 되는 경우가 이럴 때를 의미한다.

리눅스에서 cat/ proc/1/status | grep ctxt 하면 voluntary, non-voluntary ctxt_switches 라고 나온다.

• voluntary → non-preemptive
• non-voluntary → preemptive

Scheduling Criteria (Turnaround time, Waiting time...)

• Waiting Time : 어떤 프로세스가 Ready Queue 에 기다리는 시간을 의미한다. (스케쥴링 알고리즘을 통해 최소화 시킨다.)
• Turnaround Time : 실행에서 종료까지 최소화시키는 과정을 이야기 함

#Algorithm Solutions

• FCFS : 선입선출 (현재는 쓰이지 않음)
• SJF, SRTF (Shortest Job First, Shortest Remaining Time First): 짧은 작업시간을 가지고 있는 작업을 실행
  (*SRTF: 남은시간이 짧은 시간을 먼저 실행)
• RR (Round Robin) : 정해진 시간만큼만 작업을 하도록 한다. (ready queue 를 사용한다, 시분할과 관련있음)
• Priority-based : 우선순위를 정해서 작업을 진행한다.

Scheduling algorithm - FCFS

선입선출 알고리즘, 호송효과(convoy effects) 비교적 빠르게 처리할 수 있는 작업이 앞선 작업으로 인해 멈춰있는 효과를 의미함

Process	Burst Time
P1	24
P2	3
P3	3

 

위의 작업에서 P1 → P2 → P3 순으로 온다고 했을 때 아래와 같은 간트차트가 만들어진다.

FCFS Gantt

<대기시간>

P1~3 대기시간: P1 =0, P2 = 24, P3 = 27

전체 대기시간: ( 0 + 24 + 27 ) = 51

평균 대기시간: 51 / 3 = 17

 

<반환시간>

P1~3 반환시간: P1 =24, P2 = 27, P3 = 30

전체 반환시간: ( 24 + 27 + 30 ) = 81

평균 반환시간: 81 / 3 = 27

 

매우 비효율적이다.. 만약 시간순서를 변경해서 P2, P3, P1 으로 작업을 재조정하면..

FCFS Gantt (2)

<대기시간>

P1~3 대기시간: P1 =6, P2 = 0, P3 = 3

전체 대기시간: ( 6 + 0 + 3 ) = 9

평균 대기시간: 9 / 3 = 3

 

<반환시간>

P1~3 반환시간: P1 =3, P2 = 6, P3 = 30

전체 반환시간: ( 3 + 6 + 30 ) = 39

평균 반환시간: 39 / 3 = 13

 

놀랍게도 평균대기시간이 17 에서 3으로 평균 반환시간은 27에서 13으로 크게 줄어들었다.

cpu-burst time 에 따라서 결과가 매우 달라진다. FCFS는 끝날때 까지 작업을 내려놓지 않기 때문에 non-preemptive하다.

 

호송효과(convoy effect) : 병목현상으로 인해 대기시간이 길어져 프로세스 처리가 빠르게 되지 않는 현상을 의미한다.

 

Scheduling algorithm - SJF

오는 순서에 무관하게 실행시간이 짧은 프로세스 먼저 처리하기.

Process	Burst Time
P1	6
P2	8
P3	7
P4	3

 

<대기시간>

P1~3 대기시간: P1 =3, P2 = 16, P3 = 9, P4 = 0

전체 대기시간: ( 3+ 16 + 9 + 0 ) = 28

평균 대기시간: 28 / 4 = 7

 

<반환시간>

P1~3 반환시간: P1 =9, P2 = 24, P3 = 16, P4 = 3

전체 반환시간: ( 9 + 24 + 16 + 3) = 52

평균 반환시간: 52 / 4 = 13

 

• SJF는 Probable Optimal 하다. 최소의 평균 대기시간을 보장한다.
• 짧은 프로세스의 작업은 기다리는 시간을 최소화 하고, 긴 프로세스의 작업의 기다리는 시간을 최대화 시킨다.

 

• 하지만, SJF 스케쥴링은 next CPU burst 시간을 정확하게 측정할 방법이 없기 때문에, 일반화 하여 구현하는게 어렵다.
• 예측은 가능함, 과거를 통해 미래를 알 수 있다. → 과거의 값을 통해 지수적으로 평균을 구할 수 있다. (exponential avg.)
  • 과거를 길게 보고 경향성으로 최근 데이터에 가중치를 줌으로써 예측값을 추정한다.

estimate[ i + 1 ] = alpha * burst[ i ] + ( 1.0 - alpha ) * estimate[ i ]

SJF Estimate algorithm

• SJF는 또한 preemptive, non-preemptive 둘 다 가능하다. → 선점형이 유리하다.
• 구현하긴 어려움

 

Scheduling algorithm - SRTF : Preemptive SJF

현재시각 기준으로 Remaining Time 가장 낮은 프로세스를 CPU 점유할 수 있도록 한다. (기다리지 않고 선점한다)

 

Process	Arrival Time	Burst Time
P1	0	8
P2	1	4
P3	2	9
P4	3	5

 

• Remaining Time 계산을 해서 더 짧은게 도착 한다면 선점시키는 방식이다. (Greedy)

<대기시간>

전체 대기시간: [ (10 - 1) + (1 - 1) + (17 - 2) + (5 - 3) ] = 26

평균 대기시간: 26 / 4 = 6.5

 

 

Scheduling algorithm - RR(Round Robin)

Preemptive FCFS 인데 time-quantum(시간을 잘게 쪼갠 단위를 의미함)

 

레디큐는 원형큐로 만들어져서 하나씩 time-quantum을 기준으로 해서 돌아간다.

 

RR을 사용할 때 있어서 두가지 경우가 생길 수 있다.

• A Cpu burst < A time quantum : 자발적으로 CPU에서 빠져나온다. 스케쥴러는 알아서 다음 프로세스를 레디큐로부터 가져온다
• A Cpu burst > A time quantum : OS에 인터럽트를 걸어주고 context switch가 생긴다. 그리고 해당 프로세스는 레디큐의 마지막 부분(tail of ready queue) 에 들어간다.

Process	Burst Time
P1	24
P2	3
P3	3

RR w/ time quantum = 4ms

4ms 만큼 time quantum을 걸어주면 10ms 이후로 하나가 선점해서 작업을 마친다.

 

<대기시간>

• Waiting time for P1 = 10 - 4, P2 = 4, P3 = 7

RR은 waiting time 이 길어지는 경향이 있다. 그러나 preemptive algorithm 자주 쓰이기 때문에 단점을 상쇄시킬 장점이 더 많다.

 

• time quantum(slice) 를 얼마나 주느냐에 따라서 성능이 많이 차이난다.
• quantum이 무한이다 → FCFS 와 동일하다.
• Dispatch 타임이 0.001ms 이면 (너무 짧아버리면) 아무것도 실행못하고 쫓겨난다.

 

Extra Scheduling algorithm 

높은 우선 순위대로 CPU에 할당시키는 방법을 사용한다.

• 높은 우선순위를 부여하고 같은 우선순위를 가지는 것 끼리는 FCFS 처럼 작용한다. (선점, 비선점 둘다 가능함)
• starvation(기아상태, 무한대기상태) 가 문제가 되는 경우가 있다.
• 오랫동안 잡고있게 되는 상황이 발생하면 aging(우선순위를 낮추는 방법) 을 사용한다.

RR + priority scheduling / 스마트폰처럼 전화가 오면 모든 프로세스 무시하고 전화가 걸려오듯이 우선순위가 존재함

 

MLQ / MLFQ 낮은 퀀텀에서 처리할 거 다 처리하고 이후에 FCFS에서 다 처리할 수 있도록 스케쥴링함

현대적 컴퓨터에서는 스레딩을 지원하기 때문에 스케쥴링의 중요도가 낮아졌다.

 

#Thread Scheduling

• 커널 스레드에서 유저스레드에 대해 매핑만 시켜주면 더 해줄게 따로 없다.

 

#실시간 OS 에 대해 스케쥴링하는 두가지 방법

• soft-realtime : 패킷 손실이 일어나도 괜찮은것
• hard-realtime : 반드시 데드라인 안에 실행되도록 하는것