[Memory Manament] 주간 공유

[wnstn819]

공부한 내용

• page table(pml4)
  가상 주소(page주소)와 물리 주소(frame 주소)를 매핑한 테이블
  page table을 들여다보고 유효한 주소가 아니거나, frame에 page에 대한 데이터 값이 없으면(not_present=1) page fault 발생
  page fault 발생시 vm_try_fault_handler에서 supplemental page table(spt)을 참조한다.
  page를 frame으로 적재하기 위해서 page정보를 확인할 수 있는 spt가 필요하다
  

bool
vm_try_handle_fault (struct intr_frame *f UNUSED, void *addr UNUSED,
		bool user UNUSED, bool write UNUSED, bool not_present UNUSED) {
	struct supplemental_page_table *spt UNUSED = &thread_current ()->spt;
	struct page *page = NULL;
	/* TODO: Validate the fault */
	/* TODO: Your code goes here */
	if (addr == NULL)
		return false;
	if (is_kernel_vaddr(addr))
		return false;
	if (not_present)
	{
		page = spt_find_page(spt, addr);
		if (page == NULL)
			return false;
		if(write==1 && page->writable ==0)
			return false;
		return vm_do_claim_page(page);
	}
}

• supplemental page table
  각 쓰레드에는 spt가 담기고 spt에는 page 구조체에 대한 정보가 담긴다.
  spt의 자료구조는 선택사항이지만 여기서는 hash table로 구현하도록 한다.

• 자료구조
  시간복잡도: array(O(1)) = hash table(O(1)) > linked_list(O(n))
  array와 hash table 모두 인덱스로 접근할 수 있기 때문에 시간복잡도는 O(1)
  hash table은 array처럼 연속적인 메모리 공간이 필요하지 않으므로 메모리 효율성이 좋다.
  위와 같은 이유로 spt의 자료구조로 hash table 사용

• hash table
  page의 가상주소(virtual page number)를 hash 함수(page_hash)에 통과시키면 고유한 인덱스가 만들어진다.
  고유한 인덱스마다 bucket에 hash_elem(페이지 구조체)를 갖게 한다.
  겹치는 인덱스가 생길 수 있으므로, bucket을 연결 리스트로 구성한다.

[gustjd109]

핀토스 메모리 개요

1. 현재 핀토스에서의 메모리

   • 현재 주소 공간은 4개의 세그먼트로 구성
     • Stack
     • Initialized Data
     • Uninitialized Data
     • Code
     • Heap은 현재 없는 상태
       
       
   • 프로세스의 메모리 탑재 과정
     • 각 세그먼트(Stack, Data, BSS, Code)가 물리페이징에 탑재
     • 페이지 테이블 초기화
       
       
   • 한계
     • Swap 사용 불가
     • Demand Paging 사용 불가
     • Virtual Memory 구현되어 있지 않음
     • 즉, 우리는 현재 핀토스에서 위 기능을 구현해야 함

2. 현재 핀토스 메모리 레이아웃
   

   • 현재 핀토스에서의 메모리 레이아웃은 위 그림과 같다.
   • 핀토스의 가상 주소 공간은 디스크로부터 ELF 이미지의 세그먼트를 물리 메모리로 읽는다.
   • 이 방법은 물리 메모리를 낭비하는 문제가 발생하기 때문에 물리 메모리 할당 대신 가상 페이지마다 supplemental page table을 통해 적재할 정보들만 관리하도록 구현해야 한다.
     
     

3. Supplemental Page Table 구현 후, 핀토스 메모리 레이아웃
   

   • 위 그림을 보면, 헤시 테이블을 사용하는 것을 볼 수 있다.
   • 그럼 왜 헤시 테이블을 사용하여 Supplemental Page Table를 구현했을까?🤔

Supplemental Page Table에서 해시 테이블을 사용하는 이유

• GitBook의 Introduction에서 Choices of implementation(Performance perspective) 부분에 관련 내용이 간단하게 명시되어 있다.
  
  

1. Choices of implementation(Performance perspective) 내용
   • 구현할 수 있는 선택 사항에는 배열, 리스트, 비트맵 및 해시 테이블이 있습니다. 배열은 종종 가장 간단한 접근 방식이지만, 드물게 채워진 배열은 메모리를 낭비합니다. 리스트도 간단하지만, 특정 위치를 찾기 위해 긴 리스트를 탐색하는 것은 시간 낭비입니다. 배열과 리스트 모두 크기를 조정할 수 있지만, 리스트는 중간에 삽입 및 삭제를 더 효율적으로 지원합니다.
   • 핀토스는 lib/kenel/bitmap.c와 include/lib/kenel/bitmap.h에 비트맵 데이터 구조를 포함하고 있습니다. 비트맵은 각각 참 또는 거짓이 될 수 있는 비트의 배열입니다. 비트맵은 일반적으로 (동일한) 리소스 집합에서 사용량을 추적하는 데 사용됩니다 : 리소스 n이 사용 중이면 비트맵의 비트 n이 참입니다. 핀토스 비트맵은 크기가 고정되어 있지만, 크기 조정을 지원하도록 구현을 확장할 수 있습니다.
   • 핀토스에는 해시 테이블 데이터 구조도 포함되어 있습니다. 핀토스 해시 테이블은 다양한 테이블 크기에 걸쳐 삽입과 삭제를 효율적으로 지원합니다.
   • 데이터 구조가 복잡할수록 더 나은 성능이나 기타 이점을 얻을 수 있지만, 구현이 불필요하게 복잡해질 수도 있습니다. 따라서, 설계의 일부로 고급 데이터 구조(예: 균형 잡힌 이진 트리)를 구현하는 것은 권장하지 않습니다.
     
     
