操作系統(tǒng)結構分析與應用編程第一頁，共185頁。課程概述一．課程內容簡介1、講授范圍具體的技術系統(tǒng)及其算法和實現(xiàn)流程，而不是操作系統(tǒng)基本原理；2、通用操作系統(tǒng)的現(xiàn)狀和分類DOS類----結構簡單、使用方便、效率低、安全性低UNIX類----運行高效、結構通用、安全可靠、適應能力強、系統(tǒng)較復雜MVS類----功能強大、處理能力巨大、系統(tǒng)復雜、較封閉第二頁，共185頁。大巨型機+z/OS小中型機+UNIX微型機+Windows功能強大簡單易用第三頁，共185頁。3、根本特點

分時多用戶、開放性分時多用戶：多個用戶多個進程同時在一個系統(tǒng)中運行系統(tǒng)資源高度共享、有效協(xié)調開放性：標準化——結構上的一致性可移植性——應用軟件的編碼及系統(tǒng)應用接口可互操作性——可保持用戶原來的使用習慣異種機之間的互操作4、教學難點多用戶多進程——同步/互斥、數據一致性、訪問安全性開放性——硬件依賴性、結構伸縮性、廣泛適應性第四頁，共185頁。二、教學目的

1、了解主流操作系統(tǒng)的發(fā)展方向低端操作系統(tǒng)VS高端操作系統(tǒng)2、掌握UNIX類操作系統(tǒng)的內部結構和主要算法文件、文件系統(tǒng)、進程、時鐘、輸入輸出3、學習大型程序設計的方法和理念系統(tǒng)結構、功能流程、數據安全、思維模式4、奠定系統(tǒng)開發(fā)和應用開發(fā)的基礎功能選擇、層次劃分、應用系統(tǒng)模式的確定第五頁，共185頁。三、教材《UNIX操作系統(tǒng)設計》（TheDesignoftheUNIXOperatingSystem）（美）MauriceJ.Bach著陳葆玨

王旭柳純錄馮雪山譯機械工業(yè)出版社2005年10月出版第六頁，共185頁。第一章系統(tǒng)概貌1.1發(fā)展狀況1、發(fā)展歷史及版本v.01970年KenThompson和DennisRitchiePDP-7匯編語言UNICSv.11971年PDP-11匯編語言UNIX

v.21972年增加管道功能第七頁，共185頁。v.51973年DennisRitchieBlanguage----Clanguage

重寫UNIX第一個高級語言OSv.61975年對外發(fā)表UNIX大學和科研單位應用v.71978年第一個商業(yè)版本我國開始深入研究應用的最早版本SystemIII1981年完全轉向為社會提供的商品軟件第八頁，共185頁。

SystemV1983年系統(tǒng)功能穩(wěn)定完善公布號:1.0、2.0、2.3、3.5、4.0、4.2、4.3現(xiàn)在最后版本為SystemVRelease4(SVR4)第九頁，共185頁。2、主要分支和兼容版本BSD

加州大學伯克利分校XENIX/OpenServerMicrosoft、SCO公司HP-UXHP公司AIXIBMSolarisSUN公司IRIX

SGI公司UltrixDEC公司Linux開放源代碼第十頁，共185頁。3、基本功能特征交互式分時多用戶人機間實時交互數據多個用戶可同時使用一臺機器每個用戶可同時執(zhí)行多個任務軟件復用每個程序模塊完成單一的功能程序模塊可按需任意組合較高的系統(tǒng)和應用開發(fā)效率可移植性強數千行匯編碼,數十萬行C語言代碼第十一頁，共185頁。配置靈活,適應性強小內核,參數靈活可調核外應用系統(tǒng),任意裁減限制規(guī)則很少界面方便高效內部:系統(tǒng)調用豐富高效外部:shell命令靈活方便可編程應用:GUI清晰直觀功能強大安全機制完善口令、權限、加密等措施完善抗病毒結構誤操作的局限和自動恢復功能

第十二頁，共185頁。多國語言支持支持全世界現(xiàn)有的幾十種主要語言網絡和資源共享內部:多進程結構易于資源共享外部:支持多種網絡協(xié)議說明：1、其它操作系統(tǒng)可能包含部分上述UNIX的特征，但非全部（如NT就有部分多用戶系統(tǒng)特征）2、這些特征有些是核心直接實現(xiàn)的，有些是由核心提供實現(xiàn)這種特征的方便性和可能性，而由使用者來實現(xiàn)的。第十三頁，共185頁。1.2系統(tǒng)結構

內核kernelshwhodatewcvigrepdatea.outlsapp_1app_2app_nUNIX操作系統(tǒng)的整體結構

第十四頁，共185頁。系統(tǒng)調用（systemcall）以函數形式提供給核外的命令和上層應用系統(tǒng)使用的一組程序，涵蓋操作系統(tǒng)的所有功能。是應用程序請求操作系統(tǒng)服務的唯一通道。內核（kernel）系統(tǒng)調用的集合及實現(xiàn)系統(tǒng)調用的內部算法就形成操作系統(tǒng)核心第十五頁，共185頁。1.3用戶看法進程和文件是UNIX操作系統(tǒng)中最基本的兩個概念（抽象）進程：所有處在運行期間的程序實例都是進程一個進程就是處在運行期間的一個程序實例涵蓋所有的動態(tài)概念文件：所有靜態(tài)的無形數據和有形硬件設備源程序、命令、圖片、郵件、打印機、內存、磁盤等第十六頁，共185頁。1.3.1文件系統(tǒng)

/binusretchometmpdevwholsbinlibrcttysstteachtty0hd02adminhwconfliuwangchenaadir2save

UNIX文件系統(tǒng)樹示例第十七頁，共185頁。UNIX文件系統(tǒng)的特征：1、樹狀層次結構樹根、樹枝、樹葉、路徑2、對文件數據的一致對待文件為有序無格式的字節(jié)流，邏輯意義由使用者解釋3、文件管理建立、刪除、修改、備份、移動、替換存儲空間的分配和釋放4、文件的訪問和保護索引節(jié)點（inode）、文件描述符(fd)用戶分組、權限劃分5、設備文件管理統(tǒng)一各外部設備的訪問模式第十八頁，共185頁。charbuffer[2048];main(intargc,char*argv[]){ intfdold,fdnew; if(argc!=3) { printf(“need2argumentsforcopyprogram\n”); exit(1); } fdold=open(argv[1],O_RDONLY); if(fdold==-1) { printf(“cannotopen\n”,argv[1]); exit(1); } fdnew=creat(argv[2],0666); if(fdnew==-1) { printf(“cannotcreate\n”,argv[2]); exit(1); } copy(fdold,fdnew); exit(0);}copy(intold,intnew){ intcount; while((count=read(old,buffer,sizeof(buffer)))>0) write(new,buffer,count);}第十九頁，共185頁。1.3.2處理環(huán)境

程序：可執(zhí)行的文件

