操作系統：第6章文件管理(概念與邏輯物理存儲)

1、2022-2-251現代操作系統現代操作系統第第2020講：第講：第6 6章章 文件管理文件管理( ( 文件與文件系統文件與文件系統 ) )主講主講: :朱貴良朱貴良20152022-2-252內容提綱內容提綱一一 文件與文件系統文件與文件系統二二 文件的邏輯結構文件的邏輯結構三三 文件的物理結構與存儲設備文件的物理結構與存儲設備四四 件的存儲空間管理件的存儲空間管理本節(jié)小結本節(jié)小結2022-2-253一一 文件與文件系統文件與文件系統2022-2-255一 文件與文件系統文件與文件系統 【一一】數據單位的再認識數據單位的再認識( (位，字節(jié)，字，記錄，文件位，字節(jié)，字，記錄，文件) )，1.

2、1.基本數據項：基本數據項：描述一對象具體屬性的字符集，是最小的數據單位，描述一對象具體屬性的字符集，是最小的數據單位，即原子數據，又稱為數據元素或字段。每個基本數據項具有一個即原子數據，又稱為數據元素或字段。每個基本數據項具有一個具體的具體的“數據名稱數據名稱”和和“數據類型數據類型”。2.2.記錄：記錄：一組相關數據項的集合，用于描述一個對象在某方面的屬一組相關數據項的集合，用于描述一個對象在某方面的屬性。能夠唯一標識條記錄的一個或幾個數據項，稱為性。能夠唯一標識條記錄的一個或幾個數據項，稱為“關鍵字關鍵字(key(key) )”。通常，只需用一個數據項作為關鍵字。通常，只需用一個數據項作

3、為關鍵字。3.3.文件：文件：文件是指由創(chuàng)建者所定義、具有文件名的一組相關元素的文件是指由創(chuàng)建者所定義、具有文件名的一組相關元素的集合。多數文件是用戶直接可見部分。因而，文件管理是操作系集合。多數文件是用戶直接可見部分。因而，文件管理是操作系統一個非常重要的內容，是最大的數據單位統一個非常重要的內容，是最大的數據單位 2022-2-256一 文件與文件系統文件與文件系統【二二】文件定義與描述文件定義與描述1.1.文件文件定義：定義：文件是指由創(chuàng)建者所定義、文件是指由創(chuàng)建者所定義、是一組被賦名的、是一組被賦名的、在在邏輯上邏輯上具有完整意義、在內容存放有嚴格順序、記錄在某種介質上的、有具有完整意

4、義、在內容存放有嚴格順序、記錄在某種介質上的、有意義的信息集合。意義的信息集合。2.2.文件的屬性文件的屬性：文件是容納數據的容器。是文件系統中最大的數據單位。文件是容納數據的容器。是文件系統中最大的數據單位。 每個文件都具有名稱、每個文件都具有名稱、類型、大小、存儲的具體物理位置。類型、大小、存儲的具體物理位置。文件的建立時間。指文件最后一次的修改時間。文件的建立時間。指文件最后一次的修改時間。文件的組織形式，掩蓋了物理上存放的不連續(xù)性，遮掩了低層文件的組織形式，掩蓋了物理上存放的不連續(xù)性，遮掩了低層物理硬件上的細節(jié)。物理硬件上的細節(jié)。2022-2-257一 文件與文件系統文件與文件系統3.

5、3. 文件操作文件操作最基本的文件操作最基本的文件操作包括：包括： (1) (1) 創(chuàng)建文件。系統應為分配必要外創(chuàng)建文件。系統應為分配必要外存，建立一個目錄項，記錄新文件的文件名、外存、的地址等屬性存，建立一個目錄項，記錄新文件的文件名、外存、的地址等屬性信息。信息。(2) (2) 刪除文件；刪除文件；(3) (3) 讀文件。須在系統調用中給出文件名和讀文件。須在系統調用中給出文件名和應讀入內存的地址。在目錄項中，還須有一個指針用于對文件的讀應讀入內存的地址。在目錄項中，還須有一個指針用于對文件的讀/ /寫。寫。(4) (4) 寫文件。寫文件。(5) (5) 設置文件的讀設置文件的讀/ /寫位

6、置。即為文件的讀寫位置。即為文件的讀/ /寫操寫操作，設置用于文件讀作，設置用于文件讀/ /寫操作位置的指針。寫操作位置的指針。 文件的文件的“打開打開”和和“關閉關閉”操作操作“打開打開”是指系統將指名文件的屬性從外存拷貝到內存，并將文是指系統將指名文件的屬性從外存拷貝到內存，并將文件表目中的編號件表目中的編號( (或稱為索引或稱為索引) )返回給用戶。以方便索引查找，從返回給用戶。以方便索引查找，從而避免了對該文件的再次檢索。關閉文件，即從打開文件表中的而避免了對該文件的再次檢索。關閉文件，即從打開文件表中的表目上將其刪掉。表目上將其刪掉。 2022-2-258一 文件與文件系統文件與文件

