上海大學(xué)操作系統(tǒng)2復(fù)習(xí)資料資料

1、存儲(chǔ)管理的主要功能：地址轉(zhuǎn)換（邏輯地址轉(zhuǎn)為物理地址存儲(chǔ)器的分配和回收存儲(chǔ)保護(hù)存儲(chǔ)擴(kuò)充地址轉(zhuǎn)換（重定位）邏輯地址物理地址；多道程序中編譯程序不可能預(yù)支經(jīng)編譯后所得到的目標(biāo)模塊應(yīng)放在內(nèi)存何處，不能用絕對(duì)裝入，要用可重定位裝入。靜態(tài)轉(zhuǎn)換：在裝入時(shí)對(duì)目標(biāo)程序中指令和數(shù)據(jù)地址進(jìn)行修改動(dòng)態(tài)轉(zhuǎn)換地址轉(zhuǎn)換推遲到真正執(zhí)行時(shí)靜態(tài)的不允許程序運(yùn)行時(shí)在內(nèi)存中移動(dòng)位置，動(dòng)態(tài)的可以分配方式連續(xù)分配單一連續(xù)分配單個(gè)程序獨(dú)占固定分區(qū)分配劃分分區(qū)：分區(qū)大小相等、不等內(nèi)存分配：按大小排序，分區(qū)使用表優(yōu)點(diǎn)：能在內(nèi)存中裝入多道程序缺點(diǎn)：存儲(chǔ)空間浪費(fèi)動(dòng)態(tài)分區(qū)分配數(shù)據(jù)結(jié)構(gòu)：空閑分區(qū)表；空閑分區(qū)鏈動(dòng)態(tài)分區(qū)分配算法：順序搜索算法（用于不太大

2、的系統(tǒng)）首次適應(yīng)：空閑分區(qū)地址遞增，從鏈?zhǔn)组_始尋找，滿足要求后切割優(yōu)點(diǎn)：優(yōu)先利用低址，保留高址大空閑區(qū)，為以后到達(dá)的大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件缺點(diǎn)：低址部分被不斷劃分，留下許多難以利用的、很小的空閑分區(qū)循環(huán)首次適應(yīng)：空閑分區(qū)地址遞增，從上次找到的下個(gè)空閑分區(qū)開始優(yōu)點(diǎn)：避免低址部分留下太多空閑分區(qū)缺點(diǎn)：缺乏大的空閑分區(qū)最佳適應(yīng)：空閑分區(qū)大小遞增，找到的第一個(gè)優(yōu)點(diǎn)：避免大材小用缺點(diǎn)：每次切割剩下的都是最小的，會(huì)留下難以利用的碎片最壞適應(yīng)：找最大的一個(gè)空閑分區(qū)優(yōu)點(diǎn)：使剩下的空間不會(huì)太小，產(chǎn)生碎片的可能性最小，對(duì)中小作業(yè)有利缺點(diǎn)：缺乏大的空閑分區(qū)索引搜索算法（大中型系統(tǒng)）快速適應(yīng)：每一類相同容量

3、的分區(qū)，單獨(dú)設(shè)一個(gè)鏈表，查找時(shí)先去索引表，然后去鏈表取下第一塊即可（可將其理解為一個(gè)菜單）優(yōu)點(diǎn)：提高搜索速度缺點(diǎn)：分區(qū)歸還主存時(shí)較為復(fù)雜；分配空閑分區(qū)時(shí)是以進(jìn)程為單位的，一個(gè)分區(qū)只屬于一個(gè)進(jìn)程，存在浪費(fèi)（以空間換空間）伙伴系統(tǒng)：內(nèi)容看書吧時(shí)間性能：劣于快速適應(yīng)，優(yōu)于順序搜索空間性能：劣于順序搜索優(yōu)于快速適應(yīng)哈希算法直接根據(jù)分區(qū)大小利用哈希函數(shù)計(jì)算分配內(nèi)存：m.size-u.size<=size回收內(nèi)存：回收區(qū)與前后空閑分區(qū)的鄰接情況動(dòng)態(tài)可重定位分區(qū)分配比動(dòng)態(tài)分區(qū)增加了緊湊功能地址變換在程序執(zhí)行期間隨著對(duì)每條指令或數(shù)據(jù)的訪問自動(dòng)進(jìn)行（動(dòng)態(tài)地址轉(zhuǎn)換）離散分配方式分頁(yè)存儲(chǔ)管理：將用戶程序的地址

