운영체제를 공부하기 위해 운영체제 아주 쉬운 세 가지 이야기 라는 책을 읽고 공부한 내용을 정리합니다.
잘못되거나 부족한 부분이 있으면 언제든 댓글로 가르침 부탁드립니다.
이전 포스팅에서 얘기했드시, 한 프로세스에 하나의 베이스와 바운드만 있다면, 사용하지 않는 힙과 스택 공간이 낭비되기 쉽다. 이를 세그멘테이션이라는 아이디어로 해결할 수 있다.
주소 공간의 논리적인 세그멘트(보통 코드, 스택, 힙 세 파트로 나뉨)마다 베이스와 바운드 쌍을 두고 각기 다른 물리 저장소 위치에 저장하여 내부 단편화를 막는 것이다.
하드웨어는 세그멘트 단위로 메모리를 저장하기 위해서 세그멘트 레지스터를 사용한다. 일반적으로 코드, 스택, 힙 3가지로 나눌 때 2개의 비트를 사용해야 세그멘트를 구분할 수 있다. 그리고 나머지 비트는 오프셋(주소가 참조하는 바이트가 이 세그멘트를 시작으로 몇 번째 바이트인지 나타냄)을 나타낸다.
새로운 프로세스가 실행되면, 빠르게 비어있는 물리 메모리 영역을 채우게 된다. 하지만 이때 물리 메모리 공간보다 작은 세그멘트들이 채워지면서 그 사이 사이에 낭비되는 빈공간들이 생겨난다. 이때 외부 단편화 문제가 발생한다. 할당된 영역 외부의 빈 공간들은 다양한 크기의 작은 조각으로 분할되어 단편화된다. 따라서 빈 공간 전체 크기 합계가 충분하더라도 하나의 연속된 영역이 존재하지 않으면 메모리 할당 요청이 실패되는 문제를 뜻한다. 이를 해결하는 방법으로는
1.3에서 언급한 외부 단편화를 해결하는 방법 중 하나는 기존 세그멘트를 복사해 한 쪽으로 압축시키는 것이다. 이를 가장 쉽게 하는 방법이 빈공간 관리이다. 빈 공간 리스트를 관리하는 알고리즘을 사용해 가장 효율적으로 외부 단편화를 줄이는 것이다.
분할과 병합은 빈공간을 관리하는 자료구조가 있다는 가정하에 진행된다. 규칙은 간단하다.
최적적합
빈공간리스트를 1회 전체 검색해서 요청한 크기가 충족되는 빈 청크 중 가장 작은 청크를 리턴한다.
최악적합
가장 큰 청크를 찾아 요청에 응답한다. 청크를 여전히 크게 남겨두는 것이 목적이다.
최소적합
요청보다 큰 청크를 찾자마자 리턴한다. 가장 빠르지만 메모리상 비효율적이다.
다음적합
마지막으로 할당한 메모리를 기억하여 리스트의 첫부분에 단편이 집중되는 것을 방지한다. 이 또한 빠르다.
버디 할당 (ex : 이진 버디 할당)
요청을 충족 시키기에 충분한 공간이 발견될 때(더 분할하면 공간이 부족할 때)까지 빈 공간을 2개로 분할한다. 그리고 메모리를 해제할 때 바로 옆 할당기가 비어 있는지 확인해 비어있다면 하나로 합치는 작업을 한다.
기타로, 균혀이진트리, 스플레이트리, 부분정렬트리 등의 복잡한 자료구조를 사용해 빈공간 검색 비용을 줄인다.