第六章_文件管理

1、第六章第六章 文件管理文件管理內(nèi)容提要內(nèi)容提要l 文件管理的功能文件管理的功能l 文件和文件系統(tǒng)文件和文件系統(tǒng)l 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)l 文件的存儲結(jié)構(gòu)文件的存儲結(jié)構(gòu)l 目錄管理目錄管理l 文件存儲空間管理文件存儲空間管理l 文件的共享和保護(hù)文件的共享和保護(hù)文件管理的功能文件管理的功能（1）文件存儲空間的管理文件存儲空間的管理設(shè)置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，來記錄文件存儲空間的使用情況設(shè)置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，來記錄文件存儲空間的使用情況對存儲空間的分配和回收的功能對存儲空間的分配和回收的功能（2） 目錄管理目錄管理主要任務(wù)：為每個(gè)文件建立目錄項(xiàng)，并對眾多的目錄項(xiàng)加以有效主要任務(wù)：為每個(gè)文件建立目錄項(xiàng)，

2、并對眾多的目錄項(xiàng)加以有效的組織，以實(shí)現(xiàn)方便的按名存取的組織，以實(shí)現(xiàn)方便的按名存取實(shí)現(xiàn)文件共享實(shí)現(xiàn)文件共享提供快速的目錄查詢手段，以提高對文件的檢索速度提供快速的目錄查詢手段，以提高對文件的檢索速度（3） 文件的讀文件的讀/寫管理寫管理根據(jù)用戶請求，從外存中讀取數(shù)據(jù)；或?qū)?shù)據(jù)寫入外存。根據(jù)用戶請求，從外存中讀取數(shù)據(jù)；或?qū)?shù)據(jù)寫入外存。（4）文件的共享和保護(hù)文件的共享和保護(hù)防止未經(jīng)核準(zhǔn)的用戶存取文件；防止冒名頂替存取文件；防止以防止未經(jīng)核準(zhǔn)的用戶存取文件；防止冒名頂替存取文件；防止以不確切的方式使用文件。不確切的方式使用文件。6.1 6.1 文件和文件系統(tǒng)文件和文件系統(tǒng)1、文件、文件n 具有一定名

3、稱的一組相關(guān)數(shù)據(jù)的集合。文件通常具有一定名稱的一組相關(guān)數(shù)據(jù)的集合。文件通常存放在外部存儲介質(zhì)上（如磁盤、光盤等）存放在外部存儲介質(zhì)上（如磁盤、光盤等）n各種程序、數(shù)據(jù)集合各種程序、數(shù)據(jù)集合n一些低速的外部設(shè)備，如鍵盤、終端顯示器和打一些低速的外部設(shè)備，如鍵盤、終端顯示器和打印機(jī)等也被看做文件印機(jī)等也被看做文件文件n文件命名文件命名文件提供了一種將數(shù)據(jù)保存在外部存儲介質(zhì)上以便于文件提供了一種將數(shù)據(jù)保存在外部存儲介質(zhì)上以便于訪問的功能。為了方便用戶使用，每個(gè)文件都有特定訪問的功能。為了方便用戶使用，每個(gè)文件都有特定的名稱。這樣用戶就不必關(guān)心文件存儲方法、物理位的名稱。這樣用戶就不必關(guān)心文件存儲方法

4、、物理位置以及訪問方式等，而可以直接通過文件名來使用文置以及訪問方式等，而可以直接通過文件名來使用文件。件。文件名稱的長度因系統(tǒng)而異。文件名稱的長度因系統(tǒng)而異。有的文件系統(tǒng)不區(qū)分文件名的大小寫，而有的則加以有的文件系統(tǒng)不區(qū)分文件名的大小寫，而有的則加以區(qū)分。區(qū)分。有的文件系統(tǒng)只能使用有的文件系統(tǒng)只能使用ASCIIASCII字符命名文件，而有的則字符命名文件，而有的則可以使用可以使用UnicodeUnicode字符。字符。有的操作系統(tǒng)對不同的后綴有特定的解釋，而有的則有的操作系統(tǒng)對不同的后綴有特定的解釋，而有的則沒有統(tǒng)一的規(guī)定。沒有統(tǒng)一的規(guī)定。文件n文件的內(nèi)部組織：記錄和數(shù)據(jù)項(xiàng)文件的內(nèi)部組織：記

5、錄和數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)：數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。用來描述實(shí)體的數(shù)據(jù)項(xiàng)：數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。用來描述實(shí)體的某個(gè)屬性，如學(xué)生的學(xué)號，姓名等。有基本數(shù)據(jù)項(xiàng)和某個(gè)屬性，如學(xué)生的學(xué)號，姓名等。有基本數(shù)據(jù)項(xiàng)和組合數(shù)據(jù)項(xiàng)之分組合數(shù)據(jù)項(xiàng)之分記錄：記錄是一組相關(guān)數(shù)據(jù)項(xiàng)的集合，用于描述一個(gè)記錄：記錄是一組相關(guān)數(shù)據(jù)項(xiàng)的集合，用于描述一個(gè)對象在某方面的屬性。如一個(gè)學(xué)生記錄，由學(xué)號，姓對象在某方面的屬性。如一個(gè)學(xué)生記錄，由學(xué)號，姓名，年齡等組成。名，年齡等組成。文件：文件指具有一定名稱的一組相關(guān)數(shù)據(jù)的集合。文件：文件指具有一定名稱的一組相關(guān)數(shù)據(jù)的集合。 文件n文件屬性：關(guān)于文件本身的說明信息或?qū)傩孕畔?。文件屬性：關(guān)于文件

6、本身的說明信息或?qū)傩孕畔ⅰＮ募Q：供用戶使用的外部標(biāo)識。這是文件最基本的屬性。文件名稱：供用戶使用的外部標(biāo)識。這是文件最基本的屬性。文件內(nèi)部標(biāo)識：是一個(gè)編號，可以方便的管理和查找文件。文件內(nèi)部標(biāo)識：是一個(gè)編號，可以方便的管理和查找文件。文件物理位置：文件在存儲介質(zhì)上所存放的物理位置文件物理位置：文件在存儲介質(zhì)上所存放的物理位置文件擁有者：操作系統(tǒng)通常為多用戶的，不同的用戶也擁有文件擁有者：操作系統(tǒng)通常為多用戶的，不同的用戶也擁有各自不同的文件，對這些文件的操作權(quán)限也不同。各自不同的文件，對這些文件的操作權(quán)限也不同。文件權(quán)限：文件的擁有者可以為自己的文件賦予各種權(quán)限。文件權(quán)限：文件的擁有者可以

