[정글] WEEK 11-12 | 대충 핀토스 지겹다는 제목

Subject	Done
스레드	✔
사용자 프로그램	✔
가상 메모리	✔
파일 시스템

 

📌 프로젝트 이해하기

Introduction

• 지금까지 적절한 동기화를 통해 멀티 스레드 처리, 여러 사용자 프로그램 로드 가능했음
• 하지만 실행 가능한 프로그램의 수와 크기는 시스템의 주 메모리 크기에 의해 제한됨
• 프로젝트 3에서는 무한 메모리를 구축하여 이러한 제한을 제거하도록 하는 것이 목표

Word	Same Word	Description
Page	Virtual Page	길이가 4096 바이트인 가상 메모리의 연속적인 영역
Frame	Physical Frame, Page Frame	물리 메모리의 연속적인 영역
Offset	Page Offset	64 비트 가상 주소의 마지막 12 비트

 

Pages

• 페이지는 반드시 page-aligned여야 함, 페이지 크기로 균등하게 나눌 수 있는 가상 주소에서 시작해야 함
• 상위 비트는 페이지 테이블의 인덱스를 나타내는 데 사용됨
• 64비트 시스템에서는 가상 주소를 다음과 같이 4단계 페이지 테이블을 사용하여 생성
• 각 프로세스는 유저 가상 페이지들이 존재, 커널 가상 페이지들은 전역적이므로 실행 중인 스레드나 프로세스에 관계 없이 동일한 위치에 유지됨
• 유저 프로세스는 자신의 유저 페이지에만 접근 가능, 커널은 유저 페이지와 커널 페이지 모두 접근 가능

63          48 47            39 38            30 29            21 20         12 11         0
+-------------+----------------+----------------+----------------+-------------+------------+
| Sign Extend |    Page-Map    | Page-Directory | Page-directory |  Page-Table |    Page    |
|             | Level-4 Offset |    Pointer     |     Offset     |   Offset    |   Offset   |
+-------------+----------------+----------------+----------------+-------------+------------+
              |                |                |                |             |            |
              +------- 9 ------+------- 9 ------+------- 9 ------+----- 9 -----+---- 12 ----+
                                          Virtual Address

 

Frames

• 프레임 또한 반드시 page-size 그리고 page-aligned여야 함
• 지금부터 커널 가상 메모리를 물리 메모리에 직접 매핑해야 함
• 커널 가상 메모리의 첫 페이지는 물리 메모리의 첫번째 프레임에 매핑, 두번째 페이지는 두번째 프레임에 매핑됨
• 따라서 커널 가상 메모리를 통해 프레임에 접근 가능

                        12 11         0
+-----------------------+-----------+
|      Frame Number     |   Offset  |
+-----------------------+-----------+
            Physical Address

 

Page Tables

• CPU가 가상 주소를 물리 주소로, 즉 페이지에서 프레임으로 변환하는 데 사용되는 데이터 구조
• 왼쪽 가상 주소는 페이지 번호와 오프셋으로 이루어짐
• 페이지 테이블은 페이지 번호와 수정되지 않은 오프셋과 결합, 오른쪽 물리 주소를 얻을 수 있는 프레임 번호로 변환

                          +----------+
         .--------------->|Page Table|-----------.
        /                 +----------+            |
        |   12 11 0                               V  12 11 0
    +---------+----+                         +---------+----+
    | Page Nr | Ofs|                         |Frame Nr | Ofs|
    +---------+----+                         +---------+----+
     Virt Addr   |                            Phys Addr    ^
                  \_______________________________________/

 

Swap Slots

• Swap Slot - 스왑 파티션에 있는 디스크 공간의 페이지 크기 영역
• 슬롯 배치를 결정하는 하드웨어 제한이 프레임보다 유연, 페이지 정렬 필요

 

Resource Management Overview

• Supplemental page table - Page table 보완용, Page fault handling 처리
• Frame table - 물리 프레임의 제거 룰을 효율적으로 구현 가능하게 함
• Swap table - 스왑 슬롯의 사용을 추적 가능하게 함

 

📌 자료 구조 선택

구현 시 배열, 리스트, 배트맵, 해시 테이블로 구현 가능하다. 어떤 걸 사용할 것인가?

배열

• 가장 간단한 접근 방식, 하지만 빈도가 낮을 경우 메모리를 낭비할 수 있음

 

리스트

• 간단하지만 특정 위치를 찾기 위해 긴 목록을 탐색하면 시간이 낭비됨
• 배열과 리스트 모두 크기를 조정할 수 있지만 리스트가 중간 삽입 및 삭제를 더 효율적으로 지원함

 

