2019년 5급 공채 기술 2차 운영체제론

문제 4개 · 100점. 참고 답안·채점 기준은 앱에서 볼 수 있습니다.

모든 계산문제는 풀이과정을 제시하시오.

제1문 (25점)

요구 페이징(demand paging)을 사용하는 가상 메모리 시스템(virtual memory system)에서, 아래의 페이지 교체(page replacement) 기법들에 대한 물음에 답하시오. (총 25점)
㉮ LRU(Least Recently Used)
㉯ WS(Working Set) model

	<가 정>

○기법 ㉮의 경우 해당 프로세스에게 총 3개의 페이지 프레임이 할당되어 있다. ○기법 ㉯의 경우 윈도우 크기(window size)는 ４이다. ○각 기법에서 초기에 모든 페이지 프레임들은 비어 있다.

(1) 총 9개의 페이지(페이지 번호 1～9)를 가지고 있는 프로세스가 발생시킨 페이지 참조열(page reference string) ω1, ω2가 다음과 같다.
ω1＝“121234534534567896789”
ω2＝“(12)¹⁰⁰(345)³⁰⁰(6789)²⁰⁰”

각 페이지 참조열 ω1, ω2에 대해 위의 페이지 교체 기법 LRU와 WS model을 사용할 때, 각각의 메모리 상태 변화 과정을 보이고 페이지 부재(page fault) 발생 횟수를 구하시오. (단, 여기서 (12)¹⁰⁰ 표현은 페이지 참조열 “12”가 “121212…”의 형태로 100회 반복됨을 의미한다) (20점)
(2) LRU 기법과 WS model 기법의 공통점과 차이점을 설명하시오. (5점)

제2문 (20점)

식사하는 철학자 문제를 그림과 같이 5명의 철학자(phil 0～phil 4)와 이들 사이의 5개의 젓가락(chop 0～chop 4)으로 표현하였다. 철학자는 생각을 하다가 배가 고프면 양쪽의 젓가락을 모두 확보한 후에 식사를 하고, 식사가 끝나면 양쪽의 젓가락을 모두 반납하고 생각을 계속한다. 두 명 이상의 철학자가 동시에 식사를 할 수도 있다. 젓가락을 확보하고 반납하는 데 뮤텍스를 사용한다. chop i에는 mutex[i]가 사용되며, mutex[i]를 사용하기 위한 함수로는 Lock(mutex[i])와 Unlock(mutex[i])만 있다고 하자. 교착상태에 대한 고려 없이 단순하게 철학자 i를 위한 함수를 작성하면 다음과 같다. 물음에 답하시오. (총 20점)

식사하는 철학자 문제	철학자 i를 위한 함수
[그림]	Phil(int i) { int left = i; int right = (i+1) % 5; while (1) { Lock(mutex[left]); Lock(mutex[right]); 식사; Unlock(mutex[left]); Unlock(mutex[right]); 생각; } }

(1) 위 함수를 사용할 경우 교착상태가 발생하는 상황을 구체적인 시나리오로 제시하시오. (5점)
(2) 교착상태를 방지하기 위해서 시스템 내 모든 자원들에 대하여 일정한 순서를 정해놓고 동시에 사용해야 하는 자원들은 이 순서대로 확보하도록 하는 정책을 적용하려고 한다. 이 정책을 적용할 수 있도록 자원들의 순서를 정의하고, 철학자 i를 위한 함수를 작성하시오. 그리고 이 함수를 적용하면 교착상태가 발생하지 않음을 설명하시오. (15점)

제3문 (30점)

다음과 같이 구현된 가중치 기반의 CPU 스케줄러에서 아래 표와 같이 프로세스 A, B, C가 준비(ready) 큐에 도착할 때 물음에 답하시오. (총 30점)

프로세스	도착시각	수행시간	가중치
A	0	5	1
B	1	5	1
C	2	5	2

	<가 정>

