가상 메모리, 페이징(Paging) [3 / 4]

junto·2024년 3월 16일

operating system

목록 보기

9/13

세그먼트 방식은 다양한 세그먼트 크기로 인해 공간이 단편화되어 할당이 점점 어려워지는 문제가 있었다. 페이징(Paging) 방식은 주소 공간을 일정한 크기로 분할하여 사용하기 때문에 외부 단편화 문제를 해결할 수 있다.

1. 페이징(Paging)

프로세스의 논리 주소를 고정 크기 단위(Page)로 나눈다. 이에 상응하여 물리 주소도 고정 크기 단위로 나눈다.
페이징은 세그먼테이션과 달리 유연하고 단순하다. 프로세스의 주소 공간 사용 방식과는 상관없이 효율적인 주소 공간을 제공한다. 예를 들어 힙과 스택이 어떤 방향으로 커지는지, 어떻게 사용되는지에 대한 가정을 하지 않아도 된다. 또한 빈 공간 16KB가 필요할 때, 페이지 크기가 4KB라면 4개의 페이지만 제공하면 된다.
작은 주소 공간(64바이트)에서 페이지 크기가 16바이트일 때, 가상 주소는 6비트( $2^6$ )가 필요하다. 가상 주소를 페이지 크기로 나누면 가상 페이지 번호(Virtual Page Number, VPN)와 오프셋(offset)을 알 수 있다. 이를 그림으로 나타내면 아래와 같다.
VPN은 4개의 페이지 중 어떤 페이지를 참조하는지, offset은 참조하는 페이지 내에서 어떤 위치를 가리키는지를 나타낸다.
물리 메모리 주소도 물리 프레임 번호(Physical Frame Number, PFN)와 offset으로 구성된다.
프로그램마다 페이지 테이블(page table)이 필요하다. 페이지 테이블에는 가상 페이지를 물리 페이지에 매핑하는 정보가 포함되어 있다. 페이지 테이블의 시작 주소를 저장하는 레지스터(Page Table Base Register)와 페이지 테이블 엔트리(Page Table Entry, PTE)개수를 나타내는 레지스터(Page Table Length Register)가 존재하여 유효한 엔트리 접근을 보장한다.

페이지 테이블 베이스 주소(PTBR)은 주소 변환 정보를 담고 있는 테이블의 시작 주소다. 물리 주소로 전환하기 위해 가장 먼저 참조된다.

1) 동작 방법

가상 주소 "21"을 물리 주소로 변환해보자. 이진수로 [010101]이다. 변환 후에도 가상 주소의 오프셋은 유지된다.
페이지 테이블 엔트리(PTE)를 통해 가상 페이지 번호(VPN) "01"에 해당하는 물리 프레임 번호 (PFN)을 찾는다. 위의 예시에선 7이며 동일 오프셋을 적용하면 [1110101]이 된다.
가상 주소 "21"은 물리 주소 "117"로 변환된 것을 알 수 있다.

2) 페이지 테이블

(1) Valid bit

페이지 테이블 엔트리가 유효한지를 나타낸다. 할당되지 않은 주소 공간(invalid)을 표현하기 위해 필요하다.

(2) Protected bit

페이지에 대한 접근 권한(읽기, 쓰기, 실행)을 제어한다.

(3) Presented bit

페이지가 물리 메모리에 있는지 또는 디스크에 있는지(스왑 아웃) 가리킨다.

(4) Dirty bit

메모리에 반입된 후 페이지가 변경되었는지를 나타낸다.

(5) Reference bit (또는 Access bit)

페이지가 최근에 참조되었는지를 나타낸다. 페이지 교체 정책에 사용된다.
x86 페이지 테이블 항목(PTE)를 나타낸 것이다.
- P: Present bit
- U/S: 사용자 모드 프로세스가 페이지에 엑세스 할 수 있는지를 결정하는 사용자/슈퍼바이저 비트
- PWT,PCD,PAT,G: 페이지에 대한 하드웨커 캐시의 동작을 결정하는 비트
- A: Reference bit
- D: Dirty bit
- PFN: 물리 페이지 번호

