5급 공채 2차

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

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

제1문 (20점)

세그먼테이션(segmentation) 기반 메모리 관리 시스템에서 한 프로세스가 가질 수 있는 최대 세그먼트 개수는 8개이고, 한 세그먼트의 최대 길이는 64KB라고 하자. 이때, 논리 주소(logical address)는 <세그먼트 번호, 바이트 오프셋(offset)>으로 구성된다. 예를 들어, 논리 주소 <3, 400>은 세그먼트 3의 바이트 400을 의미한다. 프로세스 P의 세그먼트 테이블이 다음과 같을 때, 물음에 답하시오. (총 20점)
세그먼트 번호Base (시작주소)Limit (길이, bytes)
06300800
132001300
2700650
347001400
414001500
  1. (1) 한 프로세스가 가질 수 있는 논리 주소 공간의 최대 크기를 계산하시오. (2점)
  2. (2) 논리 주소를 표현하는 데 필요한 비트의 수를 계산하시오. (2점)
  3. (3) 프로세스 P의 다음 논리 주소에 대한 물리 주소(physical address)를 10진수로 표기하시오. (단, 오류가 있다면 세그먼트 오류라고 표기하고, 이유를 설명하시오) (12점)
    가)<2, 675>
    나)<4, 1350>
    다)100000010001000102－이진수로 표현된 논리주소 (비트 값이 0인 상위비트는 표시하지 않음)
  4. (4) 프로세스 P가 할당받은 물리 주소 5995 번지의 논리 주소를 <세그먼트 번호, 바이트 오프셋> 형식으로 기술하시오. (4점)

제2문 (20점)

다음 조건을 만족하는 파일 시스템에 대해 물음에 답하시오. (총 20점)
○스토리지 영역을 구성하는 기본 단위는 섹터이며, 섹터의 크기는 512바이트이다.
○파일 시스템, 즉, 스토리지 볼륨은 부트 코드를 저장하는 부트 세그먼트, 볼륨의 메타 데이터를 저장하는 볼륨 제어 블록(volume control block), 스토리지 공간 할당 정보를 저장하는 아이노드 비트맵(inode bitmap)과 데이터 비트맵(data bitmap), 아이노드들을 저장하는 아이노드 세그먼트, 데이터 블록들을 저장하는 데이터 세그먼트 등으로 구성된다.
○일반 파일 및 디렉터리 파일 등의 메타 데이터는 해당 아이노드에 저장되며, 아이노드의 크기는 64바이트로 모두 동일하다.
○스토리지에서 아이노드들은 아이노드 세그먼트에 연속적으로 할당된다. 첫 번째 아이노드의 아이노드 번호를 0으로 하며, 이후 순차적으로 1씩 증가한다.
○아이노드 세그먼트는 100번 섹터에서 시작하며, 총 1024개의 섹터를 차지한다.
○아이노드의 할당 정보는 아이노드 비트맵을 통해 관리되며, 아이노드 비트맵의 크기는 1KB이다.
○일반 파일 및 디렉터리 파일의 데이터가 저장되는 데이터 블록의 할당 정보는 데이터 비트맵을 통해 관리되며, 데이터 비트맵의 크기는 10KB이다.
○데이터 블록의 크기는 4KB이며, 블록 번호는 4바이트로 표시한다.
  1. (1) 위 조건을 만족하는 파일 시스템(스토리지 볼륨)에 생성 가능한 파일(일반 파일 및 디렉터리 파일 포함)의 최대 개수를 구하고, 그 계산과정을 보이시오. (7점)
  2. (2) 1025번 아이노드가 위치한 섹터 번호와 오프셋(섹터 시작부터 해당 아이노드 시작 위치까지의 바이트 거리)을 계산하시오. (4점)
  3. (3) 아이노드 내부에 해당 파일의 데이터 블록 위치를 추적하기 위한 블록 번호들의 배열(원소 수는 10개, 개별 원소의 크기는 4바이트)을 두는 색인 할당(indexed allocation) 기법을 사용한다고 할 때, 파일의 크기가 1GB인 대용량 파일을 지원하기 위한 간접 색인 수준(indirection level)의 최솟값을 단일 간접 색인(single indirection), 2중 간접 색인(double indirection), 3중 간접 색인(triple indirection), 4중 간접 색인(quadruple indirection) 등으로 답하고, 그 이유를 설명하시오. (9점)

제3문 (20점)

