操作系統(tǒng)第8章

1第八章、文件系統(tǒng)8.1、文件系統(tǒng)的概念8.2、文件的邏輯結構和存取方式8.3、文件的物理結構和存儲設備8.4、文件的存儲空間8.5、文件目錄管理8.6、文件存取控制8.7、文件的使用8.8、文件系統(tǒng)的層次結構聯(lián)系2數(shù)據(jù)處理38.1、文件系統(tǒng)的概念一、文件

是數(shù)據(jù)的組織形式，是具有文件名字的相關信息的集合。 文件屬性：文件名、文件類型、長度、建立日期、存取權限

按邏輯結構分類：

無結構文件：字符流集合，基本信息單位是字符；（白紙） （流式文件）

結構文件：基本信息單位是記錄，記錄是有若干字節(jié)組成的具有 特定意義的信息單位。（表格）4文件的分類系統(tǒng)文件庫文件用戶文件普通文件目錄文件特殊文件輸入文件輸出文件輸入/輸出文件只讀文件讀寫文件不保護文件性質(zhì)用途組織形式信息流向保護級別5二、文件系統(tǒng)操作系統(tǒng)中與管理文件有關的軟件和數(shù)據(jù)，以及被管理的文件的總體。1、管理對象：文件、目錄、外存存儲空間2、作用：系統(tǒng)角度：對文件存儲空間組織和分配，對文件存儲、保護、檢索、存?。挥脩艚嵌龋喊疵嫒?，對用戶透明。3、功能：

1）文件存儲空間管理

2）目錄管理

3）文件讀寫管理

4）文件安全管理

5）為用戶提供接口64、特點：

1）友好的用戶接口；

2）按名存取，對用戶透明，存取靈活；

3）文件共享；

4）合理分配文件存儲空間，提高外存利用率；

5）文件安全。5、優(yōu)點：

1）使用方便；

2）安全性好；

3）統(tǒng)一性。7文件的結構和組織用戶觀點:

是研究用戶“思維”中的抽象文件（邏輯文件），重點在于為用戶提供一種邏輯結構清晰、使用簡便的邏輯文件形式。用戶將按照這種形式去存儲、檢索和加工有關文件中的信息。實現(xiàn)觀點:

是研究保存在設備“介質(zhì)”中的實際文件（物理文件）。重點是選擇一些工作性能良好、設備利用率高的物理文件形式。系統(tǒng)將按照這種形式同外設打交道并控制信息的傳輸。88.2、文件的邏輯結構和存取方式一、邏輯結構

文件的邏輯結構：用戶可見的文件的組織形式； 文件的物理結構：文件在外存上的存儲組織形式；

無結構文件（流式文件）基本信息單位是字符；按字符輸入先后順序排列；利用讀寫指針訪問；管理簡單，查找困難；適用于對基本信息單位操作不多的文件；

結構文件基本信息單位是記錄；記錄是有若干字節(jié)組成的具有特定意義的信息單位；對記錄按不同順序組織主要用于信息管理；9記錄的組成記錄名（號）鍵名—鍵：特殊的屬性或多個屬性的組合，用于記錄的區(qū)分屬性—屬性值

記錄名R 1296 姓名：張三 學號：9246003

性別：男 生日：1986年3月 成績：86 …10記錄的組織結構1、連續(xù)結構2、多重結構3、轉(zhuǎn)置結構4、順序結構111、連續(xù)結構

把記錄按生成或輸入的先后順序連續(xù)排列。

特點：

1）排列與內(nèi)容無關，利于追加記錄；

2）搜索性能差；

3）適用于所有類型文件。122、多重結構 n個記錄包含m個鍵（m<=n），把包含同一個鍵的記錄名排成隊列； 查找時：先查鍵，在查對應鍵后的記錄隊列；133、轉(zhuǎn)置結構

在多重結構的基礎上：在一個鍵下，把包含此鍵的記錄指針以目錄的方式排列起來。144、順序結構

把鍵按某種規(guī)定的順序排列成順序結構文件； 適用于按同樣順序進行的搜索。15二、存取方法

按什么樣的方式訪問記錄，與用戶提供的記錄的訪問條件有關。

1、順序存取法

2、隨機存取法（直接存取法）

