CPU 스케쥴러
정의
여러개의 프로그램이 실행될 때 해결해야되는 이슈가 발생.
- 여러 Process가 CPU를 점유하려고 할 때, 누구에게 줄 것인가?
- 하나의 Process에게 얼마나 오랫동안 CPU를 할당할 것인가?
이러한 이슈들을 해결하는 작업이 바로 CPU 스케줄링이다. 즉, 어떤 프로세스에게 얼마 동안 CPU를 할당할지 결정하는 작업이라고 할 수 있다.
CPU burst
프로그램 실행중에 연속적으로 CPU를 사용하는 단절된 구간이다. (스케줄링의 단위)
.
I/O burst
프로그램 실행중에 I/O작업이 끝날때까지 block되는 구간이다.
프로세스의 특성 분류
프로세스의 종류에 따라 CPU burst / I/O burst의 빈도와 길이가 다르다. 이러한 특성에 따라 프로세스를 다음의 두 가지로 나눌 수 있다.
✨ I/O bound process
- CPU를 잡고 계산하는 시간보다 I/O에 많이 시간이 필요한 프로세스
- 사용자와의 인터랙션이 많이 들어가는 프로그램이 많다
- many, short CPU bursts
✨ CPU bound process
- 계산 위주의 프로세스
- CPU를 진득하게 쓰는 프로그램
- few, very long CPU bursts
** 여러 종류의 job(=process)이 섞여 있기 때문에 CPU 스케쥴링이 필요하다
- Interactive job에게 적절한 response 제공 요망
- CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용
CPU Scheduler & Dispatcher
✨ CPU Scheduler
- Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다
✨ Dispatcher
- CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다
- 이 과정을 context switch(문맥 교환)라고 한다.
→ CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있
는 경우이다
1. Running → Blocked (예: I/O 요청하는 시스템 골)
2. Running → Ready (예: 할당 시간만료로 timer interrupt)
3. Blocked → Ready (예: I/O 완료후 인터럽트)
4. Terminate
🏴 1, 4에서의 스케줄링은 nonpreemptive (=강제로 빼앗지 않고 자진 반납)
"All other scheduling is preemptive (=강제로 빼앗음)
Scheduling Criteria
: Performance Index(=Performance Measure, 성능척도)
시스템 입장에서의 성능 척도
→ 제한된 시간 내에 최대한 많은 프로세스를 처리 (‘작업량’이 관건)
✨CPU utilization (이용률)
- 전체 시간 중에서 CPU가 쉬지않고 작업을 처리한 시간의 비율
✨Throughput (처리량)
- 시간 단위당 실행을 완료하는 프로세스의 개수
네트워크에서의 처리량은 단위 시간당 전송한 양을 의미
프로세스 입장에서의 성능 척도
→ CPU를 최대한 빨리 얻어서 빨리 실행 (‘시간’이 관건)
✨Turnaround time (소요시간, 반환시간)
- 특정 프로세스가 실행을 요청한 시점부터 완전히 종료된 시점까지의 소요 시간 (실제 실행 시간 외에 ready queue에서의 대기시간과 device queue에서의 대기시간도 포함)
✨Waiting time (대기 시간)
- 프로세스가 CPU사용을 기다린 시간의 총 합
✨Response time (응답시간)
- 요청이 제출된 때부터 '첫 번째 응답'(최초로 CPU를 얻는 시간)이 생성될 때까지 걸리는 시간
(for time-sharing environment)
CPU 스케쥴러 알고리즘
FCFS(First-Come First-Served)
- 프로세스를 들어온 순서대로 실행하는 알고리즘이다. 먼저 온 것이 먼저 서비스를 받는다. (FIFO과 같은것)
- FCFS 알고리즘의 평가 기준은 평균적인 waiting time이고, burst time과 queue에 추가된 순서를 고려하여 계산한다.
Process Burst Time
| Process | Burst Time |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
CASE 1
도착 순서 : P1 → P2 → P3
Waiting time P1 = 0, P2 = 24, P3 = 27
Average waiting time = (0 + 24 + 27) / 3 = 17
CASE 2
도착 순서 : P2 → P3 → P1
Waiting time P1 = 6, P2 = 0, P3 = 3
Average waiting time = (6 + 0 + 3) / 3 = 3
💡 Case1 보다 Case2가 훨씬 효율적이다. 문제는 순서가 어떻게 올지는 모른다.
문제점
✨ Convoy Effect (콘보이 현상)
- burst time이 긴 프로세스가 queue에 먼저 들어오게 되면 다음의 모든 프로세스들은 오래 기다릴 수 밖에 없다.
🏴 Short process가 long process의 뒤에서 오래 기다리는 현상을 콘보이 현상이라 한다
SJF(Shortest Job First)
- 각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용
- CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
✨ Two schemes:
-
Non-Preemptive
✓ 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점(preemption) 당하지 않음 -
Preemptive
✓ 현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김.
✓ 이 방법을 Shortest-Remaining-Time-First(SRTF)이라고도 부른다
✨ SJF is optimal(최적화)
주어진 프로세스들에 대해 minimum average waiting time을 보장
Process Burst Time
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0.0 | 7 |
| P2 | 2.0 | 4 |
| P3 | 4.0 | 1 |
| P4 | 5.0 | 4 |
CASE Non-Preemptive
Waiting time : P1 = 0 , P2 = 6 , P3 = 3, P4 = 7
Average waiting time : (0 + 6 + 3 + 7 ) / 4 = 4
CASE Preemptive
Waiting time : P1 = 9, P2 = 1, P3 = 0, P4 = 2
Average waiting time : (9 + 1 + 0 + 2)/4 = 3
문제점
- Starvation(기아)
- SJF 방식의 경우 우선순위가 낮은 프로세스(long burst time)는 영원히 CPU를 못얻을 수 있다.
- CPU Burst를 알 수 없다.
- 다음번 CPU burst time을 어떻게 알 수 있는가?
(input data, branch, user ...) - 추정(estimate)만이 가능하다.
- 과거의 CPU burst time을 이용해서 추정
- 다음번 CPU burst time을 어떻게 알 수 있는가?
📌 예측 식
τ = 예측 버스트 시간
t = 실제 버스트 시간
α = 가중치
💡 최근 데이터일수록 더 큰 비중으로 반영하고 오래된 데이터 일수록 적은 비중으로 반영하는 특성이 있다. (알파가 0<= α <=1 사이이기 때문에)
📌 위의 식을 풀어보게 되면
τ(n+1) = α * t(n) + (1 - α) * τ(n)
이제 이전 공식에서 τ(n)을 확장해 보겠습니다.
τ(n) = α * t(n-1) + (1 - α) * τ(n-1)
이제 두 번째 방정식의 τ(n)을 첫 번째 방정식으로 대체하십시오.
τ(n+1) = α * t(n) + (1 - α) * [α * t(n-1) + (1 - α) * τ(n-1)]
→ τ(n+1) = α * t(n) + (1 - α) * α * t(n-1) + (1 - α)^2 * τ(n-1)
이 프로세스를 계속하면 수식을 재귀적으로 계속 확장할 수 있습니다.Priority Scheduling
✨ 프로세스마다 적절한 우선순위를 부여하여 우선순위가 높은 프로세스부터 실행하는 알고리즘
✨ 우선순위는 프로세스 생성 시에 사용자에 의해 지정되기도 하고 운영체제에서 내부적으로 메모리 용량이나 실행 시간 등을 기준으로 하여 결정하기도 한다.
✨ highest priority를 가진 프로세스에게 CPU 할당
(smallest integer = highest priority).
- Preemptive
- nonpreemptive
✨ SJF는 일종의 priority scheduling이다
- priority=predicted next CPU burst time
Problem
- Starvation(기아): 낮은 우선순위의 프로세스는 영원히 실행되지 않을 수 있다.
Solution
- Aging: 시간이 경과함에 따라 프로세스의 우선순위를 증가시켜 Starvation 문제 해결.
Round Robin(RR)
✨ 실제 CPU 스케쥴링에서 가장 많이사용는 방법의 근간이 되는 알고리즘
✨ 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐
(일반적으로 10-100 milliseconds).
✨ 할당 시간이 지나면 프로세스는 선정(preempted)당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다.
✨ n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다.
→ 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
✨ Performance
- q large → FCFS
- q small → context switch 오버헤드가 커진다
RR with Time Quantum = 20
| Process | Burst Time |
|---|---|
| P1 | 53 |
| P2 | 17 |
| P3 | 68 |
| P4 | 24 |
💡 일반적으로 SJF보다 average turnaround time이 길지만 response time(응답시간)은 더 짧다
왜 Round Robin 알고리즘을 사용할까?
- long job과 short job이 섞여 있기 때문에.
- 모든 프로세스가 동일한 burst time을 가지는 경우
✓ 모든 프로세스를 일정 단위로 잘게 쪼개서 번갈아가며 처리하기 때문에 Turnaround time, Waiting time이 길어지고 모든 프로세스가 마지막까지 메모리에 남아있다가 거의 동시다발적으로 종료된다.
Multilevel Queue
✨ Ready queue를 프로세스의 특성에 따라 여러 레벨로 분할
- foreground (interactive , short job 위주)
- background (batch - no human interaction , long job 위주)
✨ 각 큐는 독립적인 스케줄링 알고리즘을 가짐
- foreground - RR
- background - FCFS
✨ 큐에 대한 스케줄링이 필요
- Fixed priority scheduling
✓ 높은 우선순위의 queue를 항상 먼저 처리. 높은 우선순위 queue가 비었을 때만 낮은 우선순위의 queue에 있는 프로세스를 실행함
✓ Starvation 가능성 문제. - Time slice
✓ 각 큐에 CPU time을 적절한 비율로 할당
✓ Eg. 80% to foreground in RR, 20% to background in FCFS💡 Starvation이 발생할 수 있다.
Why? → 프로세스가 다른 Queue로 이동하지 못하기 때문
Multilevel Feedback Queue
✨ 프로세스가 다른 큐로 이동 가능
✨ 에이징(aging)을 이와 같은 방식(큐 이동)으로 구현할 수 있다
✨Multilevel-feedback-queue scheduler를 정의하는 파라미터들
- Queue의 수
- 각 큐마다 scheduling algorithm
- Process를 상위 큐로 보내는 기준
- Process를 하위 큐로 내쫓는 기준
- 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준
Example of Multilevel Feedback queue
-
Three queues:
- Q₀ : time quantum 8ms
- Q₁: time quantum 16ms
- Q₂: FCFS
-
Scheduling
- new job이 queue Q₀로 들어감
- CPU를 잡아서 할당 시간 8ms 동안 수행됨
- 8ms 동안 다 끝내지 못했으면 queue Q₁으로 내려감
- Q₁에 줄서서 기다렸다가 CPU를 잡아서 16 ms 동안 수행됨
- 16 ms에 끝내지 못한 경우 queue Q₂로 쫓겨남
Multiple-Processor Scheduling
(이 환경에서 다루는 것은 CPU가 하나인 상황이다. 멀티 CPU에 대한것은 살펴만 본다)
✨ CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐
✨ Homogeneous processor인 경우
- Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
- 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
✨ Load sharing
- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
- 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
✨ Symmetric Multiprocessing (SMP)
- 각 프로세서가 각자 알아서 스케줄링 결정
✨ Asymmetric multiprocessing
- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름
Real-Time Scheduling
(우리가 일반적으로 사용하는 컴퓨터는 Real-Time이 아니다. Real-Time 컴퓨터에 대한 스케줄링)
✨ Hard real-time systems
- Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링해야 함
- 프로세스들의 CPU 도착 시간을 알고 스케줄링 하는 경우도 많음
✨ Soft real-time computing
- Soft real-time task는 일반 프로세스에 비해 높은 priority 갖도록 해야 함
Thread Scheduling
✨ Local Scheduling
- 운영체제가 Thread의 존재를 모를때
- User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
✨ Global Scheduling
- 운영체제가 Thread의 존재를 알때
- Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
Algorithm Evaluation(알고리즘 평가)
✨ Queueing models
- 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산
- 이론적, 아주 옛날에 사용했던 방법
✨ Implementation (구현) & Measurement (성능 측정)
- 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교
✨ Simulation (모의 실험)
- 알고리즘을 모의 프로그램으로 작성후 trace를 입력으로 하여 결과 비교
- trace가 신빙성이 있어야함(아주 제한된 환경이 아닌 실제 환경과 비슷해야됨)
