《計算機操作系統》講義

一、課程簡介

操作系統是計算機系統的核心，它負責控制和管理整個計算機系統的軟

硬件資源，并使之協調工作。隨著計算機的功能不斷地發展和創新，計算機

系統仍然遵循馮?諾依曼提出的體系結構，操作系統的核心功能依然是對處

理器、存儲器和輸入輸出設備的管理。對操作系統的基本原理和核心功能的

學習和理解，是進一步創新的基礎。

學習本課程，使學生了解操作系統的基本概念、功能、分類和發展歷史，

掌握操作系統的使用操作方法，掌握進程和線程的管理技術，掌握處理機的

管理和調度策略，掌握存儲管理系統、文件系統和設備管理技術，在此基礎

上結合Linux的進程和存儲管理與文件系統進行深入學習與分析，掌握目前

主流操作系統Linux的基本原理和功能以及特點。使學生比較清楚地了解現

在主流操作系統的一般面貌和內部結構，為進一步學習軟、硬件技術及移植、

修改、設計和使用系統打下良好的理論基礎。通過本課程的學習，可深刻理

解計算機軟硬件如何協同工作，而且明確開發大型軟件必然需要取得操作系

統的支持，為以后設計和實現大型應用軟件和系統軟件打好基礎；具備基本

的分析問題和解決問題的能力。課程中應使學生掌握計算機操作系統的基本

理論知識，基本原理與設計分析方法，掌握基本的實驗技能。學生學習本課

程后，為后續課程《計算機網絡》、《數據庫原理》、《編譯原理》、《計算機接

口技術》、《計算機組成原理》、《嵌入式系統》、《軟件工程》的學習打下一個

堅實的基礎。

二、課程教材

教材：張堯學，史美林，張高.計算機操作系統教程（第3版）.北京：清華大

學出版社,2006

教學內容：

第一章緒論

第二章操作系統用戶界面

第三章進程管理

第四章處理機調度

第五章存儲管理

第六章進程與存儲管理示例

第七章文件系統

第八章設備管理

第九章Linux文件系統

三、課程安排

1、學時安排

總學時：56

理論學時：46

實驗學時：10

2、參考書目

[1]張堯學編.計算機操作系統教程（第三版）習題解答與實驗指導.北京:清華

大學出版社，2006

[2]湯子瀛主編.計算機操作系統（第三版）.西安:西安電子科技大學出版社，

2001

[3]AndrewS.Tanenbaum.ModernOperatingSystems,SecondEdition.Englewood

Cliffs,N.J,PrenticeHall,2001

14J屠祁等編.操作系統基礎（第三版）.北京:清華大學出版社，2000

[5]馮耀霖等編.操作系統.西安:西安電子科技大學出版社，2001

[6]左萬歷.計算機操作系統教程（第二版）.北京：高等教育出版社，2004

備課札記

第一章操作系統引論

主要內容:

本章主要介紹什么是操作系統；操作系統在計算機

系統中的地位、作用；操作系統的發展過程；操作系統

的基本特征和功能；操作系統的結構設計模式；并對操

作系統的今后發展動向和現在流行的操作系統進行介

紹。

教學安排：

理論教學；共2學時y

1.1什么是操作系統

一、系統軟件的構成

銀行系統航空訂票系統游戲｝應用程序

編譯器編輯器命令解釋器

系統程序

操作系統

機器語言

微程序硬件

物理設備

二、操作系統的作用

1、操作系統作為用戶與計算機硬件系統之間的接口

用戶通過兩種方式使用計算機：一是命令方式；二是系統

調用方式。

2、操作系統作為計算機系統資源的管理者

系統資源分為：處理機資源（一個或多個）、存儲器資源、

I/O設備資源以及信息資源。

相應操作系統的管理分為：處理機管理（進程管理）、存儲

器管理、I/O設備管理和文件管理

3、操作系統作為擴充機器一虛擬機

計算機安裝了操作系統后，易于程序設計人員在邏輯上編

寫程序，方便了用戶使用。

三、操作系統的定義

操作系統可以定義為如下3個方面的程序集合：

1、控制和管理計算機系統的硬件和軟件資源;

2、合理地組織計算機的工作流程；備課札記

3、方便用戶的使用。

1.2操作系統的發展史和分類

一、操作系統的發展簡史

二、操作系統分類

迄今為止，各類操作系統均屬于下列操作系統之一或它們的組

