단원 모의 문제

④ — 셸은 사용자가 친 명령을 해석해 전하는 명령어 해석기이고, sh·bash·csh·ksh처럼 여럿 가운데 사용자마다 골라 씁니다. 시스템에 하나뿐인 것은 커널입니다.

• ① 맞습니다. 대부분 C로 작성되어 다른 기계로 옮기기 좋은, 이식성이 높은 운영체제입니다.
• ② 맞습니다. UNIX는 다중 사용자·다중 작업을 지원합니다.
• ③ 맞습니다. 커널은 켜질 때 메모리에 올라와 꺼질 때까지 머물며 자원을 관리합니다.

다시 볼 레슨: 운영체제의 역할과 종류

④ — 한 프로세스 안의 스레드는 그 프로세스의 코드·데이터·열린 파일을 함께 씁니다. 실행 흐름은 저마다 따로라, 흐름을 따라가는 PC·레지스터·스택은 스레드마다 둡니다.

• ① 스레드를 프로세스 여럿처럼 봤습니다. 코드·데이터까지 따로 두는 것은 프로세스 여럿이고, 스레드는 이것을 함께 써서 만들고 바꾸는 부담이 작습니다.
• ② 둘을 뒤바꿨습니다. 코드·데이터를 함께 쓰고, 스택을 스레드마다 둡니다.
• ③ 스택까지 함께 쓴다고 봤습니다. 두 스레드는 서로 다른 함수를 부르며 따로 돌므로, 돌아갈 자리를 쌓는 스택은 저마다 있어야 합니다.

다시 볼 레슨: 프로세스와 스레드

② — 시각 0에는 W뿐이라 W(0~6)가 돌고, 비선점이라 끝날 때까지 쥡니다. 시각 6에 X(4)·Y(1)·Z(2)가 기다려 가장 짧은 Y(6~7), 다음 Z(7~9), 마지막 X(9~13) 차례입니다.

(6 + 4 + 4 + 12) ÷ 4 = 6.5입니다.

• ① 평균 대기 시간을 셌습니다. 반환 시간은 끝난 시각 − 도착 시각이고, 대기 시간은 거기서 실행 시간을 한 번 더 뺀 값입니다.
• ③ HRN으로 셌습니다. 시각 7에 기다린 시간까지 넣어 견주면 X가 Z보다 앞서지만, SJF는 실행 시간만 봅니다.
• ④ FCFS로 셌습니다. 도착순(W X Y Z)이 아니라 실행 시간이 짧은 순으로 고릅니다.

다시 볼 레슨: CPU 스케줄링: 비선점

③ — SJF는 CPU가 빌 때마다 그 순간 기다리는 프로세스 가운데 가장 짧은 것을 고르고, 고른 것을 끝날 때까지 무르지 않습니다. 단계마다 그 자리에서 가장 좋아 보이는 것을 고르고 다시 무르지 않는 것이 탐욕 알고리즘입니다.

• ① 나눠 풀고 합친다고 봤습니다. SJF는 프로세스 묶음을 나누지 않고, 빌 때마다 하나씩 고릅니다.
• ② 앞에서 구한 답을 표에 적어 다시 쓴다고 봤습니다. SJF는 지난 선택을 적어 두었다가 꺼내 쓰지 않습니다.
• ④ 막히면 되돌아가 다른 것을 고른다고 봤습니다. 비선점 SJF는 한번 준 CPU를 거두지 않아, 고른 것을 무르지 않습니다.

다시 볼 레슨: 알고리즘 설계 기법 · CPU 스케줄링: 비선점

① — 할당량이 어느 실행 시간보다도 크면 아무도 잘리지 않아, 줄에 선 차례(도착순)로 끝까지 도는 FCFS와 같아집니다. 아주 작으면 CPU를 넘기는 문맥 교환이 잦아지고, 그동안 CPU는 쓸모 있는 일을 하지 못합니다.

• ② (나)를 잘못 봤습니다. 할당량이 작아도 모두가 돌아가며 차례를 받으므로 끝없이 밀리는 프로세스는 없습니다.
• ③ (가)를 잘못 봤습니다. 잘리지 않으면 줄에 선 차례대로 돌 뿐, 실행 시간이 짧은 순으로 다시 고르지 않습니다.
• ④ 둘 다 잘못 봤습니다. 크면 도착순으로 끝까지 돌고, 작으면 문맥 교환이 잦아집니다.

다시 볼 레슨: CPU 스케줄링: 선점 · 프로세스와 스레드

① — 칸 하나를 늘 비워 두므로 여섯 칸에 다섯까지 섭니다. 넣을 때 rear를 (rear + 1) % 6으로 옮기므로, 5번 다음은 0번 칸입니다.

• ② (나)에서 % 6을 빼먹었습니다. 칸 번호는 0~5뿐이라 6번 칸은 없고, 끝 칸 다음은 첫 칸입니다.
• ③ (가)에서 칸 수를 그대로 셌습니다. 여섯 칸을 다 채우면 rear가 front와 같아져 빈 줄과 구별되지 않아, 하나를 비워 둡니다.
• ④ 두 가지를 다 놓쳤습니다. 다섯까지 서고, 5번 다음은 0번입니다.