3、按鍵存取法161、順序存取法：

按文件的邏輯地址順序存取。 設置一個讀指針ptr，指向當前記錄，要訪問下一條記錄時，ptr=ptr+l（記錄長度）。

1）可讀可寫文件：

2）可變長記錄：172、隨機存取法（直接存取法）

按記錄的編號來存取記錄，或利用編號形成記錄的偏移地址來定位。

1）定長記錄：

2）不定長記錄：183、按鍵存取法

對按鍵的特定順序存放記錄的文件（多重、轉(zhuǎn)置、順序結構），通過對鍵的查找定位。19三、搜索算法

如何從文件中把符合指定條件的記錄找出來，與文件的邏輯結構有關。1、線性搜索法

從第一個記錄開始，依次把每個記錄的鍵值或記錄號與給定的鍵值或記錄號比較，直至找到匹配記錄或查到文件尾。 搜索速度慢，平均查找次數(shù)為0.5n次。202、散列法

定義一個散列函數(shù)H(K)，通過此函數(shù)計算出含指定鍵的記錄的邏輯地址； 可能出現(xiàn)沖突：H(Ki)=H(Kj)，但Ki<>Kj

解決沖突：開放定址法

Hi=(H(key)+di)MODm(i=1..n)

di–增量序列

1）di=a*i：線性探測再散列

2）di=r1...rn：隨機探測再散列

3）di=c*(i*i)：平方探測再散列213、二分搜索法（折半查找）

將鍵按大小順序排序（K0<K1<…<Kn），記錄長d，鍵間距d，查找鍵為K的記錄：

初始：L=0，H=n，把K與K0、Kn比較，相等則找到； 不 等

K？K[(L+H)/2]：

=：找到

<：繼續(xù)搜索左半部分，H=（L+H）/2

>：繼續(xù)搜索右半部分，L=（L+H）/2

最多查找[log2n]+1次，比線性搜索法效率高，但要預先排序。228.3、文件的物理結構和存儲設備一、文件的物理結構

文件在外存上的組織形式，包括文件在外存上的安置、編目、鏈接方法。

存儲基本單元—物理塊（512/1024字節(jié)）

1、以塊為單位對文件進行物理存儲空間的分配；

2、塊是外存與內(nèi)存間信息傳遞的單位；

3、一塊對應一個或多個記錄，一個記錄對應多個塊；（虛文件）邏輯文件 物理文件（實文件） 邏輯地址 物理地址存儲映射23文件的物理結構的類型1、連續(xù)文件2、串聯(lián)文件3、索引文件241、連續(xù)文件把邏輯上連續(xù)的文件依次分配到連續(xù)的物理塊中；存?。哼壿媺K號i 物理塊號Bi 物理塊首單元地址B0+iBi*塊長25優(yōu)點：

1）管理簡單；

2）順序存取速度快；缺點：

1）不能動態(tài)增長；

2）增加、刪除記錄困難；

3）要求分配連續(xù)空間。適于：隨機存取文件和順序存取文件。不適于：存放經(jīng)常修改的用戶文件和數(shù)據(jù)庫文件。262、串聯(lián)文件

將文件邏輯塊裝入非連續(xù)物理塊號，每個物理塊內(nèi)用一個單元存放下一個邏輯塊所在物理塊的地址。27優(yōu)點：

1）可動態(tài)增長，增加刪除記錄容易；

2）解決碎片問題，外存利用率高；缺點：

搜索效率低，存取速度慢。適于：邏輯連續(xù)且存取方法為順序存取的文件。不適于：隨機存取的文件。

283、索引文件

為每個文件建立一張索引表，記錄文件邏輯塊號和其存放的物理塊號的對應關系。

索引表的組織：

1）按邏輯塊號遞增順序排列；

2）無任何次序；

3）按鍵的順序排列（鍵值—物理塊號）

目錄的存放： 按塊存放，最好不要分塊存放； 當文件塊數(shù)>一塊能存放的目錄項：多級索引結構

29邏輯塊號邏輯塊號物理塊號020115222325+單級索引索引表30多級索引組號組索引表始址00組索引表始址11組索引表始址……NN組索引表始址邏輯塊號物理塊號…………邏輯塊號物理塊號…………邏輯塊號物理塊號……………文件A主索引表始址…目錄主索引表…一級索引表31優(yōu)點： 連續(xù)文件的“存取迅速”結合優(yōu)點 串聯(lián)文件的“非連續(xù)存放”缺點：

