[OS] Virtual Memory

Virtual Memory (= Logical Memory)

• 메인 메모리의 크기는 한정되어 있다. 그렇다면 메인 메모리의 크기보다 큰 프로세스를 실행시키고 싶으면 어떻게 해야 할까? 이를 위해 나온 개념이 Virtual Memory, 가상 메모리이다.
• 실행을 위해 프로그램의 모든 부분이 필요한 것은 아니다. 따라서 필요한 부분만 Physical Memory에 적재하고 전체가 다 적재된 것처럼 사용하기 때문에 Physical Address Space보다 Logical Address Space가 더 크다.
• 주소 공간을 여러개의 프로세스가 공유할 수 있도록 해준다.
• 더 효율적인 프로세스 생성이 가능하게 해준다.
• 페이지들이 swap in & swap out 될 수 있게 해줘야 적용이 가능하다.

---

Demand paging

가상메모리 구현 방식에는 Demand paging, demand segmentation이 있는데 그 중 demand paging에 대해 알아보자

• Demand paging은 page가 필요할 때만 메모리로 가져오는 방식이다.
• 장점: 프로세스 단위가 아닌 page 단위이기 때문에 I/O & memory 가 적게 듬, 응답이 빠름, 더 많은 유저가 사용할 수 있음
• Lazy swapper: page가 필요할 때만 메모리로 swap in 해주는 것 (page를 swap in & swap out 해주는 swapper를 pager라고 함)

Valid-Invalid Bit

• 어떤 page가 디스크에 있고 어떤 page가 메모리에 있는지 구별할 수 있어야 하는데 이를 위해 사용되는 개념이 valid-invalid bit이다.
• Page table에서 valid-invalid bit가 v (valid)라면 해당 page가 메모리에 적재되어 있다는 의미이다.
• Page table에서 valid-invalid bit가 i (invalid)라면
  • illegal: 해당 page가 프로세스의 주소 공간에 정의되지 않음
  • not-in-memory: 해당 page가 메모리에 적재되지 않고 디스크에만 존재하는 상태
  • obsolete: 디스크에 있지만, 오리지널 데이터가 업데이트 되어 최신 버전이 아닌 경우
  • 이 세 경우에 대해 page fault가 발생한다. page fault란 page가 아직 메모리에 적재되지 않아 발생하는 상황을 말한다.

---

Page Fault

• invalid page에 접근하면 HW (MMU) trap (page fault trap)이 발생 -> page fault handler를 호출해서 디스크에서 page를 가져오게 됨
• OS가 page fault를 핸들링 하는 과정 (중요!)

  

  1. OS가 다른 테이블을 체크해서 page fault가 illegal reference로 인한 것인지 not-in-memory 인건지 등등.. 원인을 파악한다.
     • 만약 illegal reference라면 중단
     • 만약 not-in-memory라면 (+ obsolete) 계속 진행한다.
  2. 빈 page frame을 가져온다. (만약 빈공간이 없다면 replace!)
  3. 디스크에서 page를 읽어서 frame에 적재한다.
     1. 디스크 I/O가 끝날 때까지 process는 'wait' 상태로 머무른다.
     2. 디스크 I/O가 끝나면 page table entries는 업데이트 된다. (frame #, valid-invalid bit = "valid"로)
     3. process를 Ready queue에서 제거한다. 나중에 dispatch!
  4. CPU가 프로세스에 할당 되면 page fault trap은 종료된다.
  5. page fault를 일으켰던 instruction을 재실행한다.

---

Performance of Demand Paging

• Page fault rate 0 <= p <= 1.0 이라고 하자.
  • 0일때는 page faults가 일어나지 않았다는 것, 1.0일 때는 모든 참조가 page fault를 유발한다는 것을 의미한다.
• Effective Access Time (EAT)
  • EAT = (1 - p) x memory access + p x (page fault 오버헤드 + page를 swap out하는 시간(필요하다면) + 디스크에서 page를 swap in하는 시간 + 프로세스 재시작 오버헤드)
  • EX) 메모리 접근 시간이 200 nanoseconds, 평균 page-fault service time이 8 milliseconds라고 하자.
  • EAT = (1 - p) x 200 + p x 8 milliseconds = (1 - p) x 200 + p x 8,000,000 = 200 + p x 7,999,800 이다.
  • 따라서 만약 1000번에 한번꼴로 발생하게 된다고 한다면 EAT = 8.2 microseconds고 이건 성능에 문제가 된다!
