計(jì)算機(jī)操作系統(tǒng)考研輔導(dǎo)講義(第4、5章)

PAGEPAGE40四、文件管理4.1考試大綱（一）文件系統(tǒng)基礎(chǔ)1．文件概念2．文件結(jié)構(gòu)順序文件；索引文件；索引順序文件3．目錄結(jié)構(gòu)文件控制塊和索引結(jié)點(diǎn)；單級目錄結(jié)構(gòu)和兩級目錄結(jié)構(gòu)；樹形目錄結(jié)構(gòu)。4．文件共享共享動(dòng)機(jī)；共享方式；共享語義。5．文件保護(hù)訪問類型；訪問控制。（二）文件系統(tǒng)實(shí)現(xiàn)1．文件系統(tǒng)層次結(jié)構(gòu)2．目錄實(shí)現(xiàn)3．文件實(shí)現(xiàn)（三）磁盤組織與管理1．磁盤的結(jié)構(gòu)2．磁盤調(diào)度算法3．磁盤的管理4.2知識點(diǎn)歸納4.2.1文件系統(tǒng)的管理功能是通過把它所管理的程序和數(shù)據(jù)組織成一系列文件的方法來實(shí)現(xiàn)的。而文件是指具有文件名的若干相關(guān)元素的集合。元素通常是記錄，而記錄又是一組有意義的數(shù)據(jù)項(xiàng)的集合?；谖募到y(tǒng)的概念，可以把數(shù)據(jù)組成分為數(shù)據(jù)項(xiàng)、記錄和文件三級。一、文件概念1、數(shù)據(jù)項(xiàng)在文件系統(tǒng)中，數(shù)據(jù)項(xiàng)是最低級的數(shù)據(jù)組織形式，可把它分成以下兩種類型：（1）基本數(shù)據(jù)項(xiàng)。用于描述一個(gè)對象的某種屬性的字符集，是組織中可以命名的最小邏輯數(shù)據(jù)單位，即原子數(shù)據(jù)。（2）組合數(shù)據(jù)項(xiàng)。它是由若干基本數(shù)據(jù)項(xiàng)組成的。簡稱組項(xiàng)?；緮?shù)據(jù)項(xiàng)除了數(shù)據(jù)名外，還應(yīng)有數(shù)據(jù)類型。2、記錄記錄是一組相關(guān)數(shù)據(jù)項(xiàng)的集合，用于描述一個(gè)對象在某方面的屬性。一個(gè)記錄應(yīng)包含哪些數(shù)據(jù)項(xiàng)，取決于需要描述對象的哪個(gè)方面。而在諸多記錄中，為了能唯一地標(biāo)識一個(gè)記錄，必須在一個(gè)記錄的各個(gè)數(shù)據(jù)項(xiàng)中，確定出一個(gè)或幾個(gè)數(shù)據(jù)項(xiàng)，把它們的集合稱為關(guān)鍵字。3、文件文件是由創(chuàng)建者所定義的、具有文件名的一組相關(guān)元素的集合，可分為有結(jié)構(gòu)文件和無結(jié)構(gòu)文件兩種。在有結(jié)構(gòu)的文件中，文件由若干個(gè)相關(guān)記錄組成；而無結(jié)構(gòu)的文件則被看成是一個(gè)字符流。文件在文件系統(tǒng)中是一個(gè)最大的數(shù)據(jù)單位。此外，文件應(yīng)具有自己的屬性，屬性可以包括：文件類型、文件長度、文件的物理位置、文件的建立時(shí)間等。二、文件結(jié)構(gòu)文件是由一系列的記錄組成的。文件系統(tǒng)設(shè)計(jì)的關(guān)鍵要素，是將這些記錄構(gòu)成一個(gè)文件的方法，以及將一個(gè)文件存儲到外存上的方法。因此，對于任何文件都存在著以下兩種形式的結(jié)構(gòu)：文件的邏輯結(jié)構(gòu)。這是從用戶的觀點(diǎn)出發(fā)所觀察到的文件組織形式，是用戶可以直接處理的數(shù)據(jù)及其結(jié)構(gòu)，它獨(dú)立于文件的物理特性，又稱為文件組織。文件的物理結(jié)構(gòu)。又稱為文件的存儲結(jié)構(gòu)，是指文件在外存上的存儲組織形式。這不僅與存儲介質(zhì)的存儲性能有關(guān)，而且與所采用的外存分配方式有關(guān)。無論是文件的邏輯結(jié)構(gòu)，還是文件的物理結(jié)構(gòu)，都會影響對文件的檢索速度。下面介紹一下文件的邏輯結(jié)構(gòu)。對文件邏輯結(jié)構(gòu)所提出的基本要求，首先是能提高檢索速度，其次是便于修改，第三是降低文件的存儲費(fèi)用。A、文件邏輯結(jié)構(gòu)的類型文件的邏輯結(jié)構(gòu)可分為兩大類，一類是有結(jié)構(gòu)文件，是指由一個(gè)以上的記錄構(gòu)成的文件，故又把它稱為記錄式文件；其二是無結(jié)構(gòu)文件，是由字符流構(gòu)成的文件，故又稱為流式文件。（1）有結(jié)構(gòu)文件在記錄式文件中，每個(gè)記錄都用于描述實(shí)體集中的一個(gè)實(shí)體，各記錄有著相同或不同數(shù)目的數(shù)據(jù)項(xiàng)。記錄的長度可分為定長和不定長兩類。定長記錄是指文件中所有記錄的長度都是相同的，所有記錄中的各數(shù)據(jù)項(xiàng)，都處在記錄中相同的位置，具有相同的順序和長度；變長記錄是指文件中各記錄的長度不相同。產(chǎn)生變長記錄的原因，可能是由于一個(gè)記錄中所包含的數(shù)據(jù)項(xiàng)數(shù)目并不相同，也可能是數(shù)據(jù)項(xiàng)本身的長度不定，但不論哪一種，在處理前，每個(gè)記錄的長度是可知的。根據(jù)用戶和系統(tǒng)管理上的需要，可采用多種方式來組織這些記錄，形成下述的幾種文件：順序文件。是由一系列記錄按某種順序排列所形成的文件。其中的記錄通常是定長記錄，因而能用較快的速度查找文件中的記錄。索引文件。當(dāng)記錄為可變長度時(shí)，通常為之建立一張索引表，并為每個(gè)記錄設(shè)置一個(gè)表項(xiàng)，以加快對記錄的檢索速度。索引順序文件。是上述兩種文件構(gòu)成方式的結(jié)合。它為文件建立一張索引表，為每一組記錄中的第一個(gè)記錄設(shè)置一個(gè)表項(xiàng)。（2）無結(jié)構(gòu)文件大量的源程序、可執(zhí)行文件、庫函數(shù)等，所采用的就是無結(jié)構(gòu)的文件形式，即流式文件。其長度以字節(jié)為單位。對流式文件的訪問，則是采用讀寫指針來指出下一個(gè)要訪問的字符。2、順序文件（1）邏輯記錄的排序文件是記錄的集合。文件中的記錄可以是任意順序的，因此，它可以按照各種不同的順序進(jìn)行排列。可歸納為兩種情況：第一種是串結(jié)構(gòu)，各記錄之間的順序與關(guān)鍵字無關(guān)。通常的辦法是由時(shí)間來決定，即按存入時(shí)間的先后排列。第二種情況是順序結(jié)構(gòu)，指文件中的所有記錄按關(guān)鍵字排列?？梢园搓P(guān)鍵詞的長短從小到大排序，也可以從大到小排序，或按其英文字母順序排序。對順序結(jié)構(gòu)的文件可利用某種有效的查找算法，獲得更高的檢索效率。（2）順序文件的優(yōu)缺點(diǎn)順序文件的最佳應(yīng)用場合是在對諸記錄進(jìn)行批量存取時(shí)，即每次要讀或?qū)懸淮笈涗?。此時(shí)，對順序文件的存取效率是所有邏輯文件中最高的；此外，也只有順序文件才能存儲在磁帶上，并能有效地工作。在交互應(yīng)用的場合，如果用戶（程序）要求查找或修改單個(gè)記錄，為此系統(tǒng)便要去逐個(gè)地查找諸記錄。這是，順序文件所表現(xiàn)出來的性能就可能很差，尤其是當(dāng)文件較大時(shí)，情況更為嚴(yán)重。順序文件的另一個(gè)缺點(diǎn)是增加或刪除記錄比較困難。3、索引文件對于定長記錄的文件，如果要查找第i個(gè)記錄，可直接根據(jù)下式計(jì)算來獲得第i個(gè)記錄相對于第一個(gè)記錄首址的地址：Ai=i*L。然而，對于可變長度記錄的文件，要查找其第i個(gè)記錄時(shí)，需首先計(jì)算出該記錄的首地址。為此，需順序地查找每個(gè)記錄，從中獲得相應(yīng)記錄的長度Li，然后才能按下式計(jì)算出第i個(gè)記錄的首址。假定在每個(gè)記錄前用一個(gè)字節(jié)指明該記錄的長度，則Ai=，可見，對于定長記錄，除了可以方便地實(shí)現(xiàn)順序存取外，還可較方便地實(shí)現(xiàn)直接存取。然而對于變長記錄就較難實(shí)現(xiàn)直接存取。為了解決這一問題，可為變長記錄文件建立一張索引表，對主文件中的每個(gè)記錄，在索引表中設(shè)立一個(gè)相應(yīng)的表項(xiàng)，用于記錄該記錄的長度L和指向該記錄的指針（指向該記錄在邏輯地址空間中的首址）。由于索引表是按記錄鍵排序的，因此，索引表本身是一個(gè)定長記錄的順序文件，從而可以方便地實(shí)現(xiàn)直接存取。如圖4-1示出了索引文件的組織形式。索引號長度m指針ptrR00m0R11m1……Riimi……索引表邏輯文件圖4-1索引文件的組織在對索引文件進(jìn)行檢索時(shí)，首先是根據(jù)用戶提供的關(guān)鍵字，并利用折半查找法去檢索索引表，從中找到相應(yīng)的表項(xiàng)；再利用該表項(xiàng)中給出的指向記錄的指針值，去訪問所需的記錄。而每當(dāng)要向索引文件中增加一個(gè)新記錄時(shí)，便需對索引表進(jìn)行修改。由于索引文件可有較快的檢索速度，故它主要用于對信息處理的及時(shí)性要求較高的場合。使用索引文件的主要問題是，它除了有主文件外，還需配置一張索引表，而且每個(gè)記錄都要有一個(gè)索引項(xiàng)，因此提高了存儲費(fèi)用。4、索引順序文件索引順序文件可能是最常見的一種邏輯文件形式。它有效地克服了變長記錄文件不便于直接存取的缺點(diǎn)，而且所付出的代價(jià)也不算太大。它是順序文件和索引文件想結(jié)合的產(chǎn)物。將順序文件中的所有記錄分為若干個(gè)組（例如50個(gè)記錄為一組）；為順序文件建立一張索引表，在索引表中為每組中的第一個(gè)記錄建立一個(gè)索引項(xiàng)，其中含有該記錄的鍵值和指向該記錄的指針。如圖4-2所示：在對索引文件進(jìn)行檢索時(shí)，首先也是利用用戶（程序）所提供的關(guān)鍵字以及某種查找算法，去檢索索引表，找到該記錄所在記錄組中第一個(gè)記錄的表項(xiàng)，從中得到該記錄組第一個(gè)記錄在主文件中的位置；然后再利用順序查找法去查找主文件，從中找到所要求的記錄。鍵邏輯地址姓名其它屬性AnQiAnQiBaoRongAnKangChenLinBaoRong邏輯文件圖4-2索引順序文件如果在一個(gè)順序文件中所含有的記錄數(shù)為N，則為檢索到具有指定關(guān)鍵字的記錄，平均須查找個(gè)記錄；但對于索引順序文件，則為能檢索到具有指定關(guān)鍵字的記錄，平均只要查找個(gè)記錄數(shù)，因而檢索效率比順序文件約提高倍。B、文件物理結(jié)構(gòu)（外存分配方式）文件的物理結(jié)構(gòu)（文件外存分配方式）主要考慮怎樣才能有效地利用外存空間和如何提高對文件的訪問速度。1、連續(xù)分配—順序式的文件結(jié)構(gòu)如同內(nèi)存的動(dòng)態(tài)分區(qū)分配，會產(chǎn)生外存碎片，可利用緊湊方法，將碎片拼接成一大片。優(yōu)點(diǎn)：順序訪問容易，連續(xù)分配支持直接存取順序訪問速度快。缺點(diǎn)：要求有連續(xù)的存儲空間必須事先知道文件的長度2、鏈接分配：隱式鏈接和顯式鏈接優(yōu)點(diǎn)：可離散分配，解決了碎片問題缺點(diǎn)：只適合于順序訪問，對隨機(jī)訪問極其低效，不支持直接訪問，不可靠。顯式鏈接：文件分配表FAT3、索引分配單級索引、多級索引、混合索引方式三、目錄結(jié)構(gòu)在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，都要存儲大量的文件。為了能對這些文件實(shí)施有效的管理，必須對它們加以妥善組織，這主要通過文件目錄實(shí)現(xiàn)。文件目錄也是一種數(shù)據(jù)結(jié)構(gòu)，用于標(biāo)識系統(tǒng)中的文件及其物理地址，供檢索時(shí)使用。對目錄管理的要求如下：（1）實(shí)現(xiàn)“按名存取”。即用戶只需向系統(tǒng)提供所需訪問文件的名字，便能快速準(zhǔn)確地找到指定文件在外存上存儲位置。這是目錄管理中最基本的功能，也是文件系統(tǒng)向用戶提供的最基本的服務(wù)。（2）提高對目錄的檢索速度。通過合理地組織目錄結(jié)構(gòu)的方法，可加快對目錄的檢索速度，從而提高對文件的存取速度。（3）文件共享。在多用戶系統(tǒng)中，應(yīng)允許多個(gè)用戶共享一個(gè)文件。這樣就須在外存中只保留一份該文件的副本，供不同用戶使用，以節(jié)省大量的存儲空間，并方便用戶和提高文件的利用率。（4）允許文件重名。系統(tǒng)應(yīng)允許不同用戶對不同文件采用相同的名字，以便于用戶按照自己的習(xí)慣給文件命名和使用文件。1、文件控制塊和索引結(jié)點(diǎn)為了能對一個(gè)文件進(jìn)行正確的存取，必須為文件設(shè)置用于描述和控制文件的數(shù)據(jù)結(jié)構(gòu)，稱之為“文件控制塊”。文件管理程序可借助于文件控制塊中的信息，對文件施以各種操作。文件與文件控制塊一一對應(yīng)，而人們把文件控制塊的有序集合稱為文件目錄，即一個(gè)文件控制塊就是一個(gè)文件目錄項(xiàng)。通常，一個(gè)文件目錄也被看作是一個(gè)文件，稱為目錄文件。（1）文件控制塊為了能對系統(tǒng)中的大量文件施以有效地管理，在文件控制塊中，通常含有以下三類信息，即基本信息、存取控制信息及使用信息?；拘畔㈩惏ǎ何募⑽募奈锢砦恢?、文件的邏輯結(jié)構(gòu)、文件的物理結(jié)構(gòu)。存取控制信息類包括：文件主的存取權(quán)限、核準(zhǔn)用戶的存取權(quán)限以及一般用戶的存取權(quán)限。使用信息類包括文件建立的日期和時(shí)間、文件上一次修改的日期和時(shí)間及當(dāng)前使用信息。（2）索引結(jié)點(diǎn)稍加分析發(fā)現(xiàn)，在檢索目錄文件的過程中，只用到了文件名，僅當(dāng)找到一個(gè)目錄項(xiàng)（即其中的文件名與指定要查找的文件名相匹配）時(shí)，才需從該目錄項(xiàng)中讀出該文件的物理地址。而其它一些對該文件進(jìn)行描述的信息，在檢索目錄時(shí)一概不用，顯然，這些信息在檢索目錄時(shí)，不需調(diào)入內(nèi)存。為此，在有的系統(tǒng)中如UNIX系統(tǒng)，便采用了把文件名和文件描述信息分開的辦法，使文件描述信息單獨(dú)形成一個(gè)稱為索引結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)。在文件目錄中的每個(gè)目錄項(xiàng)，僅由文件名和指向該文件所對應(yīng)的索引結(jié)點(diǎn)指針?biāo)鶚?gòu)成。磁盤索引結(jié)點(diǎn)是存放在磁盤上的索引結(jié)點(diǎn)。每個(gè)文件有唯一的一個(gè)磁盤索引結(jié)點(diǎn)，它主要包括文件主標(biāo)識符、文件類型、文件存取權(quán)限、文件物理地址、文件長度、文件連接計(jì)數(shù)、文件存取時(shí)間。內(nèi)存索引結(jié)點(diǎn)是存放在內(nèi)存中的索引結(jié)點(diǎn)。當(dāng)文件被打開時(shí)，要將磁盤索引結(jié)點(diǎn)拷貝到內(nèi)存的索引結(jié)點(diǎn)中，便于以后使用。在內(nèi)存索引結(jié)點(diǎn)中又增加索引結(jié)點(diǎn)編號、狀態(tài)、訪問計(jì)數(shù)、文件所屬文件系統(tǒng)的邏輯設(shè)備號、鏈接指針等。2、單級目錄結(jié)構(gòu)這是最簡單的目錄結(jié)構(gòu)。在整個(gè)文件系統(tǒng)中只建立一張目錄表，每個(gè)文件占一個(gè)目錄項(xiàng)，目錄項(xiàng)中含文件名、文件擴(kuò)展名、文件長度、文件類型、文件物理地址以及其它文件屬性。此外，為表明每個(gè)目錄項(xiàng)是否空閑，又設(shè)置了一個(gè)狀態(tài)位。每當(dāng)要建立一個(gè)新文件時(shí)，必須先檢索所有的目錄項(xiàng)，以保證新文件名在目錄中是唯一的。然后再從目錄表中找出一個(gè)空白目錄項(xiàng)，填入新文件的文件名及其它說明信息，并置狀態(tài)位為1，刪除文件時(shí)，先從目錄中找到該文件的目錄項(xiàng)，回收該文件所占用的存儲空間，然后在清除該目錄項(xiàng)。單級目錄的優(yōu)點(diǎn)是簡單且能實(shí)現(xiàn)目錄管理的基本功能——按名存取，但卻存在下述一些缺點(diǎn)：查找速度慢；不允許重名；不便于實(shí)現(xiàn)文件共享。3、兩級目錄為了克服單級目錄所存在的缺點(diǎn)，可以為每一個(gè)用戶建立一個(gè)單獨(dú)的用戶文件目錄UFD。這些文件目錄具有相似的結(jié)構(gòu)，它由用戶所有文件的文件控制塊組成。此外，在系統(tǒng)再建立一個(gè)主文件目錄MFD；在主文件目錄中，每個(gè)用戶目錄文件都占有一個(gè)目錄項(xiàng)，其目錄項(xiàng)中包括用戶名和指向該用戶目錄文件的指針。用戶名指向子目錄的指針Wang用戶目錄WangAlphaAlphaZhangTestTestGaoZhang用戶目錄ReportReportTestTestGao用戶目錄BetaBetaDeviceDeviceMisxMisx圖4-3兩級目錄結(jié)構(gòu)在兩級目錄結(jié)構(gòu)中，如果用戶希望有自己的用戶文件目錄，可以請求系統(tǒng)為自己建立一個(gè)用戶文件目錄；如果自己不再需要UFD，也可以請求系統(tǒng)管理員將它撤消。在有了UFD后，用戶可以根據(jù)自己的需要?jiǎng)?chuàng)建新文件。每當(dāng)此時(shí)，OS只需檢查該用戶的UFD，判斷在該UFD中是否已有同名的另一個(gè)文件。若有，用戶必須為新文件重新命名；若無，便在UFD中建立一個(gè)新目錄項(xiàng)，將新文件名及其有關(guān)屬性填入目錄項(xiàng)中，并置其狀態(tài)位為“1”。當(dāng)用戶要?jiǎng)h除一個(gè)文件時(shí)，OS也只需查找該用戶的UFD，從中找出指定文件的目錄項(xiàng)，在回收該文件所占用的存儲空間后，將該目錄項(xiàng)刪除。如圖4-3所示兩級目錄結(jié)構(gòu)基本上克服了單級目錄的缺點(diǎn)，并具有以下優(yōu)點(diǎn)：提高了檢索目錄的速度；在不同的用戶目錄中，可以使用相同的文件名；不同用戶還可使用不同的文件名來訪問系統(tǒng)中同一個(gè)共享文件。4、樹形目錄結(jié)構(gòu)對于大型文件系統(tǒng)，通常采用三級或以上的目錄結(jié)構(gòu)，以提高對目錄的檢索速度和文件系統(tǒng)的性能。多級目錄結(jié)構(gòu)又稱為樹型目錄結(jié)構(gòu)，主目錄在這里被稱為根目錄，把數(shù)據(jù)文件稱為樹葉，其它的目錄均作為樹的結(jié)點(diǎn)。圖示出了樹型目錄結(jié)構(gòu)。圖中用方框代表目錄文件，圓圈代表數(shù)據(jù)文件。在該樹型目錄結(jié)構(gòu)中，根目錄中有三個(gè)用戶的總目錄項(xiàng)A、B和C。在B項(xiàng)所指出的B用戶的總目錄B中，又包括三個(gè)分目錄F、E和D，其中每個(gè)分目錄中又包含多個(gè)文件。如B目錄中的F分目錄中，包含J和N兩個(gè)文件。為了提高文件系統(tǒng)的靈活性，應(yīng)允許在一個(gè)目錄文件中的目錄項(xiàng)既是作為目錄文件的FCB，又是作為數(shù)據(jù)文件的FCB，這一信息可用目錄項(xiàng)中的一位來指示。例如，在圖中，用戶A的總目錄中，目錄項(xiàng)A是目錄文件的FCB，而目錄項(xiàng)B和D則是數(shù)據(jù)文件的FCB。如圖4-4所示：AABCGAABDFEDJNKJMKAHFAC圖4-4樹型目錄結(jié)構(gòu)5、圖形目錄結(jié)構(gòu)圖形目錄結(jié)構(gòu)是在樹形目錄結(jié)構(gòu)的基礎(chǔ)上形成的一種目錄，樹形目錄結(jié)構(gòu)要保證目錄結(jié)構(gòu)中沒有環(huán)，如果有環(huán)就會形成圖狀結(jié)構(gòu)。在圖狀結(jié)構(gòu)目錄中通過link文件實(shí)現(xiàn)文件共享；在此結(jié)構(gòu)中，實(shí)現(xiàn)目錄的遍歷和文件的刪除等操作時(shí)，可能會存在問題，相對于數(shù)形目錄，圖形目錄結(jié)構(gòu)需要一些額外的措施來解決上述問題，如采用“垃圾收集”機(jī)制來解決文件的刪除問題等。四、文件共享1、共享動(dòng)機(jī)在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，必須提供文件共享手段，即指系統(tǒng)應(yīng)允許多個(gè)用戶（進(jìn)程）共享同一份文件。這樣，在系統(tǒng)中只需保留該共享文件的一份副本。如果系統(tǒng)不能提供文件共享功能，就意味著凡是需要該文件的用戶，都需各自備有此文件的副本，顯然這會造成對存儲空間的極大浪費(fèi)。隨著計(jì)算機(jī)技術(shù)的發(fā)展，文件共享的范圍也在不斷擴(kuò)大，從單機(jī)系統(tǒng)中的共享，擴(kuò)展為多機(jī)系統(tǒng)的共享，進(jìn)而又?jǐn)U展為計(jì)算機(jī)網(wǎng)絡(luò)范圍的共享，甚至實(shí)現(xiàn)全世界的文件共享。2、共享方式（1）基于索引結(jié)點(diǎn)的共享方式在樹型結(jié)構(gòu)的目錄中，當(dāng)有兩個(gè)（或多個(gè)）用戶要共享一個(gè)子目錄或文件時(shí)，必須將共享文件或子目錄鏈接到兩個(gè)（或多個(gè)）用戶的目錄中，，才能方便地找到該文件，如圖所示。此時(shí)該文件系統(tǒng)的目錄結(jié)構(gòu)已不再是樹型結(jié)構(gòu)，而是一個(gè)有向非循環(huán)圖。如圖4-5所示：AABCBBCCCAC？BCCBC圖4-5包含有共享文件的文件系統(tǒng)如何建立B目錄與共享文件之間的鏈接呢？如果在文件目錄中包含了文件的物理地址，即文件所在盤塊的盤塊號，則在鏈接時(shí)，必須將文件的物理地址拷貝到B目錄中去。但如果以后B或C還要繼續(xù)向該文件中填加新內(nèi)容，也必然要相應(yīng)地增加新的盤塊，而這些新增加的盤塊，也只會出現(xiàn)在執(zhí)行了操作的目錄中?？梢姡@種變化對其他用戶而言，是不可見的，因而新增加的這部分內(nèi)容已不能被共享。為了解決這個(gè)問題，可以引用索引結(jié)點(diǎn)，即諸如文件的物理地址及其它的文件屬性等信息，不再是放在目錄項(xiàng)中，而是放在索引結(jié)點(diǎn)中。在文件目錄中只設(shè)置文件名及指向相應(yīng)索引結(jié)點(diǎn)的指針，如圖4-6所示。此時(shí)，由任何用戶對文件進(jìn)行的追加或修改操作，所引起的相應(yīng)結(jié)點(diǎn)內(nèi)容的改變（例如，增加了新的盤塊和文件長度等），都是其他用戶可見的，從而也就能提供給其他用戶來共享。在索引結(jié)點(diǎn)中還應(yīng)有一個(gè)鏈接計(jì)數(shù)count，用于表示鏈接到本索引結(jié)點(diǎn)上的用戶目錄項(xiàng)的數(shù)目。當(dāng)count=3時(shí)，表示有三個(gè)用戶目錄項(xiàng)連接到本文件中，或者說是有三個(gè)用戶共享此文件。當(dāng)用戶C創(chuàng)建一個(gè)新文件時(shí)，他便是該文件的所有者，此時(shí)將count置1。當(dāng)有用戶B要共享此文件時(shí)，在用戶B的目錄中增加一目錄項(xiàng)，并設(shè)置一指針指向該文件的索引結(jié)點(diǎn)，此時(shí)文件主仍然是C，count=2。如果用戶C不再需要此文件，也不能將此文件刪除。因?yàn)槿魟h除了該文件，必然刪除了該文件的索引結(jié)點(diǎn)，這樣便會使B的指針懸空，而B可能正在此文件上執(zhí)行寫操作，此時(shí)也因此半途而廢。TestrTestrTestrCount=2文件的物理地址Wang用戶文件目錄Lee用戶文件目錄索引結(jié)點(diǎn)Test圖4-6基于索引結(jié)點(diǎn)的共享方式但如果C不刪除此文件而等待B繼續(xù)使用，這樣，由于文件主是C，如果系統(tǒng)要記帳收費(fèi)，則C必須為B使用此共享文件而付帳，直至B不在需要。如圖4-7所示。owner=cowner=ccount=1C的目錄C的目錄C的目錄C的目錄owner=ccount=2owner=ccount=1鏈接前擁有者刪除文件后鏈接后圖4-7進(jìn)程B鏈接前后的情況（2）利用符號鏈實(shí)現(xiàn)文件共享為使能共享的一個(gè)文件夾，可由系統(tǒng)創(chuàng)建一個(gè)類型的新文件，也取名為，并將寫入的目錄中，以實(shí)現(xiàn)的目錄與文件的鏈接。在新文件中只包含被鏈接文件的路徑名。這樣的鏈接方法被稱為符號鏈接。新文件中的路徑名，只被看作是符號鏈，當(dāng)要訪問被鏈接的文件且正要讀類新文件時(shí)，此要求將被截獲，根據(jù)新文件中的路徑名去讀該文件，于是就實(shí)現(xiàn)了用戶對文件的共享。在利用符號鏈方式實(shí)現(xiàn)文件共享時(shí)，只是文件主才擁有指向其索引結(jié)點(diǎn)的指針；而共享該文件的其它用戶，則只有該文件的路徑名，并不擁有指向其索引結(jié)點(diǎn)的指針。這樣，這樣也就不會發(fā)生在文件主刪除一共享文件后留下一懸空指針的情況。當(dāng)文件的擁有者把一個(gè)共享文件刪除后其他用戶試圖通過符號鏈去訪問一個(gè)已被刪除的共享文件時(shí)，會因系統(tǒng)找不到該文件而使訪問失敗，于是再將符號鏈刪除，此時(shí)不會產(chǎn)生任何影響。符號鏈的共享方式也存在自己的問題：當(dāng)其它用戶去讀共享文件時(shí)，系統(tǒng)是根據(jù)給定的文件路徑名，逐個(gè)分量地去查找目錄，直到找到該文件的索引結(jié)點(diǎn)。因此，在每次訪問共享文件時(shí)，都可能要多次讀盤，這使得每次訪問文件的開銷很大，且增加了啟動(dòng)磁盤的頻率。此外，要為每個(gè)共享用戶建立一條符號鏈，由于該鏈實(shí)際上是一個(gè)文件，盡管該文件非常簡單，卻要為它配置一個(gè)索引結(jié)點(diǎn)，要耗費(fèi)一定的磁盤空間。符號鏈方式有一個(gè)很大的優(yōu)點(diǎn)，是它能夠用于鏈接世界上任何地方機(jī)器中的文件。五、文件保護(hù)在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，存放了愈來愈多的寶貴信息供用戶使用，給人們帶來了極大的好處和方便；但同時(shí)也潛在有不安全性。影響文件安全性的主要因素有：人為因素、系統(tǒng)因素、自然因素。存取控制機(jī)制是確保文件安全性的重要措施。訪問類型。我們可利用一個(gè)矩陣來描述系統(tǒng)的存取控制，并把該矩陣稱為訪問矩陣。訪問矩陣的行代表域，列代表對象，矩陣中的每一項(xiàng)是由一組訪問權(quán)組成。因?yàn)閷ο笠延闪酗@式地定義，故可以只寫出訪問權(quán)而不必寫出是對哪個(gè)對象的訪問權(quán)，每一項(xiàng)的訪問權(quán)access（i，j）定義了在域Di中執(zhí)行的進(jìn)程能對對象Qj施加的操作集。訪問矩陣中的訪問權(quán)，通常是由資源的擁有者或者管理者所決定的。當(dāng)用戶創(chuàng)建一新文件時(shí)，創(chuàng)建者便是擁有者，系統(tǒng)在訪問矩陣中為新文件增加一列，由用戶決定在該列的某個(gè)項(xiàng)中應(yīng)具有哪些訪問權(quán)，而在另一項(xiàng)中又應(yīng)具有哪種訪問權(quán)。當(dāng)用戶刪除此文件時(shí)，也要相應(yīng)地將該文件在訪問矩陣的列中取消。訪問矩陣如圖5-8所示，它是由3個(gè)域和8個(gè)對象組成。當(dāng)進(jìn)程在域D1中執(zhí)行時(shí)，它能讀文件F1，讀寫文件F2。進(jìn)程在域D2中執(zhí)行時(shí)，它能讀文件F3、F4、F5及寫文件F4、F5和執(zhí)行文件F4，此外還可打印。只有當(dāng)進(jìn)程在域D3中運(yùn)行時(shí)，才可使用繪圖機(jī)。 對象域文件1文件2文件3文件4文件5文件6打印機(jī)1繪圖儀2D1RR,WD2RR,W,ER,WWD3R,W,EWWR：讀；W：寫；E：執(zhí)行圖4-8一個(gè)保護(hù)矩陣上面的訪問矩陣，在概念上是簡單的，極易理解。但在具體實(shí)現(xiàn)上，卻有一定的困難。這是因?yàn)椋谏跃咭?guī)模的系統(tǒng)中，域的數(shù)量和對象的數(shù)量都可能很大。保存訪問矩陣需要比較大的存儲空間，同時(shí)進(jìn)行訪問時(shí)也十分費(fèi)時(shí)。事實(shí)上，每個(gè)用戶（進(jìn)程）所需訪問的對象，通常都是非常有限的，因此訪問矩陣是非常稀疏的矩陣，目前實(shí)現(xiàn)的方法，是將訪問矩陣按列劃分，或者按行劃分，分別形成訪問控制表或訪問權(quán)利表。訪問控制表指對訪問矩陣按列進(jìn)行劃分，為每一列建立一張?jiān)L問控制表。在該表中，已把矩陣中屬于該列的所有空項(xiàng)刪除，此時(shí)的訪問控制表是由一有序?qū)Γㄓ颍瑱?quán)集）所組成。由于在大多數(shù)情況下，空項(xiàng)遠(yuǎn)多于非空項(xiàng)，因而使用訪問控制表可以顯著地減少所占用的存儲空間，并能提高查找速度。域是一個(gè)抽象的概念，它能以各種方式實(shí)現(xiàn)：每個(gè)用戶可以是一個(gè)域，這是最常見的一種情況，一個(gè)用戶是一個(gè)域，而對象則是文件，此時(shí)，用戶能夠訪問的文件集和訪問權(quán)限取決于用戶的身份；每個(gè)進(jìn)程是一個(gè)域，此時(shí)，能夠訪問的對象集中的各訪問權(quán)，取決于進(jìn)程身份。（2）訪問權(quán)限表如果把訪問矩陣按行進(jìn)行劃分，便可由每一行構(gòu)成一張?jiān)L問權(quán)限表，換言之，是由一個(gè)域?qū)γ恳粋€(gè)對象可以執(zhí)行的一組操作所構(gòu)成的表。表中的每一項(xiàng)即為該域?qū)δ骋粚ο蟮脑L問權(quán)限，當(dāng)域?yàn)橛脩簦ㄟM(jìn)程），對象為文件時(shí)，訪問權(quán)限表便可用來描述一個(gè)用戶（進(jìn)程）對每一文件所能執(zhí)行的一組操作。如圖對應(yīng)于圖中域D2的訪問權(quán)限表。在表中共有三個(gè)字段，其中，類型字段用于說明對象的類型；權(quán)利字段是指域D2對該對象所擁有的訪問權(quán)限；對象字段是一個(gè)指向相應(yīng)對象的指針。由該表可以看出，域D2可以訪問的對象有4個(gè)，即文件3、4、5和打印機(jī)，對文件3的訪問權(quán)限是只讀，對文件4的訪問權(quán)限是可讀、可寫或可執(zhí)行等。類型權(quán)利對象0文件R—指向文件3的指針1文件RWE指向文件4的指針2文件RW-指向文件5的指針3打印機(jī)-W-指向打印機(jī)1的指針圖4-9訪問權(quán)限表訪問權(quán)限表是安全的，那么由它所保護(hù)的對象才可能是安全的。因此，訪問權(quán)限表不允許被用戶（進(jìn)程）直接訪問。通常，可采用三種方式對訪問權(quán)限表進(jìn)行保護(hù)：將訪問權(quán)限表存儲到系統(tǒng)區(qū)內(nèi)的一個(gè)專用區(qū)中，只允許OS對它進(jìn)行訪問；為每個(gè)對象建立一個(gè)標(biāo)識位，用于標(biāo)明該對象是否要訪問權(quán)限表，該標(biāo)識位不允許被用戶程序訪問；可以將訪問權(quán)限表放在用戶空間，但須將表中的每一個(gè)訪問權(quán)限都譯成密碼。目前大多數(shù)系統(tǒng)都同時(shí)采用訪問控制表和訪問權(quán)限表。2、訪問控制在計(jì)算機(jī)應(yīng)用范圍迅速擴(kuò)大的同時(shí)，如何保證系統(tǒng)安全性的問題，變的更為重要了。在稍具規(guī)模的系統(tǒng)中，都加強(qiáng)了對系統(tǒng)安全性的管理，不少系統(tǒng)已經(jīng)從多個(gè)級別上來保證系統(tǒng)的安全性。下面介紹在四個(gè)級別上對文件進(jìn)行安全性管理的措施：（1）系統(tǒng)級安全管理系統(tǒng)級安全管理的主要任務(wù)，是不允許未經(jīng)核準(zhǔn)的用戶進(jìn)入系統(tǒng)，從而也就防止了他人非法地使用系統(tǒng)中的各類資源（包括文件）。系統(tǒng)級的安全管理有以下幾種主要方法：a．注冊。注冊的主要目的是使系統(tǒng)管理員能夠掌握要使用系統(tǒng)的諸用戶的情況，并保證用戶名在系統(tǒng)中的唯一性。為此，在系統(tǒng)中保存了一張用戶表，每個(gè)注冊用戶在其中占有一個(gè)表項(xiàng)。表項(xiàng)中包括用戶名和指定的口令。b．登錄。用戶注冊后，若要使用本系統(tǒng)，還需進(jìn)行登錄。登錄的主要目的，是通過核實(shí)該用戶的注冊名及口令來檢查該用戶使用系統(tǒng)的合法性。c．若干措施。系統(tǒng)管理員可采取以下措施，來進(jìn)一步保證文件的系統(tǒng)級安全性：規(guī)定用戶定期地修改口令，以防口令被竊；限定用戶在指定的終端上機(jī)，不能任意更換終端；限定用戶在規(guī)定的時(shí)間上機(jī)，其它時(shí)間不得上機(jī)。（2）用戶級安全管理是為了給用戶分配“文件訪問權(quán)”而設(shè)計(jì)的。用戶對文件訪問權(quán)限的大小，是根據(jù)用戶性質(zhì)、需求及文件屬性而分配的。用戶級安全包括兩方面的內(nèi)容：a．用戶分類不同系統(tǒng)對用戶進(jìn)行分類的方法各不相同，在一些系統(tǒng)中把用戶分為四類：超級用戶。這是具有最高文件訪問權(quán)的用戶，通常是系統(tǒng)管理員；系統(tǒng)操作員。系統(tǒng)賦予其較高的文件訪問權(quán)；用戶。在登錄時(shí)，系統(tǒng)根據(jù)其需求，為他指定對一系列文件的訪問權(quán)。顧客。系統(tǒng)限定他只能訪問某些特定文件。b．文件訪問權(quán)已經(jīng)在系統(tǒng)中登錄過的用戶都具有指定的訪問權(quán)。訪問權(quán)決定了用戶對哪些文件能執(zhí)行哪些操作。當(dāng)對某用戶賦予其訪問指定目錄的權(quán)限時(shí)，他便具有了對該目錄下的所有子目錄和文件的訪問權(quán)。某種訪問權(quán)也可被賦予一個(gè)用戶組，這時(shí)，該組中的每個(gè)成員便都具有這種訪問權(quán)?？梢远x八種訪問權(quán)限：建立、刪除、打開、讀、寫、查詢、修改、父權(quán)等。（3）目錄級安全管理是為保護(hù)系統(tǒng)中的各種目錄而設(shè)計(jì)的，它與用戶權(quán)限無關(guān)。為保證目錄的安全，規(guī)定只有系統(tǒng)核心才具有寫目錄的權(quán)利。通常，系統(tǒng)是分別為用戶和目錄獨(dú)立地指定權(quán)限的。當(dāng)用戶試圖訪問一目錄時(shí)，核心將通過對用戶訪問權(quán)和目錄中的訪問權(quán)的比較后，用戶才能獲得有效的訪問權(quán)。即在用戶和目錄中都有的訪問權(quán)；或者說，有效訪問權(quán)是上述兩個(gè)權(quán)限的交集。（4）文件級安全管理是通過系統(tǒng)管理員或文件主對文件屬性的設(shè)置，來控制用戶對文件的訪問。通?？稍O(shè)置以下幾種屬性：只執(zhí)行、隱含、索引、修改、只讀、讀/寫、共享、系統(tǒng)，用戶對文件的訪問，將由用戶訪問權(quán)、目錄訪問權(quán)限及文件屬性三者的權(quán)限所確定。或者說，是有效權(quán)限和文件屬性的交集。4.2.2一、文件系統(tǒng)層次結(jié)構(gòu)如圖示出了文件系統(tǒng)的模型?？蓪⒃撃Ｐ头譃槿齻€(gè)層次，其最低層是對象及其屬性；中間層是對對象進(jìn)行操縱和管理的軟件集合；最高層是文件系統(tǒng)提供給用戶的接口。用戶（程序）文件系統(tǒng)接口用戶（程序）文件系統(tǒng)接口對對象操縱和管理的軟件的集合對象及其屬性圖4-10文件系統(tǒng)模型1、對象及其屬性。文件管理系統(tǒng)管理的對象有：（1）文件。它作為文件管理的直接對象。（2）目錄。為了方便用戶對文件的存取和檢索，在文件系統(tǒng)中必須配置目錄。對目錄的組織和管理是方便用戶和提高對文件存取速度的關(guān)鍵。（3）磁盤存儲空間。文件和目錄必定占用存儲空間，對這部分空間的有效管理，不僅能提高外存的利用率，而且能提高對文件的存取速度。2、對對象操縱和管理的軟件集合這是文件管理系統(tǒng)的核心部分。文件系統(tǒng)的功能大多是在這一層實(shí)現(xiàn)的，其中包括：對文件存儲空間的管理、對文件目錄的管理、用于將文件的邏輯地址轉(zhuǎn)換為物理地址的機(jī)制、對文件讀和寫的管理，以及對文件的共享和保護(hù)等功能。3、文件系統(tǒng)的接口為方便用戶使用文件系統(tǒng)，文件系統(tǒng)通常向用戶提供兩種類型的接口：（1）命令接口。這是指作為用戶與文件系統(tǒng)交互的接口。用戶可通過鍵盤終端鍵入命令，取得文件系統(tǒng)的服務(wù)。（2）程序接口。這是指作為用戶程序與文件系統(tǒng)的接口。用戶程序可通過系統(tǒng)調(diào)用來取得文件系統(tǒng)的服務(wù)。二、文件的實(shí)現(xiàn)在實(shí)現(xiàn)文件的存儲時(shí)，最重要的問題是如何來記錄一個(gè)文件被存放在哪一些磁盤塊中。由于磁盤具有可直接訪問的特性，故當(dāng)利用磁盤來存放文件時(shí)，具有很大的靈活性。在為文件分配外存空間時(shí)所要考慮的主要問題是：怎樣才能有效地利用外存空間和如何提高對文件的訪問速度。目前常用的外存分配方法有：連續(xù)分配、鏈接分配和索引分配三種。通常，在一個(gè)系統(tǒng)中，僅采用其中的一種方法來為文件分配外存空間。1、連續(xù)分配方式連續(xù)分配要求為每一個(gè)文件分配一組相鄰接的盤塊，在采用連續(xù)分配方式時(shí)，可把邏輯文件中的記錄順序地存放到鄰接的各物理盤塊中，這樣形成的文件結(jié)構(gòu)稱為順序文件結(jié)構(gòu)，此時(shí)的物理文件稱為順序文件。這種分配方式保證了邏輯文件中的記錄順序與存儲器中文件占用盤塊的順序的一致性。為使系統(tǒng)能找到文件存放的地址，應(yīng)在目錄項(xiàng)的“文件物理地址”字段中，記錄該文件第一個(gè)記錄所在的盤塊號和文件長度。連續(xù)分配的主要優(yōu)點(diǎn)：順序訪問容易。訪問一個(gè)占有連續(xù)空間的文件，非常容易；順序訪問速度快。因?yàn)橛蛇B續(xù)分配所裝入的文件，所占用的盤塊可能是位于一條或幾條相鄰的磁道上，這時(shí)磁頭的移動(dòng)距離最少，因此訪問速度快。連續(xù)分配的主要缺點(diǎn)：要有連續(xù)的存儲空間；必須事先知道文件的長度。2、鏈接分配方式如同內(nèi)存管理一樣，連續(xù)分配所存在的問題就在于：必須為一個(gè)文件分配連續(xù)的磁盤空間。如果將一個(gè)邏輯文件存儲到外存上時(shí)，并不要求為整個(gè)文件分配一塊連續(xù)的空間，而是可以將文件裝到裝到多個(gè)離散的盤塊中，就可消除上述缺點(diǎn)。在采用鏈接分配方式時(shí)，可通過在每個(gè)盤塊上的鏈接指針，將同屬于一個(gè)文件的多個(gè)離散的盤塊鏈接成一個(gè)鏈表，把這樣形成的物理文件稱為鏈接文件。由于鏈接分配是采取離散分配方式，消除了外部碎片，故而顯著地提高了外存空間的利用率；又因?yàn)槭歉鶕?jù)文件的當(dāng)前需要，為它分配必需的盤塊，當(dāng)文件動(dòng)態(tài)增長時(shí)，可動(dòng)態(tài)地再為它分配盤塊，無須事先知道文件的大小。此外，對文件的增、刪、改也十分方便。鏈接方式又可分為隱式鏈接和顯式鏈接兩種形式。（1）隱式鏈接在采用隱式鏈接分配方式時(shí)，在文件目錄的每個(gè)目錄項(xiàng)中，都須含有指向鏈接文件第一盤塊和最后一個(gè)盤塊的指針。而在每個(gè)盤塊中都含有一個(gè)指向下一個(gè)盤塊的指針。隱式鏈接分配方式的主要問題在于：它只適合順序訪問，對隨機(jī)訪問是極其低效的；只通過鏈接指針來將一大批離散的盤塊鏈接起來，任何一個(gè)指針出問題，都會導(dǎo)致整個(gè)鏈的斷開。（2）顯式鏈接把用于鏈接文件各物理塊的指針，顯式地存放在內(nèi)存的一張鏈接表中，該表在整個(gè)磁盤僅設(shè)置一張，如圖所示。表的序號是物理盤塊號，從0開始，直至N-1；N為盤塊總數(shù)。在每個(gè)表項(xiàng)中存放鏈接指針，即下一個(gè)盤塊號。在該表中，凡是屬于某個(gè)文件的第一個(gè)盤塊號，或者是每一條鏈的鏈?zhǔn)字羔標(biāo)鶎?yīng)的盤塊號，均作為文件地址被填入相應(yīng)文件的FCB的“物理地址”字段中。由于查找記錄的過程是在內(nèi)存中進(jìn)行的，因而不僅顯著地提高了檢索速度，而且大大減少了訪問磁盤的次數(shù)。由于分配給文件的所有盤塊號都放在該表中，故把該表成為文件分配表。MS-DOS、Windows及OS/2等操作系統(tǒng)都采用了FAT。PCB物理塊號FAT02102434551圖4-11顯式鏈接結(jié)構(gòu)3、索引分配（1）單級索引分配鏈接分配方式雖然解決了連續(xù)分配方式所存在的問題，但又出現(xiàn)了兩個(gè)問題：其一不能支持高效的直接存取，要對一個(gè)較大的文件直接存取，須首先在FAT中順序地查找許多盤塊號；FAT需占用較大的內(nèi)存空間，由于一個(gè)文件所占用的盤塊號，是隨機(jī)地分布在FAT中的，因而只有將整個(gè)FAT調(diào)入內(nèi)存，才能保證在FAT中找到一個(gè)文件的盤塊號，當(dāng)磁盤容量較大時(shí)，F(xiàn)AT可能要占用數(shù)MB以上的內(nèi)存空間，這是令人難以接受的。事實(shí)上，在打開某個(gè)文件時(shí)，只需把文件占用的盤塊的編號調(diào)入內(nèi)存即可，完全沒有必要將整個(gè)FAT調(diào)入內(nèi)存。為此，應(yīng)將每個(gè)文件所對應(yīng)的盤塊號集中地放在一起。索引分配方法就是基于這種想法所形成的一種分配方法。它為每個(gè)文件分配一個(gè)索引塊（表），在把分配給該文件的所有盤塊號，都記錄在該索引塊中，因而該索引塊就是一個(gè)含有許多盤塊號的數(shù)組。在建立一個(gè)文件時(shí)，便須在為之建立的目錄項(xiàng)中，填上指向該索引塊的指針。索引分配方式支持直接訪問，當(dāng)要讀文件的第i個(gè)盤塊時(shí)，可以方便地直接從索引塊中找到第i個(gè)盤塊的盤塊號；另外索引分配方式也不會產(chǎn)生外部碎片，當(dāng)文件較大時(shí)，索引分配方式無疑要優(yōu)于鏈接分配方式。索引分配方式的主要問題是：可能要花費(fèi)較多的外存空間。對于小文件采用索引分配方式時(shí)，其索引塊的利用率是極低的。（2）多級索引分配當(dāng)操作系統(tǒng)為一個(gè)大文件分配磁盤空間時(shí)，如果所分配出去的盤塊的盤塊號已經(jīng)裝滿一個(gè)索引塊時(shí)，操作系統(tǒng)便為該文件分配另一個(gè)索引塊，用于將以后繼續(xù)為之分配的盤塊號記錄于其中。依次類推，再通過鏈指針將各索引塊按序鏈接起來。當(dāng)文件太大時(shí)，索引塊太多，這種方法是低效的。此時(shí)，應(yīng)為這些索引塊再建立一級索引，稱為第一索引。即系統(tǒng)再分配一個(gè)索引塊，作為第一級索引的索引塊，將第一塊、第二塊等索引塊的盤塊號，填入到此索引表中，這樣便形成了兩級索引分配方式。如果文件非常大時(shí)，還可用三級、四級索引分配方式。（3）混合索引方式三、目錄的實(shí)現(xiàn)當(dāng)用戶要訪問一個(gè)已存文件時(shí)，系統(tǒng)首先利用用戶提供的文件名對目錄進(jìn)行查詢，找出該文件的文件控制塊或?qū)?yīng)索引結(jié)點(diǎn)；然后根據(jù)FCB或索引結(jié)點(diǎn)中所記錄的文件物理地址（盤塊號），換算出文件在磁盤上的物理位置；最后，再通過磁盤驅(qū)動(dòng)程序，將所需文件讀入內(nèi)存。目前對目錄進(jìn)行查詢最常用的方式是線性檢索法。線性檢索法又稱為順序檢索法。在單級目錄中，利用用戶提供的文件名，用順序查找法直接從文件目錄中找到指名文件的目錄項(xiàng)。在樹型目錄中，用戶提供的文件名是由多個(gè)文件分量名組成的路徑名，此時(shí)須對多級目錄進(jìn)行查找。假定用戶給定的文件路徑名是/usr/ast/mbox，則查找/usr/ast/mbox的文件的過程如圖所示。其查找過程說明如下：首先，系統(tǒng)應(yīng)先讀入第一個(gè)文件分量名usr，用它與根目錄文件（或當(dāng)前目錄文件）中各目錄項(xiàng)中的文件名順序地進(jìn)行比較，從中找出匹配者，并得到匹配項(xiàng)的索引結(jié)點(diǎn)號6，再從6號索引結(jié)點(diǎn)中得知usr目錄文件放在132號盤塊中，將該盤塊內(nèi)容讀入內(nèi)存。接著，系統(tǒng)再將路徑名中的第二個(gè)分量名ast讀入，用它與放在132號盤塊中的第二級目錄文件中各目錄項(xiàng)的文件名順序進(jìn)行比較，又找到匹配項(xiàng)，從中得到ast的目錄文件放在26號索引結(jié)點(diǎn)中，再從26號索引結(jié)點(diǎn)中得知/usr/ast是存放在496號盤塊中，再讀入496號盤塊。然后，系統(tǒng)又將該文件的第三分量名mbox讀入，用它與第三級目錄文件/usr/ast中各目錄項(xiàng)中的文件名的比較，最后得到/usr/ast/mbox的索引結(jié)點(diǎn)號為60，即在60號索引結(jié)點(diǎn)中存放了指定文件的物理地址。目錄查詢操作到此結(jié)束。如果在順序查找過程中，發(fā)現(xiàn)有一個(gè)文件分量名未能找到，則應(yīng)停止查找，并返回“文件未找到”的信息。根目錄結(jié)點(diǎn)6是的/usr目錄132盤塊是/usr的目錄結(jié)點(diǎn)26是/usr/ast的目錄496號盤塊是/usr/ast的目錄1．6．26．1．．1．．6．．4bin19dick64grants7dev13230erik49692books14lib51jim60mbox9etc26ast81minik6usr45bal17src8tmp圖4-12查找/usr/ast/mbox的步驟4.2.3一、磁盤的結(jié)構(gòu)磁盤設(shè)備是一種相當(dāng)復(fù)雜的機(jī)電設(shè)備，這里僅對磁盤的某些性能，如數(shù)據(jù)的組織、磁盤的類型和訪問時(shí)間等方面做扼要介紹。1、數(shù)據(jù)的組織與格式磁盤設(shè)備可包括一或多個(gè)盤塊，每片分兩面，每面可分成若干條磁道，各磁道之間留有必要的間隙。在每條磁道上可存儲相同數(shù)目的二進(jìn)制位。這樣，磁盤密度即每英寸中所存儲的位數(shù)，顯然內(nèi)層磁道的密度較外層磁道的密度高。每條磁道又分成若干個(gè)扇區(qū)，其典型值為10~100個(gè)扇區(qū)。每個(gè)扇區(qū)的大小相當(dāng)于一個(gè)盤塊，各扇區(qū)之間保留一定的間隙。為了在磁盤上存儲數(shù)據(jù)，必須先將磁盤格式化。一種溫盤中一條磁道格式化后，每條磁道含有30個(gè)固定大小的扇區(qū)，每個(gè)扇區(qū)為600個(gè)字節(jié)，其中512字節(jié)存放數(shù)據(jù)，其余的用于存放控制信息。每個(gè)扇區(qū)包括兩個(gè)字段：（1）標(biāo)識符字段。其中一個(gè)字節(jié)的SYNCH具有特定的位圖像，作為該字段的定界符。利用磁道號、磁頭號及扇區(qū)號三者來標(biāo)識一個(gè)扇區(qū)；CRC字段用于段校驗(yàn)。（2）數(shù)據(jù)字段。存放512字節(jié)的數(shù)據(jù)。2、磁盤的類型對磁盤，可以從不同的角度進(jìn)行分類。最常見的有：軟盤和硬盤、單片盤和多片盤、固定頭磁盤和移動(dòng)頭磁盤等。（1）固定頭磁盤這種磁盤在每條磁道上都有讀/寫磁頭，所有的磁頭都被裝在一剛性磁臂中。通過這些磁頭可訪問所有各磁道，并進(jìn)行并行讀寫，有效地提高了磁盤的I/O速度。這種結(jié)構(gòu)主要用于大容量的磁盤上。（2）移動(dòng)頭磁盤每一個(gè)盤面僅配有一個(gè)磁頭，也被裝入磁臂中。為能訪問該盤面上的所有磁道，該磁頭必須能移動(dòng)以進(jìn)行尋道，可見，移動(dòng)磁頭僅能以串行方式讀/寫，致使其I/O速度較慢；但由于其結(jié)構(gòu)簡單，故廣泛應(yīng)用于中小型磁盤設(shè)備中。3、磁盤的訪問時(shí)間磁盤設(shè)備在工作時(shí)，以恒定速率旋轉(zhuǎn)。為了讀或?qū)?，磁頭必須能移動(dòng)到所要求的磁道上，并等待所要求的扇區(qū)的開始位置旋轉(zhuǎn)到磁頭下，然后在開始讀或?qū)憯?shù)據(jù)。故可把對磁盤的訪問時(shí)間分成以下三部分。（1）尋道時(shí)間Ts是指把磁臂（磁頭）移動(dòng)到指定磁道上所經(jīng)歷的時(shí)間。該時(shí)間是啟動(dòng)磁臂的時(shí)間s與磁頭移動(dòng)n條磁道所花費(fèi)的時(shí)間之和，即Ts=m×n+s。其中m是一常數(shù)，與磁盤驅(qū)動(dòng)器的速度有關(guān)。（2）旋轉(zhuǎn)延遲時(shí)間Tτ是指指定扇區(qū)移動(dòng)到磁頭下面所經(jīng)歷的時(shí)間。對于硬盤，典型的旋轉(zhuǎn)速度大多為5400r/min，每轉(zhuǎn)需時(shí)11.1ms，平均旋轉(zhuǎn)延遲時(shí)間為5.55ms。（3）傳輸時(shí)間Tt是指把數(shù)據(jù)從磁盤讀出或向磁盤寫入數(shù)據(jù)所經(jīng)歷的時(shí)間。Tt的大小與每次所讀寫的字節(jié)數(shù)b和旋轉(zhuǎn)速度有關(guān)。其中，r為磁盤每秒鐘的轉(zhuǎn)數(shù)，N為一條磁道上的字節(jié)數(shù)。二、磁盤調(diào)度算法磁盤是可供多個(gè)進(jìn)程共享的設(shè)備，當(dāng)有多個(gè)進(jìn)程都要求訪問磁盤時(shí)，應(yīng)采用一種最佳調(diào)度算法，以使各進(jìn)程對磁盤的平均訪問時(shí)間最小。由于在訪問磁盤的時(shí)間中，主要是尋道時(shí)間，因此，磁盤的調(diào)度目標(biāo)，是使磁盤的平均尋道時(shí)間最少。目前常用的磁盤調(diào)度算法有如下幾種：1、先來先服務(wù)是一種最簡單的磁盤調(diào)度算法，它根據(jù)進(jìn)程請求訪問磁盤的先后次序進(jìn)行調(diào)度，此算法的優(yōu)點(diǎn)是公平、簡單，且每個(gè)進(jìn)程的請求都能依次得到處理，不會出現(xiàn)某一進(jìn)程的請求長期得不到的情況。但此算法由于未對尋道進(jìn)行優(yōu)化，致使平均尋道時(shí)間可能較長。2、最短尋道時(shí)間優(yōu)先該算法選擇這樣的進(jìn)程，其要求訪問的磁道，與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時(shí)間最短，但這種算法不能保證平均尋道時(shí)間最短。3、掃描算法（1）進(jìn)程“饑餓”現(xiàn)象最短尋道時(shí)間優(yōu)先算法雖然能獲得較好的尋道性能，但卻可能導(dǎo)致某個(gè)進(jìn)程發(fā)生“饑餓”現(xiàn)象。因?yàn)橹灰粩嘤行逻M(jìn)程的請求到達(dá)，且其所要訪問的磁道與磁頭當(dāng)前所在磁道的距離較近，這種新進(jìn)程的請求必然優(yōu)先滿足。會導(dǎo)致老進(jìn)程出現(xiàn)“饑餓”現(xiàn)象。（2）SCAN算法該算法不僅考慮到欲訪問的磁道與當(dāng)前磁道間的距離，更優(yōu)先考慮的是磁頭當(dāng)前的移動(dòng)方向，當(dāng)磁頭正在自里向外移動(dòng)時(shí)，掃描算法所考慮的下一個(gè)訪問對象，應(yīng)是其欲訪問的磁道既在當(dāng)前磁道之外，又是距離最近的。這樣自里向外地訪問，直至再無更外的磁道需要訪問時(shí)，才將磁臂換向自外向里移動(dòng)。同理，要訪問在這個(gè)方向距離最近的，直至在無更里面的磁道要訪問。從而避免出現(xiàn)“饑餓”現(xiàn)象。由于這種算法中磁頭移動(dòng)的規(guī)律頗似電梯的運(yùn)行，因而又常稱之為電梯調(diào)度算法。4、循環(huán)掃描算法掃描算法既能獲得較好的尋道性能，又能防止“饑餓”現(xiàn)象，故被廣泛用于大、中、小型機(jī)器和網(wǎng)絡(luò)中的磁盤調(diào)度，但也存在這樣的問題：當(dāng)磁頭剛從里向外移動(dòng)而越過了某一磁道時(shí)，恰好又有一進(jìn)程請求訪問此磁道，這時(shí)該進(jìn)程必須等待，待磁頭繼續(xù)從里向外，然后再從外向里掃描完所有要訪問的磁道后，才處理該進(jìn)程的請求，致使該進(jìn)程的請求被大大地推遲。為了減少這種延遲，循環(huán)掃描算法規(guī)定磁頭單向移動(dòng)，例如，只是自里向外移動(dòng)，當(dāng)磁頭移到最外的磁道并訪問后，磁頭立即返回到最里的欲訪問磁道，亦即將最小磁道號緊接著最大磁道號構(gòu)成循環(huán)，進(jìn)行循環(huán)掃描。采用循環(huán)掃描方式后，上述請求進(jìn)程的請求延遲將從原來的2T減為T+Smax，其中T為由里向外或由外向里單向掃描完要訪問的磁道所需的尋道時(shí)間，Smax是將磁頭從最外面被訪問的磁道直接移到最里面欲訪問的磁道的尋道時(shí)間（或相反）。三、磁盤的管理為了實(shí)現(xiàn)磁盤空間的管理，首先必須記住空閑存儲空間的情況。為此，首先，系統(tǒng)應(yīng)為分配磁盤空間而設(shè)置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)；其次，系統(tǒng)應(yīng)提供對存儲空間進(jìn)行分配和回收的功能。1、空閑表法空閑表法屬于連續(xù)分配方式，它為每個(gè)文件分配一個(gè)連續(xù)的存儲空間。系統(tǒng)為外存上的所有空閑區(qū)建立一張空閑表，每個(gè)空閑區(qū)對應(yīng)于一個(gè)空閑表項(xiàng)，空閑表中包括：序號、該空閑區(qū)的第一個(gè)盤塊號、該區(qū)的空閑盤塊數(shù)等信息，應(yīng)將所有空閑區(qū)按起始盤塊號遞增的次序排列，形成空閑盤塊表。空閑盤區(qū)的分配和內(nèi)存的動(dòng)態(tài)分配類似，同樣可采取首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng)算法等。在內(nèi)存分配上，雖然很少采用連續(xù)分配方式；然而在外存管理上，由于它具有較高的分配速度，可減少訪問磁盤的頻率，故它在諸多分配方式中仍占有一席之地。2、空閑鏈表法是將所有的空閑盤區(qū)拉成一條空閑鏈，根據(jù)構(gòu)成鏈的基本元素不同，可有兩種鏈表形式：空閑盤塊鏈和空閑盤區(qū)鏈。（1）空閑盤塊鏈?zhǔn)菍⒋疟P上的所有空閑存儲空間，以盤塊為基本元素拉成一條鏈。當(dāng)用戶因創(chuàng)建文件而請求分配存儲空間時(shí)，系統(tǒng)從鏈?zhǔn)组_始，依次摘下適當(dāng)數(shù)目的空閑盤塊分配給用戶，當(dāng)用戶因刪除文件而釋放存儲空間時(shí)，系統(tǒng)將回收的盤塊，依次鏈入空閑盤塊鏈的尾部。這種方法的優(yōu)點(diǎn)是用于分配和回收一個(gè)盤塊的過程非常簡單；缺點(diǎn)是空閑盤塊鏈可能很長。（2）空閑盤區(qū)鏈將磁盤上的所有空閑盤區(qū)拉成一條鏈（每個(gè)盤區(qū)可包含若干個(gè)盤塊）。在每個(gè)盤區(qū)上除含有用于指示下一個(gè)空閑盤區(qū)的指針外，還應(yīng)標(biāo)有指明本盤區(qū)大?。ūP塊數(shù)）的信息。盤區(qū)的分配方法與內(nèi)存的動(dòng)態(tài)分區(qū)分配類似。這種方法的優(yōu)缺點(diǎn)剛好和第一種方法的優(yōu)缺點(diǎn)相反，即分配與回收過程較復(fù)雜，但空閑盤區(qū)鏈較短。3、位示圖法（1）位示圖是利用二進(jìn)制的一位來表示磁盤中一個(gè)盤塊的使用情況。當(dāng)其值為“0”時(shí)，表示對應(yīng)的盤塊空閑；為“1”時(shí)表示已分配。磁盤上的所有盤塊都有一個(gè)二進(jìn)制位與之對應(yīng)，這樣由所有盤塊所對應(yīng)的位構(gòu)成一個(gè)集合，稱為位示圖。通?？捎胢×n個(gè)位數(shù)來構(gòu)成位示圖，并使m×n等于磁盤的總塊數(shù)。（2）盤塊的分配根據(jù)位示圖進(jìn)行盤塊分配時(shí)，可分三步進(jìn)行：123456789101112131415161100100011110001120011001100000111301000011110000114．．16圖4-13位示圖（2）盤塊的分配根據(jù)位示圖進(jìn)行盤塊分配時(shí)，可分三步進(jìn)行：a．順序掃描位示圖，從中找出一個(gè)或一組其值均為“0”的二進(jìn)制位（“0b．將所找到的一個(gè)或一組二進(jìn)制位，轉(zhuǎn)換成與之相應(yīng)的盤塊號。假定，找到的其值為“0”c．修改位示圖，令map[i,j]=1.(3)盤塊的回收盤塊的回收分兩步：將回收盤塊的盤塊號轉(zhuǎn)換成位示圖中的行號和列號，轉(zhuǎn)換公式為：i=（b-1）DIVn+1j=（b-1）MODn+1修改位示圖。令map[i,j]=0。這種方法的主要優(yōu)點(diǎn)，是從位示圖中很容易找到一個(gè)或一組相鄰接的空閑盤塊。此外由于位示圖很小，占用空間少，因而可將它保存在內(nèi)存中，在每次進(jìn)行盤區(qū)分配時(shí)，無需首先去把磁盤分配表讀入內(nèi)存，從而省掉許多磁盤的啟動(dòng)操作。4.3經(jīng)典例題解析1、試述文件管理系統(tǒng)設(shè)置打開文件、關(guān)閉文件命令的原因。分析：該題目深入地考察了文件系統(tǒng)的功能。操作系統(tǒng)要處理大量用戶文件，而訪問一個(gè)文件要查詢目錄，有時(shí)甚至要多次查詢目錄。由于文件目錄和文件一起存放在輔存上，當(dāng)存取文件時(shí)，必須先到輔存中讀取文件目錄信息，從中獲得文件的存放地址，然后再去存取文件。這樣一來，文件信息的存取將花費(fèi)很多時(shí)間。如果將整個(gè)文件目錄放入主存，雖然可以提高存取速度，但這需要占據(jù)大量的主存空間，顯然這也是不可取的。實(shí)際上，在一段時(shí)間內(nèi)使用的文件數(shù)總是有限的，因此只要將目錄中當(dāng)前使用的那些文件的目錄表目復(fù)制到內(nèi)存中就可以了。這樣，既不占用太多的主存空間，又可顯著提高查詢文件目錄的速度。為此，大多數(shù)操作系統(tǒng)中設(shè)置了兩個(gè)文件操作：打開文件和關(guān)閉文件。打開文件操作完成的功能是將文件的有關(guān)目錄信息復(fù)制到主存活動(dòng)文件表中，以建立用戶和這個(gè)文件的聯(lián)系，并將該表目的編號（或稱為索引）返回給用戶，以后，當(dāng)用戶要求對該文件操作時(shí)，系統(tǒng)便可直接利用該索引號到活動(dòng)文件表中去查找，避免了對該文件的再次檢索，提高檢索速度。關(guān)閉文件操作的功能是用戶宣布這個(gè)文件當(dāng)前不再使用，系統(tǒng)將其在主存中的相應(yīng)目錄信息刪去，因而也就切斷了用戶與這個(gè)文件的聯(lián)系。2、有一磁盤組共有10個(gè)盤面，每個(gè)盤面有100個(gè)磁道，每個(gè)磁道有16個(gè)扇區(qū)。假定分配以扇區(qū)為單位，若使用位示圖管理磁盤空間，問位示圖占用多少空間？若空白文件目錄的每個(gè)表目占用5個(gè)字節(jié)，問什么時(shí)候空白文件目錄大于位示圖？分析：空白文件目錄是管理磁盤空間的一種方法，該方法將文件存儲設(shè)備上的每個(gè)連續(xù)空閑區(qū)看作一個(gè)空白文件。系統(tǒng)為所有空白文件單獨(dú)建立一個(gè)目錄，每個(gè)空白文件在這個(gè)目錄中占一個(gè)表目。表目的內(nèi)容至少包括第一個(gè)空白塊的地址、空白塊的數(shù)目；位示圖是另一種常用的管理磁盤空間的方法，該方法通過建立一張位示圖來反映整個(gè)存儲空間的分配情況。由題目知，磁盤組扇區(qū)總數(shù)為：16×100×10=16000因此，使用位示圖描述扇區(qū)狀態(tài)需要的位數(shù)為：16000位=2000字節(jié)又由題目所給條件知，空白文件目錄的每個(gè)表占5個(gè)字節(jié)，位示圖需要占2000字節(jié)，2000個(gè)字節(jié)可存放的表目數(shù)為：2000/5=400，所以當(dāng)空白區(qū)數(shù)目大于400時(shí)，空白文件目錄大于位示圖。3、假定磁盤塊的大小為1K，對于540M的硬盤，其文件分配表FAT需要占用多少存儲空間？分析：文件分配表FAT是一個(gè)數(shù)據(jù)結(jié)構(gòu)，用在以鏈接方式存儲文件的系統(tǒng)中記錄磁盤分配和跟蹤空白磁盤塊。由題目所給條件可知，硬盤大小為540M，磁盤塊的大小為1K，所以該硬盤共有：540M/1K=540K（個(gè)）磁盤塊，又512K<540K<1024K，故540K個(gè)盤塊號要用20位二進(jìn)制表示，即文件分配表的每個(gè)表目為2.5個(gè)字節(jié)。FAT要占用的存儲空間總數(shù)為：2.5×540=1350K。4、在UnixSystemⅤ中，如果一個(gè)盤塊的大小為1KB，每個(gè)盤塊占4個(gè)字節(jié)，那么，一個(gè)進(jìn)程要訪問偏移量為263168字節(jié)處的數(shù)據(jù)時(shí)，需要經(jīng)過幾次間接?分析：一個(gè)盤塊可放1K/4=256（個(gè)）盤塊號263168的邏輯盤塊號為：263168/1K=257因?yàn)?0<257<266，所以263168的塊號在一次間接塊內(nèi)，需經(jīng)過一次間接。5、在UnixSystemⅤ中，卷資源表如下所示，現(xiàn)有一進(jìn)程要釋放4個(gè)物理塊，其塊號為150#，156#，172#，177#，畫出卷資源表的變化，在此基礎(chǔ)上假定一進(jìn)程要求分配5個(gè)空閑塊，畫出分配后的卷資源表。S_nfree=98S_nfree=98S_free[0]=120S_free[1]=121…S_free[96]=145S_free[97]=2104.4題型練習(xí)4.4.11．文件系統(tǒng)的主要目的是().A．實(shí)現(xiàn)對文件的按名存取B．實(shí)現(xiàn)虛擬存儲C．提高外存的讀寫速度D．用于存儲系統(tǒng)文件

