OS Concepts 10th 9장: Main Memory

본 글은 Operating System Concepts 10th (운영체제) 책을 보며 내용을 개인 공부에 목적으로 정리했습니다.
이전에 운영체제 관련 강의들을 들으면서 정리한 시리즈 글들이 있는데,
지식을 습득하는 데 있어 가장 느리지만 가장 빠른 방법이 원본책을 자세히 보는 것이라 생각됩니다.
책 내용들을 최대한 이해하기 위해 거의 모든 내용을 담고 있습니다.

책 pdf 링크 : Operating System Concepts 10th Edition by Abraham Silberschatz Peter B Galvin Greg Gagne pdf free download
연습 문제 정답지 : Solutions of Practice Exercises, Tenth Edition of Operating System Concepts, AVI SILBERSCHATZ

9. Main Memory

• CPU 스케줄링을 통해 CPU 이용률과 사용자에 제공하는 컴퓨터 응답속도를 모두 향상할 수 있다.
• 그러나 이러한 성능 향상을 실현하려면 많은 프로세스를 메모리에 유지해야 한다.
  • 즉, 메모리를 공유해야 한다.
• 이 장에서는 메모리를 관리하는 다양한 방법에 관해 설명한다.

• 목표
  • 논리 주소와 물리 주소의 차이점과 주소를 변환할 때 MMU(메모리 관리 장치)의 역할을 설명한다.
  • 메모리를 연속적으로 할당하기 위해 최초, 최적 및 최악 접합 전략을 적용한다.
  • 내부 및 외부 단편화의 차이점을 설명한다.
  • TLB (translation look-aside buffer)가 포함된 페이징 시스템에서 논리 주소를 물리 주소로 변환한다.
  • 계층적 페이징, 해시 페이징 및 역 페이지 테이블을 설명한다.
  • IA-32, x86-64 및 ARMv8 아키텍처의 주소 변환에 관해 설명한다.

9.1 Background

• 메모리(memory)는 각각 주소(address)가 할당된 일련의 바이트들로 구성된다.
• CPU는 PC(program counter)가 지시하는 대로 메모리로부터 다음 수행할 명령어를 가져온다.
• 전형적인 명령어 실행은 먼저 메모리로부터 한 명령어를 가져오는 데서부터 시작한다.
• 그런 다음 명령어를 해독하고, 메모리에서 피연산자(operand)를 가져와 피연산자에 대해 명령어를 실행한 후에 계산 결과를 메모리에 다시 저장한다.
  • 메모리는 주소에 지시한 대로 읽기, 쓰기만 할 뿐 이 주소들이 어떻게 생성되었는지 혹은 그 주소가 가리키는 내용이 무엇인지를 모른다.

9.1.1 Basic Hardware

• 메인 메모리와 각 처리 코어에 내장된 레지스터들은 CPU가 직접 접근할 수 있는 유일한 범용 저장장치이다.
  • 기계 명령어들은 메모리 주소만을 인수로 취하고, 디스크의 주소를 인수로 취하지 않는다.
  • 따라서 모든 실행되는 명령어와 데이터들은 CPU가 직접적으로 접근할 수 있는 메인 메모리와 레지스터에 있어야 한다.
  • 만약 데이터가 메모리에 없다면 CPU가 그것들을 처리하기 전에 메모리로 이동시켜야 한다.

• 각 CPU 코어에 내장된 레지스터들은 일반적으로 CPU 클록(clock)의 1사이클 내에 접근이 가능하다.
  • 일부 처리 코어들은 레지스터에 있는 명령어의 해독과 간단한 연산을 클록 틱(clock tick)당 하나 또는 그 이상의 속도로 처리한다.
• 하지만 메인 메모리의 접근을 완료하기 위해서는 많은 CPU 클록 틱 사이클이 소요되며, 이 경우 CPU가 필요한 데이터가 없어서 명령어를 수행하지 못하고 지연되는(stall) 현상이 발생하게 된다.
  • 메인 메모리는 메모리 버스를 통해 전송된다.
• 이를 해결하기 위한 방법으로 캐시(cache)를 도입해 CPU와 메인 메모리 사이에 (통상 빠르게 접근할 수 있도록 CPU 안에) 빠른 속도의 메모리를 추가하는 것이다.
• CPU에 구축된 캐시를 관리하여 하드웨어는 어떠한 운영체제의 도움 없이 메모리 접근 속도를 향상한다.

• 운영체제가 CPU와 메모리 간의 접근 중에 개입하게 되면 성능이 떨어지기 때문에 “보호 기법”은 반드시 하드웨어가 지원해야 한다.
• 먼저 각각의 프로세스가 독립된 메모리 공간을 가지도록 보장해야 한다.
  • 개별적인 프로세스별 메모리 공간은 서로를 보호하고 동시 실행을 위해 여러 프로세스가 메모리에 적재되게 하는 것이 필수적이다.

