서론
Virtual Memory를 통해, 우리는 Process가 필요한 부분만 Main Memory에 올려 사용이 가능하다는 것을 알았다. 그런데, Process는 여전히 Main Memory를 사용해야 하고, 우리는 Main Memory를 효율적으로 관리해야 한다. Process마다 사용해야 하는 Memory의 크기는 다르므로, 우리는 Main Memory를 Variable Partition으로 나누어 Process에게 할당을 한다.
모든 Process는 동시에 종료되는 것이 아니기에, Variable Partition으로 나누게 되면 필연적으로 hole이 생기게 된다. Memory는 효율적으로 관리되어야 하기 때문에, 새로운 Process를 어떤 hole에 집어넣어 사용할지 정하는 방법에는 3가지가 있다.
- first-fit
첫 번째 사용 가능한 가용 공간을 할당한다. 처음부터 탐색을 할 수도 있고, 저번에 탐색을 종료하였던 곳부터 시작할 수도 있다. - best-fit
필요로 하는 메모리의 용량보다 큰 가용공간중에 가장 작은 것을 채택한다. - worst-fit
가장 큰 가용공간을 할당한다.
3번의 worst-fit이 얼핏보면 worst-choice가 될 수 있다고 생각이 들 수 있다. Worst-fit을 사용하게 되면, 가장 큰 공간에 process를 할당하게 되는데, 이 때, 남은 공간이 다른 process를 배정할 수 있을 정도로 클 가능성이 있다.
1~3번 방법 중 어떠한 방법을 사용하더라도 "hole"은 여전히 존재할 수밖에 없다. 이러한 경우의 hole을 External Fragmentation 이라고 한다.
일반적으로, OS는 Memory를 일정 크기로 분할을 하고, Process가 Memory를 요청을 하면 분할한 부분의 정수배를 process에게 나누어 주는데, Process가 원하는 memory의 크기가 이 정수배로 딱 떨어지지 않아 남는 부분이 존재할 수 있다. 이 경우의 hole을 Internal Fragmentation 이라고 한다.
Paging
External Framentation은 process의 physical Address가 연속되었기 때문에 발생했다고 볼 수 있다. Paging은 이러한 문제를 해결하기 위해 만든 Process의 physical Address가 연속되지 않아도 되는 메모리 관리 기법이다.
Method
Physical Memory는 frame 이라는 같은 크기의 블록으로 나뉘어지고, Virtual Memory는 page 라는 같은 크기의 블록으로 나뉘어지고, page의 크기는 frame의 크기와 적확하다. 이 부분이 Paging 작동 방법의 핵심이라고 볼 수 있다.
Logical Address를 page number(p), page offset(d)로 나눈다. 이를, p번째 page의 d번째 명령 이라고 생각을 하는 것이다. d는 그대로 내버려두고, p를 page table로 가져간다. 그다음에, page table의 p번째 element를 가져온다. page table을 table 이라고 하면, table[p] 에는 p번째 page에 대응하는 frame의 주소(f)를 갖고있다. 다시, f와 d를 이어, physical address를 구하게 된다.
Frame 관리를 위해서는 어느 process가 어느 frame을 사용하고 있는지, 어느 frame이 사용 가능한지를 인지하고 있어야 한다. 이는 Frame Table이라는 시스템에 단 하나 존재하는 자료구조에 저장을 한다.
Problem
이러한 Paging에는 단점이 하나 존재한다. Page table이 Main Memory에 있다는 점이다. 즉, Logical Address를 Physical Address로 바꾸기 위해서는, Main memory를 참조하는 작업이 추가되는 것이고, 이는 성능저하로 이어진다. 이를 위해, TLB(Translation Look-aside Buffer) 의 이름을 가진 소형 하드웨어 캐시를 사용하여 page table의 일부를 가지고 있는다. TLB에 대응하는 page number가 없는 경우에만 page table을 참조하게 된다.
additional..
-
권한(r,w,x)도 paging table에 기록되어있다.
-
Unix, Linux 계열 OS에서 page 크기를 알아내는 방법은 2가지가 있다.
getconf PAGESIZE를 입력하면 현재 OS에서 사용하는 page의 크기가 나온다.
- getpagesize() syscall을 사용하면 return 값으로 pagesize를 알려준다.
Limit
- External Fragmentation을 해결하였지만, Internal Fragmentation을 해결하지는 못했다.
- 위에서 현재 사용중인 Macbook-Pro M1 의 경우, Page의 크기가 16KB() 였다. 또한, 현재 사용중인 OS는 64-bit 체제이기에, page table은 ()개 가량의 row를 갖게 될 것이다. Frame Table만으로도 Memory를 얼마나 잡아먹을지 상상도 하기 싫다.
- 앞서 말했듯이 page table에 권한정보도 저장을 한다. 하지만,paging은 같은 크기로 메모리를 나누기에, stack, code 부분과 같은 논리적으로 다른, 즉 권한이 다른 부분도 같은 page에 저장될 수 있어 page table을 제작하는데에 어려움이 존재한다.
다행히, 2번 문제는 Paging을 개량하는 것으로 해결이 가능하다. Page Table을 구현하는 여러가지 방법을 보면서, 64-bit 체제에 적합한지만 간단하게 보고 넘어가자.
a. Hierarchical Paging
paging을 1번이 아닌 여러번을 사용하는 방법이다. page table이 용량을 너무 먹으려고 개량을 하려고 했더니 더 많은 Table을 만들어야 한다. 즉, 일반적으로 64-bit 구조에서 Hierarchical Paging 방식은 부적합하다.
b. Hashed Page Tables
Logical Address를 Hash로 사용하는 방법이다. Page Number을 Hash 값으로 사용하여, 해싱을 한다. hashing으로 충돌되는 값들은 linked list로 저장이 된다.
64-bit system에서 사용하기 위해, hashed page table을 개량하여 Cluster Page Table을 사용한다.
동작 방식은 다음과 같다.
1. Virtual Address를 Virtual Hash Input, Block offset(Boff), Offset으로 나눈다.
2. Virtual Hash Input을 Clusted Page Table에 hashing하여 pointer를 찾아낸다.
3. tag와 input값이 일치할 경우, 해당 클러스터에서 Boff에 맞는 PTE를 찾는다.
4. 해당 PTE를 사용하여 Physical Offset을 찾아낸다.
c. Inverted Page Table
기존의 paging이 page number를 offset으로 활용하여 주소를 알아냈다면, 반대로 pid, page number를 page table에서 찾고, 그것의 offset을 physical address로 활용하는 방법이다.
