操作系統(tǒng)四版課件3

1、3.13.23.3本章講述內(nèi)容：本章講述內(nèi)容：3.43.53.6基本概念基本概念內(nèi)存儲器內(nèi)存儲器（簡稱內(nèi)存、主存、物理存儲器）（簡稱內(nèi)存、主存、物理存儲器） 處理機(jī)能直接訪問的存儲器。用來存放系處理機(jī)能直接訪問的存儲器。用來存放系統(tǒng)和用戶的程序和數(shù)據(jù)，其特點(diǎn)是存取速度快，存統(tǒng)和用戶的程序和數(shù)據(jù)，其特點(diǎn)是存取速度快，存儲方式是以新?lián)Q舊，斷電信息丟失。儲方式是以新?lián)Q舊，斷電信息丟失。外存儲器外存儲器（簡稱外存、輔助存儲器）（簡稱外存、輔助存儲器） 處理機(jī)不能直接訪問的存儲器。用來存放處理機(jī)不能直接訪問的存儲器。用來存放用戶的各種信息，存取速度相對內(nèi)存而言要慢得多用戶的各種信息，存取速度相對內(nèi)存而言

2、要慢得多，但它可用來長期保存用戶信息。在文件系統(tǒng)中介，但它可用來長期保存用戶信息。在文件系統(tǒng)中介紹。紹。存儲器分類存儲器分類指導(dǎo)思想：利用輔存（如磁盤、磁帶等）提指導(dǎo)思想：利用輔存（如磁盤、磁帶等）提供的大容量存儲空間，存放準(zhǔn)備運(yùn)行的程序供的大容量存儲空間，存放準(zhǔn)備運(yùn)行的程序和數(shù)據(jù)，當(dāng)需要時或主存空間允許時，隨時和數(shù)據(jù)，當(dāng)需要時或主存空間允許時，隨時將它們讀入主存儲器。將它們讀入主存儲器。信息的二級存儲信息的二級存儲 目前，計算機(jī)采用的都是以存儲器為中心的體系結(jié)構(gòu)。存儲器負(fù)責(zé)存放整個系統(tǒng)的程序與數(shù)據(jù)，是重要的系統(tǒng)資源。.磁帶磁盤主存儲器高速緩存寄存器快慢存取速度小大容量昂貴便宜價格. 在考慮計

3、算機(jī)存儲器的設(shè)計時，必須顧及“價格”、“容量”、“訪問時間”這三個重要特性。各種實(shí)現(xiàn)技術(shù)間往往有以下的關(guān)系：存取時間越快，每“位”的價格就越高；容量越大，每“位”的價格就越低；容量越大，存取速度就越慢。. 只能在“價格”、“容量”、“訪問時間”三者間尋求折中，采用存儲器的層次結(jié)構(gòu) 。這時，從上往下就有：每“位”的價格遞減；存儲容量遞增；存取時間遞增。 . 這種層次結(jié)構(gòu)中，容量較大、價格便宜的慢速存儲器（如磁盤），可作為容量較小、價格較貴的快速存儲器的后備。這正是存儲管理中虛擬存儲技術(shù)的實(shí)現(xiàn)基礎(chǔ)。 這種層次結(jié)構(gòu)中，CPU可直接到寄存器、高速緩沖存儲器、內(nèi)存儲器這三層上訪問數(shù)據(jù)，不能直接到磁盤和磁

4、帶上訪問數(shù)據(jù)，那里的數(shù)據(jù)只有轉(zhuǎn)移到內(nèi)存儲器后，才能接受CPU的處理。.高速緩沖存儲器CPU主存儲器字傳送塊傳送 相對于內(nèi)存，高速緩存容量小、存取速度快。在它里面只存放內(nèi)存中的一小部分?jǐn)?shù)據(jù)內(nèi)容。 . 在CPU與內(nèi)存間，可安排“高速緩沖存儲器”，簡稱為“高速緩存”。. 當(dāng)CPU試圖訪問內(nèi)存中的某一個字時，就總是先檢查該字是否在高速緩存中。如果在，就直接將它從高速緩存?zhèn)魉徒oCPU；如果不在，則先把內(nèi)存中包含此字在內(nèi)的一塊數(shù)據(jù)讀入高速緩存，然后再把所需的字從高速緩存?zhèn)魉徒oCPU。 槽號標(biāo)簽012C-10123塊塊（K個字）2n-1塊（K個字）地址高速緩沖存儲器主存儲器 內(nèi)存和高速緩存間是以“塊”為單位

5、傳遞數(shù)據(jù)的，高速緩存與CPU之間則是以“字”為單位傳遞數(shù)據(jù)的。 . 當(dāng)CPU需存取內(nèi)存中某塊里的某字，而那塊不在存儲槽中，就把那塊傳到一槽里。高速緩存中的槽都有標(biāo)簽，用來標(biāo)識這個存儲槽在當(dāng)前存放的是內(nèi)存中的哪一塊。 存儲擴(kuò)充的含義是通過技術(shù)手段，給用戶造成有一個非常大的內(nèi)存的虛幻感覺，但其實(shí)并沒有擴(kuò)大實(shí)際內(nèi)存的容量。存儲管理若能做到這種意義下的存儲擴(kuò)充，那么就能使用戶程序的規(guī)模不受內(nèi)存實(shí)際容量的限制。存儲擴(kuò)充無疑是一件非常好的事情。這是虛擬存儲要討論的話題。1. 這是存儲管理必須承擔(dān)的任務(wù)，它應(yīng)該隨時記錄內(nèi)存的使用情況；根據(jù)用戶程序的需要分配存儲區(qū)；在用戶程序運(yùn)行完后，及時收回存儲區(qū)，以提高內(nèi)

6、存的使用效率。2. 存儲共享是指允許多個進(jìn)程訪問內(nèi)存中的同一部分，這是提高存儲利用率的一種措施。. 存儲保護(hù)涉及兩個問題，一是確保用戶進(jìn)程的程序不侵犯操作系統(tǒng)；二是確保兩個用戶程序之間不相互干擾。.3. 為適應(yīng)多道程序設(shè)計環(huán)境，為使內(nèi)存中的程序能夠移動，存儲管理必須對用戶程序邏輯地址空間中的地址實(shí)施重新定位，以保證進(jìn)程程序的正確運(yùn)行。4. 把用戶程序指令中的相對地址變換成為所在絕對地址空間中的絕對地址的過程，稱為“地址重定位地址重定位”。 1.2.01001KB2KB30003KBXXXXXXcall 100用戶程序A的相對地址空間XXXXXXcall 100內(nèi)存儲器020KB20KB+100

7、21KB22KB20KB+300023KB操作系統(tǒng)XXXXXXXcall 20580內(nèi)存儲器020KB20KB+10021KB22KB20KB+300023KB操作系統(tǒng)XXXXXXcall 22628內(nèi)存儲器022KB22KB+10023KB24KB22KB+300025KB操作系統(tǒng)20KB.絕對地址(或物理地址).絕對地址空間(或物理地址空間).相對地址(或邏輯地址).相對地址空間(或邏輯地址空間)單元地址：單元地址：內(nèi)存儲器由一個個存儲單元組成。一個存儲單元內(nèi)存儲器由一個個存儲單元組成。一個存儲單元存放存放若干若干個二進(jìn)制的位（個二進(jìn)制的位（bitbit），），8 8個二進(jìn)制的位被稱做一個

