Pintos paging Virtual memory jungle swap 운영체제

PintOS 3주차 키워드 정리

정글일지 36

Virtual Memory Management

  • Paging

    • Virtual Page

    page, memory page, virtual page는 인접하고 고정된 길이를 가지는 가상 메모리 블록이며 page table에 등록되어 있다. 가상 메모리 운영 체제에서 메모리 관리를 위한 가장 작은 단위의 데이터이다. 이와 유사하게, page frame는 운영체제가 메모리 페이지를 매핑하는, 인접하고 고정된 길이를 가지면서 가장 작은 단위의 physical 메모리 블록이다. 하드 디스크 드라이브와 같은, 메인 메모리와 auxiliary store(보조 저장?) 사이의 페이지 전송이 페이징, swapping 이라고 불린다. 컴퓨터 메모리는 페이지들로 나누어져 있어 조금 더 빠르게 정보를 찾을 수 있다.기 본 발상은 인쇄된 책의 페이지를 본따 이름 붙어졌다. 예를 들어, 독자가 책의 5천번째 단어를 찾고 싶어 한다면, 첫 단어부터 셀 수도 있다. 시간 낭비긴 하지만.. 독자가 각 페이지에 있는 단어의 수의 리스트를 갖고 있다면 훨씬 빨리 할 수 있다. 이 리스트로 어느 페이지에 5천번째 단어가 있는지, 그 페이지에서 몇번째인지 알 수 있다. 책의 각 페이지에 대한 단어 리스트는 컴퓨터 파일 시스템의 page table에 영감을 주었다.

    • Physical Frame

    가상 메모리 페이지가 저장되어 있는 physical memory 위치를 뜻한다. physical frame은 운영 체제에서 필요한 경우 메모리를 할당하거나 비할당 해주는 역할을 하는 메모리 관리자가 관리한다. 프로그램이 메모리를 요청할 때, 운영체제는 요청받은 메모리를 가상 메모리 주소에 지정하고, 그 이후 물리 physical frame에 매핑된다. 이후 프로그램이 가상 메모리 주소에 읽거나 쓰게 되고, 운영체제는 분명하게 가상 메모리 주소와 physical frame 사이 매핑을 관리한다.

    physical memory가 꽉 차면, 운영 체제는 ‘page swapping’이라는 기법을 사용하여 물리 메모리에서 page file이나 swap file이라 불리는 특수 디스크 파일로 일부 페이지들을 옮긴다. 프로그램이 이 페이지들에 다시 접근할 때, 운영 체제는 물리 메모리로 다시 되돌려 놓는다. Physical frame은 가상 메모리 관리의 필수적인 구성 요소이다. 저장된 프로그램이 사용하는 데이터와 instruction이 위치한 물리 메모리 위치를 나타내기 때문이다.

    • Page table & supplementary page table

    컴퓨터 운영체제의 가상 메모리 시스템에서 가상 주소와 물리 주소를 매핑한 것을 저장하기 위해 사용되는 자료 구조이다. 가상 주소는 접근 프로세스가 실행하는 프로그램이 사용하는 반면, 물리 주소는 하드웨어나 좀더 구체적으로는 RAM(Random Access Memory) subsystem이 사용한다. Page table은 메모리에서 데이터에 접근하기 위해 필요한 가상 주소 translation의 핵심 구성 요소이다.

    가상 메모리를 사용하는 운영체제에서, 모든 프로세스는 크고 연속적인 범위의 메모리를 사용하는 듯한 모습을 보인다. 물리적으로, 각 프로세스의 메모리는 물리 메모리의 다른 지역들에 흩어져 있을수도 있고, HDD(Hdard Disk Drive)나 SSD(Solid State Drive)같은 secondary storage로 옮겨졌을 수도 있다. 프로세스가 메모리에 접근하길 요청할 때, 프로세스가 준 가상 주소를 데이터가 저장된 실제 메모리의 물리 주소로 매핑하는 것은 운영체제의 책임이다. Page table은 운영 체제가 가상 주소를 물리 주소에 매핑한 것을 저장하는 곳이고, 이 ‘매핑한 것’은 PTE(Page Table Entry)라고 한다.

  • Memory Management Unit(MMU)

PMMU(Paged Memory Management Unit)라고도 불리는 MMU는 자신을 지나가는 모든 메모리 참조를 가지며 주로 가상 메모리 주소를 물리 주소로 번역하는 컴퓨터 하드웨어 유닛이다. MMU는 가상 메모리 관리를 효율적으로 수행하고, 동시에 메모리 보호, 캐쉬 컨텐, 버스 중재를 다루며, 8비트 시스템같은 더 간단한 컴퓨터 구조에서 [^bank switching]을 다룬다.

