[운영체제] 3-5. (2) 가상 메모리 (Virtual Memory)

페이지 테이블 (Page Table)

 

 앞서 프로세스를 구성하는 페이지는 물리 메모리 내에 불연속적으로 배치될 수 있다고 설명했다. 이 경우, CPU는 다음으로 실행할 페이지가 어느 프레임에 위치하는지 찾기가 어렵다. 이러한 문제를 해결하기 위해 페이지 테이블(Page Table)이라는 자료구조를 사용한다.

 

💡페이지 테이블(Page Table)

 

페이지 테이블(Page Table)

• 프로세스의 각 페이지 번호와 실제 물리 메모리의 프레임 번호를 매핑한 자료구조
• CPU는 페이지 테이블을 참고하여 논리 주소를 물리 주소로 변환하고 메모리에 접근한다.

 

💡페이지 테이블 엔트리(PTE, Page Table Entry)

 

 페이지 테이블은 운영체제마다 차이가 있지만 일반적으로 페이지 번호, 프레임 번호 외에 유효 비트, 보호 비트, 참조 비트, 수정 비트와 같은 테이블 엔트리 정보를 저장한다.

페이지 테이블 엔트리(PTE, Page Table Entry)

• 페이지 테이블 엔트리(Page Table Entry, PTE)의 구성 요소

페이지 번호	프레임 번호	유효 비트(valid bit)	보호 비트(rwx)			참조 비트(reference bit)	수정 비트(dirty bit)
페이지 번호	프레임 번호	0/1	r	w	x	0/1	0/1

 

➡️ 유효 비트(Valid bit)

• 해당 페이지가 메모리에 적재되어 접근 가능한지를 나타내는 정보
• 유효 비트가 1이면 메모리에 적재되어 있고, 0이면 보조기억장치에 있다는 의미
• CPU는 보조기억장치에 저장된 페이지에 바로 접근 불가하므로 보조기억장치에 저장된 페이지에 접근하려면, 보조기억장치 속 페이지를 메모리로 적재한 뒤 접근해야한다. 만일 CPU가 메모리에 적재되지 않은 페이지, 즉 유효 비트가 0인 페이지에 접근하면 페이지 폴트(page fault)라는 예외(Exception)가 발생한다.

🔎 페이지 폴트(Page fault)

• CPU가 메모리에 없는 페이지(유효 비트=0)에 접근하려 할 때 발생하는 예외(Exception)
• CPU의 페이지 폴트 처리 과정
  1. 기존 작업 내역을 백업
  2. 페이지 폴트 처리 루틴 수행
     • 원하는 페이지를 메모리에 적재하고 유효 비트를 1로 변경
  3. 페이지가 적재된 이후, 중단된 명령 재개 및 수행

 

➡️ 보호 비트(Protection bit)

• 페이지 보호 기능을 위해 존재하는 비트로, 페이지의 접근 권한을 나타내는 비트
• 읽기(Read)를 나타내는 r, 쓰기(Write)를 나타내는 w, 실행(eXecute)을 나타내는 x의 조합으로 페이지 접근 권한을 제한함
• ex. 보호 비트가 100으로 설정된 페이지는 r이 1, w와 x가 0이므로 읽기만 가능
• ex. 보호 비트가 111로 설정된 페이지는 r,w,x가 모두 1이므로 읽기, 쓰기, 실행 모두 가능

 

➡️ 참조 비트(Reference bit)

• CPU가 해당 페이지에 접근한 적이 있는지를 나타내는 비트
• 페이지에 적재한 이후에 CPU가 읽거나 쓴 페이지는 참조 비트가 1로, 읽거나 쓴 적이 없는 페이지는 0으로 유지

 

➡️ 수정 비트(Modified bit)

• 해당 페이지에 데이터 변경(쓰기 작업)이 발생했는지를 나타내는 비트로 더티 비트(Dirty bit)라고도 부름
• 수정 비트가 1이면 변경된 적 있는 페이지
  • 한 번이라도 페이지에 쓰기 작업을 한 경우로 페이지를 메모리에서 삭제할 때 페이지의 수정 내역을 보조기억장치에도 반영해 두어야하므로 보조기억장치에 대한 쓰기 작업 필요
