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

1.1 文件是什么

• 文件是對磁盤的抽象
• 所謂文件是指一組帶標識（標識即為文件名）的宣吱、在邏輯上有完整意義的信息項的序列。
• 信息項：構成文件內容的基本單位（單個字節(jié)瞳别，或多個字節(jié)）征候，各信息項之間具有順序關系

• 文件內容的意義：由文件建立者和使用者解釋

  
  
  1

1.2 如何設計一個文件系統(tǒng)

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

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

  • 一個文件的組織
  • 如何命名
  • 如何保護文件
  • 可以實施的操作

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

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

1.3 文件系統(tǒng)

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

• 文件系統(tǒng)要完成哪些任務
  1、統(tǒng)一管理磁盤空間畔裕，實施磁盤空間的分配與回收
  2衣撬、實現(xiàn)文件的按名存取：名字空間--映射-->磁盤空間
  3扮饶、實現(xiàn)文件信息的共享具练，并提供文件的保護、保密手段
  4甜无、向用戶提供一個方便使用扛点、易于維護的接口，并向用戶提供有關統(tǒng)計信息
  5岂丘、提高文件系統(tǒng)的性能
  6陵究、提供與IO系統(tǒng)的統(tǒng)一接口

1.4 文件的分類

按文件性質和用途分類（UNIX），一般分為普通文件奥帘、目錄文件铜邮、特殊文件（設備文件）、管道文件寨蹋、套接字

• 普通文件
  即用戶自己建立的文件松蒜，包含了用戶的信息，一般為ASCII或二進制文件

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

• 特殊文件
  字符設備文件：和輸入輸出有關已旧，用戶模仿串行I/O設備秸苗，例如終端、打印機评姨、網(wǎng)卡等难述。
  塊設備文件：磁盤

1.5 文件的邏輯結構

2

1.6 典型的文件邏輯結構與文件存取

• 流式文件：構成文件的基本單位是字符
  文件是有邏輯意義年鸳、無結構的一串字符的集合
• 記錄式文件：文件由若干記錄組成趴久，可以按記錄進行讀寫、查找等操作搔确。每條記錄有其內部結構
• 文件的邏輯結構與文件存取之間的關系
  順序存缺斯鳌（訪問）
  隨機存取：提供讀寫位置（當前位置）膳算。如UNIX的seek操作座硕。

1.7 文件的存儲介質

1.7.1 存儲介質與物理塊

• 典型的存儲介質
  磁盤（包括固態(tài)盤SSD）、磁帶涕蜂、光盤华匾、U盤、......
• 物理塊（塊block机隙、簇cluster）
  信息存儲蜘拉、傳輸、分配的獨立單位
  存儲設備劃分為大小相等的物理塊黍瞧，統(tǒng)一編號

1.7.2 典型的磁盤結構

3

1.7.3 磁盤訪問

一次訪問磁盤的請求：讀寫诸尽、磁盤地址（設備號原杂、柱面號印颤、磁頭號、扇區(qū)號）穿肄，內存地址（源/目）
完成過程由三個動作組成：

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

1.7.4 磁盤空間管理

有關數(shù)據(jù)結構

• 位圖
  用一串二進制位反映磁盤空間中分配使用情況年局，每個物理塊對應一位，分配的物理塊為0咸产，否則為1矢否。
  申請物理塊時，可以在位示圖中查找1的位脑溢，返回對應的物理塊號
  歸還時僵朗，將對應位轉置1。

• 空閑塊表
  將所有空閑塊記錄在一個表中屑彻，即空閑塊表
  主要兩項內容：起始塊號验庙，塊數(shù)

• 空閑塊鏈表
  把所有空閑塊鏈成一個表
  擴展：成組鏈接法

磁盤地址與塊號的轉換

4

成組鏈接法設計思想

5

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

• 當空閑塊數(shù) > 1 , i = L + 空閑塊數(shù)俏扩；
  從i單元得到一個空閑塊號糜工；
  把該塊分配給申請者；
  空閑塊數(shù)減1
• 當空閑塊數(shù) = 1录淡， 取出L + 1單元內容（一組的第一塊號或0）捌木；
  其值 = 0無空閑塊，申請者等待
  其值不等于零嫉戚，把該塊內容復制到專用塊
  該塊分配給申請者刨裆；

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

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

• 當空閑塊數(shù) < 100空閑塊數(shù)加一彬檀；
  j := L + 空閑塊數(shù)
  歸還塊號填入j單元

• 當空閑塊數(shù) = 100帆啃， 則把內存中登記的信息寫入歸還塊中；
  把歸還塊號填入L+ 1單元窍帝；
  將L單元置成1努潘。

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

2.1 文件屬性

• 文件控制塊（File Control Block：FCB）
  為管理文件而設置的數(shù)據(jù)結構坤学，保存管理文件所需的所有有關信息（文件屬性或元數(shù)據(jù)）

• 常用屬性
  文件名疯坤，文件號，文件大小深浮，文件地址压怠，創(chuàng)建時間，最后修改時間飞苇，最后訪問時間菌瘫，保護，口令布卡，創(chuàng)建者雨让，當前擁有者，文件類型羽利，共享計數(shù)宫患，各種標志（只讀、隱藏、系統(tǒng)娃闲、歸檔虚汛、ASCII/二進制、順序/隨機訪問皇帮、臨時文件卷哩、鎖）

• 基本文件操作

  
  
  6

2.2 文件目錄、目錄項與目錄文件

• 文件目錄

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

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

• 目錄項

  • 構成文件目錄的基本單元
  • 目錄項可以是FCB，目錄是文件控制塊的有序集合

2.3 文件目錄結構的演化

