PintOS - WIL 10-11주차

Hyeongjin Song·2023년 12월 15일
정글

jungle

목록 보기
9/12

공부 키워드

Virtual Memory

Page Table

Translation Lookaside Buffer (TLB)

Page Fault

Lazy Loading

Page Replacement Policy

Anonymous page

Swap Disk

File-backed Page

Direct Memory Access

Q. mmap 은 디스크의 내용을 물리 메모리로 올리는거야? 아니면 가상 메모리로 올리는거야?
A. mmap은 주로 디스크의 파일을 가상 메모리로 매핑하는 데 사용되며, 이로 인해 해당 파일의 내용이 가상 메모리에 로드됩니다. 따라서 mmap을 사용하면 디스크의 파일을 가상 메모리 주소 공간에 올릴 수 있습니다.
가상 메모리 주소 공간은 실제 물리 메모리와 연결되어 있으며, 운영 체제의 메모리 관리 기능은 가상 메모리 주소 공간을 효과적으로 물리 메모리와 관리합니다. 이러한 방식으로 mmap을 사용하면 디스크의 파일 내용을 가상 메모리에 로드하고 해당 파일을 가상 메모리 주소로 접근할 수 있게 됩니다.
그러나 mmap을 사용하는 경우 모든 파일 내용이 한 번에 물리 메모리에 로드되는 것은 아닙니다. 대신, 페이지 단위로 데이터를 로드하고 필요한 페이지만 실제 물리 메모리에 올립니다. 이렇게 함으로써 메모리 사용을 최적화하고 파일의 크기와 상관없이 대용량 파일을 처리할 수 있습니다.

Q. mmap함수 구현 전(다시 말해, 지금까지)까지는 모든 파일을 메모리에 올린 것인가?
A. YES

Q. virtual page와 page frame 모두 20bit의 page number, 그리고 12bit의 offset으로 동일하다. 그렇다면, 프로세스마다 존재하는 virtual space는 physical space와 동일한 것인가?
A. YES

Q. 디스크 내에서 file-backed page가 존재하는 곳과 swap-out된 page가 존재하는 곳은 같은 곳인가?
A. NO

Q. hash table에서 각각의 bucket에 vm_entry를 넣는 기준은 무엇인가? 즉, 해시 함수는 무엇인가?
A. 아래에서 자세히 다룬다. FNV 해싱 기법을 이용한다.

1. Anonymous Page

modify

  1. vm/vm.c
  2. vm/uninit.c
  3. vm/file.c
  4. vm/anon.c -> for anon page

TO DO

  1. page management

  2. frame maangement

    vm/vm.c내의 vm_get_frame, vm_claim_page, vm_do_claim_page 함수를 구현

  1. thread->spt
  2. vm/file.c
  3. vm/vm.c

Virtual memory

설계

프로세스는 독립된 갓아 메모리 공간을 가짐 - 커널 영역 + 유저 영역 : 그리고 각각은 커널 페이지, 유저 페이지로 표현한다.

두 영역의 경계는 KERN_BASE라는 상수로 0x8004000000이다.
즉, 가상 메모리의 커널 페이지 영역은 0x8004000000위에 존재한다.
한편, USER_STACK 상수는 유저 페이지 영역 중 스택 영역이 시작되는 주소. 스택이므로 아래 방향으로 커진다.

핀토스는 가상 메모리의 커널 페이지 영역이 물리 메모리에 1:1로 매핑된다. 즉, 가상 메모리 영역의 커널 페이지 영역이 곧 물리 메모리인 것이다. 따라서 KERN_BASE가 물리 메모리 주소 0에 매핑된다.

핀토스는 단일 프로세스 운영체제이기 때문에 가상 메모리의 커널 영역이 물리 메모리에 매핑되어도 문제가 되지 않는다. 현재 프로세스가 전체 시스템의 관리자가 되어 리소스에 대한 독점권을 가지기 때문이다. 하지만, 다중 프로세스 운영 체제에서는 가상 메모리 매핑과 관련된 별도의 관리 및 보호 메커니즘이 필요하다.

할당

핀토스는 2개의 할당 방식을 제공한다. 페이지 단위로 메모리를 할당받는 palloc과, 원하는 크기 만큼의 메모리를 할당받는 malloc이다.

  1. palloc
  • palloc_get_page : 1개의 페이지 할당
  • palloc_get_multiple : 여러 개의 페이지 할당

