OS 🔑

• 메모리 관리_Demand paging, Page replacement algorithms(FCFS, LRU, LRU Approximation(NRU), LFU, MFU) Paging Paging은 logical memory를 physical memory로 mapping 하는 여러 방법 중 하나입니다. Logical memory를 같은 크기의 page로, physical memory를 page와 같은 크기의 frame으로 나눈 뒤 page를 특정 frame에 할당하여 이를 page table에 기록합니다. Page table의 크기는 매우 커서 main memory에 저장 해야 하는데, CPU가 명령을 수행할 때마다 메모리에 접근하기에는 overhead가 크므로 TLB(일종의 캐시)에 자주 참조될 것으로 예상되는 page에 대한 정보를 저장하여 사용합니다. (Paging에 대한 자세한 설명을 읽어보고 싶으신 분은 여기로) Demand Paging 그렇다면, 프로그램이 로드.. 2022.06.21
• 메모리 관리_Mapping(Contiguous allocation, Paging, Segmentation) 지난 포스팅에서는 logical memory를 physical memory에 할당하고 physical address를 확정하는 시점에 대해 다루었습니다. Compile time, Load time, Execution time 중에서 현재 사용되고 있는 방식은 Execution time 입니다. 프로세스의 코드 라인이 실행이 될 때 logical memory를 physical memory에 할당하고, 이를 참조할 때마다 MMU가 logical address를 physical address로 변환합니다. 그렇다면, logical memory를 physical memory에 어떻게 할당할 수 있을까요? 본 포스팅에서는 logical memory와 physical memory를 mapping 하는 방법에 대해 .. 2022.06.16
• 메모리 관리_Address binding(Compile time, Load time, Execution time) Symbolic Address / Logical Address / Physical Address 우리는 프로그램을 작성할 때, 변수명과 함수명을 통해 값에 접근합니다. 값에 접근하기 위해 사용되는 변수와 함수 이름을 Symbolic Address 라고 부릅니다. 이렇게 작성한 프로그램은 컴파일이 되면서 독자적인 공간을 가지게 됩니다. 이를 logical memory라고 하며, 가상의 공간이므로 virtual memory 라고도 불립니다. 일반적으로 logical memory는 0번지 부터 시작하여 상대적 주소로 표현되고, CPU는 logical address를 참조하여 명령을 내리게 됩니다. 프로그램과 데이터는 실제 메모리 주소에 올라가야 합니다. logical memory의 코드와 데이터들은 실제 메모.. 2022.06.16

Algorithm techniques 📈

• 최소신장트리(Minimal Spanning Tree)_크루스칼(Kruscal) 알고리즘 최소신장트리(MST)에 대한 이해 - 신장트리란, 뱡향성이 없는 그래프의 부분그래프(Subgraph)들 중에서, 모든 정점을 포함하는 트리이다. - 최소신장트리란, 신장트리들 중에서 간선의 합이 가장 작은 트리를 말한다. - 그래프에서 최소신장트리는 여러 개 있을 수 있다. 최소신장트리를 구하는 알고리즘으로는 크게 크루스칼(Kruscal) 알고리즘과 프림(Prim) 알고리즘이 있으며, 해당 글에서는 크루스칼 알고리즘의 방법을 다룬다. V(노드의 개수) = 6, E(간선의 개수) = 7 인 다음과 같은 그래프에서 최소신장트리의 간선 길이의 합을 구해보자. 간선들 중, 가장 길이가 짧은 간선을 선택하여 연결된 두 노드를 확인한다. 만약 두 노드가 다른 집합에 속해있다면 두 노드를 같은 집합에 포함시키고 해당.. 2022.03.04
• 유니온파인드(Union-Find) Union-Find 에 대한 이해 - 공통 원소가 없는, "상호 배타적"인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. - 원소들이 어떠한 집합에 포함되어있을 때, 특정 원소가 포함되어있는 집합을 찾는 Find 연산을 지원한다. - 두 원소들이 속한 집합이 다를 때, 두 집합을 하나의 집합으로 합치는 Union 연산을 지원한다. 트리 형태로 표현되어있는 원소들간의 서로소 집합을 살펴보자. 위의 그림에서 원소들의 상호 배타적 집합은 총 4개이다. 각 원소들은 하나의 집합에 포함되어있고, 같은 집합에 포함되어있는 원소들은 같은 루트 노드를 공유한다. 예를 들어, 노드 2번과 노드 4번은 같은 집합에 포함되어 하나의 트리로 연결되어있고 루트 노드 1번을 공유한다. 노드 6번과 노.. 2022.03.03
• 위상정렬(Topological sort) 위상정렬 - 위상정렬이란, 사이클이 없는 방향 그래프(DAG: Directed Acyclic Graph)에서 정점 사이의 선후 관계를 위배하지 않고 정렬하는 알고리즘이다. - 흔히 선수과목들의 수강 순서를 정하는 문제가 위상정렬에 비유된다. - 정해진 순서를 위배하지 않고 정렬하는 방법은 여러가지가 있을 수 있다. 위상정렬의 과정 N(노드의 개수) = 7, M(간선의 개수) = 7 인 다음과 같은 그래프에서 위상정렬을 수행해보자. 간선이 노드 x에서 노드 y로 흐를 때, 노드 x는 노드 y보다 앞에 위치되어야 한다. - 즉, 어떠한 노드가 해당 노드 쪽으로 들어오는 간선을 가지고 있다면 이 노드는 가장 앞에 올 수 없다. - 결과적으로, 현재 상태에서 가장 앞에 올 수 있는 노드들은 indegree(노드.. 2022.03.01