交通923、927操作系統(tǒng)電子-課件zgsosjiaoan

107一月2023北京交通大學計算機學院翟高壽主講教師：翟高壽（副教授）聯(lián)系電話：(辦)電子郵件：制作人：翟高壽制作單位：北京交通大學計算機學院《操作系統(tǒng)》207一月2023北京交通大學計算機學院翟高壽第四章存儲器管理4.1程序的裝入和鏈接4.2連續(xù)分配方式4.3基本分頁存儲管理方式4.4基本分段存儲管理方式4.5虛擬存儲器概念及關鍵技術4.6請求分頁存儲管理方式4.7請求分段存儲管理方式307一月2023北京交通大學計算機學院翟高壽用戶程序處理過程內(nèi)存裝入程序源程序裝入模塊鏈接程序庫編譯程序……目標模塊407一月2023北京交通大學計算機學院翟高壽程序的鏈接鏈接過程根據(jù)外部訪問符號名表，將經(jīng)過編譯或匯編得到的一組目標模塊以及它們所需要的庫函數(shù)，裝配成一個完整的裝入模塊關鍵問題修改相對地址變換外部調(diào)用符號鏈接方式靜態(tài)鏈接方式、裝入/運行時動態(tài)鏈接方式507一月2023北京交通大學計算機學院翟高壽程序鏈接示意圖目標模塊模塊ACALLB;Return;L-1相對地址0模塊BCALLC;Return;M-10模塊CCodeReturn;N-10裝入模塊模塊AJSR“L”;Return;L-1相對地址0模塊BJSR“L+M”;Return;L+M-1L模塊CCodeReturn;L+M+N-1L+M607一月2023北京交通大學計算機學院翟高壽鏈接方式比較靜態(tài)鏈接方式可執(zhí)行文件、難以實現(xiàn)“內(nèi)存”模塊共享裝入時動態(tài)鏈接便于軟件版本的修改和更新便于實現(xiàn)目標模塊為多個應用程序共享運行時動態(tài)鏈接將某些目標模塊的鏈接推遲到執(zhí)行時根據(jù)是否需要再完成707一月2023北京交通大學計算機學院翟高壽程序的裝入基本目標及相關問題由裝入程序?qū)⒀b入模塊載入到內(nèi)存裝入位置、地址變換（重定位）及時機裝入方式絕對裝入方式（單道程序環(huán)境）靜態(tài)可重定位裝入方式（多道程序環(huán)境）動態(tài)運行時裝入方式（運行中移動位置）關鍵概念相對地址、絕對地址、重定位及其寄存器807一月2023北京交通大學計算機學院翟高壽絕對裝入模塊和可重定位裝入模塊

JMP1424CodeLOAD1,2224

---------------

Data14242224絕對地址1024絕對裝入模塊PROGRAMJMPAddriCodeLOAD1,Addrj

------------------DATADataAddriAddrj符號地址目標模塊

JMP400CodeLOAD1,1200

---------------

Data4001200相對地址0可重定位裝入模塊907一月2023北京交通大學計算機學院翟高壽（靜態(tài)/動態(tài)）可重定位重定位程序裝入或執(zhí)行時對裝入模塊或目標程序中的指令及數(shù)據(jù)地址的修改過程靜態(tài)重定位由重定位裝入程序在將裝入模塊裝入內(nèi)存時一次性完成重定位需要連續(xù)存儲空間，裝入后不能移動動態(tài)重定位需要特殊硬件（地址變換機構）支持，以保證地址轉(zhuǎn)換不會影響指令的執(zhí)行速度便于動態(tài)鏈接和代碼共享1007一月2023北京交通大學計算機學院翟高壽動態(tài)重定位示意圖CPU10000相對地址2500+重定位寄存器內(nèi)存物理地址12500LOAD1,250036510000101001250015000LOAD1,2500365010025005000作業(yè)J1107一月2023北京交通大學計算機學院翟高壽第四章存儲器管理4.1程序的裝入和鏈接4.2連續(xù)分配方式4.3基本分頁存儲管理方式4.4基本分段存儲管理方式4.5虛擬存儲器概念及關鍵技術4.6請求分頁存儲管理方式4.7請求分段存儲管理方式1207一月2023北京交通大學計算機學院翟高壽4.2