7、為自己的文件賦予各種權(quán)限。文件類型：可以從不同角度對文件進(jìn)行分類。文件類型：可以從不同角度對文件進(jìn)行分類。文件長度：文件中數(shù)據(jù)的長度。文件長度：文件中數(shù)據(jù)的長度。文件時(shí)間：文件時(shí)間有很多。如文件創(chuàng)建時(shí)間、文件最后一文件時(shí)間：文件時(shí)間有很多。如文件創(chuàng)建時(shí)間、文件最后一次修改時(shí)間、文件最后一次執(zhí)行時(shí)間，等。次修改時(shí)間、文件最后一次執(zhí)行時(shí)間，等。文件屬性n文件分類：可按不同的分類標(biāo)準(zhǔn)對文件進(jìn)行分類文件分類：可按不同的分類標(biāo)準(zhǔn)對文件進(jìn)行分類（1 1）按文件的邏輯結(jié)構(gòu)劃分）按文件的邏輯結(jié)構(gòu)劃分無結(jié)構(gòu)文件無結(jié)構(gòu)文件有結(jié)構(gòu)文件有結(jié)構(gòu)文件（2 2）按文件的物理結(jié)構(gòu)分）按文件的物理結(jié)構(gòu)分連續(xù)文件連續(xù)文件非連續(xù)文

8、件非連續(xù)文件鏈接文件鏈接文件索引文件索引文件文件分類（3 3）按文件的用途分）按文件的用途分系統(tǒng)文件系統(tǒng)文件庫文件庫文件用戶文件用戶文件 （4 4）按文件中數(shù)據(jù)的組織形式分）按文件中數(shù)據(jù)的組織形式分源文件源文件目標(biāo)文件目標(biāo)文件可執(zhí)行文件可執(zhí)行文件（5 5）按文件的存取控制屬性分）按文件的存取控制屬性分只執(zhí)行文件只執(zhí)行文件只讀文件只讀文件讀寫文件讀寫文件 文件分類n文件存取：用戶在使用文件時(shí)按何種次序存取文件。文件存取：用戶在使用文件時(shí)按何種次序存取文件。順序訪問：按從前到后的順序?qū)ξ募M(jìn)行讀寫操作。順序訪問：按從前到后的順序?qū)ξ募M(jìn)行讀寫操作。如磁帶。如磁帶。隨機(jī)訪問：也稱直接訪問?？梢园慈我?/p>

9、的次序?qū)ξ募S機(jī)訪問：也稱直接訪問。可以按任意的次序?qū)ξ募M(jìn)行讀寫操作。如磁盤。進(jìn)行讀寫操作。如磁盤。索引訪問：也稱按鍵訪問，這種方式對文件中的記錄索引訪問：也稱按鍵訪問，這種方式對文件中的記錄按某個(gè)數(shù)據(jù)項(xiàng)的值來排列，從而可以根據(jù)鍵值來快速按某個(gè)數(shù)據(jù)項(xiàng)的值來排列，從而可以根據(jù)鍵值來快速存取。如索引表很長，則可以將索引表再加以索引，存取。如索引表很長，則可以將索引表再加以索引，以形成具有層次結(jié)構(gòu)的多級索引。以形成具有層次結(jié)構(gòu)的多級索引。文件存取文件存取n文件操作：文件系統(tǒng)向用戶提供的各種調(diào)用接口。文件操作：文件系統(tǒng)向用戶提供的各種調(diào)用接口。（1 1）創(chuàng)建文件）創(chuàng)建文件為文件分配必要的外存空間為文

10、件分配必要的外存空間為文件建立目錄項(xiàng)，里面記錄了新文件的文件名和在外存的為文件建立目錄項(xiàng)，里面記錄了新文件的文件名和在外存的地址地址（2 2）刪除文件）刪除文件系統(tǒng)從目錄中找到要?jiǎng)h除文件的目錄項(xiàng)，并置空該目錄項(xiàng)。系統(tǒng)從目錄中找到要?jiǎng)h除文件的目錄項(xiàng)，并置空該目錄項(xiàng)。回收該文件所占有的存儲空間回收該文件所占有的存儲空間 （3 3）讀文件）讀文件在系統(tǒng)調(diào)用中給出文件名和應(yīng)讀入的內(nèi)存目標(biāo)地址在系統(tǒng)調(diào)用中給出文件名和應(yīng)讀入的內(nèi)存目標(biāo)地址系統(tǒng)查找目錄，找到指定的目錄項(xiàng)，從中得到文件在外存中系統(tǒng)查找目錄，找到指定的目錄項(xiàng)，從中得到文件在外存中的位置的位置通過讀指針，將外存中的數(shù)據(jù)讀到內(nèi)存緩沖區(qū)通過讀指針，將

11、外存中的數(shù)據(jù)讀到內(nèi)存緩沖區(qū)文件的操作（4 4）寫文件）寫文件在系統(tǒng)調(diào)用中給出文件名及文件在內(nèi)存中的源地址在系統(tǒng)調(diào)用中給出文件名及文件在內(nèi)存中的源地址系統(tǒng)查找目錄，找到指定的目錄項(xiàng)系統(tǒng)查找目錄，找到指定的目錄項(xiàng)通過寫指針，將內(nèi)存緩沖區(qū)中的數(shù)據(jù)寫到外存的文件中通過寫指針，將內(nèi)存緩沖區(qū)中的數(shù)據(jù)寫到外存的文件中（5 5）截?cái)辔募┙財(cái)辔募?如果一個(gè)文件的內(nèi)容已經(jīng)陳舊而需要全部更新，但文件名和文件屬如果一個(gè)文件的內(nèi)容已經(jīng)陳舊而需要全部更新，但文件名和文件屬性并沒有發(fā)生變化時(shí)，可以截?cái)辔募?，即將原來文件的長度置為性并沒有發(fā)生變化時(shí)，可以截?cái)辔募磳⒃瓉砦募拈L度置為0 0（6 6）設(shè)置文件的讀）設(shè)置文件

12、的讀/ /寫位置寫位置指用于設(shè)置文件讀指用于設(shè)置文件讀/ /寫指針的位置，這樣，每次讀寫指針的位置，這樣，每次讀/ /寫文件時(shí)，不是寫文件時(shí)，不是從文件的始端而是從所設(shè)置的位置開始操作，為文件提供隨機(jī)存取從文件的始端而是從所設(shè)置的位置開始操作，為文件提供隨機(jī)存取的能力。的能力。（7 7）打開文件）打開文件系統(tǒng)將指名文件的屬性從外存拷貝到內(nèi)存打開文件的一個(gè)表目中，系統(tǒng)將指名文件的屬性從外存拷貝到內(nèi)存打開文件的一個(gè)表目中，并將該表目的編號返回給用戶并將該表目的編號返回給用戶（8 8）關(guān)閉文件）關(guān)閉文件文件從打開文件表目中被刪除掉文件從打開文件表目中被刪除掉 文件的操作n文件結(jié)構(gòu)：文件的組織形式，它

