5급 공채 2차

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

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

제1문 (20점)

메모리 용량이 256MB인 컴퓨터 시스템에 다음과 같은 세 개의 작업(job)이 동시에 제출되었고, 작업 우선순위는 작업1>작업2>작업3이다. 작업 실행시간은 각 작업의 CPU 사용시간과 입출력시간의 합을 말한다. 문맥교환(context switching) 시간은 무시한다. 단일 프로그래밍(uni-programming)과 다중 프로그래밍(multi-programming) 방식에 대한 다음 물음에 답하시오. (단, 계산 최종값은 소수점 둘째자리에서 반올림한다) (총 20점)
작업1작업2작업3
실행시간5분10분15분
CPU 사용률70%20%10%
메모리 요구량30MB120MB80MB
디스크 사용률0%100%0%
터미널 사용률0%0%20%
테이프 사용률100%0%0%
  1. (1) 단일 프로그래밍과 다중 프로그래밍에 대해, 최종 완료시간(세 개의 작업이 모두 종료되는 데까지 걸린 시간)과 처리량을 각각 계산하시오. (8점)
    단일 프로그래밍다중 프로그래밍
    최종 완료시간(분)
    처리량(작업수/분)
  2. (2) 단일 프로그래밍과 다중 프로그래밍에 대해, 최종 완료시간까지의 평균 CPU 사용률을 계산하시오. (6점)
    단일 프로그래밍다중 프로그래밍
    평균 CPU 사용률(%)
  3. (3) 작업의 처리시간(turnaround time)은 그 작업이 제출된 시점부터 종료될 때까지 걸린 시간이다. 단일 프로그래밍과 다중 프로그래밍에 대해 평균 처리시간을 계산하시오. (6점)
    단일 프로그래밍다중 프로그래밍
    평균 처리시간(분)

제2문 (30점)

공유자원에 접근하는 코드를 임계구역(critical section)으로 정해 임계구역 내부의 연산을 원자적으로 처리하는 것을 동기화 문제라 한다. 단일 프로세서 환경에서 다음 물음에 답하시오. (총 30점)
  1. (1) 동기화 문제의 해결안은 상호배제, 진행, 한계대기의 3가지 조건을 충족해야 한다. 이 3가지 조건을 설명하시오. (5점)
  2. (2) 다음은 스레드1과 스레드2 간의 동기화 문제를 해결하기 위한 피터슨 알고리즘이다. 두 스레드는 변수 turn, flag1, flag2를 공유한다. 임계구역 내에서는 대기상태로 전환되거나 종료되지 않는다고 가정한다. 먼저 스레드2가 L5와 L6 문장까지 실행하고, 문맥교환이 일어나서 스레드1이 L1, L2 그리고 L3 문장을 실행하였다. 이 상황에서 진행 조건과 한계대기 조건이 어떻게 해결되는지 설명하시오. (10점)
    스레드1스레드2
    repeat
    L1 : flag1 = TRUE:
    L2 : turn = SECOND:
    L3 : while (flag2 == TRUE && turn == SECOND) :
    임계구역

    L4 : flag1 = FALSE:
    until FALSE:    		repeat
    L5 : flag2 = TRUE:
    L6 : turn = FIRST:
    L7 : while (flag1 == TRUE && turn == FIRST) :
    임계구역

    L8 : flag2 = FALSE:
    until FALSE:
    임계구역
    임계구역
  3. (3) 다음 각 방법이 동기화 문제를 어떻게 해결하는지와 어떤 단점을 가지고 있는지 설명하시오. (15점)
    가) 모든 인터럽트를 잠근다.
    나) 선점(preemption)을 금지한다.
    다) 스핀락(spinlock)을 사용한다.

제3문 (25점)

