張惠娟副教授Mszhj@163com知識(shí)講解

張惠娟副教授Ms.zhj@163.com實(shí)用操作系統(tǒng)概念1內(nèi)容框架

概述體系結(jié)構(gòu)進(jìn)程管理內(nèi)存管理

文件管理外設(shè)管理2內(nèi)容

Chp13:MassstorageStructure

Chp11:Filesystem3Module11:File-System

FileConceptDirectoryStructureFree-SpaceManagementFileImplementationEfficiencyandPerformanceProtectionRecovery4引言計(jì)算機(jī)應(yīng)用程序都要：存儲(chǔ)信息和檢索信息

能夠存儲(chǔ)大量的信息長(zhǎng)期保存信息可以共享信息FileConcept6解決方法文件信息以一種單元，即文件的形式存儲(chǔ)在磁盤(pán)或其他外部介質(zhì)上。文件是通過(guò)操作系統(tǒng)來(lái)管理的，包括：文件的結(jié)構(gòu)、命名、存取、使用、保護(hù)、實(shí)現(xiàn)方法。FileConcept7文件系統(tǒng)

負(fù)責(zé)信息組織、存儲(chǔ)和訪問(wèn)，提供高效、快速和方便的信息存儲(chǔ)和訪問(wèn)功能。FileConcept8用戶觀點(diǎn)文件系統(tǒng)如何呈現(xiàn)在其面前，如：一個(gè)文件由什么組成、如何命名，如何保護(hù)文件、可進(jìn)行何種操作等。操作系統(tǒng)觀點(diǎn)文件目錄怎樣實(shí)現(xiàn)、怎樣管理存儲(chǔ)空間、文件存儲(chǔ)位置、磁盤(pán)實(shí)際運(yùn)作方式(與設(shè)備管理的接口)等等FileConcept9文件定義是一組帶標(biāo)識(shí)的、在邏輯上有完整意義的信息項(xiàng)的序列。

其中：

標(biāo)識(shí)是文件名信息項(xiàng)是構(gòu)成文件內(nèi)容的基本單位長(zhǎng)度是單個(gè)字節(jié)或多個(gè)字節(jié)文件內(nèi)容由文件建立者和使用者解釋FileConcept10文件的各信息項(xiàng)之間具有順序關(guān)系FileConcept編號(hào)：01……i……n-1信息項(xiàng)信息項(xiàng)信息項(xiàng)……...信息項(xiàng)……...讀寫(xiě)指針11文件系統(tǒng)是操作系統(tǒng)中統(tǒng)一管理信息資源的一種軟件。管理文件的存儲(chǔ)、檢索、更新，提供安全可靠的共享和保護(hù)手段，并且方便用戶使用。FileConcept12文件系統(tǒng)的功能統(tǒng)一管理文件的存儲(chǔ)空間，實(shí)施存儲(chǔ)空間的分配與回收。實(shí)現(xiàn)文件的按名存取

名字空間映射

存儲(chǔ)空間實(shí)現(xiàn)文件信息的共享，并提供文件保護(hù)和保密措施FileConcept13向用戶提供方便使用的接口

如提供對(duì)文件系統(tǒng)操作命令、提供對(duì)文件的操作命令：信息存取、加工等系統(tǒng)維護(hù)及向用戶提供有關(guān)信息文件系統(tǒng)的執(zhí)行效率提供與I/O的統(tǒng)一接口FileConcept14FileAttributes

Informationaboutfilesarekeptinthedirectorystructure,whichismaintainedonthedisk.Name–onlyinformationkeptinhuman-readableform.Type–neededforsystemsthatsupportdifferenttypes.Location–pointertofilelocationondevice.FileConcept15Size–currentfilesize.Protection–controlswhocandoreading,writing,executing.Time,date,anduseridentification–dataforprotection,security,andusagemonitoring.FileConcept16FileOperationscreatewritereadrepositionwithinfile–fileseekdeletetruncateFileConcept17open(Fi)–searchthedirectorystructureondiskforentryFi,andmovethecontentofentrytomemory.close(Fi)–movethecontentofentryFiinmemorytodirectorystructureondisk.FileConcept18Filetype分類目的對(duì)不同文件進(jìn)行管理,提高系統(tǒng)效率；提高用戶界面友好性按信息保存期限分類

臨時(shí)文件；永久文件；檔案文件按文件保護(hù)方式分類

只讀文件；讀寫(xiě)文件；可執(zhí)行文件FileConcept19按文件性質(zhì)和用途分類系統(tǒng)文件用戶文件庫(kù)文件