7、系統其它文件操作其它文件操作為了方便用戶使用文件，通常，為了方便用戶使用文件，通常，OSOS都提供了數條有關文件操都提供了數條有關文件操作的系統調用，可將這些調用分成若干類作的系統調用，可將這些調用分成若干類: : 最常用的一類是有最常用的一類是有關對文件屬性進行操作的，即允許用戶直接設置和獲得文件的關對文件屬性進行操作的，即允許用戶直接設置和獲得文件的屬性，如改變已存文件的文件名、改變文件的擁有者屬性，如改變已存文件的文件名、改變文件的擁有者( (文件主文件主) )、改變對文件的訪問權，以及查詢文件的狀態(tài)改變對文件的訪問權，以及查詢文件的狀態(tài)( (包括文件類型、包括文件類型、大小和擁有者以及

8、對文件的訪問權等大小和擁有者以及對文件的訪問權等) )；另一類是有關目錄的，如創(chuàng)建一個目錄，刪除一個目錄，改另一類是有關目錄的，如創(chuàng)建一個目錄，刪除一個目錄，改變當前目錄和工作目錄等；此外，還有用于實現文件共享的系變當前目錄和工作目錄等；此外，還有用于實現文件共享的系統調用和用于對文件系統進行操作的系統調用等。統調用和用于對文件系統進行操作的系統調用等。 2022-2-259一 文件與文件系統文件與文件系統文件記錄1記錄2記錄n數據項1數據項2數據項n圖圖1 1文件、記錄和數據項之間的層次關系示意圖文件、記錄和數據項之間的層次關系示意圖 2022-2-2510一 文件與文件系統文件與文件系統【

9、三三】文件系統文件系統文件系統定義文件系統定義OSOS中與管理文件的軟件和數據的集合稱為文件中與管理文件的軟件和數據的集合稱為文件系統。其主要功能包括系統。其主要功能包括文件的建立、撤銷、修改、刪除、復制、移文件的建立、撤銷、修改、刪除、復制、移動、訪問權限與存取控制、檢索等：動、訪問權限與存取控制、檢索等：文件系統功能文件系統功能1.1.為了合理的存放文件，必需對磁盤等輔助存儲器空間為了合理的存放文件，必需對磁盤等輔助存儲器空間 ( (或稱文或稱文件空間件空間) ) 進行統一管理。在用戶創(chuàng)建新文件時為其分配空閑區(qū)，進行統一管理。在用戶創(chuàng)建新文件時為其分配空閑區(qū)，而在用戶刪除或修改某個文件時，

10、回收和調整存儲區(qū)。而在用戶刪除或修改某個文件時，回收和調整存儲區(qū)。2.2.為實現按名存取，需要有一個用戶可見的文件邏輯結構，用戶為實現按名存取，需要有一個用戶可見的文件邏輯結構，用戶按照文件邏輯結構所給定的方式進行信息的存取和加工。這種按照文件邏輯結構所給定的方式進行信息的存取和加工。這種邏輯結構是獨立于物理存儲設備的。邏輯結構是獨立于物理存儲設備的。2022-2-2511一 文件與文件系統文件與文件系統3.3.文件在存儲設備上的存放順序，稱為文件的物理結構。存儲結文件在存儲設備上的存放順序，稱為文件的物理結構。存儲結構的設計以便于信息存放和加工為目標；構的設計以便于信息存放和加工為目標；4.

11、4.實現對文件信息的查找。實現對文件信息的查找。5.5.成文件的共享和提供保護功能。成文件的共享和提供保護功能。文件系統的特點文件系統的特點1.1.用戶接口友好，用戶只對文件進行操作，而不管文件結構和存用戶接口友好，用戶只對文件進行操作，而不管文件結構和存放的物理位置。放的物理位置。2.2.對文件按名存取，對用戶透明。對文件按名存取，對用戶透明。3.3.某些文件可以被多個用戶或進程所共享。某些文件可以被多個用戶或進程所共享。4.4.文件系統一般均可使用磁盤、光盤等大容量存儲介質。文件系統一般均可使用磁盤、光盤等大容量存儲介質。2022-2-2512一 文件與文件系統文件與文件系統文件系統的三個

12、模型文件系統的三個模型1.1. 最高層：文件系統的兩種類型接口最高層：文件系統的兩種類型接口命令接口命令接口 指作為用戶與文件系統交互的接口。指作為用戶與文件系統交互的接口。 如通過鍵如通過鍵盤輸入命令，與文件系統進行交互。盤輸入命令，與文件系統進行交互。程序接口程序接口用戶程序與文件系統的專用接口，一般通過專用用戶程序與文件系統的專用接口，一般通過專用的系統調用命令（函數接口）進行銜接服務。的系統調用命令（函數接口）進行銜接服務。圖2文件系統模型文件系統接口文件系統接口對對象操縱和管理的軟件集合對對象操縱和管理的軟件集合文件管理系統管理的對象及其屬性文件管理系統管理的對象及其屬性用戶（用戶（

13、程序程序）2022-2-2513一 文件與文件系統文件與文件系統2.2. 中間層：對對象操縱和管理的軟件集合：中間層：對對象操縱和管理的軟件集合：這是文件管理系統的核心部分。文件系統的功能大多是在這一這是文件管理系統的核心部分。文件系統的功能大多是在這一層實現的，其中包括層實現的，其中包括: : 對文件存儲空間、讀寫、文件目錄的管對文件存儲空間、讀寫、文件目錄的管理、用于將文件的邏輯地址轉換為物理地址的機制、對文件的理、用于將文件的邏輯地址轉換為物理地址的機制、對文件的管理，以及對文件的共享與保護等功能。管理，以及對文件的共享與保護等功能。3. 3. 最低層：文件管理系統管理的對象及其屬性：最

