Virtual Memory

Background

메모리 관리 전략은 모두 멀티프로그래밍을 위해 많은 프로세스를 동시에 메모리에 유지한다는 목표를 가진다. 그리고 대부분 실행 전에 전체 프로세스를 메모리에 유지해야 한다는 경향이 있다.

Virtual memory(가상 메모리)는 전체 프로세스가 메모리에 있지 않아도 실행할 수 있도록 하는 기술이다.

장점

• 실제 물리 메모리보다 크기가 큰 프로그램을 실행할 수 있다.
• 프로그래머에게 보여지는 논리 메모리를 물리 메모리와 분리하여서, 메인 메모리를 매우 큰 균일한 보조장치의 배열로 추상화 할 수 있다.
• 프로그래머가 메모리 장치 제한으로부터 자유로워진다.
• 프로세스 간에 파일이나 라이브러리를 공유하고, 공유메모리를 구현하게 한다.
• 프로세스 생성을 위한 효율적인 메커니즘을 제공한다.

단점

• 구현이 어렵다.
• 주의를 기울이지 않고 사용하면 성능을 크게 저하시킬 수 있다.

프로세스의 가상 메모리 공간은 프로세스가 어떻게 메모리에 저장되는지에 대한 논리적인 view다. 이 view에서는 특정 논리 주소에서 시작하고 메모리가 연속적으로 존재하는 것처럼 보인다.

물리 메모리는 frame으로 조직화되고, 프로세스에 할당되는 frame은 연속적이지 않을 수 있지만 논리 page를 물리 page frame에 맵핑하는 것은 MMU의 역할이다.

가상 메모리는 page 공유를 통해 프로세스 간 파일이나 메모리를 공유할 수 있게 한다.

• 시스템 라이브러리 (표준 C 라이브러리)와 같은 공유 객체를 가상 주소 공간으로 맵핑하여 여러 프로세스가 공유할 수 있게 한다.
• 가상 메모리는 한 프로세스가 다른 프로세스와 공유하는 메모리 영역을 만들 수 있게 함으로써 두 개 이상의 프로세스가 공유 메모리를 통해 소통할 수 있게 한다.
• 메모리 영역을 공유하는 프로세스들은 자신만의 가상 주소 공간으로 인식하지만 실제로는 공유되는 공간이다.
• Page는 fork() system call을 통해 프로세스가 생성될 때 공유될 수 있다. 이로 인해 프로세스 생성 속도가 향상된다.

Demand Paging

실행 가능한 프로그램을 보조장치에서 메모리로 어떻게 로드할까?

1. 모든 프로그램을 로드한다.

   • 문제는 초기에 불필요하게 모든 프로그램이 메모리에 로드된다는 점이다.
   • 사용자 선택에 따른 옵션으로 실행되는 프로그램이 선택되지 않아도 메모리에 로드된다.

2. 필요한 page들만 로드한다.

   • 이 기법을 Demand Paging이라고 한다.
   • 가상 메모리 시스템에서 일반적으로 사용된다.
   • demand-paged 가상 메모리를 사용하면 page는 실행 중 필요할 때만 로드된다. 사용되지 않는 페이지들은 로드되지 않는다.

Basic Concepts

가장 일반적인 컨셉은 page가 필요할 때만 메모리에 로드하는 것이다. 프로세스가 실행 중일 때 어떤 page는 메모리에 있고, 어떤 페이지는 보조장치에 있을 것이다. 그렇다면 사용/비사용 메모리는 어떻게 구분할까?

1. Valid-Invalid bit를 활용한다.

   • Bit가 valid이면 연관 페이지는 합법적이며, 메모리에 로드된다.
   • 반대의 경우 허용되지 않으며, 보조장치에 위치한다.

2. Page-table entry

   • 메모리에 있는 page는 valid
   • 현재 메모리에 없는 page는 invalid
   • MMU 주소 변환 과정에서 valid-invalid bit가 invalid면 page fault로 OS에 trap을 발생시킨다.

Page fault 대처하는 절차

1. PCB와 함께 저장되는 내부 테이블을 검사하여 유효한 메모리 접근인지 아닌지 확인한다.
2. 메모리 참조가 유효하지 않으면 해당 프로세스를 종료한다.
3. 메모리 참조가 유효하지만 아직 page in이 되지 않았으면 해당 페이지를 메모리에 page in 한다.
4. 가용한 frame을 찾는다.
5. page를 새롭게 할당된 frame에 읽기 위해 보조장치 연산을 스케줄한다.
6. 보조장치 읽기가 끝났다면 내부 테이블을 수정한다.
7. trap에 의해 방해받은 연산을 재시작한다.

위 과정을 거치면 프로세스는 그 page가 마치 계속 있던 것처럼 접근할 수 있다.