13、影響對文件的檢索速文件結(jié)構(gòu)：文件的組織形式，它影響對文件的檢索速度。度。n文件系統(tǒng)的設(shè)計(jì)者一般從兩種不同的觀點(diǎn)去研究文件文件系統(tǒng)的設(shè)計(jì)者一般從兩種不同的觀點(diǎn)去研究文件的結(jié)構(gòu)：一種是從用戶使用角度去研究；的結(jié)構(gòu)：一種是從用戶使用角度去研究；另一種是從另一種是從系統(tǒng)實(shí)現(xiàn)的角度去研究。系統(tǒng)實(shí)現(xiàn)的角度去研究。文件的邏輯結(jié)構(gòu)：這是從用戶的觀點(diǎn)出發(fā)所觀察到的文件的邏輯結(jié)構(gòu)：這是從用戶的觀點(diǎn)出發(fā)所觀察到的文件組織形式，是用戶可以直接處理的數(shù)據(jù)及其結(jié)構(gòu)，文件組織形式，是用戶可以直接處理的數(shù)據(jù)及其結(jié)構(gòu)，它獨(dú)立于文件的物理特性。它獨(dú)立于文件的物理特性。文件的物理結(jié)構(gòu)：即文件的存儲結(jié)構(gòu)。指文件在外存文件的物理結(jié)構(gòu)：

14、即文件的存儲結(jié)構(gòu)。指文件在外存上的存儲組織形式。文件的物理結(jié)構(gòu)和存儲介質(zhì)的存上的存儲組織形式。文件的物理結(jié)構(gòu)和存儲介質(zhì)的存儲性能以及所采用的外存分配方式有關(guān)。儲性能以及所采用的外存分配方式有關(guān)。 文件的結(jié)構(gòu)文件的結(jié)構(gòu)2、文件系統(tǒng)、文件系統(tǒng)n文件系統(tǒng)定義文件系統(tǒng)定義: 操作系統(tǒng)中與管理文件有關(guān)的軟件和數(shù)據(jù)操作系統(tǒng)中與管理文件有關(guān)的軟件和數(shù)據(jù)稱為文件系統(tǒng)。它負(fù)責(zé)為用戶建立文件，撤銷、讀寫、修稱為文件系統(tǒng)。它負(fù)責(zé)為用戶建立文件，撤銷、讀寫、修改和復(fù)制文件，方便用戶按名存取，實(shí)現(xiàn)文件的共享和保改和復(fù)制文件，方便用戶按名存取，實(shí)現(xiàn)文件的共享和保護(hù)。護(hù)。n文件系統(tǒng)的層次模型文件系統(tǒng)的層次模型該模型由許多不

15、同層構(gòu)成該模型由許多不同層構(gòu)成每一層都會使用下一層的功能特性來創(chuàng)建新的功能，每一層都會使用下一層的功能特性來創(chuàng)建新的功能，為上一層服務(wù)。為上一層服務(wù)。文件系統(tǒng)基本基本I/O控制層：由設(shè)備驅(qū)動控制層：由設(shè)備驅(qū)動程序和程序和I/O處理程序組成，負(fù)處理程序組成，負(fù)責(zé)啟動該設(shè)備上的責(zé)啟動該設(shè)備上的I/O操作，操作，處理處理I/O請求的完成。請求的完成?；疚募到y(tǒng)層：該層處理基本文件系統(tǒng)層：該層處理在磁盤間和磁帶系統(tǒng)間交換在磁盤間和磁帶系統(tǒng)間交換的數(shù)據(jù)塊，關(guān)注數(shù)據(jù)塊在磁的數(shù)據(jù)塊，關(guān)注數(shù)據(jù)塊在磁盤中的位置。盤中的位置。文件組織模塊層：負(fù)責(zé)所有文件組織模塊層：負(fù)責(zé)所有文件文件I/O的初始和終止的初始和終止

16、邏輯文件系統(tǒng)層：使用戶和邏輯文件系統(tǒng)層：使用戶和應(yīng)用程序能夠訪問到記錄應(yīng)用程序能夠訪問到記錄文件系統(tǒng)接口文件系統(tǒng)接口邏輯文件系統(tǒng)層邏輯文件系統(tǒng)層文件組織模塊層文件組織模塊層基本文件系統(tǒng)層基本文件系統(tǒng)層基本基本I/O控制層控制層物理磁盤物理磁盤文件系統(tǒng)層次模型文件系統(tǒng)層次模型文件系統(tǒng)的層次模型文件管理的要素文件管理的要素文件結(jié)構(gòu)文件結(jié)構(gòu)目錄管理目錄管理操作，操作，文件名文件名用戶訪問控制用戶訪問控制用戶用戶和程和程序命序命令令訪問方法訪問方法文件操文件操作函數(shù)作函數(shù)記錄記錄組塊組塊主存緩沖區(qū)主存緩沖區(qū)中的物理塊中的物理塊磁盤中的磁盤中的物理塊物理塊磁盤磁盤調(diào)度調(diào)度I/O文件文件分配分配空閑空閑空

17、間空間管理管理文件管理關(guān)注的問題文件管理關(guān)注的問題操作系統(tǒng)關(guān)注的問題操作系統(tǒng)關(guān)注的問題6.2 6.2 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)n文件邏輯結(jié)構(gòu)的基本要求文件邏輯結(jié)構(gòu)的基本要求能提高檢索速度：文件由大批記錄組成，對于能提高檢索速度：文件由大批記錄組成，對于記錄的組織應(yīng)有利于提高記錄檢索的速度。記錄的組織應(yīng)有利于提高記錄檢索的速度。便于修改：便于在文件中增加、修改、刪除一便于修改：便于在文件中增加、修改、刪除一條記錄條記錄降低文件的存儲費(fèi)用：即減少文件存儲占用的降低文件的存儲費(fèi)用：即減少文件存儲占用的存儲空間。存儲空間。n無結(jié)構(gòu)的字節(jié)流式文件 這類文件是由先后到達(dá)的相關(guān)字節(jié)組成，文件內(nèi)的信息不再

