啟蒙篇

文件的由來

磁盤上保存的是一對十六進制的數據，如何切分數據形成不同的文件，也就是如何確定一個文件的起始和終止位置？
將相關數據打包在一起形成一個文件，比如從什么位置開始到什么位置結束，是一張圖片、一段文字、一個視頻
還需要為每一個打包文件配置一個 FCB，類似PCB
FCB保存在磁盤，記錄文件的名字、文件的起始位置、文件的終止位置等信息
通過文件的名字? 匹配 FCB中符合的文件，通過名字作為檢索，查詢文件的相關信息，比如文件的存儲位置

目錄的由來

每個文件都有與之對應的FCB??
將FCB的集合重新打包成一個文件，形成目錄文件（其他文件的檔案袋），其他文件叫做普通文件，比如圖片、視頻、文檔
操作系統啟動的時候，將目錄文件讀取到內存，就可以使用戶看到文件結構

文件管理邏輯圖

文件系統由文件和目錄兩個部分組成
文件：邏輯結構? 數據怎么組織？如何打包？
目錄：物理結構? 組織好的數據如何保存？
數據打包形成文件
FCB 打包形成目錄
物理結構：組織好的數據如何存儲？

閑聊文件系統

操作系統、文件系統和存儲器都有很多類型
通常講win、linux具有那種文件系統的方法和原理
操作系統：unix 、 linux 、 windows 、 android 、 ios? 、macos
文件系統：ext 、NTFS(win)? 、APFS(MAC)、 FAT 、YFFS、JFFS
存儲器：硬盤類、光盤類、磁帶類、flash類（固態硬盤、U盤、云盤）
文件系統的基本構成 = 文件 +? 目錄；使得磁盤數據保存、管理、搜索更加便捷化和人性化

基礎篇

文件的邏輯結構和物理結構

邏輯結構：文件是由不同的十六進制數據組成的，每個數據都有指定的位置，如果數據的位置打亂了，就不可以表示先前的數據，文件就沒有意義。比如刪除文件的一部分，使文件損壞。
物理結構：將磁盤進行切割，分成很多塊，每一塊散列存儲在磁盤
使用的時候，將物理結構按照邏輯順序拼接在一起就形成了正確的邏輯結構，就可以還原原本的文件

文件系統的邏輯結構（數據是如何組織起來的）

文件的邏輯結構

有結構文件：記錄式文件：格式多樣化(描述信息，比如位置信息等等)、內容多樣化（字體的顏色大小）、便于搜索查詢
有結構文件比如excel，即使只記錄一個字母，但是需要記錄大量的相關信息，因此文件會很大
無結構文件：流式文件，比如txt，僅僅可以按照順序簡單記錄每一個字符；
*并不是所有文件的所有內容都是可視化的
流式文件特征：1，簡單順序，以字節為單位記錄每一個數據；2，由于沒有結構，搜索的時候只可以窮舉搜索，適用性很差；3，適用于對基本信息單位操作(修改操作)不多的文件，比如源代碼、目標代碼文件、圖片

有結構文件的數據組織：

1，數據項：最低級的數據組織形式，文件的細胞，每個的數據項的長度不一樣。數據項是最小單元，word的數據單元是單個字，excel的數據單元是單個表格
2，記錄：一組有意義的數據項的組合，關鍵字，唯一標識一個記錄，每個記錄的長度都可能不一樣
3，文件：文件系統中最大的數據單位
知識點準備
1，抽象化，以記錄為最小單位
2，抽象化后的定長記錄(不夠標準定長的數據就補長)和變長記錄(每個記錄的長度不一樣)的表示
3，定長（直接訪問或者順序訪問）和變長記錄（順序訪問）方式的查詢(變長需要有一個字節來記錄數據的長度)

順序文件

分為1，串結構（時間排序，往表格里面輸入的先后順序）定長和變長；2，順序結構(關鍵字排序，按照成績排序)分為定長和變長
特點：1，對順序文件的記錄做增加刪除比較困難，需要移動和重新排序；2，只有順序文件可以保存在磁帶上；3，定長記錄的順序文件比變長記錄的順序文件查找快

索引文件

原因，變長文件查詢比較麻煩，只可以使用順序查找的方式進行查詢。對變長記錄的順序文件進行改進，使其可以直接訪問/順序訪問(索引表)
索引表是定長的，利用直接訪問的優勢
索引表：索引號(排序的位號) 、記錄長度(配合第三個參數) 和記錄指針? ? ?索引表是附文件，將索引表拼接在主文件(變長順序存儲)的前面，就形成了索引文件
特點：1，通過索引表查詢記錄很快；2，索引表會導致文件大小的增加，因為拼接了索引表