Pure demand paging은 필요하기 전까지는 page를 메모리로 로드하지 않는다. 극단적인 경우 다음과 같은 수순을 밟는다.

1. 초기 메모리에 page가 없이 프로세스가 시작된다.
2. 프로세스의 첫 명령어에 대한 instruction pointer가 non-memory-resident page인 경우 프로세스는 즉시 fault가 발생한다.
3. 필요한 모든 page가 메모리에 있을 때까지 fault를 발생시키며 실행된다.

이론적으로 어떤 프로그램은 instruction 수행 시 여러 새 page에 접근하는데, 이때 여러 page fault가 발생할 수 있다. 이는 용납할 수 없는 시스템 성능이다.

다행히도 이런 현상은 잘 발생하지 않으며, 프로그램은 참조 시 지역성을 가지기 때문에 충분한 성능을 보인다.

Demand paging을 위한 하드웨어 지원은 paging, swapping과 유사하다.

1. Page table은 entry를 invalid로 표시할 수 있다.
2. 보조장치는 메인 메모리에 있지 않은 page를 저장한다.
   • 보통 고속 디스크나 NVM 장치에 저장한다.
   • Swap 장치라고 알려져있다.

Demand paging 핵심 요구사항

• Page fault 후 재실행 능력이 있어야 한다.
• Page fault 시 저장한 프로세스를 정확히 같은 위치, 같은 상태에서 시작해야 된다.

Page fault는 어떤 메모리 참조에도 발생할 수 있다. 만약 page fault가 instruction fetch 과정에서 발생했다면, fetching을 재시작 할 수 있다. 또 page fault가 operand fetching 과정에서 발생했다면 다시 instruction을 fetch와 decode하고 operand를 fetch 해야 한다.

Free-Frame List

Page fault 시 OS는 보조장치에서 page를 메모리로 가져온다. Page fault를 처리하기 위해 OS는 가용 프레임 리스트를 관리해야 한다. 첫 시스템 시작 시 모든 가용 메모리가 리스트에 추가된다. 또한 가용 프레임은 stack이나 heap이 확장될 때도 할당되어야 한다.

OS는 zero-fill-on-demand 방식으로 가용 프레임을 할당한다. 가용 프레임은 할당되기 전에 0으로 채워진다. 보안 상 이전의 내용을 지운다. 만약 가용 프레임이 demand paging으로 요청되었는데 list가 0이거나 임계값 아래로 떨어지면 다시 채워줘야 하며, 이를 page replacement라고 한다.

Performance of Demand Paging

Copy-on-Write

fork() system call을 통해 부모 프로세스의 복제본인 자식 프로세스를 생성할 수 있는데, 이때 자식 프로세스는 부모의 주소 공간을 복사하고, 부모의 page를 복제한다. 하지만 많은 자식 프로세스가 exec() system call을 수행하는데, 이 경우 부모 주소 공간의 복제가 불필요하다.

Copy-on-write는 fork() 할 때 모든 페이지를 복사하는 것이 아니라, 쓰기 할 때 복사하는 것을 말한다. 수정될 수 없는 코드는 부모-자식 간 공통 page를 참조하여 공유한다. 자식 프로세스 생성 초기에 demand paging을 생략할 수 있기 때문에 프로세스 생성을 더 빠르게 하고, 새로 생성되는 프로세스에 배정되는 page의 수를 최소화 할 수 있다. 이는 Windows, Linux, macOS에서 사용되는 기법이다.

Page Replacement

이어지는 예제에서는 각 page는 첫 참조 시 한 번만 fault가 발생함을 가정한다. 만약 프로세스 당 10개의 page를 요구했지만 실제로는 그의 절반인 5개만 사용한다면, demand paging으로 사용되지 않을 5개를 load하기 위한 I/O를 줄일 수 있다. 또한 실행하는 프로세스의 수를 두 배로 늘려 다중 프로그래밍의 차수를 높일 수 있다. 40개 frame만 있어도 8개의 프로세스를 실행할 수 있는 것이다.

하지만 다중 프로그래밍의 차수를 늘리면 메모리 과할당이 발생한다. 만약 6개의 프로세스를 실행하는데 6개 모두 원래 요구인 10 page의 절반인 5개의 page를 사용한다고 가정한다. 6개의 프로세스를 실행하면서도 10개의 frame이 남는다. 이때 갑자기 프로세스가 특정 data set을 위해 추가로 5개 page를 더 사용한다면? 총 60개의 frame이 필요하나 현재 frame은 40개 밖에 없어서 불가능하다.

메모리 과할당 상황에서 OS가 선택할 수 있는 옵션은 다음과 같다.