14、低層：文件管理系統管理的對象及其屬性：文件文件它作為文件管理的直接對象。它作為文件管理的直接對象。目錄目錄為方便用戶對文件的存取和檢索而配置的目錄，每個為方便用戶對文件的存取和檢索而配置的目錄，每個目錄項均有文件名及該文件所在的物理地址目錄項均有文件名及該文件所在的物理地址( (或指針或指針) )。磁盤磁盤( (磁帶磁帶) )存儲空間。存儲空間。2022-2-2514一 文件與文件系統文件與文件系統【四四】文件類型文件類型1.1.按用途劃分按用途劃分系統文件系統文件 只允許用戶調用執(zhí)行，禁止用戶進行只允許用戶調用執(zhí)行，禁止用戶進行R/WR/W訪問；訪問；用戶文件用戶文件 泛指由用戶編寫的源代碼

15、與數據文件，及其生成泛指由用戶編寫的源代碼與數據文件，及其生成的目標文件、可執(zhí)行文件或。用戶將其委托的目標文件、可執(zhí)行文件或。用戶將其委托OSOS進行管理。進行管理。庫文件庫文件 標準程序，函數等標準程序，函數等( (只能執(zhí)行不能修改只能執(zhí)行不能修改) )。 特殊文件特殊文件 指系統中的各類指系統中的各類I/OI/O設備，依據傳輸速度可分為設備，依據傳輸速度可分為塊設備文件和字符設備文件。前者用于磁盤或光盤等塊設備的塊設備文件和字符設備文件。前者用于磁盤或光盤等塊設備的I/O I/O 操作。后者用于終端、打印機等字符設備的操作。后者用于終端、打印機等字符設備的I/O I/O 操作。操作。202

16、2-2-2515一 文件與文件系統文件與文件系統2.2.按按訪問權限劃分按按訪問權限劃分R R文件文件 只讀文件；只讀文件；R/WR/W文件文件 可讀可寫文件；可讀可寫文件；E E文件文件 只能執(zhí)行的隱含文件；只能執(zhí)行的隱含文件；3.3.按邏輯結構劃分按邏輯結構劃分記錄文件記錄文件（結構文件）（結構文件） 由若干個相關記錄組成的文件；由若干個相關記錄組成的文件；流式文件流式文件（無結構文件）（無結構文件） 由一個字符流組成的文件；由一個字符流組成的文件； 4.4.按照物理結構劃分按照物理結構劃分連續(xù)存放的文件連續(xù)存放的文件 順序文件順序文件不連續(xù)存放的文件不連續(xù)存放的文件 指針鏈接文件、如鏈表

17、、索引文件；指針鏈接文件、如鏈表、索引文件；2022-2-2516一 文件與文件系統文件與文件系統5.5.按組織形式和處理方式分類按組織形式和處理方式分類普通文件普通文件 由由ASCIIASCII碼或二進制碼組成的字符文件。一碼或二進制碼組成的字符文件。一般用戶建立的源程序文件、數據文件、目標代碼文件及操般用戶建立的源程序文件、數據文件、目標代碼文件及操作系統自身代碼文件、庫文件、實用程序文件等都是普通作系統自身代碼文件、庫文件、實用程序文件等都是普通文件，通常存儲在外存儲設備上。文件，通常存儲在外存儲設備上。目錄文件目錄文件 由文件目錄組成，也由字符序列構成，屬由文件目錄組成，也由字符序列構

18、成，屬于系統文件，文件操作與普通文件一樣。其功能在于對文于系統文件，文件操作與普通文件一樣。其功能在于對文件目錄進行管理，能夠快速對其它文件的信息進行檢索。件目錄進行管理，能夠快速對其它文件的信息進行檢索。 2022-2-2517一 文件與文件系統文件與文件系統【五五】國內外有關文件管理的學術派別觀點簡介國內外有關文件管理的學術派別觀點簡介1.1.無定義派無定義派( (強調文件與強調文件與OS的整體性的整體性) )該派對文件的研究，側重于文件系統的實現，側重于考慮文件該派對文件的研究，側重于文件系統的實現，側重于考慮文件系統的客觀性、安全性和保護機制方面的研究。系統的客觀性、安全性和保護機制方

19、面的研究。 （Wodharer、Taunebaum、Menglier 學派）學派）2.2.定義派定義派( (強調文件與強調文件與OS可隔離性可隔離性) )系統定義派：系統定義派：該派的主要觀點是從系統角度對文件加以論述，該派的主要觀點是從系統角度對文件加以論述，強調文件的相對獨立性，主張把文件系統從強調文件的相對獨立性，主張把文件系統從os中從核心層剝中從核心層剝離出來。對外存進行嚴格定義，突出強調了內外存之間的關離出來。對外存進行嚴格定義，突出強調了內外存之間的關系及外存的物理結構。系及外存的物理結構。 ( (孟靜、徐甲同、羅宇孟靜、徐甲同、羅宇) )2022-2-2518一 文件與文件系統

20、文件與文件系統用戶定義派：用戶定義派： 該派強調了文件對用戶的重要性，如何滿足用該派強調了文件對用戶的重要性，如何滿足用戶需要對文件加以論述，強調了外殼命令功能的完整性和用戶需要對文件加以論述，強調了外殼命令功能的完整性和用戶操作的方便性。戶操作的方便性。( (湯子贏湯子贏 龐麗萍龐麗萍) ) 。 3.3. 研究派研究派( (實現派實現派) )：該派側重于文件系統的實現研究，擱置爭議，該派側重于文件系統的實現研究，擱置爭議，從解決問題的角度，如提高查找的速度、方法等。主要析解從解決問題的角度，如提高查找的速度、方法等。主要析解UNIXUNIX、 LinuxLinux。（孫玉芳、劉日升）。（孫玉

