11. 檔案系統實作 (Implementing File Systems)

Implementing File Systems

 

※目的:

    為使用者或是作業系統本身提供大量的資料儲存空間

 

  • 档案系统基本概念
  • 檔案系统特点

 

 

 档案系统基本概念

 

檔案:檔案是一组赋名的相关联字符流的集合,或者是相关联记录 (一个有意义的信息单位)的集合。

 

檔案包括两部分:

 

檔案体:檔案本身的信息;

 

檔案说明:檔案存储和管理信息;如:檔案名、檔案内部标识、檔案存储地址、访问权限、访问时间等;

 

檔案系统:作业系统中与管理檔案相关的软件和数据称为檔案系统。即:檔案管理软件和被管理对象。

 

檔案系统功能:它负责为用户建立檔案,撤消、读写、修改和复制檔案,还负责完成对檔案的按名存取和进行存取控制。

 

目录:是由檔案说明组成的用于檔案检索的特殊檔案。

 

 

 

檔案系统特点

 

1.友好用户接口,用户只对檔案进行操作,而不管檔案结构和存放的物理位置。

 

2.对檔案按名存取,对用户透明。

 

3.某些檔案可以被多个用户或进程共享。

 

4.檔案系统大都使用磁盘、磁带和光盘等大容量存储器作为存储介质,因此,可存储大量信息。

 

 

 

檔案的分类

 

1、按檔案的性质和用途分类:

 

2、按檔案的组织形式分类:

 

3、按其他方法分类:



檔案逻辑结构(檔案的组织)

 什么是檔案逻辑结构? 是指从用户观点出发讨论檔案内部的逻辑结构(logical structure)或用户访问模式;檔案逻辑结构是用户可见的结构,是用户可以直接处理的数据结构,与物理存储无关。

檔案存取方法

 

三种檔案存取方法

 

  • 顺序存取
  • 随机存取
  • 按键存取(直接存取)

 

顺序存取:是按照檔案的逻辑地址顺序存取。

 

随机存取:随机存取法允许用户根据记录编号来存取文件的任一记录,或者是根据存取命令把读写指针移到欲读写处来读写。

 

按键存取:檔案的存取是根据给定的键或记录名进行的。按键存取法首先搜索到要进行存取的记录的逻辑位置,再将其转换到相应的物理地址后进行存取.

 

檔案存储设备

 

1、顺序存储设备:如磁带

特点:只适合顺序存取。连续文件。 优点:容量大;顺序存取速度快

 

2、直接存取设备:如磁盘,光盘等

特点:适合连续檔案、串联檔案、索引檔案 、适合直接存取(按键存取.随机存取)

 

 

檔案存取控制

 

檔案系统存取验证模块的功能:

 

1.对于拥有读、写或执行权限的用户, 应让其对檔案进行相应的操作.

 

2.对于没有拥有读、写或执行权限的用户,应禁止他们对檔案进行相应的操作.

 

3.应防止一个用户冒充其他用户对檔案进行存取。

 

4.应防止拥有存取权限的用户误用檔案。

 

※存取效率設計的考量?

1.在主記憶體與磁碟之間的資料傳輸都是以區塊作為存取的基本單位。

2.大部分的檔案系統都會將數個區塊集合成一個磁簇,並以磁簇   (cluster)為單   位進行檔案資料的存    取。

※磁碟主要可分為磁盤讀寫頭兩大部分:

   – 磁盤中的磁軌是用來儲存資料。
   – 讀寫頭是用來在磁盤上讀取或是寫入資料。

←檔案存取步驟

解說如下:

步驟1(應用程式):行程發出讀取檔案的需求,並提供檔案路徑

步驟2(邏輯檔案系統):測試使用者對於檔案存取要求的權限

步驟3(檔案組織模組):將邏輯檔案的路徑轉換為磁碟機的體區塊位置

步驟4(基本檔案系統):對磁碟機進行讀取實體區塊的要求

步驟5(I/O控制):進行實際的 I/O 控制

步驟6(裝置):從儲存裝置中實際讀出資料

 

 

 File-System Structure

1.設備驅動程式(Device driver):負責啟動該設備上的I/O操作,處理I/O請求的完成。

2.基本檔系統(I/O control):處理與磁片或磁帶交換的數據塊。

   注重的是這些塊在外存設備中的位置,而並不知道該檔所涉及的數據或結構的內容。

3.基本I/O管理程式(basic file system):負責所有檔I/O的開始或結束。選擇執行檔的I/O設備,

   外存的分配,I/O緩衝區的指定

4.file-organization module:為了實現用戶對檔的按名存取,系統要對目錄進行查詢,

   找出該檔的檔控制塊或者索引節點,進而找到該檔的物理地址。

