메모리 할당(2) - 비연속 할당

2. 비연속 할당(Non-Continuous Allocation)

하나의 프로세스가 메모리의 여러 영역에 분산되어 올라가는 것을 의미한다. 사용자 프로그램을 여러 개의 블록으로 분할하고

실행 시 필요한 블록들만 메모리에 적재, 나머지 블록들은 스왑 디바이스(Swap Device)에 존재하는 방식으로 동작한다.

 

연속 할당에서의 주소 매핑(Address Mapping)은 상대 주소(Relative Address, 프로그램의 시작 주소를 0으로 가정한 주소)를

할당된 주소에(Allocation Address) 재배치(Relocation) 하는 과정을 통해 이루어진다.

 

비연속 할당 역시 가상 주소를 실제 주소로 바꾸어주는 주소 매핑 과정이 필요하다.

가상 주소는 연속된 메모리 할당을 가정한 주소이며, 실제 주소는 실제 메모리에 적재된 주소를 의미한다.

사용자/프로세스는 실행 프로그램 전체가 메모리에 연속적으로 적재되었다 가정하고 실행할 수 있다. 

 

 

블록매핑

사용자 프로그램을 블록 단위로 분할/관리하는 것을 의미한다. 블록 매핑을 위해서는 아래와 같은 각 블록에 대한 주소 매핑 정보와 함께

BMT(Block Map Table)이 필요하다. BMT란 주소 매핑을 위한 테이블로서 커널 공간에 프로세스마다 하나의 BMT가 존재한다.

 

블록 매핑은 다음의 과정을 통해 이루어진다. 우선 프로세스의 BMT에 접근한다. BMT에서 블록 B에 대한 항목(entry)을 찾는다.

그리고 레지던스 비트(Residence Bit)를 검사한다. 레지던스 비트가 1인 경우, BMT에서 블록 B에 대한 실제 주소(Real Address) 값을

확인한다. 이후, 메인 메모리 상에서의 실제 주소를 계산한다(r = a + d). 해당 실제 주소(r)를 이용하여 메모리에 접근한다.

레지던스 비트가 0인 경우, 스왑 디바이스에서 해당 블록을 메모리로 가져오고 BMT를 업데이트한다.

 

 

페이징 시스템(Paging System)

프로그램을 같은 크기의 블록으로 분할하는 기법을 의미한다. 프로그램의 분할된 블록을 페이지(Page)라고 하며,

페이지와 같은 크기로 분할된 메모리 상의 영역을 페이지 프레임(Page Frame)이라고 한다. 

이처럼 페이지는 크기에 따른 분할이지, 논리적 분할이 아니다. 따라서 페이지를 공유하거나 보호하는 과정이 복잡하다.

또한, 메모리 이용 시 외부 단편화는 해소되지만 내부 단편화 발생 가능성이 있다.

 

페이징 시스템에서의 주소 매핑은 PMT(Page Map Table)를 이용하여 이루어진다. 

주소 매핑 메커니즘은 크게 직접 사상과 연관 사상, 그리고 이 둘을 하이브리드로 사용하는 방법 세 가지가 있다.

 

 

직접 사상(Direct Mapping)

블록 매핑 방법과 유사하다. 우선, 프로세스의 PMT가 저장되어 있는 메모리 주소 b에 접근한다. 해당 PMT에서 페이지 p에 대한

엔트리(entry)를 찾는다(p의 엔트리 위치 = b + p * entrySize). 찾은 엔트리의 레지던스 비트를 검사한다. 레지던스 비트가 1인 경우,

페이지 프레임 번호(Page Frame Number) p'를 확인한다. 이를 이용하여 실제 주소(r = p' * pagesize + d)를 계산하고 메모리에 접근한다.

레지던스 비트가 0인 경우, 페이지 폴트(page fault)가 발생한다. 해당 페이지를 스왑 디바이스에서 메모리로 적재하고 PMT를 갱신한다.

PMT가 메모리에 위치하고 있기에 직접 사상 과정에서 메모리 접근은 2번 이루어진다. 이는 성능 저하 문제를 야기한다.

이를 해결하기 위해 PMT를 위한 전용 기억장치(하드웨어)를 사용하는 방법인 연관 사상이 등장한다. 

 

연관 사상(Associative Mapping)

TLB(Translation Look-aside Buffer)라고 불리는 캐시 메모리(하드웨어)에 PMT를 적재하고, PMT를 병렬적으로 탐색한다.

부하가 낮고 속도가 빠르지만 하드웨어가 비싸서 크기가 큰 PMT를 다루기 어려운 문제가 있다.

 

혼합 사상(Hybrid Direct/Associative Mapping)

위의 두 가지 사상 기법을 혼합하여 사용하는 방법이다. 이를 통해 연관 사상의 장점은 활용하면서 하드웨어의 비용은 줄일 수 있다.

