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

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

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

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

DynamicPartitionAllocation動(dòng)態(tài)分區(qū)分配是依據(jù)進(jìn)程實(shí)際需要，動(dòng)態(tài)地為之分配連續(xù)內(nèi)存空間。在實(shí)現(xiàn)可變分區(qū)存放管理方式時(shí)，必須處理下述三個(gè)問(wèn)題：（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頁(yè)序號(hào)1分區(qū)大小(kb)分區(qū)始址(k)狀態(tài)12346424403044132210270可用可用可用可用5圖5--7空閑分區(qū)說(shuō)明表N個(gè)字節(jié)可用前向指針N+20后向指針N+20圖5--8空閑鏈結(jié)構(gòu)522固定分區(qū)分配FixedPartitionAllocation第4頁(yè)二.分區(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ū)分布均勻，從而降低了查找開銷；但會(huì)缺乏大空閑區(qū)。（3）最正確適配策略（Best-fitstrategy）

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

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

PartitionAllocationOperation1、分配內(nèi)存(MemoryAllocation)u.size:請(qǐng)求分區(qū)大?。?/p>

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

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

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

回收區(qū)F2

回收區(qū)F1F1

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

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

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

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

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

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

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

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

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

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

SwappinginMulti-programmingEnvironment

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

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

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

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

Basicmethodsofpagedmemorymanagement

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

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

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

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

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

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

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

頁(yè)表長(zhǎng)度頁(yè)內(nèi)地址頁(yè)號(hào)b

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