• 개별적인 메모리 공간을 분리하기 위해서 특정 프로세스만 접근할 수 있는 합법적인(legal) 메모리 주소 영역을 설정하고, 프로세스가 합법적인 영역만을 접근하도록 하는 것이 필요하다.
• Figure 9.1에서 보여주듯이, 기준(base)과 상한(limit)이라고 불리는 2개의 레지스터들을 사용하여 이러한 보호 기법을 제공한다.
  • 기준 레지스터(base register)는 가장 작은 합법적인 물리(physical) 메모리 주소의 값을 저장한다.
  • 상한 레지스터(limit register)는 주어진 영역의 크기를 저장한다.
  • 기준과 상한 레지스터가 논리(logical) 주소 공간을 정의한다.
  • 기준과 상한 레지스터는 여러 가지 특권 명령을 사용하는 운영체제에 의해서만 적재된다.
  • 이러한 기법은 운영체제만 레지스터들의 값을 변경할 수 있도록 허가해 줌으로써 사용자 프로그램이 레지스터의 내용을 변경하는 것을 막는다.

• 메모리 공간의 보호는 CPU 하드웨어가 사용자 모드에서 만들어진 모든 주소와 레지스터를 비교함으로써 이루어진다.
• 사용자 모드에서 수행되는 프로그램이 운영체제의 메모리 공간이나 다른 사용자 프로그램의 메모리 공간에 접근하면 운영체제는 치명적인 오류로 간주하고 트랩(trap)을 발생시킨다.
  • 이러한 기법은 사용자 프로그램이 운영체제나 다른 사용자 프로그램의 코드나 데이터 구조를 수정하는 것을 만든다.

types of address

• 책에는 없지만, 주소의 정의를 정리할 필요가 있다고 느꼈다. ¹
• 논리 주소(logical address) : 프로세스마다 독립적으로 갖는 공간
  • 논리적인 주소 체계로, 0번지를 시작으로 상대적인 주소 값을 갖는다.
  • CPU에서 인식하는 주소 체계로, 가상(virtual), 상대(relative), 재배치 가능(relocatable) 주소라고도 부른다.
• 물리 주소(physical address) : 실제 물리적인 메모리 위치를 식별하는 주소
  • 절대(absolute) 주소라고도 한다.
• 심볼 주소(symbolic address) : 변수나 함수와 같이 코드에서 사용하는 상징적인 이름을 주소로 사용하는 방법이다.

9.1.2 Address Binding

• 프로그램은 원래 이진 실행 파일 형태로 디스크에 저장되어 있다.
• 실행하려면 프로그램을 메모리로 가져와서 프로세스 문맥 내에 배치해야 한다.
• 이 시점에 가용한 CPU에서 실행할 수 있게 된다.
• 프로세스가 실행되면 메모리에서 명령 및 데이터에 액세스 한다.
• 프로세스가 종료되면 다른 프로세스에서 사용하기 위해 메모리가 회수된다.

• 대부분의 경우 Figure 9.3과 같이 여러 단계를 거쳐 실행되기 때문에 이들 단계를 거치는 동안 주소들은 여러 가지 다른 표현 방식을 거치게 된다.

• 원시 프로그램에서 주소는 숫자가 아닌 심볼 형태(ex. 변수 count)로 표현된다.
• 컴파일러(compiler)는 이 심볼(symbolic) 주소를 재배치(relocatable) 가능 주소로 바인딩시키고(binding), 다음에 링커(linker)나 로더(loader)가 재배치 가능 주소를 절대 주소(absolute address)로 바인딩시킨다.
  • 바인딩(binding) 과정은 한 주소 공간에서 다른 주소 공간으로 맵핑하는 것이다.

• 메모리 주소 공간에서 명령어와 데이터의 바인딩은 그 바인딩이 이루어지는 시점에 따라 다음과 같이 구분된다.
  • 컴파일 시간(compile time) 바인딩 : 만일 프로세스가 메모리 내에 들어갈 위치를 컴파일 시간에 미리 알 수 있으면 컴파일러는 절대 코드를 생성할 수 있다.
  • 적재 시간(load time) 바인딩 : 만일 프로세스가 메모리 내 어디로 올라오게 될지를 컴파일 시점에 알지 못하면 컴파일러는 일단 이진 코드를 재배치 가능코드로 만들어야 한다.
    • 이 경우에 심볼과 진짜 번지수와의 바인딩은 프로그램이 메인 메모리로 실제로 적재되는 시간에 이루어지게 된다.
  • 실행 시간(execution time) 바인딩 : 만약 프로세스가 실행하는 중간에 메모리 내의 한 세그먼트로부터 다른 세그먼트로 옮겨질 수 있다면 이것을 바인딩이 실행 시간까지 허용되었다고 이야기한다.

9.1.3 Logical-Versus Physical-Address Space

