[운영체제] 8장: Virtual Memory

Types of Memory

• Real Memory: 메인 메모리
  • 프로그램 전체가 메인 메모리에 적재되어 있다.
• Virtual Memory: 메인 메모리 + 디스크 메모리
  • 프로그램의 일부만 메인 메모리에 적재되어 있고 나머지는 하드 디스크에 있다.
  • real memory보다 훨씬 많은 프로그램들을 메인 메모리에 적재할 수 있다.

Execution of a Program

• OS는 프로그램의 일부를 메인 메모리로 가져 온다.
  • Resident set: 프로그램 중 메인 메모리에 적재되어 있는 부분
• 실행하려는 코드나 데이터가 메인 메모리에 없다면 interrupt가 발생한다.
• OS는 interrupt가 발생한 프로세스를 blocked queue로 옮긴다.
• 하드 디스크의 I/O 작업을 하는 동안 프로세서를 넘겨 다른 프로세스가 실행되도록 한다.
• I/O 작업이 끝나고 I/O interrupt가 발생하면 OS는 그 프로세스를 ready queue로 옮긴다.
• 메모리의 크기가 제한적이기 때문에 필요한 페이지를 가져오려면 이미 메모리에 있던 페이지를 버려야 한다. 이때 여전히 프로세스의 일부가 메인 메모리 상에 존재하기 때문에 suspend 상태가 되는 것은 아니다.

Thrashing & Locality

• Thrashing
  • 프로세스 일부를 swapping 하는 과정에서 하드 디스크로 옮겨간 조각이 직후에 필요한 경우
  • 프로세서는 프로세스 조각들을 swapping 하는 데에 시간을 낭비하게 된다.
• Principle of Locality
  • locality of reference 때문에 thrashing의 발생 가능성이 낮다.

Paging

Page Table Entries

• 각 프로세스는 고유의 페이지 테이블을 가지고 있다.
• P bit
  • P == 1: 페이지가 메인 메모리에 존재한다.
  • P == 0: 페이지가 하드 디스크에 존재한다.
• M bit
  • M == 1: 메인 메모리에 올라와서 데이터가 변경된 적이 있다.
    • 페이지를 버릴 때 하드 디스크에 write 작업이 필요하다.
  • M == 0: 데이터 변경된 적이 없다.
  • 페이지 안에 프로그램 코드만 존재한다면 M == 1 경우는 없다. (코드가 변경될 수는 없음)

Address Translation in a Paging System

• Page Table Ptr: 페이지 테이블의 시작 주소
  • 페이지 테이블도 데이터로서 메모리에 존재하기에 필요하다.
  • Virtual address의 Page #(인덱스 역할) + Page Table Ptr 을 통해 특정 entry에 액세스한다.
• 페이지 테이블의 크기가 한 페이지 이내일 경우의 그림

Page Tables

• 프로그램의 크기가 커진다.
  → 한 프로그램을 구성하는 페이지 개수가 많아진다.
  → 페이지 테이블의 entry가 많아진다.
  → 페이지 테이블의 크기가 페이지 하나의 크기보다 커질 수 있다.
  → 페이지 테이블이 여러 페이지에 걸쳐서 존재한다.
  → Virtual memory이기 때문에 원하는 페이지 정보를 담고 있는 페이지 테이블이 존재하는 페이지가 메인 메모리 상에 없을 수 있다.

• Two-Level Hierarchical Page Table

• User address space = 4*2^30 bytes (= 프로그램 최대 크기)
• 1 page 크기 = 2^12 bytes = 4 kbytes (전제)
• 프로그램 최대 페이지 수 = 4-Gbyte / 4-kbyte = 2^20 개
• 1 page entry 크기 = 4 bytes (전제)
• 페이지 테이블 크기 = 2^20 * 4 bytes = 2^22 bytes > 4 kbytes(1 page 크기)
• 페이지 테이블 나누기: 2^22 bytes / 4 kbytes = 2^10 개
• 페이지 테이블을 여러 개로 나눴으니 페이지 테이블의 정보를 담을 페이지 테이블이 필요하다.
  • 페이지 테이블을 위한 페이지 테이블의 크기 = 4 bytes * 2^10 = 4 kbytes
  • 페이지 테이블의 크기가 1페이지 크기와 같으므로 root 페이지 테이블이 된다.
  • root 페이지 테이블의 크기는 1페이지 크기보다 작거나 같다.
