[OS] Virtual Memory

virtual Memory는 모든 요청에 운영체제가 관여
** 메모리 관리 방법 중 페이징 기법을 사용하는 것으로 가정

Demand Paging

• 실제로 필요할 때 page를 메모리에 올리는 것

  • I/O 양의 감소
  • Memory 사용량 감소
  • 빠른 응답 시간
  • 더 많은 사용자 수용

• Valid / Invalid bit의 사용

  • Invalid의 의미
    • 사용되지 않는 주소 영역인 경우
    • 페이지가 물리적 메모리에 없는 경우
  • 처음에는 모든 page entry가 invalid로 초기화
  • address translation 시기에 invalid bit이 set되어 있으면 page fault
  • page fault trap(interrupt)이 발생하면 CPU는 자동적으로 OS에게 넘어감

🚧 Page Falut

• invalid page를 접근하면 MMU가 trap을 발생시킴(page fault trap)
• Kernel mode로 들어가서 page fault handler가 invoke됨
• 다음과 같은 순서로 page fault를 처리함

  1. Invalid reference? (eg. bad address, protection violation) -> abort process

  2. Get an empty page frame(비어있는 page frame이 없을 경우 뺏어옴 : replace)

  3. 해당 페이지를 disk에서 memory로 읽어옴

     1) Disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당함(block)
     2) Disk read가 끝나면 page tables entry 기록, valid / invalid bit = "valid"
     3) ready queue에 process를 insert -> dispatch later
     

  4. 이 프로세스가 CPU를 잡고 다시 running

  5. 아까 중단되었던 instruction을 재개

🚧 Performance of Demand Paging

page fault 값이 0이면 모든 page가 메모리에 있는 상태 page fault가 나지 않음

1일 경우엔 무조건 page fault

🚧 Free frame이 없는 경우

• Page replacement
  • 어떤 frame을 빼앗아올지 결정해야 함
  • 곧바로 사용되지 않을 page를 쫓아내는 것이 좋음
  • 동일한 페이지가 여러 번 메모리에서 쫓겨났다 가 다시 들어올 수 있음
• Replacement Algorithm
  • page-fault rate을 최소화하는 것이 목표
  • 알고리즘의 평가 : 주어진 page reference string에 대해 page fault를 얼마나 내는지 조사
  • reference string의 예
    1,2,3,4,1,2,5,1,2,3,4,5

🚧 Page Replacement

victim이 변경 사항이 없으면 그냥 디스크로 쫓아내면 됨
하지만 write가 발생했을 경우 쫓아낼 때 디스크에 변경사항을 써줘야함

📌 Optimal Algorithm

page fault를 가장 적게 하는 알고리즘
미래에 참조되는 페이지들을 미리 다 안다고 가정하는 알고리즘
따라서 실제 시스템에서 사용할 수는 없음
빨간색은 page fault
연보라색은 메모리에서 참조

📌 FIFO(First In First Out) Algorithm

📌 LRU(Least Recently Used) Algorithm

제일 오래 전에 사용 된 페이지를 쫓아내는 알고리즘

📌 LFU(Least Frequently Used) Algorithm

참조 횟수가 가정 적은 페이지를 쫓아내는 알고리즘

LRU / LFU Algorithm 예제

LRU / LFU Algorithm 구현

LRU Algorithm은 메모리에 있는 페이지들을 시간 순서에 따라 정렬 (linked list)
replace를 해야해 페이지를 쫓아내야하면 리스트에서 가장 위에 있는 페이지를 쫓아냄
걸리는 시간은 order of 1

LFU Algorithm은 메모리에 있는 페이지들을 참조 횟수에 따라 정렬 (linked list)
이런 식으로 구현했을 경우 걸리는 시간은 order of n

따라서 linked list로 구현하지 않고 heap 구조 중 이진트리를 이용해서 구현함
이런식으로 구현 했을 경우 걸리는 시간은 order of log n

📌 다양한 캐슁 환경

캐슁 기법

• 한정된 빠른 공간(=캐쉬)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스하는 방식
• paging system 외에도 cache memory, buffer caching, Web caching 등 다양한 분야에서 사용
  캐쉬 운영의 시간 제약
• 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음
• Buffer caching이나 Web caching의 경우
  • O(1)에서 O(lon n) 정도까지 허용
• Paging System인 경우
  • page fault인 경우에만 OS가 관여함
  • 페이지가 이미 메모리에 존재하는 경우 참조시 각 등의 정보를 OS가 알 수 없음
  • O(1)인 LRU의 list 조작조차 불가능

🚧 Paging System에서 LRU, LFU 가능한가?

CPU에서 프로세스A가 running 중일 때 매 실행마다 instruction을 불러와서 실행함

