3장 메모리 관리

　모든 프로그래머가 원하는 것은 무한히 크고, 빠르며, 자신이 혼자 사용할 수 있는 메모리이다. 또한 비휘발성(nonvolatile) 메모리를 원한다. 또 한가지 중요한 것은 가격이 비싸지 않아야 한다는 것이다. 하지만 현재 기술로는 위의 모든 요구 조건을 만족시킬 수 있는 메모리를 만들 수는 없다.
　메모리 계층 구조(memory hierarchy)란 캐시 메모리(cache memory), 메인 메모리(main memory), 디스크 스토리지(storage) 등의 서로 다른 특성을 갖는 메모리들을 층 구조로 구성하는 방법이다. 캐시 메모리는 보통 메가바이트(megabyte) 크기를 가지며, 빠르고 휘발성이며 비싸다. 반면 메인 메모리는 가가바이트(gigabyte) 크기를 가지며, 중간 속도이고 휘발성이며 중간 정도의 가격을 갖는다. 마지막으로 디스크 스토리지는 테라바이트(terabyte) 크기를 가지며, 느리고 비휘발성이며 가격이 싸다. 이러한 계층 구조를 사용하기 좋은 모델로 추상화시키고 이 추상화된 객체를 관리하는 것이 운영체제의 역할이다.
　운영체제 중에서 메모리 계층 구조 관리를 담당하는 부분을 메모리 관리자(memory manager)라고 한다. 메모리 관리자는 현재 사용 중인 메모리 부분을 파악하고, 프로세스들이 메모리를 필요로 하면 할당해 주고, 더 이상 사용하지 않으면 해제하는 작업을 실행한다.

메모리 추상화가 없는 컴퓨터

　메모리 추상화의 가장 단순한 형태는 추상화를 사용하지 않는 것이다. 즉 모든 프로그램은 물리 메모리를 직접 사용하였다.(ex. MOV REGISTER1, 1000) 메모리 추상화가 없는 환경에서는 두 개의 프로그램이 동시에 메모리에서 실행된다는 것은 불가능하다.
　물리 메모리를 직접 사용하는 추상화 없는 메모리 모델에서도 설계에 여러 가지 선택이 가능하다. 다음은 3가지 선택의 경우들을 보여준다.

　(a)는 RAM(Random Access Memory: 임의접근 메모리)의 아래 부분에 운영체제가 존재하고 그 위에 사용자 프로그램이 존재하는 메모리 구성의 예를 보여준다. 반면 (b)는 주소 공간 상단에 배치된 ROM(Read Only Memory)에 운영체제가 존재하는 예를 보여주며, (c)는 ROM에는 장치 드라이버가 존재하고 그 아래에 있는 RAM에 사용자 프로그램과 운영체제가 존재하는 예를 보여준다.
　컴퓨터 시스템이 이와 같은 방법으로 구성되어 있으면 대부분 한 순간에 하나의 프로세스만 동작하게 된다. 사용자가 명령을 입력하면 운영체제는 요청한 명령 프로그램을 디스크에서 메모리로 적재하고 그것을 실행한다. 그 프로세스가 종료되면 운영체제는 프롬프트를 출력하고 사용자가 다른 명령을 입력할 때까지 대기한다. 만일 새로운 명령이 요청되면 운영체제는 새로운 명령을 위한 프로그램을 디스크에서 메모리로 적재하는데 이때 기존에 있던 프로그램을 덮어쓰게 된다.
　메모리 추상화가 없는 시스템에서 병령성(parallelism)을 획득하는 방법 중에 하나는 여러 개의 스레드(multiple thread)를 사용하는 것이다. 한 프로세스에 존재하는 스레드들은 모두 같은 메모리 이미지를 공유하기 때문에 가능하다. 하지만 이것의 다른 의미는 스레드들이 서로 다른 프로그램을 실행할 수는 없다는 것이다. 따라서 스레드를 통해 병렬성을 얻을 수는 있지만 이것은 제한되어 있다. 실제로 많은 사람들은 관련되지 않은 서로 다른 프로그램들을 동시에 실행하기를 원하며 이것은 스레드 추상화가 지원하지 않는 기능이다.

메모리 추상화가 없는 환경에서 여러 프로그램 실행

　메모리 추상화가 없는 시스템에서도 여러 프로그램을 동시에 실행하는 방법이 가능하긴 하다. 운영체제가 해야하는 일은 우선 메모리에 존재하던 프로그램 이미지를 디스크에 저장하고 다음에 실행할 프로그램을 메모리로 올리는 것이다. 사실상 메모리에 한 순간에 하나의 프로그램이 존재하기만 하면 충돌을 방지할 수 있다.
　특별한 하드웨어의 도움이 있으면 스와핑을 사용하지 않더라도 여러 프로그램을 동시에 실행하는 것이 가능하다. 보호 키(protection key)를 통해 사용자 프로세스들은 서로 간섭하는 것을 예방할 수 있으며 운영체제 역시 프로세스들로부터 간섭을 막아 보호할 수 있다. 하지만 예를 들어 프로그램 2개가 서로 다른 보호키를 가지고 있을 때 두 프로그램들이 모두 절대 물리 주소(absolute physical address)를 사용할 경우 문제가 발생한다.
　이를 해결하기 위해 정적 재배치(static relocation)라는 기법을 사용한다. 정적 재배치란 프로그램이 메모리에 적재될 때 프로그램의 내용을 수정하는 것이다. 하지만 이 기법은 일반적인 방법은 아니며 또한 적재하는 시간을 증가시킨다. 더욱이 이 기법은 프로그램의 어느 위치에 주소가 있는지 부가적인 정보를 요구한다.

메모리 추상화: 주소 공간

　프로세스가 물리 메모리를 직접 사용하는 것은 다음과 같은 단점이 있다.

• 프로그램이 물리 메모리의 모든 주소를 접근할 수 있다면 사용자는 실수로 또는 의도적으로 운영체제를 파괴할 수 있으며 결국 시스템을 중지시킬 수 있다.
• 여러 프로그램들을 동시에 실행시키는 것이 어려워진다.

주소 공간 개념

　여러 프로그램들을 동시에 메모리에 적재하고 서로 간섭 없이 실행하기 위해서는 보호(protection)와 재배치(relocation) 방법이 제공되어야 한다. IBM360에서는 메모리 공간마다 보호 키를 연결하고 프로세스가 메모리를 접근할 때 키를 비교하는 방법으로 보호를 제공한다. 한편, 이것만으로는 재배치를 제공하지 못하기 때문에 프로그램을 적재할 때 프로그램이 참조하는 주소를 직접 바꾸는 방법으로 재배치를 제공하였다. 하지만 이 방법은 느리고 복잡하다.
　보호와 재배치를 제공하는 더 효과적인 방법은 주소 공간(address space)이라는 새로운 메모리 추상화를 제공하는 것이다. 주소 공간이란 프로세스가 메모리를 접근할 때 사용하는 주소들의 집합으로 각 프로세스는 자신만의 주소 공간을 갖는다. 한 프로세스가 갖는 주소 공간은 다른 프로세스가 갖는 주소 공간과 독립되어 있다. 각 프로세스들에게 서로 다른 주소 공간을 제공해야 하는데, 한 프로그램에서 사용하는 28 주소가 다른 프로그램에서 사용하는 28 주소와는 서로 다른 물리 주소를 가리키도록 해야한다.

Base와 Limit 레지스터
　각 프로세스의 주소 공간을 물리 메모리의 서로 다른 주소 공간으로 연속적으로 매핑하는 방법은 동적 재배치(dynamic relocation) 방법 중의 한가지로 상당히 단순하다. 이 방법을 위해 CPU는 base와 limit이라는 이름의 특별한 하드웨어 레지스터를 사용한다. 프로그램이 실행될 때 base 레지스터에 프로그램이 적재된 메모리 시작 위치가, limit 레지스터에 프로그램의 크기가 저장된다. 예를 들어, 첫 번째 프로그램이 실행될 때 base와 limit에는 각각 0과 16,384가 저장되며, 두 번째 프로그램에는 16,384와 16.384가 저장된다.
　프로세스가 명령어 반입이나 데이터를 읽고 쓰기 위해 메모리를 참조하면 CPU 하드웨어는 자동으로 프로세스가 참조하려는 메모리 주소에 base 레지스터 값을 더한다. 또한 프로세스가 참조하려는 주소가 limit 레지스터의 값과 동일한지 혹은 큰지를 확인한다. 만일 그렇다면 메모리 참조는 중단되고 결함(fault)이 발생한다. 아니라면 더한 값을 참조하려는 메모리 주소 값을 메모리 버스에 보낸다.
　Base와 limit 레지스터는 각 프로세스에게 자신 고유의 주소 공간을 제공하는 간단한 방법을 지원한다. 참조되는 모든 메모리 주소는 명령이 접근하려는 주소와 base 레지스터에 기록된 값이 더해진 값이 되며 이것은 하드웨어에 의해 자동으로 계산된다. 많은 구현에서 base와 limit 레지스터는 오직 운영체제만 변경할 수 있도록 보호된다.
　Base와 limit 레지스터를 사용하는 재배치의 단점은 모든 메모리 참조마다 덧셈과 비교 연산이 요구 된다는 것이다. 비교 연산은 상대적으로 빠르게 처리될 수 있지만 덧셈은 특별한 하드웨어 로직을 사용하지 않으면 캐리 전파 때문에 시간이 많이 걸린다.

스와핑

　지금까지는 시스템에 존재하는 물리 메모리의 용량이 모든 프로세스를 적재할 만큼 충분히 많은 경우에 대한 경우를 보았다. 하지만 실제 시스템에서 모든 프로세스들이 필요로 하는 메모리의 전체 크기는 시스템에 존재하는 실제의 RAM 용량보다 크다. 이러한 문제를 해결하기 위한 방법으로 스와핑(swapping)과 가상 메모리(virtual memory)가 제안되었다. 스와핑은 한 프로세스의 모든 이미지가 메모리로 적재되어 실행되다가 더 이상 실행되지 않을 경우 다시 디스크로 내려 보내는 방법이다. 따라서 현재 실행되고 있지 않은 프로세스는 메모리를 차지하지 않고 디스크에 존재하게 된다. 주기적으로 깨어나 실행하고 다시 수면에 빠지는 프로세스들은 메모리의 상태에 따라 계속 메모리에 존재할 수도 있고, 또는 실행 중일 때만 메모리에 존재하고 수면에 들어가면 다시 스와핑 될 수도 있다. 가상 메모리는 한 프로세스의 전체 이미지가 아닌 일부만 메모리에 있어도 그 프로세스의 실행이 가능하다.
　다음은 스와핑 시스템의 동작을 에시한 것이다.

