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

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

第12章文件管理

復(fù)習(xí)題：

、域和記錄有什么不同？

答：域是基本數(shù)據(jù)單位。一個(gè)域包含一個(gè)值。記錄是一組相關(guān)

的域的集合，它可以看做是應(yīng)用程序的一個(gè)單元。

、文件和數(shù)據(jù)庫(kù)有什么不同？

答：文件是一組相似記錄的集合，它被用戶和應(yīng)用程序看做是一個(gè)實(shí)體。

并可以通過名字訪問。數(shù)據(jù)庫(kù)是一組相關(guān)的數(shù)據(jù)集合，它的本質(zhì)特征是數(shù)據(jù)元素間存在著明確的關(guān)系，并且可供不同的應(yīng)用程序使用。

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

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

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

答：堆是最簡(jiǎn)單的文件組織形式。數(shù)據(jù)按它們到達(dá)的順序被采集，每個(gè)記錄一

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

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

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

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

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

件的關(guān)鍵域值的記錄被找到。索引順序文件提供一個(gè)執(zhí)行最小窮舉搜索的索引結(jié)構(gòu)。

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

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

中的目錄名和最后到達(dá)的文件名組成。工作目錄是一個(gè)這樣的目錄，它是含有用戶正在使用的當(dāng)前目錄的樹形結(jié)構(gòu)。

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

更新，改變保護(hù)，刪除。

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

保存在一個(gè)塊中。在每個(gè)塊的末尾可能會(huì)有一些未使用的空間，稱為內(nèi)部碎片。

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

、列出并簡(jiǎn)單定義三種文件分配方法。

答：連續(xù)分配是指在創(chuàng)建文件時(shí)，給文件分配一組連續(xù)的塊。鏈?zhǔn)椒峙浠趩蝹€(gè)的

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

習(xí)題：

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

固定組塊：最大整數(shù)

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

可變組塊跨越式：

于不采用跨越的方式，可變長(zhǎng)度非跨越式組塊會(huì)導(dǎo)致平均R/2的空間浪費(fèi)，但不需要指向后繼組塊的指針：

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

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

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

、當(dāng)數(shù)據(jù)

a.很少修改并且以隨機(jī)順序頻繁地訪問時(shí)。

b.頻繁地修改并且相對(duì)頻繁地訪問文件整體時(shí)，c.頻繁地修改并以隨機(jī)順序頻繁地訪問時(shí)。

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

答案：a.索引文件

b.索引順序文件

c.索引文件或散列文件

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

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

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

、一些操作系統(tǒng)具有一個(gè)樹結(jié)構(gòu)的文件系統(tǒng)，但是把樹的深度限制到某個(gè)比較小的級(jí)數(shù)上。這種限制對(duì)用戶有什么影響？它是如何簡(jiǎn)化文件系統(tǒng)的設(shè)計(jì)的？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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