18、劃分結(jié)構(gòu)。如各種程序、文本文件等。n有結(jié)構(gòu)的記錄式文件 這類文件由若干個(gè)記錄組成。 記錄又分成定長記錄和變長記錄兩種。 定長記錄指文件中所有記錄的長度都是相同的。 變長記錄指文件中各記錄的長度不相同。文件邏輯結(jié)構(gòu)的類型文件邏輯結(jié)構(gòu)的類型記錄式文件中記錄的組織記錄式文件中記錄的組織n順序文件：由一系列記錄按某種順序(可以是按文件的創(chuàng)建時(shí)間或按關(guān)鍵字排序)排列所形成的文件。其中的記錄可以是定長記錄，也可以是變長記錄。R0R1R2R3RiLLLLLL2L3L4LL(i 1)LRptr(a) 定長記錄文件L0R0L1R1RiWptr(b) 變 長記錄文件Li00L0L0 1L1L0 L1 2Li(Lk

19、 1)i1k0(Lk 1)ik0定長和變長記錄文件定長和變長記錄文件n要讀或?qū)懸淮笈涗洉r(shí)，對順序文件的存取效率是所有邏輯文件中最高的，因此順序文件通常用于批處理應(yīng)用中；n此外，也只有順序文件才能存儲在磁帶上， 并能有效地工作。n在交互應(yīng)用的場合，如果用戶(程序)要求查找或修改單個(gè)記錄，為此系統(tǒng)便要去逐個(gè)地查找諸記錄。順序文件所表現(xiàn)出來的性能就可能很差， 尤其是當(dāng)文件較大時(shí)， 情況更為嚴(yán)重。順序文件的優(yōu)缺點(diǎn)順序文件的優(yōu)缺點(diǎn)索引文件（2）索引文件：系統(tǒng)中建立一張索引表，在表中為每個(gè)記）索引文件：系統(tǒng)中建立一張索引表，在表中為每個(gè)記錄設(shè)置一個(gè)表項(xiàng)，以加快對記錄的檢索速度。錄設(shè)置一個(gè)表項(xiàng)，以加快對記

20、錄的檢索速度。索引號0長度 m指針 ptrm01m1imi索引表R0R1Ri邏輯文件索引號0長度 m指針 ptrm01m1imi索引表R0R1Ri邏輯文件索引文件的組織索引文件的組織索引順序文件（3）索引順序文件：將順序文件中的所有記錄分成若干個(gè)）索引順序文件：將順序文件中的所有記錄分成若干個(gè)組；為順序文件建立一張索引表，在索引表中為每組中的組；為順序文件建立一張索引表，在索引表中為每組中的第一個(gè)記錄建立一個(gè)索引項(xiàng)，其中含有該記錄的鍵值和指第一個(gè)記錄建立一個(gè)索引項(xiàng)，其中含有該記錄的鍵值和指向該記錄的指針。向該記錄的指針。 鍵An QiBao RongChen Lin邏輯地址姓 名An QiAn

21、 Kang其它屬性Bao Rong邏輯文件索引順序文件索引順序文件 操作系統(tǒng)不了解也不關(guān)心文件的組織形式和內(nèi)容，它所操作系統(tǒng)不了解也不關(guān)心文件的組織形式和內(nèi)容，它所“看到的看到的”都是字節(jié)流。文件信息的實(shí)際意義是由用戶級都是字節(jié)流。文件信息的實(shí)際意義是由用戶級程序強(qiáng)加和關(guān)心的。程序強(qiáng)加和關(guān)心的。 6.3 6.3 外存分配方式外存分配方式n目前常用的外存分配方法有：連續(xù)分配、鏈接分配和索引目前常用的外存分配方法有：連續(xù)分配、鏈接分配和索引分配三種。分配三種。n通常，一個(gè)系統(tǒng)中，僅采用其中的一種方法來為文件分配通常，一個(gè)系統(tǒng)中，僅采用其中的一種方法來為文件分配外存空間。外存空間。n文件存儲器的存儲

22、空間，通常劃分成若干個(gè)大小相等的塊文件存儲器的存儲空間，通常劃分成若干個(gè)大小相等的塊(例如例如512個(gè)字節(jié)為一塊個(gè)字節(jié)為一塊)，叫物理塊。，叫物理塊。n在文件存儲器上的文件稱為物理文件，在文件存儲器上的文件稱為物理文件，n 存放文件記錄的物理塊叫物理記錄。存放文件記錄的物理塊叫物理記錄。 1、 連續(xù)分配連續(xù)分配 最簡單的物理結(jié)構(gòu)，它是把邏輯上連續(xù)的信息文件存貯在最簡單的物理結(jié)構(gòu)，它是把邏輯上連續(xù)的信息文件存貯在連續(xù)的物理塊中的一種組織方式。連續(xù)的物理塊中的一種組織方式。 連續(xù)分配n 最簡單的物理結(jié)構(gòu)，它是把邏輯上連續(xù)的信息文件存貯在連續(xù)的物理塊中的一種組織方式。 123056749101181