• CPU가 생성하는 주소를 논리 주소(logical address)라 하며, 메모리게 취급하게 되는 주소(즉, 메모리 주소 레지스터(MAR, memory address register))는 물리 주소(physical address)라 한다.
• 컴파일 또는 적재 시에 주소를 바인딩하면 논리 주소와 물리 주소가 같다.
  • 그러나 실행 시간 바인딩 기법에서는 논리, 물리 주소가 다르다.
  • 이러면 논리 주소를 가상 주소(virtual address)라 한다.
• 프로그램에 의해 생성된 모든 논리 주소 집합을 논리 주소 공간(logical address space)라 하며 이 논리 주소와 일치하는 모든 물리 주소 집합을 물리 주소 공간(physical address space)이라 한다.

• 프로그램의 실행 중에는 가상 주소를 물리 주소로 바꾸어줘야 하는데 이 변환(mapping) 작업은 하드웨어 장치인 메모리 장치 관리(MMU, memory management unit)에 의해 실행된다.

• 기준 레지스터를 재배치(relocation) 레지스터라고 부른다.
• 재배치 레지스터 속에 들어있는 값은 주소가 메모리로 보내질 때마다 그 모든 주소에 더해진다.

9.1.4 Dynamic Loading

• 메모리 공간을 더 효율적으로 이용하기 위해서는 동적 적재(dynamic loading)를 해야 한다.
• 동적 적재에서 각 루틴은 실제 호출되기 전까지는 메모리에 올라오지 않고 재배치 가능한 상태로 디스크에서 대기하고 있다.
• 먼저 main 프로그램이 메모리에 올라와 실행된다.
• 이 루틴이 다른 루틴을 호출하게 되면 호출된 루틴이 이미 메모리에 적재됐는지를 조사한다.
• 만약 적재되어 있지 않다면, 재배치 가능 연결 적재기(relocatable linking loader)가 불려 요구된 루틴을 메모리로 가져오고, 이러한 변화를 테이블에 기록해둔다.

9.1.5 Dynamic Linking & Shared Libraries

• 동적 연결 라이브러리(DLLs, dynamically linked libraries)는 사용자 프로그램이 실행될 때, 사용자 프로그램에 연결되는 시스템 라이브러리이다.
• 동적 연결 개념은 동적 적재의 개념과 유사하다.
  • 동적 적재에서는 로딩(loading)이 실행 시까지 미루어졌었지만 동적 연결에서는 연결(linking)이 실행 시기까지 미루어지는 것이다.
  • 하지만 동적 적재와는 달리 동적 연결과 공유 라이브러리는 일반적으로 운영체제의 도움이 필요하다.
  • 메모리에 있는 프로세스들이 각자의 공간은 자기만 액세스할 수 있도록 보호된다면, 운영체제만이 기억 공간에 루틴이 있는지를 검사해 줄 수 있고 운영체제만이 여러 프로세스가 같은 메모리 주소를 공용할 수 있도록 해줄 수 있다.
• 동적 연결은 주로 표준 C 언어 라이브러리와 같은 시스템 라이브러리에 사용된다.
• DLL은 또한 이러한 라이브러리를 여러 프로세스 간에 공유할 수 있어 메인 메모리에 DLL 인스턴스가 하나만 있을 수 있다는 것이다.
  • 이러한 이유로 DLL을 공유 라이브러리라고도 한다.

• 프로그램이 동적 라이브러리에 있는 루틴을 참조하면 로더는 DLL을 찾아 필요한 경우 메모리에 적재한다.
• 그런 다음 동적 라이브러리의 함수를 참조하는 주소를 DLL이 저장된 메모리의 위치로 조정한다.

9.2 Contiguous Memory Allocation

• 메인 메모리는 운영체제뿐만 아니라 여러 사용자 프로세스도 수용해야 한다. 그리고 각 영역은 각각 목적에 맞도록 효율적으로 관리되어야 한다.
• 메모리는 일반적으로 2개의 부분으로 나누어지는데, 하나는 운영체제를 위한 것이며 다른 하나는 사용자 프로세스를 위한 것이다.
  • 많은 운영체제는 운영체제를 높은 메모리에 배치한다.
  • 일반적으로 여러 사용자 프로세스가 동시에 메모리에 상주하기를 원한다.
  • 따라서 메모리에 적재되기를 기다리는 프로세스에 사용 가능한 메모리를 할당하는 방법을 고려해야 한다.
  • 연속적인 메모리 할당에서 각 프로세스는 다음 프로세스가 적재된 영역과 인접한 하나의 메모리 영역에 적재된다.

9.2.1 Memory Protection

• 만일 시스템이 상한 레지스터와 재배치 레지스터를 가지고 있다면 프로세스가 자신이 소유하지 않은 메모리를 접근할 수 없게 강제할 수 있다.
  • 재배치(relocation) 레지스터는 가장 작은 물리 주소의 값을 저장한다.
  • 상한(limit) 레지스터는 논리 주소의 범위 값을 저장한다.
    • 각각의 논리 주소는 상한 레지스터가 지정한 범위 안에 존재해야 한다.
