計算機操作系統(tǒng)原理

李國

2007.12.3

基本授課內(nèi)容

?一、操作系統(tǒng)引論

?二、進程管理

?三、處理機調度與死鎖

?四、存儲器管理

?五、設備管理

?六、文件管理

?七、操作系統(tǒng)接口

第一章操作系統(tǒng)引論

1.1操作系統(tǒng)的目標和作用

1.2操作系統(tǒng)的發(fā)展過程

1.3操作系統(tǒng)的基本特性

1.4操作系統(tǒng)的主要功能

1.5操作系統(tǒng)的結構設計

1.1操作系統(tǒng)的目標和作用

一、操作系統(tǒng)的目標

方便性

有效性

可擴充性

開放性

.、操作系統(tǒng)的作用

1、作為用戶與計算機硬件系統(tǒng)之間的接口。

應用軟件

操作系統(tǒng)

系統(tǒng)工具開發(fā)人員

操作系統(tǒng)

計算機硬件

2、作為計算機系統(tǒng)資源的管理者

主要包括四類資源：處理機、存儲器、I/O設

備以及信息（數(shù)據(jù)與程序）。

3、操作系統(tǒng)用作擴充機器

虛擬機：在裸機的基礎上，每增加一層新的

操作系統(tǒng)的軟件，就變成了功能更為強大

的虛擬機或虛機器。

、推動操作系統(tǒng)發(fā)展的主要動力

1、不斷提高計算機資源利用率

2、方便用戶

3、器件的不斷更新?lián)Q代

4、計算機體系結構的不斷發(fā)展。

1.2操作系統(tǒng)的發(fā)展過程

一、無操作系統(tǒng)的計算機系統(tǒng)

1、人工操作方式（1946~50年代，電子管時代）

?【特點】：計算機資源昂貴，沒有操作系統(tǒng)

?【工作方式】：

-用戶：用戶既是程序員、操作員，還是計算機專業(yè)人員；

-編程語言：為機器語言；

-輸入輸出：紙帶或卡片；

?【計算機的工作特點】：

-用戶獨占全機：用戶獨占計算機所有資源，資源利用率低；

-CPU等待用戶：計算前，手工裝入紙帶或卡片；計算完成后，手工

卸取紙帶或卡片；CPU利用率低；

?【主要矛盾】：

-計算機處理能力的提高，手工操作的低效率

-用戶獨占全機的所有資源；

2、脫機輸入/輸出方式

引入外圍機控制數(shù)據(jù)的提前錄入和延后輸

出，具體參照P5圖1-2

二、單道批處理系統(tǒng)

1、單道批處理系統(tǒng)的處理過程

引入監(jiān)督程序，成批的作業(yè)首先在外存排隊等待，

由監(jiān)督程序負責將每一個作業(yè)裝入內(nèi)存，處理完

成后，再掉調入下一個作業(yè)，直至運行完畢。

2、單道批處理系統(tǒng)的特征

自動性

順序性

單道性

三、多道批處理系統(tǒng)

1、多道程序設計的基本概念

用戶提交的作業(yè)都先存放在外存的后備隊列中，由

作業(yè)調度程序按一定的算法選擇若干作業(yè)調入內(nèi)

存，共享CPU和系統(tǒng)的各種資源。

2、多道批處理的特征

（1）多道性：在內(nèi)存中有多個程序（嚴格而言為進

程）同時執(zhí)行（宏觀上）；

（2）無序性：進入內(nèi)存的順序與執(zhí)行完的順序無關

（3）調度性：經(jīng)過2次調度，先調度到內(nèi)存，轉換

為進程后，進行進程調度，要CPU進行執(zhí)行。

3、多道批處理系統(tǒng)的優(yōu)缺點：

(1)資源利用率高了；

(2)系統(tǒng)吞吐量大了；

(3)平均周轉時間長；

(4)無交互能力。

4、多道批處理系統(tǒng)需要解決的問題

(1)處理機管理問題

(2)內(nèi)存管理問題

(3)I/O設備管理問題

(4)文件管理問題

(5)作業(yè)管理問題

處理上述問題組成一系列程序的集合，由此

構成了完整意義上的操作系統(tǒng)。

操作系統(tǒng)的定義：操作系統(tǒng)是一組控制和管

理計算機硬件和軟件資源，合理的組織計

算機工作流程以及方便用戶使用的程序的

集合。

四、分時系統(tǒng)

1、定義：在一臺主機上連接了多個帶有顯示

器和鍵盤的終端，同時允許多個用戶通過

自己的終端，以交互方式使用計算機，共

享主機中的資源。

2、分時系統(tǒng)實現(xiàn)的關鍵問題

(1)及時接收：多路卡

(2)及時處理：分時間片的原則。

為此：(1)用戶作業(yè)可以直接進入內(nèi)存

(2)時間片選擇大小要適當。

3、分時系統(tǒng)的特征：

(1)多路性

(2)獨立性

(3)及時性

(4)交互性

五、實時系統(tǒng)

1、理解：系統(tǒng)能及時響應外部事件的請求，在規(guī)定

的時間內(nèi)完成對該事件的處理，并控制所有實時

任務協(xié)調一致的運行。

2、實時系統(tǒng)的應用領域：

要求與被控制的變化速度相比，其反應速

度足夠快；工作安全可；需要人工干預時，操作簡便。

N口生產(chǎn)過彳呈控制，宇航自劫控制等。

要求計算機能夠在容許的延遲時

間內(nèi)，相應外部的事件請求，完成對該事件的處理，

并控制所有的實時設備和實時任務協(xié)調運行。如飛機

訂票系統(tǒng),期貨、股票交易系統(tǒng)等。

3、實時系統(tǒng)與分時系統(tǒng)的比較

(1)多路性

(2)獨立性

(3)及時性

(4)交互性

(5)高可靠性

1.3操作系統(tǒng)的基本特性

一、并發(fā)性(concurrency)

多個事件在同一時間段內(nèi)發(fā)生。操作系統(tǒng)是

一個并發(fā)系統(tǒng)，各進程間的并發(fā)，系統(tǒng)與應用間

的并發(fā)。操作系統(tǒng)要完成這些并發(fā)過程的管理。

并行(parallel)是指在同一時刻發(fā)生。

-在多道程序處理時，宏觀上并發(fā)，微觀上交替

執(zhí)行(在單處理器情況下)。

-程序的靜態(tài)實體是可執(zhí)行文件，而動態(tài)實體是

進程(或稱作任務)，并發(fā)指的是進程。

「共享性（sharing）

多個進程共享有限的計算機系統(tǒng)資源。操作系

統(tǒng)要對系統(tǒng)資源進行合理分配和使用。資源在一

個時間段內(nèi)交替被多個進程所用。

-互斥共享方式（如音頻設備），資源分配后到

釋放前，不能被其他進程所用。

-同時訪問方式，（如可重入代碼，磁盤文件）

-資源分配難以達到最優(yōu)化

.、虛擬性（virtual）

一個物理實體映射為若干個對應的邏輯實體

（分時或分空間）。虛擬是操作系統(tǒng)管理系統(tǒng)資源

的重要手段，可提高資源利用率。

-CPU--每個用戶（進程）的“虛處理機”。

-存儲器——每個進程都占有的地址空間（指令

+數(shù)據(jù)+堆棧）O

-顯示設備——多窗口或虛擬終端

如虛擬光驅。

四、異步性(asynchronism)

異步性也稱不確定性，指進程的執(zhí)行順序和

執(zhí)行時間及執(zhí)行結果的不確定性：

-程序執(zhí)行結果不確定，不可再現(xiàn)。相同輸入與

環(huán)境下多次運行結果不同。

-多道程序設計環(huán)境下，程序按異步方式運行。

多個進程并發(fā)執(zhí)行，“時走時?！?，不可預知

每個進程的運行推進快慢，引發(fā)執(zhí)行順序與時

間的不確定。