비트맵

• 비트맵은 True or False가 될 수 있는 비트의 배열, 일반적으로 리소스 집합에서 사용량을 추적하는 데 사용됨
• 예를 들어 리소스 n이 사용 중일 경우, 비트맵의 비트 n은 참으로 표시함

해시 테이블

• 다양한 테이블 크기에서 삽입 및 삭제를 효율적으로 지원

Managing the Supplemental Page Table
1) Supplemental Page Table

• 각 페이지에 대한 추가 데이터, Page Table을 보완해주는 역할
• Page fault 시 커널이 SPT에서 fault가 발생한 페이지를 조회하여 어떤 데이터가 있어야 하는지 알아낼 수 있음
• 프로세스가 종료될 때 커널은 SPT를 참조하여 해제할 리소스를 결정함

 

2) Organization of Supplemental Page Table

• Segment 측면 : 연속적인 페이지 그룹, 즉 실행 파일 또는 메모리 매핑 파일을 포함하는 메모리 영역 (권장)
• Page 측면 : 선택적으로 Page Table 자체를 사용하여 추가 페이지 테이블의 구성원을 추적할 수 있음

 

3) Handling page fault

• SPT의 가장 중요한 사용자는 Page fault handler
• 지금부터 Page fault는 파일 또는 스왑 슬롯에서 페이지를 가져와야 함을 의미
• exception.c의 page_fault()는 vm_try_handle_fault()를 호출함

 

Managing the Frame Table

• Frame Table은 각 프레임에 대해 하나의 엔트리를 포함
• 각 엔트리에는 현재 이를 차지하고 있는 페이지에 대한 포인터와 기타 데이터가 포함되어 있음
• 빈 프레임이 없을 때, 제거할 페이지를 선택할 때 효율적으로 구현 가능하게 함
• 사용 가능한 페이지가 없으면 프레임에서 일부 페이지를 제거하여 사용 가능한 프레임을 만들어야 함
• 사용자 페이지에 사용되는 프레임은 palloc_get_page(PAL_USER)를 통해 User pool에서 가져와야 함
• 스왑 슬롯을 할당하지 않고 프레임을 제거할 수 없음, 스왑이 가득차면 커널을 패닉 상태로 만들게 됨

 

The process of eviction

1. 페이지 교체 알고리즘을 이용하여 내보낼 프레임 선택, "accessed"나 "dirty" 비트가 유용하게 사용됨
2. 해당 프레임을 참조하는 모든 페이지 테이블에서 참고를 제거, 공유를 구현하지 않았다면 단일 페이지에서만
3. 필요한 경우 페이지를 파일 시스템에 쓰거나 스왑함, 제거된 프레임은 다른 페이지를 저장하는 데 사용됨

 

Accessed and Dirty Bits

• CPU는 페이지에 대한 Read or Write 시 accessed 비트를 1로 설정, Write 시 dirty 비트는 1로 설정
• 동일한 프레임을 참조하는 두 개 이상의 페이지를 알고 있어야 함
• aliased된 프레임에 액세스하면 accessed 비트와 dirty 비트는 하나의 페이지 테이블 엔트리에 대해서만 (액세스에 사용된 페이지에 대한 엔트리) 업데이트됨, 다른 엔트리들은 업데이트되지 않음
• 모든 유저 가상 페이지는 커널 가상 페이지에 aliase가 지정됨, 이 aliase들을 관리해야 함
• 다른 aliase는 공유를 구현하거나 코드에 버그가 있는 경우에만 발생됨

 

Managing the Swap Table

• Swap table을 통해 사용 중이거나 사용 가능한 스왑 슬롯 추적 가능
• 프레임에서 스왑 파티션으로 페이지를 내보내기 위해 사용하지 않은 스왑 슬롯을 선택할 수 있어야 함
• 페이지를 다시 읽거나 스왑된 프로세스가 종료될 때 교체 슬롯을 해제할 수 있어야 함
• 스왑 슬롯은 실제로 필요할 때만 (lazy하게) 할당되어야 함
• 실행 파일에서 데이터 페이지를 읽고 프로세스 시작 즉시 스왑에 쓰는 것은 올바르지 않음
• 특정 페이지를 저장하기 위해 스왑 슬롯을 예약하면 안됨
• 내용을 프레임으로 다시 읽을 때 스왑 슬롯을 해제해야 함

 

Managing Memory Mapped Files

