武漢大學(xué) 操作系統(tǒng)期末考試復(fù)習(xí)筆記

Chapter1:導(dǎo)論

計(jì)算機(jī)系統(tǒng)可以大致分為4個(gè)部分：硬件，操作系統(tǒng)，系統(tǒng)程序與應(yīng)用程序，用

戶

操作系統(tǒng)是配置在計(jì)算機(jī)硬件上的第一層軟件，是對(duì)硬件的首次擴(kuò)充，它位于硬

件與其他軟件之間，是所有其他軟件運(yùn)行的基礎(chǔ)。

對(duì)操作系統(tǒng)的公認(rèn)的定義：操作系統(tǒng)是一直在計(jì)算機(jī)上運(yùn)行的程序（通常稱為內(nèi)

核）

操作系統(tǒng)是計(jì)算機(jī)系統(tǒng)中的一個(gè)系統(tǒng)軟件，它管理和控制計(jì)算機(jī)系統(tǒng)中的

硬件和軟件資源。

裸機(jī)：沒(méi)有配置軟件的計(jì)算機(jī)，即計(jì)算機(jī)硬件

虛擬機(jī)：覆蓋了軟件的機(jī)器

最基本的操作系統(tǒng)類型有三種：批處理操作系統(tǒng)，分時(shí)操作系統(tǒng)，實(shí)時(shí)操作系

統(tǒng)

批處理系統(tǒng)：?jiǎn)蔚琅幚硐到y(tǒng)，多道批處理系統(tǒng)

在單處理機(jī)系統(tǒng)中，多道程序運(yùn)行的特點(diǎn)是多造、宏觀上并行和微觀上

串行。

分時(shí)系統(tǒng)：時(shí)間片輪轉(zhuǎn)，設(shè)置多路卡，（用戶能在很短時(shí)間內(nèi)獲得響應(yīng)）人機(jī)交

互，共享主機(jī)，方便用戶上機(jī)

實(shí)時(shí)系統(tǒng)：系統(tǒng)能及時(shí)響應(yīng)外部事件的請(qǐng)求，在規(guī)定的時(shí)間范圍內(nèi)完成對(duì)該事件

的處理，并控制實(shí)時(shí)任務(wù)協(xié)調(diào)一致地運(yùn)行。（響應(yīng)時(shí)間由控制對(duì)象決定，可靠性

高）

在主機(jī)控制下進(jìn)行的輸入/輸出操作稱為_聯(lián)用鐮人獻(xiàn)C操作。（聯(lián)機(jī)批處理，脫

機(jī)批處理，聯(lián)機(jī)UO,脫機(jī)I/O）

作業(yè)是用戶在一次解題或一個(gè)事務(wù)處理過(guò)程中要求計(jì)算機(jī)系統(tǒng)所做的工作集合，

包括用戶程序、所需的數(shù)據(jù)及命令等

操作系統(tǒng)的4個(gè)基本特征：并發(fā)，共享，虛擬，不確定（并發(fā)和共享互為存在

條件）

計(jì)算機(jī)系統(tǒng)的兩種運(yùn)行狀態(tài):核心態(tài)（kernelmode）,0,用戶態(tài)（usermode）,1

Chapter2：操作系統(tǒng)結(jié)構(gòu)

用戶接口：命令行接口(聯(lián)機(jī)命令接口，脫機(jī)命令接口)、批處理接口以及圖形

用戶接口(GUI)

系統(tǒng)調(diào)用(systemcalls):系統(tǒng)調(diào)用在運(yùn)行程序和操作系統(tǒng)之間提供接口

運(yùn)行程序和操作系統(tǒng)之間的參數(shù)傳遞有3種常用方法：寄存器中的參數(shù)傳遞，參

數(shù)存在內(nèi)存的一張表中表地址作為寄存器的參數(shù)傳遞，程序把參數(shù)壓入棧由操作

系統(tǒng)彈出

系統(tǒng)調(diào)用的類型：大致可分為5類：進(jìn)程控制，文件管理，設(shè)備管理，信息維護(hù)，

通信

系統(tǒng)調(diào)用與過(guò)程調(diào)用的區(qū)別：系統(tǒng)調(diào)用在核心態(tài)下運(yùn)行,子程序在用戶態(tài)下運(yùn)行;

系統(tǒng)調(diào)用通過(guò)中斷機(jī)構(gòu)進(jìn)入以實(shí)現(xiàn)運(yùn)行狀態(tài)的改變，子程序直接調(diào)用不涉及運(yùn)行

狀態(tài)改變

系統(tǒng)結(jié)構(gòu)：

MS-DOS：以最小的空間提供最多的功能。不劃分模塊，其接口和功能層次沒(méi)有

劃分清楚

早起的UNIX：受硬件功能限制，由兩個(gè)獨(dú)立的部分組成，系統(tǒng)程序和內(nèi)核

內(nèi)核包括了在物理硬件之上，系統(tǒng)調(diào)用之下的一切。內(nèi)核通過(guò)系統(tǒng)調(diào)用提供文件

系統(tǒng)、CPU調(diào)度、存儲(chǔ)管理和其他操作系統(tǒng)功能

操作系統(tǒng)分層：0層為硬件層，N層(最高層)為用戶接口，每層都利用較低層

的功能和服務(wù)，為較高層隱藏一定的數(shù)據(jù)結(jié)構(gòu)、操作和硬件的存在

層次結(jié)構(gòu)：給模塊賦予了層次順序使調(diào)用關(guān)系變得有序，在上下兩層不變的基礎(chǔ)

上可以換掉某層便于移植和擴(kuò)充，但犧牲一定的靈活性為代價(jià)

微內(nèi)核：微內(nèi)核通常包括最小的進(jìn)程和內(nèi)存管理以及通信功能

微內(nèi)核特點(diǎn)：降低了開發(fā)難度，具有較好的擴(kuò)展性及可移植性，特別適合大規(guī)模

開放式的分布系統(tǒng)。但是效率較低

模塊結(jié)構(gòu)，將操作系統(tǒng)內(nèi)核按照功能劃分為一個(gè)個(gè)獨(dú)立的模塊，模塊之間相對(duì)獨(dú)

立，只能通過(guò)事先規(guī)定好的接口方式來(lái)調(diào)用。每個(gè)模塊實(shí)現(xiàn)一個(gè)完整獨(dú)立的功能,

所有模塊之間相互調(diào)用，共同構(gòu)成一個(gè)完整的系統(tǒng)內(nèi)核。

模塊結(jié)構(gòu)特點(diǎn)：效率高，但全局函數(shù)使用多造成訪問(wèn)控制困難，結(jié)構(gòu)不清晰可理

解性可維護(hù)性可移植性差

宏內(nèi)核：在運(yùn)行過(guò)程中，它是一個(gè)獨(dú)立的進(jìn)程。模塊結(jié)構(gòu)、層次結(jié)構(gòu)的系統(tǒng)內(nèi)核

基本都是宏內(nèi)核

微內(nèi)核：大部分內(nèi)核模塊都作為獨(dú)立的進(jìn)程，它們之間通過(guò)信息通信使模塊之間

互相提供服務(wù)。

Chapter3進(jìn)程

進(jìn)程的順序執(zhí)行:程序通常由若干個(gè)程序段所組成，它們必須按照某種先后次序

來(lái)執(zhí)行，僅當(dāng)前一個(gè)操作執(zhí)行完后才能執(zhí)行后繼操作

順序執(zhí)行的特征：順序性，封閉性(一旦開始運(yùn)行結(jié)果不受外界影響)，可再現(xiàn)

性(執(zhí)行情況相同重復(fù)執(zhí)行獲得相同結(jié)果)

程序的并發(fā)執(zhí)行:若干程序或程序段同時(shí)在系統(tǒng)中運(yùn)行

并發(fā)執(zhí)行的特性：間斷性，失去封閉性(進(jìn)程共享資源)，不可再現(xiàn)性

Bernstein條件:能保證兩個(gè)程序段并發(fā)執(zhí)行而不會(huì)產(chǎn)生與時(shí)間有關(guān)的錯(cuò)誤(全局

變量的改變什么的)

R(Si)nw(Sj)={}這兩條保證

R(Sj)nw(Si)={}兩次讀之間數(shù)據(jù)不變

w(Si)nw(Sj)={}本條保證寫操作結(jié)果不丟

考慮下面是條語(yǔ)句：

SI：a=x+yS2：b=z+l

S3：c=a-bS4：d=c+l

R(Sl)={x,y}R(S2)={z}R(S3)={a,b}

W(Sl)={a}W(S2)=W(S3)={c}

因R(Sl)nW(S2)UR(S2)nW(Sl)UW(Sl)nW(S2)={},故SI和S2可以并發(fā)

執(zhí)行。

因R(S2)nW(S3)UR(S3)nW(S2)UW(S3)nW(S2)=,故S2和S3不能并發(fā)

執(zhí)行。

并發(fā)語(yǔ)句描述：cobegin.….coend

進(jìn)程：進(jìn)程是執(zhí)行中的程序。一個(gè)進(jìn)程包括，代碼段，程序計(jì)時(shí)器和處理機(jī)寄存

器內(nèi)容，棧，數(shù)據(jù)部分

進(jìn)程的特征：動(dòng)態(tài)性(進(jìn)程是動(dòng)態(tài)存在和消失的而程序是靜態(tài)實(shí)體)，并發(fā)性(多

個(gè)進(jìn)程實(shí)體同時(shí)在內(nèi)存并能在一段時(shí)間內(nèi)同時(shí)發(fā)生)，獨(dú)立性(進(jìn)程是獨(dú)立運(yùn)行

的基本單位)，異步性(進(jìn)程各自以獨(dú)立的不可預(yù)知的速度向前推進(jìn))，結(jié)構(gòu)性(由

很多段組成(程序段，數(shù)據(jù)段，控制塊))