21、芳、劉日升）?！玖糠峙捎^點背景分派觀點背景1.1.文件和載體文件和載體( (內外存內外存) )有關；有關；2.2.文件和文件和I/OI/O設備有關；設備有關；3.3.文件和用戶有關；文件和用戶有關；4.4.文件和文件和OSOS有關有關以上為個人觀點，僅供參考！以上為個人觀點，僅供參考！二二 文件的邏輯結構文件的邏輯結構2022-2-2520二 文件的邏輯結構文件的邏輯結構【一一】邏輯與結構的絮語邏輯與結構的絮語1.1.什么是邏輯？什么是邏輯？表示客觀事物發(fā)展的規(guī)律；表示客觀事物發(fā)展的規(guī)律；表示思維的規(guī)律性或規(guī)則；表示思維的規(guī)律性或規(guī)則；形式邏輯；形式邏輯；某種特殊理論、觀點或說法，如：誰先

22、控制海洋誰就將某種特殊理論、觀點或說法，如：誰先控制海洋誰就將控制世界?？刂剖澜?。研究思維形式及其規(guī)律的科學研究思維形式及其規(guī)律的科學。邏輯是什么？是客觀事物內在之間的關系！邏輯是什么？是客觀事物內在之間的關系！2022-2-2521二 文件的邏輯結構文件的邏輯結構2.2. 結構是什么？結構是什么？ 結構即是一種觀念形態(tài)，又是物質的一結構即是一種觀念形態(tài)，又是物質的一種運動狀態(tài)種運動狀態(tài) ，是人們用來表達世界存在的形態(tài)和運動狀態(tài)的專，是人們用來表達世界存在的形態(tài)和運動狀態(tài)的專業(yè)術語。業(yè)術語。 3.3.文件的邏輯結構釋疑文件的邏輯結構釋疑 即文件的形態(tài)與變化狀態(tài)！文件即文件的形態(tài)與變化狀態(tài)！文件

23、的邏輯結構是一種字符流形式。是一種無結構的文件組織方式。的邏輯結構是一種字符流形式。是一種無結構的文件組織方式。無結構的基本特征即反映了由字符組成的文件內部之間的相互無結構的基本特征即反映了由字符組成的文件內部之間的相互關系，即邏輯關系，結構形態(tài)。其基本特征是：關系，即邏輯關系，結構形態(tài)。其基本特征是： 只有一個基本信息單位；只有一個基本信息單位；查找文件元素信息困難。查找文件元素信息困難。文件管理簡單，方便用戶操作文件管理簡單，方便用戶操作是一種是一種用戶可見的結構。用戶可見的結構。2022-2-2522二 文件的邏輯結構文件的邏輯結構【二二】文件的邏輯結構類型文件的邏輯結構類型有結構文件有

24、結構文件(記錄式結構文件記錄式結構文件)無結構文件無結構文件 只有1個記錄的字符流式文件，簡稱為流失文件1. 定長記錄文件的組織形式 順序文件；2. 變長記錄文件的組織形式 索引文件， 索引順序文件圖圖3 3：文件的邏輯結構類型圖：文件的邏輯結構類型圖2022-2-2523二 文件的邏輯結構文件的邏輯結構1.1. 有結構文件的類型（有結構文件的類型（記錄式結構文件）記錄式結構文件）1 1）記錄絮語與類型記錄絮語與類型記錄是一個具有特定意義的信息單位，它由記錄自身的邏輯地址記錄是一個具有特定意義的信息單位，它由記錄自身的邏輯地址( (相相對位置對位置) )、及記錄名所對應的一組屬性值所組成。、及

25、記錄名所對應的一組屬性值所組成。記錄式結構記錄式結構 具有不同的排列方式，因而構成兩種不同的邏輯結具有不同的排列方式，因而構成兩種不同的邏輯結構，即定長記錄結構和定長記錄結構。構，即定長記錄結構和定長記錄結構。2)2) 定長記錄定長記錄所有記錄的長度都是等長的。定長記錄的處理方便、所有記錄的長度都是等長的。定長記錄的處理方便、開銷小，是目前被廣泛用于數據處理中的一種記錄格式。開銷小，是目前被廣泛用于數據處理中的一種記錄格式。 3) 3) 變長記錄變長記錄文件中各記錄的長度不等。原因是記錄中的數據項文件中各記錄的長度不等。原因是記錄中的數據項數大小長短并不一致，如論文中的題目、摘要、關鍵詞、內容

26、等。數大小長短并不一致，如論文中的題目、摘要、關鍵詞、內容等。記錄處理之前，其長度可知。記錄處理之前，其長度可知。2022-2-2524二 文件的邏輯結構文件的邏輯結構2.2.無結構文件無結構文件流式文件流式文件源程序、可執(zhí)行文件、庫函數等，均為無結構源程序、可執(zhí)行文件、庫函數等，均為無結構的文件形式，即流式文件。其長度以字節(jié)為單位。的文件形式，即流式文件。其長度以字節(jié)為單位。對流式文件的訪問，則是采用讀對流式文件的訪問，則是采用讀/ /寫指針來指出寫指針來指出下一個要訪問的字符。下一個要訪問的字符。流式文件看做是只有一個流式文件看做是只有一個記錄的記錄式文件的一個特例。記錄的記錄式文件的一個

