가상 메모리

가상 메모리

물리적인 메모리의 한계를 극복하기 위해 도입

• 물리 메모리 크기 한계 극복
  • 프로세스의 이미지를 모두 메모리에 올릴 필요 없다
  • 현재 실행에 필요한 부분만 메모리에 올린다
  • 오류 처리 제외, 배열 일부 제외, 워드프로세스에서의 정렬 일부 등등
  • 동적 적재와 비슷한 개념

요구 페이징

• 전체 프로그램을 메모리에 적재할 필요가 없다

• 필요한 부분만 메모리에 적재하면 된다

• Demand Paging

  • 프로세스 이미지는 backing store 에 저장
    • backing store == swap device
  • 프로세스는 페이지의 집합
  • 지금 필요한 페이지만 메모리에 올린다(load) -> 요구되는(demand) 페이지만 메모리에 올린다

• 하드웨어 지원이 필요하다

  • 메모리에 적재되어 있는지 표시하기 위해 비트 추가된 페이지 테이블
    • 테이블에 메모리 적재 여부를 비트를 이용하여 표시
  • backing store
    • == swap device
    • 페이지들을 가지고 있을 저장공간이 필요하다
    • ssd 나 dram 등등

• 페이지 테이블에 비트를 추가하여 페이지 메모리 적재 여부를 표시한다
• 만약 CPU가 참조하는 페이지가 없다면 적재해야 한다
  • 페이지 테이블이 Interrupt를 일으킨다
  • Interrupt가 일어나면 CPU는 하던 일을 중단하고, 해당 Interrupt 처리 루틴을 실행한다
  • 여기서 Interrupt 처리 루틴은 없는 페이지 가져오는 것
    • page fault 처리 루틴

Copy-on-Write

어떠한 공유 페이지가 있을 때, write 가 있다면 page 를 복사하여야 한다.

• 프로세스가 pork() 하게 되면 공유 영역은 MMU가 똑같은 물리적 메모리를 가리킨다.
  • page 공유
• 만약 한 프로세스가 페이지를 수정한다면 해당 페이지를 복사하여 별도로 관리하는 것이 필요하다
  • 복사한 다음 변경하는 프로세스가 해당 페이지 가리키도록 한다

Page Fault

CPU에서 페이지를 읽으러 했을 때 backing store에는 있지만 메모리에는 없다면 page fault

• 페이지 폴트
  • 접근하려는 페이지가 메모리에 없다
  • Backing store 에서 해당 페이지를 가져온다
• 발생 과정
  • CPU가 어떤 주소를 요청
    • 5번째 page에 20번째 line
  • page table 이 invalid
    • interrupt 발생
  • CPU는 page fault 처리 루틴으로 점프
  • swap device 에서 페이지를 메모리로 가져온다
    • 메모리에 공간(frame)이 있다고 가정
  • page table 을 valid로 변경
  • CPU가 다시 주소를 요청

• pure demand paging : 정말 필요한 페이지만 메모리에 적재하는 것

• preparing : 미리 필요할 수 있는 페이지 적재

• swapping : 프로세스 전체를 메모리에 적재하거나 swap device 로 보내거나

• demand paging : 가져오는 단위가 page

지역성의 원리

• Locality of reference
  • 메모리 접근은 시간적, 공간적 지역성을 가진다
  • 덕분에 실제 page fault 확률은 매우 낮다
• 다른 방법
  • HDD는 접근 시간이 너무 길다 -> swap device 로 부적합
  • SSD 또는 느린 저가 DRAM 사용

시간적 지역성

최근에 읽었던 것 읽을 가능성이 크다

공간적 지역성

주변에 있는 것 읽을 가능성이 크다

그래서 인근의 데이터를 block 단위로 가져옴

페이지 교체

메모리가 가득 찼을 경우 victim을 내리고 새로 페이지를 적재한 다음 page table에 표시하는 것.

• Demand Paging
  • 요구되어지는 페이지만 backing sotre 에서 가져온다
  • 프로그램 실행 게속에 따라 요구 페이지가 늘어나고,
  • 언젠가는 메모리가 가득 차게 된다
