一、文件與文件系統(tǒng)

1.1 文件是什么

• 文件是對(duì)磁盤的抽象
• 所謂文件是指一組帶標(biāo)識(shí)（標(biāo)識(shí)即為文件名）的、在邏輯上有完整意義的信息項(xiàng)的序列。
• 信息項(xiàng)：構(gòu)成文件內(nèi)容的基本單位（單個(gè)字節(jié)，或多個(gè)字節(jié)），各信息項(xiàng)之間具有順序關(guān)系

• 文件內(nèi)容的意義：由文件建立者和使用者解釋

  
  
  1

1.2 如何設(shè)計(jì)一個(gè)文件系統(tǒng)

這里先看文件管理的需求：

• 從用戶角度
  文件系統(tǒng)是如何呈現(xiàn)在用戶面前：

  • 一個(gè)文件的組織
  • 如何命名
  • 如何保護(hù)文件
  • 可以實(shí)施的操作

• 從操作系統(tǒng)角度：怎樣組織、管理文件

  • 文件的描述、分類
  • 文件目錄的實(shí)現(xiàn)
  • 存儲(chǔ)空間的管理
  • 文件的物理地址
  • 磁盤實(shí)際運(yùn)作方式（與設(shè)備管理的接口）
  • 文件系統(tǒng)的性能

1.3 文件系統(tǒng)

• 操作系統(tǒng)中統(tǒng)一管理信息資源的一種軟件，管理文件的存儲(chǔ)、檢索、更新，提供安全可靠的共享和保護(hù)手段，并且方便用戶使用

• 文件系統(tǒng)要完成哪些任務(wù)
  1、統(tǒng)一管理磁盤空間，實(shí)施磁盤空間的分配與回收
  2、實(shí)現(xiàn)文件的按名存?。好挚臻g--映射-->磁盤空間
  3、實(shí)現(xiàn)文件信息的共享，并提供文件的保護(hù)、保密手段
  4、向用戶提供一個(gè)方便使用、易于維護(hù)的接口，并向用戶提供有關(guān)統(tǒng)計(jì)信息
  5、提高文件系統(tǒng)的性能
  6、提供與IO系統(tǒng)的統(tǒng)一接口

1.4 文件的分類

按文件性質(zhì)和用途分類（UNIX），一般分為普通文件、目錄文件、特殊文件（設(shè)備文件）、管道文件、套接字

• 普通文件
  即用戶自己建立的文件，包含了用戶的信息，一般為ASCII或二進(jìn)制文件

• 目錄文件
  管理文件系統(tǒng)的系統(tǒng)文件

• 特殊文件
  字符設(shè)備文件：和輸入輸出有關(guān)，用戶模仿串行I/O設(shè)備，例如終端、打印機(jī)、網(wǎng)卡等。
  塊設(shè)備文件：磁盤

1.5 文件的邏輯結(jié)構(gòu)

2

1.6 典型的文件邏輯結(jié)構(gòu)與文件存取

• 流式文件：構(gòu)成文件的基本單位是字符
  文件是有邏輯意義、無(wú)結(jié)構(gòu)的一串字符的集合
• 記錄式文件：文件由若干記錄組成，可以按記錄進(jìn)行讀寫、查找等操作。每條記錄有其內(nèi)部結(jié)構(gòu)
• 文件的邏輯結(jié)構(gòu)與文件存取之間的關(guān)系
  順序存?。ㄔL問(wèn)）
  隨機(jī)存?。禾峁┳x寫位置（當(dāng)前位置）。如UNIX的seek操作。

1.7 文件的存儲(chǔ)介質(zhì)

1.7.1 存儲(chǔ)介質(zhì)與物理塊

• 典型的存儲(chǔ)介質(zhì)
  磁盤（包括固態(tài)盤SSD）、磁帶、光盤、U盤、......
• 物理塊（塊block、簇cluster）
  信息存儲(chǔ)、傳輸、分配的獨(dú)立單位
  存儲(chǔ)設(shè)備劃分為大小相等的物理塊，統(tǒng)一編號(hào)

1.7.2 典型的磁盤結(jié)構(gòu)

3

1.7.3 磁盤訪問(wèn)

