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

Chapter1:導(dǎo)論

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

戶

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

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

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

核）

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

硬件和軟件資源。

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

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

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

統(tǒng)

批處理系統(tǒng)：單道批處理系統(tǒng)，多道批處理系統(tǒng)

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

串行。

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

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

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

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

高）

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

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

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

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

操作系統(tǒng)的4個基本特征：并發(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)用與過程調(diào)用的區(qū)別：系統(tǒng)調(diào)用在核心態(tài)下運(yùn)行,子程序在用戶態(tài)下運(yùn)行;

系統(tǒng)調(diào)用通過中斷機(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：以最小的空間提供最多的功能。不劃分模塊，其接口和功能層次沒有

劃分清楚

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

互相提供服務(wù)。

Chapter3進(jìn)程

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

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

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

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

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

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

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

變量的改變什么的)

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

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

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

考慮下面是條語句：

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ā)語句描述：cobegin.….coend

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

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

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

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

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

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

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

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

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

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

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

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

通過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ì)列

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

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

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

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

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

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

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

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

次之間的對話的語言稱為原語）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

間通信

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

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

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

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

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

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

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

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

那么

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

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

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

Chapter4線程

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

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

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

更好的并發(fā)性

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

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

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

器、寄存器集和棧）。但它可以與同屬一個進(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)建撤銷切換時間短，共享內(nèi)存和

資源線程間通信方便

多線程模型

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

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

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

工作的線程。

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

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

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

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

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

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

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

一占八、、

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

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

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

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

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

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

多線程問題：

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

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

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

開銷四個方面說。

ChaptersCPU調(diào)度

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

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

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

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

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

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

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

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

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

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

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

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

作業(yè)：是用戶在一次解題或一個事務(wù)處理過程中要求計(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)通過JCB感知作業(yè)的存在，JCB是

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

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

多道程序的設(shè)計(jì)目標(biāo)在于任何時候都有某些進(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)，時間片

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

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

成為調(diào)度時間

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

CPU利用率

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

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

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

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

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

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

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

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

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

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

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

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

可能有饑餓

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

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

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

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

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

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

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

時間片大?。禾螅和嘶癁镕CFS太小：調(diào)度頻繁系統(tǒng)開銷大?，F(xiàn)代操作系統(tǒng)的

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

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

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

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

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

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

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

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

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

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

間。

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

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

I

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

4,要求運(yùn)行時間依次為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。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

既考慮作業(yè)等待時間，又考慮作業(yè)執(zhí)行時間的調(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ū)問題：每個進(jìn)程有一個訪問共享數(shù)據(jù)的代碼段，稱為臨界區(qū)（critical

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

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

享變量

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

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

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

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

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

是有限的）

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

進(jìn)程不能進(jìn)入自己的臨界區(qū)時，應(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ū)代碼時，禁止中斷（很多缺點(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)；

??

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

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

wait()和signaI()來訪問。

wait(S)signaI(S):

{whileS0dono-op;{S++;

S—;}

Wait是原來的P操作

Signal是原來的V操作

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

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

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

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

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

稱為signal操作)改變。

wait(semaphore*s)