介.

1、單用戶（微機）操作系統；

2、批處理系統；

3、分時系統；

4、實時系統；

5、網絡操作系統；

6、分布式操作系統；

7、多處理機操作系統；

其中前4類操作系統的運行環境以單處理機系統為主，后3類以多

計算機系統為主。備課札記

1.3操作系統的特征與功能

一、操作系統的特征

1并發(Concurrence)

指宏觀上在一段時間內有多道程序在同時運行，而微觀上

這些程序是在交替執行。

*注意區分并行。并行是指兩個或多個事件在同一時刻發

生。

2^共享(Sharing)-------------

程序的并發執行使系統中的全部資源不在為某個程序所獨

占，而是有多個程序共同使用。

3、虛擬(Virtual)

多道程序設計技術把一臺物理計算機虛擬為多臺邏輯上的

計算機，使的每個用戶都感覺是“獨占”計算機。

4、異步性(Asynchronism)-------------

指一組事件在多次出現時，它們出現的時間和次序沒有一

定規律。多道程序環境下，指每道持續均以人們不可預知的速

度向前推進。

其中并發和共享是操作系統的兩個基本特征。

二、操作系統的功能

五大管理功能：

1、進程管理一處理機管理

主要任務：對處理機的分配和運行實施有效的管理。

2、存儲器管理

主要任務：對內存進行分配、保護和擴充。

3、設備管理

主要任務：根據設備分配原則對設備進行分配，使設備與

主機并行工作，為用戶提供良好的設備使用界面。

4、文件管理

主要任務：有效地管理文件的存儲空間，合理地組織和管

理文件系統，為文件訪問和文件保護提供良好的使用手段。

5、作業管理

作業：是用戶需要計算機完成任務的總和。

主要任務：根據用戶要求對作業的運行進行合理的組織和

控制。

1.4操作家統.結構設計模式

1、模塊化結構模式

備課札記

系統由許多標準的、可兼容的基本單位（模塊）構成。各模塊

功能獨立，可以單獨設計，模塊之間通過規定的接口相互調用。

系統開發周期短，但模塊之間調用關系復雜、相互依賴，使分

析、移植和維護系統較為困難。

2、層次化結構模式

把操作系統分成許多基本的模塊，并將這些模塊按照某種邏輯

關系進行分層，各層之間只能單向依賴，即上層軟件基于下層之

后，不能構成循環。

整個系統的正確性由各層次的正確性來保證，易于保證可靠性,

也便于維護和移植。

3、客戶/服務器結構模式

操作系統的基本功能構成了內核。用戶進程（即客戶進程）向

服務器進程發出請求，服務器進程完成操作后，把結果返回給客

戶進程。服務器進程運行在用戶態下而不是核心態下。

4、對象模式

利用面向對象技術設計的操作系統。

5、對稱多處理模式

操作系統工作在所有的處理機上且共享同一內存。

1.5主要操作系統的介紹

一、Windows系列

個人操作系統商用操作系統

1985Windows1.0

1987Windows2.0

1990Windows3.0

1993Windows3.XWindowsNT3.1（NT第1版）1993

WindowsNT3.5（NT第2版）1994

1995Windows95WindowsNTs.51（NT第3版）1995

WindowsNT4.0（NT第4版）1996

1998Windows98WindowsCE1998

2000WindowsMEWindows2000（NT5.0）2000

2001WindowsXP

二、UNIX系列備課札記

三、Linux發展

Linux是由LinusTorvalds于1991年開發的。

1991年9月，Linux0.0.1,很不完善。

1991年10月，Linux0.0.2,第一個“正式”版本。兩周后0.0.3。

1991年12月，Linux0.1.0,已經有許多人在上面工作了。

1994年3月，Linux1.0

1.6小結

操作系統是由一系列程序模塊組成的，它的基本功能是資源管理和方

便用戶：它管理處理機、內存、I/O設備和文件，提供用戶接口。

操作系統發展40年來，主要有兩個目的：第一，為程序開發和執行提

供一個方便的環境；第二，為保證計算機系統順利執行，操作系統對各個

計算機活動進行調度。

操作系統的形成和發展是與計算機硬件發展密切相關的。

操作系統這類系統軟件有自己的基本特征，這就是：并發、共享和異步性。

操作系統提供大量的服務，在最低層是系統調用，它允許正在運行的程序直接得到

