張惠娟副教授Ms.zhj@163.com實用操作系統概念1內容框架

概述體系結構進程管理內存管理

文件管理外設管理2內容

Chp13:MassstorageStructure

Chp11:Filesystem3Module11:File-System

FileConceptDirectoryStructureFree-SpaceManagementFileImplementationEfficiencyandPerformanceProtectionRecovery4引言計算機應用程序都要：存儲信息和檢索信息

能夠存儲大量的信息長期保存信息可以共享信息FileConcept6解決方法文件信息以一種單元，即文件的形式存儲在磁盤或其他外部介質上。文件是通過操作系統來管理的，包括：文件的結構、命名、存取、使用、保護、實現方法。FileConcept7文件系統

負責信息組織、存儲和訪問，提供高效、快速和方便的信息存儲和訪問功能。FileConcept8用戶觀點文件系統如何呈現在其面前，如：一個文件由什么組成、如何命名，如何保護文件、可進行何種操作等。操作系統觀點文件目錄怎樣實現、怎樣管理存儲空間、文件存儲位置、磁盤實際運作方式(與設備管理的接口)等等FileConcept9文件定義是一組帶標識的、在邏輯上有完整意義的信息項的序列。

其中：

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

名字空間映射

存儲空間實現文件信息的共享，并提供文件保護和保密措施FileConcept13向用戶提供方便使用的接口

如提供對文件系統操作命令、提供對文件的操作命令：信息存取、加工等系統維護及向用戶提供有關信息文件系統的執行效率提供與I/O的統一接口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分類目的對不同文件進行管理,提高系統效率；提高用戶界面友好性按信息保存期限分類

臨時文件；永久文件；檔案文件按文件保護方式分類

只讀文件；讀寫文件；可執行文件FileConcept19按文件性質和用途分類系統文件用戶文件庫文件

FileConcept20按文件的邏輯結構分類

流式文件；記錄式文件按文件的物理結構分類

順序（連續）文件；鏈接文件；索引文件FileConcept21FileConcept22

FileStructure

邏輯結構物理結構FileConcept23邏輯結構是從用戶角度研究文件的組織形式無結構文件有結構文件FileConcept24一條記錄一個字節字節序列記錄序列樹FileConcept25無結構文件：流式文件

構成文件的基本單位是字符，文件是有邏輯意義的、無結構的一串字符的集合。文件

一個無結構字節序列好處

提供很大的靈活性FileConcept26有結構文件：記錄文件

文件是由若干個記錄組成，每個記錄有一個鍵，可按鍵進行查找。文件一個固定長度記錄的序列，每條記錄有其內部結構FileConcept27物理結構

從系統角度來看文件，從文件在物理介質上的存放方式來研究文件.連續（順序）結構鏈接結構索引結構

FileConcept28連續結構（順序）文件信息存放在若干連續的物理塊中FileConcept29012345678910111213141516171819202122232425262728293031文件名始址塊數count02tr143mail196list284f62文件目錄countftrmaillistFileConcept30優點簡單支持順序存取和隨機存取順序存取速度快所需的磁盤尋道次數和尋道時間最少FileConcept31缺點

文件不能動態增長預留空間:浪費重新分配和移動不利于文件插入和刪除外部碎片問題存儲壓縮技術FileConcept32鏈接結構文件信息存放在若干不連續的物理塊中，各塊之間通過指針連接，前一個物理塊指向下一個物理塊。

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

一個盤塊一個索引表,多個索引表鏈接起來多級索引

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

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

UNIX采用了三級索引結構后，文件最大可達16兆個物理塊FileConcept4243AccessMethods

順序存取方式隨機(直接)存取方式FileConcept44存儲介質物理結構存取方式磁帶連續結構順序存取磁盤連續鏈接索引順序順序順序隨機

隨機FileConcept45基本概念目錄結構文件訪問方法目錄結構改進DirectoryStructure46基本概念文件控制塊（FCB）文件控制塊是操作系統為管理文件而設置的數據結構，存放了為管理文件所需的所有有關信息（文件屬性）文件控制塊是文件存在的標志DirectoryStructure47文件控制塊內容

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

Asingledirectoryforallusers.DirectoryStructure52優點

簡單、易實現缺點

NamingproblemGroupingproblem

DirectoryStructure53二級目錄結構

Separatedirectoryforeachuser.

DirectoryStructure54優點PathnameCanhavethesaemfilenamefordifferentuserEfficientsearchingNogroupingcapability

缺點

增加系統開銷DirectoryStructure55樹型目錄結構DirectoryStructure56優點層次結構清晰，便于管理和保護有利于文件分類解決重名問題提高文件檢索速度能進行存取權限的控制缺點

查找一個文件按路徑名逐層檢查，由于每個文件都放在外存，多次訪盤影響速度DirectoryStructure57其它方法哈希表算法目錄項信息存在一哈希表中搜索時根據文件名計算哈希值得到一個指向表中文件的指針其他算法

如B+樹DirectoryStructure58文件訪問方法目錄檢索

用戶給出文件名，按名尋找目錄項根據路徑名檢索：全路徑名：從根開始相對路徑：從當前目錄開始DirectoryStructure59文件尋址

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

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

