- 선점형 스케줄링
- Round Robin
- SRT (Shortest Remaining Time)
- MLQ (Multi Level Queue)
- MLFQ (Multi Level Feedback Queue)
- 비선점형 스케줄링
- FCFS (First Come First Service)
- SJF (Shortest Job First)
- HRN (Highest Response Ratio Next)
- 우선순위
- 기한부
- 기아 현상 : 우선 순위가 낮아 무한정 대기하는 현상
→ 기아 현상이 발생할 수 있는 스케줄링 기법 : SRT, MLQ / SJF, 우선순위 - 에이징 기법 : 기아 현상을 해결하기 위한 기법
→ MLFQ / HRN
비선점형 스케줄링 - FCFS (First Come First Service)
Q. 다음과 같은 상황에서 FCFS 알고리즘을 적용하였을 때 프로세스 완료 순서를 쓰시오.
| 프로세스 | 실행 시간 |
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
| P4 | 20 |
- A. P1, P2, P3, P4
- 풀이
- FCFS는 비선점형 스케줄링으로 CPU가 강제로 꺼낼 수 없고 들어온 순서 그대로 진행을 하게 되는데, 도착시간 같은 것이 주어지지 않았기 때문에 위에서부터 순서대로 완료하게 됨
Q. 다음은 CPU에 서비스를 받으려고 도착한 순서대로 프로세스와 그 서비스 시간을 나타낸다.
FCFS CPU Scheduling에 의해서 프로세스를 처리한다고 했을 경우 프로세스의 평균 대기 시간을 구하시오.
| 프로세스 | 실행 시간 |
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
A. 17
- 풀이
- P1부터 순차적으로 실행
- P1은 바로 실행되기 때문에 대기 시간이 존재하지 않음 (0초)
- P2는 P1을 기다리고 실행하기 때문에 대기 시간이 24초
- P3는 P2가 끝난 뒤 실행되기 때문에 대기 시간이 27초(P1 실행시간 24초 + P2 실행시간 3초)
- 따라서, 총 대기 시간은 51초로 51 / 3 = 17초
Q. 다음과 같은 3개의 작업에 대하여 FCFS 알고리즘을 사용할 때, 임의의 작업 순서로 얻을 수 있는 최대 평균 반환 시간을 T,
최소 평균 반환 시간을 t라고 가정했을 경우 T-t의 값은?
| 프로세스 | 실행 시간 |
| P1 | 9 |
| P2 | 3 |
| P3 | 12 |
A. 6
반환 시간 = 실행 시간 + 대기 시간
최대 평균 반환 시간을 구하려면 실행 시간이 가장 긴 것부터 실행을 해야 대기 시간이 최대화
따라서, 아래의 표처럼 P3, P1, P2 순서로 실행해야 최대 평균 반환시간이 나오고, 총 반환 시간은 12 + 21 + 24 = 57초
평균 반환 시간은 57 / 3 = 19초
| 프로세스 | 실행시간 | 대기시간 | 반환시간 |
| P3 | 12 | 0 | 12 |
| P1 | 9 | 12 | 21 |
| P2 | 3 | 21 | 24 |
최소 평균 반환 시간을 구하려면 실행 시간이 가장 짧은 것부터 실행을 해야 대기 시간이 최소화
따라서, 아래의 표처럼 P2, P1, P3 순서로 실행해야 최소 평균 반환시간이 나오고, 총 반환 시간은 3 + 12 + 24 = 39초
평균 반환 시간은 39 / 3 = 13초
| 프로세스 | 실행시간 | 대기시간 | 반환시간 |
| P2 | 3 | 0 | 3 |
| P1 | 9 | 3 | 12 |
| P3 | 12 | 12 | 24 |
Q. 다음과 같은 3개의 작업에 대하여 FCFS 알고리즘을 사용할 때, 임의의 작업 순서로 얻을 수 있는 최대 평균 반환 시간을 T, 최소 평균 반환 시간을 t라고 가정했을 경우 T-t의 값은?
| 프로세스 | 실행시간 |
| P1 | 9 |
| P2 | 6 |
| P3 | 12 |
A. 4
최대 평균 반환 시간 = 12 + 21 + 27 = 60 / 3 = 20
| 프로세스 | 실행시간 | 대기시간 | 반환시간 |
| P3 | 12 | 0 | 12 |
| P1 | 9 | 12 | 21 |
| P2 | 6 | 21 | 27 |
최소 평균 반환 시간 = 6 + 15 + 27 = 48 / 3 = 16
| 프로세스 | 실행시간 | 대기시간 | 반환시간 |
| P2 | 6 | 0 | 6 |
| P1 | 9 | 6 | 15 |
| P3 | 12 | 15 | 27 |
비선점형 스케줄링 - SJF (Shortest Job First)
Q. 다음과 같은 프로세스가 차례로 큐에 도착했을 때 SJF 정책을 사용할 경우, 가장 먼저 처리되는 작업은?
| 프로세스 | 실행 시간 |
| P1 | 6 |
| P2 | 8 |
| P3 | 4 |
| P4 | 3 |
A. P4
- 풀이
- SJF는 실행 시간이 가장 짧은 프로세스를 우선시
- 따라서, 프로세스 실행 순서는 P4 → P3 → P1 → P2
Q. 다음과 같은 프로세스들이 차례로 준비상태 큐에 들어왔을 경우 SJF 스케줄링 기법을 이용하여 제출시간(도착시간)이 없는 경우의 평균 실행 시간은?
| 프로세스 | P1 | P2 | P3 |
| 실행 시간(초) | 18 | 6 | 9 |
A. 11
- 풀이
- 평균 실행 시간은 프로세스 각각의 실행 시간을 모두 더해서 나누면 끝
- 18 + 6 + 9 = 33 / 3 = 11초
Q. 다음과 같은 작업들이 차례로 준비상태 큐에 들어왔다고 가정할 경우, SJF 기법으로 스케줄링한다면 프로세스 2의 대기 시간은?
| 프로세스 | 도착시간 | 실행시간 |
| 1 | 0 | 7 |
| 2 | 1 | 3 |
| 3 | 2 | 5 |
A. 6
- 풀이
- 이전의 문제와 달리 도착 시간이 추가 되어 더 생각해야할 부분이 발생함
- 프로세스 1은 이미 도착해있어 바로 실행을 하게 되고, 프로세스 2는 프로세스 1이 종료된 후 실행되기 때문에 대기 시간이 7초라고 생각할 수 있겠지만, 1초의 이동 시간(도착 시간)이 있기 때문에 7 - 1 = 6초로 계산을 해야함
Q. 다음과 같은 Task List에서 SJF 방식으로 Scheduling할 경우 Task 2가 종료되는 시간을 구하시오.
| Task | 도착 시간 | 실행 시간 |
| Task 1 | 0 | 6 |
| Task 2 | 1 | 3 |
| Task 3 | 2 | 4 |
A. 9
- 풀이
- 도착 시간이 0인 Task1이 먼저 실행
- Task1이 실행되고 있는 6초 동안 Task2와 Task3이 도착
- 6초가 지난 뒤 Task 2가 실행(3초)
- 즉, Task1의 6초 + Task2의 3초 = 9초
- 더 나아가서 각각의 Task의 대기 시간, 반환 시간을 구하면 다음과 같음
| Task | 도착 시간 | 실행 시간 | 대기 시간 | 반환 시간 |
| Task 1 | 0 | 6 | 0 | 6 |
| Task 2 | 1 | 3 | 5 (6 - 1) Task1 실행 시간 - Task2 대기 시간 |
8 |
| Task 3 | 2 | 4 | 7 ( 6 + 3 - 2) Task 1 + Task 2 실행시간 - Task3 대기 시간 |
11 |
Q. 대기하고 있는 프로세스 P1, P2, P3, P4의 처리 시간은 24[ms], 9[ms], 15[ms], 10[ms]일 때, 최단 작업 우선(Shortest-Job-First) 스케줄링으로 처리했을 때 평균 대기 시간은 얼마인가?
| 프로세스 | 처리 시간(실행 시간) |
| P1 | 24 |
| P2 | 9 |
| P3 | 15 |
| P4 | 10 |
A. 15.5
평균 대기 시간 = (0 + 9 + 19 + 34) / 4 = 62 / 4 = 15.5
| 프로세스 | 처리 시간 | 대기 시간 | 반환 시간 |
| P2 | 9 | 0 | 9 |
| P4 | 10 | 9 | 19 |
| P3 | 15 | 19 | 34 |
| P1 | 24 | 34 | 58 |
Q. SJF 스케줄링에서 다음과 같은 작업들이 준비상태 큐에 있을 때 평균 반환시간과 평균 대기시간을 구하시오.
| 프로세스 | 실행 시간 |
| P1 | 6 |
| P2 | 3 |
| P3 | 8 |
| P4 | 7 |
A. 평균 반환 시간 : 13 / 평균 대기 시간 : 7
| 프로세스 | 실행 시간 | 대기 시간 | 반환 시간 |
| P2 | 3 | 0 | 3 |
| P1 | 6 | 3 | 9 |
| P4 | 7 | 9 | 16 |
| P3 | 8 | 16 | 24 |
- 총 대기 시간 : 0 + 3 + 9 + 16 = 28
- 평균 대기 시간 : 28 / 4 = 7
- 총 반환 시간 : 3 + 9 + 16 + 24 = 52
- 평균 반환 시간 : 52 / 4 = 13
Q. 다음과 같이 P1, P2, P3, P4 프로세스가 동시에 준비상태 큐에 도착했을 때 SJF 스케줄링 알고리즘에서 평균 반환 시간과 평균 대기 시간을 쓰시오.
(단, 프로세스 간 문맥 교환에 따른 오버헤드는 무시하며, 주어진 4개의 프로세스 외에 처리할 다른 프로세스는 없다고 가정한다.)
| 프로세스 | 실행 시간 |
| P1 | 5 |
| P2 | 6 |
| P3 | 4 |
| P4 | 9 |
A. 평균 반환 시간 : 13 / 평균 대기 시간 : 7
| 프로세스 | 실행 시간 | 대기 시간 | 반환 시간 |
| P3 | 4 | 0 | 4 |
| P1 | 5 | 4 | 9 |
| P2 | 6 | 9 | 15 |
| P4 | 9 | 15 | 24 |
- 총 대기 시간 : 28
- 평균 대기 시간 : 28 / 4 = 7
- 총 반환 시간 : 52
- 평균 반환 시간 : 52 / 4 = 13
Q. 다음은 프로세스가 준비상태 큐에 도착한 시간과 프로세스를 처리하는 데 필요한 실행 시간을 보여준다.
비선점형 SJF 스케줄링 알고리즘을 사용할 경우, 프로세스들의 대기시간 총합을 구하시오.
(단, 프로세스 간 문맥 교환에 따른 오버헤드는 무시하며, 주어진 4개 프로세스 외에 처리할 다른 프로세스는 없다고 가정한다.)
| 프로세스 | 도착시간 | 실행시간 |
| P1 | 0 | 30 |
| P2 | 5 | 10 |
| P3 | 10 | 15 |
| P4 | 15 | 10 |
A. 90
- 풀이
- 도착 시간이 0인 P1이 가장 먼저 실행
- P1의 실행 시간은 30초로, 30초 동안 나머지 프로세스(P2, P3, P4)가 모두 도착하게 됨
- 따라서, P1의 실행이 끝난 뒤 실행 시간이 가장 짧은 순서대로 P2 → P3 → P4가 실행
- 아래 표에 따라 대기 시간 총합은 0 + 25 + 25 + 40 = 90초가 됨
| 프로세스 | 도착 시간 | 실행 시간 | 대기 시간 | 반환 시간 |
| P1 | 0 | 30 | 0 | 30 |
| P2 | 5 | 10 | 25 (30 - 5 도착시간) | 35 |
| P4 | 15 | 10 | 25 (40 - 15 도착시간 ) ※ 40 = P1 실행 + P2 실행 |
35 |
| P3 | 10 | 15 | 40 (50 - 10 도착시간 ) ※ 50 = P1 실행 + P2 실행 + P3 실행 |
55 |
비선점형 스케줄링 - HRN (Highest Response ratio Next)
Q. HRN 스케줄링 기법에서 우선순위를 구하는 식을 쓰시오.
A. (대기시간 + 서비스 시간 or 실행시간) / 서비스 시간 or 실행시간
Q. HRN 방식으로 스케줄링할 경우 입력된 작업이 다음과 같을 때 우선 순위가 가장 높은 작업은?
| 작업 | 대기 시간 | 서비스 시간 |
| A | 8 | 2 |
| B | 10 | 6 |
| C | 15 | 7 |
| D | 20 | 8 |
A. A
- 풀이
- A = (8 + 2) / 2 = 5
- B = (10 + 6) / 6 = 2.66666
- C = (15 + 7) / 7 = 3.11111
- D = (20 + 8) / 8 = 3.5
- 우선 순위 높은 순 : A → D → C → B
Q. HRN 스케줄링 방식에서 입력된 작업이 다음과 같을 때 우선 순위가 가장 높은 것은?
| 작업 | 대기 시간 | 서비스(실행) 시간 |
| A | 5 | 20 |
| B | 40 | 20 |
| C | 15 | 45 |
| D | 20 | 2 |
A. D
- 풀이
- A = (5 + 20) / 20 = 1.25
- B = (40 + 20) / 20 = 3
- C = (15 + 45) / 45 = 1.333333
- D = (20 + 2) / 2 = 11
- 우선 순위 높은 순 : D → B → C → A
Q. HRN 방식으로 스케줄링 할 경우, 입력된 작업이 다음과 같을 때 우선 순위가 높은 순서부터 차례로 옳게 나열한 것은?
| 작업 | 대기 시간 | 서비스(실행) 시간 |
| A | 40 | 20 |
| B | 20 | 20 |
| C | 70 | 10 |
| D | 120 | 30 |
A. C, D, A, B
- 풀이
- A = (40 + 20) / 20 = 3
- B = (20 + 20) / 20 = 2
- C = (70 + 10) / 10 = 8
- D = (120 + 30) / 30 = 5
- 우선 순위 높은 순 : C → D → A → B
선점형 스케줄링 - SRT (Shortest Remaining Time)
Q. 다음 표는 단일 CPU에 진입한 프로세스의 도착시간과 처리하는 데 필요한 실행 시간을 나타내는 것이다.
프로세스 간 문맥 교환에 따른 오버헤드는 무시한다고 할 때, SRT 스케줄링 알고리즘을 사용한 경우, 네 프로세스의 평균 반환 시간을 쓰시오.
| 프로세스 | 도착 시간 | 실행 시간 |
| P1 | 0 | 8 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 6 | 4 |
A. 7
- 풀이
- 선점형 스케줄링의 경우 새로운 프로세스가 들어왔을 때 현재 실행 중인 프로세스와 실행 시간을 비교하여 실행 시간이 더 짧은 프로세스를 먼저 수행함
- 선점형 스케줄링은 CPU가 이미 작업 중인 프로세스를 넣었다 뺐다 할 수 있기 때문
- 도착 시간이 0인 P1 먼저 실행 (2초) → P1의 남은 실행 시간 : 6초
- 총 실행 시간 2초(P2 도착) → P1 실행 시간(6초) vs P2 실행 시간 (4초) → P2 실행 (2초) → P2의 남은 실행 시간 : 2초
- 총 실행 시간 4초(P3 도착) → P2 실행 시간(2초) vs P3 실행 시간 (1초) → P3 실행 (1초) → P3 종료
- 총 실행 시간 5초(P4 미도착) → 남은 프로세스 시간 비교 → P1(6초) vs P2(2초) → P2 실행(1초)
→ P2 남은 시간 : 1초 - 총 실행 시간 6초(P4 도착) → P2 실행 시간 (1초) vs P4 실행 시간 (4초) = P2 실행(1초) → P2 종료
- 남은 프로세스끼리 비교 → P1 (6초) vs P4 (4초) → P4 실행 (4초) 후 종료 → P1 실행(6초) 후 종료
- 위의 순서를 정리하면 아래와 같음
| 경과 시간 | 0 | 2 | 4 | 5 | 6 | 8 | 12 |
| 프로세스 | P1 | P2 | P3 | P2 | P2 | P4 | P1 |
| 실행 시간 | 2 | 2 | 1 | 1 | 1 | 4 | 6 |
| 남은 시간 | 6 | 2 | 0 | 1 | 0 | 0 | 0 |
| 실행 후 도착 프로세스 | P2(4초) | P3(1초) | P4(4초) |
- 위의 표에서 대기 시간은 프로세스가 끝난 시점에서 이전 실행 시간 중 자기 자신의 프로세스를 제외하고 모두 더하면 됨
- P1 = 경과 시간 12에서 프로세스가 종료 → 앞의 모든 실행 시간 중 자기 자신만 제외 → 2(P2) + 1(P3) + 1(P2) + 1(P2) + 4(P4) = 9
- P2 = 경과 시간 6에서 프로세스가 종료 → 2(P1) + 1(P3) = 3
- P3 = 경과 시간 4에서 프로세스가 종료 → 2(P1) + 2(P2) = 4
- P4 = 경과 시간 8에서 프로세스가 종료 → 2(P1) + 2(P2) + 1(P3) + 1(P2) + 1(P2) = 7
- 대기 시간과 반환 시간으로 정리하여 계산
- 평균 반환 시간 = 17 + 5 + 1 + 5 = 28 / 4 = 7
| 프로세스 | 도착 시간 | 실행 시간 | 대기 시간 | 반환 시간 |
| P1 | 0 | 8 | 9 - 0(도착시간) | 17 |
| P2 | 2 | 4 | 3 - 2 = 1 | 5 |
| P3 | 4 | 1 | 4 - 4 = 0 | 1 |
| P4 | 6 | 4 | 7 - 6 = 1 | 5 |
Q. 다음 표는 단일 CPU에 진입한 프로세스의 도착 시간과 처리하는 데 필요한 실행 시간을 나타낸 것이다.
프로세스 간 문맥 교환에 따른 오버헤드는 무시한다고 할 때, SRT 스케줄링 알고리즘을 사용한 경우, 네 프로세스의 평균 반환 시간을 쓰시오.
| 프로세스 | 도착 시간 | 실행 시간 |
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
A. 7
- 풀이
- 각 프로세스의 실행 시간 및 순서를 계산하여 대기 시간관 반환 시간 산출
- 평균 반환 시간 = 16 + 5 + 1 + 6 = 28 / 4 = 7
| 경과 시간 | 0 | 2 | 4 | 5 | 7 | 11 |
| 프로세스 | P1 | P2 | P3 | P2 | P4 | P1 |
| 실행 시간 | 2 | 2 | 1 | 2 | 4 | 5 |
| 남은 시간 | 5 | 2 | 0 | 0 | 0 | 0 |
| 실행 후 도착 프로세스 |
P2(4) | P3(1) | P4(4) |
| 프로세스 | 도착 시간 | 실행 시간 | 대기 시간 | 반환 시간 |
| P1 | 0 | 7 | 9 - 0 = 9 | 16 |
| P2 | 2 | 4 | 3 - 2 = 1 | 5 |
| P3 | 4 | 1 | 4 - 4 = 0 | 1 |
| P4 | 5 | 4 | 7 - 5 = 2 | 6 |
Q. 다음은 프로세스가 준비상태 큐에 도착한 시간과 프로세스를 처리하는 데 필요한 실행 시간을 보여준다.
선점형 스케줄링 알고리즘인 SRT 알고리즘을 사용할 경우, 프로세스들의 대기 시간 총합은?
(단, 프로세스 간 문맥 교환에 따른 오버헤드는 무시하며, 주어진 4개 프로세스 외에 처리할 다른 프로세스는 없다고 가정한다.)
| 프로세스 | 도착 시간 | 실행 시간 |
| P1 | 0 | 30 |
| P2 | 5 | 10 |
| P3 | 10 | 15 |
| P4 | 15 | 10 |
A. 50
| 경과 시간 | 0 | 5 | 10 | 15 | 25 | 40 |
| 프로세스 | P1 | P2 | P2 | P4 | P3 | P1 |
| 실행 시간 | 5 | 5 | 5 | 10 | 15 | 25 |
| 남은 시간 | 25 | 5 | 0 | 0 | 0 | 0 |
| 실행 후 도착 프로세스 |
P2(10) | P3(15) | P4(10) |
| 프로세스 | 도착 시간 | 실행 시간 | 대기 시간 | 반환 시간 |
| P1 | 0 | 30 | 35 - 0 = 35 | 65 |
| P2 | 5 | 10 | 5 - 5 = 0 | 10 |
| P3 | 10 | 15 | 25 - 10 = 15 | 30 |
| P4 | 15 | 10 | 15 - 15 = 0 | 10 |
선점형 스케줄링 - RR (Round Robin)
Q. 라운드 로빈 방식으로 스케줄링 할 경우 입력된 작업이 다음과 같고 각 작업의 CPU 할당 시간이 4시간일 때 모든 작업을 완료하기 위한 CPU 사용 순서를 옳게 나열하시오.
| 작업 | 입력 시간 | 수행 시간 |
| A | 10:00 | 5시간 |
| B | 10:30 | 10시간 |
| C | 12:00 | 15시간 |
A. A B C A B C B C C
- 풀이
- 라운드 로빈은 각 작업마다 동일한 시간을 부여하는 방식
- 가장 먼저 입력 받은 A를 4시간 동안 수행 → 남은 시간 : 1시간
→ A가 10:00부터 4시간 수행하여 14:00에 종료되어 B, C 작업이 모두 준비상태 큐에 들어옴 - B를 4시간 동안 수행 → 남은 시간 : 6시간
- C를 4시간 동안 수행 → 남은 시간 : 11시간
- A를 1시간 동안 수행 → A 종료
- B를 4시간 동안 수행 → 남은 시간 : 2시간
- C를 4시간 동안 수행 → 남은 시간 : 7시간
- B를 2시간 동안 수행 → B 종료
- C를 4시간 동안 수행 → 남은 시간 : 3시간
- C를 3시간 동안 수행 → C 종료
- 가장 먼저 입력 받은 A를 4시간 동안 수행 → 남은 시간 : 1시간
- 라운드 로빈은 각 작업마다 동일한 시간을 부여하는 방식
Q. 라운드 로빈 방식으로 스케줄링할 경우 입력된 작업이 다음과 같고 각 작업의 CPU 할당 시간이 3시간일 때, CPU의 사용 순서를 나열하시오.
| 작업 | 입력 시간 | 수행 시간 |
| A | 10:00 | 5시간 |
| B | 10:30 | 10시간 |
| C | 12:00 | 15시간 |
A. A B C A B C B C B C C
- 풀이
- A : 3시간 / 잔여 : 2시간
- B : 3시간 / 잔여 : 7시간
- C : 3시간 / 잔여 : 12시간
- A : 2시간 / 종료
- B : 3시간 / 잔여 : 4시간
- C : 3시간 / 잔여 : 9시간
- B : 3시간 / 잔여 : 1시간
- C : 3시간 / 잔여 : 6시간
- B : 1시간 / 종료
- C : 3시간 / 잔여 : 3시간
- C : 3시간 / 종료
Q. 준비상태 큐 프로세스 A, B, C가 차례로 도착하였다.
라운드 로빈으로 스케줄링할 때 타임 슬라이스를 4초로 한다면 평균 반환 시간을 구하시오.
(단, 도착시간은 염두에 두지 않는다.)
| 프로세스 | A | B | C |
| 실행 시간(초) | 17 | 4 | 5 |
A. 17초
- 풀이
- 선점형 스케줄링 SRT와 동일하게 종료된 시점의 프로세스 앞의 실행 시간을 모두 더하는데, 자기 자신 프로세스는 제외
- 평균 반환 시간 : 26 + 8 + 17 = 51 / 3 = 17
| 프로세스 | A | B | C | A | C | A | A | A |
| 실행시간 | 4 | 4 | 4 | 4 | 1 | 4 | 4 | 1 |
| 남은시간 | 13 | 0 | 1 | 9 | 0 | 5 | 1 | 0 |
| 프로세스 | 실행 시간 | 대기 시간 | 반환 시간 |
| A | 17 | 9 | 26 |
| B | 4 | 4 | 8 |
| C | 5 | 12 | 17 |
Q. 프로세스들의 도착시간과 실행 시간이 다음과 같다.
CPU 스케줄링 정책으로 라운드로빈 알고리즘을 사용할 경우 평균 대기 시간을 구하시오.
(단, 시간 할당량은 10초이다.)
| 작업 | 도착 시간 | 실행 |
| P1 | 0 | 10 |
| P2 | 6 | 18 |
| P3 | 14 | 5 |
| P4 | 15 | 12 |
| P5 | 19 | 1 |
A. 12.2
평균 대기 시간 = 0 + 20 + 6 + 19 + 16 = 61 / 5 = 12.2
| 경과 시간 | 0 | 10 | 20 | 25 | 35 | 36 | 44 |
| 프로세스 | P1 | P2 | P3 | P4 | P5 | P2 | P4 |
| 실행 시간 | 10 | 10 | 5 | 10 | 1 | 8 | 2 |
| 남은 시간 | 0 | 8 | 0 | 2 | 0 | 0 | 0 |
| 도착 프로세스 | P2, P3 | P4, P5 |
| 작업 | 도착 시간 | 실행 시간 | 대기 시간 | 반환 시간 |
| P1 | 0 | 10 | 0 | 10 |
| P2 | 6 | 18 | 26 - 6 = 20 | 38 |
| P3 | 14 | 5 | 20 - 14 = 6 | 11 |
| P4 | 15 | 12 | 34 - 15 = 19 | 31 |
| P5 | 19 | 1 | 35 - 19 = 16 | 17 |
Q. 다음 표와 같이 작업이 제출되었을 때, 라운드 로빈 정책을 사용하여 스케줄링 할 경우 평균 반환 시간을 구하시오.
(단, 작업할당 시간은 4시간으로 한다.)
| 작업 | 제출 시간 | 실행 시간 |
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
A. 18.25
평균 반환 시간 = 20 + 7 + 24 + 22 = 73 / 4 = 18.25
| 경과 시간 | 0 | 4 | 8 | 12 | 16 | 20 | 24 | 25 |
| 프로세스 | P1 | P2 | P3 | P4 | P1 | P3 | P4 | P3 |
| 실행 시간 | 4 | 4 | 4 | 4 | 4 | 4 | 1 | 1 |
| 남은 시간 | 4 | 0 | 5 | 1 | 0 | 1 | 0 | 0 |
| 도착 프로세스 | P2, P3, P4 |
| 작업 | 제출 시간(도착 시간) | 실행 시간 | 대기 시간 | 반환 시간 |
| P1 | 0 | 8 | 12 - 0 = 12 | 20 |
| P2 | 1 | 4 | 4 - 1 = 3 | 7 |
| P3 | 2 | 9 | 17 - 2 = 15 | 24 |
| P4 | 3 | 5 | 20 - 3 = 17 | 22 |
Q. 다음과 같이 3개의 프로세스가 있다고 가정한다.
각 프로세스의 도착시간과 프로세스의 실행에 필요한 시간은 아래 표와 같다.
CPU 스케줄링 알고리즘으로 RR을 사용한다고 가정한다.
3개의 프로세스가 CPU에서 작업을 하고 마치는 순서는?
(단, CPU를 사용하는 타임 슬라이는 2이다.)
| 작업 | 도착 시간 | 실행 |
| P1 | 0 | 5 |
| P2 | 1 | 7 |
| P3 | 3 | 4 |
A. P1, P3, P2
- 풀이
- 해당 문제의 함정은 도착 시간에 있음
- 아래 표에서 경과 시간이 0일 때 P1이 2초 실행하는 동안 Queue에 P2가 적재
- P2가 실행될 때 P3는 아직 Queue에 들어오지 않은 상태이기 때문에 Queue에 P1이 적재
- 경과시간 2에서 P2가 1초 실행되었을 때 P3가 Queue에 들어옴
- Queue에는 이미 P1이 있기 때문에 P1, P3 순서로 적재
- P2의 실행이 끝나고 P1이 실행될 때 P3 뒤에 P2가 붙어 Queue에는 P3, P2가 됨
| 경과 시간 | 0 | 2 | 4 | 6 | 8 | 10 | 11 | 13 | 15 |
| 프로세스 | P1 | P2 | P1 | P3 | P2 | P1 | P3 | P2 | P2 |
| 실행 시간 | 2 | 2 | 2 | 2 | 2 | 1 | 2 | 2 | 1 |
| 남은 시간 | 3 | 5 | 1 | 2 | 3 | 0 | 0 | 1 | 0 |
| Queue | P2 | P1, P3 | P3, P2 | P2, P1 | P1, P3 | P3, P2 | P2 | P2 | P2 |
Q. 아래의 프로세스 P1, P2, P3을 시간 할당량(Time Quantum)이 2인 RR 알고리즘으로 스케줄링할 때, 평균 응답시간으로 옳은 것은?
(단, 응답시간이란 프로세스의 도착시간부터 처리가 종료될 때까지의 시간을 말한다.
계산 결과값을 소수점 둘째 자리에서 반올림 한다.)
| 프로세스 | 도착 시간 | 실행 시간 |
| P1 | 0 | 3 |
| P2 | 1 | 4 |
| P3 | 3 | 2 |
A. 5.7
평균 반환(응답)시간 = 5 + 8 + 4 = 17 / 3 = 5.66666666
| 경과 시간 | 0 | 2 | 4 | 5 | 7 |
| 프로세스 | P1 | P2 | P1 | P3 | P2 |
| 실행 시간 | 2 | 2 | 1 | 2 | 2 |
| 남은 시간 | 1 | 2 | 0 | 0 | 0 |
| Queue | P2 | P1, P3 | P3, P2 | P2 |
| 프로세스 | 도착 시간 | 실행 시간 | 대기 시간 | 반환 시간 |
| P1 | 0 | 3 | 2 - 0 = 2 | 5 |
| P2 | 1 | 4 | 5 - 1 = 4 | 8 |
| P3 | 3 | 2 | 5 - 3 = 2 | 4 |
Q. 다음 표에서 보인 4개의 프로세스들을 시간 할당량이 5인 라운드 로빈 스케줄링 기법으로 실행시켰을 때 평균 반환 시간을 구하시오.
| 프로세스 | 도착 시간 | 실행 시간 |
| P1 | 0 | 10 |
| P2 | 1 | 15 |
| P3 | 3 | 6 |
| P4 | 6 | 9 |
A. 29
평균 반환 시간 = 20 + 39 + 28 + 29 = 116 / 4 = 29
| 경과 시간 | 0 | 5 | 10 | 15 | 20 | 25 | 30 | 31 | 35 |
| 프로세스 | P1 | P2 | P3 | P1 | P4 | P2 | P3 | P4 | P2 |
| 실행 시간 | 5 | 5 | 5 | 5 | 5 | 5 | 1 | 4 | 5 |
| 남은 시간 | 5 | 10 | 1 | 0 | 4 | 5 | 0 | 0 | 0 |
| Queue | P2, P3 | P3, P1, P4 | P1, P4, P2 | P4, P2, P3 | P2, P3 | P3, P4 | P4, P2 | P2 |
| 프로세스 | 도착 시간 | 실행 시간 | 대기 시간 | 반환 시간 |
| P1 | 0 | 10 | 10 - 0 = 10 | 20 |
| P2 | 1 | 15 | 25 - 1 = 24 | 39 |
| P3 | 3 | 6 | 25 - 3 = 22 | 28 |
| P4 | 6 | 9 | 26 - 6 = 20 | 29 |
'License' 카테고리의 다른 글
| [정처기 실기 - 계산식] 크론 표현식 / 퍼미션 / LOC 기법 (1) | 2025.06.10 |
|---|---|
| [정처기 실기 - 계산식] 디스크 스케줄링 [ FCFS / SSTF / SCAN / C-SCAN / LOOK / C-LOOK ] (0) | 2025.06.10 |
| [정처기 실기 - 계산식] 주기억 장치 계산식 / 페이지 교체 알고리즘 (0) | 2025.06.03 |
| [정처기 실기 - 계산식] IP 클래스 / 서브넷마스크 / 서브넷 계산 (0) | 2025.06.02 |
| [매경테스트] 재무 오답정리 (1) | 2024.11.29 |