操作系統的服務；在較高層，命令解釋程序為用戶提供請求服務的機制，而不必編寫程

序

第二章進程的描述與控制

乙￡要內容：

本章的重點在于建立進程的概念，深入理解進程動態性以及

進程間的相互作用。程序是靜態的，進程是動態的。進程有不同

的狀態，在一定的條件下發生狀態變遷，每個進程有惟一的進程

控制塊（PCB）,PCB是進程存在的惟一標志。

教學安排：

,理論教學；共6學時

2.1前趨圖和程序執行

-、前趨圖的定義

1、前趨圖

前趨圖是一個有向無環圖。有向是指結點Pi到Pj有邊，用〈Pi,Pj）表示。無

環是指在整個圖中不存在循環。

2、前趨圖的表示

使用兩個集合來表示。一個是結點集合“P”，另一個是前趨關系（有向邊）的

集合“一”。

例：

P={P1,P2,P3,P4,P5,P6,P7},

一={<P1,P2),〈Pl,P3),<P2,P4>,<P3,P5),<P4,P6),<P5,P6〉，<P6,

P7)}0

二、程序的順序執行（單道程序設計環境）

備課札記

順序程序活動有三個主要特點：

(1)程序所規定的動作在機器上嚴格地按順序執行。備課札記

(2)只有程序本身的動作才能改變程序的運行環境。

(3)程序的執行結果與程序運行的速度無關。

上述特點概括起來就是程序順序性、封閉性和可再現性。所謂順序性

就是處理機的操作嚴格按程序所規定的順序執行，即程序和機器執行程序

的操作一一對應。所謂封閉性就是指程序一旦運行起來，其計算結果僅取

決于程序本身；除了人為地改變運行狀態或機器出現故障外，沒有別的因

素能影響程序運行的過程。所謂可再現性就是當機器在同一數據集上重復

執行同一程序，每次執行都會得到相同的結果。

程序順序執行的特征：順序性、封閉性、可再現性

三、程序的并發執行(多道程序設計環境)

1、多道程序設計

在硬件引入通道和中斷機構后，使得處理機和外部設備之間，外部設

備和外部設備之間可以并行操作。這樣就引入了多道程序設計技術。

多道程序設計是在一臺計算機上同時運行兩個或更多個程序。從宏觀

上看，系統中的多個程序都同時得到執行，從微觀上看它們是在交替執行,

即程序是并發執行的。多道程序設計具有提高系統資源利用率和增加作業

吞吐量的優點。

例：(一個極端化的例子，但能說明問題)

假定有兩道作業A和B都在執行，每個作業都是執行一秒鐘，然后等

待一秒鐘，進行數據輸入，隨后再執行，再等待……一直重復60次。如果

按單道方式，先執行作業A,A作完了再執行B,那么兩個作業都運行完，

共需要4分鐘，CPU的利用率為百分之五十。如果我們采用多道程序技術

來執行同樣的作業A和B就能大大改進系統性能，作業A先運行，它運行

一秒后等待輸入。此時讓B運行，B運行一秒后等待輸入，此時恰好A輸

入完，可以運行了，……就這樣在CPU上交替地運行A和B,在這種理想

的情況下，CPU不空轉，其使用率升到百分之百，并且吞吐量也隨之增加

了。

2、并發程序的表示

為了在高級語言以及描述程序中的并發成分，Dijkstra引出了一組并

發語句Parbegin/Parendo

具體形式：

Parbegin

S1；

S2；

Sn；

parend備課札記

其中SI,S2,…，Sn表示可以并發執行的語句。

3、程序并發執行時的特征-------

1)間斷性(制約性)

并發程序在執行期間可以相互制約

2)失去封閉性

由于資源共享，所以資源狀態的改變不再取決于某一個程序，

而是由并發執行的多個程序所共同決定。

3)不可再現性

失去封閉性后，對于同一個程序來說，即使初始條件相同，但

在程序重復執行時.，因資源狀態受到其他并發程序的影響，每次

并不相同，所以其運行的結果可能不同。

四、程序并發執行的條件

程序的并發執行能有效的提高資源利用率和系統的吞吐量，但并

發執行也帶來了“不可再現性”缺點。為了去掉這一缺點，由Bernstein-------

于1966年提出了程序并發執行的條件。

1、讀集和寫集

R(Pi)={al,a2,…，am},表示程序Pi在執行期間所需參考