8、二進(jìn)制的位被稱做一個字節(jié)（個字節(jié)（ByteByte）。內(nèi)存中的存儲單元按一定的順序號進(jìn)行）。內(nèi)存中的存儲單元按一定的順序號進(jìn)行編號，每個單元對應(yīng)的編號，稱為該單元的單元地址。編號，每個單元對應(yīng)的編號，稱為該單元的單元地址。物理地址：物理地址：在操作系統(tǒng)中，把單元地址稱為內(nèi)存儲器在操作系統(tǒng)中，把單元地址稱為內(nèi)存儲器的物理地址，也叫做的物理地址，也叫做絕對地址絕對地址。物理地址空間：物理地址空間：從任何一個絕對地址開始的一段連續(xù)的從任何一個絕對地址開始的一段連續(xù)的內(nèi)存空間，被稱為內(nèi)存空間，被稱為物理地址空間，物理地址空間，也稱為也稱為絕對地址絕對地址空間空間。邏輯地址空間邏輯地址空間：用戶程序產(chǎn)生

9、出一個相對于用戶程序產(chǎn)生出一個相對于“0”0”編編址的地址空間，這個地址空間被稱為是址的地址空間，這個地址空間被稱為是用戶程序用戶程序的的邏輯地址空間也稱為邏輯地址空間也稱為相對地址空間相對地址空間。邏輯地址邏輯地址：在邏輯地址空間中的地址被稱為在邏輯地址空間中的地址被稱為邏輯地址邏輯地址也叫做也叫做相對地址相對地址 。 要求編程人員熟悉內(nèi)存使用情況，程序設(shè)計時要極小心地對待指令中的地址，不能夠出現(xiàn)任何差錯，否則后果不堪設(shè)想；1. 即在程序裝入內(nèi)存之前，程序指令中的地址就已經(jīng)是絕對地址，已經(jīng)正確地反映了它將要進(jìn)入的存儲區(qū)位置。. 優(yōu)點(diǎn)：程序中的邏輯地址與實(shí)際內(nèi)存中的物理地址完全相同。因此在程序

10、執(zhí)行前不需對程序指令中的地址再進(jìn)行任何調(diào)整和修改，裝入到指定內(nèi)存位置就可運(yùn)行。.不適用于多道程序設(shè)計環(huán)境。缺點(diǎn)：(1)(2)(3)(4)程序進(jìn)入內(nèi)存后，不能做任何移動，只能固定在這個存儲區(qū)內(nèi)；對程序做任何微小修改，都可能會牽扯到程序整體的變動，費(fèi)工耗時；2. 在多道程序設(shè)計環(huán)境下，用戶事先無法、也不愿意知道自己的程序會被裝入到內(nèi)存的什么位置，他們只是向系統(tǒng)提供相對于“0”編址的程序。. 操作系統(tǒng)要有一個“重定位裝入程序重定位裝入程序”，功能是：一根據(jù)當(dāng)前內(nèi)存使用情況，為欲裝入的二進(jìn)制目標(biāo)程序分配所需的存儲區(qū)；二根據(jù)所分配的存儲區(qū)，對程序中的指令地址進(jìn)行重新計算和修改；三將重定位后的二進(jìn)制目標(biāo)程

11、序裝入到指定的存儲區(qū)中。 靜態(tài)重定位由軟件（重定位裝入程序）實(shí)現(xiàn)，無須硬件提供支持； 靜態(tài)重定位的特點(diǎn)靜態(tài)重定位是在程序運(yùn)行之前完成地址重定位工作的； 地址重定位的工作是在程序裝入時被一次集中完成的； 物理地址空間里的目標(biāo)程序與原邏輯地址空間里的目標(biāo)程序面目已不相同，前者是后者進(jìn)行地址調(diào)整后的結(jié)果 ； 實(shí)施靜態(tài)重定位后，位于物理地址空間里的用戶程序不能在內(nèi)存中移動，除非再重新進(jìn)行地址定位 ；. 采用這種重定位方式，用戶向裝入程序提供相對于“0”編址的二進(jìn)制目標(biāo)程序，無需關(guān)注程序具體的裝入位置。通過重定位裝入程序的加工，目標(biāo)程序進(jìn)入分配給它的物理地址空間，程序指令中的地址也都被修改為正確反映該空

12、間的情形。因為這種地址重定位是在程序執(zhí)行前完成的，因此稱為地址的“靜態(tài)重定位靜態(tài)重定位” 。 .(1)(2)(3)(4)(5)(6) 適用于多道程序設(shè)計環(huán)境。 3. 對用戶程序?qū)嵭械刂返撵o態(tài)重定位后，定位后的程序就被“釘死”在了它的物理地址空間里，不能做任何移動。 . 將地址定位的時間推遲到程序執(zhí)行時再進(jìn)行，這就是地址“動態(tài)重定位”方式。在對程序?qū)嵭袆討B(tài)重定位時需要硬件的支持。 為阻止用戶程序指令中的地址闖入操作系統(tǒng)所占用的區(qū)域，在CPU里設(shè)置一個用于存儲保護(hù)的專用寄存器：“界限寄存器”。 . 內(nèi)存用戶區(qū)又被分為“使用區(qū)”和“空閑區(qū)”兩部分，分配給了用戶、但又未使用的區(qū)域稱為“內(nèi)部碎片”。內(nèi)部

13、碎片的存在是對內(nèi)存資源的一種浪費(fèi)。 1.2.單一連續(xù)分區(qū)存儲管理的基本思想單一連續(xù)分區(qū)存儲管理的基本思想單一連續(xù)區(qū)存儲管理的特點(diǎn)單一連續(xù)區(qū)存儲管理的特點(diǎn) 總體上把內(nèi)存儲器分為兩個分區(qū)：一個分區(qū)固定分配給操作系統(tǒng)使用；另一個分配給用戶使用，稱為“用戶區(qū)” 。.作業(yè)3作業(yè)2作業(yè)1操作系統(tǒng)用戶區(qū)內(nèi)存0ab操作系統(tǒng)使用區(qū)內(nèi)存0ab空閑區(qū)用戶區(qū)c操作系統(tǒng)使用區(qū)內(nèi)存0ab空閑區(qū)ca界限寄存器系統(tǒng)總是把整個用戶區(qū)分配給一個用戶使用 。這種系統(tǒng)只適用于單用戶（或單道）的情況。 進(jìn)入內(nèi)存作業(yè)獨(dú)享系統(tǒng)中的所有資源，包括內(nèi)存的整個用戶區(qū)。 采用這種存儲分配策略時，將對用戶程序?qū)嵭徐o態(tài)重定位。 . 作業(yè)比用戶區(qū)小時，

14、就會形成碎片，造成內(nèi)存儲器資源的浪費(fèi)。 3.4. 每次只能一個作業(yè)進(jìn)入內(nèi)存，故不適宜多道程序設(shè)計，系統(tǒng)的工作效率不高，資源利用率低下。 若用戶作業(yè)的相對地址空間比用戶區(qū)大，該作業(yè)就無法運(yùn)行。 “覆蓋”是早期為程序設(shè)計人員提供的擴(kuò)充內(nèi)存的技術(shù)，中心思想是允許作業(yè)的若干個程序段使用同一個存儲區(qū)域，共用的存儲區(qū)被稱為“覆蓋區(qū)”。 MAIN(10KB)A(50KB)B(30KB)C(30KB)D(20KB)E(40KB)MAIN(10KB)A(50KB)B(30KB)C(30KB)D(20KB)E(40KB)0180KB連接裝配10KB50KB40KB內(nèi)存MAINA或BC或D或E5. 對換技術(shù)對換技術(shù)

15、作業(yè)1作業(yè)2作業(yè)3輔助存儲器內(nèi)存儲器操作系統(tǒng)用戶區(qū)換出換入 基本思想：將作業(yè)都存放在輔存。每次只讓其中的一個進(jìn)入內(nèi)存投入運(yùn)行。當(dāng)運(yùn)行中提出輸入輸出請求或分配給的時間片用完時，就把這個程序從內(nèi)存“換出”到輔存，把輔存里的另一個作業(yè)“換入”運(yùn)行 ，產(chǎn)生出“多道”的效果。 1. 所謂“固定分區(qū)固定分區(qū)”存儲管理，是指預(yù)先把內(nèi)存的用戶區(qū)劃分成若干個連續(xù)的分區(qū)，它們的尺寸可以相同，也可以不同。劃分后，內(nèi)存中分區(qū)的個數(shù)以及每個分區(qū)的尺寸保持不變。每個分區(qū)里只允許裝入一個作業(yè)運(yùn)行。 2.操作系統(tǒng)第1分區(qū)(8KB)第2分區(qū)(32KB)第3分區(qū)(64KB)第4分區(qū)(132KB)0256KB20KBABCDEF操

