[PintOS 4주차] Day 2

munsik22 2025. 5. 30. 11:42

Memory Management #

가상 메모리 시스템을 지원하기 위해 가상 페이지와 물리 프레임을 효율적으로 관리해야 한다. 어떤 (가상/물리) 메모리가 어떤 목적으로 누구에 의해 사용 중인지를 추적해야 한다는 뜻이다. 우선 보조 페이지 테이블을 먼저, 그리고 물리 프레임을 다뤄야 한다.

📃 앞으로 "page"는 virtual page를, "frame"은 physical page를 의미한다.

🔹 Page Structure and Operations

`struct page`

vm.h에서 정의된 page는 VM의 페이지를 나타내는 구조체다. 우리가 페이지에 대해 알아야 하는 모든 필요한 데이터들을 저장한다.

struct page {
  const struct page_operations *operations;
  void *va;              /* Address in terms of user space */
  struct frame *frame;   /* Back reference for frame */

  union {
    struct uninit_page uninit;
    struct anon_page anon;
    struct file_page file;
#ifdef EFILESYS
    struct page_cache page_cache;
#endif
  };
};

page 구조체는 페이지 동작, 가상 주소, 물리 프레임 정보를 포함한다.
추가로 union 필드도 가지고 있다.
- union은 한 메모리 영역에서 다른 종류의 데이터를 저장할 수 있게 하는 특별한 자료형이다.
- union에는 다양한 멤버들이 있지만, 한 번에 하나의 멤버만 값을 가질 수 있다.
- 시스템의 페이지가 union_page, anon_page, file_page 또는 page_cache가 될 수 있음을 의미한다.
- 예를 들어, 페이지가 anonymous page라면, page 구조체는 struct anon_page anon 필드를 그것의 멤버 중 하나로 가질 것이다. anon_page는 anonymous page에 필요한 정보들을 포함한다.

Page 동작

페이지는 VM_UNINIT, VM_ANON 또는 VM_FILE이 될 수 있다.
- 페이지는 스왑 인, 스왑 아웃, 페이지 파괴와 같은 여러 동작들을 수행한다.
- 각 페이지 타입별로 이러한 동작을 위해 요구되는 단계와 태스크가 달라진다. 달리 말해, VM_ANON 페이지와 VM_FILE 페이지를 위해 서로 다른 destroy 함수가 실행되어야 한다.
- 각 케이스를 다루기 위해 각 함수에 대해 switch-case문을 사용하는 것이 하나의 방법이다.
- 이를 다루는 방법으로 객체 지향 프로그래밍의 컨셉인 "클래스 상속"이 도입되었다: 실제로 C에는 클래스도, 상속도 없지만, 대신에 함수 포인터를 사용해 이 컨셉을 실현한다.
함수 포인터는 함수나 메모리에 있는 실행가능 코드를 가리키는 포인터다.
- 따로 체크하는 것 없이 run-time 값을 기반으로 실행되는 특정한 함수를 호출하는 단순한 방법을 제공해준다.
- 예를 들어, 코드 레벨에서 단순히 destroy(page)을 호출하는 것으로도 충분하다: 컴파일러가 올바른 함수 포인터를 호출함으로써 페이지 종류에 따라 적절한 destroy 루틴을 선택할 것이다.
페이지 동작을 위한 구조체 struct page_operations는 함수의 테이블로서 3개의 함수 포인터를 가진다.

struct page_operations {
  bool (*swap_in) (struct page *, void *);
  bool (*swap_out) (struct page *);
  void (*destroy) (struct page *);
  enum vm_type type;
};