4、空間分為若干固定大小的區(qū)域（頁(yè)）頁(yè)面：進(jìn)程的邏輯地址空間分為若干頁(yè)物理塊：內(nèi)存的物理地址空間分為若干塊若干頁(yè)裝入多個(gè)可以不相鄰的物理塊最后一頁(yè)經(jīng)常裝不滿，形成的碎片為“頁(yè)內(nèi)碎片”頁(yè)面太小減小內(nèi)存碎片，內(nèi)存利用率提高每個(gè)進(jìn)程占用頁(yè)面過多，頁(yè)表過長(zhǎng)，占用大量?jī)?nèi)存降低頁(yè)面換進(jìn)換出的效率頁(yè)面太大減少頁(yè)表長(zhǎng)度，提高換進(jìn)換出效率頁(yè)內(nèi)碎片增大頁(yè)面適中大?。?的冪，通常為1kb-8kb邏輯地址形式：頁(yè)號(hào)+位移量/頁(yè)內(nèi)地址（一維）頁(yè)表：實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射進(jìn)程的各個(gè)頁(yè)離散的存儲(chǔ)在內(nèi)存的任一物理塊中為了找到每個(gè)頁(yè)面對(duì)應(yīng)的物理塊地址轉(zhuǎn)換機(jī)構(gòu)硬件（一個(gè)頁(yè)表項(xiàng)用一個(gè)寄存器）實(shí)現(xiàn)的動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)存儲(chǔ)保護(hù)：頁(yè)表

5、長(zhǎng)度寄存器執(zhí)行檢索前，先將頁(yè)號(hào)與頁(yè)表長(zhǎng)度進(jìn)行比較，若頁(yè)號(hào)大于等于頁(yè)表長(zhǎng)度，則表示本次訪問的地址已超越進(jìn)程的地址空間。這一錯(cuò)誤被系統(tǒng)發(fā)現(xiàn)，產(chǎn)生越界中斷若未發(fā)生越界錯(cuò)誤，則將頁(yè)表始址與頁(yè)號(hào)*頁(yè)表項(xiàng)長(zhǎng)度相加，得到該表項(xiàng)在頁(yè)表中的位置快表在地址變換機(jī)構(gòu)中增設(shè)一個(gè)具有并行查詢能力的特殊高速緩沖寄存器（快表）快表不命中時(shí)要訪問兩次內(nèi)存一次訪問內(nèi)存中的頁(yè)表，找到物理塊，將塊號(hào)與頁(yè)內(nèi)偏移量W（即頁(yè)內(nèi)地址）拼接以形成物理地址第二次從第一次得到的地址中獲得所需要的數(shù)據(jù)分段存儲(chǔ)管理：把用戶地址空間分為大小不同的若干段為了滿足用戶（程序員）在編程和使用（信息共享、信息保護(hù)、動(dòng)態(tài)增長(zhǎng)、動(dòng)態(tài)鏈接）上的要求，支持以模塊為單

6、位進(jìn)行邏輯地址形式：段號(hào)+段內(nèi)地址（二維，既包含一部分地址空間，又標(biāo)識(shí)了邏輯關(guān)系）數(shù)據(jù)結(jié)構(gòu)段表（記錄該段在內(nèi)存中的起始地址和段的長(zhǎng)度）段表可放在寄存器（提高地址轉(zhuǎn)換速度）或內(nèi)存（更常見）中地址轉(zhuǎn)換段表寄存器（存放段表始址和段表長(zhǎng)度），硬件實(shí)現(xiàn)的動(dòng)態(tài)地址轉(zhuǎn)換存儲(chǔ)保護(hù)進(jìn)行地址變換時(shí)，系統(tǒng)將邏輯地址中的段號(hào)S與段表長(zhǎng)度TL進(jìn)行比較，若S>TL則段號(hào)太大，訪問越界，產(chǎn)生越界中斷信號(hào)分頁(yè)分段管理比較分頁(yè)分段大小固定、硬件決定小固定、程序決定信息信息的物理單位獨(dú)立的信息邏輯單元，更便于共享目的r提高內(nèi)存利用率方便程序設(shè)計(jì)邏輯地址一維，頁(yè)號(hào)+頁(yè)內(nèi)地址二維，段號(hào)+段內(nèi)地址段頁(yè)式管理既有分段系統(tǒng)的易于實(shí)現(xiàn)

