페이징

코승호딩·2022년 10월 21일

운영체제

목록 보기

8/10

📌페이징이란

이제까지 앞에서 알아본 메모리 공간 관리는 모두 가변 크기를 사용하는 세그멘테이션 기법이었다.
가변 크기로 할당하게 되면 외부 단편화 문제가 발생하였고, 이러한 문제를 해결하기 위해 페이징 기법이 나오게 되었다.

페이징 : 주소 공간을 페이지라고 불리는 동일한 크기의 조각으로 잘라서 관리한다.
페이지의 크기는 페이지 프레임의 크기(나중에 알아보자)
페이지 : 가상 공간에서 나누어진 고정 크기 단위
페이지 프레임 : 변환된 물리 주소 실제 메모리에서 페이지를 부르는 단위

즉 가상 메모리에서 page를 실제 메모리에서는 page frame이라고 불리는 고정 크기의 공간으로 프로세스를 실행하는 것이다.

페이징 장점 1 : 유연성
주소 공간의 일관적인 관리
HW로 구현할 필요가 없다.
페이징 장점 2 : 빈 공간 관리가 쉽다.
페이지 크기와 페이지 프레임의 크기가 같다.
빈 공간 리스트의 모든 조각의 크기가 같다.

위 좌측 그림에서 64바이트의 크기의 가상주소공간의 크기를 16바이트 4개로 쪼개놨다. 여기서 16바이트 공간을 페이지라고 부른다.
위 우측 그림은 실제 메모리이며 128바이트의 메모리를 16 바이트씩 8개로 쪼개놨다. 여기서 16바이트 공간을 페이지 프레임이라고 부른다.

주소 변환

각 페이지들에 대한 실제 메모리 위치를 기억하고 이를 활용해 주소 변환이 가능하다.
페이징을 사용할 때에 모든 프로세스는 페이지 테이블이 존재한다.
가상 주소를 물리 주소로 변환하기 위해 프로세스마다 페이지 테이블을 사용하는 것이다.

프로세서의 가상 주소를 변환하기 위해서는 vpn(virtual page number)과 offset이 있어야 한다.

vpn : 가상 페이지 번호
offset : 페이지 내에서의 오프셋

맨 위 그림은 64바이트 크기의 가상 공간을 16바이트로 나눠 총 4개의 페이지를 사용하였다.
4개의 페이지를 구분하기 위해 상위 2비트인 VPN에 저장하는 것이다.
그리고 하위 4비트는 offset을 통해 각 페이지의 자세한 위치를 알 수 있다.
위 그림에서는 페이지의 크기가 16바이트이므로 4개의 비트가 offset으로 사용이 되었다.

위 그림에서 010101b는 21의 이진수이며 상위 두비트가 01이기 때문에 두번째 페이지의 하위 4비트 0101에 해당하는 5바이트만큼 오프셋 된 위치를 가리킨다.
이 페이지 테이블의 2번째 인덱스에는 실제 메모리의 프레임 넘버가 저장되어 있다. 이 정보를 통해 PFN으로 변환하면 실제 메모리 주소를 얻을 수 있다.
따라서 VPN을 PFN으로 변환해주고 offset은 그대로 사용하는 것이다. 그렇게 되면 실제 메모리 주소는 1110101b가 된다.

페이지 테이블의 위치

페이지 테이블의 크기는 엄청날 수 있다.
예를들어 4KB 페이지를 갖는 32비트의 가상 주소 공간이 있다. 이 가상 주소는 20비트의 VPN, 12비트의 offset으로 분할된다.
VPN이 20개의 비트로 표현된다는 것은 OS가 프로세스에 대해 관리해야 할 페이지 수가 100만 개 정도 된다는 것이다.
따라서 페이지 테이블의 크기가 4바이트라고 한다면, 4바이트 * 100만 개 = 4MB가 된다.
-> CPU의 레지스터에 저장하는 것은 불가능하므로 메모리에 존재

페이지 테이블의 내용

가상 주소를 물리 주소로 변환하기 위한 자료 구조이다. (= 배열)
단순화 하면 선형 페이지 테이블이다.
OS는 VPN을 인덱스로 페이지 테이블을 읽고 쓴다.
VPN으로 해당 프로세스의 페이지 테이블 배열을 인덱싱하고 해당 인덱스 페이지 테이블 앤트리(PTE)를 조회한다.
PTE는 각 페이지의 정보