16、作系統(tǒng)第1分區(qū)(8KB)第2分區(qū)(32KB)第3分區(qū)(64KB)第4分區(qū)(132KB)0256KB20KBABCDEF.每個分區(qū)設(shè)置一個后備作業(yè)隊列 .多個分區(qū)只設(shè)置一個后備作業(yè)隊列 一個作業(yè)到達(dá)時，總是進(jìn)入到“能容納該作業(yè)的最小分區(qū)”的那個后備作業(yè)隊列里去排隊。 當(dāng)某個分區(qū)空閑時，統(tǒng)一都到這一個隊列里去挑選作業(yè)，裝入運(yùn)行。 缺點(diǎn) ：可能會產(chǎn)生有的分區(qū)隊列忙碌、有的分區(qū)隊列閑置的情形。作業(yè)尺寸比任何一個分區(qū)的長度都大時，就無法運(yùn)行。 .3. 分區(qū)空閑時，若它的隊列非空，就把該分區(qū)分配給隊列的第一個作業(yè)使用；作業(yè)運(yùn)行完畢，收回該分區(qū)，進(jìn)行下一次分配。 每個分區(qū)設(shè)置一個后備作業(yè)隊列 多個分區(qū)只設(shè)置

17、一個后備作業(yè)隊列 在任何一個分區(qū)釋放時，就根據(jù)分配方案從該隊列里挑選一個作業(yè)裝入運(yùn)行。 4.在固定分區(qū)存儲管理中，實(shí)行靜態(tài)重定位實(shí)行靜態(tài)重定位。. 在固定分區(qū)存儲管理中，要防止用戶程序?qū)Σ僮飨到y(tǒng)的侵?jǐn)_，也要防止用戶程序間的侵?jǐn)_。因此設(shè)置一對專用寄存器：“低界限寄存器低界限寄存器”和和“高界高界限寄存器限寄存器” ，用于存儲保護(hù) 。地址重定位存儲保護(hù)0abcdab作業(yè)1作業(yè)2作業(yè)3第1分區(qū)第2分區(qū)第3分區(qū)操作系統(tǒng)低界限寄存器高界限寄存器CPU5.是最簡單的、具有“多道”色彩的存儲管理方案。 .作業(yè)程序一次性全部裝入分配給它的連續(xù)分區(qū)。 .實(shí)行的是靜態(tài)重定位。 .會產(chǎn)生內(nèi)部碎片，引起內(nèi)存資源的浪費(fèi)

18、。 外部碎片：存儲管理中，把那些無法分配出去滿足作業(yè)存儲請求的空閑區(qū)稱為“外部碎片外部碎片”。 1.2. 在作業(yè)要求裝入內(nèi)存時，若當(dāng)時內(nèi)存中有足夠的存儲空間滿足該作業(yè)的需求，那就劃分出一個與作業(yè)相對地址空間同樣大小的分區(qū)分配給它使用。 操作系統(tǒng)空閑區(qū)作業(yè)A(15KB)作業(yè)B(20KB)作業(yè)C(10KB)內(nèi)存操作系統(tǒng)空閑區(qū)作業(yè)A(15KB)作業(yè)B(20KB)內(nèi)存操作系統(tǒng)空閑區(qū)作業(yè)A(15KB)內(nèi)存操作系統(tǒng)空閑區(qū)作業(yè)A(15KB)內(nèi)存作業(yè)B(20KB)作業(yè)C(10KB). 內(nèi)部碎片：存儲管理中，把分配給了用戶而用戶未用的存儲區(qū)稱為“內(nèi)部碎內(nèi)部碎片片”。3. .采用地址動態(tài)重定位技術(shù)，使程序能在內(nèi)存

19、中移動，為空閑區(qū)合并提供保證； . 記住各分區(qū)的使用情況，當(dāng)一個分區(qū)被釋放時，要能判定它的前、后分區(qū)是否為空閑區(qū)。若是空閑區(qū)，就進(jìn)行合并，形成一個大的空閑區(qū)。 .給出分區(qū)分配算法，在有多個空閑區(qū)都滿足作業(yè)的存儲請求時，決定分配哪一個。 . 靜態(tài)重定位是在程序運(yùn)行之前完成地址轉(zhuǎn)換的；動態(tài)重定位卻是將地址轉(zhuǎn)換的時刻推遲到指令執(zhí)行時進(jìn)行。 實(shí)行靜態(tài)重定位，原來的指令地址部分被修改了；實(shí)行動態(tài)重定位，只是按照所形成的地址去執(zhí)行這條指令，并不對指令本身做任何修改。 靜態(tài)重定位是在裝入時一次集中地把程序指令中所有要轉(zhuǎn)換的地址全部加以轉(zhuǎn)換；而動態(tài)重定位則是每執(zhí)行一條指令時，對其地址加以轉(zhuǎn)換。 靜態(tài)重定位是由

20、軟件完成地址轉(zhuǎn)換工作的；動態(tài)重定位則由一套硬件提供的地址轉(zhuǎn)換機(jī)構(gòu)來完成。 1.2. 把相對地址空間中的用戶作業(yè)程序“原封不動” 地裝入到分配給它的絕對地址空間中去。執(zhí)行某條指令時，才根據(jù)當(dāng)前程序所在區(qū)域，對指令中的地址進(jìn)行重定位。即指令中地址的轉(zhuǎn)換是在程序執(zhí)行時動態(tài)完成的，故稱為地址的“動態(tài)重定位動態(tài)重定位”。 0用戶作業(yè)A的相對地址空間XXXXXX1001KB2KB3000call 1003KB0XXXXXX22KB+10023KB24KB22KB+3000call 10025KB20KB22KB22KB定位寄存器2262822528操作系統(tǒng)內(nèi)存.由地址變換線路取出 一是調(diào)度到某作業(yè)時一是調(diào)

21、度到某作業(yè)時，若系統(tǒng)的每個空閑區(qū)尺寸都小于它的需要，但空閑區(qū)總存儲量大于它的存儲請求，于是進(jìn)行空閑區(qū)合并，得到一個大的空閑區(qū)，滿足該作業(yè)的需要；一是只要有作業(yè)運(yùn)行完一是只要有作業(yè)運(yùn)行完歸還所占用的存儲區(qū)，系統(tǒng)就進(jìn)行空閑區(qū)的合并。 釋放區(qū)的前、后鄰接分區(qū)都是空閑區(qū)。因此，釋放區(qū)應(yīng)該和前、后兩個鄰接的空閑區(qū)合并成一個新的空閑區(qū)。 釋放區(qū)的前鄰接分區(qū)是已分配區(qū)，后鄰接分區(qū)是空閑區(qū)。因此，釋放分區(qū)應(yīng)該和后鄰接的空閑區(qū)合并成一個新的空閑區(qū)。 釋放分區(qū)的前鄰接分區(qū)是空閑區(qū)，后鄰接分區(qū)是已分配區(qū)。釋放區(qū)應(yīng)該和前鄰接的空閑區(qū)合并成一個新的空閑區(qū)。 釋放分區(qū)的前、后鄰接分區(qū)都是已分配區(qū)，沒有合并的問題存在。 1

