23 페이징 : 더작은테이블 페이징의두번째문제점은페이지테이블의크기이다. 페이지테이블이크면많은 메모리공간을차지한다. 배열형태를가지는선형페이지테이블 (linear page table) 을예로들어보자. 전술한바와같이 1 선형페이지테이블은상당히커질수가있다. 페이지크기가 4 KB(2 12 바이트 ) 이고, 페이지테이블의각항목은 4 바이트인 32 비트 주소공간 (2 32 바이트 ) 을가정해보자. 주소공간에는대략백만서 ( 232 2 12 ) 의가상페이지가존재할것이다. 여기에페이지테이블항목의크기를곱하면 (4 바이트 x 백만서 ), 페이지 테이블의크기가된다. 하나의페이지테이블크기가약 4 MB 가된다. 또하나잊으면 안되는사실이있다! 일반적으로각프로세스는자기자신의페이지테이블을갖는다. 백서의프로세스가실행중이라면 ( 현대시스템에 드물지않다 ), 페이지테이블이 100 서존재하며, 400 MByte 의메모리가필요하다. 이런 청난메모리부담을해결할수 있는기술을모색해보자. 다양한해법들이존재한다. 핵심질문은아래와같이요약될 수있다. 핵심질문 : 페이지테이블을어떻게더작게만들까단순한배열기반의페이지테이블은 ( 흔히선형페이지테이블이라고불림 ) 크기가크며일반적인시스템에 메모리를과도하게차지한다. 어떻게페이지테이블의크기를줄일수있을까? 주요서념들로는무 이있는가? 새로운자료구조들은어떤비효율성을갖는가? 23.1 간단한해법 : 더큰페이지페이지테이블의크기를간단하게줄일수있는방법이한가지있다. 페이지크기를증가시키면된다. 32비트주소공간에, 이번에는 16 KB 페이지를가정해보자. 이제는 18비트의 VPN과 14비트의오프셋을갖게된다. 각 PTE (4바이트) 의크기가모두 1) 기억못할수도있다. 페이징이라는것이통제가잘안되지않는가? 해법을찾아보기전에문제가무 인지제대로이해하고있는지확인을해야한다. 문제를이해하면스스로해법도유도해낼수가있다. 여기 다루는문제는명확하다. 간단한선형 ( 배열기반의 ) 페이지테이블은너무크다는것이다.
제 23 장페이징 : 더작은테이블 여담 : 멀티페이지크기많은컴퓨터구조들 ( 예, MIPS, SPARC, x86-64) 이멀티크기페이지를지원한다는것을기억하자. 일반적으로, 작은 (4 KB 또는 8 KB) 페이지크기가사용된다. 하지만, 만약 똑똑한 응용프로그램이페이지를요청할경우, 가상주소공간의특정부분을대형페이지 ( 예, 4 MB 의크기 ) 에할당하고, 그프로그램이자주사용되는대형자료구조를해당페이지에위치시키는것을가능케할수있다. 대형페이지를사용하므로 TLB 에 하나의항목만사용한다. 이러한대형페이지는데이터베이스관리시스템과고성능프로그램에 흔히사용된다. 멀티페이지크기를사용하는주요이유는페이지테이블의공간을절약하려는것은아니다. TLB 미스를줄이면 프로그램이주소공간을접근할수있도록하기위해 이다. 그러나연구진들이발표한것과같이 [Nav+02], 하드웨어가다수의페이지크기를지원할경우, 운영체제의가상메모리관리모듈이매우복잡해진다. 대형페이지를간단히사용하는방법으로, 추가인터페이스를정의하여, 응용프로그램이대형페이지를직접요청할수있도록할수있다. 동일하다면, 페이지테이블에 2 18 서의항목이있으며, 페이지테이블의총크기는 1 MB 가된다. 기존페이지테이블대비크기가 1/4로감소된다 ( 당연하다. 테이블의크기가 1/4로감소한것은페이지크기가정확히 4배증가했기때문이다 ). 페이지크기의증가는부작용을수반한다. 가장큰문제는페이지내부의낭비공간이증가하는것이다. 이를내부단편화 (internal fragmentation) 라한다 ( 할당된페이지내부에 낭비가발생하기때문이다 ). 응용프로그램이여러페이지를할당받았지만, 할당받은페이지의일부분만사용하는터에, 결국컴퓨터시스템의메모리가금방고레되는현상이발생한다. 이런연유에, 많은컴퓨터시스템들이비교적작은페이지들을사용한다. 일반적으로 4 KB (x86) 또는 8 KB (SPARCv9) 를사용한다. 페이지테이블크기를감소시키는우리의당면문제는그리쉽게해결되지않을것이다. 23.2 하이브리드접근방법 : 페이징과세그멘트인생의어떤일을함에있어좋은방법이두가지있다면, 그두방법을잘조합하여, 장점만을취할수는 는지도검토해보아야한다. 두가지방법을조합하는것을하이브리드 (hybrid) 라고부른다. 예를들면, 초콜릿과피넛버터를 어만든 Reese 사의 Peanut Butter Cup [M28] 이있는데, 사람들은왜피넛버터와초콜릿중하나만먹을까? 2 Multics의창시자 Jack Dennis는 Multics 가상메모리시스템을구축하는데있어, 비슷한아이디어가떠올랐다 [M07]. Dennis는페이징과세그멘테이션을결합하여페이지테이블크기를줄이는아이디어를내 다. 선형페이지테이블의동작을면밀히분 해보면, 페이징과세그멘테이션을효과적으로결합할수있다는사실을발견할수있다. 힙과스택에 실제로전체공간중작은부분만사용되는경우를생각해보자. 2) 역자주 : 체중이불기는하겠다. 2 운영체제 : 아주쉬운세가지이야기 [V.0.90]
23.2 하이브리드접근방법 : 페이징과세그멘트 그림 23.1 1 KB 페이지들로이루어진 16 KB 주소공간 PFN valid prot present dirty 10 1 r-x 1 0 23 1 rw- 1 1 28 1 rw- 1 1 4 1 rw- 1 1 그림 23.2 16 KB 주소공간을위한페이지테이블 1 KB 크기의페이지를갖는 16 KB의주소공간을예로들겠다 ( 그림 23.1). 이주소공간을위한페이지테이블은그림 23.2에나타나있다. 이예제에 한서의코드페이지 (VPN 0) 가물리페이지 10번, 그리고한서의힙페이지 (VPN 4) 가 23번물리페이지에매핑되어있다. 가상주소공간의끝부분에두서의스택페이지 (VPN 14와 15) 가물리페이지 28번과 4번에매핑되어있다. 그림에 보는바와같이, 페이지테이블대부분이비어있다. 청난낭비가발생한다. 16 KB 크기의아주작은주소공간에 발생한상황이다. 32비트주소공간용페이지테이블에 비슷한상황이발생할것을상상해보자. 골치아픈일이다. 결합방식을생각해보자. 프로세스의전체주소공간을위해하나의페이지테이블을두는대신, 논리세그멘트마다따로페이지테이블을두면어떨까? 이예제에 는세서의페이지테이블이있을수있다. 코드, 힙그리고스택세그멘트에대해페이지테이블을각각두는것이다. 원유집, 박민규, 이성진역 ; www.ostep.org 3
제 23 장페이징 : 더작은테이블 세그멘테이션에 는세그멘트의물리주소시작위치를나타내는베이스 (base) 지스터, 그리고크기를나타내는바운드 (bound) 또는리미트 (limit) 지스터가있다. 우리의결합방식에 도 MMU에비슷한구조를사용한다. 베이스 지스터는세그멘트시작주소를가리키는것이아니라세그멘트의페이지테이블의시작주소를갖는다. 바운드 지스터는페이지테이블의끝을나타내기위해 사용한다. 명확하게하기위해간단한예를들어보자. 4 KB 페이지를갖는 32비트가상주소공간이 4서의세그멘트로나뉘어있다고가정하자. 이예제에 는세서의세그멘트만사용하도록하겠다. 하나는코드를위해, 다른하나는힙을위해 그리고또하나는스택을위해 사용한다. 소속세그멘트를나타내기위해상위두비트를사용한다. 미사용세그멘트는 00 으로, 01은코드를그리고 10은힙, 스택은 11을나타낸다고가정하자. 가상주소는다음과같이표현될수있다. 하드웨어에세서의베이스 / 바운드 지스터쌍이코드와힙그리고스택을위해 존재한다고가정한다. 실행중인프로세스에, 각세그멘트의베이스 지스터는각세그멘트페이지테이블의시작물리주소를갖게된다. 이시스템에 모든프로세스들은세서의페이지테이블을갖는다. 문맥교환시, 이 지스터들은새로실행되는프로세스의페이지테이블의위치값으로변경된다. TLB 미스가발생하면 ( 하드웨어기반 TLB를가정한다. 즉, TLB 미스를하드웨어가처리한다 ), 하드웨어는세그멘트비트 (SN) 을사용하여어떤베이스와바운드쌍을사용할지결정한다. 하드웨어는그 지스터에들어있는물리주소를 VPN과다음과같은형식으로조작하여페이지테이블항목 (PTE) 의주소를얻는다. SN = (VirtualAddress & SEG_MASK) >> SN_SHIFT VPN = (VirtualAddress & VPN_MASK) >> VPN_SHIFT AddressOfPTE = Base[SN] + (VPN * sizeof(pte)) 동작순 가눈에익숙하다. 앞에 살펴보았던선형페이지테이블의작동과거의동일하다. 유일한차이가있다면하나의페이지테이블베이스 지스터를사용하는대신세서중의하나의세그멘트베이스 지스터를사용하는것이다. 하이브리드기법에 핵심은세그멘트마다바운드 지스터가따로존재한다는것이다. 각바운드 지스터의값은세그멘트의최대유효페이지의서수를나타낸다. 예를들어, 첫세서의페이지들 (0, 1, 그리고 2) 을코드세그멘트로 사용중이라면, 코드세그멘트페이지테이블은세서의항목만할당을받을수있을것이고바운드 지스터는 3으로설정된다. 해당세그멘트의범위가넘어가는곳에대한메모리접근은예외를발생시키고, 해당프로세스는종료될것이다. 이와같은방식으로, 하이브리드기법은선형페이지테이블에비해메모리사용을서선시킬수있다. 스택과힙사이의할당되지않은페이지들은페이지테이블상에 ( 유효하지않다는것을표시하기위해 ) 더이상공간을차지하지않는다. 4 운영체제 : 아주쉬운세가지이야기 [V.0.90]
23.3 멀티 벨페이지테이블 팁 : 하이브리드를사용하자두서의괜찮은그리고상반되는아이디어가있다면, 두방식의장점을모두가져레수있도록두방식을혼합하는하이브리드를만들수있는지늘살펴보아야한다. 하이브리드옥수수종을예로들면자연적으로자라나는종에비해좀더강인하다고알려져있다. 물론, 모든하이브리드기법들이좋은아이디어는아니다. 지돈크 (Zeedonk), 또는존키 (Zonkey) 는얼룩말과당나귀사이에 태어난동물이다. 그런생물이존재하는지믿지못하겠다면찾아보자. 놀랄것이다. 하지만, 이기법역시문제가 는것은아니다. 첫째, 여전히세그멘테이션을사용해야한다 ; 이전에언급했듯이, 세그멘테이션은주소공간의사용에있어특정패턴을가정하기때문에우리가원하는만큼은유연하지가못하다. 큰공간을커버하지만, 드문드문사용되는 (sparsely used) 힙의경우에는여전히페이지테이블의낭비를면치못할수가있다. 둘째로, 하이브리드기법은외부단편화를유발한다. 하이브리드방식에 는페이지테이블크기에제한이 으며다양한크기를갖는다. 물론, 페이지테이블의크기는페이지테이블항목크기의정수배가되어야한다. 때문에, 메모리상에 페이지테이블용공간을확보하는것이더복잡하다. 이런이유로, 페이지테이블크기를감소시키는더나은방법을찾는노력들이지속되 다. 23.3 멀티레벨페이지테이블세그멘테이션을사용하지않고페이지테이블크기를줄이는방법에대해 생각해보자. 어떻게하면사용하지않는주소공간을페이지테이블에 제거할수있을까? 이번에소서할기법은멀티레벨페이지테이블이다. 멀티레벨페이지테이블에 는선형페이지테이블을트리구조로표현한다. 매우효율적이기때문에많은현대시스템에 사용되고있다 ( 예, x86 [BO10]). 이기법을좀더상세히설명하도록하겠다. 멀티 벨페이지테이블의기본서념은간단하다. 먼저, 페이지테이블을페이지크기의단위로나눈다. 그다음, 페이지테이블의페이지가유효하지않은항목만있으면, 해당페이지를할당하지않는다. 페이지디렉터리 (page directory) 라는자료구조를사용하여페이지테이블각페이지의할당여부와위치를파악한다. 페이지디 터리는페이지테이블을구성하는각페이지의존재여부와위치정보를가지고있다. 그림 23.3의예제를보자. 좌측그림은전형적인선형페이지테이블이다. 페이지테이블의중앙부에해당하는주소공간은사용되고있지않다. 그러나페이지테이블에 항목들이할당되어있다 ( 페이지테이블의가운데두페이지 ). 우측은동일한주소공간을다루는멀티 벨페이지테이블이다. 페이지디 터리에는두서의유효한페이지가있다 ( 첫번째와마지막 ). 유효페이지두서는메모리에존재한다. 이예를통해멀티 벨페이지테이블의동작을좀더쉽게알수있다. 선형페이지테이블에 사용되 던페이지들이더이상필요 고, 페이지디 터리를이용하여페이지테이블의어떤페이지들이할당되 는지를관리한다. 원유집, 박민규, 이성진역 ; www.ostep.org 5
제 23 장페이징 : 더작은테이블 그림 23.3 선형 ( 좌 ) 그리고멀티레벨 ( 우 ) 페이지테이블간단한 2단계테이블에, 페이지디 터리의각항목은페이지테이블의한페이지를나타낸다. 페이지디 터리는페이지디렉터리항목 (page directory entries, PDE) 들로구성된다. 각항목 (PDE) 의구성은페이지테이블의각항목 (Page Table Entry) 과유사하다. 유효 (valid) 비트와페이지프레임번호 (page frame number, PFN) 를갖고있다. 실제구현에따라추가구성요소가존재할수있다. 하지만, PTE 의유효비트와 PDE의유효비트는약간다르다. PDE 항목이유효하다는것은, 그항목이가리키고있는 (PFN을통해 ) 페이지들중최소한하나가유효하다는것을의미한다. 즉, PDE가가리키고있는페이지내의최소한하나의 PTE의 valid bit가 1 로설정되어있다. 만약 PDE의항목이유효하지않다면 ( 즉, 0이라면 ), PDE는실제페이지가할당되어있지않은것이다. 멀티 벨페이지테이블은이제까지언급된다른기법들에비해몇가지장점이있다. 첫째, 멀티 벨테이블은사용된주소공간의크기에비례하여페이지테이블공간이할당된다. 그 기때문에, 보다작은크기의페이지테이블로주소공간을표현할수있다. 두번째, 페이지테이블을페이지크기로분할함으로써메모리관리가매우용이하다. 페이지테이블을할당하거나확장할때, 운영체제는 free 페이지풀에있는빈페이지를가져다쓰면된다. 멀티 벨페이징을단순한선형페이지테이블방식과비교해보자. 선형페이지테이블의각항목은해당가상페이지의물리페이지주소를가지고있다 ( 즉, 디스크로스왑되지않는다 ). 선형페이지테이블은연속된물리메모리공간을차지한다. 큰페이지테이블 (4 MB라고하자 ) 의경우, 해당크기의연속된빈물리메모리를찾는것이쉽지않다. 멀티 벨페이징에 는페이지디 터리를사용하여각페이지테이블페이지들의위치를파악한다. 페이지테이블의각페이지들이물리메모리에산재해있더라도페이지디 터리를이용하여그위치를파악할수있으므로, 페이지테이블을위한공간할당이매우유연하다. 6 운영체제 : 아주쉬운세가지이야기 [V.0.90]
23.3 멀티 벨페이지테이블 팁 : 시간과공간간의절충점에대해이해하자자료구조설계시, 구현에 시간과공간의소요시간을적절히절충 (time-spacetrade-ofs) 해야한다. 일반적으로자료구조에접근속도를향상시키려면, 해당구조를위해공간을더사용해야한다. 한가지유의해야할사항이있다. 멀티 벨테이블에는추가비용이발생한다. TLB 미스시, 주소변환을위해두번의메모리로드가발생한다 ( 페이지디 터리와 PTE 접근을위해각각한번씩 ). 선형페이지테이블에 는한번의접근만으로주소정보를 TLB로탑재한다. 멀티 벨테이블은시간 ( 페이지테이블접근시간 ) 과공간 ( 페이지테이블공간 ) 을상호절충 (time-space-trade-ofs) 한예라할수있다. 페이지테이블크기를줄이는데성공하였으나, 대신메모리접근시간이증가했다. TLB 히트시 ( 대부분메모리접근은 TLB 히트이다 ) 성능은동일하지만, TLB 미스시에는두배의시간이소요된다. 또하나의단점은복잡도이다. 페이지테이블검색이단순선형페이지테이블의경우보다더복잡해진다. 검색을하드웨어로구현하느냐혹은운영체제로구현하느냐여부와는무관하다. 대부분의경우, 성능서선이나부하경감을위해, 우리는보다복잡한기법을도입한다. 멀티 벨페이지테이블의경우에는메모리자원의절약을위해, 페이지테이블검색을좀더복잡하게만들 다. 멀티레벨페이징예제멀티 벨페이지테이블의서념을이해하기위해 예제를하나살펴보자. 64바이트페이지를갖는 16 KB 크기의작은주소공간을생각해보자. 14비트가상주소공간이다. VPN에 8비트, 페이지오프셋에 6비트가필요하다. 선형페이지테이블은 2 8 (256) 서엔트리로구성된다. 주소공간에 작은부분만사용된다하더라도, 선형페이지테이블의크기는변하지않는다. 그림 23.4는이구조를갖는주소공간의예시를나타낸다. 이예제에 는, 가상페이지 0과 1은코드, 가상페이지 4와 5는힙그리고가상페이지 254와 255는스택으로사용된다. 주소공간의나머지페이지들은미사용중이다. 이주소공간을 2단계페이지테이블로구성해보자. 선형페이지테이블을페이지단위로분할한다. 전체테이블은 ( 이예제에 ) 총 256서의항목을갖고있다는것을상기하자. 각 PTE는 4바이트라가정한다. 페이지테이블의크기는 1 KB (256 4 바이트 ) 이다. 페이지가 64바이트라고하면 1 KB의페이지테이블은 16서의 64바이트페이지들로분할된다. 각페이지에는 16서의 PTE가있다. 이제 VPN으로부터페이지디 터리인덱스를추출하고, 페이지테이블의각페이지위치를파악하는법을살펴보자. 페이지디 터리, 페이지테이블의페이지들모두항목의배열이라는것을기억해야한다. VPN을이용하여인덱스를구성하는법만찾으면된다. 먼저페이지디 터리의인덱스를만들어보자. 예제의작은페이지테이블은 256 원유집, 박민규, 이성진역 ; www.ostep.org 7
제 23 장페이징 : 더작은테이블 그림 23.4 64 바이트페이지들로이루어진 16 KB 주소공간 팁 : 복잡도를주의하자시스템설계자들은시스템복잡도의증가를주의해야한다. 좋은시스템서발자는주어진작 을처리하기위한최소한의복잡도를갖는시스템을만든다. 예를들어, 디스크공간이풍부하다면공간사용을최소화하기위한파일시스템을설계해 는안된다. 마찬가지로, 프로세 가빠르다면어떤작 을처리하기위해운영체제내에이해하기쉬운모듈을작성하는것이 CPU 에최적화되어있고치밀하게짜여진코드를사용하는것보다더좋다. 너무성급하게최적화한코드는다른형태에 불필요한복잡도를추가하지않도록예의주시하자. 그러한시스템은더이해하기어려우며관리와디버깅을어렵게만든다. 앙투안드생텍쥐페리 (Antoine de Saint-Exupery) 는이런유명한말을남겼다. 완벽함은무 인가더추가할것이 을때얻어지는것이아니라더이상뺄것이 을때마침내얻어진다. 그가기록하지않은부분은 완벽함에대해 이야기하는것이실제로달성하는것보다더쉽다. 는것이다. 서의항목으로 16서의페이지로나뉘어있다. 페이지디 터리는페이지테이블의각페이지마다하나씩있어야하기때문에총 16서의항목이있어야한다. 결과적으로 VPN 의 4서의비트를사용하여디 터리를구성하며, 여기 는 VPN의상위 4비트를다음과같이사용한다. VPN 에 페이지 - 디렉터리인덱스 (page-directory index, 짧게 PDIndex 라고하 8 운영체제 : 아주쉬운세가지이야기 [V.0.90]
23.3 멀티 벨페이지테이블 자 ) 를추출하고나면 PDEAddr = PageDirBase + (PDIndex * sizeof(pde)) 라는간단한식을사용하여페이지-디 터리항목 (page-directory entry, PDE) 의주소를찾을수있다. 이 게페이지디 터리가구성이되며, 이것을활용하여계속해 주소변환과정을분 하도록한다. 페이지-디 터리의해당항목이무효 (invalid) 라고표시되어있으면, 이주소접근은유효하지않다. 예외가발생한다. 해당 PDE가유효하다면추가작 을해야한다. 구체적으로살펴보자. 이페이지디 터리항목이가리키고있는페이지테이블의페이지에 원하는페이지테이블항목 (page table entry, PTE) 을읽어들이는것이목표다. 이 PTE를찾기위해 VPN의나머지비트들을사용한다. 이페이지-테이블인덱스 (page-table index, 짧게 PTIndex라고하자 ) 는페이지테이블자체인덱스로사용된다. PTE의주소를다음과같이계산한다. PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(pte)). PTE의주소를생성하기위해 는페이지-디 터리항목에 얻은페이지-프 임번호 (page-frame number, PFN) 를먼저좌측쉬프트연산하고그값을페이지테이블인덱스에합산한다. 이모든것이제대로작동하는지를보기위해, 멀티 벨페이지테이블에실제값들을넣은후에하나의가상주소를변환해보자. 이예제를위해페이지디렉터리에 부터시작해보자 ( 그림 23.5의좌측 ). 이그림에 각페이지디 터리항목 (PDE) 은주소공간의페이지테이블의페이지에대해무 인가를기술하고있다. 이예제에 는주소공간에두서의유효한영역이있으며 ( 처음과끝에 ), 그리고그사이는무효한매핑들이존재한다. 물리페이지 100에 ( 페이지테이블의 0번째페이지의물리프 임번호 ), 페이지테이블의첫 16서항목이존재한다. 이항목들은가상주소공간의첫 16서페이지에대한물리주소를가진다. 그림 23.5의가운데열이해당페이지의내용이다. 페이지테이블의첫번째페이지에는첫 16서의 VPN과물리페이지주소가있다. 이예제에 는 VPN 0과 1이유효하고 ( 코드세그멘트 ), 4와 5도유효하다 ( 힙 ). 그러므로테이블에는각페이지들의매핑정보가있다. 그외의나머지엔트리들은무효로표기되어있다. PFN 101에다른유효페이지들에대한정보가들어있다. 이페이지에는가상주소공간의마지막 16서의 VPN에대한매핑이담겨있다. 그림 23.5의우측에상세내용이있다. 이예제에 는, VPN 254와 255가유효페이지이다. 이들은스택에해당한다. 이예제를통해 멀티 벨인덱스구조가공간을얼마큼절약할수있는지를확인할수 원유집, 박민규, 이성진역 ; www.ostep.org 9
제 23 장페이징 : 더작은테이블 페이지디렉터리 PT의페이지 (@PFN:100) PT의페이지 (@PFN:101) PFN 유효한가? PFN 유효 prot PFN 유효 prot 100 1 10 1 r-x --- - --- --- 0 23 1 r-x --- 0 --- --- 0 80 1 rw- --- 0 --- --- 0 59 1 rw- --- 0 --- --- 0 --- 0 --- 55 1 rw- 101 1 --- 0 --- 45 1 rw- 그림 23.5 페이지디렉터리와페이지테이블의일부있다. 선형페이지테이블의열여섯서의페이지들을모두할당하는대신단지세서만할당하였다. 페이지디 터리를위해 한페이지, 그리고유효한매핑정보를갖고있는페이지테이블내의두부분을위해두페이지를할당하였다. 더큰 (32비트또는 64비트 ) 주소공간에 는더많은공간이절약된다. 마지막으로최종주소변환을해보자. VPN 254의 0번째바이트를가리키는주소는다음과같다. 0x3F80 또는이진수로 11 1111 1000 0000 이다. 페이지디 터리내에 각항목을가르키기위해 VPN의상위 4비트를사용하였다. 1111은페이지디 터리의마지막엔트리다 (0부터시작했다면 15번째가된다 ). 페이지디 터리의 15번째엔트리에는물리프 임주소 101이저장되어있다. VPN의다음의 4비트를 (1110) 을인덱스로사용하여, 페이지테이블의해당페이지에 원하는 PTE를찾는다. 1110는 101번페이지의 16서항목중에마지막에 두번째항목이다. 여기에 55가저장되어있다. 종합하면가상주소페이지 254 (1111 1110) 는물리페이지 55에존재한다. 오프셋 000000과 PFN 55( 또는헥사로 0x37) 를결합하여다음과같이물리주소를구할수있으며, 해당메모리를접근하는데사용된다. PhysAddr = (PTE.PFN << SHIFT) + offset = 00 1101 1100 0000 = 0x0DC0. 이제페이지디 터리를사용하여페이지테이블의페이지를가리키는 2단계페이지테이블에대한서념이어느정도이해되 을것이다. 곧구체화하겠다. 2단계페이지테이블이충분하지않을때가있다! 10 운영체제 : 아주쉬운세가지이야기 [V.0.90]
23.3 멀티 벨페이지테이블 2단계이상사용하기지금까지는멀티 벨페이지테이블은페이지디 터리와페이지테이블의 2서단계를가정하였다. 경우에따라 트리의단계를더증가시키는것도가능하다 ( 그리고사실, 그래야할필요가있다 ). 간단한예제를통해 2단계이상의멀티 벨테이블에대해알아보자. 이예제에 는 512바이트페이지와 30비트가상주소공간을가정한다. 가상주소는 21비트의가상페이지번호와 9비트의오프셋을갖게된다. 멀티 벨페이지테이블의목적은페이지테이블의모든분할된부분들이단일페이지크기에맞도록하는것이다. 만약페이지디 터리가너무커지면, 어떻게될까? 멀티 벨테이블에 몇단계를둘지정하기위해 는먼저한페이지에몇서의페이지테이블항목을저장할수있을지를계산해야한다. 페이지크기가 512바이트이고 PTE의크기가 4바이트라고가정하면한페이지에 128서의 PTE를넣을수있다. 페이지테이블의페이지를인덱스로쓰려면, VPN의하위 7비트 (log 2 128) 가필요하다. 페이지디 터리를위해 몇서의비트가남았는지를이그림에 알수있다. 14 서의비트가남는다. 2단계페이지를사용한다면, 페이지디 터리에 2 14 서의항목이있게된다. 페이지디 터리를위해 128 페이지분량의연속된메모리가필요하다. 페이지테이블을페이지단위로나누어배치할수있도록하는멀티 벨페이지테이블의근본취지가훼손된셈이다. 이문제를해결하기위해, 페이지디 터리자체를멀티페이지들로나누어 트리의단계를늘리도록한다. 그리고페이지디 터리의페이지들을가리킬수있도록그위에새로운페이지디 터리를추가한다. 결과적으로다음과같이가상주소를분할할수있다. 이제가상주소의최상위비트들을 ( 그림에 PD Index 0) 사용하여상위단계의페이지디 터리에 엔트리를찾는다. 이인덱스를사용하여상위단계페이지디 터리에 페이지디 터리항목을가져온다. 만약유효하다면, 상위단계페이지디 터리에 얻은물리주소와두번째단계의페이지디 터리인덱스 (PD Index 원유집, 박민규, 이성진역 ; www.ostep.org 11
제 23 장페이징 : 더작은테이블 1) 를결합하여페이지테이블인덱스가존재한물리페이지를구한다. 해당페이지가유효할경우, 최종적으로, PTE 주소는 2번째단계의페이지디 터리항목에 얻은페이지테이블의물리주소와페이지테이블인덱스를결합하여구한다. 실제주소를구하는데드는작 이상당하다. 멀티 벨페이지테이블사용시수반되는작 이기도하다. 변환과정 : TLB를기억하자 2단계페이지테이블사용시, 전체주소변환과정을알고리즘형태로요약정리해보자 ( 그림 23.6). 이그림은모든메모리참조에대해하드웨어가어떤식으로동작하는지를나타낸다 ( 하드웨어기반 TLB를가정 ). 그림에 볼수있듯이, 복잡한멀티 벨페이지테이블접근을거치기전에, 우선 TLB를검사한다. 히트가되면페이지테이블을참조 이물리주소를직접구성한다. TLB 미스시에만, 멀티 벨페이지테이블의모든단계를거쳐물리주소를구하게된다. 이알고리즘을통해 TLB 미스발생시, 전통적인 2단계페이지테이블의주소계산비용을볼수있다. 주소변환을위해두번의추가메모리접근이발생한다. 23.4 역페이지테이블 좀더획기적인공간절약방법으로역페이지테이블 (inverted page table) 이있다. 이방법에 는여러서의페이지테이블 ( 시스템의프로세스당하나씩 ) 대신시스템에단 1 VPN = (VirtualAddress & VPN_MASK) >> SHIFT 2 (Success, TlbEntry) = TLB_Lookup(VPN) 3 if (Success == True) // TLB 4 if (CanAccess(TlbEntry. ProtectBits) == True) 5 Offset = VirtualAddress & OFFSET_MASK 6 PhysAddr = (TlbEntry. PFN << SHIFT) Offset 7 Register = AccessMemory(PhysAddr) 8 else 9 RaiseException(PROTECTION_FAULT) 10 else // TLB 11 // 페이 12 PDIndex = (VPN & PD_MASK) >> PD_SHIFT 13 PDEAddr = PDBR + (PDIndex * sizeof(pde)) 14 PDE = AccessMemory(PDEAddr) 15 if (PDE. Valid == False) 16 RaiseException(SEGMENTATION_FAULT) 17 else 18 // PDE : 이 페이 테이블 PTE 19 PTIndex = (VPN & PT_MASK) >> PT_SHIFT 20 PTEAddr = (PDE. PFN << SHIFT) + (PTIndex * sizeof(pte)) 21 PTE = AccessMemory(PTEAddr) 22 if (PTE. Valid == False) 23 RaiseException(SEGMENTATION_FAULT) 24 else if (CanAccess(PTE. ProtectBits) == False) 25 RaiseException(PROTECTION_FAULT) 26 else 27 TLB_Insert(VPN, PTE. PFN, PTE. ProtectBits) 28 RetryInstruction() 그림 23.6 멀티레벨페이지테이블의제어흐름 12 운영체제 : 아주쉬운세가지이야기 [V.0.90]
23.5 페이지테이블을디스크로스와핑하기 하나의페이지테이블만둔다. 페이지테이블은물리페이지를가상주소상의페이지로변환한다. 역페이지테이블의각항목은해당물리페이지를사용중인프로세스번호, 해당가상페이지번호를갖고있다. 페이지테이블의목적은가상주소를물리주소로변환하는것이다. 역페이지테이블에 는주소변환을위해전체테이블을검색해 원하는가상주소페이지를갖는항목을찾아야한다. 순차탐색은느리다. 탐색속도향상을위해주로해시테이블을사용한다. PowerPC는이구조를사용하는예이다 [JM98]. 좀더일반적인시각에 보자면, 역페이지테이블역시하나의자료구조일뿐이다. 자료구조로다양한시도를할수있다. 예를들면작게도만들고크게도만들수있으며느리게도빠르게도만들수가있다. 멀티 벨과반전된페이지테이블들은할수있는다양한방법중두가지예일뿐이다. 23.5 페이지테이블을디스크로스와핑하기마지막으로중요한가정을해제하겠다. 이제까지는페이지테이블이커널이소유하고있는물리메모리영역에존재한다고가정하였다. 페이지테이블크기축소를위해많은시도를하더라도, 여전히모든페이지테이블을메모리에상주시키기에는양이너무클수도있다. 그 기때문에어떤시스템들은페이지테이블들을커널가상메모리에존재시키고, 시스템의메모리가부족할경우, 페이지테이블들을디스크로스왑 (swap) 하기도한다. 이부분에대해 는페이지들을메모리에탑재하고제거하는방법을이해한후에, 다시 ( 구체적으로 VAX/VMS에대한사례연구를다루는장에 ) 상세히다루도록한다. 23.6 요약 페이지테이블이실제로어떻게구성되 는지를보았다. 단순한선형배열을사용하는구조뿐만아니라좀더복잡한자료구조의형태도살펴보았다. 테이블을위한자료구조에는시간과공간이라는모순적선택사항이존재한다. 공간을많이소모하는테이블구조를사용할수록 TLB 미스의처리속도가빨라지고, 공간을작게차지하는테이블구조를사용하면상황은반대가된다. 주어진제약조건들을적절히고려하여적합한자료구조를결정해야한다. 주기억장치용량이작았 던과거시스템 ( 많은과거의시스템들과같은 ) 의경우, 소형자료구조의사용이현명한선택이 다. 적당한크기의메모리와다수의페이지들을사용하는워크로드의경우에 TLB 미스를신속히처리할수있는큰테이블을사용하는것이옳은선택일것이다. 소프트웨어로관리되는 TLB의경우에는, 전체자료구조를운영체제서발자가임의로그리고혁신적으로서발, 그리고서선할수있다. 어떤새로운자료구조가있을까? 그새로운구조는어떤문제를해결하는가? 잠들기전에이러한질문들을해보라. 그리고운영체제서발자만꿀수있는큰꿈을꾸자. 원유집, 박민규, 이성진역 ; www.ostep.org 13
제 23 장페이징 : 더작은테이블 참고문헌 [BO10] Computer Systems: A Programmer s Perspective Randal E. Bryant and David R. O Hallaron Addison-Wesley, 2010 아직멀티 벨페이지테이블에대한좋은일차참고문 을찾아야한다. 하지만 Bryant와 O Hallaron이 이 청난교재는멀티 벨페이지테이블을사용했던초기의시스템중의하나였던 x86의세부적인내용을다루고있다. 그리고갖고있을만한좋은 중에하나이기도하다. [JM98] Virtual Memory: Issues of Implementation Bruce Jacob and Trevor Mudge IEEE Computer, June 1998 여러다른시스템들과각각의시스템의메모리가상화기법에대한 한조사로 x86과 PowerPC, MIPS 그리고다른컴퓨터구조에대한설명이상세히나와있다. [LL82] Virtual Memory Management in the VAX/VMS Operating System Hank Levy and P. Lipman IEEE Computer, Vol. 15, No. 3, March 1982 운영체제의고전인 VMS의실제가상메모리관리자에대한아주 한논문이다. 너무나 하기때문에앞으로의몇장은이논문을기반으로우리가여태까지배운가상메모리에대해 다시살펴보도록하겠다. [M28] Reese s Peanut Butter Cups Mars Candy Corporation. 이 한당과 는 1928 에 리버 리 (Harry Burnett Reese) 에의해 만들어진것으로보인다. 에종사했던그는 Milton S. Hershey의선적감 중의하나였다. 위키페디아에 적 것으로는그 다. 그게사실이라면, Hershey와 Reese는여느두명의초콜릿부호들이그런것처 로 도보기 을것이다. [M07] Multics: History url: http://www.multicians.org/history.html 운영체제역사상가장영향력있 던시스템중의하나인 Multics 시스템에대한방대한양의역사를소서하는놀라운 사이트이다. 내용중한구절을인용한다. MIT의 Jack Dennis는 Multics가처음서발될때영향력있는구조적서념들을제안하는공 을하였다. 그의공 중에는페이징과세그멘테이션을 합하는서념도 함된다. ( 션 1.2.1 중에 ) [Nav+02] Practical, Transparent Operating System Support for Superpages Juan Navarro, Sitaram Iyer, Peter Druschel, and Alan Cox OSDI 02, Boston, Massachusetts, October 2002 현대의운영체제에큰페이지나슈퍼페이지들을 함하기위해필요한모든상세정보들을나타낸좋은논문이다. 그 지만생각하는만큼그 게쉬운것은아니다. 14 운영체제 : 아주쉬운세가지이야기 [V.0.90]
숙제 숙제멀티 벨페이지테이블이어떻게동작하는지를이해하고있는지를확인하기위한재미있는작은숙제이다. 앞문장에 재미 있다는표현이적합한지에대해 는논란이있는것은사실이다. 놀랍지않겠지만, 프로그램의이름은 paging-multileveltranslate.py이다. README의상세한설명을참고하자. 문제 1. TLB 미스에대해 하드웨어가검색을한다는가정하에 선형페이지테이블을사용하면페이지테이블의위치를찾기위해하나의 지스터가필요하다. 2단계페이지테이블을사용하는경우에는몇서의 지스터가필요한가? 3단계페이지테이블을사용하는경우는몇서가필요한가? 2. 시뮬 이터를이용하여변환을수행하여보자. 이때랜덤시드는 0과 1 그리고 2를사용하여보자. -c 플래그를사용하여답이맞는지확인해보자. 각검색을수행하기위해 몇번의메모리참조가필요한가? 3. 캐시메모리가어떻게동작하는지이해했다고했을때, 캐시를사용하면페이지테이블에대한메모리참조는어떻게동작할까? 캐시히트가많이생겨날까 ( 그래 빠르게접근될것인가 )? 또는많은미스를만들어낼까 ( 그러므로느리게접근될것인가 )? 원유집, 박민규, 이성진역 ; www.ostep.org 15