Memory Management(3)

Buddy System (1)

버디 시스템(Buddy System)은 메모리 할당 및 해제를 위한 효율적인 방법 중 하나입니다. 주 메모리를 고정 크기의 블록으로 분할하고, 각 블록은 이진 트리 구조로 관리됩니다. 버디 시스템은 외부 단편화를 피하면서 메모리를 효율적으로 관리할 수 있는 장점이 있습니다.

A reasonable compromise to overcome disadvantages of both fixed and dynamic partitioning schemes. 버디 시스템이 효율적일 지라도, 현대 운영체제에서는 페이징과 세그멘테이션을 기반으로한 가상 메모리가 버디 시스템을 능가한다. 

그러나, 이 버디 시스템은 UNIX SVR4(and also in Linux)에서 사용된다 for kernel memory allocation.

 

두 개의 버디(buddy)는 둘 다 할당되지 않은 상태가 되면 합쳐집니다. 블록의 주소와 크기가 주어지면, 버디의 주소는 자동으로 결정됩니다. 블록과 버디의 주소는 정확히 한 비트 위치만 다릅니다.

 

불연속 할당 기법

• page
• segmentation
• paged segmentation

Paging (1)

페이징기법이란 프로세스의 주소공간을 동일한 크기의 페이지 단위로 나누어 물리적 메모리의 서로 다른 위치에 페이지들을 저장하는 방식이다.

페이징 기법에서는 물리적 메모리를 페이지와 동일한 크기의 프레임으로 미리 나누어둔다. 이는 메모리에 올리는 단위가 동일한 크기의 페이지 단위이므로, 메모리를 같은 크기로 미리 분할해두더라도 빈 프레임이 있으면 어떤 위치이든 사용될 수 있다. 따라서 페이징 기법은 앞서 연속할당 방식에서 발생했던 동적 메모리 할당 문제가 발생하지 않는다는 장점이 있다. 

Principles

프로세스의 물리적 주소 공간은 연속적이지 않을 수 있습니다. 물리 메모리를 고정 크기의 블록인 프레임(frames)으로 분할합니다. (크기는 2의 거듭제곱으로, 일반적으로 512바이트에서 8192바이트 사이입니다.).논리 메모리를 동일한 크기의 블록인 페이지(pages)로 분할합니다. 모든 빈 프레임을 추적합니다. n 페이지 크기의 프로그램을 실행하기 위해서는 n개의 빈 프레임을 찾아서 프로그램을 로드해야 합니다. 논리 주소를 물리 주소로 변환하기 위해 페이지 테이블을 설정합니다.내부 단편화 가능성이 있습니다.

Paging (2)

프로세스의 가상 주소 공간은 동일한 크기의 pages로 분할 된다. 가상 (logical) 주소는 a pair(p, o). p - page number, o - page offset

Paging (3)

물리적 메모리는 동일한 크기의 frames로 분할 된다. - Size of page = size of frame

물리적 메모리 주소는 a pair (f, o). f - frame number, o - frame offset

Paging (4)

Pages are mapped to frames. 페이지는 가상 주소 공간에서 연속적이다 하지만 The corresponding frames are arbitrarily located in physical memory. All pages are not necessarily mapped to frames

 

Virtual Address Translation

  페이징기법에서는 주소변환 절차가 연속할당 방식에 비해 다소 복잡하다. 하나의 프로세스라도 페이지 단이로 물리적 메모리에 올리는 위치가 상이하므로, 논리적 주소를 물리적 주소로 변환하는 작업이 페이지 단위로 이루어져야하기 때문이다. 그러므로 프로세스의 몇 번째 페이지가 물리적 메모리의 몇 번째 프레임에 들어있다는 페이지별 주소 변환 정보를 유지해야한다. 그래서 페이징 기법에서는 모든 프로세스가 각각의 주소 변환을 위한 페이지 테이블을 가지며, 이 테이블은 프로세스가 가질 수 있는 페이지의 개수만큼 주소 변환 엔트리를 가지고 있게 된다. 페이지 테이블은 가상 페이지를 물리적 프레임으로 map 한다. (A Page table maps virtual pages to physical frames.)

 

  페이징 기법에서는 프로세스의 주소 공간과 물리적 메모리가 모두 같은 크기의 페이지 단위로 나누어지기 때문에 빈 공간은 어느 곳이든 활용할 수 있다. 따라서 메모리상의 가용 공간의 크기가 작아서 빈 공간임에도 활용되지 못하는 외부조각 문제가 발생하지 않는다.

