操作系統(tǒng)精髓與設計原理

操作系統(tǒng)精髓與設計原理

第12章文件管理

復習題：

、域和記錄有什么不同？

答：域是基本數據單位。一個域包含一個值。記錄是一組相關

的域的集合，它可以看做是應用程序的一個單元。

、文件和數據庫有什么不同？

答：文件是一組相似記錄的集合，它被用戶和應用程序看做是一個實體。

并可以通過名字訪問。數據庫是一組相關的數據集合，它的本質特征是數據元素間存在著明確的關系，并且可供不同的應用程序使用。

、什么是文件管理系統(tǒng)？

答：文件管理系統(tǒng)是一組系統(tǒng)軟件，為使用文件的用戶和應用程序提供服務。、選擇文件組織時的重要原則是什么？

答：訪問快速，易于修改，節(jié)約存儲空間，維護簡單，可靠性。、列出并簡單定義五種文件組織。

答：堆是最簡單的文件組織形式。數據按它們到達的順序被采集，每個記錄一

串數據組成。順序文件是最常用的文件組織形式。在這類文件中，每個記錄都使用一種固定的格式。所有記錄都具有相同的長度，并且相同數目、長度固定的域按特定的順序組成。于每個域的長度和位置已知，因此只需要保存

各個域的值，每個域的域名和長度是該文件結構的屬性。索引順序文件保留了順序文件的關鍵特征：記錄按照關鍵域的順序組織起來。但它還增加了兩個特征：用于支持隨機訪問的文件索引和溢出文件。索引提供了快速接近目標記錄的查找能力。溢出文件類似于順序文件中使用的日志文件，但是溢出文件中的記錄可以根據它前面記錄的指針進行定位。索引文件：只能通過索引來訪問記錄。其結果是對記錄的放置位置不再有限制，只要至少有一個索引的指針

指向這條記錄即可。此外，還可以使用長度可變的記錄。直接文件或散列文件：直接文件使用基于關鍵字的散列。

、為什么在索引順序文件中查找一個記錄的平均搜索時間小于在順序文件中的平均

搜索時間？答：在順序文件中，查找一個記錄是按順序檢測每一個記錄直到有一個包含符合條

件的關鍵域值的記錄被找到。索引順序文件提供一個執(zhí)行最小窮舉搜索的索引結構。

、對目錄執(zhí)行的典型操作有哪些？

答：搜索，創(chuàng)建文件，刪除文件，顯示目錄，修改目錄。、路徑名和工作目錄有什么關系？答：路徑名是一系列從根目錄或主目錄向下到各個分支，最后直到該文件的路徑

中的目錄名和最后到達的文件名組成。工作目錄是一個這樣的目錄，它是含有用戶正在使用的當前目錄的樹形結構。

、可以授予或拒絕的某個特定用戶對某個特定文件的訪問權限通常有哪些？答：無，知道，執(zhí)行，讀(reading)，追加。

更新，改變保護，刪除。

、列出并簡單定義三種組塊方式。答：固定組塊：使用固定長度的記錄，并且若干條完整的記錄被

保存在一個塊中。在每個塊的末尾可能會有一些未使用的空間，稱為內部碎片。

可變長度跨越式組塊：使用長度可變的記錄，并且緊縮到塊中，使得塊中沒有未使用空間。因此，某些記錄可能會跨越兩個塊，通過一個指向后繼塊的指針連接?？勺冮L度非跨越式組塊：使用可變長度的記錄，但并不采用跨越的方式。如果下一條記錄比塊中剩余的未使用空間大，則無法使用這一部分，因此在大多數塊中都會有未使用的空間。

、列出并簡單定義三種文件分配方法。

答：連續(xù)分配是指在創(chuàng)建文件時，給文件分配一組連續(xù)的塊。鏈式分配基于單個的

塊，鏈中的每一塊都包含指向下一塊的指針。索引分配：每個文件在文件分配表中有一個一級索引，分配給該文件的每個分區(qū)在索引中都有一個表項。

習題：

、定義：B=塊大小R=記錄大小P=塊指針大小F=組塊因子，即一個塊中期望的記錄數。對圖中描述的三種組塊方法分別給出關于F的公式。答案：

固定組塊：最大整數

當一個可變長度記錄被保存到組塊中的時候，組塊中會增加一個標記著記錄邊界的數據，用來標識記錄。當跨越式記錄橋聯塊邊界的時候，需要用到一些關聯著后繼組塊的結構。一種可能情況是在每個記錄前加一個長度標識。另一種可能情況是在兩個記錄之間加一個特殊的區(qū)分標識。因此，我們假設每一個記錄需要一個標識，并且標識大小約等于塊指針大小。對于跨越式組塊，指向它下一個組塊的大小為P的塊指針被包含在每一個組塊中，所以跨越式記錄可以很容易地被重定位。此可知：

