Chapter 8-1. Virtual Memory

Types of Memory

Real Memory

Main Memory

Physical 한 메모리 자체를 말한다.

Virtual Memory

Main Memory + Memory on disk

전체 프로그램을 모두 메모리에 넣지 않고, 프로그램의 일부만 메모리에 넣고 실행을 시키는 방식.

전체 프로그램 중 일부는 진짜 Physical 한 메모리에 들어 있고 나머지는 hard disk에 들어있는채로 시작한다.

---

Execution of a Program

Resident set

전체 프로그램 중 메모리에 올라와 있는 부분(page, segment)

Interrupt

프로세스가 주소에 접근하려는데, 메모리에 올라와 있지 않은 주소가 필요한 경우
OS 가 Interrupt 를 건다.
→ 현재 프로세스 Blocked Queue 로 이동
→ 프로세스의 I/O 작업 (I/O Request)
→ 끝
→ I/O Interrupt
→ 프로세스가 Ready Queue 로 이동

---

Thrashing & Locality

메모리는 무제한이 아니기 때문에 하나의 프로세스당 몇 페이지만 메모리에 올라올 수 있다. 따라서 다른 페이지를 메모리로 가지고 오기 위해서는 메모리에 원래 있던 페이지를 하드디스크로 버려야 한다.

Thrashing

페이지를 잘못 버려서 프로세스를 실행하지 못하고 페이지를 버리고 가져오는데 시간을 다 쓰는 것

Reference Locality

별 일 없으면, 프로그램은 순차적으로 실행되는데, Reference Locality 덕분에 Page는 한 번 실행되면 웬만하면 Page 변경을 하지 않는다.

---

Paging

프로그램을 실행하기 위해서는 다음 두가지가 잘 되어야한다.

• Relocation
• Protection

Relocation 에 필요한 요소들

Relocation 은 Physical Address 를 얻는 과정이다.

1. Page Table 이 필요 → Frame# 필요 → offset 과 연결 ⇒ physical address
2. Presence bit : 메모리에 있나 없나 확인하는 비트
   • 0 → 해당 페이지가 메모리에 없음
     ↳ Interrupt → Block → harddisk에서 page 가져옴 → page table update → Ready → Running
   • 1 → 해당 페이지가 메모리에 있음
     ⇒ page frame# 를 찾아서 offset과 연결하여 physical Adress 를 완성해 relocation 가능
3. Modify bit : 해당 페이지가 메모리에 올라온 이후, update 된적이 있는지 확인하는 비트
   • 0 → code 변경 X
   • 1 → code 변경 O

code는 변경되지 않고, data는 변경되는 경우가 많다.

P1 프로세스의 페이지 두개를 메모리에 올려 놓고 실행을 하고 있는 상황이다.

두 페이지 중 한 페이지는 프로그램 코드이고, 한 페이지는 데이터가 포함되어 있는 페이지이다.

코드가 포함되어 있는 페이지는 수정된 것이 없지만, 데이터가 포함된 페이지는 수정된 상태이다.

P1 의 페이지는 메모리에 최대 2개까지만 올라갈 수 있기 때문에 새로운 페이지를 가져오기 위해서는 기존의 페이지를 버려야 한다.

• 이때, modify bit = 1인 경우인, data가 포함된 페이지를 그냥 버리면, 데이터가 날라가므로 hard disk에 적어주어야 한다.
• 그러나 modify bit = 0인 경우에는 새로운 페이지를 읽어올 때, hard disk 를 쓸 필요 없이 읽기만 하면 된다.

Each process has its own page table

• Each page table entry contains the frame number of
  the corresponding page in main memory
• A bit is needed to indicate whether the page is in main memory or not
• Another modify bit is needed to indicate if the page has been altered since it was last loaded into main memory

각각의 프로세스마다 Page Table 을 가지고 있다.

• 각각의 Page Table entry 는 main memory안의 해당하는 페이지의 frame# 가 있다.

---

Page Table Entries

Virutal Address

Logical Address 인데, Virutal Memory 에서 사용하는 Logical Address 이다.

