메모리 관리

1. address binding 방법의 종류

1) compile time binding

- 코드를 컴파일을 할 때 address binding을 같이 하는 경우가 있다. 하나의 컴퓨터에 하나의 프로그램만 동작하게 하는 경우에 사용할 수 있는 방법으로, 멀티프로그래밍이 지원되는 현재 대부분의 컴퓨터에서는 쓰이지 않는 바인딩 방법이다.

2) load time binding

- 프로세스가 메모리에 처음 로드될 때 바인딩을 하는 방법

3) execution time binding(=run time binding)

- 프로세스는 메모리에 처음 로드된 뒤에도 swapper에 의해 swap space로 옮겨졌다가 나중에 다시 프로세스를 실행시킬 필요가 생겨 그때 메모리로 돌아올 수 있는데, 그때마다 바인딩을 새로 할 수밖에 없다. 이처럼 프로세스가 실행될 때 바인딩을 하는 것을 execution time binding(=run time binding)이라 한다.

2. MMU의 작동 방식

1) CPU가 현재 메모리에서 불러오고자 하는 데이터의 logical address를 MMU로 전달한다.

2) MMU는 일단 그 주소가 현재 CPU를 점유하는 프로세스의 메모리 점유 범위(이를 저장하고 있는 레지스터를 limit register라 한다)를 벗어나는지를 확인한다.

- 벗어나는 경우: trap을 발생시킨다.

- 벗어나지 않는 경우: 전달받은 logical address에 현재 MMU에 저장된 그 프로세스의 시작 부분의 물리적 주소값(이를 저장하고 있는 레지스터를 relocation register 또는 base register라 한다)을 더해 메모리 상의 그 위치의 데이터를 가져온다.

3. 프로세스를 메모리에 로드하는 방법 유형

1) overlay

- 프로그램의 코드에 의해, 프로세스의 전체 데이터 중 현재 당장 필요한 부분만을 메모리에 로드하는 방법. 과거 메모리가 너무 작아 프로세스 전체를 메모리에 모두 로드하는 것이 불가능할 때, 프로그래머가 코딩을 할 때 프로세스를 쪼개 ‘지금 이 부분만 메모리에 로드한다’ 하는 명령어를 써가며 프로그램을 만드는 경우가 많았다. 이처럼 프로그래밍 때 프로그래머가 직접 프로세스의 일부만을 메모리에 로드하도록 해 이를 통해 프로세스를 메모리에 로드하는 것을 overlay라 한다.

- 프로그래머가 직접 메모리에 상주할 부분과 overlay할 부분을 나누어 설계해야 했기에 구현 난이도가 아주 높은 방법이다.

2) dynamic load

- 프로세스의 전체 데이터를 일시에 메모리에 로드하지 않고, 현재 당장 필요한 부분만을 메모리에 로드하는 방법으로, 이 역시 프로그램 코드를 통해 프로세스의 전체 데이터 중 일부를 메모리에 로드하는 방법이다. overlay와 유사하나 좀더 나중의 방법으로서, 코드 길이는 방대하나 사용 빈도는 다소 떨어지는 예외처리 같은 코드를 사용할 때 흔히 쓰였다.

3) swapping

- swapper를 사용하여, 우선순위가 낮은 프로세스를 swap out하고 우선순위가 높아진 프로세스를 swap in 하는 식으로 메모리를 관리하는 방법.

- 보통 디스크에서 메모리로 파일 내용을 전송할 때 걸리는 시간은 데이터의 길이보다는 데이터의 위치를 탐색하는 데 걸리는 시간이 훨씬 더 오래 걸리지만(디스크 헤드가 움직이는 시간이 그만큼 길기 때문), paging이 없는 경우 swap in - swap out 과정에서 전송되는 데이터 양은 디스크에서 파일 내용을 전송하는 경우보다 훨씬 많으므로 paging 없는 swapping의 swap 시간은 swap space에서 메모리로 전송되는 프로세스 데이터의 길이에 비례한다.

* dynamic linking

- 코드를 컴파일하면 메모리 이곳저곳에 컴파일된 결과 파일들이 흩어져 있을 수 있는데(특히 코드가 외부 라이브러리를 사용하는 경우), 이처럼 흩어져 있는 컴파일 결과들을 하나로 묶어 하나의 실행파일로 만드는 것을 linking이라 한다.