• 관련 개념
  1. Pure demand paging: 필요하기 전까지는 디스크에서 메모리로 swap-in하지 않는다. 프로그램을 시작할 때도 메모리에 page가 없는 상태에서 시작한다.
  2. Locality of reference: Page를 가져오는 것은 특정 시간 간격동안 매우 작은 세트의 page들에서 발생하게 된다. 따라서 공간 & 시간 지역성은 paging system을 실현 가능하게 해준다.
     • 참고) 공간 지역성은 어떤 page를 참조할 때 근처에 있는 것들을 참조할 가능성이 높다는 것이고 시간 지역성은 최근에 참조했던 page를 참조할 가능성이 높다는 특징이다.
  3. Copy-on-Write (COW): 프로세스에서 fork가 일어나서 child 프로세스가 생성되었을 때, 부모와 자식 프로세스는 초기에 메모리에서 같은 pages를 공유하게 되는 특징. 만약 어느 하나의 프로세스가 공유된 page를 수정한다면 그때 page가 복사된다. COW는 수정된 pages만 복사되기 때문에 더 효율적인 process creation을 가능하게 해준다.

     

• Demand paging에서는 어떻게 page fault를 줄일 수 있을지 생각하는게 중요하다.

---

Page replacement

• 만약 비어있는 frame이 없다면 어떻게 할까? Page replacement를 통해 replace를 해준다. 다만 변경될 page가 또 사용되지 않을지.. 등등 여러가지를 고려해서 변경해줘야 하는데 이때 최소한의 page faults를 발생시키기 위해 swap-out될 page를 선택하는 replacement algorithm을 사용하게 된다.
• Page replacement를 해줄 때 수정된 pages만 디스크에 작성하기 위해 modify (=dirty) bit (수정이 일어난 page를 표시하기 위한 용도)를 사용해서 page transfer의 오버헤드를 줄여준다. Page가 dirty하면 page를 복사해줘야 해서 access time이 늘어나기 때문!
• 기본적인 Page replacement 과정
  1. 디스크에서 요청된 page의 위치를 찾는다.
  2. 비어있는 frame을 찾는다. 만약 free frame이 있다면 사용하고, 없다면 page replacement algorithm을 사용해서 victim frame을 찾는다.
  3. 1번에서 찾은 page를 가져와서 free frame에 작성한다. page와 free frame tables를 업데이트한다.
  4. Process를 재시작한다.
• Page Replacement Algorithms: page-fault rate를 최소로 하는 알고리즘이어야한다. 아래에선 예제로 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 를 사용한다.
  1. First-In-First-Out (FIFO) Algorithm

     

     frame이 3개일 때와 4개일 때 과정

     • FIFO는 먼저들어온게 먼저 빠지는 알고리즘이다.
     • 위의 이미지를 보면 3개의 frame이 있을 땐 9 page faults, 4개의 frame이 있을 땐 10 page faults가 일어나는 것을 알 수 있는데 frame이 더 많이 있으면 더 적은 page faults가 일어날 것이라는 예상과 다르다. 이와 같은 현상이 일어나는 것을 Belady's Anomaly의 영향을 받는다고 한다.
  2. Optimal Algorithm

     

     • 미래에 대한 모든 정보를 알고 있는 경우, page fault를 최소화 시키는 page replacement 를 찾는 알고리즘이다. 즉, 가장 오랫동안 사용되지 않을 page를 먼저 빼는 알고리즘이다.
     • 가장 최소의 page fault가 일어나고 Belady's Anomaly 또한 발생하지 않는다.
  3. Least Recently Used (LRU) Algorithm

     

     • 미래가 아닌 과거에 대한 정보를 토대로 사용된지 가장 오래된 page를 먼저 빼는 알고리즘이다.
     • 성능은 FIFO와 OPT의 중간 정도이다. 일반적으로 빈번히 사용된다.
     • 구현
       • 모든 page에 대해 timestamp가 요구된다. 즉, 추가적인 메모리가 필요하다.
       • 또한 timestamp가 가장 작은 page를 찾는 과정이 필요하다.
       • 따라서 너무 많은 space/time 오버헤드가 발생한다. -> approximation model이 구현에 필요하다.
       • Counter를 이용하거나 Stack을 이용하는 방법이 있다. 하지만 이것도 오버헤드가 많이 발생해 커널에서는 이용할 수 없다. -> LRU Approximation Algorithm을 사용한다.
  4. LRU Approximation Algorithm
     • LRU와 비슷하게 동작하지만 오버헤드는 적은 알고리즘이라 커널에서도 사용가능하다.
     • Page별로 reference bit를 둬서 사용한다.
     • Page가 참조되면 reference bit = 1
     • Bit가 0인 page를 우선적으로 교체한다.
     • Timer를 두고 주기적으로 모든 page의 bit를 0으로 바꾼다. 가끔 timer 때문에 1이 되는 즉시 0으로 바껴서 victim이 되는 경우가 있는데 이는 second-chance algorithm(clock algorithm)이 해결한다.
     • Second-chance Algorithm: 차례대로 FIFO를 수행하면서 reference bit algorithm을 적용한다. 즉, page가 교체될 때 reference bit가 0이면 replace하고 1이면 reference bit를 0으로 바꾼다. (다시 한번 기회를 줌)

       

  5. Counting Algorithm
     • Page별로 몇 번 참조가 되었는지 카운트한다.
     • LFU (Least Frequently Used) Algorithm: 가장 작은 count의 page를 교체
     • MFU (Most Frequently Used) Algorithm: 가장 작은 count의 page는 이제 막 가져와서 아직 사용되지 않았을 것이라는 의견하에 나타난 algorithm