27、特例。2022-2-2525二 文件的邏輯結構文件的邏輯結構【三三】為快速查找定長記錄而組織文件形式為快速查找定長記錄而組織文件形式 順序文件順序文件1 1邏輯記錄的排序（邏輯記錄的排序（為了實現快速查找需要準備的基礎知識）為了實現快速查找需要準備的基礎知識）1 1）串結構排序串結構排序，記錄之間的順序與關鍵字無關。其排序通常按照，記錄之間的順序與關鍵字無關。其排序通常按照生成記錄的時間的次序進行決定的。串結構排序的文件查找記錄生成記錄的時間的次序進行決定的。串結構排序的文件查找記錄時由于每次都必須從頭開始，逐個記錄地查找，所以時由于每次都必須從頭開始，逐個記錄地查找，所以效率很低。效率很低。

28、2 2）順序結構排序，順序結構排序，按照關鍵字按照關鍵字( (詞詞) )的長短從小到，或從大到小，的長短從小到，或從大到小，或按照其英文字母的順序將記錄排序的結構，稱為順序結構排序。或按照其英文字母的順序將記錄排序的結構，稱為順序結構排序。 順序結構文件，順序結構文件，則可利用某種有效的查找算法，如折半查找則可利用某種有效的查找算法，如折半查找法、插值查找法、跳步查找法等，因為順序結構文件具有較法、插值查找法、跳步查找法等，因為順序結構文件具有較高的檢索效率，而被廣泛使用。高的檢索效率，而被廣泛使用。 2022-2-2526二 文件的邏輯結構文件的邏輯結構2 2順序文件的讀順序文件的讀/ /寫

29、操作寫操作順序文件中的記錄可以是定長或變長的。對于定長記錄的順序文順序文件中的記錄可以是定長或變長的。對于定長記錄的順序文件，如果已知當前記錄的邏輯地址。在讀一個文件時，設置一個件，如果已知當前記錄的邏輯地址。在讀一個文件時，設置一個讀指針讀指針RptrRptr，令它指向下一個記錄的首地址，每當讀完一個記錄，令它指向下一個記錄的首地址，每當讀完一個記錄時，便執(zhí)行：時，便執(zhí)行：Rptr:=Rptr + L Rptr:=Rptr + L ，其中的，其中的L L為記錄長度。同樣在寫為記錄長度。同樣在寫一個文件時，也應設置一個寫指針一個文件時，也應設置一個寫指針WptrWptr，操作同上。，操作同上。

30、對于變長記錄的順序文件的對于變長記錄的順序文件的R/WR/W讀或寫與定長記錄時的情況基本讀或寫與定長記錄時的情況基本一樣，故略去不述。定長和變長記錄文件如圖一樣，故略去不述。定長和變長記錄文件如圖4 4所示：所示：3 3順序文件的優(yōu)缺點順序文件的優(yōu)缺點優(yōu)點：適于批量存取，存取效率最高。優(yōu)點：適于批量存取，存取效率最高。 缺點：查找指定記錄速度慢。七次是增加或刪除記錄比較困難。缺點：查找指定記錄速度慢。七次是增加或刪除記錄比較困難。2022-2-2527二 文件的邏輯結構文件的邏輯結構R0R1R2R3RiLLLLLL2L3L4LiL(i1)LRptr(a) 定長記錄文件L0R0L1R1RiWpt

31、r(b ) 變長記錄文件Li00L0L01L1L0L12Li(Lk1)i1k0(Lk1)ik0圖圖4 4定長和變長記錄文件定長和變長記錄文件 2022-2-2528二 文件的邏輯結構文件的邏輯結構對于定長記錄，順序文件查找速度最快！對于定長記錄，順序文件查找速度最快！對于不對于不 定長記錄，順序文件查找速度則最慢！定長記錄，順序文件查找速度則最慢！2022-2-2529二 文件的邏輯結構文件的邏輯結構【四四】為快速查找定長記錄而組織文件形式為快速查找定長記錄而組織文件形式 索引文件索引文件1. 1. 索引文件索引文件 對于變長度記錄，通常為之建立一張索引表，并為對于變長度記錄，通常為之建立一張

32、索引表，并為每個記錄設置一個記錄長度的表項，如，要查找第每個記錄設置一個記錄長度的表項，如，要查找第N N條記錄，即將前條記錄，即將前面的面的N-1N-1個記錄的長度求和，即可查到第個記錄的長度求和，即可查到第N N條記錄的首地址。條記錄的首地址。2.2. 索引順序文件索引順序文件 是索引文件的改進，是索引文件的改進，它基本思路是將順序文件它基本思路是將順序文件中的所有記錄分為若干個組中的所有記錄分為若干個組( (例如，例如，5050個記錄為一個組個記錄為一個組) )，為每組建，為每組建立一個組索引表，有多少組，就有多少個組索引表。其次為整個順立一個組索引表，有多少組，就有多少個組索引表。其次

33、為整個順序文件建立一張索引表，該表中僅有組號和每組中的首條記錄地址序文件建立一張索引表，該表中僅有組號和每組中的首條記錄地址建立一個索引項，由該表找到對應的組索引表，再按照索引文件的建立一個索引項，由該表找到對應的組索引表，再按照索引文件的方式可以很快查到要找的該記錄。如圖方式可以很快查到要找的該記錄。如圖6 6所示。所示。2022-2-2530二 文件的邏輯結構文件的邏輯結構索引號0長度 m指針 ptrm01m1imi索引表R0R1Ri邏輯文件圖圖5 5索引文件的組織索引文件的組織 2022-2-2531二 文件的邏輯結構文件的邏輯結構記錄記錄長度184275N132組號組號的首地址1842

