HYZ-OS-2013-基本分頁分段

114二月2024北京交通大學計算機學院何永忠操作系統(tǒng)（A）北京交通大學計算機學院何永忠副教授第四章：內(nèi)存管理214二月2024北京交通大學計算機學院第四章存儲器管理4.1內(nèi)存管理概述4.2連續(xù)分配存儲管理方式4.3基本分頁存儲管理方式4.4基本分段存儲管理方式4.5虛擬存儲器概念及關鍵技術4.6請求分頁存儲管理方式4.7請求分段存儲管理方式314二月2024北京交通大學計算機學院4.3

基本分頁存儲管理方式4.3.1離散存儲管理方式4.3.2頁面與頁表4.3.3地址變換機構4.3.4兩級和多級頁表414二月2024北京交通大學計算機學院離散存儲管理方式連續(xù)存儲管理方式弊端碎片問題及緊湊開銷離散分配方式能否把一個程序的代碼分配到內(nèi)存不連續(xù)的多個空閑空間？514二月2024北京交通大學計算機學院離散分配的問題用戶程序塊110KB用戶程序塊230KB用戶程序塊314KB用戶程序塊426KB用戶程序塊1用戶程序塊2用戶程序塊3用戶程序塊4離散分配用戶程序614二月2024北京交通大學計算機學院離散存儲管理方式離散分配方式靜態(tài)地址變換可以嗎？動態(tài)地址變換！一個基址寄存器夠嗎？程序塊地址與物理塊地址映射關系映射表格！PhysicalAddressesCPUMMUVirtualAddressesUntranslatedreadorwrite714二月2024北京交通大學計算機學院AddressSpace:AlltheaddressesandstateaprocesscantouchConsequently,twoviewsofmemory:ViewfromtheCPU(whatprogramsees)Viewfrommemory(physicalmemory)MMUconvertsbetweenthetwoviewsWithtranslation,everyprogramcanbelinkedintosameregionofuseraddressspace.EachprocessandkernelhasdifferentphysicaladdressspaceTranslationhelpstoimplementprotectionPhysicalAddressesCPUMMUVirtualAddressesUntranslatedreadorwrite814二月2024北京交通大學計算機學院4.3

基本分頁存儲管理方式4.3.1離散存儲管理方式4.3.2頁面與頁表4.3.3地址變換機構4.3.4兩級和多級頁表914二月2024北京交通大學計算機學院進程分頁內(nèi)存分塊0頁1頁2頁3頁4頁5頁…n頁用戶程序012113216318419517……n映射表：頁表頁號塊號第12塊第13塊第14塊第15塊第16塊第17塊第18塊第19塊內(nèi)存1014二月2024北京交通大學計算機學院頁面與頁表物理塊內(nèi)存空間的劃分大小相等塊：物理塊編號：0,1,2,3…頁面進程邏輯地址空間分為大小相等塊：頁編號：0,1,2,3…最后一頁可能不是整頁頁表各頁面裝入的物理塊映射表。每個進程一個頁表，存放到內(nèi)存中。如果最后一塊沒有裝滿，形成“頁內(nèi)碎片”1114二月2024北京交通大學計算機學院頁面與頁表頁面大小選擇太大：頁表小，但頁內(nèi)碎片大。太小：頁內(nèi)碎片小，但頁表大。一般都是2^n,介于29B～8KB之間1214二月2024北京交通大學計算機學院內(nèi)存頁表的結(jié)構1314二月2024北京交通大學計算機學院裝入方式動態(tài)運行時裝入方式當要裝入一個進程時，首先在內(nèi)存中尋找等于進程頁數(shù)的空閑的物理塊填寫頁表。將與各頁號對應的物理塊填入頁表中。將進程分頁裝入空閑物理塊中1414二月2024北京交通大學計算機學院4.3

基本分頁存儲管理方式4.3.1離散存儲管理方式4.3.2頁面與頁表4.3.3地址變換機構4.3.4兩級和多級頁表1514二月2024北京交通大學計算機學院分頁存儲地址結(jié)構及地址變換分頁存儲管理地址結(jié)構

