操作系統(tǒng)大綱三四五

2023/2/3第3章存儲(chǔ)器管理考試大綱要求（一）

內(nèi)存管理基礎(chǔ)

1.

內(nèi)存管理概念

程序裝入與鏈接；邏輯地址與物理地址空間；內(nèi)存保護(hù)。

2.

交換與覆蓋

3.

連續(xù)分配管理方式

4.

非連續(xù)分配管理方式

分頁(yè)管理方式；分段管理方式；段頁(yè)式管理方式。

退出2023/2/3存儲(chǔ)器的層次結(jié)構(gòu)多級(jí)存儲(chǔ)器結(jié)構(gòu)一般計(jì)算機(jī)，存儲(chǔ)層次至少應(yīng)具有三級(jí)：最高層為CPU寄存器，中間為主存，最底層是輔存。較高檔計(jì)算機(jī)中，根據(jù)具體功能分為6層，如圖寄存器高速緩存主存磁盤(pán)緩存磁盤(pán)可移動(dòng)存儲(chǔ)介質(zhì)2023/2/3程序的裝入程序的裝入就是把程序裝入內(nèi)存空間。采用三種方式（1）絕對(duì)裝入方式：是由裝入程序根據(jù)裝入模塊中的地址，將程序和數(shù)據(jù)裝入內(nèi)存。（2）可重定位方式：是由裝入程序根據(jù)內(nèi)存當(dāng)前的實(shí)際使用情況，將裝入模塊裝入到內(nèi)存適當(dāng)?shù)牡胤?。?）動(dòng)態(tài)運(yùn)行時(shí)裝入方式：動(dòng)態(tài)運(yùn)行時(shí)的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換推遲到程序要真正執(zhí)行時(shí)才進(jìn)行。2023/2/3程序的裝入絕對(duì)裝入方式：是由裝入程序根據(jù)裝入模塊中的地址，將程序和數(shù)據(jù)裝入主存若知道程序在內(nèi)存的位置，編譯程序?qū)a(chǎn)生絕對(duì)地址目標(biāo)模塊絕對(duì)地址一般由編譯程序給出程序被裝入內(nèi)存后，由于程序中的邏輯地址與實(shí)際內(nèi)存地址完全相同，所以不允許改變程序和數(shù)據(jù)的地址只適于單道環(huán)境2023/2/3程序的裝入可重定位方式：是由裝入程序根據(jù)主存當(dāng)前的實(shí)際使用情況，將裝入模塊裝入到主存適當(dāng)?shù)牡胤健?/p>

重定位：在裝入時(shí)對(duì)目標(biāo)程序中指令和數(shù)據(jù)的修改過(guò)程。會(huì)使裝入模塊中的所有邏輯地址與實(shí)際裝入內(nèi)存的物理地址不同2023/2/3程序的裝入靜態(tài)重定位方式：是指地址轉(zhuǎn)換工作是在程序裝入內(nèi)存時(shí)由裝配程序完成的。裝配程序根據(jù)將要裝入內(nèi)存的起始地址，對(duì)程序模塊中有關(guān)的地址部分進(jìn)行調(diào)整和修改（物理地址=邏輯地址+程序存放在內(nèi)存的起始地址），一旦確定下來(lái)之后不再改變，即靜態(tài)地址重定位是在程序執(zhí)行之前完成的地址轉(zhuǎn)換。它的優(yōu)點(diǎn)：無(wú)需硬件支持，容易實(shí)現(xiàn)。缺點(diǎn)：程序經(jīng)地址重定位后不能再移動(dòng)，程序在內(nèi)存空間只能連續(xù)存儲(chǔ)，程序很難被若干個(gè)用戶(hù)所共享。2023/2/3程序的裝入動(dòng)態(tài)運(yùn)行時(shí)裝入方式：動(dòng)態(tài)運(yùn)行時(shí)的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換推遲到程序要真正執(zhí)行時(shí)才進(jìn)行。適于多道環(huán)境允許程序移動(dòng)，如切換動(dòng)態(tài)重定位需要特殊硬件支持（重定位寄存器）2023/2/3程序的裝入動(dòng)態(tài)重定位：是指地址轉(zhuǎn)換工作是在程序執(zhí)行期間由硬件變換機(jī)構(gòu)動(dòng)態(tài)實(shí)現(xiàn)地址轉(zhuǎn)換的。物理地址=邏輯地址+重定位寄存器的內(nèi)容。動(dòng)態(tài)重定位的優(yōu)點(diǎn)：用戶(hù)程序在執(zhí)行過(guò)程中內(nèi)存可移動(dòng)，程序不必連續(xù)存放在內(nèi)存中，可以放在不同區(qū)域，若干個(gè)用戶(hù)可以共享同一程序段或數(shù)據(jù)段。缺點(diǎn)：需要附加硬件支持，實(shí)行存儲(chǔ)管理的軟件算法比較復(fù)雜。2023/2/3程序的鏈接鏈接程序的功能是將經(jīng)過(guò)編譯或匯編后所得到的一組目標(biāo)模塊以及它們所需要的庫(kù)函數(shù)，裝配成一個(gè)完整的裝入模塊。實(shí)現(xiàn)鏈接的方法有三種靜態(tài)鏈接：事先進(jìn)行鏈接，以后不再拆開(kāi)的鏈接方式裝入時(shí)動(dòng)態(tài)鏈接：用戶(hù)源程序經(jīng)編譯后所得到的目標(biāo)模塊，是在裝入內(nèi)存時(shí)，邊裝入邊鏈接的。運(yùn)行時(shí)動(dòng)態(tài)鏈接：某些目標(biāo)模塊的鏈接，是在程序執(zhí)行中需要該（目標(biāo)）模塊時(shí)，才對(duì)它進(jìn)行鏈接2023/2/3內(nèi)存保護(hù)

內(nèi)存保護(hù)就是防止各用戶(hù)程序運(yùn)行時(shí)相互被破壞,最重要的就是不能破壞操作系統(tǒng).

（1）界地址寄存器保護(hù)法 （2）訪問(wèn)授權(quán)保護(hù)2023/2/32.交換與覆蓋

采用交換與覆蓋技術(shù)是為了節(jié)省內(nèi)存。交換就是系統(tǒng)根據(jù)需要把主存中暫時(shí)不運(yùn)行的某個(gè)（或某些）進(jìn)程的部分或全部信息移到外存，而把外存中的某個(gè)（或某些）進(jìn)程移到相應(yīng)的主存區(qū)，并使其投入運(yùn)行覆蓋就是指一個(gè)作業(yè)（或進(jìn)程）或多個(gè)作業(yè)（或進(jìn)程）的若干程序段或數(shù)據(jù)段共享主存的某個(gè)區(qū)域。實(shí)現(xiàn)方法是將一個(gè)作業(yè)（或進(jìn)程）劃分成若干個(gè)相互獨(dú)立的段，將不同時(shí)運(yùn)行的程序段或數(shù)據(jù)段組成覆蓋。2023/2/33.連續(xù)分配方式連續(xù)分配方式：為一個(gè)用戶(hù)程序分配一個(gè)連續(xù)的內(nèi)存空間單一連續(xù)分配固定分區(qū)分配動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)重定位分區(qū)分配2023/2/3連續(xù)分配方式單一連續(xù)分配2023/2/3連續(xù)分配方式固定分區(qū)分配將內(nèi)存中的用戶(hù)空間劃分為若干個(gè)固定大小的區(qū)域每個(gè)分區(qū)中只裝入一道作業(yè)，一個(gè)作業(yè)也只能裝入一個(gè)分區(qū)中，這樣可以裝入多個(gè)作業(yè)，使它們并發(fā)執(zhí)行。當(dāng)有一個(gè)空閑分區(qū)時(shí)，便可從外存的后備隊(duì)列中，選擇一個(gè)適當(dāng)大小的作業(yè)裝入該分區(qū)；當(dāng)該作業(yè)運(yùn)行完時(shí)，又可從后備隊(duì)列中選擇另一個(gè)作業(yè)裝入該分區(qū)（分區(qū)大小可以相同也可以不同）。

2023/2/3固定分區(qū)分配的管理特點(diǎn)（1）一個(gè)作業(yè)只能裝入一個(gè)分區(qū)，不能裝入兩個(gè)或多個(gè)相鄰的分區(qū)。一個(gè)分區(qū)只能裝入一個(gè)作業(yè)，當(dāng)分區(qū)大小不能滿(mǎn)足作業(yè)的要求時(shí)，該作業(yè)暫時(shí)不能裝入。（2）通過(guò)對(duì)“分區(qū)使用表”的改寫(xiě)，來(lái)實(shí)現(xiàn)主存的分配與回收。作業(yè)在執(zhí)行時(shí)，不會(huì)改變存儲(chǔ)區(qū)域，所以采用靜態(tài)地址重定位方式。此方法易于實(shí)現(xiàn)，系統(tǒng)開(kāi)銷(xiāo)小。（3）當(dāng)分區(qū)較大作業(yè)較小時(shí)，仍然浪費(fèi)許多主存空間(內(nèi)零頭）。并且分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的作業(yè)數(shù)目。

2023/2/3動(dòng)態(tài)分區(qū)分配

動(dòng)態(tài)分區(qū)存儲(chǔ)管理的基本思想是：在作業(yè)要求裝入內(nèi)存儲(chǔ)器時(shí)，如果當(dāng)時(shí)內(nèi)存儲(chǔ)器中有足夠的存儲(chǔ)空間滿(mǎn)足該作業(yè)的需求，那么就劃分出一個(gè)與作業(yè)相對(duì)地址空間同樣大小的分區(qū)分配給它。2023/2/3采用的數(shù)據(jù)結(jié)構(gòu)為了實(shí)現(xiàn)分區(qū)分配，系統(tǒng)中必須配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，用來(lái)記錄內(nèi)存的使用情況。比如空閑分區(qū)的情況，為作業(yè)分配內(nèi)存空間提供依據(jù)。常用的有空閑分區(qū)表和空閑分區(qū)鏈。2023/2/3分區(qū)分配算法（1）首次適應(yīng)分配算法（FF）（2）循環(huán)首次適應(yīng)分配算法（NF）（2）最佳適應(yīng)分配算法（BF）（3）最壞適應(yīng)分配算法（WF）2023/2/3(1)首次適應(yīng)法要求空閑區(qū)按首址遞增的次序組織空閑區(qū)表（隊(duì)列）。

分配：當(dāng)進(jìn)程申請(qǐng)大小為SIZE的內(nèi)存時(shí)，系統(tǒng)從空閑區(qū)鏈的鏈?zhǔn)组_(kāi)始查詢(xún)，直到首次找到等于或大于SIZE的空閑區(qū)。從該區(qū)中劃出大小為SIZE的分區(qū)分配給進(jìn)程，余下的部分仍作為一個(gè)空閑區(qū)留在空閑區(qū)鏈中，但要修改其首址和大小。若找不到滿(mǎn)足要求的，則分配失敗，返回。2023/2/3分析注意：每次分配和回收后空閑區(qū)鏈都要按首址遞增的次序排序。優(yōu)點(diǎn)：這種算法是盡可能地利用低地址空間，從而保證高地址空間有較大的空閑區(qū)。

缺點(diǎn)容易產(chǎn)生過(guò)多的小地址碎片；降低了主存空間利用率。每次查找都是從低址開(kāi)始，增加了查找的開(kāi)銷(xiāo)改進(jìn)采用循環(huán)首次適應(yīng)算法。2023/2/3（2）循環(huán)首次適應(yīng)算法