1. 프로세스를 종료한다.

   • 사용자는 프로세스가 paged 시스템에서 실행 중인 것을 모른다.
   • 갑자기 프로세스를 종료하는 것은 좋은 옵션이 아니다.

2. Standard Swapping을 통해 프로세스를 swap out하여 멀티프로그래밍의 차수를 줄인다.

   • 하지만 standard swapping은 전체 프로세스 복사에 대한 오버헤드로 더 이상 사용되지 않는다.

3. Page Swapping과 Page replacement를 결합한다.

   • 대부분의 OS가 사용하는 방식이다.

이렇게 프로세스가 원하는 page가 보조장치에 있고, 시스템에 가용 frame이 없는 상황에서 page 할당을 가능하게 해주는 것이 Page replacement다.

Basic Page Replacement

가용한 free frame이 없다면, 현재 사용되지 않고 해제 가능한 frame을 찾아 교체해야 한다. Swap space에 frame의 콘텐츠를 쓰고, 해당 page가 더 이상 메모리에 있지 않다고 page table을 수정한다. 이 과정에서 2번의 page 이동이 필요하기 때문에 page-fault service time과 effective access time이 증가한다.

Modify bit (dirty bit)

각 page 혹은 frame은 연관 하드웨어에 modify bit가 있다. Page가 수정되면 하드웨어에 의해 modify bit가 설정된다. 교체할 page를 선택할 때 modify bit를 평가하며, bit가 세팅되어있으면 page는 수정되었다는 뜻이고, 보조장치에 기록해야 한다. Bit가 세팅되어있지 않으면 페이지는 메모리에 적재된 뒤로 수정되지 않은 read-only page라는 뜻이다. 이러한 page는 필요 시 보조장치로 이동하는 것이 아니라 폐기할 수 있다. 따라서 page replacement에 소요되는 I/O 시간이 절반으로 줄어든다.

Page replacement는 demand paging의 기본 구성 요소이며, 논리 메모리와 물리 메모리의 분리를 완성한다.

Demand paging을 사용하지 않으면 논리 주소와 물리 주소가 다를 수 있지만 모든 page가 메모리에 있어야 한다. Demand paging을 사용하면 논리 주소 공간의 크기가 물리 메모리에 제한되지 않는다. Demand paging에는 해결해야 할 문제 두 가지가 있다.

1. Frame-allocation algorithm
   • 여러 프로세스가 메모리에 있을 때, 각 프로세스에 몇개의 frame을 할당할 것인지 결정
2. Page-replacement algorithm
   • Page를 교체해야 할 때 어떤 frame을 교체할 것인지 결정

여러 page 교체 알고리즘이 있으며, OS마다 교체 스킴이 존재할 것이다. 하지만 공통적으로 page 교체 알고리즘을 결정하는 기준은 낮은 page-fault rate이다. 알고리즘 평가는 아래와 같은 메모리 참조열에 대해 replacement를 실행하고, page-fault 수를 측정한다.

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

참조열은 인위적으로 생성할 수도 있고, 시스템을 추적해 생성할 수도 있다. 시스템 추적은 너무 많은(초당 백만 개) 데이터를 생성한다는 단점이 있다.

page p를 참조한 이후 메모리에 이미 적재된 page에 대한 이어지는 참조는 page fault가 일어나지 않는다고 가정한다. 알고리즘을 평가하려면 가용한 frame 수를 알아야 한다. Frame의 수가 늘어날 수록 할당할 수 있는 자리가 많기 때문에 page fault 수는 줄어든다.

아래와 같은 참조열이 있을 때, 3개의 frame이 가용하다면 첫 page 로드 시 세 번의 fault만 발생한다. 1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1

FIFO Page Replacement

FIFO 알고리즘은 가장 간단한 page replacement 알고리즘이다. 희생자 선택 기준은 page가 메모리에 들어온 시간과 관계가 있으며, page 교체 시 가장 오래된 page가 선택된다.

교체는 큐의 head에 있는 원소가 교체되고, 새로 투입되는 원소는 tail에 투입된다. 원소가 이미 메모리에 적재되어 있으면 교체가 수행되지 않고 참조한다.

FIFO 예제

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

초기값: empty|empty|empty

1. 7|empty|empty
2. 7|0|empty
3. 7|0|1
4. 2|0|1
5. 2|3|1
6. 2|3|0
7. 4|3|0
8. 4|2|0
9. 4|2|3
10. 0|2|3
11. 0|1|3
12. 0|1|2
13. 7|1|2
14. 7|0|2
15. 7|0|1

총 15번의 page fault 발생.

FIFO 결론