3) 단점

(1) 두 번의 메모리 참조

페이징을 사용한 메모리 접근 코드는 다음과 같다.

// 가상 주소에서 VPN 추출
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
// 페이지 테이블 항목(PTE) 주소 형성
PTEAddr = PTBR + (VPN * sizeof(PTE))
// PTE 반입
PTE = AccessMemory(PTEAddr);
// 프로세스가 페이지에 접근할 수 있는지 확인한다.
if (PTE.Valid == False)
	RaiseException(SEGMENTATION_FAULT)
else if (CanAccess(PTE.ProtectBits) == False)
	RaiseException(PROTECTION_FAULT)
else
	// 접근이 가능하면 물리 주소 만들고 값 가져오기
	offset = VirtualAddress & OFFSET_MASK
    PhysAddr = (PTE.PFN << PFN_SHIFT) | offset
    Register = AccessMemory(PhysAddr)

페이지 테이블 엔트리 접근

페이지 테이블 엔트리에 접근하기 위한 메모리 참조가 한 번 발생한다.

물리 주소 접근

물리 프레임 번호(PFN)를 추출하고 이를 기반으로 실제 물리 주소에 접근할 때 메모리 참조가 발생한다.
즉, Page 테이블 접근(명령어가 어디에 위치했는지) 1번, 실제 명령어 접근 1번 2번의 메모리 참조가 일어난다.

(2) 매우 큰 페이지 테이블

4KB 크기의 페이지를 가지는 32비트 주소 공간은 몇 개의 페이지 테이블 엔트리를 가질까?
먼저 4KB( $2^{12}$ )이므로 12비트 오프셋을 가지고, 20(32 - 20)비트 VPN을 가진다. 20비트 VPN은 운영체제가 각 프로세스를 위해 관리해야 하는 변환의 개수가 $2^{20}$ 라는 것을 의미한다. 대략 100만이고, 한 PTE마다 4바이트가 필요하다면 4MB가 필요하게 된다. 프로세스가 100개라면 메모리 변환 정보를 위해서만 400MB가 필요하게 된다.
이렇게 큰 용량을 MMU안에 저장하지는 못한다. 메모리에 저장해야 한다.

먼저, 첫 번째 속도 문제를 해결하기 위해 TLB라는 하드웨어의 지원을 받을 수 있다.

2. TLB(Translation-Lookaside Buffer)

1) 동작 방법 (하드웨어 처리 방식)

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True)		// TLB 히트
	if (CanAccess(TlbEntry.ProtectBits) == True)
    	Offset = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        AccessMemory(PhysAddr)
    else
    	RaiseException(PROTECTION_FAULT)
else
	PTEAddr = PTBR + (VPN * sizeof(PTE))
    PTE = AccessMemory(PTEAddr)
    if (PTE.Valid == False)
		RaiseException(SEGMENTATION_FAULT)
	else if (CanAccess(PTE.ProtectBits) == False)
		RaiseException(PROTECTION_FAULT)
	else
    	TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
        RetryInstruction()

가상 주소에서 VPN을 추출한 후 해당 VPN의 TLB 존재 여부를 검사한다.
만약 존재하면 TLB 히트이고 TLB 항목에서 PFN을 추출할 수 있다.
TLB에 변환 정보가 존재하지 않는다면 하드웨어가 변환 정보를 찾기 위해 페이지 테이블에 접근한다.
프로세스가 생성한 가상 메모리 참조가 유효하고 접근 가능하다면 해당 변환 정보를 TLB로 읽어 들인다. (매우 시간이 많이 소요되는 작업)
TLB가 갱신되면 하드웨어는 명령어를 재실행한다. TLB 변환 정보가 존재하므로, 메모리 참조가 빠르게 처리된다.

2) TLB 미스 처리주체

(1) 하드웨어