P : 이 페이지가 물리 메모리에 존재하는가? 아니면 디스크에 존재하는가?
R/W : 읽어도 되는가? 써도 되는가? 실행해도 되는가?
U/S : user mode 프로세스가 페이지에 접근할 수 있는가?
A : 한번이라도 참조한적이 있는가
D : page가 수정된 적이 있는가
PFN : 페이지 프레임 넘버

! 그러나 페이징은 너무 느리다.
해당 PTE를 얻기 위해서는 페이지 테이블의 시작 위치를 알아야 한다.
모든 메모리 접근에서 HW는 추가로 메모리에 접근해야 한다.
명령어, 페이지테이블 둘다 읽기엔 속도가 저하된다.

페이징 요약

장점 1 : 외부 단편화 없음
장점 2 : 작은 내부 단편화
단점 : 페이지 테이블로 인한 잦은 메모리 접근

📌TLB

페이징에서는 잦은 메모리 접근과 페이지 테이블을 위한 메모리 낭비가 있기 때문에 이를 보완하기 위해 나온 것이 TLB이다.
TLB는 CPU의 메모리 관리 장치(MMU)의 일부분이다.
TLB에는 VPN과 PFN 정보가 쌍으로 존재하며 이를 사용해 주소 변환을 도와주는 하드웨어는 바로 캐쉬이다.
간단히 설명하여

CPU가 주소 변환을 할 때, TLB가 존재한다면, 주소 변환을 위해 TLB를 조회한다. 원하는 변환 정보가 있다면 변환을 하고, 없다면 메모리에 존재하는 페이지 테이블에 접근하여 주소 변환 정보를 TLB에 저장한다. 그리고 다시 주소 변환을 시도한다. 이때, TLB부터 조회하고 메모리에서 주소 변환 정보를 저장했기 때문에 굉장히 빠른 속도로 주소 변환이 된다.

배열 접근

TLB로 인한 성능 향상을 알아보자

c언어에서 int는 4바이트이기 때문에 배열의 크기는 40바이트이다.
이 배열이 가상 주소 공간 100에서 시작한다고 하였을 때, 페이지 테이블은 다음과 같다.

배열 요소 하나당 4바이트이며 페이지 크기가 16바이트이기 때문에 page 공간에 4개의 배열 요소가 들어갈 수 있다.

TLB가 없다면 10번 반복이므로 10번 페이지 테이블에 접근하여 주소 변환을 해줘야 한다.
TLB가 있다면 처음에 TLB 미스로 페이지 테이블 접근 후 TLB에 저장하고 그 후는 같은 페이지 주소 정보를 가지고 있으니 TLB Hit으로 주소변환성공
a[3]에서 다시 미스 a[6]까지 히트 ... 하다보면
TLB miss 3번, TLB hit 7번이므로 TLB hit rate는 70퍼센트이다.
따라서 TLB는 공간 지역성으로 인해 성능을 70%나 올릴 수 있다.

지역성

시간 지역성 : 사용한 명령어나 데이터는 곧 다시 사용할 확률이 크다.
공간 지역성 : 프로그램이 x 주소의 메모리를 사용했다면 얼마 안지나 x 근처의 메모리를 사용할 확률이 크다.

TLB 미스

TLB 미스가 나면 페이지 테이블에 접근해야 하는데 과연 TLB 미스는 누가 처리를 하는 것일까?

CISC : HW가 전부 처리한다.
HW가 페이지 테이블의 위치를 정확히 알고 있다.
HW가 페이지 테이블을 검색해서 해당 PTE를 찾아 TLB에 업데이트 하고 해당 명령어를 다시 실행한다.
RISC : OS가 TLB를 관리한다.
미스가 나면 하드웨어가 현재 명령을 중지하고 권한을 커널 모드로 올린 뒤 Trap 처리기로 예외를 발생시킨다.
그 뒤 페이지 테이블을 조회하여 TLB를 업데이트 하고 다시 주소 변환을 시도한다.

이렇게 OS로 TLB를 관리하게 되면 하드웨어의 변경 없이 페이지 테이블 구현하는 모든 자료 구조를 사용이 가능하다.
미스가 발생해도 하드웨어가 할 일은 별로 없고 OS TLB Miss 핸들러가 작동하여 해결한다.

TLB의 구성이다.

TLB Issue : Context Switches

TLB를 사용할 때, Context Switch가 발생한다면 어떻게 될까?
여러 프로세스는 각자의 가상 메모리 공간이 존재하고 page로 쪼개어지며 페이지 테이블의 인덱스가 같은 경우가 있다.
예를 들어 A의 VPN1에 대한 정보가 TLB에 저장 되어 있는데 context switch가 발생하여 B가 실행된다면
B에서도 VPN1에 대한 주소 변환을 하려고 TLB를 확인할 때, VPN1이 값이 같아 TLB에서 주소 변환을 하면 문제가 발생한다.

