作業系統學習筆記：檔案管理-有解無憂

一、概述：

檔案的概念：

什么是檔案？

檔案是在邏輯上具有完整意義的資訊集合，它有一個名字作標識，一個檔案必須要有一個檔案名，用戶利用檔案名訪問檔案，

檔案的基本特征：

——檔案的內容為一組相關資訊，可以是源程式、可執行的二進制代碼程式、待處理的資料、表格、聲音、影像等，

——檔案具有保存性，檔案被保存在如磁盤、磁帶等存盤介質中，其內容可以被長期保存和多次使用，

——檔案可按名存取，每一個檔案擁有唯一的標識名資訊，用戶無需了解檔案所在的存盤介質，

檔案的基本屬性：

檔案系統：

什么是檔案系統？

檔案系統是作業系統中負責管理和存取檔案的程式板塊，也稱為資訊管理系統，

檔案系統的組成：

它由管理檔案所需的資料結構（例如檔案控制塊、存盤分配表等）、相應的管理軟體以及訪問檔案的一組操作所組成，

檔案系統應當具有的五大功能：

——完成檔案存盤空間的管理，

建立檔案時進行檔案存盤空間的分配，在洗掉檔案時進行檔案空間的回收，

——實作檔案名到物理地址的映射，

這種映射對于用戶來講是透明的，用戶不必了解檔案的存放位置和查找方法等，只需要指出檔案名就可以找到相應的檔案，
這一映射是通過在檔案說明部分中檔案的物理地址來實作的，

——實作檔案和目錄的操作管理，

檔案的建立、讀、寫和目錄管理等基本操作是檔案系統的基本功能，
檔案操作管理負責根據各種操作的要求完成各種操作所規定的任務，如從外存中讀出資料，或將資料寫入外存中，

——提供檔案共享能力和安全可靠措施，

檔案共享是指多個用戶可以使用同一檔案，安全是防止檔案被盜竊或破壞，
通常采用多級保護措施來實作檔案的共享與安全，另外，還要提供保證檔案系統的可靠性辦法，

——檔案系統向用戶提供了有關檔案和目錄操作的借口，

檔案的分類：

按檔案的性質和用途分類：

——系統檔案：

該類檔案只允許用戶通過系統呼叫來執行它們，而不允許對其進行修改和讀寫，系統檔案主要由作業系統核心、各種系統應用程式和資料所組成，

——庫檔案：

該類檔案包括允許用戶對其進行讀取、執行，但是不允許對其進行修改的子程式庫，如C語言子程式庫等，

——用戶檔案：

用戶檔案是用戶委托檔案系統保存的檔案，
這類檔案只有檔案的所有者和被授權的用戶才能使用，
用戶檔案主要由源程式、目標程式、用戶資料庫等組成，

按檔案的組織形式分類：

——普通檔案：

既包括系統檔案也包括用戶檔案、庫函式檔案和使用程式檔案，
普通檔案主要是指組織格式為系統中所規定的最一般格式的檔案，也就是平常所說的檔案，

——目錄檔案：

——特殊檔案：

有的系統中，所有的輸入、輸出設備都被看作特殊檔案，
這組特殊檔案在使用形式上與普通檔案相同，如查找目錄、存取操作等，
但是特殊檔案的使用是與設備處理程式密切相關的，系統必須把對特殊檔案的操作轉入到對不同的設備的操作，

按使用和管理情況分類：

——臨時檔案：

它是一種私有資源，使用戶在某次求解問題程序中產生的中間檔案，
這種檔案僅僅保存在磁盤上，在作為“檔案”的外存介質上沒有副本，臨時檔案隨用戶撤離系統而撤離，因此不可共享，

——永久檔案：

這是用戶經常要使用檔案，
這類檔案不僅在磁盤上有檔案副本，且在作為”檔案“的介質上也有一個可用的副本，

——檔案檔案：

僅保存在作為“檔案”用的外存介質上，以備查證和恢復用，

按檔案系統提出的保護級別分類：

——只讀檔案：

只允許用戶對其執行讀操作，對于寫操作，系統將拒絕執行并給出錯誤資訊，

——讀寫檔案：

只允許用戶對其進行讀、寫操作，而拒絕對其執行任何其他的操作，

——不保護檔案：

這類檔案是不加保護措施的檔案，所有用戶都可以對其進行存取等所有操作，

按檔案的資料流向分類：

——輸入型檔案：

這些檔案只能讀，

——輸出型檔案：

這些檔案只能寫入，

——輸入\ 輸出檔案：

這類檔案既可讀又可寫，

檔案的分類還有許多種，但是在檔案系統中比較重要的兩種分類方式是按檔案的邏輯結構和物理結構進行分類，下一節我將仔細介紹！

檔案的操作：

檔案系統不應要求用戶必須了解檔案的物理組織才能使用檔案，而應方便用戶，提供給用戶按其邏輯組織形式來使用檔案，

一個檔案系統至少要提供用戶以下的檔案操作功能：

——建立、洗掉、讀、寫、截斷檔案，檔案換名、打開檔案、關閉檔案、復制檔案（基本操作），

——修改、插入、洗掉資料項操作，

——檔案查找，

——修改檔案屬性：變更檔案主的名字，

檔案型別：

使用形式：主檔案名字 . 擴展檔案名

其中，擴展檔案名部分指出檔案的型別，

有三種型別檔案可以被執行：

二、檔案的結構和存取方式：