不是每次都從鏈?zhǔn)组_(kāi)始找，而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開(kāi)始查找，直到找到一個(gè)能滿(mǎn)足要求的空閑分區(qū)。設(shè)置查尋指針；循環(huán)查找方式使內(nèi)存中的空閑分區(qū)分布得更均勻，減少了查找時(shí)的開(kāi)銷(xiāo)，但會(huì)缺乏大的空閑分區(qū)。2023/2/3（3）最佳適應(yīng)法所謂最佳就是每次為作業(yè)分配內(nèi)存時(shí)，總是把能滿(mǎn)足要求、又是最小的空閑分區(qū)分配給作業(yè)，避免大材小用。要求按空閑區(qū)大小從小到大的次序組成空閑區(qū)鏈。2023/2/3最佳適應(yīng)法優(yōu)點(diǎn)：在系統(tǒng)中若存在一個(gè)與申請(qǐng)分區(qū)大小相等的空閑區(qū)，必定會(huì)被選中，而首次適應(yīng)法則不一定。若系統(tǒng)中不存在與申請(qǐng)分區(qū)大小相等的空閑區(qū)，則選中的空閑區(qū)是滿(mǎn)足要求的最小空閑區(qū)，而不致于毀掉較大的空閑區(qū)。缺點(diǎn)：空閑區(qū)的大小一般與申請(qǐng)分區(qū)大小不相等，因此將其一分為二，留下來(lái)的空閑區(qū)一般情況下是很小的，以致無(wú)法使用。隨著時(shí)間的推移，系統(tǒng)中的小空閑區(qū)會(huì)越來(lái)越多，從而造成存儲(chǔ)區(qū)的大量浪費(fèi)。2023/2/3（4）最壞適應(yīng)算法掃描整個(gè)空閑分區(qū)表，或鏈表，總是挑選一個(gè)最大的空閑區(qū)分割給作業(yè)使用。要求按空閑區(qū)大小從大到小的次序組成空閑區(qū)鏈。優(yōu)點(diǎn)：可使剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的幾率最小，對(duì)中、小作業(yè)有利。缺點(diǎn)：缺乏大的空閑分區(qū)，不利于大作業(yè)。2023/2/3可重定位分區(qū)分配

在連續(xù)分配中，必須把一個(gè)系統(tǒng)或用戶(hù)程序裝入一連續(xù)的內(nèi)存空間。不能被利用的小分區(qū)稱(chēng)為“零頭”或“碎片”。將主存中的所有作業(yè)進(jìn)行移動(dòng)，使它們相鄰接。這樣，原來(lái)分散的多個(gè)小分區(qū)便拼接成一個(gè)大分區(qū)，從而就可以把作業(yè)裝入該區(qū)。這種通過(guò)移動(dòng)，把多個(gè)分散的小分區(qū)拼接成大分區(qū)的方法被稱(chēng)為“拼接”或“緊湊”，改變作業(yè)在主存中位置的工作稱(chēng)為“移動(dòng)”。2023/2/3連續(xù)分配方式比較作業(yè)個(gè)數(shù)內(nèi)部碎片外部碎片解決碎片方法相同點(diǎn)提高作業(yè)道數(shù)單一連續(xù)分配1有無(wú)無(wú)一個(gè)程序需全部、連續(xù)裝入內(nèi)存中。對(duì)換固定分區(qū)分配N(xiāo)（分區(qū)數(shù)）有無(wú)無(wú)動(dòng)態(tài)分區(qū)分配不定無(wú)有緊湊2023/2/3非連續(xù)分配方式分頁(yè)管理方式分段管理方式段頁(yè)式管理方式2023/2/34.4.1頁(yè)面與頁(yè)表

作業(yè)地址空間劃分成連續(xù)的大小相同的頁(yè)面內(nèi)存劃分成連續(xù)的大小相等的塊（也稱(chēng)為頁(yè)框）頁(yè)面的大小與內(nèi)存塊的大小完全相同作業(yè)進(jìn)入內(nèi)存時(shí)其不同的頁(yè)面對(duì)應(yīng)于內(nèi)存中不同的塊，連續(xù)頁(yè)面可以對(duì)應(yīng)不連續(xù)的塊。2023/2/3（1）分頁(yè)管理方式頁(yè)面（用戶(hù)程序劃分）

把用戶(hù)程序按邏輯頁(yè)劃分成大小相等的部分，稱(chēng)為頁(yè)（page）

。從0開(kāi)始編制頁(yè)號(hào)，頁(yè)內(nèi)地址是相對(duì)于0編址2023/2/3內(nèi)存空間

按頁(yè)的大小劃分為大小相等的區(qū)域，稱(chēng)為塊或內(nèi)存塊（物理頁(yè)面，頁(yè)框）

在為進(jìn)程分配內(nèi)存時(shí)，以塊為單位將進(jìn)程中的若干個(gè)頁(yè)分別裝入到多個(gè)可以不相鄰接的物理塊中。由于進(jìn)程的最后一頁(yè)經(jīng)常不滿(mǎn)一塊而形成了不可利用的碎片稱(chēng)之為“頁(yè)內(nèi)碎片”邏輯上相鄰的頁(yè)，物理上不一定相鄰2023/2/3地址結(jié)構(gòu)

用戶(hù)程序的劃分是由系統(tǒng)自動(dòng)完成的，對(duì)用戶(hù)是透明的。一般，一頁(yè)的大小為2的整數(shù)次冪，因此，地址的高位部分為頁(yè)號(hào)，低位部分為頁(yè)內(nèi)地址頁(yè)號(hào)頁(yè)內(nèi)地址0111231頁(yè)號(hào)P頁(yè)內(nèi)位移量W編號(hào)0~1048575相對(duì)地址0~40952023/2/3

頁(yè)表將頁(yè)號(hào)和頁(yè)內(nèi)地址轉(zhuǎn)換成內(nèi)存地址，必須要有一個(gè)數(shù)據(jù)結(jié)構(gòu)，用來(lái)登記頁(yè)號(hào)和塊的對(duì)應(yīng)關(guān)系和有關(guān)信息。這樣的數(shù)據(jù)結(jié)構(gòu)稱(chēng)為頁(yè)表。頁(yè)表的作用就是實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射。2023/2/3頁(yè)表內(nèi)容頁(yè)表包含以下幾個(gè)表項(xiàng)：頁(yè)號(hào)：登記程序地址空間的頁(yè)號(hào)。塊號(hào)：登記相應(yīng)的頁(yè)所對(duì)應(yīng)的內(nèi)存塊號(hào)其它：登記與存儲(chǔ)信息保護(hù)有關(guān)的信息。頁(yè)號(hào)塊號(hào)其它05…165…213…2023/2/3地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)的任務(wù)是實(shí)現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換。即把程序地址轉(zhuǎn)換成內(nèi)存地址，這個(gè)轉(zhuǎn)換過(guò)程是在程序執(zhí)行過(guò)程中完成的，是動(dòng)態(tài)地址映射。在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，由系統(tǒng)提供的地址映射硬件來(lái)完成地址映射工作。2023/2/3例設(shè)頁(yè)長(zhǎng)為1K，程序地址字長(zhǎng)為16位，用戶(hù)程序空間和頁(yè)表如圖。

2023/2/3計(jì)算時(shí)要注意：若給出的地址字為16進(jìn)制，則將其轉(zhuǎn)換為二進(jìn)制，然后，根據(jù)頁(yè)長(zhǎng)及程序地址字的長(zhǎng)度，分別取出程序地址字的高幾位和低幾位就得到頁(yè)號(hào)及頁(yè)內(nèi)地址。如頁(yè)長(zhǎng)為2K，程序地址字為16位，則高5位為頁(yè)號(hào)，低11位為頁(yè)內(nèi)地址。2023/2/3若給出的地址字為10進(jìn)制，則用公式： 程序地址字/頁(yè)長(zhǎng)商為頁(yè)號(hào)，余數(shù)為頁(yè)內(nèi)地址。如程序地址為8457，

頁(yè)長(zhǎng)為4KB，則8457/4096可得：商為2，余數(shù)為256。2023/2/3快表和聯(lián)想存儲(chǔ)器在前述的頁(yè)地址變換過(guò)程中有一個(gè)嚴(yán)重的問(wèn)題，那就是每一次對(duì)內(nèi)存的訪問(wèn)都要訪問(wèn)頁(yè)表，頁(yè)表是放在內(nèi)存中的，也就是說(shuō)每一次訪問(wèn)內(nèi)存的指令至少要訪問(wèn)兩次內(nèi)存，運(yùn)行速度要下降一半。第一次訪問(wèn)內(nèi)存中的頁(yè)表，從中找到指定頁(yè)的物理塊號(hào)，再將塊號(hào)與頁(yè)內(nèi)偏移量W拼接，形成物理地址第二次訪問(wèn)內(nèi)存時(shí)，才是從第一次所得地址中獲得所需數(shù)據(jù)（獲向此地址中寫(xiě)入數(shù)據(jù)）2023/2/3解決這個(gè)問(wèn)題的一種方法是把頁(yè)表放在一組快速存儲(chǔ)器中（Cache），從而加快訪問(wèn)內(nèi)存的速度。我們把這種快速存儲(chǔ)器組成的頁(yè)表稱(chēng)為快表，把存放在內(nèi)存中的頁(yè)表稱(chēng)為慢表?？毂碛纸新?lián)想存儲(chǔ)器（associativememory）或TLB（Translationlookasidebuffers）用以存放當(dāng)前訪問(wèn)的那些頁(yè)表項(xiàng)2023/2/3p’頁(yè)表地址越界

L比較P>=Lpp’...快表

b+頁(yè)號(hào)p

頁(yè)內(nèi)地址dP’d物理地址頁(yè)表地址寄存器頁(yè)表長(zhǎng)度寄存器邏輯地址地址映射機(jī)制2023/2/3兩級(jí)頁(yè)表和多級(jí)頁(yè)表當(dāng)頁(yè)表項(xiàng)很多時(shí)，僅采用一級(jí)頁(yè)表需要大片連續(xù)空間，可將頁(yè)表也分頁(yè)，并對(duì)頁(yè)表所占的空間進(jìn)行索引形成外層頁(yè)表。由此構(gòu)成二級(jí)頁(yè)表。更進(jìn)一步可形成多級(jí)頁(yè)表。

2023/2/3二級(jí)頁(yè)表結(jié)構(gòu)及地址映射2023/2/3頁(yè)式存儲(chǔ)管理方案小結(jié)優(yōu)點(diǎn)：解決了碎片問(wèn)題便于管理

可以使程序和數(shù)據(jù)存放在不連續(xù)的主存空間缺點(diǎn)：不易實(shí)現(xiàn)共享不便于動(dòng)態(tài)連接 頁(yè)表都有可能占用較大的存儲(chǔ)空間。 要求有相應(yīng)的硬件支持，從而增加了系統(tǒng)成本，也增加了系統(tǒng)開(kāi)銷(xiāo)2023/2/3（2）分段管理方式引入段式管理方式主要是為了滿(mǎn)足用戶(hù)和程序員的需要方便用戶(hù)：用戶(hù)希望邏輯分段信息共享信息保護(hù)動(dòng)態(tài)增長(zhǎng)動(dòng)態(tài)連接2023/2/3分段系統(tǒng)基本原理分段用戶(hù)程序劃分按程序自身的邏輯關(guān)系劃分為若干個(gè)程序段，每個(gè)程序段都有一個(gè)段名，且有一個(gè)段號(hào)。段號(hào)從0開(kāi)始，每一段段內(nèi)也從0開(kāi)始編址，段內(nèi)地址是連續(xù)的。段的長(zhǎng)度由相應(yīng)的邏輯信息組的長(zhǎng)度決定，因而各段長(zhǎng)度不等。邏輯地址：由段號(hào)和段內(nèi)地址組成段號(hào)段內(nèi)地址2023/2/3內(nèi)存劃分內(nèi)存空間被動(dòng)態(tài)的劃分為若干個(gè)長(zhǎng)度不相同的區(qū)域，稱(chēng)為物理段，每個(gè)物理段由起始地址和長(zhǎng)度確定內(nèi)存分配