連續(xù)分配方式4.2.1單一連續(xù)分配4.2.2固定分區(qū)分配4.2.3動態(tài)分區(qū)分配4.2.4可重定位分區(qū)分配4.2.5對換1307一月2023北京交通大學計算機學院翟高壽單一連續(xù)分配方式內(nèi)存劃分為系統(tǒng)區(qū)和用戶區(qū)整個用戶區(qū)為一個用戶獨占，僅駐留一道程序靜態(tài)鏈接和動態(tài)重定位技術、存儲器保護措施僅適用于單用戶、單任務操作系統(tǒng)中CPU界限寄存器基址寄存器邏輯地址<+是物理地址內(nèi)存否地址錯1407一月2023北京交通大學計算機學院翟高壽4.2

連續(xù)分配方式4.2.1單一連續(xù)分配4.2.2固定分區(qū)分配4.2.3動態(tài)分區(qū)分配4.2.4可重定位分區(qū)分配4.2.5對換1507一月2023北京交通大學計算機學院翟高壽固定分區(qū)分配方式用戶區(qū)分為若干固定區(qū)域每個分區(qū)可裝入一道作業(yè)分區(qū)劃分方法(等分/不等分)內(nèi)存分配與分區(qū)說明表可用于多道程序存儲管理A:B:C=150:300:500操作系統(tǒng)作業(yè)A作業(yè)B作業(yè)C存儲空間分配情況0300K450K750K1250K1750K分區(qū)號大小KB始址K狀態(tài)1150300已分配2300450已分配3500750已分配45001250已分配1607一月2023北京交通大學計算機學院翟高壽4.2

連續(xù)分配方式4.2.1單一連續(xù)分配4.2.2固定分區(qū)分配4.2.3動態(tài)分區(qū)分配4.2.4可重定位分區(qū)分配4.2.5對換1707一月2023北京交通大學計算機學院翟高壽動態(tài)分區(qū)分配方式基本思想根據(jù)進程的實際需求，動態(tài)地對內(nèi)存空間進行分配、回收及劃分關鍵問題分區(qū)分配用數(shù)據(jù)結構分區(qū)分配算法分區(qū)分配與回收操作碎片（零頭）處理1807一月2023北京交通大學計算機學院翟高壽分區(qū)分配用數(shù)據(jù)結構(A)空閑分區(qū)表分區(qū)號大小KB始址K狀態(tài)156200空閑2100332空閑378520空閑462690空閑5………(B)空閑分區(qū)鏈前向指針0后向指針0N+2N+2N個字節(jié)可用分區(qū)大小分區(qū)狀態(tài)1907一月2023北京交通大學計算機學院翟高壽分區(qū)分配算法首次適應算法FF要求空閑分區(qū)鏈以地址遞增次序鏈接查找開銷大，但有利于大作業(yè)分配循環(huán)首次適應算法首次適應+起始查尋指針+循環(huán)查找減少查找開銷，但不利于大作業(yè)分配最佳適應算法追求既能滿足要求且又最小的空閑分區(qū)要求空閑分區(qū)按大小遞增次序鏈接微觀意義上的最佳與宏觀上的零頭問題2007一月2023北京交通大學計算機學院翟高壽動態(tài)分區(qū)內(nèi)存分配流程從頭開始查找可變分區(qū)分配用數(shù)據(jù)結構開始m.size≧u.size?檢索完否?m.size-u.size≦size?從當前分區(qū)劃出u.size大小的分區(qū)是否否否修改分配用數(shù)據(jù)結構并執(zhí)行分配是返回是檢索下一分區(qū)信息移出當前分區(qū)2107一月2023北京交通大學計算機學院翟高壽動態(tài)分區(qū)內(nèi)存回收情況F1回收區(qū)回收區(qū)F2F1回收區(qū)F2回收區(qū)2207一月2023北京交通大學計算機學院翟高壽動態(tài)分區(qū)內(nèi)存回收流程順序查找分配用數(shù)據(jù)結構直至找到某分區(qū)之m.addr>collected.addr或m.size=0開始是返回回收區(qū)與前一空閑區(qū)合并同時修正分配用數(shù)據(jù)結構非第一分區(qū)且與前一空閑區(qū)相鄰?否非最末分區(qū)且與后一空閑區(qū)相鄰?回收區(qū)與后一空閑區(qū)合并同時修正分配用數(shù)據(jù)結構與后一空閑區(qū)相鄰?與后一空閑區(qū)合并同時修正分配用數(shù)據(jù)結構是是回收區(qū)collected.size=0?否插入回收區(qū)并調(diào)整分配用數(shù)據(jù)結構否是2307一月2023北京交通大學計算機學院翟高壽4.2

