[중간정리] 3주차 - 동시성, DFS, 다익스트라, B-tree, 추상화

단일 프로세서에서 여러 프로세스에 대한 동시성

사용자에게는 여러 프로그램이 동시에 실행되는 것처럼 보이지만, 실제로는 단일 프로세서가 작업을 매우 빠르게 전환하기 때문에 그렇게 보이는 것이다. 즉, 단일 프로세서에서의 동시성은 물리적으로 동시에 실행되는 것이 아니라, 운영체제가 각 작업을 짧은 시간 간격으로 번갈아 처리함으로써 동시에 실행되는 것처럼 보이게 하는 방식이다.

 

 

DFS를 스택에서 반복문으로 바꿔 구현하기

graph = { 
    'A': ['B', 'C'], 
    'B': ['D'], 
    'C': ['E'], 
    'D': [], 
    'E': [] 
  }

def dfs(graph, start_node):
    visit = []
    stack = []
    
    stack.append(start_node)
    while stack:
        now = stack.pop()
        
        if now not in visit:
            visit.append(now)
            # 실제 DFS 순서와 맞게 하기 위해 역순으로 삽입
            stack.extend(reversed(graph[now]))
    
    return visit

print(*dfs(graph, 'A'))     # 출력 A B D C E

 

 

다익스트라 알고리즘에서의 경로 추적

다익스트라 알고리즘은 특정 시작 노드로부터 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이다. 기본적으로는 각 노드까지의 최단 거리만 계산하지만, 경로 배열(path 배열)을 따로 유지하면 시작 노드에서 특정 노드로 가는 최단 경로 그 자체도 추적할 수 있다.

import heapq
INF = int(1e9)

start = 'D'
graph = {'A': [('B', 3), ('C', 2)],
         'B': [('A', 3), ('D', 4)],
         'C': [('A', 2), ('D', 1), ('F', 1)],
         'D': [('B', 4), ('C', 1), ('E', 5), ('G', 2)],
         'E': [('D', 5)],
         'F': [('C', 1), ('G', 3)],
         'G': [('D', 2), ('F', 3)]
         }
distance = {'A': INF, 'B': INF, 'C': INF, 'D': INF, 'E': INF, 'F': INF, 'G': INF}
path = {'A': [], 'B': [], 'C': [], 'D': [], 'E': [], 'F': [], 'G': []}

def dijkstra(start):
    distance[start] = 0
    
    q = []
    heapq.heappush(q, (0, start))
    while q:
        dist, now = heapq.heappop(q)
        
        if dist > distance[now]:
            continue
        
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
                path[i[0]] = [now]
            elif cost == distance[i[0]]:
                path[i[0]].append(now)

def path_tracking(end):
    if start == end:
        return [[start]]
    
    routes = []
    for prev in path[end]:
        for r in path_tracking(prev):
            routes.append(r + [end])
    
    return routes
    
dijkstra(start)
print("=== D → F 까지의 최단거리와 최단경로 ===")
print("최단거리:", distance['F'], ", 최단경로:", path_tracking('F'))
# 출력) 최단거리: 2 , 최단경로: [['D', 'C', 'F']]

 

 

데이터베이스에서 B-tree 인덱스 사용 여부에 따른 시간 복잡도 차이

B-tree 인덱스를 사용할 경우, 데이터 검색 시간 복잡도는 O(logN)이다. B-tree는 균형 이진 트리와 유사한 구조로 구성되어 있어, 데이터 양이 많아도 빠르고 효율적인 검색이 가능하다. 이로 인해 데이터베이스는 대용량의 레코드에서도 안정적인 성능을 유지할 수 있다.

 

반면, B-tree 인덱스를 사용하지 않을 경우에는 전체 데이터를 순차적으로 검색하는 선형 탐색(O(N))이 필요하다. 이 방식은 데이터 양이 많아질수록 성능 저하가 두드러지기 때문에, B-tree 인덱스를 사용하는 것이 훨씬 유리하다.

 

 

운영체제 관점의 4가지 추상화

운영체제는 하드웨어의 복잡성을 숨기고, 사용자가 쉽게 사용할 수 있도록 다양한 자원을 추상화(abstraction)한다. 그리고 이 추상화는 여러 계층으로 나눌 수 있다.

 

• 파일: 디스크와 입출력장치의 추상화
  • 하드디스크나 SSD 같은 저장장치는 물리적으로는 블록 단위로 데이터를 저장하지만, 운영체제는 이를 사용자에게 파일이라는 단위로 추상화하여 제공한다.
  • 이와 마찬가지로, 모든 입출력장치의 조작 또한 파일의 형태로 추상화하여 제공한다.
• 가상 메모리: 메인 메모리와 입출력장치의 추상화
  • 실제 메모리보다 큰 주소 공간을 사용할 수 있도록 하며, 필요에 따라 디스크(보조기억장치)를 활용한 페이징 등의 기법을 통해 프로세스마다 독립적인 주소 공간을 제공한다.
• 프로세스: 실행중인 프로그램(프로세서, 메모리, 입출력장치)의 추상화
  • 사용자 프로그램의 실행에 필요한 자원들을 통합적으로 관리하는 단위. 운영체제는 이를 하나의 실행 단위로 추상화하여 스케줄링, 메모리 할당 등을 처리한다.
• 가상머신: 컴퓨터 전체(운영체제, 프로세서, 메모리, 입출력장치)의 추상화
  • 실제 물리적 하드웨어 위에서 여러 개의 운영체제가 동시에 실행될 수 있도록 해주는 환경. 각 가상 머신은 독립된 컴퓨터처럼 동작한다.