컴퓨터 시스템/OS [WIL] 컴퓨터 운영체제 ' Virtual memory ' (pintos project 3)
Campkim2021. 10. 28. 04:13
회고 및 잡설
OS 강의평가
Pintos 초기에는 어려운 난이도와 디버그의 빡침을 못참고 혼자 샤우팅을 하곤했다. 한달 정도 지나니 난이도에 어느정도 적응하고 무언가 잘 되지 않더라도 내면의 분노를 다스리는 것을 넘어서 이제는 감정에 무뎌진 나를 발견했다.
이번주차에 진행된 Pintos project는 Virtual memory에 대한 내용이다. 책으로 처음 접했을 때 와닿지 않았던 부분들을 이해할 수 있는 뜻깊은 시간이다. 1, 2주차와 마찬가지로 책에서 관련내용을 읽고 처음에 상황을 이해하는데 초반 몇 일을 소모했다.
많이 어려웠지만 늘 그랬듯이 시간을 갈아넣어서 그래도 많은 공부가된 것 같다.
아직도 배워야 할 것들이 너무 많기 때문에 핀토스 메뉴얼이나 개념 설명글을 작성하는데에 시간을 많이 쓰고 싶지 않다.
단지 어렵게 배운 만큼 깨달은 내용을 잊고 싶지 않을 뿐이다. 이 글은 깨닳은 내용을 정리하고 나중에 잊었을때 다시 보기 위한 목적이다. 자세한 개념 설명은 인터넷의 다른 블로그나 책에 더 자세히 나와있기 때문에 키워드 위주로 정리하려고 한다.
PINTOS week 3 수행과제 및 학습내용 - 'Virtual Memory'
Virtual memory 구현에 필요한 자료구조를 이해하고 적용한다. (hash table / linked list .. )
효율적인 메모리 사용을 위해 Demand paging에 대해 학습하고, pintos에 구현한다. 1~2주차 Thread / User program까지는 PintOS에는 Demand phasing 이 구현되어 있지 않고, 물리메모리에 프로세스 진행에 필요한 모든 메모리가 맵핑되어 있었다.
System call fork ( ) / exec ( ) 함수 실행시 Virtual memory가 어떻게 변하는지 이해한다.
Anonymous / File mapped page에 대해 학습하고 관련 함수들을 구현한다. 가상메모리의 page와 물리메모리의 frame 에 대해 이해한다.
초기 프로세스 스택 셋업 방식과 Stack growth를 이해하고 구현한다.
System call mmap / munmap을 통한 파일 접근과 open ( ), read ( ), write( ) 를 통한 파일접근의 차이점을 이해한다.
64 bit 기반의 X86/64, linux, Pintos에서 사용되는 Multi level page table.
Vitual address ( = logical address)를 physical address 주소변환에 페이지 테이블이 이용된다. 가상 메모리는 프로세스가 메모리의 모든 공간을 독점적으로 사용하는 듯한 환상을 심어준다.단순한 구조의 페이지 테이블을 사용하면 모든 공간에 대한 주소 맵핑이 되어야하고 따라서 페이지 테이블의 사이즈가 너무 크게 된다는 문제 점있다.문제 해결을 위해서 포인터를 활용한 트리구조의 페이지 테이블이 채택되었다. 이것이 다중레벨 페이지 테이블이다. 이런 구조를 사용하면 힙과 스택사이공간처럼 미할당 영역에 대한 주소공간은 매핑을 유예할 수 있기 때문에 메모리 관리에 유리하다.
TLB = Translation Lookaside Buffer ( CSAPP 9.6 )
주소번역 하드웨어인 MMU 내부에 있는 작은cache.
그냥 캐시라고 이해하면 된다. 각 라인에 PTE의 일부분을 캐시하고 있다. 이 쪼만한 캐시가 주소 번역 과정을 매우 빠르게 만든다.
TLB의 장점은 TLB가 없거나 TLB 미스가 났을 때 주소번역 과정을 생각하면 된다.
Cache hit을 하더라도, 메모리에 2번 접근해야하는 비효율이 있다. TLB hit이 된다면 mmu에서 TLB를 이용해 자체적으로 Physical address로 주소변환을 하는 것같은 효과가 있다.
Pintos에서는 Virtual memory 이미지, data를 저장하는 방식으로 Thread마다 supplemetary table 이라는 자료구조를 가지고있는데, 이 supplementary tale을 hash table로 구현해야 했다.
hash 함수는 Pintos에 필요한 수준으로만 이해했다.
핵심은 해시 함수를 이용하여 인덱스 변환을 하는 자료구조로 시간복잡도가 O(1)이라는 점이다.
해쉬 함수의 종류는 여러가지가 있으며 아직도 연구되고 있는 분야같다.
처음에 이 개념을 접했을때, Key에 대응하는 Index의 집합 전체 사이즈가 다를텐데 어떻게 모두 대응되지? 라는 의문이 생겼다. 정답은 대응될 수 없다는 것이었다. 2개 이상의 키가 특정 인덱스 하나에 대응되는 상황이해쉬충돌이라는 개념으로 정의되어 있었다. 해쉬충돌을 해결하는 방법에는 여러가지가 있는 것으로 알고있다. Pintos에 구현된 방법으로는, bucket에 linked list 형식으로 뒤로 붙인다.
Hash find 함수에서는 bucket을 찾는데 시간복잡도 O(1)이 들고, 추가적으로 bucket내의 원소의 개수를 m이라고할 때, O(m)만큼만의 시간복잡도를 더 하여 table내 원소를 참조했다.
해시 테이블은(Key, Value)로 데이터를 저장하는 자료구조중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.
예를 들어 우리가 (Key, Value)가 ("John Smith", "521-1234")인 데이터를 크기가 16인 해시 테이블에 저장한다고 하자. 그러면 먼저 index = hash_function("John Smith") % 16 연산을 통해 index 값을 계산한다. 그리고 array[index] = "521-1234" 로 전화번호를 저장하게 된다.
어라훈 구조로 데이터를 저장하면 Key값으로 데이터를 찾을 때 해시 함수를 1번만 수행하면 되므로 매우 빠르게 데이터를 저장/삭제/조회할 수 있다.해시테이블의 평균 시간복잡도는 O(1)이다.
1. 초기 프로그램 실행시 process_exec의 load_segment 부분에서 Disk의 file로부터 필요한 data를 곧바로 physical memory에 적재하지 않고 file, offset, readbyte와 같은 data loading에 필요한 정보들만 page에 저장한뒤, SPT table에 page를 insert한다. (만일 running time에 mmap 과 같은 시스템콜이 실행되어도 동일하게 spt table에만 추가를 해둔다. 물론 page에 필수적인 정보는 담아서 추가한다. file_backed page라는점, file, offset 등)
2. 실제 물리적 접근이 이루어지면 프로세서는 virtual address에 필요한 data가 없음을 확인하고 page fault가 발생하게된다. (이때 해당 vaddr은 pml4에 install되어 있지도 않음)
3. Page fault handler로 제어가 넘어가고 vm_try_handler 가 실행되며 이어지는 흐름에서 vaddr에 대하여 검증하고, 문제가 없다면 physical frame을 할당받고, disk로부터 적합한 data를 load하여 메모리에 적재한다.
Demand paging은 멀티 프로세싱에서 한정된 물리메모리를 효율적으로 사용하기 위한 방법이다. Pintos내에서 기존에 구현되어 있는 load_segment 함수를 수정하여 구현했다.
기존 1~2주차까지 Pintos에서는 process exec과정에서 load (file, .. ) 함수에서 Disk의 file 데이터를 pml4, 가상주소와 물리주소에 맵핑하는 시점에 물리메모리에 실행에 필요한 실제 데이터를 모두 다 load 했다.
Demand paging은 문자 그대로 프로그램 러닝타임에 실제 해당 virtual address에 대응되는 데이터의 demand가 있을때, disk로부터 물리메모리에 적재(swap-in)하는 기법이다.
Demand paging의 핵심은 가상메모리에 page를 할당하는 시점과 물리메모리에 메모리를 실제 load하는 시점을 분리한 것이다. 프로세스는 메모리를 독점적으로 사용하고 있고, 프로그램 실행에 필요한 모든 데이터가 물리메모리에 이미 있는 것 처럼 행동한다. 프로세스가 메모리에 접근을 시도하는 시점에 page fault가 나고 page fault handler에 의해 필요한 data가 load 된다.
Page에는 Type이 있고, Type별로 demand phasing을 구현하는 방식이 조금씩 다르다.
ANONYMOUS PAGE, FILE BACKED PAGE 두가지 type의 페이지가 있는데, DISK에 파일의 실체가 있고, 해당 파일을 가상메모리에 맵핑한 페이지는 file backed page로 분류된다.
그렇지 않고 커널에 의해 running time혹은 file load 초기에 할당받은 페이지는 anonymous page로 분류된다.
따라서 DISK로 다시 SWAP-OUT 할 때, Consistency에 대해 신경써줘야 한다.
MMU는 특정 주소에 접근시 Dirty bit / Access bit에 FLAG 표시를 해주는데 dirty bit가 check 되어있으면 swap-out할 때 syscall로 파일 변경점에 대하여 update를 해줘야 한다.
핀토스에서는 처음에 실행파일인 ELF file을 load 할 때, 해당 파일에 대한 모든 페이지를 ANONYMOUS page로 load하는데 이 부분이 나는 의아했다. ELF file또한 Disk에 존재하는 파일이기 때문에 가상메모리 이미지상에 filed_backed_page와 anonymous page가 혼재해야 할 것 같다고 생각했기 때문이다. 이와 관련하여 조교님께 질문을 했고 친절한 답변을 받았다.
PINTOS 질문모르는게 없으신 조교님..
만일 시스템콜 exec( ) 가 실행되어 진행중인 process가 다른 process로 교체되는 일이 발생한다면, spt table도 함께 초기화 되어야한다. fork( )에서는 spt table이 적절히 복사되어야 하는데, page에 대응하는 frame은 copy on write 기능 구현 여부에 따라 복사할지, 새로 할당할지 결정이 되어야한다. pintos가 아닌 현실 운영체제에서는 copy on write는 당연히 구현되어있다.
mmap / munmap
mmap은 가상메모리 영역에 페이지를 할당받아 새로운 영역을 맵핑하는 시스템콜이다. 파일식별자 fd로 명시된 연속적인 객체를 맵핑한다. file의 offset 기준으로 length byte만큼 맵핑한다. 이때 할당받는 페이지들은 File backed PAGE이다.
디스크에 위치한 file에 접근하는 syscall로 open, write, read가 있다. 이 syscall들은 매번 호출 시에 Disk에 위치한 파일에 접근하게된다.
mmap은 이러한 disk 접근방식대신 메모리 참조방식이 가능하게 해준다. file을 아래 이미지 처럼 memory의 특정 영역에 mapping 해준다. mapping된 page는 anonymous가 아니므로 수정됬을 때, write back 될 수 있다.
빈번한 파일접근이 필요한경우 속도측면에서 mmap이 유리할 것이라고 추론할 수 있다.
mmap으로 맵핑된 영역 역시 demand paging 이라는 점 기억해야한다.
OS에서는 mmap 관련 시스콜들에 대하여 copy on write를 지원하기 때문에 아래 이미지처럼 프로세스간에 동일한 영역을 share한다. (Pintos에서는 copy on write도 별도로 구현해야한다.)
Memory swap
가상메모리는 프로세스에게 독자적인 주소공간을 제공하고, 메모리를 독점적으로 사용한다는 환상을 심어준다. 하지만 이는 환상에 불가하고 실제 물리메모리의 공간은 수많은 프로세스를 돌리기에는 턱없이 부족하다.
이를 위해 메모리상의 페이지들을 디스크에서 물리메모리로 넣었다 뺏다가 하면서 메모리를 효율적으로 관리한다.
이를 memory swap이라고 한다.
이 기능을 구현하고 생각해보면 Main memory를 DISK의 Cache처럼 사용한다는 말이 무슨 말인지 납득할 수 있다.
그래서 cache와 마찬가지로 swap에서도 policy가 있다. 대표적으로 access bit를 활용한 clock algorithm이 있다.
Anonymous page의 경우 DISK에 근본이되는 실체가 없기 때문에, swap disk를 별도로 만들어 줘야한다. 해당 영역에 임시적으로 swap out 되는 page들에 대한 정보를 저장해주고 다시 swap-in 해야할 때 불러온다.
File_backed_page의 경우 DISK에 근본이되는 파일이 있다. 만약에 mmap을 통해 mapping된 file page의 경우라면
swap out시에 dirty flag를 확인하고 파일에 수정이 있었다면 실제 디스크에 있는 파일에 수정내용을 업데이트 해줘야한다. 변경점이 없다면 그냥 메모리 할당 해제만 해주면된다.
