12 Paging (페이징)

페이징(Paging)은 운영체제와 하드웨어가 협력하여 가상 메모리를 물리 메모리로 매핑하는 기술 중 하나입니다. 이는 메모리를 일정한 크기의 고정된 블록으로 나누는 것을 의미합니다. 각 블록은 페이지라고 불리며, 물리 메모리는 페이지 프레임이라고 불리는 동일한 크기의 조각으로 나뉩니다.

비연속적 할당

프로세스의 페이지는 물리 메모리에 연속적으로 위치할 필요가 없습니다. 각 페이지는 독립적으로 할당될 수 있어 외부 단편화를 줄일 수 있습니다.

 

페이지 테이블

가상 메모리의 각 페이지와 물리 메모리의 각 페이지 프레임을 매핑하는 페이지 테이블이라는 자료구조를 사용합니다. 이 테이블은 운영체제가 관리하며, 프로세스의 가상 주소를 물리 주소로 변환합니다.

• PTBR은 "Page Table Base Register"의 약어로, 컴퓨터 아키텍처에서 가상 메모리 관리를 위한 중요한 레지스터입니다. 가상 메모리는 물리 메모리보다 크기가 크거나 다양한 프로세스가 메모리를 공유하는 경우에 사용됩니다. PTBR은 이러한 가상 메모리를 관리하기 위해 페이지 테이블의 시작 주소를 저장하는 역할을 합니다. 간단하게 설명하면, 페이지 테이블은 가상 주소 공간과 물리 주소 공간 간의 매핑 정보를 저장하는 테이블입니다. PTBR은 이 페이지 테이블의 시작 지점을 가리키며, 이를 통해 운영체제는 가상 주소를 물리 주소로 변환할 수 있습니다.
• TLB는 "Translation Lookaside Buffer"의 약어로, 가상 메모리 주소를 물리 메모리 주소로 변환하는 데 사용되는 고속 캐시입니다. 가상 메모리 관리 시스템에서 성능을 향상시키기 위한 핵심 구성 요소 중 하나입니다. 간단하게 설명하면, TLB는 가상 주소에서 물리 주소로의 변환을 담당하는데, 이를 효율적으로 수행하기 위해 자주 사용되는 페이지 테이블 엔트리들을 캐시에 저장합니다.

 

고정 크기 페이지

메모리를 고정 크기의 페이지로 나눕니다. 이 페이지는 가상 메모리와 물리 메모리 양쪽에 동일한 크기로 존재합니다.

 

내부 단편화(Internal Fragmentation)

메모리 내의 조각들 중에서 실제로 사용되지 않는 부분을 나타냅니다. 내부 단편화는 주로 동적 메모리 할당 시에 발생하며, 할당된 메모리 블록이 프로세스가 요구하는 메모리 양보다 큰 경우에 발생합니다.

동적 메모리 할당 기법에서는 내부 단편화를 최소화하기 위한 다양한 방법들이 사용됩니다. 이러한 방법에는 가변 크기 할당, 메모리 풀(memory pool) 사용, 또는 힙 관리 알고리즘의 최적화가 포함될 수 있습니다.

 

 

---

 

 

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

페이지 테이블 엔트리(Page Table Entry, PTE)는 페이지 테이블에서 한 개의 항목을 나타내는 데이터 구조입니다. 페이지 테이블은 가상 메모리 주소와 물리 메모리 주소 간의 매핑 정보를 저장하며, 각각의 페이지 테이블 엔트리는 하나의 가상 페이지에 대한 매핑 정보를 담고 있습니다.

• 프레임 번호(Frame Number): 가상 페이지가 매핑되는 물리 메모리의 프레임 번호를 나타냅니다. 이를 통해 가상 주소를 물리 주소로 변환할 수 있습니다.
• 유효 비트(Valid Bit): 해당 페이지 테이블 엔트리가 유효한지를 나타내는 비트입니다. 유효한 페이지 테이블 엔트리는 가상 주소와 물리 주소 간의 유효한 매핑을 나타내며, 유효하지 않은 경우에는 해당 가상 페이지가 메모리에 없다는 것을 의미합니다.
• 쓰기 권한 비트(Write-Protect Bit): 해당 페이지에 대한 쓰기 권한을 제어하는 비트입니다. 이 비트가 설정되어 있으면 해당 페이지는 읽기 전용이 되어 쓰기가 불가능합니다.
• 액세스 권한 비트(Access Rights Bit): 페이지에 대한 읽기 및 실행 권한을 제어하는 비트입니다. 이 비트를 통해 해당 페이지에 접근 가능한지 여부를 확인할 수 있습니다.
• 기타 플래그 비트(Other Flags): 페이지 테이블 구현에 따라서 추가적인 플래그 비트가 존재할 수 있습니다. 예를 들어, 캐시 사용 여부 등을 나타낼 수 있습니다.

