Memory Management: 메모리 관리 (2/3)

3. 물리적 메모리의 할당 방식 Allocation of Physical Memory

메모리는 일반적으로 두 영역으로 나뉘어 사용한다. 

* OS 상주 영역 

interrupt vector 와 함께 낮은 주소 영역 사용

 

* 사용자 프로세스 영역

높은 주소 영역 사용

 

사용자 프로세스 영역의 관리 방법은 프로세스를 메모리에 올리는 방식에 따라 

연속 할당 (contiguous allocation) 방식과 불연속할당 (noncountiguous allocation) 방식으로 나뉜다. 

 - 연속 할당(contiguous allocation)

연속 할당 방식은 프로세스를 메모리에 올릴 때 그 주소 공간을 여러 개로 분할하지 않고 물리적 메모리의 한 곳에 연속적으로 적재하는 방식이다. 이 방식은 물리적 메모리를 고정된 크기의 분할로 미리 나누어 놓느냐 아니냐에 따라 고정 분할 방식과 가변 분할 방식으로 나뉜다.

* 고정 분할 방식 (Fixed Partition Allocation)

- 물리적 메모리를 주어진 개수만큼의 영구적인 분할(partition)으로 나눈다.

- 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재한다.

어쩄든 어느 방식이던 분할 당 하나의 프로그램의 적재가 가능하다. 따라서 동시에 메모리에 올릴 수 있는 프로그램의 수가 정해지며 수행 가능한 프로그램의 최대 크기 또한 제한된다는 점에서 가변 분할 방식보다 융통성이 떨어진다.

internal fragmentation(내부 조각) 과 external fragmentation (외부 조각)이 발생한다.

내부조각이란 프로그램의 크기 보다 분할의 크기가 커서 메모리가 낭비되는 경우, 프로그램이 적재되지 않고 놀고 있는 메모리 공간을 내부 조각이라고 한다. 얘는 이미 프로그램이 할당되었지만, 남는 경우라서 이 내부 조각보다 작은 크기의 프로그램이 오더라도 그 프로그램을 내부 조각에 할당할 수 없다.

외부 조각이란 프로그램의 크기보다 분할의 크기가 작아서 프로그램이 들어가지 못하고 메모리는 메모리대로 놀고 있는 메모리 공간을 의미한다. 빈 공간임에도 사용할 수 없는 것이다. 얘는 외부조각보다 작은 프로그램이 온다면 그 프로그램을 외부 조각에 할당할 수 있다.

 

* 가변 분할 방식 (Varable Partition Allocation)

 고정분할 방식과는 다르게 메모리에 적재되는 프로그램의 크기에 따라 분할의 크기, 개수가 동적으로 변하는 방식이다. 기술적 관리 기법이 필요하다. 내부 조각은 발생하지 않지만 외부 조각은 발생할 가능성이 있다.

연속 할당에서는 hole 이라는 것이 존재한다. hole이란 가용 메모리 공간이다. 다양한 크기의 hole 들이 메모리 여러 곳에 흩어져 있다. 프로세스가 도착하면 수용 가능한 hole을 할당한다. 운영체제는 다음의 정보를 유지한다. a) 현재 할당한 공간 b) 가용 공간(hole)

 

따라서 가변분할 방식에서 주요하게 다루는 쟁점 중 하나는 주소 공간의 크기가 n인 프로세스를 메모리에 올릴 때 물리적 메모리 내 가용 공간(hole) 중 어떤 위치에 올릴 것이냐 하는 문제이다 이것을 Dynamic Storage Allocation Problem라고 한다.

 

Dynamic Storage Allocation Problem (동적 메모리 할당 문제)

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

대표적으로 3가지로 구분할 수 있다. 

 * first-fit (최초 적합)

 size가 n 이상인 것 중 최초로 찾아지는 hole에 할당한다. 시간 측면에서 효율적이라고 할 수 있다.

 

 * Best-fit (최적 적합)

 size가 n 이상인 가장 작은 hole을 찾아서 할당한다. hole 리스트가 크기 순으로 종렬되지 않은 경우 모든 hole 들의 리스트를 탐색해야 한다. 많은 수의 아주 작은 hole들이 생성되고 시간적 오버헤드가 발생하지만 메모리 공간적 측면에선 효율적이다. 

 