的所有變量的集合，稱“讀集”。

W(Pi)={bl,b2,…，bn},表示程序Pi在執行期間要參改變一

的所有變量的集合，稱“寫集”。

2、程序并發執行的條件

程序Pi和Pj若滿足下述條件，他們能并發執行，且具有“可再

現性”。

Bernstein條件：

R(Pi)nw(Pj)UR(PJ)nw(Pi)uw(Pi)nw(Pj)={}o

2.2進程的描述

一、進程的定義與特征

1、進程概念的引入

由于多道程序并發執行時共享系統資源，共同決定這些資源的狀態，

因此系統中各程序在執行過程中就出現了相互制約的關系，程序的執行出

現“走走停停”的新狀態。這些都是在程序的動態過程中發生的。而程序

本身是機器能夠翻譯或執行的一組動作或指令，是靜止的。因此，用程序

這個靜態概念已不能如實反映程序并發執行過程中的這些特征。為此，人們引入“進程”

(Process)這一概念來描述程序動態執行過程的性質。即進程就是操作系統為進行處理

機管理而引入的概念。

2、進程的定義備課札記

進程定義為：在并發環境下，程序在一個數據集合上的的執行過程。

即：進程是進程實體的運行過程。

3、進程的特征

序號特征說明

是動態概念，有一事實

上的生命期，是動態地

1動態性

產生和消亡的。

多個進程的實體能存在

2并發性于同一內存中，在一段

時間內都能運行。

作為資源申請和獨立調

獨立性

3度的基本單位。

各進程向前推進的速度

4異步性

是不可預知的。

程序段、數據段、控制

5結構性

結構和堆棧段等組成。

*小結：進程與程序的主要區別:

序號進程程序

1動態的靜態的

是獨立性的，能并發執不能并發執行

2

行

程序和進程無一一對應關系。一個程序可由多個進程

3共用；另一方面，一個進程在其活動中又可順序地執

行

4異步運行，會相互制約程序不具備此特征

二、進程的基本狀態

進程的動態性是由它的狀態和轉換體現出來的。

1、進程的基本狀態

三種基本狀態是：執行態、就緒態和阻塞態(或等待態)

(1)執行態(Running)

運行狀態是指當前進程已分配到CPU,它的程序正在處理機上執行時的狀態。

(2)就緒態(Ready)

就緒狀態是指進程已具備運行條件，但因為其它進程正占用CPU,所

以暫時不能運行而等待分配CPU的狀態。備課札記

(3)阻塞態(Blocked)------------

阻塞態是指進程因等待某種事件發生而暫時不能運行的狀態。

進程的狀態及其轉換：如下圖

2、進程狀態的轉換

(1)就緒一一執行

處于就緒狀態的進程被調度程序選中，分配到CPU后，該進程的狀態

就由就緒態變為運行態。

(2)執行一一阻塞

正在運行的進程因某個條件未滿足而放棄對CPU的占用，這個進程的

狀態就由運行態變為阻塞態。

(3)阻塞一一就緒

處于阻塞狀態的進程所等待事件發生了，系統就把該進程的狀態由阻

塞態變為就緒態。

(4)執行----就緒

正在運行的進程如用完了本次分配給它的CPU時間片，它就得從CPU

上退下來，暫停運行。該進程狀態就由運行態變為就緒態.

所等待事件發生

(如I/O完成)

*小結：進程基本狀態

執行態：此時正用CPU；

就緒態：可運行，但未分到CPU；

阻塞態：不能運行，等待某個外部事件發生。

在一定條件下，進程狀態才發生轉換

三、進程的組成

1、進程的組成

進程實體通常由程序、數據集合和PCB這三部分組成。進程的這三部分構成進程在

系統中的存在和活動的實體，有時也統稱為“進程映象”。

__________備課札記

PCB

程序段

數據段

2、進程控制塊的組成（ProcessControlBlock,簡稱PCB）

進程控制塊有時也稱進程描述塊（ProcessDescriptor）它是進程組成中

最關鍵的部分。其中含有進程描述信息和控制信息，是進程動態性的集中

反映，它是系統對進程進行識別和控制的依據。用來描述進程當前的狀態、

本身的特性的數據結構被稱為進程控制塊。

一般來說，進程控制塊包括如下內容：

1）進程標識符信息

①外部標識符：進程名；

②內部標識符：進程的序號（PID）；

③其他：族系關系，UID,GID,PPID