　초기에는 메모리에 프로세스 A만 존재한다. 그러다가 프로세스 B와 C가 새로 생성 되었거나 디스크에서 스왑 인(swap in) 되었다. (d)는 프로세스 A가 스왑 아웃(swap out) 된 것을 보여주며, 그 이후에 프로세스 D가 적재 되었고, 프로세스 B가 스왑 아웃되었다. 마지막으로 프로세스 A가 스왑 인 되었다. 마지막 상태에서 프로세스 A의 메모리 위치가 바뀌었기 때문에 재배치가 필요하다. 재배치는 스왑 인 될 때 소프트웨어적으로 실행될 수도 있으며, 또는 프로그램이 실행될 때 하드웨어적으로 실행될 수도 있다.
　스와핑 결과 메모리에 여러 개의 분리된 빈 공간들이 만들어지며 프로세스들의 위치를 이동하여 빈 공간들을 모아 하나의 큰 공간으로 합칠 수 있다. 이것을 메모리 조각모음(memory compaction)이라고 한다. 메모리 조각모음은 시간이 많이 걸리는 작업이기 때문에 자주 실행되지는 않는다.
　만약 프로세스의 크기가 실행 중에 증가할 것으로 예상된다면 프로세스가 생성되거나 스왑 인 될 때 여분의 빈 공간을 더 할당해 주는 것도 좋은 생각이다. 이것은 프로세스의 크기 증가에 따라 프로세스를 이동시키거나 다른 프로세스들을 스왑 아웃 시키는 부하를 줄일 수 있다. 다음 (a)는 공간 확장을 고려하여 두 프로세스에게 여분의 공간을 더 할당한 예를 보여준다. 이때 이 프로세스를 디스크로 스왑 아웃 한다면 실제 사용하는 메모리 내용만 스왑 아웃 하면 된다. 여분의 메모리 내용까지 스왑 아웃한다면 사실상 스왑 공간을 낭비하는 것이 된다.

　메모리의 동적 할당과 해제가 가능한 힙을 위한 데이터 세그먼트와 지역 변수 및 복귀 주소가 저장되는 스택 세그먼트라는 두 개의 세그먼트를 갖는 것처럼 만일 프로세스가 증가될 수 있는 두 개의 세그먼트를 갖는다면 (b)와 같은 메모리 배치가 가능하다. 이 그림에서 각 프로세스는 할당 받은 메모리 상단에 스택 세그먼트를 배치하고 데이터 세그먼트는 메모리 하단의 프로그램 텍스트 위에 배치한다. 스택은 아래방향으로 자라며 데이터는 위 방향으로 자란다. 중간의 메모리 공간은 스택 또는 힙 어느 공간으로도 사용될 수 없다. 만일 메모리가 부족하다면 다른 여분의 공간이 큰 메모리 위치로 이동하거나, 스왑 아웃 되거나, 강제 종료된다.

가용 메모리 공간 관리

　메모리가 동적으로 할당된다면 운영체제는 메모리 공간의 어떤 부분이 사용 중인지 관리하여야 한다. 메모리 사용량을 관리할 때 사용하는 대표적인 두 가지 자료 구조가 비트맵(bit map)과 리스트(list)이다.

비트맵을 이용한 관리
　비트맵을 이용한 관리 방법은 메모리를 여러 개의 할당 단위(allocation unit)로 나누어 관리한다. 할당 단위는 몇 워드 크기를 갖는 작은 단위에서부터 몇 KB크기를 갖는 큰 단위까지 가능하다. 각 할당 단위마다 비트가 하나씩 대응되는데, 이 비트가 0이면 해당 할당 단위가 가용하고 1이면 이미 사용 중임을 의미한다.(반대 설정도 가능) 다음은 메모리의 일부분과 이를 관리하는 비트맵의 예를 보여준다.

　할당 단위의 크기 설정은 중요한 설계 이슈이다.

• 할당 단위의 크기가 작으면 비트맵 공간이 커진다.
  • 4바이트를 할당 단위로 설정한다 하더라도 4바이트마다 1비트만 존재하면 된다. 즉, 32비트마다 1비트가 필요한 것이므로 32n 비트에 n 크기의 비트맵이 필요하게 되며 결국 전체 메모리의 1/33이 비트맵으로 사용된다.
• 반면 할당 단위가 커지면 비트맵의 공간이 작아진다.
  • 이 경우에는 프로세스의 크기가 할당 단위의 정수배가 아니면 마지막 할당 단위의 일부 공간이 낭비된다.

　비트맵 크기는 메모리 크기와 할당 단위의 크기에 의해 결정되며, 고정된 크기의 공간으로 메모리의 사용량을 관리하는 간단하면서도 효과적인 방법이다. 하지만 비트맵 검색은 시간이 많이 걸린다.

연결 리스트를 이용한 관리
　메모리의 사용량을 관리하는 다른 방법은 할당된(allocated) 메모리 공간과 가용한(free) 메모리 공간을 연결 리스트(linked list)로 관리하는 것이다. 위 그림에서 (a)의 메모리 상태를 연결 리스트로 나타낸 것이 (c)이다. 리스트의 각 엔트리는 빈 공간(H)이거나 프로세스의 내용(P)을 담고 있음을 나타내는 정보, 시작하는 주소, 길이, 그리고 다음 엔트리를 가리키는 포인터로 구성된다.
　이 예에서 리스트의 각 엔트리들은 시작 주소를 키로 정렬되어 있다. 이러한 방식의 정렬은 프로세스가 종료되거나 스왑 아웃될 때 리스트의 관리를 쉽게 한다. 종료되는 프로세스는 메모리의 가장 끝에 존재하는 프로세스를 제외하면 일반적으로 2개의 이웃을 갖는다. 이웃은 다른 프로세스가 차지한 공간이거나 빈 공간이며, 다음과 같이 4가지 조합이 가능하다.

　프로세스 X가 종료될 때 가능한 4가지 이웃들의 조합

• (a): 리스트의 반경은 해당 엔트리의 P를 H로 바꾸는 것 만으로 완료된다.
• (b), (c): 두 개의 엔트리가 통합되어 하나로 되며, 결국 전체 리스트에서 엔트리가 하나 줄어 든다.
• (d): 3개의 엔트리가 하나로 통합되며, 결국 리스트 전체적으로 2개의 엔트리가 줄어 든다.

　프로세스가 사용 중인 메모리 공간과 빈 공간들이 주소 값을 키로 정렬되어 있으면 새로 생성되는 프로세스 또는 디스크에서 스왑 인 되는 프로세스를 위한 메모리 공간을 할당할 때 다양한 알고리즘을 적용할 수 있다. 일단 메모리 관리자가 얼마 크기의 메모리 공간을 할당해야 하는지 이미 알고 있다고 가정하자.

• 최초적합(first fit)
  • 가장 간단한 알고리즘.
  • 메모리 관리자가 리스트를 순서대로 검색하며 요청한 공간을 담을 수 있는 크기의 빈 공간이 발견되면 그 공간을 할당한다.
  • 최초적합은 검색을 최소한으로 하기 때문에 빠른 할당이 가능하다.
• 다음적합(next fit)
  • 최초적합을 약간 수정한 알고리즘. 최초적합과 유사하게 동작한다.
  • 자신이 빈 공간을 할당해 주었을 때 그 위치를 기억해둔다. 새로운 할당을 위해 알고리즘을 다시 호출되면 지난 번에 기억해 두었던 위치부터 검색을 시작한다.(최초적합은 항상 리스트의 처음부터 검색을 시작)
  • 최초적합에 비해 성능이 조금 떨어짐
• 최적적합(best fit)
  • 리스트의 처음부터 끝까지 모든 엔트리들을 검색하여 요청한 크기에 가장 근접하게 큰 빈 공간을 할당한다.
  • 큰 빈 공간을 잘라서 할당하는 것이 아니라 가능한 요청한 크기를 최적으로 만족할 수 있는 빈 공간을 찾는 것이다.
• 최악적합(worst fit)
  • 가능한 프로세스가 요구하는 크기에 맞도록 빈 공간을 할당하여 그 결과를 작은 빈 공간들을 많이 생성하는 문제를 해결.
  • 항상 가장 큰 빈 공간을 할당해 준다. 그 결과 할당되고 남은 빈 공간도 가능한 큰 공간이 될 수 있도록 하는 것이다.

가상 메모리

　메모리 크기보다 큰 프로그램의 실행 문제가 존재한다. 이 해결책으로 오버레이(overlay)라고 불리는 작은 조각들로 나누어 실행하는 방법이 있다. 이 방법은 오버레이 관리자를 메모리로 적재한다. 이 관리자는 오버레이 0을 메모리로 올려 실행한다. 오버레이 0의 실행이 끝나면 관리자는 오버레이 1을 적재하여 실행한다. 오버레이 1은 오버레이 0과 다른 위치에 적재될 수도 있으며(가용 메모리 공간이 있는 경우), 오버레이 0이 존재하던 위치에 덮어 적재될 수도 있다(가용 메모리 공간이 없는 경우).
　가상 메모리(virtual memory)라고 알려진 기법의 기본 아이디어는 각 프로그램이 자신의 고유한 주소 공간을 가지며 주소 공간은 페이지(page)라고 불리는 조각들로 구성된다. 각 페이지는 연속된 주소를 갖는다. 프로그램이 실행되면 페이지들은 물리 메모리에 매핑된다.

페이징(paging)

　프로그램은 실행되면서 메모리 주소들을 참조한다. 에를 들어 “MOV REG, 1000”을 실행하면 메모리 주소 1000번지에 있는 내용을 REG라는 레지스터로 복사하는 일을 한다.
　프로그램이 참조하는 주소는 가상 주소(virtual address)라고 불리며 가상 주소 공간을 형성한다. 가상 메모리를 사용하지 않은 컴퓨터에서는 가상 주소가 그대로 메모리 버스에 실리며 결국 이 주소가 물리 주소(physical address)가 된다. 따라서 이 주소에 존재하는 데이터를 접근할 수 있다. 반면 가상 메모리를 사용하는 시스템에서는 가상 주소가 그대로 메모리 버스에 실리지는 않는다. 그 대신 가상 주소는 다음과 같이 MMU(Memory Management Unit)에 의해 물리 주소로 매핑된다.

　다음은 매핑이 어떻게 동작하는지 예를 보여준다.