以段為單位分配內(nèi)存，每一個(gè)段在內(nèi)存中占據(jù)連續(xù)空間（內(nèi)存隨機(jī)分割，需要多少分配多少），但各段之間可以不連續(xù)存放2023/2/3段表段映射表。每個(gè)程序有一個(gè)段表程序的每個(gè)段在表中占有一個(gè)表項(xiàng)，其中記錄了該段在內(nèi)存中的起始地址和段的長(zhǎng)度。可放在內(nèi)存中，也可放在寄存器中。段表是用于實(shí)現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射。

段號(hào)012段首址段長(zhǎng)度58K20K100K110K260K140K2023/2/33、地址變換機(jī)構(gòu)段地址映射過(guò)程為：系統(tǒng)中設(shè)置了段表寄存器，用于存放段表始址和段表長(zhǎng)度TL。取出段號(hào)S和段內(nèi)位移W。若S>TL，段號(hào)太大—越界。根據(jù)段表始址找到段表，查找段號(hào)為S的表目，得到該段在內(nèi)存的起始地址。檢查段內(nèi)地址d是否起過(guò)該段的段長(zhǎng)SL。若超過(guò)越界。把段首地址與段內(nèi)位移相加，形成內(nèi)存物理地址。2023/2/3地址變換機(jī)構(gòu)2023/2/3同頁(yè)地址變換一樣，在段地址變換過(guò)程中，也有兩次訪問(wèn)內(nèi)存的問(wèn)題。為了加快訪問(wèn)內(nèi)存的速度也可采用快速存儲(chǔ)器組成快表。2023/2/3

Cl

Cb+段號(hào)S段內(nèi)地址d比較比較b

+d段表S>=Cl快表物理地址段表始址寄存器段表長(zhǎng)度寄存器邏輯地址Lb...SLb地址越界d>=Ld>=L地址映射及存儲(chǔ)保護(hù)機(jī)制地址越界地址越界比較2023/2/3段式存儲(chǔ)管理方案小結(jié)優(yōu)點(diǎn)：便于動(dòng)態(tài)申請(qǐng)內(nèi)存管理和使用統(tǒng)一化便于共享便于動(dòng)態(tài)鏈接缺點(diǎn)：產(chǎn)生外部碎片2023/2/3（3）段頁(yè)式存儲(chǔ)管理方式產(chǎn)生背景:結(jié)合頁(yè)式段式優(yōu)點(diǎn)，克服二者的缺點(diǎn)基本原理地址變換過(guò)程2023/2/3基本原理用戶(hù)程序劃分 按段式劃分（對(duì)用戶(hù)來(lái)講，按段的邏輯關(guān)系進(jìn)行劃分；對(duì)系統(tǒng)講，按頁(yè)劃分每一段）邏輯地址內(nèi)存劃分 按頁(yè)式存儲(chǔ)管理方案內(nèi)存分配 以頁(yè)為單位進(jìn)行分配段號(hào)段內(nèi)地址頁(yè)號(hào)頁(yè)內(nèi)地址2023/2/3段表：記錄了每一段的頁(yè)表始址和頁(yè)表長(zhǎng)度頁(yè)表：記錄了邏輯頁(yè)號(hào)與內(nèi)存塊號(hào)的對(duì)應(yīng)關(guān)系（每一段有一個(gè)，一個(gè)程序可能有多個(gè)頁(yè)表）內(nèi)存分配管理：同頁(yè)式管理地址變換過(guò)程2023/2/3圖4-21利用段表和頁(yè)表實(shí)現(xiàn)地址映射

2023/2/3地址變換過(guò)程圖4-22段頁(yè)式系統(tǒng)中的地址變換機(jī)構(gòu)2023/2/3在段頁(yè)式系統(tǒng)中，為了獲得一條指令數(shù)據(jù)，須三次訪問(wèn)內(nèi)存。1、訪問(wèn)內(nèi)存中的段表，從中取得頁(yè)表始址2、訪問(wèn)內(nèi)存中的頁(yè)表，從中取出該頁(yè)所在的物理塊號(hào)，將該塊號(hào)與頁(yè)內(nèi)地址一起形成指令或數(shù)據(jù)的物理地址3、從物理地址中取出指令或數(shù)據(jù)?？毂淼刂纷儞Q過(guò)程2023/2/3總結(jié)固定分區(qū)的分配方式會(huì)產(chǎn)生內(nèi)零頭，因?yàn)槭钦页鲆粋€(gè)滿(mǎn)足作業(yè)要求的空閑分區(qū)分配給作業(yè)，大小不一定剛好合適，分區(qū)中有一部分存儲(chǔ)空間會(huì)被浪費(fèi)。在可變式分區(qū)分配中，是按照作業(yè)的大小找出一個(gè)分區(qū)來(lái)分配如果大于作業(yè)申請(qǐng)的空間，則一分為二，剩下的一分部作為系統(tǒng)的空閑分區(qū)，有可能很小無(wú)法利用而成為外零頭。2023/2/3總結(jié)為了解決外零頭的問(wèn)題，提出了離散的分配方式，在分頁(yè)式存儲(chǔ)管理中，存儲(chǔ)空間被分面與頁(yè)大小相等的物理塊，作業(yè)的大小不可能都是物理塊的整數(shù)倍，因此在作業(yè)的最后一頁(yè)中有可能有部分空間未被利用，屬于內(nèi)零頭。分段式存儲(chǔ)管理中，其內(nèi)存分配方式類(lèi)似于動(dòng)態(tài)分區(qū)的分配，因此會(huì)產(chǎn)生外零頭。段頁(yè)式存儲(chǔ)管理中，其內(nèi)存分配方式類(lèi)似于頁(yè)式的分配，因此會(huì)產(chǎn)生內(nèi)零頭。2023/2/3（二）

虛擬內(nèi)存管理考試大綱要求1.

虛擬內(nèi)存基本概念

2.

請(qǐng)求分頁(yè)管理方式

3.

頁(yè)面置換算法

最佳置換算法（OPT）；先進(jìn)先出置換算法（FIFO）；最近最少使用置換算法（LRU）；時(shí)鐘置換算法（CLOCK）。

4.

頁(yè)面分配策略

5.

抖動(dòng)

抖動(dòng)現(xiàn)象；工作集。

2023/2/31虛擬內(nèi)存基本概念程序局部性原理時(shí)間局部性一條指令被執(zhí)行了，則在不久的將來(lái)它可能再被執(zhí)行，如果某數(shù)據(jù)被訪問(wèn)過(guò)，則不久以后該數(shù)據(jù)可能再次被訪問(wèn)。（循環(huán)操作）空間局部性若某一存儲(chǔ)單元被使用，則在一定時(shí)間內(nèi)，與該存儲(chǔ)單元相鄰的單元可能被使用，即程序在一段時(shí)間內(nèi)所訪問(wèn)的地址，可能集中在一定的范圍之內(nèi)。（程序順序執(zhí)行）2023/2/3虛擬存儲(chǔ)器的定義虛擬存儲(chǔ)器是指僅把作業(yè)的一部分裝入內(nèi)存便可運(yùn)行作業(yè)的存儲(chǔ)器系統(tǒng)。具體地說(shuō)，所謂虛擬存儲(chǔ)器是指具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)主存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。實(shí)際上，用戶(hù)所看到的大容量只是一種感覺(jué)，是虛的，故而得名虛擬存儲(chǔ)器。2023/2/32.請(qǐng)求分頁(yè)式存儲(chǔ)管理它是建立在純分頁(yè)基礎(chǔ)上的，增加了請(qǐng)求調(diào)頁(yè)功能、頁(yè)面置換功能所形成的請(qǐng)求分頁(yè)存儲(chǔ)管理系統(tǒng)。把作業(yè)分成大小相等的若干頁(yè)，把主存分成與頁(yè)大小相等的若干塊；對(duì)每個(gè)作業(yè)限定分給它的主存塊數(shù)，先把作業(yè)的部分頁(yè)裝入主存的這些塊中，在作業(yè)運(yùn)行時(shí)再裝入所需要的頁(yè)。2023/2/3采用的數(shù)據(jù)結(jié)構(gòu)（1）頁(yè)表頁(yè)表用來(lái)記錄作業(yè)的分配情況。（2）缺頁(yè)中斷機(jī)構(gòu)在請(qǐng)求分頁(yè)系統(tǒng)中，每當(dāng)所要訪問(wèn)的頁(yè)面不在主存時(shí)，便要產(chǎn)生一次缺頁(yè)中斷，請(qǐng)求操作將所缺的頁(yè)調(diào)入主存。（3）地址變換機(jī)構(gòu)2023/2/3頁(yè)表表項(xiàng)頁(yè)號(hào)、內(nèi)存塊號(hào)、狀態(tài)位、訪問(wèn)位、修改位、外存地址 狀態(tài)位P：表示該頁(yè)是否已調(diào)入內(nèi)存，供程序訪問(wèn)時(shí)參考訪問(wèn)位A：用于記錄本頁(yè)在一段時(shí)間內(nèi)被訪問(wèn)的次數(shù)或最近已有多長(zhǎng)時(shí)間未被訪問(wèn)，供選擇換出頁(yè)面時(shí)參考頁(yè)號(hào)內(nèi)存塊號(hào)狀態(tài)位P訪問(wèn)位A修改位M外存地址2023/2/3頁(yè)表表項(xiàng)頁(yè)號(hào)、內(nèi)存塊號(hào)、駐留位、外存地址、訪問(wèn)位、修改位 修改位：查看此頁(yè)是否在內(nèi)存中被修改過(guò)，供置換頁(yè)面時(shí)參考。外存地址：該頁(yè)存放在外存上的地址。供調(diào)入該頁(yè)時(shí)參考。頁(yè)號(hào)內(nèi)存塊號(hào)狀態(tài)位P訪問(wèn)位A修改位M外存地址2023/2/3缺頁(yè)中斷（PageFault）機(jī)構(gòu)缺頁(yè)中斷機(jī)構(gòu)在請(qǐng)求分頁(yè)系統(tǒng)中，每當(dāng)所要訪問(wèn)的頁(yè)面不在主存時(shí)，便要產(chǎn)生一次缺頁(yè)中斷，請(qǐng)求操作將所缺的頁(yè)調(diào)入主存。缺頁(yè)中斷作為中斷，它同樣需要經(jīng)歷諸如保護(hù)CPU環(huán)境、分析中斷原因、轉(zhuǎn)入缺頁(yè)中斷處理程序進(jìn)行處理、恢復(fù)CPU環(huán)境等幾個(gè)步驟。