현대의 MMU는 일반적으로 [^가상 주소 공간]을 페이지들로 나누고, 각 페이지들은 2의 제곱이나 몇 KB의 크기를 가지거나 훨씬 클 수도 있다. 주소의 [^하위 비트]는 바뀌지 않은채로 남아있다. 상위 주소 비트는 가상 페이지 숫자이다.

  • Page Table Entry(PTE)

대다수의 MMU는 메인 메모리에서 가상 페이지 숫자를 물리 페이지 숫자로 매핑하기 위해 item에 관한 메모리 내부 표를 사용한다. page table이라고 부르며, 각 페이지당 1개의 PTE를 포함하고 있다. PTE들의 associative 캐쉬는 TLB(Translation Lookaside Buffer)라고 부르고 가상 주소가 매핑될 때 마다 메인 메모리에 접근해야하는 번거로움을 방지하기 위해 사용된다. 다른 MMU는 PTE set를 갖고 있는 레지스터나 메모리의 배열이 private할 수도 있다. 물리 페이지 숫자는 완성된 물리 주소가 받는 page offset과 결합된다.

PTE는 페이지가 작성되었는지, 마지막으로 언제 사용되었는지, 어떤 종류의 프로세스들이 읽고 썼는지, 캐쉬에 저장되어야 하는지 같은 정보를 포함할 수도 있다.

때론, PTE는 물리 RAM이 그 가상 페이지로 할당하지 않았다는 이유로 가상 페이지 접근을 금지한다. 이 경우, MMU는 CPU에 page fault 신호를 보낸다. 운영체제는 RAM의 여분 frame을 찾아 요청받은 가상 주소를 매핑하는 새 PTE를 만들어서 상황을 처리한다. 램이 부족하다면, 존재하는 페이지(victim이라고 함,희생자)를 선택해야 할 수도 있고, 대체 알고리즘을 사용하여, 디스크에 저장할 수도 있다.(이걸 페이징이라고 함). 일부 MMU들에서 PTE가 부족하다면, 운영체제는 새 매핑을 위해 하나를 free해야 한다.

MMU는 규칙 위반이나 존재하지 않는 메모리로의 접근에 대해 불법 접근 에러 조건이나 타당하지 않은 page fault를 만들어낼 수 있지만, 운영체제가 다룰 때는 각각 segmentation fault와 bus eeror 조건으로 연결시킨다.

  • Translateion Lookaside Buffer(TLB)

CPU 내 MMU는 운영체제의 페이지 테이블에서 사용된 최근 매핑의 캐쉬를 저장한다. 이것을 TLB(Translation Lookaside Buffer)라고 하며 associative cache이다.

가상 주소가 물리 주소로 번역이 필요할 때, TLB가 먼저 탐색된다. TLB hit라고 불리는데, 발견되면 물리 주소는 반환되고 메모리 접근은 진행될 수 있다. 그러나, TLB Miss로 불리는 실패한 상황이 되면, MMU나 운영체제의 TLB miss handler는 일반적으로 페이지 테이블에 있는 주소 매핑을 찾아봐서 매핑이 존재하는지 확인하는데 이를 page walk라고 불린다.하나가 존재하면 TLB에 다시 받아써지는데 이 과정은 반드시 수횅되어야 한다. 가상 메모리 시스템에서 하드웨어는 TLB를 통해 메모리에 접근하기 때문이다. 그 후 faulting instruction이 재시작되는데, 병렬적으로 발생할 수도 있다. 차후의 번역은 TLB hit를 야기하고 메모리 접근은 계속될 것이다.