索引順序文件

分組，索引表記錄鍵值和邏輯地址，邏輯地址是指向不同分組的第一個邏輯地址
N個記錄分為根號N 組，平均查詢根號N次
增加索引表多占了空間，但是提高了存取速度
組間索引組內順序
同組無序，組間有序

Hash文件

直接文件 = 散列文件 = HASH文件 = 哈希文件
散列文件存取文件的速度很快，但是會引發沖突 -> 數據結構 Hash查找
Hash(記錄) = 記錄應該保存的位置(物理位置)?
好的hash函數會減少沖突的次數，但是沖突不會避免

目錄文件的邏輯結構(PCB是如何組織起來的？)

文件控制FCB

FCB保存在磁盤上，記錄文件的相關信息
FCB 記錄文件名、邏輯結構、物理結構、文件類型（目錄類型還是普通文件）、文件大小、磁盤位置（物理位置）、控制信號（文件保護，文件的權限）、計數信息（文件共享）
多個FCB排列組合變成了目錄結構
FCB數量有限，文件的數量有限

索引節點inode

過程：將FCB分解，目錄文件只保留文件的名字，除了文件名字之外的信息打包形成的塊，簡稱inode
拆解的原因：原版的FCB太大，導致目錄文件的很大，電腦查詢文件的時候，需要將目錄文件調入內存，導致內存的消耗變大。其次，讀取大的目錄文件的時候，磁盤訪問次數也會變多，導致文件查詢速度很慢，瘦身之后的FCB就克服了這個缺點
節點表記錄所有inode，查詢的時候，需要通過文件名字查詢FCB，找到對應的inode，再到節點表查詢inode里面查詢物理位置
節點表保存在磁盤，瘦身版FCB(文件名+inode號)時讀入內存，不用的時候存儲在磁盤
索引節點：編號遞增且唯一。每個索引節點唯一關聯一個目錄文件或者普通文件(inode代替先前的原版PCB成為文件的檔案袋)
inode數量有限，操作系統安裝的時候就已經確定了
這種方式適用于Unix系統

目錄結構

單級目錄結構

FCB連續，每個FCB對應一個文件，沒有文件夾的概念
目錄基本操作
1，檢索文件
2，創建文件，先申請FCB，再分配內存空間
3，刪除文件，先回收磁盤塊，再刪除FCB
4，移動文件，（沒有目錄層級的概念，復制剪貼）
特點
1，實現按名存取，但是不可以重名
2，檢索文件很慢
3，不適用于多用戶操作系統，（用戶空間隔離，彼此文件不可見）
4，沒有文件夾

兩級目錄結構

針對單級目錄的優化
實現了多用戶，但是靈活性不夠，不可以對文件進行分類管理
相關FCB都相聯，比如不同用戶的FCB相聯，同一用戶的不同文件的FCB相聯
區分了用戶，但是用戶進入自己的文件夾下，和單級目錄結構一致，只有文件，沒有層級結構

多級目錄結構

改進兩級目錄，解決不可以對文件進行分類的問題
特點
1，更好的對文件進行分類管理，樹形目錄層次清晰、分類清晰
2，磁盤啟動次數多因為按照樹形結構，從上到下，每一級分別讀入內存進行查詢（按塊讀取）（一塊就啟動一次）

無環圖目錄結構

樹形目錄結構 + 有向邊 = 無環圖目錄
被多條有向邊指向的目錄文件，就是被共享的文件
設計的目的是為了共享?
有向邊由硬鏈接/軟連接實現

文件共享

文件共享的原因：1，單機? 節約空間，只保留一個副本（缺點，牽一發動全身，個人修改對別人影響很大）；2，聯網? 互聯網發展的必然性 C/S 模型，不同用戶訪問同一文件

硬鏈接共享

云盤共享數據，接收別人共享的文件，保存到我的云盤，本質是添加inode號，使得多個用戶關聯同一份文件，inode號指向文件
需要添加計數信息參數，刪除文件，就是刪除關聯inode的信息，同時減少計數
只有當文件的計數為0，代表這個文件不再被使用，刪除文件，回收inode
inode通過物理地址直接找到文件的存儲位置，速度很快

軟連接共享