2023/2/3缺頁(yè)中斷同一般中斷的區(qū)別？缺頁(yè)中斷同一般中斷都是中斷，相同點(diǎn)是：保護(hù)現(xiàn)場(chǎng)中斷處理恢復(fù)現(xiàn)場(chǎng)不同點(diǎn)：在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)。一般中斷是一條指令完成后中斷，缺頁(yè)中斷是一條指令執(zhí)行時(shí)，發(fā)現(xiàn)所要訪問(wèn)的指令或數(shù)據(jù)不在內(nèi)存時(shí)所產(chǎn)生的中斷一條指令執(zhí)行時(shí)可能產(chǎn)生多個(gè)缺頁(yè)中斷。如指令可能訪問(wèn)多個(gè)內(nèi)存地址，這些地址在不同的頁(yè)中。2023/2/3下圖用數(shù)字標(biāo)出了缺頁(yè)中斷的處理過(guò)程：根據(jù)當(dāng)前執(zhí)行指令中的虛擬地址，形成數(shù)對(duì)：（頁(yè)號(hào)，頁(yè)內(nèi)位移）。用頁(yè)號(hào)去查頁(yè)表，判斷該頁(yè)是否在內(nèi)存儲(chǔ)器中若該頁(yè)的R位（缺頁(yè)中斷位）為“0”，表示當(dāng)前該頁(yè)不在內(nèi)存，于是產(chǎn)生缺頁(yè)中斷，讓操作系統(tǒng)的中斷處理程序進(jìn)行中斷處理。中斷處理程序去查存儲(chǔ)分塊表，尋找一個(gè)空閑的內(nèi)存塊；查頁(yè)表，得到該頁(yè)在輔助存儲(chǔ)器上的位置，并啟動(dòng)磁盤(pán)讀信息。把從磁盤(pán)上讀出的信息裝入到分配的內(nèi)存塊中。根據(jù)分配存儲(chǔ)塊的信息，修改頁(yè)表中相應(yīng)的表目?jī)?nèi)容，即將表目中的R位設(shè)置成為“1”，表示該頁(yè)已在內(nèi)存中，在B位填入所分配的塊號(hào)。另外，還要修改存儲(chǔ)分塊表里相應(yīng)表目的狀態(tài)。由于產(chǎn)生缺頁(yè)中斷的那條指令并沒(méi)有執(zhí)行，所以在完成所需頁(yè)面的裝入工作后，應(yīng)該返回原指令重新執(zhí)行。這時(shí)再執(zhí)行時(shí)，由于所需頁(yè)面已在內(nèi)存，因此可以順利執(zhí)行下去。2023/2/3頁(yè)面調(diào)入策略（1）何時(shí)調(diào)入（2）何處調(diào)入

（3）頁(yè)面調(diào)入過(guò)程2023/2/3何時(shí)調(diào)入（1）預(yù)調(diào)入采用一種以預(yù)測(cè)為基礎(chǔ)的調(diào)入策略，將預(yù)計(jì)不久要使用的頁(yè)調(diào)入主存。缺點(diǎn)：預(yù)計(jì)不準(zhǔn)場(chǎng)合：進(jìn)程的首次調(diào)入（2）請(qǐng)求調(diào)入當(dāng)發(fā)生缺頁(yè)時(shí)，提出請(qǐng)求，由系統(tǒng)調(diào)入優(yōu)點(diǎn)：命中率100%，實(shí)現(xiàn)簡(jiǎn)單缺點(diǎn)：開(kāi)銷(xiāo)大，每次只調(diào)入一頁(yè)場(chǎng)合：大多數(shù)2023/2/3何處調(diào)入磁盤(pán)分對(duì)換區(qū)和文件區(qū)，有不同。（1）磁盤(pán)有足夠的對(duì)換區(qū)時(shí)，全部從對(duì)換區(qū)調(diào)入頁(yè)面。運(yùn)行前拷入對(duì)換區(qū)（2）磁盤(pán)無(wú)足夠的對(duì)換區(qū)時(shí)，修改過(guò)的部分從對(duì)換區(qū)調(diào)入頁(yè)面，沒(méi)修改的部分從文件區(qū)調(diào)入。（3）UNIX方式：運(yùn)行過(guò)的頁(yè)面從對(duì)換區(qū)調(diào)入，未運(yùn)行的頁(yè)面從文件區(qū)調(diào)入2023/2/3頁(yè)面調(diào)入過(guò)程保護(hù)現(xiàn)場(chǎng)轉(zhuǎn)中斷處理程序查頁(yè)表，找到頁(yè)的外存地址內(nèi)存未滿(mǎn)則調(diào)入，修改頁(yè)表內(nèi)存已滿(mǎn)，則先置換。被置換的頁(yè)若被修改過(guò)，則寫(xiě)入磁盤(pán)。將缺頁(yè)調(diào)入內(nèi)存，修改頁(yè)表和快表再訪內(nèi)存2023/2/33.頁(yè)面置換算法（1）最佳置換算法（OPT）（2）先進(jìn)先出置換算法（FIFO）（3）最近最久未使用算法（LRU）（4）Clock置換算法2023/2/3最佳置換算法理想淘汰算法—最佳頁(yè)面算法（OPT）選擇以后永不使用的，或許是在最長(zhǎng)(未來(lái))時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面淘汰。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁(yè)率。2023/2/3最佳置換算法假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下的頁(yè)面號(hào)引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

進(jìn)程運(yùn)行時(shí)，先將7，0，1三個(gè)頁(yè)面裝入內(nèi)存。以后，當(dāng)進(jìn)程要訪問(wèn)頁(yè)面2時(shí)，將會(huì)產(chǎn)生缺頁(yè)中斷。此時(shí)OS根據(jù)最佳置換算法，將選擇頁(yè)面7予以淘汰。

2023/2/3先進(jìn)先出頁(yè)面置換算法先進(jìn)先出（FIFO）是人們最容易想到的頁(yè)面淘汰算法。其做法是當(dāng)要進(jìn)行頁(yè)面淘汰時(shí)，總是把最早進(jìn)入內(nèi)存的頁(yè)面作為淘汰的對(duì)象。2023/2/3最近最久未用（LRU）置換算法的著眼點(diǎn)是在要進(jìn)行頁(yè)面置換時(shí)，檢查這些頁(yè)面的被訪問(wèn)時(shí)間，總是把最長(zhǎng)時(shí)間未被訪問(wèn)過(guò)的頁(yè)面置換出去。這是一種基于程序局部性原理的置換算法。也就是說(shuō)，該算法認(rèn)為如果一個(gè)頁(yè)面剛被訪問(wèn)過(guò)，那么不久的將來(lái)被訪問(wèn)的可能性就大；否則被訪問(wèn)的可能性就小。最近最久未使用（LRU）置換算法2023/2/31.LRU(LeastRecentlyUsed)置換算法的描述

4.7.2最近最久未使用（LRU）置換算法2023/2/34.7.3Clock置換算法

1.簡(jiǎn)單的Clock置換算法圖4-30簡(jiǎn)單Clock置換算法的流程和示例2023/2/32023/2/32.改進(jìn)型Clock置換算法由訪問(wèn)位A和修改位M可以組合成下面四種類(lèi)型的頁(yè)面：

1類(lèi)(A=0,M=0):

表示該頁(yè)最近既未被訪問(wèn)，又未被修改，是最佳淘汰頁(yè)。

2類(lèi)(A=0,M=1)：表示該頁(yè)最近未被訪問(wèn)，但已被修改，并不是很好的淘汰頁(yè)。

3類(lèi)(A=1,M=0)：最近已被訪問(wèn)，但未被修改，該頁(yè)有可能再被訪問(wèn)。

4類(lèi)(A=1,M=1):

最近已被訪問(wèn)且被修改，該頁(yè)可能再被訪問(wèn)。2023/2/3其執(zhí)行過(guò)程可分成以下三步：

(1)從指針?biāo)甘镜漠?dāng)前位置開(kāi)始，掃描循環(huán)隊(duì)列，尋找A=0且M=0的第一類(lèi)頁(yè)面，將所遇到的第一個(gè)頁(yè)面作為所選中的淘汰頁(yè)。在第一次掃描期間不改變?cè)L問(wèn)位A。

(2)如果第一步失敗，即查找一周后未遇到第一類(lèi)頁(yè)面，則開(kāi)始第二輪掃描，尋找A=0且M=1的第二類(lèi)頁(yè)面，將所遇到的第一個(gè)這類(lèi)頁(yè)面作為淘汰頁(yè)。在第二輪掃描期間，將所有掃描過(guò)的頁(yè)面的訪問(wèn)位都置0。

(3)如果第二步也失敗，亦即未找到第二類(lèi)頁(yè)面，則將指針?lè)祷氐介_(kāi)始的位置，并將所有的訪問(wèn)位復(fù)0。然后重復(fù)第一步，如果仍失敗，必要時(shí)再重復(fù)第二步，此時(shí)就一定能找到被淘汰的頁(yè)。2023/2/34、頁(yè)面分配策略?xún)?nèi)存分配策略：固定和可變置換策略：全局和局部組合成3種合適的策略：固定分配局部置換可變分配全局置換可變分配局部置換2023/2/35.工作集由于程序的局部性原理，進(jìn)程在一段時(shí)間內(nèi)集中訪問(wèn)一些固定頁(yè)面的子集稱(chēng)為該進(jìn)程的工作集。為了減少進(jìn)程訪問(wèn)中的缺頁(yè)次數(shù)，為每個(gè)進(jìn)程分配一定數(shù)量的頁(yè)框作為工作集使用。2023/2/35.抖動(dòng)采用某個(gè)淘汰算法淘汰一頁(yè)時(shí)，如果算法選擇不當(dāng)，就會(huì)出現(xiàn)這樣的現(xiàn)象：剛被淘汰的頁(yè)面馬上又要用，因而要把它調(diào)入。調(diào)入不久再被淘汰，淘汰不久再次裝入。如此反復(fù)，使整個(gè)系統(tǒng)處于頻繁地調(diào)入調(diào)出狀態(tài)，大降低系統(tǒng)的處理效率，這種現(xiàn)象叫抖動(dòng)。如果分配給進(jìn)程的物理塊號(hào)數(shù)與當(dāng)前工作集大小一致，可以有效避免抖動(dòng)現(xiàn)象。在實(shí)際中，可以通過(guò)調(diào)整淘汰算法，或者根據(jù)缺頁(yè)率的大小動(dòng)態(tài)的分配給進(jìn)程物理頁(yè)塊，都可以防止抖動(dòng)的發(fā)生。2023/2/3第4章文件管理（一）

文件系統(tǒng)基礎(chǔ)

1.

文件概念

2.

文件邏輯結(jié)構(gòu)

順序文件；索引文件；索引順序文件。

3.

目錄結(jié)構(gòu)

文件控制塊和索引節(jié)點(diǎn)；單級(jí)目錄結(jié)構(gòu)和兩級(jí)目錄結(jié)構(gòu)；樹(shù)形目錄結(jié)構(gòu)；圖形目錄結(jié)構(gòu)。

4.

文件共享

5.

文件保護(hù)

訪問(wèn)類(lèi)型；訪問(wèn)控制。

2023/2/31文件概念文件是指具有文件名的若干相關(guān)元素的集合。元素通常是記錄。記錄是一組有意義的數(shù)據(jù)項(xiàng)集合。文件類(lèi)型

2023/2/3文件操作用戶(hù)通過(guò)文件系統(tǒng)所提供的系統(tǒng)調(diào)用實(shí)施對(duì)文件的操作。1、最基本的文件操作有：創(chuàng)建、刪除、讀、寫(xiě)、截?cái)辔募驮O(shè)置文件的讀、寫(xiě)位置2023/2/3文件操作2、文件的“打開(kāi)”和“關(guān)閉”操作所謂“打開(kāi)”，是指系統(tǒng)將指名文件的屬性(包括該文件在外存上的物理位置)從外存拷貝到內(nèi)存打開(kāi)文件表的一個(gè)表目中，并將該表目的編號(hào)(或稱(chēng)為索引)返回給用戶(hù)。以后，當(dāng)用戶(hù)再要求對(duì)該文件進(jìn)行相應(yīng)的操作時(shí)，便可利用系統(tǒng)所返回的索引號(hào)向系統(tǒng)提出操作請(qǐng)求。系統(tǒng)這時(shí)便可直接利用該索引號(hào)到打開(kāi)文件表中去查找，從而避免了對(duì)該文件的再次檢索。這樣不僅節(jié)省了大量的檢索開(kāi)銷(xiāo)，也顯著地提高了對(duì)文件的操作速度。如果用戶(hù)已不再需要對(duì)該文件實(shí)施相應(yīng)的操作時(shí)，可利用“關(guān)閉”(close)系統(tǒng)調(diào)用來(lái)關(guān)閉此文件，OS將會(huì)把該文件從打開(kāi)文件表中的表目上刪除掉。

