Virtual Memory

주소 변환의 원리

cpu와 마찬가지로 memory에서도 가상화 비슷한 전략을 추구한다. 제어와 효율성을 추구함. 프로그램을 다른 프로그램으로부터 보호하고 운영체제를 프로그램으로부터 보호하려면 하드웨어 도움이 필요함. 밑의 핵심문제를 보자

여기서 다루는 기법은 하드웨어-기반 주소 변환인데 짧게 주소 변환이라고도 한다. 가상 주소를 물리 주소로 변환하는 것. 주소 변환은 하드웨어가 하지만 하드웨어를 셋업 하기 위해 운영체제가 관여해야 함. 메모리의 빈 공간 사용 공간 등 알고 있어야 함. 먼저 가장 간단한 가정부터 시작함 사용자의 주소 공간이 물리 메모리에 연속적으로 배치되어야 한다고 가정. 또한 주소 공간은 물리 메모리 크기보다 작고, 주소 공간의 크기가 같다고 가정. 예시를 보면 프로그램 관점에서 0부터 시작해서 최대 16KB까지인데 이걸 어디에 재배치해야 하나 가 문제이다. 우리의 전략은 동적 재배치라고 하는 방식으로 한다 여기서 베이스 레지스터와 바운드 레지스터가 쓰인다. 베이스는 가상 주소를 물리 주소로 변환하게 더해주는 offset 같은 역할을 하고 바운드는 보호를 위해 존재하는데 주소가 지정된 크기를 넘어가지 않게 한다. 바운드를 설정하는 방법은 2가지가 있는데 베이스를 더하기 전에 바운드 기준으로 보거나 바운드를 물리 주소로 하여 베이스를 더하고 보는 방식이 있다. 하드웨어 요구 사항을 보자

하드웨어는 바운드 베이스 레지스터 변경 명령어 제공해야 한다. 이 명령은 커널 모드에서만 동작해야 한다. 또한 cpu는 바운드 주소를 벗어난 메모리 접근이 일어나면 예외를 발생시킴. 다음은 운영체제 책임을 보자

첫째로 운영체제는 주소 공간이 저장될 메모리 공간을 찾아야 한다. 둘째로는 프로세스가 어떻게든 종료가 되면 메모리를 회수해야 한다. 셋째로 프로세스 전환 시 pcb에 레지스터를 저장하고 복원해야 하고 , 넷째로 핸들러 함수들을 부팅할 때 로드에서 하드웨어가 알게 해줘야 함.

밑은 구체적은 실행 과정이다.

동적 재배치를 마무리하고 넘어가겠다. 일단 동적 재배치는 비효율적이다 스택과 힙 사이에 크기가 너무 크고 할당된 영역의 내부 공간이 다 사용되지 않기 때문에 내부 단편화가 일어남. 고정 크기의 슬롯에 주소 공간을 배치해야 하기 때문. 다음은 물리 메모리의 이용률을 높이고 내부 단편화를 방지하기 위해 세그멘테이션에 대해 알아보자.

segmentation

먼저 세그멘테이션을 왜 쓰는지 한 번 더 정리하자 이와 같은 아이디어가 나오게 된 배경은 스택과 힙 사이의 공간은 사용되지 않더라도 주소 공간을 물리 메모리에 재배치할 때 물리 메모리를 차지한다. 메모리 낭비가 심하고 위의 방식은 사실 주소 공간이 물리 메모리보다 작은 경우였다. 위의 2가지 내용을 해결해 나가 보자. mmu에 하나의 베이스와 바운드 쌍만 존재하는 것이 아니라 주소 공간의 논리적인 세그먼트마다 베이스와 바운드가 존재한다. 세그먼트에는 여기서는 일단 코드 스택 힙이 있다. 각 세그먼트를 물리 메모리의 각기 다른 위치에 배치해서 사용되지 않는 가상 주소 공간이 물리 메모리를 차지하는 것을 방지 할 수 있다. 베이스와 바운드가 주소를 변환하는 방식은 기존과 비슷한데 주의할 점은 가상 주소의 시작 부분에 맞춰서 오프셋을 더해주어야 한다. 또한 여기서 바운드는 단지 크기만을 비교하면 알 수 있다.

 그럼 하드웨어가 어느 세그먼트를 참조해야 하고 세그먼트 안에서 오프셋은 얼마인지 어떻게 아냐? 가상 주소를 최상위 몇 비트를 기준으로 주소 공간을 나눔 여기서는 최상위 2비트가 세그먼트를 나타내고 나머지가 오프셋을 나타낸다. 다른 방법으로 implicit 한 방법이 있는데, 주소가 어떻게 형성되었나를 관찰하여 세그먼트를 결정한다. 주소가 프로그램 카운터에서 생성되었다면 코드에 있고 스택 또는 베이스 포인터면 스택 세그먼트이고 나머지는 힙이다. 세그 먼트 중에서도 스택을 한번 보자 스택은 다른 세그먼트랑은 다르게 주소가 반대로 커진다 즉 작아진다. 따라서 오프셋을 구할 때도 크기에서 오프셋을 빼준값을 다시 더해줘서 변환해준다. 주소 공간들 간에 특정 메모리 세그먼트를 공유하는 것이 메모리 절약하기에 좋은데 특히 코드 공유가 일반적이다. 그리고 이러한 공유를 지원하기 위해서는 protection bit 추가가 필요하다.  이 비트를 추가하여 세그먼트를 읽거나 쓸 수 있는지 혹은 세그먼트의 코드를 실행시킬 수 있는지를 나타낸다.  소단위 세그멘테이션, 우리는 크게 세그맨테이션을 만들었는데 대단위라고 볼 수 있다. 작게 쪼개는 소단위는 융통성 있게 세그먼트를 사용할 수 있다.  다시 정리를 해보면 시스템이 각 주소 공간 구성 요소를 별도로 물리 메모리에 재배치하기 때문에 전체 주소 공간이 하나의 베이스-바운드 쌍을 가지는 간단한 방식에 효율적이다.  이러한 세그멘테이션은 새로운 문제들을 제기하는데 첫째로는 문맥 교환 시 세그먼트 레지스터의 저장과 복원이다. 운영체제는 프로세스가 시작되기 전에 이 레지스터들을 올바르게 연결해야 함. 두 번째는 미사용 중인 메모리 공간의 관리다. 운영체제는 세그먼트를 위한 비어있는 물리 메모리 영역을 찾을 수 있어야 한다. 이전에는 각 주소 공간이 동일하다고 가정했다. 지금은 프로세스가 많은 세그먼트를 가질 수 있고 그 크기는 다 다르다. 일반적으로는 작게 나누게 되면 새롭게 생겨나는 큰 공간을 할당하기가 힘들다 이런 문제를 외부 단편화라고 한다. 이 문제의 해결책 중 하나는 물리 메모리를 압축하는 것이다. 다른 방법은 빈 공간 리스트를 관리하는 알고리즘을 사용하는 것이다. 빈 공간 관리 알고리즘은 여러 방법이 존재함. 또 다른 문제로는 드문드문 사용되는 힙이 하나의 세그먼트에 배정되어 있다면 물리 메모리에 올릴 때 전체가 존재해야 한다. 이러한 문제들을 밑에서 다뤄 보겠다.