• 특정 페이지 주소를 찾기 위해서는 상위 페이지 테이블부터 탐색해야 한다.
• root 페이지 테이블의 entry에는 찾으려는 페이지 정볼르 담고 있는 페이지 테이블의 시작 주소를 가리키고 있다.

• 32-bit Virtual address: 프로그램 최대 크기 2^32 bytes (4-Gbyte)
• 첫 번째 10-bit: root 페이지 테이블에서의 인덱스
  • root 페이지 테이블의 entry 개수 = 2^10 개
• 두 번째 10-bit: 2nd 페이지 테이블에서의 인덱스
  • 한 페이지에 2^10개의 page entry가 들어갈 수 있다.
• 12-bit offset: 1페이지 크기 2^12 bytes

  1페이지 크기 -> 2^10 bytes
  → 프로그램 최대 페이지 수 = 2^32 / 2^10 = 2^22 개
  → 1st 페이지 테이블 크기 = 4 bytes 2^22 = 2^24 bytes
  → 2nd 페이지 테이블의 entry 개수 = 2^24 bytes / 2^10 bytes = 2^14 개
  → 2nd 페이지 테이블 크기 = 4 bytes 2^14 = 2^16 bytes
  → 3rd 페이지 테이블의 entry 개수 = 2^16 bytes / 2^10 bytes = 2^6 개
  → 3rd 페이지 테이블 크기 = 4 bytes * 2^6 = 2^8 bytes
  → 3rd 페이지 테이블 = root 페이지 테이블
  💡 페이지 테이블의 크기가 1페이지 크기보다 크다면 비트 수는 1페이지 크기 / 1 page entry 크기의 지수이다.
  

Inverted Page Tables

• 메인 메모리에 적재되어 있는 페이지에 대한 페이지 테이블
• k번째 entry에는 메인 메모리의 k번째 페이지 프레임에 저장된 페이지 정보를 저장한다.
• page entry에 포함된 정보
  • 페이지 번호
  • 프로세스 ID
  • 컨트롤 비트
  • chain pointer: 반드시 필요한 것은 아니지만 원하는 페이지 정보를 빠르게 찾기 위해 사용된다.
• 페이지 테이블을 순회하면서 원하는 entry를 찾았을 때 그 인덱스가 메인 메모리 상에서 프레임 번호이다.
• 해싱 연산 값이 같은 것끼리 연결해서 chain pointer로 순회한다. 페이지 테이블의 chain 값에 다음 entry의 인덱스가 저장되어 있다.
• hash function의 Output = chain으로 순회할 entry 중 시작 프레임 번호
• 장점: 페이지 테이블의 크기가 작다.
• 단점: 원하는 entry를 찾는 데에 시간이 오래 걸릴 수 있다.
• hierarchical page table과 비교하여 공간적으로는 우수하지만 시간적으로는 우수하지 않다.

Translation Lookaside Buffer