2. GitBook 내용만으로는 의문이 풀리지 않아서 생각을 좀 더 해봤다.
   • 해시는 key와 value로 데이터를 저장하는 자료구조이다.
   • 내부적으로 배열(bucket 또는 slot)을 이용하여 데이터를 저장하기 때문에 O(1)의 시간복잡도를 가져 데이터를 빠르게 검색할 수 있다.
   • 해시 테이블은 각각의 key값에 해시 함수를 적용하여 배열의 고유한 인덱스를 생성하고, 이 인덱스를 활용하여 값을 저장하고 검색할 수 있다.
   • 따라서, Supplemental Page Table 구현 후, 핀토스 메모리 레이아웃처럼 해시 테이블의 인덱스를 이용하여 실제 주소를 가지고 있는 배열을 찾아 데이터를 찾을 수 있다.
   • 위와 같이 데이터를 저장하고 빠르게 검색할 수 있다는 장점때문에 사용하는 것이 아닐까 생각이 든다(맞는겨???😒).

[wnstn819]

📌 - Hash table

• 기본적인 해쉬 테이블은 key - value를 저장하는 구조이다
• 예를들어서 50을 저장할 때 index = hash_function(50) % 16 을 통해서 해쉬 값을 받아와서 해당 테이블에 저장한다.
• 이렇게 저장하면 key에 대한 데이터를 찾을 때 한번만 수행하면 index 위치를 찾을 수 있기 때문에 저장과 삭제가 O(1)로 매우 빠르다.

하지만 이런 방식으로 해쉬 테이블을 구현하게 되면 해쉬 값이 겹칠 경우 문제가 발생하는데 겹치게 되면 충돌이 발생한다. 해결 방법으로는

📌 - Seperate Chaining

Linked List를 이용하는 방식으로 각 index 데이터를 저장하는 linked list에 대한 포인터를 가지는 방식이다.

index로 인해서 충돌이 발생하면 그 index가 가리키고 있는 linked list에 노드를 추가하여 값을 추가한다.

이렇게 하면 충돌이 발생하더라도 데이터를 삽입하는데 문제가 없다.

하지만 단점으로 최악의 경우로 같은 index에 계속해서 값이 들어간다면 탐색을 하는데 많은 시간이 들게 되어 비효율적이다.

📌 - load factor

로드 팩터(Load Factor)는 해시 테이블에서 사용되는 지표로, 해시 테이블에 저장된 요소 수와 버킷 수 간의 비율을 나타낸다. 주로 해시 테이블의 가득 차는 정도를 측정하는 데 사용된다.
로드 팩터 = (해시 테이블에 저장된 요소의 수) / (해시 테이블의 버킷 수)
로드 팩터는 일반적으로 요소 수를 버킷 수로 나눈 값으로 계산된다. 예를 들어, 해시 테이블에 100개의 요소가 있고 버킷이 50개인 경우, 로드 팩터는 100/50 = 2이다.

작은 로드 팩터는 해시 테이블에 여유 공간이 많다는 것을 의미하며, 충돌이 발생할 확률이 적어진다. 반대로 큰 로드 팩터는 해시 테이블이 가득 차있거나, 버킷 당 평균 요소 수가 많아져 충돌이 더 자주 발생할 가능성이 높아진다.

로드 팩터를 적절하게 설정하고, 재해싱을 효율적으로 수행함으로써 해시테이블의 성능을 향상시킬 수 있습니다.

---

🗒️ - hash.c -> rehash()

static void
rehash (struct hash *h) {
	size_t old_bucket_cnt, new_bucket_cnt;
	struct list *new_buckets, *old_buckets;
	size_t i;

	ASSERT (h != NULL);

	/* Save old bucket info for later use. */
	old_buckets = h->buckets;
	old_bucket_cnt = h->bucket_cnt;

	/* Calculate the number of buckets to use now.
	   We want one bucket for about every BEST_ELEMS_PER_BUCKET.
	   We must have at least four buckets, and the number of
	   buckets must be a power of 2. */
	new_bucket_cnt = h->elem_cnt / BEST_ELEMS_PER_BUCKET;
	if (new_bucket_cnt < 4)
		new_bucket_cnt = 4;
	while (!is_power_of_2 (new_bucket_cnt))
		new_bucket_cnt = turn_off_least_1bit (new_bucket_cnt);

	/* Don't do anything if the bucket count wouldn't change. */
	if (new_bucket_cnt == old_bucket_cnt)
		return;
       
       
       / ************************* /

pintos에서는 요소가 추가 될때마다 rehash를 해서 이전 버킷의 값과 현재 요소의 개수 / 2 를 해서 이전 버킷과 새로운 버킷의 값이 다르면 재배치를 하게 되는데, 현재는 재배치를 자주하게 되어서 이 부분을 LOAD_FACTOR를 이용해서 해당하는 값을 초과하게 되면 한번에 2배 정도의 버킷을 할당해서 연산을 더 줄일 수 있지 않을까 생각합니다.

while (!is_power_of_2 (new_bucket_cnt))
		new_bucket_cnt = turn_off_least_1bit (new_bucket_cnt);

-> 이 부분에서 2배로 해주고 있었음...