14操作系統(tǒng)的主要功能

、處理機管理功能：

可歸結為進程管理，包括以下方面

-進程控制：進程的創(chuàng)建和撤消、進程狀態(tài)的轉

換等；

-進程同步：協(xié)調進程執(zhí)行的順序關系；

-進程通信；

-調度：作業(yè)調度和進程調度兩層。。

二、存儲器管理功能：

1、內(nèi)存分配

2、內(nèi)存保護

3、地址映射

4、內(nèi)存擴充

三、設備管理功能：

1、設備分配

2、設備處理（相當于啟動）

3、緩沖管理

4、虛擬設備

四、文件管理功能：

1、文件存儲空間管理

2、目錄管理

3、文件讀寫管理

4、文件保護。

五、用戶接口：

1、命令接口

2、程序接口

3、圖形接口

1.5操作系統(tǒng)的結構設計

一、傳統(tǒng)的操作系統(tǒng)結構

1、無結構操作系統(tǒng)

操作系統(tǒng)是由一組過程的集合，各過程之間相互調用,

在操作系統(tǒng)內(nèi)部不存在任何結構，也因此稱為整體

系統(tǒng)結構

2、模塊化操作系統(tǒng)結構

操作系統(tǒng)是由按其功能劃分為若干個具有一定獨立性

和大小的模塊。每個模塊具有某個方面的管理功能,

規(guī)定好模塊之間的接口。

3、分層式操作系統(tǒng)結構

從物理機器開始，在上面不斷添加新的層次

軟件，實現(xiàn)若干功能，構成滿足需要的操

作系統(tǒng)。

二、微內(nèi)核操作系統(tǒng)

1、微內(nèi)核是20世紀90年代發(fā)展的現(xiàn)代操作系

統(tǒng)內(nèi)核結構，典型的操作系統(tǒng)如

WindowsNTo實現(xiàn)了以微內(nèi)核為操作系統(tǒng)

核心，以客戶/服務器為基礎，并且采取了

面向對象的程序設計方法的新型體系結構。

2、客戶/服務器模式

操作系統(tǒng)劃分為兩部分：一部分用于提供各種服務

的一組服務器，如進程服務器、存儲器服務器等,

運行在用戶態(tài)；另一部分是內(nèi)核，用于處理客戶

和服務器之間的通信。CPU執(zhí)行內(nèi)核程序運行在

核心態(tài)。

3、微內(nèi)核技術：

(1)定義：精心設計的，能實現(xiàn)現(xiàn)代操作系統(tǒng)核心

功能的小型內(nèi)核，與一般操作系統(tǒng)不同，更小更

精練，運行在核心態(tài)，開機長駐內(nèi)存，并非一個

完整的操作系統(tǒng)，是構建通用操作系統(tǒng)的重要基

礎。

(2)微內(nèi)核的基本功能

-進程管理

-存儲器管理

-進程通信管理

-I/O設備管理

第二章進程管理

2.1進程的基本概念

一、程序的順序執(zhí)行及特征

1、參照課本P27圖2-1

2、特征：

順序性

封閉性

可再現(xiàn)性

二、程序的并發(fā)執(zhí)行及其特征

1、前趨圖：利用有向無環(huán)圖中結點描述進程

有向弧描述進程執(zhí)行順序。

2、并發(fā)執(zhí)行的特征

間斷性L",‘

失去并發(fā)性I

不可再現(xiàn)性G.：Gq

Plp2P3P4

三、進程的特征與狀態(tài)

1、進程的特征

(1)結構特征：進程實體主要包括程序段、

數(shù)據(jù)段和進程控制塊三部分。

(2)動態(tài)性是進程最基本的特征，表現(xiàn)在進

程的創(chuàng)建、狀態(tài)的轉換、撤消等進程是有

生命周期的，程序本身是靜態(tài)的。

(3)并發(fā)性，所謂前面提到程序的并發(fā)實質

上是進程的并發(fā)

(4)獨立性：CPU進行調度的獨立單位以及進行

資源分配的基本單位

(5)異步性，推進順序是異步的。

2、進程的定義：

(1)進程是程序的一次執(zhí)行。

(2)進程是一個程序及其數(shù)據(jù)在處理機上順序執(zhí)行

時所發(fā)生的活動。

(3)進程是一個數(shù)據(jù)集合上運行的過程，是系統(tǒng)進

行資源分配和調度的一個獨立單位。

進程是進程實體的運行過程，是系統(tǒng)進行資源分配

和調度的一個獨立單位。

3、進程的三種基本狀態(tài)

(1)就緒狀態(tài)：當進程剛剛建立后處于就緒狀態(tài)，

具備所有資源，只差CPU調度就可執(zhí)行，一個系

統(tǒng)中處于就緒狀態(tài)的進程有多個，構成就緒隊列。

(2)執(zhí)行狀態(tài)：獲得CPU,進行執(zhí)行，在單處理

機內(nèi)只有1個執(zhí)行狀態(tài)進程；

(3)阻塞狀態(tài)：處于執(zhí)行狀態(tài)的進程因為發(fā)生某事

件而暫時無法繼續(xù)執(zhí)行，如等待I/O,申請緩沖區(qū)

等，可以根據(jù)不同的阻塞原因放到不同的阻塞隊

列中，從而構成阻塞隊列。

四、進程控制塊

1、進程控制塊的作用

進程控制塊（PCB）是為了描述和控制進程的運行

為進程定義的數(shù)據(jù)結構，屬于進程實體的一部分

是操作系統(tǒng)中最重要的記錄型數(shù)據(jù)結構，記錄了

操作系統(tǒng)所需要的、用于描述進程當前情況及控

制進程運行的全部信息，操作系統(tǒng)通過PCB來對

并發(fā)執(zhí)行的進程來進行控制和管理的。

進程存在的唯一標志是PCB。

2、進程控制塊的基本組成

(1)進程標識符：

a,內(nèi)部標識符就是PCB區(qū)中的標號，是數(shù)字。

b.外部標識符就是進程的實際名字

(2)處理機的狀態(tài)，中斷時處理狀態(tài)的保護，

斷點地址保護

(3)進程調度所需信息(如進程狀態(tài)、優(yōu)先級、

進程等待時間及阻塞原因等

(4)進程控制信息：如程序段和數(shù)據(jù)段的地址、

資源清單、進程同步與通信機制、進程隊列中

各進程的鏈接指針。

3、PCB的組織方式:

(1)鏈接方式

(2)索引方式

22進程控缶U

一、進程控制中心：操作系統(tǒng)內(nèi)核通過原語操作實

現(xiàn)。

1、內(nèi)核是基于硬件的第一層軟件擴充，并長駐內(nèi)存

它為系統(tǒng)對進程和資源進行控制和管理，提供了

良好的環(huán)境。內(nèi)核通常包括中斷處理、時鐘管理、

進程控制、進程通信和調度原語，以及資源管理

中的基本操作等。

2、所謂原語，是由若干條機器指令構成，用以完成

特定功能的一段程序，為了保證其操作的正確性,

它應該是原子操作，即原語是一個不可分割的操

作。

、基本進程控制原語

1、進程創(chuàng)建原語

(1)申請空白PCB

(2)為新進程分配資源。

(3)初始化進程控制塊

(4)將新進程插入到就緒隊列。

2、進程終止原語

(1)根據(jù)標識符，從PCB集合中檢索出該進

程的PCB,讀出進程狀態(tài)。

(2)若被終止進程屬執(zhí)行狀態(tài)，需要重新調

度新進程執(zhí)行。

(3)該進程所有子孫進程一并終止。

(4)被終止進程的全部資源都被釋放。

3、進程阻塞原語block。

(1)將阻塞進程由執(zhí)行狀態(tài)變?yōu)樽枞麪顟B(tài),

并加入到阻塞隊列中

(2)系統(tǒng)重新調度新進程進行執(zhí)行。