23、3141512171819162122232025262724list29303128m ailcountfilestartlengthcount02tr143mail196list284f62目 錄trf 優(yōu)點(diǎn)：（1） 管理簡單 只要記住文件所在的第一塊位置及文件包括的塊數(shù)即可；（2） 存取速度快 只要訪問一次文件的管理信息，就可方便地存取到任一記錄。缺點(diǎn)：（1） 不靈活 要求在文件創(chuàng)建時(shí)，就給出文件的最大長度，不利于文件的動態(tài)修改；（2） 產(chǎn)生碎片 連續(xù)分配n把邏輯上連續(xù)的信息文件存貯在不連續(xù)的物理塊中。n根據(jù)指針?biāo)诘奈恢貌煌譃殡[式鏈接和顯式鏈接兩種。（1）隱式鏈接 存放信息的物理塊

24、中設(shè)有一個(gè)指向下一個(gè)物理塊指針。文件各塊通過鏈指針鏈在一起。 鏈接分配隱式鏈接25123056749101181314151217181916212223202526272429303128filestartendjeep925目 錄101-116n 存放信息的物理塊中設(shè)有一個(gè)指向下一個(gè)物理塊指針。文件各塊通過鏈指針鏈在一起。 優(yōu)點(diǎn)：（1）提高了磁盤空間利用率,不存在碎片問題（2）有利于文件的動態(tài)修改缺點(diǎn)： 只能順序存取。 隱式鏈接n為了實(shí)現(xiàn)隨機(jī)存取，可以把指針字從文件的各物理塊中取出，放在一個(gè)表中，此表叫文件分配表FAT(File Allocation Table)。n系統(tǒng)工作時(shí)，文件分配表

25、被讀到主存。n存取任一記錄時(shí)在主存沿鏈查找，很快能定位文件中任一個(gè)記錄的位置。顯示鏈接012345物 理 塊 號2FCBFAT0451顯示鏈接6EOF11105EOF0123456789FATFCB A4FCB B9MS-DOS的文件物理結(jié)構(gòu)的文件物理結(jié)構(gòu)顯示鏈接這個(gè)方法的主要缺點(diǎn)這個(gè)方法的主要缺點(diǎn): 在系統(tǒng)工作期間，整個(gè)表必須在主存。占用內(nèi)存太多。在系統(tǒng)工作期間，整個(gè)表必須在主存。占用內(nèi)存太多。 以以100G磁盤為例，若每塊按磁盤為例，若每塊按512個(gè)字節(jié)計(jì)，則這個(gè)表個(gè)字節(jié)計(jì)，則這個(gè)表將占用將占用200M項(xiàng)。每項(xiàng)至少占用項(xiàng)。每項(xiàng)至少占用4個(gè)字節(jié)。因此，這個(gè)表要個(gè)字節(jié)。因此，這個(gè)表要占用占用8

26、00M字節(jié)的主存。字節(jié)的主存。 為了節(jié)省主存，盤文件映射（分配）表必須作為一個(gè)為了節(jié)省主存，盤文件映射（分配）表必須作為一個(gè)文件放在磁盤上。并要求存放該文件的各個(gè)盤塊不要過于文件放在磁盤上。并要求存放該文件的各個(gè)盤塊不要過于分散。否則，可能要讀取多個(gè)存放盤文件映射表的物理塊，分散。否則，可能要讀取多個(gè)存放盤文件映射表的物理塊，才能找到它們之間的對應(yīng)關(guān)系，從而減少了它的優(yōu)越性。才能找到它們之間的對應(yīng)關(guān)系，從而減少了它的優(yōu)越性。顯示鏈接n鏈接分配方式雖然解決了連續(xù)分配方式所存在的問題， 但又出現(xiàn)了另外兩個(gè)問題， 即： （1） 不能支持高效的直接存取。要對一個(gè)較大的文件進(jìn)行直接存取，須首先在FAT中

27、順序地查找許多盤塊號。 （2）FAT需占用較大的內(nèi)存空間。 n為了實(shí)現(xiàn)文件的隨機(jī)存取，在文件目錄表中為每個(gè)文件保留一個(gè)索引表塊號，該索引塊指出文件的邏輯塊與物理塊的映射關(guān)系。n現(xiàn)代操作系統(tǒng)幾乎都提供索引結(jié)構(gòu)索引分配123056749101181314151217181916212223202526272429303128countfile塊 序 號jeep19目 錄91611025 1 1 119索引分配方式索引分配方式單級索引分配單級索引分配01210510625435635798510510625474035635711259853607401125主索引360第二級索引磁盤空間多級索引分

28、配多級索引分配modeowners (2)time stamps (3)sizeblock counti.addr (0)i.addr (1)direct blockssingle indirectdouble indirecttriple indirectdatadatadatadatadatadatadatadatadatadata混合索引分配混合索引分配（1）允許文件動態(tài)修改，增加了使用的靈活性；（2）可直接對文件進(jìn)行存取。 缺點(diǎn)：（1）索引表要占用額外空間；（2）降低了文件的存取速度(至少需要訪問存貯器二次：一次訪問索引表，一次訪問文件信息)。 索引結(jié)構(gòu)文件的優(yōu)點(diǎn)索引結(jié)構(gòu)文件的優(yōu)點(diǎn) 文

29、件的存貯介質(zhì)是指存儲文件信息的材料。它們是以塊為單位進(jìn)行信息的存儲、傳輸。常用的存貯介質(zhì)有磁帶磁盤和光盤。其特點(diǎn)如下表所示：存儲介質(zhì)存儲介質(zhì)物理結(jié)構(gòu)物理結(jié)構(gòu)存取方式存取方式磁帶磁帶連續(xù)結(jié)構(gòu)連續(xù)結(jié)構(gòu)順序存取順序存取磁盤和光盤磁盤和光盤連續(xù)連續(xù)鏈接鏈接索引索引順序順序順序順序順序順序 隨機(jī)隨機(jī)6.4 6.4 目錄管理目錄管理 n目錄管理要實(shí)現(xiàn)的功能：目錄管理要實(shí)現(xiàn)的功能：實(shí)現(xiàn)實(shí)現(xiàn)“按名存取按名存取” ” 提高對目錄的檢索速度提高對目錄的檢索速度文件共享文件共享允許文件重名允許文件重名對目錄管理的要求n文件控制塊：文件控制塊：用于描述和控制文件的數(shù)據(jù)結(jié)構(gòu)用于描述和控制文件的數(shù)據(jù)結(jié)構(gòu)文件管理者可以借助

30、文件控制塊中的信息，對文件施以各種文件管理者可以借助文件控制塊中的信息，對文件施以各種操作操作文件與文件控制塊一一對應(yīng)文件與文件控制塊一一對應(yīng)文件控制塊的有序集合稱為文件目錄，即一個(gè)文件控制塊就文件控制塊的有序集合稱為文件目錄，即一個(gè)文件控制塊就是一個(gè)文件目錄項(xiàng)是一個(gè)文件目錄項(xiàng)文件控制塊是文件存在的唯一標(biāo)志文件控制塊是文件存在的唯一標(biāo)志文件控制塊（FCB） 文件控制塊中，包含文件的一些信息，這些信息被分成以文件控制塊中，包含文件的一些信息，這些信息被分成以下四類下四類n基本信息基本信息文件名：由文件的創(chuàng)建者選擇的名，在一個(gè)特定的目錄中具文件名：由文件的創(chuàng)建者選擇的名，在一個(gè)特定的目錄中具有唯一

31、性有唯一性文件類型：例如文本文件、二進(jìn)制文件等文件類型：例如文本文件、二進(jìn)制文件等文件組織：系統(tǒng)所支持的不同組織形式文件組織：系統(tǒng)所支持的不同組織形式n地址信息地址信息起始地址：文件存放在外存的物理地址起始地址：文件存放在外存的物理地址已使用大?。何募拇笮∫咽褂么笮。何募拇笮》峙浯笮。何募淖畲箝L度分配大?。何募淖畲箝L度文件控制塊n存取控制信息存取控制信息文件主：擁有文件的控制權(quán)文件主：擁有文件的控制權(quán)訪問控制：可包括有權(quán)限用戶的用戶名和口令訪問控制：可包括有權(quán)限用戶的用戶名和口令允許的操作：控制讀、寫、執(zhí)行等權(quán)限允許的操作：控制讀、寫、執(zhí)行等權(quán)限n使用信息使用信息創(chuàng)建日期：文件首次存放

32、在目錄中的時(shí)間創(chuàng)建日期：文件首次存放在目錄中的時(shí)間讀時(shí)間：最后一次讀文件記錄的時(shí)間讀時(shí)間：最后一次讀文件記錄的時(shí)間修改時(shí)間：最后一次更新、插入或刪除記錄的時(shí)間修改時(shí)間：最后一次更新、插入或刪除記錄的時(shí)間備份時(shí)間：文件最后一次備份到其它存儲介質(zhì)的時(shí)間備份時(shí)間：文件最后一次備份到其它存儲介質(zhì)的時(shí)間文件控制塊n目錄文件：目錄文件：為了加快對文件的檢索，往往將文件控制塊集中為了加快對文件的檢索，往往將文件控制塊集中在一起進(jìn)行管理。這種文件控制塊的有序集合就在一起進(jìn)行管理。這種文件控制塊的有序集合就叫文件目錄。叫文件目錄。文件控制塊就是其中的目錄項(xiàng)文件控制塊就是其中的目錄項(xiàng) 文件目錄具有將文件名轉(zhuǎn)換成該

33、文件在外存的物文件目錄具有將文件名轉(zhuǎn)換成該文件在外存的物理地址的功能，它實(shí)現(xiàn)文件名和存放盤塊之間的理地址的功能，它實(shí)現(xiàn)文件名和存放盤塊之間的映射映射目錄文件的概念n為了檢索目錄的方便，把文件名和文件其它信息分開存放。使文件其它信息單獨(dú)成為一個(gè)數(shù)據(jù)結(jié)構(gòu)，我們把這種用于存放文件描述信息的數(shù)據(jù)結(jié)構(gòu)稱為索引結(jié)點(diǎn)，簡稱i結(jié)點(diǎn)。n文件目錄中的每個(gè)目錄項(xiàng)，僅由文件名和指向該文件所對應(yīng)的i結(jié)點(diǎn)的指針構(gòu)成。 索引結(jié)點(diǎn)（i結(jié)點(diǎn)）目錄文件n搜索目錄n創(chuàng)建目錄n刪除目錄n顯示目錄n修改目錄常用的文件目錄組織形式：n單級目錄結(jié)構(gòu)n兩級目錄結(jié)構(gòu)n多級樹形目錄結(jié)構(gòu)目錄結(jié)構(gòu)目錄結(jié)構(gòu)n文件存儲器上保存的全部文件建立一張目錄表，

34、每個(gè)文件在表中占有一項(xiàng)。單級目錄單級目錄單級目錄結(jié)構(gòu)單級目錄結(jié)構(gòu)目錄項(xiàng)1目錄項(xiàng)2目錄項(xiàng)3目錄項(xiàng)n文件1文件2文件3文件n目錄管理（續(xù)）目錄管理（續(xù)） 文件目錄的目錄項(xiàng)包含如下一些信息：文件目錄的目錄項(xiàng)包含如下一些信息：n文件名：由創(chuàng)建者給出的文件名：由創(chuàng)建者給出的1n個(gè)字符個(gè)字符n文件類型：由文件擴(kuò)展名給出，例如：文件類型：由文件擴(kuò)展名給出，例如：.OBJ, EXE,BAS,C，PAS，ADA，n文件組織形式：連續(xù)、鏈接、或索引式文件組織形式：連續(xù)、鏈接、或索引式n文件的物理地址、文件大小、存取權(quán)限文件的物理地址、文件大小、存取權(quán)限n文件的擁有者：文件的擁有者：n文件的創(chuàng)建、修改和訪問日期等等

35、。文件的創(chuàng)建、修改和訪問日期等等。 單級目錄結(jié)構(gòu)n基本操作基本操作建立一個(gè)新文件時(shí)，在目錄表中增加一個(gè)新目錄項(xiàng)建立一個(gè)新文件時(shí)，在目錄表中增加一個(gè)新目錄項(xiàng)撤消一個(gè)文件時(shí)，刪除該文件所對應(yīng)的目錄項(xiàng)撤消一個(gè)文件時(shí)，刪除該文件所對應(yīng)的目錄項(xiàng)訪問某個(gè)文件時(shí)，按文件名順序查找目錄，從而找訪問某個(gè)文件時(shí)，按文件名順序查找目錄，從而找 到對應(yīng)到對應(yīng)文件的目錄項(xiàng)文件的目錄項(xiàng)n優(yōu)點(diǎn)優(yōu)點(diǎn)實(shí)現(xiàn)了按名存取實(shí)現(xiàn)了按名存取目錄結(jié)構(gòu)管理簡單，它主要用于單用戶操作系統(tǒng)目錄結(jié)構(gòu)管理簡單，它主要用于單用戶操作系統(tǒng)n缺點(diǎn)缺點(diǎn)文件多時(shí)，目錄檢索時(shí)間長文件多時(shí)，目錄檢索時(shí)間長 不允許文件重名不允許文件重名不便于實(shí)現(xiàn)文件的共享不便于實(shí)現(xiàn)

36、文件的共享n解決文件重名的一個(gè)辦法是采用兩級目錄結(jié)構(gòu)。它由一個(gè)主文件目錄和若干個(gè)用戶文件目錄組成。n主文件目錄中，每個(gè)用戶目錄文件都占有一個(gè)目錄項(xiàng)，包括用戶名和指向該用戶目錄文件的指針。n二級目錄中，用戶可以建立自己的文件目錄。兩級目錄結(jié)構(gòu)用戶名用戶名WangZhangGao指向子目錄指針指向子目錄指針Wang的用戶目錄的用戶目錄AlphaTestAlphaTestReportTestZhang的用戶目錄的用戶目錄ReportTestGao的用戶目錄的用戶目錄BetaDeviceMisxBetaDeviceMisx兩級目錄結(jié)構(gòu)兩級目錄結(jié)構(gòu) 主目錄主目錄兩級目錄結(jié)構(gòu)n基本操作基本操作當(dāng)一個(gè)新用戶

37、開始使用文件系統(tǒng)時(shí)，系統(tǒng)為其在主文件目錄當(dāng)一個(gè)新用戶開始使用文件系統(tǒng)時(shí)，系統(tǒng)為其在主文件目錄表中找一個(gè)空表目，并為其分配一個(gè)存放用戶文件目錄的區(qū)表中找一個(gè)空表目，并為其分配一個(gè)存放用戶文件目錄的區(qū)域，然后把用戶名和該區(qū)域的起始地址填寫在該對應(yīng)表目中。域，然后把用戶名和該區(qū)域的起始地址填寫在該對應(yīng)表目中。用戶建立一個(gè)新文件時(shí)，文件系統(tǒng)先按用戶名在主目錄中找用戶建立一個(gè)新文件時(shí)，文件系統(tǒng)先按用戶名在主目錄中找到他的文件目錄的地址，然后在用戶目錄表中為其建立一個(gè)到他的文件目錄的地址，然后在用戶目錄表中為其建立一個(gè)目錄項(xiàng)，填上文件名以及文件的管理和控制信息。目錄項(xiàng)，填上文件名以及文件的管理和控制信息。

38、用戶要訪問他的一個(gè)文件時(shí)，先按用戶名在主目錄中找到他用戶要訪問他的一個(gè)文件時(shí)，先按用戶名在主目錄中找到他的文件目錄位置，然后按文件名在用戶文件目錄中找到文件的文件目錄位置，然后按文件名在用戶文件目錄中找到文件的有關(guān)信息，最后完成指定的文件操作。的有關(guān)信息，最后完成指定的文件操作。用戶要撤消一個(gè)文件時(shí)，先按用戶名在主目錄中找到他的文用戶要撤消一個(gè)文件時(shí)，先按用戶名在主目錄中找到他的文件目錄位置，然后按文件名在用戶文件目錄中找到文件的目件目錄位置，然后按文件名在用戶文件目錄中找到文件的目錄項(xiàng)，釋放文件所占用的塊并撤消該目錄項(xiàng)。當(dāng)系統(tǒng)要撤消錄項(xiàng)，釋放文件所占用的塊并撤消該目錄項(xiàng)。當(dāng)系統(tǒng)要撤消該用戶時(shí)

39、，系統(tǒng)將該用戶在主目錄表中的目錄項(xiàng)撤消。該用戶時(shí)，系統(tǒng)將該用戶在主目錄表中的目錄項(xiàng)撤消。 兩級目錄結(jié)構(gòu)n兩級目錄結(jié)構(gòu)的優(yōu)點(diǎn)：兩級目錄結(jié)構(gòu)的優(yōu)點(diǎn)：解決了文件的重名（用戶名解決了文件的重名（用戶名| |文件名）問題和文件共享問題；文件名）問題和文件共享問題；降低了文件查找時(shí)間。降低了文件查找時(shí)間。不同用戶可以使用不同的文件名訪問系統(tǒng)中的同一個(gè)共享文不同用戶可以使用不同的文件名訪問系統(tǒng)中的同一個(gè)共享文件。件。n缺點(diǎn)：缺點(diǎn)：增加了系統(tǒng)空間開銷。增加了系統(tǒng)空間開銷。兩級目錄結(jié)構(gòu)多級目錄結(jié)構(gòu) n現(xiàn)代操作系統(tǒng)向用戶提供現(xiàn)代操作系統(tǒng)向用戶提供了功能更強(qiáng)，更加靈活的了功能更強(qiáng)，更加靈活的目錄結(jié)構(gòu)，就是層次式的目

40、錄結(jié)構(gòu)，就是層次式的目錄結(jié)構(gòu)，也叫樹形目錄目錄結(jié)構(gòu)，也叫樹形目錄結(jié)構(gòu)。結(jié)構(gòu)。n和二級目錄類似，它有一和二級目錄類似，它有一個(gè)主目錄個(gè)主目錄(又稱根目錄又稱根目錄)，在根目錄下又有許多子目在根目錄下又有許多子目錄（樹枝節(jié)點(diǎn)）和普通文錄（樹枝節(jié)點(diǎn)）和普通文件的記錄（樹葉節(jié)點(diǎn)），件的記錄（樹葉節(jié)點(diǎn)），每個(gè)子目錄下依次也有許每個(gè)子目錄下依次也有許多子目錄或普通文件作為多子目錄或普通文件作為其目錄項(xiàng)。其目錄項(xiàng)。 ABCFED13ABD2GA4AC5671011JNK12JMK13AHF141516b1718192021a89多級目錄結(jié)構(gòu)多級目錄結(jié)構(gòu) 路徑名：也稱絕對路徑名，在樹形目錄結(jié)構(gòu)中，路徑名：也稱

41、絕對路徑名，在樹形目錄結(jié)構(gòu)中， 從根從根目錄到任何數(shù)據(jù)文件，目錄到任何數(shù)據(jù)文件， 都只有一條惟一的通路。都只有一條惟一的通路。 在在該路徑上從樹的根該路徑上從樹的根( (即主目錄即主目錄) )開始，開始， 把全部目錄文件把全部目錄文件名與數(shù)據(jù)文件名，依次地用名與數(shù)據(jù)文件名，依次地用“/”/”連接起來，連接起來， 即構(gòu)成即構(gòu)成該數(shù)據(jù)文件的路徑名該數(shù)據(jù)文件的路徑名(path name)(path name)。 系統(tǒng)中的每一個(gè)系統(tǒng)中的每一個(gè)文件都有惟一的路徑名。如：文件都有惟一的路徑名。如：A/A/C/11A/A/C/11當(dāng)前目錄：用戶根據(jù)自己的工作情況，在一段時(shí)間內(nèi)，當(dāng)前目錄：用戶根據(jù)自己的工作情

42、況，在一段時(shí)間內(nèi)，指定某一級的一個(gè)目錄作為當(dāng)前目錄。指定某一級的一個(gè)目錄作為當(dāng)前目錄。相對路徑名：從當(dāng)前目錄開始直到數(shù)據(jù)文件為止所構(gòu)相對路徑名：從當(dāng)前目錄開始直到數(shù)據(jù)文件為止所構(gòu)成的路徑名，稱為相對路徑名成的路徑名，稱為相對路徑名多級目錄結(jié)構(gòu)中的路徑 n優(yōu)點(diǎn)：優(yōu)點(diǎn)：層次結(jié)構(gòu)清晰，解決重名問題；層次結(jié)構(gòu)清晰，解決重名問題；有利于文件分類；有利于文件分類；提高文件檢索速度。提高文件檢索速度。n缺點(diǎn)：缺點(diǎn)：管理復(fù)雜管理復(fù)雜按路徑名逐層查找文件，需多次訪問磁盤，影響速度按路徑名逐層查找文件，需多次訪問磁盤，影響速度 多級目錄結(jié)構(gòu) 6.5 文件存儲空間的管理 （空閑磁盤空間的管理）n由于磁盤容量大，價(jià)格

43、便宜，計(jì)算機(jī)廣泛地采用磁盤由于磁盤容量大，價(jià)格便宜，計(jì)算機(jī)廣泛地采用磁盤作為文件的存貯器。作為文件的存貯器。n文件管理要解決的問題之一是如何為新創(chuàng)建的文件分文件管理要解決的問題之一是如何為新創(chuàng)建的文件分配存儲空間。配存儲空間。n文件存文件存儲儲器存器存儲儲空間的管理主要包括：空間的管理主要包括：為記錄存儲空間應(yīng)設(shè)置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。為記錄存儲空間應(yīng)設(shè)置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。提供對存儲空間分配和回收算法。提供對存儲空間分配和回收算法。n兩種分配方式：連續(xù)分配和離散分配兩種分配方式：連續(xù)分配和離散分配n文件存儲空間的基本分配單位是磁盤塊。文件存儲空間的基本分配單位是磁盤塊?？臻e磁盤空間的管理n空閑分區(qū)表n

44、空閑分區(qū)鏈表n位示圖n成組鏈接法空閑分區(qū)表n系統(tǒng)為外存上的所有空閑區(qū)建立一張空閑表，每個(gè)空閑區(qū)對應(yīng)一個(gè)空閑表項(xiàng)，其中包括空閑區(qū)的序號、第一個(gè)空閑盤塊號、空閑盤塊數(shù)等信息。 序號序號第一空閑盤塊號第一空閑盤塊號空閑盤塊數(shù)空閑盤塊數(shù)12429331554空閑分區(qū)表空閑分區(qū)表空閑分區(qū)表n空閑分區(qū)表適合于可變大小分區(qū)的連續(xù)分配方式n為文件分配存儲空間時(shí)，可以采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng)算法查找空閑分區(qū)。n然后將該分區(qū)分配給文件，同時(shí)修改空閑分區(qū)表，刪除相應(yīng)表項(xiàng)。n當(dāng)刪除文件釋放出空間時(shí)，系統(tǒng)回收其存儲空間，并合并相鄰空閑分區(qū)?？臻e分區(qū)表n實(shí)現(xiàn)簡單n但是，當(dāng)存儲空間中的空閑分區(qū)分布較分散