連續(xù)分配方式4.2.1單一連續(xù)分配4.2.2固定分區(qū)分配4.2.3動態(tài)分區(qū)分配4.2.4可重定位分區(qū)分配4.2.5對換2407一月2023北京交通大學計算機學院翟高壽動態(tài)重定位分區(qū)分配方式緊湊連續(xù)分配要求程序裝入內(nèi)存空間的連續(xù)性分區(qū)分配產(chǎn)生的零頭/碎片問題通過移動把多個分散拼接成大分區(qū)用戶程序內(nèi)存地址變化及地址修正問題動態(tài)重定位動態(tài)運行時裝入方式及重定位寄存器動態(tài)重定位分區(qū)分配算法動態(tài)分配分區(qū)算法+緊湊功能2507一月2023北京交通大學計算機學院翟高壽緊湊（拼接）技術操作系統(tǒng)用戶程序220KB用戶程序532KB用戶程序325KB用戶程序635KB操作系統(tǒng)用戶程序2用戶程序5用戶程序3用戶程序6112KB緊湊前緊湊后2607一月2023北京交通大學計算機學院翟高壽動態(tài)重定位分區(qū)分配流程從頭開始查找可變分區(qū)分配用數(shù)據(jù)結構開始找到不小于u.size的空閑分區(qū)否?空閑分區(qū)總和不小于u.size?進行拼湊形成連續(xù)空閑區(qū)修改分配用數(shù)據(jù)結構是否否按動態(tài)分區(qū)方式進行分配，修改分配用數(shù)據(jù)結構返回是2707一月2023北京交通大學計算機學院翟高壽4.2

連續(xù)分配方式4.2.1單一連續(xù)分配4.2.2固定分區(qū)分配4.2.3動態(tài)分區(qū)分配4.2.4可重定位分區(qū)分配4.2.5對換2807一月2023北京交通大學計算機學院翟高壽多道程序環(huán)境下的對換對換的概念及意義內(nèi)存（進程、程序、數(shù)據(jù)）外存提高內(nèi)存利用率對換實現(xiàn)機制UNIX：對換進程（中級調(diào)度）對換實現(xiàn)方式進程對換：分時系統(tǒng)頁面/分段對換：虛擬存儲技術2907一月2023北京交通大學計算機學院翟高壽對換空間的管理文件區(qū)和對換區(qū)功能、管理目標及管理方式對換區(qū)使用情況數(shù)據(jù)結構空閑分區(qū)表/鏈（盤塊為基本單位）對換區(qū)分配與回收操作分配算法分配操作回收操作3007一月2023北京交通大學計算機學院翟高壽進程的換出和換入進程的換出被換出進程的選擇（進程狀態(tài)+優(yōu)先級+內(nèi)存駐留時間）換出過程（換出非共享或不再共享的程序及數(shù)據(jù)段對換空間申請換出內(nèi)存釋放內(nèi)存分配數(shù)據(jù)結構及PCB修改）進程的換入被換入進程的選擇（進程狀態(tài)+換出時間）換入過程（內(nèi)存申請換入

PCB修改）3107一月2023北京交通大學計算機學院翟高壽