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

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

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

제1문 (25점)

단일 프로세서 환경에서 여러 쓰레드를 가진 두 개의 프로세스가 수행 중이다. 쓰레드의 우선순위와 수행 내용은 아래 표와 같다.
[그림]

쓰레드	우선순위	수행 내용
A	1	15ms 수행－시스템 I/O 호출－10ms 수행
B	2	15ms 수행
C	3	15ms 수행
D	1	15ms 수행－시스템 I/O 호출－5ms 수행
E	2	25ms 수행

다음 가정에 기반하여 물음에 답하시오. (총 25점)

○프로세스의 우선순위는 동일하고, 라운드로빈 스케줄링으로 수행된다.
○쓰레드의 우선순위는 값이 작을수록 순위가 높고, 선점형 커널이다.
○타임 퀀텀(time quantum)은 10ms이다.
○시스템 I/O 호출에서 커널 소요시간은 없고, 입출력에 소요되는 시간만 20ms이다.
○문맥 교환에 소모되는 시간은 없다.
○두 프로세스 중 프로세스 1이 먼저 선택되어 수행된다.

(1) 쓰레드가 사용자 수준 쓰레드로 구현되어 있을 때, 시간에 따른 쓰레드의 수행을 간트 차트로 그리시오. (10점)
(2) 쓰레드가 커널 수준 쓰레드로 구현되어 있을 때, 시간에 따른 쓰레드의 수행을 간트 차트로 그리시오. (단, 타임 퀀텀 내에서는 같은 프로세스에 있는 쓰레드 처리를 우선으로 한다) (10점)
(3) 위 결과를 바탕으로 사용자 수준 쓰레드와 커널 수준 쓰레드를 비교하시오. (5점)

제2문 (30점)

요구 페이징을 지원하는 시스템에서, 디스크에 8개의 페이지(페이지 번호는 0번부터 7번까지)를 갖는 프로세스가 4개의 페이지 프레임을 할당받았다. 이 프로세스가 아래 순서로 페이지를 참조한다. 다음 물음에 답하시오. (단, LRU는 Least Recently Used, LFU는 Least Frequently Used를 의미한다) (총 30점)

페이지 참조 순서

0, 1, 2, 2, 7, 1, 5, 7, 0, 2, 1, 0, 4, 0, 3, 6, 2, 6, 1, 4, 6, 5, 7, 5, 3, 4, 3, 7, 2, 2, 3, 2

(1) LRU 교체 정책을 적용할 때, ①페이지 프레임의 마지막에 남아 있는 페이지 번호와 ②페이지 부재 횟수를 구하시오. (10점)
(2) LFU(x) 교체 정책은 현재 참조와 직전 (x - 1)개의 참조에서 참조된 횟수만을 이용하는 정책이다. LFU(8) 교체 정책을 적용할 때, ①페이지 프레임의 마지막에 남아 있는 페이지 번호와 ②페이지 부재 횟수를 구하시오. (단, 참조 횟수가 같은 경우 LRU 교체 정책을 적용한다) (10점)
(3) LFU(x) 교체 정책을 일반화하여, 주어진 x에 대하여 score ( i , x )의 값이 가장 작은 페이지를 교체하는 NEW_LFU(x) 교체 정책을 구현하고자 한다. 이를 위해 다음과 같은 함수를 정의하였다.
score ( i , x ) = \sum_{t} = 0^{x} - 1 w ( t ) R_{i} ( t )
○t = 0은 현재 참조를 의미한다.
○w ( t )는 직전 t번째 참조의 가중치를 나타낸다.
○R_{i} ( t )는 직전 t번째 참조에서 페이지 i가 참조되었다면 1, 그렇지 않다면 0인 함수이다.

가중치 w ( t )의 할당 방법에 따라서 NEW_LFU(x)가 ①LFU(x) 교체 정책이 되거나 ②LRU 교체 정책이 될 수 있다. 이 때, 가중치 w ( t )의 할당 방법을 각각 기술하고, w ( t )의 예를 들어보시오. (10점)

제3문 (15점)

