CPU Scheduling 2

kocw 강의 : 이화여자대학교 반효경 교수님의 운영 체제 강의,10강 CPU Scheduling

 

 

"어떤 프로세스한테 CPU를 줄 것이냐"

"줬으면 계속 둘 것인가. 아니면 다시 뺏어올 것인가"

• non-preemptive scheduling (비-선점형 스케줄링) -> 주면 다 쓸 때까지 계속 둔다.
• preemptive scheduling (선점형 스케줄링) -> 줬다 뺏었다

---

Scheduling Criteria (performance index, performance measure)

• system 입장에서의 성능 척도
  • CPU utilization : 전체 시간에서 cpu 가 놀지 않고 일한 시간의 비율
  • Throughput : 주어진 시간동안 몇 개의 작업을 완료했는가
• process 입장에서의 성능 척도
  • Turnaround time : cpu 를 쓰러 와서 다 쓰고 갈 때까지 걸린 시간, time to execute a process
    
    • process 의 runtime 이라기보다는, cpu 가 process에 할당되어서 i/o 하러 나갈 때까지의 시간을 의미
  • Response time : ready queue에서 처음으로 cpu 를 얻기까지 걸린 시간
  • Waiting time : ready queue 에서 기다린 시간, waiting in the ready queue,
    • response time은 waiting time 을 계산하기 위한 첫 번째 time data

---

Scheduling Algorithm

• FCFS (First-Come First-Served)
  • non-preemptive scheduling
  • in-efficient
  • cpu 를 오래 쓰는 작업이 먼저 오면, cpu를 짧게 쓰는 i/o 작업같은건 뒤에 줄줄이 기다려야 함
    • convoy effect : short process behind long process
  • 어떤 프로세스가 먼저 오냐에 따라, waiting time 의 편차가 매우 큼
• SJF (Shortest-Job-First)
  • cpu burst time 이 가장 짧게 쓰는 프로세스부터 준다.
  • Two schemes : 
    • non-preemptive : 돌리다가 더 짧은 얘가 등장해도 돌리던거 마저 돌림
    • preemptive : 현재 수행 중인 프로세스의 남은 burst time 보다 더 짧은 cpu burst time 을 가지는 새로운 프로세스가 도착하면 cpu 를 빼앗김, 이걸 SRTF (shortest-remaining-time-first) 라고 함
  • SRTF is optimal : 주어진 프로세스들에 대해 minimum average waiting time 을 보장
  • 이 알고리즘이 최고냐? 아니 나름의 문제가 있다.
    • starvation : cpu burst time 이 높은 얘들은 돌 기회가 없다. 돌라고 하면 자꾸 burst time 짧은 얘들이 치고 들어옴
    • 애초에 cpu burst time 을 알 수 있는가?
      • 알 수는 없지만 추정은 할 수가 있다. 과거에 cpu birst time을 이용해서 추정 (exponential averaging)
        • $\t_n$ = actual length of n-th cpu burst
        • $tau_{n+1}$ = predicted value for the next cpu burst
        • $\tau_{n+1} = \alpha t_n + (1-\alpha) \tau_n (\alpha < 1)$
  • Example :
    • non-preemptive : P1 -> P3 -> P2 -> P4
    • preemptive : P1 -> P2 (P1 5만큼 남음) -> P3 (P2 2만큼 남음) -> P2 -> P4 -> P1

Process	Arrival Time	Burst Time
P1	0	7
P2	2	4
P3	4	1
P4	5	4

 

---

Priority Scheduling

• 우선순위가 제일 높은 cpu 에게 cpu 를 주겠다.
  • snallest integer = highest priority
• SJF 는 일종의 priority scheduling이다. 
  • priority = predicted next cpu burst time
• Problem
  • starvation : low priority processes may never execute
• Solution : 
  • Aging : as time progresses increase the priority of the process

---

Round Robin (RR)

• 대부분 현대 OS는 이 방식을 따른다.
• 각 process는 동일한 크기의 할당 시간(time quantum) 을 가짐
• 할당 시간이 지나면 프로세스는 preempted 당하고 ready queue 의 제일 뒤에 가서 줄을 선다
• response time 이 짧다
• n 개의 process가 ready queue 에 있고 할당 시간이 q time unit 인 경우, 각 프로세스는 최대 q time unit 단위로 cpu 시간의 1/n 을 얻는다. 
  • 어떤 프로세스도 (n-1) * q time unit 이상 기다리지 않는다.
• performance
  • large q -> FCFS 와 비슷해짐
  • q small -> context switch overhead 가 커진다.
  • 짧은 cpu burst time과 긴게 섞여있으면 성능 이점이 높아진다.
    • process가 heterogeneous 하다고 함
  • 근데 반대로 homogeneous 하면, average waiting time 이 길어짐. 왜냐하면, 다들 비슷하게 기다리고 비슷하게 끝날테니깐, 공정하긴 하지만, 모두가 늦게 끝나게 된다.

 

재밌구만