　위 예에서 컴퓨터는 16비트의 주소, 즉 0~64KB의 주소공간을 제공한다. 이 주소 공간은 가상 주소이다. 이 컴퓨터의 물리 메모리 크기는 32KB이다. 따라서 64KB 크기의 프로그램은 실행 중에 자신의 모든 페이지들을 물리 메모리 상에 적재할 수는 없다. 프로그램의 전체 이미지는 디스크 상에 존재하며 물리 메모리에는 현재 실행에 필요한 부분만 존재하게 된다.
　가상 주소 공간은 고정된 크기의 단위들로 구분되어 있으며 이 단위를 페이지(page)라고 부른다. 반면, 물리 메모리 상에 대응되는 단위는 페이지 프레임(page prame)이라고 부른다. 페이지와 페이지 프레임의 크기는 같다. 위 예에서는 각각 4KB 크기이며 64KB의 가상 메모리는 16개의 페이지로 구분되며, 32KB의 물리 메모리는 8개의 페이지 프레임으로 구분된다. RAM과 디스크 간에 데이터의 이동 역시 페이지 단위로 이루어진다.
　MMU가 16개의 가상 페이지를 8개의 페이지 프레임에 매핑하는 것 차제 만으로는 가상 주소 공간이 물리 주소보다 큰 문제를 해결하지 못한다. 이를 해결하기 위해서는 다른 기능들이 추가되어야 한다. 위 그림의 예에서는 페이지 프레임이 8개 밖에 없기 때문에 16개의 가상 페이지 중에서 오직 8개만 물리 메모리로 매핑될 수 있다. 그림에서 x로 표시된 페이지들이 매핑되지 못한 페이지들이다. 이를 위해 하드웨어적으로 present/absent 비트가 제공되며, 이를 통해 어떤 페이지가 실제 물리 메모리에 존재하는지 파악할 수 있다.
　MMU는 비트를 이용해 이 페이지가 매핑되어 있지 않음을 파악하고, CPU에게 트랩을 발생시켜 운영체제에게 이것을 알리도록 한다. 이것을 페이지 폴트(page fault)라고 한다. 운영체제는 페이지 프레임 중에서 적게 사용되고 있는 페이지 프레임을 선택하고 페이지 프레임의 내용을 디스크에 기록한다(이미 기록되어 있다면 생략). 그 이후 참조하려는 페이지의 내용을 페이지 프레임에 적재하고, 맵을 수정한 후, 트랩을 야기한 명령을 다시 실행한다.
　예를 들어 운영체제가 위의 페이지 프레임 중에서 1번을 교체하기로 선택했다고 가정하자. 그럼 운영체제는 페이지 8의 내용을 페이지 프레임 1에 적재하고 MMU에서 다음 두 가지를 수행한다. 첫 번째는 수정은 가상 페이지 1이 이제는 매핑되지 않았음을 표시한다. 이렇게 되면 이제부터 가상 주소 4096~8191의 참조는 트랩을 야기한다. 두 번째 수정은 가상 페이지 8번이 페이지 프레임 1에 매핑되었음을 기록한다. 그러면 트랩이 발생한 위 명령을 다시 실행할 때 이제는 가상 주소 32780이 물리 주소 4108(4096 + 12)으로 변환되어 실제 물리 메모리를 참조하게 된다.
　MMU의 내부 구조를 살펴보면서 동작 방법과 페이지 크기를 2의 정수 배로 선택한 이유를 보자. 다음 그림(4KB 크기의 페이지들을 16개로 관리하는 MMU의 내부 동작)은 가상 주소 8196(0010 0000 0000 0100)이 위 그림에서 예시된 매핑 정보를 이용해 물리 주소로 전환되는 과정을 보여준다.

　16비트 크기를 갖는 가상 주소는 페이지 번호와 오프셋으로 구분된다. 이 예에서는 페이지 번호(virtual page number)를 위해 4비트가 사용되고(페이지 개수가 16개), 오프셋(vitrual page offset)을 위해 12비트가 사용된다(페이지의 크기가 4096).
　페이지 번호는 페이지 테이블(page table)의 인덱스로 사용된다. 페이지 테이블에는 해당 페이지 번호에 대응되는 페이지 프레임 번호가 기록되어 있다. 만일 present/absent 비트가 0이면 페이지 폴트가 발생한다. 반면 1이라면 페이지 테이블에 기록되어 있는 페이지 프레임 번호(pageframe number) 세 비트와 가상 주소의 오프셋에 대응되는 12비트가 결합하여 물리 주소가 된다. 이 주소는 주소 출력 레지스터를 통해 메모리 버스로 전달되고, 결국 메모리 참조 주소가 된다.

페이지 테이블

　가상 주소를 물리 주소로 매핑하는 과정을 요약하면 다음과 같다.

• 가상 주소를 페이지 번호(상위 비트)와 오프셋(하위 비트)으로 구분한다.
  • 예를 들어 16비트 주소 크기를 갖는 시스템에서 페이지 크기가 4KB라면, 상위 4비트는 페이지를 가리키는 페이지 번호로 사용되고, 하위 12비트는 바이트 오프셋(0부터 4095까지)으로 사용된다.
  • 물론 페이지 번호로 3비트, 5비트 또는 다른 개수의 비트를 사용하는 것도 가능하지만 페이지의 크기도 변하게 된다.
• 페이지 번호를 인덱스로 이용해 페이지 테이블에서 가상 주소에 대응되는 앤트리를 찾는다.
  • 페이지 테이블 앤트리에서 페이지 프레임 번호를 얻을 수 있다(매핑되어 있다면).
• 가상 주소에서 페이지 번호가 차지하던 부분을 페이지 프레임 번호로 대치하면(즉, 페이지 프레임 번호를 상위에 놓고, 오프셋을 하위에 놓으면) 결국 물리주소가 된다.
  • 이 물리 주소가 메모리 참조에 사용된다.

　결국 페이지 테이블의 목표는 가상 페이지를 물리 페이지 프레임으로 매핑하는 것이다. 이 결과를 이용하여 가상 주소의 페이지 번호 부분을 페이지 프레임 번호로 변경하면 물리 주소를 구하게 된다.

페이지 테이블 엔트리 구조
　엔트리의 구조는 CPU에 따라 다르며 하드웨어 종속적이다. 하지만 모든 CPU들이 공통으로 가지고 있는 정보들이 있는데 다음은 공통적인 페이지 테이블 엔트리 구조를 보여준다.

　엔트리의 크기 역시 시스템에 따라 다르나 일반적으로 32비트 크기를 갖는다.

• 엔트리의 가장 중요한 부분은 페이지 프레임 번호(page frame number)이다.
  • 가상 주소를 물리 주소로 매핑하는 기능을 담당한다.
• 그 다음으로 중요한 필드는 present/absent 비트이다.
  • 이 비트가 1이면 해당 엔트리가 유효하며 페이지 프레임 번호를 사용할 수 있다. 반면 0이면 해당 엔트리에 대응되는 페이지가 물리 메모리에 존재하지 않은 상태이다.
  • 이 엔트리에 대한 접근은 결국 페이지 폴트를 야기한다.
• 보호비트(Protection bit)는 어떤 접근이 혀용되어 있는지를 표시한다.
  • 가장 간단한 형태는 1비트의 보호 정보를 갖는 것이며 1일 경우 읽기만 가능하고 0일 경우 읽기/쓰기가 모두 가능하다.
  • 좀더 복잡한 경우에는 3비트로 구성되며 각 비트는 읽기, 쓰기, 실행이 가능한지 여부를 표시한다.
• 수정비트(Modified bit)와 참조비트(Reference bit)는 페이지 사용을 표현한다.
  • 수정비트
    • 페이지의 내용이 변경되면 하드웨어는 자동으로 수정 비트를 설정한다. 수정비트는 운영체제가 페이지 프레임을 교체할 때 영향을 준다.
    • 만일 수정 비트가 1로 설정되어 있으면(“dirty”), 이 페이지 프레임은 교체될 때 그 내용이 디스크에 기록되어야 한다. 반면 0이면(“clean”) 이 페이지 프레임 내용은 디스크에 쓰여질 필요 없이 새로운 내용으로 덮여 쓰여져도 된다. 이것은 유효한 내용이 디스크에 이미 존재하기 때문이다.
    • 이 비트는 페이지의 상태를 반영하기 때문에 더티 비트(dirty bit)이라고도 불린다.
  • 참조비트
    • 참조 비트는 해당 페이지가 읽기 또는 쓰기로 접근되었을 때 설정된다. 이 비트는 운영체제가 페이지 폴트 처리를 위해 교체할 페이지 프레임을 선택할 때 이용된다.
    • 최근에 사용된 페이지 보다는 그렇지 않은 페이지를 교체 대상으로 선택하는 것이 성능에 좋다. 이 선택에 참조 비트가 이용되며, 다양한 페이지 교체 알고리즘에서 이 비트가 중요한 역할을 한다.
• 캐시 무효화(caching disabled) 비트는 해당 페이지가 캐싱될 수 있는지 여부를 가리킨다.
  • 이 기능은 페이지가 메모리가 아닌 장치 레지스터에 매핑되어 있을 때 중요한 역할을 실행한다.
  • 운영체제가 특정 장치에게 요청을 보내고 응답을 기다리고 있다면 CPU가 그 장치의 상태를 나타내는 레지스터 내용을 직접 읽어야지 캐싱되어 있는 오래 전 데이터를 읽어서는 안 된다. 이 비트를 이용해 페이지의 캐싱을 끌 수 있다.
  • 시스템의 I/O 주소가 메모리에 매핑된 공간(memory mapped I/O)이 아닌 별도의 I/O 주소 공간(separated I/O)을 사용하는 시스템에서는 이 비트가 필요 없다.

페이징 속도 향상

　페이징 시스템의 다음의 두 가지 중요한 문제를 해결해야 한다.

• The page table can be extremely large
  • 가상 주소 공간이 커지면 페이지 테이블의 크기도 커진다.
  • 최근 컴퓨터는 가상 주소를 위해 32비트를 사용하며 64비트를 사용하는 경우도 많아지고 있다. 따라서 페이지 테이블의 크기도 고려해야 한다.
  • 예를 들어 만일 4KB 크기의 페이지를 사용한다면 32비트 시스템에서는 백 만개의 페이지가 필요하며($\frac{2^{32}}{2^{12}(= 4\mathrm{KB})} = 2^{20} = 100만$ ) 64비트 시스템에서는 우리가 상상한 것보다 훨씬 많은 페이지가 존재하게 된다. 백 만개의 페이지가 존재하기 위해서는 백 만개의 페이지 테이블 엔트리가 필요하다.
  • 각 프로세스마다 자신 고유의 주소 공간을 갖기 때문에 각 프로세스마다 자신의 고유한 페이지 테이블을 갖는다.
• The mapping must be fast
  • 가상 주소에서 물리 주소로 주소 변환은 빠르게 이루어져야 한다.
  • 메모리가 참조될 때마다 가상 주소와 물리 주소 간에 변환이 필요하기 때문에 주소 변환은 빠르게 이루어져야 한다.
    

　크고 빠른 페이지 매핑의 요구는 컴퓨터 시스템을 구현하는데 크게 영향을 주었다. 두가지 구현 방법이 있다.

• 빠른 하드웨어 레지스터 배열로 구성된 단일한 페이지 테이블(single page table)을 사용한다.
  • 이 테이블의 각 엔트리는 각각 가상 페이지에 대응되며 가상 페이지 번호에 의해 인덱싱된다.
  • 프로세스가 실행될 때 운영체제는 메모리에 존재하던 프로세스의 페이지 테이블 전체를 하드웨어 레지스터 배열에 적재한다.
  • 프로세스의 실행 중에는 페이지 테이블을 위한 메모리 참조는 필요없다.
  • 이 방법의 장점은 직관적이며 주소 변환을 위한 추가적인 메모리 참조가 없다. 반면 페이지 테이블의 크기가 커지면 구현을 위한 비용이 커지고 문맥교환 시점에 페이지 테이블 전체를 적재하는 비용이 크다.