7

2.4 與目錄相關的概念

• 路徑名
  絕對路徑名：從根目錄開始
  相對路徑：從當前目錄開始

• 當前目錄/工作目錄

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

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

8

三纯衍、文件的物理結構

文件在存儲介質上的存放方式

主要解決兩個問題：

• 假設一個文件被劃分成N塊栋齿，這N塊在磁盤上是怎么存放的？
• 其地址（塊號或簇號）在FCB中是怎樣記錄的襟诸？

3.1 連續(xù)（順序）結構

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

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

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

• 缺點

  • 文件不能動態(tài)增長，因為可能后面的磁盤空間已經(jīng)被占據(jù)了鹅龄。如果要增長則需要給出預留空間揩慕，但是這樣就導致了浪費或重新分配和移動的開銷。
  • 不利于文件插入和刪除
  • 產(chǎn)生外部碎片：可以使用緊縮技術進行整理

3.2 鏈接結構

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

  10
  
  說明：在FCB中我們只需要給出第一塊的塊號即可拴鸵。

• 優(yōu)點

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

• 缺點

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

于是我們可以對此種結構進行某種改造：文件分配表FAT

3.3 文件分配表（FAT）

11

3.4 索引結構

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

那索引表應該存放在何處俺亮？
這里必須知道每個文件的索引表長度是不一樣的，于是不能存放在FCB中疟呐，因為FCB是固定大小的脚曾。于是我們在FCB中只記錄索引表的地址。

12

• 優(yōu)點
  保持了鏈接結構的優(yōu)點囤踩，又解決了其缺點

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

• 缺點

  • 較多的尋道次數(shù)和尋道時間
  • 索引表本身帶來了系統(tǒng)開銷堵漱，如：內存、磁盤空間涣仿、存取時間

• 組織方式
  問題：索引表很大勤庐，需要多個物理塊存放時怎么辦？

  • 1好港、鏈接方式
    一個盤塊存一個索引表愉镰，多個索引表鏈接起來
  • 2、多級索引方式
    將文件的索引表地址放在另一個索引表中
  • 3钧汹、綜合模式
    直接索引方式與間接索引方式結合

• 多級索引與綜合模式
  

  13
  
  說明：圖上部分是多級索引模式丈探，此模式中頂級索引表中都記錄的是次級索引表地址。而在圖下部分則是綜合模式拔莱，頂級索引表中一部分記錄的是直接的物理塊碗降，而另一部分是記錄的次級索表塊地址，即一部分是直接尋址塘秦，一部分是間接尋址讼渊。

3.5 UNIX的三級索引結構

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

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

• 問題：采用這種結構仇轻，一個文件最大可以達到多少個物理塊

  
  
  14

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

4.1 概述

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

• 磁盤上
  如何啟動操作系統(tǒng)叶组？
  磁盤是怎樣管理的拯田？怎樣獲取磁盤的有關信息？
  目錄文件在磁盤上怎么存放甩十？普通文件在磁盤上怎么存放船庇？

• 內存中
  當進程使用文件時，操作系統(tǒng)是如何支持的侣监？
  文件系統(tǒng)的內存數(shù)據(jù)結構

4.2 相關術語

• 磁盤分區(qū)
  把一個物理磁盤的存儲空間劃分為幾個相互獨立的部分鸭轮，稱為分區(qū)

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

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

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

4.3 磁盤上的內容

15

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

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

16

4.5 內存中所需的數(shù)據(jù)結構（以UNIX為例）

17

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

5.1 文件目錄檢索

訪問一個文件-->兩步驟

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

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

• 問題：如何加快目錄檢索？
• 一種解決方案
  目錄項分解法：即把FCB分成兩部分
  • 符號目錄項：文件名渠啤，文件號
  • 基本目錄項：除文件名外的所有字段
    
    18
    
    說明：每個方格表示目錄文件（由目錄項組成）添吗，每個橢圓表示普通文件。如何我們采用目錄項分解法，于是符號目錄項中的內容就特別簡單僵腺，此時目錄項就變成了符號目錄項；基本目錄項保存在了磁盤的專用區(qū)域壶栋。
• 好處
  假設一個FCB占48個字節(jié)辰如，物理塊大小512字節(jié)。符號目錄項占8字節(jié)（文件名6字節(jié)贵试，文件號2字節(jié)）琉兜，基本目錄項占48-5 = 42字節(jié)。
  這里給出一個目錄文件有128個目錄項毙玻，在分解前則需要13個物理塊豌蟋，分解后符號目錄項占2塊，基本目錄項占11塊桑滩∥嗥＃總塊數(shù)是不變的，但是查找一個文件的平均訪問磁盤的次數(shù)分解前為(1+13)/2=7次运准，分解后為(1+2)/2 + 1 = 2.5次幌氮。于是就提高了文件檢索的速度。

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

• FCB= 目錄項 +i節(jié)點
• 目錄項：文件名 +i節(jié)點號
• 目錄文件由目錄項構成
• i節(jié)點：描述文件的相關信息
• 每個文件由一個目錄項该互、一個i節(jié)點和若干磁盤塊構成
  
  19
  
  說明：上圖是UNIX系統(tǒng)的文件布局。下面看如何查找一個文件
  
  20
  
  說明：要查找的文件為/usr/ast/mbox听哭，根目錄文件中一個點表示本目錄的目錄項慢洋，兩個點表示父目錄的目錄項，每個目錄項都包含文件名和i節(jié)點號陆盘。從i節(jié)點中可以知道這個文件的第一塊存放在128這個位置普筹，于是我們讀取usr中的內容，從這個目錄中去找ast這個文件隘马，以此類推太防。