FileConcept20按文件的邏輯結(jié)構(gòu)分類

流式文件；記錄式文件按文件的物理結(jié)構(gòu)分類

順序（連續(xù)）文件；鏈接文件；索引文件FileConcept21FileConcept22

FileStructure

邏輯結(jié)構(gòu)物理結(jié)構(gòu)FileConcept23邏輯結(jié)構(gòu)是從用戶角度研究文件的組織形式無(wú)結(jié)構(gòu)文件有結(jié)構(gòu)文件FileConcept24一條記錄一個(gè)字節(jié)字節(jié)序列記錄序列樹(shù)FileConcept25無(wú)結(jié)構(gòu)文件：流式文件

構(gòu)成文件的基本單位是字符，文件是有邏輯意義的、無(wú)結(jié)構(gòu)的一串字符的集合。文件

一個(gè)無(wú)結(jié)構(gòu)字節(jié)序列好處

提供很大的靈活性FileConcept26有結(jié)構(gòu)文件：記錄文件

文件是由若干個(gè)記錄組成，每個(gè)記錄有一個(gè)鍵，可按鍵進(jìn)行查找。文件一個(gè)固定長(zhǎng)度記錄的序列，每條記錄有其內(nèi)部結(jié)構(gòu)FileConcept27物理結(jié)構(gòu)

從系統(tǒng)角度來(lái)看文件，從文件在物理介質(zhì)上的存放方式來(lái)研究文件.連續(xù)（順序）結(jié)構(gòu)鏈接結(jié)構(gòu)索引結(jié)構(gòu)

FileConcept28連續(xù)結(jié)構(gòu)（順序）文件信息存放在若干連續(xù)的物理塊中FileConcept29012345678910111213141516171819202122232425262728293031文件名始址塊數(shù)count02tr143mail196list284f62文件目錄countftrmaillistFileConcept30優(yōu)點(diǎn)簡(jiǎn)單支持順序存取和隨機(jī)存取順序存取速度快所需的磁盤(pán)尋道次數(shù)和尋道時(shí)間最少FileConcept31缺點(diǎn)

文件不能動(dòng)態(tài)增長(zhǎng)預(yù)留空間:浪費(fèi)重新分配和移動(dòng)不利于文件插入和刪除外部碎片問(wèn)題存儲(chǔ)壓縮技術(shù)FileConcept32鏈接結(jié)構(gòu)文件信息存放在若干不連續(xù)的物理塊中，各塊之間通過(guò)指針連接，前一個(gè)物理塊指向下一個(gè)物理塊。

FileConcept33文件目錄文件名始址末址jeep92501234567891011121314151617181920212223242526272829303111016-125FileConcept34優(yōu)點(diǎn)提高了磁盤(pán)空間利用率,不存在外部碎片問(wèn)題有利于文件插入和刪除有利于文件動(dòng)態(tài)擴(kuò)充FileConcept35缺點(diǎn)存取速度慢，不適于隨機(jī)存取可靠性問(wèn)題，如指針出錯(cuò)更多的尋道次數(shù)和尋道時(shí)間鏈接指針占用一定的空間FileConcept36索引結(jié)構(gòu)文件信息存放在若干不連續(xù)物理塊中，系統(tǒng)為每個(gè)文件建立一個(gè)專用數(shù)據(jù)結(jié)構(gòu)--索引表，并將這些塊的塊號(hào)存放在一個(gè)索引表中一個(gè)索引表就是磁盤(pán)塊地址數(shù)組,其中第i個(gè)條目指向文件的第i塊FileConcept37012345678910111213141516171819202122232425262728293031文件名索引表地址文件目錄Jeep1991611025-1-1-11938優(yōu)點(diǎn)保持了鏈接結(jié)構(gòu)的優(yōu)點(diǎn),又解決了其缺點(diǎn)：即能順序存取,又能隨機(jī)存取滿足了文件動(dòng)態(tài)增長(zhǎng)、插入刪除要求能充分利用外存空間FileConcept39缺點(diǎn)較多的尋道次數(shù)和尋道時(shí)間索引表本身帶來(lái)了系統(tǒng)開(kāi)銷如：內(nèi)外存空間，存取時(shí)間FileConcept40索引表組織鏈接模式

一個(gè)盤(pán)塊一個(gè)索引表,多個(gè)索引表鏈接起來(lái)多級(jí)索引