• MMU는 동적으로 논리 주소에 재배치 레지스터의 값을 더함으로써 주소를 변환하는 역할을 한다.
  • 이렇게 변환된 주소는 메모리로 보내진다.

• CPU 스케줄러가 다음으로 수행할 프로세스를 선택할 때, 디스패처(dispatcher)는 문맥 교환의 일환으로 재배치 레지스터와 상한 레지스터에 정확한 값을 적재한다.
• CPU에 의해서 생성되는 모든 주소는 이 레지스터들의 값을 참조해서 확인 작업을 거치기 때문에, 운영체제와 다른 사용자 프로그램을 현재 수행 중인 사용자 프로그램의 접근으로부터 보호할 수 있다.

9.2.2 Memory Allocation

• 메모리를 할당하는 가장 간단한 방법 중 하나는 프로세스를 메모리의 가변 크기 파티션에 할당하는 것이다.
  • 각 파티션에는 정확히 하나의 프로세스만 적재될 수 있다.
  • 가변 파티션(variable partition) 기법에서 운영체제는 사용 가능한 메모리 부분과 사용 중인 부분을 나타내는 테이블을 유지한다.
  • 하나의 큰 사용 가능한 메모리 블록을 hole로 간주한다. (아래 하늘색 부분)

• 프로세스가 시스템에 들어오면, 운영체제는 각 프로세스가 메모리를 얼마나 요구하며, 또 사용 가능한 메모리 공간이 어디에 얼마나 있는지를 고려하여 공간을 할당한다.
• 프로세스가 공간을 할당받게 되면, 이후로는 CPU를 할당받기 위해 경쟁한다.
• 프로세스가 끝내면 메모리를 반납하고, 운영체제는 다른 프로세스에 이 공간을 할당할 수 있다.

• 일반적으로 메모리에는 다양한 크기의 hole이 여기저기 흩어져 있다.(scatter)
• 프로세스에 공간이 필요할 때 운영체제는 이 hole의 집합에서 적절한 것을 찾아내야 한다.
• 동적 메모리 할당 문제(dynamic storage allocation problem)은 일련의 가용 공간-리스트로부터 크기 n-바이트 블록을 요구하는 것을 어떻게 만족시켜 줄 것이냐를 결정하는 문제이다.
• 이러한 문제에 대한 해결책 중 3가지를 소개한다.
  • 최초 적합(first-fit) : 첫 번째 사용 가능한 가용 공간을 할당한다.
  • 최적 적합(best-fit) : 사용 가능한 공간 중에서 가장 작은 것을 택한다.
  • 최악 적합(worst-fit) : 가장 큰 가용 공간을 택한다.

9.2.3 Fragmentation

• 최초 적합 전략과 최초 적합 전략 모두 외부 단편화(external fragmentation)로 인해 어려움을 겪는다.
• 프로세스들이 메모리에 적재되고 제거되는 일이 반복되다 보면, 어떤 가용 공간은 너무 작은 조각이 되어 버린다.
• 외부 단편화는 유휴 공간들을 모두 합치면 충분한 공간이 되지만 그것들이 너무 작은 조각드롤 여러 곳에 분산되어 있을 때 발생한다.
• 또한 메모리의 전체 크기와 프로세스 크기들은 모두 외부 단편화에 따라 큰 영향을 미칠 수 있다.

• 외부 단편화 문제를 해결하는 방법으로 압축(compaction)이 있는데, 이 방법은 메모리 모든 내용을 한군데로 몰고 모든 가용 공간을 다른 한군데로 몰아서 큰 블록을 만드는 것이다.
  • 압축은 프로세스들의 재배치가 실행 시간에 동적으로 이루어지는 경우에만 가능하다.
  • 주소가 동적으로 재배치할 수 있다면, 재배치 작업은 프로그램과 데이터를 새로운 위치로 옮기고 새 위치를 반영하기 위하여 기준 레지스터만 변경하면 완료된다.

• 외부 단편화 문제를 해결할 수 있는 다른 방법은 한 프로세스의 논리 주소 공간을 여러 개의 비연속적인 공간으로 나누어 필요한 크기의 공간이 가용해지는 경우 물리 메모리를 프로세스에 할당하는 방법이다.
  • 이것은 페이징(paging)에 사용되는 전략이다.
• 내용을 이어서 보고싶다면 다음 링크를 클릭한다.
  • 링크 : [Operating System Concepts 10th] 9. Main Memory 리뷰 (2)

9.3 Paging

• 전의 글에서 논의된 메모리 관리는 프로세스의 물리 주소 공간이 연속적이어야 했다.
• 페이징(paging)은 프로세스의 물리 주소 공간이 연속되지 않아도 되는 메모리 관리 기법이다.
• 페이징은 연속 메모리 할당을 괴롭하는 2가지 문제인 외부 단편화(external fragmentation)와 관련 압축의 필요성을 피한다.
• 페이징은 운영체제와 컴퓨터 하드웨어 간의 협력을 통해 구현된다.

9.3.1 Basic Method

