Virtual Memory

dragonappear·2023년 7월 24일
0

Operating System 101

목록 보기
10/10


Virtual Memory

✔️ Virtual Memory

  • 프로그램의 일부분만 메모리에 올려놓고 실행하는 기술
  • 물리 메모리 개념과 사용자의 논리 메모리 개념을 분리한다

✔️ 장점

  • 프로그램은 물리 메모리 크기에 제약받지 않게 된다

  • 사용자 프로그램이 더 작은 메모리를 차지하므로 더 많은 프로그램을 동시에 수행할 수 있다

  • 메모리를 스왑하는 횟수가 줄어든다

  • 페이지 공유를 통해 파일이나 메모리가 둘 또는 그 이상의 프로세스들에 의해 공유될 수 있다
    • ex) 시스템 라이브러리는 읽기만 허용되는 상태로 프로세스 주소 공간에 매핑될 수 있다.
    • ex) 프로세스들이 메모리를 공유할 수 있다

Demand Paging

✔️ Demand Paging

  • 페이지가 필요할 때 메모리에 적재하는 방법
  • 한 번도 접근되지 않는 페이지는 물리 메모리에 적재되지 않음

✅ Locality of reference(참조 국부성)

대부분의 프로그램은 실행될 때 어느 한 특정 작은 부분만 한동안 집중적으로 참조하기 때문에 요구 페이징은 만족할 만한 성능을 보인다.

✅ Pager

  • 프로세스 내의 개별 페이지들을 관리한다
  • 프로세스 전체를 스왑하는 대신에 실제로 필요한 페이지들만 메모리에 읽어 온다

✅ 장점

사용되지 않을 페이지는 메모리로 가져오지 않음으로써 시간 낭비와 메모리 공간 낭비를 줄인다

✔️ Hardware

어느 페이지가 디스크에 있고 어느 페이지가 메모리에 올라와 있는지 구별할 필요가 있다. 이 때 하드웨어의 도움이 필요하다

✅ Page-table

valid-invalid 비트가 적용하여 해당 페이지가 메모리에 올라와 있는지 설정할 수 있다.

✅ Swap space

  • 메인 메모리에 없는 모든 페이지들을 가지고 있는 공간
  • 스왕 영역에서의 디스크 입출력은 파일 시스템에서의 입출력 보다 빠르다
    • 파일 시스템보다 더 큰 블록을 사용하기 때문에

✔️ Page Fault Trap

프로세스가 메모리에 올라와 있지 않은 페이지에 접근하려고 하면 어떤 일이 발생할까?

  1. 메모리 참조가 valid 인지 invalid 인지 확인한다.
  2. invalid 페이지에 대한 참조라면(메모리에 적재되지 않은 페이지) 그 프로세스는 중단된다
  3. 자유 프레임을 찾는다
  4. 자유 프레임을 해당 페이지에 할당한다
  5. 디스크 읽기가 완료되면, 페이지 테이블을 갱신한다
  6. 트랩에 의해 중단되었던 명령어를 다시 수행한다

✅ Page fault 처리

페이지 폴트 처리는 크게 아래 3가지로 볼 수 있다.

  1. 페이지 폴트 인터럽트(트랩) 처리
  2. 디스크에서 페이지 읽기
  3. 프로세스 재시작

다른 작업보다 페이지를 읽는 시간이 압도적으로 시간이 많이 드는 작업이다

✅ Effective access time for demand page

  • EAT = (1-p) ma + p (page fault time)
    • ma = memory access time
    • p = probability of page fault
  • 페이지 폴트율을 낮게 유지하는 것이 상당히 중요하다

✔️ Pure demang Paging

어떤 페이지가 필요하지 않는한 절대로 페이지를 메모리에 가져오지 않는 방법

  • 메모리에 페이지가 하나도 올라와 있지 않은 상태에서 프로세스를 시작할 수 있다

  • OS에서 명령어 포인터의 값을 프로세스의 첫 명령으로 설정하는 순간 이 명령이 메모리에 존재하지 않는 페이지에 있으므로 페이지 폴트가 발생한다

  • 페이지가 적재되고 나면 프로세스는 수행을 계속하는데 프로세스가 사용하는 모든 페이지가 메모리에 올라 올 때까지 필요할 때마다 페이지 폴트가 발생한다

✔️ Issue

✅ [1] Instruction Restart

  • 페이지 폴트가 발생하여 중단된 프로세스 상태(레지스터 상태)를 저장해두면 다시 이 프로세스를 시작할 때 정확히 같은 위치, 같은 상태에서 프로세스를 다시 수행할 수 있다.

  • 만약 Page fault가 Instruction Fetch시에 발생했다면 Instruction를 메모리로 읽어 온 후 다시 수행을 진행하면 된다

  • 만약 operand를 fetch하는 동안에 Page fault가 발생했다면 나중에 그 명령어를 다시 읽어오고 decode하여 operand를 fetch하면 된다

  • ex) ADD A,B,C;

    1. Fetch and decode the instruction(ADD)
    2. Fetch A
    3. Fetch B
    4. ADD A and B
    5. Store the sum in C