* Worst-fit (최악 적합)

가장 큰 hole에 할당한다. 역시 모든 리스트를 탐색해야 한다. 상대적으로 아주 큰 hole들이 생성된다. 시간도 낭비되고 공간도 낭비된다.

 

어쩄든 외부 조각은 없애는게 좋은데 어떻게 없앨 수 있을까? -> compaction

compaction

외부조각 문제를 해결하는 한가지 방법

물리적 메모리 중에서 프로세스에 의해 사용 중인 메모리 영역을 한 쪽으로 몰고 hole들을 한 곳으로 몰아 큰 block을 만드는 것이다. 현재 수행중인 프로세스의 메모리 상의 위치를 상당 부분 이동시켜야 하므로 매우 많은 비용이 들고 중간에 일부 가용 공간이 발생하더라도 최소한의 메모리 이동으로 compaction을 하는 방법이 필요한데 이건 매우 복잡한 문제이다. 또한 프로세스의 주소가 실행시간에 동적으로 재배치 가능한 runtime binding일 경우에만 수행 가능하다. 

 

 - 불연속할당 (noncountiguous allocation)

하나의 프로세스가 물리적 메모리의 여러 영역에 분산되어 올라갈 수 있다.

 * paging -> 동일한 크키로 나누어 올림

 * segmentation -> 크기 일정하지 않음, 의미 단위로 메모리에 올린다.

 * paged Segmentation -> segmentation 기본, 동일 크기의 페이지로 나누어 메모리에 올리는 paged segmentation

 

4. 페이징 기법

페이징 기법이란 프로세스의 주소 공간(virtual memory)을 동일한 크기의 페이지 단위로 나누어 물리적 메모리의 서로 다른 위치에 페이지들을 저장하는 방식을 말한다. 따라서 주소 공간의 내용이 page 단위로 noncontiguous하게 저장되며 일부는 backing store에, 일부는 physical memory에 저장된다. 페이징 기법에서는 물리적 메모리를 페이지와 동일한 크기의 frame(프레임)으로 미리 나누어둔다. 따라서 메모리의 hole이 생기지 않는다. 운영체제는 모든 가용 frame들을 관리한다. 페이징 기법에서는 주소 변환 절차가 연속할당 방식에 비해 복잡한데 그럴 수 밖에 없는게 프로세스 전체를 올리는게 아니라 페이지 단위로 쪼개서 물리적 메모리에 올리므로 주소가 페이지 별로 다르며, 논리적 주소를 물리적 주소로 변환하는 작업이 페이지 단위로 이루어져야 하기 때문이다. 특정 프로세스의 몇번째 페이지가 물리적 메모리의 몇번째 프레임에 들어있다는 페이지별 주소 변환 정보를 유지하고 있어야 한다. 따라서 페이징 기법에서는 모든 프로세스가 각각의 주소 변환을 위한 페이지 테이블(page table: 각각의 페이지들이 물리적 메모리에 어디 있는지 저장해둔 일종의 배열이다)을 가지며, 이 테이블은 프로세스가 가질 수 있는 페이지 개수만큼 (논리적인 주소 만큼) 엔트리가 존재한다. 페이징 기법에서는 외부 조각은 발생하지 않지만 내부 조각은 발생할 수 있다. 

 

 <Address Translation Architecture>