작은 크기의 TLB를 사용하면서 PMT는 메모리 커널 공간에 저장하고, PMT 중 일부 엔트리들을 TLB에 적재한다. 이때, 최근에 사용된

page들에 대한 엔트리가 저장된다. 이후, 주소 매핑 과정에서는 프로세스의 PMT가 TLB에 적재되어 있는지 확인한다.

TLB에 적재되어 있는 경우, 레지던스 비트를 검사하고 페이지 프레임 번호를 확인하여 실제 주소를 찾아간다.

TLB에 적재되어 있지 않은 경우, 직접 사상으로 페이지 프레임 번호를 확인한다.

이후 해당 PMT 엔트리를 TLB에 적재하고 실제 주소를 찾아간다.

 

 

페이징 시스템에서의 메모리 관리

프로그램을 페이지로 분할하듯이, 메모리 역시 페이지와 같은 크기로 미리 분할한다.

이를 페이지 프레임이라고 하며 프레임 테이블(Frame Table)을 만들어 관리/사용한다.

프레임 테이블 내에서 페이지 프레임 당 하나의 엔트리를 가지며, 구성은 Allocated/Available Filed, PID(Process ID) Field,

Link Filed(Free Page 들을 연결하는 Free List), AV(Free List Header)로 이루어져 있다.

 

페이지 공유 및 보호

여러 프로세스가 특정 페이지를 공유할 수 있다.

공유 가능 페이지는 크게 함수와 같이 코드로 이루어진 프로시저 페이지(Procedure Page)와 데이터 페이지(Data Page)로 구분된다.

데이터 페이지의 경우 Read-Only-Data와 Read-Write-Data로 나뉘는데, 후자의 경우 병행성 제어 기법 관리하에서만 가능하다.

 

ed 1, 2, 3 함수를 공유하는 프로시저 페이지(왼쪽), 데이터 페이지(오른쪽)

 

페이지 공유시 각 프로세스 별 PMT에서의 엔트리는 동일해야 문제가 발생하지 않으며,

아래와 같이 페이지 보호를 위하여 프로텍션 비트를 사용할 수 있다.

 

 

세그멘테이션 시스템(Segmentation System)

프로그램을 논리적 블록으로 분할하는 기법을 의미한다. 따라서 페이징 시스템과 달리 블록의 크기가 서로 다를 수 있다.

메모리를 미리 분할하지 않아 주소 매핑 및 메모리 관리의 부하가 크다는 단점이 있다. 하지만 논리적으로 분할되어 있어, 세그먼트 공유와 보호가 용이하다. 또한, 메모리 이용 시 내부 단편화는 해소되지만 외부 단편화 발생 가능성이 있다.

 

세그멘테이션 시스템에서의 주소 매핑은 SMT(Segment Map Table)를 이용하여 이루어진다. 우선, 프로세스의 SMT가 저장되어

있는 주소 b에 접근한다. 이후, SMT에서 세그먼트 s의 엔트리를 찾는다(s의 엔트리 위치 = b + s*entrySize).

찾은 엔트리의 레지던스 비트가 1인 경우, 세그먼트 주소와 세그먼트 길이, 프로텍션 비트를 확인한다.

만약 세그먼트 길이보다 displacement가 큰 경우, 세그먼트 오버플로우 예외 처리(Segment Overflow Exception) 모듈을 호출한다.

프로텍션 비트 상 허가되지 않는 연산일 경우, 세그먼트 보호 예외 처리(Segment Overflow Exception) 모듈을 호출한다.

실제 주소(r = a + d)를 계산하고 메모리에 접근한다. 레지던스 비트가 0인 경우, 세그먼트 폴트(Segment Fault)가 발생한다.

스왑 디바이스로부터 해당 세그먼트를 메모리로 적재하고 SMT를 갱신한다.

 

 

Hybrid Pagin/Segmentation System

페이징과 세그멘테이션의 장점을 결합한 시스템이다. 기본적인 아이디어는 프로그램을 논리적 단위인 세그먼트로 분할하고,

각 세그먼트를 다시 고정된 크기의 분할하는 것이다. 그리고 메모리에는 페이지 단위로 적재한다. 

각 프로세스마다 하나의 SMP를, 각 세그먼트마다 하나의 PMT를 사용한다.

 

논리적 분할과 고정 크기 분할을 결합함으로써 페이지 공유/보호가 쉬워졌고, 메모리 할당/관리 오버헤드도 작아졌다.

외부 단편화 문제도 해결된다. 다만, 내부 단편화 문제는 여전히 있으며 전체 테이블의 수가 증가하여 메모리 소모가 커진다.

주소 매핑 과정 역시 복잡하며, 직접 사상의 경우 메모리 접근이 3번이나 이루어져 성능이 저하될 수 있다는 단점이 있다.