- 프로그램의 코드에 남이 만든 라이브러리 코드가 포함된 것을 static linking이라 한다. static linking은 라이브러리를 많이 사용할수록 실행파일 크기가 커지는데, 어차피 남이 만든 라이브러리를 사용하는데 이를 프로그램을 만들 때마다 일일이 프로그램 코드에 포함시켜 컴파일을 하게 된다면 여러 프로세스가 동일한 코드를 중복해서 갖고 있게 된다. 이러한 프로세스들이 모두 동시에 메모리에 로드되게 된다면 이는 큰 메모리 자원 낭비가 될 것이다.

- 반대로, 라이브러리가 프로그램의 코드에 직접 포함되지 않고 별도의 독립된 파일로 존재하여 프로그램이 메모리에 로드된 후 필요할 때에만 이 파일에 접근해서 필요한 코드를 실행하게 한다면, 여러 프로세스가 같은 라이브러리를 사용한다 하더라도 메모리 낭비가 일어나지 않을 것이다. 이를 ‘linking이 프로세스의 실행 시에만 일어난다’ 하여 dynamic linking이라 한다.

- Linux의 .so 파일, Window의 .dll 파일이 dynamic link를 지원하기 위해 존재하는 파일이다.

4. 메모리 주소 할당 방법 1: 프로세스를 쪼개지 않고 메모리 상의 연속적인 영역에 할당

1) 고정분할

- 메모리를 정해진 크기로 나누고, 프로세스를 로드할 때 특정 메모리 영역의 크기가 그 프로세스보다 클 때 그곳에 프로세스를 할당하는 방법이다.

- 로드된 프로세스의 크기가 너무 커서 나뉜 메모리 영역에 할당되지 못한 경우 그 영역을 ‘외부 조각’이라 한다. 반대로, 나뉜 메모리 영역이 너무 커서 그 영역 내에 프로세스가 할당되었음에도 채워지지 않은 영역이 있는 경우 그 영역을 ‘내부 조각’이라 한다.

2) 가변분할

- 특별히 메모리를 정해진 크기로 나누거나 하지는 않고 그냥 프로세스를 메모리의 빈 영역에 되도록 빈틈 없이 차례대로 할당하는 방법이다. 메모리를 정해진 크기로 나누거나 하지 않고 되도록 빈틈 없이 프로세스를 할당하므로, 고정분할 방식의 ‘내부 조각’ 같은 개념은 존재하지 않는다. (그러나 외부 조각 개념은 있다. 먼저 로드된 프로세스가 종료될 경우 그 메모리 영역은 텅 빈 공간이 되지만, 그 다음으로 로드된 프로세스의 크기가 그 공간보다 크다면 그 프로세스는 그 영역에 할당될 수 없다. 이때 이렇게 빈 공간으로 남는 영역이 가변분할에서의 외부 조각이다.)

- 프로세스를 할당할 영역을 찾는 알고리즘은 일단 모두 메모리의 앞 주소부터 차례대로 훑기 시작한다는 점이 같다. 이때 (1)적절한 공간이 나타나면 곧바로 그곳에 할당하는 알고리즘(first fit), (2)전체 빈 공간 개수를 모두 비교하여, 그 프로세스가 들어갈 수 있으면서 크기가 가장 작은 공간에 할당하는 알고리즘(best fit), (3)크기가 가장 큰 공간에 프로세스를 할당하는 알고리즘(worst fit) 세 가지가 있다. 둘 이상의 프로세스를 할당한다 할 때, worst fit보다 first fit이나 best fit 알고리즘이 속도, memory utilization 측면에서 더 효과적이라는 사실이 알려져 있다.

• 프로세스가 로드됐다 종료되는 일이 반복되면, 전체 외부조각의 크기를 합하면 메모리에 여유 공간이 충분한데도 불구하고 외부조각들이 서로 떨어져 있기 때문에 더 이상 메모리에 프로세스가 로드되지 못하는 경우가 발생할 수 있다. 이를 외부 단편화(external fragmentation)라 한다. 이를 해결하려면 메모리에 로드돼 있는 프로세스들에 할당된 메모리 영역을 한 군데로 몰아 외부조각의 크기를 커지게 해야 하는데(이를 compaction이라 한다) 굉장히 큰 overhead가 발생하여(프로세스를 최소한으로 이동하는 알고리즘을 생각할 수 있지만 이 역시 실제 구현에는 곤란한 점이 많다) 이 방식을 사용하는 데는 어려운 점이 있다.