文件頭包括：·文件的幻數（magicnumber）·編譯器的版本號·機器類型·數據段、正文段、工作變量的段大小·程序入口點文件頭正文段數據段工作變量段BSS（符號表、重定位信息等）第二十頁，共185頁。進程：程序的一次執(zhí)行實例一個程序可同時有多個實例；系統(tǒng)中可同時有多個進程父進程：調用系統(tǒng)調用fork的進程子進程：由系統(tǒng)調用fork產生的新進程執(zhí)行程序：調用execl,用被執(zhí)行程序的內容覆蓋本進程地址空間

abc執(zhí)行abcxyz用xyz覆蓋abc執(zhí)行xyzxyz第二十一頁，共185頁。例子：執(zhí)行可運行文件copy，其功能是拷貝文件，其運行格式為：copyoldfilenewfile另一個名為cpfile的程序具體調用copy，其源程序如下： main(intargc,char*argv[]) { if(fork()==0) execl(“copy”,“copy”,argv[1],argv[2]],0); wait((int*)0); printf(“copydone\n”); } 第二十二頁，共185頁。在用戶環(huán)境下，程序的執(zhí)行通常由命令解釋器shell來完成，標準的命令格式為：cmd[-options][arguments]shell可識別的命令類型有：1、簡單命令catfile12、多條命令who;date;ps3、復合命令ps–e|grepstudent2(ls;catfile3;pwd)>run_log4、后臺命令ls–lR/home/teacher>tlist&第二十三頁，共185頁。1.3.3構件原語

“軟件復用”和“模塊組裝”理念

程序內部：簡單功能劃分；純代碼設計

程序外部：使用構件原語進行功能重疊和組裝UNIX包含兩種構件原語：

①輸入輸出重定向

②管道第二十四頁，共185頁。I/O重定向（I/Oredirect）：一個進程通常(default)打開三個文件：標準輸入文件（fd=0）標準輸出文件（fd=1）標準錯誤輸出文件（fd=2）例如：grepabcgrepabc<file1grepabc<file1>file2grepabc<file1>file22>file3第二十五頁，共185頁。管道（pipe）：

A進程將標準輸出重新定向到管道中去；B進程將標準輸入重新定向從管道中來。例如：

ps-e|grepstudent3|wc-l

查看當前系統(tǒng)中與用戶student3相關的進程有多少

A進程的輸出B進程的輸入第二十六頁，共185頁。1.4操作系統(tǒng)服務

UNIX操作系統(tǒng)提供五種主要的服務（也是UNIX核心的五個重要組成部分）：

1．進程管理建立、終止、掛起、通信等

2．時鐘管理分時共享cpu，時間片，調度

3．存儲管理二級存貯器（內存和對換區(qū)），分配主存

4．文件系統(tǒng)管理二級存貯結構。分配和收回存貯區(qū)和索引節(jié)點

5．設備管理對I/O設備進行有控制的存?。ǘ噙M程系統(tǒng)的特征）第二十七頁，共185頁。內核提供的服務的特點：服務是透明的

①文件類型透明：用戶可不關心是普通文件還是外部設備，但O.S自己要關心文件類型！

②文件系統(tǒng)的透明：文件系統(tǒng)類型、存放的物理位置。

③存貯方式透明：文件的存放位置、存放方式、存放格式

④各用戶進程能得到核心相同服務：無論系統(tǒng)程序還是用戶程序，平等對待，分時運行第二十八頁，共185頁。1.5硬件假設

（假設機器硬件只支持的運行狀態(tài)）UNIX系統(tǒng)上進程的執(zhí)行分成兩種狀態(tài)：

用戶態(tài)、核心態(tài)

用戶態(tài)：進程正在執(zhí)行用戶代碼時的狀態(tài)核心態(tài)：進程正在執(zhí)行系統(tǒng)代碼（系統(tǒng)調用）時的狀態(tài)用戶態(tài)和核心態(tài)的區(qū)別：

①用戶態(tài)：進程只能存取自己的地址空間

核心態(tài)：進程可存取核心和用戶地址空間

②用戶態(tài)：不能存取特權指令，只能存取自己的指令和數據

核心態(tài)：除了能存取自己的指令和數據外，還可存取特權指令

第二十九頁，共185頁。一個進程在運行時必須處在，而且只能處在或者核心態(tài)或者用戶態(tài)下：核心態(tài)的進程不是與用戶進程平行運行的孤立的進程集合，而是每個用戶進程的一部分?！昂诵姆峙滟Y源”:一個在核心狀態(tài)下執(zhí)行的進程分配資源。一個進程某時在“用戶態(tài)”下運行，另一時刻又在“核心態(tài)”下運行，在其生命周期內可能在這兩種狀態(tài)間切換多次用戶態(tài)核心態(tài)012345timeA

|

B

|

C

|

D

|

A

|第三十頁，共185頁。

核心——處在核心態(tài)下的進程的相應部分的集合硬件是按核心態(tài)和用戶態(tài)來執(zhí)行操作的，但對這兩種狀態(tài)下正在執(zhí)行程序的多個用戶是相同對待的。

readwriteopen

A進程B進程C進程第三十一頁，共185頁。1.5.1中斷與例外中斷（要保存上下文）：來自進程之外的事件（外設、時鐘等）引起的，發(fā)生在兩條指令執(zhí)行之間，中斷服務完畢后從下一條指令繼續(xù)執(zhí)行。(中斷服務是由核心中特殊的函數，而不是特殊的進程來執(zhí)行的)例外（不保存上下文）：來自進程內部的非期望事件（地址越界，除數為0等），發(fā)生在一條指令執(zhí)行過程中，例外事件處理完后重新執(zhí)行該指令。第三十二頁，共185頁。1.5.2處理機執(zhí)行級用一組特權指令給處理機設置一個執(zhí)行級，以屏蔽同級和低級的中斷，最大限度地減少其它事件的干擾，使當前任務順利執(zhí)行并盡快完成；但開放更高級的中斷，以響應更緊迫的請求。中斷事件中斷級別硬件故障高低時鐘硬盤網絡終端軟件中斷第三十三頁，共185頁。1.5.3存儲管理

UNIX系統(tǒng)中的存儲管理原則(或特點)：1．當前正在執(zhí)行的進程（全部或部分）駐留在主存中；2．核心是永遠駐留在主存中的（是永遠活動的?。?．編譯程序產生的指令地址是虛地址（邏輯地址）；4．程序運行時核心與硬件（存儲管理部件MMU）一起建立虛地址到物理地址的映射。

核心永遠是活躍的普通進程具有特定的生命周期（除非人為設定為無限循環(huán)）第三十四頁，共185頁。

readwriteopenclose...核心代碼段A進程B進程openreadreadwrite映射映射只是用戶進程中的核心態(tài)下運行的代碼段常駐內存，而非整個用戶進程常駐內存。這些代碼段是“可再入段”（或純代碼段、可共享代碼段），被各用戶進程段共享，為提高運行速度，避免頻煩訪問磁盤，故常駐內存，這些代碼段的集合就是OS的內核。第三十五頁，共185頁。第二章核心導言2.1UNIX操作系統(tǒng)的體系結構“文件”和“進程”是UNIX系統(tǒng)的兩個最基本實體和中心概念，UNIX系統(tǒng)的所有操作都是以這兩者為基礎的。整個系統(tǒng)核心由以下五個部分組成：