• 물리 메모리는 프레임(frame)이라 불리는 같은 크기 블록으로 나누어진다.
• 논리 메모리는 페이지(page)라 불리는 같은 크기의 블록으로 나누어진다.
• 프로세스가 실행될 때 그 프로세스의 페이지는 파일 시스템 또는 예비(backing) 저장장치로부터 가용한 메인 메모리 프레임으로 적재된다.
  • 예비 저장장치(backing store)는 메모리 프레임 혹은 프레임의 묶음인 클러스터와 동일한 크기의 고정 크기 블록으로 나누어진다.

• CPU에서 나오는 모든 주소는 페이지 번호(p: page)와 페이지 오프셋(d: offset) 2개의 부분으로 나누어진다.
• 페이지 번호는 프로세스 페이지 테이블(page table)을 액세스할 때 사용된다.

• 페이지 테이블은 물리 메모리의 각 프레임의 시작 주소를 저장하고 있다.
• 오프셋(offset)은 참조되는 프레임 안에서의 위치이다.
• 따라서, 프레임의 시작 주소와 페이지 오프셋이 결합하여 물리 메모리 주소가 된다.

• 다음은 CPU에 의해 생성된 논리 주소를 물리 주소로 변환하기 위해 MMU가 취한 단계를 요약한 것이다.
  1. 페이지 번호 p를 추출하여 페이지 테이블의 인덱스로 사용한다.
  2. 페이지 테이블에서 해당 프레임 번호 f를 추출한다.
  3. 논리 주소의 페이지 번호 p를 프레임 번호 f로 바꾼다.
• 오프셋 d는 변하지 않기 때문에 대체되지 않으며, 프레임 번호와 오프셋은 이제 물리 주소를 구성한다.

• 프레임 크기와 마찬가지로 페이지 크기는 하드웨어에 의해 정해진다.
• 페이지 크기는 2의 거듭제곱으로, 이렇게 선택하면 논리 주소를 페이지 번호 및 페이지 오프셋으로 쉽게 변환할 수 있다.
• 논리 주소 공간의 크기가 $2^m$이고 페이지 크기가 $2^n$ 바이트인 경우 논리 주소의 상위 m-n 비트는 페이지 번호를 지정하고 n 하위 비트는 페이지 오프셋을 지정한다.
• 따라서 논리 주소는 다음과 같다.

• 페이징 자체는 일종의 동적 재배치이다.
• 모든 논리 주소는 페이징 하드웨어에 의해 실제 주소로 바인딩 된다.
• 페이징을 사용하는 것은 각 메모리 프레임마다 하나씩 기준 레지스터를 테이블로 유지하는 것과 유사하다.

• 페이징 기법을 사용하면 외부 단편화가 발생하지 않는다.
  • 모든 놀고 있는 프레임이 프로세스에 할당될 수 있기 때문이다.
• 그러나 이제는 내부 단편화가 발생한다.
  • 할당은 항상 프레임의 정수배로 할당되기 때문이다.
  • 만약 프로세스가 페이지 경계와 일치하지 않는 크기의 메모리를 요구한다면, 마지막 페이지 프레임은 전부 할당되지 않는다.

• 작은 페이지 크기가 좋다고 생각할 수 있지만, 페이지 크기가 작아지면 그에 반비례하여 페이지 테이블의 크기가 커지게 되고 이 테이블이 차지하는 공간은 낭비된다.
  • 디스크의 입장에서는 페이지의 크기가 클수록 효율적이다.
  • 현재 보통 페이지 크기는 4KB 또는 8 KB이다.

• 한 프로세스가 실행되기 위해 도착하면 그 프로세스의 크기가 페이지 몇 개분에 해당되는지 조사한다.
• 각 사용자 페이지는 한 프레임씩 필요하다.
  • 즉, 프로세스가 n개 페이지를 요구하면 메모리에서 이용할 수 있는 프레임이 n개 있어야 한다.
  • n개의 프레임을 사용할 수 있다면 이 프레임들은 이 프로세스에 할당한다.
• 그리고는 프로세스의 처음 페이지가 할당된 프레임 중 하나에 적재되고, 그 프레임 번호가 페이지 테이블에 기록된다.
• 그다음 페이지는 또 다른 프레임에 적재되고, 또 그 프레임 번호가 페이지 테이블에 기록되며 이 과정이 반복된다. (Figure 9.11)

• 페이징의 가장 유용한 특징은 메모리에 대한 프로그래머의 인식과 실제 내용이 서로 다르다는 것이다.
  • 프로그래머는 메모리가 하나의 연속적인 공간이며, 메모리에는 이 프로그램만 있다고 생각한다.
  • 그러나 실제로는 프로그램은 여러 곳에 프레임 단위로 분산되어 있고, 많은 다른 프로그램이 올라와 있다.