○스케줄링은 매 시각 t마다 수행되며, 시각 t일 때의 가상시간 v_{i} ( t )가 가장 작은 프로세스를 다음 실행 프로세스로 선정한다. 만약 가상시간이 가장 작은 프로세스가 두 개 이상인 경우, 현재 실행 중인 프로세스, 준비 큐에 먼저 도착한 프로세스의 순서로 다음 실행 프로세스를 선정한다. 시각 t는 정수이며, 가상시간 v_{i} ( t )는 수식（1)에 의해 계산된다. 단, 시각 t에 준비 큐에 도착하는 프로세스의 가상시간은 t이다. 수식 (1) v_{{i}} ( t ) = v_{{i}} ( t - 1 ) + \left. \frac{{r_{{i}}}}{{w_{{i}}}} \times \sum_{{process \ j}}^{{}} w_{{j}} \right. ○w_{i}는 프로세스 i의 가중치이며 양의 정수이다. 시각 t에서 가중치의 합 \sum_{{process \ j}}^{{}} w_{{j}}는 현재 수행 중인 프로세스와 준비 상태인 프로세스들의 가중치 합이며, 시각 t에 도착한 프로세스는 가중치의 합 계산 대상에서 제외한다. ○r_{i}는 시각 t－1부터 시각 t 사이에서 프로세스 i가 실행된 시간이다. 즉, 시각 t－1부터 시각 t 사이에서 프로세스 i가 실행되었다면 r_{i}는 1이며, 그렇지 않으면 0이다.

(1) 시각 t에서 각 프로세스의 가상시간 v_{i} ( t )를 다음 표에 표시하시오. (15점)
시각 ０ 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A
Ｂ
Ｃ
(2) 매 시각 어느 프로세스가 다음 실행 프로세스로 선정되는지 다음 표에 표시하시오. (5점)
시각 ０ 1 2 3 4 5 6 7 8 9 10 11 12 13 14
실행
프로세스

(3) 시각 t에서의 오류값 e ( t )는 수식 (2)에 의해 계산된다. R_{{i}} ( t )는 윈도우 크기가 S일 때 프로세스 i가 시간 구간 [t－S, t)에서 실행된 실제 시간이다. 시각 t에서의 오류값을 계산할 때 시각 t에 도착한 프로세스는 계산 대상에서 제외한다.
수식 (2) e ( t ) \, = \, \sum_{{process \, \, i}}^{{}} \left| R_{{i}} ( t ) - \frac{{w_{{i}}}}{{\sum_{{process \, \, j}}^{{}} w_{{j}}}} \times S \, \, \right|
S＝4일 때, 매 시각 오류값을 다음 표에 표시하시오. (10점)

	<가 정>

○t－S가 도착시각보다 작은 프로세스의 경우 S는 (t－도착시각)을 적용한다. 예를 들면 시각 2에서 프로세스 A의 경우 S＝2, 프로세스 B의 경우 S＝1을 적용한다.

시각	1	2	3	4	5	6	7	8	9	10	11	12	13	14
오류값

제4문 (25점)

디스크 회전 속도가 10,000RPM인 하드디스크에서 다음과 같은 규칙에 의해 섹터를 배치한다고 할 때 물음에 답하시오. (총 25점)

○디스크는 데이터를 읽는 작업과 메인 메모리로 데이터를 전송하는 작업을 동시에 수행할 수 없으므로 데이터를 전송하는 동안 헤드가 다음 섹터를 지나치는 것을 방지하기 위해 각 트랙의 연속적인 섹터들을 일정한 간격을 두고 배치한다. 이 간격의 크기를 디스크 인터리빙(disk interleaving) 계수라고 하며, 섹터 단위로 표시한다. 예를 들어, 디스크 인터리빙 계수가 1이면 동일 트랙의 연속적인 섹터들이 한 개의 섹터를 건너뛰고 배치됨을 의미한다.
○디스크 헤드가 다음 섹터를 읽기 위해 한 트랙에서 다음 트랙으로 이동할 때, 디스크 회전에 의해 읽으려고 하는 섹터를 지나치는 경우를 방지하기 위하여 각 트랙의 섹터 0을 이전 트랙의 섹터 0으로부터 일정한 거리만큼 떨어진 위치에 배치한다. 이 거리를 실린더 스큐(cylinder skew)라고 하며, 섹터 단위로 표시한다.

(1) 한 트랙에 존재하는 섹터의 수가 300개이고 트랙 간의 탐색 시간이 200\mu s일 때, 실린더 스큐의 최솟값을 구하시오. (8점)
(2) 한 섹터의 크기가 256바이트일 때 디스크의 최대 데이터 전송률(MB / s)을 구하시오. (단, 1MB를 1,000,000B로 가정한다) (7점)
(3) 디스크에서 메인 메모리로 데이터를 전송하는 과정에서 데이터 전송률이 6.4MB / s라고 가정할 때 디스크 인터리빙 계수의 최솟값을 구하시오. (단, 1MB를 1,000,000B로 가정한다) (10점)

시각	０	1	2	3	4	5	6	7	8	9	10	11	12	13	14
A
Ｂ
Ｃ