두 함수 모두 flag를 인자로 받아 할당받을 메모리가 속할 영역(PAL_USER), 초기화 여부(PAL_ZERO) 그리고 할당 시 오류가 발생하면 패닉 상태로 전환하는 지(PAL_ASSERT)에 대한 조건들을 추가로 전달할 수 있다.
PAL_USER는 가상 메모리의 커널 페이지 영역(=물리메모리)에서 유저 풀에 해당하는 영역의 메모리를 할당받을 수 있다. 만약 PAL_USER를 전달하지 않으면 커널 페이지 영역에서 커널 풀에 해당하는 영역의 메모리를 할당받을 수 있다.

여기서 등장하는 유저 풀과 커널 풀에 대해 이해하기 위해서는 유저 모드와 커널 모드에 대한 지식이 필요하다. 프로세스가 유저모드로 실행되고 있을 때에는 가상 메모리의 유저 페이지 영역의 메모리에만 접근이 가능하고, 커널 모드에서는 커널 풀에 직접 접근하거나 커널 풀에서 메모리를 할당받을 수 있다.

  1. malloc
  • malloc

처음에는 desc배열을 순회하면서 인자로 들어온 size만큼의 적당한 블록을 찾아 할당한다. 하지만 적합한 크기의 블록이 없는 경우, 페이지 단위로 할당한다.

결론적으로 핀토스는 힙 영역이 존재하지 않기 때문에 정적으로 할당된 메모리 영역만을 사용한다. 즉, 핀토스는 프로세스에 필요한 모든 메모리를 미리 할당(프로그램이 로드될 때)하여 사용하고, 이 작업은 프로세스가 실행될 때 load() -> load_segment()를 통해서 일어난다.

Project 3에서는 페이지 테이블을 보충하는 spt를 만들어서 새로운 방식으로 페이지 폴트를 처리하고 페이지 별로 Type을 두어 실행하는 프로그램의 세그먼트 페이지들을 익명 페이지로 설정해놓고 lazy loading을 시켜주게끔 vm 로직을 새롭게 구현했다.

Supplemental Page Table

프로세스마다 해시 테이블 구조의 spt를 만들고, 이를 이용하여 페이지 폴트를 처리해야 한다.
bucket들의 list = buckets가 존재하고 각각의 bucket에는 page가 담긴다.
모든 페이지는 vm_alloc_page_with_initializer()에서 생성된다.

Anonymous Page & Lazy Loading

vm 구현 전까지 핀토스는 어떤 프로그램의 프로세스가 생성될 때 해당 프로그램에 대한 모든 페이지를 읽고 한번에 페이지를 할당한다. 따라서, load_segment()가 끝나면 해당 프로그램에 대한 모든 페이지가 물리 메모리에 올라가고 가상 메모리에도 매핑된다고 볼 수 있다. 상당히 비효율적인 방식이다. 사용 여부가 불확실한 페이지들을 미리 물리 메모리에 올려놓을 필요는 없기에, Lazy Loading이 필요하다.

모든 페이지를 spt에 등록해두고 만약 page fault가 발생하면 그 때 spt에서 원하는 페이지를 검색해서 해당 페이지에 대한 정보를 바탕으로 물리 메모리에 올린다.

fork?

fork() 호출 시 부모의 spt 역시 넘겨주어야 한다. 따라서 supplemental_page_table_copy함수를 구현해야 한다.

Stack Growth

vm 구현 전에는 유저 스택 영역은 USER_STACK부터 시작해서 최대 1페이지(stack bottom = 0x4747f000)만 할당되어 활용되었다. 즉, 프로그램이 사용하는 메모리 공간 중 스택 영역은 딱 한페이지만 사용이 가능했다.

이제 유저 스택 영역을 최대 1MB로 설정하여 page fault 발생 시 해당 주소가 유저 스택 영역 내의 주소일 경우 유저 스택 영역을 해당 주소까지 확장해주는 stack growth를 구현.

최대 1MB의 스택 영역은 한 페이지가 4KB인 핀토스에서 최대 256개의 스택 페이지를 생성할 수 있다.

void *stack_bottom =
     (void *) (((uint8_t *) USER_STACK) - (PGSIZE * STACK_MAX_PAGES))

