1.文件目錄?

1.1文件目錄的內(nèi)容?

基本信息：文件名、文件類型、文件組織等；
地址信息：卷（存儲文件的設備）、起始地址，（起始物理地址）、文件長度（以字節(jié)、字或塊為單位）等。
訪問控制信息：文件所有者、訪問信息（用戶名和口令等）、合法操作等；
使用信息：創(chuàng)建時間、創(chuàng)建者身份、當前狀態(tài)、最近修改時間、最近訪問時間等。

1.2目錄內(nèi)容的組織方式及分析

目錄項：全部目錄內(nèi)容
目錄項：部分目錄信息，如文件名、文件大小、外存中的存儲位置等，其余部分保存在文件頭部。

1.3目錄文件及操作

目錄文件：多個文件的目錄項構(gòu)成的一種特殊文件。
其操作包括：搜索目錄、創(chuàng)建目錄、刪除目錄、顯示目錄、修改目錄。

1.4目錄結(jié)構(gòu)

單級目錄結(jié)構(gòu)： 所有用戶的全部文件目錄保存在一張目錄表中，每個文件的目錄項占用一個表項。 實現(xiàn)簡單，易于維護。
問題：重名問題；存放文件數(shù)量受限；當目錄文件很大時，檢索時間長；不便于實現(xiàn)文件共享。
兩級目錄結(jié)構(gòu)： 主文件目錄、用戶文件目錄 一定程度解決了重名問題，提高了文件目錄檢索效率，簡單的文件共享。
問題：不便用戶文件的邏輯分類；需要進一步解決重名、共享、檢索效率等問題。
層次目錄結(jié)構(gòu) ： 樹形目錄：

無循環(huán)圖結(jié)構(gòu)：

2.文件的邏輯組織與訪問

2.1有結(jié)構(gòu)文件與文件系統(tǒng)

大多數(shù)的文件系統(tǒng)是無結(jié)構(gòu)文件系統(tǒng)。實際應用卻需要處理各種數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)一般不依賴文件系統(tǒng)，而是由相應的應用程序提供。例如，UNIX的文件系統(tǒng)，它本身不含任何數(shù)據(jù)結(jié)構(gòu)。但是，UNIX卻能支持使用有結(jié)構(gòu)文件的應用程序，如各種基于UNIX操作系統(tǒng)的數(shù)據(jù)庫管理系統(tǒng)、電子郵件系統(tǒng)等。這類應用程序必須能定義自己的數(shù)據(jù)結(jié)構(gòu)，并能實現(xiàn)記錄與字節(jié)流之間的轉(zhuǎn)換。
一種電子郵件的格式定義：
type message = record to : array [ ] of address ; from : array [ ] of address ; subject : array [ ] of line ; cc : array [ ] of address; body : array [ ] of string ;Procedure getRecord (void) ; var msg : message ; begin msg = allocate(sizeof(message)); msg . to = getAddress(…); msg . from = getAddress(…); msg . cc = getAddress(…); msg . subject = getLine(…); msg . body = getString(…); return(msg); end. Procedure putRecord (void) ; var msg : message ; begin putAddress(msg . to); putAddress(msg . from); putAddress(msg . cc); putLine(msg . subject); putString(msg . body); end; 配置在某些大型計算機中的操作系統(tǒng)，如IBM MVS 、Macintosh的文件系統(tǒng)自身就能提供若干數(shù)據(jù)結(jié)構(gòu)。
文件系統(tǒng)直接控制管理有結(jié)構(gòu)文件，稱為有結(jié)構(gòu)文件系統(tǒng)，或高級文件系統(tǒng)。

2.2文件的組織一般原則

有利于快速訪問文件記錄。該原則適用于訪問單條記錄。若以批量方式訪問文件，該原則不太重要。
易于更新。更新文件內(nèi)容時，可能需要首先查找源數(shù)據(jù)，再進行修改。但是，對于 CD-ROM 文件，該原則這并不重要。
存儲代價小，無冗余信息。但是，有時候必須犧牲適量的存儲空間，以提高文件訪問速度。
維護簡單 ，可靠性高。