Paging System 이므로, Page#와 Offset 으로 구성이 되어 있다.

Page Table Entry

한 페이지마다 해당하는 페이지의 Presence bit, Modify bit, Other Control Bit, Frame# 가 구성요소로 존재한다.

구조체 변수라고 생각하면, 4개의 멤버를 가지는 구조체 변수이다.

페이지마다 하나씩 존재하므로 구조체 배열로 관리 된다.

---

Address Translation in a Paging System

Register

• Register 는 실행하고 있는 프로세스의 페이지 테이블의 시작 주소값이 들어 있다.
• Register 는 1개만 있으면 된다.
  → CPU 는 한번에 하나의 프로세스만 실행하기 때문이다.

Q. Page # 와 Page Table 의 시작 주소를 더하는 이유?

X[i] ⇒ 여기서 X 는 구조체 배열의 이름이며, X[i] 의 주소는 X + i 이다.

즉, Page Table 의 시작 주소는 배열의 시작 주소이고 Page# 는 인덱스이므로 더하는 것이다.

하지만, 이러한 경우는 굉장히 운이 좋은 것이다.
페이지 테이블은 프로그램 크기가 커지면, 크기가 어마무시하게 커져, 한 페이지 안에 안 들어갈 수도 있다. 위와 같은 상황은 페이지 테이블이 한 페이지보다 작은 경우이기에 가능한 경우이다.

만약 페이지 테이블이 한 페이지가 넘어가게 되면, 페이지 테이블 중, 누구는 메모리에 있고 누구는 메모리에 있지 못하게 되는데, 페이지 테이블의 각 페이지가 메모리에 있나 없나, 메모리에 있다면, 어떤 프레임에 있나 알 수 있는 또다른 페이지 테이블이 필요하게 된다.

---

Two-Level Hierarchical Page Table

Second Level Page Table

• 엔트리 하나하나마다 페이지가 어디에 있는지를 나타낸다.
• Page Table 의 크기가 4Mbyte 인데, 이는 한 페이지를 넘어가게 된다.
  즉, 이 Page Table 의 Page 가 메모리 프레임 어느 곳에 위치하는지를 나타내는 root page table이 필요하게 된다.

Root Page Table

• Second Level Page Table이 메모리 어디 프레임에 들어가 있는지를 나타낸다.

프로그램의 최대 크기
(= 전체주소가 사용하는 bit, 기본 가정)

주어지는 값이다.

이 프로그램의 최대 크기는 4Gbyte(2^32 bytes) 이다.

• Giga = 2^30 Bytes

페이지의 크기
(= Offset bit, 기본 가정)

주어지는 값이다.

페이지의 크기는 2^12 byte 이다.

한 프로그램이 포함하는 페이지의 최대 개수

프로그램의 최대 크기 / 페이지의 크기 = 페이지의 최대 개수

한 프로그램이 포함하는 페이지의 최대 개수는 2^20 개 있을 수 있다.

페이지 테이블의 한 entry 의 크기

주어지는 값이다.

entry 는 원소의 개수를 말한다.

페이지가 2^20개 존재하므로, entry는 최대 2^20개 존재할 수 있다.

전체 페이지 테이블의 최대 크기 (2단계 페이지 테이블)

entry의 크기 X 최대 Page 수 = Page Table 의 최대 크기

• Mega = 2^20

전체 페이지 테이블(2단계 페이지 테이블)이 포함하는 페이지의 최대 개수

페이지의 테이블중 일부는 메모리, 일부는 하드디스크에 위치할 수 있다.

Page Table 의 최대 크기 / Page의 크기 = 전체 페이지 테이블이 포함하는 페이지의 최대 개수

• K = 2^10

즉, 1024개의 페이지가 페이지 테이블에 존재한다.
→ 어디에?
→ 하나하나 Entry 가 필요하다.

Root page table(페이지 테이블의 각 페이지가 어디에 있는지를 알려주는 페이지 테이블)의 크기