7、、分段可共享、易于保護(hù)、動(dòng)態(tài)鏈接等優(yōu)點(diǎn)，也能像分頁(yè)系統(tǒng)那樣，很好的解決內(nèi)存的外部碎片問題先將用戶程序分成若干段，再把每個(gè)段分成若干頁(yè)，并為每個(gè)段賦予一個(gè)段名邏輯地址：段號(hào)+段內(nèi)頁(yè)號(hào)+頁(yè)內(nèi)地址（二維）數(shù)據(jù)結(jié)構(gòu)：每個(gè)進(jìn)程一張段表（頁(yè)表地址和頁(yè)表長(zhǎng)度），每個(gè)段一張頁(yè)表，位視圖地址轉(zhuǎn)換：硬件（段表寄存器）實(shí)現(xiàn)的動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)，訪問3次內(nèi)存第一次訪問內(nèi)存中的段表，得到頁(yè)表始址；第二次訪問內(nèi)存中的頁(yè)表，去除該頁(yè)所在的物理塊號(hào)，并將該號(hào)與頁(yè)內(nèi)地址一起形成指令或數(shù)據(jù)的物理地址，第三次訪問從第二次訪問得到的地址中取出指令或數(shù)據(jù)。常規(guī)存儲(chǔ)器一次性：作業(yè)必須一次性裝入內(nèi)存后方能運(yùn)行駐留性：作業(yè)被裝入內(nèi)存后，整個(gè)作

8、業(yè)都一直駐留在內(nèi)存中，其中任何部分都不會(huì)被換出，直至運(yùn)行結(jié)束局部性原理在一較短時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分，相應(yīng)地，它所訪問的存儲(chǔ)空間也局限于某個(gè)區(qū)域。時(shí)間局限性：若程序的某條指令被執(zhí)行，則不久后這條指令可能再次被執(zhí)行，若某條數(shù)據(jù)被訪問過，則這條數(shù)據(jù)可能再次被訪問。原因是程序中存在著大量的循環(huán)操作空間局限性：一旦程序訪問了某個(gè)存儲(chǔ)單元，在不久后，其附近的存儲(chǔ)單元也將被訪問，即程序在一段時(shí)間內(nèi)所訪問的地址可能集中在一定的范圍內(nèi)。典型情況是程序的順序執(zhí)行虛擬存儲(chǔ)器定義：具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。邏輯容量由內(nèi)存容量和外村容量之和決定，運(yùn)行速度接近

9、于內(nèi)存速度，成本又接近外存特征多次性：一個(gè)作業(yè)的程序和數(shù)據(jù)無需在作業(yè)運(yùn)行時(shí)一次性全部裝入內(nèi)存，而是允許被分成多次調(diào)入內(nèi)存運(yùn)行，只需將當(dāng)前需要運(yùn)行的那部分程序和數(shù)據(jù)裝入內(nèi)存即可對(duì)換性：一個(gè)作業(yè)的程序和數(shù)據(jù)，無需在作業(yè)運(yùn)行時(shí)一直常駐內(nèi)存，而是允許在作業(yè)的運(yùn)行過程中進(jìn)行換進(jìn)換出虛擬性：用戶看到的內(nèi)存容量遠(yuǎn)大于十級(jí)內(nèi)存容量實(shí)現(xiàn)方法分頁(yè)請(qǐng)求系統(tǒng)分段請(qǐng)求系統(tǒng)請(qǐng)求分頁(yè)數(shù)據(jù)結(jié)構(gòu)頁(yè)號(hào)、物理塊號(hào)、狀態(tài)位P、訪問字段A、修改位M、外存地址狀態(tài)位：指示該頁(yè)是否已調(diào)入內(nèi)存訪問字段：記錄本頁(yè)在一段時(shí)間內(nèi)被訪問的次數(shù)或時(shí)多久未被訪問，提供給置換算法進(jìn)行換進(jìn)換出時(shí)的參考修改位：標(biāo)識(shí)該頁(yè)是否被修改過，供置換頁(yè)面參考外存地址：通