一次訪問(wèn)磁盤的請(qǐng)求：讀寫、磁盤地址（設(shè)備號(hào)、柱面號(hào)、磁頭號(hào)、扇區(qū)號(hào)），內(nèi)存地址（源/目）
完成過(guò)程由三個(gè)動(dòng)作組成：

• 尋道（時(shí)間）：磁頭移動(dòng)定位到指定磁道
• 旋轉(zhuǎn)延遲（時(shí)間）：等待指定扇區(qū)從磁頭下旋轉(zhuǎn)經(jīng)過(guò)
• 數(shù)據(jù)傳輸（時(shí)間）：數(shù)據(jù)在磁盤與內(nèi)存之間的實(shí)際傳輸

1.7.4 磁盤空間管理

有關(guān)數(shù)據(jù)結(jié)構(gòu)

• 位圖
  用一串二進(jìn)制位反映磁盤空間中分配使用情況，每個(gè)物理塊對(duì)應(yīng)一位，分配的物理塊為0，否則為1。
  申請(qǐng)物理塊時(shí)，可以在位示圖中查找1的位，返回對(duì)應(yīng)的物理塊號(hào)
  歸還時(shí)，將對(duì)應(yīng)位轉(zhuǎn)置1。

• 空閑塊表
  將所有空閑塊記錄在一個(gè)表中，即空閑塊表
  主要兩項(xiàng)內(nèi)容：起始?jí)K號(hào)，塊數(shù)

• 空閑塊鏈表
  把所有空閑塊鏈成一個(gè)表
  擴(kuò)展：成組鏈接法

磁盤地址與塊號(hào)的轉(zhuǎn)換

4

成組鏈接法設(shè)計(jì)思想

5

成組鏈接法：分配算法
分配一個(gè)空閑塊
查L單元（空閑塊數(shù)）

• 當(dāng)空閑塊數(shù) > 1 , i = L + 空閑塊數(shù)；
  從i單元得到一個(gè)空閑塊號(hào)；
  把該塊分配給申請(qǐng)者；
  空閑塊數(shù)減1
• 當(dāng)空閑塊數(shù) = 1， 取出L + 1單元內(nèi)容（一組的第一塊號(hào)或0）；
  其值 = 0無(wú)空閑塊，申請(qǐng)者等待
  其值不等于零，把該塊內(nèi)容復(fù)制到專用塊
  該塊分配給申請(qǐng)者；

把專用塊內(nèi)容讀到內(nèi)存L 開(kāi)始的區(qū)域。

成組鏈表法：回收算法
歸還一塊
查L單元的空閑塊數(shù)

• 當(dāng)空閑塊數(shù) < 100空閑塊數(shù)加一；
  j := L + 空閑塊數(shù)
  歸還塊號(hào)填入j單元

• 當(dāng)空閑塊數(shù) = 100， 則把內(nèi)存中登記的信息寫入歸還塊中；
  把歸還塊號(hào)填入L+ 1單元；
  將L單元置成1。

二、文件控制塊和文件目錄

2.1 文件屬性

• 文件控制塊（File Control Block：FCB）
  為管理文件而設(shè)置的數(shù)據(jù)結(jié)構(gòu)，保存管理文件所需的所有有關(guān)信息（文件屬性或元數(shù)據(jù)）

• 常用屬性
  文件名，文件號(hào)，文件大小，文件地址，創(chuàng)建時(shí)間，最后修改時(shí)間，最后訪問(wèn)時(shí)間，保護(hù)，口令，創(chuàng)建者，當(dāng)前擁有者，文件類型，共享計(jì)數(shù)，各種標(biāo)志（只讀、隱藏、系統(tǒng)、歸檔、ASCII/二進(jìn)制、順序/隨機(jī)訪問(wèn)、臨時(shí)文件、鎖）

• 基本文件操作

  
  
  6

2.2 文件目錄、目錄項(xiàng)與目錄文件

• 文件目錄

  • 統(tǒng)一管理每個(gè)文件的元數(shù)據(jù)，以支持文件名到文件物理地址的轉(zhuǎn)換
  • 將所有文件的管理信息組織在一起，即構(gòu)成文件目錄

• 目錄文件
  將文件目錄以文件的形式存放在磁盤上