①文件系統(tǒng)：文件管理和存儲空間管理（節(jié)點和空間管理）

②I/O設備管理：核心→緩沖→塊設備（隨機存取設備）核心→原始設備（raw設備，字符設備，裸設備）

③進程控制：進程的調度、同步和通訊

④存貯管理：在主存與二級存儲之間對程序進行搬遷

⑤時鐘管理：把cpu的時間分配給當前最高優(yōu)先權的進程。第三十六頁，共185頁。

硬件硬件控制字符設備

塊設備設備驅動程序高速緩沖文件子系統(tǒng)系統(tǒng)調用界面程序庫進程控制子系統(tǒng)進程間通訊調度程序存儲管理用戶程序用戶級核心級核心級硬件級陷入第三十七頁，共185頁。2.2系統(tǒng)概念2.2.1文件系統(tǒng)概貌

1．索引節(jié)點（indexnode——inode）

inode特征：文件的內部名稱（或代號），方便機器操作；每個文件都有一個且只有一個inode與之對應；inode存放文件的靜態(tài)參數：存放地點、所有者、文件類型、存取權限、文件大小等；每個文件都可以有多個名字，但都映射到同一個inode上；各inode之間以inode號相區(qū)別；第三十八頁，共185頁。2．鏈結（link）——對應命令名ln文件i節(jié)點abcxyz文件名·一個文件可有多個名字，多個名字都對應同一個文件i節(jié)點，每個名字就是該文件節(jié)點的一個鏈結；.一個普通文件的名字個數，就是該文件的鏈結數；·每個鏈接名可以放在不同的目錄下（同一個文件系統(tǒng)下）；·刪除一個鏈接名時，文件鏈接數減一。如鏈接數不為零，則文件（節(jié)點）仍然存在。第三十九頁，共185頁。使用文件鏈結的目的：①方便用戶的使用習慣，如“列目錄”，可用ls、dir、list、lc等；②誤刪文件時可補救，又不多占空間。abc和xyz具有相同的i結點號；③減少移植應用程序時，因使用指定位置的文件，而拷貝該文件到指定位置去的麻煩。第四十頁，共185頁。3．符號鏈結（symbollink）——對應命令名ln-s文件i節(jié)點abcxyz文件名

給文件的名字再取一個名字，而不是給文件節(jié)點再取一個名字。鏈接的是“符號”而不是文件，因此“符號”可以是不存在的文件，即無意義的字符串。abc和xyz具有不同的inode號，xyz的內容是它所指向的名字的字符串，大小是字符串長度為3字節(jié)?！捌胀ㄦ溄Y”中各名字必須在同一文件系統(tǒng)中，“符號鏈結”可在不同的文件系統(tǒng)中。第四十一頁，共185頁。4．活動i節(jié)點表（索引節(jié)點表）——inode表

在內存中存放當前要使用的文件inode的表（或稱為活動i節(jié)點表），表中的每一個表項對應一個當前正被使用的文件的狀態(tài)信息。這樣要使用（打開）同一個文件的進程不必再到盤上去尋找了，（共享！）第四十二頁，共185頁。5．用戶打開文件表（或稱用戶文件描述符表）在系統(tǒng)中每一個進程都有一個描述該進程的數據結構user（類似于描述文件的i節(jié)點），在user中有一個數組，存放一組指針指向系統(tǒng)打開文件表中該進程打開的文件所對應的表項。structfile*u_o]NOFILE為每個進程最多可同時打開的文件數，這與系統(tǒng)中的進程數和內存大小以及交換區(qū)大小等有關系，一般為20~100。這個u_ofile數組就是該進程的用戶打開文件表。第四十三頁，共185頁。6．系統(tǒng)打開文件表（file表）

系統(tǒng)打開文件表主要存放被打開文件的讀寫指針。因為一個進程在一個時間片內可能讀寫不完所需內容，需要在下一個時間片繼續(xù)從上一個時間片結束時的讀寫位置開始讀寫，故在進程生存期間應保持一讀寫指針。此外file表中還存放被打開文件的動態(tài)信息：如文件狀態(tài)、引用計數（當前使用該文件的進程數）等。第四十四頁，共185頁。A進程B進程file表活動inode表用戶打開文件表系統(tǒng)打開文件表活動i節(jié)點表第四十五頁，共185頁。為什么要單獨設立一個file表來存放讀寫指針呢？由于可能有多個進程要共享一個被打開文件的inode，而每個進程的讀寫指針都不相同，故不能放在inode表中。

另一方面，要使不同進程的打開文件指針（文件描述符）或同一進程的不同打開文件指針能夠共享一個打開文件指針（協(xié)同操作），就不能把讀寫指針放進某一個進程的用戶打開文件表中。

因此只能在用戶打開文件表和活動inode表之外再建立一個系統(tǒng)打開文件表（file表）來存放讀寫指針。第四十六頁，共185頁。

UNIX操作系統(tǒng)中共享活動文件的方法：

在內存中某個活動文件的副本只有一個，不同的進程采用不同的指針指向這文件的副本。由于任一時刻只有一個進程在運行（微觀上看），故該文件也只要求內存中有一個副本即可，只是各個進程有自己的讀寫指針而已。這是在UNIX系統(tǒng)中共享文件（包括用戶文件和系統(tǒng)文件）的主要方法。對其它資源的共享采用的是與之相似的另外幾種方法。第四十七頁，共185頁。2.2.2進程相關概念：映像——

程序以及與動態(tài)執(zhí)行該程序有關的各種信息的集合(類似于歷史檔案)。它包括存儲器映象、通用寄存器映像，地址映射空間、打開文件狀態(tài)等。進程——

對映像的執(zhí)行。對映像的執(zhí)行也就是一個程序在虛擬機上動態(tài)執(zhí)行的過程。第四十八頁，共185頁。可執(zhí)行文件的構成：

進程是可執(zhí)行文件的一次執(zhí)行實例，高級語言程序經過編譯或匯編語言程序經過匯編后所產生的、缺省名為a.out的可執(zhí)行文件的結構包括圖示四個部分：

文件頭正文段數據標識段其它信息段第四十九頁，共185頁。文件頭——·文件的幻數（magicnumber）·編譯器的版本號·機器類型·正文段、數據標識段、其它信息段的大小·程序入口點正文段——程序的功能代碼數據標識段——標識未初始化的數據要占用的空間大小其它信息段——主要用于存放符號表第五十頁，共185頁。程序的執(zhí)行一個進程在執(zhí)行系統(tǒng)調用exec時，把可執(zhí)行文件裝入本進程的三個區(qū)域中：

正文區(qū)：對應可執(zhí)行文件的正文段

數據區(qū)：對應可執(zhí)行文件的數據標識段