進(jìn)程狀態(tài)：新建，運(yùn)行，等待，就緒，終止

通常一個(gè)進(jìn)程至少應(yīng)有以下三種基本狀態(tài)：就緒狀態(tài)，執(zhí)行狀態(tài)(運(yùn)行)，阻塞

狀態(tài)(等待狀態(tài)通常是I/O請(qǐng)求)

進(jìn)程由PCB,程序段，數(shù)據(jù)段三部分組成

進(jìn)程控制塊(PCB,process-control-block)：每個(gè)進(jìn)程在操作系統(tǒng)內(nèi)用進(jìn)程控制塊

表示。PCB是描述和管理進(jìn)程的數(shù)據(jù)結(jié)構(gòu)。它是進(jìn)程實(shí)體的一部分，操作系統(tǒng)

通過(guò)PCB感知進(jìn)程的存在，PCB是進(jìn)程存在的唯一?標(biāo)志。

進(jìn)程的掛起狀態(tài)：(由于系統(tǒng)故障，檢查，資源內(nèi)存不足等原因)人為將進(jìn)程掛

起使之處于靜止?fàn)顟B(tài)。

/*進(jìn)程調(diào)度*/

作業(yè)隊(duì)列：系統(tǒng)中所有進(jìn)程的集合

就緒隊(duì)列：內(nèi)存中就緒并等待執(zhí)行的所有進(jìn)程的集合（常用鏈表實(shí)現(xiàn)）

設(shè)備隊(duì)列：等待某DO設(shè)備的進(jìn)程隊(duì)列

長(zhǎng)程調(diào)度（作業(yè)調(diào)度）：選擇可以進(jìn)入就緒隊(duì)列的進(jìn)程

短程調(diào)度（CPU調(diào)度）：選擇下一個(gè)執(zhí)行并分配CPU

長(zhǎng)程調(diào)度（作業(yè)調(diào)度）的頻率相對(duì)低，長(zhǎng)程調(diào)度控制了多道

進(jìn)程可以分為：DO型進(jìn)程，和CPU型進(jìn)程

上下文切換：將CPU切換到另一個(gè)進(jìn)程需要保存當(dāng)前進(jìn)程的狀態(tài)并恢復(fù)另一個(gè)

進(jìn)程的狀態(tài)，這個(gè)任務(wù)稱為上下文切換

原語(yǔ)：原語(yǔ)是由若干條機(jī)器指令構(gòu)成的，用以完成特定功能的一段程序，實(shí)現(xiàn)對(duì)

進(jìn)程的管理和控制。這段程序在執(zhí)行期間不可分割（原語(yǔ)不允許被中斷。不同層

次之間的對(duì)話的語(yǔ)言稱為原語(yǔ)）

種類：創(chuàng)建原語(yǔ)，撤銷原語(yǔ)，阻塞原語(yǔ)，喚醒原語(yǔ)，掛起原語(yǔ)，激活原語(yǔ)…

進(jìn)程創(chuàng)建：通過(guò)創(chuàng)建進(jìn)程系統(tǒng)調(diào)用可以創(chuàng)建多個(gè)新進(jìn)程，創(chuàng)建進(jìn)程稱為父進(jìn)程，

被創(chuàng)建進(jìn)程稱為子進(jìn)程。每個(gè)新進(jìn)程可以再創(chuàng)建新進(jìn)程，從而形成了進(jìn)程樹。進(jìn)

程樹乂稱為進(jìn)程圖或進(jìn)程家族樹

有的系統(tǒng)中，若父進(jìn)程終止不允許子進(jìn)程繼續(xù)，這種現(xiàn)象稱為：級(jí)聯(lián)終止

進(jìn)程的組織：線性方式，鏈接方式（鏈表方式），索引方式

進(jìn)程通信：進(jìn)程之間的信息交換

低級(jí)進(jìn)程通信方式：進(jìn)程互斥與同步交換的信息量較少且效率較低。P、V操作

是一種低級(jí)進(jìn)程通信原語(yǔ)

高級(jí)進(jìn)程通信方式：進(jìn)程之間以較高的效率傳送大量數(shù)據(jù)

高級(jí)進(jìn)程通信方式分為三大類：共享存儲(chǔ)器系統(tǒng)，消息傳遞系統(tǒng)，管道通信系統(tǒng)

或共享文件系統(tǒng)

共享存儲(chǔ)器系統(tǒng)：相互通信的進(jìn)程共享某些數(shù)據(jù)結(jié)構(gòu)或共享存儲(chǔ)區(qū)

消息傳遞系統(tǒng)：進(jìn)程間的數(shù)據(jù)交換以消息為單位，程序員直接利用系統(tǒng)提供的一

組通信命令（原語(yǔ)）來(lái)實(shí)現(xiàn)通信。

消息傳遞系統(tǒng)因其實(shí)現(xiàn)方式不同可分為：直接通信方式（講消息直接發(fā)在接受進(jìn)

程的消息隊(duì)列上），間接通信方式（將消息發(fā)送到信箱）

管道（共享文件）通信：通過(guò)連接讀進(jìn)程和寫進(jìn)程的共享文件來(lái)實(shí)現(xiàn)讀寫進(jìn)程之

間通信

緩沖（Buffering）：通信進(jìn)程交換的信息都駐留在臨時(shí)隊(duì)列中，隊(duì)列實(shí)現(xiàn)有三種形

式，零容量（發(fā)送者必須等待接受者），有限容量（線路滿則發(fā)送者必須等待），

無(wú)限容量（發(fā)送者無(wú)需等待）

管道：使用管道通信時(shí)，基本上采用文件系統(tǒng)的原有機(jī)制實(shí)現(xiàn)。包括創(chuàng)建、打開、

關(guān)閉、讀寫等。

管道機(jī)制應(yīng)提供以下三方面的協(xié)調(diào)能力：互斥（互斥讀寫管道），同步（管道空

滿情況處理），存在（確定對(duì)方是否存在）

在單處理機(jī)計(jì)算機(jī)系統(tǒng)中，如果有N個(gè)進(jìn)程（只考慮等待，就緒，運(yùn)行）

那么

運(yùn)行狀態(tài)最多1個(gè)，最少0個(gè)；

等待狀態(tài)最多N個(gè)，最少。個(gè)；

就緒狀態(tài)最多N-1個(gè)，最少0個(gè)。

Chapter4線程

在操作系統(tǒng)中引入進(jìn)程的目的是：使用多道程序能并發(fā)執(zhí)行，以改善資源利用率

及提高系統(tǒng)吞吐量

在操作系統(tǒng)中引入線程的目的是：減少程序并發(fā)執(zhí)行的時(shí)空開銷，使操作系統(tǒng)有

更好的并發(fā)性

線程是CPU使用的一個(gè)基本單元，包括線程標(biāo)識(shí)（threadID）,程序計(jì)數(shù)器（PC）,

寄存器集（registerset）,棧（stack）

線程自己基本上不擁有資源，只擁有一點(diǎn)在運(yùn)行時(shí)必不可少的資源（如程序計(jì)數(shù)

器、寄存器集和棧）。但它可以與同屬一個(gè)進(jìn)程的其他線程共享進(jìn)程擁有的全部

資源

線程與屬于同一進(jìn)程的線程共享：代碼段，數(shù)據(jù)段，其他操作系統(tǒng)資源

線程的狀態(tài)，同步與通信與進(jìn)程類似

進(jìn)程的掛起及終止將影響到其中所有進(jìn)程

線程的優(yōu)點(diǎn)：響應(yīng)能力強(qiáng)（即使進(jìn)程的一塊被阻塞了，其他部分也能運(yùn)行），資

源共享，經(jīng)濟(jì)性，多處理器體系結(jié)構(gòu)的利用，創(chuàng)建撤銷切換時(shí)間短，共享內(nèi)存和

資源線程間通信方便

多線程模型

操作系統(tǒng)中有多種方式實(shí)現(xiàn)對(duì)進(jìn)程的支持：內(nèi)核線程（kernelThreads）,用戶線

程（UserThreads）的組合實(shí)現(xiàn)

內(nèi)核線程：也稱內(nèi)核級(jí)線程，是指依賴于內(nèi)核，由操作系統(tǒng)內(nèi)核完成創(chuàng)建和撤銷

工作的線程。

一個(gè)內(nèi)核線程的阻塞不會(huì)影響其他線程的運(yùn)行。

處理機(jī)分配的對(duì)象是線程，所以有多個(gè)線程的進(jìn)程將獲得更多的處理機(jī)時(shí)間

用戶線程：也稱用戶級(jí)線程，是指不依賴于操作系統(tǒng)核心，由應(yīng)用進(jìn)程利用線程

庫(kù)提供創(chuàng)建、同步、調(diào)度和管理線程的函數(shù)來(lái)控制的線程

用戶線程的維護(hù)由應(yīng)用進(jìn)程完成，可以用于不支持線程的操作系統(tǒng)

當(dāng)一個(gè)線程阻塞時(shí)，整個(gè)進(jìn)程都必須等待。

處理機(jī)時(shí)間是分配給進(jìn)程的，進(jìn)程內(nèi)有多個(gè)線程時(shí)，每個(gè)線程的執(zhí)行時(shí)間相對(duì)少

一占八、、

用戶線程與內(nèi)核線程的關(guān)系

多對(duì)一模型：將多個(gè)用戶線程映射到一個(gè)內(nèi)核線程。線程管理由線程庫(kù)在用戶空

間進(jìn)行。用于不支持內(nèi)核線程的系統(tǒng)中（只有一個(gè)內(nèi)核線程，相當(dāng)于沒(méi)有）