빈 공간 관리

이 장에서는 모든 메모리 관리 시스템의 근본적인 측면을 논의함,  여기서 메모리 관리 시스템이란 힙의 페이지를 관리하는 malloc일 수도 있고 프로세스의 주소 공간의 일부분을 관리하는 운영체제 자체 일 수도 있다. 구체적으로 빈 공간 관리에 관련된 문제를 논의할 것이다.  빈 공간 관리가 어려운 경우는 관리하는 공간이 가변-크기 빈 공간들의 집합으로 구성되어 있는 경우이다. 이 경우는 malloc과 free에서 처럼 사용자 수준 메모리-할당 라이브러리에서, 그리고 세그멘테이션으로 물리 메모리를 관리하는 운영체제에서 발생한다. 어느 경우에도 외부 단편화 존재  여기서는 사용자 수준 메모리 할당 라이브러리에 존재하는 메모리 할당기에 초점을 맞출 것이다. 이 라이브러리가 관리하는 공간은 힙으로 불리며 힙의 빈 공간을 관리하는 데는 연결 리스트가 일반적으로 사용. 반드시 리스트일 필요는 없음. 또한 우리는 외부 단편화를 중점으로 이야기하겠다. 우리는 또한 클라이언트에게 할당된 메모리는 다른 위치로 재배치될 수 없다고 가정. free 하기 전까지. 단편화 해결을 위한 빈 공간 압축은 이경우에 사용 불가. 운영체제가 세그먼트를 위한 단편화 해결하기 위해서는 쓸 수 있음. 나중에 알아보고 이제 할당기에서 사용하는 일반적인 기법을 보자.  크게 2가지로 나뉜다 분할과 병합. 분할은 말 그대로 빈 공간 리스트에서 할당 요청이 들어오면 요청한 만큼만 주고 나머지는 다시 빈 공간 리스트에 있게 됨. 병합은 기존 사용되던 메모리 청크가 반납될 때 그 주변의 빈 공간 들과 합치는 것이다. 힙 영역에서 할당된 공간의 크기를 알기 위해서는 헤더라는 블록이 존재해야 됨 거기에는 사이즈와 안전성 검사를 위한 magic number가 있다. 또한 헤더는 사이즈를 제외하고 자기만의 크기가 있어야 됨. 따라서 우리는 할당해줄 때 헤더 크기까지 생각해야 됨. 힙의 확장도 생각해 봐야 하는데 시스템 콜인 sbrk를 요청함. 그럼 운영체제는 빈 물리 페이지를 찾아 프로세스 주소 공간에 매핑한 후, 새로운 힙의 마지막 주소를 반환.  기법에 대해 봤으니 진짜 할당을 어떻게 하는지 , 자세한 거는 직접 찾아보고 정책들 살펴보자 먼저 최적 적합 이건 가장 사이즈 맞는 것 중에 작은 거 찾음 그래서 무조건 빈 공간 리스트 다 돌아야 됨,  최악 적합은 그냥 무조건 큰 거 줌 이것도 전체 탐색함. 최초 적합은 처음 탐색하면서 만난 최조 중에 적합한 거 줌. 이거는 빈 공간 리스트 순서를 관리하는 게 중요함. next fit도 있는데 이건 그전에 찾았던 위치 다음부터 계속 진행해 나감. 또 다른 접근법으로는 개별 리스트가 있는데 특정 응용 프로그램에서 자주 요청하는 한 두 개 크기를 그 객체를 위한 별도의 리스트를 유지. 단편화를 확실히 줄여줌 근데 문제가 지정된 크기와 일반 메모리 풀 사이에 어떻게 메모리를 할당하는지가 의문. 그래서 나온 게 슬랩 할당기 이거는 커널 객체를 위한 객체 캐시를 이용함 여기서 말하는 객체는 우리가 아는 아이 노드, 락 등등. 객체 캐시는 지정된 크기의 객체들로 구성된 빈 공간 리스트임. 기존에 할당된 캐시 공간이 부족하면 상위 메모리 할당기에게 슬랩을 요청. 반대로 슬랩 내 객체들의 참조 횟수가 0이면 회수가 일어남. 슬랩은 빈 객체들을 사전에 초기화된 상태로 유지한다는 점에서 개별 리스트보다 우수함. 다음으로 버디 할당에 대해 알아보자 이건 빈 공간 리스트를 2^n인 하나의 크기에서 2씩 나눠서 계속  일정 크기의 2의 거듭제곱으로 만듦 버디 할당의 이점은 해제될 때 있다. 해제할 때 예를 들어 8KB 블록을 빈 공간 리스트에 반환하면 다른 8KB가 비어 있는지 확인하고 병합하여 16KB를 얻음 이렇게 계속 반복해서 다시 크게 만듦. 버디 할당이 잘 동작하는 이유는 특정 블록의 버디를 결정하는 것이 쉽다. 각 버디 쌍의 주소는 오직 한 비트만 다름. 앞에서 설명한 것들의 문제는 확장성임 리스트는 결국 개수가 늘어나면 순회 시간이 늘어남 따라서 다른 자료구조도 생각해볼 수 있음.