4、進程喚醒原語wakeup。

將被喚醒進程狀態(tài)由阻塞變換為就緒狀態(tài),

從阻塞隊列中刪除，加入到就緒隊列中。

2.3進程同步

一、進程同步的基本概念

1、兩種形式的制約關系

(1)間接相互制約關系：因為臨界資源的特

性造成進程間的制約。

(2)直接相互制約關系：進程之間相互協(xié)作

互相制約關系。

2、臨界資源：如打印機、磁帶機等一段時間

內(nèi)只允許一個進程進行使用的資源。

3、臨界區(qū)：

每個進程中訪問臨界資源的那段代碼成為臨

界區(qū)。整個程序段分為：進入?yún)^(qū)、臨界區(qū)

退出區(qū)以及剩余區(qū)。

4、同步機制應遵循的規(guī)則：

(1)空閑讓進

(2)忙則等待

(3)有限等待

(4)讓權等待

二、信號量機制：

1、整型信號量

Wait(s):whiles<0dono-op

s:=s-1;

Signal(s):s:=s+1;

2、記錄型信號量

Wait(s):

{s.value=s.value-1;ifs.value<0block(s.l);}

Signal(s):

{s.value=s.value+1;ifs.value<=0

wakeup(s.l)}

記錄型信號量的物理意義

Wait:相當于分配資源的過程。若有資源進行分配，則

分配后就不會小于0,因此可以完全執(zhí)行完Wait原

語，然后進入臨界區(qū)，如減1后出現(xiàn)小于。的情況則

表示實際上已經(jīng)沒有資源可以分配了，因此該進程

要放到阻塞隊列L中，此時S.VALUE的絕對值就是

阻塞進程的數(shù)量。

Signal:相當于釋放資源的過程。一個進程執(zhí)行完正常

釋放資源，但加1后仍小于等于。表示它原來是個負

數(shù)，因此阻塞隊列里有等待該資源沒有滿足的阻塞

進程，因此，在釋放資源的同時要喚醒阻塞進程。

如加1后正常的正數(shù)，就光釋放完資源就結束了。

3、記錄型信號量的應用

(1)實現(xiàn)互斥

對于N個進程對1個臨界資源的互斥共享，每

個進程的算法描述：

VARMutex：=1；

進程pi：Repeat

Wait(Mutex)；

臨界區(qū)；

Signal(Mutex)

untilfalse;

(2)實現(xiàn)前趨關系：

見p45圖2?10

Vara,b,c,d,e,f,g:=0,0,0,0,0,0,0

S1:s1;signal(a);signal(b);

S2:wait(a);s2;signal(c);signal(d);

S3:wait(b);s3;signal(e);

S4:wait(c);s4;signal(f);

S5:wait(d);s3;signal(g);

S6:wait(e);wait(f);wait(g);s6;

3、利用信號量實現(xiàn)進程同步

輸入進程1個數(shù)據(jù)——?輸出進程

緩沖區(qū)

輸入進程：計算進程：

RepeatRepeat

輸入數(shù)據(jù)；wait(p2);

wait(P1);從緩沖區(qū)取數(shù)據(jù);

放數(shù)據(jù)入緩沖區(qū);signal(P1);

signal(P2);計算數(shù)據(jù)；

untilfalse;untilfalse;

2.4經(jīng)典進程同步問題

、生產(chǎn)者-消費者問題

消

生

費

產(chǎn)

者

者

進

進

程

程

具有n個緩沖區(qū)的緩沖池

多個生產(chǎn)者進程和多個消費者進程共享一個有N個緩沖區(qū)

的緩沖池，生產(chǎn)者進程負責輸入數(shù)據(jù)，消費者進程負責輸出

數(shù)據(jù)，兩個相互合作。用信號量機制把每個進程的執(zhí)行過程

表達出來。因為緩沖區(qū)是臨界資源，一段時間內(nèi)只能有1個進

程使用，所以，對緩沖區(qū)的放數(shù)據(jù)及取數(shù)據(jù)只能有一個進程

來使用緩沖區(qū)，存在互斥問題；同時，生產(chǎn)■與消費構成同步

關系，相互合作，互相制約。

VARmutex:=1,empty=n;full=O;buffter[0..n-1];

inout:=0,0;

生產(chǎn)者進程i：

Repeat

生產(chǎn)數(shù)據(jù)nextp；

wait(empty);

wait(mutex);

buffer[in]:=nextp;

in=(in+1)%n;

signal(full);

untilfalse;

消費者進程i：

Repeat

wait(full);

wait(mutex);

Nextc=buffer(out);

out=(out+1)%n;

signal(empty);

untilfalse;

二、哲學家就餐問題

5個哲學家圍做一個圓桌，5支筷子分

布與每人的兩側，每人先是思考問題，然

后拿起左右兩邊的筷子就餐，后放筷子繼

續(xù)思考問題。用信號量機制描述每人的活

動過程。

分析：筷子5支，都屬于臨界資源，因此互

斥使用；

哲學家i：

Repeat

wait(SM);

wait(chopstick[i]);

wait(chopstick[(i+1)%5]);

就餐；

signal(chopstick[i]);

signal(chopstick[(i+1)%5]);

signal(sm);

繼續(xù)思考；

untilfalse;

Chopstick[0..4]=1;sm=4(5支筷子最多允許4個人同

時去搶，才總有一人人拿到2支，才能吃飯，他放

下后別人可以繼續(xù)用，若允許5個人都搶，可能會

出現(xiàn)一人1支筷子，出現(xiàn)僵持死鎖狀態(tài))

三、讀者-寫者問題

?一個數(shù)據(jù)文件可以同時允許有多個讀者進行訪問，

但每次只允許1個寫者進行修改，讀者和寫者不能

同時出現(xiàn)。

?分析：把多個讀者作為一個整體來考慮，則加上

n個寫者的話，這n+1個對象對數(shù)據(jù)塊互斥訪問，

需要1個互斥信號量wmutex=1柔控制;另外對手讀

者整體中，考慮與寫者互斥的只是第一個讀者來

時要考慮的，有了第一個，其他讀者就可以跟著

進來，同樣，釋放資源時候也只是最后一個讀者,

其他讀者想走就撤就可以。

?為了表示到底有多少讀者，引入記數(shù)變量

readcount,而對變量的使用，屬于臨界資源，一

次只允許一個進程使用，所以再引入信號量

rwmutex=1;一_________

寫者進程i：

REPAET

wait(wmutex);

修改文件；

signal(wmutex);

untilfalse;

例題1、司機與售票員的合作問題

VARS1=1;S2=0;

司機：售票員：

Wait(s1);Wait(s2);

啟動車輛;開車門；

正常行車；上下乘客；

到站停車關車門

Signal(s2);Signal(s1);

售票

例題2：假定閱覽室能容納100個人閱讀，讀者進入和離開閱

覽室時，都必須在閱覽室門口的一個登記表上登記。假定

每次只允許一個人登記和撤消登記，設閱覽室內(nèi)有100個

座位，用信號量機制描述讀者進程的同步算法。

讀者進程i：Vars=100;mutex=1;

Wait(s);

Wait(mutex);

查登記表，并置某座位為占用態(tài)

Signal(mutex);

在座位上坐下閱讀；

Wait(mutex);

查登記表，并置某座位為空閑狀態(tài)

Signal(mutex);

SignaKs)；7,?>———

例題3：桌子上有一只盤子只能放一只水果，爸爸專門向盤

子中放蘋果，媽媽專門向盤子中放橘子，一個兒子專等吃

盤子中的橘子，一個女兒專等吃盤子中的蘋果。用信號量

機制實現(xiàn)他們之間的同步機制。

Vars=1,s1=s2=0

爸爸:準備蘋果；女兒:wait(s1);

wait(s);

從盤子上拿走蘋果;

將蘋果放在盤子內(nèi);

signal(sl);signal(s);

媽媽:準備橘子；

