CS 정리 | OS | 4. CPU 스케줄링 (2) | kocw 반효경 교수님

Konseo·2023년 9월 11일

운영체제

목록 보기

8/19

각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용
CPU busrt time이 가장 짧은 프로세스를 제일 먼저 스케줄
Two schemes
- Nonpreemptive
  - 일단 CPU를 잡으면 CPU burst가 완료될 떄까지 CPU를 선점(preemption) 당하지 않음
- Preemptive
  - 현재 수행 중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
  - 이 방법을 Shortest-Remaining-Time-First (SRTF)이라고도 부른다.
SJF is optimal 🕵🏼‍♀️ !
- 주어진 프로세스들에 대해 minimum average waiting time을 보장한다
그러나 SJF방식은 매우 치명적인 단점이 존재하는데 첫 쨰로 CPU를 제러중인 프로세스의 Burst Time을 예측할 수 없다는 것이고, 둘 쨰는 starvation 문제를 야기시킨다는 점이다.

각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐 (일반적으로 10-100 millseconds)
할단 시간이 지나면 프로세스는 선점(preempted)당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다.
n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU시간의 1/n을 얻는다.
- 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
성능
- q large => FCFS와 동일한 방식으로 바뀜
- q small => context switch 오버헤드가 커진다
일반적으로 SJF보다 avarage turnaround time이 길지만 response time 은 더 짧다
만약 모든 프로세스가 동일하다면 RR 방식은 효과가 없음

ready queue를 여러 개로 분할
- foreground (interative)
- background (batch - no human interaction)
각 큐는 독립적인 스케줄링 알고리즘을 가짐
- foreground - RR
- background - FCFS
큐에 대한 스케줄링이 필요
- Fixed priority scheduling
  - serve all from foreground then from background
  - prossibility of starvation (-)
- Time slice
  - 각 큐에 CPU time을 적절한 비율로 할당
    - 80%는 foreground 20%는 background 등

multilevel queue + 신분 변동 가능 🕺🏻
프로세스가 다른 큐로 이동 가능
위 사진에 따르면, 만약 현재 프로세스의 cpu burst time이 24라면 level이 계속 떨어져서(=priority가 내려가면서) 최종적으로 FCFS 알고리즘을 갖고 있는 레벨의 큐로 이동하게 됨.
에이징(aging)을 이와 같은 방식으로 구현할 수 있다.
Multilevel-feedback-queue shceduler를 정의하는 파라미터들
- Queue의 수
- 각 큐의 scheduleing algorithm
- process를 상위 큐로 보내는 기준
- process를 하위 큐로 내쫗는 기준
- 프로세스가 CPU 사용권을 받으려할 때 들어갈 큐를 결정하는 기준

위에서 설명한 것(하나의 CPU에 대하여 스케줄링하는 방식에 대해 알아봄)과는 다른 성격의 스케줄링 방식
CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐
Homogeneous processor 인 경우
- queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있음
- 어떤 작업은 반드시 특정 프로세서에서 수행되어야하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
load sharing
- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
- 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
  - ```
  ex. 한 줄 서기? vs 각 칸마다 줄 서기?
```
Symmetric Multiprocessing (SMP)
- 모든 CPU는 대등하다
- 각 프로세서가 각자 알아서 스케줄링 결정
Asymmetric multiprocessing
- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

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

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

어떤 CPU 스케줄링 알고리즘이 좋은 알고리즘일까?

(사진에서 server 부분을 cpu 라고 생각하면 됨)

Queueing models
- 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 Performance index 값을 계산
Implementation (구현) & Measurement (성능 측정)
- 실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정 비교
- ex. 내가 만든 스케줄링 코드를 리눅스에 넣어서 비교
Simulation (모의 실험)
- 알고리즘을 모의 프로그램으로 작성 후 trace(=신빙성 있는 input data)를 입력으로 하여 결과 비교