2023/2/32文件邏輯結(jié)構(gòu)對(duì)于任何一個(gè)文件，都存在著兩種形式的結(jié)構(gòu)

文件的邏輯結(jié)構(gòu)

文件的物理結(jié)構(gòu)

對(duì)邏輯結(jié)構(gòu)的基本要求提高檢索速度便于修改降低文件的存儲(chǔ)費(fèi)用2023/2/3文件邏輯結(jié)構(gòu)的類(lèi)型1、有結(jié)構(gòu)文件由一個(gè)以上的記錄構(gòu)成的文件。記錄式文件：每個(gè)記錄都用于描述實(shí)體集中的一個(gè)實(shí)體，各記錄有著相同或不同數(shù)目的數(shù)據(jù)項(xiàng)。記錄的長(zhǎng)度可分為定長(zhǎng)和不定長(zhǎng)兩類(lèi)2023/2/3定長(zhǎng)記錄：文件中所有記錄的長(zhǎng)度相等。文件長(zhǎng)度用記錄數(shù)目表示。處理方便，開(kāi)銷(xiāo)小。變長(zhǎng)記錄：文件中的記錄長(zhǎng)度不相等。組織形式順序文件索引文件索引順序文件2023/2/32、無(wú)結(jié)構(gòu)文件由字符流構(gòu)成的文件如果說(shuō)大量的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫(kù)，是采用有結(jié)構(gòu)的文件形式的話(huà)，則大量的源程序、可執(zhí)行文件、庫(kù)函數(shù)等，所采用的就是無(wú)結(jié)構(gòu)的文件形式，即流式文件。長(zhǎng)度以字節(jié)為單位。

2023/2/3（1）順序文件對(duì)順序文件(SequentialFile)的讀/寫(xiě)操作圖6-3定長(zhǎng)和變長(zhǎng)記錄文件2023/2/3（1）順序文件順序文件的優(yōu)缺點(diǎn)順序文件的最佳應(yīng)用場(chǎng)合，是在對(duì)諸記錄進(jìn)行批量存取時(shí)，即每次要讀或?qū)懸淮笈涗?。此時(shí)，對(duì)順序文件的存取效率是所有邏輯文件中最高的。在交互應(yīng)用的場(chǎng)合，如果用戶(hù)(程序)要求查找或修改單個(gè)記錄，為此系統(tǒng)便要去逐個(gè)地查找諸記錄。如果想增加或刪除一個(gè)記錄，都比較困難。

2023/2/3（2）索引文件為了解決這一問(wèn)題，可為變長(zhǎng)記錄文件建立一張索引表，對(duì)主文件中的每個(gè)記錄，在索引表中設(shè)有一個(gè)相應(yīng)的表項(xiàng)，用于記錄該記錄的長(zhǎng)度L及指向該記錄的指針。由于索引表是按記錄鍵排序的，因此索引表本身是一個(gè)定長(zhǎng)記錄的順序文件，從而也就可以方便地實(shí)現(xiàn)直接存取。2023/2/3（2）索引文件圖6-4索引文件的組織2023/2/3（2）索引文件索引文件可有較快的檢索速度，故它主要用于對(duì)信息處理的及時(shí)性要求較高的場(chǎng)合。但它除了有主文件外，還須配置一張索引表，且每個(gè)記錄都要有一個(gè)索引項(xiàng)，因此提高了存儲(chǔ)費(fèi)用2023/2/3（3）索引順序文件圖6-5索引順序文件索引順序文件，將順序文件中的所有記錄分為若干個(gè)組，每組中的第一個(gè)記錄建立一個(gè)索引項(xiàng)2023/2/33目錄結(jié)構(gòu)現(xiàn)代計(jì)算機(jī)系統(tǒng)中，對(duì)大量的文件實(shí)施有效的管理，主要是通過(guò)文件目錄實(shí)現(xiàn)的。文件目錄也是一種數(shù)據(jù)結(jié)構(gòu)，用于標(biāo)識(shí)系統(tǒng)的文件及其物理地址，供檢索時(shí)使用。對(duì)目錄管理的要求如下：(1)實(shí)現(xiàn)“按名存取”。(2)提高對(duì)目錄的檢索速度。(3)文件共享。(4)允許文件重名。

2023/2/3文件控制塊和索引結(jié)點(diǎn)文件控制塊（FCB）：文件控制塊是操作系統(tǒng)為管理文件而設(shè)置的數(shù)據(jù)結(jié)構(gòu)，存放了為管理文件所需的所有有關(guān)信息，文件管理程序可借助于文件控制塊中的信息，對(duì)文件施以各種操作。文件控制塊是文件存在的標(biāo)志，文件與文件控制塊一一對(duì)應(yīng)，文件控制塊的有序集合稱(chēng)為文件目錄2023/2/3文件目錄：把所有的FCB組織在一起，就構(gòu)成了文件目錄，即文件控制塊的有序集合目錄項(xiàng)：構(gòu)成文件目錄的項(xiàng)目（目錄項(xiàng)就是FCB）目錄文件：為了實(shí)現(xiàn)對(duì)文件目錄的管理，通常將文件目錄以文件的形式保存在外存，這個(gè)文件就叫目錄文件2023/2/3(2)索引結(jié)點(diǎn)文件目錄是存放在磁盤(pán)上的，當(dāng)文件很多時(shí)，文件目錄可能要占用大量的盤(pán)塊。在查找目錄的過(guò)程中，先將存放目錄文件的第一個(gè)盤(pán)塊中的目錄調(diào)入內(nèi)存，然后把用戶(hù)所給定的文件名與目錄項(xiàng)中的文件名逐一比較。若未找到指定文件，便再將下一個(gè)盤(pán)塊中的目錄項(xiàng)調(diào)入內(nèi)存。在檢索目錄文件的過(guò)程中，我們發(fā)現(xiàn)只用到了文件名，其它信息在檢索目錄時(shí)一概不用，所以也不需調(diào)入內(nèi)存。將文件名與文件描述信息分開(kāi)。文件描述信息單獨(dú)形成一個(gè)稱(chēng)為索引結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，在文件目錄中每個(gè)目錄項(xiàng)只存文件名和指向該文件索引結(jié)點(diǎn)的指針。索引結(jié)點(diǎn)還有磁盤(pán)索引結(jié)點(diǎn)與內(nèi)存索引結(jié)點(diǎn)之分。2023/2/3(2)索引結(jié)點(diǎn)2023/2/3目錄結(jié)構(gòu)（1）單級(jí)目錄結(jié)構(gòu)為所有文件建立一個(gè)目錄文件（組成一線性表）文件名物理地址文件說(shuō)明狀態(tài)位文件名1文件名2…單級(jí)目錄2023/2/3基本原理它采用的方法是為外存的全部文件設(shè)立一張目錄表。表中包括全部文件的文件名、存儲(chǔ)文件的物理地址，以及文件的其他屬性，如文件長(zhǎng)度、文件類(lèi)型等等。每個(gè)文件占據(jù)表中的一條記錄。該目錄表存放在外存的某個(gè)固定區(qū)域，需要時(shí)系統(tǒng)將其全部或部分調(diào)入主存?；静僮鳎航?，刪除優(yōu)點(diǎn)（1）目錄結(jié)構(gòu)易于實(shí)現(xiàn)，管理簡(jiǎn)單（2）能實(shí)現(xiàn)按名存取缺點(diǎn)：(1)查找速度慢：平均n/2(2)不允許重名(3)不便于實(shí)現(xiàn)文件共享單級(jí)目錄結(jié)構(gòu)2023/2/3（2）二級(jí)目錄結(jié)構(gòu)為了克服單級(jí)目錄的缺點(diǎn)，為每一個(gè)用戶(hù)建立一個(gè)單獨(dú)的用戶(hù)文件目錄UFD。二級(jí)文件目錄結(jié)構(gòu)把目錄分成主目錄和用戶(hù)文件目錄兩級(jí)。主目錄由用戶(hù)名和用戶(hù)文件目錄首地址組成，用戶(hù)文件目錄中登記相應(yīng)的用戶(hù)文件的目錄項(xiàng)。2023/2/3（2）兩級(jí)目錄兩級(jí)目錄結(jié)構(gòu)2023/2/3在二級(jí)目錄結(jié)構(gòu)中，區(qū)別不同的文件除文件名外還有文件的用戶(hù)名，因此不同的用戶(hù)可以使用相同的文件名。例如用戶(hù)Zhang中使用文件名Test，用戶(hù)Wang也可使用文件名Test，因?yàn)闃?biāo)識(shí)這兩個(gè)文件時(shí)還要加上用戶(hù)名，Zhang：Test和Wang：Test，不致于造成混淆。

2023/2/3優(yōu)點(diǎn)：提高了檢索目錄的速度:m+n(2)在不同的用戶(hù)目錄中，可以使用相同的文件名。(3)不同用戶(hù)還可使用不同的文件名來(lái)訪問(wèn)系統(tǒng)中的同一個(gè)共享文件（4）可實(shí)現(xiàn)對(duì)文件的保護(hù)和保密作用。缺點(diǎn):(1)二級(jí)文件目錄雖然解決了不同用戶(hù)之間文件同名的問(wèn)題，但同一用戶(hù)的文件不能同名。(2)如果一個(gè)用戶(hù)擁有很多的文件，那么在他的目錄中進(jìn)行查找，所花費(fèi)的時(shí)間仍然會(huì)很長(zhǎng)(3)缺乏靈活性。（2）二級(jí)目錄結(jié)構(gòu)2023/2/3（3）多級(jí)目錄結(jié)構(gòu)1)目錄結(jié)構(gòu)多級(jí)目錄結(jié)構(gòu)由根目錄和各級(jí)目錄組成，為管理上的方便，除根目錄外，其它各級(jí)目錄均以文件的形式組成目錄文件。根目錄中的每個(gè)目錄項(xiàng)可以對(duì)應(yīng)一個(gè)目錄文件，也可以對(duì)應(yīng)一個(gè)數(shù)據(jù)文件，同樣目錄文件中的每個(gè)目錄項(xiàng)可以對(duì)應(yīng)一個(gè)目錄文件，也可以對(duì)應(yīng)一個(gè)數(shù)據(jù)文件。如此類(lèi)推，就形成多級(jí)目錄結(jié)構(gòu)。也稱(chēng)樹(shù)形目錄結(jié)構(gòu)2023/2/32023/2/32）路徑名在多級(jí)目錄結(jié)構(gòu)中一個(gè)文件的唯一標(biāo)識(shí)不再是文件名，而是從根結(jié)點(diǎn)開(kāi)始，經(jīng)過(guò)一個(gè)或多個(gè)中間結(jié)點(diǎn)，到達(dá)某個(gè)葉結(jié)點(diǎn)的一條路徑。稱(chēng)這條路徑為文件的路徑名，它是文件的唯一標(biāo)識(shí)。路徑名由根目錄和所經(jīng)過(guò)的目錄名和文件名以及分隔符組成，通常使用分隔符/。例如/d1/f1，/d2/d5/f3，/f7