Page Type

  • Uninitialized page
    • Lazy initialization Uninitialized page는 가상 메모리에서 프로세스에 할당되었으나 어떤 데이터로 초기화 되지 않은 페이지를 말한다. 프로세스가 이 페이지에 접근하면 운영체제는 일반적으로 페이지를 위한 물리 메모리를 할당하고 프로세스에게 제어권을 반환하기 전에 0으로 초기화한다. 반면, lazy initialization은 페이지의 초기화를 정말 필요하기 전까지 미루는 기법이다. 프로세스의 가상 주소 공간을 미리 초기화하는 대신, 운영 체제는 각 페이지에게 물리 메모리를 조금만 할당하고 남아있는 페이지들의 초기화를 프로세스가 접근하기 전까지 미룬다. Lazy initialization은 프로세스가 사용하는 물리 메모리의 양을 줄이는데 도움이 되는데, 특히 프로세스가 거대한 가상 주소 공간에 비해 특정 시간동안 작은 부분에만 접근할때 도움이 된다. 프로세스가 lazy initializaion을 사용하여 할당된 uninitialized page에 접근할 때, 운영 체제는 페이지를 위해 물리 메모리를 할당하고 disk에 있는 데이터로 페이지를 초기화 한 후에 프로세스에게 제어권을 반환할 것이다. 요약하자면, uninitialized page는 할당되었지만 초기화되지 않은 페이지를 나타내는 반면, lazy initialization은 실제 필요한 순간 전까지 초기화를 늦추는 기법이다.
  • Anonymous page
    • Stack growth Anonymous page는 프로세스의 가상 주소 공간의 페이지들 중 프로세스가 할당했지만 어떤 파일이나 device와 관련되지 않은 것들을 말한다. 이 페이지들은 일반적으로 프로세스가 동적 메모리 할당에 사용하는데, heap에서 메모리를 할당하는 malloc()이나 new함수를 호출할 때가 그 예시이다. Anonymous pages는 데이터나 코드를 저장하는데 쓰이고, 운영체제의 memory manager가 관리한다. Stack growth는 실행중인 프로그램의 스택에 추가적인 메모리를 할당하는 프로세스를 말한다. C나 C++같은 많은 프로그래밍 언어에서 스택은 지역 변수와 함수 call frames를 저장하는데 쓰인다. 함수가 호출되면, 함수의 지역 변수들과 return 주소는 스택에 저장되고 함수가 반환되면, 이 데이터는 stack에서 pop되어 나온다. 프로그램이 초기에 정해진 것보다 더 많은 메모리를 스택에 할당하려고 한다면, 운영 체제는 스택에게 부가적인 메모리를 할당할 것이고 이에 따라 스택 포인터를 조정한다. 이 추가 메모리 할당 프로세스가 stack growrth라고 불린다. Anonymous page는 stack growth를 돕는데 사용될 수 있다. 프로그램이 스택에 추가적인 메모리를 요청할 때, 운영 체제는 추가로 anonymous page를 할당하고 프로세스의 가상 주소 공간을 거기에 할당할 수도 있다. 이 페이지들은 추가된 stack frame을 저장하는데 사용 될수도 있다. 그러나, stack growth가 위험하고 불안정한 operation이 되는 것은 아무 쓸모도 없다. 프로그램이 가용한 것보다 더 많은 메모리를 할당하려 한다면 잠재적으로 스택 오버플로우 에러를 초래할 수도 있기 때문이다. 결론적으로, Anonymous pages는 연결되지 않은 페이지들이고, 동적 메모리 할당을 위해 사용되는 프로세스의 가상 주소 공간에 있다. 반면 stack growth는 실행중에 프로그램의 스택에 추가적인 메모리를 할당하는 걸 말한다. stack growth를 위해 stack frame에 추가 메모리를 제공하는 방법으로 anonymous page가 사용될 수 있다.
  • FIle-backed page
    • mmap syscall File-backed page는디스크에 있는 파일과 연관된 프로세스의 가상 주소 공간에 있는 page들이다. 프로세스가 file-backed page에 접근할 때, 운영 체제는 그에 알맞은 데이터를 파일에서 물리 메모리에 load하고 페이지에 연관된 physical frame을 매핑한다. 이 덕분에, 프로세스가 실제로는 디스크에 저장되었더라도 마치 메모리에 있는 것처럼 데이터에 접근할 수 있다. mmap syscall은 Unix-like 운영체제의 시스템 콜인데, 프로세스가 파일이나 device를 자신의 가상 주소 공간에 file-backed paged로 매핑하도록 해준다., 프로세스가 mmap을 호출할 때, 운영 체제는 프로세스의 주소 공간에서 연속적인 가상 메모리 지역을 할당하고 file이나 device의 일부에 매핑할 것이다. 그 이후, 프로세스는 상응하는 가상 메모리 주소를 읽거나 써서 파일내의 데이터에 자신이 마치 메모리에 있는 것처럼 접근할 수 있다. 운영 체제는 demand paging이라 하는 기법을 사용하여 자동적으로 필요한 만큼 물리 메모리로 파일의 데이터를 load할 것이다. 프로세스가 매핑된 지역의 데이터를 수정한다면, 수정 내용은 페이지가 물리 메모리에서 쫓겨난 후에 파일에 기록될 것이다. mmap syscall은 다양한 목적으로 사용될 수 있는데, 메모리-매핑 파일, 프로세스들간 공유 메모리를 위해 쓰인다. 또한 page file이 back 해주는 anonymous pages를 만드는데도 [^사용된다.]파일과 함께 사용될 때 mmap은 이전의 파일 입출력 이상의 이익을 수행 능력에서 보이는데 운영체제가 물리 메모리의 파일 데이터의 캐시를 관리하는데 더욱 효율적으로 만들고, 프로세스가 명시적인 read나 write 시스템 콜과 상관없이 직접 데이터에 접근할 수 있기 때문이다. 요악하자면, file-backed page는 디스크의 파일이 back하는 프로세스의 가상 주소 공간 내의 page이고, 반면 mmap syscall은 프로세스가 가상 주소 공간을 file-backed page로 매핑하도록 해주는 시스템 콜이다. mmap syscall은 파일 입출력 operation보다 향상된 성능을 제공하는데, 운영체제가 파일 데이터의 캐시를 더욱 효율적으로 관리하게 해주기 때문이다. [^사용된다.]: anonymous pages는 프로세스가 할당했지만 file이나 device가 back하지 않은 프로세스의 가상 주소 공간에 있는 page이다. mmap syscall은 page file이 back해주는 anonymous page를 만드는데 사용될 수 있는데, swap space라고 불린다. 프로세스가 MAP_ANONUMOUS플래그를 가진 mmap을 사용하여 운영 체제에 메모리를 요청할 때, 운영 체제는 anonymous page를 할당하고 swap space로 이 페이지들을 back할 것이다. 프로세스는 이 페이지들을 동적 메모리 할당이나 다른 목적으로 사용할 수 있고, 운영 체제는 anonymous page를 swap space에서 페이징 해오거나(page from), swap space로 페이징하는 것(page to) 을 관리한다.

