2022년 5급 공채 기술 2차 운영체제론
문제 5개 · 100점. 참고 답안·채점 기준은 앱에서 볼 수 있습니다.
제1문 (15점)
교착상태(deadlock)를 다루는 여러 방법 중 회피(avoidance)가 있다. 시스템에 5개의 프로세스 P0, P1, P2, P3, P4와 네 개의 자원 A, B, C, D가 있고, 현재 시스템의 상태가 아래와 같다고 가정하자.
여기서, <Allocation>은 프로세스에 현재 할당된 각 자원의 수, <Max>는 프로세스가 작업을 수행하기 위해 요청하는 각 자원의 최댓값, <Available>은 현재 시스템 내 가용한 각 자원의 수를 의미한다. 예를 들어, P0는 현재 A, B, C, D 자원을 각각 0, 1, 0, 2개 할당받았고, 작업을 수행하기 위해 최대 0, 1, 1, 2개를 요청하며, 현재 시스템에 A, B, C, D가 각각 2, 0, 1, 2개 가용함을 의미한다. 교착상태 회피 기법 중 은행원 알고리즘(banker's algorithm)을 이용해 다음 물음에 답하시오. (총 15점)
| <Allocation> | <Max> | <Available> | ||||||||||||||||||||||
| A | B | C | D | A | B | C | D | A | B | C | D | |||||||||||||
| P0 | 0 | 1 | 0 | 2 | 0 | 1 | 1 | 2 | 2 | 0 | 1 | 2 | ||||||||||||
| P1 | 3 | 0 | 1 | 0 | 3 | 2 | 1 | 0 | ||||||||||||||||
| P2 | 1 | 2 | 3 | 0 | 1 | 3 | 4 | 1 | ||||||||||||||||
| P3 | 2 | 0 | 2 | 1 | 4 | 2 | 4 | 2 | ||||||||||||||||
| P4 | 2 | 5 | 0 | 4 | 5 | 5 | 2 | 5 | ||||||||||||||||
여기서, <Allocation>은 프로세스에 현재 할당된 각 자원의 수, <Max>는 프로세스가 작업을 수행하기 위해 요청하는 각 자원의 최댓값, <Available>은 현재 시스템 내 가용한 각 자원의 수를 의미한다. 예를 들어, P0는 현재 A, B, C, D 자원을 각각 0, 1, 0, 2개 할당받았고, 작업을 수행하기 위해 최대 0, 1, 1, 2개를 요청하며, 현재 시스템에 A, B, C, D가 각각 2, 0, 1, 2개 가용함을 의미한다. 교착상태 회피 기법 중 은행원 알고리즘(banker's algorithm)을 이용해 다음 물음에 답하시오. (총 15점)
- (1) 현재 시스템의 상태가 안전한지(safe)를 답하고, 그 이유를 설명하시오. (8점)
- (2) P3가 A, B, C, D를 각각 1, 0, 1, 1개를 요청했을 경우, 이 요청을 바로 수락(grant)할 수 있는지를 답하고, 그 이유를 설명하시오. (7점)
제2문 (25점)
3개의 단계(0～2)로 이루어진 다단계 피드백 큐를 갖는 스케줄러가 있다. \mathrm{T}_{{p}}는 프로세스 \mathrm{T}의 우선순위를 의미하고, 스케줄러는 다음과 같이 동작한다고 가정한다.
이때, 다음과 같은 프로세스들에 대해 물음에 답하시오. (단, RR을 위한 시간할당량은 1이라고 가정한다) (총 25점)
| ①우선순위의 값이 낮은 프로세스가 더 높은 우선순위를 갖는다. ②프로세스 \mathrm{T}가 처음 시스템에 들어오면 \mathrm{T}_{{p}}는 0이 된다. ③우선순위가 0인 프로세스는 0단계 큐에, 우선순위가 1인 프로세스는 1단계 큐, 우선순위가 2 이상인 프로세스는 2단계 큐에 들어간다. ④각 단계에서는 RR(Round-Robin) 정책을 사용하고, 각 큐에서 프로세스는 엄격한 FIFO(즉, 프로세스가 시스템에 들어오거나 임의의 큐로 이동할 때에는 큐의 마지막에 추가됨)를 따른다. ⑤프로세스 \mathrm{T}가 실행 중인 상태이면, 단위시간 1마다 \mathrm{T}_{{p}}는 1씩 증가한다. ⑥단위시간 3마다, \mathrm{T}_{{p}}는 다음과 같이 계산된다.
여기서, load는 현재 시스템 상에 있는 프로세스의 수이다. 즉, 모든 우선순위는 3, 6, 9, … 단위시간마다 위의 수식에 의해 조정된다. 단, 실행 중인 프로세스에 대해서 d는 우선순위를 조정하기 전에 먼저 증가된다고 가정한다. ⑦단위시간 3마다 우선순위를 조정할 때, 우선순위를 조정하는 순서는 2단계 큐, 1단계 큐, 0단계 큐로 진행한다. | |||||||
| d \, | |||||||
이때, 다음과 같은 프로세스들에 대해 물음에 답하시오. (단, RR을 위한 시간할당량은 1이라고 가정한다) (총 25점)
| 프로세스 | 도착시간 | CPU 시간 |
| A | 0 | 6 |
| B | 2 | 4 |
| C | 4 | 2 |
| D | 5 | 2 |
- (1) 각 시간 단위별로 처리되는 프로세스를 나타내는 다음과 같은 간트 차트를 완성하고, 각 시간 단위별로 다단계 피드백 큐의 내용을 그려라. (13점)
[그림] - (2) 평균반환시간을 구하시오. (12점)
제3문 (20점)
요구 페이징(demand paging) 기법을 사용하는 페이징 시스템(paging system)에서 주기억장치 용량이 256MB이고, 가상주소 공간으로 4GB를 사용한다고 가정한다. 각 페이지 크기는 4KB이고, 현재의 페이지 테이블(page table)이 아래와 같을 때, 다음 물음에 답하시오. (총 20점)
| 페이지 번호 | 유효/무효 비트 | 페이지 프레임 번호 |
| 0 | 0(무효) | 10 |
| 1 | 1(유효) | 2 |
| 2 | 1(유효) | 1 |
| 3 | 0(무효) | 8 |
| 4 | 0(무효) | 6 |
| 5 | 1(유효) | 4 |
| 6 | 1(유효) | 9 |
| 7 | 0(무효) | 5 |
- (1) 가상 주소(virtual address)를 표현하는데 필요한 최소 비트 수를 구하시오. (2점)
- (2) 물리 주소(physical address)를 표현하는데 필요한 최소 비트 수를 구하시오. (2점)
- (3) 가상 주소를 (p, d)로 표현한다고 가정할 때, p의 표현에 필요한 최소 비트 수와 d의 표현에 필요한 최소 비트 수를 각각 구하시오. (단, 여기서 p는 페이지 번호, d는 오프셋(offset)을 의미한다) (3점)
- (4) 1단계 페이지 테이블(single level page table)을 사용한다고 가정할 때, 페이지 테이블의 최대 엔트리 개수를 구하시오. (2점)
- (5) 페이지 프레임의 크기와 페이지 프레임의 개수를 각각 구하시오. (2점)
- (6) 위에 주어진 페이지 테이블을 참고하여, 가상 주소 12,000번지를 물리 주소로 변환하시오. (단, 물리 주소를 구할 수 없는 경우에는 해당 가상 주소 접근 시 어떤 현상이 발생하는지 설명하시오) (3점)
- (7) 위에 주어진 페이지 테이블을 참고하여, 가상 주소 20,000번지를 물리 주소로 변환하시오. (단, 물리 주소를 구할 수 없는 경우에는 해당 가상 주소 접근 시 어떤 현상이 발생하는지 설명하시오) (3점)
- (8) 위에 주어진 페이지 테이블을 참고하여, 물리 주소 10,000번지에 해당하는 가상 주소를 구하시오. (3점)
제4문 (20점)
다음은 쓰레드를 구현한 의사코드 일부이다. 이를 보고 물음에 답하시오. (총 20점)
int counter = 0;
thread_function1( )
{
for (int i = 0; i < 100000; i++) {
counter++;
}
}
thread_function2( )
{
for (int i = 0; i < 100000; i++) {
counter--;
}
}
thread_function1( )
{
for (int i = 0; i < 100000; i++) {
counter++;
}
}
thread_function2( )
{
for (int i = 0; i < 100000; i++) {
counter--;
}
}
- (1) 위의 두 함수를 각각 쓰레드로 동시에 실행하면 두 쓰레드가 종료되었을 때 counter 변수의 최종 값이 0이 아닐 수 있다. 그 이유를 설명하시오. (5점)
- (2) counter 변수의 값이 정상적인 결과인 0이 나오도록 위의 코드를 이진 세마포어를 이용하여 수정하시오. (단, 세마포어 변수 s를 사용하고, wait(s)와 signal(s) 연산을 이용하시오) (5점)
- (3) 2)의 결과 코드를 “counter++”와 “counter--”가 한 번씩 번갈아가면서 실행되도록 이진 세마포어를 이용하여 수정하시오. (단, 세마포어 변수 th1과 th2를 추가로 사용하시오) (10점)
제5문 (20점)
다음 표와 같은 특징을 갖는 디스크를 가정하자. 이 디스크에서 A～I의 ID를 갖는 요청에 대하여 디스크 스케줄링 알고리즘을 적용할 때, 다음 물음에 답하시오. (단, 초기에 디스크 헤드는 79에 위치하며, 헤드의 진행 방향은 증가하는 방향이고, A～I의 요청은 동시에 도착한 것으로 가정한다. 디스크 헤드 이동 시의 회전 지연 시간은 평균 회전 지연 시간을 적용한다) (총 20점)
| 디스크 특징 | |
| 평균 회전 지연 | 10ms |
| 탐색 시간 | 20＋0.1×ms (는 이동 거리) |
| 트랙(실린더) 수 | 200 (0부터 199) |
| 요청 ID | A | B | C | D | E | F | G | H | I |
| 트랙 번호 | 99 | 189 | 9 | 49 | 89 | 74 | 34 | 164 | 109 |
- (1) SSTF(Shortest Seek Time First) 스케줄링 알고리즘을 설명하고, 이 알고리즘을 적용할 때 디스크 헤드의 전체 이동 거리와 전체 지연 시간(전송 시간 제외)을 계산하시오. (4점)
- (2) LOOK 스케줄링 알고리즘과 C-LOOK(Circular-LOOK) 스케줄링 알고리즘을 설명하고, 각 알고리즘을 적용할 때 디스크 헤드의 전체 이동 거리와 전체 지연 시간(전송 시간 제외)을 계산하시오. (10점)
- (3) SSTF, LOOK, C-LOOK 스케줄링 알고리즘 중에서 특정 트랙에 대하여 기아(starvation) 상태가 발생할 수 있는 알고리즘, 모든 트랙에 대하여 공평하게 접근하는 알고리즘, 그리고 디스크 요청의 대부분이 가까이에 있는 특정 트랙들에 집중될 때 적합한 알고리즘을 각각 선택하고 그 이유를 설명하시오. (6점)