pintos-Memory Management 구현

💡목표 : 페이지와 프레임의 구조를 만드는 것

페이지(spt)에서 만들어야 할 것

• 구조체 삽입
• 구조체 탐색
• 구조체 삭제

프레임(ft)에서 만들어야 할 것

• 구조체 삽입

• 구조체 탐색

• 구조체 삭제

• 구조체 순회

• 🤔 Hash table이란?
  해시 테이블은 데이터를 효율적으로 저장하고 검색하기 위한 자료구조입니다. 데이터를 저장하는 공간인 버킷(bucket)과 데이터를 해시 함수를 통해 버킷에 매핑하는 연산으로 구성됩니다.

해시 테이블은 일반적으로 배열로 구현되며, 배열의 각 요소를 버킷이라고 합니다. 각 버킷은 연결 리스트나 이진 트리 등으로 구성될 수 있습니다. 각 데이터는 해시 함수를 통해 버킷에 매핑되어 저장되며, 데이터를 검색할 때에도 동일한 해시 함수를 사용하여 해당 버킷을 찾습니다.

해시 함수는 데이터를 입력받아 고정된 길이의 해시 코드를 반환하는 함수입니다. 이 해시 코드는 데이터의 고유한 식별자로 사용되어 버킷과 매핑됩니다. 해시 함수는 데이터의 특징을 잘 반영하고, 충돌을 최소화하는 것이 중요합니다. 충돌은 서로 다른 데이터가 동일한 해시 코드를 가지는 상황을 의미하며, 이는 해시 테이블의 성능을 저하시킬 수 있습니다.

해시 테이블의 주요 연산은 데이터의 삽입, 검색, 삭제입니다. 데이터의 삽입은 해시 함수를 통해 데이터를 적절한 버킷에 저장합니다. 검색은 해시 함수를 이용하여 데이터의 위치를 찾고, 해당 버킷에서 연결 리스트나 이진 트리 등을 탐색하여 데이터를 찾습니다. 삭제는 검색과 마찬가지로 데이터의 위치를 찾은 후, 해당 버킷에서 데이터를 제거합니다.

해시 테이블은 데이터의 삽입, 검색, 삭제 연산을 평균적으로 상수 시간(O(1))에 수행할 수 있으며, 많은 양의 데이터를 빠르게 처리하는 데에 효과적입니다. 그러나 해시 함수의 성능과 충돌을 처리하는 방법에 따라 성능이 달라질 수 있으므로, 적절한 해시 함수의 선택과 충돌 해결 기법의 구현이 중요합니다.

• 🙄 supplemental page table을 hash table 이용해서 구현하는 이유?

  Supplemental page table을 해시 테이블로 구현하는 이유는 효율성과 검색 속도를 향상시키기 위해서입니다.

Supplemental page table은 가상 주소와 물리 주소 사이의 매핑 정보를 유지하는 데이터 구조입니다. 이 매핑 정보는 가상 주소를 물리 주소로 변환하기 위해 필요하며, 페이지 폴트나 페이지 교체 등의 메모리 관리 작업에서 사용됩니다. 이러한 작업은 빈번하게 발생할 수 있으며, 매번 전체 매핑 정보를 선형 검색하는 것은 비효율적입니다.

해시 테이블은 데이터를 효율적으로 검색하기 위한 자료구조로서, 상수 시간(O(1))에 데이터를 찾을 수 있는 장점을 가지고 있습니다. 따라서 supplemental page table을 해시 테이블로 구현하면 매핑 정보를 빠르게 검색할 수 있으며, 가상 주소를 물리 주소로 변환하는 과정에서의 성능을 향상시킬 수 있습니다.

또한, 해시 테이블은 충돌을 처리하는 방법을 통해 충돌을 최소화할 수 있습니다. 충돌은 서로 다른 가상 주소가 동일한 해시 값에 매핑되는 상황을 의미하며, 해시 테이블에서는 이를 해결하기 위해 체이닝 또는 개별 체이닝 등의 충돌 해결 기법을 사용합니다. 이를 통해 매핑 정보를 정확하게 유지하면서도 검색 성능을 향상시킬 수 있습니다.

따라서 해시 테이블을 사용하여 supplemental page table을 구현함으로써, 매핑 정보의 효율적인 관리와 빠른 검색 속도를 제공할 수 있습니다.

1. thread 구조체에 해시 테이블 자료 구조를 추가

• struct thread

  프로세스마다 가상주소 공간이 할당되므로, 가상 페이지를 관리할 수 있는 자료구조인 해시 테이블 정의

프레임(ft) 만들 때 고려해야 할 점

• synchronization 동기화
  : ft는 모든 thread가 공유하는 하나의 자원으로 한번에 하나의 thread가 접근하여 충돌 없이 관리하기 위해서는 lock을 이용해야 한다.

• 구조체 순회
  : swap in/out을 하기 위해서는 ft를 순회하면서 메모리 내에서 쫒아낼 프레임을 빠르게 골라내야 한다. 이때 eviction policy를 고려하면서 순회를 진행하고 반환해야 한다.