堆棧區(qū)：新建立的進程工作區(qū)堆棧主要用于傳遞參數，保護現(xiàn)場，存放返回地址以及為局部動態(tài)變量提供存儲區(qū)。進程在核心態(tài)下運行時的工作區(qū)為核心棧，在用戶態(tài)下運行時的工作區(qū)為用戶棧。核心棧和用戶棧不能交叉使用。第五十一頁，共185頁。堆棧使用舉例。有如下程序，在主程序中調用函數，并進行參數傳遞：main(intargc,char*argv[]){charbuf[1024];intnumber;

…readfile(buf,number);

…}readfile(charbuffer[],intline){char*pointer;inttemp;

…}第五十二頁，共185頁?？諚ｍ斨羔槜５字羔樀偷刂犯叩刂酚脩魲＿M入主程序時的堆棧狀況第五十三頁，共185頁。棧頂指針棧底指針低地址高地址調用main()時argc,argv本程序返回地址棧底指針暫存處buf,number第五十四頁，共185頁。棧頂指針棧底指針低地址高地址調用readfile時argc,argv本程序返回地址棧底指針暫存處buf,numberbuffer,linereadfile的返回地址棧底指針暫存處pointer,temp第五十五頁，共185頁。3.進程的標識進程由其進程標識號PID來識別。0#進程

是由機器上電時“手工”創(chuàng)建的，調用fork創(chuàng)建了1#進程后，成為對換進程（swap）。1#進程init進程，由它來創(chuàng)建系統(tǒng)初始化過程中所需的其它所有的進程。父進程調用fork系統(tǒng)調用的進程子進程由系統(tǒng)調用fork產生的進程除0#進程外，其它所有進程都是另一個進程調用fork后產生的。第五十六頁，共185頁。進程狀態(tài)及狀態(tài)轉換①運行狀態(tài)此時進程正在占用處理機，進程的全部映像駐在內存中。②就緒狀態(tài)此時進程基本具備了運行條件，正在等待使用處理機。③睡眠狀態(tài)進程不具備運行條件，需等待某種事件的發(fā)生，無法繼續(xù)執(zhí)行下去。第五十七頁，共185頁。

調度調度睡眠喚醒中斷第五十八頁，共185頁。5.在UNIX環(huán)境下，進程有如下特征：

①每個進程在核心進程表（proc數組）都占有一項，在其中保留相應的狀態(tài)信息。

②每個進程都有一個“每進程數據區(qū)（perprocessdataarea----ppda）”保留相應進程更多的信息和核心棧；

③處理機的全部工作就是在某個時候執(zhí)行某個進程

④一個進程可生成或消滅另一進程

⑤一個進程中可申請并占有資源

⑥一個進程只沿著一個特定的指令序列運行，不會跳轉到另一個進程的指令序列中去，也不能訪問別的進程的數據和堆棧。（抗病毒傳播的重要原因之一）第五十九頁，共185頁。第三章數據緩沖區(qū)高速緩沖硬件緩存（cache）

由一種高速寄存器（register）組成，主要解決CPU與RAM之間的速度差問題。數據緩沖區(qū)高速緩沖（buffer）

由軟件實現(xiàn)的解決文件系統(tǒng)和物理硬盤之間的數據同步的一種方法。數據緩沖區(qū)高速緩沖是UNIX特有的對數據并發(fā)訪問的一種控制機制。第六十頁，共185頁。問題的提出：1、磁盤機械運行速度大大低于處理機的運行速度；2、多進程并發(fā)運行，少量的磁盤（通道）I/O成為瓶頸；3、數據訪問的隨機性，磁盤忙閑不均第六十一頁，共185頁。解決辦法：1、建立一個被稱為數據緩沖區(qū)高速緩沖（簡稱高速緩沖）的內部數據緩沖區(qū)池（bufferpool）來存放要用的數據；2、寫數據時把數據盡量多地盡量長時間地保存在緩沖池中

延遲寫出到磁盤上以備后續(xù)進程使用3、讀數據時先在緩沖池中查找已有的數據如沒有，再從磁盤讀取，并保存在緩沖池中事先預讀數據到緩沖池中第六十二頁，共185頁。3.1緩沖區(qū)及緩沖區(qū)首部

緩沖區(qū)池由若干個緩沖區(qū)組成，每一個緩沖區(qū)又由兩部分組成：一個實際存放數據的存儲區(qū)和一個標識該緩沖區(qū)的緩沖區(qū)首部。存儲區(qū)

因為緩沖區(qū)首部與數據存儲區(qū)之間有一一對應的關系，所以通常把兩者統(tǒng)稱為緩沖區(qū)。緩沖區(qū)是緩沖區(qū)池中數據存儲的基本單位。緩沖區(qū)首部第六十三頁，共185頁。緩沖區(qū)首部的定義:structbuf{緩沖區(qū)標志標識緩沖區(qū)狀態(tài)緩沖區(qū)鏈接指針向前向后串成鏈表空閑緩沖區(qū)鏈表指針聯(lián)結空閑緩沖區(qū)設備號標識緩沖區(qū)塊號union{緩沖區(qū)中的數據類型數據塊超級塊柱面塊i節(jié)點塊}b_un其它控制信息}第六十四頁，共185頁。3.2緩沖池的結構1、最近最少使用（LRU）算法：程序設計采用模塊化和層次化結構，盡量避免使用goto語句，程序跳轉少，適應“流水線（pipeline）”體系結構的系統(tǒng)；特定時間段內，程序在一個相對集中空間（代碼段）內運行，涉及的數據（廣義的：文件名、變量、指針和數組等）的個數相對較少；當前使用過的數據，馬上還要使用的可能性最大，較長時間未用過的數據，即將使用的可能性最小。第六十五頁，共185頁。2、緩沖池設計基本原則：存放有剛使用過的數據盡量長時間地保留在內存中，以便馬上還要使用時能在內存中找到；需要騰出內存空間時，把很久都未使用過（即最近最少使用）的數據交換到磁盤上去。這些數據馬上還要使用的可能性最小。第六十六頁，共185頁。3、空閑緩沖區(qū)鏈表核心維護了一個空閑緩沖區(qū)鏈表，它按照最近被使用的先后次序排列?？臻e鏈表是一個以空閑緩沖區(qū)鏈表頭開始的“雙向循環(huán)鏈表”。鏈表的開始和結束都以鏈表頭為標志。

鏈表頭空閑緩沖區(qū)1空閑緩沖區(qū)2空閑緩沖區(qū)3空閑緩沖區(qū)n第六十七頁，共185頁。4、空閑緩沖區(qū)鏈表操作

取用任意空閑緩沖區(qū)從空閑緩沖區(qū)鏈表的表頭位置取下一個空閑緩沖區(qū)，后面的空閑緩沖區(qū)依次向前移動。

釋放一個空閑緩沖區(qū)把這個裝有數據的空閑緩沖區(qū)附加到空閑鏈表的鏈尾。只有當該空閑緩沖區(qū)所裝數據出錯時才掛到鏈頭。