• 페이지 테이블의 모든 내용을 메모리에 유지한다.
  • 페이지 테이블 시작 주소를 가리키는 하나의 레지스터만 있으면 된다.
  • 문맥교환 시점에 단지 이 레지스터의 내용만 변경하면 된다는 장점이 있다. 반면 각 명령을 실행할 때마다 페이지 테이블 엔트리를 참조하기 위한 최소한 한번의 메모리 참조가 더 필요하게 되며 결국 실행이 느려진다.

Translation Lookaside Buffers
　대부분의 프로그램들이 적은 개수의 페이지들을 집중적으로 참조하는 경향이 있다. 결국 페이지 테이블 엔트리 중에서 일부만 빈번하게 참조되며 다른 엔트리들은 아주 드물게 참조되는 것이다. 이를 해결하기 위한 방법은 페이지 테이블 참조 없이 가상 주소를 물리 주소로 매핑할 수 있는 작은 하드웨어를 사용하는 것이다. 이 하드웨어를 TLB(Translation Lookaside Buffer)또는 연관 메모리(associative memory)라고 부르며 구조는 다음과 같다.

　이것은 일반적으로 MMU 내부에 존재하며 적은 개수의 엔트리를 갖는다. 위에서는 8개의 엔트리를 가지고 있으며, 대부분 64개 미만의 엔트리를 갖는다. 각 엔트리는 한 페이지에 대한 정보를 포함한다. 구체적으로 가상 페이지 번호, 페이지 수정 여부를 나타내는 비트, 보호 코드(읽기/쓰기/실행 허가), 물리 페이지 프레임 번호 등을 포함한다. 각 정보들은 실제 페이지 테이블 엔트리에 저장되어 있는 정보들이다. 다만 페이지 번호는 실제 저장 되어 있는 것은 아니며 페이지 테이블 엔트리의 인덱스로 알아낼 수 있다. TLB 엔트리의 첫 번째 필드는 valid 비트이며 엔트리가 유효한지 여부를 나타낸다.
　TLB가 어떻게 동작하는지 알아보자.

• MMU는 주소 변환을 할 때 우선 요청된 가상 페이지 번호가 TLB에 있는지 검색한다.
  • 이때 모든 엔트리를 동시에(즉, 병렬로) 검색한다.
• 만일 페이지가 존재하고 유효하며 보호 코드를 위반하지 않는다면 대응되는 페이지 프레임을 사용하여 주소 변환을 실행한다.
  • 즉, 메모리에 있는 페이지 테이블에 대한 접근이 필요 없다. 만일 보호 코드를 위반한다면(예를 들어, 읽기 가능 페이지인데 쓰기 시도를 한다면) 보호 결함(protection fault)이 발생한다.
• TLB에 참조하는 페이지 번호가 존재하지 않는다면 TLB 미스가 발생한다.
  • MMU는 페이지 테이블을 검색하여 해당 페이지 테이블 엔트리를 찾는다. 그리고 TLB 엔트리 중에 하나를 선택하여 그 내용을 교체하고 새로 찾은 페이지 테이블 엔트리 내용을 선택한 TLB 엔트리에 기록한다. 이후 이 페이지가 다시 참조된다면 이때부터는 TLB 미스가 아닌 TLB 히트가 발생한다.
• TLB 엔트리가 교체될 때 수정 비트는 페이지 테이블에 기록한다.
  • 참조 비트를 제외한 다른 정보들은 이미 페이지 테이블에 기록되어 있다. 새로운 정보가 메모리에서 TLB로 적재될 때에는 대응하는 페이지 테이블 엔트리에 있는 내용들이 적재된다.

대용량 메모리를 위한 페이지 테이블

　페이지 테이블을 이용한 주소 변환에서 TLB를 사용하면 가상 주소를 물리 주소로 변환할 때 속도를 향상시킬 수 있다. 하지만 문제는 이것 만이 아니다. 큰 가상 공간을 효과적으로 관리하는 방법이 필요하다. 이 문제에 대한 두 가지 접근 방법이 있다.
다단계 페이지 테이블(multilevel page table)

　(a)는 32비트 가상 주소가 3 부분으로 구분되어 있는 것을 보여준다. 구체적으로 2개의 페이지 테이블 필드 10비트의 PT1 필드, 10비트의 PT2 필드, 그리고 12비트의 Offset 필드로 구분된다. 오프셋 부분이 12비트이므로 페이지의 크기는 4KB가 되고, 나머지 20비트로 페이지를 지정할 수 있으며 결국 $2^{20}$개의 페이지가 존재할 수 있다.
　다단계 페이지 테이블의 핵심은 모든 페이지 테이블을 항상 메모리에 유지할 필요가 없다는 것이다. 특히 주소 공간에 비어있는 부분을 전혀 유지할 필요가 없다.
　(b)는 2단계 페이지 테이블(second-level page tables)의 동작 과정을 보여준다.

역 페이지 테이블(inverted page table)
　다단계 페이지 테이블에서 주소공간이 $2^{64}$바이트라면 4KB 페이지를 사용할 경우 $2^{52}$개의 엔트리가 요구된다. 각 엔트리의 크기를 8바이트로 잡으면 페이지 테이블 크기가 3천만 GB가 된다. 이는 좋은 생각이 아니다.
　다른 접근 방법 중 하나가 역 페이지 테이블이다. 이 방법에서는 가상 주소 공간의 각 페이지마다 엔트리가 하나씩 존재하는 것이 아니라 물리 메모리의 각 페이지 프레임마다 하나의 엔트리가 존재한다. 예를들어, 64비트 가상 주소공간(4KB 페이지)이라 할지라도 만일 물리 메모리의 크기가 1GB라면 262,144개($\frac{1 \mathrm{GB}}{4 \mathrm{KB}} = 2^{18} = 262144$)의 엔트리만 있으면 된다. (물리 메모리의 크기가 256MB 라면 $\frac{256 \mathrm{MB}}{4 \mathrm{KB}} = 64 \times 2^{10} = 2^{16}$) 각 엔트리는 각 페이지 프레임에 어떤 프로세스의 페이지가 존재하는지에 대한 정보 즉, (프로세스 번호, 페이지 번호) 정보를 유지한다.
　가상 주소 공간이 물리 주소 공간에 비해 상당히 클 경우 역 페이지 테이블은 주소 변환을 위한 메모리 공간의 사용을 크게 줄일 수 있다. 반면, 가상-물리 주소 변환이 복잡해진다는 단점이 있다. 프로세스 n이 가상 페이지 p를 접근할 때 MMU는 더 이상 p를 페이지 테이블의 인덱스로 사용하여 물리 페이지 프레임을 알아낼 수 없다. 그 대신, 역 페이지 테이블 전체를 검색하여 (p, v)를 갖는 엔트리가 있는지 검사한다. 이 검색은 페이지 폴트가 발생했을 때 만이 아니라 메모리 참조가 있을 때마다 발생한다. 이는 컴퓨터 시스템을 무척 느리게 할 것이다.
　이 문제를 해결하는 방법 중 하나는 TLB를 사용하는 것이다. TLB가 자주 접근하는 페이지들의 정보를 유지하고 있으면 주소 변환은 다단계 페이지 테이블 기법만큼의 속도로 실행될 수 있다. 하지만 TLB 미스의 경우 역 페이지 테이블 검색은 여전히 요구된다. 검색을 빠르게 하는 한가지 방법은 가상 주소를 기반으로 해쉬 테이블을 이용하는 것이다. 메모리 상에 존재하는 페이지들 중 같은 해쉬 값을 갖는 페이지들은 다음과 같이 체인으로 연결된다.

　만일 해쉬 테이블이 물리 페이지 프레임 크기만큼의 슬롯을 가지고 있다면 각 체인은 평균 하나의 엔트리를 가지게 되며 따라서 매핑 속도가 증가한다. 일단 페이지 프레임 번호가 발견되면 새로운 (가상, 물리) 정보는 TLB에 적재된다.

페이지 교체 알고리즘(Page Replacement Algorithms)

　페이지 폴트가 발생하면 운영체제는 새로 진입할 페이지를 위한 공간을 만들기 위해 이미 존재하고 있는 페이지 중에 하나를 내 보내야 (메모리에서 제거해야) 한다. 만일 내보낼 페이지가 변경되어 있다면 그 페이지의 내용은 디스크로 보내져 기록되어야 한다. 반면, 페이지가 변경되지 않았다면 디스크에 기록할 필요는 없다. 새로 읽혀진 페이지는 쫓겨난 페이지가 차지하고 있던 공간을 차지한다.
　내보낼 페이지를 임의적(random)으로 선택할 수 있다. 하지만 임의적으로 선택하는 것 보다는 자주 사용되지 않을 페이지를 선택하는 것이 시스템 성능에 도움이 된다. 만일 자주 사용될 페이지를 선택한다면 곧 다시 페이지 폴트를 맞게 되고 다시 메모리로 가져오는 추가적인 부하를 야기하게 될 것이다. 어떤 페이지를 교체할까에 대한 문제가 페이지 교체 알고리즘이다.

최적 페이지 교체 알고리즘(Optimal Page Replacement Algorithm)

　가장 좋은 페이지 교체 알고리즘은 설명하기는 쉽지만 실제 구현하기는 불가능하다. 이 알고리즘의 동작 원리는 다음과 같다. 페이지 폴트가 발생했을 때, 이미 메모리에 몇 개의 페이지들이 존재한다고 가정한다.

• 최적 페이지 교체 알고리즘은 가장 큰 레이블을 갖는 페이지를 교체한다.
  • 만일 8백만 명령어 뒤에 참조되는 페이지와 6백만 명령어 뒤에 참조되는 페이지가 있다면, 앞에 있는 페이지를 교체하게 된다.
• 결국 교체에 따른 페이지 폴트 발생을 가능한 많이 뒤로 미룰수 있다.

　이 알고리즘의 유일한 단점은 구현이 불가능하다는 것이다. 하지만 이러한 방법으로 최적의 알고리즘과 실제 구현 가능한 알고리즘과 성능 비교가 가능하다. 만일 운영체제가 현재 사용하는 알고리즘이 최적의 알고리즘에 비해 $1\%$성능이 나쁘다면 더 좋은 알고리즘에 대한 노력은 최대 $1\%$의 성능 향상을 가져올 수 있다.

NRU 페이지 교체 알고리즘(Not Recently Used Page Replacement Algorithm)

　가상 메모리를 지원하는 대부분의 컴퓨터는 각 페이지마다 운영체제가 페이지 사용 정보를 수집할 수 있도록 하기 위한 2개의 상태 비트를 유지한다.

• 참조 비트(referenced bit, R): 페이지가 참조될 때마다 설정된다. (read, written)
• 변경 비트(modified bit, M): 페이지가 수정될 때마다 설정된다. (written)