만약 주소변환을 했는데 해당 하는 페이지가 이미 물리적 메모리에 올라가 있을 때 그걸 그대로 가져다 씀
여기서 OS는 하는 일이 없음

만약 프로세스 A가 실행을 하다가 page fault가 발생할 경우 디스크 접근(I/O)를 필요로 하기 때문에 trap이 발생
트랩이 발생하면 CPU가 운영체제로 넘어감
운영체제는 가장 참조횟수가 적은 페이지 가장 오래된 페이지 등을 알 수 없음

왜냐하면 프로세스가 사용하는 페이지는 이미 메모리에 올라와 있는 경우에는 CPU가 운영체제한테 넘어가지 않음 하드웨어 적으로 주소변환해서 CPU한테 넘김(운영체제가 관여하지 않음)
이미 메모리에 올라가 있는건 OS가 알 수 없고
trap이 발생해서 CPU가 OS에 넘어 갔을 때 백 스토리지에서 메모리에 올라간 것만 알 수 있음

따라서 운영체제는 이미 메모리에 있는 페이지들을 쫓아낼 기준을 알 수가 없음
따라서 LRU LFU같은 것들을 페이징 시스템(버추얼메모리시스템)에서는 맞지 않음
하지만 아예 사용하지 않는 것은 아니고 퍼버캐싱 웹캐싱에서는 사용될 수 있음

그럼 페이징 시스템에서는 리플레이스를 하기 위해 어떤 알고리즘을 사용해야하는가? Clock Algorithm

📌 Clock Algorithm

• LRU의 근사(approximation) 알고리즘

• 여러 명칭으로 불림

  • Second Chance Algorithm
  • NUR(Not Used Recently) 또는 NRU(Not Recently Used)

• Reference bit을 사용해서 교체 대상 페이지 선정(circular list)

• Reference bit가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동

• 포인터 이동하는 중에 Reference bit 1은 모두 0으로 바꿈

• Reference bit이 0인 것을 찾으면 그 페이지를 교체

• 한 바퀴 되돌아와서도(=second chance) 0이면 그 때는 replace 당함

• 자주 사용되는 페이지라면 second chance가 올 때 1

• Clock Algorithm의 개선

  • Reference bit과 modified bit(dirty bit)을 함께 사용
  • Reference bit=1 : 최근에 참조된 페이 지
  • Modified bit=1 : 최근에 변경된 페이지 (I/O를 동반하는 페이지)

시계 모양의 알고리즘이라 Clock Algorithm이라는 이름이 붙음
각 페이지들이 시계모양으로

페이지가 최근에 참고가 되면 레퍼런스 비트를 1로 세팅 이건 운영체제가 하지 않고 하드웨어가 하는 일
레퍼런스 비트가 1이라는건 최근에 참고 됐음을 나타냄
레퍼런스 비트가 0이라는거는 시계가 한바퀴 돌았을 때 한번도 참조되지 않았음을 의미
레퍼런스 값이 0인 것을 쫓아냄 이런 면에서 LRU와 근사 알고리즘임 하드웨어가 비트를 세팅해주는 것을 보고 운영체제는 쫓아낼 페이지를 정함

페이지가 read가 아닌 write가 발생할 때 하드웨어는 modified bit을 1로 설정해줌 이는 메모리에서 백킹스토어로 쫓겨날 때 백킹 스토어에 수정된 내용을 반영한 후 쫓겨나야 함

모디파이드 비트가 1이면 디스크에 써줘야함으로 번거로워짐 따라서 쫓아내는 페이지를 결정할 때 참조횟수뿐만 아니라 수정횟수도 참고함

🚧 Page Frame의 Allocation

프로그램이 여러개가 메모리에 올라가 있음.
프로그램이 원활하게 실행되기 위해서는 CPU에서 돌아가면서 page fault를 최소화하고 일련의 페이지들을 같이 메모리에 적재하는 것이 효율적이다.
예를 들어 for loop에 속한 페이지가 3개라면 3개를 같이 적재하는 것이 효율적
코드에 해당하는 페이지 뿐만 아니라 데이터가 필요할 경우 데이터가 있는 페이지도 같이 적재되어 잇는 것이 효율적
프로그램 별로 allocation을 해주지 않을 경우 특정 프로그램 관련 페이지로 메모리를 점령할 수 있음

• Allocation problem : 각 process에 얼마만큼의 page frame을 할당할 것인가?
• Allocation의 필요성

  • 메모리 참조 명령어 수행시 명령어, 데이터 등 여러 페이지 동시 참조

    • 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있음

  • Loop를 구성하는 page들은 한꺼번에 allocate 되는 것이 유리함

    • 최소한의 allocation이 없으면 매 loop마다 page fault