取用裝有指定內容的空閑緩沖區(qū)從鏈表頭開始查找，找到后取下使用，用完后放到鏈尾。當系統(tǒng)不斷從鏈頭取用空閑緩沖區(qū)，又把使用過的（裝有數據的）緩沖區(qū)掛到鏈尾，一個裝有有效數據的緩沖區(qū)就會逐漸向鏈表頭移動。在鏈表頭位置的就是“最近最少使用”的空閑緩沖區(qū)。第六十八頁，共185頁。5、空閑緩沖區(qū)分類

系統(tǒng)中共設置了四個空閑緩沖區(qū)鏈表，根據緩沖區(qū)的不同用途而把它的放入不同的空閑緩沖區(qū)鏈表中。避免在取用空閑緩沖區(qū)時，逐個判斷緩沖區(qū)中的內容。這四個空閑鏈表是：0#空閑緩沖區(qū)鏈表——存放文件系統(tǒng)超級塊1#空閑緩沖區(qū)鏈表——存放通常使用的數據塊2#空閑緩沖區(qū)鏈表——存放延遲寫、無效數據或錯誤內容3#空閑緩沖區(qū)鏈表——存放沒有對應存儲空間的緩沖區(qū)首部如果某種類型的空閑緩沖區(qū)不夠用時，核心也從其它空閑緩沖區(qū)鏈表中取用空閑緩沖區(qū)。第六十九頁，共185頁。6、緩沖區(qū)設置

當核心需有一個空閑緩沖區(qū)時，它根據要裝入的數據類型，從相應的空閑緩沖區(qū)鏈表的表頭位置取下一個空閑緩沖區(qū)，裝入一個磁盤數據塊；根據該數據塊所對應的設備號和塊號數據對計算其hashno（散列、雜湊）值，根據其hashno的值放入到相應hash鏈表的鏈頭。

hashno=((diskno+blkno)/RND)%BUFHSZ

diskno：設備號

blkno：塊號

BUFHSZ：最大hash值，通常為63。

RND：隨機數，其值為：RND=MAXBSIZE/DEV_BSIZE

MAXBSIZE：最大文件系統(tǒng)塊的大小

DEV_BSIZE：物理設備塊大小

hashno的取值范圍：0~62第七十頁，共185頁。7、緩沖池的結構具有相同hashno的緩沖區(qū)鏈接在同一個hash鏈表中，因此系統(tǒng)中共有63個hash鏈表，分別鏈接hashno為0~62的緩沖區(qū)。每一個hash鏈表都是一個由鏈表頭指向的雙向循環(huán)鏈表，查找某一個指定hashno值的緩沖區(qū)時，也是從相應的hash鏈表的表頭位置開始向表尾方向進行查找。這63個hash鏈表就構成了數據緩沖區(qū)高速緩沖的緩沖池，所有的緩沖區(qū)都存放在緩沖池中的某一個鏈表中。鏈表頭緩沖區(qū)1緩沖區(qū)2緩沖區(qū)3緩沖區(qū)nhash鏈表的結構第七十一頁，共185頁。緩沖區(qū)緩沖區(qū)緩沖區(qū)緩沖區(qū)緩沖區(qū)緩沖區(qū)緩沖區(qū)緩沖區(qū)緩沖區(qū)空閑鏈表頭Hash鏈表頭hashno=0hashno=1hashno=62緩沖池的結構第七十二頁，共185頁。8、緩沖區(qū)的使用如果要找特定緩沖區(qū)，根據hashno從相應的hash鏈表的表頭處開始逐個向后查找；如果找到，則直接取用，并將其移動到hash鏈的鏈頭；如果未找到，則從相應的空閑緩沖區(qū)鏈表的表頭處取下一個空閑緩沖區(qū)，填入相應數據，重新計算其hashno，并放到新的hash鏈表的表頭；釋放緩沖區(qū)時，將該緩沖區(qū)仍保留在原h(huán)ash隊列中，同時掛接到空閑緩沖區(qū)鏈表的表尾。（同時在兩個隊列中）申請緩沖區(qū)的兩個途徑：要指定緩沖區(qū)——在hash鏈表中查找要空閑緩沖區(qū)——在空閑鏈表中查找第七十三頁，共185頁。9、進一步說明一個緩沖區(qū)只有當它是空閑狀態(tài)時，它才同時處在hash鏈表和空閑鏈表中。如果不空閑，則它只能處在某一個hash鏈表中。在空閑緩沖區(qū)鏈表中的緩沖區(qū)一定在某個hash鏈表中；在hash鏈表中的緩沖區(qū)不一定在空閑鏈中。不存在脫離hash鏈表的另一個空閑的緩沖區(qū)鏈表。緩沖池中的緩沖區(qū)個數是固定不變的，每個緩沖區(qū)在不同時刻存放著不同的磁盤數據塊，具有不同的hash值，因此處在不同的hash鏈表中。緩沖區(qū)中的數據與某個磁盤數據塊一一對應，這種對應有兩個特點：

①一個磁盤數據塊在緩沖池中最多只能有一個副本；

②緩沖區(qū)與數據塊的對應是動態(tài)的，LRU數據塊將被釋放。第七十四頁，共185頁。3.3緩沖區(qū)的檢索算法

在UNIX文件系統(tǒng)中的下層，即直接與邏輯存儲設備聯(lián)系的部分，包含如下基本算法：

getblk申請一個緩沖區(qū)brelse釋放一個緩沖區(qū)bread讀一個磁盤塊breada讀一個磁盤塊，預讀另一個磁盤塊bwrite寫磁盤塊第七十五頁，共185頁。1、申請一個緩沖區(qū)算法getblk根據緩沖池的結構，核心申請一個緩沖區(qū)分配個磁盤塊時，可能出現(xiàn)的五種典型狀況：

①

該塊已在hash隊列中，并且緩沖區(qū)是空閑的；

②

hash隊列中找不到該塊，需從空閑鏈表中分配一個緩沖區(qū)；

③

hash隊列中找不到該塊，在從空閑鏈表中分配一個緩沖區(qū)時，發(fā)現(xiàn)該空閑緩沖區(qū)標記有“延遲寫”，核心必須寫出緩沖區(qū)內容到磁盤上，再重新分配一個空閑緩沖區(qū)；

④

hash隊列中找不到該塊，并且空閑鏈表已空；

⑤

該塊已在hash隊列中，但該緩沖區(qū)目前狀態(tài)為“忙”。第七十六頁，共185頁。2、釋放一個緩沖區(qū)算法brelse

喚醒等待緩沖區(qū)的所有進程提高處理機的執(zhí)行級別以封鎖同級或低級的中斷將該緩沖區(qū)放到空閑隊列的尾部（緩沖區(qū)有效）或頭部（緩沖區(qū)無效）降低處理機的執(zhí)行級別以開放中斷第七十七頁，共185頁。3、讀一個磁盤塊bread由getblk算法申請一個可用的緩沖區(qū)如果緩沖區(qū)中的內容有效，則直接返回該緩沖區(qū)如果緩沖區(qū)中的內容無效，則啟動磁盤去讀所需的數據塊等待磁盤操作完成后返回第七十八頁，共185頁。4、讀一個磁盤塊并預讀另一個磁盤塊breada

