計算機攜作系統

主講教師：周星

土課程主要內容

詼操作系統引論（1章)

詼進程管理（2?3章）

詼存儲管理（4章）

詼設備管理（5章）

年文件管理（6章）

詼操作系統接口（7章

詼系統安全性（9章）

**分布式操作系統

垓件系統的引入(1)

■所有的計算機應用程序都需要存儲和檢索信息。

進程運行時，可在它自己的地址空間存儲一定量

的信息，但存儲容量受虛擬地址空間大小的限制O

■對于某些應用程序，它自己的地址空間已經足夠

用了，但對于其他一些應用程序，例如航空訂票

系統、銀行系統或公司記帳系統，這些存儲空間

又顯得太小了。

棄件系統的引入（2）

■在進程的地址空間保存信息的第二個問題是：進程終止

時，它保存的信息也隨之丟失。對于很多應用（如數據

庫）而言，有關信息必須能保存幾星期、幾個月，甚至

永久保留。在使用信息的進程的終止時，這些信息是不

可以消失的。甚至，即使是系統崩潰致使進程消亡了，

這些信息也該保存下來。

■第三個問題：經常需要多個進程同時存取同一信息（或

者其中部分信息）。如果只在一個進程的地址空間里保

存在線電話簿，那么只有該進程才可以對它進行存取，

也就是說一次只能查找一個電話號碼。解決這個問題的

方法是使信息本身獨立于任一進程。

棄件系統的引入(3)

■因此，長期存儲信息有三個基本要求：

(1)能夠存儲大量信息；

(2)使用信息的進程終止時，信息仍舊存在；

(3)必須能使多個進程并發存取有關信息。

■解決所有這些問題的通常做法是：把信息以一種單元的

形式，也就是所謂的文件，存儲在磁盤或其他外部介質

上。進程在需要時可以讀取這些信息或寫入新的信息。

存儲在文件中的信息必須是永久性的，也即信息不會因

為創建和終止進程而受到影響。只有在文件的所有者顯

式地刪除文件時，文件才會消失。

土第6章文件系統

■文件系統的功能/需解決的問題

A從操作系統角度看：文件目錄怎樣實現，怎樣

管理存儲空間，文件存儲位置，磁盤實際運作

方式（與設備管理的接口）等等

A從用戶角度看：文件系統如何呈現在其面前：

一個文件由什么組成，如何命名，如何保護文

件，可以進行何種操作等等

上第6章文件系統

■文件和文件系統

■文件邏輯結構

■外存分配方式

■目錄管理

■文件存儲空間的管理

■文件共享與文件保護本章作業

■數據一致性控制

■**UNIX系統的文件管理

上6.1文件和文件系統

■文件、記錄和數據項（數據的組成）

■文件類型和文件系統模型

■文件操作

土一、數據的組成

■數據項

A基本數據項（最小的邏輯數據單位）

＞組合數據項

■記錄

＞是一組相關數據項的集合

■文件

上文件

＞是指記錄在外存上的具有文件名的一組相關信息的集合。

可分為有結構文件和無結構文件兩種。有結構文件是由

若干個相關記錄組成，而無結構文件則被看成一個字符

流。

■文件屬性

A文件名、文件類型、文件長度、文件的物理位置、文件

的建立日期以及用戶對該文件的存取權限等

■文件表示的范圍/包含的內容

A源程序、二進制代碼、文本文檔、數據、表格、聲音和

圖像等。

■文件的特點

＞文件具有保存性

＞文件是按名存取

＞文件的內容是一組信息的集合

件、記錄和數據項間的層次關系

■■■記錄n

■■■數據項n

上二、文件類型一文件名.擴展名

■按用途分

■按文件的邏輯結構分

＞系統文件

力有結構文件（記錄式文件）

A用戶文件

辦無結構文件（流式文件）

＞庫文件

■按文件的物理結構分

■按數據形式分

0順序文件

＞源文件

力鏈接文件

＞目標文件

O索引文件

＞可執行文件

■按信息流向分

■按存取控制屬性

O輸入文件

＞只讀文件

O輸出文件

＞讀寫文件

O輸入輸出文件

＞只執行文件

＞不保護文件

II

三、文件系統模型

文件系統接口

邏輯文件系統層

對對象操縱基本I/O管理程序層（文件組織模塊）

和管理的軟

件集合基本文件系統層（物理I/O層）

I/O控制層（設備驅動程序）

對象（文件、目錄及磁盤存儲空間）及其屬性說明

基本基本文件系統層：負責內存與磁盤間的數據塊交，擇

設備換（在外存及內存緩沖區的位置）。

口

、文件操作

■用戶通過文件系統所提供的系統調用實施對文件的

操作。最基本的操作有：

