1、UNIX_Linux操作系統(tǒng)內(nèi)核結(jié)構(gòu)電子科技大學(xué)信軟學(xué)院Saturday, July 23, 2022教 師 介 紹劉玓 教授大型主機(jī)教學(xué)團(tuán)隊(duì)主任大型主機(jī)與網(wǎng)絡(luò)安全工程系主任Email：主要研究方向：操作系統(tǒng)、大型主機(jī)、網(wǎng)絡(luò)應(yīng)用課 程 概 述一課程內(nèi)容簡介 1、講授范圍 具體的技術(shù)系統(tǒng)及其算法和實(shí)現(xiàn)流程，而不是操作系統(tǒng)基本原理； 2、通用操作系統(tǒng)的現(xiàn)狀和分類 DOS類 - 結(jié)構(gòu)簡單、使用方便、效率低、安全性低 UNIX類 - 運(yùn)行高效、結(jié)構(gòu)通用、安全可靠、適應(yīng)能力強(qiáng)、系統(tǒng)較復(fù)雜 MVS類 - 功能強(qiáng)大、處理能力巨大、系統(tǒng)復(fù)雜、較封閉大巨型機(jī) + z/OS小中型機(jī) + UNIX微型機(jī) + Win

2、dows功能強(qiáng)大簡單易用 3、根本特點(diǎn) 分時(shí)多用戶、開放性 分時(shí)多用戶： 多個(gè)用戶多個(gè)進(jìn)程同時(shí)在一個(gè)系統(tǒng)中運(yùn)行 系統(tǒng)資源高度共享、有效協(xié)調(diào) 開放性： 標(biāo)準(zhǔn)化 結(jié)構(gòu)上的一致性 可移植性 應(yīng)用軟件的編碼及系統(tǒng)應(yīng)用接口 可互操作性 可保持用戶原來的使用習(xí)慣 異種機(jī)之間的互操作 4、教學(xué)難點(diǎn) 多用戶多進(jìn)程同步/互斥、數(shù)據(jù)一致性、訪問安全性 開放性硬件依賴性、結(jié)構(gòu)伸縮性、廣泛適應(yīng)性 二、教學(xué)目的 1、了解主流操作系統(tǒng)的發(fā)展方向 低端操作系統(tǒng) VS 高端操作系統(tǒng) 2、掌握UNIX類操作系統(tǒng)的內(nèi)部結(jié)構(gòu)和主要算法 文件、文件系統(tǒng)、進(jìn)程、時(shí)鐘、輸入輸出 3、學(xué)習(xí)大型程序設(shè)計(jì)的方法和理念 系統(tǒng)結(jié)構(gòu)、功能流程、數(shù)據(jù)

3、安全、思維模式 4、奠定系統(tǒng)開發(fā)和應(yīng)用開發(fā)的基礎(chǔ) 功能選擇、層次劃分、應(yīng)用系統(tǒng)模式的確定三、教材 UNIX操作系統(tǒng)設(shè)計(jì) （The Design of the UNIX Operating System） （美）Maurice J.Bach 著 陳葆玨 王旭 柳純錄 馮雪山 譯 機(jī)械工業(yè)出版社 2005年10月出版四、考核說明 本課程為“考查”，請以選“考試”的同學(xué)進(jìn)行更正。 成績構(gòu)成：平時(shí)成績 + 期末報(bào)告第一章 系統(tǒng)概貌1.1 發(fā)展?fàn)顩r1、發(fā)展歷史及版本 v.0 1970年 Ken Thompson 和 Dennis Ritchie PDP-7 匯編語言 UNICS v.1 1971年 PD

4、P-11 匯編語言 UNIX v.2 1972年 增加管道功能 v.5 1973年 Dennis Ritchie B language - C language 重寫UNIX 第一個(gè)高級語言O(shè)S v.6 1975年 對外發(fā)表UNIX 大學(xué)和科研單位應(yīng)用 v.7 1978年 第一個(gè)商業(yè)版本 我國開始深入研究應(yīng)用的最早版本 System III 1981年 完全轉(zhuǎn)向?yàn)樯鐣?huì)提供的商品軟件 System V 1983年 系統(tǒng)功能穩(wěn)定完善 公布號: 1.0、2.0、2.3、3.5、4.0、4.2、4.3 現(xiàn)在最后版本為 System V Release 4 (SVR4)2、主要分支和兼容版本BSD 加州

5、大學(xué)伯克利分校 XENIX/OpenServer Microsoft、SCO公司HP-UX HP公司AIX IBMSolaris SUN公司IRIX SGI公司Ultrix DEC公司Linux 開放源代碼3、基本功能特征 交互式分時(shí)多用戶人機(jī)間實(shí)時(shí)交互數(shù)據(jù)多個(gè)用戶可同時(shí)使用一臺(tái)機(jī)器每個(gè)用戶可同時(shí)執(zhí)行多個(gè)任務(wù)軟件復(fù)用每個(gè)程序模塊完成單一的功能程序模塊可按需任意組合較高的系統(tǒng)和應(yīng)用開發(fā)效率可移植性強(qiáng)數(shù)千行匯編碼, 數(shù)十萬行C語言代碼配置靈活, 適應(yīng)性強(qiáng)小內(nèi)核, 參數(shù)靈活可調(diào)核外應(yīng)用系統(tǒng), 任意裁減限制規(guī)則很少界面方便高效內(nèi)部: 系統(tǒng)調(diào)用豐富高效外部: shell命令靈活方便可編程應(yīng)用: GUI

6、清晰直觀功能強(qiáng)大安全機(jī)制完善口令、權(quán)限、加密等措施完善抗病毒結(jié)構(gòu)誤操作的局限和自動(dòng)恢復(fù)功能 多國語言支持支持全世界現(xiàn)有的幾十種主要語言網(wǎng)絡(luò)和資源共享內(nèi)部: 多進(jìn)程結(jié)構(gòu)易于資源共享外部: 支持多種網(wǎng)絡(luò)協(xié)議說明：1、其它操作系統(tǒng)可能包含部分上述UNIX的特征，但非全部（如NT就有部分多用戶系統(tǒng)特征）2、這些特征有些是核心直接實(shí)現(xiàn)的，有些是由核心提供實(shí)現(xiàn)這種特征的方便性和可能性，而由使用者來實(shí)現(xiàn)的。1.2 系統(tǒng)結(jié)構(gòu) 硬件內(nèi)核kernelshwhodatewcvigrepdatea.outlsapp_1app_2app_nUNIX操作系統(tǒng)的整體結(jié)構(gòu) 系統(tǒng)調(diào)用（system call） 以函數(shù)形式提供給

7、核外的命令和上層應(yīng)用系統(tǒng)使用的一組程序，涵蓋操作系統(tǒng)的所有功能。是應(yīng)用程序請求操作系統(tǒng)服務(wù)的唯一通道。內(nèi)核（kernel） 系統(tǒng)調(diào)用的集合及實(shí)現(xiàn)系統(tǒng)調(diào)用的內(nèi)部算法就形成操作系統(tǒng)核心1.3 用戶看法 進(jìn)程和文件是UNIX操作系統(tǒng)中最基本的兩個(gè)概念（抽象）進(jìn)程： 所有處在運(yùn)行期間的程序?qū)嵗际沁M(jìn)程 一個(gè)進(jìn)程就是處在運(yùn)行期間的一個(gè)程序?qū)嵗?涵蓋所有的動(dòng)態(tài)概念文件： 所有靜態(tài)的無形數(shù)據(jù)和有形硬件設(shè)備 源程序、命令、圖片、郵件、 打印機(jī)、內(nèi)存、磁盤等1.3.1 文件系統(tǒng) / bin usr etc home tmp dev who ls bin lib rc ttys st teach tty0 hd0