• 수정 비트가 0이면 변경된 적 없는 페이지
  • 보조기억장치에 반영할 수정 내역 없으므로 별도의 쓰기 작업 없이 삭제 가능

---

내부 단편화 (Internal Fragmentation)

 

페이징은 외부 단편화 문제는 해결할 수 있지만, 내부 단편화라는 또 다른 문제를 야기할 수 있다.

 

내부 단편화 ( Internal Fragmentation)

 

💡내부 단편화 (Internal Fragmentation)

• 페이징은 프로세스의 논리 주소 공간을 페이지라는 일정한 크기의 단위로 나누는 방식이지만, 모든 프로세스가 페이지 크기에 딱 맞게 잘리는 것은 아니다. 즉 모든 프로세스의 크기가 페이지의 배수가 아니다.
• 예를 들어, 페이지 크기는 10KB인데 프로세스의 크기가 107KB인 경우, 마지막 페이지는 3KB만큼 남게된다.
• 이렇게 페이지 하나의 크기보다 작은 크기로 발생하게 되는 메모리 낭비를 내부 단편화 (Internal Fragmentation)라고 한다.

---

페이지 테이블 베이스 레지스터 (PTBR)

 

페이지 테이블 베이스 레지스터 (PTBR)

 

💡페이지 테이블 베이스 레지스터 (PTBR)

• 프로세스마다 각기 다른 페이지 테이블이 메모리 내 서로 다른 위치에 존재하기 때문에, 프로세스를 실행할 때마다 페이지 테이블 위치를 나타내는 레지스터가 필요
• 이때 필요한 페이지 테이블의 위치를 가리키는 레지스터를 페이지 테이블 베이스 레지스터(Page Table Base Register, PTBR)라고 함

---

페이지 테이블 문제점과 해결 방안

 

 각 프로세스의 페이지 테이블은 메모리에 적재될 수 있는데, 이 경우 문제가 발생할 수 있다. 모든 프로세스의 페이지 테이블을 메모리에 두게되면 1️⃣ 메모리 접근 횟수가 많아지고, 2️⃣ 메모리 용량을 많이 차지하기 때문에 비효율적이다. 따라서 운영체제는 모든 페이지 테이블을 메모리에 적재하는 것을 가급적 지양한다. 각각의 문제 상황과 해결 방법에 대해 알아보자.

 

💡메모리 접근 횟수 문제

 

🔎 문제 상황

• 페이지 테이블이 메모리에 있을 경우, CPU가 데이터를 찾으려면 페이지 테이블에 접근하기 위해 1회 + 실제 프레임에 접근하기 위해 1회, 이렇게 총 2번 메모리에 접근해야 한다. 따라서 메모리 접근 시간이 2배로 늘어날 수 있다.

🔎 해결 방안

TLB (Translation Look-aside Buffer)

• TLB(Translation Look-aside Buffer) 사용
• 자주 접근하는 페이지 테이블 엔트리를 저장한 캐시 메모리
• CPU가 페이지 접근 시 먼저 TLB 확인 → TLB는 페이지 테이블의 캐시이므로 참조 지역성의 원리에 근거해 자주 사용할 법한 페이지 위주로 페이지 테이블의 일부 내용을 저장해 놓는다.
• TLB Hit
  • CPU가 접근하려는 논리 주소의 페이지 번호가 TLB에 있는 경우로, TLB가 CPU에게 해당 페이지 번호가 적재된 프레임 번호를 알려준다.
  • TLB에 정보 있으면 메모리 접근 횟수 1회로 감소
  • 메모리 접근 횟수를 낮추려면 TLB 히트율을 높여야한다.
• TLB Miss
  • TLB에 정보 없으면 페이지 테이블을 메모리에서 다시 참조 (메모리 접근 2회)

 

💡메모리 용량 문제

 