預讀的前提：程序是在一個有限的空間內運行，程序對數據的訪問是可預見的。

預讀的命中率：不一定達到100%，但良好的系統(tǒng)結構和算法可使命中率達到較高的水平。

預讀的結果：放在緩沖池內，以免需要的時候再去啟動磁盤讀數據塊。第七十九頁，共185頁。5、寫磁盤塊bwrite

啟動磁盤驅動程序的寫操作如果是“同步寫”，則本進程睡眠等待磁盤寫操作的完成，磁盤寫操作完成后，中斷喚醒本進程，本進程釋放該緩沖區(qū)并返回；如果是“異步寫”，則無需等待磁盤寫操作的完成，將緩沖區(qū)放到空閑鏈表的表頭，以便隨后某個進程申請空閑緩沖區(qū)時，將其寫到磁盤上去。本進程不再關心該緩沖區(qū)實際被寫出的時間和結果，而直接返回去作其它事情。事實上無論是同步寫還是異步寫，其根本區(qū)別在于本進程是否等待磁盤驅動程序完成操作后所發(fā)出的中斷信號。第八十頁，共185頁。3.3數據緩沖區(qū)高速緩沖的優(yōu)缺點優(yōu)點：提供了對磁盤塊的統(tǒng)一的存取方法消除了用戶對用戶緩沖區(qū)中數據的特殊對齊需要減少了磁盤訪問的次數，提高了系統(tǒng)的整體I/O效率有助于保持文件系統(tǒng)的完整性缺點：數據未及時寫盤而帶來的風險額外的數據拷貝過程，大量數據傳輸時影響性能第八十一頁，共185頁。第四章文件和文件系統(tǒng)的內部結構現(xiàn)代UNIX的文件系統(tǒng)通常可由三大模塊組成：①本地文件系統(tǒng)（UFS）——User②網絡文件系統(tǒng)（NFS）——Network③虛擬文件系統(tǒng)（VFS）——Virtual第八十二頁，共185頁。本地文件系統(tǒng)（UFS）是UNIX系統(tǒng)中的基本文件系統(tǒng)，它通常固定存放在本地機器的存貯設備上，任何一種結構形式的文件系統(tǒng)都必然會直接或間接地與某個本地文件系統(tǒng)相聯(lián)系。本地文件系統(tǒng)的構成一個根文件系統(tǒng)+若干子文件系統(tǒng)所組成根文件系統(tǒng)存放本操作系統(tǒng)的最主要和最基本的部分可獨立啟動運行系統(tǒng)起動后，根文件系統(tǒng)就不能卸下來子文件系統(tǒng)主要存放應用程序和用戶文件一般不能獨立啟動系統(tǒng)運行過程中可隨時安裝和卸下第八十三頁，共185頁。網絡文件系統(tǒng)（NFS）

是本地機器上的文件系統(tǒng)和遠地機器上的文件系統(tǒng)之間的介質，它管理和控制所有有關對遠地文件的各種操作，給本地用戶提供一個訪問遠地文件的使用方便的高層接口，避免用戶直接涉及網絡通訊方面的具體細節(jié)。第八十四頁，共185頁。虛擬文件系統(tǒng)（VFS）VFS是整個操作系統(tǒng)的用戶界面，它給用戶提供一個統(tǒng)一的文件系統(tǒng)使用接口，避免用戶涉及各個子文件系統(tǒng)的特征部分。用戶感覺使用的是一個整體的，比本地機器上實際硬盤空間大得多的文件系統(tǒng)。虛構文件系統(tǒng)接受來自用戶的操作請求，根據該操作所訪問的文件是存放在本地機器上，還是存放在遠地機器上而分別把操作交給本地文件系統(tǒng)或網絡文件系統(tǒng)；本地文件系統(tǒng)或網絡文件系統(tǒng)（實際上再傳給遠地機器上的本地文件系統(tǒng)）進行相應的操作后，將結果返回到虛擬文件系統(tǒng)中再傳回給用戶。第八十五頁，共185頁。網絡虛擬文件系統(tǒng)VFS網絡文件系統(tǒng)NFS本地文件系統(tǒng)UFS物理存儲介質虛擬文件系統(tǒng)VFS網絡文件系統(tǒng)NFS本地文件系統(tǒng)UFS物理存儲介質用戶用戶A機器B機器基于虛擬文件系統(tǒng)的體系結構第八十六頁，共185頁。4.1文件系統(tǒng)結構

4.1.1本地文件系統(tǒng)1．文件的存貯結構UNIX的普通文件的邏輯結構是無格式的有序字節(jié)流，而它們的物理存貯結構是以索引方式來組織的。每個文件都是由一個索引節(jié)點i節(jié)點來表示的，每個i節(jié)點由其i節(jié)點號來標識。i節(jié)點通常以靜態(tài)的形式存放在磁盤的i節(jié)點表中。每個磁盤i節(jié)點表項是由數據結構icommon定義的，描述對應文件的靜態(tài)參數。第八十七頁，共185頁。超級塊磁盤i節(jié)點表數據存儲區(qū)磁盤icommon表icommonicommonicommonicommonicommon文件所有者標識（UID）用戶組標識（GID）文件類型（FIFO、DIR、CHR、BLK、REG、LNK等）文件保護模式（存取許可權）mode文件存取時間（atime,mtime,ctime）鏈接數目link文件大小size文件數據塊索引表indextable第八十八頁，共185頁。icommon與inode的關系

進程要讀寫一個文件時，先在內存的活動i節(jié)點表（即inode表）中申請一個空閑的活動i節(jié)點，并把磁盤上i節(jié)點（icommon）中的各項參數讀入其中，當核心操作完成后，如果必要，就把在內存中的活動i節(jié)點寫回到磁盤上去。內存活動i節(jié)點由數據結構inode來定義，它除了包含磁盤上對應的icommon中的各項參數外，還包含有其它的參數，如該活動i節(jié)點的狀態(tài)、文件所在的邏輯設備號、i節(jié)點號、活動i節(jié)點鏈接指針，最近使用的i節(jié)點在目錄中的位置等動態(tài)信息。第八十九頁，共185頁。structinode{活動i節(jié)點鏈接指針狀態(tài)標志設備號i節(jié)點號最近訪問的i節(jié)點在目錄中的位置空閑i節(jié)點鏈接指針structincommon{文件模式和類型（FIFO、DIR、CHR、BLK、REG、LNK等）文件鏈接數文件所有者標識數（UID）文件所屬用戶組標識數（GID）文件大小文件最近存取時間（atime,mtime,ctime）數據塊索引表其它信息}}第九十頁，共185頁。2、數據塊索引表數據塊索引表用于檢索本文件占用的數據塊。它包含12項直接索引表目和3項間接索引表目。根據要讀寫的數據在文件中的位置可計算出該數據所在的邏輯塊號，查索引表就可找到邏輯塊所在的文件系統(tǒng)塊號。系統(tǒng)根據計算出來的邏輯塊號判斷是否包含在直接索引表中，如果則取出直接索引表中的文件系統(tǒng)塊號；如不是，則看是否包含在一次間接索引塊中，否則再尋找二次和三次間接索引塊。最長要存取三次間址索引塊才能找到相應數據的文件系統(tǒng)塊號（要取出數據則要讀4次磁盤）。