struct page를 보면 operations라는 필드를 볼 수 있다. file.c에서는 함수 프로토타입 이전에 선언된 file_ops라는 page_operation 구조체를 볼 수 있다. 이는 file-backed 페이지에 대한 함수 포인터 테이블이다. .destroy 필드는 페이지를 파괴하는 함수인 file_backed_destroy 값을 가진다.
함수 포인터 인터페이스로 file_backed_destroy가 어떻게 호출되는지 알아보자.
- vm_dealloc_page(page)가 호출된다고 가정하자: 이 때 page는 file-backed 페이지(VM_FILE)다.
- 함수 내부에서 destroy(page)를 호출한다:
```
#define destroy(page) if ((page)->operations->destroy) (page)->operations->destroy (page)
```
- destroy 함수를 호출하는 것은 실제로는 (page)->operations->destroy(page)를 실행하는 것이다: 여기서 destroy 함수는 페이지 구조체에서 가져온 것이다.
- 페이지가 VM_FILE 페이지기 때문에, .destroy 필드는 fie_backed_destroy를 가리키게 된다.
- 그 결과, file-backed 페이지를 위한 destroy 루틴이 실행된다.

🔹 Implement Supplemental Page Table

핀토스는 메모리의 가상/물리적 매핑을 관리하기 위한 페이지 테이블(pml4)를 가지고 있다. 거기에 페이지 폴트와 리소스 관리를 위해 각 페이지에 대한 추가적인 정보를 가지는 보조 페이지 테이블(SPT)이 필요하다.

SPT가 뭐였더라?

SPT는 각 프로세스마다 존재하는 커널 내부 자료구조로, 페이지 폴트 발생 시 해당 가상주소에 대해 다음을 알려준다.
- 이 주소에 어떤 페이지가 매핑되어야 하는가?
- 그 페이지의 유형은 무엇인가?
- 어떻게 해당 데이터를 준비해야 하는가?
SPT에 저장되는 페이지 유형
1. Anonymous Page
  - 디스크에 대응되지 않는 순수 메모리 전용 데이터
  - (예) heap 영역에서 malloc()으로 할당된 메모리, 초기화되지 않은 전역변수(.bss)
  - 새로운 프레임을 할당하고 0으로 초기화하거나, 복사된 내용을 메모리에 적재
2. File-backed Page
  - 특정 파일의 일부를 매핑한 페이지 (ELF 세그먼트, mmap된 파일 등)
  - (예) 실행 파일의 코드(.text)나 데이터(.data) 세그먼트, mmap()을 통한 파일 매핑
  - 파일에서 해당 offset만큼 읽어와서 메모리에 적재
3. Uninit Page (= Lazy Page)
  - 위 두 종류 중 어떤 것으로든 나중에 초기화될 예정인 미확정 페이지
  - (예) 프로그램이 실행되기 전 load_segment()에서 vm_alloc_page_with_initializer()를 통해 등록되는 모든 초기 상태의 페이지
  - SPT에는 VM_UNINIT으로 등록되지만, 페이지 폴트 시 실제 메모리 접근이 발생하면 initializer()를 호출해 Anoymous나 File-based backed로 전환됨

유형	설명	초기화 방법
Anonymous	파일 없이 메모리만 사용하는 페이지	0으로 초기화 또는 복사
File-backed	파일로부터 데이터를 가져오는 페이지	파일에서 읽어와서 로딩
Uninit	아직 어떤 타입이 될지 정해지지 않음	접근 시 Lazy하게 초기화

SPT의 중요한 역할 2가지는 다음과 같다.
1. 페이지 폴트 시 커널이 SPT에서 오류가 발생한 가상 페이지를 조회해서 어떤 데이터가 있어야 하는지 확인함: anonymous/file-backed/uninit
2. 프로세스가 종료될 때 커널이 SPT를 참조해 어떤 리소스를 free할 지 결정함
  - Anonymous page: 실제 프레임 메모리도 free해야 함
  - File-backed page: dirty인 경우 write back 필요
  - Swap에 있는 페이지: 스왑 슬롯도 free해야 함

SPT 구현하기

가장 먼저 SPT를 위한 기본 기능들을 구현해보자. 우선 어떻게 SPT를 설계할 것인지 정해야 한다. 그리고 다음 3가지 기능들을 선택한 디자인에 따라 구현한다.

void supplemental_page_table_init (struct supplemental_page_table *spt);

SPT를 초기화한다. SPT를 위해 사용할 자료구조를 선택해야 한다. 이 함수는 다음과 같은 상황에서 호출된다.
- 새로운 프로세스가 시작될 때: initd
- 프로세스가 포크될 때: __do_fork

