CPU Scheduling

zioo·2022년 9월 7일
1
post-thumbnail

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

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 rateservice rate 등을 통해 각종 performance index값을 계산

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

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

Simulation(모의 실험)

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

0개의 댓글