[OS / 운영 체제] Paging, Frame Table, Hardware Support, Shared Pages, Hierarchical Paging

Paging

overhead는 2가지가 있다. 메모리 관점에서 page table 을 먼저 살펴보자. page table의 메모리 공간은 무시하지 못할 만큼 크다. page의 한 칸이 frame number 를 나타낼 수 있어야 하고 page offset이 12 bit라면 20bit의 크기를 담을 수 있어야 한다. 4MB 정도 해당하므로 무시할 수 없다. page table은 컴퓨터 안에 프로세스 개수 만큼 존재한다. 프로세스가 100개 정도 있다고 하면 400MB 정도 차지한다고 볼 수 있다.  두 번째는 Internel Fragmentation 관점이다. 예를 들어 logical memory의 공간이 14라고 하면 어찌 됐든 16에 해당하는 메모리를 할당 받아야 한다. 그렇게 되면 하나의 Frame에는 2개의 메모리 공간이 남게 된다. 이렇게 2가지의 Overhead가 존재할 수 있다. 이래도 Paging의 방법을 사용하는 이유는 External Fragmentation이 없어지기 때문이다. 

 

 

또 다른 Overhead

속도 관점. page table을 한 번 Access해서 다시 참조하는 page의 논리로는 시간이 더 걸린다. page table은 memory에 있는 공간이므로 결과적으로 보면 Memory를 두 번 Access를 하기 때문에 시간이 더 오래 걸린다. Memory table의 위치를 담고 있는 PCB가 존재하고 그곳도 Access를 해야 한다. 

 

X86 ~

31 ~ 12 bit는 Frame number에 해당하고 그 뒤의 비트에는 어떤 것들이 차지 하는가. 해당 페이지의 속성이 저장된다. Read / Write 페이지 중에 어떤 것은 Read만 하고 Write 만 할 수 있는 특성을 가지고 있다. 가끔 Reading 만 허용해야 하는 경우가 존재한다. 이런 곳은 프로그램 코드가 들어간 곳이다. Read Only Memory 만을 지원해야 한다. 

 

 

Frame Table

운영 체제는 Physical Memory를 관리할 책임이 있다. 관리하기 위해 필요한 내용을 frame table에 저장해야 한다. frame table을 1개 존재한다. 각 frame이 사용 중인지 비어있는 지를 담고 있는 정보가 다 저장되어 있다. list of free frame이라는 개념이 있다. 현재 빈 Frame이 어디에 있는 지에 대한 정보를 list로 담고 있는 것이다. 

 

 

Free Frames

현재 4개의 페이지가 필요한 상황. list of free frame을 하면 좋은 점이 메모리에 대한 요청이 왔을 때 그에 대한 처리 속도가 빨라진다는 것이다. 운영 체제 입장에서 15 만이 빈 Frame일 경우 어떻게 행동해야 하는가? Free Frame을 미리 확보해야 한다. Disk로 안 쓰는 내용을 내려서 Free Frame에 대한 공간을 확보한다. 이러한 동작은 언제 이루어져야 하는가?  CPU Time이 한가할 때 Free Frame을 확보해야 한다. 

 

 

Hardware Support

운영 체제는 프로세스 마다 Page table을 가지고 있다. Process 마다 address space를 가지고 있기 때문이다. 대부분의 운영체제는 이런 논리 흐름을 따른다. 하지만 이 방법에 의한 메모리를 총 3번 접근을 해야 한다. PCB(Page table의 주소) Page table, Physical Memory 이렇게 3번이다. 이 중에 PCB에 담겨 있는 Page table 정보를 래지스터에 저장하는 방법을 사용할 수 도 있다.  옛날 System은 page table을 CPU Resgiser에 넣을 수 있었다. 하지만 요즘은 안됀다.

 

 

Hardware Support