페이징: 개요

운영체제는 거의 모든 공간 관리 문제 해결할 때 두 가지 중 하나를 사용하는데 하나가 우리가 앞서 보았던 세그멘테이션이고 이건 가변 크기의 조각들로 분할함 근데 문제가 외부 단편화가 생기기 쉬움 그래서 여기서는 페이징이라고 동일한 크기의 조각으로 분할하는 것을 생각. 페이징의 장점은 유연성이다. 프로세스 주소 공간 사용 방식과는 상관없이 효율적으로 주소 공간 개념을 지원함. 힙과 스택이 어느 방향으로 커지는지 중요하지 않음 또 다른 장점은 단순함이다. 예를 들어 4개의 페이지를 물리 메모리 프레임에 배치하기 원하면 그냥 빈 공간 리스트에서 네 개의 페이지를 선택하면 됨 주소 공간의 각 가상 페이지에 대한 물리 메모리 위치 기록을 위하여 운영체제는 프로세스마다 페이지 테이블이라는 자료 구조를 유지함// 페이지 테이블의 주요 역할은 가상 페이지의 주소 변환임  가상 주소가 어떻게 물리 페이지로 변환되는지 보자 예를 들어 64바이트 주소 공간에서 페이지 크기가 16 바이트면 4개의 페이지가 가능하니까 2비트로 표현이 가능함 따라서 2비트 vpn을 가짐 나머지 4비트는 오프셋 vpn으로 페이지 테이블에서 페이지 테이블 엔트리 고르고 거기서 PFN을 찾아서 offset을 붙여서 만들어 준다. 여기서 한번 질문해보자 페이지 테이블은 어디에 저장되고 크기가 얼마이고 느리게 만들지 않을까?? 먼저 페이지 테이블은 위의 이론상 4KB를 가지면 변환 주소가 2^20이라는 걸 알 수 있다. 페이지 테이블 항목마다 4바이트 가지면 4MB 메모리가 필요하게 됨. 이게 또 프로세스가 100이라 그러면 400MB나 된다. 따라서 MMU에 있을 수는 없고 지금은 물리 메모리에 있다고 가정 나중에 보면 운영체제 가상 메모리에 존재할 수도 있고 디스크에 스왑 될 수도 있다.  자 그럼 페이지 테이블에는 실제 무엇이 있는가 아까 잠깐 이야기했지만, 페이지 테이블은 vpn을 통해서 pte에서 맞는 PFN을 찾게 함 여기서 valid bit라는 비트가 있는데, 프로그램이 실행을 시작할 때 코드와 힙이 주소 공간의 한쪽에 있고 반대쪽은 스택이 차지하고 있을 것이다. 그 사이의 모든 공간을 무효로 표시하고 이 메모리에 접근하려 하면 트랩을 발생시킴. 즉 할당되지 않은 주소 공간을 표현하기 위해 반드시 필요.  미사용 페이지를 모두 표시함으로써 이러한 페이지들이 물리 프레임을 할당할 필요를 없앤다. 또 페이지가 읽을 수 있는지 쓸 수 있는지 실행될 수 있는지를 표시하는 protection bit가 있다. present bit은 이 페이지가 물리 메모리에 있는지 혹은 디스크에 있는지 가리킨다. 이런 기본적인 기법들은 나중에 물리 메모리보다 더 큰 주소 공간을 지원하기 위해 주소 공간의 일부를 스왑 하는 방법에 대해 자세히 이야기함.  dirty bit은 변경되었는지 여부를 나타냄. reference bit은 때때로 페이지가 접근되었는지를 추적하기 위해 사용. 이 정보는 페이지 교체 때 자세히 다룸. 