Page Table Implementation

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

• Page-table base register points to the page table(페이지 테이블의 시작 위치를 가리킨다.)
• Page-table length register indicates size of the page table(페이지 테이블의 크기를 보관한다.)

Memory acccess overhead - 페이징 기법에서의 메모리 접근은 주소 변환을 위한 페이지 테이블에 접근하는 것과, 변환된 주소에서 실제 데이터에 접근하는 것, 이렇게 두번의 메모리 접근이 필요하다. 따라서 메모리에 한번 접근하기 위해 매번 메모리에 두번 접근해야하는 오버헤드가 발생 -> solution: 오버헤드를 줄이고 메모리의 접근 속도를 향상시키기 위한 TLB(Translation Look-aside Buffer)라고 불리는 고속의 주소 변환용 하드웨어 캐시

TLB의 구현에는 일반적으로 병렬탐색(parallel search)이 가능한 연관 레지스터(associative register)를 사용한다. 병렬탐색이란 TLB내의 모든 항목을 동시에 탐색할 수 있는 기능 -> 한 번의 TLB 접근 시간에 TLB내의 모든 항목을 한꺼번에 조사함으로써 주소 변환 정보가 TLB에 있는지 곧바로 확인할 수 있게 되는 것.

 

연관 레지스터를 사용할 때 평균적인 메모리 접근시간(Effective Access Time: EAT)이 얼마나 걸리는지 확인해보자. 메모리에 접근하는 시간을 1이라 하고, 연관 레지스터에 접근하는 시간을 E 이라고 하면, E은 1보다 충분히 작은 값이 될 것. 한편 요청된 페이지에 대한 주소 변환 정보가 연관 레지스터에 존재할 확률을 a라고 하면 평균적인 메모리 접근 시간은 EAT = 2 + E - a

Handling Large Page Table

while a process is running, its page table must be in physical memory in its entirety. Only need to map the portion of the address space actually being used (a tiny fraction of entire address space)

 

Approaches  - Multi-level paing, Hashed page table, inverted page table

 

• Two-Level Paging 

페이지 테이블에 사용되는 메모리 공간의 낭비를 줄이기 위해 2단계 페이징 기법을 사용한다. 이 기법에서는 주소 변환을 위해 외부 페이지 데이블과 내부 페이지 테이블의 두 단계에 걸친 페이지 테이블을 사용한다. 한편, 2단계 페이징 기법을 사용할 경우 페이지 테이블을 위해 사용되는 메모리 공간을 줄여 공간적인 이득을 볼 수 있지만, 주소 변환을 위해 접근해야하는 페이지 테이블의 수가 증가하므로 시간적인 손해가 뒤따른다.

 

• Hashed Page Table

The virtual page number is hashed into a page table. This page table contains a chain of elements hashing to the same location. Virtual page numbers are compared in this chain searching for a match. If a match is found, the corresponding physical frame is extracted.

 

• Inverted Page Table

One entry for each real page of memory (frame) - Only one page table in the system

페이지 테이블로 인한 메모리 공간의 낭비가 심한 이유는 모든 프로세스의 모든 페이지에 대해 페이지 테이블 항목을 다 구성해야 하기 때문이다. 이를 해결하기 위한 방법으로 역페이지 테이블 기법이 있다. 이 역페이지 테이블 기법은 논리적 주소에 대해 페이지 테이블을 만드는 것이 아니라, 물리적 주소에 대해 페이지 테이블을 만드는 것이다. 즉, 각 프로세스마다 페이지 테이블을 두지 않고, 시스템 전체에 페이지 테이블 하나만을 두는 방법이다.

역페이지 테이블에 주소변환 요청이 들어오면, 그 주소를 담은 페이지가 물리적 메모리에 존재하는지 여부를 판단하기 위해 페이지 테이블 전체를 다 탐색해야하는 어려움이 있다 -> 상당한 시간 소요 

Decreases memory needed to store each page table, but increases time needed to search the table when a page reference occurs.

Page Sharing

공유 - 서로다른 프로세스의 페이지가 동일한 프레임에 매핑되는것을 말한다.