운영체제 시리즈 11. Memory management -2

물리적 메모리의 할당방식

물리적 메모리는 운영체제 상주영역과 사용자 프로세스 영역으로 나뉜다. OS 상주영역은 interrupt vector와 함께 낮은 주소영역을 사용하고, 사용자 프로세스 영역은 높은 주소 영역을 사용한다.

연속할당

각각의 프로세스가 메모리의 연속적 공간에 적재되는 것이다.

 

• 고정분할 방식 : 사용자 프로그램이 들어갈 부분을 파티션으로 미리 나눠놓는 방식이다. 동시에 메모리에 올릴 수 있는 프로램에 제한이 있으며 수행가능한 프로그램의 최대크기에 제한이 있다. 외부조각과 내부조각이 발생할 수 있다. 외부조각은 사용이 안 된 메모리공간이나 현재 상태에서 사용하기엔 작아서 사용될 수 없는 공간을 의미한다. 내부조각은 분할된 메모리 공간을 사용하고 남는 공간을 의미한다.
• 가변분할 방식 : 미리 안 나눠놓는 방식으로 분할의 크기, 개수가 동적으로 변한다. 실행될 때마다 프로그램을 메모리에 차곡차곡 올리게 된다. 수행이 끝나면 외부조각이 발생할 수 있다. 운영체제는 메모리 내 가용공간(hole) 중 어디에 메모리를 올릴지 결정해야 한다. 이를 동적 메모리 할당 문제(dynamic storage-allocation problem)이라고 한다.

 

고정분할방식과 가변분할방식

동적 메모리 할당 문제 (Dynamic storage-allocation problem)

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

 

1. First-fit (최초적합) : 사이즈가 n 이상인 것 중 최초로 찾아지는 hole에 할당한다. hole을 찾는 오버헤드가 적다.

2. Best-fit : 모든 hole을 탐색하고 사이즈가 n이상인 가장 작은 hole에 할당한다. 가장 적합한 hole을 찾는다.

3. Worst-fit : 가장 큰 홀에 할당한다. 이것 역시 모든 리스트를 탐색해야 한다.

Compaction

hole을 모아 한군데로 합쳐 큰 가용공간을 만드는 것을 의미한다. 비용이 매우 많이 들고, 전체 프로램의 바인딩과 관련되어 있어 복잡하다.

불연속 할당

하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음을 뜻한다. 아래 3가지 기법이 있고 하나씩 정리해보도록 하겠다.

 

• 페이징(Paging) : 프로세스의 주소 공간을 같은 페이지 단위로 나누어 저장하는 방식
• 세그먼테이션 (Segmentation) : 프로세스의 주소 공간을 의미 단위로 나누어 저장하는 방식
• 페이지드 세그먼테이션(Paged segmentation) : 페이징과 세그먼테이션의 장점을 합친 방식

페이징(Paging)

프로세스의 주소공간을 동일한 크기의 페이지 단위로 나누어 페이지 단위로 메모리에 저장하는 방식이다. 메모리에 올리는 단위가 동일하기 때문에 메모리를 분할해놓더라도 빈 프레임이 있다면 어디든 사용가능하다. 외부조각 문제가 발생하지 않으나, 프로세스가 페이지의 배수단위라는 보장이 없으므로 마지막 조각은 내부조각이 발생할 수 있다. 연속할당에서 발생했던 동적 메모리 할당 문제가 발생하지 않는다. 모든 프로세스의 주소 변환을 위한 페이지 테이블이 존재하며 페이지 갯수만큼 주소 변환 엔트리를 가진다.

 

페이지 테이블

주소변환기법

CPU가 사용하는 논리적 주소에서 페이지 번호(p)와 페이지 오프셋(d)로 나누어 주소변환을 한다. 페이지번호(p)는 페이지 테이블을 가리킨다. 페이지 테이블에서 p인덱스로 접근하면 해당되는 페이지의 물리 메모리의 위치정보, 즉 프레임 번호(f)를 갖는다. 페이지 오프셋(d)에는 해당 페이지에서의 오프셋 정보를 갖는다. 주소변환 기법을 사용하여 논리적 주소에 대응되는 물리적 주소를 얻을 수 있다.

페이지 테이블의 구현

페이지 테이블의 주소변환

페이지 테이블은 주소변환을 하기 위한 자료구조이다. 페이징 기법에서 메모리 접근 연산은 논리적 주소에서 페이지 테이블의 접근하여 물리적 주소를 알아내고, 변환 주소에서 실제 데이터에 접근하는 두 번의 메모리 접근을 하게된다. 접근 오버헤드를 줄이기 위해 TLB(Translation Look-aside Buffer)라는 고속의 주소 변환용 하드웨어 캐시가 사용되기도 한다.  TLB에서는 연관레지스터를 사용하여 병렬탐색을 함으로써 시간을 줄인다. TLB와 페이지테이블은 각 프로세스 마다 존재한다. 따라서 문맥교환이 일어나면 TLB도 기존 정보를 삭제하고 새로운 정보로 교체된다. 

