운영체제(이론) - 핀토스 - Virtual memory - 중요 키워드(Page Table, Page Fault, Page Replacement Policy, 스왑 디스크)

컴퓨터 시스템의 메모리 관리 기술 중 하나로, 물리적 메모리(RAM)의 한계를 극복하고 프로그램이 더 많은 메모리를 사용할 수 있는 방법

간략 주요 개념

페이지 - 가상 메모리는 일정한 크기의 블록으로 나뉘며, 이 블록을 페이지라고 한다. 일반적으로 페이지는 4KB.

페이지 테이블 - 가상 메모리 주소 and 물리 메모리 주소를 매핑하는 테이블. 각 프로세스마다 별도의 페이지 테이블 존재

페이징 - 가상 메모리를 페이지 단위로 물리 메모리를 적재. 필요한 페이지만 물리 메모리에 로드 and 나머지는 디스크에 저장.

스왑 - 물리 메모리가 부족할 때 사용하지 않는 페이지를 디스크에 옮기고, 필요한 페이지를 디스크에서 물리 메모리로 가져오기

ex)

1. 프로세스가 실행되는 상황

프로그램 A가 실행. 이 프로그램이 16KB의 메모리를 필요로 한다고 가정. but 시스템에는 실제로 8KB의 물리 메모리만 남아 있는 상황

2. 가상 메모리 공간 설정

운영체제는 프로그램 A에 16KB의 가상 메모리 공간 할당. 이 가상 메모리 공간은 페이지로 나뉘며, 페이지 크기가 4KB라고 가정.

• 페이지 1: 0 - 4KB
• 페이지 2: 4KB - 8KB
• 페이지 3: 8KB - 12KB
• 페이지 4: 12KB - 16KB

3. 페이지 테이블 생성

각 페이지가 물리 메모리의 어느 위치에 저장되어 있는지 매핑하는 페이지 테이블이 생성. 초기에 페이지 테이블 예시

가상 페이지	물리 페이지
페이지 1	물리 페이지 1 (0 - 4KB)
페이지 2	물리 페이지 2 (4KB - 8KB)
페이지 3	디스크에 있음
페이지 4	디스크에 있음

4. 프로그램 실행 중 페이지 폴트(Page Fault)

프로그램 A가 페이지 3의 데이터를 필요로 한다면, 현제 페이지 3은 물리 메모리에 없기 때문에 페이지 폴트 발생.

운영체제는 물리 메모리의 사용하지 않는 페이지를 디스크로 옮기고, 페이지 3을 물리 메모리에 로드.

페이지 테이블은 업데이트되어 페이지 3의 위치 반영

가상 페이지	물리 페이지
페이지 1	물리 페이지 1 (0 - 4KB)
페이지 2	물리 페이지 2 (4KB - 8KB)
페이지 3	물리 페이지 3 (8KB - 12KB)
페이지 4	디스크에 있음

페이지 and 프레임

메모리 관리의 기본 단위.

페이지

가상 메모리의 일정한 크기의 블록

• 프로그램의 가상 주소 공간은 여러 개의 페이지로 나뉜다.
• 크기는 일반적으로 4KB, 8KB, 16KB등으로 설정.
• 각 페이지는 페이지 번호 and 페이지 오프셋으로 구분.

프레임

물리 메모리의 일정한 크기의 블록

• 물리 주소 공간은 여러 개의 프레임으로 나뉜다.
• 페이지의 크기와 동일 하다.
• 각 프레임(프레임 번호로 구분)

페이지와 프레임의 매핑

가상 메모리 시스템에서 페이지 and 프레임은 페이지 테이블을 통해 서로 매핑. 가상 페이지 번호를 물리 프레임 번호로 변환.

페이지 테이블

가상 주소 > 물리 주소로 바꿔주는 역할을 하는 자료구조

• 구성

페이지 테이블은 여러 개의 엔트리로 구성되며, 각 엔트리는 가상 페이지 번호 and 해당 페이지가 매핑된 물리 프레임 번호를 포함.

• 매핑 정보

가상 페이지 번호(VPN)

물리 프레임 번호(PFN)

유효 비트 (Valid Bit)

추가 정보 - 접근 권한, 수정 여부, 참조 비트

페이지 and 프레임의 예시

ex)1 - 가상 주소 변환(4KB라고 가정)

1. 가상 주소 분할

