- Keyword
Virtual memory management
- paging
- virtual page
- physical frame
- page table & supplementary page table
- Memory Management Unit (MMU)
- Translation Lookaside Buffer (TLB)
Page type
- Uninitialized page
- Lazy initialization
- Anonymous page
- stack growth
- file-backed page
- mmap syscall
Swap in/out
- page replacement policy
- swap disk
Copy on Write (COW)
- Background
Memory Terminology
: 메모리 용어
메모리와 스토리지에 대한 몇 가지 용어를 제시하는 것으로 시작합니다. 이러한 용어 중 일부는 프로젝트2( 가상 메모리 레이아웃 참조)로부터 봤을거라 익숙해야 하지만 대부분은 새로운 것입니다.
Pages
페이지
가상 페이지라고도 하는 페이지는 길이가 4,096바이트( 페이지 크기 ) 인 가상 메모리의 연속 영역입니다 . 페이지는 페이지 정렬 되어야 합니다 . 즉, 페이지 크기로 균등하게 나눌 수 있는 가상 주소에서 시작 해야 합니다 . 따라서 64비트 가상 주소의 마지막 12비트는 페이지 오프셋 (또는 오프셋 )입니다. 상위 비트는 곧 도입될 페이지 테이블의 인덱스를 나타내는 데 사용됩니다. 64비트 시스템에서는 가상 주소를 아래 그림처럼 만드는 4레벨 페이지 테이블을 사용합니다.
각 프로세스에는 가상 주소 KERN_BASE(0x8004000000) 아래에 있는(작은) 페이지인 독립적인 사용자(가상) 페이지 집합이 있습니다 . 반면에 커널(가상) 페이지 세트 는 전역적이므로 실행 중인 스레드나 프로세스에 관계없이 동일한 위치에 유지됩니다. 커널은 사용자 페이지와 커널 페이지 모두에 액세스할 수 있지만 사용자 프로세스는 자신의 사용자 페이지에만 액세스할 수 있습니다. 자세한 내용은 가상 메모리 레이아웃 을 참조하십시오.
Pintos는 가상 주소 작업을 위한 몇 가지 유용한 기능을 제공합니다. 자세한 내용은 가상 주소 섹션 을 참조하십시오.
Frames
프레임
때로는 물리적 프레임 또는 페이지 프레임이라고하는 프레임은 물리적 메모리의 연속 영역입니다. 페이지와 마찬가지로 프레임도 페이지 크기와 페이지 정렬이 필요합니다. 따라서 64 비트 물리 주소는 다음과 같이 프레임 번호와 프레임 오프셋 (또는 오프셋)으로 나눌 수 있습니다.
12 11 0
+-----------------------+-----------+
| Frame Number | Offset |
+-----------------------+-----------+
Physical Address
x86-64는 물리적 주소에서 메모리에 직접 액세스하는 방법을 제공하지 않습니다. Pintos는 커널 가상 메모리를 물리적 메모리에 직접 매핑하여 이 문제를 해결합니다.
커널 가상 메모리의 첫 번째 페이지는 물리적 메모리의 첫 번째 프레임에 매핑되고, 두 번째 페이지는 두 번째 프레임에 매핑되는 식입니다. 따라서 커널 가상 메모리를 통해 프레임에 액세스할 수 있습니다.
Pintos는 물리적 주소와 커널 가상 주소 간의 변환을 위한 기능을 제공합니다. 자세한 내용은 가상 주소 를 참조하십시오.
Page Table
페이지 테이블
페이지 테이블(page table)은 CPU가 가상 주소를 실제 물리 주소로 변환하기 위해 사용하는 데이터 구조이다. 페이지 테이블 형식은 x86-64 아키텍처에 의해 결정됩니다. 핀토스는 페이지 테이블 관리 코드를 threads/mmu.c 에서 제공합니다.
아래 다이어그램은 페이지와 프레임 간의 관계를 보여줍니다. 왼쪽의 가상 주소는 페이지 번호와 오프셋으로 구성됩니다. 페이지 테이블은 페이지 번호를 프레임 번호로 변환하고, 오른쪽에 있는 물리적 주소를 얻기 위해 수정되지 않은 오프셋과 결합됩니다.
+----------+
.--------------->|Page Table|-----------.
/ +----------+ |
| 12 11 0 V 12 11 0
+---------+----+ +---------+----+
| Page Nr | Ofs| |Frame Nr | Ofs|
+---------+----+ +---------+----+
Virt Addr | Phys Addr ^
\_______________________________________/
Swap Slots
슬롯 교체
스왑 슬롯은 스왑 파티션에 있는 디스크 공간의 페이지 크기 영역입니다. 슬롯의 배치를 지시하는 하드웨어 제한은 프레임보다 유연하지만 스왑 슬롯은 단점이 없기 때문에 페이지 정렬을 해야 한다.
- Resource Management Overview
자원 관리 개요
다음 데이터 구조를 설계/구현해야 합니다.
Supplemental page table(추가 페이지 테이블)
페이지 테이블을 보완하여 페이지 폴트 처리를 활성화합니다. 아래의 추가 페이지 테이블 관리를 참조하십시오.
Frame table(프레임 테이블)
물리적 프레임의 축출 정책을 효율적으로 구현할 수 있습니다. 아래의 프레임 테이블 관리를 참조하십시오. → 스왑 영역으로 아웃 시키는 것과 관련된 듯
Swap table(스왑 테이블)
스왑 슬롯의 사용량을 추적합니다. 아래의 스왑 테이블 관리를 참조하십시오.
완전히 다른 세 가지 데이터 구조를 구현할 필요는 없습니다. 관련 리소스를 전체적으로 또는 부분적으로 통합된 데이터 구조로 병합하는 것이 편리할 수 있습니다. → local? global? or malloc..
각 데이터 구조에 대해 각 요소에 포함되어야 하는 정보를 결정해야 합니다. 또한 데이터 구조의 범위(로컬(프로세스별) 또는 전역(전체 시스템에 적용))와 해당 범위 내에서 필요한 인스턴스 수를 결정해야 합니다.
디자인을 단순화하기 위해 이러한 데이터 구조를 페이징할 수 없는 메모리(예: calloc 또는 malloc에 의해 할당된 메모리)에 저장할 수 있습니다 . 즉, 포인터 사이의 포인터가 유효한 상태로 유지된다는 것을 확신할 수 있습니다.
Choices of implementation (Performance perspective)
구현 선택(성능 관점)
구현을 위한 가능한 선택에는 배열, 목록, 비트맵 및 해시 테이블이 포함됩니다. 배열은 가장 단순한 접근 방식인 경우가 많지만 배열이 희박하게 채워지면 메모리가 낭비됩니다. 목록도 간단하지만 특정 위치를 찾기 위해 긴 목록을 탐색하는 것은 시간을 낭비합니다. 배열과 목록 모두 크기를 조정할 수 있지만 목록은 중간에 삽입 및 삭제를 보다 효율적으로 지원합니다.
핀토스는 lib/kernel/bitmap.c의 비트맵 데이터 구조를 포함하며 include/lib/kernel/bitmap.h를 포함한다. 비트맵(bitmap)은 비트의 배열로, 각각 참일 수도 있고 거짓일 수도 있다. 비트맵은 일반적으로 (동일한) 리소스 집합에서 사용을 추적하는 데 사용된다. 리소스 n이 사용 중이면 비트맵의 비트 n은 true다. 핀토스 비트맵은 크기가 고정되어 있지만, 크기 조정을 지원하기 위해 구현을 확장할 수 있다.
Pintos는 또한 해시 테이블 데이터 구조를 포함합니다 (해시 테이블 참조). 핀토스 해시 테이블은 광범위한 테이블 크기에 걸쳐 삽입과 삭제를 효율적으로 지원한다.
더 복잡한 데이터 구조가 더 나은 성능이나 기타 이점을 제공할 수 있지만 불필요하게 구현을 복잡하게 만들 수도 있습니다. 따라서 설계의 일부로 고급 데이터 구조(예: 균형 이진 트리)를 구현하지 않는 것이 좋습니다.
- Managing the Supplemental Page Table (구현 관련 내용)
추가 페이지 테이블 관리
supplemental page table은 각 페이지에 대한 추가 데이터로 페이지 표를 보완합니다. 페이지 테이블의 형식에 따른 제약 때문에 필요합니다. 이러한 데이터 구조를 종종 페이지 테이블이라고도 합니다. 혼동을 줄이기 위해 “Supplemental”이라는 단어를 추가합니다. p.392
supplemental page table은 적어도 두 가지 목적으로 사용됩니다. 가장 중요한 것은 페이지 폴트시 커널이 supplemental page table에서 page fault가 발생한 가상 페이지를 검색하여 어떤 데이터가 있어야하는지를 찾는 것입니다. 둘째, 프로세스가 종료 될 때 커널은 supplemental page table을 참조하여 어떤 리소스를 해제할 것인지 결정합니다.
- Organization of Supplemental Page Table
원하는 대로 추가 페이지 테이블을 구성할 수 있습니다. 조직에는 세그먼트 또는 페이지 측면에서 적어도 두 가지 기본적인 접근 방식이 있습니다. 여기서 세그먼트는 연속된 페이지 그룹, 즉 실행 파일 또는 메모리 매핑 파일을 포함하는 메모리 영역을 나타냅니다.
선택적으로, 페이지 표 자체를 사용하여 추가 페이지 표의 구성원을 추적할 수 있습니다. 그렇게 하려면 핀토스 페이지 테이블 구현을 threads/mmu.c에서 수정해야 합니다. 우리는 이 접근 방식을 advanced 학생들에게만 추천합니다.
- Handling page fault
페이지 폴트 처리
supplemental page table의 가장 중요한 사용자는 page fault handler입니다. 프로젝트 2에서 페이지 폴트 항상 커널이나 사용자 프로그램의 버그를 나타냅니다. 프로젝트 3에서는 더 이상 사실이 아닙니다.
페이지 장애는 페이지를 파일 또는 스왑 슬롯에서 가져와야 함을 나타낼 수 있습니다. 이러한 경우를 처리하려면 더 정교한 페이지 오류 처리기를 구현해야 합니다.
userprog/exception.c의 page_fault()인 page fault handler는 vm/vm.c의 vm_try_handle_fault()를 호출합니다.
page fault handler는 대략 다음 작업을 수행해야 합니다.
-
supplemental page table에서 faulted가 발생한 페이지를 찾습니다. 메모리 참조가 유효한 경우 supplemental page table entry을 사용하여 파일 시스템이나 스왑 슬롯에 있거나 단순히 모두 0인 페이지일 수 있는 페이지에 들어가는 데이터를 찾습니다.
sharing을 구현하는 경우(즉, Copy-on-Write), 페이지의 데이터는 이미 페이지 프레임에 있을 수 있지만 페이지 테이블에는 없을 수 있습니다.
supplemental page table이 사용자 프로세스가 액세스하려는 주소의 데이터를 기대해서는 안된다는 것을 표시하거나(있을거라고 기대하지 말라는건가), 페이지가 커널 가상 메모리 내에 있거나, 액세스가 읽기 전용 페이지에 쓰려는 시도인 경우, 액세스가 유효하지 않습니다.
유효하지 않은 액세스는 프로세스를 종료하고 모든 리소스를 해제합니다.
-
페이지를 저장할 프레임을 얻습니다. sharing을 구현하는 경우 필요한 데이터가 이미 프레임에 있을 수 있으며 이 경우 해당 프레임을 찾을 수 있어야 합니다.
-
파일 시스템에서 데이터를 읽거나 스왑하거나 0으로 만드는 등의 방법으로 데이터를 프레임으로 가져옵니다. sharing을 구현하는 경우 필요한 페이지가 이미 프레임에 있을 수 있으며 이 경우 이 단계에서 조치가 필요하지 않습니다.
-
결함(faulting)이 있는 virtual address에 대한 페이지 테이블 항목이 physical page를 가리키도록 합니다.
threads/mmu.c의 기능을 사용할 수 있습니다.
- Managing the Frame Table
프레임 테이블 관리
프레임 테이블은 각 프레임에 대해 하나의 항목을 포함합니다. 프레임 테이블의 각 항목에는 현재 점유하고 있는 페이지에 대한 포인터와 사용자가 선택한 기타 데이터가 포함되어 있습니다. 프레임 테이블을 사용하면 사용 가능한 프레임이 없을 때 축출할 페이지를 선택하여 Pintos가 축출 정책을 효율적으로 구현할 수 있습니다.
사용자 페이지에 사용되는 프레임은 palloc_get_page(PAL_USER)를 호출하여 "user pool"에서 가져와야 합니다. 일부 테스트 케이스가 예기치 않게 실패할 수 있는 "kernel pool"에서 할당하지 않으려면 PAL_USER를 사용해야 합니다. palloc.c를 프레임 테이블 구현의 일부로 수정하는 경우 두 풀의 구분을 유지해야 합니다.
프레임 테이블에서 가장 중요한 작업은 사용하지 않는 프레임을 얻는 것입니다. 이것은 프레임이 비어 있을 때 쉽습니다. 비어 있는 것이 없으면 프레임에서 일부 페이지를 제거하여 프레임을 비워야 합니다.
스왑 슬롯을 할당하지 않고 프레임을 제거할 수 없지만 스왑이 가득 차면 커널을 패닉 상태로 만듭니다. 실제 OS는 이러한 상황을 복구하거나 방지하기 위해 광범위한 정책을 적용하지만 이러한 정책은 이 프로젝트의 범위를 벗어납니다.
퇴거 절차(eviction comprises)는 대략 다음 단계로 구성됩니다.
- 페이지 교체 알고리즘을 사용하여 제거할 프레임을 선택합니다. 아래에 설명된 페이지 테이블의 "액세스된(accessed)" 및 "더티한(dirty)" 비트가 유용할 것입니다.
- dirty bit : 캐시 내용에 변경이 있었음을 기록한 플래그 비트; 컴퓨터 메모리 블록과 연관되며 해당 메모리 블록이 수정되었는지 여부를 나타낸다. - 프레임을 참조하는 페이지 테이블에서 프레임에 대한 참조를 제거합니다. sharing을 구현하지 않은 경우, 주어진 시간에 단일 페이지만 프레임을 참조해야 합니다.
- 필요한 경우 페이지를 파일 시스템이나 스왑에 쓰십시오. 그런 다음 축출된 프레임(evicted frame)을 사용하여 다른 페이지를 저장할 수 있습니다.
- Accessed and Dirty Bits
액세스 및 더티 비트
x86-64 하드웨어는 각 페이지에 대한 PTE(페이지 테이블 항목(entry))의 비트 쌍을 통해 페이지 교체 알고리즘을 구현하는 데 약간의 지원을 제공합니다. 페이지에 대한 읽기 또는 쓰기에서 CPU는 액세스된 비트를 페이지의 PTE에서 1로 설정하고 모든 쓰기에서 CPU는 더티 비트 를 1로 설정합니다 . CPU는 이 비트를 0으로 재설정하지 않지만 OS는 그렇게 할 수 있습니다.
aliases(별칭), 즉 동일한 프레임을 참조하는 두 개(또는 그 이상)의 페이지를 알고 있어야 합니다. 앨리어싱된 프레임에 액세스하면 액세스된 비트와 더티 비트가 하나의 페이지 테이블 항목(액세스에 사용되는 페이지에 대한 항목)에서만 업데이트됩니다. 다른 별칭에 대한 액세스 및 더티 비트는 업데이트되지 않습니다.
Pintos에서 모든 사용자 가상 페이지는 커널 가상 페이지에 별칭이 지정됩니다(aliased). 이러한 별칭은 어떻게든 관리해야 합니다. 예를 들어, 코드는 두 주소에 대해 액세스된 비트와 더티 비트를 확인하고 업데이트할 수 있습니다. 또는 커널은 사용자 가상 주소를 통해서만 사용자 데이터에 액세스하여 문제를 피할 수 있습니다.
다른 별칭은 공유를 구현하거나 코드에 버그가 있는 경우에만 발생해야 합니다.
액세스된 비트 및 더티 비트 와 함께 작동하는 기능에 대한 자세한 내용은 섹션 페이지 테이블 액세스 및 더티 비트 를 참조하십시오.
- Managing the Swap Table
스왑 테이블 관리
스왑 테이블은 사용 중인 슬롯과 사용 가능한 스왑 슬롯을 추적합니다. 프레임에서 스왑 파티션으로 페이지를 제거하기 위해 사용하지 않는 스왑 슬롯을 선택할 수 있어야 합니다. 페이지를 다시 읽거나 페이지가 교환된 프로세스가 종료될 때 교환 슬롯을 해제할 수 있어야 합니다.
vm/build 디렉토리에서 pintos-mkdisk swap.dsk --swap-size=n 명령을 사용하여 n-MB 스왑 파티션을 포함하는 swap.dsk라는 디스크를 만듭니다. 이후 핀토스를 실행하면 swap.dsk가 자동으로 추가 디스크로 첨부됩니다. 또는 핀토스에게 --swap-size=n으로 단일 실행을 위해 임시 n-MB 스왑 디스크를 사용하라고 지시할 수 있습니다.
스왑 슬롯은 퇴거에 실제로 필요한 경우에만 지연 할당(allocated lazily)되어야 합니다(진짜 필요할 때만 써라). 실행 파일에서 데이터 페이지를 읽고 프로세스 시작 시 즉시 스왑에 쓰는 것은 lazy하지 않습니다. 스왑 슬롯은 특정 페이지를 저장하기 위해 예약되어서는 안 됩니다.
Free a swap slot when its contents are read back into a frame.
스왑 슬롯의 내용을 프레임으로 다시 읽을 때 슬롯을 해제합니다.
- Managing Memory Mapped Files
메모리 매핑 파일 관리
파일 시스템은 read 및 write 시스템 호출을 통해 가장 일반적으로 액세스(접근)된다. 보조 인터페이스(secondary interface)는 mmap 시스템 호출을 사용하여 파일을 가상 페이지로 매핑하는 것이다. 그런 다음 프로그램은 파일 데이터에 직접 메모리 명령을 사용할 수 있습니다.
foo 파일의 길이가 0x1000바이트(4kB 또는 한 페이지)라고 가정합니다. 주소 0x5000부터 시작하는 메모리에 foo를 매핑하면 위치 0x5000. .0x5fff에 대한 모든 메모리 액세스가 foo의 해당 바이트에 액세스합니다.
다음은 mmap을 사용하여 파일을 콘솔에 인쇄하는 프로그램입니다. 명령 줄에 지정된 파일을 열고 가상 주소 0x1000000에 매핑하고 매핑 된 데이터를 콘솔 (fd 1)에 쓰고 파일을 매핑 해제합니다.
#include <stdio.h>
#include <syscall.h>
int main (int argc UNUSED, char *argv[])
{
void *data = (void *) 0x10000000; /* Address at which to map. */
int fd = open (argv[1]); /* Open file. */
void *map = mmap (data, filesize (fd), 0, fd, 0); /* Map file. */
write (1, data, filesize (fd)); /* Write file to console. */
munmap (map); /* Unmap file (optional). */
return 0;
}제출물은 메모리 매핑된 파일이 사용하는 메모리를 추적할 수 있어야 합니다. 이는 매핑된 영역에서 페이지 오류를 적절하게 처리하고 매핑된 파일이 프로세스 내의 다른 세그먼트와 겹치지 않도록 하는 데 필요합니다.
💡 정리
✔️ 페이지는 길이가 4,096바이트( 페이지 크기 ) 인 가상 메모리의 연속 영역
프레임은 물리적 메모리의 연속 영역
Pintos는 물리적 주소와 커널 가상 주소 간의 변환을 위한 기능을 제공
페이지 테이블(page table)은 CPU가 가상 주소를 실제 물리 주소로 변환하기 위해 사용하는 데이터 구조
스왑 슬롯은 스왑 파티션에 있는 디스크 공간의 페이지 크기 영역
Resource Management Overview 자원 관리 개요
다음 데이터 구조를 설계/구현
1. Supplemental page table(추가 **페이지 **테이블) : 페이지 테이블을 보완하여 페이지 폴트 처리를 활성화
2. Frame table(프레임 **테이블) : 물리적 프레임의 축출 정책을 효율적으로 구현
3. Swap table(스왑 **테이블) : 스왑 슬롯의 사용량을 추적
Managing the Supplemental Page Table 추가 페이지 테이블 관리
SPT의 목적 2가지
- 페이지폴트시 커널은 supplemental page table에서 page fault가 발생한 가상 페이지를 검색하여 어떤 데이터가 있어야하는지를 찾음
- 프로세스가 종료 될 때 커널은 supplemental page table을 참조하여 어떤 리소스를 해제할 것인지 결정
세그먼트는 연속된 페이지 그룹, 즉 실행 파일 또는 메모리 매핑 파일을 포함하는 메모리 영역. Paging / Segmentation
Handling page fault 페이지 폴트 처리
page fault handler는 대략 다음 작업을 수행해야 합니다.
- supplemental page table에서 faulted가 발생한 페이지를 찾습니다. 메모리 참조가 유효한 경우 supplemental page table entry을 사용하여 파일 시스템이나 스왑 슬롯에 있거나 단순히 모두 0인 페이지일 수 있는 페이지에 들어가는 데이터를 찾습니다.
sharing을 구현하는 경우(즉, Copy-on-Write), 페이지의 데이터는 이미 페이지 프레임에 있을 수 있지만 페이지 테이블에는 없을 수 있습니다.
supplemental page table이 사용자 프로세스가 액세스하려는 주소의 데이터를 기대해서는 안된다는 것을 표시하거나(있을거라고 기대하지 말라는건가), 페이지가 커널 가상 메모리 내에 있거나, 액세스가 읽기 전용 페이지에 쓰려는 시도인 경우, 액세스가 유효하지 않습니다.
유효하지 않은 액세스는 프로세스를 종료하고 모든 리소스를 해제합니다.- 페이지를 저장할 프레임을 얻습니다. sharing을 구현하는 경우 필요한 데이터가 이미 프레임에 있을 수 있으며 이 경우 해당 프레임을 찾을 수 있어야 합니다.
- 파일 시스템에서 데이터를 읽거나 스왑하거나 0으로 만드는 등의 방법으로 데이터를 프레임으로 가져옵니다. sharing을 구현하는 경우 필요한 페이지가 이미 프레임에 있을 수 있으며 이 경우 이 단계에서 조치가 필요하지 않습니다.
- 결함(faulting)이 있는 virtual address에 대한 페이지 테이블 항목이 physical page를 가리키도록 합니다. threads/mmu.c의 기능을 사용할 수 있습니다 .
Managing the Frame Table 프레임 테이블 관리
프레임 테이블은 각 프레임에 대해 하나의 항목을 포함
각 항목에 : 현재 점유하고 있는 페이지에 대한 포인터 + 사용자가 선택한 기타 데이터가 포함
사용자 페이지에 사용되는 프레임은 palloc_get_page(PAL_USER)를 호출하여 "user pool"에서 가져와야 함
가장 중요한 작업은 사용하지 않는 프레임을 얻는 것. 비어 있는 것이 없으면 프레임에서 일부 페이지를 제거하여 프레임을 비워야 함.
스왑이 가득 차면 커널을 패닉 상태로 만듦
퇴거 절차(eviction comprises) - (프로세스의 방출)
- 페이지 교체 알고리즘을 사용하여 제거할 프레임을 선택합니다.
페이지 테이블의 "액세스된(accessed)" 및 "더티한(dirty)" 비트가 유용할 것입니다.
- dirty bit : 캐시 내용에 변경이 있었음을 기록한 플래그 비트; 컴퓨터 메모리 블록과 연관되며 해당 메모리 블록이 수정되었는지 여부를 나타낸다. - 프레임을 참조하는 페이지 테이블에서 프레임에 대한 참조를 제거합니다. sharing을 구현하지 않은 경우, 주어진 시간에 단일 페이지만 프레임을 참조해야 합니다.
- 필요한 경우 페이지를 파일 시스템이나 스왑에 쓰십시오. 그런 다음 축출된 프레임(evicted frame)을 사용하여 다른 페이지를 저장할 수 있습니다.
Managing the Swap Table 스왑 **테이블 **관리
스왑 테이블은 사용 중인 슬롯과 사용 가능한 스왑 슬롯을 추적
페이지를 다시 읽거나 페이지가 스왑된 프로세스가 종료될 때 스왑 슬롯을 해제
Managing Memory Mapped Files 메모리 **매핑 **파일 ****관리
보조 인터페이스(secondary interface)는 mmap 시스템 호출을 사용하여 파일을 가상 페이지로 매핑