2023/2/33）當(dāng)前目錄在多級(jí)目錄結(jié)構(gòu)中，文件路徑名一般較長(zhǎng)，而用戶(hù)總是局部地使用文件，為了方便起見(jiàn)，可把經(jīng)常使用的文件所在的目錄指定為工作目錄。查詢(xún)時(shí)，若路徑名以/開(kāi)頭；則從根目錄開(kāi)始查找，否則從當(dāng)前目錄開(kāi)始查找。相對(duì)路徑名，絕對(duì)路徑名2023/2/3（4）圖形目錄結(jié)構(gòu)加了鏈接的樹(shù)形目錄結(jié)構(gòu)。2023/2/34.文件共享基本概念文件共享是指一個(gè)文件可以被多個(gè)授權(quán)的用戶(hù)共同使用。文件的共享要解決兩個(gè)問(wèn)題。一是如何實(shí)現(xiàn)共享，二是對(duì)各類(lèi)共享文件的用戶(hù)進(jìn)行存取控制。早期實(shí)現(xiàn)文件共享的方法（1）繞彎路法（2）連訪法（3）基本文件法2023/2/34.文件共享共享方式硬鏈接軟鏈接（符號(hào)鏈接）2023/2/3硬鏈接

記錄的是目標(biāo)文件的索引結(jié)點(diǎn)。它只能鏈接文件，不能鏈接目錄，不能跨文件系統(tǒng)。創(chuàng)建鏈接時(shí)，將增加目標(biāo)文件的引用計(jì)數(shù)。刪除目標(biāo)文件或鏈接文件時(shí)都會(huì)導(dǎo)致引用計(jì)數(shù)的減少。2023/2/3基于索引結(jié)點(diǎn)的共享方式2023/2/3符號(hào)鏈接利用符號(hào)鏈實(shí)現(xiàn)文件共享

由系統(tǒng)創(chuàng)建一個(gè)LINK類(lèi)型的新文件，與共享文件名相同，并將其寫(xiě)入B的目錄中。新文件中只包含被鏈接文件的路徑名，這樣的鏈接方法被稱(chēng)為符號(hào)鏈接。新文件中的路徑名被看作是符號(hào)鏈。當(dāng)B要訪問(wèn)被鏈接的文件時(shí)，讀LINK類(lèi)文件，OS根據(jù)新文件中的路徑名去讀該文件，實(shí)現(xiàn)文件的共享。2023/2/3基于符號(hào)鏈的共享方式Owner=wang類(lèi)型：普通文件物理地址Owner=Lee類(lèi)型：LINK文件物理地址Test符號(hào)鏈2023/2/3符號(hào)鏈接

在利用符號(hào)鏈方式實(shí)現(xiàn)文件共享時(shí)，只是文件主才擁有指向其索引結(jié)點(diǎn)的指針；而共享該文件的其他用戶(hù)，則只有該文件的路徑名，并不擁有指向其索引結(jié)點(diǎn)的指針。這樣，也就不會(huì)發(fā)生在文件主刪除一共享文件后留下一懸空指針的情況。當(dāng)文件的擁有者把一個(gè)共享文件刪除后，其他用戶(hù)試圖通過(guò)符號(hào)鏈去訪問(wèn)一個(gè)已被刪除的共享文件時(shí)，會(huì)因系統(tǒng)找不到該文件而使訪問(wèn)失敗，于是再將符號(hào)鏈刪除，此時(shí)不會(huì)產(chǎn)生任何影響。創(chuàng)建符號(hào)鏈接不會(huì)增加目標(biāo)文件的引用計(jì)數(shù)。2023/2/3符號(hào)鏈接

優(yōu)點(diǎn)：可以用于鏈接世界上任何地方的機(jī)器中的文件。缺點(diǎn)：當(dāng)其他用戶(hù)去讀共享文件時(shí)，系統(tǒng)是根據(jù)給定的文件路徑名，逐個(gè)分量地去查找目錄，直至找到該文件的索引結(jié)點(diǎn)。因此在每次訪問(wèn)時(shí)都要多次讀盤(pán)，開(kāi)銷(xiāo)大。每個(gè)LINK文件都要配置索引結(jié)點(diǎn)，耗費(fèi)一定的磁盤(pán)空間。

2023/2/3文件保護(hù)為了防止系統(tǒng)中的文件被非法竊取和破壞。訪問(wèn)類(lèi)型。包括讀、寫(xiě)、執(zhí)行等訪問(wèn)控制存取控制矩陣存取控制表2023/2/3（二）文件系統(tǒng)實(shí)現(xiàn)文件系統(tǒng)層次結(jié)構(gòu)應(yīng)用程序接口邏輯文件系統(tǒng)文件組織模塊基本文件系統(tǒng)I/O控制設(shè)備檢查用戶(hù)提供命令句法的正確性負(fù)責(zé)目錄的管理和維護(hù)，以及文件的安全保護(hù)檢查。負(fù)責(zé)將預(yù)讀寫(xiě)文件的邏輯記錄和讀寫(xiě)位置轉(zhuǎn)換成其在文件中的相對(duì)塊號(hào)，進(jìn)而轉(zhuǎn)換成在文件存儲(chǔ)器中的物理塊號(hào)。將上層傳下來(lái)的命令和物理塊轉(zhuǎn)換成對(duì)適當(dāng)?shù)脑O(shè)備驅(qū)動(dòng)程序調(diào)用由設(shè)備驅(qū)動(dòng)程序和中斷處理程序組成。它負(fù)責(zé)將上層傳來(lái)的命令，轉(zhuǎn)換成硬件設(shè)備的專(zhuān)用I/O指令和相應(yīng)設(shè)備的地址，控制設(shè)備完成與主存之間的信息傳輸，將傳輸是否成功的狀態(tài)碼返回上層模塊。2023/2/3目錄實(shí)現(xiàn)線性表哈希表2023/2/3文件實(shí)現(xiàn)與文件的邏輯結(jié)構(gòu)和存取方法有關(guān)。2023/2/3文件物理結(jié)構(gòu)文件的物理結(jié)構(gòu)是指文件在物理存儲(chǔ)介質(zhì)上的結(jié)構(gòu)。1、順序結(jié)構(gòu)——連續(xù)分配方式2、鏈接結(jié)構(gòu)——鏈接分配方式3、索引結(jié)構(gòu)——索引分配方式2023/2/3（1）連續(xù)分配連續(xù)分配要求為每一個(gè)文件分配一組相鄰接的盤(pán)塊。通常它們都位于一條磁道上。在進(jìn)行讀/寫(xiě)時(shí)，不必移動(dòng)磁頭，僅當(dāng)訪問(wèn)到一條磁道的最后一個(gè)盤(pán)塊后，才需要移到下一條磁道。這樣所形成的文件結(jié)構(gòu)稱(chēng)為順序文件結(jié)構(gòu)，此時(shí)的物理文件稱(chēng)為順序文件。2023/2/3（1）連續(xù)分配這種分配方式保證了邏輯文件中的記錄順序與存儲(chǔ)器中文件占用盤(pán)塊的順序的一致性。為使系統(tǒng)能找到文件存放的地址，應(yīng)在目錄項(xiàng)的文件物理地址字段中，記錄該文件第一個(gè)記錄所在的盤(pán)塊號(hào)和文件長(zhǎng)度（以盤(pán)塊數(shù)進(jìn)行計(jì)量）。2023/2/32023/2/3優(yōu)點(diǎn)簡(jiǎn)單順序訪問(wèn)容易順序訪問(wèn)速度快所需的磁盤(pán)尋道次數(shù)和尋道時(shí)間最少2023/2/3缺點(diǎn)要求有連續(xù)的存儲(chǔ)空間外部碎片問(wèn)題外存緊湊必須事先知道文件的長(zhǎng)度文件不易動(dòng)態(tài)增長(zhǎng)預(yù)留空間:浪費(fèi)重新分配和移動(dòng)2023/2/3（2）鏈接結(jié)構(gòu)這是一種非連續(xù)的結(jié)構(gòu)，將一個(gè)邏輯文件存儲(chǔ)到外存上時(shí)，并不要求為整個(gè)文件分配一塊連續(xù)的空間，而是可以將文件裝到多個(gè)離散的盤(pán)塊中。采用鏈接分配方式時(shí)，可通過(guò)在每個(gè)盤(pán)塊上的鏈接指針，將同屬于一個(gè)文件的多個(gè)離散的盤(pán)塊鏈接成一個(gè)鏈表，把這樣形成的物理文件稱(chēng)為鏈接文件。2023/2/3隱式鏈接在文件目錄的每個(gè)目錄項(xiàng)中，都須含有指向鏈接文件第一個(gè)盤(pán)塊和最后一個(gè)盤(pán)塊的指針。鏈接結(jié)構(gòu)的文件適用于順序存取。因?yàn)橐@得某一塊的塊號(hào)，必須先讀出第一個(gè)盤(pán)塊。。。。順序查找直至第i塊，因此要隨機(jī)地存取信息就較為困難，且可靠性差。2023/2/3文件名始址末址jeep925文件目錄01234567891011121314151617181920212223242526272829303111016-1252023/2/3優(yōu)缺點(diǎn)優(yōu)點(diǎn)：提高了磁盤(pán)空間利用率,不存在外部碎片問(wèn)題有利于文件插入和刪除有利于文件動(dòng)態(tài)擴(kuò)充缺點(diǎn)：存取速度慢，不適于隨機(jī)存取鏈接指針占用一定的空間可靠性問(wèn)題，如指針出錯(cuò)2023/2/3顯式鏈接文件分配表(FAT)將盤(pán)塊中的鏈接指針按盤(pán)塊號(hào)的順序集中起來(lái)，構(gòu)成盤(pán)文件映射表/文件分配表顯式地存放在內(nèi)存中。整個(gè)磁盤(pán)僅設(shè)置一張，利用FAT可進(jìn)行隨機(jī)存取。2023/2/3圖示2023/2/3鏈接分配方式雖然解決了連續(xù)分配方式所存在的問(wèn)題，但又出現(xiàn)了另外兩個(gè)問(wèn)題：不能支持高效的直接存取FAT需占用較大的內(nèi)存空間實(shí)際上打開(kāi)某個(gè)文件時(shí)，只需把該文件占用的盤(pán)塊的編號(hào)調(diào)入內(nèi)存即可。為此應(yīng)將每個(gè)文件所對(duì)應(yīng)的盤(pán)塊號(hào)集中地放在一起。2023/2/3（3）索引分配一個(gè)文件的信息存放在若干不連續(xù)物理塊中，系統(tǒng)為每個(gè)文件建立一個(gè)專(zhuān)用數(shù)據(jù)結(jié)構(gòu)--索引表，并將這些塊的塊號(hào)存放在索引表中。一個(gè)索引表就是磁盤(pán)塊地址數(shù)組,其中第i個(gè)條目指向文件的第i塊——單級(jí)索引分配2023/2/3單級(jí)索引分配2023/2/3012345678910111213141516171819202122232425262728293031文件名索引表地址文件目錄Jeep1991611025-1-1-1192023/2/3優(yōu)點(diǎn)保持了鏈接結(jié)構(gòu)的優(yōu)點(diǎn)，又解決了其缺點(diǎn)：即能順序存取，又能隨機(jī)存取滿(mǎn)足了文件動(dòng)態(tài)增長(zhǎng)、插入刪除的要求能充分利用外存空間不會(huì)產(chǎn)生外部碎片2023/2/3缺點(diǎn)索引表本身要花費(fèi)較多的外存空間。通常采用一個(gè)專(zhuān)門(mén)的盤(pán)塊作為一個(gè)索引塊。對(duì)于小文件采用索引分配方式時(shí)，其索引塊的利用率極低。如果文件非常大，一個(gè)索引塊裝不了，需要多個(gè)索引塊時(shí)，單級(jí)索引分配方式也是低效的

