[OS] CPU 스케쥴링

🧠·2022년 5월 20일
0

CPU 스케쥴링을 하는 이유

  • CPU의 utilization을 극대화 하기 위해서
  • Throughput을 최대화 하자
    - Throughput: 단위시간내에 완료되는 프로세스 수
  • Turnaround time:
    - 프로세스가 실행에서 종료되기까지의 시간을 최소화 하자
  • Waiting time:
    - 프로세스가 대기하는 시간을 최소화 하자
  • Response time:
    - 응답하기 까지의 시간을 최소화 하자
  • CPU burst 상태: running 상태
  • I/O burst 상태: waiting 상태

CPU Scheduler

  • ready queue에 있는 프로세스 중 어떤 순서로 골라서 CPU를 할당할지 선택

FIFO Queue

Fist In First Out

Preemptive vs Non-Preemptive

  • Non-Preemptive Scheduling(비선점 스케쥴링): Process가 자발적으로 종료되기 전까지 CPU 할당 보장
  • Preemptive Scheduling(선점 스케쥴링): CPU를 선점하고 있는 Process에서 CPU 강제 회수 가능

Decision Making for CPU-Scheduling

  • CASE 1 running -> waiting: I/O 작업이나 이벤트가 발생하여 대기상태에 들어감 (Non-preemptive)
  • CASE 2 running -> ready
  • CASE 3 wating -> ready
  • CASE 4 terminate: 프로세스 종료 후 exit (Non-preemptive)
  • CASE 1 & 4: 자발적으로 상태가 바뀜
  • CASE 2 & 3: Preemptive or Non-preemptive (Preemptive를 주로 선택. 당연한 선택)

Dispatcher

CPU 제어권을 바꿔주는 장치

functions of dispatcher:

  • Context Switching (문맥 교환)
  • user mode로 전환
  • 새로운 프로세스의 위치로 resume

Dispatcher는 가능한 최대로 빨라야 함

  • 모든 context switch마다 일어나기 때문

문맥 교환시 지연되는 시간을 (save PCB or restore PCB) dispatcher latency 라고 함
따라서 dispatcher latency는 짧아야 함

  • $ vmstat 1 3
    cs부분에 나오는 숫자가 1초에 context switching이 일어나는 횟수
  • $ cat /proc/1/status | grep ctxt
    voluntary_ctxt_switches: Non-preemptive
    nonvoluntary_ctxt_switches: preemptive

CPU Scheduling Algorithm

FCFS (Fist-Come, First-Serve)

  • CPU를 먼저 요청한 프로세스에 CPU를 할당
  • FIFO Queue에 도착한 프로세스를 순서대로 pop한 후 실행

  • 프로세스가 P1, P2, P3 순서로 큐에 들어올 때
  • Waiting Time
    - P1: 0s / P2: 24s / P3: 27s
    - Total Waiting Time: 51s
    • Average Waiting Time: 51/3 = 17s
  • Turnaround Time
    - P1: 24s / P2: 27s / P3: 30s
    - Total Turnaround Time: 81s
    • Average Turnaround Time: 81/3 = 27s

  • 프로세스가 P2, P3, P1 순서로 큐에 들어올 때
  • Waiting Time
    - P2: 0s / P3: 3s / P1: 6s
    - Total Waiting Time: 9s
    • Average Waiting Time: 9/3 = 3s
  • Turnaround Time
    - P2: 3s / P3: 6s / P3: 30s
    - Total Turnaround Time: 39s
    • Average Turnaround Time: 39/3 = 13s

도착 순서만 바꼈을 뿐인데
Waiting Time이 17s -> 3s로 바뀜
Turnaround Time이 27s -> 13s로 바뀜

  • Convoy Effect:
    CPU-burst 시간이 긴 프로세스가 아주 짧은 CPU-burst 시간을 가지는 프로세스보다 먼저 왔을 때 나머지 프로세스 들이 기다리는 시간이 길어지는 것을 의미

FCFS 알고리즘은 Non-preemptive