이제 문제를 알아보자 페이징은 일단 너무 느리다. 페이지 테이블 자체가 메모리 상에서 매우 크게 증가할 수 있기 때문.  먼저 시스템은 프로세스가 페이지 테이블에서 적절한 페이지 테이블 엔트리를 가져와야 하기 때문에 현 프로세스의 페이지 테이블의 위치를 알아야 한다. 이걸 페이지 테이블 베이스 레지스터라 하는 곳에 저장한다. 

페이징을 사용한 메모리 접근

모든 메모리 참조에 대해 먼저 페이지 테이블에서 변환 정보를 반입해야 하기 때문에 무조건 메모리 참조 더 필요함. 자 그럼 2가지 문제를 정리해 보자. 하드웨어와 소프트웨어의 신중한 설계 없이는 페이지 테이블로 인해 시스템이 매우 느려질 수 있고 많은 메모리를 차지한다. 그럼 어떻게 이 시스템을 고안했는지 보자.

페이징: 더 빠른 변환

자 주소 변환 속도를 그럼 어떻게 빠르게 할 수 있을까?? 여기 TLB라는 하드웨어가 나온다. 아무튼 운영체제에서 개선이 필요하면 일단 하드웨어도 생각해 봐야 한다. TLB는 MMU의 일부다. 주소 변환 캐시라 보면 됨.  간략하게 설명하면 가상 메모리 참조 시. 하드웨어는 먼저 TLB에 원하는 변환 정보가 있는지를 확인함. 만약 있다면 페이지 테이블을 가지 않고 변환을 바로 실행. 이 방법 덕분에 페이징이 진짜 사용 가능하게 됨.

TLB 제어 흐름 알고리즘

TLB에 존재하는 걸 TLB히트라고 하는데 TLB가 변환 값을 갖고 있다는 뜻이다. TLB미스가 나면 하드웨어가 변환 정보를 찾기 위해서 페이지 테이블에 접근하고 가상 메모리 참조가 유효하고 접근 가능하면 변환 정보를 TLB로 읽어 들임. TLB가 갱신되면 하드웨어는 명령어를 재 실행. 자 그럼 여기서 또 궁금증이 생기는데 TLB 미스는 어디서 처리하나 여기서 두 가지  방법이 나옴 하드웨어적으로 해결하려는 것이 CISC라고 과거에 복잡한 명령어들로 구성된 하드웨어들이 있었다. 그래서 TLB미스를 하드웨어가 페이지 테이블에 대한 명확한 정보를 가지고 처리하도록 설계함. 인텔 x86이 하드웨어로 관리되는 TLB의 예시다 이따가 보겠지 담 x86 cpu는 멀티 페이지 테이블을 사용함. 다음으로 RISC는 보다 최근에 등장했는데 TLB를 소프트웨어가 관리하는 구조이다. TLB에서 주소 찾는 것이 실패하면 예외를 발생시키고, 커널 모드로 들어가서 트랩 핸들러를 실행. TLB 미스를 처리하는 핸들러임. 여기서 트랩 핸들러는 시스템 콜의 핸들러와는 다르게 다음 명렬 어가 아니라 기존 명령어를 한번 더 실행. 또 기억해야 될 점은 TLB 미스가 무한 반복되지 않도록 주의해야 함 왜냐면 애초에 TLB핸들러를 접근하는 과정에서 TLB 미스가 발생할 수가 있기 때문이다. 그래서 TLB 핸들러를 물리 메모리에 위치시키는 것도 방법이다. 다른 방법은 TLB의 일부를 핸들러 코드 주소를 저장하는 데 영구 할당하는 것이다. 그러면 TLB 핸들러는 항상 히트될 것이다. 이런 방식은 연결(wired) 반환이라 함. 소프트웨어적으로 TLB를 관리하는 방식의 장점은 유연성이다. 또 다른 장점은 단순함. 미스가 났을 때 하드웨어가 할 일이 별로 없기 때문이다. 자 그럼 TLB에 대해서 구체적으로 알아보자 TLB는 어떻게 구성돼있나.  일단 TLB는 완전 연관 방식으로 설계돼서 변환 정보를 어디서든 접근 가능함.

즉 TLB는 완전 연관 캐시이다. 다른 비트들 중에서  valid bit가 여기에도 있는데 페이지 테이블이랑 다른 점은 페이지 테이블에서는 해당 페이지가 프로세스에 할당되지 않은 것을 의미하고 접근하지 않고 접근하면 kill 되지만. TLB는 말 그대로 항목이 아직 무효 처리되어 있어서 갱신시키면서 채워지게 된다. 이건 나중에 context switching 할 때도 사용된다. 새로운 프로세스가 이전 변환 정보를 사용하는 것을 원천 차단. 자 그럼 두 개의 프로세스가 있을 때 예제를 한번 보자.