struct page *spt_find_page (struct supplemental_page_table *spt, void *va);

주어진 SPT에서 가상주소 va에 대응되는 struct page를 찾는다. 실패하면 NULL을 리턴한다.

bool spt_insert_page (struct supplemental_page_table *spt, struct page *page);

주어진 SPT에 struct page를 삽입한다. 이 함수는 가상주소가 주어진 SPT에 존재하지 않는지 확인해야 한다.

🔹 Frame Management

모든 페이지들은 생성될 때 메모리의 메타데이터를 가지지 않는다. 따라서, 물리 메모리를 관리하는 다른 방식이 필요하다. vm.h에 물리 메모리를 나타내는 struct frame이 있다.

/* The representation of "frame" */
struct frame {
  void *kva; // kernel virtual address
  struct page *page; // page structure
};

static struct frame *vm_get_frame (void);

palloc_get_page를 호출함으로써 유저 풀에서 새로운 물리 페이지를 가져온다.
- 성공적으로 페이지를 가져왔다면, 프레임을 할당하고, 멤버를 초기화해서 리턴한다.
- vm_get_frame을 구현한 후에, 이 함수를 사용해 모든 유저 공간 페이지들(PALLOC_USER)을 할당해야 한다.
- 아직 페이지 할당 실패의 경우에 스왑 아웃을 다룰 필요는 없다. (일단 PANIC("todo")로 표시)

bool vm_do_claim_page (struct page *page);

페이지를 claim한다: 새로운 물리 프레임을 할당한다.
- 먼저 vm_get_frame을 호출해서 프레임을 얻는다.
- 그 다음 MMU를 설정해야 한다: VA에서 PA로의 매핑을 PT에 추가해야 한다.
- 리턴값은 이 동작이 성공했는지 아닌지를 나타낸다. (성공하면 true, 실패하면 false)

bool vm_claim_page (void *va);

가상주소 va를 할당하기 위해 페이지를 claim한다. 우선 페이지를 얻은 후에 vm_do_claim_page를 호출해야 한다.

Hash Table #

[출처] Hash Table Data Structure | GeeksforGeeks

핀토스는 기본적으로 hash.c에서 해시 테이블 자료구조를 제공한다. 사용하려면 hash.h 헤더 파일을 include해야 하며, 해시 테이블을 사용하는 코드가 없기 때문에 아무렇게나 수정해도 지장 없다.

대부분의 VM 프로젝트 구현은 페이지를 프레임으로 변환하는 데 해시 테이블을 사용한다. 해시 테이블을 다른 용도로 사용할 수도 있다.

🔹 Data Types

struct hash;

해시 테이블 전체를 나타낸다.
- struct hash의 실제 멤버들은 "불투명opaque"하다.
- 해시 테이블을 사용하는 코드는 struct hash 멤버에 직접 접근해서도 안되고, 그럴 필요도 없다.
- 대신, 해시 테이블 함수와 매크로를 사용해야 한다.

struct hash_elem;

해시 테이블에 넣고자 하는 구조체 안에 struct hash_elem 멤버를 넣는다.
- struct hash_elem 역시 불투명하다: 해시 테이블 요소들에 대해 작동하는 모든 함수들은 실제로는 해시 테이블의 실제 요소 타입으로의 포인터가 아니라 struct hash_elem으로의 포인터를 리턴한다.
- 주어진 해시 테이블의 진짜 요소에 대해 struct hash_elem을 얻어야 하거나, 혹은 그 반대로 해야 할 수 있다.
- 주어진 해시 테이블의 진짜 요소에 대해, 그것의 struct hash_elem로의 포인터를 얻기 위해 &을 사용하고, 반대 방향으로는 hash_entry() 매크로를 사용한다.

#define hash_entry(HASH_ELEM, STRUCT, MEMBER)
	((STRUCT *) ((uint8_t *) &(HASH_ELEM)->list_elem - offsetof (STRUCT, MEMBER.list_elem)))