• Allocation Scheme
  • Equal Allocation : 모든 프로세스에 똑같은 개수 할당
  • Proportional Allocation : 프로세스 크기에 비례하여 할당
  • Priority Allocation : 프로세스의 priority에 따라 다르게 할당

📌 Global vs. Local Replacement

Global Replacement

• Replace 시 다른 process에 할당된 frame을 빼앗아 올 수 잇음
• Process 별 할당량을 조절하는 또 다른 방법
• FIFO, LRU, LFU 등의 알고리즘을 Global Replacement로 사용시에 해당
• Working set, PFF 알고리즘 사용

Local Replacement

• 자신에게 할당된 frame 내에서만 replacement
• FIFO, LRU, LFU 등의 알고리즘을 process 별로 운영 시

위의 두 방법은 미리 할당하지 않고 그 때 그 때 유동적으로 페이지를 할당함

Global Replacement는 자신 뿐만 아니라 다른 프로그램의 페이지도 쫓아 낼 수 잇는 방법이고
Local Replacement는 자신에게 할당된 페이지를 쫓아내는 방법임

📌 Thrashing

• 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당받지 못한 경우 발생
• Page fault rate이 매우 높아짐
• CPU utilization이 낮아짐
• OS는 MPD(Multiprogramming degree)를 높여야 한다고 판단
• 또 다른 프로세스가 시스템에 추가됨(higher MPD)
• 프로세스 당 할당된 frame의 수가 더욱 감소
• 프로세스는 page의 swap in / swap out으로 매우 바쁨
• 대부분의 시간에 CPU는 한가함
• low throughput

x축은 메모리에 올라와 있는 프로그램의 개수
x축이 늘어날 수록 CPU의 사용률은 높아짐
근데 지속적으로 프로그램의 개수가 늘어날 경우 Thrashing이 발생함

왜냐하면 프로그램마다 할당받는 메모리 page가 너무 적어지기 때문에 page fault가 빈번히 발생하게 됨

어떤 프로세스가 CPU를 잡더라도 page fault가 발생하기 때문에 페이지 사용률이 낮아짐
그럼 OS는 프로그램을 더 실행해도 된다고 판단(MPD를 높여도 된다) -> 그럼 또 다른 프로세스가 시스템에 추가됨

아래 두개는 Thrashing을 방지하기 위한 알고리즘

🚧 Working-Set Model

Locality of reference

• 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조함
• 집중적으로 참조되는 해당 page들의 집합을 locality set이라 함

Working-Set Model

• Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야하는 page들의 집합을 Working Set이라 정의함
• Working Set Model에서는 process의 Working Set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame을 반납한 후 swap out(suspend)
• Thrashing을 방지함
• Multiprogramming degree를 결정함

Working-Set Algorithm

워킹셋은 미리 알 수가 없음
과거를 통해 working set을 추정함
과거 델타 시간동안 참조된 페이지들을 메모리에서 쫓아내지 않음 이것을 워킹셋이라 판단함
델타시간을 윈도우라고 부름
메모리 공간이 부족해 워킹셋을 다 메모리에 올리지 못하면 디스크로 서스펜드

참조된 페이지들을 델타시간 동안만 유지한 후 버린다는 말과 똑같음 근데 버리려 했는데 다시 참조가 된다면 버리지 않음

• Process들의 Working Set size의 합이 page frame의 수보다 큰 경우

  • 일부 process를 swap out 시켜 남은 process의 working set을 우선적으로 충족시켜 줌(MPD를 줄임)

• Working Set을 다 할당하고도 page frame이 남는 경우

  • Swap out 됐던 프로세스에게 Working Set을 할당(MPD를 키움)

• Window size Δ

  • Working Set을 제대로 탐지하기 위해서는 Window size를 잘 결정해야 함
  • Δ 값이 너무 작으면 locality set을 모두 소용하지 못할 우려
  • Δ 값이 크면 여러 규모의 locality set tndyd
  • Δ 값이 ∞이면 전체 프로그램을 구성하는 page를 Working Set으로 간주

🚧 PFF(Page-Fault Frequency) Scheme

현재 시점에서 page-fault rate 어느정도인지 보고 특정 프로그램이 page fault를 얼마나 내는지 본다. 그리고 page fault를 많이 내는 프로그램에 페이지를 더 할당해준다.
만약에 page fault를 많이 내는 프로세스에게 더 할당해줄 페이지가 없다면 그 프로세스를 swap out

📌 Page Size의 결정

Page size를 감소시키면

• 페이지 수 증가

• 페이지 테이블 크기 증가

• Internal fragmentation 감소

• Disk transfer의 효율성 감소

  • Seek / rotation vs. transfer

• 필요한 정보만 메모리에 올라와 메모리 이용이 효율적

  • Locality의 활용 측면에서는 좋지 않음

따라서 트렌드는 Larger page size