2）處理機狀態信息

當進程進行切換時一，需要保護的信息包括：通用寄存器、指令計數器、

程序狀態字（PSW）和用戶棧指針。

3）進程調度信息

進程狀態、進程優先權、調度所需的其它信息和事件（原因）。

4）進程控制信息

程序和數據的存儲情況；同步和通信機制；資源清單和鏈接指針。

3、進程控制塊的作用：

進程控制塊是進程組成中最關鍵的部分。每個進程有惟一的進程控制

塊。操作系統根據PCB對進程實施控制和管理。

進程的動態、并發等特征是利用PCB表現出來的。

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

4、PCB的組織方式

有鏈接方式和索引方式兩種。

1）鏈接方式

把具有相同狀態的PCB,用其中的鏈接指針，鏈接成一個隊列。如教

材P45圖2-7所示。

2）索引方式

系統根據所有進程的狀態，建立幾張索引表。索引表目中，記錄相應狀態的PCB在

PCB表中甲地址。每張索引表的地址放在相應的專用單元中。如教材P46

圖2-8所示。備課札記

2.3進程控制--------

為了防止用戶程序對系統程序的破壞，系統提供了不同的處理機執行

狀態，通常分為系統態（也稱做管理態）和用戶態兩種。

1、系統態：當操作系統程序執行時，處理機處于系統態。即內核運行

在系統態下。

2、用戶態：用戶程序在用戶態下執行。^^3

—＞操作系統內核（Kernel）

1、操作系統內核

內核是計算機硬件的第一層擴充軟件。它們常住內存，對進程進行控

制、對存儲器進行管理以及對設備進行管理。

內核一般由中斷處理程序、各種常用設備的驅動程序以及一些運行頻

率較高的模塊（如時鐘管理、進程調度等）組成。

2、內核的功能

1）支撐功能

?中斷管理

是內核的最基本功能。是整個操作系統賴以活動的基礎。

?時鐘管理

是內核的基本功能。操作系統中的許多活動也都需要它。

?原語操作

所謂原語（Primitive）是機器指令的延伸，往往是為了完成某些特

定的功能而編制的一段系統程序。為保證操作的正確性，在許多機

器中規定，執行原語操作時，要屏蔽中斷，以保證操作的不可分割

性，即一個操作中的所有動作要么全做，要么全不做。操作系統中

完成某些基本操作時，往往利用原語操作來實現。

2）資源管理功能

?進程管理

由于進程管理的運行頻率高，所以這些模塊的全部或部分功能都放

一內核'中。

?存儲器管理

目的是保證存儲器管理的運行速度。

?設備管理

設備管理和設備密切相關，因此其中一大部分也放在內核中。

二、進程的控制

1、進程圖

進程圖是用來描述進程家族關系的有向樹。由父進程創建子進程，子

備課札記

進程再創建子進程，……,從而構成一棵樹型的進程圖。如教材P48圖2-90

2、進程控制原語

內核中有很多原語，如創建進程、終止進程、阻塞進程等。

1）進程創建

?引起進程創建的事件

用戶登錄、作業調度、提供服務和應用請求。

?進程創建原語的主要操作過程

（1）申請一個空閑的PCB；

（2）為新進程分配資源；

（3）將進程的PCB初始化；

（4）將新進程加到就緒隊列中。

2）進程終止

?引起進程終止的事件

正常終止、異常結束和外界干預。

?終止進程的主要操作過程

（1）從系統的PCB表中找到指定進程PCB；

（2）回收該進程所占用的全部資源；

（3）若該進程還有子孫進程，則還要終止其所有子孫進程，回收它們

所占用的全部資源；

（4）釋放被終止進程的PCB,并從原來隊列中摘走。

3）進程阻塞

正在運行的進程通過調用阻塞原語主動地把自己阻塞。

?引起進程阻塞的事件

請求系統服務、啟動某種操作、新數據尚未到達和無新工作可做。

?阻塞的過程

（1）立即停止當前進程的執行；

（2）將現行進程的CPU現場送到該進程的PCB現場保護區中保存起

來，以便將來重新運行時恢復此時的現場。

（3）把該進程PCB中的現行狀態由“運行”改為阻塞，把它插入到

具有相同事件的阻塞隊列中。

（4）然后轉到進程調度程序，重新從就緒隊列中挑選一個合適進程投

入運行。

4）進程喚醒