elem(struct hash_elem으로의 포인터)을 내장한 구조체로의 포인터를 리턴한다.
- type, elem이 들어간 구조체의 이름, 멤버, elem이 가리키는 type의 member의 이름을 제공해야 한다.
- 예를 들어, h가 h_elem이라는 이름의 (struct hash_elem 타입의) 스레드 구조체 멤버를 가리키는 struct hash_elem * 변수라고 가정하자: hash_entry(h, struct thread, h_elem)은 h가 가리키는 struct thread의 주소를 만들어 낸다.
각 해시 테이블 요소는 key를 포함해야 한다.
- key는 요소를 식별하고 구분하는 데이터로, 해시 테이블의 요소들 중에서 유일해야 한다.
- 요소들은 또한 유일한 필요는 없는 non-key 데이터들도 가질 수 있다.
- 한 요소가 해시 테이블 내에 있는 동안, 그것의 key 데이터는 바뀌면 안 된다.
- 대신, 필요한 경우, 그 요소를 해시 테이블에서 지우고, key를 바꿔서 요소에 재삽입한다.
각 해시 테이블에 대해, key에 대해 동작하는 해시 함수와 비교 함수를 만들어야 한다.

typedef unsigned hash_hash_func (const struct hash_elem *e, void *aux);

unsigned int의 아무 범위의 값으로서 요소의 데이터의 해시를 리턴한다.
- 한 요소의 해시는 요소의 키에 대한 pseudo-random 함수여야 한다.
- 요소 내의 non-key 데이터나 key가 아닌 상수가 아닌 데이터에 의존해야 한다.
- 핀토스는 해시 함수를 위한 적절한 기반으로서 다음 함수들을 제공한다.
  - unsigned hash_bytes (const void *buf, size t *size): buf에서 시작하는 size 바이트의 해시를 리턴한다. 32비트 워드의 범용 Fowler-Noll-Vo 해시로 구현되었다.
  - unsigned hash_string (const char *s): null로 끝나는 문자열 s의 해시를 리턴한다.
  - unsigned hash_int (int i): 정수 i의 해시를 리턴한다.
- key가 적절한 타입의 단일 데이터인 경우, 해시 함수가 직접 위 함수들 중 하나의 출력 리턴하는 것이 좋다.
- 다중 데이터인 경우, ^(XOR) 연산자 등을 사용해 여러 호출의 출력을 합칠 수 있다.
- bool hash_less_func (const struct hash_elem *a, const struct hash_elem *b, void *aux)
  - 요소 a와 b에 저장된 key를 비교한다: a < b인 경우 true를, a ≥ b인 경우 false를 리턴한다.
  - 두 요소가 같은 경우, 동일한 값들을 해시해야 한다.
- void hash_action_func (struct hash_elem *element, void *aux): 호출자에 의해 선택된 동작 aux을 수행한다.

🔹 Basic Functions

bool hash_init (struct hash *hash, hash_hash_func *hash_func, hash_less_func *less_func, void *aux)

hash를 해시 함수로 hash func, 비교 함수로 less func, 보조 데이터로 aux를 갖는 해시 테이블로 초기화한다.
- 성공 시 true를 반환하고, 실패 시 false를 반환한다.
- 메모리를 할당할 수 없으면 hash_init()는 malloc()을 호출하고 실패한다.
- 일반적으로 aux는 null 포인터를 가진다.

void hash_clear (struct hash *hash, hash_action_func *action)

hash_init()으로 초기화되었던 해시에서 모든 요소들을 제거한다.
- action이 null이 아닌 경우, 해시 테이블의 각 요소들에 대해 한 번씩 호출돼서, 호출자가 해당 요소에서 사용되는 메모리나 다른 리소스를 해제할 수 있다.
- 예를 들어, 해시 테이블 요소들이 malloc()으로 동적 할당된 경우, action은 요소를 free()시켜줄 수 있다.
- hash_clear()가 action을 호출한 이후에 주어진 해시 요소의 메모리에 접근하지 않기 때문에 안전하다.
- 그러나 action은 해시 테이블을 수정할 수 있는 함수(hash_insert(), hash_delete() 등)를 호출해서는 안 된다.