31

1211

0

頁號頁內(nèi)地址邏輯地址與頁號及頁內(nèi)偏移地址之間的換算PageNo=INT[Addr/PageLength]PageOffset

=AddrMODPageLength舉例：對于1KB頁面，若給定邏輯地址2170B，則PageNo=？，PageOffset

=？地址變換任務關鍵在于頁號到物理塊號的轉(zhuǎn)變No=2,offset=1221614二月2024北京交通大學計算機學院基本的地址變換機構頁表始址頁表長度頁表寄存器頁號(3)頁內(nèi)地址邏輯地址寄存器BlockNo頁表BlockNo塊內(nèi)地址物理地址寄存器+≦越界中斷頁號物理塊號0123快表其他名稱聯(lián)想寄存器（AssociativeMemory）TLB(Tranlation

LookasideBuffer)目的提高地址變換速度方法TLB中存放經(jīng)常訪問的頁表項（一般大小16-512項)。Importantmeasure:AverageAccesstime=

(HitRatexHitTime)+(MissRatexMissTime)1814二月2024北京交通大學計算機學院具有快表的地址變換機構頁表始址頁表長度頁表寄存器頁號(3)頁內(nèi)地址邏輯地址寄存器BlockNo頁表BlockNo塊內(nèi)地址物理地址寄存器+≦越界中斷頁號物理塊號01233BlockNo輸入寄存器頁號物理塊號快表1914二月2024北京交通大學計算機學院快表引入前后數(shù)據(jù)存取速度比較假定快表檢索時間為20ns，內(nèi)存訪問時間為100ns，若假定快表查找命中率為80%，則沒有快表和有塊表時訪問一次內(nèi)存的平均訪問時間為多少？2014二月2024北京交通大學計算機學院快表引入前后數(shù)據(jù)存取速度比較假定快表檢索時間為20ns，內(nèi)存訪問時間為100ns，則若能在快表中找到CPU給出的頁號，CPU為存取一個數(shù)據(jù)將需要(100+20)=120ns；而若不能在快表中找到CPU給出的頁號，CPU為存取一個數(shù)據(jù)將需要(100+100+20)=220ns。進一步說，若假定快表查找命中率為80%，則其有效訪問時間為120×80%＋220×(1－80%)=140ns。2114二月2024北京交通大學計算機學院4.3

基本分頁存儲管理方式4.3.1離散存儲管理方式4.3.2頁面與頁表4.3.3地址變換機構4.3.4兩級和多級頁表4.3.5反置頁表2214二月2024北京交通大學計算機學院頁表空間問題及對策頁表空間問題現(xiàn)代計算機系統(tǒng)支持非常大的邏輯地址空間(232~264)，頁表變得龐大。例如，對于具有32位邏輯地址空間的分頁系統(tǒng)，規(guī)定頁面大小為4KB即212B，則每個進程頁表的頁表項可達【】個；若同時設定頁表項大小為4B，則每個進程僅頁表便需占用【】內(nèi)存空間，且要求是連續(xù)的解決方案多級頁表(頁表分頁及對換)220=1M4M2314二月2024北京交通大學計算機學院兩級頁表結(jié)構示意圖10111078…1742外層頁表第0頁頁表………內(nèi)存012n146…0121023第1頁頁表114115…011023第n頁頁表1468…011023…1267114045311514682414二月2024北京交通大學計算機學院兩級頁表結(jié)構基本方法基本思想對頁表按內(nèi)存物理塊大小進行分頁，對它們進行編號并離散地存放于不同的物理塊中；同時為離散分配的頁表分頁再建立一張頁表，稱之為外層頁表，以記錄各頁表分頁對應的物理塊號以32位邏輯地址空間、頁面大小為4KB、頁表項大小4B為例：物理塊數(shù)=232/4K=220；故頁表項大小足夠表示物理塊；頁面大小212，【12】位表示頁內(nèi)地址；內(nèi)層頁表包含【4KB/4B=1K】個頁表項，故內(nèi)層頁號為【10】位；因此外層頁表的外層頁號32-12-10=【10】位。此時邏輯地址結(jié)構為：