檔案的組織結構是指檔案的構造方式，用戶和檔案系統往往從不同的角度對待同一個檔案，

因此對于任何一個檔案都存在兩種形式的結構:

——檔案的邏輯結構：用戶按自己對資訊的使用要求組織檔案，這種檔案是獨立于物理環境而構造的，因此把用戶概念中的檔案稱為檔案的邏輯結構，或稱邏輯檔案，

——檔案的物理結構：又稱為檔案的存盤結構，是指檔案在輔存上的存盤組織形式，這與存盤介質的性質有關，

無論是檔案的邏輯結構還是物理結構，其構造方式都會影響對檔案的處理速度，

檔案的存取方式：

——順序存取：

順序存取是按照檔案的邏輯地址順序存取，

——隨機存取：

隨機存取法允許用戶根據記錄的編號存取檔案的任一記錄，或者是根據存取命令把讀寫指標移到欲讀寫處來讀寫，

——按鍵存取：

按鍵（關鍵字）存取是一種用在復雜檔案系統，特別是資料庫管理系統中的存取方法，

檔案的邏輯結構：

設計檔案系統時，選擇邏輯結構應遵循的原則：

便于修改
應提高檢索效率
使檔案資訊占據最小的存盤空間
便于用戶進行操作

檔案的邏輯結構分類：

——記錄式檔案（有結構檔案）：

記錄式檔案在邏輯上被看成一組連續有序的記錄的集合，每個記錄由彼此相關的域構成，

根據記錄的長度分類：定長記錄檔案、變長記錄檔案，

定長記錄檔案：檔案中所有記錄的長度都是相同的，所有記錄中的各資料項都處在記錄中相同的位置，具有相同的順序及長度，檔案的長度用記錄數目表示，
變長記錄檔案：檔案中各記錄的長度不相同，原因可能是一個記錄中所包含的資料詳數目不同，

記錄式檔案可把檔案中的記錄按各種不同的方式排列，構成不同的邏輯結構，這樣的記錄式檔案可以分為三類：

順序檔案：它是指按照某種順序排列的記錄所構成的檔案，通常是定長記錄檔案，因此能用較快的速度查找檔案的記錄，
索引檔案：通常建立一張索引表，為每一個記錄設定一個表項，以加速對于記錄的檢索速度，索引表本身就是一個定長記錄的順序檔案，從而也就可以方便地實作直接存取，
索引順序檔案：是上述兩種檔案方式的結合，它將順序檔案中的所有記錄分為若干組（譬如50個記錄為一組），并且為順序檔案建立一張索引表，在索引表中為每組中的第一個記錄建立一個索引項，其中含有記錄的鍵值和指向該記錄的指標，

索引順序檔案可能是最為常見的一種邏輯檔案形式，它有效的克服了變長記錄檔案不便于直接存取的缺點，而且所付出的代價也在可接受的范圍之內，

——流式檔案（無結構檔案）：

無結構的流式檔案是相關的有序字符的集合（源程式檔案、目標代碼檔案、檔案檔案等），

——特點是：

流式檔案是指檔案內的資料不再組成記錄，只是依次的一串資訊的集合，
字符是構成檔案的基本單位，
讀取經常按照長度來讀取所需的資訊，也可以使用插入的特殊字符作為分界，
查找困難、管理簡單，

存盤介質：

常用的存盤介質有磁盤、光碟、磁帶、閃存等，

——一盤磁帶、一個磁盤組或一張軟盤都稱為一卷，卷是存盤介質的物理單位，

——塊是存盤介質上連續資訊所組成的一個區域，也叫做物理記錄，塊是記憶體儲器和輔助存盤設備進行資訊交換的物理單位，每次總是交換一塊或整數塊資訊，塊大小要考慮用戶使用方式、資料傳輸效率和存盤設備等因素，不同型別的存盤介質塊的大小常常不同，同一型別介質的塊的大小也可能不同，

檔案的存盤結構密切地依賴于存盤設備的物理特性，存盤設備的特性也決定了檔案的存取方法，

順序存盤設備：

——什么是順序存盤設備？

順序存盤存盤設備是嚴格依賴資訊的物理位置進行定位和讀/寫的存盤設備，順序存盤設備只有在前面的物理塊被訪問之后，才能訪問后續物理塊的內容，

我們以磁帶機為例對順序存盤設備進行相關的介紹！

磁帶機是一種典型的順序存盤設備，

——磁帶上的物理塊沒有確定的物理地址，只是由帶上的物理標志來識別，

——如果帶速高，資訊密度大，且所需塊間隙小的話，則磁帶存取速度和資料傳輸率高，

什么間隙？為什要有它？
塊與塊之間應當留有一定長度的間隙，用于磁帶設備的啟動與停止的緩沖，
間隙是塊之間不記錄用戶代碼資訊的區域，

——磁帶的一個突出優點是物理塊長的變化范圍較大，塊可以很小，也可以很大，

——磁帶作為順序存盤介質，具有存盤容量大、穩定可靠、檔案卷可拆卸、便于保存和塊長變化范圍較大等優點，

直接存盤設備：

——什么是直接存盤設備？

直接存盤設備又叫隨機存盤設備，允許檔案系統直接存取對應存盤介質上的任意物理塊，

我們以磁盤機為例進行直接存盤設備的介紹！

磁盤機是一種典型直接存盤存盤設備，