• Memory full
  • 메모리가 가득 차면 추가로 페이지를 가져오기 위해
  • 어떤 페이지는 backing store 로 몰아내고(page-out)
  • 그 빈 공간으로 페이지를 가져온다(page-in)
  • page table에 해당 page 가 메모리에 있다고 표시한다

Victim page

페이지 교체 시 메모리에서 내보내지는 페이지

• 어떤 페이지를 몰아낼 것인가?
  • I/O 시간 절약을 위해
  • 기왕이면 modify 되지 않은 페이지를 victim 으로 선택
    • 메모리에 적재된 페이지에 변경사항이 있다면
    • 하드디스크의 페이지에도 적용하여야 한다
  • 변경 여부를 표시하기 위해 페이지 테이블에 변경 여부를 나타내는 modified bit 추가
    • dirty bit 라고도 한다
• modify 되지 않은 페이지 중에서 무엇을 victim으로?
  • OPT
  • FIFO
  • LRU

페이지 교체 알고리즘

Page fault를 최대한 줄이는 방향으로 Victim frame 를 결정하는 알고리즘

• 페이지 폴트 알고리즘의 목표

  • pafe fault 낮추기

• FIFO

  • 가장 먼저 들어온 페이지를 victim으로
  • 장점
    • 간단하고 구현하기 쉽다
  • 단점
    • Belady's Anomaly
      • 메모리 프레임이 늘어날 때
      • pafe fault rate 가 늘어날 때가 있다??

• Optimal page Replacement

  • 가장 오랫동안 사용하지 않을 것 같은 페이지를 victim으로
  • 장점
    • 낮은 pafe fault rate
  • 단점
    • 어떤 페이지를 사용하지 않을 지 추측이 불가능하다
  • 성능 비교를 위한 알고리즘

• LRU(Least Recently used)

  • 가장 사용한지 오래 된 페이지를 victim 으로
  • 장점
    • 성능도 나쁘지 않다
    • Belady's Anomaly 발생 안함
  • 단점
    • 가장 사용한지 오래 된 페이지를 계산하기 힘들다
  • 하드웨어적인 지원을 필요로 한다
    • counter나 stack
  • counter
    • 페이지가 참조되면 카운터나 클락 복사
    • 가장 값이 작은 페이지 victim으로
  • stack
    • 페이지 번호를 스택에 넣는다
    • 중간에 호출되면 스택에서 제외된 다음 가장 위로 간다
    • FIFO가 안되지만 하여튼 스택

• LRU-Approximation

  • LRU는 추가적인 하드웨어 세팅이 필요하다
    • 그래서 많은 시스템은 그냥 reference bit를 제공
  • reference bit
    • 처음은 0
    • 페이지가 참조되면 bit 를 1
    • reference bit 가 0 인 페이지 교체
    • 없으면 아무거나
  • LRU 만큼은 아니지만 나름 효율적

• Second-Chance Algorithm

  • FIFO 사용
  • reference bit를 이용해서 두번째 기회 제공
  • 나갈 차례가 됬는데 reference bit가 0이면 1로 바꾸고 넘어감
  • 1이면 나감

프레임 할당

각 프로세스에게 어느 정도의 프레임을 할당할 것인지

• Equal
  • 모든 프로세스에게 동등하게 할당
• proportional
  • 프로세스 크기에 따라 다르게 할당

• Global
  • victim 선정을 전체 프레임
• Local
  • victim 선정을 소유한 프레임에서만

Thrashing

• 프로세스가 swapping pages in and out을 하느라 바쁜 상황

• 멀티 프로그래밍의 정도가 높아지면 CPU 효율이 증가하다

• 일정 수준 이하가 되면 급격히 감소

• 프로세스가 충분하지 않은 페이지를 가지고 있다면 발생

• frame은 한정되어 있는데 너무 많은 프로세스가 한번에 돌게 되면

• 각 프로세스에게 할당 될 프레임이 감소하게 된다

• 일정 정도가 넘으면 swap 이 너무 빈번하게 일어나 성능이 떨어진다

• 이것을 thrashing 이라 한다