5. 메모리 주소 할당 방법 2: 프로세스를 여러 조각으로 나누어 각 조각을 메모리 상의 빈 공간 구석구석에 할당

1) paging

(1) 개요

- 가상메모리 상의 프로세스를 균일한 크기의 page로 자른 후(보통 4KiB), 일부는 디스크에 그대로 두고 필요한 내용은 메인 메모리의 곳곳에 page 단위로 불연속적으로 나누어 프로세스를 저장하는 방법. 이의 구현을 위해 메인 메모리 역시 page와 같은 크기로 분할하며, 분할된 각 단위를 frame이라 부른다. 즉, 가상메모리의 프로세스의 한 page는 메인 메모리의 한 frame에 올라가게 된다. (이로써 external fragmentation 문제는 발생할 여지가 사라진다. 단, 프로세스의 크기가 딱 4KiB 단위로 나눠떨어지는 것은 아니므로, internal fragmentation 문제는 발생하는 경우가 있다.)

- 메인 메모리의 주소값 하나에 해당하는 메모리의 크기는 1B고, 32비트 CPU - OS 체제에서 표현할 수 있는 메모리 주소값의 총 개수는 \(2^{32}\)개이므로, 32비트 CPU - OS 체제에서 하나의 프로세스에 할당되는 최대 메모리 용량은 4GiB이다(현재 널리 쓰이는 AMD64 CPU - 64비트 OS 체제에서는 256TiB까지 늘어난다). 이를 4KiB로 나누면 \(2^{20}\)이 되므로, 32비트 CPU - OS 체제에서 프로세스 하나는 최대 약 백만 개의 page로 나뉘게 된다. 즉, 위에서 언급한 방식대로 각 page마다 base register를 사용해 address binding을 하면 레지스터가 약 백만 개가 필요하게 된다. 레지스터는 가격이 많이 나가는 자원이라 그런 식으로 MMU를 만들지는 않으며, 보통 각 page의 메모리 내 위치를 32비트 정수로 담아 이를 표의 형태로 메모리에 저장한다(이 표를 page table이라 한다). page 하나의 메모리 내 주소값을 32비트(=4B) 정수로 표현한 것을 백만 개 모은 것이므로, page table이 차지하는 메모리 내 용량은 최대 4MiB이다.

- paging을 구현하기 위해 실제로 MMU에 저장되는 값은 그 프로세스의 page table이 시작하는 메모리 내 주소값과 page table의 크기이다. 이를 저장하는 레지스터를 각각 PTBR(page-table base register)과 PTLR(page-table length register)라 한다. logical address에서 그 logical address에 해당하는 실제 메인 메모리 상의 주소로 접근할 때에는 이 값을 이용하여 2단계 접근을 하게 된다. (MMU에서 page table의 위치를 찾아내고, 메인 메모리의 page table에 접근해 현재 logical address에 해당하는 page의 메인 메모리 상의 주소를 찾아내야 비로소 그 logical address의 physical address를 알 수 있다.)

- 메모리 주소값 하나에 해당하는 메모리의 크기가 1B라 했으므로, 크기가 4KiB인 page가 담고 있는 메모리 주소값의 총 개수는 \(2^{12}\)개이다. 또, page table의 총 엔트리 개수는 약 백만 개(\(2^{20}\))라 했으므로, 결국 paging을 하더라도 표현할 수 있는 주소값의 총 개수는 변하지 않는다.

(2) TLB

- 2단계 접근은 메인 메모리 주소값으로 그 주소값에 저장된 값을 꺼내는 작업을 2회 반복해 시간이 다소 걸리는 작업이므로, 보통 translation lookaside buffer(TLB)라는 고속 associative cache를 사용하여 최근에 탐색한 page 번호의 메모리 상의 주소를 cache에 저장해 두는 식으로 속도를 개선한다. (여러 프로세스의 page table을 담당하는 TLB는 컴퓨터 시스템에 하나뿐이므로, context switch 때마다 TLB에 저장된 내용 역시 flush된다. 이는 context switch의 오버헤드가 늘어나는 한 원인이 된다.)