CISC(Complex Instruction Set Computers)에서 하드웨어 개발자들은 운영체제 개발자들을 완전히 신뢰할 수 없었다고 한다. TLB 미스를 하드웨어가 처리하도록 했다. 이를 위해 하드웨어 페이지 테이블에 대한 명확한 정보를 가지고 있어야 한다.

(2) 운영체제

RISC(Reduced Instruction Set Computing)는 소프트웨어 관리 TLB를 사용한다.

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True)		// TLB 히트
	if (CanAccess(TlbEntry.ProtectBits) == True)
    	Offset = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        AccessMemory(PhysAddr)
    else
    	RaiseException(PROTECTION_FAULT)
else
	RaiseException(TLB_MISS)

TLB에서 주소 찾는 것이 실패하면 하드웨어는 예외(exception)를 발생시킨다. 커널 모드로 변경이 되면 트랩 핸들러를 실행하여 TLB 미스 처리를 담당하는 운영체제 코드가 실행된다.
TLB가 미스 처리된 경우 트랩을 발생시킨 명령을 다시 실행해야하며, 재실행 시에는 TLB에서 히트가 발생한다. 따라서 TLB 미스가 무한 반복하지 않도록 주의해야 한다. TLB 미스 핸들러를 물리 메모리에 위치시키는 것도 하나의 방법이다.

3) 구성

VPN | PFN | valid bit | protection bit | dirty bit | ASID ...

TLB는 완전 연관 캐시이므로 변환 주소를 찾을 때 TLB의 각 항목을 동시에 검색할 수 있다.
TLB의 valid bit는 TLB에 탑재된 변환 정보가 유효한지를 나타내기 위해 사용한다. 페이지 테이블에서는 할당되지 않은 주소 공간을 표현하는 데 사용했다.
Context Switch의 경우 잘못된 변환을 막기 위해 기존 TLB 내용을 비우는 방식을 사용했지만, 성능에 큰 부담을 준다. TLB 내에 공간 주소 식별자(Address Space Identifier, ASID)필드를 추가하여 프로세스 별로 TLB 변환 정보를 구별하는 기능을 제공한다.

TLB를 도입하여 페이징(Paging)이 사용할 수 있는 가상 메모리 기법이 된다. 여전히 페이지 테이블 크기가 매우 크다는 문제를 남아있다.

3. 페이지 테이블 크기를 줄이는 방법

1) 더 큰 페이지

페이지 크기를 증가시키면 페이지 테이블 크기가 줄어든다.
32비트 주소 공간에서 페이지 크기가 4KB가 아닌 16KB를 가정하자. 기존의 20비트 VPN에서 18비트 VPN으로 줄어든다. 페이지 테이블 크기는 4MB에서 1MB로 줄어든다. (페이지 크기가 4배 증가했으므로 페이지 테이블의 크기는 4배 줄어든다)
페이지 크기의 증가는 페이지 내부의 공간이 낭비되는 내부 단편화(internal fragmentation) 문제가 발생한다.

2) 페이징과 세그먼트

논리 세그먼트마다 페이지 테이블을 두는 방식이다. 세그먼트 하나마다 여러 개의 페이지로 구성되어 있다.
소속 세그먼트를 나타내기 위해 상위 비트를 사용한다. 미사용 세그먼트는 00, 01은 코드, 10은 힙, 스택은 11을 나타낸다고 가정하면 다음과 같이 표현할 수 있다.

SN = (VirtualAddress & SEG_MASK) >> SN_SHIFT
VPN = (VirtualAddress & VPN_MASK) >> VPN_SHIFT
AddressOfPTE = (Base[SN] + (VPN * sizeof(PTE))

segment-table-entry가 segment의 base address를 가지고 있는 것이 아니라 segment를 구성하는 page table의 base address를 가진다.
세그먼트마다 베이스-리밋 레지스터가 따로 존재하므로 스택과 힙 사이에 할당되지 않은 페이지들은 더 이상 공간을 차지하지 않는다.
세그멘테이션은 주소 공간 사용에 있어 특정한 패턴을 가정하기 때문에 유연하지 못하다는 단점이 있다. 또한, 드문드문 사용되는 큰 공간에 대해 일부분만 사용하는 경우에도 모두 물리 메모리에 위치해야 한다는 단점이 있다.

3) 멀티 레벨 페이지

