2025년 5급 공채 기술 2차 운영체제론
문제 5개 · 100점. 참고 답안·채점 기준은 앱에서 볼 수 있습니다.
제1문 (20점)
단일 프로세서 환경에서 다음과 같은 매개변수를 갖는 다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue Scheduling)을 운용한다고 가정한다. 다음 물음에 답하시오. (총 20점)
○큐의 개수: 3 (Q0, Q1, Q2)
○각 큐에 할당된 시간 할당량(Time quantum): Q0, Q1, Q2 각각 8ms, 16ms, 24ms
○각 큐의 실행 우선 순위: Q0>Q1>Q2
○프로세스가 최초로 실행될 때 진입하는 큐:Q0
○각 큐는 FIFO 방식의 라운드로빈 스케줄링을 운용하며, 실행 중인 경우 상위 레벨의 큐가 하위 레벨의 큐를 선점하지 않는다.
○프로세스에 CPU가 할당될 때 큐에서 제거되며, 각 큐에 할당된 시간 할당량을 다 사용하고도 종료되지 않은 프로세스는 한 단계 낮은 우선 순위 큐에 추가된다.
○Q2에서 스케줄링되어 1회 실행된 이후에도 프로세스의 실행시간이 남아 있다면, 이 프로세스는 Q0에 추가된다.
○각 큐에 할당된 시간 할당량(Time quantum): Q0, Q1, Q2 각각 8ms, 16ms, 24ms
○각 큐의 실행 우선 순위: Q0>Q1>Q2
○프로세스가 최초로 실행될 때 진입하는 큐:Q0
○각 큐는 FIFO 방식의 라운드로빈 스케줄링을 운용하며, 실행 중인 경우 상위 레벨의 큐가 하위 레벨의 큐를 선점하지 않는다.
○프로세스에 CPU가 할당될 때 큐에서 제거되며, 각 큐에 할당된 시간 할당량을 다 사용하고도 종료되지 않은 프로세스는 한 단계 낮은 우선 순위 큐에 추가된다.
○Q2에서 스케줄링되어 1회 실행된 이후에도 프로세스의 실행시간이 남아 있다면, 이 프로세스는 Q0에 추가된다.
- (1) 모든 큐가 비어 있는 상태에서 아래와 같은 CPU 사용 시간(CPU burst time)을 갖는 프로세스들이 다음의 순서대로 동시에 생성된다고 가정한다.P1 (40ms)→P2 (20ms)→P3 (10ms)→P4 (30ms)
이 때, 모든 프로세스가 큐에 추가된 직후의 다단계 큐의 모습은 다음과 같다.Q0 P1(40) P2(20) P3(10) P4(30) Q1 Q2
위 그림에서 P1(40)은 P1의 실행시간이 40ms 남아 있다는 것을 의미한다. 실행이 완료된 프로세스는 모든 큐에서 제거된다고 가정하자. 프로세스들이 생성된 시점부터 80ms가 지난 시점에서 각 큐에 남아 있는 프로세스들과 각 프로세스에게 남아 있는 실행 시간을 위 그림과 같이 도시하시오. (7점) - (2) 1)번 문제에서 47ms가 흐른 시점에 CPU 사용 시간 50ms를 갖는 프로세스 P5가 생성되었다고 가정하고, 80ms가 지난 시점에서 각 큐에 남아 있는 프로세스들과 각 프로세스에게 남아 있는 실행 시간을 위 그림과 같이 도시하시오. (7점)
- (3) CPU 스케줄링 알고리즘의 성능을 비교하기 위한 다양한 기준 중에서 처리량(Throughput), 총 처리시간(Turnaround time), 대기시간(Waiting time)의 개념에 대해 설명하시오. (6점)
제2문 (20점)
다음은 페이징 기반의 가상 메모리 시스템에서 변환색인버퍼(TLB, Translation Lookaside Buffer)를 사용하는 상황에 관한 설명이다. 다음 물음에 답하시오. (총 20점)
가상 주소를 표현하는데 32비트를 사용하며, 페이지 크기는 4KB이다. 한 프로세스가 실행 중이며, 이 프로세스의 페이지 테이블 전체가 메인 메모리에 상주하고 있다. 시스템은 TLB를 사용하고 있으며, 캐시는 사용하지 않는다고 가정한다. 찾는 페이지는 모두 메인메모리에 존재하고 있다.
○TLB 접근 시간:10ns
○메모리 접근 시간:100ns
○TLB hit ratio:95%
○페이지 테이블:2단계 구조(Two-level page table)
○2차(Secondary) 페이지 테이블의 엔트리 개수:1024
○TLB 접근 시간:10ns
○메모리 접근 시간:100ns
○TLB hit ratio:95%
○페이지 테이블:2단계 구조(Two-level page table)
○2차(Secondary) 페이지 테이블의 엔트리 개수:1024
- (1) 가상 주소는 최상위 페이지 테이블의 인덱스, 2차 페이지 테이블의 인덱스, 오프셋으로 구성된다. 각각을 표현하는데 필요한 비트를 구하시오. (6점)
- (2) 위 시스템에서 EMAT(Effective Memory Access Time)를 계산하시오. (7점)
- (3) TLB를 사용하지 않을 때의 EMAT를 계산하시오. (7점)
제3문 (20점)
시스템 상태가 다음과 같다고 가정할 때 교착상태와 관련된 은행가 알고리즘을 이용하여 다음 물음에 답하시오. (총 20점)
| ○P0부터 P4까지 5개의 프로세스가 실행 중이다. ○3개의 자원 A, B, C가 각각 9개, 6개, 7개 있다. ○현재 시스템 상태는 다음과 같다.
| ||||||||||||||||||||
| 프로세스 | 현재 할당량 | 최대 요구량 | ||||||||||||||||||
| ABC | ABC | |||||||||||||||||||
| P0 | 101 | 842 | ||||||||||||||||||
| P1 | 110 | 313 | ||||||||||||||||||
| P2 | 301 | 803 | ||||||||||||||||||
| P3 | 201 | 231 | ||||||||||||||||||
| P4 | 002 | 422 |
- (1) 위의 표를 보고 현재 안전(Safe) 상태인지 불안전(Unsafe) 상태인지 쓰고, 만일 안전 상태라면 모든 안전 시퀀스의 개수를 쓰고, 불안전 상태이면 자원 할당이 불가능한 시점까지의 시퀀스를 쓰시오. (8점)
- (2) 프로세스 P1이 A의 자원 1개와 C의 자원 2개를 더 요청한다고 가정하자. 이 요청을 허용할지 불허할지 결정하고, 만일 허용한다면 모든 안전 시퀀스의 개수를 쓰고, 불허한다면 자원 할당이 불가능한 시점까지의 시퀀스를 쓰시오. (8점)
- (3) 교착상태를 발생시킬 수 있는 네 가지 필요 조건들을 쓰고 각각에 대해서 설명하시오. (4점)
제4문 (20점)
0번～99번 트랙으로 구성된 디스크 장치에서 현재 디스크 헤드는 50번 트랙에 있고, 다음과 같은 디스크 입출력 요청들이 디스크 큐에 대기하고 있을 때, 다음 물음에 답하시오. (총 20점)
요청 트랙들:17 78 96 29 40 8 49 62 88 91
- (1) 이 요청 트랙들을 SSTF 알고리즘으로 스케줄링하였을 때 요청이 처리되는 순서를 표시하고 총 탐색 거리를 계산하시오. (4점)
- (2) 이 요청 트랙들을 LOOK 알고리즘으로 스케줄링하였을 때 요청이 처리되는 순서를 표시하고 총 탐색 거리를 계산하시오. (단, 헤드는 0번 트랙 방향으로 이동 중이었다) (4점)
- (3) 이 요청 트랙들을 C-SCAN 알고리즘으로 스케줄링하였을 때 요청이 처리되는 순서를 표시하고 총 탐색 거리를 계산하시오. (단, 헤드는 99번 트랙 방향으로 이동할 때 서비스를 수행하며, 헤드는 99번 트랙 방향으로 이동 중이었다) (4점)
- (4) 디스크 입출력 요청이 많은 대형 데이터베이스 시스템에서 자주 사용되는 SSTF 알고리즘에서 나타날 수 있는 문제점을 위의 요청 트랙들 경우를 적용하여 설명하시오. (4점)
- (5) 트랙 번호가 연속적으로 요청되지 않고, 특정 범위에 요청이 몰리는 비균등 요청 분포 환경이 존재한다고 가정한다. 예를 들어 대부분의 요청이 트랙 0번～20번 사이에 몰려 있고, 나머지는 드물게 발생한다. 이와 같은 상황에서 두 알고리즘 C-SCAN과 LOOK을 비교했을 때, 어떤 알고리즘이 응답 시간 편차(응답 시간의 불균형)를 줄이는 데 더 유리한지 쓰고, 그 이유는 무엇인지 설명하시오. (4점)
제5문 (20점)
Linux Ext2 파일 시스템의 디스크 레이아웃은 다음과 같이 부트 블록(Boot block)과 여러 블록 그룹(Block group)으로 구성되며, 각 블록 그룹은 수퍼 블록(Super block), 그룹 기술자(Group descriptors), 데이터 비트맵(Data bitmap), 아이노드 비트맵(Inode bitmap), 아이노드 테이블(Inode tables), 데이터 영역(Data blocks)으로 구성된다. 한 블록의 크기가 4KB라고 가정할 때, 다음 물음에 답하시오. (총 20점)
[그림]
[그림]
- (1) 하나의 블록 그룹에 생성 가능한 최대 파일 개수를 215개로 하기 위해, 아이노드 비트맵과 아이노드 테이블에 할당해야 하는 블록의 최소 개수를 각각 구하시오. (단, 아이노드의 크기는 128바이트이며 아이노드 테이블에 연속적으로 할당된다고 가정한다) (6점)
- (2) 하나의 아이노드에 데이터 블록 포인터가 15개 저장되고, 이들 중 direct pointer 12개, 그리고 single indirect pointer, double indirect pointer, triple indirect pointer가 각각 1개씩 있다고 가정할 때 이 시스템에 저장될 수 있는 파일의 최대 크기는 얼마인가? (단, 블록 포인터는 32비트로 표현된다고 가정하고, 수식으로 답할 수 있다) (7점)
- (3) 파일의 크기가 50,000바이트인 파일을 순차적으로 처음부터 끝까지 읽을 때, 접근해야 하는 디스크 블록의 최소 개수는 몇 개인가? (단, 해당 파일의 아이노드는 미리 메인메모리에 적재되어 있으며, 데이터 영역의 블록들은 메인메모리에 적재되어 있지 않다고 가정한다) (7점)끝