答案-1:A2．文件系統(tǒng)是指().A．文件的集合B．文件的目錄集合C．實(shí)現(xiàn)文件管理的一組軟件D．文件,管理文件的軟件及數(shù)據(jù)結(jié)構(gòu)的總體答案-2:D3．文件管理實(shí)際上是管理().A．主存空間B．輔助存儲空間

C．邏輯地址空間D．物理地址空間

:B4．下列文件的物理結(jié)構(gòu)中,不利于文件長度動(dòng)態(tài)增長的文件物理結(jié)構(gòu)是().

A．順序文件B．鏈接文件C．索引文件D．系統(tǒng)文件5.下列描述不是文件系統(tǒng)功能的是().A．建立文件目錄B．提供一組文件操作

C．實(shí)現(xiàn)對磁盤的驅(qū)動(dòng)調(diào)度D．實(shí)現(xiàn)從邏輯文件到物理文件間的轉(zhuǎn)換6．文件系統(tǒng)在創(chuàng)建一個(gè)文件時(shí),為它建立一個(gè)().A．文件目錄B．目錄文件C．邏輯結(jié)構(gòu)D．邏輯空間7．面向用戶的文件組織機(jī)構(gòu)屬于().A．虛擬結(jié)構(gòu)B．實(shí)際結(jié)構(gòu)C．邏輯結(jié)構(gòu)D．物理結(jié)構(gòu)8．按文件用途來分,編譯程序是().A．用戶文件B．檔案文件C．系統(tǒng)文件D．庫文件9．將信息加工形成具有保留價(jià)值的文件是().A．庫文件B．檔案文件C．系統(tǒng)文件D．臨時(shí)文件10．文件目錄的主要作用是().A．按名存取B．提高速度C．節(jié)省空間D．提高外存利用率11．如果文件系統(tǒng)中有兩個(gè)文件重名,不應(yīng)采用().A．一級目錄結(jié)構(gòu)B．樹型目錄結(jié)構(gòu)

