[ 이화여대 운영체제 - 반효경 교수님 강의 ]
CH5. CPU Scheduling
CPU and I/O Bursts in Program Execution
- 사람이 반응하는 프로그램은 CPU & I/O burst 가 짧아지고 많아진다
- 세포 분석 프로그램은 I/O burst 가 적다
CPU-burst Time 분포
프로세스 특성 분류
CPU Scheduler & Dispatcher
- CPU Scheduler
- Dispatcher
- CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스를 넘긴다.
- context switch
1,4 -> 비선점형(non-preemptive) = 강제로 빼앗지 않고 자진 반납
2,3 -> 선점형(preemptive) = 강제로 빼앗음
- 현대에는 거의 preemptive 한 스케줄링을 사용한다.
CPU Scheduling
- 누구한테 할당할 거냐
- preemptive vs nonpreemptive
Scheduling Criteria
= performance Index, performance Measure ,성능 척도
System 입장
- CPU utilization (이용료)
- keep the CPU as busy as possible
- 전체 시간 중에 CPU가 일한 시간
- Throughput (처리량)
- 주어진 시간 동안 몇 개의 작업을 완료 했는지
Process 입장 ⇒ 시간 관련
- Turnaround time (소요시간)
- CPU를 쓰러 들어와서 다 쓰고 나갈 때 까지의 시간
- Waiting time (대기 시간)
- Response time (응답 시간)
waiting time vs response time
waiting time
- CPU를 얻었다가 뺏겼다 얻었다 뺐겼다 하며 총 기다린 시간
response time
중국집 비유
-
주방장
-
손님 입장
-
Turnaround time : 가게에 와서 다먹고 나가는데 까지 걸린 시간
-
Waiting time : 손님이 밥을 먹은 시간 말고 기다린 시간들의 합
-
Response time : 첫 음식을 받기까지 걸린 시간 / 늦게 주면 허기가 져서 당이 떨어짐 / 큰일남 / 중요
CPU Scheduling Algorithm
종류
-
FCFS (First-Come First-Served)
-
SJF (Shortest-Job-First)
-
SRTF (Shortest-Remaining-Time-First)
-
Priority Scheduling
-
RR (Round Robin)
-
Multilevel Queue
-
Multilevel Feedback Queue
1. FCFS (First-Come First-Served)
먼저 온 순서대로 처리하는 것
- nonpreemptive
- 효율적이지 않음
- CPU 오래쓰는 애가 먼저 오면 오래 기다려야 함
Convoy effect
-> 앞의 긴 작업 때문에 큐에서 짧은 작업들이 기다리는 현상
Waiting time : p1 = 0, p2 = 30, p3= 33
Waiting time : p1 = 4, p2 = 0, p3= 3
convoy effect
- 1차 세계 대전 때 나온 개념
- 전쟁 물자를 앞 뒤에서 보호함
2. SJF (Shortest-Job-First)
각 프로세스의 다음 번 CPU burst Time을 가지고 스케줄링에 활용하여 이 시간이 가장 짧은 프로세스 를 제일 먼저 스케줄한다.
- minimum average waiting time (Preemptive version)
Two schemes
- Nonpreemptive
- 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점 당하지 않음
- Preemptive
- 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
Example : Non-Preemptive SJF
- CPU를 다 쓰고 나가는 시점에 스케줄링이 일어남
Example : Preemptive SJF
- Nonpreemptive 보다 빠름
- 새로운 프로세스가 도착하면 언제든 스케줄링이 일어남
SJF 문제점
- starvation : CPU burst가 긴 작업(long-precess)들은 영원히 실행 X
- CPU 실행 시간을 미리 알 수 없음
다음 CPU Burst Time 의 예측
- t : 실제 CPU 사용시간
- T : CPU 예측 시간
- a , 0 ≤ a ≤ 1
최근 거는 가중치 높게, 예전 거는 가중치 낮게 해서 예측
3. Priority Scheduling
개발자가 우선순위 프로세스에게 부여하는 순서대로 스케줄링이 된다.
문제
- starvation : 낮은 우선순위는 영원히 실행 X
해결방법
- Aging : 시간이 지날수록 프로세스의 우선순위를 높임
4. RR (Round Robin)
공평하게 프로세스들이 돌아가면서 수행하는 알고리즘
- 현대적인 CPU 스케줄링은 RR에 기반함
- 응답 시간이 빠르다
- 각각의 프로세스는 동일한 크기의 할당 시간 time quantum(= time slice)을 가짐
- 일반적으로 10-100 milliseconds
- 어떤 프로세스도 (n-1)*q time unit 이상 기다리지 않는다.
Performance
- q large : FCFS
- q small : context switch 오버해드가 발생 (10~100ms 적당)
특이한 예
- 비슷한 실행 시간 가진 것들만 많으면 모든 것이 한 번에 끝날 수도 있음
Example : RR with Time Quantum = 20
중요 장점 : response time 짧음
Turnaround time Varies With Time Quantum
5. Multilevel Queue
- Ready queue를 여러 개로 분할
- foreground (interactive) / 우선순위가 높음
- background (batch - no human interaction) / starvation이 일어날 수 있음
- 각 큐는 독립적인 스케줄링 알고리즘을 가짐
- foreground - RR (공정)
- background - FCFS
- 큐에 대한 스케줄링이 필요 (해결법)
- Fixed priority scheduling -> 우선 순위 레벨 고정
- Time slice
- 각 큐에 CPU time을 적절한 비율로 할당
6. Multilevel Feedback Queue
프로세스들이 상황에 따라 queue와 queue 사이를 이동할 수 있는 스케줄링 알고리즘
-
queue 하나에 대해 RR을 적용하는것 보다 더 CPU burst가 짧은 프로세스를 우대해주는 스케줄링 방식이다.
-
프로세스가 다른 큐로 이동 가능
-
Aging을 이와 같은 방법으로 구현할 수 있음
-
Multilevel Feedback Queue
-
RR 만으로는 부족
-
처음 들어오는 큐는 우선순위 가장 높은 큐에 넣는다
-
time quantum 짧게 주고 RR 방식 이용
- 상위 queue에서 할당한 시간이 만료될 경우 바로 다음 하위 queue로 강등되며 상위 queue가 빌 때 까지 대기해야 함
-
내려갈 수록 점점 time quantum 길게 준다, 맨 아래 큐는 FCFS 방식 이용
7.Multiple-Processor Scheduling
CPU가 여러 개인 경우 스케줄링은 더욱 복잡
- Homogeneous processor 인 경우
- Queue에 한줄로 세워서 각 프로세서사 알아서 꺼내가게 할 수 있다
- Load sharing
- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 매커니즘 필요
- 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
- Sysmmetric Multiprocessing (SMP)
- Asymmetric multiprocessing
- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름
8.Real-Time Scheduling
Hard real-time systems
- 정해진 시간 안에 반드시 끝내도록 스케줄링 해야함
Soft real-time computing
- 일반 프로세스에 비해 높은 priority를 가지게 함
9.Thread Scheduling
Local Scheduling
- User level thread 의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄링할지 결정
- 운영체제는 thread를 모름
- 사용자 프로세스가 직점 어느 쓰레드에 CPU 줄지 결정
Global Scheduling
- Kernel level thread의 경우 일반 프로세스와 마찬 가지로 커널 단기 스케줄러가 어떤 thread를 스케줄링할지 결정
Algorithm Evaluation
Queueing models
- 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index값을 계산
Implementation(구현) & Measurement(성능 측정)
- 실제 시스템에 알고리즘을 구현하여 실제 작업(work)에 대해 성능 측정 비교
Simulation(모의 실험)
- 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교