다음과 같이 A(위), B(아래)의 VPN 10에 대한 주소 변환 정보가 TLB에 저장이 되어 있다.
VPN은 동일하지만 PFN은 동일하지 않다.
하지만 위 그림과 같이 TLB에 저장하면 어떤 프로세스인지 알 수 없다. 딱 봐도 모르겠다.
서로의 주소 공간이 아닌 곳에 잘못 접근할 수 있어 큰 문제가 될 수 있다.

해결방법 1 : 주소 공간 ID를 사용하여 구분한다.
하드웨어의 도움을 받아 ASID라는 정보를 추가하면 된다.
해결방법 2 : 모든 valid를 0으로 한다. 이렇게 되면 0으로 초기화 되어 모든 TLB의 내용을 지운다.
그러나 문맥 교환마다 이 작업을 해야 하므로 비용이 많이 발생한다.

만약 2개의 프로세스가 페이지를 공유한다면?
위와 같이 PFN이 동일하면 메모리의 사용을 줄일 수 있어 메모리 공간을 더 확보 가능

TLB 교체 정책

LRU(Least Recently Used)

사용한지 오래된 엔트리 방출
지역성을 이용

페이징 선형 테이블

모든 프로세스당 한 개씩 페이지 테이블이 필요하다.
32비트 주소 공간에서 4KB 크기의 페이지를 사용하고 페이지 테이블 엔트리로 4바이트를 사용한다면
페이지 테이블은 매우 커서 많은 메모리가 소비 된다.

페이징 테이블 크기 줄이기

그럼 만약 페이지의 크기를 늘린다면 페이지 테이블의 크기를 줄일 수 있을 것이다.
위 그림과 같이 하나의 페이지를 4KB가 아닌 16KB로 늘릴 경우
페이지 테이블의 크기는 1MB가 되는 것이다.
기존 테이블 크기보다 1/4로 감소한 것을 볼 수 있다.
그러나 당연히 이렇게 큰 페이지는 내부 단편화가 발생할 수 있다.

다음 그림과 같이 페이지 테이블의 대부분이 미사용중인 것을 볼 수 있다.

하이브리드 접근법 : 페이징과 세그먼트

페이지 테이블로 인한 메모리 부담을 줄이기 위해 사용되는 기법이다.

세그먼트를 사용하지만, base 주소가 실제 세그먼트 시작주소가 아닌 세그먼트의 페이지 테이블의 주소이다.
바운드 레지스터는 페이지 테이블의 끝 주소를 갖는다.

세그멘테이션에서 살펴본것과 같이 모든 프로세스는 Code, Heap, Stack 총 3개의 세그먼트를 갖고있고 이에 해당하는 3개의 페이지 테이블을 갖는다.
실행 중인 프로세스에서 각 세그먼트의 베이스 레지스터는 각 세그먼트 페이지 테이블의 시작 물리 주소를 갖게 된다.
문맥 교환 시, 레지스터들은 새로 실행되는 프로세스의 페이지 테이블의 위치값으로 변경된다.

TLB 미스 발생시 하드웨어는 세그먼트 비트를 사용하여 어떤 베이스와 바운드 쌍울 사용할지 결정한다.
하드웨어는 그 레지스터에 들어 있는 물리 주소를 VPN과 다음과 같은 형식으로 조작하여 PTE의 주소를 얻는다.

따라서 바운드 레지스터가 세그먼트의 페이지 테이블의 끝 값을 가지므로 사용하지 않는 페이지 테이블의 공간을 유지할 필요가 없다.
그러나 이 하이브리드 방법은 세그멘테이션의 문제인 외부 단편화가 있다.
또한 세그멘테이션 방법을 사용할 때 생각해야 하는 연속된 메모리 공간을 관리해야 한다.
정말 외부 단편화, 내부 단편화 이리저리 화가난다.

📌멀티-레벨 페이지 테이블

긴 페이지 테이블을 트리 형식으로 변경한 것이다.

페이지 테이블을 페이지 크기의 조각으로 자른다.
어떤 조각의 속하는 페이지들이 전부 무효 상태이면 그 조각은 비워둔다(메모리 할당x)
조각의 유효 여부와 조각의 위치를 알기 위해 페이지 디렉토리라는 새 자료구조를 사용해야 한다.

