9-2강. Memory Management 2

2. Noncontiguous allocation (불연속 할당)

 

- Paging

 프로세스가 구성하는 주소 공간을 같은 크기의 Page로 잘라서 Page 단위로 물리적인 메모리로 올려놓거나 Backing store에 내려 두거나 하는 것이다. 프로세스의 주소 공간을 자른 것처럼 물리적인 메모리에 사용자 프로세스가 들어갈 수 있는 공간들도 페이지와 똑같은 크기로 잘라 놓는데 이 물리적 공간을 Page Frame(페이지 프레임)이라고 한다. 이 Page Frame은 페이지 하나가 올라갈 수 있다. 이 기법을 사용하면 hole들의 크기가 균일하지 않아 발생하는 문제, 즉, External fragmentation(외부 조각 문제)가 발생하지 않는다. 물론 Internal fragmentation(내부 조각 문제)는 발생할 수 있다. 그 이유는 반드시 프로세스의 크기가 페이지 크기의 배수가 된다는 보장이 없기 때문이다. 추가적으로 Paging기법을 사용하면 MMU에 의한 주소 변환이 아니라 Page Table을 사용하여 주소 변환을 해야 한다.

 

 <그림 1>을 살펴보면 해당 프로세스에 해당하는 주소 공간을 Page 0, 1, 2, 3으로 자른 뒤에 Physical memory에 적절한 곳에 로드한다. 이때 각 페이지는 몇 번째 Page Frame에 들어갔는지를 저장하는 Page Table이 필요하다. 이 구조를 <그림 2>로 나타낼 수 있다. CPU가 논리적 주소를 주게 되면 물리적인 메모리로 대치시킬 때 Page Table을 활용한다. 이때 논리적 주소의 앞부분 p가 Page 번호가 입력되면 해당하는 Page Frame인 f가 출력된다. d가 해당 페이지 내의 상대적인 위치인 Offset을 의미하므로 p d 의 조합에서 f d로 바뀌게 되는 것이다.

 

 

그림 1 : Paging Examle

 

그림 2 : Address Translation Architecture

 

 기존에 연속 할당에서는 MMU의 register 두 개를 이용하여 주소 변환을 했다. 그렇다면 Page Table은 어디에 들어가야 할 것인가? 일반적으로 페이지 하나의 크기는 4KB이다보니 한 프로세스의 주소 공간을 페이지로 나누면 상당히 큰 숫자의 Page Table Entry가 필요하다. 그 큰 Entry들이 register안에 들어가지는 못할 것이다. 게다가 프로세스마다 Page Table이 별도로 존재해야 한다. 그렇다고 메모리 접근을 위한 주소 변환인데 어디 하드 디스크에 넣어둘 수도 없다. 또 캐시 메모리에 들어가기에도 Page Table들의 용량이 너무 크다. 따라서 Page Table을 메모리에다가 집어넣게 된다. 

 

 즉 Page Table은 main memory에 상주하게 되고, 앞서 MMU의 relocation register와 limit register는 Page Table을 가리키는 Page-table base register(PTBR)와 테이블의 크기를 보관하는 Page-table length register(PTLR)가 된다. 이러한 이유로 Paging 기법에서는 모든 메모리 접근 연산에는 2번의 memory access가 필요하다. page table을 통한 주소 변환을 위한 접근 1번, 그리고 실제 data/instruction 접근 1번이다. 이 비용이 크기 때문에 속도 향상을 위해 Associative register 혹은 Translation look-aside buffer (TLB)라 불리는 고속의 Lookup hardware cache를 사용할 수도 있다. 이것은 메인 메모리보다 빠른, 메모리와 CPU사이에 존재하는 하드웨어이다. 

 

 아마 Cache memory에 대해 알고 있을 것이다. 이 캐시 메모리는 운영체제에게는 Transparent 계층이기 때문에 메인 메모리에서 빈번히 사용되는 데이터들을 저장하여 CPU의 속도 향상을 가져다 준다. 주소 변환 시에도 마찬가지로 Page Table에서 빈번히 참조되는 일부 Entry들을 담고 있는 별도의 캐시를 두고 있는데 그것이 TLB이다. 이에 따라 주소 변환을 하려고 할 때는 TLB를 먼저 검색하고, 있으면 바로 Physical memory로 접근한다. 만약 TLB에 없다면 TLB miss(일종의 Cache miss)가 일어나며 메인 메모리에 있는 Page Table을 참조하게 된다. 여기서 주의할 점은 TLB는 Page Table과는 다르게 전체 Page와 Frame의 매치 정보를 갖고 있는 것이 아니기 때문에 TLB에는 Page number와 Frame number를 함께 가지고 있어야 한다는 것이다. 그리고 이렇게 되면 TLB에서는 전체를 검색해 보아야 한다는 단점이 있기 때문에 병렬적인 검색(Parallel Search)이 가능한 Associative register를 활용하여 구현하고 있다. 마지막으로 TLB는 프로세스에 종속적이기 때문에 Context switch 때 flush된다. <그림 3>을 참조하면 이해가 쉬울 것이다.

 

