CPU Scheduling

Hye·2022년 8월 24일
운영체제
0

운영체제

목록 보기
5/11

✏️CPU-burst time의 분포

  • CPU burst : CPU만 연속적으로 쓰면서 instruction을 실행하는 일련의 단계
  • I/O burst : I/O를 실행하는 단계
  • 여러 종류의 job(=process)이 섞여 있기 때문에 CPU 스케쥴링이 필요
    • interactive job에게 적절한 response제공 요망
    • CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용

✏️프로세스의 특성 분류

  • 프로세스는 그 특성에 따라 다음 두 가지로 분류

    • I/O-bound process
      • CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
      • many short CPU bursts
    • CPU-bound process
      • 계산 위주의 job
      • few very long CPU bursts

✏️CPU Scheduler & Dispatcher

  • CPU Scheduler
    • Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고름
  • Dispatcher
    • CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘김
    • 이 과정을 context switch(문맥 교환)이라고 함

  • CPU 스케쥴링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우

    1. Running → Blocked (ex. I/O 요청하는 시스템 콜)
    2. Running → Ready (ex. 할당 시간 만료로 timer interrupt)
    3. Blcoked → Ready (ex. I/O 만료 후 interrupt)
    4. Terminate

  • 1, 4 scheduling : nonpreemptive (비선점형, =강제로 빼앗지 않고 자진 반납)

  • All other scheduling : preemptive (선점형, =강제로 빼앗음)

✏️Scheduling Criteria

= Performance Index / Performance Mesaure (성능 척도)

  • CPU utilization (이용률)
    • CPU가 놀지 않고 일한 시간 / 전체 시간의 비율
    • keep the CPU as busy as possible
    • 시스템 입장에서의 성능 척도
  • Throughput (처리량)
    • # of processes that complete their execution per time unit
    • 시스템 입장에서의 성능 척도
  • Turnaround time (소요시간, 반환시간)
    • amount of time to execute a particular process
    • 프로세스 입장에서의 성능 척도
  • Waiting time (대기 시간)
    • amount of time a process has been waiting in the ready queue
    • 프로세스 입장에서의 성능 척도
  • Response tine (응답 시간)
    • amount of tine it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment)
    • 처음으로 CPU 얻기까지 걸린 시간
    • 프로세스 입장에서의 성능 척도

✏️Scheduling Algorithms

1️⃣ FCFS (First-Come First-Served)

  • 비선점형

  • example

    • ProcessBurst Time
      P124
      P23
      P33

    • 프로세스 도착 순서 : P1, P2, P3

      • Waiting time for P1 = 0, P2 = 24, P3 = 27
      • Average waiting time : (0 + 24 + 27) / 3 = 17

    • 프로세스 도착 순서 : P2, P3, P1

      • Waiting time for P1 = 6, P2 = 0, P3 = 3
      • Average waiting time : (6 + 0 + 3) / 3 = 3

  • Convoy effect : short process behind long process

  • 앞의 프로세스가 대기시간에 큰 영향을 미침

2️⃣ SJF (Shortest-Job-First)

  • 각 프로세스의 다음번 CPU burst time을 가지고 스케쥴링에 활용
  • CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케쥴
  • Two schemes:
    • Nonpreemptive
      • 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점당하지 않음
      • example
        • ProcessArrival TimeBurst Time
          P10.07
          P22.04
          P34.01
          P45.04
        • Average waiting time = (0 + 6 + 3 + 7) / 4 = 4
    • Preemptive
      • 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
      • 이 방법을 Shortest Remaining Time First(SRTF)라고 부름
      • example
        • ProcessArrival TimeBurst Time
          P10.07
          P22.04
          P34.01
          P45.04
        • Average waiting time = (9 + 1 + 0 + 2) / 4 = 3
  • SJF is optimal
    • 주어진 프로세스들에 대해 minimum average waiting time을 보장 - Preemptive 버전
  • 문제점 : 기아 현상, 다음 CPU burst time 정확히 모름
  • 다음 CPU Burst Time의 예측
    • 추정(estimate)만이 가능
    • 과거의 CPU burst time을 이용해서 추정 (exponential averaging)
      1. tnt_n = actual length of nthn^{th} CPU burst
      2. τn+1τ_{n+1} = predicted value for the next CPU burst
      3. 𝛼, 0 ≤ 𝛼 ≤ 1
      4. τn+1τ_{n+1} = 𝛼tnt_n + (1-𝛼)τnτ_n
      • 𝛼 = 0
        • τn+1τ_{n+1} = τnτ_n
        • Recent history does not count
      • 𝛼 = 1
        • τn+1τ_{n+1} = tnt_n
        • Only the actual last CPU burst counts
      • 식을 풀면 다음과 같다
        • τn+1=atn+(1−a)atn−1τ_{n+1} = at_n + (1-a)at_{n-1} + ⋯ + (1−a)jatn−j(1-a)^jat_{n-j} + ⋯ + (1−a)n+1τ0(1-a)^{n+1}τ_0
      • 𝛼와 (1-𝛼)가 둘다 1 이하이므로 후속 term은 선행 term보다 적은 가중치 값을 가진다