다음과 같이 TLB가 되어있다 10번째 가상 페이지가 두 프로세스에서 다르게 매핑되어 있는 것이다. 하지만 TLB는 그걸 모른다. 그럼 바로 해결해 보자. 위에서 말한 valid bit를 0으로 해서 비워주는 방식이 있다 근데 이건 문맥 교환 때마다 해주면 프로세스 바뀔 때마다 갱신해줘야 함. 다른 방법으로는 주소 공간 식별자라는 ASID 필드를 추가해 무슨 프로세스 인지 알 수 있게 해 준다. 위와 다르게 다른 가상 페이지가 같은 물리 프레임을 가리킨다 하면 이건 하나의 페이지에 두 프로세스가 공유하고 있다는 것을 알 수 있다. 이게 바이너리든 공유 라이브러리든 물리 페이지 수를 줄일 수 있기 때문에 굉장히 유용함. 자 그럼 TLB는 어떤 식으로 교체하는지 알아보자. 간단히 설명하면 LRU를 대표적으로 들 수 있다. 이름과 같이 최근까지 가장 사용이 덜 된 페이지를 내보내는 것이다. 하지만 이 방식은 교수님 수업에서 말한 것처럼 실제로 구현하기에 매우 까다로워서 pu와 마찬가지로 memory에서도 가상화 비슷한 전략을 추구한다. 제어와 효율성을 추구함. 프로그램을 다른 프로그램으로부터 보호하고 운영체제를 프로그램으로부터 보호하려면 하드웨어 도움이 필요함. 밑의 핵심문제를 보자

 

페이징: 더 작은 테이블

페이징의 두 번째 문제점은 페이지 테이블의 크기이다.  페이지 테이블이 크면 많은 메모리 공간을 차지하게 된다. 전에 이야기한 것처럼 페이지 크기가 4KB이고 페이지 테이블의 각 항목은 4바이트인 32비트 주소 공간을 가정해 보자. 그럼 주소 공간에는 대략 백만 개의 가상 페이지가 존재할 것이고, 여기에 항목의 크기를 곱하면 페이지 테이블 크기가 약 4MB가 된다. 또한 프로세스마다 페이지 테이블을 가지니 100개만 해도 400MB가 됨. 그럼 어떻게 줄 일 수 있나? 간단한 방법으로는 페이지 크기를 늘리면 된다. 하지만 당연히 내부 단편화가 증가함. 이러면 당연히 메모리가 금방 고갈된다. 그래서 생각해보면 전에 말한 세그먼트와 페이징의 기술을 합쳐서 방법을 생각해 볼 수 있다. 16KB 주소 공간을 예시로 들어 보자

1KB 크기의 페이지를 갖는 16KB의 주소 공간을 예로 보자. 위의 테이블을 보면 대부분이 비어있다. 새로운 방식으로 결합해서 생각해 보자. 프로세스 전체 주소 공간을 위해 하나의 페이지 테이블을 두는 게 아니라, 논리 세그먼트마다 따로 페이지 테이블을 두는 것이다. 여기서는 코드, 힙 그리고 스택 세그먼트에 페이지 테이블을 각각 두는 것이다. 여기서 베이트 레지스터는 세그먼트 시작 주소가 아니라 세그먼트의 페이지 테이블의 시작 주소를 갖는다. 가상 주소는 다음과 같이 표현 가능하다.

이 시스템에서 모든 프로세스들은 세 개의 페이지 테이블을 갖는다. context switch시 레지스터들은 새로 실행되는 프로세스의 페이지 테이블의 위치 값으로 변경. 세그먼트 비트를 사용하여 세그먼트를 고른 뒤 나머지는 기존 페이징 방식과 같이 PTE를 얻는다. 정리하자면 하이브리드 기법의 핵심은 세그먼트마다 바운드 레지스터가 따로 존재하는 것이다. 바운드 레지스터 값은 세그먼트 최대 유효 페이지의 개수를 나타낸다. 여기서 스택과 힙 상의 할당되지 않은 페이지들은 페이지 테이블 상에서 공간을 차지하지 않음. 하지만 여기도 단점이 있는데 세그먼테이션 단점처럼 유연하지 못하고, sparce 한 힙의 경우에는 여전히 페이지 테이블을 낭비한다. 또 다른 단점으로는 외부 단편화를 유발함. 메모리 상에서 페이지 테이블용 공간 확보가 어렵다.

멀티 레벨 페이지 테이블

세그멘테이션을 사용하지 않고 페이지 테이블 크기를 줄이는 방법에 대해서 생각해보면, 멀티 레벨 페이지 테이블을 생각할 수 있다. 여기서는 페이지 테이블을 트리 구조로 표현. 기본 개념부터 잡자. 페이지 테이블을 페이지 크기의 단위로 나눈다. 그다음, 페이지 테이블의 페이지가 유효하지 않은 항목만 있으면, 해당 페이지를 할당하지 않는다. 페이지 디렉터리라는 자료 구조를 사용하여 페이지 테이블 각 페이지의 할당 여부와 위치를 파악함. 페이지 디렉터리는 페이지 테이블을 구성하는 각 페이지의 존재 여부와 위치 정보를 가지고 있다. 밑의 예시를 보자

 

