CS & 알고리즘 스터디: 세 번째 스터디
Mayday
많은 사람들이 스터디를 이탈하기 시작했다.
아무래도 스터디를 운영해본 적이 없는 나의 부족함 때문이 아닐까 싶다. 더 잘 이끌었으면, 혹은 더 메리트 있게 느껴졌다면 나가지 않았을 수도 있다는 생각이 들어 많은 아쉬움이 남는다. 그래도, 남은 사람들과 내가 생각했던 커리큘럼의 마지막까지 완주하는 것이 목표이다. 이를 토대로 다음에 스터디를 다시 운영하게 된다면 더욱 발전된 형태의 운영을 할 수 있지 않을까 싶으면서도, 정확히 어떤 부분에서 발전을 시킬 수 있을지는 아직은 감이 잘 잡히지 않는다.
세 번째 스터디
분량 부담에 대한 의견을 수렴하여 알고리즘 문제 수를 대폭 줄였다. 그렇지만, 그런 만큼 그 문제 해결의 밀도를 높히고 싶어 이번 주 부터는 알고리즘 분류를 공개하지 않고 접근하기로 했다. 물론 내가 선정한 문제들이기에, “당신은 아는 것 아닌가요?”라는 생각이 들 수도 있지만, 진짜 하나도 기억이 안났다.
역설적으로, 이번 주에는 지난 주보다 더 많은 문제들을 풀었다. 아무래도 하다 보니 내가 약하다고 느끼는 부분들이 명확해져서 이를 보완하고자 하는 마음이 컸던 것 같다.
스터디원의 제안에 따라 이번에는 면접 형태로 진행하도록 했다. 원래는 기존에 했던 코어타임과 같이 번갈아가면서 본인이 공부한 내용을 공유하고, 해당 주제에 대해 토의하며 부족한 부분에 살을 붙이는 방식으로 했는데, 정글이 끝난 현 상황에서 실전 면접과 비슷한 형태로 진행해보는 것도 꽤 좋은 방식이라고 생각했다.
키워드
이번 주부터는 본격적으로 컴퓨터 시스템과 운영체제 쪽으로 공부하게 되었다.
시스템 콜
Q: 시스템 콜이 운영체제에서 어떤 과정으로 실행되는지 설명해 주세요
A:
시스템 콜은 응용 프로그램이 운영체제의 서비스를 요청할 때 사용하는 인터페이스이다. 응용 프로그램은 사용자 모드에서 커널의 서비스를 필요로 할 때 필요한 기능에 대응하는 시스템 콜을 호출한다.
Q: 시스템 콜의 유형에 대해 설명해 주세요. A:
시스템 콜은 다음의 유형으로 분류된다:
- 프로세스 제어: fork, exit, wait, kill 등
- 파일 관리: open, read, write, close 등
- 장치 관리: read, write 등
- 정보 유지: alarm, sleep, gettimeofday 등
- 통신: socket, connect, bind, listen, accept 등
프로세스 제어부터 정보 유지까지는 PintOS과제 때 다뤘으며, 통신 부분은 Proxy-Lab에서 다루었다.
Q: 왜 유저모드와 커널모드를 구분해야 하나요?
A:
유저모드와 커널모드를 구분하는 이유는 시스템의 안정성과 보안을 보장하기 위함과 동시에 자원 관리를 효율적으로 하기 위해서이다. 유저 모드에서 응용 프로그램들은 직접적으로 하드웨어 또는 메모리에 접근을 하지 못하도록 되어있다. 이는 프로그램이 시스템을 실수로라도 손상시키는 것을 방지하며, 다른 프로그램에 데이터를 훼손하지 못하도록 한다. 추가적으로, 유저모드와 커널모드의 분리로 인하여 프로그램이 오류를 일으켜도 커널에 영향을 끼치지 않는다. 즉, 프로그램이 충돌하거나 비정상적으로 종료되어도 운영체제 전체의 안정성에는 영향이 없다. 자원 관리 측면에서, 운영체제는 유저 모드 프로그램의 요청에 따라 자원을 적절하게 할당 및 관리하여 효율성을 향상시킨다.
인터럽트
Q: 인터럽트는 어떻게 처리하나요?
A:
인터럽트의 처리 과정은 여러 단계를 거친다. 입출력 디바이스는 프로세서 칩의 핀에 시그널을 보냄으로 인터럽트를 발생시키고, 발생시킨 디바이스를 식별하는 예외번호는 시스템 버스에 보내지게 된다. 우선 현재의 작업에서 진행중인 인스트럭션의 실행을 완료한 후에, 인터럽트 핀이 high로 올라가있음이 확인되면 적절한 인터럽트 핸드러를 호출한다. 이 때 CPU는 현재 실행 중인 작업의 상태(프로그램 카운터, 레지스터 값 등)을 미리 저장해두어야 이후 원래 작업을 재개할 수 있다. CPU는 인터럽트 핸들러로 점프하여 해당 루틴을 실행한 후 기존에 진행하던 작업의 상태를 복원하여 재개한다.
출처: Computer Systems: A Programmer’s Perspective
Q: Polling 방식에 대해 설명해주세요.
A:
폴링은 운영체제 혹은 응용 프로그램이 특정 자원의 상태를 주기적으로 확인하는 기법이다. 보통 하드웨어 장치의 상태를 점검하기 위해 사용되며, 일정한 주기로 장치 또는 이벤트의 상태를 확인하여 필요한 작업을 수행한다.
폴링 방식을 사용하는 예시로는 다음이 있다:
- 키보드 입력 확인: CPU는 주기적으로 키보드 컨트롤러를 읽어 키 입력 여부를 확인한다
- 프린터 상태 확인: 프린터의 상태 레지스터를 주기적으로 확인하여 프린터가 준비되었는지 확인한다
폴링 방식의 장점:
- 단순하다: 구현이 간단하며, 인터럽트 처리 메커니즘 없이도 장치와 상호작용이 가능하다.
- 예측 가능하다: 주기적으로 상태를 확인하기 떄문에 장치의 상태 변화에 대한 예측이 가능하다.
폴링 방식의 단점:
- 비효율적이다: CPU가 주기적으로 확인을 하는 과정으로 인해 다른 작업을 수행할 시간이 낭비된다.
- 응답이 지연된다: 주기 사이에 이벤트가 발생하면 즉각적인 대응이 어려울 수 있기 때문에 인터럽트 방식에 비해 이벤트의 처리가 느릴 수 있다.
Q: 동시에 두 개 이상의 인터럽트가 발생하면 어떻게 처리해야 하나요?
A:
동시에 두 개 이상의 인터럽트가 발생하게 되는 경우에 대비하여 운영체제에는 다양한 메커니즘이 준비되어 있다. 대표적으로 인터럽트 우선순위 설정과 인터럽트 네스팅이 있다.
인터럽트 우선순위:
인터럽트 우선순위를 설정함으로 어떤 인터럽트가 먼저 처리될 지 결정할 수 있다. 이는 하드웨어적으로 또는 소프트웨어적으로 결정될 수 있으며, 각 인터럽트는 고유한 우선순위를 가지고 있다. 하드웨어 인터럽트 컨트롤러가 인터럽트를 관리하며, 우선순위에 따라 CPU로 전달되는 인터럽트의 순서가 결정된다.
인터럽트 네스팅:
인터럽트 처리 중 다른 인터럽트가 발생할 때 새 인터럽트를 허용하는 방식이다. 우선순위가 높은 새로운 인터럽트가 발생하면 현재 처리 중인 인터럽트를 중단하고 새로운 인터럽트를 처리한다. 이 높은 우선순위의 새 인터럽트의 처리가 완료되면 중단된 기존의 인터럽트를 재개한다. 이 방법은 중요한 인터럽트를 즉시 처리할 수 있다는 장점이 있다. 반대로, 네스팅을 허용하지 않으면 현재 인터럽트가 처리된 후에 새 인터럽트를 처리한다. 이는 간단하지만 중요 인터럽트의 처리를 지연시킬 수 있다는 단점이 있다.
프로세스
Q: 프로세스와 스레드의 차이에 대해 설명해 주세요.
A:
| 특성 | 프로세스 | 스레드 |
|---|---|---|
| 정의 | 실행 중인 프로그램 인스턴스 | 프로세스 내의 작은 실행 단위 |
| 주소 공간 | 독립적인 주소 공간 | 프로세스의 주소 공간을 공유 |
| 자원 소유 | 자체 자원 소유 | 프로세스의 자원을 공유 |
| 오버헤드 | 높은 오버헤드, 생성 및 전환 비용 높음 | 낮은 오버헤드, 생성 및 전환 비용 낮음 |
| 안정성 | 프로세스 간의 격리로 안정성 높음 | 프로세스 내의 오류 전파 가능 |
| 통신 | IPC를 통해 통신 | 프로세스 내에서 직접 메모리 접근 가능 |
프로세스는 독립적인 실행 환경을 제공하며, 서로간의 격리로 인해 안정성 높다. 다만, 이러한 특성 때문에 프로세스 간 전환 비용이 높으며 자원 소모 또한 크다. 반면, 스레드는 가벼운 실행 단위이며, 서로간의 통신이 빠르며 오버헤드가 낮다. 스레드를 사용할 때 주의해야 할 점은, 프로세스의 자원을 공유하기 때문에 동기화 문제나 오류 전파 가능성이 발생할 수 있다는 점이다.
높은 안정성이 요구될 땐 프로세스
병렬 처리가 필요한 환경에서는 스레드
Q: PCB가 무엇인가요?
A:
PCB는 Process Control Block, 즉 프로세스 제어 블록의 약자이다. PCB는 운영체제에서 각 프로세스에 대한 중요한 정보를 저장하는 데이터 구조이며, 여기에는 운영체제가 프로세스를 관리 및 제어하기 위해 필요한 정보를 포함한다.
프로세스 제어 블록의 주요 항목으로는 다음이 있다:
- 프로세스 번호 (Process Identification: PID): 프로세스의 구분 기준이 되는 식별자
- 프로세스 상태: 실행, 준비 등 프로세스의 현재 상태
- 프로그램 카운터 (Program Counter: PC): 프로세스 수행을 위해 다음에 실행할 명령의 주소의 목록
- 레지스터: CPU의 레지스터에 해당하는 정보
- 메모리 관리 정보: 가상주소와 실주소의 매핑 정보
- 프로세스 우선순위: 운영체제의 프로세스 스케줄링 정책
Q: 자식 프로세스가 상태를 알리지 않고 죽거나, 부모 프로세스가 먼저 죽게 되면 어떻게 처리하나요?
A:
자식 프로세스가 상태를 알리지 않고 죽는 경우를 ‘좀비 프로세스’, 부모 프로세스가 먼저 죽는 경우를 ‘고아 프로세스’ 라고 부른다.
- 좀비 프로세스 (Zombie Process):
- 자식 프로세스가 종료되었지만 부모 프로세스가 그 종료 상태를 수집하지 않은 상태
- 자식 프로세스는 종료되었지만, PCB는 남아있는 상태
- 부모 프로세스는 wait() 또는 waitpid() 시스템 콜을 사용하여 자식 프로세스의 종료 상태를 수집
- 부모 프로세스가 위의 시스템 콜들을 호출하지 않는 경우 좀비 프로세스가 남아 시스템 자원을 낭비
- 고아 프로세스 (Orphan Process):
- 부모 프로세스가 종료된 후에도 계속 실행 중인 자식 프로세스
- 고아 프로세스 발생 시 init 프로세스(PID 1)가 고아 프로세스가 됨
- 주기적으로 자식 프로세스의 종료 상태를 수집하여 좀비 프로세스가 되지 않도록 함
Q: 프로세스 주소공간에 대해 설명해 주세요.
A:
- 코드(code) 영역: 작성한 코드가 적재되는 공간으로, 0과 1로 변환된 기계어가 저장된다.
- 데이터(data) 영역: 작성한 코드에서 선언된 전역변수, 정적변수, 상수 등이 저장되며, 프로세스 시작 시 초기화된다.
- 스택(stack): 지역변수, 매개변수, return 주소들이 저장된다.
- 힙(heap): 동적으로 생성되는 데이터 구조나 객체들이 저장된다. 동적으로 할당되는 메모리로, 실행 중 동적으로 확장될 수 있다.
Q: 스택과 힙 공간에 대해, 접근속도가 더 빠른 공간은 어디일까요?
A:
스택은 CPU 레지스터와 밀접한 관계를 가지며 이로 인해 매우 빠른 접근이 가능한 반면, 힙은 포인터를 통해 접근해야 하는 관계로 스택에 비해 접근 속도가 느리다.
Q: 프로세스 주소공간에서 스택과 힙영역의 크기는 언제 결정되나요? 프로그램 개발자가 아닌, 사용자가 이 공간의 크기를 수정할 수 있나요?
A:
스택의 초기 크기는 프로그램을 컴파일할 때 또는 링킹할 때 결정된다. 힙은 동적 할당에 따라 그 크기가 변경되기 때문에 초기 설정 떄 정확한 크기가 결정되지 않는다. 두 가지 모두 사용자가 직접 수정할 수는 없다.
컨텍스트 스위칭
Q: 프로세스와 스레드는 컨텍스트 스위칭이 발생했을 때 어떤 차이가 있을까요?
A:
프로세스간의 컨텍스트 스위칭은 메모리 공간 또한 함께 전환된다. 각 프로세스는 독립적인 주소 공간을 가지기 때문에, 컨텍스트 스위칭 시 현재 실행 중인 프로세스의 주소 공간에서 다음으로 실행될 프로세스의 주소 공간으로 전환된다. 이 과정에서 페이지 테이블이 변경되며, 가상 메모리 매핑이 재설정된다. 여기에 더해, 자원 공유가 복잡하며 오버헤드가 크기 떄문에 시스템 자원 소비가 큰 편이고 시간이 오래 걸린다.
한 프로세스 내의 스레드는 서로 주소 공간을 공유하며, 자원 또한 공유하기 때문에 간단하고 효율적이다. 단순히 스택 및 레지스터의 상태만 변경해주면 되기 때문에 지연 시간이 거의 없다.
Q: 컨텍스트 스위칭은 언제 일어날까요?
A:
컨텍스트 스위칭은 다음의 경우에 발생한다:
- 인터럽트 발생
- 시스템 콜
- 멀티태스킹
- 프로세스 상태 변화
- 스케줄링 결정
문제 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import sys
input = sys.stdin.readline
N = int(input())
dp = list([0] * 10 for _ in range(N + 1))
dp[1] = [1] * 10
for k in range(N + 1):
dp[k][0] = 1
for i in range(2, N + 1):
for j in range(10):
dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
print(sum(dp[N]) % 10007)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import sys
import heapq
INF = float("inf")
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
cows = [INF]* (N+1)
for i in range(M):
a, b, c = map(int, input().split())
graph[a].append((b, c))
graph[b].append((a, c))
def dijkstra(start):
q = []
cows[start] = 0
heapq.heappush(q, (0, start))
while q:
cow, cur = heapq.heappop(q)
if cows[cur] < cow:
continue
for next in graph[cur]:
cost = cow + next[1]
if cost < cows[next[0]]:
cows[next[0]] = cost
heapq.heappush(q, (cost, next[0]))
return cows[N]
print(dijkstra(1))"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import sys
input = sys.stdin.readline
p, m = map(int, input().split())
rooms = []
for _ in range(p):
l, n = map(str, input().split())
l = int(l)
made = False
if not rooms:
rooms.append([(l, n)])
else:
for j in range(len(rooms)):
level, nickname = rooms[j][0]
if l-10 <= level and l + 10 >= level and len(rooms[j]) < m:
rooms[j].append((l, n))
made = True
break
if not made:
rooms.append([(l,n)])
for k in range(len(rooms)):
if len(rooms[k]) == m:
print("Started!")
else:
print("Waiting!")
players = sorted(rooms[k], key=lambda x: x[1])
for player in players:
print(*player)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
list = []
for _ in range(N):
list.append(int(input().rstrip()))
left = max(list)
right = sum(list)
while left <= right:
mid = (left + right) // 2
cur = mid
count = 1
for i in range(N):
if cur < list[i]:
cur = mid
count += 1
cur -= list[i]
if count > M or mid < max(list):
left = mid + 1
else:
right = mid-1
K = mid
print(K)
회고
정말 어려웠다. 정글 과정을 거치면서 분명히 한 번 쯤은 접해본 내용이 대다수였지만, 사람의 단기 기억력은 휘발적이라는 걸 새삼 느꼈다.