• 가상 주소 0x1234는 페이지 번호 and 페이지 오프셋으로 분할
• 페이지 번호(VPN) = 0x1(상위 비트)
• 페이지 오프셋(offset) = 0x234(하위비트)

2. - 페이지 테이블 참조

• 페이지 번호 0x1에 해당하는 페이지 테이블 엔트리를 참조
• 페이지 테이블 엔트리 : VPN 0x1 → PFN 0x3

3. 물리 주소 생성

• 물리 프레임 번호(PFN) 0x3과 페이지 오프셋 0x234를 결합하여 물리 주소 생성.
• 물리 주소 = 0x3000 + 0x234 = 0x3234

ex)2 - 페이지 폴트 처리

• 페이지 폴트 발생:
  • 프로그램이 가상 주소 0x4567에 접근.
  • 페이지 번호(VPN) = 0x4, 페이지 오프셋(offset) = 0x567
  • 페이지 테이블을 참조한 결과, 페이지 번호 0x4가 유효x > 확인o 페이지 폴트 발생
• 페이지 로드:
  • 운영체제는 디스크에서 페이지 번호 0x4에 해당하는 데이터를 읽어와 물리 메모리의 빈 프레임에 로드합니다.
  • 예를 들어, 물리 프레임 번호 0x7에 로드합니다.
• 페이지 테이블 업데이트:
  • 페이지 테이블 엔트리를 업데이트 > 페이지 번호 0x4가 물리 프레임 번호 0x7에 매핑 되었음 기록
  • 페이지 테이블 엔트리: VPN 0x4 -> PFN 0x7
• 프로세스 재개:
  • 페이지 폴트 처리가 완료되면, 프로그램은 다시 가상 주소 0x4567에 접근을 시도하고, 이번에는 성공적으로 접근할 수 있습니다.
  • 물리 주소 = 0x7000 + 0x567 = 0x7567

페이지와 프레임의 관리

1. 페이징

• 가상 메모리를 일정 크기의 페이지로 나누고, 물리 메모리를 동일한 크기의 프레임으로 나누어 관리
• 필요할 때만 페이지를 물리 메모리에 로드하여 메모리 사용 최적화

2. 페이지 교체 알고리즘

• FIFO, LRU, LFU

3. 스왑 공간

• 물리 메모리가 부족할 때 사용하지 않는 페이지를 디스크의 스왑 공간으로 옮기고, 필요한 페이지를 스왑 공간에서 물리 메모리로 가져온다.

가상 주소 변환 과정

1. 가상 주소 분할

Virtual Adderss → VPN + Offset

ex)

가상 주소 0x1234가 주어졌을 때, 페이지 크기가 4KB라고 가정.

• 상위 비트(페이지 번호) : 0x1 (가상 페이지 번호, VPN)
• 하위 비트(페이지 오프셋) : 0x234(오프셋)

+-----------------------+
|   Virtual Address     |
|       0x1234          |
+-----------------------+
| VPN 0x1 | Offset 0x234|
+-----------------------+

2. 페이지 테이블 참조

VPN > PFN

페이지 테이블은 가상 페이지 번호를 물리 프레임 번호로 매핑 하는데 사용. 여기서 각 가상 페이지 번호가 물리 메모리의 어느 프레임에 해당하는지 저장.

+-----------------------+
|    Page Table         |
+-----------------------+
| VPN 0x0 -> PFN 0x5    |
| VPN 0x1 -> PFN 0x3    |
| VPN 0x2 -> PFN 0x7    |
| VPN 0x3 -> PFN 0x2    |
+-----------------------+

3. 물리 주소 생성

PFN + Offset → Physical Address

물리 프레임 번호(PFN) - 0x3 + 페이지 오프셋 - 0x234

= 물리 주소 0x3234

+-----------------------+
| Physical Address      |
|    0x3000 + 0x234     |
|      = 0x3234         |
+-----------------------+

가상 주소 공간의 페이지가 물리 주소 공간의 프레임에 매핑(페이지 테이블을 통해)

+----------------------+          +----------------------+
|   Virtual Address    |          |    Physical Address  |
|       Space          |          |        Space         |
+----------------------+          +----------------------+
|  Page 0  |  Page 1   |  ----->  | Frame 1 | Frame 4    |
|  (0x0)   |  (0x1)    |          |  (0x3)  |  (0x1)     |
+----------------------+          +----------------------+
|  Page 2  |  Page 3   |  ----->  | Frame 3 | Frame 6    |
|  (0x2)   |  (0x3)    |          |  (0x2)  |  (0x7)     |
+----------------------+          +----------------------+
|  Page 4  |  Page 5   |  ----->  | Frame 5 | Frame 0    |
|  (0x4)   |  (0x5)    |          |  (0x5)  |  (0x4)     |
+----------------------+          +----------------------+
|  Page 6  |  Page 7   |  ----->  | Frame 7 | Frame 2    |
|  (0x6)   |  (0x7)    |          |  (0x6)  |  (0x0)     |
+----------------------+          +----------------------+