🔎 문제 상황

• 프로세스의 크기가 클수록 페이지 테이블의 크기도 커지기 때문에 프로세스를 이루는 모든 페이지 테이블 엔트리들을 메모리에 저장하게되면 메모리 낭비가 발생할 수 있다.

🔎 해결 방안

계층적 페이징(Hierarchical paging)

페이지 테이블의 계층은 2개, 3개, 그 이상으로도 구성될 수 있다.

• 계층적 페이징(Hierarchical paging) = 다단계 페이지 테이블(Multilevel page table) 사용
• 페이지 테이블을 여러 개의 페이지로 자르고, CPU와 가장 가까운 바깥 쪽에 페이지 테이블(Outer 페이지 테이블)을 하나 더 두어 잘린 테이블 페이지들을 가리키게 한다.
• Outer 페이지 테이블만 메모리에 유지되어 메모리 낭비가 줄고, 페이지 테이블의 일부분을 보조기억장치에 저장할 수 있어 메모리 효율 증가한다.

---

페이징 주소 체계

 

하나의 페이지 내에는 여러 주소가 포함되어 있기 때문에 페이징 시스템에서 논리 주소는 기본적으로 <페이지 번호(page number), 변위(offset)> 로 구성되어있다.

 

💡페이지 번호(Page Number)

• 몇 번째 페이지 번호에 접근할지 나타낸다.
• 페이지 테이블을 참조하면 물리 메모리 내의 어떤 프레임에 접근할지 알 수 있다.

 

💡변위(offset)

• ?

---

페이지 교체 알고리즘

 

💡요구 페이징(Demand Paging)

• 메모리에 프로세스를 적재할 때 처음부터 모든 페이지를 적재하지 않고, 실제로 필요한 시점에(요구될 때) 해당 페이지를 메모리에 적재하는 기법
• 프로그램 실행 시 전체를 한 번에 메모리에 올리는 게 아니라, 페이지가 처음 접근되는 순간에 그때 비로소 메모리로 가져온다.
• 요구 페이징 과정 예시

1️⃣ CPU가 특정 페이지에 접근하는 명령어를 실행한다.
2️⃣ 해당 페이지가 현재 메모리에 존재하면, (유효 비트가 1일 경우) → CPU는 이미 메모리에 올라와 있는 프레임에 접근해 바로 실행한다.
3️⃣ 해당 페이지가 메모리에 없으면, (유효 비트가 0일 경우) → 페이지 폴트(page fault)가 발생한다.
4️⃣ 페이지 폴트가 발생하면, 처리 루틴 실행
→ 보조기억장치에서 해당 페이지를 메모리로 가져와 적재
→ 유효 비트를 1로 변경(메모리에 있음 표시)
5️⃣ 다시 명령을 반복 수행 → 이제 페이지가 메모리에 있으므로 정상적으로 접근 가능

 

 

💡순수 요구 페이징(Pure Demand Paging)

• 아무런 페이지도 메모리에 적재하지 않고 프로세스를 실행 가능한데, 이를 순수 요구 페이징(Pure Demand Paging)이라고 한다.
• 프로세스의 첫 명령어를 실행하는 순간 페이지 폴트가 발생하고, 필요한 페이지만 메모리에 적재한다.
• 어느 정도 필요한 페이지가 메모리에 적재된 이루부터는 페이지 폴트 발생 빈도가 감소한다.

 

 이렇게 요구 페이징을 사용하면 프로세스가 접근하는 페이지가 점점 메모리에 쌓이고, 결국 메모리 공간이 가득 차는 순간이 온다. 이때, 새로운 페이지를 적재해야 하면, 기존에 메모리에 적재된 일부 페이지를 스왑 아웃(swap out)하여 내보내고 그 자리에 새 페이지를 적재해야 한다. 이 상황에서 메모리에 적재된 페이지 중 보조기억장치로 내보낼 페이지를 선택하는 방법을 페이지 교체 알고리즘(Page Replacement Algorithm)이라고 한다.

 

