522固定分區(qū)分配FixedPartitionAllocation市公開課一等獎省賽課獲獎?wù)n件

最早一個可運(yùn)行多道程序存放管理方式。它將內(nèi)存空間劃分為若干個固定大小區(qū)域，在每個分區(qū)中能夠裝入一道作業(yè)。一.劃分分區(qū)方法1.分區(qū)大小相等全部內(nèi)存分區(qū)都大小相等，其缺點(diǎn)是顯著:(空間浪費(fèi)或者使大程序無法運(yùn)行)。2.分區(qū)大小不等為了克服分區(qū)大小相等分配方法缺點(diǎn)，可在內(nèi)存中劃分出多個較小分區(qū)、適量中等分區(qū)及少許大分區(qū)。二、內(nèi)存分配（見圖5-6）通常將這些分區(qū)依據(jù)其大小進(jìn)行排隊,并為之建立一張分區(qū)使用表。5.2.2固定分區(qū)分配

FixedPartitionAllocation522固定分區(qū)分配FixedPartitionAllocation第1頁分區(qū)號大小(kb)始址(k)狀態(tài)1234153050100304575125已分配已分配已分配已分配操作系統(tǒng)作業(yè)A作業(yè)B作業(yè)C

030k45k75k125k225kA:B:C=15:30:50圖5--6固定分區(qū)使用表(a)分區(qū)說明表;(b)存放空間分配情況（a）（b）522固定分區(qū)分配FixedPartitionAllocation第2頁5.2.3動態(tài)分區(qū)分配

DynamicPartitionAllocation動態(tài)分區(qū)分配是依據(jù)進(jìn)程實際需要，動態(tài)地為之分配連續(xù)內(nèi)存空間。在實現(xiàn)可變分區(qū)存放管理方式時，必須處理下述三個問題：（1）分區(qū)分配中所用數(shù)據(jù)結(jié)構(gòu)（2）分區(qū)分配算法（3）分區(qū)分配操作一、分區(qū)分配中數(shù)據(jù)結(jié)構(gòu)慣用數(shù)據(jù)結(jié)構(gòu)有兩種：1.空閑分區(qū)表2.空閑分區(qū)鏈522固定分區(qū)分配FixedPartitionAllocation第3頁序號1分區(qū)大小(kb)分區(qū)始址(k)狀態(tài)12346424403044132210270可用可用可用可用5圖5--7空閑分區(qū)說明表N個字節(jié)可用前向指針N+20后向指針N+20圖5--8空閑鏈結(jié)構(gòu)522固定分區(qū)分配FixedPartitionAllocation第4頁二.分區(qū)分配算法

PartitionAllocationAlgorithm（1）首次適應(yīng)策略（First-FitStrategy）

分配主存中第一次碰到適合該作業(yè)要求空閑空間。(要求空閑分區(qū)鏈以地址遞增次序鏈接)

特點(diǎn):傾向于使用低地址部分,從而保留了高地址部分大空閑區(qū);但,低地址部分分區(qū)數(shù)量增多,從而增加了查找空閑區(qū)開銷。（2）循環(huán)首次適應(yīng)策略（CyclicFirst-fitstrategy）

查找空閑區(qū)從上次找到空閑區(qū)下一空閑區(qū)開始，并循環(huán)查找。（需要設(shè)置一起始查找指針。）

特點(diǎn)：空閑區(qū)分布均勻，從而降低了查找開銷；但會缺乏大空閑區(qū)。（3）最正確適配策略（Best-fitstrategy）

從空閑區(qū)中挑選一個能滿足作業(yè)要求最小分區(qū)。（空閑區(qū)以其空間大小遞增次序形成空閑區(qū)鏈）（缺點(diǎn)：更輕易形成碎片）（4）最壞適應(yīng)策略（Worst-fitstrategy）

該策略分配滿足作業(yè)要求最大一塊空閑空間。522固定分區(qū)分配FixedPartitionAllocation第5頁三、分區(qū)分配操作

PartitionAllocationOperation1、分配內(nèi)存(MemoryAllocation)u.size:請求分區(qū)大小；

m.size:表中每個空閑分區(qū)大??；