• 운영체제는 물리 메모리를 관리하기 때문에 물리 메모리의 자세한 할당에 대해 파악하고 있어야 한다.
  • 즉, 어느 프레임이 할당되어 있고, 어느 프레임이 사용 가능한지, 총 프레임은 몇 개나 되는지 등을 알아야 하는데, 이런 정보는 프레임 테이블(frame table)이라는 시스템에 하나밖에 없는 자료구조에 있다.
• 또한, 운영체제는 모든 프로세스의 주소들을 실제 주소로 사상할 수 있어야 한다.

9.3.2 Hardware Support

• 페이지 테이블은 프로세스별 자료구조이므로 페이지 테이블에 대한 포인터는 각 프로세스의 PCB에 다른 레지스터 값과 함께 저장된다.
• CPU 스케줄러가 실행할 프로세스를 선택하면 사용자 레지스터를 다시 적재하고 저장된 사용자 페이지 테이블로부터 적절한 하드웨어 페이지 테이블값을 다시 적재해야 한다.

• 페이지 테이블의 하드웨어 구현은 여러 가지 방법으로 수행할 수 있다.
• 가장 간단한 경우, 페이지 테이블은 전용 고속 하드웨어 레지스터 세트로 구현되므로 페이지 주소 변환이 매우 효율적이다.
• 그러나 이러한 접근 방식은 각각의 레지스터가 문맥 교환 중에 교체되어야 하므로 문맥 교환 시간을 증가시킨다.
• 페이지 테이블에 레지스터를 사용하는 것은 페이지 테이블이 작은 경우 적합하다.
• 하지만 큰 페이지 테이블을 구현하기 위해서 위처럼 빠른 레지스터를 사용하는 것은 부적절하다.
• 따라서, 대부분의 컴퓨터는 페이지 테이블을 메인 메모리에 저장하고 페이지 테이블 기준 레지스터(PTBR, page-table base register)로 페이지 테이블을 가리키도록 한다.
  • 다른 페이지 테이블 사용하려면 단지 이 레지스터만을 변화시키면 되고, 따라서 문맥 교환 시간을 줄일 수 있다.

  
  이미지출처 ¹

9.3.2.1 Translation Look-Aside Buffer (TLB)

• 메인 메모리에 페이지 테이블을 저장하면 문맥 교환 속도가 빨라지지만 메모리 액세스 시간이 느려질 수도 있다.
  • 페이지 번호를 기준으로 PTBR 오프셋의 값을 사용하여 페이지 테이블의 항목을 찾는다. (메모리 액세스 접근 1번)
  • 이렇게 얻은 프레임 번호와 페이지 오프셋을 결합하여 실제 주소를 생성한다. (메모리 액세스 접근 2번)
  • 그런 다음 메모리에서 원하는 위치에 액세스할 수 있다.

• 이 문제에 대한 해결에는 TLB(translation look-aside buffer)라고 불리는 특수한 소형 하드웨어 캐시가 사용된다.
  • TLB는 매우 빠른 연관 메모리로 구성된다.
  • TLB 내의 각 항목은 키(key)와 값(value)의 두 부분으로 구성된다.
  • 변환 색인 버퍼(TLB, translation lookaside buffer) : 가상 메모리 주소를 물리적인 주소로 변환하는 속도를 높이기 위해 사용되는 캐시 [^2]
• TLB에 페이지를 찾아달라고 요청이 들어오면 찾고자 하는 페이지를 동시에 여러 개의 내부 키(페이지 번호)와 비교한다.
• 페이지 번호가 같은 것이 발견되면 그에 대응하는 프레임 번호를 알려준다.
• 하지만 파이프라인 단계 동안 검색을 하기 위해서는 TLB의 크기는 작게 유지할 수 밖에 없다.
  • 통상 32개에서 1,024개의 항목을 유지한다.

• TLB는 페이지 테이블의 일부분만을 저장한다.
• CPU가 논리 주소를 생성하면 MMU는 해당 페이지 번호가 TLB에 있는지 확인한다.
• 페이지 번호가 발견되면 해당 프레임 번호를 즉시 알 수 있고 메모리를 접근하는 데 사용된다. (TLB hit)

이러한 절차들은 CPU 내부에서 명령어 파이프라인의 일환으로 실행되기 때문에 페이징을 사용하지 않는 시스템과 비교하면 성능 저하는 전혀 없다.

• 페이지 번호가 TLB에 없으면 (TLB miss) 주소 변환은 위 9.3.1에 설명된 단계에 따라 진행되며, 여기서 페이지 테이블에 대한 메모리 참조가 이루어져야 한다.
• 프레임 번호가 확보되면 이를 사용하여 메모리에 액세스할 수 있다.

• 만약 TLB가 가득 차면, 기존 항목 중에서 교체될 항목을 선택해야 한다.
  • 교체 정책은 LRU부터 RR, 무작위 등 다양한 정책이 사용된다.
• 어떤 TLB는 각 항목에 ASIDs (address-space identifiers)를 저장하기도 한다.
  • ASID는 그 TLB 항목이 어느 프로세스에 속할 것인지를 알려주며 그 프로세스의 정보를 보호하기 위해 사용된다.