페이지 디렉터리에 유효한 페이지가 2개 있고 이 페이지들은 메모리에 존재한다. 페이지 디렉터리의 항목들은 테이블의 한 페이지를 나타낸다. PDE의 구성은 유효 비트와 PFN으로 구성된다. 페이지가 유효하다는 것은 이 페이지 내에 페이지들 중 최소한 하나가 유효하다는 것을 의미한다. 즉, PDE가 가리키고 있는 페이지 내의 최소한 하나의 PTE의 valid bit가 1로 설정됨. 멀티 레벨 페이지 테이블의 장점은 사용된 주소 공간의 크기에 비례하여 페이지 테이블 공간을 할당함. 다른 장점으로  페이지 테이블을 페이지 크기로 분할함으로써 메모리 관리가 매우 용이하다. 페이지 테이블을 할당하거나 확장할 때 운영체제는 free페이지 풀에 있는 빈 페이지를 가져다 쓰면 됨. 기존 선형 페이지 테이블은  크기가 클 경우 연속된 빈 물리 메모리를 찾는 것이 쉽지 않다.  한 가지 유의 사항은 멀티 레벨 페이지는 시간면에서 손해를 볼 수밖에 없다. TLB 미스 시 주소 변환을 위해 두 번의 메모리 로드가 발생.  또 다른 단점으로는 복잡도다.

다음으로는 페이지 테이블을 2단계 이상 사용하는 경우를 보자 예제에서는 512바이트 페이지와 30비트 가상 주소 공간을 가정한다. 페이지 크기가 512바이트이고 PTE크기가 4 바이트면 한 페이지에 128개의 PTE를 넣을 수 있다.  페이지 디렉터리를 위해서 14개의 비트가 남는다.  128 페이지의 연속된 메모리가 필요하게 되니 다시 나눈다. 7개의 비트들로 나눠서 작성한다. 

마지막으로 다른 기법을 한번 보자 역 페이지 테이블이라고 프로세스당 여러 개의 페이지 테이블을 두는 대신 한 시스템에 페이지 테이블을 하나 두고 그 테이블에 프로세스의 정보와 가상 페이지 번호를 갖는다. 모든 테이블을 검색해야 돼서 검색이 빠른 해시 테이블을 사용한다. 

마무리를 하면서 다른 가정을 해 보겠다. 원래 페이지 테이블은 커널이 소유하고 있는 물리 메모리에 있다고 가정했지만,  여전히 모든 페이지 테이블을 메모리에 상주시키기에는 양이 너무 클 수 있으니 커널 가상 메모리에 존재하게 하거나. 페이지 테이블을 디스크로 스왑 하는 방식도 생각해 볼 수 있다. 더 자세한 건 나중에.

결론적으로 속도를 위해 TLB를 사용했고, 공간 복잡도를 개선하기 위해 여러 기법들을 살펴보았다. 공간을 많이 소모하는 테이블을 사용할수록 TLB 미 초밥 처리속도가 빨라지고, 공간을 작게 차지하는 테이블 구조를 사용하면 반대의 상황이 된다.

물리 메모리 크기 극복:메커니즘

지금 까지는 비현실적으로 가상 주소 공간이 작아서 물리 메모리에 탑재가 가능하다고 가정. 하지만 현실적으로 다수의 프로세스들이 큰 주소 공간을 사용하는 것처럼 느껴야 함. 이것을 구현하려면 하드 디스크가 필요함 우리는 이제 하드 디스크에 스왑 공간을 두어서 큰 가상 메모리가 있는 것 같은 환상을 줄 수 있다. 스왑 공간이란 디스크에 페이지들을 저장할 수 있는 일정 공간을 확보하는 것이다. 운영체제는 스왑 공간에 있는 모든 페이지들의 디스크 주소를 기억해야 한다. 이제 스왑을 위한 기능을 알아보자. present bit라는 것을 사용하는데 페이지 테이블 엔트리에 present bit를 둬서 물리 메모리에 해당 페이지가 존재하는 지를 알 수 있다. 물리 메모리에 존재하지 않는 페이지를 접근하는 행위가 페이지 폴트를 일으킨다. 그걸 처리하는 것이 페이지 폴트. 먼저 기존 메커니즘대로 cpu에서 특정 데이터를 요구해서 메모리에 접근해야 하는데 tlb에 그 주소가 없어서 페이지 테이블로 갔는데 없고 디스크로 스왑 되어 있다면 운영체제는 해당 페이지를 메모리로 스왑해 온다. 그 뒤 다시 확인하면서 tlb까지 갱신. 그럼 원하는 페이지의 위치를 어떻게 파악하나. 많은 시스템들이 해당 정보, 즉 해당 페이지의 스왑 공간에서의 위치를 페이지 테이블에 저장한다. 운영체제는 PFN과 같은 PTE비트들을 페이지의 디스크 주소를 나타내는 데 사용할 수 있다. 페이지 폴트 발생 시, 운영체제는 페이지 테이블 항목에서 해당 페이지의 디스크 상 위치를 파악하여, 메모리로 탑재함. 이 과정 중에 해당 프로세스가 차단된 상태라는 것을 유의해야 함. 페이지 폴트 처리 시 운영체제는 다른 프로세스들을 실행할 수 있다. I/O 실행은 시간이 많이 소요되기 때문이다. 만약 메모리에 빈 공간이 없으면 페이지를 아웃시키는 페이지 교체 정책을 쓰는데 구체적인 것은 나중에 다루겠다.. 그렇다면 공간이 꽉 찼을 때만 페이지를  교체하는가? 아니다 메모리에는 항상 어느 정도 여유 공간을 비워두기 때문에 운영체제는 여유 공간에 관련된 최댓값과 최솟값을 선정하여 여기에 맞춰 페이지 교체 알고리즘을 작동시킨다. 또한 다수의 페이지들을 클러스터나 그룹으로 묶어서 한 번에 스왑 파티션에 저장하기도 한다. 위의 알고리즘은 백그라운드 페이징 스레드가 처리할 수 있게 알고리즘이 알려준다. 이 스레드가 페이지들을 비운 뒤 스레드들을 다시 깨워서 원하는 페이지들을 불러들일 수 있도록 한다.