將一個(gè)大文件的所有索引表（二級(jí)索引)的地址放在另一個(gè)索引表（一級(jí)索引)中綜合模式

UNIX文件系統(tǒng)采用多級(jí)索引結(jié)構(gòu)(綜合模式)。FileConcept41綜合模式每個(gè)文件索引表為13個(gè)索引項(xiàng)，每項(xiàng)2個(gè)字節(jié)。最前面10項(xiàng)直接登記存放文件信息的物理塊號(hào)（直接尋址）如果文件大于10塊，則利用第11項(xiàng)指向一個(gè)物理塊，該塊中最多可放256個(gè)文件物理塊的塊號(hào)（一次間接尋址）。對(duì)于更大的文件還可利用第12和第13項(xiàng)作為二次和三次間接尋址

UNIX采用了三級(jí)索引結(jié)構(gòu)后，文件最大可達(dá)16兆個(gè)物理塊FileConcept4243AccessMethods

順序存取方式隨機(jī)(直接)存取方式FileConcept44存儲(chǔ)介質(zhì)物理結(jié)構(gòu)存取方式磁帶連續(xù)結(jié)構(gòu)順序存取磁盤(pán)連續(xù)鏈接索引順序順序順序隨機(jī)

隨機(jī)FileConcept45基本概念目錄結(jié)構(gòu)文件訪問(wèn)方法目錄結(jié)構(gòu)改進(jìn)DirectoryStructure46基本概念文件控制塊（FCB）文件控制塊是操作系統(tǒng)為管理文件而設(shè)置的數(shù)據(jù)結(jié)構(gòu)，存放了為管理文件所需的所有有關(guān)信息（文件屬性）文件控制塊是文件存在的標(biāo)志DirectoryStructure47文件控制塊內(nèi)容

NameTypeAddressCurrentlengthMaximumlengthDatelastaccessed(forarchival)Datelastupdated(fordump)OwnerID(whopays)Protectioninformation(discusslater)DirectoryStructure48文件目錄把所有FCB組織在一起，就構(gòu)成了文件目錄，即文件控制塊的有序集合目錄項(xiàng)構(gòu)成文件目錄的項(xiàng)目（目錄項(xiàng)就是FCB）目錄文件為實(shí)現(xiàn)對(duì)文件目錄的管理，通常將文件目錄以文件形式保存在外存，這個(gè)文件就叫目錄文件。DirectoryStructure49目錄結(jié)構(gòu)目的一級(jí)目錄二級(jí)目錄樹(shù)型目錄（多級(jí)目錄）其它方法DirectoryStructure50目的Efficiency–locatingafilequickly.Naming–convenienttousers.Twouserscanhavesamenamefordifferentfiles.Thesamefilecanhaveseveraldifferentnames.Grouping–logicalgroupingoffilesbyproperties,(e.g.,allPascalprograms,allgames,…)DirectoryStructure51一級(jí)目錄結(jié)構(gòu)

Asingledirectoryforallusers.DirectoryStructure52優(yōu)點(diǎn)

簡(jiǎn)單、易實(shí)現(xiàn)缺點(diǎn)

NamingproblemGroupingproblem

DirectoryStructure53二級(jí)目錄結(jié)構(gòu)

Separatedirectoryforeachuser.

DirectoryStructure54優(yōu)點(diǎn)PathnameCanhavethesaemfilenamefordifferentuserEfficientsearchingNogroupingcapability

缺點(diǎn)

增加系統(tǒng)開(kāi)銷DirectoryStructure55樹(shù)型目錄結(jié)構(gòu)DirectoryStructure56優(yōu)點(diǎn)層次結(jié)構(gòu)清晰，便于管理和保護(hù)有利于文件分類解決重名問(wèn)題提高文件檢索速度能進(jìn)行存取權(quán)限的控制缺點(diǎn)

查找一個(gè)文件按路徑名逐層檢查，由于每個(gè)文件都放在外存，多次訪盤(pán)影響速度DirectoryStructure57其它方法哈希表算法目錄項(xiàng)信息存在一哈希表中搜索時(shí)根據(jù)文件名計(jì)算哈希值得到一個(gè)指向表中文件的指針其他算法

如B+樹(shù)DirectoryStructure58文件訪問(wèn)方法目錄檢索

用戶給出文件名，按名尋找目錄項(xiàng)根據(jù)路徑名檢索：全路徑名：從根開(kāi)始相對(duì)路徑：從當(dāng)前目錄開(kāi)始DirectoryStructure59文件尋址