——各磁盤塊的編號按柱面順序（零號柱面開始,由外向里），每個柱面按磁道順序（從上向下），每個磁道又按扇區順序進行排序，假定用 t 表示每個柱面上的磁道數（磁頭/盤片），用 s 表示每個磁道上的扇區數，則第 i 柱面， j 磁頭，k 扇區所對應的塊號 b 可有如下公式確定：（位置決定塊號）

b= （i×t+j）×s + k

——根據塊號 p 也可確定該塊在磁盤上的位置，每個柱面上有D =s×t個磁盤塊，設M= p/D，N= p%D，于是，第P塊在磁盤上位置為：（塊號確定位置）

柱面號= M= p/D= p/(s×t)
磁頭號=N / s
扇區號=N % s

磁盤機的特性與用途：

——磁盤具有直接讀寫的性質，并且物理塊的大小固定不變，所以在這種介質上可以按照多種物理結構組織資訊，并且不一定要求資訊按邏輯記錄的順序存盤，

——由于定位時間遠遠小于磁帶設備的定位時間，因此廣泛用于資訊存盤，并且作為虛擬存盤器和虛擬設備使用，

——存盤介質的容量逐漸增大，并且有些可像磁帶一樣隨時更換，因而也作為保存檔案材料之用，成為一種高速、大容量、可拆卸的海量存盤器，

檔案的物理結構：

檔案的物理結構直接影響檔案系統的性能，究竟采用哪種存盤結構，需要根據存盤設備型別、應用目標、回應時間和存盤空間等多種因素進行權衡，

磁帶檔案的物理結構：

——磁帶機是一種順序存取的設備，一切組織在磁帶上的檔案都采用順序結構,也就是將一個檔案在邏輯上連續的資訊存放到存盤介質的依次相鄰的塊上，便形成順序結構，磁帶上的每個檔案都有檔案頭標、檔案資訊和檔案尾標三個組成部分，

磁盤檔案的物理結構：

順序檔案/連續檔案：

——定義：將一個檔案中邏輯上連續的資訊存放到磁盤上的依次相鄰的塊上便形成順序結構，這類檔案叫順序檔案，又稱連續檔案，

——優點：順序訪問容易、速度快，

——缺點：要求有連續的存盤空間、必須事先知道檔案的長度，

鏈接檔案：

——定義：順序的邏輯記錄被存放在不連續的磁盤塊上，用指標把這些磁盤塊按邏輯記錄的順序鏈接起來，則形成了檔案的鏈接結構，鏈接結構的檔案稱為“鏈接檔案”或“串聯檔案” ，

——特性：采取離散分配方式，從而消除了外部碎片，故可顯著地提高輔存空間的利用率，且也無需事先知道檔案的長度，磁盤上的所有空閑塊都可以被利用，

——優點：消除了外部碎片、顯著地提高外存空間的利用率、無需事先知道檔案的長度、插入洗掉記錄容易，

——缺點：隱式鏈接，只適合于順序訪問、直接訪問低效、可靠性較差；顯式連接，不能支持高效地直接存取、存放鏈接指標的FAT表會占用較大的記憶體空間，

分類：

隱式鏈接：在每個盤塊中含有一個指向下一個盤塊的指標，

顯式鏈接：把用于鏈接檔案物理塊的指標顯式地存放在外存的一張鏈接表即檔案分配表（FAT）中，

和FAT表相關的計算：假定磁盤有n塊,若2m-1≤n≤2m，則FAT表的每項至少有m位，但多數情況取整位元組倍數，有時取半個位元組倍數，

計算舉例：假定盤塊的大小為1KB，硬碟的大小為500MB，采用顯示鏈接分配方式時，該硬碟共有500K個盤塊，故FAT中共有500K個表項；如果盤塊從1開始編號，為了能保存最大的盤塊號500K，該FAT表項最少需要19個位元位，將它擴展為半個位元組的整數倍后，可知每個FAT表項需20位，即2.5個位元組，因此，FAT需占用的存盤空間的大小為：

2.5×500K=1250KB，

索引檔案：

——定義：為每個檔案分配一個索引塊（用來存放索引的物理塊），把分配給該檔案的所有盤塊號都記錄在該索引塊中，按照這種分配方式存盤的檔案就是索引檔案，

——應用：一級索引、兩級索引或多級索引結構，

——優點：支持直接訪問，且不會產生外部碎片，

——缺點：索引要花費較多的外存空間，

——混合索引分配方式：指將多種不同級的索引分配方式結合而形成的一種分配方式，有效且實用，

相關計算題：索引檔案的檔案最大長度的計算

題目：在UNIX中，其索引結構共有13個地址項，其中10項登記直接地址，1項一級索引，1項二級索引，1項三級索引，假如每個盤塊的大小為4KB，一個盤塊號占用4位元組，計算支持的檔案最大長度是多少，
求解：直接地址項登記檔案10個盤塊，一級索引可登記1K個盤塊，二級索引可登記1K×1K=1M個盤塊，三級索引可登記1K×1K×1K =1G個盤塊，允許檔案長度=1G×4KB十1M×4KB十1K×4KB十40KB≥4TB，

直接檔案（散列/Hash）：

——定義：在直接存取存盤設備上，記錄的關鍵字與其地址之間可以通過某種方式（函式）建立對應關系，利用這種關系實作記錄存取的檔案稱為直接檔案，

——“沖突”問題：地址的總數和記錄的關鍵字之間并不存在一一對應的關系，不同的關鍵字經過變換可能會得到相同的地址，