페이지 기법에서는 cpu가 사용하는 논리적 주소를 페이지 번호 p와 페이지 오프셋 d로 나누어 주소변환(address translation)에 사용한다. 페이지 번호는 각 페이지별 주소 변환 정보를 담고 있는 페이지 테이블 접근 시 인덱스(index)로 사용되고, 해당 인덱스의 항목(entry)에는 그 페이지의 물리적 메모리 상의 기준 주소(base address, 시작 위치)가 저장된다. 따라서 특정 프로세스의 p번째 페이지가 위치한 물리적 메모리의 시작 위치를 알고 싶다면 해당 프로세스의 페이지 테이블에서 p번째 항목을 찾아보면 된다. 페이지 오프셋 d는 하나의 페이지 내에서 변위를 알려준다. 따라서 기준 주소 값에 변위를 더함으로써 요청된 논리적 주소에 대응하는 물리적 주소를 얻을 수 있다.

 

<Implementation of Page Tabel> 페이지 테이블의 구현

페이지 테이블은 페이징 기법에서 주소 변환을 하기 위한 자료구조로 물리적 메모리(main memory)에 위치하게 된다. 현재 cpu에서 실행 중인 프로세스의 페이지 테이블에 접근하기 위해 운영체제는 2개의 레지스터를 사용한다. 

* Page-table base register(PTBR): 페이지 테이블 기준 레지스터

 메모리 내에서 페이지 테이블 시작 위치를 가리킨다.

 

* Page-table length register(PTLR): 페이지 테이블 길이 레지스터

페이지 테이블 크기를 보관한다.  

 

모든 메모리 접근 연산에는 2번의 memory access가 필요하다. page table(메인 메모리에 있음) 접근 한번,  변환된 주소에서 실제 data/instruction 접근 한번. 이건 오버헤드가 뒤따르게 된다. 따라서 이와 같은 페이지 테이블 접근 오버헤드를 줄이고 메모리 접근 속도를 향상시키기 위해 TLB(translation lock-aside buffer, = associative register)라고 불리는 고속의 lookup hardware cache 사용한다. 

 

<paging hardware with TLB>

TLB: 주소 변환을 위한 캐쉬메모리(당연히 하드웨어) page table에서 빈번히 참조되는 것 일부만을 캐슁한다. 메인 메모리보다 빠름 근데 비쌈. 따라서 요청되는 페이지에 대한 주소 변환 정보가 TLB 내에 존재할 수도 있고 아닐 수도 있다. 일부만 TLB에 있다. 만약 요청된 페이지 번호가 TLB 내에 존재한다면 곧바로 대응하는 물리적 메모리의 프레임 번호를 얻을 수 있지만, TLB에 존재하지 않는 경우라면 메인 메모리의 페이지 테이블에 접근해서 물리적 메모리의 주소를 얻어내야 한다. 

 

페이지테이블과 TLB에 저장되어 있는 정보는 구조가 조금 다르다. 페이지 테이블에는 하나의 프로세스를 구상하는 모든 페이지에 대한 주소 변환 정보가 페이지 번호에 따라 순차적으로 들어있다. 페이지 번호가 주어지면 테이블의 시작 위치에서 페이지 번호만큼 떨어진 항목에 곧바로 접근해 해당 페이지에 대응하는 프레임 번호를 얻을 수 있다. 

그러나 TLB는 프로세스의 모든 페이지에 대한 주소 변환 정보를 TLB가 가지고 있지 않기 때문에 페이지 번호와 이에 대한 프레임 번호가 쌍으로 저장되어 있어야 한다. 또한 TLB를 통한 주소 변환은 해당 페이지에 대한 주소 변환 정보가 TLB에 있는지 확인하기 위해 TLB의 모든 항목을 접근해야 하는 오버헤드가 발생한다. 이러한 오버헤드를 줄이기 위해 TLB의 구현에는 일반적으로 병렬탐색(parallel search: 한번의 TLB 접근 시간에 TLB 내의 모든 항목을 한꺼번에 조사할 수 있음)가 가능한 연관 레지스터(associative register)를 사용한다. 어쨌든 이렇게 TLB는 빠르고 TLB에서 검색 걸리면 물리적 메모리 주소로 가면 되니까 메인 메모리 접근은 1번뿐이다. 페이지 테이블은 프로세스마다 존재하며 TLB도 프로세스마다 다른 값이다 (context switch가 발생할 때 flush됨)

 