• 파일 시스템은 Read/Write 시스템콜을 통해 가장 일반적으로 액세스됨
• mmap 시스템콜을 사용하여 파일을 가상 페이지로 매핑함
• 그러면 프로그램은 파일 데이터에서 직접 메모리 명령을 사용할 수 있음
• 아래 프로그램은 명령줄에 지정된 파일을 열고 가상 주소 0x10000000에 매핑한 다음, 매핑된 데이터를 콘솔에 쓰고(fd 1), 파일 매핑을 해제함
• 제출물은 메모리 매핑된 파일이 사용하는 메모리를 추적할 수 있어야 함

#include <stdio.h>
#include <syscall.h>
int main (int argc UNUSED, char *argv[])
{
  void *data = (void *) 0x10000000;                 /* Address at which to map. */
  int fd = open (argv[1]);                          /* Open file. */
  void *map = mmap (data, filesize (fd), 0, fd, 0); /* Map file. */
  write (1, data, filesize (fd));                   /* Write file to console. */
  munmap (map);                                     /* Unmap file (optional). */
  return 0;
}

 

📌 프로젝트 파고들기

Todo	Done
Memory Management	✔
Anonymous Page	✔
Stack Growth	✔
Memory Mapped Files	✔
Swap In/Out	✔
Copy on Write

 

1. Memory Management

• 가상 메모리 시스템을 지원하려면 Virtual Page와 Physical Frame을 효과적으로 관리해야 함
• 즉 어떤 메모리 영역이 어떤 목적으로, 누구에 의해, 사용되고 있는지 관리해야 함
• 먼저 Supplemental Page Table을 다룬 다음 Physical Frame을 다룰 예정

  

  가상 메모리와 물리 메모리의 관계

 

2. Anonymous Page

• Anonymous page라는 디스크 기반이 아닌 이미지를 구현함
• Anonymous mapping에는 backing file이나 device가 없음, File-backed page와 달리 이름이 지정된 파일 소스가 없기 때문에 'Anonymous'라고 함
• Anonymous page는 스택 및 힙과 같은 실행 파일에 사용됨
• anon.h의 anon_page는 Anonymous page를 설명하는 구조체이며 현재 비어있으므로 구현해야 함
• vm.h의 page 구조체를 참조, 예를 들어 Anonymous page일 경우 해당 구조체에 anon_page anon이 포함되어 있음을 확인

 

3. Stack Growth

• 기존에는 단일 페이지였으며, 프로그램 실행은 USER_STACK 크기로 제한되었음
• 이제 Stack이 현재 설정 크기보다 커지면 필요에 따라 추가 페이지를 할당하도록 함
• 스택 액세스로 보이는 경우에만 추가 페이지 할당, 즉 스택 액세스와 다른 액세스를 구분할 수 있는 방법을 고안
• 사용자 프로그램이 스택 포인터보다 아래의 스택에 쓰게 되면 버그
• PUSH 명령어는 스택 포인터를 조정하기 전에 액세스 권한을 확인하므로 스택 포인터 8바이트 아래에서 페이지 오류가 발생할 수 있음
• 사용자 프로그램의 스택 포인터의 현재값을 얻을 수 있어야 함
• syscall_handler() 또는 page_fault()로 전달된 구조체 intr_frame의 rsp 멤버에서 해당 값을 검색 가능

 

4. Memory Mapped Files

• 메모리 매핑 페이지 구현, 익명 페이지와 달리 메모리 매핑 페이지는 파일 기반 매핑
• 페이지의 내용은 일부 기존 파일의 데이터를 미러링함
• 페이지 오류가 발생하면 즉시 물리적 프레임이 할당되고 내용이 파일에서 메모리로 복사됨
• 메모리 매핑된 페이지가 매핑 해제되거나 교체되면 콘텐츠의 모든 변경 사항이 파일에 반영됨

 

5. Swap In/Out

• 메모리 스와핑은 물리 메모리 사용을 최대화하기 위한 메모리 회수 기술
• 주 메모리의 프레임이 할당되면 시스템은 사용자 프로그램의 메모리 할당 요청을 더 이상 처리할 수 없음
• 그래서 현재 디스크에 사용되지 않는 메모리 프레임을 교체하면 됨
• 메모리가 부족한 상태에서 메모리 할당 요청을 받으면, 스왑 디스크로 제거할 페이지를 선택함
• Eviction될 페이지로 선택된 페이지는 anonymous page 이거나 file-backed page일 수 있음, 따로 처리해야 함