——解決“沖突”方法：設計出好的變換函式，并且還要求有好的處理沖突的方法，

——優點：存取速度較快，存盤空間不必連續，邏輯記錄與物理記錄之間不存在對應或順序關系，

——缺點：對沖突的處理需要時間和空間的開銷，

設備、檔案、存取方法之間的關系：

三、檔案目錄：

為什么引入檔案目錄？

在現代計算機系統中，通常需要存盤大量的檔案，為了能有效地管理這些檔案，必須對它們加以妥善的組織，以做到用戶只需向系統提供所需訪問檔案的名字，系統就能快速、準確的找到指定檔案，
這主要是以來檔案目錄來實作的，換句話說通過檔案目錄可以將檔案名轉換為改檔案在外存上的物理位置，

個人理解：就像日常生活中你去圖書館，書太多，找起來太費勁，所以才會有圖書目錄供你查詢，

檔案目錄管理應當達到的基本要求：

——實作“按名存取”

用戶只需要提供檔案名，就可以對檔案進行存取，

——提高對目錄的檢索速度

合理地組織目錄結構，可以加快對于目錄的檢索速度，從而加快對于檔案的存取速度，

——檔案共享

在多用戶系統中，應當允許多個用戶共享一個檔案，

——允許檔案重名

系統應當允許不同用戶對于不同檔案用相同的名字，以便用戶按照自己的習慣命名檔案，

檔案控制塊：

概念：

檔案系統在創建每個檔案時為其建立了一個檔案目錄，也稱為檔案說明或檔案控制塊FCB，檔案目錄是為檔案設定的用于檔案描述和檔案控制的資料結構，它與檔案一一對應，它是隨著檔案的建立而誕生，隨著檔案的洗掉而消失，某些內容隨著檔案的使用而動態改變，

檔案控制塊包括的內容：

——有關檔案存取控制的資訊：檔案名、型別、檔案屬性等，

——有關檔案結構的資訊：邏輯結構、物理結構、存盤位置，

——有關檔案管理的資訊：建立日期、修改日期等

檔案目錄結構：

檔案系統把若干個檔案的檔案目錄組織成一個獨立的檔案，這個全部由檔案目錄組成的檔案稱為目錄檔案，

一級目錄結構：

——實作方式：最簡單的檔案目錄，在作業系統中，為每個磁盤設定一張線性表，每個檔案的相關說明資訊占用一個目錄項，

——優點：實作容易、管理簡單、實作了按檔案名存取，

——缺點：搜索范圍寬、不允許檔案重名、難于實作檔案共享，

二級目錄：

——實作方式：第一級為主檔案目錄，用于管理所有用戶的檔案目錄，它的目錄項登記了系統用戶的名字及該用戶檔案目錄的地址，第二級為用戶檔案目錄，它為該用戶的每個檔案保存一登記欄，其內容與一級目錄的目錄項相同，

——優點：實作了對檔案的保密和保護、允許不同用戶使用相同的檔案名、可以實作檔案共享，

多級檔案目錄結構：

——實作方式：主檔案目錄演變為根目錄，根目錄項既可以表示一個普通檔案，也可以是下一級目錄的目錄檔案一個說明項，如此層層類推，形成了一個樹型層次結構，

——優點：解決了檔案重名問題、有利于檔案的分類、便于制定保護檔案的存取權限，有利于檔案的保密，

目錄的查找：即實作“按名存取”，

線性檢索法：

——一級目錄結構采用順序查找法，依次掃描檔案目錄的目錄項，將目錄項中的名字與欲查找的檔案名相比較，

——在多級目錄中，采用絕對路徑和相對路徑的查找方法，使用相對路徑名查找速度要快于絕對路徑，

絕對路徑：由根目錄沿各級子目錄到達該檔案的路徑名，如：E:\BaiduNetdisk\skin\demo.java
相對路徑：就是從當前目錄開始到檔案的路徑名，如：skin\demo.java

——查找舉例：

假設要查找絕對路徑名為\usr\include\user.h的檔案，從根目錄查起，線性檢索查找程序如下：

第一步：從根目錄查起，把根目錄檔案資訊讀到記憶體緩沖區，按給定的路徑名中第一個分量usr依次與緩沖區中每個目錄項比較，若找不到名為usr的目錄項，則繼續讀入根目錄檔案的后續資訊再比較，直到找到usr目錄項或查完根目錄都沒有找到，
第二步：找到usr后，再根據這個目錄項內容把usr目錄檔案資訊讀到記憶體緩沖區，按第一步的程序，查找到include目錄項，
第三步：找到include后，再根據這個目錄項內容把include目錄檔案資訊讀到記憶體緩沖區，按第一步的程序，查找到user.h目錄項，

哈希檢索：

——目錄項資訊存放在一個哈希表中，進行目錄檢索時，首先根據目錄名來計算一個哈希值，然后得到一個指向哈希表目錄項的指標，

——哈希檢索演算法的難點，在于選樣合適的哈希表長度和哈希函式的構造，

其他演算法：

——除了上面的兩種演算法之外，還可以考慮其他演算法，如B+樹，

目錄的改進：目錄檔案只存盤符號目錄資訊

——為何改進？

一個檔案目錄項一般要占用很多空間，這樣會導致目錄檔案往往很大，在查找目錄時，為了找到所需的目錄項，常常要將存放目錄檔案的多個物理塊逐塊讀入記憶體進行查找，這就降低了查找速度，（個人理解：過大，多次調入，查找麻煩）

