본문 바로가기

Life/Study

(54)

[운영체제] 페이징 기법(외부 단편화, 내부 단편화) 기초 개념/뜻 운영체제 주기억장치 관리 기법의 이해: 페이징(Paging) 기법 심층 분석 컴퓨터에서 프로그램이 실행되기 위해서는 반드시 주기억장치(Main Memory, RAM)에 적재되어야 한다. 과거 운영체제는 프로그램에 연속적인 메모리 공간을 통째로 할당하는 방식을 사용했는데, 이는 실행 시간이 지날수록 메모리 곳곳에 작은 빈 공간들이 생겨나 전체 메모리 공간이 사용 불가능해지는 치명적인 문제(외부 단편화)를 낳았다. 페이징 기법(Paging)은 이러한 메모리 단편화 문제를 해결하고, 나아가 주기억장치의 크기를 뛰어넘는 프로그램을 실행할 수 있게 하는 가상 기억장치(Virtual Memory)의 기반을 다지기 위해 등장한 획기적인 주기억장치 관리 기법이다.1. 페이징 기법의 기본 개념과 작동 원리페이징 기법은..

[자료구조] 힙 (Heap) 수많은 데이터를 처리할 때, 어떤 데이터는 "지금 당장, 가장 먼저" 처리되어야 하는 중요성을 가진다(마치 시스템의 CPU 스케줄러처럼). 이러한 우선순위(Priority) 개념을 자료 구조로 구현한 게 바로 우선순위 큐(Priority Queue)고, 이 큐를 가장 효율적으로 구현하는 자료 구조가 힙(Heap) 이다. 힙은 단순한 데이터 보관함이 아니라, 항상 가장 중요한 데이터를 맨 위에 배치하는 '정렬된 더미'의 역할을 한다. 힙(Heap)은 한글로 "더미" 또는 "쌓아놓은 것"을 의미한다. 실제로 힙의 동작 원리를 생각해보면, 마치 편의점의 유통기한이 임박한 상품을 가장 앞에 진열해놓은 진열대와 같다. 이렇게 항상 가장 우선순위가 높은 데이터(최댓값 또는 최솟값)를 먼저 처리하는 특성 때문에..

[자료구조] 스레드 트리(Threaded Tree) 기존의 이진 트리를 순회할 때는 방문하지 않고 지나쳐온 부모 노드들을 기억하기 위해 스택(Stack)이라는 별도의 저장소를 사용해야 했다. 하지만 스택을 관리하는 것은 메모리를 추가로 사용해야 하고, 코드가 복잡해지는 번거로움이 있다. 이러한 문제를 해결하기 위해 등장한 것이 스레드 트리(Threaded Binary Tree)다. 스레드 트리는 "다음에 어디로 가야 하는지"를 알려주는 일종의 네비게이션 표지판인 '스레드(Thread, 실)'를 트리 내부에 직접 심어놓은 구조다. 이를 통해 스택 없이도 물 흐르듯 자연스럽게 트리를 순회할 수 있다. 이 스레드 트리를 구현하는 방법은 크게 두 가지로 나뉘는데, 메모리 공간을 어떻게 활용하느냐에 따라 그 효율성이 달라진다. 첫 번째 방법은 '포인터 필드 ..

[자료구조] B Tree, B+, B* 트리 비교 & 차이점 기존의 이진 트리(Binary Tree)는 데이터가 많아질수록 키만 멀대같이 커지는 잭과 콩나무의 콩나무와 같아 불안정했다. 트리의 높이가 너무 높아지다 보니 데이터를 찾기 위해 하드디스크가 수없이 많은 층을 오르내려야 했고 과부하로 이어지게 됐다. 이에 대한 해결책으로 등장한 B 계열 트리는 더 효율적인 옆으로 뚱뚱하고 층수는 낮은 땅딸보 트리로 개종하게 된다. 마치 지진에 취약한 고층 아파트에서 한 층에 방이 많고 넓은 저층 고급 저택으로 이사를 한 것과 같다. 층수를 획기적으로 낮춰(Low Depth) 엘리베이터(I/O)를 타는 횟수까지 줄인 생존형 자료구조다. 가장 기본이 되는 B-트리는 모든 노드가 평등한 데이터 민주주의를 표방한다. 데이터가 꼭 바닥(leaf node)에만 있는 것이 아니라..

이전 1 2 3 4 ··· 14 다음

티스토리툴바