2018년 5급 공채 기술 2차 운영체제론
문제 4개 · 100점. 참고 답안·채점 기준은 앱에서 볼 수 있습니다.
모든 계산문제는 풀이과정을 제시하시오.
제1문 (24점)
가상메모리 관리 기법에 대하여 다음 물음에 답하시오. (총 24점)
- (1) 16비트 주소 체계를 사용하고 세그먼트(segment) 하나의 최대 크기가 1KB인 세그멘테이션(segmentation) 기법을 사용하는 시스템을 가정하자.
가) 이 시스템의 물리 메모리 중 세그먼트가 들어갈 수 있는 사용자 메모리 영역의 총 크기가 64KB라면, 하나의 프로세스는 최대 몇 개의 세그먼트로 구성되는지 계산하시오. (4점)
나) 세그먼트 테이블(segment table)의 각 엔트리가, 세그먼트 시작 위치를 바이트 단위로 나타내는 시작값(base)과 세그먼트 길이를 나타내는 한계값(limit) 두 가지 요소로만 구성된다고 할 때, 각 엔트리는 최소한 몇 비트로 구성되는지 계산하시오. (4점) - (2) 페이징 시스템에 대하여 다음 물음에 답하시오.
가) 페이지의 크기와 프레임의 크기가 4바이트, 가상 주소 공간은 4개의 페이지로 구성될 때, 다음 페이지 테이블의 가상 주소 5와 가상 주소 14에 대한 물리 주소는 각각 얼마인지 계산하시오. (단, 가상 주소의 범위는 0에서 15까지이다) (4점)페이지 인덱스 프레임 인덱스 0 5 1 7 2 2 3 4
나) TLB(Translation look-aside buffer)가 사용된다고 가정하자. 메모리 접근시간을 \alpha, TLB 검색 시간을 \beta, TLB 적중률을 \gamma라고 할 때, 유효 메모리 접근시간을 계산하시오. (단, 1단계 페이지 테이블을 가정한다) (4점)
다) 28비트 가상 주소 공간을 사용할 경우 페이지 크기가 4KB이다. 페이지 테이블의 각 엔트리가 4바이트를 차지한다고 가정할 때, 1단계로 구성된 페이지 테이블의 크기를 KB 단위로 계산하시오. (4점)
라) 페이지 크기의 증가가 내부 단편화와 페이지 테이블의 크기에 미치는 영향을 설명하시오. (4점)
제2문 (30점)
프로세스 P0, P1, P2, P3가 다음 표와 같이 준비 큐에 도착하였다고 가정하자. 물음에 답하시오. (총 30점)
| 프로세스 | 도착시간(초) | 실행시간(초) |
| P0 | 0 | 7 |
| P1 | 1 | 5 |
| P2 | 2 | 3 |
| P3 | 3 | 1 |
- (1) 선점형 SJF(Shortest Job First) 스케줄링 알고리즘과 비선점형 SJF 스케줄링 알고리즘에 대해 전체 프로세스의 평균 대기시간을 계산하시오. (16점)
- (2) 다음과 같은 가정 하에서 Multi-level Feedback Queue 스케줄링 알고리즘을 사용할 때, 각 프로세스의 대기시간과 전체 프로세스의 평균 대기시간을 계산하시오. (14점)
<가 정> ○대기 큐의 번호 i는 0부터 시작되고, 최상위 대기 큐의 번호는 0이며, 큐의 번호가 작을수록 우선순위가 높다.
○새로 생성되는 프로세스는 항상 최상위 대기 큐에 들어온다.
○모든 대기 큐에는 선입선처리(FCFS) 스케줄링 알고리즘이 적용된다.
○각 대기 큐 i에 대한 시간 할당량은 2^{{i}}이며, 할당량이 경과해도 프로세스가 종료되지 못하면 하위 대기 큐로 이동한다.
○프로세스가 수행 중에 상위의 대기 큐에 다른 프로세스가 진입할 경우, 현재 남아있는 시간 할당량을 모두 사용하고 CPU를 반환한다.
○최상위 대기 큐를 제외한 각 대기 큐는 프로세스들의 대기시간에 대한 임계치로 2^{{2 i}}을 가지며, 대기시간이 이 임계치와 같거나 큰 프로세스는 상위 대기 큐로 이동한다. 또한 대기 큐 i에서 프로세스가 CPU를 할당받을 순서가 되더라도 그 시점에서 대기시간이 임계치보다 크거나 같으면 해당 프로세스는 먼저 상위 대기 큐로 이동한 후 CPU를 할당받는다.
제3문 (20점)
다음과 같이 5개의 프로세스 P1, P2, P3, P4, P5와 4종류의 자원 A(6개), B(7개), C(12개), D(12개)가 존재하는 시스템을 가정하자. 교착상태 회피(deadlock avoidance)기법을 적용한다고 가정하고, 각 프로세스의 자원에 대한 최대 요구량과 현재 할당량이 다음 표와 같을 때 물음에 답하시오. (총 20점)
| 최대 요구량 | 현재 할당량 | |||||||
| A | B | C | D | A | B | C | D | |
| P1 | 0 | 0 | 1 | 2 | 0 | 0 | 1 | 2 |
| P2 | 2 | 7 | 5 | 0 | 2 | 0 | 0 | 0 |
| P3 | 6 | 6 | 5 | 6 | 0 | 0 | 3 | 4 |
| P4 | 4 | 3 | 5 | 6 | 2 | 3 | 5 | 4 |
| P5 | 0 | 6 | 5 | 2 | 0 | 3 | 3 | 2 |
- (1) 위 상태에서 현재 남아 있는 자원의 양을 보여주는 가용자원량 벡터(available-resources vector)와 각 프로세스가 추가로 요청할 수 있는 자원의 양을 보여주는 추가요구가능량 행렬(additional-needs matrix)을 구하시오. (4점)
- (2) 위 상태가 안전상태(safe state)인지 불안전상태(unsafe state)인지를 판단하시오. 안전상태인 경우에는 안전순서(safe sequence)를 기술하고, 불안전상태인 경우에는 그 이유를 설명하시오. (4점)
- (3) 위 상태에서 프로세스 P3가 자원 (A, B, C, D)에 대해 (0, 1, 0, 0) 만큼의 단위자원을 요청했을 경우, 이를 허락해야 하는지 아니면 거부해야 하는지를 판단하고, 그 이유를 설명하시오. (4점)
- (4) 위 상태에서 프로세스 P2가 자원 (A, B, C, D)에 대해 (0, 1, 0, 0) 만큼의 단위자원을 요청했을 경우, 이를 허락해야 하는지 아니면 거부해야 하는지를 판단하고, 그 이유를 설명하시오. (4점)
- (5) 교착상태 회피 기법이 교착상태 검출/복구 기법과 다른 가장 큰 차이점을 설명하시오. (4점)
제4문 (26점)
하드디스크의 용량과 성능 정보는 다음 표와 같다. 물음에 답하시오. (총 26점)
| 디스크 총 용량 | 1TB |
| 섹터 크기 | 512바이트 |
| 데이터 저장 면의 수 | 8개 |
| 평균 탐색시간 | 5ms |
| 디스크 회전속도 | 7,200RPM |
| 데이터 전송속도 | 100MB/s |
- (1) 한 면에 저장되는 트랙 수가 8,192개이고 각 트랙에 저장되는 섹터 수가 동일하다고 가정할 때, 한 트랙에 존재하는 섹터 수를 계산하시오. (6점)
- (2) 10KB 파일을 읽는 데 소요되는 평균 기대시간을 계산하시오. (단, 이 파일은 한 트랙에 모두 연속으로 저장되어 있다) (6점)
- (3) SCAN 계열 알고리즘 등 운영체제에서 실제로 사용하는 많은 디스크 스케줄링 알고리즘은 트랙 정보만 활용하여 탐색시간을 개선하려는 노력만 하고, 회전지연시간이나 데이터전송시간은 일반적으로 고려하지 않는다. 그 이유를 설명하시오. (4점)
- (4) 다음 가정에 따라 다양한 디스크 스케줄링 기법을 적용하려고 한다. 물음에 답하시오.
<가 정> ○현재 트랙 64를 처리하고 있으며, 방금 전에 트랙 62를 처리하였다.
○현재 대기 큐에 있는 요청들은 (59, 23, 61, 36, 7, 98, 68, 49, 72)이다.
가) 실생활의 엘리베이터의 동작과 가장 유사한 디스크 스케줄링 기법의 명칭을 쓰고, 이 기법을 적용할 때의 디스크 헤드 이동 경로를 쓰시오. (5점)
나) 디스크 헤드의 현재 트랙 위치에서 가장 가까운 요청 트랙을 먼저 처리하는 기법으로서, 탐색 패턴에 지역성이 높게 나타나는 디스크 스케줄링 기법의 명칭을 쓰고, 이 기법을 적용할 때의 디스크 헤드 이동 경로를 쓰시오. (5점)