위 그림에서 왼쪽에는 기존의 페이지 테이블, 오른쪽에는 멀티 레벨 페이지 테이블이 있다.
왼쪽 페이지 테이블은 1개의 페이지 테이블은 전혀 사용하고 있지 않고 낭비가 되고 있다.
오른쪽은 페이지 디렉토리라는 자료 구조를 사용하여 실제 사용중인 2개의 페이지테이블에만 접근하고 있다.
이렇게 주소 변환에 한 번의 단계가 추가되어 멀티 레벨이라 부르는 것이다.
페이지 디렉토리는 PDE들로 구성되어 있고, 하나의 PDE는 페이지 크기의 페이지 테이블 조각 하나를 담당한다.

페이지 디렉토리 크기 = PDE 개수 * PDE 크기
PDE 개수 = 페이지 테이블 크기 / 페이지 크기
PDE도 유효 비트와 PFN을 가지고 있다.

그렇다면 멀티 레벨 페이지 테이블의 장단점을 요약해보자

장점 1 : 페이지 테이블의 크기가 실제 사용하고 있는 메모리 크기에 비례하여 낭비가 적다.
장점 2 : 페이지 테이블의 추가, 삭제가 편하다, 연속된 메모리를 요구하지 않는다.
단점 1 : 성능-공간의 상호 절충이다.
단점 2 : 복잡하다.

멀테 레벨 페이징 예제

다음과 같이 64비트의 페이지를 갖는 16KB 크기의 주소 공간이 있다.
VPN은 8비트, 오프셋은 6비트가 필요하다.
가상 페이지 0, 1은 코드, 4, 5는 힙, 254, 255는 스택으로 사용된다. 그리고 나머지 페이지들은 미사용이다.
PTE는 4바이트라 가정하였을 때, 선형 페이지 테이블을 사용하면 페이지 테이블 하나의 크기는 2^10 즉, 1KB이다.

이 상황에서 페이지 디렉토리를 생성해보자
VPN으로부터 페이지 디렉토리 인덱스를 추출하고, 페이지 데이블의 각 페이지 위치를 파악하면 된다.
위 예에서 256개의 PTE가 16페이지에 나뉘어져 있다.
페이지 디렉토리는 페이지 테이블의 각 페이지마다 있어야 하므로 총 16개의 항목이 존재해야 한다.
따라서 VPN4개의 비트를 이용해 위 그림과 같이 디렉토리를 구성한다
페이지 디렉토리의 해당 항목이 유효하지 않다면 예외 처리를 발생시킨다.
유효하다면 더 나아가 페이지 테이블 인덱스로 페이지 테이블 내부에서 PTE를 찾는다.

Inverted Page Tables

페이지 테이블 크기를 줄이는 방법은 페이지 테이블을 거꾸로 적용하는 것이다.
즉 프로세스마다 페이지 테이블이 하나씩 존재하는 것이 아닌
모든 프로세스가 하나의 페이지 테이블을 사용하는 것이다.
주소 변환 시간에 검색이 필요하다.

물리 메모리 크기의 극복

페이지 테이블을 아예 디스크에 저장하여 메모리 낭비를 줄이는 방법을 설명하고자 한다

📌실제 메모리 그 이상 : 정책

메모리 압박은 OS가 페이지를 쫓아 내도록 한다.
어떤 페이지를 방출할 것인지 결정하는 것이 OS의 교체 정책이다

교체 정책의 목적은 캐시 미스를 줄이는 것이다.
캐시 미스 확률을 통해 평균 메모리 접근 시간을 얻을 수 있다.

평균 메모리 접근 시간 = (캐시 히트 수 x 메모리 1회 접근 시간) + (캐시 미스 수 x 디스크 1회 접근 시간)

최적 교체 정책

가장 적은 교체 회수를 가진다.
앞으로 재사용될 시간이 가장 나중인 페이지를 교체한다.
최소의 캐시미스
비교를 위해서 사용, 다른 방법들이 얼마나 완벽한지 알기 위한 비교 용도

tracing the optimal policy는 다음과 같이 동작한다.
처음에 아무것도 없으니 3번까지 미스가 발생한다. -> 강제미스
캐시에 0, 1, 2가 존재하는데 3번 페이를 요청하고 따라서 페이지 폴트가 일어나 페이지를 교체해야 한다.
optimal에서는 페이지 폴트가 발생한 시점에서 가장 나중에 사용되는 페이지 2를 교체한다.
그후 미스에서는 0, 3중 랜덤으로 3을 교체하여 5 / 11의 미스율을 보여준다.

간단한 정책 : FIFO