10、常時(shí)物理塊號(hào)，供調(diào)入該頁(yè)時(shí)參考動(dòng)態(tài)地址轉(zhuǎn)換硬件+軟件缺頁(yè)中斷內(nèi)存分配固定分配局部置換：進(jìn)程物理塊固定；缺頁(yè)時(shí)只能從分配給該頁(yè)的n個(gè)頁(yè)面中選出一頁(yè)換出，然后再調(diào)入一頁(yè)，以保證分配給進(jìn)程的內(nèi)存空間不變可變分配全局置換：進(jìn)程運(yùn)行期間分配的物理塊可調(diào)整；缺頁(yè)則將空閑的物理塊分配給該進(jìn)程，分配給該進(jìn)程的內(nèi)存空間增加可變分配局部置換調(diào)入策略預(yù)調(diào)頁(yè)：預(yù)先估計(jì)在不久后便會(huì)被訪問的頁(yè)面，將其調(diào)入內(nèi)存請(qǐng)求調(diào)頁(yè)：進(jìn)程發(fā)現(xiàn)需要訪問某程序和數(shù)據(jù)，但此頁(yè)面不在內(nèi)存，便立即提出請(qǐng)求，由OS將需要的頁(yè)面調(diào)入內(nèi)存從哪里調(diào)入對(duì)換區(qū)：系統(tǒng)擁有足夠的對(duì)換區(qū)空間（進(jìn)程運(yùn)行前將與該進(jìn)程有關(guān)的文件從文件去拷貝僅對(duì)換區(qū)文件區(qū)：系統(tǒng)缺少足夠的

11、對(duì)換區(qū)空間UNIX方式：放在文件區(qū)的直接從文件區(qū)調(diào)入；曾經(jīng)用過又換出的，由于放在對(duì)換區(qū)，直接從對(duì)換區(qū)調(diào)入；由于unix系統(tǒng)允許頁(yè)面共享，某進(jìn)程請(qǐng)求的頁(yè)面若被其他進(jìn)程調(diào)入內(nèi)存，可直接使用抖動(dòng)：剛被換出的頁(yè)面很快又要被使用，需要重新調(diào)入，此時(shí)再選一頁(yè)調(diào)出；而此剛被調(diào)出的頁(yè)面又很快要被訪問，又需要調(diào)入，如此頻繁的更換頁(yè)面，以致一個(gè)進(jìn)程在運(yùn)行中把大部分時(shí)間花費(fèi)在頁(yè)面置換工作上，稱該進(jìn)程發(fā)生了“抖動(dòng)”預(yù)防方法：采用局部置換；把工作集算法融入處理機(jī)調(diào)度；利用“L=S'準(zhǔn)則調(diào)節(jié)缺頁(yè)率；選擇暫停的進(jìn)程影響缺頁(yè)率的因素：置換算法、頁(yè)面大小、進(jìn)程分得的頁(yè)塊數(shù)量，進(jìn)程訪問內(nèi)存的離散程度。工作集在某段時(shí)間間隔

12、內(nèi)，進(jìn)程實(shí)際要訪問頁(yè)面的集合置換算法OPT最佳置換算法：理想化，性能最好，實(shí)際無法實(shí)現(xiàn)，以其作為標(biāo)準(zhǔn)衡量其他算法的優(yōu)劣FIFO先進(jìn)先出算法：最直觀，性能最差，實(shí)際應(yīng)用極少LRU最近最久未用算法NRU最近未用算法LFU最近最少使用算法請(qǐng)求分段段的大小受到物理內(nèi)存配置的限制便于實(shí)現(xiàn)段的動(dòng)態(tài)鏈接便于實(shí)現(xiàn)段的共享：共享段表段的置換時(shí)，有時(shí)還要“緊湊”合并空閑分區(qū)才能換入要裝入的段。文件系統(tǒng)文件系統(tǒng)主要功能文件目錄管理提供文件操作的接口文件存儲(chǔ)空間的管理文件的共享和文件保護(hù)、保密文件：文件是指由創(chuàng)建者所定義的、具有文件名的一組相關(guān)元素的集合文件系統(tǒng)：從用戶角度看，是實(shí)現(xiàn)“按名存取”文件的軟件。邏輯文件（邏輯結(jié)構(gòu)）：用戶所看到的文件是由一系列的邏輯記錄組成的，是用戶可以直接處理的數(shù)據(jù)及其結(jié)構(gòu)，獨(dú)立于文件的物理特性，又稱問文件組織無結(jié)構(gòu)的字符流文件有結(jié)構(gòu)的記錄文件物理文件（物理結(jié)構(gòu)）：文件在存儲(chǔ)介質(zhì)上的結(jié)構(gòu)，用戶看不到邏輯結(jié)構(gòu)與物理結(jié)構(gòu)都會(huì)贏下對(duì)文件的檢索速度文件目錄：文件控制塊的集合，UNIX中，文件目錄是文件名與inode號(hào)構(gòu)成的目錄項(xiàng)的集合。目錄文件：文件的內(nèi)容是文件的目錄（D