[운영체제] 물리적인 메모리 관리 기법 / 연속 할당(고정 분할 방식과 가변 분할 방식) / 불연속 할당(페이징 기법과 세그멘테이션 기법)

물리적인 메모리 관리 기법

메모리는 일반적으로 낮은 주소 영역의 운영체제 커널이 상주하고 있는 영역과 높은 주소 영역의 사용자 프로세스 영역으로 나뉘어 사용된다.

사용자 프로세스 영역을 어떻게 할당하고 관리하는지에 따라 크게 두 가지 방법으로 나뉜다.

• 연속 할당(Contiguous Allocation)
• 불연속 할당(Noncontiguous Allocation)

 

연속 할당(Contiguous Allocation)

각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 방법으로, 두 가지 방식이 있다.

• 고정 분할 방식(Fixed Partition Allocation)
• 가변 분할 방식(Variable Partition Allocation)

 

고정 분할 방식

물리적인 메모리를 영구적으로 미리 분할(파티션)로 나누는 것을 의미한다. 동시에 메모리에 load되는 프로그램 수가 고정되어 있으며 파티션 당 하나의 프로그램이 적재된다.

고정 분할 방식은 Internal fragmentation과 External fragmentation이 발생할 수 있다.

 

가변 분할 방식

프로그램의 크기를 고려해서 메모리에 할당하는 것을 의미하며, 파티션의 크기나 개수가 동적으로 변한다.

가변 분할 방식은 External fragmentation이 발생할 수 있다.

 

외부 조각과 내부 조각

• 외부 조각(External fragmentation): 프로그램의 크기보다 파티션의 크기가 작은 경우를 의미하며, 어떠한 프로그램도 배정되지 않은 메모리의 빈 곳임에도 불구하고 프로그램이 할당할 수 없는 작은 파티션을 말한다.
• 내부 조각(Internal fragmentation): 프로그램 크기보다 파티션의 크기가 큰 경우를 의미하며, 하나의 파티션 내부에서 발생하는 사용되지 않는 메모리 조각을 말한다. 즉, 특정 프로그램에 배정되었지만 사용되지 않는 공간을 의미한다.

 

Hole

가용 메모리 공간을 의미하며, 다양한 크기의 hole들이 메모리 여러 곳에 흩어져 있다.

운영체제는 메모리의 할당 공간과 가용 공간인 hole을 유지하고 있어야 하며, 프로세스가 도착하면 수용 가능한 hole을 할당시킨다.

 

Dynamic Storage-Allocation Problem

가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제이다.

• First-fit: size가 n 이상인 것 중 최초로 찾은 hole에 할당하는 방법
• Best-fit: size가 n 이상인 것 중 가장 작은 hole에 할당하는 방법
• Worst-fit: 가장 큰 hole에 할당하는 방법

 

Compaction

외부 조각 문제를 해결하는 방법으로, 사용 중인 메모리 영역을 한 군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block을 만드는 것을 말한다.

최소한의 메모리를 이동하기 때문에 매우 복잡하고 비용이 많이 드는 방법이다.

 

프로세스의 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 수행될 수 있기 때문에 런타임 바인딩에서만 수행이 가능하다.

 

불연속 할당(Noncontiguous Allocation)

하나의 프로세스가 메모리의 영역에 분산되어 올라가도록 하는 방법

• Paging
• Segmentation
• Paged Segmentation

 

Paging 기법

프로세스의 가상 메모리를 동일한 사이즈의 page 단위로 나누어 불연속하게 저장하는 방법이다.

일부는 backing storage에, 일부는 physical memory에 저장하며, 물리적 메모리는 동일 크기의 frame으로 나누고 논리적 메모리는 동일 크기의 page로 나눈다. (frame과 같은 크기)

 

페이징 기법은 Page Table을 이용하여 논리적 주소를 물리적 주소로 변환할 수 있다.

 

Page Table

페이지 테이블은 메인 메모리에 상주하며, 프로세스마다 페이지테이블이 존재한다.

 

두 가지 레지스터

• PTBR: 페이지 테이블의 시작 위치를 가리킨다. (base)
• PTLR: 테이블의 크기를 보관하는 용도로 사용된다. (length)

 

페이지 테이블은 모든 메모리 접근 연산에서 두 번의 접근이 필요한데, 주소 변환을 위한 페이지 테이블 접근 연산 한 번과 실제 데이터 접근 연산 한 번, 총 두 번의 메모리 접근이 필요하다.

따라서 메모리 접근 속도가 느리며, 속도 향상을 위해 associate register 혹은 TLB라고 불리는 고속의 lookup hardware cache를 사용할 수 있다.

 

TLB(Translation Look-aside Buffer)

페이징 기법에서 주소 변환 시 페이지 테이블을 접근하기 전에 TLB에 보관되어 있는 프로세스를 먼저 확인하는 캐시 역할을 한다.