C．二級目錄結(jié)構(gòu)D．A和C12．文件系統(tǒng)采用樹型目錄結(jié)構(gòu)后,對于不同用戶的文件,其文件名().A．應(yīng)該相同B．應(yīng)該不同

C．可以不同,也可以相同D．受系統(tǒng)約束13．文件系統(tǒng)采用二級文件目錄可以().A．縮短訪問存儲器的時(shí)間B．實(shí)現(xiàn)文件共享

C．節(jié)省內(nèi)存空間D．解決不同用戶間的文件命名沖突14．文件代表了計(jì)算機(jī)系統(tǒng)中的().A．硬件B．軟件C．軟件資源D．硬件資源15．索引式(隨機(jī))文件組織的一個(gè)主要優(yōu)點(diǎn)是().A．不需要鏈接指針B．能實(shí)現(xiàn)物理塊的動(dòng)態(tài)分配

C．回收實(shí)現(xiàn)比較簡單D．用戶存取方便16．有一個(gè)長度為3000個(gè)字節(jié)的流式文件要存儲在磁盤上，磁盤的每塊可以存放512個(gè)字節(jié),該文件至少用()塊.A．5B．6C．7D．300017．文件的存儲方法依賴于().A．文件的物理結(jié)構(gòu)B．存放文件的存儲設(shè)備的特性