34、6276A5NFFD2記錄記錄長度184275N132第1組索引表第1組索引表第N組索引表順序順序+索引索引1表表圖圖5 5：針對不定長記錄的索引順序文件組織表：針對不定長記錄的索引順序文件組織表 湯湯3 P2113 P211圖圖6-56-5是錯誤！是錯誤！2022-2-2532二 文件的邏輯結構文件的邏輯結構百度百科中的鍵值說百度百科中的鍵值說注冊表中的鍵值就相當于系統特有的數據庫種的某個關鍵字段，用特注冊表中的鍵值就相當于系統特有的數據庫種的某個關鍵字段，用特定的方法調用，根據特有位置的鍵值，判斷程序應該執(zhí)行的步驟。定的方法調用，根據特有位置的鍵值，判斷程序應該執(zhí)行的步驟。鍵值位于注冊表結

35、構鏈末端，它包含當前執(zhí)行時用到的實際配置信息鍵值位于注冊表結構鏈末端，它包含當前執(zhí)行時用到的實際配置信息和數據，其數據類型可以是字符串、或二進制值、或和數據，其數據類型可以是字符串、或二進制值、或DWORDDWORD（雙字（雙字節(jié)），以適應不同環(huán)境的使用需求。節(jié)），以適應不同環(huán)境的使用需求。鍵值項是指顯示在鍵值項是指顯示在“注冊表編輯器注冊表編輯器”右側的項目，每個鍵值項包括名右側的項目，每個鍵值項包括名稱，類型和數據三部分。名稱由除反斜杠之外的任意字符組成。鍵稱，類型和數據三部分。名稱由除反斜杠之外的任意字符組成。鍵值項所定義的內容即為該鍵值項的值，即值項所定義的內容即為該鍵值項的值，即“鍵

36、值鍵值”，其中最多能存，其中最多能存放放64KB64KB大小的數據。大小的數據。 鍵的含鍵的含 用于標識數據和控制數據的一個和幾個字符，稱為關鍵字。用于標識數據和控制數據的一個和幾個字符，稱為關鍵字。 由用戶設置并操作，用于產生一組代碼或符號的由用戶設置并操作，用于產生一組代碼或符號的“一個按鍵一個按鍵”。O SO S 中 鍵中 鍵的 含 義的 含 義2022-2-2533二 文件的邏輯結構文件的邏輯結構【五五】直接文件與直接文件與哈希哈希(Hash)文件文件 直接到物理地址中可以訪問的文件簡稱為直接到物理地址中可以訪問的文件簡稱為直接文件！直接文件！根據給定的記錄根據給定的記錄鍵值，直接獲得

37、指定記錄的物理地址。這種由記錄鍵值到記錄物理地鍵值，直接獲得指定記錄的物理地址。這種由記錄鍵值到記錄物理地址的轉換被稱為鍵值轉換。址的轉換被稱為鍵值轉換。哈希哈希(Hash)(Hash)文件文件 是目前應用最為廣泛的一種是目前應用最為廣泛的一種直接文件直接文件。它利用它利用HashHash函數函數( (或稱散列函數或稱散列函數) )，可將記錄，可將記錄鍵值鍵值轉換為相應記錄轉換為相應記錄的地址。但為了實現文件存儲空間的動態(tài)分配，通常由的地址。但為了實現文件存儲空間的動態(tài)分配，通常由HashHash函數函數指向一目錄表相應表目的指向一目錄表相應表目的指針指針，找到指向相應記錄的物理塊，找到指向相

38、應記錄的物理塊，通常，把通常，把HashHash函數作為標準函數存于系統中，供存取文件時調用。函數作為標準函數存于系統中，供存取文件時調用。 2022-2-2534二 文件的邏輯結構文件的邏輯結構fHash函數目錄表鍵值圖6Hash文件的邏輯結構示意圖 2022-2-2535二 文件的邏輯結構文件的邏輯結構【六六】有文件結構的排列模式有文件結構的排列模式 1.1. 連續(xù)模式結構連續(xù)模式結構：按照記錄生成的先后順序排列：按照記錄生成的先后順序排列有利于記錄追加和變更；有利于記錄追加和變更；搜索效率低。搜索效率低。2.2. 多重邏輯模式結構：多重邏輯模式結構：按照按照鍵鍵和記錄名排列成行、列式的一

39、種結構；和記錄名排列成行、列式的一種結構； 此種方法能夠實現有效存儲，是非常重要的一種方法。此種方法能夠實現有效存儲，是非常重要的一種方法。采用二維表的矩陣模式。采用二維表的矩陣模式。3.3. 轉置模式結構：轉置模式結構：為方便查找，把列、行進行變換的一種結構。為方便查找，把列、行進行變換的一種結構。4.4. 排序模式結構：排序模式結構：按照時間、字母等某種順序組織的記錄結構按照時間、字母等某種順序組織的記錄結構2022-2-2536二 文件的邏輯結構文件的邏輯結構【七七】實現文件邏輯結構的原則實現文件邏輯結構的原則 信息變動少；信息變動少； 查找速度快；查找速度快； 文件信息占據存儲空間最小

40、；文件信息占據存儲空間最小； 方便用戶操作。方便用戶操作。2022-2-2537二 文件的邏輯結構文件的邏輯結構【八八】文件的存取方法文件的存取方法通過對文件訪問實現文件的修改、追加和搜索等操作，方法有三：通過對文件訪問實現文件的修改、追加和搜索等操作，方法有三：1 1. . 順序存取法：順序存取法：按照文件的邏輯地址順序存取。按照文件的邏輯地址順序存取。2.2. 隨機存取法隨機存取法( (直接存取法直接存取法) )：根據記錄編號訪問文件的任一記錄，根據記錄編號訪問文件的任一記錄，或根據存取命令，通過移動指針的方法，實現對文件的讀寫訪問?；蚋鶕嫒∶?，通過移動指針的方法，實現對文件的讀寫訪問

