[OS] Virtual Memory (2/2)

앞선 포스트에서 가상 메모리(Virtual Memory)는 논리적 메모리와 물리적 메모리을 분리해 실제 메모리 크기와 상관 없이 가상의 메모리를 사용하는 것이 장점 이라고 설명했다. 그렇다면 가상 메모리에서 프로세스의 크기가 남은 물리적 메모리의 크기보다 더 클 경우 어떻게 할까?

Swapping

Swapping

swapping이란 main memory에 있는 일부 프로세스를 secondary memory(HDD, SSD, Flash 등)으로 내보내고 실행할 프로세스를 secondary memory에서 main memory로 불러오는 작업을 말한다.

• swap out: secondary memory로 내보내는 과정
• swap in: main memory로 불러오는 과정
• swap time: swap out time + swap in time

swapping은 디스크 액세스가 필요하기 때문에 전체 프로세스를 swapping하는 것은 굉장히 비효율적이다. 따라서 현대 OS는 swap time을 최소화하는 것이 중요하다.

어떻게 Swap time을 최소화할 수 있을까 ?

프로세스 전체를 swapping하는 것이 아닌, 프로세스의 일부만을 swapping해 swap time을 줄일 수 있다. 이것을 demad paging이라고 부른다.

Demand Paging

Demand Paging

demand paging이란 프로그램 실행 시작 시에 프로그램 전체를 디스크에서 물리 메모리로 로드하는 것이 아닌, 프로그램을 시작하기 위해 필요한 일부만 로드하고 나머지는 필요할 때(on demand) 로드하는 방법을 말한다.

장점

• disk I/O가 줄어들어 response time이 줄어든다.
• 프로그램의 일부만 로드해 실행할 수 있기 때문에 메모리 사용량이 줄어들고, 멀티프로그래밍에 용이하다.

사용할 페이지가 메모리에 로드되어 있는지 어떻게 알 수 있지 ?

Valid-Invalid bit

각 프로세스의 page table에는 valid-invalid bit를 가지고 있다.

• valid-invalid bit = 1 → valid(해당 페이지가 메모리에 있다)
• valid-invalid bit = 0 → invalid(해당 페이지가 메모리에 없다)

참조할 페이지가 메모리에 없다면 ?

address binding할 때, valid-invalid bit가 0(invalid)이면 page fault가 발생했다고 말한다.
page fault는 참조하려는 페이지가 메모리에 존재하지 않는 것을 말한다.
page fault가 발생하면 OS에게 trap(software interrupt)을 발생시키고, OS는 page fault를 처리해야 한다.

OS가 page fault를 처리하는 방법

Page Fault

1. 메모리 참조가 발생하면 OS는 해당 참조가 잘못된 참조인지, 정상적인 참조인지 먼저 판단한다.

• 잘못된 참조(Illegal reference) → abort
• 정상 참조 → valid-invalid bit 확인

2. valid-invalid bit가 0이라면, trap을 발생시킨다.
3. OS는 메모리에서 빈 프레임(frame)을 찾고 (빈 프레임이 없을 경우 victim frame을 찾아 swap out)
4. 해당 페이지를 디스크에서 찾아 메모리의 빈 프레임에 swap in 한다.
5. 페이지 테이블에 해당 페이지의 레퍼런스를 저장하고 valid-invalid bit를 1로 설정한다.
6. 프로세스를 재실행한다.

page fault time = swap page out + swap page in + restart overhead

✅ demand paging system은 page fault rate를 최소화하는 것이 가장 중요하다 !!

Page Replacement

프로세스가 page를 참조할 때 page fault가 발생하게 되면, OS는 메모리에서 빈 프레임 찾아 원하는 페이지를 빈 프레임에 로드한다. 이때 만약 메모리에 빈 프레임이 없다면, 사용하지 않는 페이지를 찾아 디스크로 내보내야 한다.
page replacement는 메모리에서 사용하지 않는 페이지를 찾아 page out하는 작업을 말한다. page replacement는 page fault가 최소로 일어나는 페이지를 page out해야 한다.

Page Replacement 방법

Page Replacement

1. 디스크에서 원하는 페이지를 찾는다.
2. 빈 프레임을 찾는다.

• 빈 프레임이 있을 경우 해당 프레임에 페이지를 로드하고 페이지 테이블을 수정한다.
• 빈 프레임이 없을 경우 page replacement algorithm을 통해 희생될 프레임을 찾아 디스크로 swap out한다.
  
  • modify bit를 확인하여 page의 수정이 있을 경우만 swap out한다. (disk I/O를 최소화하기 위함)

3. 비워진 프레임에 페이지를 로드하고 페이지 테이블을 수정한다.
4. 프로세스를 재실행한다.

Page Replacement Algorithm

page replacement alogrithm의 목적은 page fault 비율을 최소화하는 것이다.

FIFO Algorithm

가장 간단한 페이지 교체 알고리즘으로 FIFO(first-in first-out)의 흐름을 가진다.
먼저 물리 메모리에 들어온 페이지 순서대로 페이지 교체하는 알고리즘

장점

• 이해하기 쉽고, 프로그램하기도 쉽다.

단점

• 오래된 페이지가 항상 불필요하지 않은 정보를 포함하지 않을 수 있다. (초기 변수 등)
• 처음부터 활발하게 사용되는 페이지를 교체해서 page fault rate를 높일 수 있다.
• Belady's anomaly: 페이지 프레임 수를 늘려도 되려 page fault가 더 많이 발생하는 모순이 존재한다.

Belady's anomaly

Optimal Algorithm

앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체하는 알고리즘

장점

• 알고리즘 중 가장 낮은 page fault rate를 보장한다.

단점

• 구현의 어려움이 있다.

→ 모든 프로세스의 메모리 참조의 계획을 미리 파악할 방법이 없음

Least Recently Used(LRU) Algorithm

가장 오랫동안 사용되지 않은 페이지를 선택하여 교체하는 알고리즘
대체적으로 FIFO 알고리즘보다 우수하고, OPT 알고리즘보다는 떨어진다.

구현 방법

• Counter
  • 페이지 테이블의 모든 엔트리에 counter를 가짐
  • 해당 페이지가 참조되었을 때 counter에 시간을 업데이트한다.
  • 페이지 교체가 필요할 때, 가장 작은 counter를 가지는 페이지를 교체한다.
  • 단점
    • 가장 작은 counter를 찾기 위해 탐색 시간이 필요하다.
    • 메모리 참조가 일어날 때마다 counter를 업데이트해야 한다.
• Reference bit
  • Counter가 너무 많은 리소스를 요구하기 때문에 이를 최소화한 방법
  • 교체되면 reference bit → 0, 참조되면 reference bit → 1
  • 정확한 순서를 알 순 없지만, 해당 페이지가 참조되었는지 아닌지 판단할 수 있음
• Additional-Reference-Bits Algorithm
  • 페이지 테이블의 모든 엔트리에 8 비트 변수를 가짐
  • 해당 페이지가 참조되었을 때, 맨 앞 비트를 1로 바꿔줌
  • 일정한 시간이 지나면, 오른쪽으로 1bit shift
  • 가장 최근에 참조된 페이지의 값이 가장 크기 때문에 가장 작은 페이지가 교체된다.

---

Reference

10th edition - Operating System Concepts