8、2 admin hwconf liu wang chen aa dir2 save UNIX文件系統(tǒng)樹示例UNIX文件系統(tǒng)的特征：1、樹狀層次結(jié)構(gòu) 樹根、樹枝、樹葉、路徑2、對文件數(shù)據(jù)的一致對待 文件為有序無格式的字節(jié)流，邏輯意義由使用者解釋3、文件管理 建立、刪除、修改、備份、移動(dòng)、替換 存儲(chǔ)空間的分配和釋放4、文件的訪問和保護(hù) 索引節(jié)點(diǎn)（inode）、文件描述符(fd) 用戶分組、權(quán)限劃分5、設(shè)備文件管理 統(tǒng)一各外部設(shè)備的訪問模式char buffer2048;main(int argc, char *argv)int fdold, fdnew;if(argc != 3)printf(“n

9、eed 2 arguments for copy programn”);exit(1);fdold = open(argv1, O_RDONLY);if (fdold = -1)printf(“cannot open file %sn”, argv1);exit(1);fdnew = creat(argv2, 0666);if(fdnew = -1)printf(“cannot create file %sn”, argv2);exit(1);copy(fdold, fdnew);exit(0);copy(int old, int new)int count;while(count = rea

10、d(old, buffer, sizeof(buffer) 0)write(new, buffer, count);1.3.2 處理環(huán)境 程序：可執(zhí)行的文件 文件頭包括： 文件的幻數(shù)（magic number） 編譯器的版本號 機(jī)器類型 數(shù)據(jù)段、正文段、工作變量的段大小 程序入口點(diǎn)文件頭正文段數(shù)據(jù)段工作變量段BSS（符號表、重定位信息等）進(jìn)程： 程序的一次執(zhí)行實(shí)例 一個(gè)程序可同時(shí)有多個(gè)實(shí)例；系統(tǒng)中可同時(shí)有多個(gè)進(jìn)程父進(jìn)程： 調(diào)用系統(tǒng)調(diào)用fork的進(jìn)程子進(jìn)程： 由系統(tǒng)調(diào)用fork產(chǎn)生的新進(jìn)程執(zhí)行程序： 調(diào)用execl, 用被執(zhí)行程序的內(nèi)容覆蓋本進(jìn)程地址空間 abc執(zhí)行abcxyz用xyz覆蓋abc

11、執(zhí)行xyzxyz例子： 執(zhí)行可運(yùn)行文件copy，其功能是拷貝文件，其運(yùn)行格式為： copy oldfile newfile另一個(gè)名為cpfile的程序具體調(diào)用copy，其源程序如下：main(int argc, char *argv )if (fork() = 0)execl(“copy”, argv1, argv2, 0);wait(int *)0);printf(“copy donen”); 在用戶環(huán)境下，程序的執(zhí)行通常由命令解釋器shell來完成，標(biāo)準(zhǔn)的命令格式為： cmd -options arguments shell可識別的命令類型有： 1、簡單命令 cat file1 2、多條命

12、令 who; date; ps 3、復(fù)合命令 ps e | grep student2 (ls ; cat file3 ; pwd) run_log 4、后臺(tái)命令 ls lR /home/teacher tlist &1.3.3 構(gòu)件原語 “軟件復(fù)用”和“模塊組裝”理念 程序內(nèi)部： 簡單功能劃分；純代碼設(shè)計(jì) 程序外部： 使用構(gòu)件原語進(jìn)行功能重疊和組裝 UNIX包含兩種構(gòu)件原語： 輸入輸出重定向 管道I/O重定向（I/O redirect）： 一個(gè)進(jìn)程通常(default)打開三個(gè)文件： 標(biāo)準(zhǔn)輸入文件（fd=0） 標(biāo)準(zhǔn)輸出文件（fd=1） 標(biāo)準(zhǔn)錯(cuò)誤輸出文件（fd=2）例如： grep abc g

13、rep abc file1 grep abc file2 grep abc file2 2 file3管道（pipe）： A進(jìn)程將標(biāo)準(zhǔn)輸出重新定向到管道中去； B進(jìn)程將標(biāo)準(zhǔn)輸入重新定向從管道中來。例如： ps -e | grep student3 | wc -l 查看當(dāng)前系統(tǒng)中與用戶student3相關(guān)的進(jìn)程有多少 A進(jìn)程的輸出B進(jìn)程的輸入1.4 操作系統(tǒng)服務(wù) UNIX操作系統(tǒng)提供五種主要的服務(wù)（也是UNIX核心的五個(gè)重要組成部分）： 1進(jìn)程管理 建立、終止、掛起、通信等 2時(shí)鐘管理 分時(shí)共享cpu，時(shí)間片，調(diào)度 3存儲(chǔ)管理 二級存貯器（內(nèi)存和對換區(qū)），分配主存 4文件系統(tǒng)管理 二級存貯結(jié)構(gòu)。

14、分配和收回存貯區(qū)和索引節(jié)點(diǎn) 5設(shè)備管理 對I/O設(shè)備進(jìn)行有控制的存?。ǘ噙M(jìn)程系統(tǒng)的特征）內(nèi)核提供的服務(wù)的特點(diǎn)：服務(wù)是透明的 文件類型透明： 用戶可不關(guān)心是普通文件還是外部設(shè)備，但O.S自己要關(guān)心文件類型！ 文件系統(tǒng)的透明： 文件系統(tǒng)類型、存放的物理位置。 存貯方式透明： 文件的存放位置、存放方式、存放格式 各用戶進(jìn)程能得到核心相同服務(wù)： 無論系統(tǒng)程序還是用戶程序，平等對待，分時(shí)運(yùn)行1.5 硬件假設(shè) （假設(shè)機(jī)器硬件只支持的運(yùn)行狀態(tài)） UNIX系統(tǒng)上進(jìn)程的執(zhí)行分成兩種狀態(tài)： 用戶態(tài)、 核心態(tài) 用戶態(tài)： 進(jìn)程正在執(zhí)行用戶代碼時(shí)的狀態(tài) 核心態(tài)： 進(jìn)程正在執(zhí)行系統(tǒng)代碼（系統(tǒng)調(diào)用）時(shí)的狀態(tài)用戶態(tài)和核心態(tài)的

15、區(qū)別： 用戶態(tài)：進(jìn)程只能存取自己的地址空間 核心態(tài)：進(jìn)程可存取核心和用戶地址空間 用戶態(tài)：不能存取特權(quán)指令，只能存取自己的指令和數(shù)據(jù) 核心態(tài)：除了能存取自己的指令和數(shù)據(jù)外，還可存取特權(quán)指令 一個(gè)進(jìn)程在運(yùn)行時(shí)必須處在，而且只能處在或者核心態(tài)或者用戶態(tài)下：核心態(tài)的進(jìn)程不是與用戶進(jìn)程平行運(yùn)行的孤立的進(jìn)程集合，而是每個(gè)用戶進(jìn)程的一部分?！昂诵姆峙滟Y源”: 一個(gè)在核心狀態(tài)下執(zhí)行的進(jìn)程分配資源。一個(gè)進(jìn)程某時(shí)在“用戶態(tài)”下運(yùn)行，另一時(shí)刻又在“核心態(tài)”下運(yùn)行，在其生命周期內(nèi)可能在這兩種狀態(tài)間切換多次 用戶態(tài)核心態(tài)0 1 2 3 4 5 timeA | B | C | D | A | 核心處在核心態(tài)下的進(jìn)程的相

16、應(yīng)部分的集合硬件是按核心態(tài)和用戶態(tài)來執(zhí)行操作的，但對這兩種狀態(tài)下正在執(zhí)行程序的多個(gè)用戶是相同對待的。 readwriteopen A 進(jìn)程 B 進(jìn)程 C 進(jìn)程1.5.1 中斷與例外中斷（要保存上下文）： 來自進(jìn)程之外的事件（外設(shè)、時(shí)鐘等）引起的，發(fā)生在兩條指令執(zhí)行之間，中斷服務(wù)完畢后從下一條指令繼續(xù)執(zhí)行。(中斷服務(wù)是由核心中特殊的函數(shù)，而不是特殊的進(jìn)程來執(zhí)行的)例外（不保存上下文）： 來自進(jìn)程內(nèi)部的非期望事件（地址越界，除數(shù)為0等），發(fā)生在一條指令執(zhí)行過程中，例外事件處理完后重新執(zhí)行該指令。1.5.2 處理機(jī)執(zhí)行級 用一組特權(quán)指令給處理機(jī)設(shè)置一個(gè)執(zhí)行級，以屏蔽同級和低級的中斷，最大限度地減少其

17、它事件的干擾，使當(dāng)前任務(wù)順利執(zhí)行并盡快完成；但開放更高級的中斷，以響應(yīng)更緊迫的請求。中斷事件中斷級別硬件故障高低時(shí)鐘硬盤網(wǎng)絡(luò)終端軟件中斷1.5.3 存儲(chǔ)管理 UNIX系統(tǒng)中的存儲(chǔ)管理原則(或特點(diǎn))： 1當(dāng)前正在執(zhí)行的進(jìn)程（全部或部分）駐留在主存中； 2核心是永遠(yuǎn)駐留在主存中的（是永遠(yuǎn)活動(dòng)的?。?； 3編譯程序產(chǎn)生的指令地址是虛地址（邏輯地址）； 4程序運(yùn)行時(shí)核心與硬件（存儲(chǔ)管理部件MMU）一起建立虛地址到物理地址的映射。 核心永遠(yuǎn)是活躍的 普通進(jìn)程具有特定的生命周期（除非人為設(shè)定為無限循環(huán)） readwriteopenclose.核心代碼段A進(jìn)程B進(jìn)程openreadreadwrite映射映射只