A對記錄的操作：檢索、插入、修改、刪除

A對文件的操作

最基本的：創建、打開、關閉、刪除、讀、

寫、截斷

由其它的：文件屬性類操作、目錄類操作

、文件操作

■文件的“打開”和"關閉”操作

>“打開”：系統將文件的屬性（目錄信息）從

外存復制到內存打開文件表中，并返回該表目

的編號給用戶，建立了用戶與文件間的聯系。

以后若再訪問此文件，則利用編號直接在內存

中檢索，從而節省大量的檢索開銷，提高了文

件的操作速度。

>“關閉”：當用戶不再需要對該文件的操作時,

系統利用關閉文件將文件的屬性從內存打開表

中刪除，從而切斷用戶與文件間的聯系。

口

上6.2文件邏輯結構

■對任一文件存在著兩種形式的結構：

＞文件的邏輯結構（文件組織）

亡從用戶觀點出發，所觀察到的文件組織形式，是用

戶可以直接處理的數據及其結構，它獨立于物理特

性。

A*文件的物理結構（文件的存儲結構）

力是指文件在外存上的存儲組織形式，與存儲介質

的存儲性能有關。（分為順序、鏈接及索引結構）

■注：文件的邏輯結構和物理結構都將影響文件的檢索速

16.2文件邏輯結構

■對文件的邏輯結構提出的要求：

A提高檢索速度；便于修改；降低文件存儲費用。

■文件邏輯結構的類型

■順序文件

■索引文件

■索引順序文件

『、文件邏輯結構的類型

■有結構的記錄式文件

＞文件構成：由一個以上的記錄構成。

A記錄長度：分為定長和變長。

A分類（按記錄的組織）：順序文件、索引文件、

索引順序文件

■無結構的流式文件

A文件構成：由字符流構成。

A長度：字節為單位

A訪問：讀寫指針

＞注：Unix中所有文件視為流式文件

II

.二、順序文件

■邏輯記錄的排序

A串結構：記錄順序與關鍵字無關，按存入時間的先后

才非列。后一種情況更有利于提高查詢速度。

一二二\如可用折半查找法等。________J

＞順序結椅］記錄順序按關鍵字排列。

■對順序文件的讀、寫操作

?記錄為定長的順序文件：易于定位，甚至可隨機讀取

A記錄為變長的順序文件：不易定位，只能順序讀取

Rptr=Rptr+1Rptr=Rptr+Lj

讀指針

N■■■

Rptr

Ri

■■■

J頤序文件的優缺點

⑥優點

＞批處理時效率是所有邏輯文件中最高的。

＞可存在于磁帶上

A對定長記錄，還可方便實現直接存取。

合缺點

A交互應用時“效率低”(如要查找單個記錄)，

尤其是對變長記錄的順序文件。

A增加、刪除記錄涉及到排序問題，開銷大。

■解決方法：事務文件(log)，用于存放將更新到主

文件的記錄。

返回

三、索引文件

＞為解決變長記錄文件的直接存取低效問題。

■索引文件

＞為變長記錄文件建立一張索引表。

索引號長度m指針ptr

0/

m0

1m1/

■■■

■/

1mi

邏輯文件

索引表

是引文件的特點

⑥優點

＞通過索引表可方便地實現直接存取，具有較快的

檢索速度。

＞易于進行文件的增刪。

（8）缺點

A索引表的使用增加了存儲費用；

＞索引表的查找策略對文件系統的效率影響很大。

■注：若索引表很大，可建多級索引

返回

索引順序文件

＞為解決變長記錄文件的直接存取低效且存儲費用增

加的問題。

索引文件

＞為順序文件建立一張索引表。

索引號長度m指針ptr

<邏

/

輯

索0

m0

---?

文

引1m-j■■■

件

表

■■■

■

1mi■■■

■■■

產引順序文件的特點

。優點

＞通過索引表可方便地實現直接存取，具有較快的

檢索速度。

＞易于進行文件的增刪。

（8）缺點

＞索引表的查找策略對文件系統的效率影響很大。

II

6.3外存分配方式

■文件存儲單位：簇(cluster)

?文件的存儲空間通常由多個分立的簇組成，而

每個簇包含若干個連續的扇區(sector)/塊。

■目前常用的外存分配方法：

(1)連續分配(順序分配)

(2)鏈接分配

(3)索引分配

1）外存分配方法?連續/順序分配

■圖示

■為每一個文件分配一片連續的磁盤塊/簇

■只需要起始塊/簇號和長度，適用于預分配方法

■可以隨機存取

■文件不能增長（預留空間一浪費；重新分配和移動）

■可以通過緊縮（compact）將外存空閑空間合并成連

續的區域。

■從邏輯地址映射到物理地址較簡單