• 目錄項(xiàng)

  • 構(gòu)成文件目錄的基本單元
  • 目錄項(xiàng)可以是FCB，目錄是文件控制塊的有序集合

2.3 文件目錄結(jié)構(gòu)的演化

7

2.4 與目錄相關(guān)的概念

• 路徑名
  絕對(duì)路徑名：從根目錄開(kāi)始
  相對(duì)路徑：從當(dāng)前目錄開(kāi)始

• 當(dāng)前目錄/工作目錄

• 目錄操作
  創(chuàng)建目錄、刪除目錄等等

2.4 目錄文件之間的關(guān)聯(lián)

8

三、文件的物理結(jié)構(gòu)

文件在存儲(chǔ)介質(zhì)上的存放方式

主要解決兩個(gè)問(wèn)題：

• 假設(shè)一個(gè)文件被劃分成N塊，這N塊在磁盤上是怎么存放的？
• 其地址（塊號(hào)或簇號(hào)）在FCB中是怎樣記錄的？

3.1 連續(xù)（順序）結(jié)構(gòu)

• 文件的信息存放在若干連續(xù)的物理塊中
  

  9
  
  在上圖a中，存放者多個(gè)連續(xù)的文件，在b中有些磁盤空間被還回來(lái)了。如果有些塊太小，可能就不能再利用了。在FCB中我們只需要給出文件塊的首地址和塊數(shù)即可。

• 優(yōu)點(diǎn)
  簡(jiǎn)單
  支持順序存取和隨機(jī)存取
  所需的磁盤尋道次數(shù)和尋道時(shí)間最少
  可以同時(shí)讀入多個(gè)塊，檢索一個(gè)塊也很容易

• 缺點(diǎn)

  • 文件不能動(dòng)態(tài)增長(zhǎng)，因?yàn)榭赡芎竺娴拇疟P空間已經(jīng)被占據(jù)了。如果要增長(zhǎng)則需要給出預(yù)留空間，但是這樣就導(dǎo)致了浪費(fèi)或重新分配和移動(dòng)的開(kāi)銷。
  • 不利于文件插入和刪除
  • 產(chǎn)生外部碎片：可以使用緊縮技術(shù)進(jìn)行整理

3.2 鏈接結(jié)構(gòu)

• 一個(gè)文件的信息存放在若干不連續(xù)的物理塊中，各塊之間通過(guò)指針連接，前一個(gè)物理塊指向下一個(gè)物理塊
  

  10
  
  說(shuō)明：在FCB中我們只需要給出第一塊的塊號(hào)即可。

• 優(yōu)點(diǎn)

  • 提高了磁盤空間的利用率，不存在外部碎片問(wèn)題
  • 有利于文件插入和刪除
  • 有利于文件動(dòng)態(tài)擴(kuò)充

• 缺點(diǎn)

  • 存取速度慢，不適于隨機(jī)存取
  • 可靠性問(wèn)題，如指針出錯(cuò)
  • 更多的尋道次數(shù)和尋道時(shí)間
  • 鏈接指針占用一定的空間

于是我們可以對(duì)此種結(jié)構(gòu)進(jìn)行某種改造：文件分配表FAT

3.3 文件分配表（FAT）

11

3.4 索引結(jié)構(gòu)

• 一個(gè)文件的信息存放在若干個(gè)不連續(xù)物理塊中
• 系統(tǒng)為每個(gè)文件建立一個(gè)專用數(shù)據(jù)結(jié)構(gòu)：索引表，并將這些物理塊的塊號(hào)存放在該索引中。
• 索引表就是磁盤塊地址數(shù)組，其中地i個(gè)條目指向文件的第i塊。

那索引表應(yīng)該存放在何處？
這里必須知道每個(gè)文件的索引表長(zhǎng)度是不一樣的，于是不能存放在FCB中，因?yàn)?code>FCB是固定大小的。于是我們?cè)?code>FCB中只記錄索引表的地址。

12

• 優(yōu)點(diǎn)
  保持了鏈接結(jié)構(gòu)的優(yōu)點(diǎn)，又解決了其缺點(diǎn)

  • 既能順序存取，又能隨機(jī)存取
  • 滿足了文件動(dòng)態(tài)增長(zhǎng)、插入刪除的要求
  • 能充分利用磁盤空間

