0. 자원 관리 개요

구현할 자료구조 :

• 보조 페이지 테이블
• 프레임 테이블
• 스왑 테이블

구현을 위한 가능한 선택지로는 배열, 리스트, 비트맵, 해시 테이블이 있습니다. 대개는 배열이 가장 단순한 접근법이지만, 밀도가 희박한 배열은 메모리를 낭비시킵니다. 리스트 또한 단순하지만, 특정 위치를 찾기 위해 긴 리스트를 순회하는 것은 시간을 소모합니다. 배열과 리스트 둘 다 크기의 재조정(resize)이 가능하지만, 중간 부분의 삽입과 삭제에 있어서는 리스트가 더 효율적입니다.

보조 페이지 테이블

페이지 테이블을 보조해서 페이지 폴트 핸들링이 가능하도록 해준다.

보조 페이지 테이블의 관리

보조 페이지 테이블은 각 페이지에 대한 추가 데이터를 이용해서 페이지 테이블을 보조합니다. 페이지 테이블의 포맷으로 인해 생기는 제한들 때문에 보조 페이지 테이블이 필요합니다. 이런 자료구조는 종종 “페이지 테이블”로도 불리는데, 저희는 혼란을 방지하기 위해서 “보조”라는 단어를 붙였습니다.

보조 페이지 테이블의 정의

아래의 보조 데이터들을 담고있는, 프로세스마다 존재하는 자료구조

• 각각의 페이지에 대해서 데이터가 존재하는 곳(frame, disk, swap 중 어디에 존재하는지)
• 이에 상응하는 커널 가상주소를 가리키는 포인터 정보
• active인지 inactive 인지 등

보조 페이지 테이블의 역할

• Page fault시 커널이 보조(supplement) 페이지 테이블에서 오류가 발생한 가상 페이지를 조회하여 어떤 데이터가 있어야 하는지를 확인할 필요가 있다.
• 프로세스가 종료될 때 커널이 추가 페이지 테이블을 참조하여 어떤 리소스를 free시킬 것인지를 결정한다.
• 어떤 pte(page-table entry)가 물리 주소를 가리키고 있는 상황에서 다른 pte도 같은 물리 주소를 가리킬 수 있다. why? 페이지 테이블은 pte마다 하나씩 가지고 있고 서로 다른 가상 주소를 갖지만 같은 물리 주소를 참조하는 경우가 충분히 발생할 수 있기 때문이다. 참조하는 테이블은 전부 다르지만 결국 같은 물리 주소를 가리키고 있는 것. 이러한 경우를 다루려면 하나의 프로세스가 어떤 물리 주소를 참조하는지에 대한 정보가 필요하기에 보조 페이지 테이블이 필요하다.
• 기존 페이지 테이블은 물리 주소를 향한 일방적인 pointing에 불과하다. 때문에 물리 주소의 값이 바뀌어 있으면 패닉이다 (페이지 교체, 페이지 테이블의 업데이트, 메모리 할당 및 해제 등의 이유로). 기존에 어떠한 데이터가 있는지에 대한 정보를 갖고 있지 않기에 문제가 발생한다. 보조 페이지 테이블에서는 원래 물리 주소에 들어가 있어야 할 데이터가 어떤 것인지에 대한 정보를 갖는다.

보조 페이지 테이블의 구조(에 접근하는 방법)

• 세그먼트 측면
  세그먼트는 연속된 페이지 그룹을 의미
  ex - 실행파일을 포함하는 메모리 영역이나, 메모리 매핑된 파일
• 페이지 측면

페이지 폴트 다루기

페이지 폴트 : CPU가 프로그램을 실행하면서 필요한 페이지가 물리적 메모리에 없는 경우도 생기게 되는데 이것을 페이지 폴트(Page Fault)라고 한다.

보조 페이지 테이블을 사용하는 핵심 유저는 바로 페이지 폴트 핸들러입니다. 프로젝트 2에서는, 페이지 폴트는 항상 커널 또는 유저 프로그램의 버그를 의미했습니다. 하지만 프로젝트 3에서는 더 이상 아닙니다. 이제 페이지 폴트는 파일 또는 스왑 슬롯에서 페이지를 가져와야 한다는 사실을 의미하게 됩니다. 이러한 경우들을 다루기 위해서는, 더 복잡한 페이지 폴트 핸들러를 구현해야 할 것입니다. userprog/exception.c에 있는 페이지 폴트 핸들러 page_fault()는 vm/vm.c 에 있는 당신의 페이지 폴트 핸들러 vm_try_handle_fault() 를 호출합니다.

당신의 페이지 폴트 핸들러가 해야 하는 일들을 대략적으로 설명하면 다음과 같습니다 :

1. 보조 페이지 테이블에서 폴트가 발생한 페이지를 찾습니다. 만일 메모리 참조가 유효하다면, 보조 페이지 엔트리를 사용해서 데이터가 들어갈 페이지를 찾으세요. 페이지는 파일 시스템에 있거나, 스왑 슬롯에 있거나, 또는 단순히 0으로만 이루어져야 할 수도 있습니다. 당신이 만약 Copy-on-Write와 같은 공유를 구현한다면, 페이지의 데이터는 이미 페이지 테이블에 없고 페이지 프레임에 들어가 있을 것입니다. 만약 보조 페이지 테이블이 다음과 같은 정보를 보여주고 있다면 - 유저 프로세스가 접근하려던 주소에서 데이터를 얻을 수 없거나, 페이지가 커널 가상 메모리 영역에 존재하거나, 읽기 전용 페이지에 대해 쓰기를 시도하는 상황 - 그건 유효하지 않은 접근이란 뜻입니다. 유효하지 않은 접근은 프로세스를 종료시키고 프로세스의 모든 자원을 해제합니다.

   메모리 참조가 유효하다면 -> 유저 가상메모리의 모습을 생각하면 heap은 아래에서 위로, stack은 위에서 아래로 커지는 것을 떠올릴 수 있을 것입니다. 이는 스택과 힙이 충분히 자라지 않은 경우 스택과 힙 사이에는 사용되지 않는 영역들이 존재한다는 말입니다. 이 사용되지 않는 영역을 참조하는 경우 ‘메모리 참조가 유효하지 않다’고 표현합니다.

   공유 : 여러개의 페이지가 한 물리 주소를 맵핑하여 그 프레임을 공유하는 것.