第九十一頁，共185頁。直接0直接1直接2直接11一次間址二次間址三次間址數據塊索引表一級間址塊二級間址塊三級間址塊數據塊第九十二頁，共185頁。3、inode表的結構在內存中，活動i節(jié)點表類似于數據緩沖區(qū)高速緩沖中的緩沖池結構?；顒觟節(jié)點表中的每一項就是一個活動i節(jié)點緩沖區(qū)，用來存放一個被打開文件的inode。（以下把活動i節(jié)點緩沖區(qū)簡稱為“活動i節(jié)點”）?？臻e的活動i節(jié)點相互鏈接在一起構成“空閑活動i節(jié)點鏈表”，這是一個雙向（非循環(huán)）鏈表，分別由鏈頭指針和鏈尾指針指向空閑活動i節(jié)點鏈表的開始和結束。如下圖所示：第九十三頁，共185頁。鏈表頭空閑i節(jié)點1空閑i節(jié)點2空閑i節(jié)點3空閑i節(jié)點n空閑活動i節(jié)點鏈表為雙向（非循環(huán)）鏈表，分別由鏈表頭指針和鏈表尾指針指向空閑鏈表的首尾。NULL鏈表尾第九十四頁，共185頁。活動i節(jié)點hash鏈表當某個文件（即某個磁盤i節(jié)點）被打開時，根據該i節(jié)點所對應的設備號和i節(jié)點號計算其hash值：

hn=(devno+inumber)%64可得到0~63共64個hash值。具有相同hash值的活動i節(jié)點鏈接在同一個hash鏈表中，這樣內存中就有64個hash鏈表，每個hash鏈表都是由hash鏈頭開始的雙向鏈表（與數據緩沖區(qū)鏈表不同的是此處的空閑和非空閑鏈表都是非循環(huán)的）。內存活動i節(jié)點表就是由這64個hash鏈表組成。如下圖所示：第九十五頁，共185頁。inodeinodeinodeinodeinodeinodeinodeinodeinode空閑鏈表頭Hash鏈表頭hn=0hn=1hn=63NULL空閑鏈表尾活動inode表的結構第九十六頁，共185頁。4、文件系統(tǒng)的存儲結構

在UNIX系統(tǒng)中，一個物理磁盤通常被劃分成一個或多個邏輯文件系統(tǒng)（簡稱文件系統(tǒng)或子文件系統(tǒng)），每個邏輯文件系統(tǒng)都被當作一個由邏輯設備號標識的邏輯設備。UNIX的普通文件和目錄文件就保存在這樣的文件系統(tǒng)中。邏輯文件系統(tǒng)的存儲結構可分為兩類型：

一級存儲結構型：常用于運行環(huán)境較小的文件系統(tǒng)中

二級存儲結構型：常用于運行環(huán)境較大（特別是硬盤空間較大）的文件系統(tǒng)中第九十七頁，共185頁。①、一級存儲結構型這種類型的邏輯文件系統(tǒng)由超級塊、索引節(jié)點表塊和數據區(qū)組成，（如果是根文件系統(tǒng)，就還包括引導塊）。整個存儲結構是一維的。引導塊超級塊i節(jié)點表塊數據區(qū)引導塊：boot程序超級塊：fs結構，存放文件系統(tǒng)的靜態(tài)參數i節(jié)點表塊：磁盤icommon表數據區(qū)：各數據塊第九十八頁，共185頁。②、兩級存儲結構型

這種存儲結構的文件系統(tǒng)由兩級組成：第一級由超級塊和若干個柱面組塊（cylindergroupblock）所組成（如果是根文件系統(tǒng)則還包括引導塊）。第二級（即柱面組塊）又是由超級塊拷貝塊、柱面組信息塊，i節(jié)點表塊和數據區(qū)所組成。文件系統(tǒng)的存儲結構是二維的。目前大多數在大存儲環(huán)境下運行的UNIX版本都采用這種存貯結構，其優(yōu)點是能快速定位數據塊。

第一級存儲結構引導塊超級塊1號柱面組塊2號柱面組塊……n號柱面組塊

第二級存儲結構超級塊拷貝塊柱面組信息塊i節(jié)點表塊數據區(qū)第九十九頁，共185頁。超級塊是由fs定義的數據結構，用于存放文件系統(tǒng)的靜態(tài)參數：structfs{內存超級塊鏈接指針超級塊的磁盤地址柱面組塊的位移量最近修改時間文件系統(tǒng)大小文件系統(tǒng)塊大小柱面組數柱面組大小片大小文件系統(tǒng)標識數文件系統(tǒng)標志區(qū)最近訪問的柱面組號確定分配算法的參數}第一百頁，共185頁。超級塊拷貝塊：在每個柱面組塊中存放有一個超級塊拷貝塊，其目的是使系統(tǒng)在超級塊被意外破壞時，能從任何一個柱面組中進行恢復而不致使整個文件系統(tǒng)陷入癱瘓。

每個柱面組中的超級塊拷貝塊的存放位置為安全起見不一定都裝在柱面組中的最前面，而是可浮動地裝在該柱面組中的任何位置。一般性的方法是：如果第n號柱面組中的超級塊拷貝塊開始于該柱面組中的第i磁道，則第n+1柱面組中的超級塊拷貝塊開始于該柱面組中的第i+1磁道。文件系統(tǒng)一旦建立后，它們的位置就是固定不變的。第一百零一頁，共185頁。柱面組信息塊（cg塊）

柱面組信息塊中存放的是有關該柱面組的靜態(tài)參數，它由數據結構cg來定義：structcg{內存中柱面組塊的鏈接指針本柱面組塊中i節(jié)點表大小本柱面組塊中數據區(qū)大小最近一次所用塊的位置最近一次所用片的位置最近一次所用i節(jié)點的位置本柱面組空閑數據塊總數i節(jié)點位示圖空閑塊位示圖}第一百零二頁，共185頁。位示圖：位示圖為一張表，其中的每一個二進制位（bit）的值來表示某一個資源（例如數據塊或i節(jié)點）的狀態(tài)，這樣每檢測一個字節(jié)的值就可以知道八個資源的狀態(tài)；每檢測一個四字節(jié)的整數的值就可以知道32個資源的狀態(tài)。系統(tǒng)只需要維護一張較小的表（位示圖）就可以快速地檢測指定資源的忙閑狀態(tài)，或快速查找可用的空閑資源。第一百零三頁，共185頁。5、文件系統(tǒng)的數據塊