1）索引表占據(jù)存儲空間大；

2）存取速度減慢，訪問兩次（以上）存儲器。 改進：把索引表事先調(diào)入內(nèi)存。適用于：順序、直接、按鍵存取32邏輯記錄的大小<>物理塊的大小1、記錄小于物理塊：

記錄擴充到塊大小，擴充部分浪費；2、一塊含m個記錄： 計算一個記錄所在的邏輯塊號和塊內(nèi)偏址 由邏輯塊號找到對應的物理塊號 首單元地址=物理塊號*塊長+塊內(nèi)偏址3、一個記錄含多個塊：

找連續(xù)的m塊存放；33二、文件的存儲設備

磁帶磁表面存儲器順序存取設備磁盤硬盤信息記錄格式、存儲器接口相似直接存儲設備軟盤光盤光感應存儲器341、順序存取設備—磁帶順序訪問每一塊，某塊的定位要建立在相鄰塊的移動上。特點： 容量大、價格便宜、尋址時間長、信息傳輸率低。適用于： 連續(xù)分配的文件結構，且存取方式為順序存取。352、直接存取設備—磁盤、光盤

通過磁頭沿半徑方向的移動和磁盤的轉(zhuǎn)動相結合，把磁頭直接定位到指定的物理塊起始地址，不必順序查找。

特點： 尋址時間短、存取速度快、容量大

適用于：

各種類型的文件。3637邏輯結構—記錄如何組織成文件

（連續(xù)/多重/轉(zhuǎn)置/順序）存取方法—查找記錄的大戰(zhàn)略

（順序/隨機/按鍵）搜索方法—查找記錄的小戰(zhàn)術

（線性/散列/二分）物理結構—

記錄存儲在存儲器上的方式 （連續(xù)/串聯(lián)/索引）38文件的物理結構與存取方法的關系存儲設備直接存取設備順序存取設備文件類型連續(xù)文件非連續(xù)文件連續(xù)文件串聯(lián)文件索引文件存取方法直接/順序順序直接/順序/按鍵順序文件長度固定可變/固定可變/固定固定398.4、文件的存儲空間實質(zhì)：空閑塊的組織、分配和回收。一、空閑文件目錄

二、空閑塊鏈三、位示圖40

一、空閑文件目錄

管理：（類似內(nèi)存分區(qū)管理） 分配：找空閑塊數(shù)>請求塊數(shù)的空閑區(qū) 回收：新—增表項；相鄰—合并修改適用于： 少量大空閑區(qū)，建立連續(xù)文件。序號空閑塊個數(shù)第一個空閑塊號空閑塊號41二、空閑塊鏈

把空閑區(qū)通過指針連接起來，每區(qū)末塊存下一區(qū)的起始塊號和塊數(shù)； 一個空閑區(qū)內(nèi)的塊也連接起來，每塊首單元存下一塊的塊號，從鏈頭分配，回收至鏈尾。 空閑區(qū)排列順序：

1、按大小順序排列

2、按釋放空閑區(qū)的先后次序排列

3、成組鏈法42成組鏈法1、把空閑塊按50塊分為一組，初始從后往前劃分；2、每組末塊用于存放前一組的總塊數(shù)和各塊塊號；3、第一組前無組，末塊不用，塊數(shù)為49塊；4、最后一組的塊數(shù)不一定是50塊，其塊數(shù)、塊號存放于文件資源表中。43441、分配：

1）設置一個棧頂指針Ptr，初值=文件資源表中當前組總塊數(shù)；

2）Ptr=Ptr–1，從棧頂?shù)靡豢臻e塊號，把此塊分配出去；

3）繼續(xù)分配就不斷重復2）步，直到Ptr=0，準備分配下一組；

4）把Ptr=0時的棧頂塊（下一組的信息）的內(nèi)容讀入文件資源表，成為新的當前組，把棧頂塊分配出去；