• 缺點(diǎn)

  • 較多的尋道次數(shù)和尋道時(shí)間
  • 索引表本身帶來(lái)了系統(tǒng)開(kāi)銷，如：內(nèi)存、磁盤空間、存取時(shí)間

• 組織方式
  問(wèn)題：索引表很大，需要多個(gè)物理塊存放時(shí)怎么辦？

  • 1、鏈接方式
    一個(gè)盤塊存一個(gè)索引表，多個(gè)索引表鏈接起來(lái)
  • 2、多級(jí)索引方式
    將文件的索引表地址放在另一個(gè)索引表中
  • 3、綜合模式
    直接索引方式與間接索引方式結(jié)合

• 多級(jí)索引與綜合模式
  

  13
  
  說(shuō)明：圖上部分是多級(jí)索引模式，此模式中頂級(jí)索引表中都記錄的是次級(jí)索引表地址。而在圖下部分則是綜合模式，頂級(jí)索引表中一部分記錄的是直接的物理塊，而另一部分是記錄的次級(jí)索表塊地址，即一部分是直接尋址，一部分是間接尋址。

3.5 UNIX的三級(jí)索引結(jié)構(gòu)

在UNIX文件系統(tǒng)中采用的是多級(jí)索引結(jié)構(gòu)（綜合模式）

• 每個(gè)文件的主索引表有15個(gè)索引項(xiàng)（FCB中），每項(xiàng)兩個(gè)字節(jié)
• 前12項(xiàng)直接存放文件的物理塊號(hào)（直接尋址）
• 如果文件大于12塊，則利用第13項(xiàng)指向一個(gè)物理塊，在該塊中存放的是一級(jí)索引表。假設(shè)扇區(qū)大小為512字節(jié)，物理塊等于扇區(qū)塊大小，一級(jí)索引表可以存放256個(gè)物理塊號(hào)
• 對(duì)于更大的文件還可以利用第14項(xiàng)和第15項(xiàng)作為二級(jí)和三級(jí)索引表

• 問(wèn)題：采用這種結(jié)構(gòu)，一個(gè)文件最大可以達(dá)到多少個(gè)物理塊

  
  
  14

四、文件系統(tǒng)的實(shí)現(xiàn)

4.1 概述

• 實(shí)現(xiàn)文件系統(tǒng)需要考慮磁盤上和內(nèi)存中的內(nèi)容布局

• 磁盤上
  如何啟動(dòng)操作系統(tǒng)？
  磁盤是怎樣管理的？怎樣獲取磁盤的有關(guān)信息？
  目錄文件在磁盤上怎么存放？普通文件在磁盤上怎么存放？

• 內(nèi)存中
  當(dāng)進(jìn)程使用文件時(shí)，操作系統(tǒng)是如何支持的？
  文件系統(tǒng)的內(nèi)存數(shù)據(jù)結(jié)構(gòu)

4.2 相關(guān)術(shù)語(yǔ)

• 磁盤分區(qū)
  把一個(gè)物理磁盤的存儲(chǔ)空間劃分為幾個(gè)相互獨(dú)立的部分，稱為分區(qū)

• 文件卷
  磁盤上的邏輯分區(qū)，由一個(gè)或多個(gè)物理塊組成。

  • 一個(gè)文件卷可以是整個(gè)磁盤或部分磁盤或跨盤（RAID）
  • 同一個(gè)文件卷使用同一份管理數(shù)據(jù)進(jìn)行文件分配和磁盤空閑空間管理，不同的文件卷中的管理數(shù)據(jù)是相互獨(dú)立的。
  • 一個(gè)文件卷上包括文件系統(tǒng)信息、一組文件（用戶文件、目錄文件）、未分配空間
  • 塊或簇：一個(gè)或多個(gè)（2的冪次方）連續(xù)的扇區(qū)，可尋址數(shù)據(jù)庫(kù)

• 格式化
  在一個(gè)文件卷上建立文件系統(tǒng)，即建立并初始化用于文件分配和磁盤空閑空間管理的管理數(shù)據(jù)

