#단편화, 스와핑, 페이징, 세그먼테이션

주기억장치에 프로세스를 적재시키지만 단편화 문제가 발생한다. 단편화란 ‘이용되지 않고 낭비되는 공간의 발생’이라고 할 수 있으며, 분할된 영역 내에서 낭비되는 공간이 발생하는 경우를 ‘내부 단편화’라 하고, 전체 영역에서 이용되지 않는 공간이 발생하는 경우를 ‘외부 단편화’라고 한다. 외부 단편화의 한 예로, 작은 크기로 분할된 영역 a가 있는 반면, 필요한 메모리 자원이 이보다 큰 프로세스들만이 메모리를 점유한다면, 이 때 이 영역a는 외부 단편화의 한 요인으로 볼 수 있다.

그러나 이런 단편화는 근본적으로는 해결할 수 없어 보인다. 프로세스의 작업이 동시에 끝나 메모리 자원이 동시에 반환될 수 없기 때문이다. 따라서 단편화를 근본적으로 해결하기 보다는, 불규칙적인 메모리 할당 공간을 보다 효율적으로 관리할 수 있는 기법을 통해 성능 향상을 꾀하는 것이 더 현실적으로 보인다.

이를 위해 스와핑(Swapping), 페이징(Paging), 세그먼테이션(Segmentaion) 기법이 있으며, 특히 페이징과 세그먼테이션은 사상 테이블을 이용하여 불규칙적으로 할당된 메모리 공간을 효율적으로 관리할 수 있다.

스와핑에서는 메모리에서 실행 중이지 않은 프로세스의 메모리 이미지를 보조기억장치에 저장한다.

즉, 메모리가 가득 찬 상태에서 새로운 프로세스가 메모리 공간을 요구할 때, 운영체제는 현재 메모리에서 사용 중이지 않은 프로세스를 식별하여 그 프로세스의 이미지를 보조기억장치로 이동하는 ‘스왑 아웃(swap out)’ 작업을 진행한다. 반대로 스왑 아웃된 프로세스에 대한 실행이 요청되면 보조기억장치에서 이 이미지를 가져오는 ‘스왑 인(swap in)’ 작업이 수행된다.

그러나 스와핑은 문맥 교환(context switching) 시간이 오래 걸릴 뿐만 아니라, 실제 시스템에 적용하기가 어렵다는 단점이 있다. 따라서 실제 구현은 디스크 내에 별도로 스왑 공간을 분리하는 방법으로 이루어지며, 유닉스(Unix)와 같은 운영체제에서는 시스템 부하가 클 때만 스와핑이 작동하도록 되어 있다.

가상기억장치 시스템 중 같은 크기의 블록들로 분할하는 시스템을 페이징 시스템(paging system)이라 한다. 페이징 시스템에서는 실행 대상의 모든 프로그램들이 일정 크기의 블록들로 분할되며, 이와 같이 분할된 블록들을 페이지(page)라 한다. 이러한 시스템에서는 프로그램이 페이지 단위로 주기억장치에 적재되므로 주기억장치 영역도 페이지크기와 같은 크기로 분할되는데 이와 같이 분할된 주기억장치 영역들을 페이지 프레임(page frame) 이라 한다.

페이징에서는 ‘주소 사상’을 ‘페이지 사상 테이블(PMT, Page Map Table)’을 이용한다. 여기서 주소 사상이란 논리 주소(가상주소, 상대주소)를 물리 주소(절대 주소, 실 주소)로 변경하는 과정이며, 페이징에서 ‘직접 사상 기법’을 이용한 주소 사상은 아래의 알고리즘과 같이 수행된다.