• 가상 주소 공간은 프로세스마다 독립적으로 할당되며 페이지로 나뉜다.
• 물리 주소 공간은 시스템 전체에서 공유되며 프레임으로 나눈다.
• 페이지 테이블을 통해 가상 페이지 번호(VPN)는 물리 프레임 번호(PFN)로 매핑.
• 매핑 과정을 통해 가상 주소 > 물리 주소로 변환.

페이지 폴트 처리 과정

1. 페이지 폴트 발생

프로세스가 가상 주소 0x4567에 접근하려고 함. 페이지 번호, 페이지 오프셋으로 나뉜다.

• 가상 주소(0x4567), 페이지 번호(0x4), 페이지 오프셋(ox567)

+-----------------------+
|   Virtual Address     |
|       0x4567          |
+-----------------------+
| VPN 0x4 | Offset 0x567|
+-----------------------+
|  Page Fault!          |
+-----------------------+

2. 페이지 로드

Disk > Memory

디스크에는 여러 페이지 저장. ex) 0, 1, 4 등이 디스크에 저장.

물리 메모리에는 여러 프레임 저장. ex) 3, 4, 7. 여기서는 Frame 4가 빈 프레임이라고 가정.

+-------------------------------+
|    Disk                       |
|  +--------+--------+--------+ |
|  | Page 0 | Page 1 | Page 4 | |  <- Page 4가 디스크에 있음
|  +--------+--------+--------+ |
|                  ^            |
|                  |            |
+-------------------------------+
                  |
                  v
+-------------------------------+
|    Physical Memory            |
|  +--------+--------+--------+ |
|  | Frame 3 | Frame 4 | Frame 7| |  <- Frame 4에 page 4가 로드됨
|  +--------+--------+--------+ |
+-------------------------------+

• 디스크에서 페이지 읽기 - 운영체제는 디스크에서 필요한 페이지(이 경우 page 4)를 읽어온다.
• 물리 메모리에 페이지 저장 - 읽어온 page 4를 물리 메모리의 빈 프레임(이 경우 Frame 4)에 저장.

3. 페이지 테이블 업데이트

• 디스크에서 페이지 4를 물리 메모리로 로드한 후, 페이지 테이블을 업데이트하여 가상 페이지 번호 0x4가 물리 프레임 번호 0x4에 매핑되었음을 기록

+-----------------------+
|    Page Table         |
+-----------------------+
| VPN 0x0 -> PFN 0x5    |
| VPN 0x1 -> PFN 0x3    |
| VPN 0x2 -> PFN 0x7    |
| VPN 0x3 -> PFN 0x2    |
| VPN 0x4 -> PFN 0x4    |  <-- Updated
+-----------------------+

4. 프로세스 재개

페이지 테이블이 업데이트된 후, 프로세스는 다시 가상 주소 0x4567에 접근을 시도한다. 이 때, 가상 주소 0x4567은 물리 주소 0x4567로 변환

최종 물리 주소

+-----------------------+
| Physical Address      |
| 0x4000 + 0x567 = 0x4567|
+-----------------------+

페이지 교체 알고리즘

FIFO 페이지 교체 알고리즘

가장 먼저 들어온 페이지를 가장 먼저 내보내는 방식

1. 페이지 로드 순서 유지

• 메모리에 로드된 페이지는 큐(FIFO) 구조로 관리

2. 페이지 폴트 발생 시 교체

• 새로운 페이지 로드해야 할 때 물리 메모리에 빈 프레임이 없으면 > 큐의 맨 앞에 있는 페이지 제거 and 새로운 페이지를 해당 위치 로드

요약된 큐 and 메모리 상태 변화

단계	페이지 참조	큐 상태	메모리 상태	페이지 폴트 발생
1	A	[A]	[A, -, -]	예
2	B	[A, B]	[A, B, -]	예
3	C	[A, B, C]	[A, B, C]	예
4	D	[B, C, D]	[D, B, C]	예
5	E	[C, D, E]	[D, E, C]	예
6	F	[D, E, F]	[D, E, F]	예
7	G	[E, F, G]	[G, E, F]	예