그림 3 : Paging Hardware with TLB

---

* Effective Access Time (EAT) *

 그러면 실제로 메모리 접근 시간은 어떻게 계산되는가?

Associative register lookup time = ε ( < 1)

memory cycle time = 1

Hit ratio = α (Associative register에서 찾아지는 비율)

 

 

 

EAT = (1 + ε)*α + ( 2 + ε)*(1 - α) = 2 + ε - α

 

따라서 Page Table만 있을 때 걸리는 시간 2보다는 2 + ε - α가 훨씬 짧다.

 

---

* Two-Level Page Table *

 

 지금까지는 <그림 2, 3>에서 살펴볼 수 있듯이 Page Table이 1단계로 존재했으나 Page Table은 2단계로 존재할 수 있다. 여기서는 Outer-page table과 innter-page table이 있다. 그러면 왜 2단계 페이지 테이블을 사용하는가? 일단 속도는 줄어들진 않을 것이다. 페이지 테이블을 위한 공간이 줄어드는 것때문에 2단계 페이지 테이블을 사용하는 것이다.

 

 현대 컴퓨터는 Address space가 매우 큰 프로그램을 지원한다. 32 bit address를 사용한다면 2^32B (4GB)의 주소 공간을 표현할 수 있는데 Page size가 4KB이면 1M(1,048,576)개의 Page table entry가 필요하며, Page Entry 한 개의 크기가 4B 정도이기 때문에, 프로세스마다 4MB의 Page Table이 필요하게 된다. 그러나 대부분의 프로그램은 4GB의 주소 공간 중 일부분만 사용하기 때문에 Page Table 공간이 심하게 낭비된다. 

 

 이를 해결하고자 등장한 것이 2단계 페이지 테이블이다. <그림 4>와 <그림 5>를 함께 살펴보자. Outer-page Table의 Entry에 접근하면 그 데이터(p1)는 Inner-Page Table의 인덱스를 가리킨다. 이것을 타고 들어가면 두 번째 Page-Table의 Page를 얻을 수 있고, 여기서 p2 인덱스에 접근하면 한 페이지에 해당하는 Page Frame의 Physical Address의 시작 주소를 얻을 수 있다. 마지막으로 여기에 Offset인 d를 더하면 실제 물리 주소에 접근할 수 있다. 참고로 Inner-page Table에 들어있는 Page는 페이지의 크기와 동일하다. Inner-Page Table에 들어가는 Page는 1K가 된다(페이지 크기가 4KB, Entry 크기가 4B). 

 

 추가적으로 한 페이지에서 나타날 수 있는 변위는 최대 4KB이고 4K는 2^12이기 때문에 Offset을 나타내기 위해서는 12bit가 필요하다. 그리고 우리는 방금 Inner-Page Table에 Entry가 1K가 있다는 것을 알았다. 따라서 Inner-Page Table에서는 2^10의 서로 다른 Entry위치를 구분하기 위해 10bit가 필요하다. Outer-Page Table과 Inner-Page Table은 자연스럽게 10bit가 필요할 것이다.

 

 잠깐! 근데 잘 생각해보자. Inner-Table 에서는 1K * 1K, 즉, 1M개가 필요하고, 거기에다가 Outer-Page Table에서도 1K가 추가로 필요하다. 그러면 1단계 페이지 테이블보다 시간도 손해, 공간도 손해 아닌가?! 답은 아니다. 왜냐하면 실제 프로그램에서 사용하는 Page Entry는 몇 개 안되는데 1단계에서는 모든 Page Entry 1M개에 대한 공간이 전부 필요했다. 그러나 2단계를 쓰게 되면 Outer-Page Table은 1K개의 모든 Entry들이 다 만들어지긴 하지만, 실제로 사용이 되지 않는 Inner-Page Table의 엔트리 값이 NULL로 초기화되어 있기 때문에 2단계 페이지 테이블이 더 효과적이다.

 

 

그림 4 : Two-level Page Table

그림 5 : Address-Translation Scheme (Two-level)

---

  - Segmentation

 

 세그먼테이션 기법은 프로그램의 주소 공간을 같은 크기로 자르는 것이 아니라 어떤 의미 있는 단위로 자르는 것이다. 대개 Code, Data, Stack 공간으로 주소 공간이 구성되는데 이 세그먼트 별로 물리 공간에 올릴 수 있게 하는 것이다. 그러나 이 방법도 Segment의 크기가 균일하지 않기 때문에 앞서 살펴본 Dynamic Storage-Allocation Problem이 발생할 것이다. 

 

- Paged Segmentation

...

 

To be continued...

 

 

본 글들은 이화여대 반효경 교수님 2017학년도 1학기 운영체제 강의를 기반으로 작성됩니다.

링크 : http://www.kocw.net/home/search/kemView.do?kemId=1046323