喚醒原語執行過程：

（1）首先把被阻塞進程從相應的阻塞隊列中摘下；

（2）將現行狀態改為就緒態，然后把該進程插入到就緒隊列中；

（3）如果被喚醒進程比運行進程有更高的優先級，則設置重新調度標備課札記

,志O

阻塞原語與喚醒原語恰好是--對相反的原語：調用前者（阻塞原語）

是自己去睡眠，調用后者（喚醒原語）是把“別人”喚醒。使用時也要成

對，前邊有睡的，后邊有叫醒的。否則，前者就要“長眠”了。如同兩個

士兵輪流站崗值班和睡覺休息。相關者喚醒，自己不能喚醒自己。

2.4線程的基本概念

一、線程的引入

1、處理機分配單位的演變

進程的兩個基本屬性：一是擁有資源的獨立單位；二是獨立調度和分

配的基本單位。由于進程是一個資源的擁有者，所以進程在創建、終止和

切換中，系統必須為之付出較大的時空開銷。于是想把這兩個屬性分開，

即對擁有資源的基本單位，不進行頻繁的切換；而對于調度和分配的基本

單位，使其輕裝運行。

3

2>

^^

多進程、每個進程一個線程多進程、每個進程多個線程

2、線程的定義

線程是進程中的一個實體，是被系統獨立調度和分配的基本單位。又

稱為輕型進程。

二、線程與進程的比較

1、單線程和多線程的進程模型

單線程進程模式多線程進程模式

線程線程備課札記

進程用戶棧進程控制塊控制塊

控制塊控制塊用戶棧用戶棧

用戶內核棧用戶

內核棧內核棧

地址空間地址空間

2、線線程線程

程與進程

的比較

性能進程線程

進程內的線程切

換，不會引起進程

調度切換。當不同進程調度的基本單位

內的線程進行切換

時，進程進行切換。

并發性可以可以

擁有資源的獨立單僅擁有能運行的基

擁有資源

位本資源

系統開銷大小

三、線程的分類

線程分為用戶級線程（ULT）和內核支持線程（KLT）。

1、用戶級線程（ULT）

線程僅存在用戶級中，對于線程的創建、撤消和切換，都不利用系統

調用來實現,因而這種線程與內核無關。

2、內核支持線程（KLT）

又稱輕便進程。線程的實現依賴內核

用戶空間備課札記

內核空間

2.5小結

進程可以理解為：”程序在并發環境中的執行過程。”它最基本的特征

是并發性和動態性，一個進程至少應有三種狀態，它們在一定條件下相互

轉化。

每一個進程都有惟一的進程控制塊（PCB）,它是進程存在的惟一標志。

PCB表的物理組織方式有若干種，最常見的是線性方式、鏈接方式和

索引方式。

第三章進程的同步與通信

主要內容：

本章將在系統動態模型基礎上討論進程（線程）間的

同步和互斥、進程通信以及操作系統提供的相應工具。

教學安排：

理論教學；共6學時

3.1進程同步的基本概念

一、進程的同步與互斥

進程間的相互關系分為同步關系和互斥關系。

1、同步（直接制約關系）

同步是指為完成同一任務的伙伴進程間，因為需要在某些位置上協調

它們的工作而相互等待、相互交換信息所產生的制約的關系。

兩者要步調協調一致，是同步關系，同時又相互牽制。

2、互斥（間接制約關系）

兩個進程在邏輯上本來完全獨立，毫無關系，只是由于競爭同一個物理資源而相互

制約。攵

二、臨界資源和臨界區備課札圮

1、臨界區的定義

一次僅允許一個進程使用的這類資源稱為臨界資源，在每個進程中訪

問臨界資源的那段程序區叫臨界區。

訪問臨界資源的程序結構描述：

repeat

Entrysection

Criticalsection；

Exitsection

Remaindersection；

Untilfalse；

2、互斥準則

?空閑讓進

只要臨界資源空閑，允許請求者使用。

?忙則等待

當臨界資源正被進程訪問，其他請求則等待，保證臨界資源的

互斥訪問。

?有限等待

讓等待進入臨界資源的進程，在等待一段有限的時間后進入臨

界區，以免出現“死等”。

?讓權等待

當請求進程不能進入臨界區時，應立即釋放處理機，以免進程

陷入“忙等”。

三、利用軟件方法解決進程互斥問題