22、.2.已分配區(qū)空閑區(qū)釋放分區(qū)空閑區(qū)已分配區(qū)釋放分區(qū)空閑區(qū)空閑區(qū)釋放分區(qū)已分配區(qū)已分配區(qū)釋放分區(qū). 若有作業(yè)運(yùn)行結(jié)束，則根據(jù)作業(yè)名到已分配表里找到它的表目項，將該項的 “狀態(tài)”改為“空”，隨之在空閑區(qū)表里尋找一個狀態(tài)為“空”的表目項，把釋放分區(qū)的信息填入，并將表目項狀態(tài)改為“空閑”。 作業(yè)提出存儲需求時，查空閑區(qū)表里狀態(tài)為“空閑”的表目項。若該項的尺寸能滿足所求，就將它一分為二：分配出去的那部分在已分配表里找一個狀態(tài)為“空” 的表目項進(jìn)行登記，剩下的部分仍在空閑區(qū)表里占據(jù)一個表目項。 1. 設(shè)置兩張表：“已分配表”和“空閑區(qū)表”。其中“序號”是表目項的順序號，“起始地址”、“尺寸”、“狀態(tài)” 都

23、是該分區(qū)的相應(yīng)屬性。由于系統(tǒng)中分區(qū)的數(shù)目是變化的，因此每張表格中的表目項數(shù)要足夠的多，暫時不用的表目項的狀態(tài)被設(shè)為“空”。 內(nèi)存操作系統(tǒng)空閑區(qū)(8KB)作業(yè)B(32KB)空閑區(qū)(32KB)作業(yè)D(120KB)空閑區(qū)(300KB)序號起始地址尺寸狀態(tài)12345020KB28KB60KB92KB212KB512KB28KB32KB作業(yè)B空空空92KB120KB作業(yè)D序號起始地址尺寸狀態(tài)1234560KB32KB作業(yè)B空閑空空作業(yè)D20KB8KB212KB300KB已分配表空閑區(qū)表. 把內(nèi)存中每個空閑分區(qū)視為一個整體，在它里面開辟出兩個單元，一個存放該分區(qū)的長度（size），一個存放它下一個空閑分區(qū)

24、的起址（next），操作系統(tǒng)開辟一個單元，存放第1個空閑分區(qū)的起址，這個單元稱為“鏈?zhǔn)字羔槨?。最后一個空閑分區(qū)的next里存放標(biāo)志“NULL” 。這樣一來，系統(tǒng)里所有空閑分區(qū)被next連接成一個鏈表。從鏈?zhǔn)字羔槼霭l(fā)，順著各個空閑分區(qū)的next往下走，就能到達(dá)每一個空閑分區(qū)。 20KB8KB60KB2.sizenext空閑區(qū)長度下一個空閑區(qū)起址空閑區(qū)8KB212KB32KBNULL300KB20KB60KB空閑區(qū)(8KB)32KB212KB空閑區(qū)(32KB)300KBNULL空閑區(qū)(300KB)作業(yè)B(32KB)作業(yè)D(120KB)020KB28KB60KB92KB212KB512KB內(nèi)存內(nèi)存操

25、作系統(tǒng)鏈?zhǔn)字羔樻準(zhǔn)字羔?基本思想 對提出的任何一個存儲請求，從空閑區(qū)鏈表首指針開始查看一個個空閑區(qū)。若有滿足要求的，按尺寸分配，調(diào)整next指針；若到達(dá)NULL未見滿足要求，則分配失敗。 存儲分配.存儲釋放作業(yè)完成任務(wù)后，將占用的存儲區(qū)釋放，鏈入空閑區(qū)鏈表（要調(diào)整指針和空閑區(qū)合并）。 在每個空閑分區(qū)里，即存放下一個空閑區(qū)起址next，也存放它的上一個空閑區(qū)起址（prior）的信息。這樣，通過雙向鏈表，就可以方便地由next找到一個空閑區(qū)的下一個空閑區(qū)，也可以由prior找到一個空閑區(qū)的上一個空閑區(qū)。 空閑區(qū)(300KB)sizenext.3.基本思想20KB空閑區(qū)長度下一個空閑區(qū)起址空閑區(qū)30

26、0KBNULL作業(yè)B(32KB)作業(yè)D(120KB)020KB28KB60KB92KB212KB512KB內(nèi)存操作系統(tǒng)鏈?zhǔn)字羔榩rior上一個空閑區(qū)起址空閑區(qū)(32KB)32KB212KB60KB20KB空閑區(qū)(8KB)8KB60KBNULL.存儲合并 把釋放區(qū)鏈入空閑區(qū)雙向鏈表時，若通過它的prior發(fā)現(xiàn)該釋放區(qū)的前面一個空閑區(qū)的起址加上長度，等于釋放區(qū)的起址，那么說明它前面的空閑區(qū)與它直接鄰接，應(yīng)該把這個釋放區(qū)與原先的空閑區(qū)合并。若釋放區(qū)起址加上長度正好等于next所指的下一個空閑區(qū)的起址，那么說明它與后面的空閑區(qū)直接鄰接，應(yīng)該把這個釋放區(qū)與原先的空閑區(qū)合并。 .空閑區(qū)的兩種組織形式 若將

27、每個空閑分區(qū)按其起址由小到大排列在鏈表里，則把這種組織稱為“地址法地址法”；若按每個空閑分區(qū)的長度由小到大排列在鏈表里，則把這種組織稱為“尺寸法尺寸法”。 最先適應(yīng)算法：最先適應(yīng)算法：總是把最先找到的、滿足存儲需求的那個空閑分區(qū)作為分配的對象。 出發(fā)點(diǎn)盡量減少查找時間，有可能把大的空閑區(qū)分割許多小的分區(qū)，對大作業(yè)不利出發(fā)點(diǎn)盡量減少查找時間，有可能把大的空閑區(qū)分割許多小的分區(qū)，對大作業(yè)不利。1.2. 最佳適應(yīng)算法：最佳適應(yīng)算法：總是從當(dāng)前所有空閑區(qū)中找出一個能夠滿足存儲需求的、最小的空閑分區(qū)作為分配的對象 。盡可能不把大的空閑區(qū)分割許多小的分區(qū)，保證大作業(yè)需要。盡可能不把大的空閑區(qū)分割許多小的分

28、區(qū)，保證大作業(yè)需要。 最壞適應(yīng)算法：最壞適應(yīng)算法：總是從當(dāng)前所有空閑區(qū)中找出一個能夠滿足存儲需求的、最大的空閑分區(qū)作為分配的對象。出發(fā)點(diǎn)是照顧中、小作業(yè)的需求。出發(fā)點(diǎn)是照顧中、小作業(yè)的需求。.3.作業(yè)一次性地全部裝入到一個連續(xù)的存儲分區(qū)中。 . 分區(qū)是按照作業(yè)對存儲的需求劃分的，因此不會出現(xiàn)內(nèi)部碎片這樣的存儲浪費(fèi)。 .為確保作業(yè)能夠在內(nèi)存中移動，要由硬件支持實(shí)行指令地址的動態(tài)重定位。 . 只要作業(yè)的存儲需求大于系統(tǒng)提供的整個用戶區(qū)，該作業(yè)就無法投入運(yùn)行。 . 有可能出現(xiàn)極小的分區(qū)暫時分配不出去的情形，產(chǎn)生外部碎片。 由于是通過移動程序來達(dá)到分區(qū)合并的目的，勢必增加系統(tǒng)在這方面的時間投入與開銷。

