Modified from lecture slides made by Prof. Sung-Yong Park and Prof. Youngjae Kim Chapter 9. Virtual Memory Introduction to Operating Systems CSW3020 Prof. Young Pyo JUN CSW3020/Introduction to Operating Systems 1
주요내용 가상메모리개념 요구페이징 페이지대치알고리즘 프레임할당 작업세트모델 쓰래싱 메모리맵파일 커널메모리 2
가상메모리의필요성 프로그램이실행되기위해서반듯이메모리에적재되어야하나전체프로그램이적재될필요는없다 Error code, unusual routines, large data structures 전체프로그램이동시에적재되어있을필요는없다. 그러면, 프로그램일부만적재하여실행할수있다면? 가상메모리 (Virtual memory) separation of user logical (virtual) memory from physical memory 물리메모리가작은경우에도매우큰가상메모리를프로그래머에게제공함 (e.g., virtual memory > physical memory) 프로그래머가물리메모리크기에제약받지않고매우쉽게프로그래밍을할수있다. 실행을위해서프로그램의일부만메모리에있으면된다. CSW3020/Introduction to Operating Systems 3
메모리관리기법의분류요소 1. 물리적공간과논리적공간의크기 2. 사상 (mapping) 함수가취급하는단위 3. 프로그램전체적재또는부분적재실행 공간크기사상단위적재단위단점 분할방법논리 = 물리전체프로그램전체프로그램 단점 : 외부단편화발생 페이징 논리 = 물리 페이지 ( 세그먼트기법은가변크기 ) 전체 프로그램 단점 : 사상테이블인페이지테이블필요 가상메모리논리 > 물리페이지프로그램일부적재 장점 : 오버레이가능. 부분적재로메모리활용도증대 4
가상메모리개념 물리메모리에일부의페이지만적재 적재여부를페이지테이블에표시 5
요구페이징 (Demand Paging) 페이지부재 (page fault) 가발생, 즉, CPU 가해당페이지를요구할때까지그 페이지를메모리에올리지않는방식 페이지부재가발생하면그때트랩을걸어해당페이지를적재 Load M 6
페이지대치 물리메모리에여유가없을때희생될페이지를찾아대치 7
가상메모리를위한페이지테이블 가상메모리를위한페이지테이블은페이징기법과유사 유효 (Valid)/ 무효 (Invalid) 비트 페이지가메모리에없는경우가있으므로페이지테이블에유효 (Valid)/ 무효 (Invalid) 비트가추가됨 오염비트 (dirty bit, modify bit) 페이지대치시디스크로다시출력 (write back) 필요여부판정필요 페이지적재후변경유무를표시 8
Virtual Address Space Logical view of how a process is stored in memory Typically contiguous memory from 0 to max address (c.f. physical memory may not be contiguous) MMU maps logical pages to physical frames When a process asks for dynamic memory, it doesn t get additional frames; instead, it gets the right to use a new range of virtual address space (e.g., memory region in Linux) Requires actual physical frames only if the grown heap or stack is actually used CSW3020/Introduction to Operating Systems 9
[ 참고 ] Copy-on-Write Fork를하게되면자식프로세스를위해부모프로세스의프레임들을복제해주어야한다. 그러나, 반드시그럴필요는없다. 만약많은자식프로세스가모두 fork 후바로 exec를한다면? 먼저페이지를공유하며 copy-on-write 페이지로마크를한후, 프로세스가임의의페이지에 write를하면그때새로운프레임을생성 ( 예 : 윈도XP, Solaris, Linux) Free page 풀 (pool) 을마련하여힙이나스택변경이나 copy-on-write 에대비 ( 참고 : zero-fill-on-demand) 10
가상메모리를위한페이지테이블 가상메모리의공간이크기때문에 ( 예, 32비트어드레싱 ) 페이지테이블크기가증가 따라서페이지테이블을몇개의수준으로구현
프로그램부분적재의타당성 많은경우전체프로그램이불필요 오류코드는빈번히실행되지않음 행렬, 리스트및테이블은실제로필요한크기이상으로프로그램에서선언되어할당됨 프로그램의여러가지기능이나특성중에서어떤일부는거의사용되지않음 Locality of Reference 성질 프로그램의어느한특정작은부분만한동안집중적으로참조하는현상 (Principle of Locality) 12
프로그램부분적재의이점 프로그램의크기가물리적인용량에무관 더많은프로그램이메모리를공유하여 CPU 사용률과처리율 (Throughput) 을향상함 주소결속을실행시간에할수있음 결국, Page-fault rate 을낮추어성능을높이는것이문제! 13
부분적재실행에서해결할문제 교체공간운용 - 디스크와메모리사이의입출력을효율화 적재할페이지의선택과적재시점 - 페이징알고리즘 대치할페이지의선택 페이지대치알고리즘 적절한메모리크기 ( 프레임수 ) 의결정 - 과다한페이지오류와쓰래싱을방지하는메모리의크기 14
페이지대치알고리즘 최적대치알고리즘 FIFO(First-In-First-Out) LRU(Least Recently Used) - 최저사용 LRU 근사알고리즘 Additional Reference Bit 알고리즘 Second Chance 알고리즘 LFU(Least Frequently Used) - 최소사용 MFU(Most Frequently Used) - 최다사용 15
최적 vs 최악대치알고리즘 최적대치알고리즘 Belady( 밸러디 ) 알고리즘또는 B0 알고리즘 앞으로가장오랫동안사용되지않을페이지를찾아서교체 하는알고리즘 Lookahead 알고리즘으로실현이어려움 그러나, 대치알고리즘의상한선 최악대치알고리즘 랜덤알고리즘 현재메모리에있는페이지중에서랜덤하게하나를선택하여대치 대치알고리즘의하한선 16
페이지대치성능의한계영역 page fault rate 1.0 random algorithm Non-lookahead algorithms 0 B0 algorithm 1 n performance of page replacement algorithms number of frames 17
최적대치알고리즘 * 표시는 page fault 를의미 프레임 3 개사용시 참조스트링 1* 2* 3* 4* 1 2 5* 1 2 3* 4* 5 페이지프레임 1 1 1 1 1 1 1 1 1 3 4 4 2 2 2 2 2 2 2 2 2 2 2 3 4 4 4 5 5 5 5 5 5 2 1 3 페이지부재 7 회 프레임 4 개사용시 참조스트링 1* 2* 3* 4* 1 2 5* 1 2 3 4* 5 페이지프레임 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 5 2 1 3 페이지부재 6 회 18
FIFO 메모리에올라온지가장오래된페이지를택하여대치하는알고리즘 Belady s Anomaly( 벨러디변이 ) 발생 페이지오류율이할당되는프레임의 수가증가함에도오히려증가할수도있다. 프레임 3 개사용시 참조스트링 1* 2* 3* 4* 1* 2* 5* 1 2 3* 4* 5 FIFO 큐 1 1 1 2 3 4 1 1 1 2 5 5 2 2 3 4 1 2 2 2 5 3 3 3 4 1 2 5 5 5 3 4 4 페이지부재 9 회 프레임 4 개사용시 참조스트링 1* 2* 3* 4* 1 2 5* 1* 2* 3* 4* 5* FIFO 큐 1 1 1 1 1 1 2 3 4 5 1 2 2 2 2 2 2 3 4 5 1 2 3 3 3 3 3 4 5 1 2 3 4 4 4 4 5 1 2 3 4 5 페이지부재 10 회 19
LRU(Least Recently Used) 가장오랫동안사용하지않은페이지를대치 스택알고리즘의일종 순서바뀜에유의! 프레임 3 개사용시 참조스트링 1* 2* 3* 4* 1* 2* 5* 1 2 3* 4* 5* LRU 스택 1 1 1 2 3 4 1 2 5 1 2 3 2 2 3 4 1 2 5 1 2 3 4 3 4 1 2 5 1 2 3 4 5 페이지부재 10 회 프레임 4 개사용시 참조스트링 1* 2* 3* 4* 1 2 5* 1 2 3* 4* 5* LRU 스택 1 1 1 1 2 3 4 4 4 5 1 2 2 2 2 3 4 1 2 5 1 2 3 3 3 4 1 2 5 1 2 3 4 4 1 2 5 1 2 3 4 5 페이지부재 8 회 20
LRU(Least Recently Used) B0 알고리즘의경우미래를예측하는것이불가능하므로과거사실에의거하여결정을내리는수밖에없음 가까운미래의근사값으로 가장최근의과거 를사용. 즉, 오랜기간사용되지않는페이지를대치 Locality of reference에근거하여가장오랫동안사용하지않은페이지는앞으로도상당한기간사용되지않을것이라는가정 B0 와 LRU 의대칭성에따른성능의유사성 B0는 w에서 r t 를기준으로해서오른쪽 ( 미래 ) 으로가장멀리있는페이지를대치 LRU는왼쪽 ( 과거 ) 으로가장멀리있는페이지를대치 LRU w= r 1, r 2, r 3, r t-1, r t, r t+1, B0 21
FIFO 와 LRU FIFO 는페이지가프레임으로적재된순서를이용 LRU 는적재된순서가아닌 참조된시간 정보가필요 참조된시간을관리하는것이적재순서를관리하는것보다 어려운작업 22
LRU 의문제점 B0와의대칭적유사성으로개념적으로는좋은기법이나각프레임들의최후사용시간에따른순서를정하는데에하드웨어의지원이필수 첫째방법 : 임의프레임에참조가일어날때마다해당페이지테이블에있는사용시간레지스터에 CPU의논리시계혹은계수기값을기록 둘째방법 : 페이지번호의 LRU스택을유지 ( 예제를보았음 ). 마이크로코드로구현하여오버헤드를최소화 23
LRU 에의근접 - 참조비트 순수한의미의 LRU를위한지원하드웨어보다는참조비트지원 처음에는모든비트가운영체제에의해 0으로설정 참조된각페이지의참조비트가하드웨어에의해 1로설정 약간의시간이지난다음어떤페이지가참조되었는지해당비트를시험하여결정 사용순서는모르지만해당기간동안의사용여부를판별함으로써부분적순서정보추출이가능 LRU 대치에근사한다양한대치알고리즘에서사용가능 24
참조바이트활용 일정간격 ( 타이머인터럽트, 예 :10ms) 으로참조비트를참조바이트에복사 최근의 8번기간동안그페이지사용기록을간직 참조바이트값이가장작은페이지를대치 페이지테이블 참조비트 2. 복사 참조바이트 ( 쉬프트레지스터 ) 1. 쉬프트 예 : 11000100 이 01110111 보다최근에사용됨 8 회이상이전의참조상황은비교할수없다는한계가있음 25
2 차기회알고리즘 (Clock Policy) 참조비트만제공될경우에사용 LRU와근접한것으로판명된알고리즘 FIFO 형태로빈프레임찾기를계속하여참조비트가 0이면그프레임의페이지를대치 1이면 0으로변경하여다시한번기회를부여하고 FIFO 대치계속 26
2 차기회알고리즘 (Clock Policy) 27
페이지오류율비교 Bear( 80) 실험내용 (Finkel( 88) 도유사한결과 ) 페이지크기 256 Words FORTRAN 프로그램이 0.25x10 6 회의메모리참조추적FIFO의경우최적에비해 2배이상나쁨 28
사전대치 (Prepaging) 페이지오류발생은많은오버헤드야기 트랩에의해처리되고이후해당프로세스를다시실행시키려면스케쥴이되어야함 페이지대치까지수행되어야한다면더많은시간이소요 오염비트는대치시출력요인을줄일수있어약간의도움이됨 만약, 항상빈프레임을갖고있으면페이지대치가일어나는것을미연에방지할수있음 페이지대치알고리즘을사전에실행 미리선정된희생자를디스크로내보내는출력작업은 CPU와병행할수있으므로더욱효과적임 29
사전적재 (Preloading) 나아가, 페이지부재발생시점에페이지를적재하지말고미리여러페이지를한번에적재해놓는방법 페이지참조에대한예측이필요하나다양한정보를활용할수있음 예 : 서브루틴 ( 함수 ), 행렬이참조되는경우연관페이지모두를적재 컴파일러에의하여필요정보가제공될수있음 현재입출력에사용되는페이지, 즉입출력중인페이지는대치되지말아야함 30
페이지크기 Locality 부분 일반적으로 작아지면필요한페이지수가많으나, 어느정도 시간이지나면 locality 에의해인접부분을모두 포함하게되어페이지폴트발생은낮아지게됨 커질수록개별페이지들은최근의참조로부터보다 멀어지게되어 locality 효과가약화되어페이지 폴트가증가 페이지크기가프로그램크기에근접할경우페이지 폴트는발생하지않을것임 정답은없다, 그러나, 페이지크기는계속커지는 추세로진행되어왔으며, 현재 4KB, 8KB 가 보편화됨 큰페이지 VS 작은페이지 31
프레임할당 최소로필요한프레임의수 명령의구조로결정됨 HW 측면 : IBM 370 MVC 명령어경우 - 6 페이지필요 명령어위해 2페이지 ( 저장공간으로부터저장공간으로의명령 ) from 파트를위하여 2 페이지 ( 간접주소 ) to 파트를위하여 2 페이지 ( 간접주소 ) SW 측면의고려요소 Loop 내의 page 는한꺼번에 allocate 되는것이유리함 그렇지않으면최악의경우매 loop 마다 page fault 가능 32
프레임할당 프레임할당알고리즘 동등할당 (Equal Allocation) 모든프로세스에게똑같은개수의프레임을할당 비례할당 (Proportional Allocation) 프로그램의크기에비례하여프레임을할당 우선순위할당 프로그램의크기가아니라우선순위에따라프레임할당 33
프레임할당 프레임할당개수와페이지폴트발생률 페이지크기가고정되어있을때주기억장치에유지되는페이지의 개수가늘어날수록페이지폴트발생률은떨어짐 34
쓰래싱 (Thrashing) 발생원인 프로세스가많아짐에따라, 페이지폴트가보다자주일어나게되면 프로세스들이페이징을기다리는동안 CPU 이용률이떨어지게되고, CPU 스케쥴러는 CPU 이용률을높이려고프로세스수를더늘리려는악순환이반복됨 결국프로세스들이실행되는시간보다페이지를교체하는데에더많은시간이소요되는현상 (Thrashing) 이발생 35
쓰래싱 (Thrashing) 쓰래싱현상의방지 각프로세스가필요로하는최소한의프레임개수를보장해야한다. 그러나, 각프로세스가필요로하는최소한의프레임개수를알수있는방법이필요 Locality Model에근거한작업세트 (Working Set) 방법 36
작업세트모델 (Working Set Model) 메모리참조패턴의 locality ( 국부성또는지역성 ) 에근거 작업세트 - 가장최근의 d개페이지참조에들어있는페이지의집합 적당한 d 값의선택이중요 ( 예 ) 어떤연구에서는 10,000개 d 가작으면지역을충분히포함못함 d 가크면지역이서로겹침
작업세트 ( 예 ) 38
작업세트크기의동적변화패턴 39
스래싱과작업세트모델의활용 WSS(Working Set Size) m = M/S (M 은메모리총사이즈, S 는페이지크기 ) 40
페이지부재빈도 쓰래싱은결국페이지부재빈도 (PFF, Page-fault Frequency) 문제 임의프로세스에대하여 원하는페이지부재율의 상한선과하한선을정해놓고, 상한선을넘으면더많은 프레임을할당해주고 하한선을넘으면프레임을회수 41
Memory-mapped File 메모리사상파일 - 임의프로세스의가상주소공간중일부를파일에할애하여디스크입출력시스템콜대신메모리를접근하도록하는방식 예 : Solaris의경우 mmap( ) 시스템콜을통하여대상파일을메모리공간의일부로사상 여러프로세스가메모리사상파일을통해특정파일을공유하는것도가능 copy-on-write 적용, 동기화를위해 mutex 사용 42
Memory-mapped File 메모리사상파일을이용하여공유메모리구현가능 동일파일을프로세스들의가상주소공간에사상하여프로세스들이통신할수있도록제공 사상된파일이통신하는프로세스들사이의공유메모리영역으로동작 43
Kernel Memory Allocation 커널메모리는사용자모드프로세스에게할당되는페이지와는별도의메모리풀사용 Buddy system 물리적으로연속된페이지 ( 프레임 ) 들로이루어진고정된크기의세그먼트로부터메모리할당 할당시 Power-of-2 allocator: 2의거듭제곱단위로할당 최소의맞는공간이만들어질때까지둘 (buddy) 로나눔 반납시하나의큰세그먼트로합쳐짐 - 병합 (coalescing) ( 장점 ) 속도가빠르다 ( 단점 ) 단편화 ( 예 : 33KB가필요한경우 ) 44
Kernel Memory Allocation Slab Allocation( 슬랩할당 ) 슬랩 : 하나또는그이상의연속된페이지 캐시 (cache): 하나또는그이상의슬랩들로구성 각커널인스턴스 ( 객체 ) 생성시할당될캐시를미리준비 (preallocated) 객체예 : PCB, 파일객체, 세마포등커널내주요자료구조 캐시가생성되면 free로표시된몇개의커널객체들을미리마련해놓음 캐시내의최대객체수는해당슬랩의크기에좌우 예 : 한페이지가 4KB 인경우 12KB 슬랩은 3 개의 페이지로구성되며 2KB 객체를 6 개포함가능 참고 : 슬랩할당기는 Solaris 2.4 커널에서처음사용, 리눅스는원래버디시스템사용하다버전 2.2 부터슬랩할당기 (SLAB) 사용, 버전 2.6.24 부터이를개선한 SLUB 할당기로대체 45
Kernel Memory Allocation 슬랩할당알고리즘 장점 : 커널수행중커널객체가요청되면해당캐시의 free 객체들중에서하나를할당, 해당객체를 used로표시 예 : struct task_struct는대략 1.7KB, 프로세스하나가생성할때 struct task_struct를위한캐시의 free 객체에서하나를신속히할당 캐시에할당된슬랩은 full( 모든객체 used), empty( 모든객체가 free), partial(used, free 객체가섞여있음 ) 중하나의상태 커널객체할당요청이오면, 먼저 partial 슬랩의 free 객체를이용해할당해주고, partial 슬랩이없으면 empty 슬랩의 free 객체를할당. 만약 empty 슬랩도없으면새로운슬랩하나를캐시에할당 단편화가발생하지않는다. 각커널객체마다해당캐시존재 빠르다. 객체들이미리생성되어있고캐시에서쉽게할당가능 46
End of Chapter 9 CSW3020/Introduction to Operating Systems 49