使用軟件設計方法，在Entrycode和exitcode位置上設計相應

代碼，實現對臨界區的互斥執行。

在進行下面的講解前，首先假設進程Pi（i=0,1）和Pj（j=l-i）。

算法］一嚴格輪換法

設置整形變量turn（令牌），用turn=i還是j來區分進入臨界區

的進程。

Pi進程算法的描述

repeat

備課札記

WhileturnWidoskip；

Criticalsection；

Turn=j；

noncriticalsection；

untilfalse；

缺點：如果初值tum=i；則算法嚴格按Pi-Pj輪換使用臨界資

源，即使某時刻臨界區空閑（準則1空閑讓進）。

算法2

為了避免出現忙等的情況，使用數組flag來記錄各進程使用臨

界區的情況。

Varflag：array[O..l]ofBoolean＞；

Flag[i]=true表示進程Pi正在執行其臨界區。

Pi進程算法的描述

repeat

Whileflag[j]doskip；

Flag[i]=true；

Criticalsection；

Flag[i]=false；

noncriticalsection；

untilfalse；

缺點：雖然解決了算法1中的忙等，但卻不能保證臨界資源的

互斥使用（準則2忙則等待）。

算法3

為了解決while語句和Hag]]設置語句之間為另一進程執行留

有可乘之機的情況，交換這兩個語句執行的順序。

Pi進程算法的描述

repeat

Flag[i]=true；

Whileflag[j]doskip；

Criticalsection；

Flag[i]=false；

noncriticalsection；備課札記

untilfalse；

缺點：雖然解決了算法2中的不能互斥使用的情況，但卻導致

了都不能進入的情況(準則1空閑讓進)。

算法4

為了解決上述問題，同時引入兩個變量，一個Hag[i]表示Pi進

程要求進入或正在執行臨界區，另一個turn表示要求進入的進程編

號。

Pi進程算法的描述

repeat

Flag[i]=true；tum=j；

Whileflag[j]andturn=jdoskip；

Flag[i]=false；

Criticalsection；

noncriticalsection；

untilfalse；

缺點：能保證互斥使用，但卻導致了浪費處理機資源的情況(準

則4讓權等待)。

四、利用硬件方法解決進程互斥問題

使用硬件指令保證其操作的原子性，但不能滿足“讓權等待”。

1、Test—and一Set指令實現互斥

1)Test—and-Set指令功能

functionTS(varlock：boolean)：boolean

begin

TS=lock；

Lock=true；

End

LOCK：TRUE表示在使用；FALSE表示空閑。TS是一條指令,

執行過程，不會被打斷。

2)利用TS實現進程互斥

repeat

WhileTS(lock)doskip；

Criticalsection；

lock=false；

noncriticalsection；備課札記

untilfalse；

2、利用SWAP指令實現進程互斥

1)SWAP指令功能

procedureSWAP(vara,b：boolean)

vartemp：boolean；

begin

temp=a；

a=b；

b=temp；

End

交換變量a和b的值。

2)利用SWAP實現進程互斥

Key=true；

Whilekeydoswap(key,lock)；

repeat

Criticalsection；

lock=false；

noncriticalsection；

untilfalse；

3.2信號量機制

信號量是操作系統解決進程互斥與同步的工程。

一、整型信號量機制

1、整型信號量

定義：把信號量定義為一個整型量，除初始化外，僅能通過兩個原子

操作WAIT和SIGNAL來訪問。

WAIT和SIGNAL的描述：