31

2221

1211

0

外層頁號內(nèi)層頁號頁內(nèi)地址2514二月2024北京交通大學計算機學院兩級頁表結(jié)構示意圖10111078…1742外層頁表第0頁頁表………內(nèi)存012n146…0121023第1頁頁表114115…011023第n頁頁表1468…011023…1267114045311514682614二月2024北京交通大學計算機學院具有兩級頁表的地址變換結(jié)構外層頁表始址外層頁表長度外層頁表寄存器外層頁號內(nèi)層頁號頁內(nèi)地址邏輯地址寄存器BlockNo頁表BlockNo塊內(nèi)地址物理地址寄存器+≦越界中斷內(nèi)層頁號物理塊號PageAddress外層頁表外層頁號分頁頁表起始地址+2714二月2024北京交通大學計算機學院兩級頁表地址變換107817421011…2745外層頁表1011塊………內(nèi)存012n146…01210231078塊1141151350110231742塊146815721452011023…12671140453115146832位地址空間邏輯：0x802A9F?->物理0x401FF0?->物理2814二月2024北京交通大學計算機學院多級頁表結(jié)構對于64位計算機，如規(guī)定頁面大小仍為4KB，則每個進程的頁表項可達264/4K=252個，且外層頁表可能有252/210=242個頁表項；即使按每個頁表分頁1M個頁表項來劃分，頁表分頁將達到4MB，而外層頁表仍有252/220=4G個頁表項，要占用16GB的連續(xù)內(nèi)存空間。可見，無論怎樣劃分，其結(jié)果都是不能接受的。因此，必須采用多級頁表，將16GB的外層頁表再進行分頁，并將各個分頁離散的分配到不相鄰接的物理塊中，在利用第二級的外層頁表來映射它們之間的關系。事實上，對于64位的機器，用三級頁表結(jié)構都很難適應2914二月2024北京交通大學計算機學院第四章存儲器管理4.1內(nèi)存管理概述4.2連續(xù)分配存儲管理方式4.3基本分頁存儲管理方式4.4基本分段存儲管理方式4.5虛擬存儲器概念及關鍵技術4.6請求分頁存儲管理方式4.7請求分段存儲管理方式3014二月2024北京交通大學計算機學院4.4

基本分段存儲管理方式4.4.1分段存儲管理方式的引入4.4.2分段系統(tǒng)的基本原理4.4.3信息共享4.4.4段頁式存儲管理方式3114二月2024北京交通大學計算機學院分段存儲管理方式的引入滿足用戶在編程和使用上的多方面要求信息共享信息保護 （分段作為信息的邏輯單位）動態(tài)鏈接3214二月2024北京交通大學計算機學院4.4

基本分段存儲管理方式4.4.1分段存儲管理方式的引入4.4.2分段系統(tǒng)的基本原理4.4.3信息共享4.4.4段頁式存儲管理方式3314二月2024北京交通大學計算機學院分段作業(yè)地址空間被劃分為若干段，每個段定義了一組邏輯信息，如主程序MAIN、子程序段X、數(shù)據(jù)段D及棧段S，各段均有自己的名字（段號）每個段都從0開始編址，并采用一段連續(xù)的地址空間，且段的長度取決于相應的邏輯信息組的長度，因而各段長度可不等整個作業(yè)的地址空間是二維的，其邏輯地址有段號(名)和段內(nèi)地址所組成（不連續(xù)!）31

1615

0