void hash_destroy (struct hash *hash, hash_action_func *action);

action이 null이 아닌 경우, 해시의 각 요소로부터 호출해서 hash_clear()을 호출한 것과 같은 의미를 가진다. 그 다음에 해시에 할당되었던 메모리를 free시킨다.
- 이후에 hash는 hash_init()을 호출하지 않는 한 어떤 해시 테이블 함수에도 전달되면 안 된다.

size_t hash_size (struct hash *hash);

현재 hash에 저장된 요소의 수를 리턴한다.

bool hash_empty (struct hash *hash);

hash에 현재 요소가 하나도 없으면 true를, 하나라도 있으면 false를 리턴한다.

🔹 Search Functions

각 함수들은 해시 테이블에서 주어진 요소와 같은 요소가 있는지 찾는다. 검색이 성공하면 (해시 테이블에 새로운 요소를 삽입하는 등의) action을 수행하거나, 단순히 탐색의 결과를 리턴한다.

struct hash_elem *hash_insert (struct hash *hash, struct hash elem *element);

hash에서 element와 동일한 요소가 있는지 검색한다.
- 아무것도 찾지 못하면 hash에 element를 삽입하고 null을 리턴한다.
- 테이블이 이미 element와 동일한 요소를 가지고 있는 경우, hash를 수정하지 않고 리턴된다.

struct hash_elem *hash_replace (struct hash *hash, struct hash elem *element);

hash에 element를 삽입한다. element와 동일한 hash 내의 요소는 제거된다. 제거된 요소를 리턴하거나, hash가 동일한 요소가 없었던 경우 null 포인터를 리턴한다.
호출자는 리턴된 요소와 관련된 리소스들을 적절히 해제해야 한다. 예를 들어, 해시 테이블 요소들이 malloc()으로 동적 할당되었다면, 호출자는 더 이상 필요 없어진 요소들 반드시 free() 해줘야 한다.

다음 함수들에 전달되는 요소는 오직 해싱과 비교 목적으로만 사용되어야 한다. 절대 해시 테이블에 삽입되지 않는다. 따라서, 오직 요소의 key 데이터만이 초기화되어야 하고, 요소의 다른 데이터들은 사용되지 않는다. 요소 타입의 인스턴스를 지역 변수로 선언하고, key 데이터를 초기화한 다음에 struct hash_elem의 주소를 hash_find()나 hash_delete()에 전달하는 것이 좋다.

struct hash_elem *hash_find (struct hash *hash, struct hash elem *element);

hash에서 element와 같은 요소를 찾는다. 찾으면 해당 요소를, 없으면 null 포인터를 리턴한다.

struct hash_elem *hash_delete (struct hash *hash, struct hash elem *element);

hash에서 element와 동일한 요소를 찾는다. 찾으면 hash에서 지우고 리턴한다. 없으면 null 포인터를 리턴하고 hash는 변경되지 않는다.
마찬가지로, 호출자는 리턴되는 요소와 관련된 리소스들을 적절히 해제해줘야 한다.

🔹 Iteration Functions

아래 함수들은 해시 테이블을 반복할 수 있도록 한다. 2개의 인터페이스가 제공되며, 첫 번째 인터페이스는 각 요소에 대해 동작할 수 있도록 writing과 hash_action_func를 필요로 한다.

void hash_apply (struct hash *hash, hash action func *action);

hash 내의 각 요소에 대해 임의의 순서로 한 번씩 action을 호출한다.
- action은 해시 테이블을 수정할 수 있는 함수(hash_insert(), hash_delete() 등)를 호출하면 안 된다.
- action이 요소들의 다른 데이터는 수정해도 key 데이터는 수정하면 안 된다.

두 번째 인터페이스는 "iterator" 데이터 타입에 기반한다. 관용적으로, 반복자들은 다음과 같이 사용된다.

struct hash_iterator i;
hash_first (&i, h);
while (hash_next (&i)) {
    struct foo *f = hash_entry (hash_cur (&i), struct foo, elem);
    . . . do something with f . . .
}

struct hash_iterator;