45、且數(shù)量較多時(shí)，空閑分區(qū)表將會很大，需要很大的內(nèi)存空間，會降低空閑分區(qū)表的檢索速度。n對于非連續(xù)存儲的文件，合并空閑分區(qū)的操作并非必須，反而會影響其效率。n用專門的空閑分區(qū)表登記空閑分區(qū)信息會浪費(fèi)一定的存儲空間，而且不適合登記分散且數(shù)目很多的空閑分區(qū)，不利于基于存儲塊的鏈接文件和索引文件的存儲空間分配。n可以通過指針將各個(gè)空閑分區(qū)連接起來，并記載各空閑分區(qū)大小，稱為空閑分區(qū)鏈表?？臻e分區(qū)鏈表 5 4 18 2 0 1 headn將外存中的所有空閑盤區(qū)鏈接起來，成為一個(gè)空閑鏈表 空閑盤塊鏈 ：如果將磁盤上的所有空閑空間，以盤塊為單位形成一條鏈，得到的是空閑盤塊鏈。當(dāng)為用戶文件分配存儲空間時(shí)，系統(tǒng)從

46、鏈?zhǔn)组_始，依次取下適當(dāng)數(shù)目的空閑盤塊分配給該用戶文件，當(dāng)用戶釋放存儲空間時(shí)，系統(tǒng)將回收的盤塊依次插入鏈表的末尾。空閑盤區(qū)鏈：將磁盤上的所有空閑空間，以盤區(qū)為單位形成一條鏈，得到的是空閑盤區(qū)鏈。由于組成盤區(qū)的空閑盤塊數(shù)目不定，因此鏈中的每個(gè)結(jié)點(diǎn)除有指向下一個(gè)盤區(qū)的指針之外，還要指明本結(jié)點(diǎn)的空閑盤塊數(shù)?？臻e分區(qū)鏈表n空閑分區(qū)鏈表適合于各種文件分配方法n如果基于存儲塊分配，則可以取空閑分區(qū)鏈的第一個(gè)存儲塊進(jìn)行分配，并調(diào)整空閑分區(qū)鏈?zhǔn)字羔樅头謪^(qū)大小。n如果基于可變分區(qū)分配，可以采用首次適應(yīng)算法，從鏈表頭開始查找，找到的第一個(gè)適合的分區(qū)分配。然后，調(diào)整空閑分區(qū)鏈?zhǔn)字羔樅头謪^(qū)大小。n當(dāng)刪除文件釋放存儲空間