5）重復1~4步的操作，分配新當前組的空閑塊。先分當前組前49塊末塊信息讀入資源表分配末塊452、回收：1）把回收塊號寫入棧頂單元里，Ptr=Ptr+1，塊數(shù)加1；2）當Ptr=50時，把文件資源表中這50塊的塊號和塊數(shù)50寫到新回收塊的前51個單元中去；3）Ptr=0，把存放信息的新回收塊的塊號入棧，成為新的當前組的末塊，開始新的一組的積累。注意： 經(jīng)過一段時間的分配和回收，每組的塊號不一定連續(xù)。463、優(yōu)點：1）空閑塊號的記錄不占據(jù)額外空間，只臨時借用每組末塊存放，該組分完后把末塊信息讀入文件資源表，模塊也可以參與分配；2）絕大部分分配和回收在文件資源表中進行，只需在兩組交接時啟動設備通道，讀/寫一個物理塊，避免內(nèi)外存的頻繁讀寫，效率高；3）利用棧頂指針的移動來分配和回收空閑塊，直觀、效率高。47三、位示圖

內(nèi)存中劃出若干字，其中每一位代表一個外存的物理塊，1—已分配，0—未分配，作為分配的依據(jù)。

關鍵： 字位數(shù) 物理塊號

優(yōu)點：記錄緊湊，存于內(nèi)存，分配回收速度快。488.5、文件目錄管理一、文件目錄

一種數(shù)據(jù)結構，標識系統(tǒng)中文件的信息，供檢索時使用。1、目錄管理的功能

1）實現(xiàn)按名存取

2）對目錄快速搜索

3）解決文件命名沖突

4）實現(xiàn)文件共享492、文件的組成

文件體

文件控制塊FCB

基本信息文件名存取控制信息文件主存取權限使用信息建立日期時間內(nèi)部標識符核準用戶存取權限上次修改日期時間物理位置一般用戶存取權限訪問時間邏輯結構50二、文件目錄結構目錄文件：若干文件的文件控制塊的有序集合文件目錄結構：文件與目錄文件、目錄文件之間的關系。1、單級目錄

系統(tǒng)一張目錄表，每個文件的FCB占一表項，一一對應。 優(yōu)點： 管理簡單，實現(xiàn)按名存取。 缺點：

1）查找速度慢

2）不允許重名

3）不便于文件共享 適用于： 單用戶環(huán)境512、二級目錄（P194）第一級（一個）：系統(tǒng)主目錄MFD

匯總每個用戶的目錄文件的信息第二級（多個）：用戶文件目錄UFD

匯總某個用戶的若干文件的信息優(yōu)點：

1）提高檢索速度

2）允許重名

3）實現(xiàn)共享缺點： 用戶內(nèi)部檢索速度慢，不能重名。523、多級目錄樹型目錄結構： 最高層：根目錄，存放第二層的目錄文件和普通文件的信息。 中間層：各級子目錄，存放其下層的目錄文件和普通文件的信息。

最低層：各級目錄下的普通文件。文件表示：絕對路徑名（從根目錄開始經(jīng)歷的各級目錄）+文件名當前目錄：相對路徑名優(yōu)點：

1）層次清楚，便于分門別類地管理；

2）檢索速度快；

3）解決命名沖突；

4）實現(xiàn)共享。缺點：

目錄文件多，占用空間。5354三、便于共享的文件目錄文件共享：不同用戶用不同的文件名共享同一個文件的一個副本。1、繞道法

訪問文件不在當前目錄，從當前目錄開始向上找到與訪問文件路徑的交叉點，在從此點向下找到該文件。2、鏈接法

在具有共享關系的目錄之間進行鏈接，一個目錄中的表目直接指向另一個目錄的表目3、基本文件目錄表法553、基本文件目錄表法基本文件目錄表BFD：

存放所有文件得說明信息，每個文件對應一個表項，擁有唯一內(nèi)部標識符。 基本文件目錄 0

空閑文件目錄 1