18、是用戶進(jìn)程中的核心態(tài)下運(yùn)行的代碼段常駐內(nèi)存，而非整個(gè)用戶進(jìn)程常駐內(nèi)存。這些代碼段是“可再入段”（或純代碼段、可共享代碼段），被各用戶進(jìn)程段共享，為提高運(yùn)行速度，避免頻煩訪問磁盤，故常駐內(nèi)存，這些代碼段的集合就是OS的內(nèi)核。 第二章 核心導(dǎo)言2.1 UNIX操作系統(tǒng)的體系結(jié)構(gòu) “文件”和“進(jìn)程”是UNIX系統(tǒng)的兩個(gè)最基本實(shí)體和中心概念，UNIX系統(tǒng)的所有操作都是以這兩者為基礎(chǔ)的。整個(gè)系統(tǒng)核心由以下五個(gè)部分組成： 文件系統(tǒng)： 文件管理和存儲(chǔ)空間管理（節(jié)點(diǎn)和空間管理） I/O設(shè)備管理： 核心緩沖塊設(shè)備（隨機(jī)存取設(shè)備） 核心原始設(shè)備（raw設(shè)備，字符設(shè)備，裸設(shè)備） 進(jìn)程控制： 進(jìn)程的調(diào)度、同步和通訊

19、存貯管理： 在主存與二級存儲(chǔ)之間對程序進(jìn)行搬遷 時(shí)鐘管理： 把cpu的時(shí)間分配給當(dāng)前最高優(yōu)先權(quán)的進(jìn)程。 硬 件硬 件 控 制字符設(shè)備 塊設(shè)備設(shè)備驅(qū)動(dòng)程序高速緩沖文件子系統(tǒng)系 統(tǒng) 調(diào) 用 界 面程 序 庫進(jìn)程控制子系統(tǒng)進(jìn)程間通訊調(diào)度程序存儲(chǔ)管理用戶程序用戶級核心級核心級硬件級陷入2.2 系統(tǒng)概念2.2.1 文件系統(tǒng)概貌 1索引節(jié)點(diǎn)（index nodeinode） inode特征：文件的內(nèi)部名稱（或代號），方便機(jī)器操作；每個(gè)文件都有一個(gè)且只有一個(gè)inode與之對應(yīng)；inode存放文件的靜態(tài)參數(shù)：存放地點(diǎn)、所有者、文件類型、存取權(quán)限、文件大小等；每個(gè)文件都可以有多個(gè)名字，但都映射到同一個(gè)inode

20、上；各inode之間以inode號相區(qū)別；2鏈結(jié)（link） 對應(yīng)命令名 ln文件i節(jié)點(diǎn)abcxyz文件名 一個(gè)文件可有多個(gè)名字，多個(gè)名字都對應(yīng)同一個(gè)文件i節(jié)點(diǎn)，每個(gè)名字就是該文件節(jié)點(diǎn)的一個(gè)鏈結(jié)；. 一個(gè)普通文件的名字個(gè)數(shù)，就是該文件的鏈結(jié)數(shù)； 每個(gè)鏈接名可以放在不同的目錄下（同一個(gè)文件系統(tǒng)下）； 刪除一個(gè)鏈接名時(shí)，文件鏈接數(shù)減一。如鏈接數(shù)不為零，則文件（節(jié)點(diǎn)）仍然存在。使用文件鏈結(jié)的目的：方便用戶的使用習(xí)慣，如“列目錄”，可用ls、dir、list、lc等；誤刪文件時(shí)可補(bǔ)救，又不多占空間。abc和xyz具有相同的i結(jié)點(diǎn)號；減少移植應(yīng)用程序時(shí)，因使用指定位置的文件，而拷貝該文件到指定位置去的麻

21、煩。3符號鏈結(jié)（symbol link） 對應(yīng)命令名 ln -s 文件i節(jié)點(diǎn)abcxyz文件名 給文件的名字再取一個(gè)名字，而不是給文件節(jié)點(diǎn)再取一個(gè)名字。 鏈接的是“符號”而不是文件，因此“符號”可以是不存在的文件，即無意義的字符串。 abc和xyz具有不同的inode號，xyz的內(nèi)容是它所指向的名字的字符串，大小是字符串長度為3字節(jié)。 “普通鏈結(jié)”中各名字必須在同一文件系統(tǒng)中，“符號鏈結(jié)” 可在不同的文件系統(tǒng)中。4活動(dòng)i節(jié)點(diǎn)表（索引節(jié)點(diǎn)表） inode表 在內(nèi)存中存放當(dāng)前要使用的文件inode的表（或稱為活動(dòng)i節(jié)點(diǎn)表），表中的每一個(gè)表項(xiàng)對應(yīng)一個(gè)當(dāng)前正被使用的文件的狀態(tài)信息。這樣要使用（打開）同

22、一個(gè)文件的進(jìn)程不必再到盤上去尋找了，（共享?。?5用戶打開文件表（或稱用戶文件描述符表） 在系統(tǒng)中每一個(gè)進(jìn)程都有一個(gè)描述該進(jìn)程的數(shù)據(jù)結(jié)構(gòu)user（類似于描述文件的i節(jié)點(diǎn)），在user中有一個(gè)數(shù)組，存放一組指針指向系統(tǒng)打開文件表中該進(jìn)程打開的文件所對應(yīng)的表項(xiàng)。 struct file *u_ofileNOFILE NOFILE 為每個(gè)進(jìn)程最多可同時(shí)打開的文件數(shù)，這與系統(tǒng)中的進(jìn)程數(shù)和內(nèi)存大小以及交換區(qū)大小等有關(guān)系，一般為20100。 這個(gè)u_ofile數(shù)組就是該進(jìn)程的用戶打開文件表。6系統(tǒng)打開文件表（file表） 系統(tǒng)打開文件表主要存放被打開文件的讀寫指針。 因?yàn)橐粋€(gè)進(jìn)程在一個(gè)時(shí)間片內(nèi)可能讀寫不完

23、所需內(nèi)容，需要在下一個(gè)時(shí)間片繼續(xù)從上一個(gè)時(shí)間片結(jié)束時(shí)的讀寫位置開始讀寫，故在進(jìn)程生存期間應(yīng)保持一讀寫指針。 此外file表中還存放被打開文件的動(dòng)態(tài)信息：如文件狀態(tài)、引用計(jì)數(shù)（當(dāng)前使用該文件的進(jìn)程數(shù)）等。A進(jìn)程B進(jìn)程file表活動(dòng)inode表用戶打開文件表系統(tǒng)打開文件表活動(dòng)i節(jié)點(diǎn)表為什么要單獨(dú)設(shè)立一個(gè)file表來存放讀寫指針呢？ 由于可能有多個(gè)進(jìn)程要共享一個(gè)被打開文件的inode，而每個(gè)進(jìn)程的讀寫指針都不相同，故不能放在inode表中。 另一方面，要使不同進(jìn)程的打開文件指針（文件描述符）或同一進(jìn)程的不同打開文件指針能夠共享一個(gè)打開文件指針（協(xié)同操作），就不能把讀寫指針放進(jìn)某一個(gè)進(jìn)程的用戶打開文件

24、表中。 因此只能在用戶打開文件表和活動(dòng)inode表之外再建立一個(gè)系統(tǒng)打開文件表（file表）來存放讀寫指針。 UNIX操作系統(tǒng)中共享活動(dòng)文件的方法： 在內(nèi)存中某個(gè)活動(dòng)文件的副本只有一個(gè)，不同的進(jìn)程采用不同的指針指向這文件的副本。由于任一時(shí)刻只有一個(gè)進(jìn)程在運(yùn)行（微觀上看），故該文件也只要求內(nèi)存中有一個(gè)副本即可，只是各個(gè)進(jìn)程有自己的讀寫指針而已。這是在UNIX系統(tǒng)中共享文件（包括用戶文件和系統(tǒng)文件）的主要方法。對其它資源的共享采用的是與之相似的另外幾種方法。2.2.2 進(jìn)程相關(guān)概念：映像 程序以及與動(dòng)態(tài)執(zhí)行該程序有關(guān)的各種信息的集合(類似于歷史檔案)。它包括存儲(chǔ)器映象、通用寄存器映像，地址映射空間