一對(duì)一模型：將每個(gè)用戶線程映射到一個(gè)內(nèi)核線程。這種模型的絕大多數(shù)實(shí)現(xiàn)限

制了系統(tǒng)支持的線程數(shù)量

多對(duì)多模型：多個(gè)用戶線程到同樣數(shù)量或更少的內(nèi)核線程上

多線程問(wèn)題：

線程取消可以再i下兩種情況下發(fā)生：異步取消（一個(gè)線程立即終止目標(biāo)進(jìn)程），

延遲取消（目標(biāo)線程不斷檢查它是否應(yīng)該終止）

線程與進(jìn)程的比較：從調(diào)度的基本單位，擁有資源的基本單位，并發(fā)性，和系統(tǒng)

開銷四個(gè)方面說(shuō)。

ChaptersCPU調(diào)度

處理機(jī)的三級(jí)調(diào)度：作業(yè)調(diào)度，進(jìn)程調(diào)度，交換調(diào)度

作業(yè)調(diào)度：又稱長(zhǎng)程調(diào)度，宏觀調(diào)度和高級(jí)調(diào)度，從外存上處于后備狀態(tài)的作業(yè)

中選擇一個(gè)或多個(gè)作業(yè)，給他們分配內(nèi)存、I/O設(shè)備等必要資源，并建立相應(yīng)的

進(jìn)程，使該作業(yè)具有獲得競(jìng)爭(zhēng)處理機(jī)的權(quán)利

作業(yè)調(diào)度的運(yùn)行頻率低，通常兒分鐘一次

進(jìn)程調(diào)度：又稱短程調(diào)度，微觀調(diào)度和低級(jí)調(diào)度，從就緒隊(duì)列中選取一個(gè)進(jìn)程，

將處理機(jī)分配給它。

進(jìn)程調(diào)度的運(yùn)行頻率很高，一般十幾毫秒就要運(yùn)行一次

交換調(diào)度：又稱中程調(diào)度，中級(jí)調(diào)度，將內(nèi)存總暫時(shí)不用的信息移到外存，以騰

出空間給內(nèi)存中的其他進(jìn)程使用，或?qū)⑿枰男畔耐獯孀x入內(nèi)存。

交換調(diào)度的目的是，提高內(nèi)存利用率和系統(tǒng)吞吐量

交換調(diào)度的運(yùn)行頻率介于上面兩者之間

作業(yè)：是用戶在一次解題或一個(gè)事務(wù)處理過(guò)程中要求計(jì)算機(jī)系統(tǒng)所做的工作的集

合，包括用戶程序、所需的數(shù)據(jù)及命令等

作業(yè)從提交到完成要經(jīng)歷四種狀態(tài)：提交狀態(tài)，后備狀態(tài)（將作業(yè)插入后備作業(yè)

隊(duì)列中等待調(diào)度運(yùn)行），運(yùn)行狀態(tài)（作業(yè)在內(nèi)存中執(zhí)行），完成狀態(tài)

作業(yè)控制塊（JCB,jobcontrolblock）：系統(tǒng)通過(guò)JCB感知作業(yè)的存在，JCB是

作業(yè)存在的唯一標(biāo)志

一個(gè)作業(yè)可以分成若干順序處理的加工步驟，每個(gè)步驟稱為一個(gè)作業(yè)步

多道程序的設(shè)計(jì)目標(biāo)在于任何時(shí)候都有某些進(jìn)程運(yùn)行，使CPU利用率最大化。

CPU調(diào)度可能發(fā)生如下4種情況

從運(yùn)行狀態(tài)轉(zhuǎn)到等待狀態(tài)

從運(yùn)行狀態(tài)轉(zhuǎn)到就緒狀態(tài)

從等待狀態(tài)轉(zhuǎn)到就緒狀態(tài)

進(jìn)程終止

1.4兩種情況的調(diào)度稱為非搶占調(diào)度，2,3兩種情況的調(diào)度稱為搶占式調(diào)度

進(jìn)程調(diào)度的兩種方式：搶占方式，非搶占方式

搶占方式：又稱波多方式。搶占原則有，優(yōu)先權(quán)，時(shí)間片

分派程序：用來(lái)將對(duì)CPU的控制交給由短程調(diào)度程序選擇的進(jìn)程

分派延遲：分派程序終止一個(gè)進(jìn)程的運(yùn)行并啟動(dòng)另一個(gè)進(jìn)程運(yùn)行所花的時(shí)間，也

成為調(diào)度時(shí)間

調(diào)度準(zhǔn)則：

CPU利用率

吞吐量（單位時(shí)間內(nèi)運(yùn)行完的程序數(shù)）

周轉(zhuǎn)時(shí)間（進(jìn)程從提交到運(yùn)行結(jié)束的全部時(shí)間

等待時(shí)間（進(jìn)程在就緒隊(duì)列中等待調(diào)度的時(shí)間總和）

響應(yīng)時(shí)間（從提交請(qǐng)求到系統(tǒng)首次產(chǎn)生響應(yīng)所用的時(shí)間）

帶全周轉(zhuǎn)時(shí)間（作業(yè)周轉(zhuǎn)時(shí)間與作業(yè)實(shí)際運(yùn)行時(shí)間的比）

調(diào)度算法：（畫圖用到gantt圖）

FCFS先來(lái)先服務(wù)調(diào)度，適用于作業(yè)調(diào)度，進(jìn)程調(diào)度

算法簡(jiǎn)單易于實(shí)現(xiàn)，不適用與短作業(yè)和I/O繁忙的作業(yè)

SJB最短作業(yè)優(yōu)先（搶占/非搶占）

適合短作業(yè)，對(duì)長(zhǎng)作業(yè)不利，運(yùn)行時(shí)間為估計(jì)

搶占SJB調(diào)度有時(shí)稱為最短剩余時(shí)間優(yōu)先調(diào)度，若到達(dá)新進(jìn)程的CPU區(qū)間短于當(dāng)

前運(yùn)行進(jìn)程的剩余時(shí)間，則它將搶占CPU。

可能有饑餓

優(yōu)先級(jí)調(diào)度（搶占/非搶占）

優(yōu)先級(jí)的類型：靜態(tài)優(yōu)先級(jí)，動(dòng)態(tài)優(yōu)先級(jí)（確定原則：占用CPU時(shí)間，等待時(shí)間）

存在的問(wèn)題：饑餓，低優(yōu)先級(jí)的進(jìn)程可能永遠(yuǎn)得不到運(yùn)行

解決方法：老化，視進(jìn)程等待時(shí)間的延長(zhǎng)提高其優(yōu)先級(jí)數(shù)

時(shí)間片輪轉(zhuǎn)調(diào)度（RR）

每個(gè)進(jìn)程得到小單位的CPU時(shí)間，稱為時(shí)間片，通常為10700毫秒。時(shí)間片用

完后，該進(jìn)程將被搶占并插入就緒隊(duì)列末尾。

時(shí)間片大小：太大：退化為FCFS太?。赫{(diào)度頻繁系統(tǒng)開銷大?，F(xiàn)代操作系統(tǒng)的

時(shí)間片一般為10-100ms,上下文切換時(shí)間一般少于10uSo

確定時(shí)間片大小應(yīng)考慮的因素：

系統(tǒng)對(duì)響應(yīng)時(shí)間的要求：響應(yīng)時(shí)間=時(shí)間片*進(jìn)程數(shù)

就緒隊(duì)列中的進(jìn)程數(shù)目：時(shí)間片應(yīng)與就緒進(jìn)程數(shù)成反比

系統(tǒng)的處理能力：考慮響應(yīng)時(shí)間在可承受范圍內(nèi)，系統(tǒng)速度快則時(shí)間片可以增長(zhǎng)

時(shí)間片輪轉(zhuǎn)算法的特點(diǎn)及改進(jìn)：

虛擬時(shí)間片輪轉(zhuǎn)法（針對(duì)偏重I/O的進(jìn)程）：

新進(jìn)程基于FCFS進(jìn)入就緒隊(duì)列，進(jìn)程用完時(shí)間片后也進(jìn)入就緒隊(duì)列，進(jìn)程因I/O

阻塞進(jìn)入I/O隊(duì)列，I/O完成時(shí)進(jìn)程進(jìn)入附加隊(duì)列，附加隊(duì)列的優(yōu)先級(jí)高于就緒

隊(duì)列，當(dāng)進(jìn)程從附加隊(duì)列被調(diào)度時(shí)，其運(yùn)行時(shí)間不超過(guò)上次發(fā)生中斷時(shí)剩余的時(shí)

間。

高響應(yīng)比優(yōu)先調(diào)度算法

響應(yīng)比=1+作業(yè)等待時(shí)間/估計(jì)運(yùn)行時(shí)間

I

A、B、C、D、E的到達(dá)時(shí)間依次為0、1、2、3、

4,要求運(yùn)行時(shí)間依次為3、6、4、5、2

0：A運(yùn)行，BCD依次到達(dá)；

3：rB=1+2/6,rc=1+1/4,rD=l：B先運(yùn)行。

9：rc=1+7/4,rD=1+6/5,rE=1+5/2；E先運(yùn)行。

11：rc=1+9/4,rD=1+8/5；C先運(yùn)行。

?由此可知作業(yè)的運(yùn)行順序?yàn)锳、B、E、C、D。

多級(jí)隊(duì)列調(diào)度

將就緒隊(duì)列分為多個(gè)獨(dú)立隊(duì)列，每個(gè)隊(duì)列有自己的調(diào)度算法，根據(jù)進(jìn)程屬性，一

個(gè)進(jìn)程被永久分配到一個(gè)隊(duì)列

例如分為前臺(tái)（交互式）RR算法，和后臺(tái)（批處理）FCFSo前臺(tái)的優(yōu)先級(jí)高

多級(jí)反饋隊(duì)列調(diào)度

