5급 공채 2차

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

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

제1문 (25점)

안전 필수 시스템(safety-critical system)의 실시간 스케줄링 및 우선순위 역전 방지에 대한 다음 물음에 답하시오. (총 25점)
  1. (1) 다음의 주기적 태스크 집합에 대해 스케줄링 알고리즘을 설명하고 RM(rate monotonic)과 EDF(earliest deadline first)의 스케줄링 가능성을 정량적으로 분석하시오. (15점)
    ○태스크 집합 (모든 태스크에 대해 주기와 마감시간은 동일하다)
    －T1: 주기 4ms, 실행시간 2ms
    －T2: 주기 5ms, 실행시간 2ms
    －T3: 주기 10ms, 실행시간 1ms
    ○모든 태스크는 t＝0ms에 동시 도착, 선점 가능, 문맥 교환(context switching) 비용은 0, 자원 공유 없음
    ※참고값: 2^{{\frac{{1}}{{3}}}} \approx 1.26

    ①RM 및 EDF 스케줄링의 우선순위 부여 방식과 동작 원리를 각각 설명하시오. (2점)
    ②총 이용률 U를 계산하시오. (2점)
    ③RM 스케줄링에서 최악의 경우 CPU 이용률 한계를 계산하고 ②에서 구한 U와 비교하여, RM 스케줄링 가능성에 대해 즉시 결론을 내릴 수 있는지 설명하시오. (3점)
    ④RM 스케줄을 t＝10ms까지 간트 차트(Gantt chart)로 나타내고, 모든 태스크가 첫 인스턴스의 마감시간 내에 완료되는지 판정하시오. (4점)
    ⑤EDF 스케줄을 t＝10ms까지 간트 차트로 나타내고, 스케줄링 가능성을 판정하시오. (단, 먼저 들어온 태스크를 우선 처리함) (4점)
  2. (2) 우선순위 역전 현상 메커니즘과 방지 프로토콜에 관한 다음 물음에 답하시오. (10점)
    ○시스템에 우선순위가 서로 다른 3가지 태스크 H, M, L이 존재(H가 가장 높고, M이 중간, L이 가장 낮음)
    ○자원 R은 임계구역 내에서 뮤텍스(mutex)로 보호되며, H와 L이 같은 자원 R을 사용
    ○M은 자원 R을 사용하지 않음

    ①위 시스템에서 우선순위 역전(priority inversion)이 발생하는 시나리오를 시간 순서에 따라 단계별로 기술하고, 그 결과로 인해 높은 우선순위인 H가 왜 지연되는지를 설명하시오. (5점)
    ②PIP(priority inheritance protocol)의 동작 원리를 설명하고, 이 프로토콜이 우선순위 역전을 어떻게 완화하는지 설명하시오. 또한 PIP가 해결하지 못하는 한계점을 1가지 제시하시오. (5점)

제2문 (20점)

임계구역 문제 해결을 위한 세마포(semaphore)의 wait() 연산과 signal() 연산이 다음과 같이 정의될 때, 물음에 답하시오. (총 20점)
wait(S) {
value--;
if(value < 0){
add this process to list;
block();
}
}
signal(S) {
value++;
if(value <= 0){
remove a process P from list;
wakeup(P);
}
}
  1. (1) 두 프로세스가 동시에 임계구역 내에 있을 때, 위의 정의된 세마포 연산과 관련하여 프로그래머의 실수에 기인한 동기화 오류 상황 3가지를 제시하고, 각각의 문제점을 설명하시오. (6점)
  2. (2) 1)에서 언급한 문제점들을 해결하기 위한 고수준 동기화 도구인 모니터(monitor)를 세마포와 비교하여 설명하시오. (8점)
  3. (3) 하나의 자원을 독점적으로 관리하는 모니터를 위한 아래 코드에서 (가), (나), (다)에 들어갈 명령문을 조건 변수(condition variable)의 wait()와 signal()을 사용하여 작성하시오. (6점)
    monitor resource_monitor
    {
    boolean busy;
    condition x;

    acquire(){ /* 자원 획득 */
    (가)

    }
    release(){ /* 자원 방출 */
    (나)

    }
    initialization(){ /* 초기화 */
    (다)

    }
    }
    (가)
    (나)
    (다)

제3문 (20점)