——如何改進？

為加快目錄查找可采用目錄項分解法，即把目錄項分為兩部分：符號目錄項（包含檔案名以及相應的檔案號）和基本目錄項（包含除了檔案名外檔案控制塊的其余全部資訊），

計算舉例：

假設一個檔案目錄項占48個位元組，符號目錄項占8位元組（檔案名6位元組，檔案號2位元組），基本目錄項占48-6=42位元組，設物理塊大小512位元組，假設目錄檔案有128個目錄項，若不分解目錄項，一個盤塊存放5l2/48 =10目錄項，128個目錄項需要13個盤塊，查找一個檔案的平均訪問的盤塊數：(1+13)/2=7次，

分解后一個盤塊存放5l2/8=64個符號目錄項，128個符號目錄項需要2個盤塊，查找一個檔案的平均訪問的盤塊數：(1+2)/2+1=2.5次，

四、檔案系統及其實作：

檔案系統的定義及其功能：

檔案系統的定義：

檔案系統是作業系統中負責管理和存取檔案的程式模塊，

檔案系統的功能：

打開檔案表：

打開檔案表有什么用？

——為了管理打開的檔案，

系統打開檔案表：

——該“系統打開檔案表”放在記憶體，用于保存已打開檔案的目錄項，此外，還保存檔案號、共享計數、修改標志等等，

用戶打開檔案表：

——每個行程一般都有一個“用戶打開檔案表”，該表的內容有檔案描述符，打開方式、系統打開檔案表入口等等，

用戶打開檔案表與系統打開檔案表之間的關系：

——用戶打開檔案表指向了系統打開檔案表，如果多個行程共享同一個檔案，則多個用戶打開檔案表目對應系統打開檔案表的同一入口，

外存空間的調度：

主要討論直接存盤介質的空間分配，直接存盤介質是分為若干個大小相等的物理塊，并以塊為單位來交換資訊；因此存盤空間管理實質上是空閑塊的組織和管理問題（組織、分配、回收），

空閑塊表法：

——資料結構：

系統為每個磁盤建立一張空閑塊表，表中每個登記項記錄一組連續空閑塊的首塊號和塊數，空閑塊數為“0”的登記項為“空”登記項，

——分配回收演算法：

這種管理方式適合采用順序結構的檔案 ,分配和回收演算法類似記憶體儲器的可變磁區管理方式中采用的最先適應、最優適應和最壞適應演算法，

可變磁區管理方式中采用的最先適應、最優適應和最壞適應演算法，（相關詳細介紹，👈點擊直達！）

空閑鏈表法：

空閑盤塊鏈：

——空閑盤塊鏈以盤塊為基本元素構成一條鏈，

——分配時從鏈首開始，依次摘下適當數目的空閑盤塊分配給用戶，回收時將回收的盤塊依次鏈入空閑盤塊鏈，

——優缺點：分配和回收一個盤塊的程序非常簡單，但是空閑盤塊鏈可能很長，

空閑盤區鏈：

——將磁盤上的所有空閑盤區（每個盤區可包含若干個盤塊）拉成一條鏈，（與空閑塊表相似），

——分配方法與記憶體的動態磁區分配類似，通常采用首次適應演算法，在回收盤區時，同樣也要將與回收區鄰接的空閑盤區與之合并，

——優缺點：分配和回收程序較復雜，但空閑盤區鏈較短，

位示圖法：

——磁盤塊的組織：

根據磁盤總塊數決定位示圖由多少字組成，位示圖中的每一位與一個磁盤塊對應，某位為“1”狀態表示相應塊已被占用，為“0”狀態的位所對應的塊是空閑塊，

一般公式為：塊號=i×位示圖中的字長+j

——磁盤塊的分配：

當有檔案要存放到磁盤上時，查位示圖中為“0”的位，表示對應的磁盤塊空閑可供使用，根據查到的位所在的字號和位號可計算出對應的塊號，同時在該位填上占用標志“1”，（個人理解：查空閑、改標志！）

——磁盤塊的回收：

當洗掉檔案歸還存盤空間時，可以根據歸還塊的塊號推算出在位示圖中的位置：

塊號=柱面號×每個柱面中的塊數+磁頭號×每個磁道的塊數+扇區號
字號=[塊號/位示圖中字長]
位號=塊號mod位示圖中字長

然后把這一位的“1”清成“0”，表示該塊成為空閑塊，

成組鏈接法：

——空閑塊的組織：

把空閑塊分成若干組，每組含有固定數目的空閑磁盤塊；每一組的第一個空閑塊中登記下一組空閑塊的塊號和空閑塊數；余下不足100塊的部分，登記在一個專用塊中，

——空閑塊的分配：

系統初始化時先把專用塊內容讀到記憶體儲器，每分配一塊后把空閑塊數減1，但一組的第一個空閑塊分配之前應把登記在該塊中的下一組的塊號及塊數保存到專用塊中，

分配一個空閑塊的演算法：（假設專用塊的內容已讀到起始地址為L的記憶體區域中）

——空閑塊的回收：

當歸還一塊時，只要把歸還塊的塊號登記到當前組中且空閑塊數加1，如果當前組已滿100塊，則把記憶體中的內容寫到歸還的那塊中，該歸還塊作為新組的第一塊，

歸還一塊的演算法：

五、檔案的使用：