2.3有結(jié)構(gòu)文件

有結(jié)構(gòu)文件包括：堆文件、順序文件、索引順序文件、索引文件、直接（哈希）文件。 堆文件： 最簡單的文件組織方式。可以是無結(jié)構(gòu)的字節(jié)流文件，也可以是由記錄構(gòu)成的有結(jié)構(gòu)文件。組成堆文件的記錄可以有不同的字段、不同的長度。因此，嚴格地說，堆文件應該屬于無結(jié)構(gòu)文件。記錄按到達先后次序存放，最開始存入的記錄為第一條記錄，接著存入第二條記錄，第三條記錄，其余依次類推。?

有利于累計并保存大批量數(shù)據(jù)。常用于存放剛采集到的、未被處理的數(shù)據(jù)，或存儲后較少訪問的數(shù)據(jù)，或者不便于組織的數(shù)據(jù)。堆文件易于更新，因為更新數(shù)據(jù)直接追加到文件尾，無須插入到某個中間位置。但是，堆文件的記錄訪問效率極低。因此，大多數(shù)應用程序都不采用該文件類型。
順序文件： 由若干條邏輯記錄按照其關鍵字的某種順序排列而構(gòu)成的文件，是最常用的文件組織方式。每條記錄都包含固定的字段，具有相同的長度。每條記錄都包含一個特殊字段關鍵字，不同記錄的關鍵字是不同的。記錄按關鍵字排序，若關鍵字字段的類型是字符型，則按字母排序；若關鍵字字段是數(shù)值型，則按數(shù)字排序。 ?


常用于批量數(shù)據(jù)處理，這時文件的訪問效率最高。是唯一、同時適合在磁盤和磁帶中存儲的文件。訪問效率比堆文件高。當文件較小，可以將文件全部裝入內(nèi)存，利用某種快速的查找算法，如折半查找法、插值查找法等快速查找指定的記錄。
但是，訪問一個大型順序文件時，效率將會大大降低。更新效率較低。因為記錄必須插入到按關鍵字排序的某個位置，其后的各記錄必須進行物理上的位移，效率非常低。解決方法：單獨建立一個日志文件，或事務文件。新記錄首先放在日志文件中，通過周期性地執(zhí)行批量更新操作，把日志文件合并到主文件中，并按原有的關鍵字順序排列全部記錄。?
索引順序文件： 將主文件（順序文件）的所有記錄按照某種標準分組，例如，首字母相同的記錄為一組；或按每小時或某固定長度的時間將記錄分組；或者按固定條數(shù)的記錄為一組，為主文件建立一張索引表。索引表記載每一組的第一條記錄的關鍵字值和指向該記錄的指針。索引表和主文件（順序文件）一起形成索引順序文件。

向索引順序文件插入記錄：
將記錄直接插入順序文件中，效率非常低。建立備份文件。新記錄首先插入備份文件中，系統(tǒng)再周期性地批量合并主文件和備份文件。為主文件的每條記錄增加一個指針域，指向備份文件的某一條記錄，該指針域?qū)贸绦蛲该鳌２迦胄掠涗浀絺浞菸募r，修改新記錄邏輯前序記錄的指針：前序記錄可能在主文件中，可能在在備份文件中。
直接（哈希）文件
利用Hash函數(shù)，根據(jù)記錄的關鍵字計算記錄的存儲位置，并按關鍵字訪問記錄，能提高記錄的訪問效率。常用于訪問速率要求高、一次存取一條記錄且記錄為定長的文件。如文件目錄、價格表、名單等文件記錄的存取。

3.文件的物理組織—存儲空間的管理

