[SW정글 73일차] pintos project3 VIRTUAL MEMORY의 시작

Running a user program의 큰그림을 그려보자

물리 메모리가 제한되어 있지만 많은 프로세스가 물리적 메모리를 사용하려한다. 물리적 메모리는 모든 프로세스의 페이지를 항상 저장할 만큼 크지 않은데 말이다.
해서 물리 메모리에 페이지가 필요하지 않으면 페이지를 "paged out"시킨다. 해당 페이지는 swap table 또는 file system에 기록한다.
반면, 프로세스에 페이지가 필요하고 물리 메모리에 없는 경우, 프로세스는 "paged in"한다.
이러한 방식으로 한정적인 물리 메모리를 운영할 것이다.

이번 proejct3 : VM 에서 생각해봐야할 것은

• Supplemental page table
• 물리 메모리 frame 관리
• lazy loading을 위한 page fault handler 수정 (demand paging)
• Stack growth, file-maped etc
• mmap, munmap
• Swap in/out

Terminology (용어)

• Page : 가상 메모리의 인접 영역
• Frame : 물리 메모리의 인접 영역
• Page table : 가상 주소를 물리적 주소로 변환하는 데이터 구조(페이지를 프레임으로)
• Eviction : 프레임에서 페이지를 제거하고 스왑 테이블 또는 파일 시스템에 페이지를 쓸 수 있음
• swap table : 스왑 파티션에서 제거된 페이지가 기록되는 위치

Data structures you must design (우리가 해야할 일 🙃)

1. Supplemental page table: 데이터 위치(프레임/디스크/스왑), 해당 커널 가상 주소로의 ptr, 활성/비활성 등 각 페이지에 대한 보조 데이터를 추적하는 프로세스별 데이터 구조이다.
2. Frame table: 할당(allocated)/사용 가능한(free) 물리적 프레임을 추적하는 global data structure
3. Swap table: swap table 은 사용 중인 swap slot 과 사용 가능한 swap slot을 추적한다. read back 하거나 스왑된 프로세스가 종료될 때 swap slot을 비울 수 있어야한다.
4. File mapping table: 어떤 memory-mapped files이 어떤 페이지에 매핑되는지 추적한다.

data structures 중에 맘껏 골라골라-

• Arrays : 가장 단순한 접근 방식이나, 드문드문 채워진 array는 메모리를 낭비한다.
• Lists : 매우 간단하지만 list 통과하는데 많은 시간 걸릴 수 있다.
• Bitmaps : 각각 참 또는 거짓이 될 수 있는 비트 배열로, 동일한 리소스 집합에서 사용률 추적한다. 기본적으로 핀토스 비트맵은 사이즈가 고정되어 있다. (lib/kernel/bitmap.[ch])
• Hash Tables : 넓은 범위의 테이블 사이즈에 대해 효율적으로 삽입과 삭제를 지원한다. (lib/kernel/hash.[ch])

Concept of lazy loading

• 가상 주소가 생성될 때(mmap), 핀토스는 struct page 를 가상 주소에 연결합니다.
• 각 가상 주소는 서로 다른 용도로 사용 ; anonymous memory, file-backed memory
  • struct page 는 정보를 반영한다. (struct page 위로 이동)
  • struct page 를 할당한다고 해서 가상 주소에 물리적 프레임이 할당되는 것은 아니다.

시작점

Struct page and page_operations

Q 프레임이 할당된 후 프레임의 내용을 어떻게 채울까?

페이지는 처음에 uninit_page로 시작하고,
anonymous memory 페이지는 anon_initializer되고
file-backed memory 페이지는 file_map_initializer된다.

Supplemental Page Table

• 각 page에 대한 추가 정보로 page table을 보완한다.
• spt_find_page: spt와 가상 주소에서 struct page 찾기

2가지 목적

1. page fault시, 커널은 supplemental page table에서 가상 페이지를 검색하여 어떤 데이터가 어디에 있어야 하는지를 찾는다.
2. 프로세스가 종료되면 커널은 어떤 자원을 해제할지 결정한다.

Frame Table

Q. 모든 frame이 가득 찬 경우 페이지를 저장할 frame을 어떻게 얻을 수 있을까?

A. frame table에 의해 관리하여 제거한다.

• 페이지 교체 알고리즘은 LRU에 가까워야하며 적어도 clock algorithm만큼 잘 수행해야한다.
• vm_get_messages
• user pages의 frame만 관리한다. (PAL_USER)

Q. 페이지를 어떻게 제거할까?

A.
1) 페이지 교체 알고리즘을 사용하여 제거할 프레임을 선택한다.

2) frame을 참조하는 페이지 테이블을 제거한다. (only multiple references if implementing extra credit)

3) 필요한 경우, 파일 시스템에 페이지를 쓰거나 스왑한다.

CPU에서 설정한 accessed와 dirty bit를 활용한다.

Swap Table

• 사용 중인 스왑 슬롯과 사용 가능한 스왑 슬롯을 추적한다.
• 프레임에서 스왑 파티션으로 페이지를 제거하기 위해 사용되지 않는 스왑 슬롯을 선택한다.
• page를 read back 하거나 프로세스가 종료될 때 스왑 슬롯 해제한다.

Stack Growth

• 프로젝트 2: 사용자 프로세스 스택에 공간을 미리 할당했다면
• 프로젝트 3: 필요에 따라 프로세스 스택에 더 많은 페이지를 동적으로 할당한다.
• 이제 유효한 stack 접근으로 인해 page fault가 발생할 수 있습니다!
• 유효한 stack 접근인 경우, page fault handler에 새 page를 할당한다.
• struct intr_frame으로부터 %rsp 를 가져와 page_fault()에 전달하기!