主要操作：

檔案系統與用戶的介面：

第一類是與檔案有關的操作命令或作業控制語言中與檔案有關的陳述句，這些構成了必不可少的檔案系統的人機介面，
第二類是提供給用戶程式使用的檔案類系統呼叫指令，通過這些指令用戶能獲得檔案系統的各種服務，

建立檔案的程序：

——查檔案目錄表，看當前目錄下有沒有同名檔案存在，有則拒絕建立，給出錯誤資訊，否則分配給該檔案一空目錄項，并填入檔案名和用戶提供的引數，

——為要建立的檔案分配存盤空間，

——將新建檔案的目錄項讀入打開檔案表中（即完成打開檔案的作業），為以后寫檔案作好準備，

打開檔案的程序：

——根據檔案路徑名查目錄，

——根據打開方式、共享說明和用戶身份檢查訪問合法性，

——根據檔案號查系統打開檔案表，看檔案是否已被打開，如果是，共享計數加1，否則，資訊填入系統打開檔案表空表項，共享計數置為1，

——在用戶打開檔案表中取一空表項，填寫打開方式等，并指向系統打開檔案表對應表項，

關閉檔案的程序：

——將打開檔案表中該檔案的“當前使用用戶數”減1，若為0，則撤消此表目，

——若打開檔案表目內容已被改過，則應先將表目內容寫回輔存上相應表目中，以使檔案目錄保待最新狀態；做卷定位作業，

洗掉檔案的程序：

——系統根據用戶提供的檔案名或檔案描述符，檢查此次洗掉的合法性，

——查找檔案目錄，

——將該檔案從目錄中洗掉，并釋放該檔案所占用的存盤空間，

讀、寫檔案：

——核對所給引數的合法性，

——按檔案名從打開檔案表中找到該檔案的目錄項，

——按存取控制說明檢查訪問的合法性，

——根據打開檔案表中該檔案的引數，確定讀寫的物理位置（確定塊號、塊數、塊內位移與長度等），

——向設備管理程式發I/O請求，完成資料交換作業，

為了保證對檔案的正確管理和檔案資訊的安全可靠，規定了用戶請求檔案的操作步驟：

檔案共享：

檔案共享可以提高檔案的利用率，避免存盤空間的浪費，并能實作用戶用自己的檔案名去訪問共享檔案，實作檔案共享通常有以下5種方法，

繞道法：

——用戶對所有檔案的訪問都是相對于當前目錄進行的，當所訪問的共享檔案不在當前目錄下時，從當前目錄出發向上回傳到與共享檔案所在路徑的交叉點，再沿路徑下行到共享檔案，

——繞道法要求用戶指定到達被共享檔案的路徑，并要回溯訪問多級目錄，因此，共享其他目錄下的檔案的搜索速度較慢，

鏈接法：

——鏈接法是將一個目錄中的鏈指標直接指向共享檔案的目錄項，

基本檔案目錄：

——檔案目錄分解為基本目錄和符號目錄，只要在不同檔案符號目錄中使用相同檔案內部識別符號，就可實作檔案的共享，

利用符號鏈實作檔案共享：

用戶H為了共享用戶C的—個檔案f，可以由系統創建一個LINK型別的新檔案，將新檔案寫入H的用戶目錄中，在新檔案中只包含被鏈接檔案f的路徑名，稱這樣的鏈接方法為符號鏈接，當H要訪問被鏈接的檔案f且正要讀LINK類新檔案時，被作業系統截獲，作業系統根據新檔案中的路徑名去讀該檔案，于是就實作了用戶H對檔案f的共享，

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

采用索引結點，將諸如檔案的物理地址及其它的檔案屬性等資訊，不再放在目錄項中，而是放在索引結點中，在檔案目錄中只設定檔案名及指向相應索引結點的指標，此時，由任何用戶對檔案進行追加操作或修改，所引起的相應索引結點內容的改變，例如，增加了新的盤塊號和檔案長度等，都是其他用戶可見的，從而也就能提供給其他用戶來共享，

與基本檔案目錄類似，

六、檔案系統的安全性和資料一致性：

影響檔案安全性主要因素：

——人為因素：由于人們有意或無意的行為，而使檔案系統中的資料遭到破壞、丟失或竊取，

——系統因素：由于系統的部分出現例外情況而造成對資料的破壞或丟失，特別是作為資料存盤介質的磁盤在出現故障或損壞時，會對檔案系統的安全性造成影響，

——自然因素：存放在磁盤上的資料，隨著時間的推移而發生溢位或逐漸消失，

防止人為因素造成的檔案不安全性：

隱蔽檔案和目錄：

——系統和用戶將要保護的檔案目錄隱蔽起來，在顯示檔案目錄資訊時由于不知道檔案名而無法使用，

口令（密碼）：

——檔案口令（檔案密碼）：系統要求檔案的建立者為他需要保密的檔案設定一個口令，

——用戶口令（用戶密碼）：當用戶利用計算機終端使用計算機時使用，

檔案加密：

——對于高度機密的檔案，可采用加密碼的措施，檔案加密碼是把檔案中所有字符代碼，按某種變換規則重新編碼，檔案的輸入讀出都經過編碼程式和解碼程式處理，

制定訪問權限：

存取控制矩陣：

——由系統中的全部用戶和全部檔案組成的二維矩陣，稱為存取控制矩陣，矩陣的每個元素表示用戶對檔案的使用權限，

