[Operating System Concepts 10th] 9. Main Memory 리뷰 (2)

본 글은 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

이전 글 링크 : [Operating System Concepts 10th] 9. Main Memory 리뷰 (1)

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) : 가상 메모리 주소를 물리적인 주소로 변환하는 속도를 높이기 위해 사용되는 캐시 ²
• 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. How page table base register (PTBR) is used to locate the correct frame using Page Number? - StackExchange ↩

2. 변환 색인 버퍼 - 위키백과 ↩