41、。3.3. 按鍵存取法（按鍵存取法（表格搜索法）表格搜索法）：按鍵存取是一種用在復雜文件系統，按鍵存取是一種用在復雜文件系統，特別是數據庫管理系統中，根據給定的鍵或記錄名進行存取的方特別是數據庫管理系統中，根據給定的鍵或記錄名進行存取的方法。該方法首先搜索到訪問記錄的邏輯位置，再將其映射到相應法。該方法首先搜索到訪問記錄的邏輯位置，再將其映射到相應的物理地址后進行存取。的物理地址后進行存取。2022-2-2538二 文件的邏輯結構文件的邏輯結構【九九】文件的文件的“鍵鍵”搜索算法搜索算法1. 1. 線性搜索法：線性搜索法：從第一個鍵或記錄開始，依次和所要搜索的鍵或記錄從第一個鍵或記錄開始，依次

42、和所要搜索的鍵或記錄相比較，直到找到所需要的記錄為止。線性搜索法的搜索效率較低，相比較，直到找到所需要的記錄為止。線性搜索法的搜索效率較低，在文件中記錄個數較多時不宜采用。在文件中記錄個數較多時不宜采用。2.2. 散列法：散列法：散列搜索法被被廣泛用于現代操作系統的數據查找。散列散列搜索法被被廣泛用于現代操作系統的數據查找。散列法的核心思想是定義一個散列函數法的核心思想是定義一個散列函數h(k)h(k)，使得對于給定的鍵，使得對于給定的鍵k k，散，散列函數列函數h(k)h(k)將其變換為將其變換為 k k所對應的邏輯地址。所對應的邏輯地址。3.3. 二分搜索法：二分搜索法：事先把搜索對象按一

43、定順序排列。該方法具有較高的事先把搜索對象按一定順序排列。該方法具有較高的搜索效率。適用于順序結構排列的按照鍵或記錄來進行搜索的一種搜索效率。適用于順序結構排列的按照鍵或記錄來進行搜索的一種方法。方法。2022-2-2539三三 文件的物理結構與存儲設備文件的物理結構與存儲設備 【一一】文件的物理結構文件的物理結構文件的物理結構是指文件在外存上的存放形式文件的物理結構是指文件在外存上的存放形式1. 1. 放到什么介質上？放到什么介質上？2. 2. 用什么方法存放？用什么方法存放？3. 3. 以什么樣的形式存放？以什么樣的形式存放？4. 4. 怎樣存放是安全的？怎樣存放是安全的？5. 5. 訪問

44、速度與系統的吻合性？訪問速度與系統的吻合性？2022-2-2540三三 文件的物理結構與存儲設備文件的物理結構與存儲設備【二二】兩個相關四個定義兩個相關四個定義1.1. 兩個相關兩個相關文件的物理結構和存儲設備密切相關。文件的物理結構和存儲設備密切相關。文件的物理結構與邏輯結構密切相關。文件的物理結構與邏輯結構密切相關。2.2. 四個定義四個定義物理文件物理文件外存中的存放文件，該文件可以外存中的存放文件，該文件可以R/WR/W訪問；訪問；邏輯文件邏輯文件內存中的文件（可以修改的用戶文件）；內存中的文件（可以修改的用戶文件）；物理結構物理結構文件在外存上的存放形式文件在外存上的存放形式( (連

45、續(xù)和串聯連續(xù)和串聯) )邏輯結構邏輯結構在內存上的虛擬存放形式：連續(xù)、順序、多重、在內存上的虛擬存放形式：連續(xù)、順序、多重、轉置。轉置。2022-2-2541三三 文件的物理結構與存儲設備文件的物理結構與存儲設備【三三】物理上連續(xù)存儲結構文件（在外存上）物理上連續(xù)存儲結構文件（在外存上）在外存上連續(xù)存放的文件，稱之為連續(xù)文件或順序文件。在外存上連續(xù)存放的文件，稱之為連續(xù)文件或順序文件。優(yōu)點：優(yōu)點： 存儲簡單，存取速度快。存儲簡單，存取速度快。缺點：缺點： 不能總動態(tài)增長，要求用戶給定最大長度。不能總動態(tài)增長，要求用戶給定最大長度。【四四】串聯結構文件（又稱鏈結構文件）串聯結構文件（又稱鏈結構文

46、件）物理塊：物理塊：512B 512B 8KB 8KB，適用于磁帶機順序存取。，適用于磁帶機順序存取。優(yōu)點：優(yōu)點： 文件可實現動態(tài)增長，通過改變指針即可以實現信息塊文件可實現動態(tài)增長，通過改變指針即可以實現信息塊的插入或刪除。的插入或刪除。缺點：缺點： 搜索速度慢，不適宜隨機存取。搜索速度慢，不適宜隨機存取。2022-2-2542三三 文件的物理結構與存儲設備文件的物理結構與存儲設備【五五】外存文件索引法外存文件索引法將多個文件建立一張索引表。將多個文件建立一張索引表。文件控制塊文件控制塊（FCBFCB）中給出索引表的首指針。中給出索引表的首指針。【六六】索引表的多重索引結構索引表的多重索引結