위 주소와의 비교를 통해 vm_try_handle_fault에서 page fault가 발생한 주소가 스택 영역인지 아닌지 판단할 수 있다.
그리고 그 주소가 rsp - (1 << 3)이라면 stack_growth가 필요한 주소라는 뜻이다.

  • user program이 실행되고, argument passing 작업을 마치고 나면 rsp는 현재 스택 페이지 내의 사용이 가능한 영역의 최상단을 가리키고 있을 것이다.
  • 이후 유저 프로그램이 스택 영역에 데이터를 PUSH 하기도 하고 POP 하기도 할 것이다. (push와 pop은 어셈블 코드이고 각각 -8byte, +8byte 씩 rsp를 움직인다. 이 때 중요한 것은 두 명령어는 일단 데이터를 rsp에서 이동한 주소에 적재한 뒤에 rsp를 갱신한다.)
  • stack growth가 필요한 page fault가 발생했다는 것은? 현재 할당되어있는 스택 페이지가 꽉 차있는 상태에서 push 명령어를 사용한 것이라는 것을 유추해볼 수 있다. 즉, rsp - (1 <<3)을 참조하려다가 page fault가 발생한 것.
  • 그러므로 stack growth가 필요한 page fault인 경우에는 addr은 무조건 rsp - (1<<3)일 것이고 이 때 pg_round_down(addr) 부터 현재 스택의 최하단까지 페이지를 만들어서 쌓아올리는 작업을 해주면 된다.

mmap, Munmap

  1. mmap
    fd로 지정된 파일에서 offset에 해당하는 물리 주소에서 시작해서 length바이트 만큼을 가상 주소 addr로 대응시킨다.
  1. munmap
    mmap으로 할당한 메모리 영역을 해제한다. addr은 mmap함수에 의해 반환된 주소여야 한다.

mmap, munmap 시스템 콜

  • 메모리 매핑 - 파일을 쉽게 읽고 쓸 수 있고, 파일을 메모리 처럼 다룰 수 있게 된다.
  • 공유 메모리 - mmap함수를 사용해서 여러 프로세스에서 동시에 같은 파일을 매핑하여 해당 메모리 영역을 공유할 수 있다. 이는 프로세스 간 통신이나 병렬 처리 등에서 유용하게 사용될 수 있다.
  • 파일 I/O 최적화 - 파일을 메모리에 매핑해서 직접 메모리에서 파일을 읽고 쓸 수 있으므로 파일 작업이 간소화된다.

Swap In / Swap Out

가상 메모리 시스템에서 물리 메모리 상의 페이지 프레임을 할당받고자 할 때, 물리 메모리 공간이 부족하다면 물리 메모리 상에 존재하는 페이지 프레임 중 하나를 내려주고 새로운 페이지 프레임을 할당시켜주면 될 것이다. 이러한 동작을 페이지 교체 기법이라고 한다.

swap out은 보조 디스크의 swap area에 페이지 프레임을 백업하는 것을 의미한다. 후에 해당 페이지 프레임이 필요하다는 요청을 받게되면 swap area에서 다시 물리 메모리로 올라가게 된다. 이를 swap in이라 한다.

pintos의 페이지 타입에는 VM_ANON과 VM_FILE이 있다.

VM_FILE은 swap-out이 될 때 굳이 swap-area로 내려갈 필요가 없다. 파일은 이미 디스크에 존재하기 때문이다. 그렇기에 VM_FILE의 swap-out의 경우에는 파일을 overwrite 해주는 식으로 수행한다. (물론 더티 비트가 설정되어있을 때만 수정)

VM_ANON 타입의 페이지는 swap-out이 될 때 swap area로 백업을 해주어야 한다. pintos 내에서 보조 메모리를 추상화한 disk라는 것이 존재하며, 이를 이용해서 swap area에 접근한다.

vm_anon_init()

disk_get() 함수를 이용해서 주어진 크기 만큼의 swap area를 할당받는다. 그리고 swap-out되어 있는 페이지들을 관리해주기 위해 swap_table 이라는 bitmap 타입 변수를 선언한다.

disk는 sector 단위로 관리된다. 핀토스 내에서 disk의 한 sector는 512byte 로 설정된다. 한 페이지 프레임은 4096byte이기 때문에 8개의 sector가 필요하다.

size_t swap_size =  
    disk_size(swap_disk) / SECTORS_PER_PAGE; // (size/page)*sector

architecture

1. 데이터 기반 해싱 : 페이지를 저장할 버킷을 고르는 해싱 방법

static struct list *
find_bucket(struct hash *h, struct hash_elem *e)
{
	size_t bucket_idx = h->hash(e, h->aux) & (h->bucket_cnt - 1);
	return &h->buckets[bucket_idx];
}

각 페이지가 들어갈 버킷을 찾는 함수이다.