Memory Mapped Files

• mmap() and munmap()
• 프로세스가 파일을 주소 공간에 매핑할 수 있다. 메모리 매핑된 페이지는 디스크에서 lazy load되어야 한다.
• mmap()은 다음과 같은 경우 오류 상태를 반환:
  • 파일 크기가 0바이트
  • 파일이 이미 매핑된 다른 페이지와 겹친다.
  • addr는 page aligned이 아니다.
• 너가 mmap된 page를 삭제할 때, 변경 내용을 원래 파일로 다시 쓴다.
• 프로세스 종료 시 모든 매핑이 암시적으로 매핑 해제된다.

---

추가 개념 정리

lazy loading

쉽게 말하면 게으른 로딩, 지연된 로딩으로 페이지를 읽어들이는 시점에 중요하지 않은 리소스 로딩을 추후에 하는 기술이다. 이 중요하지 않은 리소스들은 필요할 때 로드가 되야한다.

이는 예시로 이해가 더 쉬웠는데, 웹페이지 사용시 전체 페이지의 내용이 다운되어 랜더링된다. 이를 통해 브라우저는 웹페이지를 캐시할 수 있지만 사용자가 다운한 모든 콘텐츠를 실제로 볼 수 있다는 보장은 없다.
만약 전체 파일을 다운로드했지만 사용자가 첫번째 파일만 보고 떠난다면 웹페이지에서는 메모리 및 대역폭 낭비가 발생한다. 이런 낭비를 줄이기 위해 페이지에 접근할 때 모든 콘텐츠를 대량 로드하는 대신 사용자가 필요한 페이지의 일부에 접근할 때 콘텐츠를 load할 수 있게 하는 것이다.

demand paging

요구 페이징이란 가상 메모리 관리 방법으로, 프로세스에서 사용할 메모리 페이지를 프로세스 생성 시에 모두 할당하지 않고, 필요할 때마다 동적으로 할당하는 것이다.

demand paging의 목적은 물리 메모리와 swap device 사이의 데이터 전송을 최소한으로 하기 위함이다. 좋은 MMU(메모리 관리 장치로, 가상 메모리 주소를 실제 메모리 주소로 변환하며, 메모리 보호, 캐시 관리, 버스 중재 등의 역할) 메커니즘을 가지고 있어도 (대전 문지캠 내에서 해결해도 되는 문제인데) 그것을 운영하는 Policy가 좋지 않으면 매번 서울을 갔다와야 하는 문제가 발생할 수 있다. 생각만 해도 피곤하다.🥶

서울을 다녀오는 상황을 Thrashing이라고 한다. 고로 demand paging을 잘하는 것이 문지캠 내에서 해결하냐? 서울까지 다녀와야 하느냐?의 문제로 귀결된다고 보면 된다.

virtual address space는 실제 컴퓨터가 작은 물리 메모리를 가지고 있어서 자기보다 훨 큰 user program을 받아들일 수 있다. 존재하지 않은 물리 메모리를 표현하지만, 완전히 없는 것을 제공할 수 없으니 물리 메모리의 부족한 부분은 swap device에 보내 채우는 것이다.

고로 우리의 바람은 virtual address가 physical address로 변환이 될 때, swap device보다 RAM에 들어가는 것. 즉, swap device를 access해야 되는 횟수를 가장 최대한 줄이는 것이다.

이상적인 방법은 앞으로 사용될 페이지와 사용되지 않을 페이지를 미리 알아서 물리 메모리로 불러들이거나 swap device로 내보내는 것이다.

고려해볼 점은
1. 어떤 페이지를 언제 물리 메모리로 올릴까 (Page Selection Policy)
2. 물리 메모리에 frame이 부족해 누굴 제거하고(victim) swap device에 보낼지 (Page replacement Policy)

Thrashing

프로세스들이 사용하는 Page들의 크기보다 사용 가능한 물리 메모리의 크기가 작을 때, 사용하기 위해 Swap-in 하는 Page에 의해 앞으로 사용할 Page가 Swap-out되면서 반복적으로 page fault가 일어나는 현상을 말한다.

page fault handler

Virtual Address reference하려 하는데 타켓 페이지가 resident하지 않아(메모리에 올라와 있지 않아) 더 이상 수행할 수 없을 때 page fault라고 하는 S/W interrupt를 발생시킨다.

이제 page fault handler가 발생하면 그 fault를 만든 프로세스의 수행은 중단 시키게 된다. 그리고 중단한 애의 context를 전부 저장하며 block상태로 가게 된다.

page fault handler는 DMA controller에게 해당 페이지의 주소를 던져주고 DMA를 시작한다. swap device에서 physical memory 싸악- 페이지를 읽어들일 것이다.

1. DMA Controller에게 해당 Page의 주소를 전달
2. DMA Controller는 해당 Page를 물리 메모리에 로드
3. DMA Controller의 작업이 끝나면 인터럽트 발생
4. 운영체제는 page fault를 일으킨 프로세스의 수행을 재개

DMA controller 관련 그림은 이전에 포스팅했던 hello 프로그램을 실행할 때 무슨 일이 일어나요? 에서 볼 수 있다.

참고자료 Pintos_lab3_slide

---

오늘의 나는

오랜만에 아침 운동을 했더니 잠이 다 깨고 너무 개운해서 하루 컨디션이 좋았다.🏋🏻‍♀️

정글에서 제공해준 공식문서 깃북과 권영진 교수님의 카이스트 ppt, pintos 코드에 적혀있는 todolist를 해석해보고 진행할 수 있도록 같은 속도로 함께 해주는 팀원들에게 고맙다.