47、時(shí)，系統(tǒng)回收其存儲空間，并將回收的分區(qū)鏈接到空閑分區(qū)鏈表中。空閑分區(qū)鏈表n一段時(shí)間后，可能會使空閑分區(qū)鏈表中包含太多小分區(qū)，使文件分配到的存儲空間過分離散。n由于空閑分區(qū)長度等信息保存在存儲塊中，每次將存儲塊分配出去寫入文件數(shù)據(jù)之前，必須首先讀出其中的有關(guān)空閑分區(qū)信息，否則將丟失鏈接指針。如果一個(gè)文件需要很多空閑分區(qū)，這種操作模式將大大降低文件存儲速度。空閑分區(qū)鏈表：問題n刪除一個(gè)由許多離散小分區(qū)組成的文件時(shí)，將回收的小分區(qū)鏈接到空閑分區(qū)鏈表中需要很長時(shí)間。n若一個(gè)文件申請連續(xù)存儲空間，則需要花費(fèi)較長的時(shí)間查找相鄰的空閑分區(qū)。n因此，這種空閑空間組織方法適合于非連續(xù)存儲文件?？臻e分區(qū)鏈表：問題

48、n位示圖使用一個(gè)位向量(二進(jìn)制中的一位)來表示磁盤中一個(gè)盤塊的使用情況。n由所有存儲塊對應(yīng)的位構(gòu)成一個(gè)向量，稱為位示圖。n具有n個(gè)磁盤塊的磁盤，其位示圖有n位。圖中為0的位對應(yīng)于空閑塊，為1的位對應(yīng)于已被占用的塊。n位示圖可以描述為一個(gè)二維數(shù)組位示圖位示圖位示圖 位示圖n盤塊的分配步驟：（1）順序掃描位示圖，從中找出一個(gè)或一組其值為0的二進(jìn)制位；（2）通過映射關(guān)系找到這些二進(jìn)制位所對應(yīng)的盤塊號；（3）修改位示圖，對應(yīng)位由0變?yōu)?。n盤塊的回收步驟（1）回收盤塊的盤塊號轉(zhuǎn)換成位示圖中的行號和列號；（2）修改位示圖，對應(yīng)位由1變?yōu)? 。位示圖n一個(gè)位示圖需要占用的存儲空間大小為： 磁盤容量（字節(jié)數(shù)