2023/2/3多級(jí)索引分配為這些索引塊再建立一級(jí)索引——兩級(jí)索引分配方式。（三級(jí)、四級(jí)）2023/2/3混合索引分配方式將多種索引分配方式相結(jié)合：直接地址，一級(jí)索引、二級(jí)索引、三級(jí)索引。。。UNIX系統(tǒng)中采用2023/2/3混合索引分配方式共設(shè)有13個(gè)地址項(xiàng)，分成兩類(lèi)，直接地址和間接地址。直接地址：直接存放文件數(shù)據(jù)盤(pán)塊的盤(pán)塊號(hào)假如每個(gè)盤(pán)塊的大小為4KB，當(dāng)文件不大于40KB時(shí)，便可直接從索引結(jié)點(diǎn)中讀出該文件的全部盤(pán)塊號(hào)2023/2/3混合索引分配方式一次間接地址：假如每個(gè)盤(pán)塊的大小為4KB,一次間接地址可存放1K個(gè)盤(pán)塊號(hào)，因而允許文件長(zhǎng)達(dá)4MB2023/2/3混合索引分配方式多次間接地址：當(dāng)文件長(zhǎng)度大于4MB+40KB時(shí)，則采用二次間址分配方式。文件最大長(zhǎng)度可達(dá)4GB。三次間址分配方式，文件最大長(zhǎng)度可達(dá)4TB。2023/2/3（三）磁盤(pán)組織與管理目前，幾乎所有隨機(jī)存取的文件，都是存放在磁盤(pán)上，磁盤(pán)I/O速度的高低將直接影響文件系統(tǒng)的性能。磁盤(pán)結(jié)構(gòu)磁盤(pán)調(diào)度算法磁盤(pán)空間管理2023/2/3信息記錄在磁道上，多個(gè)盤(pán)片，正反兩面都用來(lái)記錄信息，每面一個(gè)磁頭所有盤(pán)面中處于同一磁道號(hào)上的所有磁道組成一個(gè)柱面物理地址形式：柱面號(hào)（磁道號(hào)） 磁頭號(hào)扇區(qū)號(hào)柱面、磁頭、扇區(qū)2023/2/3磁盤(pán)啟動(dòng)時(shí)，磁頭首先處于0磁道，磁盤(pán)從接到命令到向目標(biāo)扇區(qū)讀取或?qū)懭霐?shù)據(jù)完畢共經(jīng)歷三個(gè)階段：尋道：磁頭沿徑向移動(dòng)，移到目標(biāo)扇區(qū)所在磁道的上方（注意，不是目標(biāo)扇區(qū)，而是目標(biāo)扇區(qū)所在的磁道）旋轉(zhuǎn)延遲：找到目標(biāo)磁道后通過(guò)盤(pán)片的旋轉(zhuǎn)，使得要目標(biāo)扇區(qū)轉(zhuǎn)到磁頭的下方數(shù)據(jù)傳輸：數(shù)據(jù)在磁盤(pán)與內(nèi)存之間的實(shí)際傳輸磁盤(pán)的訪問(wèn)過(guò)程2023/2/32磁盤(pán)調(diào)度算法當(dāng)多個(gè)訪盤(pán)請(qǐng)求在等待時(shí)，采用一定的策略，對(duì)這些請(qǐng)求的服務(wù)順序調(diào)整安排，旨在降低平均磁盤(pán)服務(wù)時(shí)間，達(dá)到公平、高效公平：一個(gè)I/O請(qǐng)求在有限時(shí)間內(nèi)滿(mǎn)足高效：減少設(shè)備機(jī)械運(yùn)動(dòng)所帶來(lái)的時(shí)間浪費(fèi)1先來(lái)先服務(wù)FCFS2最短尋道時(shí)間優(yōu)先SSTF3SCAN算法4循環(huán)掃描算法CSCAN2023/2/3根據(jù)進(jìn)程請(qǐng)求訪問(wèn)磁盤(pán)的先后次序進(jìn)行調(diào)度優(yōu)點(diǎn)：簡(jiǎn)單，公平，每個(gè)進(jìn)程的請(qǐng)求都能依次得到處理；缺點(diǎn)：效率不高，相鄰兩次請(qǐng)求可能會(huì)造成最內(nèi)到最外的柱面尋道，使磁頭反復(fù)移動(dòng)，增加了服務(wù)時(shí)間，對(duì)機(jī)械也不利僅適應(yīng)于請(qǐng)求磁盤(pán)I/O的進(jìn)程數(shù)目較少的場(chǎng)合1）先來(lái)先服務(wù)2023/2/3優(yōu)先選擇距當(dāng)前磁頭最近的訪問(wèn)請(qǐng)求進(jìn)行服務(wù)，主要考慮尋道優(yōu)先優(yōu)點(diǎn)：改善了磁盤(pán)平均服務(wù)時(shí)間；缺點(diǎn)：造成某些訪問(wèn)請(qǐng)求長(zhǎng)期等待得不到服務(wù)，“饑餓現(xiàn)象”2）最短尋道時(shí)間優(yōu)先2023/2/3克服了最短尋道優(yōu)先的缺點(diǎn)，既考慮了距離，同時(shí)又考慮了方向具體做法：當(dāng)設(shè)備無(wú)訪問(wèn)請(qǐng)求時(shí)，磁頭不動(dòng)；當(dāng)有訪問(wèn)請(qǐng)求時(shí)，磁頭按一個(gè)方向移動(dòng)，在移動(dòng)過(guò)程中對(duì)遇到的訪問(wèn)請(qǐng)求進(jìn)行服務(wù)，然后判斷該方向上是否還有訪問(wèn)請(qǐng)求，如果有則繼續(xù)掃描；否則改變移動(dòng)方向，并為經(jīng)過(guò)的訪問(wèn)請(qǐng)求服務(wù)，如此反復(fù)3）SCAN算法（電梯算法）2023/2/3（磁頭單向移動(dòng)）電梯算法杜絕了饑餓，但當(dāng)請(qǐng)求對(duì)磁道的分布是均勻時(shí)，磁頭回頭，近磁頭端的請(qǐng)求很少（因?yàn)榇蓬^剛經(jīng)過(guò)），而遠(yuǎn)端請(qǐng)求較多，這些請(qǐng)求等待時(shí)間要長(zhǎng)一些。例如：總是自里向外移動(dòng)，當(dāng)磁頭移動(dòng)到最外的磁道并訪問(wèn)后，立即返回到最里的欲訪問(wèn)的磁道，返回時(shí)不為任何的等待訪問(wèn)者服務(wù)。返回后可再次從里向外進(jìn)行掃描。稱(chēng)為循環(huán)掃描算法4）循環(huán)掃描調(diào)度算法2023/2/3調(diào)度算法的選擇實(shí)際系統(tǒng)相當(dāng)普遍采用最短尋道時(shí)間優(yōu)先算法，因?yàn)樗?jiǎn)單有效，性?xún)r(jià)比好。掃描算法更適于磁盤(pán)負(fù)擔(dān)重的系統(tǒng)。磁盤(pán)負(fù)擔(dān)很輕的系統(tǒng)也可以采用先來(lái)先服務(wù)算法一般要將磁盤(pán)調(diào)度算法作為操作系統(tǒng)的單獨(dú)模塊編寫(xiě)，利于修改和更換。2023/2/33.磁盤(pán)管理

文件管理要解決的重要問(wèn)題之一就是如何為新創(chuàng)建的文件分配存儲(chǔ)空間。其解決方法與內(nèi)存的分配情況有許多相似之處，可采取連續(xù)分配和離散分配方式。不論哪種分配方式，存儲(chǔ)空間的基本分配單位都是磁盤(pán)塊而非字節(jié)。為了實(shí)現(xiàn)存儲(chǔ)空間的分配，系統(tǒng)首先應(yīng)記住存儲(chǔ)空間的使用情況。還要提供對(duì)存儲(chǔ)空間進(jìn)行分配和回收的手段。2023/2/33.磁盤(pán)管理

記住存儲(chǔ)空間的使用情況就是對(duì)空閑塊的管理，有以下方法：空閑表法空閑鏈表法位示圖法2023/2/31）空閑表法屬于連續(xù)分配方式，與內(nèi)存管理中的動(dòng)態(tài)分區(qū)分配方式相同。為每個(gè)文件分配一塊連續(xù)的存儲(chǔ)空間。系統(tǒng)為外存上的所有空閑區(qū)建立一張空閑表，每個(gè)空閑區(qū)對(duì)應(yīng)于一個(gè)空閑表項(xiàng)所有空閑區(qū)按其起始盤(pán)塊號(hào)遞增的次序排列序號(hào)起始空閑盤(pán)塊號(hào)盤(pán)塊數(shù)1242933155。。。。。。2023/2/31）空閑表法存儲(chǔ)空間的分配與回收空閑盤(pán)塊的分配與內(nèi)存的動(dòng)態(tài)分配類(lèi)似，同樣可以用首次、最佳、最壞適應(yīng)法。盤(pán)塊的回收也同內(nèi)存的回收方式類(lèi)似。在內(nèi)存中很少用連續(xù)分配的方式，在外存中因它具有較高的分配速度，可減少訪問(wèn)磁盤(pán)的I/O頻率，故在有些時(shí)候也可以使用對(duì)換空間，一般都采用連續(xù)分配的方式。當(dāng)文件較小時(shí)，采用連續(xù)分配方式2023/2/32）空閑鏈表法空閑鏈表法是將所有空閑盤(pán)區(qū)拉成一條空閑鏈。根據(jù)構(gòu)成的鏈所用基本元素不同，可把鏈表分成兩種形式，空閑盤(pán)塊鏈和空閑盤(pán)區(qū)鏈空閑盤(pán)塊鏈：以盤(pán)塊為單位?？臻e盤(pán)區(qū)鏈：以盤(pán)區(qū)（多個(gè)盤(pán)塊）為單位2023/2/3空閑鏈表法空閑鏈表法的分配與回收?？臻e盤(pán)區(qū)鏈：分配：與內(nèi)存動(dòng)態(tài)分配類(lèi)似?；厥眨侯?lèi)似于內(nèi)存回收。2023/2/3空閑鏈表法空閑鏈表法的分配與回收。空閑盤(pán)塊鏈：分配：當(dāng)用戶(hù)因創(chuàng)建文件而請(qǐng)求分配存儲(chǔ)空間時(shí)，系統(tǒng)從鏈?zhǔn)组_(kāi)始依次摘下適當(dāng)數(shù)目的空閑盤(pán)塊分配給用戶(hù)，然后調(diào)整鏈?zhǔn)字羔?。回收：將回收的盤(pán)塊依次插入空閑盤(pán)塊鏈的末尾。特點(diǎn)：用于分配和回收一個(gè)盤(pán)塊的過(guò)程非常簡(jiǎn)單，但在為一個(gè)文件分配盤(pán)塊時(shí)，可能要重復(fù)操作多次。2023/2/33）位示圖法系統(tǒng)為磁盤(pán)建立一張位示圖，在位示圖中每個(gè)盤(pán)塊占1位，按盤(pán)塊的順序排列。“1”表示對(duì)應(yīng)的盤(pán)塊已占用，"0"表示空閑。。2023/2/3第5章設(shè)備管理（一）

I/O管理概述

1.