Entry 의 크기 X 전체 페이지 테이블이 포함하는 페이지의 최대 개수 = Root Page Table 의 크기

2^12 는 딱 한페이지 안에 들어가는 크기이다.

프로그램 처음 시작
→ root page table 만 메모리에 존재
↳ 2nd level page table 의 page 는 root page table 을 보고 실제 올릴 page 가져오기
→ 내가 원하는 데이터가 실제로 어디에 있는지 찾으러 간다.

Q. 각 단계의 Page Table 크기를 계산할 줄 알아야 한다.

이 예제에선 전체 프로그램의 크기 = 2^32 & 페이지의 크기 = 2^12
→ 만약, 페이지의 크기를 2^10 으로 바꾸면 어떻게 될까?

• 페이지 크기 ↓
• 페이지 개수 ↑
• 페이지 테이블 크기 ↑
• root 테이블 크기 ↑

지금은 root table 이 딱 1 페이지에 들어가서 root 페이지 테이블 먼저 메모리에 올려놓고 프로세스를 실행할 수 있지만,
페이지의 크기가 작아지게 되면, root page table 자체가 페이지 하나에 있을 수 없게 된다.
→ root page table 의 페이지가 어디있는지 알 수 있는 또 다른 페이지 테이블이 필요하게 된다. ⇒ 3단계 페이지 테이블

⇒ 2^10 으로 페이지 크기를 정했을 때, root page table, 2단계 table, 3단계 table 의 크기를 계산하라!

각 단계의 Page Table 크기를 계산할 줄 알아야 한다.

---

Address Translation for Hierarchical page table

내가 원하는 데이터나 instruction 은 파란색 위치에 존재한다.

이 위치에 있는 데이터나 instruction 을 읽으려면, 나는 여기 주소가 필요하다.

이 주소는 offset + Frame# 로 결정된다.

⇒ 나는 이 프레임의 번호가 필요하다. offset은 virtual address 에서 바로 온다.

프레임 번호를 알려면, 2단계 페이지 테이블을 확인해야한다.
2단계 페이지 테이블 중 하나의 엔트리만 나와있는 것이다.

2단계 페이지 테이블은 너무 크기 때문에 각각의 페이지테이블이 어디에 들어있는지 root page table 안에 들어 있다.

root page table 안에는 내가 원하는 instruction 이나 data 를 포함하고 있는 페이지 프레임 정보가 들어 있는 페이지 테이블이 어떤 프레임에 들어있는지 하는 정보가 들어있다.

Register 안에는 root page table 시작 주소가 들어있다.
Virtual Address 최대 크기는 32bit
⇒ 프로그램의 최대 크기 = 4Gbytes (2^32 bytes, 32bit)

• 12bit = offset
• 20 bit = page#
  • 10 bit = root page table 에서 내가 원하는 entry를 찾는데 사용한다.
  • 10 bit = 내가 찾는 page table의 시작 주소

Q. 앞에 10bit, 10bit 로 Virtual Address 를 나누었는데 왜 나누었을까?

페이지 크기를 2^10 으로 줄임 → offset 크기 = 2^20
⇒ 3단계 페이지 테이블 필요
⇒ Virtual Memory → 32 → 22(32-10) | 10

22(32-10)10(offset)

큰 페이지 테이블은 중간 페이지가 존재한다.
한 페이지의 Index 값의 최대 크기 → 2^10 (배열의 크기)
= 한페이지의 크기/엔트리의 크기 → 2^12/2^2 = 2^10 (10bit 필요)

⇒ 2^10 개의 원소를 포함하는 배열

한 페이지에 들어있는 엔트리의 개수 만큼 인덱스가 필요하다.

• 페이지 테이블 장점?
  ↳ 정해져있다. (녹음듣기)
• 페이지 테이블 단점?
  ↳ 앞뒤로 굉장히 많은 페이지 테이블이 존재한다.

몇 단계로 만들지는 시스템 개발자가 처음에 결정하는 것이다.

• root → 2단계 → 데이터
• root → 2단계 → 3단계 → 데이터

장점