이 때, h->hash에 들어갈 함수는 아래와 같다.

unsigned
page_hash(const struct hash_elem *p_, void *aux)
{
	const struct page *page = hash_entry(p_, struct page, hash_elem);
	return hash_bytes(&page->va, sizeof page->va);
}

hash_bytes라는 함수를 호출하여 리턴한다.

uint64_t
hash_bytes(const void *buf_, size_t size)
{
	/* Fowler-Noll-Vo 32-bit hash, for bytes. */
	const unsigned char *buf = buf_;
	uint64_t hash;

	ASSERT(buf != NULL);

	hash = FNV_64_BASIS;
	while (size-- > 0)
		hash = (hash * FNV_64_PRIME) ^ *buf++;

	return hash;
}

Fowler–Noll–Vo hash function : FNV 해싱기법이라고 하는 방법을 사용

  1. FNV_64_BASIS를 초기 해시값으로 설정
  2. buf_가 가리키는 메모리 주소에서 시작하는 크기가 size인 바이트 시퀀스를 해싱.
  3. const unsigned char *buf = buf_;를 통해 입력 데이터를 unsigned char형으로 변환.
  4. while (size-- > 0) 루프를 통해 각 바이트를 순회하면서 다음 작업을 수행:
    -> hash = (hash * FNV_64_PRIME) ^ *buf++;를 통해 현재 해시값에 FNV_64_PRIME을 곱하고, 현재 바이트와 XOR 연산을 수행. XOR 연산은 이전에 계산된 해시값과 현재 바이트의 영향을 조합하는 역할 수행.

최종적으로 hash가 최종 해시값이 되며, 이 값이 반환된다.

다시 말해, 저장된 주소와 XOR 연산을 수행하게 된다.
간단한 예를 들어보자.

ex) page→va = 0x604000 일 때

0x604000 = 01100000 01000000 00000000 (2진수로 표현)
위 2진수를 1바이트로 쪼개면 96, 64, 0이 되고, 나머지 상위 40비트는 0이 된다.

#define FNV_64_PRIME 0x00000100000001B3UL
#define FNV_64_BASIS 0xcbf29ce484222325UL

hash = FNV_64_BASIS;

while (size-- > 0)
		hash = (hash * FNV_64_PRIME) ^ *buf++;
// buf는 순서대로 0, 64, 96, 0, 0, 0, 0, 0

주소는 64비트, 즉 8바이트이므로 size는 8이 되어 8번의 while문을 수행한다.
그리고 이렇게 최종 계산된 해시값과 h->bucket_cnt -1과 AND 비트 연산을 수행한다.

size_t bucket_idx = h->hash(e, h->aux) & (h->bucket_cnt - 1);

이렇게 되면 해시값이 무엇이든 간에 bucket_cnt의 값보다 작은 값의 인덱스로 버킷이 결정된다. bucket_cnt는 2의 n승이고, 그 값에서 1을 빼면 bucket_cnt에 해당하는 비트는 0이 되고 그 아래의 비트는 전부 1이 되기 때문이다. 즉, masking 역할을 수행하게 되는 것이다! 상당히 흥미롭다.

왜 굳이 저렇게 해싱을 할까? 🤔

hash에 FNV_64_PRIME을 곱하고 그 결과에 *buf를 XOR하는 것은 FNV-1a 해시 함수의 구현이다.
이러한 방식으로 해시 값을 갱신하는 이유는 다양한 비트를 사용하여 충돌을 예방하고, 데이터의 작은 변화에도 해시값이 균등하게 분포되도록 하기 위함이다.

  • FNV_64_PRIME은 큰 소수로, 이러한 소수를 사용하는 것이 해시 함수에서 일반적이다. 소수를 사용하면 연산이 더 복잡해지고 다양한 비트가 사용되므로, 입력 데이터의 작은 변화에도 해시값이 고르게 분포될 가능성이 높아진다. 즉, 충돌이나 패턴이 발생할 가능성을 낮춘다고 할 수 있다.
  • XOR 연산은 비트를 뒤집는 특성이 있어서, 입력 데이터의 작은 변화에도 해시값이 많이 바뀌도록 도와준다. 이렇게 함으로써 최종적인 해시값이 입력 데이터의 각 비트에 대한 영향을 받게 되어, 좀 더 균등한 해시값 분포를 얻을 수 있다.
profile
Hyeongjin Song
first in, last out
이전 포스트

WIL : PintOS - 8-9주차

다음 포스트

나만무 - WIL 14주차

0개의 댓글