吃蘋果；

wait(s);

兒子:wait(s2);

將橘子放在盤子內(nèi);

從盤子上拿走橘子;

signal(s2);

signal(s);

吃橘子；

2.5管程機制

一、定義：

一個管程定義了一個數(shù)據(jù)結構和能為并發(fā)進

程所執(zhí)行（在該數(shù)據(jù)結構上）的一組操作,

這組操作能同步進程和改變管程中的數(shù)據(jù)O

引入管程的目的是避免信號量機制書寫中的

麻煩，具體例子參考P53。

2.6進程通信

一、進程通信的類型

1、共享存儲器系統(tǒng)

(1)基于共享數(shù)據(jù)結構的通信方式

(2)基于共享存儲區(qū)的通信方式

2、消息傳遞系統(tǒng)

(1)直接通信方式：

Send(receiver,message);

Receive(sender,message);

(2)間接通信方式______

Send(mailbox,message);

Receive(mailbox,message);

3、管道通信：所謂管道是用于連接一個讀進程和一個寫進程以

實現(xiàn)他們通信的一個共享文件，又名Pipe文件，本身提供了

互斥和同步進程的能力。）

二、消息緩沖隊列通信機制

1、消息緩沖隊列通信機制中的數(shù)據(jù)結構

Typemessagebuffer=record

sender:發(fā)送者進程標識符；

size:消息長度;

text”消息TF文.

next:指向下二個消息緩沖區(qū)的指針

end

2、PCB中有關通信的數(shù)據(jù)項

Mq:消息隊列隊首指針；

Mutex:消息隊列互斥信號量

Sm:消息隊列資源信號量

4、接收原語

Procedurereceive(b)

Begin

J=internalname;

Wait(j.sm);

Wait(j.mutex);

Remove(j.mqJ);

Signal(j.mutex);

b.sender=i.sizer;

b.size=i.size;

b.text=i.size;

End;

2.7線程

一、線程的基本概念

1、線程的引入

進程的兩個屬性：資源分配的獨立單位；CPU調度

的獨立串位。

進一步提高并發(fā)程度和減少系統(tǒng)開銷引入線程。

2、線程的屬性

(1)輕型實體

(2)獨立調度和分派的基本單位

(3)可并發(fā)執(zhí)行

(4)共享進程資源。

第三章處理機調度與死鎖

3.1處理機調度的基本概念

一、高級、中級和低級調度

1、高級調度(作業(yè)調度)：由作業(yè)調度程序

按照一定算法選擇若干作業(yè)進入內(nèi)存，創(chuàng)

建出進程，分配必要的資源，將新進程掛

到就緒隊列中。

(1)接納多少作業(yè)(2)接納哪些作業(yè)

2、低級調度(進程調度)：決定就緒隊列的進

程誰獲得處理機，然后再由分派程序執(zhí)行把處理

機分配給該進程。

非搶占方式：一旦處理機分配給某個進程就要它一

直執(zhí)行下去，直至進程完成或者發(fā)生某事件而被

阻塞時，才再把處理機分配給其他進程。

搶占方式：正在執(zhí)行的進程，若有新的優(yōu)先級更高

的進程到來后則停止正在執(zhí)行的進程，新進程搶

占CPU。

搶占的標準為：(1)優(yōu)先權原則；

(2)短作業(yè)優(yōu)先原則；

(3)時間片原則。

3、中級調度

存儲管理中的對換功能，把內(nèi)存中暫時不運行的進

程換出到外存對換區(qū)，而把外存中具備運行條件

的進程換入內(nèi)存，稱為中級調度。

二、調度隊列模型

1、僅有進程調度的調度隊列模型

2、具有高級和低級調度的調度隊列模型

3、同時具有三級調度的調度隊列模型

三、選擇調度方式和調度算法的若干準則

1、面向用戶的準則

(1)周轉時間：從作業(yè)被提交給系統(tǒng)開始，到作

業(yè)完成為止的這段時間間隔。包括四部分時間：作

業(yè)在外存后備隊列上等待調度的時間、進程在就緒

隊列上等待進程調度的時間、進程在CPU上執(zhí)行

的時間、進程等待I/O操作完成的時間。

平均周轉時間

平均帶權周轉時間

(2)響應時間。

(3)截止時間的保證

(4)優(yōu)先權準則

2、面向系統(tǒng)的準則

(1)系統(tǒng)吞吐量高

(2)處理機利用率好

(3)各類資源的平衡利用。

3.2調度算法

一、先來先服務和短作業(yè)優(yōu)先調度算法

1、先來先服務調度算法

算法思想：（1）作業(yè)調度：每次調度都從后備作業(yè)

隊列中，選擇一個或多個最先進入該隊列的作業(yè)，

將它們調入內(nèi)存，為它們分配資源，創(chuàng)建進程，然

后放入就緒隊列。

（2）進程調度：每次調度是從就緒隊列中，選擇一個

最先進入該隊列的進程，為之分配處理機，使之投

入運行。

通常要考慮，目前系統(tǒng)是否滿足進程資源要求。

例子參考P76

二、短作業(yè)（進程）優(yōu)先調度算法

對短作業(yè)或短進程進行優(yōu)先調度的算法。短

作業(yè)調度算法是從后備隊列中選擇一個后

若干個估計運行時間最短的作業(yè)，將它們

內(nèi)調入內(nèi)存運行。短進程調度是從就緒隊

列中選出一估計運行時間最短的進程，分

配處理機。

注：（1）FCFS算法不利于短作業(yè)。

（2）SJF算法不利于長作業(yè)。

作業(yè)名進入輸入井需計算時間（分）需要內(nèi)存容量（KB）

A8：064215

B8：183060

C8：302450

D8：362410

E8：421220

FCFS：

作業(yè)名進入內(nèi)存開始執(zhí)行結束執(zhí)行周轉時間帶權周轉

A8：068：068：484242/42

B8：188：489：186060/30

D8：369：189：426666/24

C9：189：4210：069696/24

E9：1810：0610：189696/12

SJF：

作業(yè)名進入內(nèi)存開始執(zhí)行結束執(zhí)行周轉時間帶權周轉

A8：068：068：484242/42

D8：368：489：123636/24

E9：129：129：244242/12

B8：189：249：549696/30

C9：549：5410：18108108/24

三、高優(yōu)先權優(yōu)先調度算法

1、優(yōu)先權調度算法的類型

(1)非搶占方式：一旦處理機分配給某個進程后，

該進程一直執(zhí)行下去，直至完成，其它進程不得搶

占CPLL

(2)搶占方式：把處理機分配給優(yōu)先權最高的進程

執(zhí)行，若來新進程優(yōu)先級更高，則搶占CPU。

2、優(yōu)先權的類型：

(1)靜態(tài)優(yōu)先權：創(chuàng)建進程時確定，整個運行期間

保持不變。一般用0-255或0-7中的某個整數(shù)來表示,

有的系統(tǒng)中數(shù)字越大，優(yōu)先級越高，有的系統(tǒng)相反。

(2)動態(tài)優(yōu)先權：隨著進程的推進或等待時間的增

力口，優(yōu)先權而發(fā)生改變。

作業(yè)名進入輸入井需計算時間（分）優(yōu)先級（數(shù)大級高）

A8：00601

B8：30502

C8：40304

D8：50103

非強占方式：ACDB

強占方式：A-B-C-D-B-A

3、高響應比優(yōu)先調度算法

(1)優(yōu)先權的確定：優(yōu)先權二(等待時間+要求服務

時間)/要求服務時間

(2)高響應比優(yōu)先調度算法既照顧到了短作業(yè)，又

考慮了長作業(yè)。

四、基于時間片的輪轉調度算法

1、時間片輪轉法

將所有的就緒進程按先來先服務的原則，排成一個隊

歹U,每次調度時，把CPU分配給隊首進程，并令

其執(zhí)行一個時間片。

2、多級反饋隊列調度算法

