CPU 스케줄링
ready queue에 있는 프로세스 중에서 어떤 프로세스에게 CPU를 줄까 결정하는 문제
여러 종류의 job(process)가 섞여 있기 때문에 CPU 스케줄링이 필요
- I/O-bound process: CPU를 오래 잡고 있진 않지만 사용자와 interaction
- CPU-bound process: CPU를 오래 사용하지만 빈번하진 않음
Scheduler & Dispatcher
- CPU Scheduler : 이번에 CPU에게 줄 프로세스를 고름
- Dispatcher : CPU Scheduler에 의해 선택된 프로세스에게 CPU 제어권을 넘김 = 문맥 교환
스케줄 요소
- 누구한테 줄거냐
- 줬다면 중간에 뺏어올 것이냐 계속 줄거냐
➡️ 공평하지만 효율적이여야 함
스케줄의 성능 척도
1. 이용률(CPU Utilization)
- 전체 시간에서 CPU가 일한 시간의 비율
2. 처리량(Throughput)
- 주어진 시간동안 CPU가 처리 완료한 일의 양
➡️ 시스템 입장 - CPU로 최대한 일을 많이 시키기
3. 소요시간(Tournaround time)
- CPU를 얻은 후 일을 완료 후 다시 반환할 때 까지의 시간
4. 대기 시간(Waiting time)
- CPU를 쓰기 위해 기다린 시간(중간에 CPU를 뺏겨서 기다린 시간을 포함)
5. 응답 시간(Response time)
- ready queue에 들어와서 처음으로 CPU를 얻기까지의 시간
➡️ 프로그램 입장 - CPU를 빨리 얻어서 빨리 처리
선점 방식
1. 비선점형 방식(non-preemptive)
- 완료해서 자진 반납할 때까지 기다리는 방법
2. 선점형 방법(preemptive)
- 강제로 빼앗을 수 있는 방법
ex) timer interrupt
스케줄링 방법
1) FCFS(First-Come First-Served)
- 비선점형 스케줄링
- 먼저 온 순서대로 실행
- 공평한 방식
- 기다리면 언젠간 실행 가능
단점
- 오래 사용하는 프로세스가 잡고 있으면 다른 프로세스는 기다려야 함
- time sharing이 되지 않음
- 프로세스가 들어오는 순서에 따라 wating time의 편차가 큼 = Convoy effect
2) SJF(Shortest-Job-First)
- 프로세스 사용이(CPU burst time)이 가장 짧은 프로세스를 먼저 스케줄
- 평균 wating time이 짧음 -> SRTP 경우가 더 짧음
- 비선점형 방식
-> 더 짧은 프로세스가 와도 전부 실행될 때까지 진행 - 선점형 방식
-> 더 짧은 프로세스가 오면 뺏어서 넘겨질 수 있음 = SRTF(Shorted-Ramainig-Time-First) - 스케줄링 시점: 비선점형 = 프로세스가 CPU를 반납할 때, 선점형 = 새로운 프로세스가 왔을 때
단점
- Starvation: CPU 사용 시간이 긴 프로세스는 계속 사용을 못할 수도 있음
- CPU 사용 시간을 미리 알 수 없음 -> 이전 사용 이력으로 예측 할 순 있음
3) Priority
- 우선순위가 높은 프로퍼티가 먼저 실행되도록 할당
- 비선점, 선점 방식 가능
- 선점
-> 실행 중 더 높은 우선순위가 오면 빼앗김 - SJF는 실행 시간을 우선순위로 한 기법으로 볼 수 있음
- Starvation 문제 발생
-> Aging : 기다린 만큼 우선순위를 높여주자
4) Round Robin(RR)
- 선점형 스케줄링
- 일반적으로 이 방식을 사용
- 동일한 할당 시간(time quantum)을 부여해서 돌아가면서 실행
- 기다리는 시간은 CPU 사용 시간에 비례(오래 사용할 프로세스 일 수록 많이 기다리게 됨)
- 할당 시간을 너무 길 경우
-> FCFS처럼 동작 - 할당 시간이 너무 짧을 경우
-> 잦은 context switching(오버헤드 🆙) - SJF보다 평균 turnaround time이나 waiting time은 길 수 있지만 평균 응답 시간이 짧다
- CPU 시간이 모두 동일한 프로세스가 있을 경우에는 모두 완료되는 시점이 다 같이 늦어질 수 있음
-> 일반적으로 짧고 긴 프로세스가 섞여 있으므로 대부분 효과적
5) Multilevel Queue
- ready queue를 여러 줄로 분할
- 방법1) 우선 순위 별로 줄서기
ex) system > interactive > interactive editing > batch > student - 방법2) foreground(interactive) vs background(batch)
- 각 큐는 독립적인 스케줄링 알고리즘을 가짐
- 큐에 대한 스케줄링도 필요
- 우선 순위가 낮으면 starvation 발생
-> 큐 별로 할당 시간 비율을 주기 (상위 80%, 하위 20% 할당)
6) Multilevel Feedback Queue
- 프로세스가 경우에 따라 다른 큐로 이동 가능
- 상위 큐, 하위 큐로 나누는 기준이 필요
- 일반적으로 처음에 상위 큐로 할당한 후 RR로 퀀텀 시간을 주고 모두 소요 하면 하위 큐로 이동(퀀텀 시간은 더 긴) -> 나중에는 FCFS로 처리
7) Multi-Processor Scheduling
- CPU가 여러 개일 경우 스케줄링이 복잡해짐
- homogeneous processor
-> 큐에 한 줄로 세워서 CPU가 알아서 꺼내가도록
-> 특정 CPU에서 실행해야 하는 프로세스가 있다면 더 복잡해짐 - load sharing
-> 일부 프로세서에 job이 몰리지 않도록 메커니즘이 필요 - Symmetric Multiprocessing(SMP)
-> 각 프로세서가 알아서 스케줄링 결정 - Asymmetric Multiprocessing
-> 하나의 프로세서가 시스템 데이터 접근과 공유를 책임지고 나머지 프로세서는 그에 따름
Real-Time Scheduling
Hard real-time systems
- 정해진 시간 안에 반드시 끝내도록 스케줄링 해야 함
Soft real-time systems
- 일반 프로세스에 비해 높은 Priority를 갖도록 함
Thread Scheduling
Local Scheduling
- user level thread - 운영체제는 스레드를 모르고 프로세스가 관리하는 경우
- 프로세스에게 스케줄링하면 프로세스가 알아서 어떤 thread를 스케줄할지 결정
Global Scheduling
- kernel level thread - 운영체제가 스레드를 알고 있는 경우
- 알고리즘에 따라 운영체제가 thread 스케줄링을 결정
알고리즘 평가 방법
Queueing modles
- 확률 분포로 도착률과 처리률을 계산
implementation & Measurement
- 실제 시스템에 구현한 후 직접 돌려보고 측정
Simulation
- 모의 프로그램을 작성 후 trace룰 입렬으로 결과 비교
iOS Developer