link類型文件，文件內存有共享文件的路徑，因此會增加磁盤訪問的次數
可能引起錯誤（新的文件和舊的文件同名的時候）
linux的軟連接模式和 windows的創建快捷方式相似
軟連接，通過文件的層級目錄找到文件，僅僅依靠目錄層級和文件的名字作為索引

文件保護

文件保護是通過索引節點inode和文件控制塊FCB一起使用實現的
文件保護的原因，防止共享文件被未經過批準的用戶隨意修改和破壞
文件保護的方式
1，口令：FCB添加口令，口令匹配才可以通過，防止隨意存取
2，加密：對文件的數據進行加密，即使獲取文件，也無法解密數據；缺點：需要使用對應的加解密文件，需要耗費時間
3，訪問控制：不同角色擁有不同的權限，設置訪問控制表。這個一般Unix使用比較多，對文件分為擁有者、組、其他，分別對應讀、寫、執行三種權限
口令和訪問控制，都是在FCB的控制信息里面添加內容

文件系統的物理結構

文件的實現（物理結構）

文件物理結構學習邏輯圖

文件保存到磁盤 -> 最小單位為塊（4kb、1kb）塊設備
問題
1，存在哪？文件的分配方式
2，哪可存？磁盤存儲空間的管理

文件的分配方式

連續分配
思想：文件分配一組連續的磁盤塊
特點：
1，順序訪問? 直接訪問（起始地址 + 每一塊的大小 * 數據塊數）
2，外部碎片多，內部碎片少
3，適合長度固定的文件的（比如圖片、視頻）
磁盤塊的順序很重要，需要從指定位置讀取指定大小的文件內容；存文件的時候，也需要順序存放
FCB表格：文件的名字、存儲的起始位置、文件的長度

鏈接分配分為隱式鏈接分配和顯式鏈接分配；解決內部碎片的問題
隱式鏈接分配?
思想：順藤摸瓜 / 做記號；? 像鏈表一樣，把不連續的空間碎片，鏈接在一起；每一個塊的后面記錄下一個存儲的位置信息
特點：可以順序訪問，不可以直接訪問；穩定性不好（如果中間數據損壞，就無法銜接下一個文件，造成文件的損壞）
FCB里邊的物理結構，會確定文件的類型是連續分配、隱式鏈接分配、顯式鏈接分配等，按照對應的規則，讀取目錄文件
FCB? 隱式鏈接分配的目錄文件記錄文件的名字、起始位置和結束位置
因為有鏈接的存在，假設鏈接占據2b，每個塊存儲（4kb - 2b）大小的內存

顯式鏈接分配
解決隱式鏈接分配不穩定的問題（中間斷裂）
思想：先存再讀，整個磁盤設置一張表，記錄每個磁盤塊的分配情況，該表叫做FAT
查詢FAT，防止中間層數據斷裂
特點：FAT表占用空間比較大，磁盤無所謂，但是內存卡會浪費很大的空間

?單級索引分配

思想：為每個文件都建立一個索引表，記錄該文件的磁盤塊分配順序
將索引表記錄在一個磁盤塊，FCB的索引填寫索引表的存儲磁盤號
索引表：文件的名字、索引（索引表記錄磁盤塊的分配順序，索引記錄索引表所在的磁盤位置）
文件讀取的時候，現根據文件的名字，讀取索引表的；將索引表讀入內存之后，根據索引表依次讀取文件
FCB的物理結構會記錄模式? 單級索引
特點：可以直接訪問，但是索引表占據了磁盤的空間，文件很大，需要的索引表也會很多

多級索引分配

解決索引塊長度不一致，使索引表變成一個變長文件，不利于直接訪問的問題，再次構建索引表
8M文件占據多少空間？ 8Mb + 3* 4kb

混合索引

直接索引、單級索引、二級索引、三級索引等同時使用
條件：盤塊4kb大小、盤塊號4B大小
問：混合索引最大支持的文件大小？4TB + 4GB + 4MB + 4kb
3GB文件實際需要占用多大的空間？?好復雜?
一個盤塊可存 4kb/4B = 1k 個盤塊號
直接索引：4kb
單級索引：1k * 4kb = 4MB
二級索引：1k *1k * 4kb = 4GB
三級索引：1k * 1k *1k *4kb = 4TB
文件的索引順序依次是直接、單級、二級、三級

存儲空間管理

空閑表法