선형 페이지 테이블을 트리 구조로 표현한다. 매우 효율적이기 때문에 많은 현대 시스템에서 사용되는 기법이다.
페이지 테이블을 페이지 크기의 단위로 나눈다. 페이지 테이블의 페이지가 유효하지 않은 항목만 있으면, 해당 페이지를 할당하지 않는다. 페이지 디렉터리(page directory)라는 자료 구조를 사용하여 페이지 테이블 각 페이지의 할당 여부와 위치를 파악한다. 페이지 디렉터리는 페이지 테이블을 구성하는 각 페이지의 존재 여부와 위치 정보를 가지고 있다. 그림으로 나타내면 아래와 같다.
간단한 2단계 페이지 테이블에서 페이지 디렉터리의 각 항목은 페이지 테이블의 한 페이지를 나타낸다. 페이지 디렉터리는 페이지 디렉터리 항목(page directory entries)로 구성된다. 각 항목 PDE의 구성은 PTE와 유사하다. 유효(valid) 비트와 페이지 프레임 번호(PFN)을 갖고 있다. PDE가 유효하다는 것은 그 항목이 가리키고 있는 페이지 들 중 최소한 하나가 유효하다는 것을 의미한다. 선형 페이지 테이블과 2단계 페이지 테이블을 그림으로 나타내면 아래와 같다.
멀티 레벨 페이지 테이블에서 몇 단계로 할 지 정하기 위해서는 먼저 한 페이지에 몇 개의 페이지 테이블 항목을 저장할 수 있는지 계산해야 한다. 예를 들어 페이지 크기가 512바이트이고, PTE가 4바이트라면 한 페이지에 128개( $2^7$ ) PTE를 넣을 수 있다. VPN의 하위 7비트가 필요하다. 주소 공간이 30비트라면 현재까지 VPN( $2^7$ ), offset( $2^9$ ), $2^{14}$ 비트가 남는다. 페이지 디렉터리 자체를 멀티 페이지로 늘려 트리의 단계를 늘릴 수 있다.
구체적인 장점은 아래와 같다.
1. 멀티 레벨 페이지 테이블은 사용된 주소 공간의 크기에 비례하여 페이지 테이블 공간이 할당된다.
2. 각 페이지가 물리 메모리에 산재해 있더라도 페이지 디렉터리를 사용하여 각 페이지 테이블 페이지들의 위치를 파악할 수 있어 공간 할당이 매우 유연하다.
단점도 존재한다. TLB 히트 시의 성능은 비슷하지만 TLB 미스 시 총 세 번의 메모리 참조가 발생한다. (페이지 디렉터리 접근, PTE 접근, 실제 명령어 주소 접근) 또한, 다른 방법보다 복잡하다.

4) 역 페이지 테이블

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True)		// TLB 히트
	if (CanAccess(TlbEntry.ProtectBits) == True)
    	Offset = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        AccessMemory(PhysAddr)
    else
    	RaiseException(PROTECTION_FAULT)
else						// TLB 미스
	// 먼저 페이디 디렉터리 항목을 얻어야 함
    PDIndex = (VPN & PD_MASK) >> PD_SHIFT
    PDEAddr = PDBR + (PDIndex * sizeof(PDE))
    PDE = AccessMemory(PDEAddr)
    if (PDE.Valid == False)
		RaiseException(SEGMENTATION_FAULT)
	else
    	// PDE가 유효함: 이제 페이지 테이블에서 PTE를 가져온다
        PTIndex = (VPN & PT_MASK) >> PT_SHIFT
        PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))
        if (PTE.Valid == False)
        	RaiseException(SEGMENTATION_FAULT)
        else if (CanAccess(PTE.ProtectBits) == False)
        	RaiseException(PROTECTION_FAULT)
        else
    		TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
        	RetryInstruction()