- TLB를 사용하는 경우 평균적으로 logical address를 통해 메인 메모리 상의 값을 꺼내오는 데 걸리는 시간을 얼마나 줄일 수 있는지 계산해볼 수 있다. 메인 메모리의 주소값을 알 때 그곳에 저장된 값에 접근하는 데 걸리는 시간을 1, TLB의 값 하나에 접근하는 시간을 \(\epsilon\), 전체 page 개수 중 TLB에 저장돼 있는 page 주소에 접근하게 되는 비율(TLB hit ratio)을 \(\alpha\)라 하면, CPU가 logical address로 메인 메모리 상의 값을 꺼내오는 데 걸리는 평균 시간은 \((1+\epsilon)\cdot \alpha + (2+\epsilon)\cdot (1-\alpha)\) 이다.

- 예를 들어 i번 page의 메인 메모리 상의 주소는 page table의 i번 엔트리에 저장돼 있어 그 값을 읽어내는 데 임의 접근이 가능하지만, TLB의 각 값은 크기순으로 있는 게 아니어서 그러한 임의접근이 불가능하다. 그러나 TLB는 병렬탐색이 지원되므로, 원하는 값에 아주 빠른 시간 내에 접근이 가능하다. (따라서 위 식의 \(\epsilon\)은 1보다 훨씬 작은 값을 갖는다.)

(3) 2단계 page table

- 32비트 CPU - OS 체제에서 하나의 프로세스가 가상 메모리에서 차지하는 메모리의 크기는 최대 4GiB이지만, 그 메모리의 크기 중 실제로 유효한 값이 저장돼 있는 영역의 크기는 그에 비하면 훨씬 좁다. 따라서 page table을 4MiB나 사용하는 것은 큰 낭비에 해당한다. 그러나 그렇다고 해도 임의접근을 해야 하는 page table의 특성 상, 그 부분만 따로 빼고 page table을 만드는 것도 불가능하다. 이때, page table이 저장된 영역을 다시 page로 나누어 그에 대한 page table을 별도로 두고(이를 outer page table이라 한다), inner page table의 page가 가리키는 가상 메모리 영역의 값이 null이라면 그러한 주소들을 담고 있는 inner page table 영역을 만들지 않고 그런 영역을 가리켜야 할 outer page table이 null을 가리키도록 해 전체 page table이 차지하는 메모리 내 크기를 크게 줄일 수 있다. (참고로 outer page table이 차지하는 메모리 내 영역의 크기는 최대 4KiB에 불과하다.)

- outer page table의 엔트리 수는 최대 1024개이고, outer page table의 각 page에 담기는 inner page table의 엔트리 수 또한 최대 1024개이다. 크기가 4KiB인 page가 담고 있는 메모리 주소값의 총 개수는 \(2^12\)개라 했으므로, 결국 2단계 paging을 하더라도 표현할 수 있는 주소값의 총 개수는 변하지 않는다.

(4) multilevel paging

- page의 크기가 아주 작거나 프로세스의 크기가 아주 커지면 page table을 여러 개 사용해서 아낄 수 있는 메모리 크기가 더 커질 수도 있다. 다만 page table이 늘어날 때마다 TLB에 없는 메모리 주소에 접근할 때 드는 시간이 그만큼 늘어날 수밖에 없다.

- TLB hit ratio가 충분히 높다면, 메모리에서 값을 얻어오는 데 걸리는 평균적인 시간이 page table을 적게 쓰는 경우보다 그렇게 크게 증가하지 않을 수 있다. 예를 들어 page table을 4개 쓰는데 TLB hit ratio가 0.98, TLB 접근 시간이 0.2인 모델에서 메모리에서 값을 얻어오는 데 걸리는 평균적인 시간은 \(1.2\cdot 0.98 + 5.2\cdot0.02 = 1.28\)로 page table을 하나만 쓸 때에 비해 불과 0.08만큼만 증가할 뿐이다.

(5) inverted page table

- 지금까지 프로세스를 page 단위로 분할한 것을 page table의 엔트리로 하는 방법에 관한 내용이었다면, inverted page table은 거꾸로 메인 메모리의 각 frame을 page table의 엔트리로 하는 page table이다. 프로세스마다 page table을 두면 프로세스가 너무 많이 로드되면 그만큼 각 프로세스가 차지하는 page table의 크기가 커질 것이지만, inverted page table을 사용하면 page table을 하나만 두면 되므로 page table이 차지하는 메모리 내 크기를 획기적으로 줄일 수 있다.