47、構文件索引方法效率低下的原因：文件過大，索引表大文件索引方法效率低下的原因：文件過大，索引表大解決方法解決方法1 1；將索引表的物理塊用串聯的方式加以連接，但搜索效將索引表的物理塊用串聯的方式加以連接，但搜索效率低，花費時間多。率低，花費時間多。解決方法解決方法2 2；通過建立多重索引結構解決通過建立多重索引結構解決（張三版（張三版P188P188）索引表置于內存；索引表置于內存；直接尋址與混合尋址結構。直接尋址與混合尋址結構。2022-2-2543三三 文件的物理結構與存儲設備文件的物理結構與存儲設備【七七】文件的直接存取設備文件的直接存取設備1.1.硬盤：硬盤：表面劃分為表面劃分為20-1

48、50020-1500個同心圓，每個圓周稱為一個磁道；個同心圓，每個圓周稱為一個磁道；信息只能依序（線性）記錄在每個磁道上；信息只能依序（線性）記錄在每個磁道上； 20-150020-1500個磁道；每個磁道個磁道；每個磁道4-324-32個扇區(qū)；個扇區(qū)； 每個扇區(qū)的大?。纫粋€弧段），每個扇區(qū)的大小（既一個弧段），256-512KB256-512KB；一個扇區(qū)叫一個物理塊；扇區(qū)是硬件設定的最小存取和尋址單位一個扇區(qū)叫一個物理塊；扇區(qū)是硬件設定的最小存取和尋址單位2.2.磁盤系統：磁盤系統：盤片；磁臂，磁頭，相關邏輯電路，主機通信接口等盤片；磁臂，磁頭，相關邏輯電路，主機通信接口等3.3.磁盤訪

49、問時間（通過磁盤訪問時間（通過DMADMA實現）實現）尋道時間尋道時間 尋找磁盤的時間；尋找磁盤的時間；延遲時間延遲時間 訪問扇區(qū)時間；訪問扇區(qū)時間；傳送時間傳送時間 外存到內存的時間。外存到內存的時間。 2022-2-2544四四 文件的存儲空間管理文件的存儲空間管理導言導言: :有效地進行存儲空間管理，才能保證多個用戶有效地進行存儲空間管理，才能保證多個用戶共享文件存儲設備和實現按名存取共享文件存儲設備和實現按名存取。由于文件存儲設備是。由于文件存儲設備是分成若干個大小相等的物理塊，并以塊為單位來交換信息分成若干個大小相等的物理塊，并以塊為單位來交換信息的，因此，文件存儲空間的管理實質上是

50、一個空閑塊的組的，因此，文件存儲空間的管理實質上是一個空閑塊的組織和管理問題，它包括織和管理問題，它包括空閑塊的組織空閑塊的組織，空閑塊的分配空閑塊的分配與與空空閑塊的回收閑塊的回收等幾個問題。等幾個問題。2022-2-2545四四 文件的存儲空間管理文件的存儲空間管理【一一】空閑文件目錄表空閑文件目錄表 文件名（號）文件名（號）空閑區(qū)號空閑區(qū)號空閑塊數空閑塊數空閑塊始地址空閑塊始地址11*H22*H2022-2-2546四四 文件的存儲空間管理文件的存儲空間管理【一一】空閑文件目錄表（續(xù)）空閑文件目錄表（續(xù)）系統為文件分配空閑塊時，若有合適空閑區(qū)則分配，并改寫空閑文件系統為文件分配空閑塊時，

51、若有合適空閑區(qū)則分配，并改寫空閑文件目錄表。否則，把空閑目錄中另一空閑區(qū)也分配給申請者目錄表。否則，把空閑目錄中另一空閑區(qū)也分配給申請者( (連續(xù)文件連續(xù)文件結構除外結構除外) )。若分配的空閑區(qū)項塊數大于申請者要求，則按實際需求。若分配的空閑區(qū)項塊數大于申請者要求，則按實際需求分配后，并對該表項進行修改。分配后，并對該表項進行修改。若一個文件被刪除，則釋放相應的存儲物理塊，系統則將被釋放的塊若一個文件被刪除，則釋放相應的存儲物理塊，系統則將被釋放的塊號、長度以及第一塊塊號等信息，置入空閑文件目錄。號、長度以及第一塊塊號等信息，置入空閑文件目錄?？臻e文件項方法適用于空閑文件項方法適用于連續(xù)文件

52、結構連續(xù)文件結構的文件存儲區(qū)的分配與回收的文件存儲區(qū)的分配與回收。問問? 空閑區(qū)連續(xù)嗎空閑區(qū)連續(xù)嗎? 塊的大小塊的大小=? 分配標志分配標志? 回收回收?2022-2-2547四四 文件的存儲空間管理文件的存儲空間管理【二二】空閑塊鏈方法空閑塊鏈方法1. 1. 思路思路：將所有空閑塊鏈接在一起，當申請空閑塊時，分配程序從鏈將所有空閑塊鏈接在一起，當申請空閑塊時，分配程序從鏈頭開始摘取所需要的空閑塊，然后調整鏈首指針。反之，當回收空頭開始摘取所需要的空閑塊，然后調整鏈首指針。反之，當回收空閑塊時，把釋放的空閑塊逐個插入鏈尾上。閑塊時，把釋放的空閑塊逐個插入鏈尾上。2. 2. 空閑塊鏈接方法空閑塊鏈接方法（因系統而異）（因系統而異）1 1）按空閑區(qū)大小順序鏈接的方法；按空閑區(qū)大小順序鏈接的方法；2 2）按釋放先后順序鏈接的方法；按釋放先后順序鏈接的方法；3 3）按成組鏈接法