25、、打開文件狀態(tài)等。進(jìn)程 對映像的執(zhí)行。對映像的執(zhí)行也就是一個(gè)程序在虛擬機(jī)上動(dòng)態(tài)執(zhí)行的過程?？蓤?zhí)行文件的構(gòu)成： 進(jìn)程是可執(zhí)行文件的一次執(zhí)行實(shí)例，高級語言程序經(jīng)過編譯或匯編語言程序經(jīng)過匯編后所產(chǎn)生的、缺省名為a.out的可執(zhí)行文件的結(jié)構(gòu)包括圖示四個(gè)部分： 文件頭正文段數(shù)據(jù)標(biāo)識段其它信息段文件頭 文件的幻數(shù)（magic number） 編譯器的版本號 機(jī)器類型 正文段、數(shù)據(jù)標(biāo)識段、其它信息段的大小 程序入口點(diǎn)正文段 程序的功能代碼數(shù)據(jù)標(biāo)識段 標(biāo)識未初始化的數(shù)據(jù)要占用的空間大小其它信息段 主要用于存放符號表程序的執(zhí)行 一個(gè)進(jìn)程在執(zhí)行系統(tǒng)調(diào)用exec時(shí)，把可執(zhí)行文件裝入本進(jìn)程的三個(gè)區(qū)域中： 正文區(qū)：對應(yīng)

26、可執(zhí)行文件的正文段 數(shù)據(jù)區(qū)：對應(yīng)可執(zhí)行文件的數(shù)據(jù)標(biāo)識段 堆棧區(qū)：新建立的進(jìn)程工作區(qū) 堆棧主要用于傳遞參數(shù)，保護(hù)現(xiàn)場，存放返回地址以及為局部動(dòng)態(tài)變量提供存儲(chǔ)區(qū)。 進(jìn)程在核心態(tài)下運(yùn)行時(shí)的工作區(qū)為核心棧，在用戶態(tài)下運(yùn)行時(shí)的工作區(qū)為用戶棧。核心棧和用戶棧不能交叉使用。 堆棧使用舉例。有如下程序，在主程序中調(diào)用函數(shù)，并進(jìn)行參數(shù)傳遞：main (int argc, char *argv ) char buf1024; int number; readfile (buf, number); readfile (char buffer , int line) char *pointer; int temp;

27、空棧棧頂指針棧底指針低地址高地址用戶棧進(jìn)入主程序時(shí)的堆棧狀況棧頂指針棧底指針低地址高地址調(diào)用main()時(shí)argc, argv本程序返回地址棧底指針暫存處buf, number棧頂指針棧底指針低地址高地址調(diào)用readfile時(shí)argc, argv本程序返回地址棧底指針暫存處buf, numberbuffer, linereadfile的返回地址棧底指針暫存處pointer, temp3. 進(jìn)程的標(biāo)識 進(jìn)程由其進(jìn)程標(biāo)識號PID來識別。0#進(jìn)程 是由機(jī)器上電時(shí)“手工”創(chuàng)建的，調(diào)用fork創(chuàng)建了1#進(jìn)程后，成為對換進(jìn)程（swap）。1#進(jìn)程 init進(jìn)程，由它來創(chuàng)建系統(tǒng)初始化過程中所需的其它所有的進(jìn)

28、程。父進(jìn)程 調(diào)用fork系統(tǒng)調(diào)用的進(jìn)程子進(jìn)程 由系統(tǒng)調(diào)用fork產(chǎn)生的進(jìn)程除0#進(jìn)程外，其它所有進(jìn)程都是另一個(gè)進(jìn)程調(diào)用fork后產(chǎn)生的。進(jìn)程狀態(tài)及狀態(tài)轉(zhuǎn)換運(yùn)行狀態(tài) 此時(shí)進(jìn)程正在占用處理機(jī)，進(jìn)程的全部映像駐在內(nèi)存中。就緒狀態(tài) 此時(shí)進(jìn)程基本具備了運(yùn)行條件，正在等待使用處理機(jī)。睡眠狀態(tài) 進(jìn)程不具備運(yùn)行條件，需等待某種事件的發(fā)生，無法繼續(xù)執(zhí)行下去。 運(yùn)行睡眠就緒調(diào)度調(diào)度睡眠喚醒中斷5. 在UNIX環(huán)境下，進(jìn)程有如下特征： 每個(gè)進(jìn)程在核心進(jìn)程表（proc數(shù)組）都占有一項(xiàng)，在其中保留相應(yīng)的狀態(tài)信息。 每個(gè)進(jìn)程都有一個(gè)“每進(jìn)程數(shù)據(jù)區(qū)（per process data area-ppda）”保留相應(yīng)進(jìn)程更多的

29、信息和核心棧； 處理機(jī)的全部工作就是在某個(gè)時(shí)候執(zhí)行某個(gè)進(jìn)程 一個(gè)進(jìn)程可生成或消滅另一進(jìn)程 一個(gè)進(jìn)程中可申請并占有資源 一個(gè)進(jìn)程只沿著一個(gè)特定的指令序列運(yùn)行，不會(huì)跳轉(zhuǎn)到另一個(gè)進(jìn)程的指令序列中去，也不能訪問別的進(jìn)程的數(shù)據(jù)和堆棧。（抗病毒傳播的重要原因之一）第三章 數(shù)據(jù)緩沖區(qū)高速緩沖硬件緩存（cache） 由一種高速寄存器（register）組成，主要解決CPU與RAM之間的速度差問題。數(shù)據(jù)緩沖區(qū)高速緩沖（buffer） 由軟件實(shí)現(xiàn)的解決文件系統(tǒng)和物理硬盤之間的數(shù)據(jù)同步的一種方法。 數(shù)據(jù)緩沖區(qū)高速緩沖是UNIX特有的對數(shù)據(jù)并發(fā)訪問的一種控制機(jī)制。問題的提出： 1、磁盤機(jī)械運(yùn)行速度大大低于處理機(jī)的運(yùn)行

30、速度； 2、多進(jìn)程并發(fā)運(yùn)行，少量的磁盤（通道）I/O成為瓶頸； 3、數(shù)據(jù)訪問的隨機(jī)性，磁盤忙閑不均解決辦法：1、建立一個(gè)被稱為數(shù)據(jù)緩沖區(qū)高速緩沖（簡稱高速緩沖）的內(nèi)部數(shù)據(jù)緩沖區(qū)池（buffer pool）來存放要用的數(shù)據(jù)；2、寫數(shù)據(jù)時(shí) 把數(shù)據(jù)盡量多地盡量長時(shí)間地保存在緩沖池中 延遲寫出到磁盤上 以備后續(xù)進(jìn)程使用3、讀數(shù)據(jù)時(shí) 先在緩沖池中查找已有的數(shù)據(jù) 如沒有，再從磁盤讀取，并保存在緩沖池中 事先預(yù)讀數(shù)據(jù)到緩沖池中3.1 緩沖區(qū)及緩沖區(qū)首部 緩沖區(qū)池由若干個(gè)緩沖區(qū)組成，每一個(gè)緩沖區(qū)又由兩部分組成：一個(gè)實(shí)際存放數(shù)據(jù)的存儲(chǔ)區(qū)和一個(gè)標(biāo)識該緩沖區(qū)的緩沖區(qū)首部。存 儲(chǔ) 區(qū) 因?yàn)榫彌_區(qū)首部與數(shù)據(jù)存儲(chǔ)區(qū)之間有

31、一一對應(yīng)的關(guān)系，所以通常把兩者統(tǒng)稱為緩沖區(qū)。 緩沖區(qū)是緩沖區(qū)池中數(shù)據(jù)存儲(chǔ)的基本單位。緩沖區(qū)首部緩沖區(qū)首部的定義:struct buf 緩沖區(qū)標(biāo)志 標(biāo)識緩沖區(qū)狀態(tài) 緩沖區(qū)鏈接指針 向前向后串成鏈表 空閑緩沖區(qū)鏈表指針 聯(lián)結(jié)空閑緩沖區(qū) 設(shè)備號 標(biāo)識緩沖區(qū) 塊號 union 緩沖區(qū)中的數(shù)據(jù)類型 數(shù)據(jù)塊 超級塊 柱面塊 i節(jié)點(diǎn)塊 b_un 其它控制信息3.2 緩沖池的結(jié)構(gòu)1、最近最少使用（LRU）算法：Least Recently Used 程序設(shè)計(jì)采用模塊化和層次化結(jié)構(gòu)，盡量避免使用goto語句，程序跳轉(zhuǎn)少，適應(yīng)“流水線（pipeline）”體系結(jié)構(gòu)的系統(tǒng)； 特定時(shí)間段內(nèi)，程序在一個(gè)相對集中空間（代