① 해당 프로세스의 PMT가 저장되어 있는 주소 b에 접근 ② 해당 PMT에서 페이지 p에 대한 엔트리를 찾는다.         → (p의 엔트리 위치) = b + p * entrySize (p는 페이지 번호)  ③ 찾아진 엔트리의 존재 비트 검사 - 존재 비트 = 0일 때, 디스크 → 주기억장치로 적재 - 존재 비트 = 1일 때, 해당 엔트리에서 페이지 프레임 번호 p‘을 인출 ④ 인출된 페이지 프레임 번호 p`과 가상 주소의 변위 d를 사용해 실 주소 r을 다음과 같이 형성         → r = p‘ * pageSize + d ⑤ 실 주소 r로 주기억장치에 접근

그러나 이 경우, 물리 주소를 생성하기 위해서는 매번 페이지 테이블을 먼저 읽어야 하므로, 주기억장치로의 접근 횟수가 2배가 되고, 결국 프로세스 실행 시간이 2배 가까이 증가한다. 이런 성능 저하를 해결하기 위해 PMT를 캐시 기억장치에 적재하는 기법이 사용된다.

PMT를 기억하는 이 장치는 ‘내용 주소화 기억장치(content addressable memory)’라고도 하며, 주소의 개념 없이 지정된 내용으로 데이터에 접근할 수 있도록 하드웨어적으로 구현된 기억장치이다. 이 장치를 이용하면 페이지 번호를 킷값으로 하여 PMT에 대한 병렬 탐색이 가능하기 때문에 보다 빠른 시간 안에 원하는 데이터를 얻을 수 있다. 하지만 하드웨어의 비용이 매우 많이 든다. 이 연관 기억장치와 함께 직접 사상을 혼합하여 사용하는 ‘혼합 사상 기법’의 수행 절차에서는 주소 사상이 일어나기 전에 아래의 절차가 추가적으로 수행된다.

√ 페이지 p에 대한 PMT 엔트리가 연관 기억장치에 적재되어 있는지 확인   - 페이지 p에 대한 PMT 엔트리가 연관 기억장치에 적재된 경우     → 존재 비트를 검사하고 페이지 프레임 번호를 인출   - 페이지 p에 대한 PMT 엔트리가 연관 기억장치에 적재되지 않은 경우     → 주기억장치의 커널 공간에 있는 PMT에 접근하여 직접 사상 기법으로 페이지 프레임 번호를 인출

이런 페이징 기법에서는 페이지의 테이블의 크기가 매우 커지는 것과 페이지 테이블을 연속된 메모리 공간에 배치하기가 어렵다는 문제가 발생한다. 이를 해결하기 위한 테이블 처리 기법으로 계층적 페이징(Hierarchical Pagin), 해시 페이지 테이블(Hash Page Table), 역 페이지 테이블(Inverted Page Table) 등이 있다.

계층적 페이징에서는 페이지를 2계층으로 구성한다. 즉, 페이지 테이블 자체를 다시 페이징하는 외부 테이블을 만든다.

해시 페이지 테이블은 논리 주소의 페이지 번호를 해시 값으로 사용한다. 해시 함수를 사용하여 페이지 정보가 어디 있는지 바로 알 수 있고, 같은 위치에 저장되어야 할 여러 개의 페이지 정보를 연결리스트를 이용하여 연결할 수 있다.

역 페이지 테이블은 물리 메모리의 프레임 번호로 인덱스 되는 테이블이다. 일반적인 페이지 테이블의 역으로 생각하면 되지만, 주소 변환 시간이 길어져 검색 비용이 크고, 메모리 공유가 어렵다는 단점이 있다.

같은 크기의 블록들로 분할하는 페이징 시스템과는 달리 ‘세그먼테이션 시스템(segmentation system)’은 프로그램을 논리적인 개념을 근거로 블록 단위를 분할한다. 그리고 이 시스템에서는 프로그램 블록을 ‘세그먼트(segment)’라 한다. 각 세그먼트들의 크기가 다르기 때문에 주기억장치 영역을 미리 분할해 둘 수 없고, 각 세그먼트가 주기억장치에 적재될 때 빈 공간을 찾은 후에 할당된다.

주소 사상 기법은 페이징과 비슷하다. 하지만 세그먼테이션은 프로그램 공유나 보호에 있어 페이징 보다 비교적 덜 복잡하기 때문에, 직접 사상 과정에서 ‘보호 비트(protection bits) 필드’를 이용해서 해당 세그먼트에 대해 프로세스가 접근할 수 있는 연산 모드에 대한 정보를 처리하는 과정과, 세그먼트의 크기가 달라 ‘세그먼트 길이(segment length)’에 따른 오버플로우에 대한 예외처리를 하는 과정이 주요하게 언급된다.

이처럼 페이징 시스템에서는 사용자 프로그램을 미리 정해진 일정 크기로 분할하기 때문에 단순하고 효과적인 주소 사상이 가능하지만, 논리적 개념 없이 프로그램이 분할되기 때문에 프로그램 공유 등과 관련하여 어느 정도 오버헤드가 있다는 단점이 있다. 이와 반대로 세그먼테이션 시스템에서는 사용자 프로그램을 논리적인 단위로 분할하여 프로그램 공유 문제는 페이징 보다 쉽게 해결되지만, 서로 다른 크기의 세그먼트를 관리하기 위한 오버헤드가 추가된다는 단점을 갖는다.

참고 자료

엄영익·정태명 공저『컴퓨터 운영체제론』, 생능출판사

유튜브 'Young Hyun Bae'님 강좌,

『 09-1 메모리의 기본 구조와 동작 』

『 09-2 메모리 관리 기법 (1) 』

『 09-3 메모리 관리 기법 (2) 』