5.邏輯I/O(logical file system):使用戶和應用程式能夠訪問到記錄。

   物理I/O層處理的是數據塊,邏輯I/O處理的是檔記錄。它提供一種通用的記錄I/O的能力。

6.訪問方法層(application programs) :與用戶最近的一層。在應用程式和文件系統及保存數據的設備

   之間提供了一種標準介面。不同的訪問方法反映出不同的檔結構和訪問數據的不同方法。

 

Virtual File Systems

1.它藉由定義一項乾淨的VFS介面可將檔案系統的一般操作和製作方式分開。在同一台機器上可能其有

   不同製作VFTS介面的方式,使得局部架設的不同檔案可允許透明的存取。

2.VFS對獨一無二的網路檔案提供一個機制-

   ●VFS是基於一種稱為vnode的檔案結構

   ●vnode包含一項對於整體網路之檔案是獨一無二的數值指示器。

   ●整體系統的獨特性對於網路檔案系統的支援是必要的。

   ●核心為每一個工作的節點(檔案或目錄)維護一份vnode結構。

 

 

開啟檔案表

 

檔案系統要進行檔案存取的動作
– 到目錄結構中搜尋指定的檔案
– 開啟並記錄在一個開啟檔案表中
• Linux 系列的作業系統
– 每個被開啟的檔案會有一個相對應的檔案描述器
(file descriptor)
• Windows 中有類似檔案描述器的功能
• 檔案處理器(file handler)

當資料有所更改時
– 先在此開啟檔案表中進行修改,待檔案正常關閉
之後,才會將這些資訊寫入磁碟中。
• 開啟檔案表相關資訊
– 檔案名稱、存取權限、存取日期以及檔案指標等

 

 

共享檔案


– 一個檔案可能會被鏈結在兩個以上的目錄。
– 目錄D 可以同時被目錄A 及B 所鏈結。


• 任一個鏈結到此共享檔案的目錄中將此檔案刪
除時,不會將此共享檔案真正地從磁碟實體區
塊中刪除,而只是將此計數減1 。(ln指令)
• 當計數等於0,才將共享檔案刪除。

 檔案系統製作(implement their functions)

1. 一個啟動控制區段 (boot control block)可能包含作業系統需要的資訊以便將作業系統從該分割區啟動。

    如果磁碟沒有包含作業系統,啟動控制區段可能是空的。通常它是分割區的第一個區段。在

    UFS(Unixfile System)中,此區段稱為啟動區段,在NTFS中,它是分割區啟動磁區。


2. 一個卷區控制區段(volume control block)包含卷(或分割區)的詳細資料, 例如此分割區的區段數目、大

    小、未使用區段的數目、未使用區段的指 標、未使用FCB(File Control Block)數目與指標。在UFS中稱

    為超級區段;在NTFS稱為儲存主檔案表(master file table)。


3. 目錄結構被用在組織檔案。在UFS中,其中包含了檔案名稱和連接的inode數字。在NTFS中儲存在主檔

    案表。


4. FCB包含許多檔案的細節,其中包括了: 檔案允許權、所有權、大小和資料 區段的位置。在UFS中這稱

    為inode。在NTFS中資訊是儲存在主檔案表中,主檔案表使用關連式資料庫結構,一個檔案佔用一列。

 

 

分割和安裝( Partitions and Mounting)

1.根分割區(root partition)包含作業系統核心和其它系統檔案,它在啟動時被安裝(mounted)。

2.成功的安裝動作中,作業系統藉由要求裝置驅動程式讀取裝置目錄,並且驗證目錄中有所期望的格式

   來完成。如果格式不是有效,分割區必須做一致性檢查,並且有可能的話做修正。最後,作業系統在

   它的記憶體中之安裝表格記錄檔案系統已安裝,和此檔案系統的型態。

檔案目錄實作(Directory Implementation)

製作目錄結構時,必須考慮到存取效率與空間使用率的問題:
• 較常用的方法

   – 線性串列(linear list)

   – 雜湊表格(hash table)

   – 線性串列(linear list)

1.將所有檔案以及子目錄都串連起來。

2.實作上比較容易,但不是很有效率。

3.增加檔案的搜尋效率

   – 利用 B 樹或 B+ 樹來實作。

   – 或利用多方搜尋(Multi-Way Search)的方式來搜尋檔案 。

4.製作一個目錄最簡單的方法是使用一個線性串列的檔名,並以指標指向資料區段。這種方法很容易寫

   程式但執行上很浪費時間。

5.線性串列所組成的目錄進入點之真正缺點在於線性尋找檔案。目錄資料經常的被用到,較慢的存取做

   法會被使用者注意到。

6.確保串列維持成排序狀態的要求也可能使新增和刪除檔案變複雜,因為必須移動大量目錄資訊才能維

   持排序的目錄。

7.一個更複雜的樹狀資料結構 (例如B-tree)在這裹可能會有幫助。排序串列的優點是不需要分別的排序

   步驟就可以產生一個已經排序的目錄串列。

   – 雜湊表格(hash table)