32、碼段）內(nèi)運(yùn)行，涉及的數(shù)據(jù)（廣義的：文件名、變量、指針和數(shù)組等）的個(gè)數(shù)相對較少； 當(dāng)前使用過的數(shù)據(jù)，馬上還要使用的可能性最大，較長時(shí)間未用過的數(shù)據(jù)，即將使用的可能性最小。2、緩沖池設(shè)計(jì)基本原則： 存放有剛使用過的數(shù)據(jù)盡量長時(shí)間地保留在內(nèi)存中，以便馬上還要使用時(shí)能在內(nèi)存中找到； 需要騰出內(nèi)存空間時(shí)，把很久都未使用過（即最近最少使用）的數(shù)據(jù)交換到磁盤上去。這些數(shù)據(jù)馬上還要使用的可能性最小。3、空閑緩沖區(qū)鏈表 核心維護(hù)了一個(gè)空閑緩沖區(qū)鏈表，它按照最近被使用的先后次序排列。空閑鏈表是一個(gè)以空閑緩沖區(qū)鏈表頭開始的“雙向循環(huán)鏈表”。鏈表的開始和結(jié)束都以鏈表頭為標(biāo)志。 鏈表頭空閑緩沖區(qū)1空閑緩沖區(qū)2空閑緩沖區(qū)

33、3空閑緩沖區(qū)n4、空閑緩沖區(qū)鏈表操作 取用任意空閑緩沖區(qū) 從空閑緩沖區(qū)鏈表的表頭位置取下一個(gè)空閑緩沖區(qū)，后面的空閑緩沖區(qū)依次向前移動(dòng)。 釋放一個(gè)空閑緩沖區(qū) 把這個(gè)裝有數(shù)據(jù)的空閑緩沖區(qū)附加到空閑鏈表的鏈尾。只有當(dāng)該空閑緩沖區(qū)所裝數(shù)據(jù)出錯(cuò)時(shí)才掛到鏈頭。 取用裝有指定內(nèi)容的空閑緩沖區(qū) 從鏈表頭開始查找，找到后取下使用，用完后放到鏈尾。 當(dāng)系統(tǒng)不斷從鏈頭取用空閑緩沖區(qū)，又把使用過的（裝有數(shù)據(jù)的）緩沖區(qū)掛到鏈尾，一個(gè)裝有有效數(shù)據(jù)的緩沖區(qū)就會(huì)逐漸向鏈表頭移動(dòng)。在鏈表頭位置的就是“最近最少使用”的空閑緩沖區(qū)。5、空閑緩沖區(qū)分類 系統(tǒng)中共設(shè)置了四個(gè)空閑緩沖區(qū)鏈表，根據(jù)緩沖區(qū)的不同用途而把它的放入不同的空閑緩沖

34、區(qū)鏈表中。避免在取用空閑緩沖區(qū)時(shí)，逐個(gè)判斷緩沖區(qū)中的內(nèi)容。這四個(gè)空閑鏈表是：0#空閑緩沖區(qū)鏈表存放文件系統(tǒng)超級塊1#空閑緩沖區(qū)鏈表存放通常使用的數(shù)據(jù)塊2#空閑緩沖區(qū)鏈表存放延遲寫、無效數(shù)據(jù)或錯(cuò)誤內(nèi)容3#空閑緩沖區(qū)鏈表存放沒有對應(yīng)存儲(chǔ)空間的緩沖區(qū)首部如果某種類型的空閑緩沖區(qū)不夠用時(shí)，核心也從其它空閑緩沖區(qū)鏈表中取用空閑緩沖區(qū)。6、緩沖區(qū)設(shè)置 當(dāng)核心需有一個(gè)空閑緩沖區(qū)時(shí)，它根據(jù)要裝入的數(shù)據(jù)類型，從相應(yīng)的空閑緩沖區(qū)鏈表的表頭位置取下一個(gè)空閑緩沖區(qū)，裝入一個(gè)磁盤數(shù)據(jù)塊； 根據(jù)該數(shù)據(jù)塊所對應(yīng)的設(shè)備號和塊號數(shù)據(jù)對計(jì)算其 hashno（散列、雜湊）值，根據(jù)其 hashno 的值放入到相應(yīng) hash 鏈表的鏈

35、頭。 hashno = (diskno + blkno) / RND) % BUFHSZ diskno： 設(shè)備號 blkno： 塊號 BUFHSZ： 最大hash值，通常為63。 RND： 隨機(jī)數(shù)，其值為：RND=MAXBSIZE / DEV_BSIZE MAXBSIZE： 最大文件系統(tǒng)塊的大小 DEV_BSIZE：物理設(shè)備塊大小 hashno 的取值范圍： 0 627、緩沖池的結(jié)構(gòu) 具有相同 hashno 的緩沖區(qū)鏈接在同一個(gè)hash鏈表中，因此系統(tǒng)中共有 63 個(gè)hash 鏈表，分別鏈接 hashno 為 0 62 的緩沖區(qū)。 每一個(gè) hash 鏈表都是一個(gè)由鏈表頭指向的雙向循環(huán)鏈表，查找

36、某一個(gè)指定 hashno 值的緩沖區(qū)時(shí)，也是從相應(yīng)的hash鏈表的表頭位置開始向表尾方向進(jìn)行查找。 這 63 個(gè) hash 鏈表就構(gòu)成了數(shù)據(jù)緩沖區(qū)高速緩沖的緩沖池，所有的緩沖區(qū)都存放在緩沖池中的某一個(gè)鏈表中。鏈表頭緩沖區(qū)1緩沖區(qū)2緩沖區(qū)3緩沖區(qū)nhash 鏈表的結(jié)構(gòu)緩沖區(qū)緩沖區(qū)緩沖區(qū)緩沖區(qū)緩沖區(qū)緩沖區(qū)緩沖區(qū)緩沖區(qū)緩沖區(qū)空閑鏈表頭Hash鏈表頭hashno=0hashno=1hashno=62緩沖池的結(jié)構(gòu)8、緩沖區(qū)的使用 如果要找特定緩沖區(qū)，根據(jù)hashno從相應(yīng)的hash鏈表的表頭處開始逐個(gè)向后查找； 如果找到，則直接取用，并將其移動(dòng)到hash鏈的鏈頭； 如果未找到，則從相應(yīng)的空閑緩沖區(qū)鏈表的

37、表頭處取下一個(gè)空閑緩沖區(qū)，填入相應(yīng)數(shù)據(jù)，重新計(jì)算其hashno，并放到新的hash鏈表的表頭； 釋放緩沖區(qū)時(shí)，將該緩沖區(qū)仍保留在原h(huán)ash隊(duì)列中，同時(shí)掛接到空閑緩沖區(qū)鏈表的表尾。（同時(shí)在兩個(gè)隊(duì)列中）申請緩沖區(qū)的兩個(gè)途徑： 要指定緩沖區(qū) 在hash鏈表中查找 要空閑緩沖區(qū) 在空閑鏈表中查找9、進(jìn)一步說明 一個(gè)緩沖區(qū)只有當(dāng)它是空閑狀態(tài)時(shí)，它才同時(shí)處在hash鏈表和空閑鏈表中。如果不空閑，則它只能處在某一個(gè)hash鏈表中。 在空閑緩沖區(qū)鏈表中的緩沖區(qū)一定在某個(gè)hash鏈表中；在hash鏈表中的緩沖區(qū)不一定在空閑鏈中。不存在脫離hash鏈表的另一個(gè)空閑的緩沖區(qū)鏈表。 緩沖池中的緩沖區(qū)個(gè)數(shù)是固定不變的，

38、每個(gè)緩沖區(qū)在不同時(shí)刻存放著不同的磁盤數(shù)據(jù)塊，具有不同的hash值，因此處在不同的hash鏈表中。 緩沖區(qū)中的數(shù)據(jù)與某個(gè)磁盤數(shù)據(jù)塊一一對應(yīng)，這種對應(yīng)有兩個(gè)特點(diǎn)： 一個(gè)磁盤數(shù)據(jù)塊在緩沖池中最多只能有一個(gè)副本； 緩沖區(qū)與數(shù)據(jù)塊的對應(yīng)是動(dòng)態(tài)的，LRU數(shù)據(jù)塊將被釋放。3.3 緩沖區(qū)的檢索算法 在UNIX文件系統(tǒng)中的下層，即直接與邏輯存儲(chǔ)設(shè)備聯(lián)系的部分，包含如下基本算法： getblk 申請一個(gè)緩沖區(qū) brelse 釋放一個(gè)緩沖區(qū) bread 讀一個(gè)磁盤塊 breada 讀一個(gè)磁盤塊，預(yù)讀另一個(gè)磁盤塊 bwrite 寫磁盤塊1、申請一個(gè)緩沖區(qū)算法 getblk 根據(jù)緩沖池的結(jié)構(gòu)，核心申請一個(gè)緩沖區(qū)分配個(gè)磁