C．A和BD．文件的邏輯結(jié)構(gòu)18．多級目錄結(jié)構(gòu)形式為().A．線形結(jié)構(gòu)B,散列結(jié)構(gòu)C．網(wǎng)狀結(jié)構(gòu)D．樹型結(jié)構(gòu)

19．樹型目錄結(jié)構(gòu)的主文件目錄稱為().A．父目錄B．根目錄C．子目錄D．用戶文件目錄

20．樹型目錄結(jié)構(gòu)的第一級稱為目錄樹的().A．分支節(jié)點(diǎn)．B．根節(jié)點(diǎn)C．葉節(jié)點(diǎn)D．終節(jié)點(diǎn)

21．使用絕對路徑名訪問文件是從()開始按目錄結(jié)構(gòu)訪問某個(gè)文件.A．當(dāng)前目錄B．用戶主目錄C．根目錄D．父目錄

22．目錄文件所存放的信息是().A．某一文件存放的數(shù)據(jù)信息B．某一文件的文件目錄

C．該目錄中所有數(shù)據(jù)文件目錄D．該目錄中所有子目錄文件和數(shù)據(jù)文件的目錄23．()是指有關(guān)操作系統(tǒng)和其他系統(tǒng)程序組成的文件.A．系統(tǒng)文件B．檔案文件C．用戶文件D．順序文件