TLB에는 페이지 테이블의 일부만을 보관하고 있기 때문에 타겟이 되는 page number와 frame number를 모두 가지고 있어야 한다.

 

TLB에는 페이지 테이블과 다르게 인덱스가 없어 주소 변환을 위한 타겟이 되는 프로세스를 찾기 위해서는 순차적으로 전체를 탐색해야 하므로 오버헤드가 크다. 따라서 병렬적으로 검색이 가능한 associate register를 이용해서 TLB를 구성할 수 있다.

 

Memory Protection

• Protection Bit: page에 대한 접근 권한을 표시하는 비트 (read, write, read-only)
• Valid(v) / Invalid(I) Bit: Valid/Invalid 비트를 사용하여 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있거나 없음을 표시

 

Two-level Page Table

현대의 컴퓨터에서는 페이지 테이블을 위한 공간 낭비가 많이 발생할 수 있다. 이를 예방하고자 Two-level Page Table을 이용할 수 있다.

 

기본의 페이지 테이블은 논리적 메모리에 올라와 있는 프로세스가 사용되지 않는 프로세스라고 할지라도 테이블에는 존재해야 했다.

반면에 Two-level 페이지 테이블은 Outer-page table에 사용되지 않는 프로세스는 null 포인터로 존재하고, 이에 해당하는 Inner-page table은 만들어지지 않는 방식으로 구성된다.

 

Two-level 페이지 테이블은 주소 변환을 위해서 메모리를 두 번 접근하고, 실제 데이터를 한 번 접근하여 기존의 페이지 테이블의 접근 방식보다는 시간적으로 비효율적일 수가 있다. 하지만 공간적으로는 기존의 페이지 테이블보다는 효율적이다.

 

Multilevel Paging

컴퓨터의 주소 공간이 더 커지면 다단계 페이지 테이블이 필요하다. 각 단계의 페이지 테이블이 메모리에 존재하므로 논리적 주소의 물리적 주소 변환에 더 많은 메모리 접근이 필요하다.

TLB를 통해 메모리 접근 시간을 줄일 수 있다.

 

Inverted Page Table

Inverted 페이지 테이블은 물리 주소를 통해 논리 주소를 알아내는 구조의 페이지 테이블로, 물리적 메모리의 frame 당 페이지 테이블 엔트리가 하나씩 존재한다.

 

기존 페이지 테이블은 메모리를 효율적으로 사용하게 해주지만 페이지 테이블 자체가 차지하는 메모리가 많다. Inverted 페이지 테이블은 공간적인 이점을 얻기 위한 아키텍처로, 시스템 전체에서 하나의 페이지 테이블을 가지고 있도록 구현한 것이다.

 

반면에, Inverted 페이지 테이블은 주소 변환 시 검색할 때마다 테이블 전체를 탐색해야 하므로 오버헤드가 발생할 수 있다. associate register를 통해 병렬적으로 한 번에 탐색하여 해결할 수 있지만 비싸다.

 

Shared Pages

코드 중에서 함께 사용 가능한 영역이 있는데 이를 Shared Code라고 한다. Shared Code는 read-only로 구현하여 프로세스 간에 하나의 코드만 메모리에 올려 접근할 수 있다.

 

모든 프로세스가 접근 가능한 공유 코드이므로 모든 프로세스의 logical address place에서 동일한 위치에 있어야 한다. 즉, 페이지 번호가 같아야 한다.

 

Segmentation 기법

세그먼트 기법은 주소 공간이 담고 있는 의미를 기준으로 주소 공간을 자르고, 각각의 세그먼트는 물리적인 메모리에 서로 다른 위치에 올라갈 수 있게 하는 방법이다.

프로그램은 의미 단위인 여러 개의 segment로 구성되며, 일반적으로는 code, data, stack 부분이 하나씩 segment로 정의되어 있다.

• 작게는 프로그램을 구성하는 각각의 함수를 segment로 정의
• 크게는 프로그램 전체를 하나의 segment로 정의

 

Segmentation Architecture

논리 주소는 <Segment-number, offset>으로 구성되어 있다.

 

Segment Table

각 세그먼트별로 Protection bit가 있다.

• Valid bit
• Read/Write/Execution 권한 bit

 

Segmentation 기법의 장단점

Segment는 의미 단위이기 때문에 공유와 보안에 있어 Paging 기법보다는 훨씬 효과적이지만, Segment의 길이가 동일하지 않으므로 가변 분할 방식에서와 같이 동일한 문제점이 발생할 수 있다. (외부 조각 발생)

 

Segmentation with Paging

Segmentation 기법과 Paging 기법을 혼용한 방식으로, Segment를 구성하는 Page를 나누어 물리적인 메모리에 할당한다. 즉, 페이지 단위로 할당한다. 하지만 의미 단위로 관리하는 것들은 Segment Table을 이용한다.

Segment가 여러 개의 Page로 구성되어 있으며, Segment의 크기가 Page의 크기의 배수가 된다.