RAID(Redundant Array of Independent Disk)에 대한 다음 물음에 답하시오. (단, 디스크 용량은 모두 동일하다) (총 15점)

(1) 디스크가 2개인 RAID 0을 사용하는 시스템에서 RAID가 없는 시스템 대비 가용 공간의 차이를 설명하시오. (3점)
(2) 디스크가 2개인 RAID 1을 사용하는 시스템에서 ①RAID가 없는 시스템 대비 가용 공간의 차이를 설명하고, ②데이터 복원의 원리를 설명하시오. (6점)
(3) 디스크가 5개인 RAID 4를 사용하는 시스템에서 ①RAID가 없는 시스템 대비 가용 공간의 차이를 설명하고, ②데이터 복원의 원리와 함께 예를 들어 데이터 복원 과정을 설명하시오. (6점)

제4문 (10점)

요구 페이징 기법을 사용하는 가상 메모리 시스템을 가정하자. 다음 그림은 두 프로세스 P₀와 P₁이 특정 시간에 메모리에 적재되어 있는 상황을 나타낸다.
[그림]
다음 가정에 기반하여 물음에 답하시오. (총 10점)

○P₀와 P₁ 프로세스, 그리고 두 프로세스 수행에 필요한 모든 자원들은 하드디스크에 존재한다.
○P₀와 P₁ 프로세스에서 사용하는 각각의 페이지들은 0번부터 오름차순으로 순차적으로 하드디스크에서 메모리로 적재되었다.
○페이지 교체 정책은 지역적인 FIFO(First In First Out) 정책을 사용한다.
○유효－무효 비트의 값이 ‘1’인 경우는 해당 페이지가 물리 메모리에 적재되어 있고, ‘0’인 경우는 해당 페이지가 물리 메모리에 없고 하드디스크에는 존재함을 의미한다. 이 때 페이지 테이블에는 프레임 번호 대신 하드디스크에 저장되어 있는 주소가 기록된다.

(1) P₀와 P₁ 프로세스를 위한 페이지 테이블을 각각 완성하시오. (단, 페이지의 하드디스크 주소는 임의로 설정한다) (4점)
(2) P₀프로세스가4번 프레임의 “적재 M”이라는 명령을 실행하려고 한다. 여기서 M은 페이지 M에 있는 데이터를 의미한다. ①이 명령이 실행될 때 페이지 부재가 발생하는데 그 이유를 설명하고, ②이 명령을 성공적으로 실행하기 위한 과정을 기술하고, ③P₀와 P₁ 프로세스의 변경된 페이지 테이블을 각각 완성하시오. (6점)

제5문 (20점)

단일 프로세서 환경에서 아래 표와 같은 5개 프로세스에 대해 다단계 피드백 큐 기법을 이용하여 스케줄링 하고자 한다.

프로세스	도착시간	CPU 요구시간
A	0	8
B	3	4
C	5	9
D	8	5
E	12	6

다음 가정에 기반하여 물음에 답하시오. (총 20점)

○다단계 피드백 큐는 우선순위가 높은 단계로부터 낮은 단계로 Q1, Q2, Q3의 3단계로 구성되며, 신규 프로세스는 Q1으로 진입한다.
○Q1, Q2는 FCFS(First Come First Served) 알고리즘을 사용하며 CPU 할당시간은 각각 2와 3이다.
○Q2는 Q1에 의해 선점되지 않는다.
○Q3는 SRT(Shortest Remaining Time) 알고리즘을 사용한다.
○Q1, Q2에서 프로세스는 할당시간을 소비한 후에도 종료되지 않으면 낮은 우선순위의 큐로 이동한다.

(1) Q3에서 종료되는 프로세스를 순서대로 모두 기술하시오. (4점)
(2) 5개 프로세스의 평균 반환시간(turnaround time)과 평균 대기시간(waiting time)을 구하시오. (8점)
(3) Q3를 라운드로빈(타임 퀀텀＝4) 알고리즘을 사용한다고 했을 때 5개 프로세스의 평균 반환시간과 평균 대기시간을 구하시오. (8점)