본 포스트는 이화여대 반효경교수님의 운영체제 강의를 듣고 정리한 글입니다.
📌 CPU Scheduling
CPU가 하나의 프로세스 작업이 끝나면 다음 프로세스 작업을 수행함
이때 다음 프로세스가 어느 프로세스인지를 선택하는 알고리즘을 CPU Scheduling 알고리즘이라고 한다.
CPU는 여러 종류의 프로세스를 수행하기 때문에 CPU 스케줄링이 필요함
➡️ interactive job(process)에게 적절한 response를 제공해줘야 함
➡️ CPU와 입출력 장치 등 시스템 자원을 골고루, 효율적으로 사용해야함!
( 무작정 먼저 입력된 프로세스부터 처리하는 게 좋은게 아님)
Process
프로세스는 특성에 따라 두가지로 나뉨
I/O-bound process
CPU를 잡고 계산하는 시간보다 입출력에 많은 시간이 필요한 job
많지만 짧은 CPU burstsCPU-bound process
계산 위주의 job
적지만 긴 CPU burst
CPU burst : CPU만 연속적으로 쓰면서 instruction을 실행하는 일련의 단계
I/O burst : I/O를 실행하는 단계
모든 프로그램은 CPU, I/O burst의 연속이지만, 프로그램의 종류에 따라서 각 burst의 빈도나 길이가 다르다.
CPU Scheduler
누구에게 CPU를 줄 것인지/얼마나 쓰게 할 것인지를 결정하는 역할
Ready상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고름!
Dispatcher
CPU의 제어원을 CPU scheduler에 의해 선택된 프로세스에게 넘김!
이 과정을 context switch라고 함
CPU Scheduling이 필요한 상황
-
Running→Blocked(nonpreemptive)
CPU 잡고 있던 프로세스가 I/O 작업 등을 이유로 자진해서 CPU를 반납 -
Running→Ready
할당시간 만료로 timer interrupt가 발생한 경우 -
Blocked→Ready
I/O 완료 후 interrup가 발생한 경우 (CPU를 얻을 수 있는 권한을 줌)
I/O 종료되었다고 해서 바로 CPU를 넘겨야 할 필요는 없으나(일반적으로는 넘기지 않으나), 바로 CPU를 넘기는 경우도 있음
priority에 기반한 scheduling을 할 경우, 해당 프로세스의 priority가 클 경우 바로 CPU를 넘겨주기도 함
따라서 이 때 CPU Scheduling이 필요할 수도 있음 -
Terminate(nonpreemptive)
CPU 사용이 마무리 된 경우 자진해서 CPU를 반납
📌 Scheduling Algorithms
FCFS
First Come First Service
먼저 온 순서대로 처리
- 그다지 효율적이지는 않음😢
CPU를 오래 쓰는 프로그램이 CPU를 잡아버리면 interactive한 job들이 계속 대기해야 함
Convy Effect
✅ 긴 프로세스가 먼저 도착해서 짧은 프로세스들이 지나치게 오래 기다려야 하는 현상
이 발생 가능!
SJF
Shortest-Job-First
CPU burst time이 가장 짧은 프로세스를 가장 먼저 스케줄
average waiting time을 최소화하는 알고리즘
두가지 방식이 있음
1. Nonpreemptive
- 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점당하지 않음
- 한 프로세스가 CPU를 다 쓰고 나가는 시점에 스케줄링을 할지 말지를 결정
2. Preemptive
- 현재 수행중인 프로세스의 남은 burst time 보다 짧은 CPU burst time을 가진 새로운 프로세스가 도착하면 CPU 뺏김
== SRTF (Shortest-Remaining-Time-First) - 새로운 프로세스가 도착하면 언제든지 스케줄링이 일어날 수 있음
문제점
-
starvation
극단적으로 CPU 사용시간이 짧은 job을 선호함
➡️ CPU 사용시간이 긴 프로세스는 영원히 CPU를 받지 못할 수 있음 -
CPU 사용시간을 미리 알 수 없음
branch, user input 등을 예측할 수 없음
추정할 수는 있음
➡️ user interaction이 있는 경우 CPU burst가 짧음
➡️ 과거에 CPU를 사용한 흔적 등으로 예측
Priority Scheduling
우선순위가 가장 높은 프로세스에게 CPU 줌
- 일반적으로 우선순위는 integer로 표현
높은 우선순위 = 작은 integer - non-preemptive/preemptive 방식을 생각해볼 수 있음
- SJF도 priority scheduling의 일종이라고 볼 수 있음
priority = CPU 사용시간으로 정의한 priority scheduling 방식
문제점
SJF의 문제점 그대로 가져감
- starvation
해결 - Aging
- 특정 프로세스가 지나치게 차별받는 것을 막기 위한 방식
== starvation problem의 해결책오래 기다리면 우선순위를 높여주는 방식
→ 아무리 낮은 우선순위를 가지고 있더라도 시간이 지나면 우선순위가 높아질 것
Round Robin
CPU를 줄 때 할당시간(time quantum)을 세팅해서 주고, 할당시간이 끝나면 timer interrupt로 인해 CPU를 빼앗기고 ready queue에서 다시 줄을 서는 방식
-
현대적인 컴퓨터 시스템에서 사용하는 CPU 스케줄링은 RR에 기반함
-
response time이 빠름
== CPU를 최초로 얻기까지 걸리는 시간이 빠름
✅ 조금씩 CPU를 줬다뺏었다 하기 때문
ex) ready queue에 n개의 프로세스가 있고, 할당 시간이 q time unit일 경우, 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않음
누가 CPU를 오래 쓸지 모르는 상황에서 굳이 예측할 필요가 없이, CPU를 짧게 쓰는 프로세스가 빠르게 CPU를 쓰고 나갈 수 있음 -
waiting time이 본인이 CPU를 사용하려는 시간에 비례함
CPU를 짧게 쓰는 프로세스는 한번 할당되었을 때 바로 끝낼 수 있으므로 한번만 기다리면 되고, 길게 쓰는 프로세스는 할당됐다가 뺏겼다..를 반복 -
q time unit의 크기
q가 클 경우 → FCFS와 동일하게 동작
q가 작을 경우 → RR의 철학 상으로는 이상적이나, context switch 오버헤드가 커짐 -
CPU 사용시간이 짧고 긴 프로세스들이 섞여있을 때 사용하기 좋은 알고리즘임
동일한 CPU 사용시간을 가진 프로세스가 여러 개 있는 경우, 즉 100초짜리 프로세스 10개가 있을 경우 다같이 1000초가 되는 지점에 끝나게 됨 -
context를 save하고, switch하는 것이 가능하기 때문에 가능한 알고리즘임
Multilevel Queue
ready queue를 여러 개로 분할
(이전까지는 한 줄 서기, 요거는 여러 줄 서기라고 보면 됨!)
- 줄마다 우선순위가 다름
출신에 따라서 줄을 서고, priority 순서대로 줄을 처리 - 각 큐는 독립적인 스케줄링 알고리즘을 가짐
- 즉,
큐에 대한 스케줄링이 필요함
➡️ Fixed priority scheduling
foreground 모두 처리 후 background 처리
이 경우 starvation이 발생할 수 있음
➡️ time slice
각 queue에 CPU time을 적절한 비율로 할당하는 방식
ex) 80%는 foreground, 20%는 background에 할당
Multilevel Feedback Queue
✅ 경우에 따라서 프로세스가 줄 간에 이동할 수 있는 스케줄링 방법
✅ multilevel feedback queue scheduler 정의에 필요한 파라미터
- queue의 수
- 각 queue의 scheduling 알고리즘
- process를 상위/하위 queue로 보내는 기준
- 프로세스가 들어갈 queue를 결정하는 기준
✅ 일반적인 방식
- 처음 들어오는 프로세스는 우선순위가 가장 높은 queue에 넣음
- 우선순위가 높은 queue에는 RR time quantum을 짧게 줌
- 아래 queue로 갈수록 RR time quantum을 길게 줌
- 마지막 queue는 FCFS로 처리
- 맨 위 queue에서 할당 시간이 끝나면 아래 queue로 강등
→ 반복.. 하는 방식으로 처리 - 이 경우, CPU burst가 짧은 job은 최상위 queue에서 처리를 끝내고 빠져나갈 수 있음
- CPU burst가 길 경우 점점 아래 queue로 이동, 할당 시간은 더 받게 되지만 queue간의 우선순위에서 밀리게 됨
- CPU 사용시간이 짧은 job에게 우선순위를 크게 주는 방식
Multiple-Processor Scheduling
CPU가 여러 개 있는 경우의 CPU Scheduling 방식
Homogeneous Processor인 경우
- Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가도록 함
- 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우 다른 방식으로 해결해야 함
- ex) 미용실 손님에게 전담 선생님이 있는 경우
Load Sharing
- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
- 한 줄 queue가 아닌 각각의 프로세서에 별개의 queue를 두는 방식을 사용할 수 있음
- ex) 마트에서 각 계산대에 줄서기
Symmetric Multiprocessing (SMP)
- 모든 CPU가 대등함
- 각 프로세서가 알아서 스케줄링 결정
Asymmetric multiprocessing
-하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고, 나머지 프로세서는 거기에 따름
Real-time scheduling
deadline이 있는 job
즉, 정해진 시간 안에 반드시 끝나야 하는 job
hard real-time systems
그때그때 스케줄링하기보다는, 미리 스케줄링을 해서 적재적소에 배치되도록 함
soft real-time computing
soft real-time task는 일반 프로세스보다 높은 priority를 부여해서 처리
Thread scheduling
Local Scheduling
- User level thread에서 사용
- 사용자 프로세스가 직접 thread를 관리하고, 운영체제는 thread의 존재를 모르는 경우
OS는 그냥 해당 프로세스에 CPU를 할당하는 것이고(thread의 존재를 모르니), 해당 프로세스 내에서 어떤 Thread에 CPU를 줄지는 해당 프로세스 내부에서 결정
Global Scheduling
- Kernel level thread에서 사용
- 운영체제가 직접 thread를 관리
일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지를 결정
Algorithm Evaluation
알고리즘 평가방식
Queueing models
- 이론적인 방식
- CPU에 도착하는 도착율(arrival rate)과 CPU가 처리를 끝낸 처리율(service rate)의 정보가 확률분포로 주어질 때, 여러 성능척도 결과를 계산
얼마나 기다렸는지 등..
Implementation(구현) & Measurement(성능 측정)
- 실제 시스템에 구현해서 실행해보고 측정하는 방식
Simulation(모의 실험)
- 알고리즘을 모의 프로그램으로 작성 후 trace를 입력을 하여 결과 비교
- implementation & measurement가 어려울 때 해볼 수 있는 방식
trace : simulation에 들어가는 input data (test case 같은 느낌)
Reference
