이중 연결 성분(Biconnect Component)란? 이중 연결 성분이란, 무방향 그래프의 연결 성분에서 임의의 두 점 사이에 적어도 두 개의 단순 경로가 존재하는 연결 성분을 뜻한다. 이때, 연결 성분이란 그래프에서 서로 연결되어 있는 정점들을 말한다. 예를 들어, [1, 2, 3, 4, 5], [6, 7], [8, 9, 10]는 3개의 연결 성분으로 구성되었다고 볼 수 있다. 또한 단순 경로란, 경로 상의 정점이 모두 다른 경로를 말한다. 즉, 이중 연결 성분이란, 무방향 그래프의 연결되어 있는 정점 리스트인데, 이 리스트의 임의의 두 점 간의 경로 상에 있어서 정점이 중복되지 않는 경로가 두 개이상 존재하다는 것을 의미한다. 아래 예시와 함께 그 의미를 한 번 더 살펴보자. 위 그래프는 지금까지..
커널로의 진입이 필요한 시점은 3가지 존재한다. InterruptTrap (software interrupt)System Call 이 중에서 인터럽트가 어떻게 커널 코드로 들어가고 어떤 처리가 일어나는지 알아보자. 인터럽트란? 인터럽트란 비동기적 이벤트가 발생했다는 사실을 주변장치로 알리는 방법을 뜻한다. 여기서 비동기란 이벤트가 언제 일어날 지 알 수 없다는 뜻인데, 이는 우리가 키보드를 언제 두드릴지 모르는 것과 같다고 생각하자. 반대로 동기란 이벤트가 일어날 시간이 정해져 있다는 뜻이다. 인터럽트가 발생하면 가장 먼저 PIC(Programmable Interrupt Controller)에 신호가 도착한다. PIC 칩은 곧장 CPU로 신호를 전달하는 프로세스를 거친다. 이때 Clock 인터럽..
최소 신장 트리(Minimum Spanning Tree, MST)이란? 최소 신장 트리를 배우기 앞서, 신장 트리란 무엇인지 알아야 한다. 이는 연결 그래프의 부분 그래프로, 모든 정점과 간선의 부분집합으로 구성된다. 신장 트리의 중요한 특징 중 하나는 모든 노드가 적어도 하나의 간선과 정점에 연결되어야 하며, 사이클을 만들면 안된다. 최소 신장 트리를 이해하기 위해서는 이러한 신정트리의 개념을 정확히 파악하고 있어야 한다. 아래와 같은 그래프가 신장 트리의 예시 중 하나이다. 최소 신장 트리는 하나의 연결 성분으로 이루어진 무방향 가중치 그래프에서 간선의 가중치의 합이 최소인 신장트리를 말한다. 이러한 최소 신장 트리 알고리즘은 대표적으로 Kruskal, Prim, Sollin 알고리즘이 있다. 이는 ..
파일 시스템에서의 Data Blcok 파일에서는 Block이라고 하는 것을 저장단위로 사용한다.이 Block 하나의 크기는 4096바이트이다. 디스크에서 파일을 저장할 때, Block을 무작위로 저장하지는 않는다. 어떻게 배치하느냐에 따라 그 전략이 달라진다.우선, 지금은 잘 사용하지 않는 _Contiguous Allocation_에 대해 알아보자. Contiguous Allocation 이름을 보고 유추할 수 있듯이, _Contiguous Allocation_방식은 파일을 저장할 때 연속적으로 Block을 배치한다.이 방식을 사용하면 File Allocation Table을 사용하는데, 여기에 파일의 시작 Block과 Block의 길이를 저장한다. 물론 파일의 FCB에서도 파일의 시작 Block..
File Systems 파일 시스템이란 파일들을 담아놓는 자료구조이자, 자료들을 처리하는 알고리즘을 포함하는 Logical storage unit을 말한다. 이러한 파일 시스템은 다음과 같은 요소로 구성한다. Boot blockPartition control block(super block)Directory structure운영체제에 따라 있을 수도 있고, 없을 수도 있다.File control blocksData blocks실제 파일의 내용을 저장하는 곳이다. 논리적으로 디스크를 나누어 놓은 것을 파티션이라고 하는데, 각 파티션에는 위와 같이 Partition Control Block이 존재한다. 여기에는 boot block, super block, FCB list와 data blocks로 이..