- inverted page table의 각 엔트리는 그에 해당하는 메인 메모리의 frame에 올라가 있는 page의 프로세스 ID와 page 번호가 저장된다. address binding을 할 때에는 현재 CPU를 점유하는 프로세스의 ID와 현재 호출하려는 logical address의 page 번호를 갖고 그 page가 올라가 있는 frame을 page table에서 탐색을 하며, 그 frame을 찾았으면 그 frame의 page table 내에서의 인덱스를 통해 그 frame의 메인 메모리에서의 주소를 알아낸다. (프로세스 ID와 page 번호만 갖고 그 page가 있는 frame의 page table 내 위치에 임의로 접근할 수 있는 방법이 없으므로 인덱스를 알아내려면 원칙적으로는 순차탐색을 할 수밖에 없으나, 병렬탐색이 지원되는 associative cache 하드웨어를 사용함으로써 순차탐색보다 빠른 시간 내에 원하는 frame을 찾아내게 된다. associative cache는 값이 비싸므로 page table이 커질수록 나가는 비용이 커진다.)

(6) shared page

- 프로세스가 가진 데이터 중 여러 프로세스가 공유하는 부분이 있을 수 있다. 특히 code 부분을 여러 프로세스가 공유하는 경우가 많으며, 이때 공유되는 code를 re-entrant code 또는 pure code라 한다.

- 여러 프로세스에서 공유하는 pure code 부분은 각 프로세스 내 logical address가 동일한 부분에 위치해야 한다. code에 기록돼 있는 logical address는 컴파일 된 이상 변경되지 않으므로, 각 프로세스의 pure code가 갖는 logical address가 서로 달라진다면 오작동이 일어날 수밖에 없다.

2) segmentation

- paging이 균일한 크기의 page를 기준으로 프로세스를 잘랐다면, segmentation은 프로세스의 데이터 영역을 각 영역의 ‘의미’를 기준으로 구분하여 그 의미 단위로 프로세스를 자르는 방법이다. 크게는 code, data, stack을 각각 구분하여 프로세스를 나눌 수도 있고, 작게는 함수, 변수 같이 자그마한 단위로 프로세스를 나눌 수도 있다.

- 의미를 기준으로 segment를 나눌 경우 다음 장점이 있다.

• 메모리 영역의 권한을 설정하는 데 paging과 달리 충돌 문제가 발생하지 않는다. 예를 들어, 프로세스의 code 영역은 read only로 권한이 설정돼야 하나 data 영역은 read/write로 권한이 설정돼야 한다. 이들이 한 page에 들어있으면 그 page의 권한을 설정하는 데 문제가 발생하나, segmentation에서는 한 segment 내 데이터는 모두 code이거나 모두 data이므로 이 문제에서 자유롭다.

• 메모리 영역을 공유하는 데 있어 paging과 달리 불필요한 데이터 영역이 공유되는 일을 막을 수 있다. 예를 들어, 프로세스의 code 영역은 공유해서 얻는 이익이 크지만 data 영역은 프로세스들이 공유하면 문제가 생길 수 있다. 이들이 한 page에 들어있으면 그 page를 공유하는 경우 문제 발생 여지가 있으나, segmentation에서는 code가 담긴 segment만 공유할 수 있으므로 이 문제에서 자유롭다.

- paging에서 page table이 있듯 segmentation에서는 segment table이 있다. (대개의 경우 segment의 크기가 10을 넘지 않아 page table보다 사용하는 메모리의 크기가 훨씬 적다.)

• paging에서는 모든 page의 크기가 균일하나 segmentation에서는 모든 segment의 크기가 서로 다르기 때문에 segmentation에서는 (1)external fragmentation이 발생하며 (2)segment table에는 각 segment의 base뿐 아니라 limit도 함께 저장해야 한다.

• paging의 경우 MMU에 PTBR와 PTLR이 있었는데, segmentation의 경우 STBR와 STLR이 있다.

3) segmentation with paging

- segment 단위로 프로세스를 자르되, 잘린 segment 내부 영역을 다시 page 단위로 잘라 각 segment마다 page table을 할당하는 방법이다. 각 page에는 의미적으로 동일한 내용만 담기게 되므로, paging의 장점을 취하면서 동시에 segmentation의 장점도 취할 수 있다.