存取控制表和用戶權限表：

——存取控制表就是對存取控制矩陣中的一列進行壓縮，可讓每一個檔案附加一個簡單的表格，它規定了對該檔案的可訪問性（權限），

——用戶權限表就是對存取控制矩陣中的一行進行壓縮，該表中列出該用戶對每個檔案的訪問權限，

防止自然因素或系統因素造成的檔案不安全性：

壞塊管理：

硬體方法：

——建立一個壞塊表，在硬碟上為壞塊表分配—個扇區，當控制器第一次被初始化時，它讀壞塊表并找一個空閑塊（或磁道）代替有問題的塊，并在壞塊表中記錄映射，

軟體辦法：

——要求用戶或檔案系統構造一個包含全部壞塊的檔案，

磁盤容錯技術,也稱系統容錯技術（System Fault Tolerance）：

通過在系統中設定冗余部件來提高系統可靠性的一種技術，

SFT-I是低級磁盤容錯技術，主要用于防止磁盤表面發生缺陷所引起的資料丟失，
SFT-Ⅱ是中級磁盤容錯技術，主要用于防止磁盤驅動器和磁盤控制故障所引起的系統不能正常作業，
SFT-Ⅲ是高級系統容錯技術，提供了檔案服務器鏡像功能，在主服務器出現故障時能有備份服務器不間斷地接替主服務器的作業，

第一級容錯技術（SFT-I）：

——雙份目錄和雙份檔案分配表：建立兩份目錄表和FAT，一份稱為主檔案目錄及FAT，另外一份則稱為備份目錄及備份FAT，

——熱修復重定向：系統將一定的磁盤容量（例如2%~3％)作為熱修復重定向區，用于存放當發現盤塊有缺陷時的待寫資料，并對寫入該區的所有資料進行登記，以便于以后對資料進行訪問，

——寫后讀校驗：在每次從記憶體緩沖區向磁盤中寫入一個資料塊后，又立即從磁盤上讀出該資料塊，送至另一緩沖區中；再將該緩沖區中內容與記憶體緩沖區中在寫后仍保留的資料進行比較，若兩者一致，便認為此次寫入成功，否則再重寫，

第二級容錯技術（SFT-Ⅱ）：

——磁盤鏡像：磁盤鏡像是在同一磁盤控制器下，再增設一個完全相同的磁盤驅動器，

——磁盤雙工：將兩臺磁盤驅動器分別接到兩個磁盤控制器上，同樣地使這兩臺磁盤機鏡像，（完美的解決了磁盤控制器或者主機到磁盤控制器之間的通道發生故障的情況，這是磁盤鏡像所沒有解決的問題，）

獨立磁盤冗余陣列（RAID）：（因為相關的介紹過于龐大，會影響整篇文章的結構，故另外介紹，點擊以下鏈接直達！）

作業系統：獨立磁盤冗余陣列（RAID）的相關介紹（👈）

備份：

——建立副本：把同一個檔案保存到多個存盤介質上，當某個檔案損壞或丟失時，就可用其他存盤介質上的備用副本來替換，

——轉儲：海量轉儲、增量轉儲

海量轉儲：把存盤器中的全部檔案定期復制到備用存盤介質上，但是轉儲會浪費大量的時間和影響用戶的作業，一個小小的故障就需要所有的用戶檔案進行轉儲，所以最好是在空閑時間進行轉儲，
增量轉儲：在相當短的時間里把上一次轉儲以來改變過的檔案（包括控制塊）和新檔案轉儲到備用存盤介質上，關鍵性的重要檔案也可以再次轉儲；這種方法克服了海量轉儲的缺點，但是轉儲到磁盤上的資訊不緊湊，浪費存盤空間，

檔案系統的資料一致性：

許多檔案系統在讀取磁盤塊進行修改之后，再寫回磁盤，如果在修改過的磁盤塊全部寫回之前，系統崩潰，則檔案系統很有可能會處于不一致的狀態，如果一些未被寫回的塊是目錄塊或者包含空閑表的磁盤塊，這個問題會尤為嚴重，

為了解決檔案系統的不一致問題，一些計算機會帶有一個實用程式以檢驗檔案系統的一致性，

一致性檢查分為兩種：塊的一致性檢查和檔案的一致性檢查，

塊的一致性檢查：

為了保證盤塊資料結構的一致性，可利用軟體方法構成一個計數器表，每個盤塊對應一個表項，每一表頂中包含兩個計數器，分別用作空閑盤塊號計數器和資料盤塊號計數器，

正常情況下，上述兩組計資料中對應的一對計數器中的資料應互補，亦某個盤塊在第一組計數器中數器值為1，則在第二組計數器中計數器內容必為0，反之亦然，但如果情況并非如此時，說明發生了某種錯誤，

檔案的一致性檢查：

——重復檔案的資料一致性：在有重復檔案時，如果—個檔案拷貝修改了，則必須同時修改它的幾個檔案拷貝，保證該檔案中資料的一致性，可以采用兩種方法進行實作：

當一個檔案被修改之后，可以查找檔案目錄，得到其另外副本的物理位置，然后對他們進行同樣的修改，（修改）
為新修改的檔案建立幾個副本，并用它們替代原來的檔案副本，（替代）

——共享檔案的資料一致性：檔案的共享計數和當前共享該檔案的用戶個數相一致，

七、磁盤調度：

提高檔案系統的性能措施：

塊高速快取：

