[운영체제 공룡책] 10. Virtual Memory

가상 메모리와 디맨드 페이징

10.1 Background

• Virtual Memory

  • 어떤 프로세스의 실행을 실제 메모리에 올리지 않아도, 물리 메모리보다 프로세스의 메모리가 더 커도 실행가능하게 해줌

  • 메인 메모리 자체를 가상의 메모리로 생각을 하면 물리 메모리에서 논리 메모리를 분리할 수 있음

  • 실제 사용하지 않는 메모리는 서브 메모리(SSD, HHD)에 올려둠

• Virtual Address Space

  • contiguous memory(연속적인 메모리)에 존재

• page sharing

  • 두 개 이상의 프로세스가 서로 파일과 메모리를 주고받기 더 편함
  • 공유하는 파일과 메모리를 shared page 에 두고 사용

10.2 Demand Paging

• 프로세스 실행 중 사용하지 않는 부분까지 통째로 올리는 것은 너무 비효율적이다! 모던 컴퓨팅에서는 그렇게 사용하지 않는다 (이미 이전강의에서 논의됨)

• 그래서 모든 메모리를 올리는 대신 페이지 단위로 잘라서 올리다

• 각각의 페이지를 올리는 시점? 요청할 때 올리자! === demand paging

• 근데 요청할때마다 페이지를 올리면 많은 문제가 있따. 많은 것을 고려해야한다.

  • 그렇다면 가상 메모리에 있는 demenad-page를 어떻게 관리할 것이냐에 대한 이슈 존재 == 실행중에 요청되는 페이지를 어떻게 관리할 것이냐
  • 어떤 프로세스가 실행중일 때는 필요한 자원이 메인 메모리나 세컨더리 스토리지(하드)에 있어야함. 그래서 하드에 있는지 세컨더리에 있는지 알기 위해 valid-invalid bit 개념을 지난 시간에 활용했었음. demand paging에서도 유효성 확인을 위해 사용함
    • valid : 해당 페이지가 유효하고 메모리에 존재함
    • invalid : 해당 페이지가 유효하지 않거나 현재 세컨더리 스토리지에 있음

• Fage Fualt (아직 메모리에 로딩이 되지 않는 페이지에 엑세스 요청)

  • internal table을 확인하여 유효한 페이지인지 확인
  • 만약 유효하다면 page 제공하면 됨
  • 만약 유효하지 않다면 페이지 메모리에 로드를 해주어야함
    • 비어있는 프레임(free frame)을 찾아서 HDD에 있는 페이지를 로드해줘야함 (그래서 OS가 free-frame list를 관리함)
    • internal table이나 page table에 이제 해당 페이지가 메모리에 있다고 표시
    • 명령 재시작!

• Pure Demand Paging

  • 요청 때 까지 페이지를 메모리에 올리지 않음
  • 메모리에 페이지가 없는 상태로 프로세스를 실행할 수 있음
  • 처음에 메인 메모리에 아무것도 없으니까 첫번째 요청은 무조건 페이지 폴트가 발생한다

• Locality of Reference (참조 국부성)

  • 만약 프로세스가 여러 개의 새로운 페이지에 접근하게 된다면 각각의 명령은
  • 어떤 프로세스의 각 명령어가 여러 개의 페이지에 접근하게 된다면 동시다발적으로 page fault가 일어나는데, 다행히 통계적으로 이런 경우가 드물었음
  • 특히 메모리 관점으로 봤을 때에는 국부성(지역성)이 있음

• Hardware Support to Demand Paging

  • page table : 페이지 테이블을 사용하기 위해서는 해당 페이지가 저장된 실제 물리 메모리 주소를 알아야함. has the ability to mark valid or invalid. (with a valid-invalid bit)
  • Secondary memory: (swap space) : 페이징 스왑을 위해 세컨더리 메모리를 활용해야함