• ASID 지원이 있으면 한 TLB 안에 여러 프로세스의 정보를 동시에 함께 보관할 수 있다.
• ASID 지원이 없으면 새로운 페이지 테이블이 선택될 때마다 다음 실행 프로세스가 잘못 변환하지 않도록 하기 위해서 TLB는 전부 플러시(flush)가 되어야 한다.

• 접근하려는 메모리의 페이지 번호가 TLB에서 발견되는 비율을 적중률(hit ratio)이라고 부른다.

9.3.3 Protection

• 페이징 환경에서 메모리 보호는 각 페이지에 붙어있는 보호 비트(protection bits)에 의해 구현된다.
  • 이 비트들은 보통 페이지 테이블에 속해 있다.
• 각 비트는 이 페이지가 읽고, 쓰기 또는 읽기 전용(read-only)임을 각각 정의할 수 있다.
• 메모리에 대한 모든 접근은 페이지 테이블을 거치므로, 이때 주소 변환과 함께 이 페이지에 쓰기가 허용 여부와 같은 검사도 할 수 있다.

• 페이지 테이블의 각 엔트리에는 유효/무효(valid/invalid)라는 하나의 비트가 더 있다.
  • 이 비트가 유효(valid)로 설정되면 관련된 페이지가 프로세스의 합법적인 페이지임을 나타낸다.
  • 이 비트가 무효(invalid)로 설정되면 그 페이지는 프로세스의 논리 주소 공간에 속하지 않는다는 것을 나타낸다.
• 운영체제는 이 비트를 이용해서 그 페이지에 대한 접근 허용 여부를 정할 수 있다.

• 몇몇 시스템은 페이지 테이블의 크기를 나타내기 위해 페이지 테이블 길이 레지스터(PTLR, page table length register)라는 레지스터를 제공한다.
• 프로세스가 제시한 주소가 유효한 범위 내에 있는지를 확인하기 위해 모든 논리 주소 값이 PTLR 값과 비교된다.
• 이러한 검사에서 오류가 나타나면 트랩을 발생시킨다.

9.3.4 Shared Pages

• 페이징의 장점은 공통의 코드를 공유할 수 있다는 점이다.
• 만약 코드가 재진입 코드(reentrant code)인 경우, Fig. 9.14와 같이 공유할 수 있다.
  • 재진입 코드는 자체 수정을 할 수 없는 코드로서 실행 중에는 절대 변경되지 않는다.
  • 따라서 2개 이상의 프로세스가 동일한 코드를 동시에 실행할 수 있다.
  • 각 프로세스에는 자신의 실행을 위해 데이터를 보유하기 위한 자체 레지스터 사본과 데이터 저장영역이 있다.

9.4 Structure of the Page Table

• 이번에는 페이지 테이블을 구성하는 가장 일반적인 방법을 살펴본다.

9.4.1 Hierarchical Paging

• 모든 페이지 테이블을 메인 메모리에서 연속적으로 할당하기를 고집하기 보다는 페이지 테이블을 여러 개의 작은 조각으로 나누는 방법이 있다.
• 한 가지 방법은 2단계 페이지 기법(two-level paging scheme)으로 페이지 테이블 자체가 다시 페이징되게 하는 것이다.

• 만약 논리 주소가 20비트 페이지 번호와 12비트 페이지 오프셋으로 이루어진다고 가정해본다.
  • 4 KB의 크기를 가진 32비트의 기계이다.
• 이 경우 페이지 테이블은 페이지로 나누어지기 때문에, 페이지 번호는 다시 10비트 페이지 번호와 10비트 페이지 오프셋으로 나누어진다.
• 즉, 논리 주소는 다음과 같이 된다.
  • 여기서 $p_1$은 바깥 페이지 테이블의 인덱스이고, $p_2$는 안쪽 페이지 테이블의 페이지 내의 오프셋이다.

• Figure 9.16은 이 구조에 의한 주소 변환 기법을 나타내고 있다.
  • 이 방식에서는 주소 변환이 바깥 페이지 테이블에서 시작하여 안쪽으로 들어오므로 이 방식을 forward-mapped 페이지 테이블이라고도 부른다.

9.4.2 Hashed Page Tables

• 주소 공간이 32비트보다 커지면 가상 주소를 해시로 사용하는 해시 페이지 테이블(hashed page table)을 많이 쓴다.
• 해시 페이지 테이블의 각 항목은 연결 리스트를 가지고 있다.
  • 이곳에는 충돌을 일으켜서 모두 이곳으로 해시되는 원소들이 매달리게 된다.
  • 각 원소는 3개의 필드를 가진다.
    1. 가상 페이지 번호
    2. 사상되는(mapped) 페이지 프레임 번호
    3. 연결 리스트 상의 다음 원소 포인터