• 가장 최근에 접근한 페이지 테이블의 entry(page #, frame #)를 저장한다.
• 캐시처럼 작동한다.
  • 찾으려는 페이지 번호에 해당하는 entry가 TLB에 있는지 확인한다.
  • hit → 바로 프레임 번호 사용 / miss → 페이지 번호로 페이지 테이블 탐색
  • 페이지 테이블에서 찾은 entry의 P비트가 1이면 프레임 번호로 real address를 구성하고 entry를 TLB에 올린다.
  • P비트가 0이면 page fault가 발생하여 하드 디스크에서 해당 페이지를 찾아서 메모리에 올린다.

Page Size

• 페이지의 크기가 작다면
  • 하나의 프로그램을 구성하는 페이지의 개수가 많아진다.
  • 페이지 테이블의 entry가 많아지는 것이므로 테이블의 크기가 커진다.
  • 원하는 페이지 정보를 담고 있는 페이지 테이블이 메인 메모리에 없을 수 있다.
  • page fault가 적게 발생한다.
• 페이지의 크기가 크다면
  • page fault가 많이 발생한다.

Segmentation

- 각 프로세스는 고유의 세그먼트 테이블을 가진다.
- Length: Offset이 Length보다 작은 지 확인해야 한다. (Protection)
- Segment Base: 메모리 상에서 세그먼트 시작 주소 (Physical address)
- Relocation: Segment Base + Offset (Physical address)

Address Translation in Segmentation

- Seg Table Ptr: 세그먼트 테이블의 시작 주소
- Seg #: 세그먼트 테이블에서의 인덱스 역할

Combined Paging and Segmentation

• 메인 메모리는 동일한 크기의 페이지 프레임으로 나눈다.
• 프로그램을 먼저 세그먼트 단위로 나누고, 각 세그먼트를 페이지 프레임 크기로 나눈다.
  • paging 기법의 sharing, protection 문제를 해결할 수 있다. (segmentation 장점)
  • external fragmentation이 발생하지 않아 compaction이 필요 없다. (paging 장점)
  • internal fragmentation이 세그먼트 개수만큼 발생할 가능성이 있다.

- Virtual Address; Page Number: 세그먼트 내에서의 페이지 번호
- Segment Table Entry; Length: 마지막 페이지 번호 (페이지 개수)
- Segment Table Entry; Segment Base: 세그먼트에 속한 페이지에 대한 페이지 테이블의 시작 주소
- 메모리 적재나 수정 작업은 페이지 단위로 처리되기 때문에 세그먼트 테이블 entry에는 P, M 비트가 필요 없다.
- 세그먼트 테이블은 root 페이지 테이블 역할로 항상 메인 메모리에 적재한다.

- Seg Table Ptr: 세그먼트 테이블의 시작 주소
- Seg #: 세그먼트 테이블에서의 인덱스 역할
- 세그먼트 테이블 entry의 Segment Base + Page #로 페이지 테이블의 entry를 찾는다.

Fetch Policy

Demand paging

• 요청한 페이지만 메인 메모리에 올린다.
• 프로세스가 처음 실행될 때 page fault가 많이 발생한다.
• 장점: 필요한 페이지만 메모리에 적재되므로 메모리 사용 면에서 효율적이다.
• 단점: 하드 디스크 액세스 횟수(page fault)가 많아서 시간이 오래 걸린다.

Pre-paging

• 요청한 페이지보다 많은 페이지를 메인 메모리에 올린다.
• 프로세스가 처음 실행될 때 효율적이다.
• 장점: 하드 디스크 액세스 횟수가 적어서 시간이 적게 걸린다.
• 단점: 당장 필요하지 않은 페이지가 메인 메모리에 적재되어 있으므로 메모리 사용 면에서 비효율적이다.

Demand paging!

Replacement Policy

page fault 발생 → 프로세스 blocked → 실행 속도 감소

Optimal policy

• 앞으로 사용되지 않거나 오랫동안 사용되지 않을 페이지를 버린다.
• page fault가 가장 적게 발생하는 알고리즘이다.
• 미래 상황을 모두 알고 있다는 가정이므로 실제로 구현 불가능하다.

Least Recently Used

• 가장 오랜 시간동안 사용되지 않은 페이지를 버린다. (reference of locality)
• 각 페이지마다 마지막 사용 시간에 대한 태그가 필요하다. (control bit → 공간적 오버헤드가 크다.)
• 버릴 페이지를 결정하기 위해 모든 페이지들의 마지막 사용 시간을 비교해야 한다. (시간적 문제)
• page fault 면에서 optimal policy와 유사한 성능을 보인다.

First-In, First-Out

• 가장 먼저 메인 메모리에 적재된 페이지를 버린다. → 포인터가 필요하다.
• page fault는 많이 발생하지만 LRU의 시간적, 공간적 문제가 발생하지 않는다.
• FIFO Anomaly: 할당된 페이지 프레임 수가 증가하는데 page fault가 증가하는 현상

Clock policy

• LRU에 가까운 성능을 보인다. (page fault)
• control bit에는 use bit라는 1비트만 필요하므로 공간적 오버헤드가 작다.
• 페이지가 메인 메모리에 처음 적재 됐을 때는 use bit == 0 이다.
• 페이지가 실행되고 있을 때는 use bit == 1 이다. 거의 항상 1

- next frame pointer: 마지막으로 교체한 프레임의 다음 프레임을 가리킨다.
- 페이지 교체가 발생할 때만 포인터가 순회한다.
- 버릴 페이지를 탐색할 때 use bit == 1 이면 0으로 변경 후 다음 프레임을 탐색하고, use bit == 0 이면 그 프레임의 페이지를 교체하고 포인터는 다음 프레임을 가리킨다.
- 포인터가 한 바퀴 도는 동안에 페이지들이 계속 실행되면서 use bit == 1 을 유지하면 버릴 페이지를 찾는 데에 시간이 오래 걸릴 수 있으므로 시간적 오버헤드는 해결되지 않는다.

💡 LRU에 가까운 성능을 보이는 이유

프로세서의 속도가 상당히 빠르기 때문에 페이지가 메인 메모리에 적재되고 나서 빠른 시간 안에 실행되므로 use bit가 1인 상태로 유지되는 경향이 있다. page fault 때 마다 포인터가 순회하면서 한 바퀴를 다 돌았을 때 페이지가 한 번도 실행되지 않았다면 use bit == 0 일 것이다. 이때 그 페이지를 버리게 되는데, 즉 오랫 동안 실행되지 않은 페이지를 버리는 것이므로 LRU와 유사하다.

Resident Set Size

• Resident Set: 프로세스를 구성하는 페이지 중 메인 메모리에 적재된 페이지들의 집합
• Fixed-allocation: 모든 프로세스가 고정 개수의 프레임을 할당 받는 방법
  • 시간적 오버헤드가 거의 없어서 LRU를 사용하기 쉽다.
• Variable-allocation: 프로세스마다 서로 다른 개수의 프레임을 할당 받는 방법
  • 프로세스 working set이 메인 메모리에 다 들어갈 수 있도록 프레임을 할당해준다.

어떤 allocation 방법을 사용하는 지에 따라 적합한 교체 알고리즘이 달라진다.

Fixed Allocation & Local Scope

• Local Scope: 프로세스 자신에게 할당된 프레임 중에서 페이지를 버리는 것
• 장점
  • 페이지 교체가 빠르게 발생한다.
  • LRU가 가장 효율적인 방법
• 단점
  • 할당된 프레임 수가 많으면, 공간적 낭비가 있을 수 있다.
  • 할당된 프레임 수가 적으면, page fault가 많이 발생할 수 있다.

Fixed Allocation & Global Scope ❌

다른 프로세스의 페이지를 버리고 내 페이지를 가져온다면 Fixed Allocation 이 깨진다.
불가능한 방법

Variable Allocation & Global Scope

• Global Scope: 메인 메모리의 전체 프레임 중에서 페이지를 버리는 것
• Clock policy
• working set에 정상적 가동이 가능하다.
  • 한 프로세스의 working set이 증가할 때, 다른 플세스의 working set은 감소할 수 있다. 전자의 프로세스가 페이지 요청을 하면 후자의 프로세스 페이지 중 하나를 버려 교체하면 된다.
  • 모든 프로세스의 working set이 증가하고 있다면 page fault가 많이 발생할 수 있다.

Variable Allocation & Local Scope

• 프로세스가 실행을 시작하면 특정 기준에 따라서 프레임을 할당한다.
• 주기적으로 page fault가 얼마나 발생하는지 조사한다.
• page fault가 많이 발생한다면, 할당된 프레임 수가 working set보다 작다는 것이므로 더 많은 프레임을 할당한다. (resident set 증가)
• page fault가 거의 발생하지 않는다면, 할당된 프레임 수가 working set보다 크거나 같다는 것이므로 할당된 프레임 수를 줄인다. (resident set 감소)

Variable Allocation에서 Local과 Global 사이의 page fault 수는 비교 불가능하다.

UNIX Memory Management

• User Process: 페이지 기반의 Virtual memory system
  • TLB를 사용한다.
• Kernel: 변형된 Dynamic Partitioning을 사용하는 변형된 형태의 Buddy system

2-Handed Clock Page Replacement Algorithm

• Variable Allocation & Global Scope
• Referent bit 사용
• Fronthand: reference bit 값을 0으로 설정한다.
  • 일정 시간동안 사용된 페이지인지 아닌지를 구분한다.
• Backhand: reference bit 값이 0인 페이지들을 Paged-Out-List(버릴 페이지 목록)에 저장한다.
  • 리스트가 가득 차면 페이지들을 한 번에 버린다. 이때 페이지의 M 비트가 1이면 하드 디스크에 write 작업이 필요하다.
  • free frame을 확보한다.
  • 리스트 안에 있는 페이지가 버려지기 전에 또 필요하면 다시 할당하면 된다.
• Fronthand, Backhand 둘 다 page fault가 발생하지 않아도 평상 시에 계속 돌아간다.
  • 주기적으로 free frame을 확보함으로써 추가적인 페이지가 적재될 때 버릴 페이지를 선택하는 작업을 하지 않고 바로 적재될 수 있도록 한다.
• Fronthand와 Backhand의 간격
  • 좁을 때, Paged-Out-List 길어진다.
  • 넓을 때, Paged-Out-List 짧아진다.

Windows Memory Management

• 페이지 기반의 Virtual memory system
• Variable Allocation & Local Scope
• working set 기반의 메모리 관리
  • page fault가 많이 발생하면 resident set을 늘린다.
  • page fault가 적게 발생하면 resident set을 줄인다.
• LRU 기법 사용