다시 볼 레슨: 스택과 큐 · CPU 스케줄링: 선점

③ — 네 조건은 상호 배제·점유와 대기·비선점·환형 대기입니다. 조건은 쥔 자원을 남이 빼앗을 수 없다는 비선점이고, 빼앗을 수 있다면 기다리던 쪽이 자원을 가져가 기다림의 원이 풀립니다.

• ① 맞습니다. 자원 하나를 한 번에 한 프로세스만 쓰는 조건입니다.
• ② 맞습니다. 자원을 쥔 채 다른 자원을 기다리는 조건입니다.
• ④ 맞습니다. 기다림이 원을 이루는 조건입니다.

다시 볼 레슨: 교착 상태

② — 나눠 준 것이 4 + 2 + 1 + 3 = 10개라 남은 것은 1개이고, 더 필요한 것(최대 요구 − 가진 것)은 P1 5 · P2 1 · P3 7 · P4 3입니다. 끝낼 수 있는 프로세스를 찾고, 끝나면 가졌던 것을 돌려받는다고 셈합니다.

• ① 최대 요구가 작은 차례로 줄 세웠습니다. P2·P4가 끝난 뒤 남은 6개로는 7개가 더 필요한 P3을 끝낼 수 없습니다. 6개로 끝낼 수 있는 것은 5개가 더 필요한 P1입니다.
• ③ 가진 것을 더 필요한 것으로 읽었습니다. P3은 1개를 가졌을 뿐 더 필요한 것은 8 − 1 = 7개라, 남은 1개로는 첫 차례부터 막힙니다.
• ④ 최대 요구를 남은 것과 견줬거나, 끝난 프로세스의 자원을 돌려받지 않았습니다. 견주는 것은 더 필요한 것이고, 끝난 프로세스가 가졌던 자원은 남은 것에 더합니다.

다시 볼 레슨: 교착 상태

받는 답: 2.25

SRT는 프로세스가 도착하거나 끝날 때마다 남은 시간을 견주어, 가장 짧은 것에 CPU를 줍니다.

끝난 시각은 Y 4 · X 6 · Z 8 · W 13입니다. 대기 시간은 반환 시간 − 실행 시간으로 W 13 − 6 = 7, X 5 − 4 = 1, Y 1 − 1 = 0, Z 3 − 2 = 1이고, (7 + 1 + 0 + 1) ÷ 4 = 2.25입니다.

• 틀리는 꼴 2.50: 시각 5에 Z가 X를 빼앗는다고 봤습니다. X의 처음 실행 시간 4와 견주면 그렇게 보이지만, 견주는 것은 남은 시간 1입니다.
• 틀리는 꼴 3.25: 빼앗지 않는 SJF로 셌습니다. SRT는 새 프로세스가 올 때마다 돌던 것의 남은 시간과 견줍니다.
• 틀리는 꼴 5.50: 평균 반환 시간을 셌습니다. 대기 시간은 반환 시간에서 실행 시간을 뺍니다.

다시 볼 레슨: CPU 스케줄링: 선점

받는 답: (가) PCB · (나) MLFQ

(가)의 실마리는 '프로그램마다 하나씩, 번호·상태·다음 명령 자리를 담는 기록', (나)는 '줄을 여럿 두고, 할당량을 다 쓰면 아랫줄로, 오래 기다리면 윗줄로 옮긴다'입니다.

• 같은 이름의 다른 꼴: (가) Process Control Block · 프로세스 제어 블록, (나) Multi-Level Feedback Queue · 다단계 피드백 큐 — 원어와 한글 이름입니다. 문제가 영문 약어로 물었습니다.
• 틀리는 꼴 문맥 교환 — (가)에: CPU를 넘길 때 (가)에 적고 꺼내는 일의 이름입니다. (가)는 그 기록 자체입니다.
• 틀리는 꼴 MLQ — (나)에: 다단계 큐는 처음 정한 줄에 머물러 줄 사이를 옮기지 않습니다. (나)는 아래로 내리고 위로 올립니다.
• 틀리는 꼴 RR — (나)에: 라운드 로빈은 줄 하나에서 할당량만큼 돌리고 맨 뒤로 보냅니다. 줄을 여럿 두지 않습니다.

다시 볼 레슨: 프로세스와 스레드 · CPU 스케줄링: 선점

받는 답: 깊이 우선 탐색

실마리는 '한 갈래를 막힐 때까지 들어가고, 막히면 물러난다'와 '스택'입니다.

• 같은 이름의 다른 꼴: DFS(영문 약어) · Depth First Search(원어) — 문제가 한글로 물었습니다.
• 틀리는 꼴 너비 우선 탐색: 출발 정점의 이웃을 모두 먼저 방문한 뒤 그 이웃의 이웃으로 넓혀 가며, 큐를 씁니다. 한 갈래를 끝까지 들어가지 않습니다.

다시 볼 레슨: 그래프와 탐색 · 교착 상태