1.曾經用在檔案目錄的資料結構是雜亂表格


2.在這種方法中,一個線性串列儲存目錄的進入點,但同時也使用了一個雜亂方法的資料結構。雜亂表

   格從檔名計算出一個數值,並且傳回一個指標給線性串列中的檔名。因此它可以大量的降低目錄搜

   時間。

3.雜湊函數輸入值:檔案名稱

4.雜湊函數輸出值:某個數值範圍內的固定值

5. 搜尋速度較線性串列快得多

6.碰撞(collision )

   – 利用雜湊函數對不同檔名所產生的數值重複

   – 解決方法

7. 鏈結串列將所有雜湊數值相同的檔案都儲存在這個

    鏈結串列上

 

 

 

檔案配置方法(Allocation Methods)

1.檔案配置時,必須考慮的重點

   – 磁碟空間的有效利用

   – 檔案能否被快速地存取

2.常用的三種磁碟空間的配置方法(96nttu6, 94tpu5)

   – 連續式配置 (contiguous allocation)

   – 鏈結串列式配置(linked list allocation)

   – 索引式配置(indexed allocation)

連續式配置(contiguous allocation)

  • 搜尋適合可用空間有下列幾種常用的方法
  • 連續式配置的主要問題

1.搜尋適合可用空間有下列幾種常用的方法:
    – 最先適合(first fit)

    – 最佳適合(best fit)

    – 最差適合(worst fit)

n.從邏輯到物理的映射:

訪問 Block  = Q + starting address
位移 block = R

2. 連續式配置的主要問題

    – 搜尋可用空間的問題

    – 磁碟空間的浪費問題 因多次的使用與歸還產生

    – 外部斷裂磁碟重組 

    – 內部斷裂因以磁簇為基本單位為32k而只用1k

 

3.連續分配法需要令每個檔案佔用一組磁碟上的連續位址。磁碟位址定義了一個線性的磁碟上排列次

   序。此時的順序 (假設只有一個工作對磁碟做存取),在存取b區段之後存取b+1區段時一般不需要移

   動磁頭。若是要移動磁頭 (由一磁柱的最後一個區段移至另一磁柱的第一區段),也只是移動一條磁軌

   而已。

4.存取連續分配檔案的尋找次數將可達到最小,且搜尋時間亦為最短 (即最終需要搜尋時)。

   IBM的VM/CMS作業系統使用連續式分配,因為此方式提供較好的效率。

5.預先分配其空間可能是沒有效率。對一個長期成長緩慢的檔案而言,必須為其最後大小分配到足夠的

   空間,縱使大部份的空間長久都沒有用到。所以最後檔案有大量的內部斷裂。

      

                 鏈結串列式配置(linked list allocation)

n.每個檔是磁片塊的鏈表:塊可能分散在磁片上的任何地方

n.映射(Mapping)

訪問 block 要的地址塊的鏈接鏈塊代表該檔

位移 block = R + 1

1.優點

    – 不會有外部斷裂問題

    – 建立新檔案時並不需同時就宣告檔案大小

2. 缺點

    – 檔案只能循序存取

    – 可靠度的問題

       • 若某個檔案的一個指標被破壞,整個檔案就無法再被存取

       • 可利用雙向鏈結串列(double linked list)來解決

3.最大的問題是只能在循序存取檔案有效地使用。若要找出檔案第i區段,須由該檔案的起點開始並且循

   著指標找下去,直到找到第i區段為止。每次對指標的存取都需要做磁碟讀入。無法提供直接存取的能

   力。

4. 鏈接分配的另一項缺點就是指標本身所要佔用的空間。如果一個指標就佔用一個512位元組區段中的

    4個位元組,那麼磁碟空間的百分之0.78被利用在指標上了,而不是用於存放資料。每個檔案就需要

    更多的空間。

5. 更嚴重地是可信度的問題。因為檔案是由散佈在磁碟中的指標鏈接起來,一旦有一個指標錯了或被破

    壞,作業系統軟體的錯誤或是硬碟上的損壞都會造成指標錯誤指向

              磁盤空間的鏈路分配

                   檔案配置表格

索引式配置(indexed allocation)

n.Indexed allocation(每个文件都有自己的索引块的指针数据块)

Logical view

n.需要索引表

n.随机存取

n.動態訪問沒有外部碎片,但索引塊的有

n.邏輯到物理的映射檔的最大大小為256 k位元組和512位元組的塊大小。我們只需要1塊索引表

Q = displacement into index table
R = displacement into block

n.邏輯到物理的映射檔無限長度 (block size of 512 words)

n.Linked scheme – Link blocks of index table (no limit on size)

Q1 = block of index table
R1 is used as follows:

Q2 = displacement into block of index table