SJF (Shortest Job First)

  • 작업 시간이 짧은 것부터 실행
  • shortest-next-CPU-burst-fist scheduling

  • 프로세스 도착 순서: P1(6s) / P2(8s) / P3(7s) / P4(3s)
  • Waiting Time
    - P4: 0s / P1: 3s / P3: 9s / P2: 16s
    - Total Waiting Time: 28s
    • Average Waiting Time: 28/4 = 7s
  • Turnaround Time
    - P4: 3s / P1: 9s / P3: 16s / P2: 24s
    - Total Turnaround Time: 52s
    • Average Turnaround Time: = 52/4 = 13s

SJF 알고리즘은 provably optimal. 즉 최적임을 증명할 수 있다.

  • minimum average waiting 시간임을 증명할 수 있다.

P2 (작업 시간이 긴 프로세스) 앞으로 P1 (작업 시간이 짧은 프로세스) 을 이동시켰을 때 P2의 WT(Waiting Time)이 0초에서 3초로 늘어난 것 보다 P1의 WT이 6초에서 0초로 줄어든 것이 훨씬 더 효율적

하지만 SJF는 구현을 할 수 없다.

  • next CPU-burst 시간을 알 수 없다.

비슷하게 구현하는 방법은

  • next CPU-burst 시간을 예측
    - 과거에 측정된 값을 통해 Exponential Average(지수적 평균)를 구하여 예측

SJF는 Preemptive, Non-Preemptive 둘 다 된다

Preemptive

  • 프로세스가 실행중이더라도 ready queue에 도착하는 프로세스의 작업 시간이 짧다면 나중에 도착한 프로세스에게 CPU 점유를 뺏긴다.

Non-Preemptive

  • 프로세스가 실행중일 때 자신보다 작업시간이 더 긴 프로세스가 ready queue에 들어오면 현재 프로세스는 끝까지 진행

하지만 ready queue에 들어갈 때 마다 남은 CPU-burst 타임을 알아야 한다

SRTF (Shortest Remaining Time First)

SRTF == Preemptive SJF Scheduling

  • ready queue에 들어온 process가 현재 실행중인 프로세스의 CPU-burst 시간(Remaining Time) 보다 더 작으면 switching

Process - Arrival Time - Burst Time
P1 - 0 - 8
P2 - 1 - 4
P3 - 2 - 9
P4 - 3 - 5

  • Waiting Time
    - P1: (10 - 1) = 9s / P2: (1 - 1) = 0s / P3: (17 - 2) = 15s / P4: (5 - 3) = 2s
    - Total Waiting Time: 26s
    • Average Waiting Time: 26 /4 = 6.5s

RR (Round-Robin)

Preemptive FCFS with time quantum(time slice)

  • 보통 10ms
  • ready queue는 circular queue로 구현
  • CPU-burst 시간이 time quantum 보다 짧다면?
    - 자발적으로 프로세스를 종료 하고 CPU를 release
  • 길다면?
    - timer가 interrupt를 통해 OS에게 CPU 넘겨줌
    - Context Switching이 일어나고 현재 프로세스는 큐의 꼬리에 들어감

프로세스 / Burst time

  • P1 / 24
  • P2 / 3
  • P3 / 3
    time quantum: 4s

P2의 경우 time quantum 보다 짧아 자발적으로 종료됨

  • Waiting Time
    - P1: (10 - 4) = 6s / P2: 4s / P3: 7s
    - Total Waiting Time: 17s
    • Average Waiting Time: 17/3 = 5.66s

RR의 평균 대기 시간은 대부분의 상황에서 더 크다

  • 그렇기 때문에 다른 알고리즘과 함께 활용
  • time quantum을 얼마나 주냐에 따라 성능이 달라진다

  • time quantum을 각각 12s, 6s, 1s로 주었을 때 context switching은 각각 0회, 1회, 9회 일어남
  • context switching이 일어날 때 dispatch latency가 발생
  • quantum time을 무한대로 주면 FCFS 방식과 동일

Priority-based

  • SJF도 Prioirity-based 중 하나 (next CPU burst를 기준으로 잡음)
  • Preemptive or Non-preemptive
  • starvation 상황 발생:

MLQ (Multi-Level Queue)

MLFQ (Multi-Level Feedback Queue)

자료 캡쳐 및 참고:

profile
: )

0개의 댓글