進(jìn)程能在不同的隊(duì)列間移動(dòng)。如果進(jìn)程使用過(guò)多的CPU時(shí)間，那么它會(huì)被移動(dòng)到

更低優(yōu)先級(jí)隊(duì)列。此外，在較低優(yōu)先級(jí)隊(duì)列中等待時(shí)間過(guò)長(zhǎng)的進(jìn)程會(huì)被移到更高

優(yōu)先級(jí)隊(duì)列

每個(gè)隊(duì)列有不同優(yōu)先級(jí)，第一隊(duì)列最高，其余遞減，每個(gè)隊(duì)列的時(shí)間片大小也各

不相同，優(yōu)先級(jí)高的隊(duì)列時(shí)間片短。

當(dāng)一個(gè)新進(jìn)程進(jìn)入系統(tǒng)時(shí)，首先將它放入第1個(gè)隊(duì)列的末尾，按先來(lái)先服務(wù)的原

則排隊(duì)等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如能在此時(shí)間片內(nèi)完成，便可準(zhǔn)備撤離

系統(tǒng)；如果它在一個(gè)時(shí)間片結(jié)束時(shí)尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第2隊(duì)

列的末尾，再同樣地按先來(lái)先服務(wù)原則等待調(diào)度執(zhí)行。如此下去，最后一個(gè)隊(duì)列

中使用時(shí)間片輪轉(zhuǎn)調(diào)度算法。僅當(dāng)?shù)?個(gè)隊(duì)列為空時(shí)，調(diào)度程序才調(diào)度第2隊(duì)列

中的進(jìn)程運(yùn)行；僅當(dāng)?shù)?個(gè)至第（i-D個(gè)隊(duì)列均為空時(shí)，才會(huì)調(diào)度第i個(gè)隊(duì)列

中的進(jìn)程運(yùn)行。當(dāng)處理機(jī)正在為第i個(gè)隊(duì)列中的某進(jìn)程服務(wù)時(shí)，若又有新進(jìn)程進(jìn)

入優(yōu)先級(jí)較高的隊(duì)列中，則此時(shí)新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，即由調(diào)度

程序把正在執(zhí)行進(jìn)程放回第i個(gè)隊(duì)列末尾，重新將處理機(jī)分配給新進(jìn)程。

多級(jí)反饋隊(duì)列調(diào)度算法能較好滿足各類用戶的需求

公平分享調(diào)度算法：基于進(jìn)程組來(lái)分配CPU時(shí)間，其實(shí)現(xiàn)思想是對(duì)系統(tǒng)中的每個(gè)

用戶賦予某種權(quán)值，根據(jù)用戶權(quán)值大小，按比例分配處理機(jī)時(shí)間。

進(jìn)程切換：在操作系統(tǒng)中凡是要進(jìn)行中斷處理和進(jìn)程調(diào)度時(shí)，都將涉及到進(jìn)程上

下文的保存的恢復(fù)。

中斷時(shí)：系統(tǒng)保存和恢復(fù)的是同一個(gè)進(jìn)程的上下文

進(jìn)程調(diào)度時(shí)恢復(fù)的是調(diào)度程序所選中進(jìn)程的上下文

既考慮作業(yè)等待時(shí)間，又考慮作業(yè)執(zhí)行時(shí)間的調(diào)度算法是響應(yīng)比高優(yōu)先調(diào)度

Chapter6進(jìn)程同步

進(jìn)程同步：系統(tǒng)中各進(jìn)程之間邏輯上的相互制約關(guān)系叫做進(jìn)程同步

在多道程序系統(tǒng)中，進(jìn)程之間存在著的不同制約關(guān)系可以劃分為兩類：同步和互斥

同步指進(jìn)程間具有的一定邏輯關(guān)系；互斥是指進(jìn)程間在使用共享資源方面的約束關(guān)系。

臨界區(qū)問(wèn)題：每個(gè)進(jìn)程有一個(gè)訪問(wèn)共享數(shù)據(jù)的代碼段，稱為臨界區(qū)（critical

section）。需保證一個(gè)進(jìn)程在其臨界區(qū)執(zhí)行時(shí)，不允許其他進(jìn)程在其臨界區(qū)執(zhí)行。

臨界資源：一段時(shí)間內(nèi)僅允許一個(gè)進(jìn)程使用的資源稱為臨界資源。如打印機(jī)，共

享變量

同類臨界區(qū)：所有與同一臨界資源相關(guān)聯(lián)的臨界區(qū)

臨界區(qū)問(wèn)題的解決應(yīng)滿足：互斥，前進(jìn)（如果沒(méi)有進(jìn)程在其臨界區(qū)內(nèi)執(zhí)行，且有

進(jìn)程需要進(jìn)入臨界區(qū)，那么只有不在剩余區(qū)執(zhí)行的進(jìn)程可以參加選擇，以確定下

一個(gè)進(jìn)入臨界區(qū)的進(jìn)程，且選擇不能無(wú)限期延長(zhǎng)），有限等待（在一個(gè)進(jìn)程提出

進(jìn)入臨界區(qū)的請(qǐng)求和該請(qǐng)求得到答復(fù)的時(shí)間內(nèi)，其他進(jìn)程進(jìn)入臨界區(qū)的次數(shù)必須

是有限的）

訪問(wèn)臨界資源應(yīng)遵循的原則：空閑讓進(jìn)，忙則等待，有限等待，讓權(quán)等待（當(dāng)

進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)釋放處理機(jī)）

Peterson算法

enumbooIean{faIse,true)；

booIeanfIag[2]={faIse,faIse)；intturn；

PO：{

do{

fIag[0]=true；turn=1；

while(flag[1]&&turn==1)；〃實(shí)現(xiàn)互斥，前進(jìn)

進(jìn)程PO的臨界區(qū)代碼CSO；

fIag[0]—faIse；

進(jìn)程PO的其他代碼；}

while(true)}

P1：（

do{

flag[1]=true；turn=0；

while（flag[0]&&turn==0）；

進(jìn)程P1的臨界區(qū)代碼CS1；

fIag[1]=faIse；

進(jìn)程P1的其他代碼；}

while（true）}

硬件同步：用硬件方法實(shí)現(xiàn)互斥的主要思想是保證檢查操作與修改操作不被打斷

禁止中斷方法：當(dāng)進(jìn)程執(zhí)行臨界區(qū)代碼時(shí)，禁止中斷（很多缺點(diǎn)）

硬件指令方法

用TS實(shí)現(xiàn)互斥：

booIeanTS(boolean*1ock)