　R과 M 비트는 간단한 페이지 교체 알고리즘을 만드는 데 효과적으로 이용될 수 있다. 구체적으로 프로세스가 시작할 때 운영체제는 그 프로세스 모든 페이지의 R과 M비트를 0으로 클리어한다. 또한 최근에 참조된 페이지와 그렇지 않은 페이지를 구분하기 위하여 주기적으로 R 비트를 클리어한다.

　페이지 폴트가 발생하면 운영체제는 R과 M 비트의 현재 값에 따라 모든 페이지들을 다음 4가지 카테고리로 구분한다.

• 클래스0: 참조되지 않았고, 수정되지 않음 (R bit = 0, M bit = 0)
• 클래스1: 참조되지 않았고, 수정되었음 (R bit = 0, M bit = 1)
• 클래스2: 참조되었고, 수정되지 않음 (R bit = 1, M bit = 0)
• 클래스3: 참조되었고, 수정되었음 (R bit = 1, M bit = 1)

　NRU(Not Recently Used) 알고리즘은 클래스 0, 1, 2, 3 순서로 페이지를 교체한다. 만일 클래스0 상태의 페이지가 여러 개 있다면 그 중에 임의로 한 페이지를 선택하여 교체한다. 이 알고리즘의 기본 아이디어는 가장 최근의 클록 틱 간격(보통 20ms)동안 참조되지 않은 변경된 페이지를 교체하는 것이, 집중적으로 참조되는 변경되지 않는 페이지를 교체하는 것보다 좋다는 것이다. NRU 알고리즘은 이해하기 쉬우며, 비교적 효율적으로 구현할 수 있다. 또한 좋은 성능을 제공한다는 장점이 있다.

FIFO 페이지 교체 알고리즘(First-In First-Out Page Replacement Algorithm)

　운영체제는 현재 메모리에 존재하는 모든 페이지들을 리스트(linked list)로 관리한다. 가장 최근에 메모리에 적재된 페이지는 리스트의 뒤(tail)로 가고 가장 과거에 적재된 페이지는 리스트의 앞(head)에 존재하게 된다. 페이지 폴트가 발생하면 리스트 앞에 있는 페이지가 교체되고 새로운 페이지는 리스트의 가장 뒤에 적재된다. 하지만 자주 찾는 페이지를 제거할 수 있다는 문제가 발생한다. 이 때문에 순수한 형태의 FIFO를 페이지 교체 알고리즘으로 사용하는 시스템은 드물다.

Second-Chance 페이지 교체 알고리즘(Second-Chance Page Replacement Algorithm)

　FIFO는 자주 참조되는 페이지를 교체할 가능성이 있다는 문제가 있다. 이 문제를 피하는 방법 중 하나는 가장 오래된 페이지의 R 비트를 이용하는 것이다. 만일 R이 0이면 이 페이지는 가장 오래된 페이지이며 동시에 최근에 사용되지 않은 페이지이다. 따라서 교체해도 된다. 반면 R이 1이면 이 페이지를 리스트의 뒤로 옮기고 R 비트를 0으로 클리어하며 적재 시간도 현재 시간으로 갱신한다. 마치 이 페이지가 방금 적재된 것처럼 한번 더 기회를 주는 것이다. 그리고 이제 리스트 가장 앞에 있는 페이지 R을 검사한다.
　이 알고리즘을 second chance라고 부르며, 동작 예는 다음과 같다.

• (a)에는 A~H 페이지들이 존재하고 모든 페이지들이 FIFO 순서로 정렬되어 있다.
• 20 시간에 페이지 폴트가 발생했다고 가정하면, 가장 오래된 페이지는 A로 0 시간, 즉 프로세스가 시작한 시간에 적재된 것이다.
• 만일 이 페이지의 R이 0이면 교체된다. M이 1이면 디스크에 쓰고 0이면 그대로 버리면 된다.
• 반면, 이 페이지의 R이 1이면 A는 리스트의 끝으로 이동되고 적재 시간은 20으로 갱신된다. 그리고 A의 R 비트는 0으로 클리어된다.
  • 이후 다시 B를 교체해도 되는지 조사를 계속한다.

　결국 second chance 알고리즘이 교체하려는 페이지는 오래 되었으며 동시에 가장 최근의 클록 간격에 참조가 되지 않은 페이지이다. 만일 모든 페이지가 참조되었다면 second chance 알고리즘은 FIFO 알고리즘과 동일하게 동작한다. 예를 들어 위의 그림(a)의 모든 페이지들의 R 비트가 1이라고 가정해 보면, 운영체제는 페이지를 하나씩 리스트의 뒤로 이동시키며 R 비트를 0으로 클리어 시킨다. 결국 A 페이지로 다시 돌아오게 되고 이떄에는 R 비트가 0으로 되어 있다. 따라서 A가 교체되고 이 알고리즘은 종료된다.

클록 페이지 교체 알고리즘(The Clock Page Replacement Algorithm)

　second chance 알고리즘이 교체할 페이지를 적정하게 선택하기는 하지만 페이지를 리스트에서 이동시켜야 하기 때문에 동작의 효율성이 저하될 가능성이 있다. 더 효과적인 방법은 모든 페이지들을 다음과 같이 클록 형태의 환형 리스트로 관리하는 것이다. 화살표는 가장 오래된 페이지를 가리킨다.

　페이지 폴트가 발생하면 화살표가 가리키는 페이지를 조사한다. 만일 이 페이지의 R 비트가 0이면 이 페이지를 교체하고, 이 위치에 새로운 페이지를 삽입하고, 화살표를 다음 페이지를 가리키도록 전진시킨다. 반면 R이 1이면, 이 비트는 클리어되고 다음 페이지로 전진하여 그 다음 페이지를 조사한다. 이 과정은 R이 0인 페이지를 찾을 떄까지 반복된다. 이 알고리즘을 시계에서 시계 바늘의 움직임을 연상시키기에 클록(clock) 알고리즘이라 불린다.

LRU 페이지 교체 알고리즘(Least Recently Used page Replacement Algorithm)

　최적의 페이지 교체 알고리즘과 유사하게 동작하는 알고리즘은 다음과 같은 관찰을 기반으로 한다. 가장 최근의 명령어들에 의해 자주 접근된 페이지들을 가까운 미래에도 자주 접근될 확률이 높다. 역으로 오랫동안 참조되지 않은 페이지는 이후로도 사용되지 않을 확률이 높다. 이 관찰은 “페이지 폴트가 발생하면 가장 오랫동안 사용되지 않은 페이지를 교체하자”라는 알고리즘을 가능하게 한다. 이 알고리즘이 LRU(Least Recently Used)이다.
　LRU 알고리즘은 구현 비용이 많이 든다. LRU를 위해서는 메모리 내에 있는 모든 페이지들이 리스트로 연결되어 있어야 하며, 가장 최근에 참조된 페이지는 리스트의 앞에 그리고 가장 과거에 참조된 페이지는 리스트의 뒤에 위치해야 한다. 이때 어려운 것은 모든 메모리 참조마다 리스트를 갱신해야 한다는 것이다. 리스트에서 페이지를 찾고, 삭제하고, 리스트의 가장 앞으로 이동하는 작업은 시간이 많이 걸리는 작업이다. 심지어 하드웨어 적으로 동작해도 부하가 크다.
　LRU를 리스트가 아닌 다른 특별한 하드웨어의 지원으로 구현할 수도 있다. 우선 아주 간단한 방법부터 살펴본다.

• 이 방법은 C라는 64비트 카운터를 필요로 한다.
  • 이 카운터는 명령어가 실행될 때마다 1씩 증가한다.
  • 한편 각 페이지 테이블 엔트리는 카운터 값을 저장할 수 있는 공간을 가지고 있다.
• 메모리가 참조될 때마다 참조된 메모리를 담고 있는 페이지를 가리키는 페이지 테이블 엔트리에 C의 값이 저장된다.
• 페이지 폴트가 발생하면 운영체제는 모든 페이지 테이블 엔트리의 카운터 값을 조사하여, 가장 적은 값을 갖는 페이지를 교체한다.
  • 이 페이지가 LRU 페이지이다.

　다른 하드웨어 지원을 이용한 LRU 구현 방법을 살펴 본다.

• 시스템이 n개의 페이지 프레임을 가지고 있다면 LRU 하드웨어는 n$\times$n 비트로 구성된 행렬을 갖는다.
  • 초기에 이 행렬의 모든 비트는 0값을 갖는다.
• 페이지 프레임 k가 참조되면 하드웨어는 행렬에서 k번째 행의 모든 비트를 1로 설정한다. 그리고 k 번째 열의 모든 비트를 0으로 설정한다.
  • 이 행렬에서, 행의 이진 값이 가장 작은 행에 대응되는 페이지 프레임이 가장 과거에 참조된 것이 된다.
  • 그 다음 작은 값을 갖는 행에 대응되는 페이지 프레임이 두 번째로 오래 전에 참조된 것이다.

　다음 그림은 이 알고리즘의 동작 예를 보여준다.

　위에서 시스템은 4개의 페이지 프레임을 갖고 있다. 그리고 페이지는 다음 순서로 참조되었다.

0 1 2 3 2 1 0 3 2 3

　페이지 0이 참조된 후 행렬의 상태가 (a)에, 페이지 1이 참조된 후 행렬의 상태가 (b)에 도시되어 있다. (c)~(i)는 그 이후 페이지가 참조된 이후 행렬의 상태를 보여준다.

소프트웨어로 LRU 시뮬레이션

NFU(Not Frequently Used) 알고리즘

• 각 페이지마다 소프트웨어 카운터를 유지한다.
  • 이것은 0으로 초기값을 갖는다.
• 클록 인터럽트가 발생할 때마다 운영체제는 메모리의 모든 페이지를 검사하여 R 비트의 값을 소프트웨어 카운터에 더한다.
  • 이 카운터는 각 페이지들이 얼마나 자주 참조되었는지 알려준다.
• 페이지 폴트가 발생하면 가장 적은 카운터 값을 갖는 페이지가 교체된다.

　NFU 기법의 문제는 잊어버리는 기능이 없다는 것이다. 예를 들어 다중 패스 컴파일러의 경우, 첫 번째 패스에서 자주 참조된 페이지들은 높은 카운터 값을 가지게 되고, 이 값은 두 번째 이후의 패스에서도 유지된다. 실제로, 만일 첫 번째 패스가 그 이후 다른 패스들보다 더 긴 실행 시간을 가진다면, 패스 1에서 실행된 페이지들은 그 이후 패스에서 사용되는 페이지들에 비래 더 큰 값을 갖게 된다. 그 결과 운영체제는 패스 1에서 사용되던 더 이상 사용되지 않는 페이지가 아닌, 현재 패스에서 사용하는 유용한 페이지들을 교체하게 된다.
　NFU를 약간 변경하면 LRU와 비슷한 성능을 얻을 수 있다. 변경은 두 부분으로 구성된다. 첫 번쨰, 카운터는 R 비트를 더하기 전에 오른쪽으로 1 비트 시프트한다. 두 번째, R 비트는 오른쪽 비트가 아닌 왼쪽 최상위 비트에 추가된다.