size:事先要求不再切割剩下分區(qū)大小。內(nèi)存分配流程（見圖5-9）522固定分區(qū)分配FixedPartitionAllocation第6頁從頭開始查表檢驗完否?M.size>u.size?M.size-u.size<size?從該分區(qū)中劃出U.size大小分區(qū)將該分區(qū)分配給請求者修改相關(guān)數(shù)據(jù)結(jié)構(gòu)返回將該分區(qū)從鏈中移走繼續(xù)檢索下一個表項返回圖5-9內(nèi)存分配流程N(yùn)YYYNN522固定分區(qū)分配FixedPartitionAllocation第7頁三、分區(qū)分配操作

PartitionAllocationOperation2、回收操作(ReturnOperation)當(dāng)內(nèi)存運(yùn)行完成釋放內(nèi)存時，系統(tǒng)依據(jù)回收區(qū)首址，從空閑鏈中找到對應(yīng)插入點(diǎn)，此時可能出現(xiàn)四種情況之一：（1）回收區(qū)與插入點(diǎn)前一個分區(qū)相鄰接。（2）回收區(qū)與插入點(diǎn)后一個分區(qū)相鄰接。（3）回收區(qū)與插入點(diǎn)前、后兩個分區(qū)相鄰接。（4）回收區(qū)不與插入點(diǎn)前、后兩個分區(qū)相鄰接。522固定分區(qū)分配FixedPartitionAllocation第8頁F2

回收區(qū)F2

回收區(qū)F1F1

回收區(qū)(a)(b)(c)圖5--10內(nèi)存回收時情況522固定分區(qū)分配FixedPartitionAllocation第9頁順序地檢索可用資源表直至找到某表目m.addr>aa或m.size=0不是第一個表目且與前一可用區(qū)相鄰?所釋放可用區(qū)size=0?與后一可用分區(qū)相鄰且不為空表目?與后一可用區(qū)相鄰?所釋放可用區(qū)與后一可用區(qū)合并將該表目以上全部表目上移一格,并插入、新釋放可用區(qū)表目把所釋放可用區(qū)與前一分區(qū)合并與后一可用區(qū)合并將該表目以上所有表目；下移一格返回是否是否是否mfree圖5--11內(nèi)存回收流程Y522固定分區(qū)分配FixedPartitionAllocation第10頁操作系統(tǒng)用戶程序1用戶程序610KB用戶程序330KB操作系統(tǒng)26KB用戶程序914KB用戶程序1用戶程序9用戶程序3用戶程序680KB(a)(b)圖5--12緊湊示意(a)緊湊前;(b)緊湊后5.2.4動態(tài)重定位分區(qū)分配一、緊湊(Compact)522固定分區(qū)分配FixedPartitionAllocation第11頁二、動態(tài)重定位

DynamicRelocationLOAD1,2500365250010000365LOAD1,2500+處理機(jī)一側(cè)存放器一側(cè)圖5--13動態(tài)重定位示意01002500500010000101001250015000主存作業(yè)J相對地址重定位存放器522固定分區(qū)分配FixedPartitionAllocation第12頁修改相關(guān)數(shù)據(jù)結(jié)構(gòu)檢索空閑分區(qū)鏈(表)進(jìn)行緊湊形成連續(xù)空閑區(qū)修改相關(guān)數(shù)據(jù)結(jié)構(gòu)按動態(tài)分區(qū)方式進(jìn)行分配找到大于u.size可用區(qū)否?空閑分區(qū)總和>u.size?返回分區(qū)號及首址無法分配返回請求分配u.size分區(qū)否否是圖5--14動態(tài)分區(qū)分配算法流程三、動態(tài)重定位分區(qū)分配算法DynamicRelocationPartitionAllocationAlgorithm

522固定分區(qū)分配FixedPartitionAllocation第13頁5.2.5

IBM-PC微機(jī)中存放管理方式

MemoryManagementinIBM-PC一.段存放器和作業(yè)分段