4.3 磁盤上的內(nèi)容

15

• 引導(dǎo)區(qū)
  包括了從該卷引導(dǎo)操作系統(tǒng)所需的信息，每個(gè)卷（分區(qū)）都有一個(gè)，通常稱為扇區(qū)
• 卷信息
  包括該卷的塊數(shù)、塊大小、空閑塊數(shù)量和指針、空閑FCB數(shù)量和指針等等
• 目錄文件

4.4 磁盤上文件系統(tǒng)的布局

16

4.5 內(nèi)存中所需的數(shù)據(jù)結(jié)構(gòu)（以UNIX為例）

17

五、文件系統(tǒng)實(shí)例（UNIX）

5.1 文件目錄檢索

訪問(wèn)一個(gè)文件-->兩步驟

• 目錄檢索
  用戶給出文件名-->按文件名查找到目錄項(xiàng)/FCB
  根據(jù)路徑名檢索：
  • 全路徑名：從根目錄開(kāi)始
  • 相對(duì)路徑：從當(dāng)前目錄開(kāi)始
• 文件尋址
  根據(jù)目錄想/FCB中文件物理地址等信息，計(jì)算出文件中任意記錄或字符在存儲(chǔ)介質(zhì)上的地址

5.2 目錄文件實(shí)現(xiàn)時(shí)的改進(jìn)

• 問(wèn)題：如何加快目錄檢索？
• 一種解決方案
  目錄項(xiàng)分解法：即把FCB分成兩部分
  • 符號(hào)目錄項(xiàng)：文件名，文件號(hào)
  • 基本目錄項(xiàng)：除文件名外的所有字段
    
    18
    
    說(shuō)明：每個(gè)方格表示目錄文件（由目錄項(xiàng)組成），每個(gè)橢圓表示普通文件。如何我們采用目錄項(xiàng)分解法，于是符號(hào)目錄項(xiàng)中的內(nèi)容就特別簡(jiǎn)單，此時(shí)目錄項(xiàng)就變成了符號(hào)目錄項(xiàng)；基本目錄項(xiàng)保存在了磁盤的專用區(qū)域。
• 好處
  假設(shè)一個(gè)FCB占48個(gè)字節(jié)，物理塊大小512字節(jié)。符號(hào)目錄項(xiàng)占8字節(jié)（文件名6字節(jié)，文件號(hào)2字節(jié)），基本目錄項(xiàng)占48-5 = 42字節(jié)。
  這里給出一個(gè)目錄文件有128個(gè)目錄項(xiàng)，在分解前則需要13個(gè)物理塊，分解后符號(hào)目錄項(xiàng)占2塊，基本目錄項(xiàng)占11塊?？倝K數(shù)是不變的，但是查找一個(gè)文件的平均訪問(wèn)磁盤的次數(shù)分解前為(1+13)/2=7次，分解后為(1+2)/2 + 1 = 2.5次。于是就提高了文件檢索的速度。

六、UNIX文件系統(tǒng)

• FCB= 目錄項(xiàng) +i節(jié)點(diǎn)
• 目錄項(xiàng)：文件名 +i節(jié)點(diǎn)號(hào)
• 目錄文件由目錄項(xiàng)構(gòu)成
• i節(jié)點(diǎn)：描述文件的相關(guān)信息
• 每個(gè)文件由一個(gè)目錄項(xiàng)、一個(gè)i節(jié)點(diǎn)和若干磁盤塊構(gòu)成
  
  19
  
  說(shuō)明：上圖是UNIX系統(tǒng)的文件布局。下面看如何查找一個(gè)文件
  
  20
  
  說(shuō)明：要查找的文件為/usr/ast/mbox，根目錄文件中一個(gè)點(diǎn)表示本目錄的目錄項(xiàng)，兩個(gè)點(diǎn)表示父目錄的目錄項(xiàng)，每個(gè)目錄項(xiàng)都包含文件名和i節(jié)點(diǎn)號(hào)。從i節(jié)點(diǎn)中可以知道這個(gè)文件的第一塊存放在128這個(gè)位置，于是我們讀取usr中的內(nèi)容，從這個(gè)目錄中去找ast這個(gè)文件，以此類推。