5강) CPU 스케줄링 (CPU Scheduling)

Computer Science/운영체제

열심히 사는 우진 2023. 1. 26. 03:42

** KOCW에서 반효경 교수님의 운영체제(2014년) 강의를 수강한 내용을 정리한 글입니다.

[운영체제

운영체제는 컴퓨터 하드웨어 바로 위에 설치되는 소프트웨어 계층으로서 모든 컴퓨터 시스템의 필수적인 부분이다. 본 강좌에서는 이와 같은 운영체제의 개념과 역할, 운영체제를 구성하는 각

프로그램은 CPU burst와 I/O burst가 번갈아서 진행된다.

Burst : 연속적으로 실행하고 있는 단계

CPU Scheduler
- Ready 상태의 프로세스 중에서 CPU를 넘겨줄 프로세스를 고른다
- 운영체제 안의 코드로 존재
Dispatcher
- CPU의 제어권을 넘기는 역할
  - 이 과정을 Context switch(문맥 교환)라고 한다.
- 운영체제 안의 코드로 존재
CPU 스케쥴링이 필요한 경우는 다음과 같은 상태 변화가 있는 경우이다.
1. Running → Blocked(eg: I/O 요청하는 시스템 콜)
2. Running → Ready(eg: 할당시간 만료로 Timer interrupt)
3. Blocked → Ready(eg: I/O 완료 후 인터럽트)
4. Terminate2, 3 등 그 외 모든 스케줄링 → Preemptive (강제로 빼앗음)
5. 1, 4 → Nonpreemptive (자진 반납)

CPU 입장에서
- CPU utilization (이용률)
  - CPU가 가능한 바쁘게 유지하기
- Throughput(처리량)
  - 단위 시간 당 완료하는 실행
프로세스 입장에서
- Turnaround time (소요시간, 반환시간)
  - 특정 프로세스를 실행하는 데에 걸린 시간 (Ready queue에 들어와서 실행을 마치고 나가기까지)
- Waiting time (대기 시간)
  - 순수하게 기다린 시간(in ready queue)
  - CPU burst 동안에 생기는 대기까지 모두 포함
- Response time (응답 시간)
  - Ready queue에 들어와서 처음 CPU를 얻기까지 걸린 시간
위 얘기들은 프로세스가 실행되어 종료되기까지를 얘기하는 것이 아니라
→ 한 번의 CPU burst에 있어서를 얘기하는 것!

각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용
CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
Two schemes
- Nonpreemptive : 일단 CPU를 잡으면, CPU burst 완료 시까지 CPU를 선점(preemption) 당하지 않음
- Preemptive : 현재 수행 중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스 도착 시 → CPU를 빼앗김 (SRTF : Shortest-Remaining-Time-First)
SJF is optimal for Waiting time
- 주어진 프로세스들에 대해 Minimum average waiting time을 보장 (SRTF)

Starvation(기아 현상)
1. → CPU burst time이 긴 프로세서는 너무 오래 실행되지 않을 가능성이 있음
CPU Burst time 예측이 불가능함
1. branch, user input 등이 있기 때문
2. 추정만이 가능 → 과거의 CPU burst time을 이용해서 추청 (exponential averaging)

각 프로세스에 우선 순위가 할당됨
- 높은 우선 순위(작은 Integer)의 프로세스에게 CPU 할당
- Preemptive와 Nonpreemptive
SJF는 일종의 Priority scheduling이다.
- 우선 순위 → 다음 CPU burst time의 예측값이 낮은 순
문제점 : Starvation(기아 현상) → Low priority 프로세스가 실행되지 않을 수 있다.
- 해결 : Aging(노화) ㅍ 시간이 지남에 따라 Priority를 높인다.

현대 운영체제 스케줄링은 RR에 기반
각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐
- 일반적으로 10~100ms
할당 시간이 지나면 프로세스는 선점(preempted)당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다
n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우, 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다.
→ 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
Performance
- q large → FCFS(First-Come First-Served)
- q small → Context switch 오버헤드가 커진다

Ready queue를 여러 개로 분할
- 각 큐는 독립적인 스케줄링 알고리즘을 가짐
- Foreground (interactive) : RR
- Background (batch - no human interaction) : FCFS
큐에 대한 스케줄링이 필요
1. Fixed priority scheduling
  - Foreground 먼저 제공하고 Background 제공
  - Starvation 가능성
2. Time slice
  - 각 큐에 CPU time을 적절한 비율로 할당
  - Eg., 80% to foreground in RR, 20% to background in FCFS

CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐
Homogeneous processor인 경우 (균일한 프로세서)
- Queue에 한 줄로 세워서 각 프로세서가 꺼내가게 할 수 있음
- 특정 프로세서에서만 수행되어야 하는 프로세스가 있는 경우 → 문제가 복잡해짐
Load sharing
- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요
- 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
Symmetirc Multiprocessing (대등한, 대칭 CPU)
- 각 프로세서가 각자 알아서 스케줄링 결정
Asymmetric Multiprocessing (비대칭 CPU)
- 하나의 프로세서가 시스템 데이터 접근, 공유를 전담
- 나머지 프로세스는 거기에 따름

Local Scheduling
- User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
Global Scheduling
- Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정