29、 地址法地址法 尺寸法尺寸法 最佳適應(yīng)算法分配結(jié)果，找滿足最佳適應(yīng)算法分配結(jié)果，找滿足需要，最小的空閑區(qū)需要，最小的空閑區(qū) 最壞適應(yīng)算法分配結(jié)果，找滿足最壞適應(yīng)算法分配結(jié)果，找滿足需要，最大的空閑區(qū)需要，最大的空閑區(qū)例例 3-3B請求240KB：.伙伴系統(tǒng)是基于固定分區(qū)和可變分區(qū)提出的一種折中存儲管理方案。.在伙伴系統(tǒng)中，可用內(nèi)存分區(qū)的大小為2K，LKU，其中： 2L表示分配的最小分區(qū)的尺寸； 2U表示分配的最大分區(qū)的尺寸。C(64KB)64KBA(128KB)128KBB(256KB)512KBA(128KB)B(256KB)512KBA(128KB)128KB256KB512KB1MBC(

30、64KB)64KBA(128KB)B(256KB)D(256KB)C(64KB)64KBA(128KB)256KBD(256KB)256KB256KBC(64KB)64KB128KB256KBD(256KB)256KBC(64KB)64KBE(128KB)256KBD(256KB)256KBE(128KB)128KB256KBD(256KB)256KB512KBD(256KB)256KB1MB1MB初啟：A請求100KB：C請求64KB：D請求256KB：B釋放256KB：A釋放128KB：E請求128KB：C釋放64KB：E釋放128KB：D釋放256KB：有一個1MB內(nèi)存，采用伙伴系統(tǒng)管理

31、存儲空間的分配和回收。 例：例：固定分區(qū)：限制可運(yùn)行程序的道固定分區(qū)：限制可運(yùn)行程序的道數(shù)，產(chǎn)生碎片，利用率低數(shù)，產(chǎn)生碎片，利用率低可變分區(qū)：按需求量劃分，能可變分區(qū)：按需求量劃分，能消除內(nèi)部碎片，維護(hù)復(fù)雜。消除內(nèi)部碎片，維護(hù)復(fù)雜。 用戶作業(yè)仍然相對于“0”進(jìn)行編址，形成一個連續(xù)的相對地址空間。操作系統(tǒng)按照內(nèi)存塊的尺寸對該空間進(jìn)行劃分，每一個分區(qū)被稱為“頁頁”，編號從0開始。 把整個內(nèi)存儲器劃分成大小相等的許多分區(qū)，每個分區(qū)稱為“塊塊” 。比如把內(nèi)存儲器劃分成n個分區(qū)，編號為0,1,2,n-1。塊是存儲分配的單位。 操作系統(tǒng)內(nèi)存儲器作業(yè)A(第2頁)作業(yè)A(第0頁)作業(yè)A(第1頁)020KB24

32、KB28KB32KB36KB40KB44KB48KB256KB(04塊)第5塊第6塊第7塊第8塊第9塊第10塊第11塊04KB8KB11KB12KB第0頁第1頁第2頁10921008(1, 1092)(2, 1008)51889200用戶作業(yè)A的相對地址空間1.2.3.用戶相對地址空間中的每一個相對地址，都可以用數(shù)對“頁號，頁內(nèi)位移頁號，頁內(nèi)位移”來表示。 用數(shù)對里的“頁號”2去查作業(yè)A的頁、塊對應(yīng)關(guān)系表。 把內(nèi)存第7塊的起始地址與頁內(nèi)位移相加，就得到了相對地址3000現(xiàn)在的絕對地址，即7K+952=8120。 記錄作業(yè)A的頁、塊對應(yīng)關(guān)系 4.用戶作業(yè)A的相對地址空間XXXXXXcall 30

33、0001001KB2KB30003KB952第0頁第1頁第2頁內(nèi)存儲器操作系統(tǒng)call 3000作業(yè)A(第0頁)XXXXXX952作業(yè)A(第2頁)作業(yè)A(第1頁)04KB4KB+1005KB6KB7KB7KB+9528KB9KB10KB(03塊)第4塊第5塊第6塊第7塊第8塊第9塊(2, 952)用戶作業(yè)A的頁、塊對應(yīng)關(guān)系頁號塊號0124977K+952=8120. 運(yùn)行到指令“call 3000”時，把相對地址 3000 轉(zhuǎn)換成：(2，952)。計算公式是： 頁號=相對地址/塊尺寸 頁內(nèi)位移=相對地址%塊尺寸.系統(tǒng)就去做指令“call 8120”，從而得到了正確地執(zhí)行 。 利用內(nèi)存記錄作業(yè)頁

34、、塊對應(yīng)關(guān)系的表，就是“頁表”。每個作業(yè)都有自己的頁表。作業(yè)相對地址空間有多少頁，頁表就有多少個表項。為了地址轉(zhuǎn)換，硬件設(shè)置一個專用寄存器：“頁表控制寄存器”。進(jìn)程調(diào)度時，把調(diào)度到作業(yè)的頁表起址和長度放入寄存器中，達(dá)到映射不同作業(yè)地址的目的。 1. 把塊(或頁)的尺寸限定只能是2 的方冪，那么利用計算機(jī)系統(tǒng)設(shè)定的地址結(jié)構(gòu)，很容易得到相對地址所對應(yīng)的數(shù)對(頁號，頁內(nèi)位移) 。0150140130121110101918170615141302010001501401301211101019181706151413020100015014013012111010191817061514130201

35、00頁號(2)頁內(nèi)位移(952)頁號(11)頁內(nèi)位移(184)2.利用內(nèi)存構(gòu)成頁表操作系統(tǒng)內(nèi)存儲器塊號頁內(nèi)位移絕對地址頁表起始地址長度長度頁表控制寄存器頁號頁內(nèi)位移相對地址CPU(1)地址3000的二進(jìn)制表示地址轉(zhuǎn)換過程(2) 頁表存放在內(nèi)存，增加了系統(tǒng)在存儲上的花銷，還降低了CPU的訪問速度。因為每次對某一地址的訪問，先要訪問內(nèi)存中的頁表，形成絕對地址后，才能進(jìn)行所需的真正訪問。因此，以前只須一次訪問就能實(shí)現(xiàn)的操作，現(xiàn)在要兩次訪問內(nèi)存才能實(shí)現(xiàn)。 實(shí)現(xiàn)頁表的另一方法是用一組快速硬件寄存器構(gòu)成公用頁表。調(diào)度到誰就把誰的頁表裝入該組寄存器中。這樣硬件把頁號與寄存器組中所有表項同時并行比較，立即輸出

36、與頁號匹配的塊號。這時無須訪問內(nèi)存，并且通過并行匹配直接完成地址變換，因此速度很快。 .操作系統(tǒng)內(nèi)存儲器塊號頁內(nèi)位移絕對地址快速寄存器組頁號頁內(nèi)位移相對地址CPU(1)(2) 快速寄存器價格昂貴，完全由它來組成頁表的方案是不可取的。 .頁表頁表/快表快表 考慮到大多數(shù)程序在一次運(yùn)行時，傾向于在少數(shù)頁面中進(jìn)行頻繁訪問（即程序的“局部性”原理），因此在實(shí)際系統(tǒng)中采用內(nèi)存頁表與快速寄存器組結(jié)合的解決方案，且只用極少幾個快速寄存器來構(gòu)成寄存器組，起名為：“相聯(lián)寄存器”，或簡稱“快表”。 (1) 快表中只存部分頁表。把一個相對地址劃分出數(shù)對：（頁號，頁內(nèi)位移）后，系統(tǒng)先通過頁號與快表中的所有表項進(jìn)行并行

37、比較。若發(fā)現(xiàn)了匹配的頁，則將塊號直接取出，不再通過頁表。用該塊號與頁內(nèi)位移拼接，形成所需要的絕對地址。(2) 作業(yè)長度不可能是頁面尺寸的整數(shù)倍，平均說，分給作業(yè)的最后內(nèi)存塊會浪費(fèi)掉一半。若內(nèi)存中有n個作業(yè)，頁面尺寸為p個字節(jié)，那么內(nèi)存中就有n*p/2個字節(jié)被浪費(fèi)掉。所以，頁面尺寸要小。 當(dāng)快表中沒有匹配的頁號時，地址轉(zhuǎn)換機(jī)構(gòu)按普通訪問頁表的方式工作，獲得所需的絕對地址；再把這個頁號與塊號的對應(yīng)關(guān)系送入快表保存，以便下一次進(jìn)行地址轉(zhuǎn)換時能夠命中。若快表里沒有空表項，則要先刪除快表中的一個表項，然后將新的頁表表項替換進(jìn)去。頁表控制寄存器操作系統(tǒng)內(nèi)存儲器塊號頁內(nèi)位移絕對地址快表頁號頁內(nèi)位移相對地址長

