05. CPU 스케줄링

CPU만 쓰는 단계 - CPU burst
I/O만 하는 단계 - I/O burst

 

I/O-bound process (many short CPU bursts) - 계산 시간보다 I/O에 많은 시간이 필요한 job
CPU-bound process (few very long CPU bursts) - 계산 위주의 job
CPU-burst time의 분포를 확인하니 CPU만 오랫동안 쓰는 빈도보다 짧은 간격으로 I/O 작업을 수행하는 빈도가 높았다.
I/O는 유저와 직접적인 상호작용을 하는 작업.
더 좋은 사용자 경험을 제공하기 위해 interactive job에게 더 우선적으로 CPU를 제공해야 한다

스케줄러 & 디스패처

둘은 전부 운영체제 안의 코드이다.
CPU Scheduler - Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다
Dispatcher - 스케줄러가 선택한 프로세스에게 CPU 제어권을 넘긴다 (= context switch)

CPU 스케줄링이 필요한 경우

1. Running -> Blocked
   • 어떤 프로세스가 실행되다가 오래 걸리는 작업을 하러 간 경우 (ex. i/o 작업을 하는 경우)
2. Running -> Ready
   • timer interrupt
3. Blocked -> Ready
   • 작업 완료 후 다음 instruction을 실행할 수 있는 상태가 되었을 때 (ex. i/o 작업이 끝난 경우)
4. Terminate

강제로 빼앗는 경우 preemptive - 2, 3
자진반납의 경우 nonpreemptive - 1, 4

CPU를 누구에게 줄 것인가 & CPU를 주고 나서 계속 쓰게 할 것인가 (선점형/비선점형)

성능 척도

시스템 입장

• CPU utilization 이용률
• Throughput 처리량

사용자 입장

• Turnaround time 소요시간, 반환시간
• Waiting time 대기시간
• Response time 응답시간

CPU 스케줄링 알고리즘

01. FCFS (First-Come First-Served)

먼저 온 순서대로 처리
효율적이지는 않다
CPU를 오래 쓰는 프로그램이 도착하게 되면 뒤 프로그램은 마냥 기다려야 한다. = convoy effect

02. SJF (Shortest-Job-First)

CPU를 가장 짧게 쓰는 프로그램에게 먼저 준다
두 가지 방법이 있다

1. Nonpreemptive: 일단 CPU를 잡으면 더 짧은 프로세스가 와도 내어주지 않음
2. Preemptive: 더 짧은 프로세스가 도착하면 그 프로세스에게 내어준다 (짧다의 기준은 CPU burst time)
   Shortest-Remaining-Time-First
   선점형 SJF 버전이 가장 평균 시간이 짧다

문제점

1. Starvation
   극단적으로 CPU 시간이 짧은 것을 선호한다. CPU 사용 시간이 엄청 긴 프로세스는 영원히 CPU를 점유받지 못할 수도 있다.
2. CPU를 얼마나 쓰고 나갈지 알 수가 없다
   언제 어떤 프로세스가 도착할지 추정하기가 어렵기 때문

Priority Scheduling

두 버전으로 구현 가능
우선순위가 더 높은 것이 도착하면 그것에게 넘겨주거나 안 넘겨주거나
starvation을 해결하기 위해 aging을 도입
aging = 우선순위가 낮은 프로세스더라도 오래 기다리면 우선순위를 높여주는 방법
그렇게 하면 모든 프로세스가 cpu를 점유할 수 있게 됨

Round Robin (RR)

현대적 프로그램은 대부분 라운드로빈 기반
각 프로세스는 동일한 크기의 할당 시간을 받음
할당 시간이 지나면 다른 프로세스에게 선점당하고 ready queue의 제일 뒤로 가서 다시 기다린다.

장점

• 응답 시간이 빨라진다

할당 시간을 너무 크게 주면 FCFS랑 같은 방식이 됨
할당 시간을 너무 적게 주면 Context Switching이 자주 발생하여 오버헤드가 커진다.
일반적으로 10~100ms를 할당한다.

Multi-level queue

Ready queue를 분할한다.
각 큐의 특성에 따라 독립적인 스케줄링 알고리즘을 갖는다

 

고려해야 할 것

1. 프로세스를 어느 줄에 보낼 건지
2. 줄에 들어와서 어떤 프로세스에게 CPU를 줄 건지

• 우선순위로 할 경우 - starvation의 발생 가능성
• time slice - 80퍼센트는 우선순위가 높은 프로세스에, 20퍼센트는 낮은 프로세스에게

Multi-level feedback queue

GeeksforGeeks

큐별로 할당 시간을 정해두고 그 시간 내에 다 하지 못하면 우선순위를 내리고 또 내리고 내리는 방식
CPU 사용 시간이 짧은 프로세스가 자연스럽게 먼저 실행된다.

Multiprocessor Scheduling (CPU가 여러 개 있을 경우)

CPU가 여러 개 있으면 스케줄링은 복잡해진다.

보통 queue에 한 줄로 세워서 CPU가 알아서 꺼내가도록 하지만, 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있으면 더 복잡해진다

Load Sharing - 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요하다
symmetric multiprocessing - 각 프로세서가 알아서 스케줄링을 결정한다 (현재 가장 흔한 방법)
asymmetric multiprocessing - 한 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 그에 따른다

Real-time Scheduling

hard real-time scheduling
정해진 시간 안에 반드시 끝내야 함
미리 스케줄링해서 데드라인이 보장되도록

soft real-time computing
일반 프로세스에 비해 높은 우선순위를 갖도록 함

Thread Scheduling

스레드에는 커널 스레드와 유저 스레드가 있음. 종류에 따라 스케줄링 방식이 다르다.

Local Scheduling
user level thread
사용자 수준의 thread library가 스레드 스케줄링

 

Global Scheduling
kernel level thread
일반 프로세스와 마찬가지로 커널 단기 스케줄러가 결정

알고리즘 평가

어떤 스케줄링 알고리즘이 좋은지 평가하는 방법

1. Queueing Models
   프로세스의 도착률과 CPU가 프로세스를 처리하는 처리율이 확률 분포로 주어질 때 복잡한 계산을 통해 성능 지표 값을 도출
2. Implementation & Measurement
   실제로 스케줄링 알고리즘을 시스템에 구현해보고 직접 측정해보는 것
3. Simulation
   알고리즘을 모의 프로그램으로 작성해 trace를 input으로 하여 결과 비교