段號段內(nèi)地址3414二月2024北京交通大學計算機學院利用段表實現(xiàn)地址映射示意圖作業(yè)空間段表內(nèi)存30K40K20K80K15K120K10K150K段長段號01(MAIN)=0030K(X)=1020K(D)=2015K(S)=3010K基址23(MAIN)=030K(X)=120K(D)=215K(S)=310K40K80K120K150K3514二月2024北京交通大學計算機學院分段系統(tǒng)地址變換機構段表始址段表長度段表寄存器段號(2)段內(nèi)地址(100)邏輯地址寄存器段表8292物理地址寄存器+≦越界中斷1K6K6004K5008K2009200段長段號01基址23+≦越界中斷低四位為0段最大長度64K，0x101F0?3614二月2024北京交通大學計算機學院分頁與分段存儲管理的比較相似之處實現(xiàn)機制（離散分配、地址映射機構）目的及內(nèi)涵內(nèi)存利用率需要/用戶需要；物理單位/邏輯單位；透明/不透明分頁/段長度固定/可變；決定因素(系統(tǒng)硬件/信息性質(zhì))作業(yè)地址空間維數(shù)一維/二維、程序員編程、編譯程序3714二月2024北京交通大學計算機學院4.4

基本分段存儲管理方式4.4.1分段存儲管理方式的引入4.4.2分段系統(tǒng)的基本原理4.4.3信息共享4.4.4段頁式存儲管理方式3814二月2024北京交通大學計算機學院可重入代碼（純代碼）一種允許多個進程同時訪問的代碼為使各個進程所執(zhí)行的代碼完全相同，絕對不允許可重入代碼在執(zhí)行中有任何改變，所以它是一種不允許任何進程對其進行修改的代碼3914二月2024北京交通大學計算機學院可重入代碼（純代碼）一種允許多個進程同時訪問的代碼但事實上，大多數(shù)代碼在執(zhí)行時都有可能發(fā)生改變，例如其中用于控制程序執(zhí)行次數(shù)的變量及指針、信號量及數(shù)組等。為此，在每個進程中都必須配備局部數(shù)據(jù)區(qū)，并把在執(zhí)行中可能改變的部分都拷貝到該數(shù)據(jù)區(qū)。這樣，在程序執(zhí)行時，只去對屬于特定進程私有的數(shù)據(jù)區(qū)中的內(nèi)容進行修改，而不去改變共享的代碼，這時的可共享代碼即成為可重入代碼4014二月2024北京交通大學計算機學院信息共享比較舉例說明多個用戶對文本編輯程序的共享某多用戶系統(tǒng)，可同時接納40個用戶，假設均在執(zhí)行Editor進行文本編輯。若該文本編輯程序含有160KB的代碼區(qū)和40KB的數(shù)據(jù)區(qū)，則總共需有8000KB的內(nèi)存空間來支持40個用戶。如果該文本編輯程序代碼是可重入的，則無論分頁系統(tǒng)還是分段系統(tǒng)該程序代碼都能被共享，即內(nèi)存中只需保留一份文本編輯程序的副本，因而所需內(nèi)存空間僅為40×40+160=1760KB4114二月2024北京交通大學計算機學院基于分頁的文本編輯器共享CodePage1CodePage2…CodePage40DataPage1…DataPage10進程1…CodePage1CodePage2CodePage3CodePage4…CodePage40DataPage1…DataPage10DataPage1…DataPage10…內(nèi)存…22CodePage1CodePage2…CodePage40DataPage1…DataPage10進程22122…6061…70進程1頁表…2122…6071…80進程2頁表2124236160807170160KB40KB160KB40KB4214二月2024北京交通大學計算機學院基于分段的文本編輯器共享EditorDataSeg1進程1…EditorDataSeg1…DataSeg2…內(nèi)存…80K進程2進程1段表…240KEditorDataSeg1160K80K40K240K段長段號01基址進程2段表160K80K40K380K段長段號01基址280K380K420K4314二月2024北京交通大學計算機學院4.4

基本分段存儲管理方式4.4.1分段存儲管理方式的引入4.4.2分段系統(tǒng)的基本原理4.4.3信息共享4.4.4段頁式存儲管理方式4414二月2024北京交通大學計算機學院段頁式存儲管理方式的引入分頁與分段存儲管理各有優(yōu)缺點分頁系統(tǒng)能有效地提高內(nèi)存利用率分段系統(tǒng)則能很好地滿足用戶需