[ 스케줄링의 종류 ]
| 선점 스케줄링 | RR(Round Robin), SRT(Shortest Remaining Time), MLQ(Multi Level Queue), MFQ(Multi level Feedback Queue), 선점 우선순위 |
| 비선점 스케줄링 | FCFS(First Come First Service, FIFO), SJF(Shortest Job First), HRN(Highest Response-ratio Next), 우선순위, 기한부 |
선점 스케줄링은 하나의 프로세스가 CPU를 사용 중일 때 다른 프로세스가 CPU를 뺏어서 사용할 수 있는 스케줄링 기법이다.
비선점 스케줄링은 하나의 프로세스가 CPU를 사용 중이라면 해당 프로세스 처리가 끝날 때까지 다른 프로세스가 CPU를 사용하지 못하는 스케줄링 기법이다.
참고로 CPU에서는 한 번에 하나의 프로세스만 처리가 가능하다.
스케줄링 별로 문제를 풀어보면서 익혀보자~
문제에는 자주 나오는 알고리즘인 FCFS(=FIFO), HRN, RR, SJF, SRT 가 있고, 답은 더보기 안에서 확인할 수 있다.
[ FCFS(First Come First Service) ]
1. 다음은 CPU에 서비스를 받으려고 도착한 순서대로 프로세스와 그 서비스 시간을 나타낸다. FCFS(First Come First Service) CPU Scheduling에 의해서 프로세스를 처리할 경우 프로세스의 평균 대기 시간은 얼마인가?
| 프로세스 | 버스트 시간(초) |
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
[ 답 ]
17
[ 풀이 ]
각 프로세스 별로 대기 시간을 구해보면
P1은 맨 처음 실행되어 대기를 하지 않으니 0초.
P2는 P1의 실행 시간 만큼 기다리게 되니 24초.
P3은 P1과 P2의 실행 시간 만큼 기다리게 되니 24 + 3 = 27초.
평균 대기 시간을 구하면 (0+24+27)/3 = 51/3 = 17초이다.
2. 다음과 같은 3개의 작업에 대하여 FCFS 알고리즘을 사용할 때, 임의의 작업 순서로 얻을 수 있는 최대 평균 반환 시간을 T, 최소 평균 반환 시간을 t라고 가정했을 경우 T-t의 값은?
| 프로세스 | 실행시간 |
| P1 | 9 |
| P2 | 3 |
| P3 | 12 |
[ 답 ]
6
[ 풀이 ]
최대 평균 반환 시간은 실행 시간이 긴 프로세스부터 실행하여 반환 시간을 구한다.
따라서 P3, P1, P2 순서대로 프로세스를 실행시키면 반환시간은 12, 21, 24 순서로 나오므로 평균을 구하면 최대 평균 반환 시간(T)은 19이다.
최소 평균 반환 시간은 반대로 실행 시간이 짧은 프로세스부터 실행하여 반환 시간을 구한다.
따라서 P2, P1, P3 순서대로 프로세스를 실행시키면 반환 시간은 3, 12, 24 순서로 나오므로 평균을 구하면 최소 평균 반환 시간(t)은 13이다.
따라서 문제에서 요구하는 T-t의 값은 6이 된다.
3. 다음과 같은 3개의 작업에 대하여 FCFS 알고리즘을 사용할 때, 임의의 작업 순서로 얻을 수 있는 최대 평균 반환 시간을 T, 최소 평균 반환 시간을 t라고 가정했을 경우 T-t의 값은?
| 프로세스 | 실행시간 |
| P1 | 9 |
| P2 | 6 |
| P3 | 12 |
[ 답 ]
4
[ 풀이 ]
최대 평균 반환 시간은 실행 시간이 긴 프로세스부터 실행하여 반환 시간을 구한다.
따라서 P3, P1, P2 순서대로 프로세스를 실행시키면 반환시간은 12, 21, 27 순서로 나오므로 평균을 구하면 최대 평균 반환 시간(T)은 20이다.
최소 평균 반환 시간은 반대로 실행 시간이 짧은 프로세스부터 실행하여 반환 시간을 구한다.
따라서 P2, P1, P3 순서대로 프로세스를 실행시키면 반환 시간은 6, 15, 27 순서로 나오므로 평균을 구하면 최소 평균 반환 시간(t)은 16이다.
따라서 문제에서 요구하는 T-t의 값은 4가 된다.
[ HRN(Highest Response-ratio Next) ]
1. HRN(Highest Response-ratio Next) 방식으로 스케줄링할 경우, 입력된 작업이 다음과 같을 때 우선순위가 가장 높은 작업은?
| 작업 | 대기시간 | 서비스시간 |
| A | 8 | 2 |
| B | 10 | 6 |
| C | 15 | 7 |
| D | 20 | 8 |
[ 답 ]
A
[ 풀이 ]
HRN 스케줄링 기법에서 우선순위를 구하는 식은 (대기시간+서비스시간)/서비스시간 이다.
해당 공식을 이용해 각 작업 별로 우선순위를 구하면
A = 5
B = 8/3
C = 22/7
D = 5/2
가장 우선순위 값이 높은 작업은 A 이다.
2. HRN 스케줄링 방식에서 입력된 작업이 다음과 같을 때 우선순위가 가장 높은 걋은?
| 작업 | 대기시간 | 서비스시간 |
| A | 5 | 20 |
| B | 40 | 20 |
| C | 15 | 45 |
| D | 20 | 2 |
[ 답 ]
D
[ 풀이 ]
HRN 스케줄링 기법에서 우선순위를 구하는 식은 (대기시간+서비스시간)/서비스시간 이다.
해당 공식을 이용해 각 작업 별로 우선순위를 구하면
A = 25/20
B = 60/20
C = 60/45
D = 22/2
가장 우선순위 값이 높은 작업은 D 이다.
3. HRN 방식으로 스케줄링할 경우, 입력된 작업이 다음과 같을 때 우선순위가 높은 순서부터 차례로 옳게 나열하시오.
| 작업 | 대기시간 | 서비스시간 |
| A | 40 | 20 |
| B | 20 | 20 |
| C | 70 | 10 |
| D | 120 | 30 |
[ 답 ]
C → D → A → B
[ 풀이 ]
HRN 스케줄링 기법에서 우선순위를 구하는 식은 (대기시간+서비스시간)/서비스시간 이다.
해당 공식을 이용해 각 작업 별로 우선순위를 구하면
A = 60/20
B = 40/20
C = 80/10
D = 150/30
우선순위가 높은 순서는 C → D → A → B 이다.
[ RR(Round Robin) ]
1. 라운드로빈(Round-Robin) 방식으로 스케줄링 할 경우, 입력된 작업이 다음과 같고 각 작업의 CPU 할당 시간이 4시간일 때, 모든 작업을 완료하기 위한 CPU의 사용 순서를 옳게 나열하시오.
| 작업 | 입력시간 | 수행시간 |
| A | 10:00 | 5시간 |
| B | 10:30 | 10시간 |
| C | 12:00 | 15시간 |
[ 답 ]
A - B - C - A - B - C - B - C - C
2. 프로세스들의 도착 시간과 실행 시간이 다음과 같다. CPU 스케줄링 정책으로 라운드로빈(round-robin) 알고리즘을 사용할 경우 평균 대기 시간을 구하시오. (단, 시간 할당량은 10초이다.)
| 프로세스 | 도착시간 | 실행 |
| P1 | 0 | 10 |
| P2 | 6 | 18 |
| P3 | 14 | 5 |
| P4 | 15 | 12 |
| P5 | 19 | 1 |
[ 답 ]
12.2초
[ 풀이 ]
프로세스의 실행 순서는 다음과 같다.
P1 - P2 - P3 - P4 - P5 - P2 - P4
대기 시간은 자기 자신의 실행 시간을 제외하고, 프로세스가 끝날 때까지 대기한 시간이다. 도착 시간은 제외한다.
각 프로세스의 대기 시간을 구해보면
P1의 대기 시간: 0 - 0 (도착시간) = 0
P2의 대기 시간: 26 - 6 (도착시간) = 20
P3의 대기 시간: 20 - 14 (도착시간) = 6
P4의 대기 시간: 34 - 15 (도착시간) = 19
P5의 대기 시간: 35 - 19 (도착시간) = 16
따라서 평균 대기 시간은 (0+20+6+19+16) / 5 (프로세스 개수) = 61 / 5 = 12.2초
3. 다음 표에서 보인 4개의 프로세스들을 시간 할당량(time quantum)이 5인 라운드로빈(round-robin) 스케줄링 기법으로 실행시켰을 때 평균 반환 시간을 구하시오.
| 프로세스 | 도착시간 | 실행시간 |
| P1 | 0 | 10 |
| P2 | 1 | 15 |
| P3 | 3 | 6 |
| P4 | 6 | 9 |
[ 답 ]
29
[ 풀이 ]
해당 문제는 도착시간을 자세히 보아야 한다.
P1 - P2 - P3 - P4 순서로 프로세스가 실행된다고 생각하기 쉽지만, P1이 실행된 후 P2와 P3이 들어왔을 때는 아직 5초만 지난 상태이므로 P4가 들어오지 않았다. 따라서 P1 - P2 - P3 - P1 의 순서로 실행이 된다.
이후 RR 스케줄링 기법에 따라 실행시간이 5초라면 전체 프로세스의 실행 순서는 다음과 같다.
P1 - P2 - P3 - P1 - P4 - P2 - P3 - P4 - P2
평균 반환 시간을 구하는 방법에는 2가지가 있는데, 실행시간을 나중에 더하나 미리 더하나의 차이이다.
첫 번째는 (총 대기시간+총 실행시간) / 총 프로세스 개수
두 번째는 총 반환시간 / 총 프로세스 개수
첫 번째 방법으로 계산하면 식은 아래와 같다.
대기시간을 구할 때는 자기 자신의 실행시간과 도착시간은 제외한다.
P1의 대기시간: 10 - 0(도착시간) = 10
P2의 대기시간: 25 - 1(도착시간) = 24
P3의 대기시간: 25 - 3(도착시간) = 22
P4의 대기시간: 26 - 6(도착시간) = 20
전체 프로세스의 실행시간은 40이므로 ((10+24+22+20) + 40) / 4 = 29초가 된다.
두 번째 방법으로 계산하면 식은 아래와 같다.
반환시간은 자기 자신의 실행시간은 포함하고, 도착시간은 제외한다.
P1의 반환시간: 20 - 0(도착시간) = 20
P2의 반환시간: 40 - 1(도착시간) = 39
P3의 반환시간: 31 - 3(도착시간) = 28
P4의 반환시간: 35 - 6(도착시간) = 29
따라서 (20+39+28+29) / 4 = 29초가 된다.
[ SJF(Shortest Job First) ]
1. 다음과 같은 프로세스들이 차례대로 준비상태 큐에 들어왔을 경우 SJF 스케줄링 기법을 이용하여 제출시간이 없는 경우의 평균 실행 시간은?
| 프로세스 | P1 | P2 | P3 |
| 실행시간(초) | 18 | 6 | 9 |
[ 답 ]
11
[ 풀이 ]
SJF 스케줄링 기법은 실행 중인 프로세스의 처리가 끝날 때까지 다른 프로세스를 처리하지 않는다.
평균 실행 시간을 구하면 되므로 프로세스 실행 순서에 상관없이 전체 프로세스 실행 시간의 평균을 구하면 된다.
(18+6+9) / 3 = 11
2. 대기하고 있는 프로세스 p1, p2, p3, p4의 처리시간은 24[ms], 9[ms], 15[ms], 10[ms]일 때, 최단 작업 우선(SJF, Shortest-Job-First) 스케줄링으로 처리했을 때 평균 대기 시간은 얼마인가?
[ 답 ]
15.5[ms]
3. SJF(Shortest Job First) 스케줄링에서 다음과 같은 작업들이 준비상태 큐에 있을 때 평균 반환 시간과 평균 대기 시간은?
| 프로세스 | 실행시간 |
| P-1 | 6 |
| P-2 | 3 |
| P-3 | 8 |
| P-4 | 7 |
[ 답 ]
평균 반환 시간: 13
평균 대기 시간: 7
[ 풀이 ]
모든 작업들이 준비상태 큐에서 대기 중이므로 SJF 방식에 따라 실행시간이 짧은 프로세스부터 우선 처리한다.
프로세스의 실행 순서는 아래와 같다.
P-2 - P-1 - P-4 - P-3
대기 시간은 자기 자신이 실행되기 전까지의 시간이므로 각 프로세스의 대기 시간은 아래와 같다.
P1의 대기시간: 3
P2의 대기시간: 0
P3의 대기시간: 16
P4의 대기시간: 9
평균 대기 시간은 (3+0+16+9) / 4 = 28 / 4 = 7
평균 반환 시간은 (전체 대기 시간 + 전체 실행 시간) / 전체 프로세스의 개수 로 구할 수 있다.
전체 대기 시간은 위에서 구했듯이 28, 전체 실행 시간은 24 이므로
평균 반환 시간은 (28 + 24) / 4 = 52 / 4 = 13
4. 다음과 같은 Task List에서 SJF 방식으로 Scheduling 할 경우, Task 2의 종료 시간은?
| Task | 도착시간 | 실행시간 |
| Task 1 | 0 | 6 |
| Task 2 | 1 | 3 |
| Task 3 | 2 | 4 |
[ 답 ]
9
[ 풀이 ]
맨 처음에는 Task 1밖에 없으므로 Task 1을 실행한다. SJF 스케줄링 기법은 비선점 방식이므로 Task 1이 끝날 때까지 다른 프로세스를 처리하지 않는다. Task 1이 끝난 후 Task 1의 실행 시간인 6만큼 시간이 지났기 때문에 Task 2와 Task 3이 대기 중이다. Shortest Job First 방식이므로 실행 시간이 더 짧은 Task 2를 먼저 처리한다. Task 2의 실행시간인 3만큼 지나면 Task 2가 종료된다.
Task 2의 종료 시간은 Task 1과 Task 2의 실행시간의 합이다.
따라서 6+3 = 9
[ SRT(Shortest Remaining Time) ]
1. 다음 표는 단일 CPU에 진입한 프로세스의 도착 시간과 처리하는 데 필요한 실행 시간을 나타낸 것이다. 프로세스 간 문맥 교환에 따른 오버헤드는 무시한다고 할 때, SRT(Shortest Remaining Time) 스케줄링 알고리즘을 사용한 경우 네 프로세스의 평균 반환 시간(turnaround time)은?
| 프로세스 | 도착 시간 | 실행 시간 |
| P1 | 0 | 8 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 6 | 4 |
[ 답 ]
7
[ 풀이 ]
반환 시간은 (프로세스가 끝난 시간 - 프로세스의 도착 시간) 으로 구할 수 있다.
P1의 반환 시간: 17 - 0 (도착시간) = 17
P2의 반환 시간: 7 - 2 (도착시간) = 5
P3의 반환 시간: 5 - 4 (도착시간) = 1
P4의 반환 시간: 11 - 6 (도착시간) = 5
평균을 구하면 (17+5+1+5) / 4 = 28 / 4 = 7
2. 다음 표는 단일 CPU에 진입한 프로세스의 도착 시간과 처리하는 데 필요한 실행 시간을 나타낸 것이다. 프로세스 간 문맥 교환에 따른 오버헤드는 무시한다고 할 때, SRT(Shortest Remaining Time) 스케줄링 알고리즘을 사용한 경우 네 프로세스의 평균 반환 시간(turnaround time)은?
| 프로세스 | 도착 시간 | 실행 시간 |
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
[ 답 ]
7
[ 풀이 ]
반환 시간은 (프로세스가 끝난 시간 - 프로세스의 도착 시간) 으로 구할 수 있다.
P1의 반환 시간: 16 - 0 (도착시간) = 16
P2의 반환 시간: 7 - 2 (도착시간) = 5
P3의 반환 시간: 5 - 4 (도착시간) = 1
P4의 반환 시간: 11 - 5 (도착시간) = 6
평균을 구하면 (16+5+1+6) / 4 = 28 / 4 = 7