可變組塊跨越式：

于不采用跨越的方式，可變長度非跨越式組塊會導致平均R/2的空間浪費，但不需要指向后繼組塊的指針：

、一種避免預分配中的浪費和缺乏鄰近性問題的方案是，分配區(qū)的大小隨著文件的增長而增加。例如，開始時，分區(qū)的大小為一塊，在以后每次分配時，分區(qū)的大小翻倍?？紤]一個有n條記錄的文件，組塊因子為F，假設一個簡單的一級索引用做一個文件分配表。a.給出文件分配表中入口數的上限。

b.在任何時候，已分配的文件空間中，未被使用的空間的最大量是多少？答案：a.

b.未被使用的空間總是小于已分配文件空間。

、當數據

a.很少修改并且以隨機順序頻繁地訪問時。

b.頻繁地修改并且相對頻繁地訪問文件整體時，c.頻繁地修改并以隨機順序頻繁地訪問時。

從訪問速度、存儲空間的使用和易于更新這幾方面考慮，為了達到最大效率，你將選擇哪種文件組織？

答案：a.索引文件

b.索引順序文件

c.索引文件或散列文件

、目錄可以當做一種只能通過受限方式訪問的“特殊文件”實現，也可以當做普通文件實現。這兩種方式分別有哪些優(yōu)點和缺點？

答案：很明顯地，如果操作系統(tǒng)把目錄當做一種通過受限方式訪問的“特殊文件”實現。

安全性更容易被加強。把目錄當做一種通過受限方式訪問的普通文件實現使得操作系統(tǒng)更統(tǒng)一地管理對象，更容易地創(chuàng)建和管理用戶目錄。

、一些操作系統(tǒng)具有一個樹結構的文件系統(tǒng)，但是把樹的深度限制到某個比較小的級數上。這種限制對用戶有什么影響？它是如何簡化文件系統(tǒng)的設計的？

答案：這是一個少見的專題。如果操作系統(tǒng)構造一個文件系統(tǒng)以便子目錄被允許包含在

一個主目錄底下，那么就很少或沒有額外的邏輯被要求允許包含任意深度的子目錄。限制子目錄樹的深度造成對用戶組織文件空間不必要地限制。

、考慮一個層次文件系統(tǒng)，空閑的磁盤空間保留在一個空閑空間表中。a.假設指向空閑空間的指針丟失了。該系統(tǒng)可以重構空閑空間表嗎？b.給出一種方案，確保即使出現了一次存儲失敗，指針也不會丟失。

答案：a.可以重構。使用的方法與許多LISP的垃圾收集系統(tǒng)用的方法非常相似。首先。

我們將建立一種數據結構，代表磁盤的每一塊，并且這個磁盤支持一種文件系統(tǒng)。在這里某種映射是比較合適的。然后，我們從這個文件系統(tǒng)的根目錄開始，通過文件系統(tǒng)的遞歸下降尋找，我們標記每一塊已被文件使用的磁盤塊。當完成的時候，我們將為沒有被使用的磁盤塊建立一個空閑列表。這實質上就是UNIX命令fsck的功能。

b.在磁盤上一個或多個地方備份空閑空間列表指針。無論何時列表的開端發(fā)生變

化，備份指針也同樣更新。這樣將會保證即使發(fā)生了存儲器或者磁盤塊錯誤，你也總是能找到一個有效的指針值。

、考慮一個索引節(jié)點所表示的UNIX文件的組織.假設有12個直接塊指針，在每個索引節(jié)點中有一個一級、二級和三級間接指針。此外，假設系統(tǒng)塊大小和磁盤扇面大小都是8K。如果磁盤塊指針是32位，其中8位用于標識物理磁盤，24位用于標識物理塊，那么

a.該系統(tǒng)支持的最大文件大小是多少？

b.該系統(tǒng)支持的最大文件系統(tǒng)分區(qū)是多少？

c.假設主存中除了文件索引節(jié)點外沒有其他息，訪問在位置12，423，956中的字節(jié)需要多少次磁盤訪問？

答案：a.找出每一個塊中根據指針大小來劃分塊大小的磁盤塊指針的數目：8K/4=2Kpointersperblock

I-Node所支持的最大文件大小是：12+2K+(2K×2K)+(2K×2K×2K)直接尋址一級間接尋址二級間接尋址三級間接尋址12+2K+4M+8Gblocks

將以上數據乘以塊大小，得到：96KB+16MB+32GB+64TB

這就是該系統(tǒng)支持的最大文件大小。