R2 displacement into block of file

二级索引(4K blocks could store 1,024 four-byte pointers in outer index -> 1,048,567 data blocks and file size of up to 4GB)

Q1 = displacement into outer-index
R1 is used as follows:

Q2 = displacement into block of index table
R2 displacement into block of file
 

1.解決鏈結串列式配置的無法隨機存取的問題

2. 所有的區塊指標都集中起來存儲存在一個固定的索引區塊(indexed block)中(編號24)

3. "-1"代表整個檔案結束的符號

4.用鏈結串列式配置可解決外部斷裂和連續分配必須做檔案大小宣告的問題。但是,因缺乏一個FAT,

   鏈接分配無法使用直接存取,因為檔案的各個區段散佈在磁碟中。更重要的是指向各區段的指標也是

   散佈在整個磁碟中而且需要依序取出。索引分配把所有的指標都集中起來放在一個地方————索引

   區段

 

5.適度地控制索引區塊的大小,有下列幾種方法

   – 鏈結索引

   – 多層索引

   – 組合索引(如圖)

索引式配置(Indexed Allocation )– Mapping

                 Mapping

 

 

一致性的檢查(Consistency checking)

• 一部份的目錄資料保存在主記憶體(快取)以加速

  存取。在主記憶體上的目錄資料通常比相對應存

  放在磁碟上的資料要新,因為快取的目錄資訊在

  更新之後並不需要馬上寫入磁碟中。


• 考慮電腦毀損的可能結果。在這種情況下,開啟

  檔案的表格通常會遺失,因此任何在此目錄所開

  啟檔案的改變也跟著不見。


• 這種事件可能造成檔案系統成為不一致的狀態:

  有些檔案的實際狀態和目錄結構所描述的不一致。

  通常,在重新開機時會執行一個特殊的程式來檢

  查並校正磁碟的不一致。(不正常關機時會做的事)

 

一致性

 • 要確認檔案系統的一致性

     – 建立兩個包含所有區塊的表格:已使用、可使用

     – 檢查檔案配置以及可用空間的區塊記錄

 • 正確的區塊檢查結果表

 0   1   0   0   1   1   1   0   1   0   0   0   1   1   0   1  使用中區塊

 1   0   1   1   0   0   0   1   0   1   1   1   0   0   1   0  未使用區塊

 1   2   3   4   5   6   7   8   9  10 11 12 13 14  15 16

 

 

 

 一致性

 • 錯誤的區塊檢查結果表(重複指派與未指派) 0

     歸還可用空間,1則將之從可用空間刪除

 • 錯誤的區塊檢查結果表(重複的區塊指派)

     – 編號7被可用空間重複計算重建所有可用空間

     – 編號14被使用空間重複計算一個區塊配給不同檔案?

 

0   1   0   1   1   1   1   0   1   0   0   0   1   1   0   1  使用中區塊

1   0   1   1   0   0   0   1   0   1   0   1   0   0   1   0  未使用區塊

0   1   0   0   1   1   0   0   1   0   0   0   1   2   0   1  使用中區塊

1   0   1   1   0   0   2   1   0   1   1   1   0   0   1   0  未使用區塊

1   2   3   4   5   6   7   8   9  10 11 12 13  14 15 16

 

 

格式化(Format)

  ● 當磁碟使用前必須在每個磁區內寫入一些磁性記號,用以分辨磁軌(Track)及磁區(Sector),這

   個動作稱為格式化(Format)。

  ● 一個空白磁碟經格式化後,它有些空間已經被標記目錄、檔案配置表、置放空間、啟動程式佔用。

格式化時,有下列工作:

  1.在磁碟內產生標記目錄(Volume Table of Content),以建構磁碟之目錄結構。

  2.建立檔案配置表格(File Allocation Table),以記錄那些磁碟空間是未被使用的。

  3.找到無法讀寫的壞區塊(Bad Block),將它記錄到檔案配置表格,以避免再使用到。

  4.建立置換區域(Swap Area),以供記憶體管理系統使用。

  5.如果是開機磁碟,在磁碟啟動磁區(Boot Sector)擺入啟動程式。

UNIX之i-node結構

  ● 索引配置法一次便配置一個區塊當指標,所以它較不連續配置法浪費更多的指標空間。

  ● 任何一個UNIX檔案,均有一個i-node。

 

 

檔案系統與磁碟的關係

● 檔案系統長久使用之後,將使得磁碟內區塊有支離破碎的問題,這時可以使用檔案系統管理工具,來

   進行緊湊空間(Space Compaction)處理。

由於檔案系統是架構在磁碟上,所以為了加快檔案系統處理的時間,通常在主記憶體內會有磁碟快取記

  憶體(Disk Cache),有時也會在磁碟機控制介面(Disk Controller)內加上快取記憶體,以便發揮

  局限性的特性。