文件存儲空間分配的有關問題：
從邏輯組織的角度看，文件由若干記錄構(gòu)成；從物理組織的角度看，文件由若干數(shù)據(jù)塊組成。操作系統(tǒng)或文件管理系統(tǒng)負責為文件分配和管理數(shù)據(jù)塊。那么，如何劃分磁盤空間？如何為一個新建文件分配空間？如何為一個已存在的文件增加存儲空間？用什么數(shù)據(jù)結(jié)構(gòu)記載文件已分配到的數(shù)據(jù)塊和空閑數(shù)據(jù)塊？

3.1預分配與動態(tài)分配

創(chuàng)建新文件時，需要分配存儲空間。一次性地為新文件分配足夠的存儲空間，這是預分配的思想。先為文件分配一部分存儲空間，以后再根據(jù)需要增加存儲空間，該方法稱為動態(tài)分配。?
要求文件創(chuàng)建時必須申明需要的最大空間。編譯程序，拷貝文件，通過網(wǎng)絡傳輸文件等，可以預先知道文件的大小；很多應用都不可能預先知道文件需要的最大空間。預先準確估計文件大小是不可能的。如果估計的空間太小，無法滿足文件的存儲需要和存儲空間的增長需要；如果估計太大，會浪費存儲空間。動態(tài)分配方法能滿足文件存儲空間的增長需要。

3.2分區(qū)大小

外存空間被分成若干大小相同的數(shù)據(jù)塊，類似于內(nèi)存空間的分頁管理技術。分區(qū) = 數(shù)據(jù)塊,該方法有利于提高外存空間的利用率，但I/O性能較低。也可以采用可變大小的分區(qū) ，此時分區(qū) = 若干連續(xù)數(shù)據(jù)塊。
與分區(qū)大小有關的因素：
文件中的數(shù)據(jù)相鄰存儲有利于提高性能；若分區(qū)太小，文件分配到的分區(qū)數(shù)目將會很多。用于管理分區(qū)（已分配和未分配的）的數(shù)據(jù)結(jié)構(gòu)如表格等將會很大，增加管理復雜度；若分區(qū)大小固定，將會簡化空間的分配和回收；若分區(qū)大小可變，或分區(qū)大小固定且較小，可以減少存儲空間的浪費。確定分區(qū)大小時，需要綜合考慮以上若干因素。
可變大小的分區(qū) vs.固定小分區(qū) ：
對于預分配方法，若采用小分區(qū)，預先分配給文件足夠數(shù)量的小分區(qū)，可能使文件分配表很大。但由于文件空間不再增加，文件分配表將保持固定大小，不會改變。若采用可變大小的連續(xù)分區(qū)模式。無須設置文件分配表，只需要記住文件存儲空間的第一個數(shù)據(jù)塊的地址和分區(qū)大小，就能定位一個文件。?

3.3文件存儲空間的分配技術