페이지 테이블은 물리 페이지를 가상 주소 상의 페이지로 변환한다. 역 페이지 테이블의 각 항목은 해당 물리페이지를 사용 중인 프로세스 번호, 해당 가상 페이지 번호를 갖고 있다.
테이블 전체를 탐색해야 하므로 associative register를 사용하여 검색 속도를 증가시킨다.

4. 실제 가상 메모리 시스템(VAX/VMX)

1970년도 말 개발된 VAX/VMX 아키텍처는 복잡한 현대 운영체제에서도 일정 부분 유사성을 가진다. 당시 하드웨어 결함에도 시스템이 효과적으로 작동하기 위해 VAX/VMX가 사용한 기법들을 알아본다.

1) 메모리 관리 하드웨어

프로세스마다 512바이트 페이지 단위로 나누어진 32비트 가상 주소 공간을 제공한다. 가상 주소는 23비트 VPN과 9비트 offset으로 구성되어 있다.
페이지 테이블로 인한 메모리 소진을 막기 위해 사용자 주소 공간을 두 개의 세그먼트로 나누어 프로세스마다 각 영역을 위한 페이지 테이블을 가지도록 하였다. 스택과 힙 사이의 사이의 사용되지 않은 공간을 할당하지 않아도 된다.
운영체제는 사용자 페이지 테이블을 커널의 가상 메모리에 배치하여 메모리 압박을 더 줄인다. 이는 다수의 프로세스 간 공통 정보를 쉽게 공유할 수 있으며 메모리가 부족할 때 공간을 직접 할당하거나 스왑 아웃, 스왑 인 방식으로 메모리를 효율적으로 사용할 수 있다. 하지만, 커널 가상 메모리에 페이지 테이블을 두면 주소 변환 과정에 오버헤드가 있다. 커널 가상 주소에 접근하기 위해 사용자 가상 주소 이용한 추가적인 변환 과정이 필요하기 때문이다. 하지만 TLB에서 대부분 처리된다면 크게 문제가 되지 않는다.

2) 실제 주소 공간

실제 주소 공간의 구축 상황을 볼 수 있다. 코드 세그먼트는 절대로 0에서 시작하지 않는다. 0번지 주소는 접근 불가능한 페이지로 마킹되어 널 포인터 접근을 쉽게 검출할 수 있게 한다.
중요한 건 커널의 가상 주소 공간이 사용자 주소 공간의 일부라는 점이다. 몇 가지 이유를 살펴보자.
1. 이는 프로세스가 시스템 콜을 호출할 때 커널이 해당 프로세스 문맥에서 직접 실행될 수 있게 한다. (운영체제는 접근하는 데이터가 어디에서 오는지 고려할 필요 없이 자연스럽게 작성되고 컴파일 된다)
2. 커널이 자체 주소 공간을 가진다면 사용자 프로그램들과 커널 간의 데이터 이동이 매우 복잡하고 고통스러운 일이 된다. 커널은 보호된 영역이지만, 응용 프로그램에 마치 라이브러리처럼 보이는 것이다.

3) 가상 메모리 기법

(1) 세그먼트된 FIFO

VMS는 reference bit가 없다. 어떤 페이지가 자주 사용 중인지를 하드웨어 지원 없이 판단할 수 있어야 한다. 이를 위해 세그먼트된 FIFO 교체 정책을 이용한다. 각 프로세스는 상주 집합 크기(resident set size, RSS)라고 불리는 메모리에 유지할 수 있는 최대 페이지 개수를 지정 받는다. 페이지 개수가 RSS보다 커지면 제일 먼저 들어왔던 페이지가 쫓겨난다.
FIFO의 성능을 개선하기 위해 VMS는 전역 클린-페이지 프리 리스트(global clean-page free list)와 더티 페이지 리스트(dirty page lsit)라고 하는 두 개의 second-chance list를 도입하였다.
프로세스 P가 자신의 RSS를 넘긴다면 자신의 FIFO에서 페이지가 제거된다. 제거된 페이지가 클린(수정이 안된)상태라면 클린 페이지 리스트에, 더시 상태라면 더티 페이지 리스트에 추가된다. 다른 프로세스 Q에 빈 페이지가 필요하면 전역 클린 리스트에서 첫 번째 페이즈를 꺼낸다. 원래의 페이지가 해당 페이지가 회수 되기 전에 그 페이지에 대해 폴트를 발생시키면 P는 프리 리스트에서 페이지를 가져가서 다시 사용한다. second-chance list의 크기가 클수록 세그먼트된 FIFO 알고리즘은 LRU처럼 동작한다.