根據(jù)FCB中文件物理地址等信息，求出文件的任意記錄或字符在存取介質(zhì)上的地址，稱為文件尋址。DirectoryStructure60

目錄改進(jìn)改進(jìn)目的加快目錄檢索DirectoryStructure61改進(jìn)方法采用目錄項(xiàng)分解法，把FCB分成兩部分。符號(hào)目錄頂（次部）文件名，文件號(hào)基本目錄項(xiàng)（主部）除文件名外的所有項(xiàng)目

如：UNIX：I節(jié)點(diǎn)（索引節(jié)點(diǎn)）DirectoryStructure6263

例：一個(gè)FCB有48個(gè)字節(jié)，符號(hào)目錄項(xiàng)占8字節(jié)，文件名6字節(jié)，文件號(hào)2字節(jié)，基本目錄項(xiàng)占48-6=42字節(jié)。假設(shè)，物理塊大小512字節(jié)DirectoryStructure64

解：分解前：占512/48=10個(gè)FCB

分解后：占512/8=64個(gè)符號(hào)目錄項(xiàng)或512/42=12個(gè)基本目錄項(xiàng)假設(shè)：目錄文件有128個(gè)目錄項(xiàng)分解前：占13塊分解后：符號(hào)文件占2塊基本文件占11塊DirectoryStructure65

查找一個(gè)文件的平均訪盤(pán)次數(shù)分解前：(1+13)/2=7次分解后：(1+2)/2+1=2.5次

減少了訪問(wèn)硬盤(pán)的次數(shù)，提高了檢索速度DirectoryStructure66數(shù)據(jù)結(jié)構(gòu)管理方法Free-SpaceManagement67數(shù)據(jù)結(jié)構(gòu)空閑塊表

所有空閑塊記錄在一個(gè)表中空閑塊鏈表

把所有空閑塊鏈成一個(gè)鏈

Free-SpaceManagement68管理方法位圖法成組鏈接法

Free-SpaceManagement69位示圖

用一串二進(jìn)制位反映磁盤(pán)空間中的分配使用

情況,每個(gè)物理塊對(duì)應(yīng)一位,分配物理塊為1，否則為0。申請(qǐng)物理塊時(shí)，在位示圖中查找為0的位，返回對(duì)應(yīng)物理塊號(hào)；歸還時(shí)，將對(duì)應(yīng)位轉(zhuǎn)置0描述能力強(qiáng)，適合各種物理結(jié)構(gòu)Free-SpaceManagement70

計(jì)算公式

已知字號(hào)i，位號(hào)j

塊號(hào)＝i×字長(zhǎng)＋j

已知塊號(hào)字號(hào)＝[塊號(hào)/字長(zhǎng)]位號(hào)＝塊號(hào)mod字長(zhǎng)

Free-SpaceManagement71已知塊號(hào)，則磁盤(pán)地址：

柱面號(hào)＝[塊號(hào)/（磁頭數(shù)×扇區(qū)數(shù)）]

磁頭號(hào)＝[（塊號(hào)mod（磁頭數(shù)×扇區(qū)數(shù)））/扇區(qū)數(shù)]

扇區(qū)號(hào)＝（塊號(hào)mod（磁頭數(shù)×扇區(qū)數(shù)））mod扇區(qū)數(shù)已知磁盤(pán)地址：塊號(hào)＝柱面號(hào)×（磁頭數(shù)×扇區(qū)數(shù)）＋磁頭號(hào)×扇區(qū)數(shù)＋扇區(qū)號(hào)Free-SpaceManagement72成組鏈接法Free-SpaceManagement7374S.free100300299。。。201空閑盤(pán)塊棧0199100400399…301100500499…401…75ProtectionFileowner/creatorshouldbeabletocontrol:whatcanbedonebywhomTypesofaccessReadWriteExecuteAppendDeleteList76FileImplementation數(shù)據(jù)結(jié)構(gòu)文件執(zhí)行77

數(shù)據(jù)結(jié)構(gòu)系統(tǒng)文件表用戶文件表兩種表間的關(guān)系FileImplementation78

系統(tǒng)文件表系統(tǒng)打開(kāi)文件表（整個(gè)系統(tǒng)一張）放在內(nèi)存，用于保存已打開(kāi)文件的FCB文件號(hào)、共享計(jì)數(shù)、修改標(biāo)志FileImplementation79用戶文件表