該技術可以分為連續(xù)分配和非連續(xù)分配。其中，非連續(xù)分配可以進一步分為鏈接分配和索引分配。
連續(xù)分配：
采用可變大小的連續(xù)分區(qū)、預分配技術。把邏輯文件中的數(shù)據(jù)順序地存儲到物理上鄰接的各個數(shù)據(jù)塊中，這樣形成的物理文件可以進行順序存取。優(yōu)點：簡單、容易實現(xiàn)。
文件分配表中為每個文件建立一個表項，其中記載文件的第一個數(shù)據(jù)塊地址及文件長度。對于順序文件，連續(xù)讀/寫多個數(shù)據(jù)塊內(nèi)容時，性能較好。能很快檢索文件中的一個數(shù)據(jù)塊。例如，如果一個文件的第一個數(shù)據(jù)塊的序號為x，需要檢索文件的第y塊，則該數(shù)據(jù)塊在外存中的位置為x+y-1。
連續(xù)分配存在的問題：
不利于文件尺寸的動態(tài)增長。空間利用率不高：對于需要很長時間才能完成增長的文件，預先分配的較大存儲空間也會在較長時間得不到有效利用。該分配方案可能會導致磁盤碎片，嚴重降低外存空間的利用率。解決方法之一，系統(tǒng)定期或不定期采用緊湊技術，將小分區(qū)合并為大的、連續(xù)分區(qū)，將文件占用空間合并在一起。 鏈接分配：
連續(xù)分配的文件分區(qū)太大，不利于存儲空間的有效利用。非連續(xù)分配可以將文件分區(qū)劃小，最小的文件分區(qū)基于一個數(shù)據(jù)塊。能顯著提高存儲空間的利用率。鏈接分配方法可以按基于數(shù)據(jù)塊的文件分區(qū)進行分配，為文件分配非連續(xù)的若干數(shù)據(jù)塊，數(shù)據(jù)塊之間用指針相連。
鏈接分配消除連續(xù)分配引起的外部碎片，提高了外存空間的利用率。能適應文件尺寸的動態(tài)增長。文件分配表中的目錄項也非常簡單，只需記載文件的第一個數(shù)據(jù)塊地址和文件長度。
鏈接分配適合于文件的順序存取，但對于隨機存取卻相當?shù)托АＨ绻L問文件的第i 個數(shù)據(jù)塊，必須首先從文件分配表的相應目錄項中找到該文件的第一個數(shù)據(jù)塊地址，讀出第一個數(shù)據(jù)塊中包含的第二個數(shù)據(jù)塊的指針。然后，從第二個數(shù)據(jù)塊中讀出指向第三個數(shù)據(jù)塊的指針。依次類推，直到找到第 i –1個數(shù)據(jù)塊，從中讀出指向第i 個數(shù)據(jù)塊的指針。最后，讀取第 i 個數(shù)據(jù)塊的內(nèi)容。如果一個文件包含成百上千個數(shù)據(jù)塊，則需要花費很長的時間來訪問接近鏈表尾的數(shù)據(jù)塊。大量數(shù)據(jù)塊依靠塊內(nèi)指針逐一相連，其可靠性較差。每個數(shù)據(jù)塊必須包含指針信息，這將占用額外存儲空間。?

索引分配：

索引分配能解決連續(xù)分配和鏈接分配存在的諸多問題。不需要在每個分區(qū)中花費額外存儲空間存儲鏈接指針，而是利用專門的索引結(jié)點存儲索引信息。索引分配可以基于大小固定的分區(qū)。
基于數(shù)據(jù)塊的分區(qū)能消除外部碎片，但索引項較多，可能使一個數(shù)據(jù)塊容納不了一個文件的所有分區(qū)的索引。基于可變分區(qū)的索引分配可以保證文件存儲空間的局部連續(xù)性，有利于提高文件訪問性能，減少文件的索引項。
索引分配的優(yōu)點：
支持文件的直接存取。當需要存取文件的第i號分區(qū)時，可以直接從索引表中找到第i個分區(qū)的數(shù)據(jù)塊號或可變分區(qū)的起始數(shù)據(jù)塊號。能滿足文件的動態(tài)增長需要，只需要更新索引結(jié)點的內(nèi)容，就可以把新增加的分區(qū)記錄下來。利用多級索引，可以支持大型文件的存取。?
索引分配存在的問題：
對于一些較小的文件，例如，僅需要幾個數(shù)據(jù)塊的文件，采用索引分配方案也必須為之建立一個索引表，索引節(jié)點的利用率較低。如果文件太大，建立多級索引會花費很長時間，而且需要海量存儲空間。對于一些較小的文件，例如，僅需要幾個數(shù)據(jù)塊的文件，采用索引分配方案也必須為之建立一個索引表，索引節(jié)點的利用率較低。如果文件太大，建立多級索引會花費很長時間，而且需要海量存儲空間。

總結(jié)

以上是生活随笔為你收集整理的[OS复习]文件管理2的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。