39、盤塊時(shí)，可能出現(xiàn)的五種典型狀況： 該塊已在hash隊(duì)列中，并且緩沖區(qū)是空閑的； hash隊(duì)列中找不到該塊，需從空閑鏈表中分配一個(gè)緩沖區(qū)； hash隊(duì)列中找不到該塊，在從空閑鏈表中分配一個(gè)緩沖區(qū)時(shí)，發(fā)現(xiàn)該空閑緩沖區(qū)標(biāo)記有“延遲寫”，核心必須寫出緩沖區(qū)內(nèi)容到磁盤上，再重新分配一個(gè)空閑緩沖區(qū)； hash隊(duì)列中找不到該塊，并且空閑鏈表已空； 該塊已在hash隊(duì)列中，但該緩沖區(qū)目前狀態(tài)為“忙”。2、 釋放一個(gè)緩沖區(qū)算法 brelse 喚醒等待緩沖區(qū)的所有進(jìn)程 提高處理機(jī)的執(zhí)行級別以封鎖同級或低級的中斷 將該緩沖區(qū)放到空閑隊(duì)列的尾部（緩沖區(qū)有效）或頭部（緩沖區(qū)無效） 降低處理機(jī)的執(zhí)行級別以開放中斷3、讀一

40、個(gè)磁盤塊 bread 由 getblk 算法申請一個(gè)可用的緩沖區(qū) 如果緩沖區(qū)中的內(nèi)容有效，則直接返回該緩沖區(qū) 如果緩沖區(qū)中的內(nèi)容無效，則啟動(dòng)磁盤去讀所需的數(shù)據(jù)塊 等待磁盤操作完成后返回算法 bread輸入：文件系統(tǒng)號輸出：含有數(shù)據(jù)的緩沖區(qū)得到該塊的緩沖區(qū)（算法getblk）；if（緩沖區(qū)數(shù)據(jù)有效）return（緩沖區(qū)）；啟動(dòng)磁盤讀；sleep（等待“讀盤完成”事件）；return（緩沖區(qū)）；4、 讀一個(gè)磁盤塊并預(yù)讀另一個(gè)磁盤塊 breada 預(yù)讀的前提： 程序是在一個(gè)有限的空間內(nèi)運(yùn)行，程序?qū)?shù)據(jù)的訪問是可預(yù)見的。 預(yù)讀的命中率： 不一定達(dá)到100%，但良好的系統(tǒng)結(jié)構(gòu)和算法可使命中率達(dá)到較高的水

41、平。 預(yù)讀的結(jié)果： 放在緩沖池內(nèi)，以免需要的時(shí)候再去啟動(dòng)磁盤讀數(shù)據(jù)塊。算法 breada輸入：（1）立即讀的文件系統(tǒng)塊號 （2）異步讀的文件系統(tǒng)塊號輸出：含有立即讀的數(shù)據(jù)的緩沖區(qū)if（第一塊不在高速緩沖中）為第一塊獲得緩沖區(qū)（getblk）；if（緩沖區(qū)內(nèi)容無效）啟動(dòng)磁盤讀；if（第二塊不在高速緩沖中）為第二塊獲得緩沖區(qū)（getblk）；if（緩沖區(qū)數(shù)據(jù)有效）釋放緩沖區(qū)（brelse）；else啟動(dòng)磁盤讀；if（第一塊本來就在高速緩沖中）讀第一塊（bread）；return（緩沖區(qū)）；sleep（第一個(gè)緩沖區(qū)包含有效數(shù)據(jù)的事件）；return（緩沖區(qū)）；5、寫磁盤塊 bwrite 啟動(dòng)磁盤驅(qū)動(dòng)

42、程序的寫操作 如果是“同步寫”，則本進(jìn)程睡眠等待磁盤寫操作的完成，磁盤寫操作完成后，中斷喚醒本進(jìn)程，本進(jìn)程釋放該緩沖區(qū)并返回； 如果是“異步寫”，則無需等待磁盤寫操作的完成，將緩沖區(qū)放到空閑鏈表的表頭，以便隨后某個(gè)進(jìn)程申請空閑緩沖區(qū)時(shí)，將其寫到磁盤上去。本進(jìn)程不再關(guān)心該緩沖區(qū)實(shí)際被寫出的時(shí)間和結(jié)果，而直接返回去作其它事情。 事實(shí)上無論是同步寫還是異步寫，其根本區(qū)別在于本進(jìn)程是否等待磁盤驅(qū)動(dòng)程序完成操作后所發(fā)出的中斷信號。算法 bwrite輸入：緩沖區(qū)輸出：無啟動(dòng)磁盤讀；if（I/O同步）sleep（等待“I/O完成”事件）；釋放緩沖區(qū)（brelse）；else if （緩沖區(qū)標(biāo)記著延遲寫）為緩

43、沖區(qū)做標(biāo)記以放到空閑緩沖區(qū)鏈表頭部；3.3 數(shù)據(jù)緩沖區(qū)高速緩沖的優(yōu)缺點(diǎn)優(yōu)點(diǎn)： 提供了對磁盤塊的統(tǒng)一的存取方法 消除了用戶對用戶緩沖區(qū)中數(shù)據(jù)的特殊對齊需要 減少了磁盤訪問的次數(shù)，提高了系統(tǒng)的整體I/O效率 有助于保持文件系統(tǒng)的完整性缺點(diǎn)： 數(shù)據(jù)未及時(shí)寫盤而帶來的風(fēng)險(xiǎn) 額外的數(shù)據(jù)拷貝過程，大量數(shù)據(jù)傳輸時(shí)影響性能第四章 文件和文件系統(tǒng)的內(nèi)部結(jié)構(gòu)現(xiàn)代UNIX的文件系統(tǒng)通常可由三大模塊組成：本地文件系統(tǒng)（UFS）User File System網(wǎng)絡(luò)文件系統(tǒng)（NFS）Network File System虛擬文件系統(tǒng)（VFS）Virtual File System本地文件系統(tǒng)（UFS） 是UNIX系統(tǒng)中的

44、基本文件系統(tǒng)，它通常固定存放在本地機(jī)器的存貯設(shè)備上，任何一種結(jié)構(gòu)形式的文件系統(tǒng)都必然會(huì)直接或間接地與某個(gè)本地文件系統(tǒng)相聯(lián)系。本地文件系統(tǒng)的構(gòu)成 一個(gè)根文件系統(tǒng) + 若干子文件系統(tǒng)所組成根文件系統(tǒng) 存放本操作系統(tǒng)的最主要和最基本的部分 可獨(dú)立啟動(dòng)運(yùn)行 系統(tǒng)起動(dòng)后，根文件系統(tǒng)就不能卸下來子文件系統(tǒng) 主要存放應(yīng)用程序和用戶文件 一般不能獨(dú)立啟動(dòng) 系統(tǒng)運(yùn)行過程中可隨時(shí)安裝和卸下網(wǎng)絡(luò)文件系統(tǒng)（NFS） 是本地機(jī)器上的文件系統(tǒng)和遠(yuǎn)地機(jī)器上的文件系統(tǒng)之間的介質(zhì)，它管理和控制所有有關(guān)對遠(yuǎn)地文件的各種操作，給本地用戶提供一個(gè)訪問遠(yuǎn)地文件的使用方便的高層接口，避免用戶直接涉及網(wǎng)絡(luò)通訊方面的具體細(xì)節(jié)。虛擬文件系統(tǒng)（

45、VFS） VFS是整個(gè)操作系統(tǒng)的用戶界面，它給用戶提供一個(gè)統(tǒng)一的文件系統(tǒng)使用接口，避免用戶涉及各個(gè)子文件系統(tǒng)的特征部分。 用戶感覺使用的是一個(gè)整體的，比本地機(jī)器上實(shí)際硬盤空間大得多的文件系統(tǒng)。 虛構(gòu)文件系統(tǒng)接受來自用戶的操作請求，根據(jù)該操作所訪問的文件是存放在本地機(jī)器上，還是存放在遠(yuǎn)地機(jī)器上而分別把操作交給本地文件系統(tǒng)或網(wǎng)絡(luò)文件系統(tǒng)；本地文件系統(tǒng)或網(wǎng)絡(luò)文件系統(tǒng)（實(shí)際上再傳給遠(yuǎn)地機(jī)器上的本地文件系統(tǒng)）進(jìn)行相應(yīng)的操作后，將結(jié)果返回到虛擬文件系統(tǒng)中再傳回給用戶。網(wǎng) 絡(luò)虛擬文件系統(tǒng)VFS網(wǎng)絡(luò)文件系統(tǒng)NFS本地文件系統(tǒng)UFS物理存儲(chǔ)介質(zhì)虛擬文件系統(tǒng)VFS網(wǎng)絡(luò)文件系統(tǒng)NFS本地文件系統(tǒng)UFS物理存儲(chǔ)介質(zhì)用