(2) 페이지 클러스터링

VMS의 작은 페이지 크기를 극복할 수 있게 해준다. 페이지 크기가 적을수록 디스크 I/O는 비효율적이다. 클러스터링 기법을 사용하여 전역 더티 리스트에 있는 페이지들을 작업 묶음을 만들어 한 번에 디스크로 보낸다.

(3) demand zeroing

힙에 페이지를 추가하는 요청이 오면 물리 메모리에서 페이지를 찾아 0으로 채워 주소 공간에 페이지를 매핑한다. 이렇게 하지 않으면 다른 프로세스가 이전에 사용했던 정보를 볼 수 있게 된다.
페이지가 주소 공간에 추가되는 시점에는 거의 하는 일이 없다. 페이지 테이블에 접근 불가능 페이지라고 표기하고 항목을 추가한다. 프로세스가 추가된 페이지를 읽거나 쓸 때 운영체제로 트랩이 발생한다. (지연 처리로 성능 개선)

(4) 쓰기 시 복사(copy-on-write)

운영체제가 한 주소 공간에서 다른 공간으로 페이지를 복사할 필요가 있을 때, 복사를 하지 않고 해당 페이지를 대상 주소 공간으로 매핑한다. 해당 페이지의 PTE를 양쪽 주소 공간에서 읽기 전용으로 표시한다. 만약 양쪽 주소 공간이 페이지를 읽기만 한다면 더 이상의 조치는 필요 없고, 운영체제는 실제로 데이터의 이동 없이 빠른 복사를 할 수 있다.
두 주소 공간 중 하나가 페이지 쓰기를 시작하면 운영체제로 트랩이 발생한다. 운영체제는 그때 해당 페이지가 COW 페이지라는 것을 파악한다. 그런 후 새로운 페이지를 할당하고 데이터를 채워 주소 공간에 매핑한다.

참고 자료

2014 이화여대 반효경 운영체제 강의
운영체제, 아주 쉬운 세 가지 이야기

junto

꾸준하게

이전 포스트

가상 메모리, 세그먼테이션(Segmentation) [2 / 4]

다음 포스트

가상 메모리, 페이징(Paging) [3 / 4]

operating system

1. 페이징(Paging)

1) 동작 방법

2) 페이지 테이블

(1) Valid bit

(2) Protected bit

(3) Presented bit

(4) Dirty bit

(5) Reference bit (또는 Access bit)

3) 단점

(1) 두 번의 메모리 참조

(2) 매우 큰 페이지 테이블

2. TLB(Translation-Lookaside Buffer)

1) 동작 방법 (하드웨어 처리 방식)

2) TLB 미스 처리주체

(1) 하드웨어

(2) 운영체제

3) 구성

3. 페이지 테이블 크기를 줄이는 방법

1) 더 큰 페이지

2) 페이징과 세그먼트

3) 멀티 레벨 페이지

4) 역 페이지 테이블

4. 실제 가상 메모리 시스템(VAX/VMX)

1) 메모리 관리 하드웨어

2) 실제 주소 공간

3) 가상 메모리 기법

(1) 세그먼트된 FIFO

(2) 페이지 클러스터링

(3) demand zeroing

(4) 쓰기 시 복사(copy-on-write)

참고 자료

가상 메모리, 세그먼테이션(Segmentation) [2 / 4]

가상 메모리, 페이지 교체 [4 / 4]

0개의 댓글