---

Allocation of Frames

• 여러개의 processes가 있을 때 page frames를 어떻게 할당할까?
• 각각의 process는 최소한의 개수의 pages를 필요로 한다. (SW, HW적으로 최소한을 가지고 있는게 유리)
• 할당 방식
  1. Fixed Allocation
     • Equal Allocation: 만약 100개의 frames가 있고 5개의 processes가 있다면 각각 20 page 씩 가짐
     • Proportional Allocation: process의 사이즈에 따라 비례하게 가짐
  2. Priority Allocation
     • 위에서 말한 Proportional Allocation과 동일하게 비례하게 나눠 가지지만 사이즈에 따라서가 아니라 우선순위에 따라 다르게 나눠가짐
• Global vs Local Replacement
  1. Global Replacement: 나에게 할당된 공간을 넘어 외부의 frame에서 replacement frame을 선택
  2. Local Replacement: 본인에게 할당된 frames 내에서만 replacement frame 선택

---

기타 Issues

• Thrashing
  • Thrashing이란 page faults가 너무 많아서 process가 pages를 swapping하는데 바쁜 상황을 말한다.
  • 너무 많은 process들이 동시에 나뉘어서 메모리에 있기 때문에 일어난다.
  • Trashing이 발생했을 경우 어떻게 해야할지를 정해주는 기준표가 있다.
    • Working-Set Model: Page fault가 얼마나 발생했는지를 확인해서 upper bound를 넘어가면 page fault가 많이 발생하여 trashing, lower bound 아래이면 page fault가 거의 일어나지 않기 때문에 process가 frame을 좀 더 얻게 해서 upper bound와 lower bound 사이를 유지하도록 한다.
• Memory-Mapped Files
  • File은 disk에 저장되어 있는데 I/O 접근이 일어나는 경우 오버헤드가 발생한다. 따라서 파일에 쓰고 싶은 내용을 메모리에 가져와서 쓰고나서 디스크로 보내자. -> 접근시간이 줄어든다.
• Prepaging: page faults의 수를 줄이기 위한 방식으로 process가 시작할 때 모든 pages나 일부의 pages를 참조하기 전에 메모리에 적재해두는 방식. 하지만 만약 prepaged pages가 사용되지 않는다면 I/O와 메모리는 낭비되는 것이 된다.
• Page size: Demand paging에서는 I/O 오버헤드가 있기 때문에 page 크기를 고려해야 한다. page 크기가 크면 I/O 오버헤드가 늘어나지만 page fault가 발생할 확률이 줄어들고, page 크기가 줄어들면 I/O 오버헤드는 줄어들지만 page fault가 발생할 확률이 늘어난다.
• I/O interlock: A 프로세스가 I/O 인터럽트가 걸리면 입출력 장치의 큐에 들어간다. 그동안 CPU는 B 프로세스에게 할당된다고 가정해보자. 이때 B 프로세스가 page fault를 일으키고 global replacement를 사용하여 A 프로세스의 page를 교체했다고 생각해보자. 그럼 A 프로세스의 입출력 요청이 끝나고 돌아오는 경우 A프로세스가 실행해야 하는 부분이 B 프로세스에 의해 사용되고 있게 된다. 이 문제를 해결하기 위한 것이 I/O interlock이다. Demand paging의 victim이 된다는 것을 알지만 이 부분을 써야 하기에 I/O lock을 걸어준다. 락이 걸려있으면 이 page를 교체하지 않고 넘어간다.

---

Reference

https://velog.io/@doyuni/2020-01-03-0001-%EC%9E%91%EC%84%B1%EB%90%A8-zpk4wvjl1v