系統(tǒng)符號文件目錄 2符號文件目錄表SFD： 每個目錄文件一張，包含該目錄下所有文件的名稱和內(nèi)部標識符。BFD前三個表目56內(nèi)部標識符物理塊號012345678910空閑文件目錄Wang3Zhang4a.c5b.c6s.c9k.c10f.c6z.c7Sub_d8z.cb.cs.ca.ck.cMFDWang-SFDZhang-SFDSub_d-SFD57訪問文件的過程：交替查找BFD和SFD中表目的過程。查BFD：根據(jù)ID，得下一級SFD或文件的起始地址；查SFD：根據(jù)路徑名，得下一級SFD或文件的內(nèi)部標識符目錄存放在： 內(nèi)存：訪問速度塊、占用空間大； 當前使用文件的目錄表目讀入內(nèi)存：便于共享：

用戶想共享一個文件，在其SFD中增設一個表目，填上自取的文件名和被共享文件的內(nèi)部標識符即可。588.6、文件存取控制三層含義：

文件共享+文件保護+文件保密保護：避免文件由于文件主或其它用戶誤操作而被無意破壞。保密：防止文件被未經(jīng)允許的用戶訪問。用戶身份：

文件主、合法用戶、非法用戶實質(zhì)：

規(guī)定用戶對文件的使用權限（讀/寫/執(zhí)行）59原則：1、有訪問權限的允許進行相應的操作，并避免誤操作；2、無訪問權限的禁止進行操作，防止冒充用戶訪問；控制步驟：

1、審查用戶存取權限；

2、比較用戶權限與本次存取要求是否一致；

3、把存取要求和被訪問文件的保密性比較，是否沖突？601、存取控制矩陣 二維矩陣： 行——文件 列——用戶 元素——訪問級別（RWE）

（Filei,Userj)

表示用戶Userj對文件Filei的存取權限 特點：

控制簡單； 表格龐大，占用空間； 訪問速度慢。

612、存取控制表

每個文件一張，把用戶劃分為若干組，規(guī)定每組的存取權限。 存放在BFD中，文件被打開時，所屬說明信息讀入內(nèi)存。特點： 記錄簡潔高效，使用靈活； 占用內(nèi)存少。623、口令方式（及用戶帳號）

文件創(chuàng)建時設置一個口令，存于BFD中，用戶使用時提供口令，需一致。特點： 設置簡單，占內(nèi)存少，驗證快； 保密性差； 不能進行具體讀寫控制； 改變口令不方便。63

4、密碼方式用戶文件

設置指定代碼鍵，編碼程序

密碼文件

提供指定代碼鍵，解碼程序用戶文件特點： 保密性強：代碼鍵不存于系統(tǒng)； 犧牲系統(tǒng)開銷加密解密。648.7、文件的使用系統(tǒng)調(diào)用的功能：

1、設置、修改用戶對文件的存取權限；

2、建立、改變、刪除目錄；

3、文件共享、設置訪問路徑；

4、創(chuàng)建、打開、讀寫、關閉、撤消文件。65常用的文件系統(tǒng)調(diào)用1、建立文件

Creat（文件名，屬性，設備號）2、打開文件

Open（文件名）3、讀文件

Read（文件名，N，M）4、寫文件

Write（文件名，N，M）5、關閉文件

Close（文件名）6、撤消文件

Delete（文件名）661、建立文件Creat（文件名，屬性，設備號）登記 查MFD，若無SFD，建立其SFD； 在BFD中找一空表目，分配ID，填文件屬性； 在SFD中填入文件名和其ID；分配存儲空間，在BFD中填入物理地址調(diào)用打開文件命令將有關表目登入活動文件表，準備寫672、打開文件Open（文件名）已經(jīng)打開（共享文件）：當前用戶數(shù)加1未被打開： 把BFD中文件的表目復制到內(nèi)存活動文件目錄AFT中 當前用戶數(shù)=1

對順序存取的文件，置讀/寫指針683、讀文件 Read（文件名，N，M）在活動文件表AFT中找出該文件的表目；檢查訪問的合法性（存取控制）；將邏輯記錄號轉(zhuǎn)換為物理地址；啟動設備管理程序，以完成數(shù)據(jù)交換工作。694、寫文件 （Write文件名，N，M）步驟基本與讀文件相同，傳輸方向相反；不同：對新寫入的信息分配存儲空間705、關閉文件Close（文件名）當前用戶數(shù)減1，若當前用戶數(shù)=0： 撤消內(nèi)存的活動文件表中的對應表目；如果活動期間屬性作過修改，寫回BFD的對應表目中去。716、撤消文