WAIT(S)：WHILE(S〈=0〉DOSKIP；

S=S-1；

SIGNAL(S)：S=S+1；

小結：

?S是正數，表示資源的個數。

?WAIT和SIGNAL是原子操作。

備課札記

?原子操作的實現一般采用屏蔽中斷(適用于單處理機)或利用

TS和SWAP硬指令(適用于多處理機)實現。

?仍然不能實現讓權等待。

2、利用整型信號量實現互斥問題

repeat

WAIT(S)；______

Criticalsection；

SIGNAL(S)；

noncriticalsection；

untilfalse；

3、利用整型信號量描述前趨關系

Vara,b,c：semaphore=0,0,0；

Parbegin

BeginSI；SIGNAL(a)；end；

BeginS2；SIGNAL(b)；end；

BeginWAIT(a)；WAIT(b)；S3；SIGNAL(c)；end；

BeginWAIT(c)；S4；end；

parend

二、記錄型信號量機制

1、定義

typesemaphore=record

value：integer；

L：Listofprocess；

End；

其中L表示等待信號量進程的鏈表。

S取值為負、零和正。負和零表示阻塞進程個數，正表示現有資源的個數。

2、原子操作

WAIT(S)：S.value=S.value-1;備課札記

IfS.VALUE<0THENBLOCK(S.L);

SIGNAL(S):S.VALUE=S.VALUE+1;

IfS.VALUE<=0THENWAKEUP(S.L);

三、信號量集機制

當進程互斥使用多個臨界資源時，可能出現死鎖問題(在第四章中介

紹)。為了解決上述問題，引入了信號量集的技術。

1、AND型信號量集機制

就是將進程在整個運行過程中所需要的所有臨界資源，一次性的全部

分配給它，待進程使用完后一次性的釋放，只要尚有一個資源不能分配給一

它，則全部不能進行分配。

2、兩個原子操作

SWAIT(SI,Tl,D1,...?Sn,Tn,Dn)；

其中Si表示某類資源數，Ti表示分配下限，Di表一次分配的個數。

SSIGNAL(SI,D1,...?Sn,Dn)；

其中Si表示某類資源數，Di表示回收的個數。

3.3經典進程同步問題

一、生產者——消費者問題

1、問題的提出

2、問題的解決

varmutex,full,empty：semaphore=1,0,n；

buff：array[0..n-lJofitem；

in,out：integer=0,0；

begin

parbegin備課札記

producer()；

consumer0；

parend

end

procedureproducer()procedureconsumer()

beginbegin—

repeatrepeat

produceaniteminnextp；wait(full)；

wait(empty)；wait(mutex)；

wait(mutex)；nextc=buff[outj；

buff[in]=nextp；out=(out+l)modn；

in=(in+1)modn；signal(mutex)；

signal(mutex)；signal(empty)；

signal(full)；consumetheiteminnextc；

untilfalse；untilfalse；

endend

3、小結________

MUTEX用于控制互斥訪緩存池，問初值為1,表示消費者進程和生產

者進程在對緩存池使用時，按照互斥方式。

FULL用于同步控制，初值為0,表示當前緩存池中“滿”緩存區數。

EMPTY用于同步控制，初值為N,表示當前緩存池中“空”緩存區數。

不論是互斥還是同步，WAIT和SIGNAL操作都配對出現。

WAIT操作不能顛倒，SIGNAL操作可以。

二、讀者——寫者問題

1、問題描述

有兩種情況：一是READER有較高的優先權；二是WRITER有較

高的優先權。下面描述的是READER有較高優先權的情況。

1）如果當前無人訪問數據，無論READER或WRITER都可直接進

入訪問。

2）如果已有一個READER正在訪問數據，那么其它欲訪問數據的

READER可直接進行訪問，而當前欲訪問數據的WRITER則必須無條件等待。

3）若某個WRITER正在訪問數據，則當前欲訪問數據的READER和WRITER

均須等待。

4）當最后一個結束訪問數據的READER發現有WRITER正在等待

時，則將其中的一個喚醒。備課札記

5）當某個WRITER結束訪問數據時發現存在等待者，則按FIFO或

其他原則喚醒READER和WRITERo

2、,可題解決

varmutex,wmt：semaphore=1,1；

rcount：integer=0；

begin

parbegin

reader()；

writer0；

parend

end

procedurereader()procedurewriter()

beginbegin

repeatrepeat

wait(mutex)；wait(wmt)；

rcount=rcount+l；writingisperformed；

ifrcount==1wait(wmt)；signal(wmt)；

signal(mutex)；untilfalse；

readingisperformed；end

wait(mutex)；

rcount=rcount-l；

ifrcount==0signal(wmt)；

signal(mutex)；

untilfalse；

end

三、哲學家就餐問題

1、問題描述

有5位哲學家，他們的生活方式是交替進行思考和進餐。他們共用一

張圓桌，分別坐在5把椅子上，有5只碗和5支筷子，平時哲學家進行思

考，饑餓時便試圖取其左、右兩支筷子，取道后開始進餐，進餐后放下筷

子又繼續思考。

2、問題解決

varmutex：array[0..4]ofsemaphore=1,1,1,1,1；

begin

parbegin備課札記

p(0)；

p(1);

p(2)；

p(3)；

p(4)；

parend

end

procedurep(vari：integer)

begin