在IBM-PC微機(jī)中，采取了多重定位存放器管理方式。在PC機(jī)中共設(shè)置了四個段存放器：代碼段存放器CS(CodeSegment)；數(shù)據(jù)段存放器DS(DataSegment)；棧段存放器SS(StackSegment)；附加段存放器ES(ExpandedSegment)。對應(yīng)地，在PC機(jī)中運(yùn)行作業(yè)也可分成四個段：即代碼段，數(shù)據(jù)段，供程序使用棧段，以及作為用戶工作區(qū)附加段。這幾個段地址空間能夠鄰接；也可部分或全部重合。所以，一個作業(yè)最大地址空間可為256KB，每一個段能夠存放在內(nèi)存用戶區(qū)任何位置，如圖5-15所表示。522固定分區(qū)分配FixedPartitionAllocation第14頁附加段棧段數(shù)據(jù)段代碼段SSESCSDS段存放器圖5--15段存放器與作業(yè)分段522固定分區(qū)分配FixedPartitionAllocation第15頁5.2.5

IBM-PC微機(jī)中存放管理方式

MemoryManagementinIBM-PC二、形成訪問內(nèi)存物理地址

Intel8086芯片含有訪問20位地址總線，能直接訪問1MB內(nèi)存空間；而8086中全部存放器都是16位，其尋址能力只達(dá)64KB。為了利用16位存放器來形成訪問內(nèi)存所需20位物理地址，可用下述方法：每當(dāng)需要產(chǎn)生一個20位物理地址時，會自動地選擇一相關(guān)段存放器，先將它內(nèi)容左移4位，然后與一個16位地址偏移量（即段內(nèi)相對地址）相加，其結(jié)果便是所需要20位訪問內(nèi)存物理地址。即：(段存放器)左移4位+段內(nèi)偏移量>物理地址三、多重定位實現(xiàn)在Intel8086處理器四個段存放器中，其每一個作用與前面所介紹重定位存放器相同，可用來實現(xiàn)動態(tài)重定位。522固定分區(qū)分配FixedPartitionAllocation第16頁5.3對換(Swapping,交換）

對換技術(shù)，最早用在MIT兼容分時系統(tǒng)CTSS中。該系統(tǒng)是單用戶系統(tǒng)，在內(nèi)存中僅駐留一道用戶作業(yè)。全部其它作業(yè)都駐留在外存后備隊列上，每次只調(diào)入一個作業(yè)進(jìn)入內(nèi)存運(yùn)行；此作業(yè)時間片用完時，又將該作業(yè)調(diào)至外存，再將后備隊列上另一個作業(yè)調(diào)入內(nèi)存；也讓它運(yùn)行一個時間片時間，然后又將它調(diào)出，再調(diào)下一個作業(yè)進(jìn)入內(nèi)存。這就是早期交換技術(shù)，此時引入交換技術(shù)目標(biāo)，是為了處理因為內(nèi)存不足而無法同時容納多達(dá)數(shù)十甚至數(shù)百個用戶程序，以參加運(yùn)行問題。但這種最初交換技術(shù)已極少再用，因為其效率太低，其CPU大約有二分之一時間，都處于空閑狀態(tài)，以等候前一作業(yè)調(diào)出和后一作業(yè)調(diào)入。522固定分區(qū)分配FixedPartitionAllocation第17頁5.3.1多道程序環(huán)境下對換

SwappinginMulti-programmingEnvironment

多道程序環(huán)境下資源浪費(fèi)，造成系統(tǒng)吞吐量下降。所謂“對換”，是指把內(nèi)存中暫不能運(yùn)行進(jìn)程，或暫時不用程序和數(shù)據(jù)，換出到外存上，以騰出足夠內(nèi)存空間，把已具備運(yùn)行條件進(jìn)程，或進(jìn)程所需程序和數(shù)據(jù)，換入內(nèi)存。對換是提升內(nèi)存利用率有效辦法。在UNIX和WindowsOS都引入了對換功效。換入、換出是由系統(tǒng)對換進(jìn)程來完成。對換分類：整體對換或進(jìn)程對換；部分對換或頁面對換（分段對換）。（虛擬存放基礎(chǔ)。）522固定分區(qū)分配FixedPartitionAllocation第18頁5.3.2對換空間管理

ManagementofSwappingSpace在含有對換功效OS中，通常把外存分為文件區(qū)和對換區(qū)。前者用于存放文件，因為通常文件都是較長久地駐留在外存上，故對文件區(qū)管理主要目標(biāo)，是提升文件存放空間利用率。為此，系統(tǒng)采取離散分配方式。后者則用于存放從內(nèi)存換出進(jìn)程，因為這些進(jìn)程在對換區(qū)中駐留時間是短暫，而對換操作又較頻繁，故對對換空間管理主要目標(biāo)，則是提升進(jìn)程換入、換出速度，為此，所應(yīng)采取管理策略是用連續(xù)分配方式，較少考慮外存中碎片問題。對對換區(qū)中空閑盤塊，可采取空閑區(qū)表或空閑區(qū)鏈進(jìn)行管理。對對換區(qū)空間分配與回收，與動態(tài)分區(qū)方式時內(nèi)存分配與回收方法雷同。522固定分區(qū)分配FixedPartitionAllocation第19頁5.3.3進(jìn)程換入與換出

SwapinandSwapoutofProcess一、進(jìn)程換出在進(jìn)程換出時，是將內(nèi)存中一些進(jìn)程調(diào)至對換區(qū)，以騰出內(nèi)存空間，換出過程分以下兩步：1.選出被換出進(jìn)程選擇標(biāo)準(zhǔn)：進(jìn)程狀態(tài)、優(yōu)先級、在內(nèi)存駐留時間2.換出過程非共享程序和數(shù)據(jù)段換出；共享程序和數(shù)據(jù)段換出。二、進(jìn)程換入當(dāng)對換進(jìn)程去執(zhí)行換入操作時，便去檢驗PCB集合中全部進(jìn)程狀態(tài)，從中找出“就緒且換出”狀態(tài)進(jìn)程。522固定分區(qū)分配FixedPartitionAllocation第20頁5.4分頁存放管理方式

PagedMemoryManagement連續(xù)分配方式會形成許多“碎片(fragmentation)”，即使可經(jīng)過“緊湊”方法將碎片拼接成可用大塊空間，但須為此付出很大開銷。假如允許將一個進(jìn)程直接分散地分配到許多不相鄰接分區(qū)中，就無須再進(jìn)行“緊湊”?；谶@一思想而產(chǎn)生了離散分配方式。依據(jù)離散分配時所用基本單位不一樣，又可分為三種：1.分頁存放管理(Pagedmemorymanagement)2.分段存放管理(Segmentedmemorymanagement)3.段頁式存放管理(Segmentdmemorymanagement)522固定分區(qū)分配FixedPartitionAllocation第21頁02213438690頁1頁2頁3頁4頁N頁5頁5圖5-16頁表作用012345678910用戶程序頁表頁號塊號內(nèi)存5.4.1分頁存放管理基本方法

Basicmethodsofpagedmemorymanagement

522固定分區(qū)分配FixedPartitionAllocation第22頁一、頁面和塊

PageandBlock把一個進(jìn)程邏輯地址空間分成若干個大小相等片，稱為頁面或頁(Page)。對應(yīng)地，內(nèi)存空間也分成頁相同大小若干個存放塊，或稱為物理塊(Block)或頁框(frame)。在為進(jìn)程分配內(nèi)存時，以塊為單位將進(jìn)程中若干頁分別裝入多個能夠不相鄰接塊中。因為進(jìn)程最終一頁經(jīng)常裝不滿一塊，而形成不可利用碎片--“頁內(nèi)碎片”。分頁存放管理方式中地址結(jié)構(gòu)：其中：P=INT[A/L],d=[A]MODL，這里A是邏輯地址，L是頁面大小，INT是整除函數(shù)，MOD是取余函數(shù)。比如L=1KB，A=2170B，則P=2，d=122。頁號P位移量d522固定分區(qū)分配FixedPartitionAllocation第23頁二、頁表PageTable在分頁系統(tǒng)中，允許將進(jìn)程每一頁離散地存放在內(nèi)存任一物理塊中，但系統(tǒng)應(yīng)能確保進(jìn)程正確運(yùn)行，即能在內(nèi)存中找到每個頁面所對應(yīng)物理塊。為此，系統(tǒng)又為每個進(jìn)程建立一張頁面映射表(PageMappingTable)，簡稱頁表。頁表作用是實現(xiàn)從頁號到物理塊號地址映射。即使在簡單分頁系統(tǒng)中，也常在頁表表項中設(shè)置一存取控制字段，用于對該存放塊中內(nèi)容進(jìn)行保護(hù)。控制字段格式：1bit：readonly/readandwrite；2bit：read/write、readonly、executeonlyetc。522固定分區(qū)分配FixedPartitionAllocation第24頁計算機(jī)類型頁面字節(jié)數(shù)IBMAS/400VAX系列NS32032Intel80386Motorola6803051251251240964096三、頁面大小選擇

SelectionofPageSize在分頁系統(tǒng)中頁面大小是由機(jī)器地址結(jié)構(gòu)所決定，亦即由硬件決定。對于某一個機(jī)器只能采取一個大小頁面。比如，IBMAS/400頁面大小為512B。頁面小，則內(nèi)存碎片小，內(nèi)存利用高；但每個進(jìn)程頁面多，頁表長，占內(nèi)存，頁面換入換出效率低。頁面大，則頁表短，提升換入換出效率，但碎片又大。所以，頁面大小應(yīng)選擇適中，普通在512B~4KB之間。當(dāng)前常見幾個計算機(jī)中所選取頁面大小以下表所表示：522固定分區(qū)分配FixedPartitionAllocation第25頁5.4.2

地址變換機(jī)構(gòu)

AddressTransformMechanism為了能將用戶用戶地址空間中邏輯地址，變換為內(nèi)存空間中物理地址，在系統(tǒng)中須設(shè)置地址變換機(jī)構(gòu)。其基本任務(wù)是實現(xiàn)從LA到PA轉(zhuǎn)換。因為頁內(nèi)地址和物理地址是一一對應(yīng)，比如，對于大小是1KB頁內(nèi)地址是0~1023，其對應(yīng)物理塊內(nèi)地址也是從0~1023，無須再進(jìn)行變換。地址變換機(jī)構(gòu)任務(wù)，實際上只是將邏輯地址中頁號，轉(zhuǎn)換為內(nèi)存中物理塊號。又因為頁面映射表作用就是用于實現(xiàn)從頁號到物理塊號變換，所以，地址變換任務(wù)是借助于頁表來完成。522固定分區(qū)分配FixedPartitionAllocation第26頁頁表始址1頁表長度頁內(nèi)地址頁號(3)b物理地址邏輯地址L頁表存放器PTR頁表+>越界中止塊號頁號0123圖5--17分頁系統(tǒng)地址變換機(jī)構(gòu)一、基本地址變換機(jī)構(gòu)

BasicAddressTransformMechanism522固定分區(qū)分配FixedPartitionAllocation第27頁二、含有快表地址變換機(jī)構(gòu)

AddressTransformMechanismwithFast-table使用上述方式進(jìn)行地址變換，使CPU每次要存取一個數(shù)據(jù)時，都要兩次訪問內(nèi)存。第一次是查頁表，找塊號，形成物理地址；第二次訪問內(nèi)存時，才從第一步所得地址中取得所需數(shù)據(jù)（或向此地址中寫入數(shù)據(jù)）。所以，將使計算機(jī)處理速度降低近1/2。可見，以此高昂代價來換取存放空間利用率提升，實屬得不償失。為了提升地址變換速度，可在地址變換機(jī)構(gòu)中，增設(shè)一個含有并行查詢能力特殊高速緩沖存放器(Cache)，又稱為“聯(lián)想存放器”(AssociativeMemory)或“快表”，用以存放當(dāng)前訪問那些頁表項。圖5-18示出了含有快表地址變換機(jī)構(gòu)。522固定分區(qū)分配FixedPartitionAllocation第28頁頁表始址

頁表長度頁內(nèi)地址頁號b

db物理地址邏輯地址L頁表存放器頁表+>越界中止塊號頁號圖5--18含有快表地