LIFO 페이지 교체 알고리즘

가장 먼저 들어온 페이지를 가장 먼저 내보내는 방식

1. 페이지 로드 순서 유지

메모리에 로드된 페이지는 스택(LIFO)구조로 관리

2. 페이지 폴트 발생 시 교체

새로운 페이지 로드해야 할 때 물리 메모리에 빈 프레임이 없으면 > 스택의 맨 위에 있는 페이지 제거 and 새로운 페이지를 해당 위치 로드

요약된 스택과 메모리 상태 변화

단계	페이지 참조	스택 상태	메모리 상태	페이지 폴트 발생
1	A	[A]	[A, -, -]	예
2	B	[A, B]	[A, B, -]	예
3	C	[A, B, C]	[A, B, C]	예
4	D	[A, B, D]	[A, B, D]	예
5	E	[A, B, E]	[A, B, E]	예
6	F	[A, B, F]	[A, B, F]	예
7	G	[A, B, G]	[A, B, G]	예

스왑 디스크

스와핑

프로세스는 실행을 시작하기 전에 주 메모리에 있어야 한다. 따라서 실행 준비가 완료된 프로세스가 주 메모리로 이동한다. 이제 실행 중인 프로세스가 차단. 메모리 관리자는 차단된 프로세스를 일시적으로 디스크로 교체한다.

이상적으로 메모리 관리자가 프로세스를 매우 빠르게 교체하여 주 메모리에 항상 실행 준비가 된 프로세스가 있다.

1. 페이지 폴트 발생

프로세스가 가상 주소 0x4567에 접근 시도 . 해당 페이지(가상 페이지 번호 0x4)가 물리 메모리에 존재x. 페이지 폴트 발생

+-----------------------+
|   Virtual Address     |
|       0x4567          |
+-----------------------+
| VPN 0x4 | Offset 0x567|
+-----------------------+
|  Page Fault!          |
+-----------------------+

2. 페이지 아웃(메모리 > 스왑 디스크)

메모리에 있는 페이지 중 덜 자주 사용되는 페이지를 스왑 디스크로 옮긴다. ex) Frame 3의 내용을 스왑 디스크로 스왑 아웃.

메모리 상태:
+-------------------------------+
|    Physical Memory            |
|  +--------+--------+--------+ |
|  | Frame 1 | Frame 2 | Frame 3| <-- Frame 3를 스왑 아웃
|  +--------+--------+--------+ |
+-------------------------------+

스왑 디스크 상태:
+-------------------------------+
|    Swap Disk                  |
|  +--------+--------+--------+ |
|  | Page X | Page Y | Page Z | <-- Frame 3의 내용을 스왑 디스크에 저장
|  +--------+--------+--------+ |
+-------------------------------+

3. 페이지 인(디스크 > 메모리)

디스크에서 필요한 페이지(page4)를 읽어와 빈 프레임 3에 로드

디스크 상태:
+-------------------------------+
|    Disk                       |
|  +--------+--------+--------+ |
|  | Page 0 | Page 1 | Page 4 | <-- Page 4를 읽어옴
|  +--------+--------+--------+ |
+-------------------------------+

메모리 상태:
+-------------------------------+
|    Physical Memory            |
|  +--------+--------+--------+ |
|  | Frame 1 | Frame 2 | Frame 3| <-- Frame 3에 Page 4 로드
|  +--------+--------+--------+ |
+-------------------------------+

4. 페이지 테이블 업데이트

페이지 테이블 상태:
+-----------------------+
|    Page Table         |
+-----------------------+
| VPN 0x0 -> PFN 0x1    |
| VPN 0x1 -> PFN 0x2    |
| VPN 0x2 -> PFN 0x3    |
| VPN 0x3 -> PFN 0x4    |
| VPN 0x4 -> PFN 0x3    |  <-- Updated
+-----------------------+

5. 프로세스 재개

다시 가상 주소 0x4567에 접근 시도. 이 때, 가상 주소 0x4567은 물리 주소 0x3567로 변환.

가상 주소:
+-----------------------+
| Virtual Address 0x4567|
+-----------------------+
| VPN 0x4 | Offset 0x567|
+-----------------------+

물리 주소:
+-----------------------+
| Physical Address      |
| 0x3000 + 0x567 = 0x3567|
+-----------------------+