如：UNIX：I節點（索引節點）DirectoryStructure6263

例：一個FCB有48個字節，符號目錄項占8字節，文件名6字節，文件號2字節，基本目錄項占48-6=42字節。假設，物理塊大小512字節DirectoryStructure64

解：分解前：占512/48=10個FCB

分解后：占512/8=64個符號目錄項或512/42=12個基本目錄項假設：目錄文件有128個目錄項分解前：占13塊分解后：符號文件占2塊基本文件占11塊DirectoryStructure65

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

減少了訪問硬盤的次數，提高了檢索速度DirectoryStructure66數據結構管理方法Free-SpaceManagement67數據結構空閑塊表

所有空閑塊記錄在一個表中空閑塊鏈表

把所有空閑塊鏈成一個鏈

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

Free-SpaceManagement69位示圖

用一串二進制位反映磁盤空間中的分配使用

情況,每個物理塊對應一位,分配物理塊為1，否則為0。申請物理塊時，在位示圖中查找為0的位，返回對應物理塊號；歸還時，將對應位轉置0描述能力強，適合各種物理結構Free-SpaceManagement70

計算公式

已知字號i，位號j

塊號＝i×字長＋j

已知塊號字號＝[塊號/字長]位號＝塊號mod字長

Free-SpaceManagement71已知塊號，則磁盤地址：

柱面號＝[塊號/（磁頭數×扇區數）]

磁頭號＝[（塊號mod（磁頭數×扇區數））/扇區數]

扇區號＝（塊號mod（磁頭數×扇區數））mod扇區數已知磁盤地址：塊號＝柱面號×（磁頭數×扇區數）＋磁頭號×扇區數＋扇區號Free-SpaceManagement72成組鏈接法Free-SpaceManagement7374S.free100300299。。。201空閑盤塊棧0199100400399…301100500499…401…75ProtectionFileowner/creatorshouldbeabletocontrol:whatcanbedonebywhomTypesofaccessReadWriteExecuteAppendDeleteList76FileImplementation數據結構文件執行77

數據結構系統文件表用戶文件表兩種表間的關系FileImplementation78

系統文件表系統打開文件表（整個系統一張）放在內存，用于保存已打開文件的FCB文件號、共享計數、修改標志FileImplementation79用戶文件表

每個進程一個，進程的PCB中，記錄了用戶打開文件表的位置。FileImplementation80FileImplementation兩種表間的關系用戶打開文件表指向系統打開文件表多個進程共享同一個文件，則多個用戶打開文件表目對應系統打開文件表的同一入口8182文件執行文件操作執行過程文件共享FileImplementation83文件操作提供設置和修改對用戶文件存取權限的服務提供建立、修改、改變、刪除目錄的服務提供文件共享、設置訪問路徑的服務提供創建、打開、讀、寫、關閉、撤消文件等服務文件系統維護文件系統的轉儲和恢復FileImplementation84

文件執行Create()Open()Read()……FileImplementation85Create()實質是建立文件的FCB，并建立必要的存儲空間，分配空FCB，根據提供的參數及需要填寫有關內容，返回一個文件描述.FileImplementation86執行過程：檢查參數的合法性檢查同一目錄下有無重名文件在目錄中有無空閑位置填寫目錄項內容返回FileImplementation87Open()文件使用前都要先打開，即把FCB送到內存。

fd=open（文件路徑名，打開方式）FileImplementation88執行過程：根據文件路徑名查目錄，找到FCB主部；根據打開方式、共享說明和用戶身份檢查訪問合法性；根據文件號查系統打開文件表，看文件是否已被打開；是→共享計數加1，否則→將外存中的FCB主部等信息填入系統打開文件表空表項，共享計數置為1；FileImplementation89在用戶打開文件表中取一空表項，填寫打開方式等，并指向系統打開文件表對應表項。返回信息

fd：文件描述符，是一個非負整數，用于以后讀寫文件。FileImplementation90Read()檢查長度是否為正整數根據文件名查找目錄，確定該文件在目錄中的位置。根據隱含參數中的進程主和目錄中該文件的存儲權限數據，檢查是否有權讀？由文件內位置與要讀的長度計算最末位置，將其與目錄中的文件長度比較，超過否？FileImplementation91根據參數中的位置、長度和目錄中的映射信息，確定塊號、塊數、塊內位移與長度。（多次讀盤）根據下一塊號讀塊至內存緩沖區根據塊內位移長度取出要讀的內容，送至參數中的內存目的地址根據塊內長度或起始塊號+塊數，確定還讀下一塊嗎？同時確定下一塊塊號FileImplementation92文件共享定義

一個文件被多個用戶或程序使用目的

節省時間和存儲空間，減少了用戶工作量進程間通過文件交換信息FileImplementation93實現方法由系統目錄實現對文件的共享對要共享的文件進行連接通過“連接（Link）”命令，在用戶自己的目錄項中對要共享的文件建立起相應的表目，即建立兩個文件的等價關系FileImplementation9495EfficiencyandPerformanceEfficiencydependenton:diskallocationanddirectorya