해시 테이블 내의 위치를 나타낸다.
- 해시 테이블을 수정할 수 있는 함수를 호출하는 것은 그 해시 테이블의 모든 반복자를 무효화한다.
- struct hash와 struch hash_elem처럼, struct hash_elem은 불투명하다.

void hash_first (struct hash iterator *iterator, struct hash *hash);

hash의 첫 번째 요소 바로 앞에 반복자를 초기화한다.

struct hash_elem *hash_next (struct hash iterator *iterator);

반복자를 hash의 다음 요소로 이동시키고 해당 요소를 리턴한다.
- 요소가 남아 있지 않으면 null 포인터를 리턴한다.
- hash_next()가 반복자에 대해 null을 리턴한 후에 다시 호출하면 정의되지 않은 동작을 발생시킨다.

struct hash_elem *hash_cur (struct hash iterator *iterator);

반복자에 대해 hash_next()에 의해 가장 최근에 리턴된 값을 리턴한다.
- 반복자에 대해 hash_first()가 호출된 후, hash_next()가 호출되기 전에는 정의되지 않은 동작을 발생시킨다.

🔹 Hash Table 예제

해시 테이블 안에 넣고 싶은, struct page라는 구조체가 있다고 가정하자. 먼저 struct hash_elem의 멤버로 포함시키기 위해 struct page를 정의한다.

struct page {
    struct hash_elem hash_elem; /* Hash table element. */
    void *addr; /* Virtual address. */
    /* . . . other members. . . */
};

addr를 key로 하는 해시 함수와 비교 함수를 작성한다. 포인터는 바이트 길이를 기반으로 해시될 수 있고, < 연산자가 포인터 비교에 적당하다.

/* Returns a hash value for page p. */
unsigned
page_hash (const struct hash_elem *p_, void *aux UNUSED) {
  const struct page *p = hash_entry (p_, struct page, hash_elem);
  return hash_bytes (&p->addr, sizeof p->addr);
}

/* Returns true if page a precedes page b. */
bool
page_less (const struct hash_elem *a_,
           const struct hash_elem *b_, void *aux UNUSED) {
  const struct page *a = hash_entry (a_, struct page, hash_elem);
  const struct page *b = hash_entry (b_, struct page, hash_elem);

  return a->addr < b->addr;
}

다음으로 해시 테이블을 다음과 같이 만들 수 있다.

struct hash pages;
hash_init (&pages, page_hash, page_less, NULL);

이제 만들었던 해시 테이블을 조작할 수 있다. p가 struct page로의 포인터라면, 우리는 해시 테이블에 다음과 같이 삽입할 수 있다.

hash_insert (&pages, &p->hash_elem);

동일한 addr에 대해 페이지가 이미 페이지를 포함하고 있을 수도 있다면, 우리는 hash_insert()의 리턴값을 확인해야 한다.

해시 테이블의 요소를 검색하기 위해 hash_find()를 사용한다. hash_find()가 비교할 때 사용할 요소를 필요로 하기 때문에 설정 작업이 필요하다. 다음 함수는 (페이지들이 파일 범위 내에서 정의되었다는 가정 하에) 가상 주소에 기반한 페이지를 찾고 리턴한다.

/* Returns the page containing the given virtual address, or a null pointer if no such page exists. */
struct page *
page_lookup (const void *address) {
  struct page p;
  struct hash_elem *e;

  p.addr = address;
  e = hash_find (&pages, &p.hash_elem);
  return e != NULL ? hash_entry (e, struct page, hash_elem) : NULL;
}

struct page는 충분히 작다는 가정 하에 지역 변수로서 할당된다. 큰 구조체는 지역 변수로 할당되면 안 된다.

비슷한 함수는 hash_delete()를 사용해서 페이지를 없앨 수 있다.

🔹 Auxiliary Data

