3.4 CPU 스케줄링 [OS-study]

[ 0. I/O-bound 프로세스 vs CPU-bound 프로세스 ]

• CPU Burst: CPU 사용하는 구간

• I/O Burst: I/O 기다리는 구간

⇒ I/O-bound : I/O Burst가 더 많고 CPU Burst는 짧음 → CPU보다는 I/O 장치 대기가 많음

⇒ CPU-bound : CPU Burst가 길고 I/O Burst는 짧음 → 연산 위주

[ 1. 비선점형(non-preemptive) 알고리즘 ]

프로세스가 스스로 CPU의 소유권을 포기 : 강제 중지 X

• FCFS (First Come, First Served)

⇒ 먼저 온 것 먼저 처리 (Convoy Effect 가능성)


Convoy Effect :
하나의 느린(혹은 오래 걸리는) 작업이 뒤따르는 다른 모든 작업의 진행을 지연시키는 현상
 

• SJF (Shortest Job First)
  ⇒ 시행 시간이 짧은 거 먼저 (Starvation [긴 시행 시간을 가지면 무한 대기] 가능성)
 

• 우선순위 (SJF에 가중치 부여)

⇒ 시행 시간이 짧은거 먼저 실행하되, 오래된 작업에 우선순위를 높게 설정

심화 질문 1 : 몇몇 우선순위 알고리즘은 시행 시간에 영향을 받는다. 하지만 실제 운영체제에서는 실행 이전에 시행시간을 알 수 없다. 현대의 알고리즘 방식에서는 어떻게 이를 해결하는지 설명하시오

답

예측 데이터 이용 (like EMA)
τ[n] = α * T[n-1] + (1 - α) * τ[n-1]

• τ[n] : 이번에 예측한 실행 시간

• T[n-1] : 직전에 실제로 측정된 실행 시간

• τ[n-1] : 직전에 예측했던 실행 시간

• α : 새 데이터에 얼마나 민감하게 반응할지 결정하는 가중치(0~1)

[ 2. 선점형(preemptive) 알고리즘 ]

프로세스를 강제 중단하고 다른 프로세스에 할당 : 현대 운영체제

• RR (Round Robin) - 로드밸런서에서도 사용

⇒ 각 프로세스에 동일한 시간 할당 / 끝나면 다음 차례까지 준비 큐

(N-1) * q 시간이 지나면, 다시 자기 차례

• SRF (Shortest Remaining Time First)
  ⇒ SJF 과정 중 더 짧은 실행 시간을 가지는 작업이 들어오면 스위칭
 

• 다단계 큐


⇒ 우선 순위에 따라 준비 큐를 여러개 사용하고, 각 큐마다 스케줄링 알고리즘 적용

 


심화 질문 2 : P1, P2, P3, P4를 실행함에 있어 SJF알고리즘과 SRF알고리즘을 사용하였을때, 프로세스들의 평균 대기 시간을 연산하시오
(단, SRF에서의 ContextSwitching에 소모되는 시간은 고려하지 않는다.)


• BurstTime : 작업때 까지 걸리는 시간

• WastingTime = 대기시간

 

Ex) P1 → P2 (SJF)의 대기시간은

• 0초 : P1 arrive & P1 start (대기시간 0)

• 2초~7초 : P1 작업 중 & 2초부터 P2 대기 (대기시간 5초)
  ⇒ 예시 일 뿐 실제 과정은 다를 수 있음



답

SJF ⇒ P1 → P3 → p2 → p4

P1 대기시간 : 0

P2 대기시간 : 2~(7+1) = (P1 & P3) = 6

P3 대기시간 : 4~7 = 3

P4 대기시간 : 5~(7+1+4) = (P1 & P3 & P2) = 7

 

평균 대기시간 (SJF) (0+6+3+7)/4 = 4

 

SRF

0초 ~2초 p1(7-2, w=0)

2초 ~ 4초 p2(4-2, w=0) , p1(5, w=2)

4초 ~ 5초 P3(1-1, w=0), P2(2, w=1), P1(5, w=3)

5초 ~ 7초 P2(2-2, w=1), P1(5, w=5), P4(4, w=2)

7초~ 11초 P4(4-4, w=2), P1(5, w=9)

11초 ~ 16초 P1(5-5, w=9)

 

평균 대기시간 (SㄲF) (9+1+0+2)/4 = 3