CPU Scheduling

[ 이화여대 운영체제 - 반효경 교수님 강의 ]

CH5. CPU Scheduling

CPU and I/O Bursts in Program Execution

• 멀티프로그래밍은 CPU의 호율성을 극대화하기 위해 (프로세스) 스케줄링을 필요로 한다.

• CPU & I/O Burst Cycle

  • 프로세스 실행은 CPU 실행과 I/O 대기의 사이클로 이루어진다
    

• 사람이 반응하는 프로그램은 CPU & I/O burst 가 짧아지고 많아진다
• 세포 분석 프로그램은 I/O burst 가 적다

CPU-burst Time 분포

• job의 종류가 섞여 있다.

• I/O bound job

  • interacitve 하다
  • 답답하니까 사람한테 너무 많이 기다리지 않게 한다.

• 효율적 스케쥴링이 중요하다
  

• 대체로 I/O bound job 는 burst 시간이 짧고 빈도수가 높음

• CPU bound 은 burst 시간은 길지만, 빈도수가 낮았다.

프로세스 특성 분류

CPU Scheduler & Dispatcher

• CPU Scheduler
  • CPU를 누구에게 줄지 결정
• Dispatcher
  • CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스를 넘긴다.
  • context switch

1,4 -> 비선점형(non-preemptive) = 강제로 빼앗지 않고 자진 반납
2,3 -> 선점형(preemptive) = 강제로 빼앗음

• 현대에는 거의 preemptive 한 스케줄링을 사용한다.

CPU Scheduling

1. 누구한테 할당할 거냐
2. preemptive vs nonpreemptive

Scheduling Criteria

= performance Index, performance Measure ,성능 척도

System 입장

• CPU utilization (이용료)
  • keep the CPU as busy as possible
  • 전체 시간 중에 CPU가 일한 시간
• Throughput (처리량)
  • 주어진 시간 동안 몇 개의 작업을 완료 했는지

Process 입장 ⇒ 시간 관련

• Turnaround time (소요시간)
  • CPU를 쓰러 들어와서 다 쓰고 나갈 때 까지의 시간
• Waiting time (대기 시간)
  • CPU를 기다린 시간
  • 순수하게 기다린 시간
• Response time (응답 시간)
  • 처음으로 CPU를 얻기까지 걸린 시간

waiting time vs response time

waiting time

• CPU를 얻었다가 뺏겼다 얻었다 뺐겼다 하며 총 기다린 시간

response time

• 처음으로 CPU 얻기까지 걸린 시간

중국집 비유

• 주방장

  • CPU utilization : 주방장이 일한 시간

  • Throughput : 손님이 많은게 좋음

• 손님 입장

  • Turnaround time : 가게에 와서 다먹고 나가는데 까지 걸린 시간

  • Waiting time : 손님이 밥을 먹은 시간 말고 기다린 시간들의 합

  • Response time : 첫 음식을 받기까지 걸린 시간 / 늦게 주면 허기가 져서 당이 떨어짐 / 큰일남 / 중요

CPU Scheduling Algorithm

종류

• FCFS (First-Come First-Served)

• SJF (Shortest-Job-First)

• SRTF (Shortest-Remaining-Time-First)

• Priority Scheduling

• RR (Round Robin)

• Multilevel Queue

• Multilevel Feedback Queue

1. FCFS (First-Come First-Served)

먼저 온 순서대로 처리하는 것

• nonpreemptive
• 효율적이지 않음
• CPU 오래쓰는 애가 먼저 오면 오래 기다려야 함

Convoy effect -> 앞의 긴 작업 때문에 큐에서 짧은 작업들이 기다리는 현상

Waiting time : p1 = 0, p2 = 30, p3= 33

Waiting time : p1 = 4, p2 = 0, p3= 3

convoy effect

• 1차 세계 대전 때 나온 개념
• 전쟁 물자를 앞 뒤에서 보호함

2. SJF (Shortest-Job-First)

각 프로세스의 다음 번 CPU burst Time을 가지고 스케줄링에 활용하여 이 시간이 가장 짧은 프로세스 를 제일 먼저 스케줄한다.

• minimum average waiting time (Preemptive version)

Two schemes

• Nonpreemptive
  • 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점 당하지 않음
• Preemptive
  • 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김

Example : Non-Preemptive SJF

• CPU를 다 쓰고 나가는 시점에 스케줄링이 일어남

Example : Preemptive SJF

• Nonpreemptive 보다 빠름
• 새로운 프로세스가 도착하면 언제든 스케줄링이 일어남

SJF 문제점