每個(gè)進(jìn)程一個(gè)，進(jìn)程的PCB中，記錄了用戶打開(kāi)文件表的位置。FileImplementation80FileImplementation兩種表間的關(guān)系用戶打開(kāi)文件表指向系統(tǒng)打開(kāi)文件表多個(gè)進(jìn)程共享同一個(gè)文件，則多個(gè)用戶打開(kāi)文件表目對(duì)應(yīng)系統(tǒng)打開(kāi)文件表的同一入口8182文件執(zhí)行文件操作執(zhí)行過(guò)程文件共享FileImplementation83文件操作提供設(shè)置和修改對(duì)用戶文件存取權(quán)限的服務(wù)提供建立、修改、改變、刪除目錄的服務(wù)提供文件共享、設(shè)置訪問(wèn)路徑的服務(wù)提供創(chuàng)建、打開(kāi)、讀、寫(xiě)、關(guān)閉、撤消文件等服務(wù)文件系統(tǒng)維護(hù)文件系統(tǒng)的轉(zhuǎn)儲(chǔ)和恢復(fù)FileImplementation84

文件執(zhí)行Create()Open()Read()……FileImplementation85Create()實(shí)質(zhì)是建立文件的FCB，并建立必要的存儲(chǔ)空間，分配空FCB，根據(jù)提供的參數(shù)及需要填寫(xiě)有關(guān)內(nèi)容，返回一個(gè)文件描述.FileImplementation86執(zhí)行過(guò)程：檢查參數(shù)的合法性檢查同一目錄下有無(wú)重名文件在目錄中有無(wú)空閑位置填寫(xiě)目錄項(xiàng)內(nèi)容返回FileImplementation87Open()文件使用前都要先打開(kāi)，即把FCB送到內(nèi)存。

fd=open（文件路徑名，打開(kāi)方式）FileImplementation88執(zhí)行過(guò)程：根據(jù)文件路徑名查目錄，找到FCB主部；根據(jù)打開(kāi)方式、共享說(shuō)明和用戶身份檢查訪問(wèn)合法性；根據(jù)文件號(hào)查系統(tǒng)打開(kāi)文件表，看文件是否已被打開(kāi)；是→共享計(jì)數(shù)加1，否則→將外存中的FCB主部等信息填入系統(tǒng)打開(kāi)文件表空表項(xiàng)，共享計(jì)數(shù)置為1；FileImplementation89在用戶打開(kāi)文件表中取一空表項(xiàng)，填寫(xiě)打開(kāi)方式等，并指向系統(tǒng)打開(kāi)文件表對(duì)應(yīng)表項(xiàng)。返回信息

fd：文件描述符，是一個(gè)非負(fù)整數(shù)，用于以后讀寫(xiě)文件。FileImplementation90Read()檢查長(zhǎng)度是否為正整數(shù)根據(jù)文件名查找目錄，確定該文件在目錄中的位置。根據(jù)隱含參數(shù)中的進(jìn)程主和目錄中該文件的存儲(chǔ)權(quán)限數(shù)據(jù)，檢查是否有權(quán)讀？由文件內(nèi)位置與要讀的長(zhǎng)度計(jì)算最末位置，將其與目錄中的文件長(zhǎng)度比較，超過(guò)否？FileImplementation91根據(jù)參數(shù)中的位置、長(zhǎng)度和目錄中的映射信息，確定塊號(hào)、塊數(shù)、塊內(nèi)位移與長(zhǎng)度。（多次讀盤(pán)）根據(jù)下一塊號(hào)讀塊至內(nèi)存緩沖區(qū)根據(jù)塊內(nèi)位移長(zhǎng)度取出要讀的內(nèi)容，送至參數(shù)中的內(nèi)存目的地址根據(jù)塊內(nèi)長(zhǎng)度或起始?jí)K號(hào)+塊數(shù)，確定還讀下一塊嗎？同時(shí)確定下一塊塊號(hào)FileImplementation92文件共享定義

一個(gè)文件被多個(gè)用戶或程序使用目的

節(jié)省時(shí)間和存儲(chǔ)空間，減少了用戶工作量進(jìn)程間通過(guò)文件交換信息FileImplementation93實(shí)現(xiàn)方法由系統(tǒng)目錄實(shí)現(xiàn)對(duì)文件的共享對(duì)要共享的文件進(jìn)行連接通過(guò)“連接（Link）”命令，在用戶自己的目錄項(xiàng)中對(duì)要共享的文件建立起相應(yīng)的表目，即建立兩個(gè)文件的等價(jià)關(guān)系FileImplementation9495EfficiencyandPerformanceEfficiencydependenton:diskallocationanddirectorya