에이징(Aging) 알고리즘
　다음은 에이징(aging) 알고리즘이라 불리는 NFU의 변형된 알고리즘의 동작 예를 보여 준다.

　클록 틱0 시점에서 페이지 0~5의 R 비트 값이 각각 1, 0, 1, 0, 1, 1이라고 가정한다. 즉, 클록 틱0과 그 전 클록 틱 간격 동안 페이지 0, 2, 4, 5가 참조된 것이다. 따라서 이 페이지들의 R 비트는 1, 나머지는 0으로 설정되어 있다.

• 각 페이지의 카운터 값이 오른쪽으로 1비트 시프트한다.
• R 비트의 값이 가장 상위 비트에 추가된다.
  • 그 결과가 위 그림(a)에 나타나 있다.
  • 그림(b)~(e)는 그 이후 4개의 클록 틱이 발생했을 때 각 페이지의 카운터 변수 값을 보여준다.
• 페이지 폴트가 발생하면 카운터 값이 가장 적은 페이지가 교체된다.
  • 네 번의 클록 틱이 발생할 동안 참조되지 않은 페이지는 카운터 값의 상위 4비트가 0이 되며, 반면 세 번의 클록 틱이 발생할 동안 참조되지 않은 페이지는 카운터 값의 상위 3비트가 0이 된다. 따라서 전자의 페이지가 후자의 페이지보다 더 적은 카운터 값을 갖게 되며, 결국 우선적으로 교체된다.
    

　에이징 알고리즘은 LRU에 비해 다음 두 가지 차이가 있다. (e)에서 페이지 3과 5를 고려해 보자. 두 페이지 모두 최근 두 번의 클록 틱 간격에서 참조되지 않았다. 하지만 바로 그 이전 클록 틱 간격에서는 두 페이지 모두 참조 되었다. LRU 원칙에 따르면 두 페이지 중에 더 과거에 참조된 페이지가 먼저 교체되어야 한다. 문제는 이 두 페이지 중에서 어떤 페이지가 더 먼저 참조되었는지 모른다는 것이다. 이것은 클록 틱 간격 동안 하나의 비트로 참조 여부만 기록하였기 때문에 발생하며, 결국 시간 순서를 구별할 수 있는 정보를 기록하지 않았기 때문에 발생한 것이다. 에이징 알고리즘은 페이지 3을 교체한다. 이는 페이지 5가 두번의 클록 틱 전에 한번 더 참조되었고 페이지 3은 그렇지 않았기 때문이다.
　LRU와 에이징 알고리즘의 두 번째 차이는 카운트 값이 제한된 비트로 구성된다는 것이다.(위 예에서는 8비트) 이것은 과거에 대한 정보 기억을 제한한다. 예를 들어 두 페이지의 카운터 값이 모두 0이라고 가정해 보자. 에이징은 두 페이지 중 임의의 한 페이지를 교체한다. 이때 교체된 페이지가 9번째 클록 틱 전에 참조된 것이고 남겨둔 페이지가 1000번째 클록 틱 전에 참조된 것일 수도 있다. 하지만 실질적으로는, 만일 클록 틱이 20ms 간격으로 발생한다면 8개의 비트면 비교적 충분하다. 페이지가 최근 160ms 동안 참조되지 않았다면 참조되지 않을 페이지일 가능성이 높다.

작업 집합 페이지 교체 알고리즘

　순수한 형태의 페이징 시스템에서는 프로세스가 시작할 때 미리 메모리에 존재하는 페이지는 없다. CPU가 첫 번째 명령을 반입하려고 할 때 페이지 폴트가 발생하며 이때 운영체제가 첫 번째 명령을 반입하려고 할 때 페이지 폴트가 발생하며 이 때 운영체제가 첫 번째 명령어를 담고 있는 페이지를 메모리로 적재한다. 전역 변수나 스택에 대한 접근도 페이지 폴트를 야기하며, 역시 운영체제가 해당 페이지를 적재한다. 조금 지나면 프로세스는 자신이 필요한 대부분의 페이지를 폴트를 통해 메모리로 올리게 되고, 그 이후에는 비교적 적은 페이지 폴트를 야기하며 실행된다. 이러한 요구 전략을 요구 페이징(demand paging)이라고 한다. 요구 페이징은 미리 적재하는 것이 아니라 필요할 때 페이지를 적재한다.
　대부분의 프로세스들은 모든 페이지들을 균일하게 접근하지 않는다. 그 대신 프로세스들은 참조 지역성(locality of reference)을 보인다. 참조 지역성이란 프로세스가 실행되는 각 단계에서 전체 주소 공간의 일부 페이지들을 집중적으로 참조하는 경향을 의미한다. 예를 들어 다중패스 컴파일러의 경우 각 패스는 일부의 페이지들만 집중적으로 참조하며, 각 패스마다 참조하는 페이지 부분은 서로 다르다.
　프로세스가 현재 자주 참조하는 페이지들의 집합을 작업 집합(working set)이라고 한다. 전체 작업 집합이 모두 메모리에 존재하면, 프로세스는 다음 실행 단계로 전이하기 전까지는 많은 페이지 폴트를 야기하지 않으며 실행될 수 있다. 만일 가용 메모리 공간이 너무 적어서 전체 작업 집합을 모두 유지할 수 없다면 프로세스는 많은 페이지 폴트를 야기하고 결국 실행 시간이 크게 증가한다. 한 개의 명령을 실행하기 위해 10밀리초를 사용하게 되면 프로세스의 진행은 크게 느려진다. 이러한 상황을 스래싱(thrashing)이라고 한다.
　많은 페이징 시스템은 프로세스의 작업 집합을 파악하고 이들을 프로세스가 시작하기 전에 메모리에 유지하기 위해 노력한다. 이러한 접근 방법을 작업 집합 모델(working set model)이라고 한다. 이 모델은 페이지 폴트 발생률을 줄이는 것을 목표로 한다. 프로세스가 시작하기 전에 페이지를 적재하는 것을 선페이징(prepaging)이라고도 한다. 시간이 지남에 따라 작업 집합도 변한다는 것에 주의할 필요가 있다.
　대부분의 프로그램은 자신의 주소 공간에 있는 모든 페이지를 동일한 확률로 접근하는 것이 아니라 일부 페이지들을 집중적으로 참조한다. 메모리 참조는 명령어 반입, 데이터 읽기, 데이터 쓰기 등이 있다. 현재 시간 t에서 볼 때 우리는 지금까지 참조된 페이지 중에서 가장 최근에 참조된 k개의 페이지를 파악할 수 있다. 이 집합 w(t, k)를 작업 집합이라고 한다. k = 1은 가장 최근에 참조된 페이지 만을 갖는 작업 집합이 되며, k > 1은 가장 최근에 참조된 페이지를 포함한 페이지 집합이 된다. 따라서 w(t, k)가 주소 공간에 포함된 전체 페이지 이상의 값을 가질 수 없기 때문이다. 다음 그림은 k값의 변화에 따른 작업 집합의 변화를 보여준다.

　대부분의 프로그램이 적은 숫자의 페이지들만 참조하며 참조되는 페이지들은 시간이 지남에 따라 천천히 변한다는 사실은, 위 그래프가 초반에는 급격하게 증가되다가 k가 일정 이상의 크기가 되면 약간씩 증가하는 이유가 된다.
　작업 집합 모델에 대한 명확한 정의를 갖는 것이 이를 효율적으로 구현할 수 있는 방법이 있다는것을 의미하지는 않는다. 대표적인 한 방법으로는 최근 k개의 메모리 참조 대신 실행 시간을 사용한다. 예를 들어 작업 집합을 정의할 때 가장 최근 천만개의 메모리 참조에서 사용된 페이지들로 정의하는 것이 아니라, 최근 100밀리초의 실행 시간 동안 사용된 페이지들로 정의하는 것이다. 실제 시스템에서 시간을 사용하는 방법이 프로세스의 작업 집합을 적절하게 파악하며, 또한 구현도 비교적 간단한 것으로 판명되었다. 우선 각 프로세스마다 자신의 고유한 실행 시간을 유지한다. 만일 한 프로세스가 T 시간에 실행을 시작했고 실시간 T + 100 밀리초가 아닌 40 밀리초만 실제 CPU에서 실행 되었다면, 이 프로세스의 실행시간은 100 밀리초가 아닌 40 밀리초가 된다. 프로세스가 시작되어 실제로 사용한 CPU 시간을 각 프로세스의 현재 가상 시간(current virtual time)이라고 한다. 이러한 근사를 사용하면 한 프로세스의 작업 집합은 최근 $\tau$ 가상 시간 동안 참조된 페이지의 집합으로 정의 된다.
　작업 집합에 기반한 페이지 교체 기법을 살펴본다. 기본 아이디어는 현재 작업 집합에 포함되어 있지 않은 페이지를 교체하자는 것이다. 교체의 대상이 되는 것은 이미 메모리에 존재하는 페이지이며, 따라서 메모리에 존재하지 않는 페이지들은 이 알고리즘의 고려 대상에서 제외된다. 다음 그림에서처럼 페이지 테이블의 각 엔트리는 최소한 두 개의 키 정보를 유지한다.

　첫 번째는 페이지가 마지막으로 사용된 (근사)시간이며, 두 번째는 R(referenced) 비트이다. 그림에서 비어있는 사각형은 엔트리가 유지하는 다른 정보들로 이 알고리즘과 관련이 없기 때문에 빈 사각형으로 표현하였다.(예를 들면, 페이지 프레임 번호, 보호 비트, M 비트 등)
　알고리즘은 다음과 같이 동작한다. M과 R비트는 하드웨어가 관리한다. 또한 매 클록 틱 마다 클록 인터럽트에 의해 소프트웨어적으로 R 비트는 주기적으로 클리어 된다. 페이지 폴트가 발생하면 페이지 테이블을 검사하여 교체할 페이지를 선택한다.

• 우선 각 페이지 테이블 엔트리에서 R비트를 검사한다.
• 만일 1이면 현재 가상 시간을 엔트리의 Time of last use 필드에 기록한다.
  • 즉, 페이지 폴트가 발생한 시각에 그 페이지가 사용 중이었음을 기록한다.
  • 실제로 이 페이지는 최근 클록 틱이 발생한 간격에서 참조가 되었으며, 따라서 작업 집합에 속한 페이지로 교체의 대상이 되지 않는다.
• 만일 R이 0이면 이번 클록 틱이 발생한 간격에 참조되지 않았다는 의미이며 따라서 교체의 후보가 된다.
  • 교체할지 여부는 이 페이지의 나이에 의해 결정된다. 나이는 “현재 시간 - Time of last use 필드에 기록된 시간”으로 계산 된다.
• 만일 나이가 $\tau$보다 크면 이 페이지는 작업 집합에 더이상 포함되어 있지 않다는 의미이며, 새로운 페이지가 이것을 교체한다.
  • 페이지 테이블 엔트리가 아직 남아 있으면 검사를 계속하여 갱신한다.