위의 예제와 같이 단순한 경우는 aux 파라미터가 필요 없다. 이러한 경우에서는, 단순히 hash_init()에 aux를 null 포인터로 넘기고 해시 및 비교 함수로 전달되는 값들은 무시하면 된다.
- aux 파라미터를 사용하지 않으면 컴파일러 에러가 뜰 수도 있지만 그냥 무시하면 된다.
aux는 해시 테이블의 데이터 속성이 상수이고 해싱이나 비교에 필요하지만 데이터 항목 자체에는 저장되지 않은 경우 유용하다.
- 예를 들어, 해시 테이블의 항목이 고정 길이 문자열이지만 항목 자체가 해당 고정 길이를 나타내지 않는 경우, 길이를 aux 매개변수로 전달할 수 있다.

🔹 Synchronization

해시 테이블은 내부 동기화를 수행하지 않는다. 해시 테이블 함수 호출을 동기화하는 것은 호출자의 책임이다.
- 일반적으로 해시 테이블을 검사하지만 수정하지 않는 함수(hash_find(), hash_next() 등)는 동시에 실행될 수 있다.
- 그러나 이러한 함수는 주어진 해시 테이블을 수정할 수 있는 함수(hash_insert(), hash_delete() 등)와 동시에 안전하게 실행될 수 없으며, 주어진 해시 테이블을 수정할 수 있는 두 개 이상의 함수가 동시에 안전하게 실행될 수도 없다.
해시 테이블 요소의 데이터 액세스를 동기화하는 것도 호출자의 책임이다.
- 이 데이터에 대한 액세스를 동기화하는 방법은 다른 데이터 구조와 마찬가지로 해시 테이블 요소의 설계 및 구성 방식에 따라 달라진다.

🔸 Hash Table for SPT

왜 해시 테이블이 필요한가?
- SPT의 핵심 기능은 가상 주소를 페이지 구조체에 매핑하고, 페이지 폴트 발생 시 해당 가상 주소에 대한 정보를 빠르게 찾는 것
- 리스트 기반 구조의 선형 탐색(O(n))으로는 너무 느리다.
- 해시 테이블은 평균적으로 O(1)에 가까운 속도로 조회가 가능하므로 성능과 효율성 보장 가능
구현 예시

struct supplemental_page_table {
    struct hash spt_hash; // <가상 주소, 페이지 정보> 쌍을 저장하는 해시 테이블
};

struct page {
    void *va;                 // 가상 주소 (key)
    struct frame *frame;     // 매핑된 프레임 정보
    enum vm_type type;       // Anonymous, File-backed 등
    ...                      // 그 외 초기화 함수, aux 등
    struct hash_elem hash_elem; // 해시 테이블용 링크
};

/* Compares in hash table with page.va and choose bucket */
unsigned page_hash (const struct hash_elem *e, void *aux);
bool page_less (const struct hash_elem *a, const struct hash_elem *b, void *aux);

동작 흐름 요약

시점	동작 내용
페이지 등록	`hash_insert(&spt->spt_hash, &page->hash_elem);`
페이지 조회	`hash_find(&spt->spt_hash, &lookup_elem);`
페이지 삭제	`hash_delete(&spt->spt_hash, &page->hash_elem);`
전체 정리	`hash_destroy(&spt->spt_hash, destructor_function);`

구현 목표
1. 가상 주소 → struct page를 효율적으로 매핑: 이를 위해 내부적으로 struct hash를 포함시킨다.
2. 해시 기반으로 다음 기능들을 지원해야 한다.
  - SPT 초기화 (supplemental_page_table_init())
  - SPT 삽입 (spt_insert_page() 또는 vm_alloc_page())
  - SPT 조회 (spt_find_page())
  - SPT 제거 (spt_remove_page() 또는 vm_dealloc_page())
  - SPT 전체 파괴 (supplemental_page_table_kill())

🤝 코어타임

struct frame *frame = palloc_get_page(PAL_USER); // 또는 init_page() 구현
frame->kva = 0;
frame->page = NULL;

struct page_operations *po = palloc_get_page(PAL_USER); // 또는 init_page_ops() 구현
po->swap_in = *fa;
po->swap_out = *fb;
po->destrop = *fc;

page->operations = po; // 어디서??

destrop(page); // 〓 fc(page);

struct page *page = palloc_get_page(PAL_USER);

frame->kva = pml4_get_page(&pml4, &page);