페이지 테이블 엔트리는 가상 메모리와 물리 메모리 간의 중요한 연결을 제공하며, 이를 통해 가상 메모리 관리를 수행합니다.

 

 

---

 

요구 페이징(Demand Paging)

요구 페이징(Demand Paging)은 운영체제가 프로세스의 실행을 위해 모든 페이지를 한 번에 메모리에 적재하지 않고, 실제로 필요한 페이지만 적재하는 가상 메모리 관리 기법입니다. 이는 메모리 사용 효율성을 높이고, 시스템 성능을 향상시키는 데 도움이 됩니다.

요구 페이징의 주요 특징 

• 지역성 이용: 프로세스가 실행되는 동안 특정 시점에서는 일부 페이지만 필요하다는 지역성의 원리를 기반으로 합니다. 따라서 모든 페이지를 메모리에 사전에 적재하는 대신, 실제로 필요한 페이지만 적재하여 메모리 사용을 최적화합니다.
• 페이지 부재 처리: 프로세스가 실행되는 동안 필요한 페이지가 메모리에 없는 경우에는 페이지 부재(Page Fault)가 발생하고, 필요한 페이지만 디스크에서 메모리로 적재됩니다. 이를 통해 프로세스의 실행이 중단되지 않고 메모리를 효율적으로 활용할 수 있습니다.
• 느슨한 결합(Loose Coupling): 페이지들 간에 서로 독립적이므로, 어떤 페이지가 메모리에서 적재되지 않거나 제거되어도 다른 페이지에는 영향을 미치지 않습니다.
• 종류별 외부 단편화 감소: 모든 페이지를 사전에 메모리에 적재하지 않기 때문에 발생하는 종류별 외부 단편화를 감소시킬 수 있습니다.

요구 페이징은 가상 메모리를 사용하는 대부분의 운영체제에서 채택되어, 효율적이고 유연한 메모리 관리를 가능하게 합니다.

 

 

---

 

 

 

페이징의 작동: 프로세스가 실행될 때, 필요한 페이지들이 물리 메모리에 로드됩니다. 필요한 페이지가 메모리에 없는 경우 페이지 부재(Page Fault)가 발생하고, 운영체제는 해당 페이지를 디스크에서 가져와 물리 메모리에 할당합니다.

 

페이지 교체 알고리즘은 가상 메모리 시스템에서 페이지 부재(Page Fault)가 발생할 때 어떤 페이지를 메모리에서 제거하고 새로운 페이지로 교체할지를 결정하는 알고리즘입니다. 다양한 페이지 교체 알고리즘이 있으며, 각각의 알고리즘은 메모리 사용의 효율성을 향상시키기 위한 다른 전략을 가지고 있습니다.

일반적인 페이지 교체 알고리즘의 종류들 

1. FIFO (First-In-First-Out): 메모리에 들어온 순서대로 페이지를 교체하는 알고리즘입니다. 가장 오래전에 메모리에 들어온 페이지를 교체합니다.
2. LRU (Least Recently Used): 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘입니다. 페이지에 접근할 때마다 해당 페이지의 사용 시간을 갱신하고, 교체할 때는 사용 시간이 가장 오래된 페이지를 선택합니다.
3. LFU (Least Frequently Used): 사용 빈도가 가장 적은 페이지를 교체하는 알고리즘입니다. 페이지에 접근할 때마다 해당 페이지의 사용 횟수를 갱신하고, 교체할 때는 사용 횟수가 가장 적은 페이지를 선택합니다.
4. Optimal: 이론적으로 최적인 교체 알고리즘으로, 미래의 페이지 접근을 모두 고려하여 최소한의 페이지 부재를 발생시키는 알고리즘입니다. 실제로는 미래의 접근 패턴을 예측할 수 없으므로 구현이 어렵습니다.
5. Clock (또는 Second-Chance): FIFO와 LRU의 중간 지점에 있는 알고리즘으로, 참조 비트(Reference Bit)를 사용하여 페이지의 "순서"를 추정하는 방식입니다.
6. NRU (Not Recently Used): 페이지의 참조 여부와 수정 여부에 따라 페이지를 4개의 클래스로 분류하고, 이를 기반으로 페이지를 교체하는 알고리즘입니다.

각 알고리즘은 자체적인 특징과 장단점을 가지며, 특정 상황에서 더 효과적일 수 있습니다. 페이지 교체 알고리즘의 선택은 시스템의 특성과 요구사항에 따라 결정되며, 성능 향상을 위해 여러 알고리즘을 조합하는 경우도 있습니다.