——系統在記憶體中保存一些存儲塊，這些存盤塊在邏輯上它們屬于磁盤，

——作業時，系統檢查所有的讀請求，看所需的檔案塊是否在高速快取中，如果在，則可直接在記憶體中進行讀操作，否則，首先要將塊讀到高速快取中，再拷貝到所需的地方，

磁盤空間的合理分配：

——在磁盤空間中分配塊時，應該把有可能順序存取的塊放在一起，最好在同一柱面上，這樣可以有效地減少磁盤臂的移動次數，加快檔案的讀寫速度，提高性能，

對磁盤調度演算法進行優化

磁盤I/O（輸入輸出）時間：

采用移動磁頭的磁盤要訪問某特定的物理塊時，所用時間一般包括三部分 ：

——查找時間：

按給定的柱面號（磁道號）將讀寫磁頭移動指定的柱面或磁道上的時間，

——等待時間：

等待磁盤旋轉，使讀寫的塊位于讀寫磁頭之下的時間，

——傳輸時間：

記憶體和磁盤之間資料的實際傳送所用的時間，

磁盤的移臂調度演算法：

先來先服務調度演算法FCFS：

——演算法：根據訪問請求的先后次序選擇先提出訪問請求的為之服務，

——優缺點：是磁盤調度的最簡單的一種形式，它既容易實作，又公平合理，缺點是效率不高，

最短查找時間優先演算法SSTF：

——演算法：以磁頭移動距離的大小作為優先的因素，從當前磁頭位置出發，選擇離磁頭最近的磁道為其服務，

——優缺點：減少了磁道平均查找時間，但沒考慮磁頭移動的方向，也沒有考慮行程在佇列中等待的時間，

掃描演算法：

電梯調度演算法SCAN：

——演算法：是選請求佇列中沿磁頭臂前進方向最接近于磁頭所在柱面的訪問請求作為下一個服務物件，

——優缺點：演算法簡單、實用且高效，克服了最短尋道優先的缺點，既考慮了距離，同時又考慮了方向，但有時有的請求等待時間可能很長，

例如，如果在為訪問43號柱面的請求者服務后，當前正在為訪問67號柱面的請求者服務，同時有若干請求者在等待服務，它們依次要訪問的柱面號為186，47，9，77，194，150，10，135，110，

按照先來先服務的策略，處理順序：186→47→9→77→194→150→10→135→110，
用最短查找時間優先演算法服務的順序為： 77→47→10→9→110→135→150→186→194，
用電梯調度演算法，服務次序為： 77→110→135→150→186→194→47→10→9，

N步掃描策略：

——N步SCAN演算法是將磁盤請求佇列分成若干個長度為N的子佇列，磁盤調度將按FCFS演算法依次處理這些子佇列，而每處理一個佇列時又是按SCAN演算法，對一個佇列處理完后，再處理其他佇列，

——當正在處理某子佇列時，如果又出現新的磁盤I/O請求，便將新請求行程放入其他佇列，這樣就可避免出現粘著現象，

回圈掃描策略：

——磁盤單向移動，當移動臂向內移動時，它對本次移動開始前到達的各訪問要求自外向內地依次給予服務，直到對最內柱面上的訪向要求滿足后，然后移動臂直接向外移動，停在所有新的訪問要求的最外邊的柱面上，然后再對本次移動前到達的各訪問要求依次給予服務，

FSCAN演算法：

——FSCAN演算法實質是N步SCAN演算法的簡化，

——將磁盤請求訪問佇列分成兩個子佇列，一是當前所有請求磁盤(I／O)的行程形成的佇列，由磁盤調度按SCAN演算法進行處理，另—個佇列則是在掃描期間，新出現的所有請求磁盤I／O行程的佇列，把它們排入另一個等待處理的請求佇列，

磁盤的優化分布：

有些系統，對資料的存放位置進行優化分布可減少延遲時間，從而縮短了輸入輸出操作的時間，

實際舉例：

某系統對磁盤初始化時把每個盤面分成8個扇區，今有8個邏輯記錄被存放在同一個磁道上供處理程式使用，處理程式要求順序處理這8個記錄，每次請求從磁盤上讀一個記錄，然后對讀出的記錄要花5毫秒的時間進行處理，以后再讀下一個記錄進行處理，直至8個記錄都處理結束，假定磁盤轉速為20毫秒/周，現把這8個邏輯記錄依次存放在磁道上，如圖 (a)所示，

(a)讀一個記錄要花2.5毫秒的時間，當花了2.5毫秒的時間讀出第1個記錄并花5毫秒時間進行處理后，讀寫磁頭已經在第4個記錄的位置，為了順序處理第2個記錄，必須等待磁盤把第2個記錄旋轉到讀寫磁頭位置下面，即要有15毫秒的延遲時間，處理這8個記錄所要花費的時間為：

8×(2.5+5)+7×15=165(ms)

(b)是這8個邏輯記錄的最優分布，當讀出一個記錄處理后，讀寫磁頭正好位于順序的下一個記錄位置，可立即讀出該記錄，不必花費等待延遲時間，于是，處理這8個記錄所要花費的時間為：

8×(2.5+5)=60(ms)

Ending... ...

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/234838.html

標籤：其他

上一篇：把網頁資源放到WEB-INF下的目的以及如何訪問

下一篇：初始入門，從下載Node.js到修改npm全域安裝路徑

作業系統學習筆記：檔案管理

目錄：