모두 알다시피 메모리에 올라온 순서대로 페이지를 내보내는 것이다.
교체가 발생하게 되면 큐의 앞에 있는 페이지가 방출된다.

구현이 간단하지만, 페이지의 중요성이 고려되지 않는다.

썩 좋지 않다.
미스 비율이 옵티말보다 높아졌다.

BELADY의 역설

할당된 물리 프레임 수가 커질수록 페이지 적중률이 올라갈 것 같지만 FIFO에서 오히려 떨어지는 현상

또 다른 간단한 정책 : 무작위 random

메모리 압박시 랜덤한 페이지를 내보낸다.

성능도 운에 따르고 FIFO보다는 좋고 최적보다는 나쁘다.

가끔씩 최적과 비슷한 성능을 보인다.

과거 정보의 사용 LRU

LRU : 과거를 보고 교체할 페이지를 선택한다. 최근에 접근된 페이지는 곧 또 접근될 것이라는 아이디어 -> 지역성 활용
따라서 가장 과거에 사용한 페이지를 교체하는 것이다.
최소 최근 접근 페이지를 교체한다.

워크로드에 따른 성능 비교

위그림은 지역성이 없으며 총 페이지 수가 100개일 때의 결과이다.
-> 100개의 페이지에 총 10000번 접근
즉 페이지 요청이 랜덤하게 발생할 때의 결과이다.
이를 보면 지역성이 적용되지 않을 시 모든 방법의 결과가 크데 다르지 않다는 것을 볼 수 있다.

위 그림은 총 접근의 80%가 전체 페이지의 20%에 존재할 때이다.
지역성이 고려되어 있고 LRU가 더 나은 결과를 보여주고 있다.
LRU는 접근이 많은 페이지를 유지할 가능성이 크기 때문에 페이지 폴트 비용이 커질수록 성능이 향상한다.

마지막으로 0~49페이지까지 순서대로 50개의 페이지를 참조하는 것을 반복하는 상황이다.

과거 이력 기반 알고리즘의 구현

LRU방식은 메모리 접근 정보를 기록해야 한다.
따라서 메모리 크기가 커진다면 페이지 수가 많아져 LRU페이지를 찾는데 소요되는 시간이 너무 커진다.

약간의 하드웨어가 필요하다

LRU 근사하기

use bit형식의 하드웨어 지원이 필요하다.
페이지 하나당 use bit가 존재한다.
page가 참조될 때마다 1로 업데이트 된다.
페이지가 참조되면 use bit는 HW에 의해 1이 된다.
-> HW는 그 비트를 초기화 하지 않는다. OS가 필요할 때 초기화 한다.
그러면 이 LRU를 어떻게 구현할까
-> 간단한 접근 방법은 시계 알고리즘이다.

시계 알고리즘 : 모든 페이지를 원형 리스트에 배치한다. 처음에는 시계 바늘이 시작페이지를 가르킨다.

시계 알고리즘

시계 바늘은 use bit가 0인 페이지를 만날 때 까지 이동한다.
1이라면 최근에 사용되었다고 판단하고 0으로 바꾼 뒤 다른 페이지를 찾는다.
0인 페이지를 만나면 해당 페이지를 교체한다.

다음과 같이 LRU보다는 못하지만 과거 정보를 활용하지 않는 다른 방법보다는 낫다.

갱신된 페이지(Dirty Pages)고려

HW로 구현된 변경 비트(modified bit, dirty bit)
-> 페이지가 변경 되었다면 방출될 때 디스크에 내용을 기록해야 한다.
-> 변경되지 않았다면, 방출 비용은 없다.
갱신되지 않고 사용 되지도 않은 페이지를 우선 방출하고, 없으면 변경되고 사용되지 않는 페이지를 방출한다.

다른 VM 정책들

페이지를 언제 메모리에 로딩할 것인가?
여러가지 옵션이 있음

선반입

사용될 페이지를 추측하여 미리 불러오는 것

클러스터링, 모으기

디스크에 써야 하는 페이지들을 모아 놓았다가 한번에 쓰는 방식
여러 번의 작은 디스크 전송보다 한번의 큰 디스크 전송이 훨씬 효율적

쓰래싱

메모리 사용 요구가 감당할 수 없을 만큼 많고, 실행 중인 프로세스가 요구하는 메모리가 가용 물리 메모리 크기를 초과하는 경우

일부 프로세스를 중단한다.
워킹 셋이 물리 메모리 크기에 맞도록 조정한다.

코승호딩

코딩 초보 승호입니다.

이전 포스트

세그멘테이션

다음 포스트

페이징