그러니까 정리하자면 TLB가 없다면 논리적 주소p 가지고 페이지 테이블(메인메모리 접근 1번) 접근 -> 물리적 주소f 획득 -> 물리적 메모리 주소 접근(메인메모리 접근 2번)

TLB에 있다면 논리적 주소 p가지고 TLB 검색 -> 물리적 주소f 갖고 물리적 메모리 주소 접근(메인 메모리 접근 1번)

 

<Effective Access Time> : 평균적인 메모리 접근 시간

메모리에 접근하는 시간이 1이고, 연관 레지스터에 접근하는 시간을 입실론이라고 하면, 입실론은 1보다 충분히 작은 값이 될 것이다. 한편 요청된 페이지에 대한 주소 변환 정보가 연관 레지스터에 존재할 확률(Hit ratio)은 알파라고 하면 평균적인 메모리 접근 시간은

 EAT = (1 + 입실론)알파 + (2 + 입실론)(1 - 알파) = 2 + 입실론 - 알파

(1 + 입실론)알파는 요청된 페이지 정보가 TLB에 있는 경우

(2 + 입실론)(1 - 알파) 는 요청된 페이지 정보가 TLB에 없는 경우

 

<계층적 페이징> Two-level Page Table

현대의 컴퓨터는 address space가 매우 큰 프로그램을 지원한다. 32bit address 사용 시 2 ^32(4gb)의 주소 공간을 갖는 프로그램을 지원할 수 있다. 이러한 환경에서 페이지 크기가 4kb 일 시, 4gb/4kb, 즉 1m개의 페이지 테이블 항목이 필요하게 된다. 각 페이지 테이블이 4byte씩을 필요로 한다면 한 프로세스 당 페이지 테이블을 위해 1m * 4 byte를 필요로 한다. 대부분의 프로그램은 4gb의 주소 공간 중 지극히 일부분만 사용하는데 page table 공간이 전체 메모리의 상당 부분을 잡아먹게 되어 실제로 사용 가능한 메모리 공간이 크게 줄어들게 된다. 따라서 페이지 테이블에 사용되는 메모리 공간의 낭비를 줄이기 위해 2단계 페이징(two level paging)을 사용한다. 

 

2단계 페이징 기법에서는 주소 변환을 위해 외부 페이지 테이블(outer page table),  내부 페이지 테이블(inner page table)로 이루어진 두 단계 페이지 테이블을 사용한다. 사용되지 않는 주소 공간에 대해서는 외부 페이지 테이블의 엔트리 값을 null로 설정하며 여기에 대응하는 내부 페이지 테이블을 생성하지 않는 것이다. 2단계 페이징 기법은 공간적으론 이득이지만 주소 변환을 위해 접근해야 하는 페이지 테이블의 수가 증가하므로 시간적 손해가 뒤따르게 된다.

 

2단계 페이징 기법에서는 논리적 주소를 두 종류의 페이지 번호 (p1, p2)와 페이지 오프셋 (d)로 구분한다. p1은 outer page table의 인덱스이고, p2는 inner page table의 인덱스이다. 따라서 먼저 외부 페이지 테이블로 p1만큼 떨어진 위치에서 내부 페이지 테이블의 주소를 얻고, 내부 페이지 테이블에서 p2만큼 떨어진 위치에서 요청된 페이지가 존재하는 프레임의 위치를 알게 되고, 마지막으로 해당 프레임(물리적 메모리)에서 d만큼 떨어진 곳에서 원하는 정보에 접근할 수 있게 된다.

 

address space가 더 커지면 다단계 페이지 테이블이 필요하게 된다.

각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 physical address 변환에 더 많은 메모리 접근이 필요할 것이다. TLB를 통해 메모리 접근 시간을 줄이고, 다단계 페이지 테이블을 통해 공간적으로도 이득을 볼 수 있다.

4단계 페이지 테이블을 사용하는 경우, 메모리 접근 시간이 100ns, TLB 접근 시간이 20ns 이고 TLB hit ratio가 98%인 경우 EAT는 0.98*120 + 0.02*520 = 128ns가 된다.

 

