이전 포스팅에서 연속 할당에 대해 살펴보았습니다. 연속 할당 방법은 프로그램이 메모리에 올라갈 때 통째로 메모리에 올라가는 방식입니다. 각각의 프로세스가 메모리의 연속적인 공간에 적재됩니다.
반면 불연속 할당은 프로그램을 구성하는 주소 공간을 같은 크기의 단위(페이지)로 잘개 쪼개서 페이지 단위로 메모리에 올리는 방식입니다. 즉 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있습니다.
불연속 할당에는 Paging 기법과 Segmentation기법, Page Segmentation기법 등이 있습니다.
이번 포스팅에서는 불연속 할당의 Paging 기법에 대해 살펴보겠습니다.
1. Paging
(1) Paging 기법이란?
Paging 기법은 프로그램을 구성하는 논리적 메모리(가상 메모리)를 동일한 사이즈의 page 단위로 나누어, 각각의 페이지 별로 물리적인 메모리에 올리는 것입니다. 물리적 메모리에 올릴 때에도 페이지 일부는 backing store에, 일부는 물리적 메모리에 올릴 수 있고 페이지 단위로 불연속적으로 올라갈 수 있습니다.
이때, 물리적 메모리도 page와 동일한 크기의 frame으로 나누어 놓게 됩니다. 이렇게 하면 hole의 크기가 일정하지 않아서 생기는 문제에 대한 대안으로 어떤 hole에 집어 넣을지에 대한 알고리즘이나, hole을 한 곳으로 모으는 compaction과 같은 방법이 필요가 없는 장점이 있습니다.
대신, 주소 변환에서는 연속 할당에서 쓰였던 방법처럼 시작 주소만 더하는 것이 불가능합니다. Paging 기법에서는 주소 변환도 Page 단위로 이루어지게 됩니다. 그래서 이전 포스팅에서 살펴보았던 주소 변환을 위한 두 개의 레지스터(Relocation register, Limit register)로는 주소 변환이 불가능합니다.
(2) Page table
그래서 주소 변환을 위해 Page table이 사용됩니다. page table은 각각의 논리적인 페이지가 물리적인 메모리의 어디에 위치해있는지를 저장한 일종의 배열 구조입니다. 그래서 index를 이용해 바로 접근이 가능한 자료 구조입니다.
Page table에는 논리적 메모리 page의 개수만큼 entry가 존재하는데, 각각의 table의 entry에는 그 페이지가 몇 번째 물리적 frame에 올라가 있는지 저장되어있습니다. Entry의 크기가 정해져 있어 주소 변환을 위해 테이블을 순차적으로 탐색하는 것이 아니라, 페이지 테이블에서 n번째 entry를 찾아 그 페이지가 몇 번째 frame에 위치하는지 알 수 있게 됩니다.
Implementation of Page Table
그럼 이 Page Table은 어디에 위치할까요? Page table은 Main memory에 상주합니다.
연속 할당에서 다루었던 MMU 기법에서는 Register 두 개로 주소 변환을 하고, Register는 CPU안에 들어 있습니다. 하지만 불연속 할당에서의 Page Table은 CPU의 레지스터에 들어가기엔 용량이 큽니다. 주소 공간을 나눈 Page 단위는 하나에 보통 4KB이고, 실제 프로그램을 위해서는 이 entry가 100만 개 정도 필요합니다.
그리고 이 page table은 각 프로그램마다 존재하기 때문에 이렇게 많은 양의 entry가 레지스터나 캐시메모리에 넣기는 어렵습니다. 그리고 메모리 접근에 쓰이는 주소 변환이기 때문에 하드디스크 같은 공간에도 저장할 수 없습니다.
그래서 데이터 접근하기 위해서는 메모리에 두 번 접근해야하는 상황이 생깁니다. 주소 변환을 위해 메모리의 Page Table에 접근이 필요하고, 주소 변환 이후에 실제 데이터에 접근하기 위해 메모리에 다시 접근해야합니다.
TLB
이전에 살펴보았던 포스팅에서는 기본적으로 두 개의 레지스터 Base Register와 Limit Register가 있었습니다. 이 두 개의 레지스터는 Paging 기법에서 Page Table Base Register와 Page Table Length Register로 사용됩니다.
Page Table Base Register(PTBR)은 메모리 상에 Page Table이 어디에 있는지 그 시작 위치를 갖고 있고,Page Table Length Register(PRLR)은 Page Table의 길이를 가지고 있습니다.
즉, 기존의 주소 변환을 하던 Base Register와 Limit Register를, 페이징 기법에서는 Table의 Base값과 Limit값을 갖고 있는 용도로 사용하는 것입니다.
데이터에 접근하기 위해 메모리에 두 번 접근하는 것은 시간이 두 배로 걸리기 때문에 비용이 큽니다. 그래서 속도 향상을 위해 별도의 하드웨어인 Associative Register(TLB : Translation look-aside buffer)라 불리는 캐시를 사용합니다.
메인 메모리에서 빈번하게 사용되는 데이터를 캐시 메모리에 저장해 CPU에게 빨리 접근할 수 있는 캐시메모리처럼, 메모리 주소 변환을 위해 별도의 캐시를 두고 있는 것이 TLB 계층입니다. TLB는 Page Table에서 자주 참조되는 일부 Entry를 캐싱하고 있고, 메인 메모리보다 접근 속도가 빠른 하드웨어로 구성되어 있습니다.
아래 그림은 TLB를 통한 페이징 과정입니다.
CPU가 논리적 주소를 주면 메모리 상에 있는 Page Table에 접근하기 전 TLB를 먼저 검색하게 됩니다. TLB에 저장된 정보를 통해 주소 변환이 가능한지를 체크하는 것입니다. 만약 p에 해당하는 entry가 TLB에 이미 저장되어있다면 TLB를 통해 바로 주소 변환이 이루어 집니다. 그렇게 되면 주소 변환을 한 채로 물리적 메모리에 접근하기 때문에 메모리에 한번만 접근하면 되는 것입니다. TLB가 없는 경우에는 TLB miss가 발생했다고 표현합니다. 이 경우에는 Page Table을 통해 일반적인 주소 변환으로 메모리에 접근합니다.
TLB가 Page Table과 다른 주요한 차이점이 몇가지 있습니다.
우선, TLB는 Page Table 정보 전체를 갖고 있는 것이 아니라, 일부만 갖고 있습니다.
그리고 TLB는 논리적 페이지 번호 p와 p에 대한 주소 변환된 프레임 번호 f를 쌍으로 갖고 있습니다. 주소 변환을 할 때, Page Table에서 페이지 번호가 p인 곳을 TLB에서 찾을 때는, p번째 entry를 가면 f라는 Page frame이 저장되어 있는 것입니다. 주소 변환을 위해 TLB에서 특정 항목을 검색하는 것이 아니라, Table 전체를 검색해야합니다. 그래서 시간이 오래 걸리는 문제가 생기고 이를 해결하기 위해서 parallel search가 가능한 Associate Register를 이용해 구현합니다.
또, 프로세스마다 각각의 논리적 주소 체계가 다르고, 이것에 대해서 주소 변환을 위한 Page table은 각각의 프로세스마다 존재합니다. 그래서 TLB도 프로세스마다 다른 정보가 저장됩니다. CPU가 다른 프로세스로 넘어가면, 페이지에 대한 주소 정보도 달라지게 됩니다. 그래서 Context Switching이 일어나면 TLB Flush를 시켜 모든 Entry를 비워주어야 합니다.
(3) Two-Level Page table
Two-level Page Table은 메모리를 페이지 단위로 나누고, 각 페이지에 대한 페이지 테이블을 사용하는 것입니다. 다시 말해, 전역(바깥쪽) 페이지 테이블과 지역(안쪽) 페이지 테이블의 두 단계 테이블을 사용합니다.
Two-level Page Table은 공간을 줄이기 위해 사용됩니다. 좀 더 구체적으로 설명드리자면 컴퓨터 시스템의 메모리에 대해 살펴보아야합니다.
현대 컴퓨터 시스템에서 각 프로그램의 크기는 실제 물리적 메모리의 크기와는 독립적입니다. 실제 메모리의 크기가 클수록 더 많은 내용이 메모리에 올라가기 때문에 성능이 좋지만, 페이징 기법에서는 어차피 페이지 단위로 메모리가 나뉘어 올라가기 때문에 논리적 메모리가 물리적 메모리보다 크더라도 실행에 문제는 없습니다.
현대 컴퓨터에서는 메모리 주소 체계가 굉장히 큰데, 32비트 주소를 사용하고 최근에는 64비트 주소 체계를 사용합니다. 예를 들어, 32비트 주소 체계는 4GB(2^32)를 표시할 수 있습니다. 이를 페이지 단위로 쪼개면 각 페이지는 4KB이고 총 100만 개의 테이블 엔트리가 필요합니다. 이 페이지 테이블 엔트리를 메모리에 저장해야하지만, 각 프로그램마다 페이지 테이블을 메모리에 다 저장한다면 메모리 공간이 크게 낭비됩니다. 이런 공간 낭비를 줄이기 위해 2단계 페이지 테이블을 사용하는 것입니다.
Two-level Page Table에서는 메모리 주소를 페이지 번호와 페이지 오프셋으로 나눕니다.
페이지 번호는 전체 주소 공간을 페이지 크기로 나누어 얻은 값이고, 이를 통해 전역 페이지 테이블에서 해당 페이지의 위치를 찾습니다. 그 후 해당 페이지의 페이지 테이블을 메모리에 가져와 지역 페이지 테이블에서 페이지 오프셋을 사용해 실제 물리적 주소를 찾습니다.
Address-Translation Scheme
Two-level Page Table에서 기억할 것은 지역 페이지 테이블의 크기가 페이지의 크기와 똑같다는 것입니다. 안쪽 페이지 테이블은 테이블 자체가 페이지화 되어있어서 페이지 어딘가에 들어가있게 됩니다. 보통 안쪽 페이지 테이블 하나의 크기는 페이지 테이블과 같은 4KB입니다. 각 entry의 크기는 4바이트이고, 엔트리 개수는 1KB입니다.
32비트 주소 체계에서는 page offset과 p1, p2가 각각 몇 비트로 표현되어야 하는지 계산할 수 있는데, 먼저 비트 수를 알기 위해 제일 안쪽부터 차례로 올라가면 됩니다. 페이지 하나의 크기가 4KB이기 때문에 byte 단위로 주소 구분을 하려면 12bit가 필요합니다. 따라서 page offset은 12bit로 표현됩니다.
이제 32비트에서 남은 20비트를 p1, p2에 나누어야합니다. 지역 페이지 테이블에서는 서로 다른 2^10가지 엔트리 위치를 구분하기 위해 10비트가 필요합니다. 그래서 지역 테이블의 크기는 10비트, 전역 테이블의 크기는 10비트가 됩니다.
Effective Access Time
실제로 메모리에 접근하는 시간을 계산해볼 수 있습니다. 메인 메모리에 접근하는 시간을 1이라고 가정해보겠습니다. 그럼 TLB에 접근하는 시간(입실론, ε )은 1보다 작습니다. 그리고 TLB로부터 주소 변환 정보가 찾아지는 비율(hit rate)을 알파(α) 라고 하겠습니다.
알파(α) 의 비율만큼 TLB에 접근하는 입실론에 메인 메모리에 접근하는 시간 1을 더한 시간을 곱한만큼 걸리고, 주소 변환 정보가 없는 비율인 (1-α )와 메모리에 두 번 접근하는 시간 2에 TLB에 접근하는 시간을 더한 값을 곱해주면 Miss Time 이 나오게 됩니다.
여기서 α 는 hit time , 1-α 는 miss time입니다. 실제로는 α의 값이 굉장히 높고 입실론(ε) 값은 매우 작습니다.
(4) Muti-Level Paging
페이지 테이블은 다단계로도 사용할 수 있습니다. 예를 들어 4단계 페이지 테이블을 사용한다고 가정해보겠습니다. 메모리에 한 번 접근하기 위해서는 4번의 주소 변환과 1번의 실제 테이터 접근이 필요합니다. 만약 TLB 없이 메모리에 접근한다면 5배의 접근 시간이 걸리는 것입니다.
하지만 주소 변환을 전담해주는 TLB를 통해 직접 이루어지기 때문에, 다단계 페이지 테이블을 사용하더라도 시간 소모가 그렇게 크지는 않습니다.
만약 TLB Hit rate가 98%, ε(메모리 접근 시간)은 100ns, α(TLB 접근 시간)는 20ns 라고 한다면, 0.98*(100+20)+0.02*(500+20)으로, 총 128ns가 걸립니다. 메모리 접근 시간이 100ns에 비해 주소 변환을 위해 결과적으로 28ns만 추가 된 것입니다.
참고자료
[KOCW 이화여대 반효경 교수님 - Memory Management 2]
https://core.ewha.ac.kr/publicview/C0101020140429132440045277?vmode=f
반효경 [운영체제] 19. Memory Management 2
설명이 없습니다.
core.ewha.ac.kr
[ Operating System Concepts - Abraham Silberschatz ]
https://www.yes24.com/Product/Goods/89496122
운영체제 - 예스24
운영체제
www.yes24.com