• starvation : CPU burst가 긴 작업(long-precess)들은 영원히 실행 X
• CPU 실행 시간을 미리 알 수 없음
  • 추정은 가능

다음 CPU Burst Time 의 예측

1. t : 실제 CPU 사용시간
2. T : CPU 예측 시간
3. a , 0 ≤ a ≤ 1

최근 거는 가중치 높게, 예전 거는 가중치 낮게 해서 예측

3. Priority Scheduling

개발자가 우선순위 프로세스에게 부여하는 순서대로 스케줄링이 된다.

• highest priority 를 가진 프로세스에게 CPU할당 (작은 숫자가 우선순위가 높음)

• SJF는 일종의 priority scheduling 이다. (CPU burst time이 우선순위)

• Priority Scheduling

문제

• starvation : 낮은 우선순위는 영원히 실행 X

해결방법

• Aging : 시간이 지날수록 프로세스의 우선순위를 높임

4. RR (Round Robin)

공평하게 프로세스들이 돌아가면서 수행하는 알고리즘

• 현대적인 CPU 스케줄링은 RR에 기반함
• 응답 시간이 빠르다
• 각각의 프로세스는 동일한 크기의 할당 시간 time quantum(= time slice)을 가짐
  • 일반적으로 10-100 milliseconds
• 어떤 프로세스도 (n-1)*q time unit 이상 기다리지 않는다.

Performance

• q large : FCFS
• q small : context switch 오버해드가 발생 (10~100ms 적당)

특이한 예

• 비슷한 실행 시간 가진 것들만 많으면 모든 것이 한 번에 끝날 수도 있음

Example : RR with Time Quantum = 20

중요 장점 : response time 짧음

Turnaround time Varies With Time Quantum

5. Multilevel Queue

• Ready queue를 여러 개로 분할
  • foreground (interactive) / 우선순위가 높음
  • background (batch - no human interaction) / starvation이 일어날 수 있음
• 각 큐는 독립적인 스케줄링 알고리즘을 가짐
  • foreground - RR (공정)
  • background - FCFS
• 큐에 대한 스케줄링이 필요 (해결법)
  • Fixed priority scheduling -> 우선 순위 레벨 고정
  • Time slice
    • 각 큐에 CPU time을 적절한 비율로 할당

6. Multilevel Feedback Queue

프로세스들이 상황에 따라 queue와 queue 사이를 이동할 수 있는 스케줄링 알고리즘

• queue 하나에 대해 RR을 적용하는것 보다 더 CPU burst가 짧은 프로세스를 우대해주는 스케줄링 방식이다.

• 프로세스가 다른 큐로 이동 가능

• Aging을 이와 같은 방법으로 구현할 수 있음

• Multilevel Feedback Queue

• RR 만으로는 부족

• 처음 들어오는 큐는 우선순위 가장 높은 큐에 넣는다

• time quantum 짧게 주고 RR 방식 이용

  • 상위 queue에서 할당한 시간이 만료될 경우 바로 다음 하위 queue로 강등되며 상위 queue가 빌 때 까지 대기해야 함

• 내려갈 수록 점점 time quantum 길게 준다, 맨 아래 큐는 FCFS 방식 이용

7.Multiple-Processor Scheduling

CPU가 여러 개인 경우 스케줄링은 더욱 복잡

• Homogeneous processor 인 경우
  • Queue에 한줄로 세워서 각 프로세서사 알아서 꺼내가게 할 수 있다
• Load sharing
  • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 매커니즘 필요
  • 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
• Sysmmetric Multiprocessing (SMP)
  • 각 프로세서가 각자 알아서 스케줄링 결정
• Asymmetric multiprocessing
  • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

8.Real-Time Scheduling

Hard real-time systems

• 정해진 시간 안에 반드시 끝내도록 스케줄링 해야함

Soft real-time computing

• 일반 프로세스에 비해 높은 priority를 가지게 함

9.Thread Scheduling

Local Scheduling

• User level thread 의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄링할지 결정
• 운영체제는 thread를 모름
• 사용자 프로세스가 직점 어느 쓰레드에 CPU 줄지 결정

Global Scheduling

• Kernel level thread의 경우 일반 프로세스와 마찬 가지로 커널 단기 스케줄러가 어떤 thread를 스케줄링할지 결정

Algorithm Evaluation

Queueing models

• 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index값을 계산

Implementation(구현) & Measurement(성능 측정)

• 실제 시스템에 알고리즘을 구현하여 실제 작업(work)에 대해 성능 측정 비교

Simulation(모의 실험)

• 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교