Swap in/out

swap out : 메모리에서 다른 목적으로 물리 메모리를 free하면서 swap space로 page를 이동시키는 것

swap in : 사용 목적으로 swap space에서 페이지를 메모리로 갖고 오는 것.

  • swap disk(swap space) : 운영 체제가 inactive 나 unused 메모리 페이지를 일시적으로 저장하기 위해 구성된, 하드 드라이브나 SSD(Solid-State drive)의 구역이다. 물리 메모리(RAM)가 가득 차면, 운영 체제는 적게 사용되거나 inactive한 페이지들을 RAM에서 swap space로 이동시키고 RAM을 다른 task를 위해 free할 것이다. swap space는 운영 체제처럼 같은 디스크에 있을 수도 있고 분리된 dedicated disk나 partition에 있을 수도 있다.

    일반적으로, 필요한 swap space의 양은 물리 메모리의 양과 컴퓨터에서 실행하는 application들의 수요로 결정된다. 가용 swap space가 충분치 않으면, 시스템은 메모리가 부족해서 무반응이 될 수도 있다. 그러나, swap space가 너무 많은것도 성능에 부정적인 영향을 끼치는데, 시스템이 실제로 task를 수행하기보단 페이지들을 swap하는데 더 시간을 쏟을수도 있기 때문이다.

  • page replacement policy

    운영 체제가 새로운 페이지를 위한 공간을 free해야 할 때 물리 메모리의 어떤 페이지들이 대체되야 하는지를 결정하는 메커니즘이다.

    page replacement policy의 목적은 (프로그램이 최근에 물리 메모리에 없던 페이지에 접근하려고 시도할 때)page fault의 수를 최소화하고 시스템의 전반적인 성능을 최대화 하는 것이다. 종류로는 다음과 같은 몇가지가 있는데 각각 장단점이 있다.

    • LRU(Least Recently Used) : 이 방식은 가장 오랜 시간동안 접근되지 않은 페이지를 대체한다. 다양한 상황에도 잘 작동되어 가장 대중적임
    • FIFO(First-In-First-Out) : 가장 오래 메모리에 있었던 페이지를 대체한다. 간단하지만 빈번하게 접근한 페이지가 있다면 잘 안될 수 있음
    • Clock : 각 페이지의 가장 최근에 접근한 시간을 추적하기 위해 순환 버퍼와 clock hand를 사용하는 알고리즘. 각 페이지가 대체될 필요가 있을 때, clock hand는 최근에 접근되지 않은 페이지에 닿을때 까지 앞으로 이동하고 닿으면 그 페이지가 대체된다.
    • Random : 이 알고리즘은 무작위로 대체될 페이지를 선택한다. 간단하지만 성능의 관점에서 효율적이지 않다.
CATALOG
    log