46、戶用戶A機(jī)器B機(jī)器基于虛擬文件系統(tǒng)的體系結(jié)構(gòu)4.1 文件系統(tǒng)結(jié)構(gòu) 4.1.1 本地文件系統(tǒng)1文件的存貯結(jié)構(gòu) UNIX的普通文件的邏輯結(jié)構(gòu)是無格式的有序字節(jié)流，而它們的物理存貯結(jié)構(gòu)是以索引方式來組織的。 每個(gè)文件都是由一個(gè)索引節(jié)點(diǎn)i節(jié)點(diǎn)來表示的，每個(gè)i節(jié)點(diǎn)由其i節(jié)點(diǎn)號來標(biāo)識。 i節(jié)點(diǎn)通常以靜態(tài)的形式存放在磁盤的i節(jié)點(diǎn)表中。每個(gè)磁盤i節(jié)點(diǎn)表項(xiàng)是由數(shù)據(jù)結(jié)構(gòu)icommon定義的，描述對應(yīng)文件的靜態(tài)參數(shù)。 超級塊磁盤i節(jié)點(diǎn)表數(shù)據(jù)存儲(chǔ)區(qū)磁盤icommon表icommonicommonicommonicommonicommon文件所有者標(biāo)識（UID）用戶組標(biāo)識（GID）文件類型（FIFO、DIR、CHR、

47、BLK、REG、LNK等）文件保護(hù)模式（存取許可權(quán)）mode文件存取時(shí)間（atime, mtime, ctime）鏈接數(shù)目 link文件大小 size文件數(shù)據(jù)塊索引表 index table icommon 與 inode 的關(guān)系 進(jìn)程要讀寫一個(gè)文件時(shí)，先在內(nèi)存的活動(dòng)i節(jié)點(diǎn)表（即inode表）中申請一個(gè)空閑的活動(dòng)i節(jié)點(diǎn)，并把磁盤上i節(jié)點(diǎn)（icommon）中的各項(xiàng)參數(shù)讀入其中，當(dāng)核心操作完成后，如果必要，就把在內(nèi)存中的活動(dòng)i節(jié)點(diǎn)寫回到磁盤上去。 內(nèi)存活動(dòng)i節(jié)點(diǎn)由數(shù)據(jù)結(jié)構(gòu)inode來定義，它除了包含磁盤上對應(yīng)的icommon中的各項(xiàng)參數(shù)外，還包含有其它的參數(shù)，如該活動(dòng)i節(jié)點(diǎn)的狀態(tài)、文件所在的邏輯設(shè)

48、備號、i節(jié)點(diǎn)號、活動(dòng)i節(jié)點(diǎn)鏈接指針，最近使用的i節(jié)點(diǎn)在目錄中的位置等動(dòng)態(tài)信息。struct inode 活動(dòng)i節(jié)點(diǎn)鏈接指針 狀態(tài)標(biāo)志 設(shè)備號 i節(jié)點(diǎn)號 最近訪問的i節(jié)點(diǎn)在目錄中的位置 空閑i節(jié)點(diǎn)鏈接指針 struct incommon 文件模式和類型（FIFO、DIR、CHR、BLK、REG、LNK等） 文件鏈接數(shù) 文件所有者標(biāo)識數(shù)（UID） 文件所屬用戶組標(biāo)識數(shù)（GID） 文件大小 文件最近存取時(shí)間（atime, mtime, ctime） 數(shù)據(jù)塊索引表 其它信息 2、數(shù)據(jù)塊索引表 數(shù)據(jù)塊索引表用于檢索本文件占用的數(shù)據(jù)塊。它包含12項(xiàng)直接索引表目和3項(xiàng)間接索引表目。根據(jù)要讀寫的數(shù)據(jù)在文件中的

49、位置可計(jì)算出該數(shù)據(jù)所在的邏輯塊號，查索引表就可找到邏輯塊所在的文件系統(tǒng)塊號。 系統(tǒng)根據(jù)計(jì)算出來的邏輯塊號判斷是否包含在直接索引表中，如果是，則取出直接索引表中的文件系統(tǒng)塊號；如不是，則看是否包含在一次間接索引塊中，否則再尋找二次和三次間接索引塊。最長要存取三次間址索引塊才能找到相應(yīng)數(shù)據(jù)的文件系統(tǒng)塊號（要取出數(shù)據(jù)則要讀4次磁盤）。 直接 0直接 1直接 2直接 11一次間址二次間址三次間址數(shù)據(jù)塊索引表一級間址塊二級間址塊三級間址塊數(shù)據(jù)塊3、inode表的結(jié)構(gòu) 在內(nèi)存中，活動(dòng)i節(jié)點(diǎn)表類似于數(shù)據(jù)緩沖區(qū)高速緩沖中的緩沖池結(jié)構(gòu)?；顒?dòng)i節(jié)點(diǎn)表中的每一項(xiàng)就是一個(gè)活動(dòng)i節(jié)點(diǎn)緩沖區(qū)，用來存放一個(gè)被打開文件的in

50、ode。（以下把活動(dòng)i節(jié)點(diǎn)緩沖區(qū)簡稱為“活動(dòng)i節(jié)點(diǎn)”）。 空閑的活動(dòng)i節(jié)點(diǎn)相互鏈接在一起構(gòu)成“空閑活動(dòng)i節(jié)點(diǎn)鏈表”，這是一個(gè)雙向（非循環(huán)）鏈表，分別由鏈頭指針和鏈尾指針指向空閑活動(dòng)i節(jié)點(diǎn)鏈表的開始和結(jié)束。如下圖所示：鏈表頭空閑i節(jié)點(diǎn)1空閑i節(jié)點(diǎn)2空閑i節(jié)點(diǎn)3空閑i節(jié)點(diǎn)n 空閑活動(dòng)i節(jié)點(diǎn)鏈表為雙向（非循環(huán)）鏈表，分別由鏈表頭指針和鏈表尾指針指向空閑鏈表的首尾。NULL鏈表尾活動(dòng)i節(jié)點(diǎn)hash鏈表 當(dāng)某個(gè)文件（即某個(gè)磁盤i節(jié)點(diǎn)）被打開時(shí)，根據(jù)該i節(jié)點(diǎn)所對應(yīng)的設(shè)備號和i節(jié)點(diǎn)號計(jì)算其hash值： hn=(devno+inumber)%64可得到063共64個(gè)hash值。具有相同hash值的活動(dòng)i節(jié)點(diǎn)鏈

51、接在同一個(gè)hash鏈表中，這樣內(nèi)存中就有64個(gè)hash鏈表，每個(gè)hash鏈表都是由hash鏈頭開始的雙向鏈表（與數(shù)據(jù)緩沖區(qū)鏈表不同的是此處的空閑和非空閑鏈表都是非循環(huán)的） 。內(nèi)存活動(dòng)i節(jié)點(diǎn)表就是由這64個(gè)hash鏈表組成。如下圖所示：inodeinodeinodeinodeinodeinodeinodeinodeinode空閑鏈表頭Hash鏈表頭hn=0hn=1hn=63NULL空閑鏈表尾活動(dòng) inode 表的結(jié)構(gòu)4、文件系統(tǒng)的存儲(chǔ)結(jié)構(gòu) 在UNIX系統(tǒng)中，一個(gè)物理磁盤通常被劃分成一個(gè)或多個(gè)邏輯文件系統(tǒng)（簡稱文件系統(tǒng)或子文件系統(tǒng)），每個(gè)邏輯文件系統(tǒng)都被當(dāng)作一個(gè)由邏輯設(shè)備號標(biāo)識的邏輯設(shè)備。 UNI

52、X的普通文件和目錄文件就保存在這樣的文件系統(tǒng)中。邏輯文件系統(tǒng)的存儲(chǔ)結(jié)構(gòu)可分為兩類型： 一級存儲(chǔ)結(jié)構(gòu)型：常用于運(yùn)行環(huán)境較小的文件系統(tǒng)中 二級存儲(chǔ)結(jié)構(gòu)型：常用于運(yùn)行環(huán)境較大（特別是硬盤空間較大）的文件系統(tǒng)中、一級存儲(chǔ)結(jié)構(gòu)型 這種類型的邏輯文件系統(tǒng)由超級塊、索引節(jié)點(diǎn)表塊和數(shù)據(jù)區(qū)組成，（如果是根文件系統(tǒng)，就還包括引導(dǎo)塊）。整個(gè)存儲(chǔ)結(jié)構(gòu)是一維的。引導(dǎo)塊超級塊i節(jié)點(diǎn)表塊 數(shù)據(jù)區(qū)引導(dǎo)塊： boot程序超級塊： fs結(jié)構(gòu)，存放文件系統(tǒng)的靜態(tài)參數(shù)i 節(jié)點(diǎn)表塊：磁盤icommon表數(shù)據(jù)區(qū)： 各數(shù)據(jù)塊、兩級存儲(chǔ)結(jié)構(gòu)型 這種存儲(chǔ)結(jié)構(gòu)的文件系統(tǒng)由兩級組成：第一級由超級塊和若干個(gè)柱面組塊（cylinder group b