PTBR, PCB에 담겨 있는 page table의 주소 정보를 담고 있는 래지스터를 말한다. PTBR에는 page table의 주소가 들어간다. Context Switching을 할 때마다 바꿔줘야 한다. 그 값이 PTBR에 최신화 되어야 한다. 2 번째의 문제는 Page table에 대한 메모리 Overhead인데 이 문제는 Cache를 통해서 해결을 해야 한다. 

 

 

Hardware Support

Translation Look-aside Buffer 여기서 Translation은 Address Translation을 의미한다. page table을 access 하면 p에 대한 f (frame number)를 찾을 수 있다. 하지만 이 정보를 담고 있는 Page table을 Cache 안에 저장을 시켜버린다. 

 

 

Hardware Support

TLB에는 page number와 frame number가 들어가게 된다. (해당 pair가 저장되는 거임) TLB를 통하면 Cache Memory를 통과하므로 빠른 것이다. 그리고 빠른 이유가 또 하나 더 존재한다. page number를 살필 때 search 알고리즘이 사용되는데 이것이 하드웨어 적으로 구현된 알고리즘이 존재하는데 그것이 Associate Memory이다.

p를 Access하고 그 다음에도 p를 참고하는 가? 그렇다. 그 주변 메모리를 참고할 확률이 높다. 한 가지 Issue는 Context Switching의 경우이다. Process가 바뀌므로 Page table의 정보도 바뀌고 현재 TLB에 있는 내용을 참조할 필요가 없게 되어서 flash를 해버리게 된다. 이를 해결하기 위한 방법이 존재하기는 한다. 사용하고 다시 돌아오는 경우를 대비해서 현재 TLB의 주소의 값을 저장하면 된다. 

 

 

Associative Memory

검색할 필요도 없이 Constant Time으로 찾을 수 있다. 

 

 

Protection

Read / Write 에 대한 정보들이 담겨 있다. Page table의 모든 Page가 실제로 모든 Physical Memory로 들어가지 않을 수도 있다는 것이다. Page table이 2^3개 만큼 존재한다. (실제로 2^n 개로 존재해야 한다) 하지만 실제로 필요한 process의 Table은 6개만 요청이 들어온 상황. Physical Memory로 실제 Mapping이 되었다고 할때 v로 표시가 된다. 매칭이 되지 않은 것을 i로 표시를 한다. Present가 valid / invalid를 말하는 비트이다. logical Address Space 전체가 Physical Address와 Mapping 되는 것은 틀린 말이다~!!!(*****) 전체 사용 가능한 Entry 개수 중에 실제 사용 중인 개수를 PTBR에 저장하면 1bit를 줄일 수 있다. 

 

 

Shared Pages(****)

3 개의 Process가 있다. page table도 3개를 가지고 있다. vi가 동일한 코드를 사용하고 있을 때 각자 다른 메모리 공간을 참고하고 있는 것이 아니다. 논리적인 공간에서는 3번 사용하고 있지만 Physical Memory는 하나의 공간에 매칭되게 된다. 그래서 2 번째 실행하는 프로그램이 빠른 이유이다. (대봑....) data 영역을 공유할 수 있는가? 이는 공유되어 있지 않다. 이를 공유할 수 없는 이유는 데이터마다 다른 내용을 가지고 있기 때문이다. 반대로 text editor를 공유할 수 있는 이유는 두 개가 같기 때문이다. 

 

 

Hierarchical Paging

Paging의 Overhead는 page table이 차지하고 메모리 차원에서 제약이 있다. 하지만 이는 contiguous 이어야 한다는 특징을 가진다. 논리적일 뿐만 아니라 물리적으로 연속적이어야 한다. Page table은 Page의 Benefit을 누릴 수 없는 것. page number라는 영역을 둘 로 나눈다. P1, P2. 

 

 

Hierarchical Paging

page table이 분할되어 있는 것을 볼 수 있다. 가장 왼쪽의 박스가 오른 쪽 사진의 두 번째 이미지에 해당한다. 이 방법을 사용하는 이유는? Page table을 나눠서 관리할 수 있다는 효율적 측면에서의 장점이 있다.