2. 페이지를 저장하기 위해 프레임을 획득합니다. 만일 당신이 공유를 구현한다면, 필요한 데이터는 이미 프레임 안에 있을 겁니다. 이 경우 해당 프레임을 찾을 수 있어야 합니다.

3. 데이터를 파일 시스템이나 스왑에서 읽어오거나, 0으로 초기화하는 등의 방식으로 만들어서 프레임으로 가져옵니다. 공유를 구현한다면, 필요한 페이지가 이미 프레임 안에 있기 때문에 지금 단계에서는 별다른 조치가 필요하지 않습니다.

4. 폴트가 발생한 가상주소에 대한 페이지 테이블 엔트리가 물리 페이지를 가리키도록 지정합니다. threads/mmu.c 에 있는 함수를 사용할 수 있습니다.

기타

한 페이지의 스택이 가득 차면(혹은 여러 이유에서) 새로운 페이지가 발급이 된다. 이 때, 이전 페이지는 다음 페이지를 가리키는 포인터 변수를 담게 된다. 즉, 이전 페이지는 사용 가능한 페이지를 찾아갈 수 있게 해주는 보조 테이블의 역할을 하게 된다.

프레임 페이지 테이블

프레임 테이블에는 각 프레임의 엔트리 정보가 담겨 있다. 프레임 테이블의 각 엔트리에는 현재 해당 엔트리를 차지하고 있는 페이지에 대한 포인터(있는 경우라면), 그리고 당신의 선택에 따라 넣을 수 있는 기타 데이터들이 담겨 있다.

프레임 테이블에서 가장 중요한 작업은 사용되지 않은 프레임을 획득하는 것입니다. 이는 프레임이 free 상태라면 간단한 일입니다.
하지만 비어있는(free 상태의) 프레임이 없을 때 쫓아낼 페이지를 골라줌으로써, Pintos가 효율적으로 eviction policy를 구현할 수 있도록 해줍니다.

유저 페이지를 위해 사용된 프레임들은 palloc_get_page(PAL_USER) 를 호출함으로써 유저 풀에서 획득된 것이어야 합니다. 커널 풀에서 할당했다가 예상치 못하게 테스트 케이스에서 실패하는 일을 막기 위해서는, 반드시 PAL_USER 를 사용하여야 합니다.

eviction 절차 (구현 할 것들)

1. 당신의 페이지 재배치 알고리즘을 이용하여, 쫓아낼 프레임을 고릅니다. 아래에서 설명할 “accessed”, “dirty” 비트들(페이지 테이블에 있는)이 유용할 것입니다.

2. 해당 프레임을 참조하는 모든 페이지 테이블에서 참조를 제거합니다. 공유를 구현하지 않았을 경우, 해당 프레임을 참조하는 페이지는 항상 한 개만 존재해야 합니다.

3. 필요하다면, 페이지를 파일 시스템이나 스왑에 write 합니다. 쫓아내어진(evicted) 프레임은 이제 다른 페이지를 저장하는 데에 사용할 수 있습니다.

accessed and dirty bits

x86-64 하드웨어는 각 페이지의 페이지 테이블 엔트리(PTE)에 있는 비트쌍을 통해 페이지 재배치 알고리즘 구현을 위한 도움을 제공합니다.

1. accessed
   페이지에 read 하거나 write 할 때, CPU는 페이지의 PTE에 있는 accessed 비트를 1로 설정합니다.
   즉, 접근된 적이 있냐를 판단하는 기준이 됩니다.

2. dirty
   write 할 때 CPU는 dirty 비트를 1로 설정합니다. CPU는 절대 이 비트들을 0으로 되돌리지 않고, 대신 OS가 되돌릴 수 있습니다.
   즉, 한번이라도 write 된 적이 있냐를 판단하는 기준이 됩니다.

같은 프레임을 참조하는 두 개 (또는 그 이상)의 페이지들인 aliases 를 조심해야 합니다. aliased 프레임이 accessed 될 때, accessed와 dirty 비트는 하나의 페이지 테이블 엔트리에서만 업데이트됩니다 (access에 쓰인 페이지에서만). 다른 alias들에 대한 accessed와 dirty 비트는 업데이트 되지 않습니다.

스왑 테이블

스왑 테이블은 사용중인 스왑 슬롯과 빈 스왑 슬롯들을 추적합니다. 프레임에 있는 페이지를 스왑 파티션으로 쫓아내기 위해서, 스왑 테이블은 미사용된 스왑 슬롯을 고를 수 있도록 해줘야 합니다. 페이지가 다시 읽혀서 돌아가거나, 페이지 주인인 프로세스가 종료되어 버릴 경우에는 스왑 테이블이 스왑 슬롯을 free 해줄 수도 있어야 합니다.