38、度起始地址頁表(3).命中率 直接查快表就能實(shí)現(xiàn)內(nèi)存訪問的成功率為“命中率”。命中率越高，性能就越好。表中給出了平均命中率與相聯(lián)寄存器個數(shù)的關(guān)系。從表中可以看出，設(shè)置快表，確實(shí)能夠達(dá)到提高地址轉(zhuǎn)換速度的目的。相聯(lián)寄存器個數(shù)平均命中率8121685%93%97%.3. 頁面尺寸小，用戶作業(yè)相對地址空間的頁面數(shù)就增加，頁表就會加大。因此，從減少頁表所需內(nèi)存開銷看，頁面尺寸應(yīng)該大一些為好。選擇最佳頁面尺寸，可能需在幾個相互矛盾的因素間折中求得。 1.操作系統(tǒng)作業(yè)C第2頁作業(yè)B第0頁作業(yè)A第0頁空閑塊作業(yè)A第2頁空閑塊空閑塊作業(yè)B第1頁空閑塊空閑塊作業(yè)A第1頁作業(yè)C第3頁作業(yè)C第0頁作業(yè)C第1頁空閑塊

39、內(nèi)存儲器064K空閑塊鏈表起址塊號狀態(tài)0已分配1已分配2已分配3已分配4空閑5已分配6空閑7空閑8已分配9空閑10空閑11已分配12已分配13已分配14已分配15空閑空閑塊總數(shù)：6 系統(tǒng)維持一張表格，表格表項與內(nèi)存中的一塊相對應(yīng)， 記錄該的塊使用情況。只要表格中 “空閑塊總數(shù)” 記錄的數(shù)目大于請求的存儲量，就可進(jìn)行分配 ，并把分配出去的塊的狀態(tài)改為 “已分配” 。作業(yè)完成后歸還存儲塊時，就把表中相應(yīng)塊的狀態(tài)改為“空閑”。 單鏈表存儲分塊表 把空閑塊鏈接成一個單鏈表加以管理，系統(tǒng)必須設(shè)置一個空閑塊鏈表的起始地址指針，以便進(jìn)行存儲分配時能夠找到空閑的內(nèi)存塊。無論是進(jìn)行空閑塊的分配還是作業(yè)完成后歸還

40、存儲塊，都要調(diào)整空閑塊間的鏈表指針。 . 作業(yè)雖然不占據(jù)連續(xù)的存儲區(qū)，但每次仍要求一次全部進(jìn)入內(nèi)存。因此，如果作業(yè)很大，其存儲需求大于內(nèi)存，那么還是存在小內(nèi)存不能運(yùn)行大作業(yè)的問題。 用戶作業(yè)的相對地址空間按照塊的尺寸劃分成頁。這種劃分是在系統(tǒng)內(nèi)部進(jìn)行的，用戶感覺不到，即對用戶是“透明”的。 2.內(nèi)存存儲器事先被劃分成相等尺寸的塊，它是進(jìn)行存儲分配的單位。 . 相對地址空間中的頁可以進(jìn)入內(nèi)存中的任何一個空閑塊，并且分頁式存儲管理實(shí)行的是動態(tài)重定位，因此它打破了一個作業(yè)必須占據(jù)連續(xù)存儲空間的限制，作業(yè)在不連續(xù)的存儲區(qū)里，也能夠得到正確的運(yùn)行。 3.平均每一個作業(yè)要浪費(fèi)半頁大小的存儲塊。 .位圖 用

41、二進(jìn)制位與內(nèi)存塊的使用建立起關(guān)系，為“0”，表示對應(yīng)塊空閑；為“1”，表示對應(yīng)塊已分配。 1111010010011110空閑塊總數(shù)：60123456701字節(jié)號位號位圖 獨(dú)立的地址空間有助于實(shí)施對過程和數(shù)據(jù)的共享，不必在每一個用戶作業(yè)的地址空間里都必須有相關(guān)的備份。 每個程序段是一個獨(dú)立的邏輯實(shí)體（比如一個過程、一個數(shù)組或一個堆棧），因此可以對它們進(jìn)行不同類型的存儲保護(hù) 。 每個程序段是一個獨(dú)立的地址空間，它們可獨(dú)自增長或減小而不用顧及別的程序段，不會影響到其他程序段的地址空間。 所謂“分段式”存儲管理，即要求用戶將自己的作業(yè)程序以多個相互獨(dú)立的稱為“段”的地址空間提交給系統(tǒng)，每個段都是一個

42、從“0”開始的一維地址空間，長度不一。操作系統(tǒng)按照段長為作業(yè)分配內(nèi)存空間。 改變某程序段尺寸，就會影響其他無關(guān)程序段的起址；對某個程序段進(jìn)行修改，會影響到其他相關(guān)部分，就可能要對所有的程序重新進(jìn)行鏈接編輯。 1.不利于按照程序段的性質(zhì)，實(shí)施存儲保護(hù)和共享。 .2.3. 在編譯過程中會建立很多表，其中主要有：供打印程序清單的源程序文檔；由變量名及其屬性組成的符號表；由程序中所有的整型、實(shí)型常量組成的常量表；包含程序語法分析結(jié)果的語法分析樹；內(nèi)部過程調(diào)用時使用的堆棧。 通過編譯程序在編譯過程中建立的各種表，說明頁式及段式存儲管理中，作業(yè)程序地址空間組織形式的不同。 例例 ：解解： .在分頁式管理時

43、，這5個表必須限定在一個一維的地址空間里，如圖(a)所示。 使用使用使用使用使用空閑空閑空閑空閑堆棧語法分析樹常量表源程序文檔符號表(a)0KB4KB8KB12KB16KB20KB0KB4KB8KB12KB符號表段00KB源程序文檔常量表段1段3段40KB4KB8KB12KB16KB語法分析樹0KB4KB8KB12KB堆棧段2(b). 在分段管理時，是把這些表視為一個個相互獨(dú)立的地址空間，比如：段0、段1等，它們組成了整個用戶的地址空間，如圖(b)所示。 系統(tǒng)為每個用戶作業(yè)設(shè)置一個段表，用于記錄各段在內(nèi)存中的存放信息。邏輯空間中有多少段，段表里就有多少個表項。每個表項通常包括的信息有段號、段長

44、、該段在內(nèi)存的基址（即起始地址）等。 如果段號s大于段表長度，表示該地址越界出錯；否則以此段號為索引查段表，得到該段在內(nèi)存的基址。 硬件要提供一個段表基址寄存器。每當(dāng)重新調(diào)度時，就把調(diào)度到的作業(yè)的段表起址及段表長度（即段表中表項的個數(shù)）放入寄存器中，從而達(dá)到映射不同作業(yè)的目的。 . 在分段式存儲管理時，要指示存儲空間里的一個地址，必須提供兩部分內(nèi)容：段號和段內(nèi)位移。即邏輯地址應(yīng)該是二維的：段號，段內(nèi)位移。. 在圖(a)所示的32位地址結(jié)構(gòu)中，各用16個二進(jìn)制位表示段號s和段內(nèi)位移d，因此表示用戶的邏輯地址空間最多可以有216個段，每段最大長度是64KB。 3116 150sd段號段內(nèi)位移ds段