• Instruction Restart

  • 페이지 스왑이 일어나면 실행중인 프로세스를 대기큐에 보내서, 페이지 스왑 완료되면 프로세스가 재시작하게 함
  • paging out, paging in 되는 과정에서 위치가 정확해야함
  • 프로세스별로 페이지 테이블을 잘 관리해야하는데 페이지 테이블의 용량이 큰데 어떻게 관리해야하누?

• Free Frame List

  • OS가 어느 페이지부터 어느 페이지까지가 비어있는 지 링크드 리스트로 관리함

10.3 Copy-on-Write

• CUD를 할때 Copy하자! ⇒ read만 할 때에는 어차피 페이지가 변경되지 않으니까 복사해올 필요 없즤! 공유된 페이지로 활용하고, CUD 할 때에만 페이지를 카피해오자! == fork

---

페이지 교체 알고리즘

10.4 Page Replacement

• 만약 free frames이 없다면 어떤 일이 발생할까? (페이지를 메인 메모리에 로드할 공간이 없는거야!)

  • over allocationg memory 상태가 됨

  • 페이지를 in 시키기 위해서는 물리 메모리(메인 메모리)에 올라간 페이지를 제거해서 공간을 만들어야함

  • 그럼 어떤 페이지를 내릴까?

• Page Replacement

  • Page Fault 과정에서 free frame이 없다면, 희생자를 선정하는 알고리즘에 의해 제거할 페이지를 선정해야함
  • 새로운 페이지를 메모리에 올리고, 페이지와 프레임 테이블을 변경함!
  • page fault + page replacement 가 끝나면 프로세스는 작업을 재개함

• Page Replacement의 두 가지 문제

  • Page-replacement algorithm : 희생자를 선정하는 알고리즘
    • 중요쓰~
  • Frame-allocation algorithm : 프로세스마다 몇 개의 프레임을 할당하는 것이 효율적인가?
    • 크게 중요하지는 않지만 2가지 고려사항이 있으니 다루긴 함

• 위 두가지 문제가 중요한 이유

  • Secondary Storage(하드디스크)에 I/O를 하는 비용은 비싸다!
  • demand paging의 성능이 조금만 좋아져도 시스템 효율이 굉장히 높아짐

• 페이지 교체 알고리즘 평가하기 (목표 : page fault 비율 낮추기)

  • refernce string : 참조 문자열 (페이지 위치 표현을 쉽게 하기 위함)
  • the number of page faults (Minimized it!)
  • 물론 프레임이 많을 수록 page fault 발생이 줄어든다. 하지만 현실에서 프레임의 수는 제한되어 있기 때문에 알고리즘을 공부한다!

• 페이지 교체 알고리즘 : FIFO

  • 가장 먼저 온 페이지를 먼저 내보내라
  • 위 예제에서 총 15번의 page fault가 발생함
  • Belady’s Anomaly : 벨라디가 발생한 이상한 현상
    • 프레임을 많이 줬는데도 page-fault가 증가하는 현상
    • The page-fault rate may increase as the number of allocated frames increases

• 페이지 교체 알고리즘 : Optimal

  • 최적 알고리즘은 page fault가 가장 낮도록 최적화한 것을 의미함
  • OPT or MIN : 앞으로 사용하지 않을 것 같은 혹은 먼 시간 뒤에 사용될 거 같은 페이지를 내보냄
  • 위 예제에서는 9번의 page fault가 발생함
  • 최적화의 어려움
    • OPT는 future knowledge를 요구한다. 그렇기 때문에 실제로 사용되는 게 아니라 각 알고리즘이 페이지 교체 효율을 비교하기 위한 기준으로 사용된다.

