명품 운영체제 연습문제 5장 복합문제

안녕하세요 눈사람입니다. 운영체제를 학습하면서 풀어본 연습문제 답을 공유하고자, 포스트합니다.

해당 포스트는 직접 풀어보면서 작성한 글이므로 정답이 아닐 수 있습니다.

---

5장 연습문제(복합문제)

1. 다음 표와 같이 5개의 스레드가 있다. 스레드들이 모두 0의 시간에 도착하여 T1에서 T5의 순서로 준비 큐에 대기 중이라고 할 때 다음 물음에 답하라. 실행 시간 동안 스레드는 입출력 없이 실행된다고 가정한다.

스레드	실행시간(ms)	우선순위(숫자가 클수록 높은순서)
T1	2	2
T2	3	1
T3	8	4
T4	1	2
T5	4	3

 

(1) FCFS, SJF, Non-Preemptive Priority 스케줄링 알고리즘 각각에 대해 스레드들이 스케줄링되어 실행되는 과정을 차트로 그리고 5개의 스레드가 모두 실행되는데 걸린 평균 대기 시간을 계산하라.

FCFS

 

각 스레드는 모두 0의 시간에 도착하였기 때문에 자신의 실행 시기 만큼의 대기 시간을 갖는다. 따라서 현재 차트에서 5개 스레드가 모두 실행되는데 걸린 평균 대기 시간은 6.8ms이다.

SJF

 

모두 같은 0의 시간에 도착한 스레드들이므로 실행시간이 짧은 것부터 실행시켜준다. 이때 평균 대기시간은 4.8ms이다.

Non-Preemptive Priority

 

비선점형 우선순위 스케줄링 알고리즘이므로, 우선순위가 높은 것부터 차례대로 실행시키되 강제 종료시키지 않고 실행한다. 모두가 같은 시간에 도착했으므로 우선순위가 높은 것부터 차례대로 실행하며 이때 평균 대기 시간은 9.8ms이다.

 

(2) RR(타임 슬라이스 = 2ms)으로 스케줄링할 때 실행되는 과정을 차트로 그리고 5개의 스레드가 모두 실행되는데 걸린 평균 대기 시간을 계산하라

RR(Round Robin)

RR 알고리즘은 스레드들에게 공평한 실행 기회를 주기 위해 큐에 대기 중인 스레드들을 타임 슬라이스 주기로 돌아가며 선택한다. 따라서 2ms 간격으로 스레드들을 돌아가며 선택하여 실행한다. 이때 평균 대기 시간은 6.6ms이다.

 

(3) RR(타임 슬라이스 = 2ms)으로 스케줄링할 때 스케줄링 오버헤드(스케줄링 시간 + 컨텍스트 스위칭 시간)가 평균적으로 0.1ms 걸린다고 하면 5개의 스레드가 모두 실행되는데 걸린 시간은 총 얼마인가?

 

한 스레드에서 다음 스레드로 전환할 때마다 오버헤드를 추가해야 한다. 실행 시작 시나 마지막 스레드가 완료된 후에는 컨텍스트 전환이 필요하지 않으므로 오버헤드가 추가되지 않는다. 따라서 실행 시각 2, 4, 6, 7, 9, 10, 12, 14에 총 8회의 오버헤드가 추가되므로 총 걸린 시간은 스레드 실행 시간인 18ms에 0.8ms를 더한 값인 18.8ms가 된다.

 

2. 다음 표와 같이 5개의 스레드가 있다. 시간 단위는 밀리초이며 스레드들은 시간에 맞추어 도착한다. 실행 시간 동안 스레드는 입출력 없이 실행된다고 가정한다.

스레드	도착시간	실행시간(ms)	우선순위(숫자가 클수록 높은순서)
T1	0	4	3
T2	0	3	2
T3	0	8	5
T4	1	1	1
T5	9	5	4

 

(1) FCFS, SJF, Non-Preemptive Priority 스케줄링 알고리즘 각각에 대해 스레드들이 스케줄링되어 실행되는 과정을 그리고 5개의 스레드를 실행하는데 걸린 평균 대기 시간을 계산하라.

FSFS

 

FCFS 알고리즘은 도착 순서대로 실행하며 선점을 허용하지 않는다. 평균 대기 시간은 6.4ms이다.

SJF

 

필요한 최단 실행 시간에 따라 스레드를 실행하며 선점은 허용하지 않는다. 평균 대기 시간은 4.2ms이다.

Non-Preemptive Priority

 

스레드의 우선순위에 따라 실행되며 우선순위 번호가 높을 수록 스레드가 더 일찍 실행된다. 마찬가지로 선점을 허용하지않는다

평균 대기 시간은 9.4ms이다.

 

(2) SRTF 알고리즘으로 스케줄링되어 실행되는 과정을 그리고 평균 대기 시간을 계산하라.

SRTF

 

실행 시간이 가장 짧은 프로세스를 선택하여 다음 실행을 수행하는 선점형 스케줄링 알고리즘이다. 새로운 프로세스가 도착할 때 실행시간을 비교하여 남은 시간이 가장 짧은 프로세스가 대신하게 된다. 평균 대기 시간은 3.6ms이다.

 

(3) Preemptive Priority 알고리즘으로 스케줄링되어 실행되는 과정을 그리고 평균 대기 시간을 계산하라.

Preemptive Priority

 

선점형 우선순위 스케줄링 알고리즘은 스레드의 우선순위에 따라 실행되며 새로운 스레드가 도착할 때 우선순위가 높다면 교체되어 실행된다. 평균 대기 시간은 9.8ms이다.