53、lock）所組成（如果是根文件系統(tǒng)則還包括引導(dǎo)塊）。第二級（即柱面組塊）又是由超級塊拷貝塊、柱面組信息塊，i節(jié)點(diǎn)表塊和數(shù)據(jù)區(qū)所組成。文件系統(tǒng)的存儲(chǔ)結(jié)構(gòu)是二維的。 目前大多數(shù)在大存儲(chǔ)環(huán)境下運(yùn)行的UNIX版本都采用這種存貯結(jié)構(gòu)，其優(yōu)點(diǎn)是能快速定位數(shù)據(jù)塊。 第一級存儲(chǔ)結(jié)構(gòu)引導(dǎo)塊超級塊1號柱面組塊2號柱面組塊n號柱面組塊 第二級存儲(chǔ)結(jié)構(gòu)超級塊拷貝塊柱面組信息塊i節(jié)點(diǎn)表塊數(shù)據(jù)區(qū)超級塊 是由fs定義的數(shù)據(jù)結(jié)構(gòu)，用于存放文件系統(tǒng)的靜態(tài)參數(shù)：struct fs 內(nèi)存超級塊鏈接指針 超級塊的磁盤地址 柱面組塊的位移量 最近修改時(shí)間 文件系統(tǒng)大小 文件系統(tǒng)塊大小 柱面組數(shù) 柱面組大小 片大小 文件系統(tǒng)標(biāo)識數(shù) 文件

54、系統(tǒng)標(biāo)志區(qū) 最近訪問的柱面組號 確定分配算法的參數(shù)超級塊拷貝塊： 在每個(gè)柱面組塊中存放有一個(gè)超級塊拷貝塊，其目的是使系統(tǒng)在超級塊被意外破壞時(shí)，能從任何一個(gè)柱面組中進(jìn)行恢復(fù)而不致使整個(gè)文件系統(tǒng)陷入癱瘓。 每個(gè)柱面組中的超級塊拷貝塊的存放位置為安全起見不一定都裝在柱面組中的最前面，而是可浮動(dòng)地裝在該柱面組中的任何位置。 一般性的方法是：如果第n號柱面組中的超級塊拷貝塊開始于該柱面組中的第i磁道，則第n+1柱面組中的超級塊拷貝塊開始于該柱面組中的第i+1磁道。文件系統(tǒng)一旦建立后，它們的位置就是固定不變的。柱面組信息塊（cg塊） 柱面組信息塊中存放的是有關(guān)該柱面組的靜態(tài)參數(shù)，它由數(shù)據(jù)結(jié)構(gòu)cg來定義：s

55、truct cg 內(nèi)存中柱面組塊的鏈接指針 本柱面組塊中i節(jié)點(diǎn)表大小 本柱面組塊中數(shù)據(jù)區(qū)大小 最近一次所用塊的位置 最近一次所用片的位置 最近一次所用i節(jié)點(diǎn)的位置 本柱面組空閑數(shù)據(jù)塊總數(shù) i節(jié)點(diǎn)位示圖 空閑塊位示圖位示圖： 位示圖為一張表，其中的每一個(gè)二進(jìn)制位（bit）的值來表示某一個(gè)資源（例如數(shù)據(jù)塊或i節(jié)點(diǎn)）的狀態(tài)，這樣每檢測一個(gè)字節(jié)的值就可以知道八個(gè)資源的狀態(tài)；每檢測一個(gè)四字節(jié)的整數(shù)的值就可以知道32個(gè)資源的狀態(tài)。 系統(tǒng)只需要維護(hù)一張較小的表（位示圖）就可以快速地檢測指定資源的忙閑狀態(tài)，或快速查找可用的空閑資源。5、文件系統(tǒng)的數(shù)據(jù)塊 在文件系統(tǒng)中，按存儲(chǔ)單位來劃分，由大到小可有下列層次：文

56、件系統(tǒng) (file system)柱面組 (cylinder group)柱面 (cylinder)磁道 (track)扇區(qū) (sector)DEV_BSIZE 512字節(jié)文件系統(tǒng)的邏輯塊大小： DEV_BSIZE * 2 即1k、2k、4k、8k、16k 目的：提高傳輸速度，減少overhead文件系統(tǒng)的邏輯片大?。?DEV_BSIZE * 2 即1k、2k、4k、8k、16k 目的：減少文件尾的碎片浪費(fèi)。6目錄和目錄項(xiàng) 在 UNIX文件系統(tǒng)中，目錄的組織形式采用的是樹形結(jié)構(gòu)，一個(gè)邏輯文件系統(tǒng)就是一棵目錄樹。 目錄也被當(dāng)作文件進(jìn)行處理，一個(gè)目錄文件的結(jié)構(gòu)為表狀結(jié)構(gòu)，其中通常包含有若干表項(xiàng)，稱

57、為目錄項(xiàng)，這些目錄項(xiàng)既可以是普通文件的入口，也可以是子目錄的入口。 每一個(gè)目錄項(xiàng)中通常包含兩部分內(nèi)容： 文件的 i 節(jié)點(diǎn)號 文件名目錄 /home/student/xiaolan 的路徑和目錄結(jié)構(gòu)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每個(gè)目

58、錄項(xiàng)由數(shù)據(jù)結(jié)構(gòu)direct來定義：#define MAXNAMLEN 14struct direct short d_ino; /*目錄項(xiàng)i節(jié)點(diǎn)號*/char d_name MAXNAMELEN; /*目錄項(xiàng)名字字符串*/ 每個(gè)目錄項(xiàng)的長度通常是確定的，為16個(gè)字節(jié)，其中前兩個(gè)字節(jié)存放文件的i節(jié)點(diǎn)號d_ino，后面14個(gè)字節(jié)存放文件名d_name。 這種定長目錄項(xiàng)在算法實(shí)現(xiàn)方面比較簡單，在使用靈活方面都有所不便，并且可能因許多目錄項(xiàng)名字長度不足14字符面有空間浪費(fèi)。 在UNIX的每個(gè)文件系統(tǒng)中，有三個(gè) i 節(jié)點(diǎn)號是有固定用途的：0號i節(jié)點(diǎn)： 表示空目錄項(xiàng)，當(dāng)某個(gè)目錄項(xiàng)被刪除時(shí)，該目錄項(xiàng)的 i

59、節(jié)點(diǎn)號被置為0。1號i節(jié)點(diǎn)： 表示壞塊文件，所有的磁盤壞塊都劃歸到該節(jié)點(diǎn)上；2號i節(jié)點(diǎn)： 固定表示該邏輯文件系統(tǒng)的根（root）目錄；3號i節(jié)點(diǎn)： 表示該文件系統(tǒng)中的 lost+found 目錄。7、變長目錄項(xiàng)的目錄結(jié)構(gòu)#define MAXNAMLEN 255struct direct long d_ino; /* 目錄項(xiàng)i節(jié)點(diǎn)號 */ short d_reclen; /* 目錄項(xiàng)入口長度（占用長度） */ short d_namelen； /* 目錄項(xiàng)名字長度 */ char d_name MAXNAMLEN+1 /* 名字字符串，+1為串結(jié)束符 0 */ 由于目錄中各目錄項(xiàng)的長度是變化的

60、，因此必須在目錄項(xiàng)中標(biāo)明本目錄項(xiàng)的長度。前一個(gè)目錄項(xiàng)釋放時(shí)，把該目錄項(xiàng)的空間全部合并到前一個(gè)目錄項(xiàng)中，形成前面一個(gè)目錄項(xiàng)占用空間大于實(shí)際使用的空間。 在增加新目錄時(shí)，先查看目錄中各目錄項(xiàng)是否占用多余空間，如有，則進(jìn)行壓縮，把釋放的空間分配給新目錄項(xiàng)。 變長目錄結(jié)構(gòu)增加了算法復(fù)雜性和工作量，通常用在硬件性能較高的大型系統(tǒng)中。8、文件名和文件名緩沖區(qū) 核心在內(nèi)存中建立了一個(gè)高速的名字緩沖區(qū)，用來存放最近使用過的文件名，核心認(rèn)為“最近使用過的文件名馬上還要使用的可能性最大” 。 名字緩沖區(qū)是由ncache定義的數(shù)據(jù)結(jié)構(gòu)，只包含文件名和索引節(jié)點(diǎn)指針等重要信息：struct ncache hash鏈表指