在文件系統(tǒng)中，按存儲單位來劃分，由大到小可有下列層次：文件系統(tǒng)()柱面組(cylindergroup)柱面(cylinder)磁道(track)扇區(qū)(sector)DEV_BSIZE512字節(jié)第一百零四頁，共185頁。文件系統(tǒng)的邏輯塊大?。篋EV_BSIZE*2?即1k、2k、4k、8k、16k…目的：提高傳輸速度，減少overhead文件系統(tǒng)的邏輯片大?。篋EV_BSIZE*2?即1k、2k、4k、8k、16k…目的：減少文件尾的碎片浪費。第一百零五頁，共185頁。6．目錄和目錄項在UNIX文件系統(tǒng)中，目錄的組織形式采用的是樹形結構，一個邏輯文件系統(tǒng)就是一棵目錄樹。目錄也被當作文件進行處理，一個目錄文件的結構為表狀結構，其中通常包含有若干表項，稱為目錄項，這些目錄項既可以是普通文件的入口，也可以是子目錄的入口。每一個目錄項中通常包含兩部分內容：

文件的i節(jié)點號文件名第一百零六頁，共185頁。目錄/home/student/xiaolan的路徑和目錄結構2。2。。153home0tst85bin85。2。。153。2。。290log376student376。153。。584xiaolan584。376。。409bckup230src409。584。。//home/bin/home/log/home/student/home/student/xiaolan/home/student/xiaolan/src/home.student/xiaolan/bckup第一百零七頁，共185頁。每個目錄項由數據結構direct來定義：#defineMAXNAMLEN14structdirect{shortd_ino;/*目錄項i節(jié)點號*/chard_name[MAXNAMELEN];/*目錄項名字字符串*/}每個目錄項的長度通常是確定的，為16個字節(jié)，其中前兩個字節(jié)存放文件的i節(jié)點號d_ino，后面14個字節(jié)存放文件名d_name。這種定長目錄項在算法實現(xiàn)方面比較簡單，在使用靈活方面都有所不便，并且可能因許多目錄項名字長度不足14字符面有空間浪費。第一百零八頁，共185頁。在UNIX的每個文件系統(tǒng)中，有三個i節(jié)點號是有固定用途的：0號i節(jié)點：表示空目錄項，當某個目錄項被刪除時，該目錄項的i節(jié)點號被置為0。1號i節(jié)點：表示壞塊文件，所有的磁盤壞塊都劃歸到該節(jié)點上；2號i節(jié)點：固定表示該邏輯文件系統(tǒng)的根（root）目錄；3號i節(jié)點：表示該文件系統(tǒng)中的lost+found目錄。第一百零九頁，共185頁。7、變長目錄項的目錄結構#defineMAXNAMLEN255structdirect{longd_ino;/*目錄項i節(jié)點號*/shortd_reclen;/*目錄項入口長度（占用長度）*/shortd_namelen；/*目錄項名字長度*/chard_name[MAXNAMLEN+1]/*名字字符串，+1為串結束符\0*/}

由于目錄中各目錄項的長度是變化的，因此必須在目錄項中標明本目錄項的長度。前一個目錄項釋放時，把該目錄項的空間全部合并到前一個目錄項中，形成前面一個目錄項占用空間大于實際使用的空間。

在增加新目錄時，先查看目錄中各目錄項是否占用多余空間，如有，則進行壓縮，把釋放的空間分配給新目錄項。變長目錄結構增加了算法復雜性和工作量，通常用在硬件性能較高的大型系統(tǒng)中。第一百一十頁，共185頁。8、文件名和文件名緩沖區(qū)

核心在內存中建立了一個高速的名字緩沖區(qū)，用來存放最近使用過的文件名，核心認為“最近使用過的文件名馬上還要使用的可能性最大”。名字緩沖區(qū)是由ncache定義的數據結構，只包含文件名和索引節(jié)點指針等重要信息：structncache{hash鏈表指針LRU鏈表指針文件i節(jié)點指針/*這里只需要節(jié)點指針，因內存中已有活動i節(jié)點表*/

文件父目錄節(jié)點指針

文件名確認信息}第一百一十一頁，共185頁。鏈表頭名字緩沖區(qū)1名字緩沖區(qū)2名字緩沖區(qū)3名字緩沖區(qū)n名字緩沖區(qū)（ncache）鏈表為定長雙向循環(huán)鏈表第一百一十二頁，共185頁。

為提高查找文件名的速度，還根據每個ncache的hash值，將其掛接到一個hash鏈表中。ncache的hash值用下列公式計算：

hn=7&(*namep+*(namep-1+slen)+slen+(int)VP)namep：為指向名字字符串的指針slen：為名字長度VP：為父目錄節(jié)點指針計算出相應的hash值（0~7）。共建立8個hash鏈，每個hash鏈是一個以鏈表頭開始的雙向循環(huán)鏈表，每個ncache任何時候都同時既在hash鏈上，又在LRU鏈上。第一百一十三頁，共185頁。ncachencachencachencachencachencachencachencachencacheLRU鏈表頭Hash鏈表頭hn=0hn=1hn=7名字緩沖區(qū)(ncache)池結構第一百一十四頁，共185頁。9、資源保護

UNIX文件系統(tǒng)中的資源保護系統(tǒng)主要是對系統(tǒng)中的兩類資源進行保護：①靜態(tài)硬資源

包括存貯空間和索引節(jié)點，對這類資源的保護主要是通過quota系統(tǒng)提供的限量機制實現(xiàn)的。②動態(tài)資源

主要是指臨界區(qū)資源或獨享資源，對這類資源的保護主要是通過上鎖機制來實現(xiàn)的。第一百一十五頁，共185頁。1）quota系統(tǒng)quota系統(tǒng)的主要功能就是檢測和限制用戶對文件系統(tǒng)資源的使用。在每個邏輯文件系統(tǒng)（包括根文件系統(tǒng)和各子文件系統(tǒng)）中都可以建立一個磁盤quota文件來限制用戶對本文件系統(tǒng)資源的使用。每個quota文件是由多個dqblk數據結構所組成的表格，每個dqblk都針對一個用戶，用于存放該文件系統(tǒng)對該用戶的限制參數。如果一個用戶的使用空間包含多個文件系統(tǒng)，則需在每個文件系統(tǒng)的硬盤quota文件中給該用戶分配一個dqblk項。第一百一十六頁，共185頁。structdqblk{盤塊數硬限制盤塊數軟限制已用盤塊數節(jié)點數硬限制節(jié)點數軟限制已用節(jié)點數盤塊數時間限制節(jié)點數時間限制}系統(tǒng)在運行時，在內存中建立了一個活動dqblk鏈表（類似于活動i節(jié)點表），每個活動dqblk由其hash值而分別處在64鏈中的某個鏈表上，如果某個活動dqblk是空閑的，它同時又處在空閑活動dqblk鏈表中（與活動i節(jié)點表的結構完全一樣）。第一百一十七頁，共185頁。quota限量系統(tǒng)構成quota資源限量系統(tǒng)對盤塊數限制對節(jié)點數限制軟限制(選擇限制)硬限制(絕對限制)軟限制(選擇限制)硬限制(絕對限制)無時間限制有時