(

booIeanold；

oId=*lock；

*lock=true；

returnold；

1

?

?■

whileTS(&lock)；

〃lock=1的話，陷入while；lock=0的話，將lock置1,進(jìn)入臨界區(qū)

臨界區(qū)代碼CriticalSection；

Iock=faIse；

其他代碼remaindersection；

?

用swap指令實(shí)現(xiàn)進(jìn)程互斥：

//swap(a,b)交換兩值

I

I

I

key=true；

while(key!=faIse)Swap(&Iock,&key)；

//如果lock=true,不停的swap,直到lock=false,進(jìn)入臨界區(qū)

臨界區(qū)代碼CriticalSection；

lock=faIse；

其他代碼remaindersection；

?

?

用鎖機(jī)制實(shí)現(xiàn)互斥(自旋鎖)

Iock(w)

(

while(w==1)；

w=1；

)

unIock(w)

(

w=0；

)

進(jìn)程P1進(jìn)程P2

II

II

II

Iock(w)；Iock(w)；

臨界區(qū)；臨界區(qū)；

unIock(w)；unIock(w)；

??

這一'頁(yè)的方法都不能實(shí)現(xiàn)讓權(quán)等待，即存在忙等待

信號(hào)量：信號(hào)量S是個(gè)整型變量，除了初始化外，它只能通過(guò)兩個(gè)標(biāo)準(zhǔn)原子操作

wait()和signaI()來(lái)訪問(wèn)。

wait(S)signaI(S):

{whileS0dono-op;{S++;

S—;}

Wait是原來(lái)的P操作

Signal是原來(lái)的V操作

當(dāng)進(jìn)程需要使用資源時(shí)則對(duì)信號(hào)量執(zhí)行wait,當(dāng)釋放資源時(shí)執(zhí)行signal

互斥信號(hào)量的實(shí)現(xiàn)

信號(hào)量由兩個(gè)成員(s,q)組成，其中s是一個(gè)具有非負(fù)初值的整型變量，q是

一個(gè)初始狀態(tài)為空的隊(duì)列。又稱信號(hào)燈。

除信號(hào)量的初值外，信號(hào)量的值僅能由P操作(又稱為wait操作)和V操作(又

稱為signal操作)改變。

wait(semaphore*s)

{s_>vaIue—;

if(s->vaIue<0)

{addthisprocesstos->list;

//如果所有資源都被占用，加入等待隊(duì)列，if里的value是被減過(guò)的。如果等

于0,那么value被減過(guò)之前是1,有資源，就不用等待了

bIock();

1}

signaI(semaphre*s)

{s->vaIue++;

if(s->vaIue<=0)

//如果有進(jìn)程在等待，就把第一個(gè)進(jìn)程移除。注意if里的value是被加過(guò)的，

如果value=0,那么就沒(méi)有進(jìn)程在等待

{removeaprocessPfroms->list;

wakeup(P);

1

)

信號(hào)量中的整型變量S表示系統(tǒng)中某類資源的數(shù)目。

當(dāng)其值大于0時(shí)，表示系統(tǒng)中當(dāng)前可用資源的數(shù)目；

當(dāng)其值小于0時(shí)，其絕對(duì)值表示系統(tǒng)中因請(qǐng)求該類資源而被阻塞的進(jìn)程數(shù)目。

P,V操作類似

P,V操作是原語(yǔ)

利用信號(hào)量實(shí)現(xiàn)互斥

設(shè)S為兩個(gè)進(jìn)程P1、P2實(shí)現(xiàn)互斥的信號(hào)量，S的初值應(yīng)為1(即可用資源數(shù)目為

Do只需把臨界區(qū)置于P(S)和V(S)之間，即可實(shí)現(xiàn)兩進(jìn)程的互斥。

卜解法工

除理信號(hào)量實(shí)現(xiàn)前趨關(guān)系

■例如：Pl、P2、設(shè)七個(gè)同步信號(hào)

P3、P4、P5、P6、b、c、d、e、

為一組合作進(jìn)f、g分別表示進(jìn)程

程，其前驅(qū)圖如之間的前驅(qū)關(guān)

下所示，試用P、系，如圖所示，

V操作完成這六個(gè)其初值均為0。這

進(jìn)程的同步。六個(gè)進(jìn)程的同步

描述如下：

P2()

解法2

P(a)；

執(zhí)行P2的代碼;-設(shè)五個(gè)同步信號(hào)量fl、f2、f3、f4、f5分

v(c);G別表示進(jìn)程Pl、P2、P3、P4、P5是否執(zhí)

v(d);

P5行完成，其初值均為0。這六個(gè)進(jìn)程的同

步描述如下：

3

■0表示未完成，1表示完成了

P2()

{

犬仕)；

執(zhí)行P2的代碼;

v(f2);

V(⑵；

死鎖：兩個(gè)或多個(gè)進(jìn)程無(wú)限等待一個(gè)事件的發(fā)生，而該事件正是由其中一個(gè)的等

待進(jìn)程引起的。

饑餓：無(wú)限期的阻塞。進(jìn)程可能永遠(yuǎn)都無(wú)法從它等待的信號(hào)量隊(duì)列中移去

經(jīng)典同步問(wèn)題：

有限緩沖問(wèn)題生產(chǎn)者一消費(fèi)者問(wèn)題

它描述了一組生產(chǎn)者進(jìn)程向一組消費(fèi)者進(jìn)程提供產(chǎn)品，它們共享一個(gè)有界緩沖

池。緩沖池中的每個(gè)緩沖區(qū)可以存放一個(gè)產(chǎn)品，生產(chǎn)者進(jìn)程不斷生產(chǎn)產(chǎn)品并將產(chǎn)

品放入緩沖池中，消費(fèi)者進(jìn)程不斷從緩沖池內(nèi)取出產(chǎn)品并消費(fèi)。

設(shè)置兩個(gè)同步信號(hào)量empty、full,其初值分別為n、0。

//empty代表緩沖區(qū)空的區(qū)域個(gè)數(shù)，fuII代表緩沖區(qū)被填充的區(qū)域個(gè)數(shù)

mutex是確保對(duì)緩沖區(qū)的訪問(wèn)互斥的信號(hào)量，初值為1

<4生產(chǎn)者消費(fèi)者

—生產(chǎn)一個(gè)產(chǎn)品；p(full)；

p(empty)；p(mutex)；

p(mutex)；從緩沖區(qū)中取一個(gè)產(chǎn)品;

將一個(gè)產(chǎn)品送入緩沖區(qū);v(mutex)；

v(mutex)；v(empty)；

v(full)；消費(fèi)一個(gè)產(chǎn)品；

無(wú)論在生產(chǎn)者進(jìn)程還是在消費(fèi)者進(jìn)程中，P操作的次序都不能顛倒，否則將可能

造成死鎖。

讀者-寫者問(wèn)題

第一讀者-寫者問(wèn)題：要求沒(méi)有讀者需要保持等待除非有一個(gè)寫者已經(jīng)獲得允許

使用共享數(shù)據(jù)

第二讀者-寫者問(wèn)題：一旦寫者就緒，不會(huì)有新讀者開始讀操作

用信號(hào)量解決讀者-寫者問(wèn)題：

目標(biāo)：允許多個(gè)讀進(jìn)程同時(shí)讀此數(shù)據(jù)對(duì)象，

但是一個(gè)寫進(jìn)程不能與其他進(jìn)程(不管是寫進(jìn)程還是讀進(jìn)程)同時(shí)訪問(wèn)此數(shù)據(jù)對(duì)

象

互斥信號(hào)量mutex,初值1,共享變量readcount記錄當(dāng)前讀進(jìn)程數(shù)，初值0,寫

互斥信號(hào)量writer,用于實(shí)現(xiàn)寫進(jìn)程與寫進(jìn)程和讀進(jìn)程的互斥，初值為1

讀者：

p(mutex)；

if(readcount-0)p(writer)；

〃如果沒(méi)有讀者訪問(wèn)，則等待寫者的完成。如果有讀者，則直接訪問(wèn)臨界區(qū)

readcount=readcount+1；

v(mutex)；

讀數(shù)據(jù)集；

p(mutex)；

readcount=readcount-1；

if(readcount==0)v(writer)；//所有人讀完才能寫

v(mutex)；

Mutex用于保護(hù)readcount的互斥訪問(wèn)

哲學(xué)家進(jìn)餐問(wèn)題：

第i個(gè)哲學(xué)家活動(dòng)算法描述：

p(stick[i])；

p(stick[(i+1)%5])；

進(jìn)餐；

v(stick[i])；

v(stick[(i+1)%5])；

思考；

可能會(huì)死鎖

解決方法：至多允許四個(gè)哲學(xué)家同時(shí)進(jìn)餐。

僅當(dāng)左、右兩支筷子均可用時(shí)，才允許拿起筷子進(jìn)餐。

奇數(shù)號(hào)哲學(xué)家先拿左筷子再拿右筷子，偶數(shù)號(hào)哲學(xué)家相反。

睡眠的理發(fā)師問(wèn)題

理發(fā)店里有一位理發(fā)師，一把理發(fā)椅和N把供等候理發(fā)顧客坐的椅子。

如果沒(méi)有顧客，理發(fā)師睡眠，當(dāng)一個(gè)顧客到來(lái)時(shí)叫醒理發(fā)師；

若理發(fā)師正在理發(fā)時(shí)又有顧客來(lái)，那么有空椅子就坐下，否則離開理發(fā)店。

為解決睡眠的理發(fā)師問(wèn)題，應(yīng)使用三個(gè)信號(hào)量：

customers記錄等候理發(fā)的顧客數(shù)(不包括正在理發(fā)的顧客)；初值為0

barbers記錄正在等候顧客的理發(fā)師數(shù)；初值為0

mutex用于互斥。初值為1

變量count記錄等候的顧客數(shù)，它是customers的一份拷貝。之所以使用count

是因?yàn)闊o(wú)法讀取信號(hào)量的當(dāng)前值。

理發(fā)師：

p(customers)；/*是否有等候的顧客*/

p(mutex)；

count=count—1；/*顧客數(shù)減1*/

v(barbers)；/*理發(fā)師開始理發(fā)*/

v(mutex)；

理發(fā)；

顧客：

p(mutex)；

if(count<N)

{count=count+1

v(customers)；

v(mutex)；

p(barbers)；

理發(fā)；}

elsev(mutex)；/*無(wú)空椅子則離開*/

Chapter7死鎖

死鎖：是指多個(gè)進(jìn)程因競(jìng)爭(zhēng)系統(tǒng)資源或相互通信而造成的一種僵局，若無(wú)外力作

用，這些進(jìn)程都將永遠(yuǎn)不能向前推進(jìn)

可剝奪資源：某進(jìn)程獲得這類資源后，該資源可以被其他進(jìn)程或系統(tǒng)剝奪，如

CPU,存儲(chǔ)器

非剝奪資源：系統(tǒng)將這類資源分配給進(jìn)程后，再不能強(qiáng)行收回，只能在進(jìn)程使用

完后主動(dòng)釋放。如打印機(jī)、讀卡器

注：競(jìng)爭(zhēng)可剝奪資源不會(huì)產(chǎn)生死鎖。

永久性資源：可順序重復(fù)使用的資源，如打印機(jī)

消耗性資源：由一個(gè)進(jìn)程產(chǎn)生，被另一個(gè)進(jìn)程使用短暫時(shí)間后便無(wú)用的資源，又

稱為臨時(shí)性資源。如消息

注:競(jìng)爭(zhēng)永久性資源和臨時(shí)性資源都可能產(chǎn)生死鎖

死鎖產(chǎn)生的原因：競(jìng)爭(zhēng)資源，進(jìn)程推進(jìn)順序不當(dāng)

死鎖發(fā)生的條件：互斥，占有并等待，非搶占，循環(huán)等待（等待資源的進(jìn)程間存

在環(huán)）

通過(guò)資源分配圖來(lái)觀察進(jìn)程是否發(fā)生死鎖

如果資源分配圖沒(méi)有環(huán)，系統(tǒng)就沒(méi)有進(jìn)程死鎖。如果分配圖有環(huán)，那可能產(chǎn)生死

鎖

有死鎖的資源分配圖：有環(huán)但沒(méi)有死鎖的資源分配圖

圖中P1占有R2的一個(gè)實(shí)例可知P4釋放資源后就不會(huì)死鎖

P1申請(qǐng)并等待R1的一個(gè)實(shí)例

處理死鎖的基本辦法：忽略思索，預(yù)防死鎖，避免死鎖，檢測(cè)死鎖及解除

避免死鎖：

1.打破占有并等待，要求進(jìn)程在執(zhí)行前一次申請(qǐng)全部的資源，或只有沒(méi)有占有資

源時(shí)才可以分配資源。導(dǎo)致資源利用率低，可能出現(xiàn)饑餓

2.破壞非搶占條件，如果一個(gè)進(jìn)程占有資源并申請(qǐng)另一個(gè)不能立即分配的資源，

那么其現(xiàn)已分配的資源都可被搶占。缺點(diǎn)：實(shí)現(xiàn)復(fù)雜，釋放已獲得資源可能造成

前一段工作的失效，重復(fù)申請(qǐng)和釋放資源會(huì)增加系統(tǒng)開銷，降低系統(tǒng)吞吐量。該

協(xié)議通常應(yīng)用于狀態(tài)可以保存和恢復(fù)的資源，如CPU寄存器、內(nèi)存

3.破壞循環(huán)等待：有序資源分配法;將所有資源按類型排隊(duì)，并賦予不同序號(hào)，

要求進(jìn)程均嚴(yán)格按照序號(hào)遞增的次序請(qǐng)求資源，同類資源一次申請(qǐng)完。能保證沒(méi)

有死鎖

安全狀態(tài)：系統(tǒng)能按某種順序如＜P1、P2…、Pn＞來(lái)為每個(gè)進(jìn)程分配其所需的資

源，直至最大需求，使每個(gè)進(jìn)程都可以順利完成

＜P1＞P2、…、Pn＞為安全序列

銀行家算法：（舉例）

。時(shí)刻的安全性檢查

《銀行家算法例T

NeedO:7,4,3Needl:1,2,2Need2:6,0,0Need3:0,1,1Need4：4,3,1

■假定系統(tǒng)中有5個(gè)進(jìn)程PO、Pl、P2、P3、P4和三種類型的資AllocO：1,1,0Allod：20」Alloc2：3,0,3Alloc3：2,1,1Alloc4:1,0,2

源A、B、C,數(shù)量分別為12、5、9,在TO0寸刻的資源分配情Avail33213420

況如下所示。

w遵情況WorkNeedAllocWDrk+Alloc

進(jìn)屋'Finish

情況MaxAllocationNeedAvailableABCABCABCABC

進(jìn)程、

ABCABcABCABCPl332122201533true

P0853110743332

P3533011211744true

P1323201122

P4744431102846true

P2903303600

P28466003031149true

P3222211011

P011497431101259true

P4533043

121—~A

TO時(shí)刻存在著一個(gè)安全序列＜PkP3、P4、P2、P0＞,故系統(tǒng)是安全的。

資源分配圖簡(jiǎn)化判斷是否死鎖：找出一個(gè)既不阻塞又非孤立的進(jìn)程結(jié)點(diǎn)pi,進(jìn)

程pi獲得了它所需要的全部資源，能運(yùn)行完成然后釋放所有資源。如果能消去

所有邊，則不死鎖

資源搶占來(lái)處理死鎖：逐步從進(jìn)程中搶占資源給其他進(jìn)程使用，直到死鎖環(huán)被打

破為止。

選擇一個(gè)犧牲：最小代價(jià)

回退：返回到安全狀態(tài)，然后重新啟動(dòng)進(jìn)程

饑餓：同一進(jìn)程可能總是被選中

處理死鎖的綜合方法：將系統(tǒng)中的資源按層次分為若干類，對(duì)每一類資源使用最

適合它的辦法解決死鎖問(wèn)題。即使發(fā)生死鎖，一個(gè)死鎖環(huán)也只包含某一層次的資

源，因此整個(gè)系統(tǒng)不會(huì)受控于死鎖。

把資源分為：內(nèi)部資源（有序資源分配法），主存資源（資源剝奪法），作業(yè)資源

（可分配的設(shè)備和文件采用避免方法），交換空間（靜態(tài)分配法）

對(duì)待死鎖，一般應(yīng)考慮死鎖的預(yù)防、避免、檢測(cè)和解除四個(gè)問(wèn)題。典型的銀行家

算法是屬于避免，破壞環(huán)路等待條件是屬于預(yù)防，而剝奪資源是

解除的基本方法

Chapter8內(nèi)存管理

內(nèi)存：即存儲(chǔ)器、主存，分為兩大部分：系統(tǒng)區(qū)，用戶區(qū)

內(nèi)存由很大一組字或字節(jié)組成，每個(gè)字或字節(jié)都有它們自己的地址

存儲(chǔ)器管理的功能

存儲(chǔ)空間的分配和回收

地址變換：將邏輯地址變換成物理地址

存儲(chǔ)保護(hù)：防止因用戶程序錯(cuò)誤破壞系統(tǒng)或其他用戶，防止程序之間的相互干擾

存儲(chǔ)擴(kuò)充：在邏輯上為用戶提供一個(gè)比實(shí)際內(nèi)存更大的存儲(chǔ)空間

CPU能直接訪問(wèn)的存儲(chǔ)器有：主存，高速緩存和寄存器

將程序裝入內(nèi)存有三種方式:絕對(duì)裝入方式（編譯時(shí)產(chǎn)生絕對(duì)地址的代碼無(wú)需地

址變換），可重定位裝入方式（編譯時(shí)產(chǎn)生相對(duì)地址的目標(biāo)代碼），動(dòng)態(tài)運(yùn)行時(shí)裝

入方式（執(zhí)行時(shí)進(jìn)行地址變換）

邏輯地址：由CPU產(chǎn)生的地址。用戶編程時(shí)所用的地址，又稱相對(duì)地址、虛地址

物理地址：內(nèi)存單元所看到的地址。又稱絕對(duì)地址，實(shí)地址

邏輯地址空間：邏輯地址的集合

物理地址空間：物理地址的集合

為了確保每個(gè)進(jìn)程都有獨(dú)立的內(nèi)存空間。

基地址寄存器，界限地址寄存器

300040120900

那么程序可以訪問(wèn)300040-420900的所有地址

內(nèi)存管理單元（MMU,memory-management-unit）:運(yùn)行時(shí)把虛擬地址映射到物

理地址的設(shè)備。在MMU中，用戶進(jìn)程所產(chǎn)生的地址在送交內(nèi)存前都將加上重定位

寄存器的值

地址變換：將邏輯地址轉(zhuǎn)換為物理地址。又稱地址映射、重定位

地址變換分兩類：靜態(tài)地址變換（程序裝入時(shí)一次完成不改變，需要連續(xù)存儲(chǔ)空

間，難共享），動(dòng)態(tài)地址變換（在程序執(zhí)行過(guò)程中，每次訪問(wèn)內(nèi)存之前將要訪問(wèn)

的地址轉(zhuǎn)為內(nèi)存地址，不需連續(xù)空間，可以實(shí)現(xiàn)虛擬存儲(chǔ)）

動(dòng)態(tài)加載：子程序只有調(diào)用時(shí)才被加載。優(yōu)點(diǎn)：不用的子程序不會(huì)被加載

動(dòng)態(tài)鏈接：鏈接被推遲到執(zhí)行時(shí)期

存根：小段代碼用來(lái)定位合適的內(nèi)存駐留庫(kù)程序

程序的鏈接：鏈接程序的功能是將經(jīng)過(guò)編譯或匯編后得到的目標(biāo)模塊以及所需的

庫(kù)函數(shù)裝配成一個(gè)完整的裝入模塊

實(shí)現(xiàn)鏈接的三種方式：靜態(tài)鏈接，裝入時(shí)動(dòng)態(tài)鏈接，運(yùn)行時(shí)動(dòng)態(tài)鏈接

靜態(tài)鏈接：在程序運(yùn)行之前，將各目標(biāo)模塊及其所需的庫(kù)函數(shù)裝配成一個(gè)完整的

裝入模塊

裝入時(shí)動(dòng)態(tài)鏈接：源程序編譯后所得到的目標(biāo)模塊在裝入內(nèi)存時(shí)邊裝入邊鏈接。

運(yùn)行時(shí)動(dòng)態(tài)鏈接：將某些目標(biāo)模塊的鏈接推遲到執(zhí)行時(shí)才進(jìn)行。即在執(zhí)行過(guò)程中，

若發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，由OS去找到該模塊，將它裝入內(nèi)存并

鏈接到調(diào)用者模塊上。

覆蓋技術(shù)：把一個(gè)大程序劃分為一系列覆蓋，每個(gè)覆蓋是一個(gè)相對(duì)獨(dú)立的程序單

位。把程序執(zhí)行時(shí)不要求同時(shí)裝入內(nèi)存的覆蓋組成一組叫覆蓋段。將一個(gè)覆蓋段

分配到同一個(gè)存儲(chǔ)區(qū)中，這個(gè)存儲(chǔ)區(qū)稱為覆蓋區(qū)。覆蓋區(qū)的大小由覆蓋段中最大

的覆蓋確定。

覆蓋技術(shù)主要在早期系統(tǒng)使用，要求專業(yè)的程序員給出覆蓋結(jié)構(gòu)。

交換:進(jìn)程可以暫時(shí)從內(nèi)存中交換到備份存儲(chǔ)上，當(dāng)需要再次執(zhí)行時(shí)再換回內(nèi)存。

（例如低優(yōu)先級(jí)內(nèi)存被換出，這樣高優(yōu)先級(jí)進(jìn)程可以裝入執(zhí)行。這種交換又被稱

為滾出，滾入）

交換空間管理：交換空間設(shè)置在外存交換區(qū)，交換空間管理的主要目標(biāo)是提高交

換速度

交換空間采用連續(xù)分配方式，使用與動(dòng)態(tài)分區(qū)分配類似的數(shù)據(jù)結(jié)構(gòu)和分配算法

交換技術(shù)由操作系統(tǒng)自己完成

連續(xù)內(nèi)存分配

內(nèi)存通常分為兩個(gè)區(qū)域：一個(gè)駐留操作系統(tǒng)，通常位于內(nèi)存低端；一個(gè)駐留用戶

進(jìn)程，通常位于內(nèi)存高端

內(nèi)存保護(hù)：防止一個(gè)進(jìn)程有意無(wú)意的破壞系統(tǒng)或其他進(jìn)程（內(nèi)存訪問(wèn)不能越界）

常用的存儲(chǔ)保護(hù)方法：界限寄存器法，存儲(chǔ)保護(hù)鍵，環(huán)保護(hù)機(jī)制，訪問(wèn)權(quán)限

界限寄存器法：通過(guò)對(duì)每個(gè)進(jìn)程設(shè)置一對(duì)界限寄存器（上下界寄存器或基址限長(zhǎng)

寄存器）來(lái)防止越界訪問(wèn)（如果越界則產(chǎn)生越界中斷），達(dá)到存儲(chǔ)保護(hù)的目的。

存儲(chǔ)保護(hù)鍵：為每個(gè)存儲(chǔ)塊分配一個(gè)保護(hù)鍵，相當(dāng)于一把鎖；進(jìn)入系統(tǒng)的每個(gè)作

業(yè)賦予一個(gè)保護(hù)鍵，相當(dāng)于一把鑰匙。當(dāng)作業(yè)運(yùn)行時(shí)，檢查鑰匙和鎖是否匹配，

若二者匹配，則允許訪問(wèn)。否則發(fā)出保護(hù)性中斷信號(hào)

環(huán)保護(hù)機(jī)制：處理器狀態(tài)分為多個(gè)環(huán)，分別具有不同的存儲(chǔ)訪問(wèn)特權(quán)級(jí)，通常環(huán)

的編號(hào)越小，特權(quán)級(jí)越高。

存取權(quán)限：除上述保護(hù)方案外，還有四種存取權(quán)限：禁止做任何操作，只能執(zhí)行,

只能讀，讀/寫

內(nèi)存分配：

分區(qū)儲(chǔ)存管理分為：固定分區(qū)，動(dòng)態(tài)分區(qū)

分區(qū)分配算法：首次適應(yīng)算法，循環(huán)首次適應(yīng)算法（從上次找到的空閑分區(qū)的下

一個(gè)開始，使存儲(chǔ)空間利用均衡），最佳適應(yīng)算法（分區(qū)按容量遞增的次序排列）,

最壞適應(yīng)算法（分區(qū)按容量大小遞減）

模擬實(shí)驗(yàn)顯示，首次適應(yīng)和最佳適應(yīng)難分伯仲，但是首次適應(yīng)快

內(nèi)部碎片：分配給作業(yè)的存儲(chǔ)空間中未被使用的部分

外部碎片：系統(tǒng)中無(wú)法利用的小存儲(chǔ)塊（因?yàn)樗鼈兲×耍?/p>

解決碎片的方法：拼接/緊縮，要浪費(fèi)很多的處理機(jī)時(shí)間

分頁(yè)：將物理內(nèi)存分為固定大小的塊，稱為幀。將邏輯內(nèi)存也分為同樣大小的塊,

稱為頁(yè)。在為進(jìn)程分配存儲(chǔ)空間時(shí)，總是以塊為單位來(lái)分配，可以將進(jìn)程中的某

一頁(yè)存放到主存的某一空閑塊中。

分頁(yè)沒(méi)有外部碎片，有內(nèi)部碎片

頁(yè)的邏輯地址由頁(yè)號(hào)和頁(yè)內(nèi)位移（pageoffset）組成

頁(yè)的大小一般為512B-8KB

頁(yè)表：記錄頁(yè)面在內(nèi)存中對(duì)應(yīng)物理塊的數(shù)據(jù)結(jié)構(gòu)

分頁(yè)機(jī)制中，每一次的數(shù)據(jù)/指令存取需要兩次內(nèi)存訪問(wèn)（一次頁(yè)表一次數(shù)據(jù)）

TLB（translationlook-asidebuffer）轉(zhuǎn)換后備緩沖區(qū)，即快表，存放當(dāng)前

訪問(wèn)的那些頁(yè)表項(xiàng)

TLB失效：頁(yè)號(hào)不在TLB內(nèi)，則訪問(wèn)頁(yè)表

如果TLB中的條目已滿，則需要替換，替換策略有LRU（最近最少使用），隨即

替換等。有的TLB允許有些條目固定下來(lái)

TLB命中率：一般80%-90%

有效內(nèi)存訪問(wèn)時(shí)間：如果內(nèi)存一次存取時(shí)間是m,TLB訪問(wèn)一次時(shí)間是n,命中

率為P。那么有效內(nèi)存訪問(wèn)時(shí)間=p*（n+m）+（1-p）（2m+n）

存儲(chǔ)保護(hù)

有效-無(wú)效位（valid-invalidbit）:附在頁(yè)表的每個(gè)表項(xiàng)中。當(dāng)該位有效時(shí)，表

示相關(guān)的頁(yè)在進(jìn)程的邏輯地址空間內(nèi)，是合法的。反之不合法

共享頁(yè)：如果代碼是可重入代碼（reentrantcode純代碼）則可以共享（每個(gè)

進(jìn)程可以有自己的數(shù)據(jù)頁(yè)，但可用同一段代碼，訪問(wèn)內(nèi)存的同一塊）

可重入代碼是不能自我修改的代碼，它在執(zhí)行期間不會(huì)改變

分段（segmentation）：（考慮程序的邏輯完整性）一個(gè)程序是一些段的集合，一

個(gè)段是一個(gè)邏輯單位。如一個(gè)程序可分段為：代碼，全局變量，堆，每個(gè)線程的

棧等

每個(gè)分段有自己的名字，由0開始編址并采用一段連續(xù)的地址空間。每段分配一

個(gè)連續(xù)的內(nèi)存區(qū)，但各段之間不要求連續(xù)

段表，類比頁(yè)表

分段不會(huì)產(chǎn)生內(nèi)部碎片

三種不連續(xù)內(nèi)存管理方式是：分頁(yè)存儲(chǔ)管理、分段存儲(chǔ)管理和段頁(yè)式

存儲(chǔ)管理（訪問(wèn)兩次內(nèi)存）。

Chapter9虛擬內(nèi)存

虛擬內(nèi)存技術(shù)：允許執(zhí)行進(jìn)程不必完全在內(nèi)存中。是一種以時(shí)間換空間的技術(shù)

虛擬存儲(chǔ)器的特征：離散型（不連續(xù)內(nèi)存分配），多次性（一個(gè)作業(yè)多次裝入內(nèi)

存），對(duì)換性（允許運(yùn)行中換進(jìn)換出），虛擬性（邏輯上擴(kuò)充內(nèi)存）

按需調(diào)頁(yè)：只有在需要的時(shí)候才調(diào)入一個(gè)頁(yè)（懶惰交換）

頁(yè)錯(cuò)誤：當(dāng)訪問(wèn)無(wú)效頁(yè)時(shí)，會(huì)產(chǎn)生頁(yè)錯(cuò)誤陷阱.分頁(yè)硬件在通過(guò)頁(yè)表轉(zhuǎn)換地址時(shí)，

將發(fā)現(xiàn)已設(shè)置了無(wú)效位，會(huì)陷入操作系統(tǒng)。

缺頁(yè)中斷:缺頁(yè)中斷處理程序根據(jù)該頁(yè)在外存的地址把它調(diào)入內(nèi)存。若內(nèi)存有空

閑空間，則缺頁(yè)中斷處理程序只需把缺頁(yè)裝入并修改頁(yè)表中的相應(yīng)項(xiàng)；若內(nèi)存中

無(wú)空閑物理塊，則需要先淘汰內(nèi)存中的某些頁(yè)，若淘汰頁(yè)曾被修改過(guò)，則還要將

其寫回外存。

有效訪問(wèn)時(shí)間：

內(nèi)存的讀寫周期為t，缺頁(yè)中斷服務(wù)時(shí)間為tl（包含讀入缺頁(yè)、頁(yè)表更新、快表

更新時(shí)間），快表的命中率為a,缺頁(yè)中斷率為f,快表訪問(wèn)時(shí)間為e,則有效

存取時(shí)間可表示為：

EAT=a*（e+t）+（1-a）*［（1-f）*2（e+t）+f*（tl+2（e+t））］（里

面包括了查快表時(shí)間）

頁(yè)面置換（頁(yè)面淘汰）：

為進(jìn)程分配的幀越多，頁(yè)錯(cuò)誤越少

內(nèi)存的引用序列稱為引用串（referencestring）

采用如下引用串討論頁(yè)置換算法：70120304230321201701

（分配3個(gè)可用幀）

先進(jìn)先出置換算法（FIFO）

（會(huì)有15次頁(yè)面錯(cuò)誤）（注：計(jì)算頁(yè)面錯(cuò)誤時(shí)，注意前三個(gè)必產(chǎn)生3個(gè)頁(yè)面錯(cuò)誤）

Belady異常：頁(yè)錯(cuò)誤率可能隨分配的幀數(shù)的增加而增加

最優(yōu)置換（OPT算法/MIN算法）（不會(huì)有belady異常）產(chǎn)生的頁(yè)錯(cuò)誤率最低

置換最長(zhǎng)時(shí)間不會(huì)用到的頁(yè)（看未來(lái)）

難實(shí)現(xiàn)

LRU頁(yè)置換最近最少使用算法?？梢援嫍？磿?huì)有多少頁(yè)面錯(cuò)誤

近似LRU算法：附加引用位算法（被使用過(guò)就標(biāo)記1并添置高位（前八位）舍棄

最后一位），二次機(jī)會(huì)算法，增強(qiáng)型二次機(jī)會(huì)算法

基于計(jì)數(shù)的頁(yè)面置換：最不經(jīng)常使用算法（LFU）,最常使用頁(yè)置換算法（MFU）

頁(yè)面緩沖算法：頁(yè)面緩沖算法是FIFO算法的發(fā)展。它在系統(tǒng)中保存一個(gè)空閑幀

緩沖池。

頁(yè)面緩沖置換算法采用FIFO選擇被置換頁(yè)面，選擇出的頁(yè)面不是立即換出，而

是放入空閑幀池。

幀分配

幀的最小數(shù)量：分配的幀要大于最少數(shù)量（不然產(chǎn)生太多的頁(yè)面錯(cuò)誤）

分配算法：平均分配，比例分配（根據(jù)進(jìn)程大小，將可用的幀分給每個(gè)進(jìn)程），

按優(yōu)先級(jí)分配

全局分配與局部分配

固定分配和可變分配

將分配策略和置換范圍組合可得如下三種策略：

固定分配局部置換

可變分配全局置換

可變分配局部置換

顛簸/抖動(dòng)：頻繁的頁(yè)調(diào)度行為而幾乎不能完成任何有效的工作。如果一個(gè)進(jìn)程

在換頁(yè)上用的時(shí)間多于執(zhí)行的時(shí)間，那么這個(gè)進(jìn)程就在顛簸。

Chapter10文件系統(tǒng)接口

文件系統(tǒng)：操作系統(tǒng)中與管理文件有關(guān)的軟件和數(shù)據(jù)的集合。

文件系統(tǒng)負(fù)責(zé)管理外存上的文件，并為用戶提供對(duì)文件進(jìn)行存取、共享及保護(hù)的

手段。

文件是具有文件名的一組相關(guān)信息的集合，文件存放在外存上的。

文件由若干記錄組成。

記錄是一些相關(guān)數(shù)據(jù)項(xiàng)的集合。

數(shù)據(jù)項(xiàng)是數(shù)據(jù)組織中可以命名的最小邏輯單位。

文件屬性包含：名稱，標(biāo)識(shí)符，類型，位置，大小，保護(hù)，時(shí)間日期和用戶標(biāo)識(shí)

所有的文件的屬性信息都保存在目錄結(jié)構(gòu)中

通常目錄項(xiàng)包含文件名及標(biāo)識(shí)號(hào)，而標(biāo)識(shí)號(hào)定位文件其他屬性信息。

文件操作：建立，刪除，讀，寫，打開，關(guān)閉（文件的操作除了正常的訪問(wèn)之外,

還要包括對(duì)目錄項(xiàng)的操作）

在文件內(nèi)重定位：搜索相應(yīng)的目錄表項(xiàng)，設(shè)置當(dāng)前文件指針給定值

文件類型：實(shí)現(xiàn)文件類型的常用技術(shù)是在文件名稱內(nèi)包含類型：如名稱.擴(kuò)展名

文件分類方法

按用途分類：系統(tǒng)文件（系統(tǒng)軟件構(gòu)成的文件），庫(kù)文件（系統(tǒng)提供給用戶使用

的各種標(biāo)準(zhǔn)過(guò)程、函數(shù)和應(yīng)用程序），用戶文件（用戶委托文件系統(tǒng)保存的文件）

按保護(hù)級(jí)別分類：只讀文件，讀寫文件，執(zhí)行文件（允許核準(zhǔn)用戶調(diào)用執(zhí)行，但

不允許讀寫），不保護(hù)文件（不加任何訪問(wèn)限制）

按信息流向分類：輸入文件（來(lái)自輸入設(shè)備的文件），輸出文件，輸入輸出文件

（如磁盤上的文件，可以讀也可以寫）

按數(shù)據(jù)形式分類：源文件（由源程序和數(shù)據(jù)構(gòu)成的文件），目標(biāo)文件（源程序經(jīng)

過(guò)編譯但未鏈接成可執(zhí)行代碼的目標(biāo)代碼文件），可執(zhí)行文件（鏈接過(guò)的可運(yùn)行

文件）

文件結(jié)構(gòu)：

邏輯結(jié)構(gòu)：又稱文件組織，是從用戶觀點(diǎn)出發(fā)所看到的文件組織形式。

物理結(jié)構(gòu)：又稱文件的存儲(chǔ)結(jié)構(gòu)，是文件在外存上的存儲(chǔ)組織形式。

文件的邏輯結(jié)構(gòu)：記錄式文件（有結(jié)構(gòu)文件），流式文件（無(wú)結(jié)構(gòu)文件，由字符

序列構(gòu)成）

記錄式文件的組織方式：順序文件（順序排列，記錄通常是定長(zhǎng)的），索引文件

（有索引表），索引順序文件（分組順序排列，索引）

文件的物理結(jié)構(gòu)：順序結(jié)構(gòu)（連續(xù)），鏈接結(jié)構(gòu)（指針），索引結(jié)構(gòu)（索引表）

文件存取方法：順序存取法（按照文件中記錄的順序依次訪問(wèn)），直接存取法（任

意順序快速讀寫），按鍵存取法

目錄：用來(lái)組織文件。目錄可看作符號(hào)表，它能將文件名稱轉(zhuǎn)換成目錄項(xiàng)。

存儲(chǔ)結(jié)構(gòu)：每個(gè)磁盤分區(qū)可以創(chuàng)建一個(gè)文件系統(tǒng)。這些分區(qū)可以組合成更大的結(jié)

構(gòu)-卷。卷可以看成虛擬磁盤。

文件由文件說(shuō)明和文件體兩部分組成。

文件控制塊：即文件說(shuō)明是保存文件屬性信息的數(shù)據(jù)結(jié)構(gòu)。包含，文件名，文件

類型，文件結(jié)構(gòu)，文件物理位置，存取控制信息，管理信息

文件目錄與目錄文件：

目錄：文件控制塊的集合。即文件控制塊是一個(gè)目錄項(xiàng)。

目錄文件：文件的內(nèi)容為目錄信息。

目錄的功能：

實(shí)現(xiàn)“按名存取”：用戶只需提供文件名就可以對(duì)文件進(jìn)行操作。這是目錄管理

的最基本功能。

提高檢索速度

允許文件同名：不同目錄下的文件可以使用相同名字。

允許文件共享

目錄結(jié)構(gòu)：

單級(jí)目錄結(jié)構(gòu)（所有文件被包含在一張目錄表，每個(gè)文件占一個(gè)表目）

二級(jí)目錄結(jié)構(gòu)（將文件目錄分為，主文件目錄（記錄用戶名以及用戶文件目錄的

位置），用戶文件目錄）

多級(jí)目錄結(jié)構(gòu)（又稱樹形目錄結(jié)構(gòu)，在多級(jí)目錄結(jié)構(gòu)中，第一級(jí)目錄稱為根目錄

（樹根），目錄樹中的非葉節(jié)點(diǎn)均為目錄文件（又稱子目錄），葉結(jié)點(diǎn)為文件。）

圖形目錄結(jié)構(gòu)（無(wú)環(huán)圖目錄，允許目錄含有共享子目錄和文件。通用圖目錄）

路徑名：是一個(gè)字符串，該字符串由從根目錄出發(fā)到所找文件的通路上所有各級(jí)

子目錄名和該文件名用分隔符連接起來(lái)構(gòu)成

從根目錄出發(fā)的路徑稱為絕對(duì)路徑（absolutepathname）0

相對(duì)路徑（relativepathname）：由從當(dāng)前目錄出發(fā)到所找文件的通路上的所

有目錄名與數(shù)據(jù)文件名用分隔符連接起來(lái)而形成。

有兩個(gè)特殊目錄：

“表示給定目錄的父目錄

”.表示當(dāng)前目錄

文件共享：是指不同用戶可以共同使用某文件。

共享語(yǔ)義：是文件系統(tǒng)對(duì)共享文件或目錄沖突訪問(wèn)的處理方法。不同共享語(yǔ)義定

義了對(duì)緩存一致性問(wèn)題的不同解決方案。

一致性語(yǔ)義：描述多用戶同時(shí)訪問(wèn)共享文件時(shí)的語(yǔ)義。這些語(yǔ)義規(guī)定了一個(gè)用

戶所修改的數(shù)據(jù)何時(shí)對(duì)另一個(gè)用戶可見(jiàn)

UNIX語(yǔ)義：一個(gè)用戶對(duì)已經(jīng)打開的文件進(jìn)行寫操作，可以被同時(shí)打開同一文件

的其他用戶所見(jiàn)

會(huì)話語(yǔ)義（AFS語(yǔ)義）：一個(gè)用戶對(duì)打開文件的寫不能立即被同時(shí)打開同一文件

的其他用戶所見(jiàn)。

不可修改共享文件語(yǔ)義：一旦一個(gè)文件被其創(chuàng)建者聲明為共享，它就不能被修改。

（文件名和內(nèi)容都不能被修改）

文件系統(tǒng)的早期實(shí)現(xiàn)：繞道法（繞到共享文件上方的目錄），鏈接法（將一個(gè)目

錄中的鏈指針直接指向被共享文件所在的目錄），基本文件目錄表

Chapter11文件系統(tǒng)的實(shí)現(xiàn)

分層文件系統(tǒng)

文件系統(tǒng)按層組織：I/O控制層，基本文件系統(tǒng)層，文件組織模塊層，邏輯文件

系統(tǒng)層

I/O控制層：由驅(qū)動(dòng)程序和中斷處理程序組成，實(shí)現(xiàn)內(nèi)存與磁盤之間的信息傳輸。

基本文件系統(tǒng)層：向合適的設(shè)備驅(qū)動(dòng)程序發(fā)送一般命令就可對(duì)磁盤上的物理塊進(jìn)

行讀寫

文件組織模塊層：將邏輯塊轉(zhuǎn)換為物理塊，空閑空間管理器

邏輯文件系統(tǒng)層：管理元數(shù)據(jù)信息，管理目錄結(jié)構(gòu)，通過(guò)文件控制塊來(lái)維護(hù)文件

結(jié)構(gòu)。

用于文件系統(tǒng)管理的內(nèi)存信息：

內(nèi)存安裝表：