■不利于文件插入和刪除

連續/順序分配的主要優缺點

■主要優點

A順序訪問容易且速度快，因磁頭移動距離小

■缺點

＞要求有連續的存儲空間

＞必須事先知道文件的長度

A存在外部碎片

n

libAlliiaitbiiirnlik(

FikXFileNumrShriBlotk

o

u-OHfeA3

口<

IlkBFibB3

1tfcCKa

O6白口N

1lieD194，to

IlltC

卜山E163

ioHIN14

____m-____HbD

w口0亡］怖匚|

21口22口230乜口

~|2h1|27||2H|IaI~|

川匚］31|1對|30^0^

■文件對應目錄項（屬性）中包含：始址、總塊數、

最后一塊字節數。

口

(2)外存分配方法■鏈接分配

■Figure6-8

■每個文件是一個磁盤塊的鏈接列表：塊可以分散在磁

盤各處

■按所需分配磁盤塊，鏈接在一起

■在每個塊中有指向下一個塊的指針

■只需要起始地址

■可以通過合并(consolidation)將一個文件的各個簇連

續存放，以提高I/O訪問性能。

上鏈接分配的優缺點

⑨優點

1、無外部碎片，沒有磁盤空間浪費

2、無需事先知道文件大小。文件動態增長時，可動態分配空

閑塊。對文件的增、冊h改十分方便。

*3、不需緊縮磁盤空間。

?缺點

1、不能支持高效隨機/直接訪問，僅對順序存取特有效

2、需為指針分配空間。一塊一簇（隱式鏈接）

3、可靠性較低（指針丟失/損害）一（顯式鏈接如

文件分配表FATFigure6?9所示）

>FAT需占用較大的內存空間。

文件分配表FAT??figure6-9、6-10

■用于鏈接文件各物理塊的鏈接指針，顯式地存放在

內存的一張鏈接表中。

■該表在整個磁盤僅設置一張。

■表序號為整個磁盤的物理塊號

■表項存入鏈接指針，即下一個塊號。

■文件的首塊號存入相應文件的FC中。

■查找在內存的FAT中，故提高了檢索速度，同時又

減少磁盤的訪問次數。

■被MS-DOS和OS/2等所采用。P195Figure6-10

directory

filestartend

jeep925

。口1102口3口

4口57口

8口O2511口

1215口

16[T117|I18口19口

20||2122口23口

241|25[^(26[|271|

281|291|301|31||

(3)外存分配方法■索引分配

■Figure6-11

■為每一個文件分配一個索引塊(表)，再把分配

給該文件的所有塊號，都記錄在該索引塊中。故

索引塊就是一個含有許多塊號地址的數組。

■該索引塊的地址由該文件的目錄項指出。

■支持隨機/直接存取。

■不會產生外部碎片。

■適用于文件較大時。

索引分配的優缺點

⑥優點

A保持了鏈接結構的優點，又解決了其缺點

A即能順序存取，又能隨機存取

A滿足了文件動態增長、插入刪除的要求

A能充分利用外存空間

（8）缺點

＞較多的尋道次數和尋道時間

A索引表本身帶來了系統開銷

A如：內外存空間，存取時間

上練習題

例：請分別解釋在連續分配方式、隱式鏈接分配方式、

顯式鏈接分配方式和索引分配方式中如何將文件的

字節偏移量3500轉換為物理塊號和塊內位移量（設

盤塊大小為1KB,盤塊號需占4個字節）。

解：首先，嚼字節偏移量3500轉換成邏輯塊號和塊

內位移量：3500/1024得到商為3,余數為428,

即邏輯塊號為3,塊內位移量為428。

(1)在連續分配方式中，可從相應文件的FCB中得到分配

給該文件的起始物理盤塊號，例如aO,故字節偏移量

3500相應的物理盤塊號為aO+3,塊內位移量為428。

(2)在隱式鏈接方式中，由于每個盤塊中需留出4個字節

(如最后的4個字節)來存放分配給文件的下一個盤塊的

塊號，因此字節偏移量3500的邏輯塊號為3500/1020的

商3,而塊內位移量為余數440。

從相應文件的FCB中可獲得分配給該文件的首個

(即第。個)盤塊的塊號，如b0;然后可通過讀第bO塊獲

得分配給文件的第1個盤塊的塊號，如b1;再從b1塊中得

到第2塊的塊號,如b2;從b2塊中得到第3塊的塊號，如

b3o如此，便可得到字節偏移量3500對應的物理塊號b3,

而塊內位移量則為440。

(3)在顯式鏈接方式中，可從文件的FCB中得到分配給

文件的首個盤塊的塊號，如cO;然后可在FAT的第cO項

中得到分配給文件的第1個盤塊的塊號，如c1;再在

FAT的第c1項中得到文件的第2個盤塊的塊號，如c2;

在FAT的第c2項中得到文件的第3個盤塊的塊號，如c3。

如此，便可獲得字節偏移量3500對應的物理塊號c3,而

塊內位移量則為428。

(4)在索引分配方式中，可從文件的FCB中得到索引表

的地址。從索引表的第3項(距離索引表首字節12字節

的位置)可獲得字節偏移量3500對應的物理塊號d,而

塊內位移量為428。

索引分配的幾種方式

mode

owners(2)

■直接索引分配timestamps(3)

?data

■多級索引分配sizeblock

Adata

count

Figure6-12Adata

■混合索引分配

directblocks

Adata

data

data

singleindirect

data

doubleindirectAdata

tripleindirectdata

>data

3練習題

例放在某個磁盤上的文件系統，采用混合索引分配方

式，其FCB中共有13個地址項，第0?9個地址項為直接地

址，第10個地址項為一次間接地址，第11個地址項為二

次間接地址，第12個地址項為三次間接地址。如果每個

盤塊的大小為512字節，若盤塊號需要用3個字節來描述,

而每個盤塊最多存放170個盤塊地址。問：

(1)該文件系統允許文件的最大長度是多少？

(2)將文件的字節偏移量5000、15000.150000轉換

為物理塊號和塊內偏移量。

(3)假設某個文件的FCB己在內存，但其他信息均在

外存，為了訪問該文件中某個位置的內容，最少需要幾

次訪問磁盤，最多需要幾次訪問磁盤？

解：(1)該文件系統中一個文件的最大長度可達：

10+170+170x170+170x170x170=4942080塊,

共4942080x512字節=2471040KB

(2)5000/512得至I商為9,余數為392,即字節

偏移量5000對應的邏輯塊號為9,塊內偏移量為392。

由于9<10,故可直接從該文件的FCB的第9個地址

項處得到物理盤塊號，塊內偏移量為392。

a15000/512得至1商為29,余數為152,即字節偏

移量15000對應的邏輯塊號為29,塊內偏移量為

152O由于10<29<10+170,^29-10=19,故可

從FCB的第10個地址項，即一次間址項中得到一

次間址塊的地址；并從一次間址塊的第19項（即

該塊的第57?59這3個字節）中獲得對應的物理盤

塊號，塊內偏移量為152。

a150000/512得至U商為292,余數為496,即字節

偏移量150000對應的邏輯塊號為292,塊內偏移量

為496。由于10+170V292V10+170+170x170,

而292?（10+170）=112,112/170得至1商為0,

余數為112,故可從FCB的第11個地址項，即二次

間址項中得到二次間址塊的地址，并從二次間址塊

的第0項中獲得一4?次間址塊的地址，再從這一

次間址塊的第112項中獲得對應的物理盤塊號，塊

內偏移量為496。

3）由于文件的FCB己在內存，為了訪問文件中

某個位置的內容，最少需要1次訪問磁盤（即可通

過直接地址直接讀文件盤塊），最多需要4次訪問

磁盤（第一次是讀三次間址塊，第二次是讀二次

間址塊，第三次是讀一次間址塊，第四次是讀文

件盤塊）。

文件結構、文件存取方式與文件存儲介質的關系

存儲介質磁帶磁盤

物理結構連續結構連續鏈接索引

順序順序順序

存取方式順序存取

隨機隨機

。口1口、2口3口

\

4口5口607口

8口9HlO[\lin

12口13口)^^

16E]47QwQ^g)

20口21口2狎右匕

24口25匚66口27口

28口29□30口31口

叵

上6.4目錄管理

■對文件目錄的管理要求

A實現“按名存取力

＞提高對目錄的檢索速度

＞文件共享

＞允許文件重名

上6.4目錄管理

■文件控制塊和索引結點

■單級目錄結構

■兩級目錄結構

■才對型目錄結構

■目錄查詢技術

垓件控制塊和索引結點

■從文件管理角度看，文件由FCB和文件體（文件本身）兩部分

組成。

■文件控制塊（FCB）

>文件控制塊是操作系統為管理文件而設置的數據結構，存放

了文件的有關說明信息，是文件存在的標志。

>FCB中的信息

。基本信息類：文件名、文件長度、類型、屬性、文件物

理位置

力存取控制信息類：文件存取權限、用戶名、口令、共享

計數

力使用信息類：文件的建立日期、最后修改日期、保存期

限、最后訪問日期

土問題

■每個文件有一個FCB,它們被保存在外存空間。

當欲訪問一個文件時，應當能夠根據文件名字找

到它所對應的FCB。那么，FCB是如何保存于外

存的呢？

■它是作為目錄項存儲于目錄文件中的。因而,

FCB也被稱作目錄項。

棄件控制塊(FCB)

■文件目錄

A用于檢索文件的目錄稱為文件目錄，它是由目錄項

所構成的有序序列。

■目錄項

?構成文件目錄的項目(目錄項就是FCB)

■目錄文件

A為了實現對文件目錄的管理，通常修文件目錄以文

件的形式保存在外存，這個文件就叫目錄文件。

文件目錄和目錄文件是同一事物的兩種稱謂。從用途角度

來看稱其為文件目錄，從實現角度來看稱其為目錄文件。

件控制塊和索引結點

■索引結點文件名索引結點編號

A索引結點引入文件名1

文件名2

A磁盤索引結點

■■■■■■■■■■■■

力存放在磁盤上的索引結點（主標識、類型、存

取權限、物理地址、長度、連接計數、存取時

間）

＞內存索引結點

力存放在內存上的索引結點（索引結點編號、狀

態、訪問計數、邏輯設備號、鏈接指針）

土例題

■例：在某個文件系統中，每個盤塊為512字節，文

件控制塊占64個字節，其中文件名占8個字節。如

果索引節點編號占2個字節，對一個存放在磁盤上

的256個目錄項的目錄，試比較引入索引節點前后,

為找到其中一個文件的FCB,平均啟動磁盤的次

數。

解：在引入索引節點前，每個目錄項中存放的是對應

文件的FCB,故256個目錄項的目錄總共需要占用

256義64/512=32個盤塊。故，在該目錄中檢索到

一個文件平均啟動磁盤次數為(1+32)/2=16.5O

在引入索引節點后，每個目錄項中只需存放文

件名和索引節點的編號，因此256個目錄項的目錄總

共需要占用256x(8+2)/512=5個盤塊。因此，

找到匹配的目錄項平均需要啟動3次磁盤；而得到索

引節點編號后還需啟動磁盤將對應文件的索引節點

讀入內存，故平均需要啟動磁盤4次。可見，引入索

引節點后，可大大減少啟動磁盤的次數，從而有效

地提高檢索文件的速度。

■在整個系統中只建立一張目錄表

A優點：簡單，易實現按名存取

A缺點：限制了用戶對文件的命名（即易重名）；文

件平均檢索時間長（查找速度慢）；不便于實現文件

共享；只適用于單用戶環境

目錄文件

普通文件

上兩級目錄結構

■在整個系統中建立兩級目錄

＞為每個用戶建立一個單獨的用戶文件目錄（UFD）

＞系統中為所有用戶建立一個主文件目錄（MFD）

兩級目錄結構

■二級文件目錄結構下，每個文件均由系統中的用戶

目錄名和用戶目錄中的文件名兩部分進行標識，其

中，用戶目錄名可由操作系統控制，不會重名，因

此這種標識具有惟一性。即便不同用戶對文件使用

了相同的文件名，由于用戶名的不同而避免了命名

沖突。

■二級文件目錄替各用戶隔離開來，當用戶間相互協

作時，這種隔離就變成了阻隔他們不能互相訪問的

一道鴻溝。因此，二級目錄不方便共享。

口

■在兩級目錄中若允許用戶建立自己的子目錄，則形

成3級或多級目錄結構（即樹型目錄結構）

■共享的子目錄和文件

rootdietspell

AlistradewZ

■路徑名

＞訪問數據文件的一條路徑。

A絕對路徑、相對路徑

■當前目錄

■增加和刪除目錄

■優點

＞層次結構清晰，實現分組，便于管理和保護

＞解決重名問題

＞查找速度加快，因為每個目錄下的文件數目較少

■缺點

＞查找一個文件按路徑名逐層檢查，由于每個文件都放

在外存，多次訪盤影響速度

返回

■數據文件（按名存取）的查詢步驟

＞根據用戶提供的文件名，對文件目錄進行查詢,

找到該文件的FCB（索引結點）

?根據FCB（索引結點）所記錄的磁盤盤塊號,

換算出文件在磁盤上的物理位置

A啟動磁盤驅動程序，讀該數據文件至內存中。

■對目錄進行查詢的方式

A線性檢索法（順序檢索法）

aHash方法

返回

錄查詢技術■線性檢索法（順序檢索法）

/usr/ast/mbox

結點6是132#塊是結點26是496#塊是

根目錄

/usr的目錄/usr/ast目錄/usr/ast目錄

1■

26■

1■■

6■■

4bin64grants

496

7Dev92books

14Lib60mbox

9Etc81minix

6Usr17src

8tmp

口

上目錄查詢技術-Hash方法

■建立一個Hash索引文件目錄，系統利用用戶提供的

文件名，將它變換為文件目錄的索引值，再利用該索

引值到目錄中去查找，從而找到文件的物理地址。

注：1）當文件名中用了*,?時，系統無法利用Hash

法檢索目錄，這時須用線性檢索法查找目錄。

2）在Hash法中須對“沖突”進行處理。

3）若在Hash索引文件目錄中查詢時，相應的目錄項

為空，則表示“文件未找到力。

J5.5文件存儲空間的管理

■仍可采用連續分配和離散分配方式

■方法

＞空閑表法和空閑鏈法

A位示圖法

A成組鏈接法

上5.5.1空閑表法和空閑鏈法

■空閑表也叫空閑文件目錄，是將文件存儲器上一個

個連續的未分配區域（稱作空閑文件）按第一個空

閑塊號，連續空閑的塊數，以及相應位置（即物理

塊號）等信息記在空閑表中，圖示如下頁。

■這種方法適合于建立連續文件，適合少量的空閑區,

空閑區數量多時效率低。

上空閑表法

序號首塊空閑塊塊號空閑塊個數物理塊號

173，8,9

235535,36,37,38,39

空閑文件目錄

上空閑鏈法

■把其中所有“空閑塊”（即未分配使用的物理塊,

也稱“自由塊”）鏈接起來，當創建一個文件需

要存儲塊時，就從鏈頭上依次取下若干塊來，而

撤銷文件時則將回收空間又依次鏈接到鏈尾上。

如下圖所示。

■特點

＞簡單易行，但工作效率低。

空閑鏈法

3517..46

在主存

中存放

空閑鏈塊

」,.5,2位示圖法

■為反映整個存儲空間的分配情況，用主存中若干

字節構成位示圖。每個字節的每一位(bit)都對應了

一個物理塊的狀態。當該位取1時，標記對應的物

理塊已分配；取0時則反映了該物理塊未分配。

■盤塊的分配

(1)順序掃描，找一個或一組為0的塊。

(2)根據找到的行/列得到盤塊號。B=n(i-1)+j

(3)修改位圖map[i,j]=1。

上位示圖法

■盤塊回收

(1)由盤塊號得(i,j)

i=(b-1)divn+1j=(b-1)modn+1

(2)修改位圖：map[i,j]=O

■特點：因不占空間，可放入內存，易于訪問。

單習題1

例1:設某系統的磁盤有500塊，塊號為：0,1,2,3,…,

499o

(1)若用位示圖法管理這500塊的盤空間，當字長為32

位時，此位示圖占了幾個字？

(2)第i字的第j位對應的塊號是多少？(其中：i=0,1,

2,j=0,1,2,3,...)

解：(1)位示圖法就是在內存用一些字建立一張位示圖,

用其中的每一位表示一個盤塊的使用情況，通常用“1”表

示占用，“0”表示空閑。因此，本問題中位示圖所占的字

數為：r500/32J=16。

(2)第i字的第j位對應的塊號N=32*i+j。

單習題2

例2:有一計算機系統利用下圖所示的位示圖(行號、列

號都從0開始編號)來管理空閑盤塊。如果盤塊從1開始

編號，每個盤塊的大小為1KB。

(1)現要為文件分配兩個盤塊，試具體說明分配過程。

(2)若要釋放磁盤的第300塊，應如何處理？

O1234567891O1112131415

01111111111111111

11111111111111111

21

11O1111111111111

3111111o1111o11-1

4OOOOOOOOOOOOOO0O

5

6

答：(1)為某文件分配兩個盤塊的過程如下：

①順序檢索位示圖，從中找到第一個值為0的二進制位，得

到其行號il=2,歹1號產2。第二個值為0的二進制位，得到其

行號i2=3,歹1號j2=6。

②計算出找到的兩個空閑塊的盤塊號分別為：

b1=i1x16+j1+1=2x16+2+1=35

b2n2x16+j2+1=3x16+6+1=55

③修改位示圖，々map[2,2]=map[3,6]=1,并將對應塊35、

55分配出去。

(2)釋放磁盤的第300塊時，應進行如下處理：

①計算出磁盤第300塊所對應的二進制位的行號i和列號j:

i=(300-1)/16=18,j=(300-1)%16=11

②修改位示圖，令map[18/1]=0,表示對應塊為空閑塊。

■.5.3成組鏈接法

■一、空閑盤塊的組織

＞空閑盤塊號棧

■二、空閑盤塊的分配與回收

＞分配：到s.free(O)時，由于該塊內容為下一組的

盤號，將內容加入空閑盤塊號棧中，再分配。

A回收：至人行?6(100)時，將空閑盤塊棧中內容

放入新到的回收塊中，將該回收塊作為棧底。

399

201301-8017901

■實現：定義一個數據結構filsys,它與磁盤空閑塊管理

算法有關。

structfilsys

intsjsize;〃i結點區總塊數

ints_fsize;〃文件數據區總塊數

intsnfree;〃直接管理的空閑塊數

ints_free[100];〃空閑塊號棧

ints-ninode;〃直接管理的空閑i結點數

ints_ninode[100];〃空閑i結點棧

)

?其中，s_nfree^s_free[100]是針對文件數據區的磁盤空

閑塊管理參數，s_ninode和s_ninode[100]是針對i結點區

的磁盤空閑塊管理參數。

成組鏈接法的分配算法:

s_nfree--;

if(s_nfree==O)

if(s_free[O]==tA')sleep(pri,s_flock);

將s_free[O]塊復制到內存filsys中；

a=s_free[O];

)

else

a=s_free[s_nfree];

return(a);

成組鏈接法的回收算法：

if(s_nfree<100)

{"

s_free[s_nfree]=釋放塊的塊號；

s_nfree++;

}"

else

(

將filsys中的s_nfree和s_free[O]?s_free[99]寫到釋

放塊；

s_nfree=1;

s_free[O]=釋放塊的塊號；

}"

return;

單習

例：某個系統采用成組鏈接法來管理磁盤的空閑空間,

目前磁盤的狀態圖如下：

①該磁盤中目前還有多少個空閑盤塊？

②請簡述磁盤塊的分配過程。

③在為某文件分配3個盤塊后，系統要刪除另一

文件，并回收他所占的5個盤塊，它們的盤塊

號依次是700、711、703、788、701,請畫出

回收后的盤塊鏈接情況。

30b?40h50b???

答：(1)301塊。

(2)磁盤塊的分配過程如下：首先檢查空閑盤塊號棧是

否上鎖，如未上鎖，便從棧頂取出一空閑盤塊號，將與之

對應的盤塊分配給用戶，然后將棧頂指針下移一格。若該

盤塊號已是棧底，即S.free(0),這是當前棧中最后一個可

分配的盤塊號。由于該盤塊號所對應的盤塊中記有下一組

可用的盤塊號，因此，調用磁盤讀過程，將棧底盤塊號所

對應的盤塊的內容讀入棧中，作為新的盤塊號棧的內容，

并將原棧底對應的盤塊分配出去。最后，把棧中的空閑盤

塊數減1并返回。

700401501

上成組鏈接法的優點

■利用空閑塊管理空閑塊，沒有額外的數據結構空

間開銷，節省了磁盤空間。

■內存filsys中只需要開辟100個地址指針即可，節

省了內存空間。

■每100個塊的分配或釋放只需要訪問1次磁盤，其

余99次都在內存的filsys中完成，減少讀寫磁盤次

數，從而提高了速度。

■這種棧式管理和成組鏈接方法加快了磁盤的分配

和釋放的速度，減少了系統的時空開銷，提高了

系統的效率。

b6.6文件共享

■早期實現文件共享的方法

A繞彎路法（低效）

力允許每個用戶獲得一“當前目錄”，用戶所訪

問的所有文件均相對于當前目錄，若不在，則

“向上走"繞彎路去訪問其上級目錄。

A連訪法

A利用基本文件目錄實現文件共享

■基于索引結點的共享方式

■利用符號鏈實現文件共享

連訪法

c

返回

用基本文件目錄實現文件共享

0?—_______

,空閑文件目錄

1?-

基

本?-wang3

2wangmxS專-----主--文---件---

文?--?sqrt5zhang4目錄

件3

目4?-餐beta6

錄Zhang

5?-fQsqrt■■■的文件

.Beta目錄

6■alpha

7?-mist

8?-report

9?-?Oaf符號名ID

■■■

返回

產于索引結點的共享方式

wang的文件目錄

它共享用戶均是可見，從而可提供其他用

戶共享。

產于索引結點的共享方式

Owner=c

Count=1

■

擁有者刪除文件后

鏈接前

I］用符號鏈實現文件共享

C的目錄B的目錄C的目錄B的目錄

擁有者刪除文件后

I］用符號鏈實現文件共享

wang的文件目錄

文件物理地址test

fd

Fd文件內容：Wang\test

■優點

A當主文件刪除一共享文件時，其它共享文件的

用戶不會留下一個懸空指針。

＞可鏈接世界上任何地方的機器中的文件。

■缺點

＞根據給定的文件路徑名去查找目錄，將使訪問

文件的開銷大，啟動磁盤頻率較高。

?每一共享文件將具有幾個文件名，這將增加遍

歷共享文件的次數。

返回

上6.6文件保護

■影響文件安全性的主要因素

＞人為因素

＞系統因素

＞自然因素

■確保文件系統安全性的措施

＞存取控制機制---人為因素

＞系統容錯技術——系統因素

A后備系統--------自然因素11

上6.6文件保護一存取控制機制

■保護域

■訪問矩陣

■訪問矩陣的修改（拷貝權、所有權、控制權）

■訪問矩陣的實現（訪問控制表、訪問權限表）

■分級安全管理

＞系統級安全管理

A用戶級安全管理

＞目錄級安全管理

A文件級安全管理

■磁盤容錯技術

保護域

＞靜態聯系

◎進程的可用資源集在進程的整個生命中是固定的

＞動態聯系

進程的可用資源集在進程的整個生命中是變化的

返回

j訪問矩陣

文件A文件B文件C打印機

域D1R,WRw

域D2W,REw

域D3R,Ww

曾用以描述系統存取控制的矩陣訪問矩陣中的行代表域,

列代表對象，矩陣中每一項由一組訪問權組成。

■R?讀；W?寫；E?■執行

■訪問權access(Lj)定義了在域Di中執行的進程能對對

象施加的操作集。

■訪問權通常由資源的擁有者或管理者所決定。

j訪問矩陣

■進程擁有切換權時，可將進程從一個保護域切換

到另一保護域，以實現進程和域之間的動態聯系。

域域

文件A文件B文件C打印機域D1

D2D3

域

R,WRwS

D1

域

W,REwS

D2

域

R,Ww

D3

j訪問矩陣

■保護實現：當進程向文件系統提出存取請求時，系

統就根據存取控制矩陣將本次請求和該進程對文件

的存取權限進行比較，若不匹配就拒絕執行。

■特點：對整個系統中所有文件的訪問權限進行集中

控制。

■缺點：當用戶和文件較多時，存取控制矩陣就較大,

占據的存儲空間就較多；查找花費時間較長。

訪問矩陣的修改?拷貝權，所有權，控制權

■進程在某個域中對某對象擁有的訪問權可通過拷貝

I尋訪問權擴展到其它域（同一列即同一對象）中。

F1F2F3F1F2F3

D1EW*D1EW*

D2ER*ED2ER*E

D3ED3ERW

訪問矩陣的修改■拷貝權所有權，控制權

■利用所有權（0）可實現訪問權的擴展、增力口和

刪除（同一列即同一對象）。

F1F2F3F1F2F3

\

D10,EWD10,E

D2R*,0R*,0,WD2R*,0,WR*,0,

><*

D3EW

D3Eww

」串~問矩陣的修改-拷貝權所有權,控制權

■可改變矩陣中同一行（同一域即不同對象）的訪

問權。

FF2F3F4F5打印機繪圖儀DDD3

11212

DRR,

1W

DR,R,WWcontrol

2Ey

D汆,W

3E

返回

j訪問矩陣的實現■訪問控制表

A將訪問矩陣按列（對象）劃分，為每一列建立

一張訪問控制表ACL。

A在該表中無原矩陣中的空項。

A由有序對（域，權集）組成。

A對象為文件時，常修ACL存放于該文件的FCB/索

引結點中，作為存取控制信息。

A可定義缺省的訪問權集。

串問矩陣的實現“訪問權限表

行將訪問矩陣按行（域）劃分，形成一行一張訪

問權F艮表。

類型權力對象

文件R-指向文件3的指針

文件RWE指向文件4的指針

文件RW-指向文件5的指針

打印機指向打印機1的指針

■系統級安全管理

■用戶級安全管理

■目錄級安全管理

■系統級安全管理■文件級安全管理

A主要任務：不允許未經核準的用戶進入系統

＞主要方法

◎注冊

力登錄

其它措施

g主冊

■主要目的

A使系統管理員能夠掌握要使用系統的諸用戶的情

況，并保證用戶名次系統中的唯一性。

■實現

＞系統中保存一張用戶表。

?用戶使用前須占用用戶表一空項注冊。

A用戶使用后須由管理員將該用戶從用戶表中刪除。

A一旦刪除，該用戶便不能再進入系統，除非再次

登錄。

A用戶表中用戶有限。

登錄

■主要目的

＞通過核實該用戶的注冊名及口令來檢查該用戶

使用系統的合法性。

■實現

A輸入注冊用戶名。

＞系統將注冊用戶名與用戶表中的注冊名比較。

A若用戶名正確，則輸入用戶口令。

A口令正確，則登錄成功。

A用戶可使用系統。

產它措施

■規定用戶定期修改口令

■限定用戶的終端

■限定用戶的上機時間

注冊用戶表用戶2表

用戶1用戶名

用戶2口令

用戶3上機時間

終端號

■系統級安全管理

貨戶級安全管理

■目錄級安全管理

■用戶級安全管理■文件級安全管理