디스크를 병렬로 연결한 시스템을 RAID(Redundant Array of Independent Disks)라고 한다. 다음 물음에 답하시오. (총 25점)
  1. (1) 다양한 종류의 RAID가 있는데, 이중 RAID 0, RAID 4, RAID 5, RAID 6을 ①스트라이핑(비트 수준 또는 블록 수준), ②패리티(parity), ③디스크 고장 복구, ④에러 복구 코드(error correction code) 등의 용어를 활용하여 비교 설명하시오. (8점)
  2. (2) 디스크의 신뢰성은 MTTF(mean time to failure)로 표현된다. 1개의 디스크의 MTTF를 100,000시간(hour)이라고 가정한다. MTTR(mean time to repair)은 디스크 고장 시부터 복구 시까지의 시간을 의미하며, 10시간(hour)이 걸린다고 가정한다.
    가)100개의 디스크로 구성된 RAID의 MTTF를 계산하시오. (2점)
    나)RAID 1은 디스크 미러링을 사용하여 각각의 디스크의 복제본을 두고 관리한다. RAID 1에서 데이터 분실까지의 평균 시간(mean time to data loss, MTDL)을 MTTF와 MTTR을 이용하여 계산하시오. (5점)
  3. (3) RAID 4 또는 RAID 5로 구성된 가상 하드디스크에서 데이터 블럭 D에 대한 수정 시, 쓰기 연산의 추가비용이 발생한다. 이전 데이터 블럭을 D, 새로운 데이터 블록을 D', 이전 패리티 블록을 P, 새로운 패리티 블록을 P'이라고 하자.
    가)XOR 연산자의 성질을 이용하여 새로운 패리티 블록 P'을 재계산하는 방법에 대하여 설명하시오. (5점)
    나)D에 대한 수정 작업의 진행과정을 단계별로 설명하시오. (5점)

제4문 (25점)

요구 페이징(demand paging)을 하는 컴퓨터 시스템에서 발생할 수 있는 현상으로 쓰레싱(thrashing)이 있다. 쓰레싱이 발생하면 CPU의 이용률이 급격하게 떨어지는데, 다중 프로그래밍의 정도(degree of multi-programming)를 유지하면서도 쓰레싱을 방지하기 위하여 제시된 모델로 작업 집합(working set) 모델이 있다. 작업 집합 모델에서 작업 집합 창(working set window)의 크기를 \Delta라고 했을 때, k번째 참조 후의 평균 작업 집합 크기를 S_{k} ( \Delta ) = \frac{1}{k} \sum_{t} = 1^{k} | W ( t , \Delta ) |로 정의한다. 이때 W ( t , \Delta )는 시간 t에서의 작업 집합을 나타내며, | W ( t , \Delta ) |는 이 작업 집합의 크기를 의미한다. 또한, k번째 참조 후의 평균 페이지 부재율을 m_{k} ( \Delta ) = \frac{1}{k} \sum_{t} = 1^{k} F ( t , \Delta )라고 정의한다. 이때 F ( t , \Delta )는 시간 t에 페이지 부재가 발생하면 1, 그렇지 않으면 0이다. 프로세스의 페이지 참조 순서가 아래와 같다고 할 때 다음 물음에 답하시오. (단, 계산 최종값은 소수점 세째자리에서 반올림한다) (총 25점)
t123456789101112131415161718192021222324
참조
페이지
번호		145283478487754748132341
  1. (1) \Delta = 4일 때 시간 경과에 따라 W ( t , \Delta )가 어떻게 변화하는지를 다음과 같은 표의 형태로 구하시오. (5점)
    t123456789101112131415161718192021222324
    W ( t , \Delta )
  2. (2) S_{24} ( 4 )와 를 구하고, S_{24} ( 5 )에 따른 평균 작업 집합 크기의 경향을 예상하시오. (5점)
  3. (3) \Delta와 m_{24} ( 4 )를 구하고, m_{24} ( 5 )에 따른 평균 페이지 부재율의 경향을 예상하시오. (5점)
  4. (4) \Delta의 최솟값과 이를 만족하는 최소의 m_{24} ( \Delta )값을 구하시오. (5점)
  5. (5) 페이지 부재율을 최소화할 수 있는 작업 집합 크기의 최댓값을 구하시오. (5점)