• R비트는 0이지만 나이가 $\tau$보다 작거나 같으면 그 페이지는 여전히 작업 집합에 속해있는 것이다.
  • 이 페이지는 교체의 대상이 되지는 않고 일단 유지된다.
  • 그 대신 가장 큰 나이를 갖는 페이지(가장 작은 Time of last use를 갖는 페이지)를 기억해 둔다.
  • 만일 전체 페이지 테이블을 검사한 이후, 교체할 페이지 즉, 작업 집합에 속해 있지 않은 페이지를 발견하지 못하면, R이 0인 페이지 중에서 나이가 가장 큰 페이지를 교체하게 된다.
• 최악의 경우, 만일 모든 페이지의 R이 1이었다면, 이들 중에 하나가 임의적으로 교체된다.
  • 가능하면 수정된 페이지 보다는 수정되지 않은 페이지를 교체한다.

WSClock 페이지 교체 알고리즘

　기존의 작업 집합 기반 페이지 교체 알고리즘의 단점은 페이지 폴트가 발생할 때마다 교체할 페이지를 선택하기 위해 전체 페이지 테이블을 검사해야 한다는 것이다. 이를 개선한 알고리즘이 WSClock이다. 이 알고리즘은 클록 알고리즘을 기반으로 작업 집합 정보를 관리한다. 이 알고리즘은 구현이 간단하고 좋은 성능을 보이기 때문에 실제 시스템에서 많이 사용한다.
　이 알고리즘은 클록 알고리즘처럼 페이지 프레임들을 환형 리스트로 관리한다. 다음은 환형 리스트의 예를 보여준다.

　초기에 이 리스트는 비어있다. 첫 번째 페이지가 적재되면서, 리스트에 추가된다. 계속 페이지들이 추가되면서 이들은 링 구조의 리스트를 형성한다. 각 엔트리는 작업 집합 알고리즘에서도 사용하는 Time of last use 필드와 R 비트, M 비트(그림에 보이지 않음)를 갖는다.

• 클록 알고리즘에서처럼 페이지 폴트가 발생하면 화살표가 가리키는 페이지부터 검사한다.
• 만일 R이 1이면 이 페이지는 최근 클록 틱 간격에서 참조된 것이므로 교체의 대상이 되지 않는다.
  • 이 경우 R을 0으로 설정하고, 화살표는 다음 페이지로 전진하여 다시 검사를 계속한다.(b)
• 만일 R이 0이면(c) 나이가 $\tau$보다 크고 페이지가 수정되지 않았으면(즉, 작업 집합에 속해 있지 않고 유효한 데이터가 디스크에 존재하고 있으면), 이 페이지가 교체되고 그 위치에 새로운 페이지를 적재한다.(d) 반면 나이가 $\tau$보다 크고 페이지가 수정된 상태면 이 페이지의 내용을 우선 디스크에 기록해야 한다.
• 프로세스간 교체를 피하기 위해 이 페이지 내용의 디스크 쓰기를 스케줄링 한 후 알고리즘은 다음 페이지에 대한 검사를 계속한다.
• 이 과정을 반복하면 언젠가 오래되고 수정이 안된 페이지를 발견하게 되고 그 페이지가 교체된다.

　이론적으로는 한 클록 라운드 동안 모든 페이지들이 디스크 I/O를 위해 스케줄링 될 수 있다. 순간적으로 많은 디스크 접근의 발생을 제어하기 위해 시스템은 최대 쓰기 페이지 개수를 제하하기도 한다. 일단 제한 개수의 쓰기가 스케줄링 되면, 이후 쓰기는 더 이상 스케줄링 되지 않는다.
　만일 클록의 화살표가 시작했던 위치로 다시 돌아오면 다음 두 가지 경우를 생각해 볼 수 있다.

• 최소한 하나의 쓰기가 스케줄링 되어 있는 경우
  • 화살표를 계속 전진시켜 수정되지 않은 페이지를 찾는다.
  • 하나 이상의 수정된 페이지가 쓰기를 위해 스케줄링되어 있어 결국 쓰기가 완료된 페이지가 나타나게 될 것이다.
  • 처음으로 발견한 클린한 페이지를 교체한다.
    • 이 페이지는 가장 먼저 쓰기를 스케줄링한 페이지가 아닐 수도 있다. 왜냐하면 디스크 드라이버가 최적화를 위해 쓰기 순서를 바꾸었을 수 있기 때문이다.
• 아무런 쓰기도 스케줄링 되어 있지 않은 경우
  • 결국 모든 페이지가 작업 집합에 속해 있는 경우이다.
  • 더 이상 정보가 없으므로 알고리즘은 수정되지 않은 페이지 중에 하나를 교체할 페이지로 선택한다.
  • 만일 모든 페이지가 수정되었다면 현재 화살표가 가리키는 페이지를 선택하여 디스크에 쓰고 이것을 교체한다.

페이지 교체 알고리즘의 요약

　지금까지 살펴본 페이지 교체 알고리즘들을 요약하면 다음과 같다.

세그멘테이션(Segmentation)

　지금까지 본 가상 메모리는 1차원적이었다. 즉, 가상 주소는 0부터 시작하여 특정 크기만큼 자라며 주소는 순차적으로 증가하였다. 하지만 두 개 또는 그 이상의 서로 분리된 가상 주소 공간을 갖는 것이 하나의 주소 공간보다 더 편리한 경우가 많다. 예를 들어 컴파일러는 컴파일 도중 다양한 테이블을 생성하는데 대표적인 예는 다음과 같다.

• 소스 텍스트(Source text): 출력 리스트를 위해 저장된 프로그램 텍스트(배치 시스템)
• 심볼 테이블(Symbol table): 변수 이름과 속성을 포함한 테이블
• 상수 테이블(Constant table): 사용된 정수 형, 실수 형 상수
• 파싱 트리(Parse tree): 프로그램의 구문 분석을 위해 사용됨
• 스택(Call stack): 컴파일러에서 내부적으로 함수 호출할 때 이용

　처음 4개의 테이블은 컴파일러가 실행되면서 순차적으로 증가한다. 반면 마지막 것은 증가하기도 하고 감소하기도 한다. 1차원적인 메모리에서는 이 5개의 테이블이 가상 주소 공간에 연속된 부분으로 할당되는데 다음은 이러한 예를 보여준다.

　위 그림은 증가하는 테이블을 갖는 1차원 주소공간을 보여준다. 테이블이 증가하면서 다른 공간과 충돌할 수도 있다.
　만일 한 프로그램이 매우 많은 변수를 사용하고, 그 외는 다른 프로그램들과 유사하다고 가정하면, 심볼 테이블을 위한 메모리 부분은 가득 차는데 다른 테이블들을 위한 부분들은 여전히 여유 공간을 가지게 될 것이다. 이렇게 되면 컴파일러는 너무 많은 변수를 사용하고 있다는 에러 메시지를 출력하고 컴파일 과정을 중지할 수도 있겠지만 아직도 가용 공간이 많은데 중지하는 것은 적절한 대응 방법이 아니다.
　다른 가능한 방법으로는 가용 공간이 있는 메모리 부분에서 부족한 부분으로 공간을 옮겨주는 것이다. 하지만 이러한 이동은 테이블들의 복잡한 복사를 야기한다. 이것은 마치 사용자가 직접 오버레이(overlay)를 관리하는 것과 유사하다. 적절하게 옮겨지는 경우에도 많은 성가신 노력이 필요하고, 최악의 경우에는 다시 침범이 발생한다.
　진정으로 필요한 것은 각 메모리 부분을 증가하거나 감소시키는 작업을 프로그래머가 아닌 시스템에서 자연스럽게 제공하는 것이다. 즉, 가상 메모리가 사용자로 하여금 직접 프로그램을 여러 개의 오버레이로 나누어 제작하는 부담을 없애는 것과 같은 것이 필요하기 때문에 시스템은 세그먼트(segment)라고 부르는 여러 개의 서로 완전히 독립된 주소 공간들을 제공한다. 각 세그먼트는 0부터 시스템에서 허용된 최대 크기까지 값을 갖는 선형 주소로 구성된다. 흔히 서로 다른 세그먼트는 서로 다른 크기를 갖는다. 또한 세그먼트 크기는 실행 중에 변할 수 있다. 스택의 크기는 새로운 데이터가 추가될 때 증가하며, 추가된 데이터가 삭제되면 감소한다.
　각 세그먼트가 서로 다른 주소 공간을 구성하기 때문에 한 세그먼트는 다른 세그먼트들에게 영향을 주지 않고 독립적으로 증가하거나 감소할 수 있다. 만일 특정 세그먼트에 존재하는 스택이 증가하기 위한 더 많은 주소 공간을 필요로 한다면, 그냥 증가시키면 된다. 왜나하면 이 주소 공간에는 충돌할 가능성이 있는 다른 부분이 없기 때문이다. 물론 세그먼트의 최대 크기 이상으로 주소 공간이 증가할 수는 없다. 하지만 세그먼트의 크기를 충분히 크게 설정하면 이럴 가능성은 매우 적다. 2차원적인 주소 공간, 즉 세그먼트를 사용하기 위해서는 프로그램이 사용하는 주소가 2부분으로 표현되어야 한다. 첫 번째 부분은 세그먼트 번호이며 두 번째 부분은 세그먼트 내부에서의 주소이다. 다음 그림은 위에서 설명되었던 컴파일러가 사용하는 테이블들을 위한 세그먼트 메모리를 보여준다. 여기에는 5개의 서로 독립적인 세그먼트가 나타나 있다.

　각 세그먼트는 사용자가 인식하는 함수나 배열, 스택과 같은 논리적인 객체로 구성된다. 따라서 서로 다른 세그먼트는 서로 다른 보호 모드를 가질 수 있다. 예를 들어 함수로 구성된 세그먼트는 실행 전용(execute only)으로 설정될 수 있으며, 이곳에 대한 읽기나 변경을 예방할 수 있다. 부동 소수점 실수로 구성된 세그먼트는 읽기/쓰기는 가능하나 실행은 안되도록 설정하여 이 세그먼트로 분기하는 시도를 막을 수 있다. 이러한 보호는 프로그래밍 에러를 발견하는데 도움을 준다.
　1차원적인 페이징 시스템에 비해 세그먼트 시스템이 보호 모드에 더 적합한 이유를 살펴보면, 세그먼트 시스템에서 사용자는 각 세그먼트에 어떤 내용이 존재하는지 안다. 일반적으로 각 세그먼트는 한 유형의 데이터를 유지하며, 두 가지 이상 서로 다른 유형의 데이터를 유지하는 경우가 드물다. 즉, 함수와 스택은 서로 다른 세그먼트에 유지된다. 따라서 각 유형에 적합한 보호 및 접근 제어가 가능하다. 다음은 페이징과 세그멘테이션의 차이를 보여준다.

순수한 세그멘테이션 구현