24．由字符序列組成,文件內(nèi)的信息不再劃分結(jié)構(gòu),這是指().A．流式文件B．記錄式文件

C．順序文件D．有序文件25．AUTOEXEC.BAT文件的邏輯結(jié)構(gòu)形式是().A．字符流式文件B．庫文件C．記錄式文件D．只讀文件26．?dāng)?shù)據(jù)庫文件的邏輯結(jié)構(gòu)形式是().A．字符流式文件B．檔案文件

C．記錄式文件D．只讀文件27．邏輯文件是()的文件組織形式.A．在外部設(shè)備上B．從用戶觀點(diǎn)看

C．虛擬存儲D．目錄28對順序文件做讀文件操作時(shí),總是從()按順序讀出信息.

A．文件頭部向后B．文件中部開始

C．文件尾部開始D．當(dāng)前位置開始29．在文件系統(tǒng)中,要求物理塊必須連續(xù)的物理文件是().

A．順序文件B．鏈接文件

C．索引文件D．多重索引文件30．對文件的存取時(shí)必須按指針進(jìn)行,效率較低,采用這種物理結(jié)構(gòu)的是().A．順序文件B．鏈接文件

C．索引文件D．多重索引文件31．若用戶總是要求用隨機(jī)存取方式查找文件記錄,則采用索引結(jié)構(gòu)比采用鏈接結(jié)構(gòu)().