• 페이지 교체 알고리즘 : LRU (Least Recently Used)

  • Recall the Shortest-Job-First CPU scheduler → 예전에 배웠었지! 과거를 보고 미래를 바라보는 거!

    • OPT는 이 페이지가 언제 사용될 것인지를 보고 예측하는 거임. 미래는 과거를 보면 알 수 있다. 최근 정보(near future)를 가지고 미래를 예측해보지.
    • 아주 사용을 안한 것은 미래에도 사용할 가능성이 높지 않을까? 의 컨셉!
      • replace the page that has not been used for the longest period of time

  • 위 예제에서는 12번의 page fault가 발생함

  • LRU policy : 효율좋고 자주 사용됨

    • 근데 이를 사용하기 위해서는 해당 페이지가 언제 마지막으로 사용되었는 지 알아야함
    • 소프트웨어로 구현하기 좀 복잡해서 하드웨어 지원을 받으면 좋은데 그것도 쉽지 않지!
    • 하드웨어 지원을 받아 counter와 stack 구현하여 사용 가능

  • LRU 구현

    • 실제 스택처럼 동작하지 않지만 스텍이라고 표현함

  • LRU-Approximation

    • LRU는 하드웨어의 지원을 필요로 함
    • 많은 OS가 reference bit을 제공해줌
    • reference bit : 0으로 초기화해두었다가 페이지가 참조될때마다 1로, replace 되면 0으로!

• 페이지 교체 알고리즘 : Second-Chance (LRU 컨셉의 알고리즘 중 하나임)

  • FIFO 알고리즘 + reference bit을 사용한다
  • 선택된 페이지가 0이라면 페이지 교체를 함
  • 만약 값이 1이라면 (어딘가에서 참조되고 있다면), FIFO에 의해 다음 페이지를 선택함
  • 이 방법의 근본적인(?) 의도? 개념에는 LRU가 깔려있다

10.5 Allocation of Frames

• 프레임 할당의 고민 - N개의 프로세스가 있을 때, M개의 프레임이 있다면 각각 어떻게 할당해야하는가? (해결책은 책에 있음. 문제에 대해 인지하면 됌)
  • 분배
    • Equal allocation : 모든 프로세스에게 동일한 프레임을 할당한다
    • Proprtional allocation : 프로세스 사이즈가 큰 경우에게 더 많이 할당한다
  • 교체 범위
    • Global replacement : 프로세스에게 할당된 프레임 중 희생자를 정해서 교체할 것인가
    • Local replacement : 프로세스들이 사용하고 있는 모든 프레임 중 희생자를 선정하여 교체할 것인가

10.6 Thrasing

• 우리가 Demand Paging을 이용하여 가상메모리를 사용하면 하드웨어 메모리에 무관하게 논리적으로 큰 프로그램을 다양하게 만들 수 있다는 장점이 있었잖아! 근데 이런 문제가 있을 수 있어

• 페이지 스와핑을 하느라 본일을 해야하는 프로세스가 멈춰있는 경우가 있어!

  • 만약 페이지가 충분한 페이지를 보유하지 못한다면 page-fault rate이 아주 높겠지. 그러면 페이지 교체하느라 CPU가 일을 멈춰야하는 순간이 옴!

  • 위 그림에서 멀티프로그래밍의 정도에 따라 CPU 사용량이 올라가는데, 어느 순간이 되면 thrashing이 발생하면서 CPU 활용이 뚝 떨어짐

• Working-Set Model

  • 이 현상을 잘 보니까 Working-Set Model이라는 것을 사용해보면 좋겠다!
  • 메모리 참조에는 지역성이 있음을 기본으로 함
  • working-set window (델타로 표현함)을 지정하고 해당 워킹셋 안애 들어오는 page 대신 그 밖에 있는 페이지들을 희생양으로 삼으면 page fault가 줄 것!
  • 워킹셋을 어떤 식으로 선정하는지는 모르곘는데, 지역성이 높은 페이지끼리 묶고 특정 페이지를 사용하고 있을 떄 관련된 페이지들을 working-set window로 묶는 다는거 같음. 페이지 교체 시 관련성 있는 페이지 대신 관련없는 페이지 아무거나 제거!