45、號段內(nèi)位移03123 22(a)(b). 圖(b) 所示的32位的地址結(jié)構(gòu)中，由于用9個二進(jìn)制位表示段號s，用23個二進(jìn)制位表示段內(nèi)位移d，因此表示允許用戶的邏輯地址空間中最多可以有29個段，每段的最大長度是223=8192KB。 .分段式存儲管理時的地址轉(zhuǎn)換步驟如下 ：.(1) 從相對地址數(shù)對：段號s，段內(nèi)位移d中提取出段號s，用來進(jìn)行地址轉(zhuǎn)換。 (2)(3) 由段的基址和段內(nèi)位移d拼裝出所需的物理地址，實(shí)現(xiàn)對內(nèi)存的訪問。 段號(s)段內(nèi)位移(d)相對地址段表段表基址寄存器段號 長度基址基址段內(nèi)位移物理地址段sd內(nèi)存程序分段地址轉(zhuǎn)換機(jī)制.分段地址轉(zhuǎn)換機(jī)制圖示例：例： 在分段式存儲管理中，某作

46、業(yè)的段表如下。有該作業(yè)的六個邏輯地址為： 0，430、3，400； 1，10、2，2500 、4，42、1，11。求對應(yīng)的物理地址。段號 段 長 基 址 0 600 219 1 14 2300 2 100 90 3 580 1327 4 96 1954解：解： 對不同邏輯地址中的段號，有結(jié)果如下： （1）0，430的物理地址是219+430=649； （2）3，400的物理地址是1327+400=1727； （3）1，10的物理地址是2300+10=2310； （4）由邏輯地址知，是要訪問第2段位于2500處的元素。但第2段的段長是100，表明所要訪問的段內(nèi)位移越界出錯； （5）4，42的物理

47、地址是1954+42=1996； （6）1，11的物理地址是2300+11=2311。 在分頁式環(huán)境下，存儲保護(hù)只能以頁面為單位。在頁表的每一個表項里，設(shè)置一個所謂的“保護(hù)位”，該位的不同取值表示對應(yīng)的頁幀是可讀、可寫或只可讀等。 .1. 被共享的程序文本部分不一定正好劃分在一個或幾個完整的頁面中，有可能一個頁面中既有允許共享的內(nèi)容，又有不能共享的私有數(shù)據(jù)。因此，在分頁式環(huán)境下實(shí)現(xiàn)頁面的共享比較困難，但也不是不可能。 進(jìn)程A的邏輯地址空間進(jìn)程B的邏輯地址空間進(jìn)程C的邏輯地址空間ed10ed21ed32dataA3ed10ed21ed32dataB3ed10ed21ed32dataC3進(jìn)程A的頁

48、表031426320314263203142632頁號幀號進(jìn)程B的頁表頁號幀號進(jìn)程C的頁表頁號幀號操作系統(tǒng)0123456789101112dataAed1ed2ed3dataBdataC內(nèi)存. 假定分頁式存儲管理的頁幀尺寸為50KB，那么文本編輯程序被劃分成3頁，用戶進(jìn)程的數(shù)據(jù)段被劃分成一頁，合起來每個用戶進(jìn)程的邏輯地址空間為4頁。 . 三個進(jìn)程的邏輯地址空間和相應(yīng)的頁表，02頁都劃歸文本編輯程序（即ed1，ed2，ed3），頁表中的02表項都對應(yīng)于頁幀號3、4和6；進(jìn)程的數(shù)據(jù)頁（即dataA、dataB、dataC）都位于自己空間的第3頁，分別存放在內(nèi)存的2、8和11頁幀。 811文本編輯程

49、序段0程序段段1數(shù)據(jù)段段2進(jìn)程A的邏輯地址空間文本編輯程序段0程序段段1數(shù)據(jù)段段2進(jìn)程B的邏輯地址空間堆棧段段30252861基址243062操作系統(tǒng)內(nèi)存進(jìn)程A的段表段號段長025286 1基址243062進(jìn)程B的段表段號段長3A的數(shù)據(jù)段文本編輯程序B的數(shù)據(jù)段A的程序段B的堆棧段43062B的程序段2. 在分段式環(huán)境下，段是有完整意義的邏輯信息單位，因此對段中的所有內(nèi)容可以采用相同的方式使用。 . 為實(shí)行存儲保護(hù)，在段表表項里增加權(quán)限位，指出每段是可讀、可寫或只執(zhí)行等信息。每次進(jìn)行地址映射時，都將這次訪問的類型與權(quán)限位比較，若不符合就產(chǎn)生出錯中斷。 . 在分段式存儲管理中很容易實(shí)現(xiàn)段的共享，只

50、需在有關(guān)作業(yè)的段表中增加一個表項，讓其基址指向共享段在內(nèi)存中的起始地址即可。 . 進(jìn)程A和B要共享文本編輯程序，就可把文本編輯程序作為它們地址空間中的段0。假定文本編輯程序存放在內(nèi)存43062起始的連續(xù)分區(qū)里，那么在所對應(yīng)的各段表中，段號為0的表項的基址都是43062，從而達(dá)到共享該文本編輯程序的目的。(1) 頁是信息的物理單位，段是信息的邏輯單位：頁是信息的物理單位，段是信息的邏輯單位：系統(tǒng)根據(jù)內(nèi)存塊的尺寸劃分頁，不考慮頁中的信息是否完整。因此，一頁對應(yīng)的是信息的一個物理單位；段是基于用戶程序結(jié)構(gòu)提出的存儲管理模式，用戶知道自己的程序分多少段，每段在邏輯上都是相對完整的一組信息。所以，段是信

51、息的邏輯單位。 (2) 頁的尺寸由系統(tǒng)確定，段的尺寸因段而異：頁的尺寸由系統(tǒng)確定，段的尺寸因段而異：實(shí)行分頁式存儲管理的系統(tǒng)，頁的尺寸是由系統(tǒng)確定的，它與內(nèi)存頁幀的大小相同。段的長度取決于用戶編寫的程序，不同的段有不同的長度。 (3) 頁式地址空間是一維的，段式地址空間是二維的頁式地址空間是一維的，段式地址空間是二維的 ：在分頁式存儲管理時，用戶必須通過鏈接編輯程序，把各程序段鏈接成一個相對于0編址的一維線性空間，用戶向系統(tǒng)提供的是一個一維的邏輯地址空間；在分段式存儲管理時，用戶不把各程序段連接成一個相對于0編址的一維線性空間，各程序段之間是通過段號，段內(nèi)位移進(jìn)行訪問的。因此，用戶向系統(tǒng)提供的

52、是一個二維的邏輯地址空間。. 形式上看，分段式與分頁式存儲管理有很多相似之處。比如，一個為（頁號，頁內(nèi)位移），一個為段號，段內(nèi)位移；一個有頁表，一個有段表；如此等等。不過它們卻是兩個完全不同的概念 。.分段與分頁的主要區(qū)別 1. 由于程序執(zhí)行具有“局部性”，因此實(shí)際運(yùn)行時，沒有必要把全部信息都放在內(nèi)存里。只要合理組織，調(diào)度恰當(dāng)，在發(fā)現(xiàn)所需訪問的信息不在內(nèi)存時，能夠找到它，能夠把它調(diào)入內(nèi)存，那么不僅可以保證作業(yè)的正確執(zhí)行，而且還提高了系統(tǒng)的資源利用率，使得系統(tǒng)具有更高的運(yùn)行效率。 2. 作業(yè)提交給系統(tǒng)時，先進(jìn)入輔存。運(yùn)行時，只將部分信息裝入內(nèi)存，大部分仍保存在輔存中。運(yùn)行過程中需要用到不在內(nèi)存的