49、）/（8*數(shù)據(jù)塊大?。﹏對于較小的磁盤，位示圖占用的空間會很小。例如：一個(gè)20M的磁盤，每個(gè)盤塊為1k字節(jié)時(shí)，它要求的映象表占20k位。這個(gè)表僅占3個(gè)盤塊。 20k位/8=20*128字節(jié) 20*128字節(jié)/1k=2.5塊3塊 n但是，對于一個(gè)16GB的磁盤，若數(shù)據(jù)塊大小為512字節(jié)，則位示圖大小為4MB，大約需要占用8000個(gè)磁盤塊的存儲空間。很難一次性將該位示圖全部裝入內(nèi)存。位示圖n即使內(nèi)存足夠大，可以存放全部或絕大部分位示圖數(shù)據(jù)，搜索一個(gè)很大的位示圖將會降低文件系統(tǒng)的性能。n尤其當(dāng)磁盤空間快用完，剩下的空閑磁盤塊很少時(shí)，文件系統(tǒng)的性能將嚴(yán)重降低。位示圖成組鏈接法 n空閑表法和空閑鏈表法，都不適用于大型文件系統(tǒng)，因?yàn)檫@會使空閑表或空閑鏈表太長。n成組鏈接法是將上述兩種方法結(jié)合而形成的一種空閑盤塊管理方法，它兼顧了上述兩種方法的優(yōu)點(diǎn)而客服了兩種方法均有的表太長的缺點(diǎn)。成組鏈接法 1004003993013001003002992022012991004003992013019907999790179007899780179997901空 閑 盤 塊 號棧S.free019899n當(dāng)系統(tǒng)要為用戶分配文件所需的盤塊時(shí)，須調(diào)用盤塊分配過程來完成。n該過程首先從棧頂取出一空閑盤塊號，將與之對應(yīng)的盤塊分配給