解決哪里可以存？
空閑盤塊表：序號、第一個空閑的盤塊號、空閑數量；主要用于連續分配
?分配：分配算法，如首次適應、最佳適應、最壞適應、鄰臨適應、循環首次適應
回收：合并問題，（刪除）
存在哪里？

空閑鏈表法

空閑盤塊鏈：盤塊號+下一節點指針
空閑盤區鏈：首個盤塊號盤區大小下一個盤區指針
數據結構里面的鏈表，還是單鏈表

位示圖法

由0和1 組成，1代表存儲數據，0代表沒有存儲數據

成組鏈表法

一組一組形成鏈表，就是成組鏈表法
并不詳細? 回收和分配

目錄的實現（物理結構）

線性鏈表

目錄文件依次查詢（線性鏈表）
例題
有一個文件系統，根目錄常駐內存，如圖所示，文件目錄采用鏈接結構，每個目錄下最多放80個目錄或者文件(稱為下級文件)，每個磁盤塊最多放10個文件目錄項，如果下級目錄是目錄文件，則上級目錄指向該目錄文件的第一塊磁盤。假設目錄結構中第一塊文件按照從左向右的順序排列，... 表示有其他文件或者目錄
問題：k文件最少或者最多查詢幾次磁盤
文件文件夾都是文件
最多查詢 8 次，采用鏈接表的方式存儲，需要根據頭結點到尾節點依次查詢
每次讀取數據都需要啟動磁盤

哈希表

考的少
利用文件的名字進行哈希運算，得到文件的存儲位置

層次結構

為什么要分層？

每一層各司其職（下層為上層服務）
高內聚低耦合
利于修改代碼。推行版本的更新和便于移植

具體內容

從下往上
設備（硬件）：磁盤、flash、光盤等等
設備管理模塊(軟件)：驅動程序（讀寫控制磁盤等）
物理文件系統：存在哪里？物理結構，文件的分配方式
輔助分配模塊：哪里可存？磁盤存儲空間管理
邏輯文件系統：文件以及目錄的邏輯構成
存取控制模塊：文件的保護
文件目錄系統：根據文件的名字來搜索FCB
用戶接口：GUI、命令行、系統調用(API)
用戶普通用戶程序員

磁盤的組織和管理

磁盤的結構

扇區，一圈扇區圍成的同心圓環叫一條磁道
圓環就是磁道從外往里命名
盤面? 圓形的物理結構
多個圓形的盤面相垂直的部分構成柱面，柱面號和磁道號一致
約靠近扇區的圓心，扇區的密度越大
通過柱面號盤面號和扇區號唯一確定一個扇區

磁盤的讀寫

相關概念：
n：跨越的磁道數
m：磁盤的固定參數，是常數；移動一條磁道的耗時
s：磁臂啟動時間，也是常數
r：轉速；單位轉/秒?
b：扇區字節數
N：一條磁道字節數

磁盤的一次讀寫時間大概值(期望數值/平均數值)

一次讀寫時間：期望值/平均值 Ta = 需找時間 Ts?+ 延遲時間 Tr + 傳輸時間Tt
尋找時間：磁頭跳轉磁道的時間，也就是尋找柱面號 (也是磁道號，多塊盤的磁道組織在一起構成柱面)；m 磁盤的固定參數，是常數，平均移動一條磁道的耗時；s 磁臂啟動時間，也是常數，需要給磁臂充電，然后才有能量進行磁道之間的切換
延遲時間：磁道確定之后，磁頭還需要等待目標扇區的到來，扇區旋轉；期望值，Tr = 1/2r?
延遲時間推導：轉速一般是固定的，一般是7200轉/分鐘? 7200/60=120轉/s? 每轉一圈 1/r 秒，每個扇區用 1/r(x+1)秒；磁頭移動之后，定位的第一個扇區是隨機的，計為A，該磁道的每一個扇區都可能是目標扇區，成為目標扇區的幾率是 p = 1/(x+1)? 則，Tr = 1/2r
傳輸時間：傳輸時間是在延遲時間的基礎上來看的，Tt = b / rN? ? ? ? ? ? ? ? ? ? ? ?
磁頭掠過所有的扇區，怎么只讀一個扇區？磁頭電子開關，如果不開啟，讀取的數據是無效的
減少Ts：優化尋道順序 -> 磁盤的調度算法
減少Tr：盤面錯位編號和扇區交替編號?；增大轉速
減少Tt：增大轉速，如果磁盤確定，則無法優化