메모리를 읽어야 하는 횟수가 정해져 있다. (단계에 따라 2번, 3번, ...)

단점

페이지 테이블의 크기가 커질수록, 원하는 페이지가 메모리에 없을 확률이 높아진다.
⇒ 메모리 뿐만 아니라, 하드디스크에 가서 페이지 테이블 정보를 읽어와야 한다.
→ 메모리에 비해 하드디스크는 접근 시간이 길다.

---

Inverted Page Table

Page Table의 대부분의 엔트리들은 Presence bit가 0이다.
↔ 하지만 나는 1인것만 있으면 된다.

⇒ Presence bit 가 1인것만 뽑아서 내가 Page Table을 만들자!

각 프로세스마다 두, 세개의 엔트리만 존재하게 될 것 이다.

One page table entry for each page frame

• 각 페이지가 들어 있는 페이지 프레임 순으로 저장 해야 한다. → 실제 Physical memory 에 어느 Process에

내 프로그램의 몇번째 페이지가 어디에 있나를 저장하는 것이 아니라, 거꾸로 실제 Physical Memory에 0번 프레임에 어느 프로세스의 어느 페이지가 들어있나를 저장하는 것이다.

따라서 이 페이지 테이블은 Page table의 k번째 entry에는 k번째 page frame에 저장된 프로세스와 page에 대한 정보가 저장된다.

페이지 테이블 요소가 포함하는 것

Each entry in the page table includes:

1. Page number

2. Process identifier

the process that owns this page.

어떤 프로세스인지 알아야 한다. 여러 프로세스가 존재할 수 있기 때문

• 1번 프로세스의 0번 페이지
• 100번 프로세스의 0번 페이지
• ...

3. Control bits

includes flags, such as valid, referenced, etc

4. Chain pointer

the index value of the next entry in the chain.

없어도 되긴 하는데, 없으면 내가 원하는 페이지를 찾는데 굉장히 오래 걸린다.

내가 원하는 페이지가 어느 프레임에 있는지 최대한 빠르게 찾기 위해서 사용된다.

Hashing Function

• Page number portion of a virtual address is mapped into a hash value
• Hash value points to inverted page table
• Fixed proportion of real memory is required for the tables regardless of the number of processes

Inverted Page Table Structure

Hash Function Input

페이지 번호 필요

Hash Function Output

10으로 나눈 나머지 X

10으로 나눈 나머지가 같은 애들끼리 링크로 연결되어 있을 때, 각 링크의 시작점 O
⇒ 나머지가 3인 링크의 시작점이 몇번 Frame 에 있는지 알려준다.

ex) 나머지가 3인 링크의 시작점, 나머지가 1인 링크의 시작점, 나머지가 5인 링크의 시작점, ...

0번 엔트리에는 실제 physical memory frame 0번에 어떤 프로세스의 어떤 페이지가 들어 있는지 정보가 들어 있다.

for문을 돌리며, x[i].page#와 x[i].ID 가 인풋값과 일치하는 프로세스를 찾는다.

Chain

Chain 이 없으면 2^m 번 메모리(메모리 전체)를 읽어야 한다.
메모리 3번 읽기 → 내 데이터 읽기

장점

Page Table 의 크기가 작다.

two-hierarchy
→ Page Table 의 크기 = 4Gbyte
→ 2단계 Page Table의 크기 = 4Mbyte
↑ 이게 프로세스 하나당 존재

Inverted Page Table
한 Entry 크기, Entry 개수 ⇒ Inverted Page Table 계산 가능 ⇒ 메모리에 있을 확률 ↑

단점

최악의 경우, 메모리 안에 들어 있는 페이지의 나머지가 모두 3인 경우, 결국 전체를 훑어야하기 때문에 시간 소요가 커지게 된다.

위의 그림은 16개의 페이지 프레임을 가지는 메모리이다.

각각의 Inverted Page Table 에는 페이지#, 프로세스#, Chain Pointer 가 존재한다.

Chain Pointer 에는 다음 Chain Pointer가 존재하는 다음번 엔트리의 위치가 들어있다.