이 알고리즘은 이해하기는 쉬우나 항상 좋은 퍼포먼스를 보이지는 않는다. 교체되는 페이지가 오래전 사용되고 더 이상 사용되지 않는 모듈일 수 있으나, 반대로 초기화 되고 지속적으로 사용되는 변수일 수도 있기 때문이다. 단 활발히 사용되는 page를 교체하더라도 제대로 동작하기는 한다. Page fault가 즉시 일어날 뿐. 잘못된 page 교체는 fault rate을 높이고 프로세스 실행 속도를 느리게 하지만 잘못된 실행을 야기하지 않는다.

FIFO 알고리즘은 frame을 더 추가해도 page fault가 높아지는 벨라디의 모순이 발생할 수 있다. 벨라디의 모순은 프로세스에 메모리를 더 할당하면 성능이 좋아질 것으로 가정하지만, 이 가정이 항상 옳은 것이 아니라는 사실을 알려준다.

Optimal Page Replacement

Optimal 알고리즘은 말 그대로 최적의 알고리즘이며, 벨라디의 모순에서 자유롭다. Optimal 알고리즘은 미래에 가장 오랫동안 사용되지 않을 page를 교체하는 방법이다. 같은 frame 수라면 이 방법이 가장 작은 page-fault rate을 도출한다.

Optimal 예제

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

초기값: empty|empty|empty

1. 7|empty|empty
2. 7|0|empty
3. 7|0|1
4. 7|0|1
5. 2|0|3
6. 2|4|3
7. 2|0|3
8. 2|0|1
9. 7|0|1

총 9번의 page fault 발생.

Optimal 결론

Optimal은 page fault가 9번으로 15번인 FIFO 보다 적다. 같은 frame으로 이 알고리즘보다 page fault를 적게 일으키는 알고리즘은 없다. 안타깝게도 Optimal 알고리즘은 미래에 대한 정보를 알아야 하기 때문에 구현하기 어렵다는 단점이 있으며, 보통은 비교 목적으로 사용된다.

LRU Page Replacement

Optimal 알고리즘을 적용하지 못한다면 근사한 알고리즘이라도 적용해야 할 것이다. 미래에 대한 근사치로 최근의 과거를 사용하는 방법을 Least Recently Used (LRU) 알고리즘이라고 한다. 각 page는 마지막으로 사용된 시간을 가지며, 가장 오랫동안 사용되지 않은 page를 교체하는 방법이다.

LRU 예제

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

초기값: empty|empty|empty

1. 7|empty|empty
2. 7|0|empty
3. 7|0|1
4. 2|0|1
5. 2|0|3
6. 4|0|3
7. 4|0|2
8. 4|3|2
9. 0|3|2
10. 1|3|2
11. 1|0|2
12. 1|0|7

총 12번의 page fault 발생.

LRU 결론

LRU는 FIFO보다 좋고, OPT보다 나쁘다. 보통은 괜찮은 결과를 도출하며, 자주 사용되는 알고리즘이다. 또한 벨라디의 모순으로부터 자유롭다.

LRU는 최근 사용된 시간 혹은 순서를 기록해야 하므로 clock이나 stack을 이용해 구현해야 한다. 단, LRU 알고리즘은 TLB 레지스터 이상의 하드웨어 지원 없이는 구현이 불가하다. 메모리 참조 시 clock이나 stack을 업데이트해야 하는데, 소프트웨어 수준에서 구현한다면 너무 많은 interrupt를 허용해야 하기 때문에 메모리 참조 속도가 최대 10배 느려질 것이기 때문이다.

Page-Buffering Algorithm

Page-Buffering 알고리즘은 Page replacement 알고리즘과 함께 사용된다. 시스템이 가용 frame pool을 운영하며 교체되는 page가 빠져나오는 것을 기다리지 않고도 새롭게 page in 되는 page가 실행될 수 있게 만드는 기법이다.

가용 frame pool을 유지하면서 modified page를 관리하기도 한다. Page 장치가 IDLE 상태면 수정된 page가 보조장치에 기록되며, modify bit가 리셋된다. 이 방법을 사용하면 실제 페이지 교체 시 unmodified된 page를 디스크에 쓸 필요가 없을 가능성이 높아진다.

또 하나의 수정 가능한 부분은, 가용 frame pool을 유지하면사 각 frame에 어떤 page가 있었는지 기억하는 것이다. Page fault가 발생했을 때 이 page가 가용 frame pool에서 재사용 가능한지 확인한다. 만약 아니라면 가용 frame을 선택해 읽어온다. Frame이 보조장치에 써질 때 frame 내부 콘텐츠가 수정되지 않은 경우 이 frame이 다른 page에 의해 재사용되기 전까지는 콘텐츠를 재사용 할 수 있다. 이 방법으로 I/O 연산을 줄일 수 있다.