물리 메모리 크기의 극복 : 정책

위에서 메커니즘을 정리했으니 이제는 구체적인 정책에 대해 이야기해보겠다. 내보낼 페이지는 어떻게 결정할까? 시스템의 전체 페이지들 중 일부분만 메인 메모리에 유지된다는 것을 가정하면, 메인 메모리는 시스템의 가상 메모리 페이지를 가져다 놓기 위한 캐시로 생각될 수 있다. 이 캐시를 위한 교체 정책의 목표는 캐시 미스의 횟수를 최소화하는 것이다. 한편으로는 캐시 히트 횟수를 최대로 하는 것도 목표라 봐도 좋다. 캐시 히트와 미스의 횟수를 안다면 프로그램의 평균 메모리 접근 시간을 계산할 수 있다.

AMAT

이 지표를 통해 각 알고리즘을 비교할 것이다. 그전에 우선 최적 교체 정책을 알 필요가 있다. 이건 간단히 정리하면 미래에 어떤 페이지가 가장 안 쓰일지를 알고 그 페이지를 교체하는 것이다. 하지만 이건 사실 알기 어렵다. 그런데 왜 알아보냐면, 다른 알고리즘들의 효율을 비교할 때 도움이 되기 때문이다. 이제 차례로 보자 FIFO와 무작위 LRU가 있는데 이름과 같은 방식으로 페이지 교체하기 때문에 넘어가겠다. LRU만 간단히 적자면, 최근에 가장 안 쓰인 페이지를 교체하는 방식이다. LRU는 지역성을 잘 이용한 방식이다. 다음으로는 워크로드 별로 보게 되면  지역성이 없는 워크로드에서는 최적의 방식 말고는 다 비슷하다. 80대 20 즉 20%의 페이지들에서 80%의 참조가 발생하고 나머지 80%에 대해서 20%만 참조되는 워크로드다. 이 워크로드에서는 LRU가 비교적 높게 나타난다 FIFO와 무작위에 비해. 마지막 워크로드인 순차적 워크로드에서는 위와는 다르게 무작위가 그나마 괜찮게 나타난다. 당연히 최적은 가장 높게 나타나고. 왜냐면 LRU와 FIFO의 특성에 의해 계속 최근에 안 쓰인 걸 내보내는데 계속 새로운 것들이 오기 때문에 효율이 떨어진다. 오래된 페이지들은 정책들이 캐시에 유지하려고 선택한 페이지들보다 먼저 접근된다. 순차 반복에서는 캐시 히트율이 0%가 된다. 여기서 그럼 LRU는 비교적 괜찮은 결과를 보이는데 , 구현은 어떻게 할까 LRU의 실질적 구현은 생각보다 어렵다 왜냐하면 결국 예전 기록을 해놓아도 그걸 다 보고 비교하는데 시간이 오래 걸림. 따라서 근사하게 알고리즘을 구현하는데 환형 리스트 형식으로 페이지들을 보관한다 이때 또 use bit를 사용한다. 시계처럼 돌면서 use bit가 1이면 0으로 바꾸고 넘어가고 0이라면 그 페이지를 교체한다. 이게 비교적 LRU와 근사한 결과를 도출한다. 나머지 다른 VM 정책들로는  선반 입이라는 방식으로 미리 메모리로 읽어 들이는 방법도 있는데, 성공할 확률이 높을 때에만 해야 한다. 또 다른 방식으로 dirty bit 가 1인 수정된 페이지들을 메모리에 뒀다가 한 번에 디스크에 기록하는 클러스터링이라는 방식도 있다. 디스크는 이런 방식이 훨씬 효율적이다. 마치기 전 한 가지 기억하면 좋을 것은 쓰레싱이라는 개념인데, 실행 중인 프로세스가 요구하는 메모리가 가용 물리 메모리 크기를 초과하는 경우에 운영체제는 끊임없이 페이징을 할 수밖에 없고, 이와 같은 상황을 쓰레싱이라고 한다. 이를 해결하기 위한 방식으로 일부 프로세스를 중지시키는데, 실행되는 프로세스를 줄여서 나머지 프로세스를 모두 메모리에 탑재하여 실행하기 위해서이다. 워킹 셋이란 프로세스가 실행 중에 일정 시간 동안 사용하는 페이지들의 집합이다. 일반적으로 진입 제어라고 알려져 있다.  정리하면서, 요즘 현대 시스템들은 클락 알고리즘과 같은 알고리즘에 몇 가지 특성을 추가했는데 그중 하나가 탐색 내성이라는 것이다. LRU가 최악의 경우인 순차적 워크로드에서 보이는 행동을 방지했다. 현실적으로 과도한 페이징에 대한 최적의 해결책은 더 많은 메모리를 구입하는 것이다.