　세그멘테이션과 페이징은 구현 방법이 다르다. 본질적으로 페이징은 고정 크기이며, 세그멘테이션은 가변 크기이다. 다음 그림을 보자.

• (a)는 5개의 세그먼트를 포함한 물리 메모리의 초기 상태를 보여준다.
• 이때 세그먼트 1이 교체되고 이보다 크기가 작은 세그먼트 7이 적재되었다고 가정해보면, (b)는 이 상태를 보여준다.
  • 세그먼트 7과 세그먼트 2사이에는 사용되지 않은 공간이 존재하게 된다.
• 그 이후 세그먼트 4가 세그먼트 5와 교체되고, 세그먼트 3이 세그먼트 6과 교체되었다고 가정한다.
  • 이때 상태가 각각 (c), (d)에 나타나 있다.
  • 시스템이 계속 실행됨에 따라 메모리는 작은 조각으로 계속 분할되고, 일부 조각은 세그먼트를 위한 공간이 되고, 나머지 조작은 비어 있는 공간이 된다.
  • 이렇게 빈 조각들은 메모리 낭비를 초래하며 이러한 현상을 체커판되기(checkerboarding) 또는 외부 단편화(external fragmentation)라고 한다.
• 이러한 현상은 사용되지 않고 낭비되는 부분을 수집하는 조각모음(compaction)을 통해 해결하며 이는 (e)에 나타나 있다.

세그멘테이션과 페이징: 인텔 펜티엄

　펜티엄의 가상 메모리 구조는 세그멘테이션과 페이징을 사용한다. 펜티엄은 16K개의 세그먼트를 지원하며, 각 세그먼트의 크기는 최대 4G $\times$32비트 워드까지 가능하다.
　펜티엄의 가상 메모리 지원에 핵심적인 기능을 제공하는 것이 GDT(Global Descriptor Table)과 LDT(Local Descriptor Table)이다. 각 프로그램은 자신의 LDT를 각각 갖는다. 반면 GDT는 전체 시스템에 하나 존재하며, 각 프로그램은 이를 공유한다. LDT는 각 프로그램의 지역 세그먼트(텍스트, 데이터, 스택 등) 정보를 관리하며, GDT는 운영체제 같은 시스템 세그먼트를 관리한다.
　세그먼트를 접근하기 위해, 프로그램은 우선 세그먼트 셀렉터를 펜티엄의 여섯 개의 세그먼트 레지스터 중 하나에 적재한다. 실행 중에 CS 레지스터는 코드 세그먼트를 위한 셀렉터를 유지하고 DS 레지스터는 데이터 세그먼트를 위한 셀렉터를 유지한다. 다른 세그먼트 레지스터는 덜 빈번하게 사용된다. 각 셀렉터는 16비트로 구조는 다음과 같다.

　셀렉터의 한 비트는 세그먼트가 지역인지 전역인지 (즉 LDT에 속해 있는지 GDT에 속해있는지) 구분한다. 13개의 다른 비트는 LDT 또는 GDT 테이블의 엔트리를 가리킨다. (따라서 각 테이블은 최대 8K개의 세그먼트를 가질 수 있다.) 마지막 2비트는 보호와 관려되어 있다. 디스크립터 0은 사용할 수 없다. 이것은 주로 세그먼트 레지스터가 현재 사용 가능하지 않다라는 것을 나타내기 위해 이용된다. 즉, 세그먼트 레지스터가 디스크립터 0을 가리키면 트랩이 발생한다.
　셀렉터가 세그먼트 레지스터에 적재되면 대응되는 디스크립터가 LDT 또는 GDT에서 반입되어 마이크로프로그램 레지스터에 저장된다. 따라서 그 이후 참조는 빠르게 진행된다. 다음은 디스크립터 구조를 보여준다. 디스크립터는 8바이트로 구성되어 있으며, 세그먼트 기본 주소, 크기 등의 정보를 포함한다.

　셀렉터의 구조는 디스크립터의 위치를 효과적으로 찾을 수 있도록 구성되었다. 우선 두 번째 비트를 이용해 LDT인지 GDT인지 파악한다. 그리고 셀렉터를 내부 스크래치 레지스터에 복사한 후 하위 3비트를 0으로 클리어한다. 마지막으로 이 값과 LDT 또는 GDT 테이블의 주소를 더하여 원하는 디스크립터를 접근할 수 있다. 예를 들어 셀렉터 72는 GDT의 9번째 엔트리에 대응되며 주소는 GDT 주소 +72가 된다.
　이제부터 (셀렉터, 오프셋) 쌍으로 구성된 가상 주소가 물리 주소로 변환되는 과정을 본다.

• 마이크로프로그램이 어떤 세그먼트 레지스터를 사용하려는지 파악하고, 해당 디스크립터를 내부 레지스터에서 발견한다.
  • 만일 이 세그먼트가 존재하지 않는다면 (예를 들어 셀렉터가 0) 또는 페이징 아웃 되어 있다면, 트랩이 발생한다.
• 하드웨어는 Limit 필드를 이용해 오프셋이 세그먼트의 범위를 벗어 났는지 확인한다.
  • 만일 벗어났다면 역시 트랩이 발생한다.
  • 논리적으로는 세그먼트의 크기를 나타내는 Limit 필드는 32비트이어햐 한다.(4GB 지원이 가능) 하지만 실제로는 20비트만 사용한다.
  • G 비트(Granularity 비트)가 0이면 세그먼트 크기는 바이트 단위로 계산되며(따라서 최대 1MB), 1이면 바이트 단위가 아닌 페이지 단위로 계산된다. 펜티엄에서 페이지 크기는 4KB이므로 20비트로 $2^{32}$바이트 크기의 세그먼트가 가능하다.
• 세그먼트가 메모리에 있고 오프셋이 세그먼트 크기보다 적다면, 펜티엄은 32비트 크기의 Base 필드에 있는 값과 오프셋을 더해 선형 주소(linear address)를 생선한다.

  

  • 디스크립터에서 Base 필드는 3부분으로 나누어져있다. 이는 24비트 크기를 사용하던 286CPU와 호환성 때문이다.
  • 결국 Base 필드는 각 세그먼트가 32비트 선형 주소 공간의 어떤 위치에서라도 시작할 수 있게 허용한다.

　만일 페이징을 사용하지 않는다면, 선형 주소는 그대로 물리 주소가 되어 메모리 접근 주소로 사용된다. 결국 순수한 세그멘테이션 시스템이 되는 것이다. 세그먼트는 중첩(overlapping)될 수도 있다. 하지만 중첩의 경우 문제의 가능성이 높고 검증이 어렵기 때문에 중첩되지 않게 설정하는 것이 일반적이다.
　각 프로그램은 하나의 페이지 디렉터리(page directory)를 갖는다. 페이지 디렉터리는 1024개의 32비트 엔트리로 구성된다. 펜티엄의 한 전역 레지스터는 현재 실행 중인 프로세스의 페이지 디렉터리의 시작 주소를 가리킨다. 디렉터리의 각 엔트리는 페이지 테이블의 시작 주소를 가리키며, 페이지 테이블 역시 1024개의 32비트 엔트리로 구성된다. 페이지 테이블 엔트리는 다시 페이지 프레임의 시작 주소를 가리킨다. 다음은 이 과정을 보여준다.

　(a)는 선현 주소가 Dir, Page, Offset이라는 3필드로 부분된 것을 보여 준다.

• Dir 필드는 페이지 디렉터리를 인덱싱할 때 사용되며, 여기서 발견된 엔트리는 대응되는 페이지 테이블의 시작 주소를 가리킨다.
• Page 필드는 페이지 테이블을 인덱싱 할 때 사용하며, 여기서 발견된 엔트리는 페이지 프레임의 시작 주소를 가리킨다.
• 마지막으로 페이지 프레임 시작 주소에 Offset 필드가 더해지면 원하는 물리 주소를 얻을 수 있다.

　32비트 프레임 테이블 엔트리 중에서 20비트는 페이지 프레임을 가리키기 위해 사용된다. 나머지 비트에는 참조(reference) 비트, 수정(dirty) 비트, 보호 비트 등의 정보가 저장된다. 참조 비트와 수정 비트는 하드웨어에 의해 설정된다.
　이제 보호에 대해 살펴본다. 보호 역시 결국 가상 메모리와 관련되어 있다. 펜티엄은 다음과 같이 4단계의 보호 레벨을 제공한다.

　레벨0은 가장 권한이 높은 수준이고, 레벨3은 가장 낮은 수준이다. 프로그램이 동작할 때 자신의 실행 레벨을 가지며, 이것은 PSW의 2비트로 표현된다. 또한 각 세그먼트는 레벨을 갖는다.
　프로그램이 자기와 동일한 레벨의 세그먼트를 접근할 때에는 아무 문제 없이 그대로 접근할 수 있다. 프로그램보다 큰 숫자 레벨(낮은 권한)을 갖는 세그먼트에 저장된 데이터를 접근하는 것은 허용된다. 반면, 작은 숫자 레벨(높은 권한)을 갖는 세그먼트에 저장된 데이터를 접근하는 것은 허용되지 않으며, 트랩을 야기한다. 서로 다른 레벨 간에 함수를 호출하는 것은 허용되지만, 잘 정의된 규칙을 따라야 한다. 레벨 간에 함수 호출의 경우, CALL 명령어는 주소 대신 셀렉터를 인자로 사용한다. 이 셀렉터는 콜게이트(call gate)라고 불리는 디스크립터를 가리키며, 여기에는 호출될 함수의 주소가 기록되어 있다. 즉, 서로 다른 레벨을 갖는 코드 세그먼트로 자유롭게 분기할 수 있는 것이 아니라 공식적인 진입점(entry point)를 통해 분기해야 하는 것이다. 보호 수준과 콜게이트 개념은 보호 링(protection ring)이라는 관점에서 설계되었다.
　위 그림은 보호 링 기법의 사용 예를 보여준다.

• 레벨0에서는 I/O, 메모리 관리 등 시스템에 중요한 작업을 실행하는 운영체제의 커널 부분이 실행된다.
• 레벨1에서는 시스템 호출 핸들러가 실행된다.
  • 사용자 프로그램은 시스템 호출을 사용하기 위해 여기에있는 함수를 호출한다.
  • 여기에 있는 함수들은 보호되고 특별한 형태로 구현되어 있다.
• 레벨2에서는 라이브러리 함수가 실행된다.
  • 라이브러리는 실행 중인 많은 프로그램들에 의해 공유될 수 있다.
  • 사용자 프로그램은 라이브러리를 호출하고 데이터를 읽을 수 있다. 하지만 수정은 허용되지 않는다.
• 레벨3에서는 사용자 프로그램이 동작하며, 가장 낮은 권한으로 동작한다.

　트랩과 인터럽트는 콜게이트와 동일한 방법으로 동작한다. 즉, 이들도 주소를 직접 호출하지 않고 디스크립터를 통해 호출한다. 디스크립터는 호출된 함수를 가리킨다.