53、信息時，再把它們調(diào)入，以保證程序的正常運(yùn)行。這樣一個被用戶認(rèn)為有的、但實(shí)際上不存在的“大”存儲器，就被稱為“虛擬存儲器虛擬存儲器”。. 虛擬存儲器是一種擴(kuò)大內(nèi)存容量的設(shè)計技術(shù)，它把輔存作為計算機(jī)內(nèi)存的后援。在虛擬存儲意義下，用戶作業(yè)的相對地址空間，就是系統(tǒng)提供給他的虛擬存儲器。在多道程序設(shè)計環(huán)境下，每個用戶都有自己的虛擬存儲器。在提供虛擬存儲管理的系統(tǒng)里，把用戶作業(yè)的相對地址空間稱為“虛擬地址空間虛擬地址空間”，里面的地址稱為“虛擬地虛擬地址址”。 把內(nèi)存劃分成尺寸相同、位置固定的塊。然后按照內(nèi)存塊的大小，把作業(yè)的虛擬地址空間（即以前的相對地址空間）劃分成頁。由于頁的尺寸與塊一樣，因此虛擬地址

54、空間中的一頁，可以裝入到內(nèi)存中的任何一塊中。 最多可有2048頁每頁1KB第0頁第1頁第2頁虛擬存儲器第2045頁第2046頁第2047頁第0塊第1塊第2塊第29塊第30塊第31塊內(nèi)存儲器1.2. 作業(yè)全部進(jìn)入輔存。運(yùn)行時，只裝入要用的若干頁，其他頁仍在輔存。運(yùn)行過程中，虛擬地址被轉(zhuǎn)換成數(shù)對：(頁號，頁內(nèi)位移)。由頁號查頁表，若該頁在內(nèi)存，運(yùn)行就進(jìn)行下去；若該頁不在內(nèi)存，表明“缺頁”，運(yùn)行無法繼續(xù)。這時，就根據(jù)頁號把該頁從輔存調(diào)入內(nèi)存。所所謂謂“請求分頁式請求分頁式”，即是當(dāng)運(yùn)行中需要某頁時，再把它從輔存調(diào)入內(nèi)存使用，即是當(dāng)運(yùn)行中需要某頁時，再把它從輔存調(diào)入內(nèi)存使用的意思。的意思。 中斷處理程

55、序查存儲分塊表，找空閑塊；根據(jù)頁在輔存的位置，啟動磁盤讀信息。 2171.頁號塊號缺頁中斷位輔存地址 在請求分頁式存儲管理中，是由頁表表目項的“缺頁中斷位缺頁中斷位”來判斷所需頁是否在內(nèi)存的。該位為“1”，表示此頁在內(nèi)存；為“0”，表示不在內(nèi)存，并發(fā)出“缺頁”中斷信號，以求得系統(tǒng)的處理。 2.作業(yè)2虛擬地址空間05184KB8KB830012KBcall 8300第0頁第1頁第2頁XXXXXX205114012操作系統(tǒng)第7塊作業(yè)2的頁表內(nèi)存儲器作業(yè)2第2頁 根據(jù)執(zhí)行指令中的虛擬地址，（頁號，頁內(nèi)位移）。用頁號去查頁表，判斷該頁是否在內(nèi)存。 若該頁缺頁中斷位為“0”，產(chǎn)生缺頁中斷，進(jìn)行中斷處理。

56、 把從磁盤上讀出的信息裝入到分配的內(nèi)存塊中。 修改頁表中相應(yīng)的表目內(nèi)容，修改存儲分塊表里相應(yīng)表目的狀態(tài)。 在完成所需頁面的裝入后，返回原指令重新執(zhí)行。(1)(2)(3)(4)(5)(6) 假定一個作業(yè)運(yùn)行的頁面走向中涉及的頁面總數(shù)為A，其中有F次缺頁，必須通過缺頁中斷把它們調(diào)入內(nèi)存。定義： f=F/A稱 f 為 “缺頁中斷率缺頁中斷率” 。顯然 ，缺頁中斷率與缺頁中斷的次數(shù)有密切的關(guān)系。 缺頁中斷處理完成后，仍返回到原指令去重新執(zhí)行，因為那條指令并未執(zhí)行。而一般中斷則是返回到下一條指令去執(zhí)行，因為這條指令已經(jīng)執(zhí)行完畢了。 缺頁中斷是在執(zhí)行一條指令時產(chǎn)生的中斷，并立即轉(zhuǎn)去處理;一般中斷則是在一條

57、指令執(zhí)行完后，發(fā)現(xiàn)有中斷請求時才去響應(yīng)和處理 。3.4. 作業(yè)運(yùn)行時，虛擬地址在隨時發(fā)生變化，它是程序的執(zhí)行軌跡，是程序的一種動態(tài)特征。由于每個虛擬地址都與一個數(shù)對：（頁號，頁內(nèi)位移）相對應(yīng)，因此這種動態(tài)特征可以用程序執(zhí)行時頁號的變化來描述。通常，稱一個程序執(zhí)行過程中頁號的變化序列為“頁面走向頁面走向”。 所給程序的頁面走向是：0、1、0、2、0、1，涉及的頁面總數(shù)是6.。.用戶作業(yè)程序100 LOAD 1#, 1120104 ADD 1#, 2410108 STORE 1#, 1124虛擬地址100112010424101081124數(shù)對：(頁號, 頁內(nèi)位移)(0, 100)(1, 96)(

58、0, 104)(2, 362)(0, 108)(1, 100)頁面走向010201 程序1按行對a的元素初始化，缺頁中斷進(jìn)一頁，就能完成對a一行元素的初始化。a共128行，需128次缺頁中斷將它們調(diào)入，完成對a的初始化。程序2按列對a的元素初始化。通過缺頁中斷進(jìn)來一頁，只能對a的一行的一個列元素初始化。于是，每列元素的初始化，須128次缺頁中斷才完成。程序2需128128 = 16384次缺頁中斷，才能完成a的初始化工作。 要把128128的數(shù)組元素初始化為“0”。數(shù)組中的每個元素占一個字。若頁面尺寸為128字，規(guī)定數(shù)組按行存放，系統(tǒng)只給該作業(yè)2個內(nèi)存塊：一個存程序，另一個用于數(shù)組初始化。開始

59、時，程序已在內(nèi)存塊，數(shù)據(jù)未進(jìn)入。試問下面給出的兩個程序在運(yùn)行時各會發(fā)生多少次缺頁中斷？ 頁面尺寸頁面尺寸：頁面尺寸是與塊尺寸相同的，因此塊大頁也就大。頁面增大了，在每個內(nèi)存塊里的信息相應(yīng)增加，缺頁的可能性下降。反之，頁面尺寸減少，每塊里的信息減少，缺頁的可能性上升。 分配給作業(yè)的內(nèi)存塊數(shù)分配給作業(yè)的內(nèi)存塊數(shù)：由于分配給作業(yè)的內(nèi)存塊數(shù)多，同時能夠裝入內(nèi)存的作業(yè)頁面就多，缺頁的可能性下降，發(fā)生缺頁中斷的可能性也就下降。影響缺頁中斷次數(shù)的因素影響缺頁中斷次數(shù)的因素 .(1)程序的實(shí)現(xiàn)程序的實(shí)現(xiàn)：作業(yè)程序的編寫方法，對缺頁中斷產(chǎn)生的次數(shù)也會有影響。(2)(3)例：例：程序1：程序2：main()mai

60、n() int a128128; int a128128; int i,j; int i,j; for(i=0;i128;i+) for(j=0;j128;j+) for(j=0;j128;j+) for(i=0;i128;i+) aij=0; aij=0;解：解： 改變位：該位為“0”時，表示此頁面在內(nèi)存時數(shù)據(jù)未被修改過；為“1”時，表示被修改過。當(dāng)其為淘汰對象時，根據(jù)此位的取值來確定是否要進(jìn)行磁盤回寫操作。 引用位：在系統(tǒng)規(guī)定的時間間隔內(nèi)，該頁是否被引用過的標(biāo)志（該位在頁面淘汰算法中將會用到）。1.缺頁時，要從輔存把所需頁面調(diào)入內(nèi)存。若當(dāng)時內(nèi)存有空閑塊，那么不會有什么問題；若當(dāng)時內(nèi)存中已沒