{s_>vaIue—;

if(s->vaIue<0)

{addthisprocesstos->list;

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

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

bIock();

1}

signaI(semaphre*s)

{s->vaIue++;

if(s->vaIue<=0)

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

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

{removeaprocessPfroms->list;

wakeup(P);

1

)

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

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

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

P,V操作類似

P,V操作是原語

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

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

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

卜解法工

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

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

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

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

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

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

V操作完成這六個其初值均為0。這

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

描述如下：

P2()

解法2

P(a)；

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

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

v(d);

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

步描述如下：

3

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

P2()

{

犬仕)；

執(zhí)行P2的代碼;

v(f2);

V(⑵；

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

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

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

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

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

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

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

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

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

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

mutex是確保對緩沖區(qū)的訪問互斥的信號量，初值為1

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

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

p(empty)；p(mutex)；

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

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

v(mutex)；v(empty)；

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

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

造成死鎖。

讀者-寫者問題

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

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

第二讀者-寫者問題：一旦寫者就緒，不會有新讀者開始讀操作

用信號量解決讀者-寫者問題：

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

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

象

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

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

讀者：

p(mutex)；

if(readcount-0)p(writer)；

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

readcount=readcount+1；

v(mutex)；

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

p(mutex)；

readcount=readcount-1；

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

v(mutex)；

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

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

第i個哲學(xué)家活動算法描述：

p(stick[i])；

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

進(jìn)餐；

v(stick[i])；

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

思考；

可能會死鎖

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

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

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

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

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

如果沒有顧客，理發(fā)師睡眠，當(dāng)一個顧客到來時叫醒理發(fā)師；

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

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

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

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

mutex用于互斥。初值為1

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

是因?yàn)闊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)；/*無空椅子則離開*/

Chapter7死鎖

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

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

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

CPU,存儲器

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

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

注：競爭可剝奪資源不會產(chǎn)生死鎖。

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

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

稱為臨時性資源。如消息

注:競爭永久性資源和臨時性資源都可能產(chǎn)生死鎖

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

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

在環(huán)）

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

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

鎖

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

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

P1申請并等待R1的一個實(shí)例

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

避免死鎖：

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

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

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

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

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

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

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

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

有死鎖

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

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

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

銀行家算法：（舉例）

。時刻的安全性檢查

《銀行家算法例T

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

■假定系統(tǒng)中有5個進(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時刻存在著一個安全序列＜PkP3、P4、P2、P0＞,故系統(tǒng)是安全的。

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

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

所有邊，則不死鎖

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

破為止。

選擇一個犧牲：最小代價

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

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

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

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

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

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

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

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

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

解除的基本方法

Chapter8內(nèi)存管理

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

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

存儲器管理的功能

存儲空間的分配和回收

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

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

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

CPU能直接訪問的存儲器有：主存，高速緩存和寄存器

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

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

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

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

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

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

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

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

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

300040120900

那么程序可以訪問300040-420900的所有地址

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

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

寄存器的值

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

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

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

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

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

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

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

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

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

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

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

裝入模塊

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

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

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

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

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

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

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

的覆蓋確定。

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

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

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

為滾出，滾入）

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

換速度

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

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

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

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

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

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

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

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

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

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

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

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

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

的編號越小，特權(quán)級越高。

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

只能讀，讀/寫

內(nèi)存分配：

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

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

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

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

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

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

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

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

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

稱為頁。在為進(jìn)程分配存儲空間時，總是以塊為單位來分配，可以將進(jìn)程中的某

一頁存放到主存的某一空閑塊中。

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

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

頁的大小一般為512B-8KB

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

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

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

訪問的那些頁表項(xiàng)

TLB失效：頁號不在TLB內(nèi)，則訪問頁表

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

替換等。有的TLB允許有些條目固定下來

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

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

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

存儲保護(hù)

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

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

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

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

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

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

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

棧等

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

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

段表，類比頁表

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

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

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

Chapter9虛擬內(nèi)存

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

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

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

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

頁錯誤：當(dāng)訪問無效頁時，會產(chǎn)生頁錯誤陷阱.分頁硬件在通過頁表轉(zhuǎn)換地址時，

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

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

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

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

其寫回外存。

有效訪問時間：

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

更新時間），快表的命中率為a,缺頁中斷率為f,快表訪問時間為e,則有效

存取時間可表示為：

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

面包括了查快表時間）

頁面置換（頁面淘汰）：

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

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

采用如下引用串討論頁置換算法：70120304230321201701

（分配3個可用幀）

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

（會有15次頁面錯誤）（注：計(jì)算頁面錯誤時，注意前三個必產(chǎn)生3個頁面錯誤）

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

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

置換最長時間不會用到的頁（看未來）

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

LRU頁置換最近最少使用算法?？梢援嫍？磿卸嗌夙撁驽e誤

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

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

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

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

緩沖池。

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

是放入空閑幀池。

幀分配

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

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

按優(yōu)先級分配

全局分配與局部分配

固定分配和可變分配

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

固定分配局部置換

可變分配全局置換

可變分配局部置換

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

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

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

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

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

手段。

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

文件由若干記錄組成。

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

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

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

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

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

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

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

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

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

文件分類方法

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

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

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

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

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

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

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

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

文件）

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

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

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

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

序列構(gòu)成）

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

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

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

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

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

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

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

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

文件由文件說明和文件體兩部分組成。

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

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

文件目錄與目錄文件：

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

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

目錄的功能：

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

的最基本功能。

提高檢索速度

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

允許文件共享

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

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

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

位置），用戶文件目錄）

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

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

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

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

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

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

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

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

有兩個特殊目錄：

“表示給定目錄的父目錄

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

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

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

義了對緩存一致性問題的不同解決方案。

一致性語義：描述多用戶同時訪問共享文件時的語義。這些語義規(guī)定了一個用

戶所修改的數(shù)據(jù)何時對另一個用戶可見

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

的其他用戶所見

會話語義（AFS語義）：一個用戶對打開文件的寫不能立即被同時打開同一文件

的其他用戶所見。

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

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

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

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

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

分層文件系統(tǒng)

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

系統(tǒng)層

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

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

行讀寫

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

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

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

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

內(nèi)存安裝表：