두 개의 프로세스에 대한 임계구역 문제를 소프트웨어적으로 해결하고자 한다. 다음 물음에 답하시오. (총 20점)
  1. (1) 임계구역(critical section) 문제를 소프트웨어적으로 해결하기 위하여 만족시켜야 하는 세 가지 조건을 나열하시오. (4점)
  2. (2) 첫 번째 시도로 다음과 같이 구현하였다. 이 코드는 두 프로세스 중 한 프로세스는 lock_1(0)으로, 다른 프로세스는 lock_1(1)로 호출하여 동시에 수행된다. 이것이 임계구역 문제를 해결하는지에 대해 설명하시오. (8점)
    // 초기값
    boolean b[2] = {false, false};
    int turn = 0;
    . . .

    void lock_1(int id) {
    do {
    while(turn != id) { /* 대기 */ }
    . . . // critical section
    turn = 1-id;
    . . . // remainder
    } while(true);
    }
  3. (3) 두 번째 시도로 다음과 같이 구현하였다. 두 프로세스가 각각 lock_2(0)과 lock_2(1)로 호출하여 동시에 수행된다고 했을 때, 이것이 임계구역 문제를 해결하는지에 대해 설명하시오. (8점)
    // 초기값
    boolean b[2] = {false, false};
    int turn = 0;
    . . .

    void lock_2(int id) {
    while(true) {
    b[id] = true;
    while(turn != id) {
    while(b[1-id]) { /* 대기 */ }
    turn = id;
    }
    . . . // critical section
    b[id] = false;
    . . . // remainder
    }
    }

제4문 (20점)

최단 마감 우선(Earliest Deadline First) 스케줄링과 비율 단조(Rate-Monotonic) 스케줄링을 사용하는 실시간 시스템에 주기를 갖는 N개의 태스크가 존재한다고 가정한다. 이 시스템의 각 태스크 \tau_{{i}}는 ( \mathrm{C}_{{i}} , \ \mathrm{T}_{{i}} )로 모델링된다고 가정하고, 다음 표에서와 같은 태스크들이 주어질 때, 물음에 답하시오. (단, \mathrm{C}_{{i}}는 \tau_{{i}}의 실행시간을 의미하고 \mathrm{T}_{{i}}는 \tau_{{i}}의 주기를 의미하며, 사용률은 소수점 이하 넷째 자리에서 반올림한다) (총 20점)
실행시간 (ms)주기 (ms)
태스크 11050
태스크 21590
태스크 3330
태스크 4636
태스크 520180
태스크 6345
태스크 7220
태스크 8460
  1. (1) 주어진 태스크들에 대해 최단 마감 우선 스케줄링이 가능한지 설명하시오. (6점)
  2. (2) 비율 단조 스케줄링에서 각 태스크를 우선순위가 높은 것부터 순서대로 표시하시오. (6점)
  3. (3) 다음 표는 비율 단조 스케줄링의 사용률 상한을 나타낸다.
    태스크 개수사용률 상한
    11
    20.828
    30.779
    40.756
    50.743
    60.734
    70.728
    80.724

    비율 단조 스케줄링 기법에서 모든 태스크들의 주기(데드라인) 내 수행을 보장하는 충분조건을 기술하고, 이를 만족하는 최대 태스크 집합을 구하시오. (8점)

제5문 (20점)

리눅스 시스템에서 backdoor 파일과 backdoor2 파일의 정보가 다음과 같다. 물음에 답하시오. (총 20점)
$ ls -l backdoor*
-rwsr-xr-x 1 root root 12003 April 3 22:00 backdoor
-rwxr-xr-x 1 root root 12010 April 5 12:30 backdoor2
  1. (1) 리눅스 시스템의 프로세스가 부여받는 RUID(Real User ID), EUID(Effective User ID), RGID(Real Group ID), EGID(Effective Group ID)에 대하여 설명하시오. (4점)
  2. (2) 리눅스 시스템에서 SetUID 비트를 사용하는 이유를 설명하시오. (4점)
  3. (3) 사용자 kim의 계정 정보와 그룹 정보가 아래와 같다. 사용자 kim이 backdoor와 backdoor2를 각각 실행했을 때, 해당 프로세스의 RUID, EUID, RGID, EGID 값을 모두 구하시오. (6점)
    /etc/passwd 파일의 사용자 계정 정보
    kim:x:1000:1000:kim:/home/kim:/bin/bash
    /etc/group 파일의 사용자 그룹 정보
    kim:x:1000:
  4. (4) backdoor와 backdoor2는 매개변수로 파일 이름을 받아 해당 파일의 내용을 화면에 출력하는 프로그램이며, /etc/shadow 파일의 정보는 다음과 같다.
    -rw-r----- 1 root root 1320 May 4 18:00 shadow

    일반 계정 kim으로 로그인한 사용자가 다음과 같은 명령을 각각 실행하였을 때, 실행 결과를 설명하시오. (단, 사용자 kim의 현재 디렉터리에 두 프로그램이 저장되어 있다고 가정한다) (6점)
    $ ./backdoor /etc/shadow
    $ ./backdoor2 /etc/shadow