[Operating Systems] Memory Management

일단 메모리 관리의 필요성은 멀티프로세싱과 함께 출발한다.
멀티 프로세싱으로 인해 여러개의 메모리 공간을 필요로 하기 때문에 적절한 메모리 관리가 필요해진다.

우선 프로세스에게는 메모리가 여러 프로세스에 의해 공유되고 있다는 사실이 드러나서는 안되는 투명성(transparency)을 가져야 한다. 이것은 relocation을 이용해 각 프로세스마다 저장된 위치를 접근할 수 있도록 한다.
일반적으로 이 리로케이션은 실행 시간에 이루어지며, 하드웨어 서포트가 필요하다.
즉 MMU(Memory Management Unit)라는 하드웨어 모듈에 의해 프로그램이 바라보는 논리적 주소(Logical Address, Virtual Address)가 실제 하드웨어에 있는 물리적 주소(Physical Address)로 변경되게 된다.

또한 각 프로세스의 메모리 영역과, OS의 영역은 보호되어야 하는데 그 Protection은 Base레지스터와 Limit 레지스터를 이용해서 구현될 수 있는데 Base레지스터는 어떠한 프로세스의 Address Space의 시작 부분을 가리키며 Limit 레지스터는 크기를 나타낸다. 따라서 해당 범위 내에서의 주소만을 접근하도록 하면 Protection이 이루어 질 수 있다.

Base와 Limit 레지스터는 Context Switching 시 변경되게 될 것이다.
이것의 장점은 동적으로 address space 영역을 relocation 할 수 있다는 것과 여러 address space 간 protection을 제공한다는 점, 저렴하고 빠르게 구현될 수 있다는 것 등이 있다.
하지만 단점으로는 실제 메모리에 연속적으로만 할당되어야 하고 사용되지 않는 메모리 부분이라도 할당되어야 한다.
또한 여러 프로세스의 메모리 영역을 공유할 수도 없을 것이다.

여튼 한정된 공간에서 여러개의 프로세스를 실행하다 보면 메모리 영역이 부족할 수 있으므로 그 경우에는 하나의 victim 프로세스를 선정하고 그것을 backing store에 저장한 후 새로운 프로세스의 메모리를 할당한다. 이 과정을 swapping 이라 한다.

그럼 이러한 프로세스들을 실제 피지컬 메모리에 어떻게 할당할 것인가에 대한 문제가 있다.
우선 Contiguous Memory Allocation이라 해서 연속적으로 메모리에 할당하는 방법을 이용한다.
이 방법을 사용하면 차곡차곡 메모리 공간을 할당하게 된다.
하지만 큰 단점이 있는데 메모리 공간을 사용하는 프로세스가 종료되고 그 자원을 반납하면 그 크기만큼 메모리에 hole이 생긴다.
따라서 external fragmentation 현상이 생긴다. 실제 메모리가 가지고 있는 free 공간은 주어진 크기만큼을 할당하기에 충분하지만 연속적이지 않기 때문에 할당할 수 없는 것이다. 이것은 compaction이라는 방법을 이용해서 메모리를 땡길 수 있는데 부가적인 연산이 필요하고 이 과정중에는 작업을 할 수 없으므로 비효율적이다.
(internal fragmentation은 실제 요청한 크기보다 약간 크게 할당되어 내부적으로 사용될 수 없는 공간이 생기는 것을 말한다)

따라서 이 문제를 해결하기 위해 나온 것이 Paging 기법이다.
Paging 기법은 physical memory를 frame이라는 동일한 크기를 가지는 단위로 나누고, logical memory를 page라는 frame과 같은 크기를 가지는 단위로 나눈다. 그리고 프로세스 별로 페이지를 할당해 주는 것이다. 이방법을 이용하면 external fragmentation 문제를 해결할 수 있다. internal fragmentation이 생기기는 하나 무시할수 있는 수준이다.

그래서 각 OS 별로 page table을 관리하는 방법이 다양하게 생기며 일반적으로 각 프로세스는 메모리에 page table을 두고 PCB 내부에 page table pointer를 가지며 그것을 이용해 페이지 테이블을 접근한다. 이 방법을 사용하면 어떠한 메모리의 값에 접근하려면 페이지 테이블 한번, 데이터 얻으려 한번 이렇게 두번 접근을 해야하는 비효율성이 생긴다. 따라서 locality를 적용한 TLB를 사용한다.
TLB(Translation Look-aside Buffer)는 자주 사용되는 페이지 테이블 엔트리를 저장해 놓아서 비효율성을 조금이라도 줄이려는 것이다. 이 경우 실제 접근 시간인 Effective Access Time을 계산했을 때 TLB를 사용하지 않았을 때 보다 더 좋은 결과를 보여준다.

이러한 페이지 테이블을 여러 방식으로 구현할 수 있다.
각 주소마다 하나의 엔트리에 보관하다 보면 페이지 테이블의 크기가 매우 커지는 문제가 생길 수 있다. 따라서 여러 단계(일반적으로 두 단계를 사용한다)의 페이지 테이블을 이용하여 접근하고 또 접근하는 식으로 관리하면 더 효율적으로 관리하게 되는데 이 방법을 Hierarchical Page Tables 방식이라 한다.

또한 hash function을 이용하고 동일한 해싱값이 나오면 chain을 달아서 접근하도록 하는 방법을 Hashed Page Table이라 하며
시스템 자체에 하나의 테이블을 가지고 pid와 page number값을 이용하여 엔트리를 접근하는 것을 inverted Page Table이라고 한다.