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

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

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

1.

內(nèi)存管理概念

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

2.

交換與覆蓋

3.

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

4.

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

分頁管理方式；分段管理方式；段頁式管理方式。

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

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

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

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

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

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

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

動態(tài)分區(qū)存儲管理的基本思想是：在作業(yè)要求裝入內(nèi)存儲器時，如果當(dāng)時內(nèi)存儲器中有足夠的存儲空間滿足該作業(yè)的需求，那么就劃分出一個與作業(yè)相對地址空間同樣大小的分區(qū)分配給它。2023/2/3采用的數(shù)據(jù)結(jié)構(gòu)為了實現(xiàn)分區(qū)分配，系統(tǒng)中必須配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，用來記錄內(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ū)表（隊列）。

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

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

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

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

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

把用戶程序按邏輯頁劃分成大小相等的部分，稱為頁（page）

。從0開始編制頁號，頁內(nèi)地址是相對于0編址2023/2/3內(nèi)存空間

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

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

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

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

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

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

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

b+頁號p

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

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

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

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

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

Cl

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

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

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

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

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

2.

請求分頁管理方式

3.

頁面置換算法

最佳置換算法（OPT）；先進先出置換算法（FIFO）；最近最少使用置換算法（LRU）；時鐘置換算法（CLOCK）。

4.

頁面分配策略

5.

抖動

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

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

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

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

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

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

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

1.簡單的Clock置換算法圖4-30簡單Clock置換算法的流程和示例2023/2/32023/2/32.改進型Clock置換算法由訪問位A和修改位M可以組合成下面四種類型的頁面：

1類(A=0,M=0):

表示該頁最近既未被訪問，又未被修改，是最佳淘汰頁。

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

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

4類(A=1,M=1):

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

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

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

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

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

1.

文件概念

2.

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

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

3.

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

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

4.

文件共享

5.

文件保護

訪問類型；訪問控制。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

記住存儲空間的使用情況就是對空閑塊的管理，有以下方法：空閑表法空閑鏈表法位示圖法2023/2/31）空閑表法屬于連續(xù)分配方式，與內(nèi)存管理中的動態(tài)分區(qū)分配方式相同。為每個文件分配一塊連續(xù)的存儲空間。系統(tǒng)為外存上的所有空閑區(qū)建立一張空閑表，每個空閑區(qū)對應(yīng)于一個空閑表項所有空閑區(qū)按其起始盤塊號遞增的次序排列序號起始空閑盤塊號盤塊數(shù)1242933155。。。。。。2023/2/31）空閑表法存儲空間的分配與回收空閑盤塊的分配與內(nèi)存的動態(tài)分配類似，同樣可以用首次、最佳、最壞適應(yīng)法。盤塊的回收也同內(nèi)存的回收方式類似。在內(nèi)存中很少用連續(xù)分配的方式，在外存中因它具有較高的分配速度，可減少訪問磁盤的I/O頻率，故在有些時候也可以使用對換空間，一般都采用連續(xù)分配的方式。當(dāng)文件較小時，采用連續(xù)分配方式2023/2/32）空閑鏈表法空閑鏈表法是將所有空閑盤區(qū)拉成一條空閑鏈。根據(jù)構(gòu)成的鏈所用基本元素不同，可把鏈表分成兩種形式，空閑盤塊鏈和空閑盤區(qū)鏈空閑盤塊鏈：以盤塊為單位?？臻e盤區(qū)鏈：以盤區(qū)（多個盤塊）為單位2023/2/3空閑鏈表法空閑鏈表法的分配與回收?？臻e盤區(qū)鏈：分配：與內(nèi)存動態(tài)分配類似?；厥眨侯愃朴趦?nèi)存回收。2023/2/3空閑鏈表法空閑鏈表法的分配與回收?？臻e盤塊鏈：分配：當(dāng)用戶因創(chuàng)建文件而請求分配存儲空間時，系統(tǒng)從鏈?zhǔn)组_始依次摘下適當(dāng)數(shù)目的空閑盤塊分配給用戶，然后調(diào)整鏈?zhǔn)字羔??；厥眨簩⒒厥盏谋P塊依次插入空閑盤塊鏈的末尾。特點：用于分配和回收一個盤塊的過程非常簡單，但在為一個文件分配盤塊時，可能要重復(fù)操作多次。2023/2/33）位示圖法系統(tǒng)為磁盤建立一張位示圖，在位示圖中每個盤塊占1位，按盤塊的順序排列?！?”表示對應(yīng)的盤塊已占用，"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è)備分類2023/2/3設(shè)備控制器設(shè)備控制器主要負責(zé)控制一個或多個I/O設(shè)備，以實現(xiàn)I/O設(shè)備和計算機之間的數(shù)據(jù)交換。它是CPU與I/O設(shè)備之間的接口，接收從CPU發(fā)來的命令，并控制I/O設(shè)備工作，以使CPU從繁雜的設(shè)備控制事務(wù)中解脫出來。設(shè)備控制器可分為兩類，一類用于控制字符設(shè)備的控制器，另一類是用于控制塊設(shè)備的控制器。2023/2/3 為使中央處理機從繁忙的I/O處理中擺脫出來，現(xiàn)代大、中型計算機系統(tǒng)中設(shè)置了專門的處理I/O操作的處理機，并把這種處理機稱為通道。通道在CPU的控制下獨立地執(zhí)行通道程序，對外部設(shè)備的I/O操作進行控制，以實現(xiàn)內(nèi)存與外設(shè)之間成批的數(shù)據(jù)交換。 通道=I/O處理機

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

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

2023/2/3

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

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

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

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

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

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

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

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

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

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