VAX/VMS 가상 메모리 시스템

vax/vms 운영체제의 가상 메모리 관리자에 대해 살피면서 정리를 해보겠다. 다음은 VAX/VMS 주소 공간이다

VMS가 페이지 테이블로 인한 메모리 압박의 정도를 경감시키기 위한 두 가지 방법이 있다. 첫째는 사용자 주소 공간을 두 개의 세그먼트로 나누어 프로세스마다 p0, p1 으로 나눠 각 영역을 위한 페이지 테이블을 갖도록 했다. 따라서 스택과 힙 사이의 사용되지 않은 주소 영역을 위한 페이지 테이블 공간이 필요 없어진다. 베이스 레지스터는 해당 세그먼트 페이지 테이블의 주소를 담고 있으면 바운드는 크기를 나타냄(페이지 테이블 항목의 수). 둘째로, 운영체제는 사용자 페이지 테이블들을 커널의 가상 메모리에 배치하여 메모리 압박을 더 줄일 수 있었다. 페이지 테이블을 할당하거나 크기를 키울 때 커널은 자신의 가상 메모리, 세그먼트 S내에 공간을 할당한다. 메모리가 고갈되면 커널은 페이지 테이블의 페이지들을 디스크로 스왑 하여 물리 메모리를 다른 용도로 사용할 수 있게 한다. 커널 가상 메모리에 페이지 테이블을 넣으면 주소 변환 과정이 훨씬 더 복잡하다. 예를 들어 P0, P1 내의 가상 주소를 변환하기 위해서는 하드웨어가 먼저 페이지 테이블에서 해당 페이지 테이블 항목을 찾아야 한다. 그러나 이 과정 중에 하드웨어는 시스템의 페이지 테이블을 먼저 검색해야 할 수도 있다. 변환이 완료되면 하드웨어는 페이지 테이블 페이지의 주소를 알게 되며, 최종적으로 원하는 메모리 접근에 대한 주소를 알게 된다. 이 구조를 보면서 알 수 있는 것들이 있다. 코드 세그먼트의 처음 페이지는 접근 불가능 페이지로 마킹되어 있으며 널 포인터 접근을 검출할 수 있게 한다. 더 중요한 사실은 커널의 가상 주소 공간이 사용자 주소 공간의 일부라는 것이다. context switch 가 발생하면 운영체제는 p0과 p1 레지스터를 다음 실행될 프로세스의 페이지 테이블을 가리키도록 변경함, 하지만 S베이스와 레지스터는 변경되지 않기 때문에 동일한 커널 구조들이 각 사용자 주소 공간에 매핑됨. 커널은 여러 주소 공간들로 매핑된다. 그러한 구조를 택하면 커널이 동작이 쉬워진다.  만약 커널이 전부 물리 메모리에만 존재한다면 페이지 테이블의 페이지들을 디스크로 스왑 하는 등의 작업은 상당히 어려웠을 것이다. 또한 커널이 자체 주소를 가지면, 사용자 프로그램들과 커널 간의 데이터 이동이 매우 복잡할 것이다. 커널은 보호된 영역이기는 하지만 응용 프로그램에게 사용되는 라이브러리처럼 보인다. 페이지 교체 방법에서 세그먼트 된 fifo 정책이 있는데 두 개의 클린 페이지 리스트와 더티 페이지 리스트를 둬서 만약에 1번 프로세스가 자신의 상주 집합 크기(RSS)를 넘기면 자신의 fifo에서 페이지가 제거돼서 클린 하면 클린 리스트로 감. 그리고 프로세스 2가 페이지를 요청하면 그걸 가져감 근데 만약에 회수되기 전에 그 페이지에 폴트가 나면 리스트에 있는 거 다시 들고 옴 , 그 외의 기법으로 demand-zeroing과 copy on write가 있음 demand zeroing은 페이지 테이블에 접근 불가능 페이지라고 표기하고 항목을 추가한다. 프로세스가 추가된 페이지를 읽거나 쓸 때 운영체제로 트랩이 발생됨, 트랩 처리하면서 demand zeroing 할 페이지라는 것을 알게 됨. 비트로 표시되어 있다. 이 시점에서 운영체제는 물리 페이지를 0으로 채우고 프로세스 주소 공간으로 매핑하는 등의 작업을 함. 만약 접근 안 하면 모든 작업 할 필요 없다. 보통 요청에서는 일단 요청 들어오면 페이지 찾아서 0으로 채우고 주소 공간에 그 페이지 매핑함. 근데 이게 안 쓰이면 낭비됨. copy on write는  한 주소 공간에서 다른 공간으로 페이지를 복사할 필요가 있을 때 운영체제는 복사 안 하고 페이지를 대상 주소 공간으로 매핑하고 페이지 테이블 양쪽을 읽기 전용으로 바뀜 만약 둘 중 한 프로세스에서 접근해서 쓰기 시도하면 그 프로세스에서 lazy 하게 할당하고 데이터 채우고 새로운 페이지 폴트 일으켜서 페이지의 주소 공간에 매핑.