SSD에 관한 다음 물음에 답하시오. (총 20점)
  1. (1) SSD는 NAND 플래시 칩으로 이루어져 있다. TLC(tri-level cell)와 같은 NAND 플래시 칩의 한 셀에 정보를 읽고 쓰고 지우는 속도는 느리지만, 플래시 칩을 직렬 및 병렬로 연결하여 만들어진 SSD의 읽기와 쓰기 속도는 매우 빠르다. 이렇게 빠른 속도를 달성하기 위해 FTL(flash translation layer)이 사용된다. 성능 향상을 위해 FTL이 수행하는 핵심 기능 3가지와 그 역할을 설명하시오. (10점)
  2. (2) 블록 매핑을 사용하는 FTL의 플래시 칩 상태는 아래 그림과 같다고 가정한다. 이때 C를 C’으로 갱신하는 요청과 E를 새로 쓰는 요청이 순서대로 들어왔을 때, 각 요청 처리 후의 상태를 도식화하고 각각의 WAF(write amplification factor)를 아래 조건에 따라 계산하시오. (10점)
    [그림]
    <조 건>
    ○현재 C는 720번 청크의 802번 페이지에 매핑
    ○720번 청크는 플래시 블록 3802번에 저장
    ○하나의 페이지는 4KB
    ○상태 v는 유효(valid), i는 무효(invalid)를 의미
    ○플래시에 비어 있는 순서대로 새로운 플래시 블록이 할당
    ○버퍼와 캐시 효과는 무시

제4문 (20점)

다음과 같은 특성을 가지는 컴퓨터 시스템이 있다. 물음에 답하시오. (총 20점)
32비트 가상 주소를 사용하며, 페이지 크기는 4KB이다. 물리 메모리는 64MB이고, TLB(translation look-aside buffers)는 32개의 엔트리를 보유한다. 2단계 페이지 테이블 구조를 사용하며, 각 단계의 인덱스 비트 수는 동일하다. 캐시는 직접 사상(direct-mapped) 방식이며, 크기는 16KB, 블록 크기는 64B이다.
  1. (1) 가상 메모리 분할 방법인 페이징과 세그멘테이션에 대해, 단편화 관점에서 각각을 설명하시오. (4점)
  2. (2) 이 시스템의 2단계 페이지 테이블 구조를 분석하여, 가상 주소의 각 필드(L1 인덱스, L2 인덱스, 페이지 오프셋)의 비트 수를 구하시오. 또한 물리 주소의 비트 수와 물리 주소에서 페이지 프레임 번호(PFN)의 비트 수를 구하시오. (5점)
  3. (3) 이 시스템에서 물리 주소 기준으로 캐시의 인덱스(index) 비트 수와 태그(tag) 비트 수를 구하시오. 또한 가상 주소 0x00403A82에 접근할 때, TLB 히트 후 물리 주소가 0x00003A82로 변환되었다면 해당 물리 주소의 캐시 인덱스와 블록 오프셋을 각각 16진수로 나타내시오. (4점)
  4. (4) 메모리 시스템에서 시간에 따라 참조된 페이지의 순서가 아래와 같다.
    논리시각12345678910
    페이지ABCCBBAABA
    연산readreadreadwritereadreadreadreadreadread

    아래 조건에 따라 동작하는 워킹셋(working set) 알고리즘으로 논리시각 1부터 10까지의 메모리 참조를 처리하기 위해 스토리지에서 총 몇 번의 페이지 읽기 접근이 필요한지를 나타내고, 논리시각별 워킹셋을 보이시오. (7점)
    <조 건>
    ○윈도우 크기(window size)는 2로 가정
    ○최초의 메모리 상태는 비어있음
    ○각 시각의 메모리에는 워킹셋 알고리즘에 따라 해당 시점의 워킹셋에 포함된 페이지들만 존재

제5문 (15점)

다음 코드를 보고 물음에 답하시오. (총 15점)
int Gmin = 10;
int Gsum;

void* mem(int param) {
static int sia = 5;
int ib = 20;
char *ptr = malloc(sizeof(char) * 8);
Gsum = Gsum + param + sia + ib + Gmin;
return ptr;
}
  1. (1) 위 코드가 프로세스화 될 때, 저장 섹션(data, BSS(block started by symbol), stack, heap)별로 할당되는 변수 또는 요소를 나타내시오. (4점)
  2. (2) 저장 섹션 중 BSS가 사용되는 이유를 설명하시오. (3점)
  3. (3) 이 코드를 멀티스레드로 실행할 경우, 레이스 컨디션(race condition)이 발생할 여지가 있는 변수를 구하고, 스레드 간의 문맥 교환 관점에서 발생되는 문제점과 해결 방안을 설명하시오. (8점)
    끝