3️⃣ SRTF (Shortest-Remaining-Time-First)

4️⃣ Priority Scheduling

  • A pritority number (integer) is associated with each process
  • highest priority를 가진 프로세스에게 CPU 할당 (smallest integer - higest priority)
    • preemptive
    • nonpreemptive
  • SJF는 일종의 priority scheduling
    • priority = predicted next CPU burst time
  • Problem
    • Starvation (기아 현상) : low priority processes may never execute
  • Solution
    • Aging (노화) : as time processes increases the priority of the process

5️⃣ RR (Round Robin)

  • 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐 (일반적으로 10 - 100 milliseconds)
  • 할당 시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤에 가서 줄을 선다
  • n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다
    • 어떤 프로세스도 (n-1)q time unit 이상 기다리지 X
  • 장점 : 응답 시간 빠름
  • Performance
    • q large → FCFS
    • q small → context switch 오버헤드가 커짐
  • example (Time Quantum = 20)
    • ProcessBurst Time
      P153
      P217
      P368
      P424
  • 일반적으로 SJF보다 average turnaround time이 길지만 response time은 더 짧다

6️⃣ Multilevel Queue

  • Ready queue를 여러 개로 분할
    • foreground (interactive)
    • background (batch - no human interaction)
  • 각 큐는 독립적인 스케쥴링 알고리즘을 가짐
    • foreground - RR
    • background - FCFS
  • 큐에 대한 스케쥴링이 필요
    • Fixed priority scheudling
      • serve all from foreground then from background
      • Possibility of starvation
    • Time slice
      • 각 큐에 CPU time을 적절한 비율로 할당
      • ex. 80% to foreground in RR, 20% to background in FCFS

7️⃣ Multilevel Feedback Queue

  • 프로세스가 다른 큐로 이동 가능
  • aging을 이와 같은 방식으로 구현 가능
  • Multilevel-feedback-queue scheuler를 정의하는 파라미터들
    • Queue의 수
    • 각 Queue의 scheduling algorithm
    • Process를 상위 큐로 보내는 기준
    • Process를 하위 큐로 내쫓는 기준
    • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준
  • example
    • Three queues:
      • Q0 : time quantum 8 milliseconds
      • Q1 : time quantum 16 milliseconds
      • Q2 : FCFS
    • Scheduling
      • new job이 queue Q0로 들어감
      • CPU를 잡아서 할당 시간 8ms 동안 수행됨
      • 8ms 동안 다 끝내지 못했으면 queue Q1으로 내려감
      • Q1에 줄서서 기다렸다가 CPU를 잡아서 16ms동안 수행됨
      • 16ms에 끝내지 못한 경우 queue Q2로 쫓겨남

✏️Multiple-Processor Scheduling

  • CPU가 여러 개인 경우 스케쥴링은 더 복잡해짐
  • Homogeneous processor인 경우
    • Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있음
    • 반드시 특정 프로세서에서 수행되어야 하는 프로세서가 있는 경우에는 문제가 더 복잡해짐
  • Load sharing
    • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
    • 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
  • Symmetric Multiprocessing (SMP)
    • 각 프로세서가 각자 알아서 스케쥴링 결정
  • Asyymetric Multiprocessing
    • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

✏️Real-Time Scheduling

  • Hard real-time systems
    • Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케쥴링해야 함
  • Soft real-time computing
    • Soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야 함

✏️Thread Scheduling

  • Local Scheduling
    • User level thread의 경우 사용자 수준의 thread library에 의해 어떤 threadfㅡㄹ 스케쥴할지 결정 (사용자 프로세스가 직접)
  • Global Scheduling
    • Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케쥴러가 어떤 thread를 스케쥴할지 결정

✏️Algorithm Evaluation

1️⃣ Queueing models

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

2️⃣ Implementation(구현) & Measurement(성능 측정)

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

3️⃣ Simulation (모의 실험)

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

참고자료
KOCW, 반효경 교수님, 운영체제

profile
Hye
공부중 📚
이전 포스트

Process Management

다음 포스트

Process Synchronization

0개의 댓글