1번 or 2,3번 or 5번 step 에서 page fault가 발생했을 때, 1번 step부터 다시 재시작하면 된다

✅ [2] Free Frame List 관리

Page-in을 하기 위해서 OS는 free-frame list(a pool of free frames)를 관리해야 한다

✅ [3] Swap space 관리

스왑 영역의 입출력이 파일 시스템의 입출력보다 빠른점을 활용하여 스왑 영역을 활용할 수 있다. 스왑 영역을 활용한 여러가지 방법이 있다.

  1. 프로세스를 시작시킬 때 프로세스 파일 이미지를 스왑 공간으로 복사한 후 스왑 공간으로부터 demang paging을 함으로써 페이징 처리율을 얻는 방법

  2. 프로그램을 처음 시작시킬 때에는 파일 시스템으로부터 요구 페이징을 처리하지만 그 페이지들이 교체될 때는 스왑 공간에 페이지를 기록하는 방법

  3. 실행 파일(binary file)을 스왑 영역에 넣지 않고 스왑 영역의 크기를 줄이는 방법

✔️ Prepaging


Copy on write

  • 과거에는 부모 프로세스의 페이지들을 실제 자식 프로세스에게 복사해줌으로 써 자식 프로세스의 주소 공간을 구성해주었다. 하지만 자식들이 만들어지자마자 곧 exec() 시스템콜을 호출하면 부모 프로세스로부터 복사해온 페이지들이 쓸모 없게 된다.

  • 프로세스 생성 시간을 더 줄이기 위해 fork() 시스템콜을 통해 프로세스를 생성할 때에는 페이지 공유와 비슷한 기법으로demand paging 조차 생략 가능하다.

  • 수정될 수 있는 페이지만이 Copy on write 페이지로 표시할 수 있다.


Page Replacement Algorithm

멀티 프로그래밍 degree를 올리면 메모리 과할당이 발생한다. 더욱이 시스템 메모리는 페이지를 저장하는 용도로만 사용되는 것이 아니다. 입출력을 위한 버퍼도 상당한 양의 메모리를 사용한다.

✔️ Page Replacement

  • 빈 프레임이 존재하지 않으면 OS는 victim frame을 선정하여 페이지 교체 알고리즘을 적용해야 한다

  • free frame이 없는 경우에는 디스크를 두 번 접근해야 한다(페이지 아웃 1번+ 페이지 인 1번)

  • 이에 따라 page fault 처리 시간이 2배 소요되고 effective access time도 증가한다.

  • 이러한 오버헤드는 변경 비트(modify bit or dirty bit)를 사용해서 감소시킬 수 있다.

    • victim page가 변경되지 않았다면 디스크 상의 복사본이 변경되지 않았기 때문에 메모리 페이지를 디스크에 기록할 필요가 없어진다.
    • 따라서 page out을 하는 것을 생략할 수 있다.
    • 이 기법은 읽기 전용 페이지들에 적용할 수 있다.

✅ Page Fault Service Routine

  1. 디스크에서 필요한 페이지의 위치를 찾는다.

  2. 빈 프레임을 찾는다
    a. 빈 프레임이 있으면 그것을 사용한다
    b. 없다면 victim 프레임을 선정하기 위해 page replace algorithm을 적용
    c. victim page를 디스크에 기록하고, 페이지 테이블을 수정한다

  3. 빼앗은 프레임에 새 페이지를 읽어오고 페이지 테이블을 수정한

  4. page fault가 발생한 지점에서부터 프로세스를 계속한다

✔️ FIFO

메모리에 올라온지 가장 오래된 페이지를 교체한다

✅ 장점

간단하다

✅ 단점

자주 사용되는 페이지를 교체할 경우 page fault율이 증가한다

✅ Belady's anomaly

프로세스에게 할당되는 프레임 수를 증가했는데, 페이지 폴트율이 증가하는 현상

✔️ Optimal

✔️ LRU

✔️ LRU Approximation

✅ Additional Reference Bits

✅ Second Chance

✅ Enhanced Second Chance

✔️ Counting Based Page

✔️ Page Buffering


Frame Allocation

✔️ Minimum Number of Frames

✔️ Equal Allocation

✔️ Proportional Allocation

✔️ Global Allocation

✔️ Local Allocation

✔️ Non-uniform Memory Access


Thrashing

✔️ Cause

✔️ Working Set Model

✔️ Page Fault Frequency


Memory Mapped Files


커널 메모리 할당


0개의 댓글

관련 채용 정보