A．麻煩B．方便C．一樣D．有時(shí)方便有時(shí)麻煩32．磁盤與主機(jī)之間傳遞數(shù)據(jù)的單位是().A．柱面B．磁道C．?dāng)?shù)據(jù)塊D．記錄33．用戶歸還文件的使用權(quán)可以調(diào)用的文件操作是().

A．建立B．打開C．關(guān)閉D．刪除34．在UNIX系統(tǒng)中,磁盤存儲空間空閑塊的鏈接方式是().

A．單塊鏈接B．位示圖法C．順序結(jié)構(gòu)D．成組鏈接35．在文件管理中，采用位示圖主要是實(shí)現(xiàn)().A．磁盤的驅(qū)動(dòng)調(diào)度

B．磁盤空間的分配和回收

C．文件目錄的查找

D．頁面置換36．下面()屬于存儲介質(zhì).

A．磁帶

B．光驅(qū)

C．硬盤驅(qū)動(dòng)器

D．磁帶機(jī)

37．對一個(gè)文件的訪問，常由()共同限制.A．用戶訪問權(quán)限和文件屬性

B．用戶訪問權(quán)限和用戶優(yōu)先級C．節(jié)省主存空間D．文件屬性和口令38．文件系統(tǒng)采用二級目錄結(jié)構(gòu)，這樣可以().A．縮短訪問文件存儲器時(shí)間