• 여기서는 다음과 같이 알고리즘이 작동된다.
  • 가상 주소 공간으로부터 페이지 번호가 오면 그것을 해싱한다.
  • 그것으로 해시 페이지 테이블에서 연결 리스트를 따라가며 첫 번째 원소와 가상 페이지 번호를 비교해본다.
  • 일치되면 그에 대응하는 페이지 프레임 번호를 가져와 물리 주소를 얻는다.
  • 일치되지 않으면 연결 리스트의 그다음 원소로 똑같은 일을 반복한다.

9.4.3 Inverted Page Table

• 보통 프로세스는 각자 하나씩 페이지 테이블을 가지고, 페이지 테이블은 프로세스가 사용하는 페이지마다 하나의 항목을 가진다.
  • 프로세스는 페이지의 가상 주소를 통하여 페이지를 참조한다.
• 운영체제는 프로세스가 가상 페이지 주소를 제시할 때마다 이 테이블에 와서 그것을 실제 페이지 주소로 변환시켜 주어야 한다.
• 테이블은 가상 주소에 대해 오름차순으로 정렬되어 있고 운영체제는 테이블 내의 어느 곳에 원하는 물리 페이지가 있는지를 게산할 수 있고, 이 값을 통해서 메모리를 액세스할 수 있다.

• 이 기법의 단점 중 하나는 각 페이지 테이블 항목의 개수가 수백만 개가 될 수 있다는 것이다.
  • 이러한 테이블은 물리 메모리의 사용을 추적하기 위해 많은 양의 물리 메모리를 소비한다.
• 이 문제를 해결하는 한 방법이 역 페이지 테이블(inverted page table)이다.
• 역 페이지 테이블에서는 메모리 프레임마다 한 항목(entry)씩을 할당한다.
  • 각 항목(entry)은 그 프레임에 올라와 있는 페이지 주소, 그리고 그 페이지를 소유하고 있는 프로세스의 ID를 표시하고 있다.
• 이렇게 되면 시스템에는 단 하나의 페이지 테이블만이 존재하게 되고, 테이블 내 각 항목은 메모리 한 프레임씩을 가리키게 된다.
• 그리고 주소 공간 ID를 저장함으로써 특정 프로세스의 논리 페이지가 그에 상응하는 물리 페이지 프레임과 사상되었다는 것을 보장해준다.

• 이 방법은 논리 페이지마다 항목을 가지는 대신 물리 프레임에 대응되는 항목만 테이블에 저장하기 때문에 메모리에서 훨씬 작은 공간을 점유한다.
• 그러나 역 페이지 테이블은 주소변환 시간이 더 오래 걸릴 수 있다.
  • 역 페이지 테이블은 물리 주소에 따라 정렬되어 있고 탐색은 가상 주소를 기준으로 하므로 테이블 전체를 탐색하여야 할 수도 있다.

9.5 Swapping

• 프로세스가 실행되기 위해서는 프로세스의 명령어와 명령어가 접근하는 데이터가 메모리에 있어야 한다.
• 그러나 프로세스 또는 프로세스의 일부분은 실행 중에 임시로 백업 저장장치(backing store)로 내보내어 졌다가 실행을 계속하기 위해 다시 메모리로 되돌아 올 수 있다.
• 모든 프로세스의 물리 주소 공간 크기의 총합이 시스템의 실제 물리 메모리 크기보다 큰 경우에도 스와핑을 이용하면 동시에 실행하는 것이 가능하여 멀티 프로그래밍의 정도를 증가시킨다.

9.5.1 Standard Swapping

• 표준 스와핑에는 메인 메모리와 백업 저장장치 간에 전체 프로세스를 이동한다.
  • 백업 저장장치는 일반적으로 빠른 보조저장장치다.
  • 백업 저장장치는 저장 및 다시 접근해야 하는 프로세스의 크기에 상관없이 수용할 수 있을 만큼 커야 하며, 이러한 메모리 이미지에 직접 액세스 할 수 있어야 한다.

9.5.2 Swapping with Paging

• 표준 스와핑은 기존 UNIX 시스템에서 사용되었지만 메모리와 백업 저장장치 간에 프로세스 전체를 이동하는 데 걸리는 시간이 엄청나기 때문에 일반적으로 최신 운영체제에서는 더는 사용되지 않는다.
• Linux 및 Windows를 포함한 대부분의 시스템은 프로세스 전체가 아닌 프로세스 페이지를 스왑할 수 있는 변형(variation) 스와핑을 사용한다.
• 이 전략은 여전히 물리 메모리를 초과할 수 있지만 프로세스 전체를 스왑하는 비용은 발생하지 않는다.
• 실제로, 스와핑(swapping)이란 용어는 일반적으로 표준 스와핑을 말하며, 페이징(paging)은 페이징에서의 스와핑을 의미한다.
• 페이지 아웃(page out) 연산은 페이지를 메모리를 백업 저장장치로 이동시킨다.
• 페이지 인(page in) 연산은 페이지 아웃의 반대 연산이다.

References

1. 메모리 관리 1 - 주소 바인딩 - Primitive ↩ ↩²