[운영체제/복합문제] CPU 스케줄링 복합문제
5장. CPU 스케줄링 복합문제
1. 다음 표와 같이 5개의 스레드가 있다. 스레드들이 모두 0의 시간에 도착하여 T1에서 T5의 순서로 준비 큐에 대기 중 이라고 할 때 다음 물음에 답하라. 실행 시간 동안 스레드는 입출력 없이 실행된다고 가정한다.
| 스레드 | 실행 시간 (ms) | 우선순위 (숫자가 클수록 높은 순위) |
|---|---|---|
| T1 | 2 | 2 |
| T2 | 3 | 1 |
| T3 | 8 | 4 |
| T4 | 1 | 2 |
| T5 | 4 | 3 |
1-1 FCFS, SJF, Non-Preemptive Priority 스케줄링 알고리즘 각각에 대해 스레드들이 스케줄링되어 실행 되는 과정을 차트를 그리고 5개의 스레드가 모두 실행되는데 걸린 평균 대기 시간을 계산하라.
1-1-1 FCFS
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | |
| T1 | ||||||||||||||||||
| T2 | ||||||||||||||||||
| T3 | ||||||||||||||||||
| T4 | ||||||||||||||||||
| T5 | ||||||||||||||||||
평균 대기 시간
1
(0 + 2 + 5 + 13 + 14)/5 = 6.8ms
1-1-2 SJF
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | |
| T1 | ||||||||||||||||||
| T2 | ||||||||||||||||||
| T3 | ||||||||||||||||||
| T4 | ||||||||||||||||||
| T5 | ||||||||||||||||||
평균 대기 시간
1
(1 + 3 + 10 + 0 + 6)/5 = 4.0ms
1-1-3 Non-Preemptive Priority
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | |
| T1 | ||||||||||||||||||
| T2 | ||||||||||||||||||
| T3 | ||||||||||||||||||
| T4 | ||||||||||||||||||
| T5 | ||||||||||||||||||
평균 대기 시간
1
(12 + 15 + 0 + 14 + 9)/5 = 9.8ms
1-2 RR(타임 슬라이스 = 2ms)으로 스케줄링할 때 실행되는 과정을 차트로 그리고 5개의 스레드가 모두 실행되는데 걸린 평균 대기 시간을 계산하라.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | |
| T1 | ||||||||||||||||||
| T2 | ||||||||||||||||||
| T3 | ||||||||||||||||||
| T4 | ||||||||||||||||||
| T5 | ||||||||||||||||||
평균 대기 시간
1
(0 + 7 + 10 + 6 + 10)/5 = 6.6ms
1.3 RR(타임 슬라이스 = 2ms)으로 스케줄링할 때 스케줄링 오버헤드(스케줄링 시간 + 컨텍스트 스위칭 시간) 가 평균적으로 0.1ms 걸린다고 하면 5개의 스레드가 모두 실행되는데 걸린 시간은 총 얼마인가?
1
2
3
스케줄링 횟수 : 9회 (3,5,7,8,10,11,13,15,17)
디스패치 횟수 : 8회 (3,5,7,8,10,11,13,15)
총 실행시간 : 18ms + 0.9ms = 18.9ms
2. 다음 표와 같이 5개의 스레드가 있다. 시간 단위는 밀리초이며 스레드들은 시간에 맞추어 도착한다. 실행 시간 동안 스레드는 입출력 없이 실행된다고 가정한다. 또한 Tl, T2, T3은 모두 0의 시간에 도착하였지만 극히 작은 시간 차이 로 Tl, T2, T3 순으로 준비 큐에 대기 중이다. 이 상태에서 스케줄링이 시작된다고 가정한다.
| 스레드 | 도착 시간 | 실행 시간 (ms) | 우선순위 (숫자가 클수록 높은 순위) |
|---|---|---|---|
| T1 | 0 | 2 | 2 |
| T2 | 0 | 3 | 1 |
| T3 | 0 | 8 | 4 |
| T4 | 1 | 1 | 2 |
| T5 | 9 | 4 | 3 |
2-1 FCFS, S3F. Non-Preemptive Priority 스케줄링 알고리즘 각각에 대해 스레드들이 스케줄링되어 실행 되는 과정을 그리고 5개의 스레드를 실행하는데 걸린 평균 대기 시간을 계산하라.
2-2-1 FCFS
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | |
| T1 | ||||||||||||||||||||
| T2 | ||||||||||||||||||||
| T3 | ||||||||||||||||||||
| T4 | ||||||||||||||||||||
| T5 | ||||||||||||||||||||
평균 대기 시간
1
(0 + 4 + 7 + 14 + 7)/5 = 6.4ms
2-2-2 SJF
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | |
| T1 | |||||||||||||||||||||
| T2 | |||||||||||||||||||||
| T3 | |||||||||||||||||||||
| T4 | |||||||||||||||||||||
| T5 | |||||||||||||||||||||
평균 대기 시간
1
(4 + 0 + 8 + 2 + 7)/5 = 4.2ms
2-2-3 Non-preemptive Priority
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | |
| T1 | |||||||||||||||||||||
| T2 | |||||||||||||||||||||
| T3 | |||||||||||||||||||||
| T4 | |||||||||||||||||||||
| T5 | |||||||||||||||||||||
평균 대기 시간
1
(8 + 17 + 0 + 19 + 3)/5 = 9.4ms
2-2 SRTF 알고리즘으로 스케줄링되어 실행되는 과정을 그리고 평균 대기 시간을 계산하라.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | |
| T1 | |||||||||||||||||||||
| T2 | |||||||||||||||||||||
| T3 | |||||||||||||||||||||
| T4 | |||||||||||||||||||||
| T5 | |||||||||||||||||||||
평균 대기 시간
1
(4 + 1 + 13 + 0 + 0)/5 = 3.8ms
2-3 Preemptive Priority 알고리즘으로 스케줄링되어 실행되는 과정을 그리고 평균 대기 시간을 계산하라
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | |
| T1 | |||||||||||||||||||||
| T2 | |||||||||||||||||||||
| T3 | |||||||||||||||||||||
| T4 | |||||||||||||||||||||
| T5 | |||||||||||||||||||||
평균 대기 시간
1
(13 + 17 + 0 + 19 + 0)/5 = 9.8ms
This post is licensed under CC BY 4.0 by the author.