계층적 페이징(Two-level paging)

페이지 주소변환에 할애되는 메모리 공간을 줄이기 위해 2단계 페이징 기법을 사용한다. 외부 페이지 테이블(outer page table)과 내부 페이지 테이블(inner page table)을 사용하여 두 단계에 걸친 페이지 테이블을 사용한다. 사용되지 않는 공간은 외부 페이지를 null로 설정하고 내부 페이지를 만들지 않는다. 시간은 더 오래걸리지만 사용되는 페이지만 만들기 때문에 공간 효율성이 좋다.

<P1, P2, d> 로 구성되며 P1은 외부 페이지 테이블의 주소, P2는 내부 테이블 페이지의 주소, d는 해당 프레임에서의 오프셋을 의미한다. 페이지는 32바이트의 공간중 12바이트를 페이지를 구분하기 위한 주소공간으로 사용된다. 내부 페이지는 4KB/4B = 1K 즉, 2의 10승 만큼의 갯수를 가진다. 따라서, 내부페이지는 또 내부 페이지의 주소공간을 가지기 때문에 32비트 - (12비트 + 10비트) = 10비트 크기만큼의 공간을 메모리 공간으로 사용할 수 있다. 

역페이지 테이블

논리 메모리 주소를 가지고 페이지 테이블을 만드는 것이 아니라 물리적 메모리 주소에 대해 페이지 테이블을 만드는 기법이다. 프로세스마다 페이지 테이블을 두지 않고 시스템 전체에 대한 페이지 테이블을 하나만 만든다. 따라서 논리적 주소에는 <pid, p, d>의 정보가 들어간다. 프로세스 아이디(pid), 페이지번호(p), 오프셋(d)를 의미한다. 시간적인 오버헤드가 존재하므로 연관 레지스터(associative register)를 보관해 병렬탐색을 가능하게 한다. 

공유 페이지

여러 프로세스가 공유할 수 있게 작성된 코드를 공유코드(shared code)라고 한다. 공유코드는 읽기전용(read-only)이며 재진입 가능코드(re-entrant code) 또는 순수 코드(pure code)라고 한다. 공유 페이지란 공유코드를 담고 있는 페이지를 뜻한다. 모든 프로세스에 논리주소에 동일한 위치에 존재해야 한다. 공유 페이지에 해당되는 코드는 하나만 올려서 공통적으로 사용되는 메모리의 공간효율의 장점이 있다.

 

메모리 보호

페이지 테이블에는 주소변환정보와 메모리보호를 위한 보호비트(protection bit)와 유효-무효 비트(valid-invalid bit)를 두고 있다. 보호비트에는 각 페이지에 대한 접근권한을 담는다. 유효-무효 비트는 해당 페이지의 내용이 유효한지에 대한 내용을 담는다. 

세그먼테이션(Segmentation)

segmentation은 의미단위로 프로세스의 주소공간을 분할한다. 일반적으로 데이터, 코드, 스택 등의 기능단위로 세그먼트를 정의한다. 더 작게 쪼개면 함수 단위로도 세그먼트를 나눌 수 있다. 크기가 균일하지 않은 세그먼트를 관리하는 오버헤드가 있다. segmentation에서는 주소변환을 위해 segment table을 사용한다. 세그먼트 테이블은 기준점(base)와 한계점(limit)를 가진다. 

 

segmentation

페이징 기법처럼 세그먼테이션 기법에서도 세그먼트 테이블에 보호비트와 유효비트를 두어 관리한다. 여기서도 공유 세그먼트 개념을 지원한다. 세그먼트는 의미단위로 나뉘기 때문에 공유와 보안의 측면에서 페이징 기법보다 효과적이다. 하지만 조각이 균일하지 않기 때문에 외부조각이 발생하며, 어떤 가용공간에 할당할지 결정하는 문제가 발생한다. 

페이지드 세그먼테이션(Paged segmentation)

페이징 기법과 세그먼테이션 기법의 장점을 합친 기법이다. 세그먼테이션 기법과 같이 의미 단위로 세그먼트를 나눈다. 하지만 세그먼트가 임의의 길이를 가지는 것이 아니라 동일한 크기의 페이지 단위로 나뉜다. 하나의 세그먼트가 페이지의 배수 단위가 되게 설정하는 것이다. 이 기법에서는 주소 변환을 위해 외부의 세그먼트 테이블과 내부의 페이지 테이블로 관리한다. 이 구조는 2단계 테이블 구조와 비슷하다. 

정리

물리적 메모리의 할당방식에 대해 연속할당과 불연속 할당에 대해 알아보았다. 연속할당에는 동적할당에 따른 문제를 해결하는 방법들이 있다. 불연속 할당의 페이징, 세그먼테이션, 페이지드 세그먼테이션 기법에 대해 정리하였다. 주소변환에 있어서 OS는 역할을 하지 않고 하드웨어 측면에서 이루어 진다. 

 

운영체제 시리즈는 반효경 교수님의 운영체제 강의 와 "운영체제와 정보기술의 원리"라는 책을 바탕으로 정리한 내용입니다.