B．實(shí)現(xiàn)文件共享C．優(yōu)先級和文件屬性

D．解決不同用戶之間的文件名沖突問題39．一般來說，文件名及屬性可以收納在()中以便查找.A．目錄

B．索引C．字典

D．作業(yè)控制塊40．如果文件采用直接存取方式且文件大小不固定，則宜選擇()文件結(jié)構(gòu)A．直接

B．順序C．隨機(jī)D．索引

4.1．對文件的主要操作使用內(nèi)容是什么？它的系統(tǒng)調(diào)用內(nèi)容是什么？2．什么是文件和文件系統(tǒng)？文件系統(tǒng)有那些功能？3．什么是文件目錄？文件目錄中一般包含那些內(nèi)容？4．按文件的物理結(jié)構(gòu)，可將文件分為哪幾類？5．什么是邏輯文件？什么是物理文件？6．對目錄管理的主要要求是什么？7．在UNIX操作系統(tǒng)中，是如何對空閑盤塊進(jìn)行分配和回收的？8．文件存取控制方式有哪幾種？試比較它們各自的優(yōu)缺點(diǎn)。9．試說明文件系統(tǒng)中對文件操作的系統(tǒng)調(diào)用處理功能。10．假定一個(gè)盤組共有100個(gè)柱面，每個(gè)柱面上有16個(gè)磁道，每個(gè)盤面分成4個(gè)扇區(qū)，問：（1）整個(gè)磁盤空間共有多少個(gè)存儲塊？（2）如果用字長為32位的單元來構(gòu)造位示圖，共需要多少個(gè)字？（3）位示圖中第18個(gè)字的第16位對應(yīng)的塊號是多少？11．假定在某移動(dòng)臂磁盤上，剛剛處理了訪問60號柱面的請求，目前正在73號柱面上讀信息，并有下列請求序列等待訪問磁盤：請求序列：

1

2

3

4

5

6

7

8

9

欲訪問的柱面號：150

50

178

167

87

43

23

160

85

試用最短尋找時(shí)間優(yōu)先算法、電梯調(diào)度算法和循環(huán)掃描算法，分別排出實(shí)際上處理上述請求的次序并分別求出平均尋道長度。12．假定有一個(gè)磁盤組共有100個(gè)柱面，每個(gè)柱面有8個(gè)磁道，每個(gè)盤面劃分成8個(gè)扇區(qū)。現(xiàn)有一個(gè)5000個(gè)邏輯記錄的文件，邏輯記錄的大小與扇區(qū)大小相等，該文件以順序結(jié)構(gòu)被存放在磁盤組上，柱面、磁道、扇區(qū)均從0開始編址，邏輯記錄的編號從0開始，文件信息從0柱面、0磁道、0扇區(qū)開始存放。請問：

（1）該文件的3468個(gè)邏輯記錄應(yīng)存放在哪個(gè)柱面的第幾個(gè)磁道的第幾個(gè)扇區(qū)上。

（2）第56柱面上的第8磁道的第5扇區(qū)中存放的是該文件的第幾個(gè)邏輯記錄。13．某軟盤有40個(gè)磁道，磁頭從一個(gè)磁道移至另一磁道需要6。文件在磁盤上非連續(xù)存放，邏輯上相鄰數(shù)據(jù)塊的平均距離為13磁道，每塊的旋轉(zhuǎn)延遲時(shí)間及傳輸時(shí)間分別為100、25，問讀取100塊的文件需要多少時(shí)間？如果系統(tǒng)對磁盤進(jìn)行了整理，讓同一文件的磁盤塊盡可能靠攏，從而使邏輯上相鄰數(shù)據(jù)塊的平均距離降為2磁道，這時(shí)讀取一個(gè)100塊的文件需要多少時(shí)間？14．許多操作系統(tǒng)中提供了文件重命名功能，它能賦予文件一個(gè)新名字。若進(jìn)行文件復(fù)制，并給復(fù)制新文件起一個(gè)名字，然后刪除舊文件，也能達(dá)到給文件命名的目的。試問這兩種方法在實(shí)現(xiàn)有何不同？15．某系統(tǒng)的文件物理結(jié)構(gòu)采用混合索引分配方式，如果每個(gè)盤塊的大小為1KB，每個(gè)盤塊號占4個(gè)字節(jié)，在文件的索引結(jié)點(diǎn)中，共設(shè)12個(gè)地址項(xiàng)，前十個(gè)是直接地址，第十一個(gè)存放一次間接地址，第十二個(gè)存放二次間接地址，計(jì)算此系統(tǒng)允許的文件最大長度可達(dá)多大？16.在UNIX中，假定盤塊的大小為1KB，每個(gè)盤塊號占4字節(jié)，索引節(jié)點(diǎn)中磁盤地址信息如下表所示，將下列文件的字節(jié)偏移量轉(zhuǎn)換為物理地址：（1）9000（2）14000（3）350000解答：計(jì)算字節(jié)偏移量9000的邏輯塊號和塊內(nèi)偏移量：邏輯塊號為：INT[9000/1024]=8塊內(nèi)偏移量為：9000-8*1024=808邏輯塊號小于8，因此該塊為直接塊，由圖知物理塊號為367，塊內(nèi)偏移量為808；計(jì)算字節(jié)偏移量14000的邏輯塊號和塊內(nèi)偏移量：邏輯塊號為：INT[14000/1024]=13塊內(nèi)偏移量為：14000-13*1024=688因10≤13<266,該塊為一次間接塊。其物理塊號為952，塊內(nèi)偏移量為688；計(jì)算字節(jié)偏移量350000的邏輯塊號和塊內(nèi)偏移量：邏輯塊號為：INT[350000/1024]=341塊內(nèi)偏移量為：35000-341*1024=816因266≤341<65802,該塊為二次間接塊。其物理塊號為3333，塊內(nèi)偏移量為816；17．4.單項(xiàng)選擇題：1A2D3B4A5C6A7C8C9B10A11A12C13D14C15D16B17C18D19B20B21C22D23A24A25A26C27B28A29A30B31B32C33C34D35B36A37A38D39A40D綜合應(yīng)用題1．答：對文件系統(tǒng)的主要操作為：