💡페이지 교체 알고리즘(Page Replacement Algorithm)

 

 페이지 교체 알고리즘의 성능이 컴퓨터 전체의 성능에 영향을 미친다. 어떤 알고리즘을 사용하느냐에 따라 페이지 폴트 발생 빈도가 달라질 수 있기 때문이다. 좋은 알고리즘은 메모리에서 잘 사용하지 않는 페이지를 적절하게 보조기억장치로 내보내어 페이지 폴트 발생 빈도를 줄지만, 나쁜 알고리즘은 자주 사용하는 페이지를 보조기억장치로 내보내 페이지 폴트를 자주 발생시켜 성능 저하로 이어진다. 따라서 페이지 폴트 발생 빈도가 페이지 교체 알고리즘의 성능 지표가 된다. 아래 대표적인 페이지 교체 알고리즘 3가지에 대한 설명이다.

 

스레싱(thrasing)
프로세스가 실제로 실행되는 시간보다 페이지 교체에 더 많은 시간이 소모되는 현상으로, 지나친 페이지 교체로 인상 성능 저하 문제를 일컫는다.

 

• FIFO 페이지 교체 알고리즘 (First-In-First-Out Page Replacement Algorithm)
  • 가장 먼저 적재된 페이지부터 스왑 아웃하는 페이지 교체 알고리즘
  • 구현은 간단하지만, 자주 참조되는 페이지를 스왑 아웃 하면 자주 페이지 폴트가 발생하여 성능 저하를 일으킨다.
• 최적 페이지 교체 알고리즘 (Optimal Page Replacement Algorithm)
  • 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘
  • 메모리에 적재된 페이지들 중 앞으로 가장 적게 사용할 페이지를 스왑 아웃해 가장 낮은 페이지 폴트율을 보장하는 알고리즘이다.
  • 이론적으로는 최적이지만, 미래 사용을 예측하기 어렵기 때문에 실제 구현이 어려운 알고리즘이다.
• LRU 페이지 교체 알고리즘 (Least Recently Used Page Replacement Algorithm)
  • 가장 적게 사용한 페이지를 교체하는 알고리즘
  • 실제 시스템에서 가장 보편적으로 사용되는 페이지 교체 알고리즘, 이를 기반으로 만들어진 다양한 파생 알고리즘이 있다.

 

💡페이지 폴트의 종류

 

페이지 폴트에도 여러 종류가 있는데, 보조기억장치와의 입출력 작업이 필요한지에 따라 크게 두가지로 구분할 수 있다. 

• 메이저 페이지 폴트 (major page fault)
  • CPU가 요청한 페이지가 메모리에 없고, 보조기억장치에서 실제 데이터를 가져와야 하는 경우
  • 상대적으로 성능 저하 큼
• 마이너 페이지 폴트 (minor page fault)
  • 페이지가 메모리에 있지만, 페이지 테이블에 정보가 갱신되지 않은 경우
  • 보조기억장치 접근 없이 처리 가능, 성능 저하 적음

---

출처

https://www.hanbit.co.kr/store/books/look.php?p_code=B3079890360

이것이 취업을 위한 컴퓨터 과학이다 with CS 기술 면접

---

이미지 출처

1) 페이지 테이블

https://ddongwon.tistory.com/49

페이징(Paging)과 페이지 테이블(Page table)

2) 내부 단편화

https://toberich.co.kr/entry/외부단편화와-내부단편화

외부단편화와 내부단편화

3) 혼자 공부하는 컴퓨터 구조+운영체제

https://www.youtube.com/watch?v=8ufliWkgqMo&t=473s&ab_channel=%ED%95%9C%EB%B9%9B%EB%AF%B8%EB%94%94%EC%96%B4

4) TLB

https://cs4118.github.io/www/2023-1/lect/19-TLB.html

Translation Lookaside Buffer (TLB)

5) 계층적 페이징

https://velog.io/@lcy960729/페이지-테이블의-구조-계층적-페이징

페이지 테이블의 구조 - 계층적 페이징