是目前公認的一種較好的調度算法：

a.設定多個就緒隊列，每個隊列設定不同優(yōu)先級，由高到低,

每個隊列中進程獲得時間片有小到大；

b.新進程進入內(nèi)存，先放第1隊列的末尾，按FCFS原貝1J進行

運行，單位時間片運行完結束，否則放到第2隊列末尾，

依次類推，直至全部放到最后一級隊列，完全采取時間片

輪轉原則進行運行

c.僅當前面隊列全部空閑時，才運行后面隊列中的進程，若

正在執(zhí)行第I級隊列的某進程，來一個新進程，則將當前

執(zhí)行進程放到該級隊列的末尾，專而執(zhí)行新進程。

兼顧了長作業(yè)和短作業(yè)，采用了FCFS以及時

間片輪轉和優(yōu)先級高低綜合運用的一種調

度算法。

3.5產(chǎn)生死鎖的原因和必要條件

一、死鎖的定義和原因

1、定義：所謂死鎖是指多個進程在運行過程

中因爭奪資源而造成的一種僵局，若無外

力作用，它們都將無法再向前推進。

2、產(chǎn)生死鎖的原因

(1)競爭資源：可剝奪和非剝奪性資源/臨

時性資源

(2)進程間推進順序非法。

二、產(chǎn)生死鎖的必要條件

(1)互斥條件：資源本身的特性

(2)請求和保持條件：在請求不到新資源的時候進

程不釋放原來的資源

(3)不剝奪條件：進程獲得的資源，為使用完前不

可被剝奪

(4)環(huán)路等待條件：進程對資源的請求形成一個請

求環(huán)形鏈

三、處理死鎖的基本方法

1、預防死鎖

2、避免死鎖

3、檢測死鎖

4、解除死鎖

3.6預防死鎖的方法

一、預防死鎖

1、打破請求和保持條件：要求進程一次性申請到全

部資源后再運行，不會產(chǎn)生死鎖，但效率降低

2、打破不剝奪條件：要求進程提出新資源要求不被

滿足后，必須釋放原來的保持的資源，損失代價

嚴重；

3、打破環(huán)路等待條件：對資源進行線性排序編號，

要求每個進程必須從低號到高號申請資源，而不

考慮進程實際申請資源的先后順序。

二、系統(tǒng)安全狀態(tài)

1、安全狀態(tài)：系統(tǒng)能按某種進程順序

(p1,p2,...pn)序列，來為某個進程pi分配其所需

要資源，直至滿足每個進程對資源的最大需求，使

每個進程都可順利地完成。如果系統(tǒng)無法找到這樣

一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。

進入不安全狀態(tài)，進而會出現(xiàn)死鎖狀態(tài)，但并非所有

不安全狀態(tài)都進入死鎖狀態(tài)。

2、安全狀態(tài)舉例。

三、利用銀行家算法避免死鎖

1、數(shù)據(jù)結構：

(1)n個進程對m類資源的最大需求情況構成

最大需求矩陣Max口口；

(2)分配矩陣Allocation表示當前已經(jīng)分配的

資源情況；

(3)目前還差多少資源就可運行完畢構成需

求矩陣Need口口;

(4)目前系統(tǒng)的m類資源的可用數(shù)量

Available□一維數(shù)組□

Need[i,j]=Max[i,j]-Allocation[i,j]

2、銀行家算法：主要用來判斷在當前狀態(tài)下如果

有進程提出資源請求request口，看是否能滿足該請

求：

a：判斷請求的合法性，是否滿足小于NEED矩陣中

的向量；

b：請求的可滿足性判斷，是否小于available口向量；

c：試探分配，修改相應的參數(shù)

available[]\allocation\need;

d：進行安全性檢查，若分配后安全，則進行分配，

若判斷從此進入了不安全狀態(tài)，則恢復原來數(shù)據(jù)，

對進程請求不予滿足。

3、安全性算法檢查：

(1)設定兩個向量work=available;finish[i]=true

(2)從進程集合中找到一個能滿足下述條件的進程

finish[i]=false;need[i][j]Wwork[j];若找到,執(zhí)行步

驟3,否則執(zhí)行步驟4

(3)當進程pi獲得資源后，可順利執(zhí)行，直到執(zhí)行,

并釋放出分配給它的資源

work[j]=work[j]+allocation[i][j];finish[i]=true;

Gotostep2

(4)如果所有進程方nish[i]=true都滿足，則系統(tǒng)處于

安全狀態(tài)，否則處于不安全狀態(tài)。

4、銀行家算法舉例。

MAXALLOCATIONNEEDAVAILABLE

ABCABCABCABC

P0753010743332

P1322200122

P2902302600

P3222211011

P4433002431

（1）當前狀態(tài)是否安全

