CPU Scheduling (1)

CPU Scheduling이란?

Memory위에 여러 Process들이 올라가 있는 Multiprogramming 환경에서 CPU Utilization(CPU 이용률)을 최대화 하는 것!

CPU-Burst와 I/O-Burst가 순환하는 구조를 가진다.

CPU Scheduler

: 메모리 위의 여러 ready상태의 프로세스 중 하나를 선택하여 CPU에게 넘겨주는 것.

CPU Scheduling을 다음과 같은 상황에서 실행된다.

1. Process가 Running → Waiting 일 때 ( I/O 작업이 시작되었을 때)
2. Process가 Terminated 상태일 때
3. Process가 Running → Ready 일 때 ( Interrupt가 발생했을 때 → Ready Queue안에 변경사항이 생겼을 때)
4. Process가 Waiting → Ready 일 때 ( I/O 작업이 끝났을 때 → Ready Queue안에 변경사항이 생겼을 때)
5. , 2) → non-Preemptive ( non-Interruptable ) : CPU 안에 프로세스가 끝날때 까지 건드리지 않는다!

3), 4) → Preemptive( Interruptable ) : CPU 안에서 작업중인 Process도 Scheduling에서 고려한다.

Dispatcher

CPU의 Control을 Short-term Scheduler가 선택한 Process로 옮기는 작업을 한다.

이 작업을 Dispatch 혹은 Context Switching이라고 한다. ( Kernel Mode 💻 ) 에서 실행된다.

Dispatch 하는 과정

1. Switching Context
2. Switching Usermode
3. Program restart

Dispatch latency : Control을 넘기는데 걸리는 시간. 한 Process를 정지, 다른 한 Process를 다시 시작시키는 데 걸리는 시간.

Scheduling Criteria

scheduling 기준

1. CPU Utilization : CPU 이용률. 가능한 한 CPU를 혹사시키려고 한다. 클수록 좋다.

2. Throughput : 처리량. 단위시간 당 실행되는 Execution(명령어)의 양. 클수록 좋다.

3. Turnaround : 처리시간. 작업이 끝날 때 까지 걸리는 시간. 작을수록 좋다.

4. Waiting Time : 프로세스들이 Ready Queue에서 기다리는 시간. 작을수록 좋다.

5. Response Time : 반응시간 : 첫번째 Response가 나타나는 시간. 작을수록 좋다.

response time은 특히 시분할 시스템에서 중요하다고 한다.

여러가지 Scheduling 방식

First-Come, First-Served ( FCFS ) Scheduling

Ready Queue에 들어온 순서대로 CPU를 할당받는다.

⇒ Process들이 들어온 순서에 따라서 Waiting Time이 달라진다.

처리시간이 짧은 Process들이 먼저 들어올 수록 Waiting Time이 짧아진다.

Convoy Effect : CPU Burst가 작은 Process들이 CPU Burst가 큰 Process뒤에서 기다리는 현상.

Shortest-Job-First ( SJF ) Scheduling

CPU Burst Time이 작은 Process부터 처리하는 방식.

두가지 방식이 있다.

1. Non-Preemptive : CPU를 차지한 Process는 중지하지 않고 Scheduling을 진행한다. ( Shortest Job Next)
2. Preemptive : CPU에 있는 Process의 Next CPU Burst Time까지 고려하여 Scheduling을 진행한다. 이 방식을 Shortest-Remaining-Time-First( SRTF ) 라고 한다.

SRTF는 Context Switching( Process의 Control을 바꾸는 과정 ) 이 많이 일어난다. Dispatch Latency가 증가하고 성능이 나빠진다. ( Context Switching 은 Overhead이기 때문이다 )

BUT. 평균 Waiting Time 측면에서는 성능이 가장 좋다.

SJF는 Next CPU Burst를 필요로 한다 ⇒ Next CPU Burst를 계산하는 방법.

1. 𝑇ｎ = n번째 CPU Burst 측정값.
2. 𝙩ｎ+1 = n+1번째 CPU Burst 예측값.
3. ả = 예측값과 측정값의 비율 / ả = 0 일때. 측정값 사용 X / ả = 1 일때. 예측값 사용 X
4. 𝙩ｎ+1 = ả * 𝑇ｎ + (1 - ả) * 𝙩ｎ

Priority Scheduling

우선순위를 설정하여 우선순위가 높은 프로세스를 먼저 처리한다.

우선순위를 결정하는 정수가 있다. → 이 정수가 작을수록 우선순위가 높다.

Preemptive : CPU에 있는 프로세스까지 고려하여 Scheduling

Non-Preemptive : CPU에 들어간 프로세스는 건들지 않는다.

SJF는 Priority가 Next CPU Burst Time인 Priority Scheduling 기반 알고리즘이다.

문제점 : Starvation : 우선순위가 높은 프로세스들이 계속 들어오면 처리되지 않는 프로세스가 생긴다.

해결방법 : Ageing : 시간이 지날수록 우선순위가 높아지도록 한다.

Round Robin ( RR )

프로세스들이 CPU를 이용할 수 있는 시간에 제한이 생긴다. 이 시간 제한을 Time Quantum이라고 한다.

N개의 프로세스들이 있고, Time Quantum이 Q일 때. 프로세스가 최대로 기다리는 시간은 ( N - 1) * Q.

Time Quantum이 크다 ⇒ FIFO

Time Quantum이 작다 ⇒ Context Switching이 자주 일어나 Overhead가 증가하고 성능이 떨어진다.

SJF 보다 Turnaround ( 처리시간 ) 이 높지만, Response가 좋다.

Time Quantum 설정방법

Time Quantum이 높다고 무조건 좋아지는 것은 아니다.

Rule of Thumb : 엄지손가락의 법칙👍 90%의 프로세스가 한번에 끝나는 Time Quantum이 좋다.