<Valid(v) / Invalid(i) bit in a Page Table> 메모리 보호

<Memory Protection>

한 프로세스의 주소 공간은 다른 프로세스에 의해 접근될 수 없으므로 누가 접근하는지 등 접근 권한을 설정할 필요는 없다. 각 페이지에 대해 어떻게 접근하는지의 정보가 보호비트에 저장되는 것이다. 

페이지 테이블의 각 entry마다 아래의 bit를 둔다.

* Protection bit

page에 대한 접근 권한(read/write/read-only)

* valid - invalid bit

valid는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함 (접근 허용)

invalid - bit 는 해당 주소의 frame에 유효한 내용이 없음*을 뜻함(접근 불허)

1. 그 프로세스가 그 주소 부분을 사용하지 않는 경우
2. 해당 페이지가 메모리에 올라와있지 않고 swap area(backing store)에 있는 경우

 

<Inverted Page Table> 역 페이지 테이블

페이지 테이블로 인한 메모리 공간의 낭비가 심한 이유는 모든 프로세스의 모든 페이지에 대해 페이지 테이블 항목을 다 구성해야 하기 때문이다. 대응하는 페이지가 메모리에 있든 아니든 간에 페이지 테이블에는 존재한다는 얘기다. 이 문제를 해결하기 위한 대안으로 역페이지 테이블(Inverted Page Table) 기법이 사용될 수 있다. 역페이지 테이블 기법은 물리적 메모리의 페이지 프레임 하나 당 페이지 프레임에 하나씩의 항목을 두는 방식이다. 물리적 주소에 대해 페이지 테이블을 만드는 것이라고 생각하면 된다. 프로세스마다 페이지 테이블을 두지 않고, 시스템 전체(system-wide)에 페이지 테이블을 하나만 두는 것을 말한다. 페이지 테이블의 각 항목은 각각의 물리적 메모리의 page frame이 담고 있는 내용을 표시한다. (process id, process 의 logical address) 

단점: 주소 변환 요청이 들어오면 그 주소를 담은 페이지가 물리적 메모리에 존재하는지 여부를 판단하기 이해 페이지 테이블 전체를 탐색해야 한다 따라서 시간적 오버헤드가 따름

조치: 테이블을 연관 레지스터(associative register)에 보관해 테이블 전체 항목에 대한 병렬 탐색(parallel search)를 가능하게 함으로써 시간적 효율성을 노린다. 

 

<shared page> 공유 페이지

shared code(re-entrant code, pure code)는 메모리 공간의 효율적인 사용을 위해 여러 프로세스에 의해 공통으로 사용될 수 있도록 작성된 코드를 말한다. 읽기 전용(read only)의 특성을 가진다. 공유 페이지란 공유 코드를 가지고 있는 페이지를 말한다. 공유 페이지는 여러 프로세스에 의해 공유되는 페이지이므로 물리적 메모리에 하나만 적재되어 메모리를 좀 더 효율적으로 사용할 수 있도록 한다. 프로세스 간에 하나의 code만 메모리에 올린다. 3개가 같은 프로그램 돌리고 있다면 code, data, stack의 code는 동일하다. 따라서 shared가 가능하다면 물리적 메모리에 1카피만 올리는 것이다. 예를 들어 문서 편집기 프로그램을 공유 페이지를 사용해서 작성한 경우, 이 프로세스를 여러 개 수행시키더라도 공유 코드를 담은 페이지는 메모리에 하나만 올라가고 여러 프로세스가 이 코드를 공유해서 사용되는 것이다. 공유 코드는 읽기 전용의 성질을 가져야 할 뿐만 아니라 동일한 로지컬 어드레스를 가져야 하는 제한 사항이 있다. 즉 공유 페이지는 그 페이지를 공유하는 모든 프로세스의 주소 공간에서 동일한 페이지 번호를 가져야 한다. 공유 페이지의 반대 개념은 사유 페이지(private page)라고 하는데 이것은 논리적 주소 공간에 아무곳에나 와도 된다.