(2)p1請求(1,0,2）是否可以分配。

(3)p4請求(3,3,0）是否可以分配

(4)p0請求(0,2,0）是否可以分配

37死鎖的檢測與解除

一、死鎖的檢測

1、資源分配圖：

2、死鎖定理：當且僅當S狀態(tài)的資源分配圖

是不可完全簡化的。該充分條件被稱為死

鎖定理。

3、死鎖檢測算法。P100

、死鎖的解除

1、剝奪資源

2、撤消進程

第四章存儲器管理

4.1程序的裝入和鏈接

一、程序的執(zhí)行過程

(1)編譯

(2)鏈接

(3)裝入

二、程序的裝入

1、絕對裝入方式：編譯時知道程序駐留在內(nèi)存的什

么位置，編譯后產(chǎn)生絕對地址的目標代碼，將程

序裝入內(nèi)存，程序的邏輯地址與實際物理地址完

全相同，不需要進行地址變換。絕對裝入方式只

適用于單道程序環(huán)境。

2、可重定位裝入方式：把裝入時對目標程序中指令

和數(shù)據(jù)的修改過程稱為重定位。又因為地址變換

通常是在裝入時一次完成的，以后不再改變，故

稱為靜態(tài)重定位。不允許程序運行時在內(nèi)存中移

動位置。

3、動態(tài)運行時裝入方式：采取動態(tài)重定位方式進行

地址變換。

三、程序的鏈接

1、靜態(tài)鏈接：程序運行前先鏈接，再裝入內(nèi)

存。

(1)對相對地址的改變

(2)變換外部調用符號

2、裝入時動態(tài)鏈接：裝入內(nèi)存時，邊裝入邊

鏈接。

3、運行時動態(tài)鏈接：某些模塊的鏈接推遲到

執(zhí)行時才執(zhí)行，用不到的模塊可以不調入

內(nèi)存。

4.2連續(xù)分配方式

為程序分配一個連續(xù)的存儲空間。

一、單一連續(xù)分配技術：只能應用與單用戶單

任務操作系統(tǒng)，如DOS,整個內(nèi)存空間除了

常駐內(nèi)存的操作系統(tǒng)內(nèi)核所占的系統(tǒng)區(qū)外，

其他都是分配給用戶程序的用戶區(qū)。

系統(tǒng)區(qū)

用戶區(qū)

二、固定分區(qū)分配方式：屬于最簡單的多道

程序的存儲管理方式，

1、劃分分區(qū)的方法：

(1)分區(qū)大小相等

(2)分區(qū)大小不等

分區(qū)的數(shù)量的確定也就決定了在內(nèi)存中只能

安排多少程序同時存放和執(zhí)行。一個分區(qū)

里只能放一個作業(yè)，不管剩余多少空間，

都不能再分配給別的作業(yè)了。因此內(nèi)存利

用率不會太高。

2、內(nèi)存分配：將各區(qū)建立一個分區(qū)使用表，表示分區(qū)號、

分區(qū)的大小、分區(qū)的起始地址以及分區(qū)的狀態(tài)（即已分配

還是未分配），作為將來分配給作業(yè)的一個數(shù)據(jù)結構。

三、動態(tài)分區(qū)分配

1、分區(qū)分配的數(shù)據(jù)結構：主要有空閑分區(qū)表或者空

閑分配鏈，把每個空閑分區(qū)的序號、大小和其始

地址，作為一個表目存放在空閑分區(qū)表或鏈結點

內(nèi)，作為分配的依據(jù)。

2、分區(qū)分配算法：

(1)首次適應算法：把空閑分區(qū)按地址遞增的順序

排列，從第一個分區(qū)開始搜索到第一個滿足作業(yè)

需求的分區(qū)進行分配，剩余的空間作為新的空閑

區(qū)，將來仍然作為分配對象。缺點，每次都從地

址低的部分進行搜索，低址部分會比較瑣碎，增

加系統(tǒng)開銷。

(2)循環(huán)首次適應算法，在首次適應算法基礎上下

一個作業(yè)的搜索從上次找到的空閑分區(qū)的下一個

空閑分區(qū)開始查找，該算法會使空閑分區(qū)比較均

勻，但缺少大分區(qū)。

(3)最佳適應算法：將空閑分區(qū)按大小遞增的順序

排列，每次選擇最恰當?shù)姆謪^(qū)分配給作業(yè)，但剩

余的空間往往是最小的，有可能因為太小就不能

滿足任何一個作業(yè)的內(nèi)存需求而造成浪費，我們

稱之為內(nèi)存“零頭”或者“碎片”。

(4)最壞適應算法：要求空閑分區(qū)按地址遞減的順

序排列，每次選取最大的空閑分區(qū)分配給作業(yè)，

因為由此剩下的空閑區(qū)也是最大的，更容易分配

出去，但會缺乏大分區(qū)。

4、分區(qū)分配操作

(1)分配內(nèi)存：參考P110圖4-6

(2)回收內(nèi)存：當一個作業(yè)執(zhí)行完畢，釋放內(nèi)存空間

時，需要涉及和前后空閑區(qū)的合并問題，若回收區(qū)前面是

一個空閑區(qū)的，則只修改前空閑區(qū)的大小就可以合并了，

若回收區(qū)后面是空閑區(qū)，則需修改后面空閑區(qū)的大小和起

始地址進行合并，若回收區(qū)前后都是空閑區(qū)，則回收就要

三者合并，將第一空閑區(qū)的大小修改，刪除后面一個空閑

分區(qū)表項，造成總的空閑分區(qū)表數(shù)量減1,若回收區(qū)上下

都沒有空閑區(qū)，則在空閑分區(qū)表中添加一個新的表項。

五、可重定位分區(qū)分配

1、動態(tài)重定位的引入

(1)“零頭”或“碎片”

(2)“拼接”或“緊湊”

2、動態(tài)重定位的實現(xiàn)：地址變換過程是在程

序執(zhí)行期間，隨著對每條指令或數(shù)據(jù)的訪

問自動進行的，故稱動態(tài)重定位。

3、動態(tài)重定位的分區(qū)分配算法。參考

P112圖4-10

六、對換：

所謂對換是把內(nèi)存中暫時不運行的進程或者

暫時不用的程序和數(shù)據(jù)，調出到外存上，

騰出足夠的內(nèi)存空間，把已具備運行條件

的進程或進程所需要的程序和數(shù)據(jù)，調入

到內(nèi)存。對換是提高內(nèi)存利用率的有效措

施。

4.3基本分頁存儲管理方式

一、頁面與頁表

1、頁面、塊：將一個進程的邏輯地址分成若干個大

小相等的片，森為頁面或頁。每個頁面從0開始編

號，同時將內(nèi)存空間也分成與頁面大小相等的物

理塊，也稱為頁框或塊。

2、頁面大小：每個頁面大小是1KB,2KB或者4KB,

都是2的嘉，

3、頁表：為了實現(xiàn)頁面與物理塊的對應，引入一張

頁面和它存儲的物理塊的映射表稱為頁表。頁表

中主要有頁號和它對應的物理叫號兩項，

4、地址結構

(1)根據(jù)頁面大小，從邏輯地址的低位確定

出頁內(nèi)偏移量，剩余二進制位表示頁號。

從而將邏輯地址分解成兩部分。如P114

(2)數(shù)學計算公式：

p=int(A/L)

d=A%L

P表示頁號，d表示頁內(nèi)偏移量。

頁號塊號已知頁面大小為1024字節(jié)，

02邏輯地址分別是1011,

132148,3000o4000o5012

21

36

答案:3059,1124,1976,7072,邏輯地址非法

二、地址變換機構

1、基本地址變換機構：在進程沒有執(zhí)行前，頁表在

內(nèi)存的起始地址和頁表的長度存儲在進程的PCB內(nèi),

當進程獲得執(zhí)行后，頁表起始地址和頁表長度放到

了頁表寄存器內(nèi)。

2、基本地址變換過程：

首先將邏輯地址轉換為p和d兩部分，根據(jù)頁表寄存器

內(nèi)頁的長度判斷該頁號是否屬于越界訪問，若沒有

越界，根據(jù)頁表在內(nèi)存的起始地址找到頁表，查找

到該頁對應的索引項，得出該頁號對應的實際物理

塊，同時，頁內(nèi)偏移量同時也是物理塊的偏移量，

因此，物理塊號*塊的大?。?KB或4KB）+偏移量二

實際物理地址；或者物理塊號的二進制編碼加上偏

移量的二進制代碼表示組成實際物理地址。

3、具有快表的地址變換機構

(1)快表：聯(lián)想寄存器，在地址變換機構中增設的

具有并行查尋能力的特殊的高速緩沖寄存器，用

以存放當前訪問的那些頁表項。

(2)地址變換過程：給出邏輯地址后，先到快表中

查找索引項，若有，直接地址變換就可以形成物

理地址而不用訪問主存了，若快表中沒有，再到

內(nèi)存去查找頁表，從中找到物理塊號進行地址變

換，但同時要把該索引項重新寫到聯(lián)想寄存器內(nèi)，

若已滿，則換出認為不再需要的索引項。這樣，

根據(jù)程序執(zhí)行的局部原理，90%的檢索頁表索引

項的過程可以在聯(lián)想寄存器內(nèi)實現(xiàn)，從而提高檢

索效率。

4.4基本分段存儲管理方式

一、分段存儲管理方式的引入

1、方便編程

2、信息共享

3、信息保護

4、動態(tài)增長

5、動態(tài)鏈接

二、分段系統(tǒng)的基本原理

1、分段：將作業(yè)的邏輯地址空間分為若干個

段，每個段內(nèi)定義一組邏輯信息。作業(yè)的

地址空間分為段號（名）+段內(nèi)地址兩部分

2、段表：將不同的段分配到內(nèi)存不連續(xù)的存

儲空間，當然，具體每個段，因為長度可

能不同，但是需連續(xù)的存儲空間，因此，

段表內(nèi)需確定段號、段的長度、段在內(nèi)存

的起始地址。

3、地址變換機構

給定邏輯地址（段號S和段內(nèi)地址d）,先拿段號和

段表寄存器內(nèi)的段的長度進行比較，看是否越界,

然后拿段表寄存器的起始地址到段表中檢索到該

段段表項，根據(jù)段的長度與邏輯地址的段內(nèi)地址

進行比較，再次判斷是否越界，若沒有越界，根

據(jù)段的內(nèi)存的基地址加上段內(nèi)地址d形成實際物理

地址。也需要兩次訪問內(nèi)存，也可以引入聯(lián)想寄

存器。

段號內(nèi)存起始地址段長

0210500

1235020

210090

31350580

4193895

邏輯地址:[0,430][1,10][2,500][3,400][4,112][5,32]

答案:6401360非法1750非法

4、分頁與分段區(qū)別：

(1)頁是信息的物理單位，為了提高內(nèi)存利

用率引入的；段是信息的邏輯單位，是考

慮用戶編程需要分成的段。

(2)頁的大小固定，段的大小不確定

(3)頁的邏輯地址是1維的，段的邏輯地址

是2維的。

二、信息共享

參考P122

分段存儲管理方式與分頁存儲管理方式比較

更方便于實施信息共享。

二、段頁式存儲管理方式

1、基本原理：首先用戶程序分成若干個段,

每個段內(nèi)再實施分頁，為每個段賦予一個

段名。在段頁式系統(tǒng)中，其地址結構由段

號、段內(nèi)頁號及頁內(nèi)地址三部分組成。

2、地址變換過程（詳細見P124圖4-22）

4.5虛擬存儲器的基本概念

一、虛擬存儲器的引入

1、常規(guī)存儲器的特征

(1)一次性

(2)駐留性

2、程序執(zhí)行的局部性原理

(1)時間的局限性

(2)空間的局限性

3、虛擬存儲器的定義

所謂虛擬存儲器是指具有請求調入功能和置換功能,

能從邏輯上對內(nèi)存容量加以擴充的一種存儲器系

統(tǒng)。其邏輯容量由內(nèi)存容量和外存容量之和所決

定的。

二、虛擬存儲器的實現(xiàn)方法

1、分頁請求系統(tǒng)

2、請求分段系統(tǒng)

三、虛擬存儲器的特征

1、多次性

2、對換性

3、虛擬性

46請求分頁存儲管理方式

一、請求分頁中的硬件支持

1、頁表機制

在原來頁號和物理塊號的基礎上增加輔助項，狀態(tài)

位（0表示在外存，沒有調入，1表示在內(nèi)存）；

訪問字段（一段時間內(nèi)訪問次數(shù)或是否被訪問過

供頁面置換出去時參考）；修改位（一段時間內(nèi)

是否被修改過，置換時需要回寫到外存對換區(qū)）

外存地址（將來調入內(nèi)存時使用）；

2、缺頁中斷機構

3、地址變換機構參考P130圖4-24

二、內(nèi)存分配策略和分配算法

1、最小物理塊的確定

保證進程正常運行所需要的最小物理塊數(shù)

2、物理塊的分配策略

(1)固定分配局部置換

(2)可變分配全局置換

(3)可變分配局部置換

3、物理塊分配算法

(1)平均分配算法

(2)按比例分配算法

(3)考慮優(yōu)先權的分配算法

三、調頁策略

1、何時調入頁面

2、從何處調入頁面

3、頁面調入過程

4.7頁面置換算法

一、最佳置換算法（OPT）和先進先出置換

算法

1、OPT算法：選擇被淘汰的頁面是以后永不使用

或者最長時間內(nèi)不被執(zhí)行的頁面，因為將來的事

情不可預知，所以不可實現(xiàn)。

2、先進先出置換算法（FIFO）,完全考慮進入內(nèi)

存的先后時間；

頁面引用串：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,17,0,1

二、最近最久未使用(LRU)算法：

1、LRU算法：選擇淘汰頁面選擇最近最久

未使用的頁面予以淘汰。

2、LRU置換算法的硬件支持

(1)移位寄存器法

(2)棧

三、Clock置換算法

1、簡單的Clock置換算法：只考慮訪問位的

情況作為置換頁面的依據(jù)。

2、改進型Clock置換算法：除考慮訪問位之

夕卜，增加考慮修改位的情況。

四、其它頁面置換算法

1、最少使用置換算法

2、頁面緩沖算法

48請求分段存儲管理方式

一、請求分段中的硬件支持

1、段表機制

在段號、段長、段的基地址的基礎上，增加存取方

式、訪問字段、修改位、存在位、增補位以及外

存地址。存取方式主要是只讀、可寫、可讀寫等

對段實施保護，訪問字段確定被訪問的次數(shù)，存

在位表示是否在內(nèi)存，修改位同樣是供置換參考

增補位表示該段是否動態(tài)增長過，外存地址同樣

是在外存的盤塊號。

2、缺段中斷機構

3、地址變換機構

二、分段的共享與保護

1、共享段表

2、共享段的分配與回收

3、分段保護

第五章設備管理

5.1I/O系統(tǒng)

一、I/O設備

1、按傳輸速率分類：

(1)低速設備：每秒幾個字節(jié)至數(shù)百字節(jié)，鍵盤、

鼠標、語音的輸入、輸出設備

(2)中速設備：每秒數(shù)千字節(jié)至數(shù)萬字節(jié)的設備，

如行式、激光打印機

(3)高速設備：數(shù)百千字節(jié)至數(shù)十兆字節(jié)，磁帶機、

磁盤機、光盤機。

2、按信息交換單位分類

(1)塊設備。存儲信息以數(shù)據(jù)塊為基本單位

典型設備為磁盤，傳輸速度快，可尋址，

I/O控制方式為DMA方式

(2)字符設備。打印機等，傳輸速度低，以

字符為傳送單位，不可尋址，采用中斷驅

動方式。

3、按設備的共享屬性分類

(1)獨占設備、

(2)共享設備

(3)虛擬設備

二、設備控制器

設備控制器是在CPU和I/O設備之間的接口,

一個設備控制器控制幾個設備。

1、設備控制器的組成：

(1)設備控制器與處理機的接口

(2)設備控制器與設備的接口

(3)I/O邏輯

三、通道

1、通道是特殊的處理機，是專門通過執(zhí)行內(nèi)存

中的通道程序來控制I/O操作的可與CPU同時

工作的處理機，指令單一，只去實現(xiàn)控制I/O

過程的。

2、I/O系統(tǒng)

(1)主機系統(tǒng)：整個主機中的I/O系統(tǒng)包括了三

級控制，四級連接，即內(nèi)存、通道、設備控制

器及設備。

(2)微機系統(tǒng)：沒有通道，因此采取CPU與內(nèi)

存通過總線結構與設備控制器連接。

3、“瓶頸”問題：

(1)一個通道連接多個設備控制器，一個控

制器連接多個設備，這樣在實際通路中因為

設備控制器和通道數(shù)量的遞減從而在構造數(shù)

據(jù)通路的時候出現(xiàn)一種“瓶頸”現(xiàn)象，越向

內(nèi)存數(shù)量越少。

(2)解決瓶頸問題的有效方法是增加通路而

不增加通道，因為通道價格昂貴，可以將一

個設備連接多個控制器，一個控制器連接多

個通道，從而盡可能的增加通路。

521/0控缶U方式

＞程序I/O方式

處理機向控制器發(fā)出I/O指令啟動設備輸

入數(shù)據(jù)時，把busy信號設定為1,以后不斷

循環(huán)檢測該信號，當設備控制器輸入數(shù)據(jù)

完成，修改信號為0,由CPU將該數(shù)據(jù)送入內(nèi)

存。

二、中斷驅動I/O控制方式

CPU發(fā)送指令給設備控制器后，轉而做別的工作去，

每接受一個字符到設備控制器的數(shù)據(jù)寄存器后，就

發(fā)中斷給CPU,要CPU放數(shù)據(jù)入內(nèi)存。例如打印機

等字符設備采取該中斷驅動方式。

三、直接存儲器訪問DMAI/O控制方式

1、DMA控制方式的引入：

塊設備的專門的控制器就是DMA控制器，通過控制

器接收設備來的數(shù)據(jù)直接送數(shù)據(jù)進入內(nèi)存的存儲單

元中，不用CPU干涉，只是到連續(xù)盤塊的數(shù)據(jù)全部

輸入或輸出完成后才發(fā)中斷給CPU）。

(1)數(shù)據(jù)傳輸基本單位是數(shù)據(jù)塊

(2)所傳送的數(shù)據(jù)是從設備直接送入內(nèi)存或者相反

(3)僅在傳輸一個或多個數(shù)據(jù)塊的開始或結束時，才需要

CPU干預。

2、DMA控制器的組成：

主機與DMA控制器的接口；DMA控制器與塊設備的

接口、I/O控制邏輯

四類寄存器：

(1)命令/狀態(tài)寄存器CR

(2)內(nèi)存地址寄存器MAR

(3)數(shù)據(jù)寄存器DR

(4)數(shù)據(jù)計數(shù)器DC

3、DMA控制器的工作方式

四、I/O通道控制方式

1、I/O通道控制方式的引入

進一步減少CPU的干預，將對一個數(shù)據(jù)塊的讀寫為

單位的干預，減少為對一組數(shù)據(jù)塊的讀寫及有關

的控制和管理為單位的干預。

2、通道程序：

通道是通過執(zhí)行通道程序，并與設備控制器共同實

現(xiàn)對I/O設備的控制的。通道程序是由一系列通道

指令所構成的。

每條指令：（1）操作碼（2）內(nèi)存地址（3）計

數(shù)（4）通道程序結束位（5）記錄結束標志。

5.3緩沖管理

一、緩沖的引入

1、緩和CPU與I/O設備間速度不匹配的矛盾

2、減少對CPU的中斷頻率

3、提高CPU和I/O設備間的并行性

二、單緩沖和雙緩沖、循環(huán)緩沖及緩沖池

5.4設備分配

一、設備分配中的數(shù)據(jù)結構

1、設備控制表DCT

2、控制器控制表COCT、通道控制表CHCT

3、系統(tǒng)設備表

二、設備分配時應考慮的因素

1、設備的固有屬性：獨享設備、共享設備

虛擬設備

2、設備分配算法：

(1)先來先服務

(2)優(yōu)先級高者優(yōu)先

3、設備分配中的安全性

(1)安全分配方式

(2)不安全分配方式

4、設備獨立性

為了提高操作系統(tǒng)的可適應性和可擴展性，

應用程序獨立于具體使用的物理設備。在應用程序

中，使用邏輯設備名稱來請求使用某類設備，在系

統(tǒng)實際執(zhí)行時再轉換為具體物理設備。

特點：(1)設備分配時的靈活性

(2)考慮多通路情況

三、spooling技術

1、定義：SPOOLING技術是在系統(tǒng)中引入多道

程序設計技術后，用其中的一道程序模擬脫機輸

入時的衛(wèi)星機的功能把低速I/O設備數(shù)據(jù)傳送到高

速磁盤上，用另一道程序模擬脫機輸出時衛(wèi)星機

的功能把高速磁盤上的數(shù)據(jù)傳送出I/O設備上，這

樣在主機直接控制下，實現(xiàn)了脫機輸入、輸出的

功能，因此，我們把這種在聯(lián)機情況下實現(xiàn)的同

時外圍操作稱為SPOOLING技術或假脫機操作。

2、spooling系統(tǒng)組成

(1)輸入井和輸出井

(2)輸入緩沖區(qū)和輸出緩沖區(qū)

(3)輸入進程SR和輸出進程sp。

3、共享打印機

4、SPOOLING系統(tǒng)的特點

(1)提高了I/O的速度

(2)將獨占設備改造為共享設備

(3)實現(xiàn)了虛擬設備功能

5.5設備處理

設備處理程序通常又稱為設備驅動程序。是I/O進程與設備控

制器之間的通信程序，以進程的形式存在，故稱為設備驅

動進程。

一、設備驅動程序的功能

1、接收由I/O進程發(fā)來的命令和參數(shù)，轉換為具體要求

2、檢查用戶I/O請求的合法性

3、發(fā)出I/O命令

4、及時響應由控制器或通道發(fā)來的中斷請求，并根據(jù)其中

斷類型調用相應的中斷處理程序進行處理

5、對于有通道的計算機系統(tǒng)，驅動程序根據(jù)用戶I/O請求，

自動的構成通道程序。

二、設備驅動程序的處理過程

1、將抽象要求轉換為具體要求

2、檢查I/O請求的合法性

3、讀出和檢查設備的狀態(tài)

4、傳送必要的參數(shù)

5、工作方式的設置

6、啟動I/O設備

.▲、中斷處理程序的處理過程

1、喚醒被阻塞的驅動進程

2、保護被中斷進程的CPU環(huán)境

3、轉入相應的設備處理程序

4、中斷處理

5、恢復被中斷進程的現(xiàn)場。

5.6磁盤存儲器管理

一、磁盤性能概述

1、數(shù)據(jù)的組織和格式

盤片、磁道、扇區(qū)

2、磁盤的類型

(1)固定頭磁盤：每個磁道上有一個讀寫磁

頭。

(2)移動頭磁盤：每一個盤面上設定一個磁

頭。

3、磁盤訪問時間

(1)尋道時間

(2)旋轉延遲時間

(3)傳輸時間

二、磁盤調度

1、先來先服務FCFS：根據(jù)進程請求訪問磁

盤的先后次序進行調度。

2、最短尋道時間優(yōu)先SSTF算法

要求訪問的磁道，與當前磁頭所在的磁道距

離最近。

3、掃描（scan）算法

為了避免“饑餓”現(xiàn)象，引入電梯調度算法,

首先考慮磁頭當前的移動方向，所考慮的

下一個訪問對象，應是磁頭移動方向上的

又是距離最近的磁道。

4、循環(huán)掃描（cscan）算法

規(guī)定磁頭單向移動，磁頭移動到方向上最外

的磁道并訪問后，再返回到最里的欲訪問

磁道。

5、N?Step?Scan和FSCAN調度算法。

第六章文件管理

6.1文件和文件系統(tǒng)

一、文件、記錄和數(shù)據(jù)項

1、數(shù)據(jù)項是最低級的數(shù)據(jù)組織形式。分為基

本數(shù)據(jù)項和組合數(shù)據(jù)項。

2、記錄是一組相關數(shù)據(jù)項的集合，用于描述

一個對象在某方面的屬性。

3、文件是指由創(chuàng)建者所定義的、具有文件名

的一組相關元素的集合，可分為有結構文

件和無結構文件兩種。

4、文件屬性

(1)文件類型

(2)文件長度

(3)文件的物理位置

(4)文件的建立時間

二、文件類型和文件系統(tǒng)模型

1、文件類型

用途分：系統(tǒng)文件/用戶文件/庫文件

數(shù)據(jù)的形式分：源文件/目標文件/可執(zhí)行文件

存取控制屬性：只執(zhí)行文件/只讀文件/讀寫文件

2、文件系統(tǒng)模型

(1)對象及其屬性

(2)對對象操縱和管理的軟件集合

是文件管理系統(tǒng)的核心部分。文件存儲空間的管理、

對文件目錄的管理、將文件邏輯地址轉換為物理

地址的機制、對文件讀寫的管理、文件的共享和

保護等功能。

(3)文件系統(tǒng)的接口

命令接口

程序接口

62文件的邏輯結構

1、文件的邏輯結構：是從用戶觀點出發(fā)所觀察

到的文件組織形式，是用戶可以直接處理的數(shù)據(jù)

及其結構，其獨立于文件的物理特性，又稱為文

件組織形式。

2、文件的物理結構又稱為文件存儲結構，是

指文件在外存上的存儲組織形式。

一、文件邏輯結構的類型

1、有結構文件

(1)定長記錄

(2)變長記錄

2、無結構文件：流式文件。

二、順序文件

1、文件是記錄的集合，文件中的記錄可以是任意順

序的。

(1)串結構：各記錄之間的順序與關鍵字無關。

(2)順序結構：文件中的記錄按關鍵字排列。

2、對順序文件的讀寫操作

(1)定長記錄的順序文件可以直接讀取任意

一條記錄。

(2)對于變長記錄的順序文件只能順序訪問

每一條記錄。

3、順序文件的優(yōu)缺點：

(1)記錄的批量存取有優(yōu)勢。

(2)查找和修改單個記錄查找性能差

(3)增加和刪除記錄困難。

三、索引文件

對于變長記錄建立一張索引表，對主文件中的每個

記錄，在索引表中設有一個相應