I/O控制方式

2.軟件層次結(jié)構(gòu)

2023/2/3I/O設(shè)備I/O系統(tǒng)設(shè)備分類(lèi)2023/2/3設(shè)備控制器設(shè)備控制器主要負(fù)責(zé)控制一個(gè)或多個(gè)I/O設(shè)備，以實(shí)現(xiàn)I/O設(shè)備和計(jì)算機(jī)之間的數(shù)據(jù)交換。它是CPU與I/O設(shè)備之間的接口，接收從CPU發(fā)來(lái)的命令，并控制I/O設(shè)備工作，以使CPU從繁雜的設(shè)備控制事務(wù)中解脫出來(lái)。設(shè)備控制器可分為兩類(lèi)，一類(lèi)用于控制字符設(shè)備的控制器，另一類(lèi)是用于控制塊設(shè)備的控制器。2023/2/3 為使中央處理機(jī)從繁忙的I/O處理中擺脫出來(lái)，現(xiàn)代大、中型計(jì)算機(jī)系統(tǒng)中設(shè)置了專(zhuān)門(mén)的處理I/O操作的處理機(jī)，并把這種處理機(jī)稱(chēng)為通道。通道在CPU的控制下獨(dú)立地執(zhí)行通道程序，對(duì)外部設(shè)備的I/O操作進(jìn)行控制，以實(shí)現(xiàn)內(nèi)存與外設(shè)之間成批的數(shù)據(jù)交換。 通道=I/O處理機(jī)

通道概念2023/2/3I/O通道I/O通道的分類(lèi)字節(jié)多路通道數(shù)據(jù)選擇通道數(shù)組多路通道2023/2/31.I/O控制方式1程序I/O方式2I/O中斷方式3DMA方式4通道方式中斷DMA通道2023/2/3程序I/O方式I/O控制器是OS同硬件之間的接口。它有兩個(gè)寄存器：數(shù)據(jù)緩沖寄存器、控制/狀態(tài)寄存器。狀態(tài)控制寄存器有一個(gè)標(biāo)志忙/閑的標(biāo)志位busy。CPU外部設(shè)備控制邏輯電路控制寄存器I/O控制器數(shù)據(jù)寄存器2023/2/3工作過(guò)程以輸入為例1、把busy置12、反復(fù)測(cè)試busy，為1表示輸入機(jī)尚未輸完一個(gè)字，處理機(jī)應(yīng)繼續(xù)對(duì)該標(biāo)志進(jìn)行測(cè)試，轉(zhuǎn)2，為0表示輸入機(jī)已將輸入數(shù)據(jù)送入控制器的數(shù)據(jù)寄存器中，轉(zhuǎn)33、把數(shù)據(jù)從數(shù)據(jù)緩沖區(qū)中讀走，并置busy為1。所謂“程序循環(huán)測(cè)試”的數(shù)據(jù)傳輸方式，就是指用戶(hù)進(jìn)程使用啟動(dòng)設(shè)備后，不斷地執(zhí)行測(cè)試指令，去測(cè)試所啟動(dòng)設(shè)備的狀態(tài)寄存器。只有在狀態(tài)寄存器出現(xiàn)了所需要的狀態(tài)后，才停止測(cè)試工作，完成輸入/輸出。忙等待方式2023/2/3

在程序I/O方式中，由于CPU的高速性和I/O設(shè)備的低速性，致使CPU的絕大部分時(shí)間都處于等待I/O設(shè)備完成數(shù)據(jù)I/O的循環(huán)測(cè)試中，造成對(duì)CPU的極大浪費(fèi)。在該方式中，CPU之所以要不斷地測(cè)試I/O設(shè)備的狀態(tài)，就是因?yàn)樵贑PU中無(wú)中斷機(jī)構(gòu)，使I/O設(shè)備無(wú)法向CPU報(bào)告它已完成了一個(gè)字符的輸入操作。2023/2/3I/O中斷方式I/O控制器能發(fā)中斷。工作過(guò)程：1、發(fā)出啟動(dòng)某設(shè)備的命令，本進(jìn)程（A）變?yōu)榈却隣顟B(tài)，轉(zhuǎn)進(jìn)程調(diào)度，調(diào)度另一進(jìn)程B。2、輸入完成時(shí)，控制器發(fā)出中斷，中斷B，通過(guò)中斷進(jìn)入中斷處理程序。3、在中斷處理程序中把數(shù)據(jù)緩沖寄存器中的數(shù)取走，放入內(nèi)存特定位置M，喚醒等待進(jìn)程A，中斷返回到B的斷點(diǎn)繼續(xù)執(zhí)行。4、在以后的某個(gè)時(shí)刻O(píng)S調(diào)度要求輸入的進(jìn)程A。A從M取數(shù)處理。

2023/2/3

在I/O設(shè)備輸入每個(gè)數(shù)據(jù)的過(guò)程中，由于無(wú)須CPU干預(yù)，因而可使CPU與I/O設(shè)備并行工作。僅當(dāng)輸完一個(gè)數(shù)據(jù)時(shí)，才需CPU花費(fèi)極短的時(shí)間去做些中斷處理?？梢?jiàn)，這樣可使CPU和I/O設(shè)備都處于忙碌狀態(tài)，從而提高了整個(gè)系統(tǒng)的資源利用率及吞吐量。例如，從終端輸入一個(gè)字符的時(shí)間約為100ms，而將字符送入終端緩沖區(qū)的時(shí)間小于0.1ms。若采用程序I/O方式，CPU約有99.9ms的時(shí)間處于忙—等待中。采用中斷驅(qū)動(dòng)方式后，CPU可利用這99.9ms的時(shí)間去做其它事情，而僅用0.1ms的時(shí)間來(lái)處理由控制器發(fā)來(lái)的中斷請(qǐng)求?？梢?jiàn)，中斷驅(qū)動(dòng)方式可以成百倍地提高CPU的利用率。

2023/2/3分析同前相比，CPU利用率大大提高。缺點(diǎn)：每臺(tái)設(shè)備每輸入輸出一個(gè)字節(jié)的數(shù)據(jù)都有一次中斷。如果設(shè)備較多時(shí)，中斷次數(shù)會(huì)很多，使CPU的計(jì)算時(shí)間大大減少。為減少中斷對(duì)CPU造成的負(fù)擔(dān)，可采用DMA方式和通道方式。2023/2/3DMA方式直接存儲(chǔ)器存取控制方式的概念是指對(duì)I/O設(shè)備的控制由DMA控制器完成，在DMA控制器的作用下，設(shè)備和主存之間可以成批地進(jìn)行數(shù)據(jù)交換，而不用CPU的干涉。2023/2/35.2.3DMA方式直接存儲(chǔ)器存取控制方式的概念該方式的特點(diǎn)是：①數(shù)據(jù)傳輸?shù)幕締挝皇菙?shù)據(jù)塊，即在CPU與I/O設(shè)備之間，每次傳送至少一個(gè)數(shù)據(jù)塊；②所傳送的數(shù)據(jù)是從設(shè)備直接送入內(nèi)存的，或者相反；③僅在傳送一個(gè)或多個(gè)數(shù)據(jù)塊的開(kāi)始和結(jié)束時(shí)，才需CPU干預(yù)，整塊數(shù)據(jù)的傳送是在控制器的控制下完成的。可見(jiàn)，DMA方式較之中斷驅(qū)動(dòng)方式，又是成百倍地減少了CPU對(duì)I/O的干預(yù)，進(jìn)一步提高了CPU與I/O設(shè)備的并行操作程度。

2023/2/3DMA方式 控制器功能更強(qiáng)，除有中斷功能外，還有一個(gè)DMA控制機(jī)構(gòu)。在DMA控制器的控制下，設(shè)備同主存之間可成批交換數(shù)據(jù)，不用CPU干預(yù)。DMA控制器組成：主機(jī)與DMA控制器的接口；DMA控制器與塊設(shè)備的接口；I/O控制邏輯2023/2/3直接存儲(chǔ)器存取控制直接存儲(chǔ)器存取控制方式的特點(diǎn)I/O數(shù)據(jù)傳輸速度快，CPU負(fù)擔(dān)少。在DMA方式下，數(shù)據(jù)的傳送方向、存放數(shù)據(jù)的內(nèi)存始址及傳送數(shù)據(jù)的長(zhǎng)度等都由CPU控制。每臺(tái)設(shè)備需要配一個(gè)DMA控制器。2023/2/3I/O通道控制方式

I/O通道控制方式的引入

雖然DMA方式比起中斷方式來(lái)，已經(jīng)顯著地減少了CPU的干預(yù)，即已由以字(節(jié))為單位的干預(yù)減少到以數(shù)據(jù)塊為單位的干預(yù)，但CPU每發(fā)出一條I/O指令，也只能去讀一個(gè)連續(xù)的數(shù)據(jù)塊，要是一次去讀多個(gè)數(shù)據(jù)塊且將它們分別傳送到不同的內(nèi)存區(qū)域，則須由CPU發(fā)出多條I/O指令，進(jìn)行多次中斷。

2023/2/3I/O通道控制方式

I/O通道控制方式的引入

I/O通道方式是DMA方式的發(fā)展，它可進(jìn)一步減少CPU的干預(yù)，即把對(duì)一個(gè)數(shù)據(jù)塊的讀(或?qū)?為單位的干預(yù)，減少為對(duì)一組數(shù)據(jù)塊的讀(或?qū)?及有關(guān)的控制和管理為單位的干預(yù)。同時(shí)，又可實(shí)現(xiàn)CPU、通道和I/O設(shè)備三者的并行操作，從而更有效地提高整個(gè)系統(tǒng)的資源利用率。例如，當(dāng)CPU要完成一組相關(guān)的讀(或?qū)?操作及有關(guān)控制時(shí)，只需向I/O通道發(fā)送一條I/O指令，以給出其所要執(zhí)行的通道程序的首址和要訪問(wèn)的I/O設(shè)備，通道接到該指令后，通過(guò)執(zhí)行通道程序便可完成CPU指定的I/O任務(wù)。

2023/2/3通道的工作過(guò)程某進(jìn)程在運(yùn)行過(guò)程中，若提出了I/O請(qǐng)求，只需向通道I/O通道發(fā)一條I/O指令，以給出其所要執(zhí)行的通道程序的始址和要訪問(wèn)的I/O設(shè)備；用戶(hù)進(jìn)程阻塞以等待I/O完成通道則通過(guò)執(zhí)行通道程序控制設(shè)備控制器，控制設(shè)備完成指定的I/O任務(wù)。發(fā)出中斷信號(hào)通知CPU通道程序已執(zhí)行完成。CPU響應(yīng)中斷，進(jìn)行善后處理并喚醒被阻塞的用戶(hù)進(jìn)程2023/2/32.I/O系統(tǒng)層次及功能

用戶(hù)層軟件設(shè)備獨(dú)立性軟件設(shè)備驅(qū)動(dòng)程序中斷處理程序硬件實(shí)現(xiàn)與用戶(hù)交互的接口，產(chǎn)生I/O請(qǐng)求負(fù)責(zé)實(shí)現(xiàn)與設(shè)備驅(qū)動(dòng)器的統(tǒng)一接口、設(shè)備命名，設(shè)備的保護(hù)，設(shè)備的分配與釋放，緩沖等。與硬件直接相關(guān)，負(fù)責(zé)具體實(shí)現(xiàn)系統(tǒng)對(duì)設(shè)備發(fā)出的操作指令，驅(qū)動(dòng)I/O設(shè)備工作的驅(qū)動(dòng)程序保護(hù)環(huán)境，轉(zhuǎn)入相應(yīng)處理程序，恢