（1）文件管理：包括目錄管理，實(shí)現(xiàn)按名存取。

（2）文件存儲空間的管理：文件的組織形式--邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，分配與管理外部存取器。

（3）文件的存取控制：解決文件保護(hù)、保密和共享。

（4）提供方便的用戶接口：系統(tǒng)調(diào)用。

系統(tǒng)調(diào)用的主要內(nèi)容有：文件的創(chuàng)建、打開、讀、寫、關(guān)閉、刪除等。2．答：文件：具有符號名的一組相關(guān)元素的有序序列，是一段程序或數(shù)據(jù)集合。文件系統(tǒng)：包含文件管理程序（文件與目錄的集合）和所管理的全部文件。文件系統(tǒng)的功能包括：⑴分配與管理外部存儲器，用戶以文件形式存放信息并可按名存取。⑵提供合適的存儲方法，如鍵盤命令和系統(tǒng)調(diào)用，以及文件的創(chuàng)建create、打開open、關(guān)閉close、讀寫read/write、刪除delete、和重命名rename等。⑶文件的共享與保護(hù)，解決文件名中的沖突與存取權(quán)限的控制。3．答：文件目錄即文件名址錄。它是一張記錄所有文件的名字及其存放地址的目錄表。表中還應(yīng)包括關(guān)于文件的說明和控制方面的信息。文件目錄一般包含：文件名、文件邏輯結(jié)構(gòu)（說明該文件的記錄是否定長，記錄長度及記錄個(gè)數(shù)等）、文件在存儲器中的物理位置、存取控制信息（登記文件主本人及其他用戶具有的存取權(quán)限）、管理信息（如建立日期等）、文件類型。4．答：文件的三種物理結(jié)構(gòu)是順序文件、鏈接文件和索引文件。連續(xù)分配要求為每一個(gè)文件分配一組相鄰接的盤塊，在采用連續(xù)分配方式時(shí)，可把邏輯文件中的記錄順序地存放到鄰接的各物理盤塊中，這樣形成的文件結(jié)構(gòu)稱為順序文件結(jié)構(gòu)，此時(shí)的物理文件稱為順序文件。在采用鏈接分配方式時(shí)，可通過在每個(gè)盤塊上的鏈接指針，將同屬于一個(gè)文件的多個(gè)離散的盤塊鏈接成一個(gè)鏈表，把這樣形成的物理文件稱為鏈接文件。索引分配為每個(gè)文件分配一個(gè)索引塊（表），在把分配給該文件的所有盤塊號，都記錄在該索引塊中，因而該索引塊就是一個(gè)含有許多盤塊號的數(shù)組。在建立一個(gè)文件時(shí)，便須在為之建立的目錄項(xiàng)中，填上指向該索引塊的指針。5．答：邏輯文件：結(jié)構(gòu)是用戶所觀察到的文件組織形式，邏輯文件是用戶可直接處理的數(shù)據(jù)內(nèi)容，它獨(dú)立于物理特性，又稱為組織文件。邏輯文件是用戶觀點(diǎn)，研究用戶“思維”中的抽象文件，為用戶提供一種邏輯結(jié)構(gòu)清晰，使用簡便的邏輯文件形式，用戶按照這種形式去存儲、檢索、加工有關(guān)文件信息。物理文件：有實(shí)際存儲結(jié)構(gòu)的文件，是在外存上實(shí)際存儲的文件，與存儲介質(zhì)的存儲性能有關(guān)。物理文件是實(shí)現(xiàn)觀點(diǎn)，系統(tǒng)按物理結(jié)構(gòu)形式去和外部設(shè)備打交道。6．答：文件系統(tǒng)所要解決的核心問題，就是按照充分發(fā)揮主機(jī)和外部設(shè)備效率的原則，把信息的邏輯結(jié)構(gòu)映像成設(shè)備介質(zhì)上的物理結(jié)構(gòu)，把用戶的文件操作轉(zhuǎn)換成相應(yīng)的I/O指令。轉(zhuǎn)換過程所使用的主要數(shù)據(jù)結(jié)構(gòu)是文件目錄和輔存空間使用情況表。所以目錄管理的基本功能就是通過查目錄能實(shí)現(xiàn)符號名與具體地址之間的轉(zhuǎn)換。要求目錄的編排應(yīng)以如何能準(zhǔn)確地找到所需文件為原則，而選擇目錄的方法應(yīng)以查找速度快為準(zhǔn)則。7．答：UNIX采用成組鏈接法進(jìn)行空閑磁盤塊的管理。例如，每個(gè)50個(gè)空閑塊為一組，組中的頭一塊為“組長塊”第一組的50個(gè)空閑塊塊號放在第二組的組長塊中，而第二組的其余49塊是完全空閑的。第二組的50塊號又放在第三組的組長塊中。依次類推，組與組之間形成鏈接關(guān)系。最后一組的塊號（可能不足50塊）通常放在內(nèi)存的一個(gè)專用棧（即專用塊的空閑塊號棧）結(jié)構(gòu)中。這樣，平常對盤塊的分配和釋放是在棧中進(jìn)行（或構(gòu)成新的一組）。空閑塊分配：當(dāng)建立文件、需要分配空閑盤塊時(shí)，總是先把專用塊中表示棧深（即棧中有效元素的個(gè)數(shù)）的數(shù)值減1，這里就是40—1等于39。以39作為檢索專用塊中空閑塊號棧的索引。由圖中所示，得到盤塊號111，它就是當(dāng)前分出去的第一個(gè)空閑塊。如果需要分配20個(gè)盤塊，則上述操作就重復(fù)執(zhí)行20次。如果當(dāng)前棧深的值是1，需要分配2個(gè)空閑盤塊，那么棧深值（1）減1，結(jié)果為0，此時(shí)系統(tǒng)做特殊處理：先根據(jù)0為索引得到盤塊號150，它是第七十八組的組長；然后把150號盤塊中的內(nèi)容—下一組（即第七十七組）所有空閑盤塊的數(shù)量（50）和各個(gè)盤塊的塊號分別放入專用塊的棧深和空閑塊號棧中，從而專用塊的棧中就記載著有第七十七組盤塊的情況；最后把150盤塊分配出去。至此，分出去1塊。接著再分配一塊，此時(shí)工作簡單多了：50—1結(jié)果是49，以49索引得到第七十七組的151號塊。空閑塊釋放：在圖5-17所示的情況下，如果要?jiǎng)h除一個(gè)文件，它占用3個(gè)盤塊，塊號分別是69、75和87。首先釋放69號塊，其操作過程是：把塊號69放在棧深40所對應(yīng)的元素中，然后棧深值加1，變?yōu)?1。接著分別釋放75號塊和87好塊。最后，專用塊中棧深的值為43，空閑塊號棧中新加入的3個(gè)盤塊出現(xiàn)的次序是69，75，87。如果棧深的值是50，表示該棧已滿，此時(shí)還要釋放一個(gè)盤塊89號，則進(jìn)行特殊處理：先將該棧中的內(nèi)容（包括棧深值和各空閑塊號）寫到要釋放的新盤塊（即89號）中；將棧深及棧中盤塊號清為0；以棧深值0為索引，將新盤塊號89寫入相應(yīng)的單元中，然后棧深值加1，棧深值變?yōu)?。這樣，盤塊89號就成為新組的組長塊。成組鏈接法是UNIX系統(tǒng)中采用的空閑盤塊管理技術(shù)，它兼?zhèn)淞丝臻e空間表法和空閑塊鏈接法的優(yōu)點(diǎn)，克服了兩種方法都有的表（或鏈）太長的缺點(diǎn)。當(dāng)然，成組鏈接法在管理上要復(fù)雜一些，尤其是盤塊分配時(shí)出現(xiàn)棧空、盤塊釋放時(shí)遇到棧滿的情況下，要作特殊處理。答：文件存取控制方式有四種：8．⑴存取控制矩陣：建立一個(gè)二維訪問控制矩陣用以列出系統(tǒng)中所有用戶和文件。其中，一維列出系統(tǒng)全部用戶，另一維列出計(jì)算機(jī)系統(tǒng)的全部文件。矩陣元素“1”表示允許訪問，“0⑵用戶權(quán)限表：把一個(gè)用戶（或用戶組）所要存取的文件名集中存放在一張表中，其中每個(gè)表目指明相應(yīng)文件的存取權(quán)限。優(yōu)點(diǎn)：便于查找權(quán)限。缺點(diǎn)：如果用戶數(shù)或文件數(shù)多則過于龐大，不便查找。⑶使用口令：用戶為自己的每個(gè)文件規(guī)定一個(gè)口令，并附在用戶文件目錄中。存取文件時(shí)必須提供口令，只有當(dāng)提供的口令與目錄中口令一致時(shí)才允許存取。優(yōu)點(diǎn)：占存儲空間少，方便。缺點(diǎn)：保護(hù)能力弱。⑷使用密碼：存儲時(shí)用“密碼”對文件進(jìn)行編碼，取用文件時(shí)進(jìn)行譯碼。優(yōu)點(diǎn)：保密性強(qiáng)。在這個(gè)方案中，發(fā)方提供的代碼鍵不存入系統(tǒng)。只有當(dāng)用戶要存取文件時(shí)，才需將代碼送進(jìn)系統(tǒng)。這樣別人無法偷看或篡改別人的文件。缺點(diǎn)：必須花費(fèi)大量編碼和譯碼時(shí)間，增加了系統(tǒng)的開銷。9．答：系統(tǒng)調(diào)用是操作系統(tǒng)提供給編程人員的唯一接口。利用系統(tǒng)調(diào)用，編程人員在源程序中動(dòng)態(tài)請求和釋放系統(tǒng)資源，調(diào)用系統(tǒng)中已有的功能來完成那些與機(jī)器硬件部分相關(guān)的工作以及控制程序的執(zhí)行速度等。系統(tǒng)調(diào)用如同一個(gè)黑匣子，對使用者屏蔽了具體操作動(dòng)作，只是提供了有關(guān)功能.有關(guān)文件系統(tǒng)的系統(tǒng)調(diào)用是用戶經(jīng)常使用的，包括文件的創(chuàng)建（create）、打開(open)、讀(read)、寫(write)、關(guān)閉(close)等。下面是一個(gè)有關(guān)文件系統(tǒng)的系統(tǒng)調(diào)用的例子。main(argc,argv)intargc;

char*argv[];{intfd1,fd2,fd3,n;charbuf[512],ch=’’;fd1=open(argv[1],0);/*打開argv[1]對應(yīng)的文件，返回標(biāo)識符fd1*/fd2=open(argv[2],0);/*打開argv[2]對應(yīng)的文件