材第機攘6f.餞

（專科）

賈洞

2005

第一章操作系統概述

教學內容

1.操作系統概況

2.操作系統的形成和發展

3.操作系統的基本類型

4.操作系統的服務和功能

5.操作系統的結構

教學要求

了解操作系統的形成過程，建立起操作系統的整體概念；熟悉操作系統的基本類型和服

務方式；掌握操作系統的定義、特征和功能。

自學要點

操作系統在計算機系統中的作用；各類操作系統的特征，操作系統的功能及研究操作系

統的幾種觀點。重點是操作系統的基本概念；操作系統的基本類型及特點。

學時分配

3學時（自學學時：6學時）

1.1操作系統概況

?操作系統的虛擬機觀點

?操作系統是添加在硬件上的第一層軟件,是對硬件功能的首次擴充和延伸。

?軟件：系統軟件和應用軟件。系統軟件用來管理計算機本身及應用軟件；應用軟件用

來完成用戶所要求的實際任務。

?硬件：指未配置任何軟件的計算機。裸機又分為物理器件、微程序與機器語言三個層

次。

?操作系統的資源管理觀點

?資源分硬件資源和軟件資源。

?硬件資源是計算機硬件系統的總和，包括中央處理機、主/輔助存儲器、輸入/輸出設

備等。

?軟件資源是系統中各種程序和數據的總和，這些程序和數據均以文件的形式保存在計

算機系統中。

?操作系統的用戶服務觀點

?操作系統是用戶與計算機之間的一個接口。它為用戶提供了兩種使用操作系統的方式:

命令方式、系統調用方式。

?命令方式：是指操作系統提供了一組聯機，用戶通過鍵盤或鼠標使用這些命令，并直

接操縱計算機系統。

?系統調用方式：是指操作系統提供了?組系統調用，用戶可在自己的程序中通過調用

來相應的系統操縱計算機。

?定義

?操作系統：是計算機系統中的一個系統軟件，用來管理和控制計算機系統中的軟硬件

資源，合理地組織計算機工作流程，提供用戶和計算機之間的軟件接口，方便用戶使用計算

機。

?操作系統目標

?目前存在著多種類型的操作系統，不同類型的操作系統其目標各有側重。但?般來說

都包括：方便性、有效性、可擴充性和開放性。

?操作系統的特征

?并發：指兩個或兩個以上事件在同一時間間隔內發生。

?共享：指系統中硬件和軟件資源可為多個用戶同時使用（互斥共享、同時訪問）

?虛擬：指物理上的一個實體變成邏輯上的多個對應物。

?異步性：指內存中的多個進程均按照各自獨立的、不可預知的速度向前推進。

1.2操作系統的形成和發展

?操作系統的歷史

?操作系統的發展經歷了以下幾個階段：手工存在階段（無操作系統）、脫機輸入輸出

技術階段、批處理技術階段、多道程序設計技術階段。

1.3操作系統的基本類型

?分類

?最常用分類方法（按照操作系統的用戶服務方式分）主要有：多道批處理系統；分時

系統；實時系統。其它操作系統還包括：通用操作系統、網絡操作系統、并發操作系統、面

向對象操作系統。

?多道批處理系統

?運行方式（了解）

?特征：多道性、無序性、調度性

?優缺點：優點：資源利用率高，系統吞吐量大。缺點：平均周轉時間長、無交互能力。

?在設計批處理系統時，首先要考慮的是周轉時間和系統的吞吐量。

?分時系統

?實現基本方法；設立時間片

?特性：多路性、獨立性、及時性、交互性。

?響應時間：指從終端用戶發出一條命令開始，到系統處理完這條命令并做出回答為止

所需的最大時間間隔。

?影響響應時間的因素：系統開銷、用戶數目、時間片、信息對換量。

?改善響應時間的辦法：一種可行的辦法是減少信息對換量。而減少信息對換量可采用

重入碼技術和虛擬存儲技術。

?設計分時操作系統時，首先要考慮的是交互性和響應時間。

?實時系統

?定義：是指系統對特定輸入做出反應速度足以控制發出實時信號的對象的一種操作系

統。

?實時系統的類型：1實時控制系統；2實時信息處理系統

?特征：多路性、獨立性、及時性、交互性、高可靠性。

?設計實時操作系統時，首先要考慮的是實時性和可靠性。

?微機操作系統

?單用戶單任務OS：只允許一個用戶上機、且只允許用戶程序作為一個任務運行。最

具代表性的是CP/M和MS-DOSo

?單用戶多任務OS：只允許一個用戶上機、但允許將一個用戶程序分為若干個任務，

使它們并發執行。最具代表性的是OS/2和MS-WINDOWS?

?多用戶多任務OS：允許多個用戶通過各自的終端使用同一臺主機，共享主機的各類

資源，同時用戶程序又可進一步分成兒個任務，使它們并發執行。最具代表性的是UNIXOSo

1.4操作系統的服務與功能

?操作系統的服務

?操作系統公共服務類型：程序執行、I/O操作、文件系統管理、通信、資源分配、

差錯處理

?操作系統的服務方式：系統調用、系統程序。

?系統調用的類型：進程管理、設備管理、文件管理、信息維護和通訊五大類。

?操作系統功能

?從資源管理和用戶接口的觀點看，操作系統的基本功能為：①處理機管理；②存儲管

理；③設備管理；④信息管理（文件系統管理）；⑤用戶接口。其中硬件資源為處理機、存

儲器和設備三類，軟件資源為信息或文件（程序和數據的通稱）。

?用戶接口

?命令接口：又分聯機命令接口：為聯機用戶提供的，由一組鍵盤命令和命令解釋程序

組成；脫機命令接口：為批處理作業的用戶提供，由一組作業控制語言JCLOobcontrol

language）組成。

?程序接U：是為用戶程序在運行過程中訪問系統資源而設定的，也是用戶取得操作系

統服務的唯一途徑，由一組系統調用組成。

?圖形接口

?處理機管理

?處理機管理功能可歸結為進程管理，主要功能：進程控制；進程同步；進程通訊；進

程調度。

?存儲管理

?存儲管理應具備的功能，為：內存分配：內存保護；地址映射；內存擴充。

?設備管理

?設備管理應具備的功能，為：緩沖管理；設備分配：設備處理；虛擬設備管理。

?文件管理

?文件管理的主要功能包括：文件存儲空間管理；目錄管理；文件讀寫管理；文件保護；

文件系統的安全性；文件接口。

1.5操作系統結構

?分類

?從操作系統的內部結構來看，操作系統可分為三種主要類型：整體式系統（無結構）；

層次式系統；客戶/服務器系統。

?整體式結構

?整個系統是?堆過程的集合，每一過程都有一個定義好的接口，包括入口參數和返回

值，過程間可以相互調用而不受約束，UNIX的系統核心層是典型的沒有層次的無結構型。

?層次式系統

?按照操作系統中模塊的功能和相互依存關系把它們劃分為若干個層次：

?最底層：OS對象；?中間層：對對象進行管理和控制的軟件集合；

?最高層：OS提供給用戶使用的用戶接口。

?客戶/服務器系統

?在客戶/服務器結構中，需要把操作系統的服務功能分為若干個服務器，而用戶進程

則稱為客戶進程。操作系統由微內核和核外服務器進程組成。微內核提供最基本的、最必要

的服務，而OS的其他功能山運行在核外的服務器完成。

?主要優點：提高了系統的可靠性；適合于分布式系統中的應用。

練習題:

1：下面8個系統中，必須是實時操作系統的有——個。

1計算機輔助設計系統；2航空定票系統；3過程控制系統；4機器翻譯系統；

5辦公自動化系統；6計算機激光照排系統；7情報檢索系統；8導彈的制導系統

2：在分時系統中為使多個用戶能夠同時與系統交互，最關鍵的問題是—⑴當用戶數目

為100時，為保證響應時間不超過2秒，此時時間片最大應為一⑵

(1)：A.計算機具有足夠高的運行速度B.內存容量應足夠大C.系統能及時地接收多個

用戶輸入D.能在一最短的時間內，使所有的用戶都能運行E.能快速地進行內外存交換

(2)：A.IOmsB.20msC.50msD.100msE.200ms

3：OS/2操作系統是由—⑴—開發的，它屬于—⑵—類操作系統；UNIX操作系統是由—⑶

_推出的，它屬于一⑷一類操作系統。

(1)、⑶：A.IBM公司B.Microsoft公司C.Microsofi和IBM聯合D.Bell實驗室

⑵、(4)：A,單用戶單任務B.單用戶多任務C.多處理機D.多用戶多任務

4：分時系統形成和發展的主要動力是什么？

5：操作系統中實現虛擬的關鍵技術是什么？并加以說明。

6：設計實時環境的操作系統的主要困難是什么？

7：一個分層結構操作系統有：i裸機；j用戶；kCPU調度和P、V操作；1文件管理；m

作業管理；n內存管理：。設備管理；p命令管理等組成，請按層次結構的原則從內到外

將各部分重新排列。

8：操作系統是一種—⑴根據其服務對象，常用的單處理機操作系統可分為三種類型：

允許多個用戶在其終端上同時交互方式使用計算機的操作系統，稱為—⑵允許多用戶將

若干個作業提交給計算機系統集中處理的操作系統稱為—⑶在的控制下，計算機

系統能及時處理由過程控制反饋的數據，并做出響應；設計⑷時，首先應考慮系統的—⑸

(1):A.通用軟件B.應用軟件C.系統軟件D.操作的軟件

⑵-⑷：A.批處理操作系統B.分時操作系統C.實時操作系統D.微機操作系統

E.多處理機操作系統F.分布式操作系統G.網絡操作系統

⑸：A.可靠性和靈活性B.實時性和可靠性C.優先權分配D.時間片輪轉

E.短作業優先F.時間片加分配

9：操作系統的基本特征有哪些？

10：什么是操作系統？

11：操作系統有哪幾種基本類型？它們的主要特征有那些？

12：分時系統的響應時間是什么？它與哪些因素有關？

13：實時系統可分哪幾類？

14：多道程序和多重處理有何區別？

參考答案:

1解：1,2,3,7,8

2解：1D;2B

3解:1c;2b;3d;4d

4答：主要動力是為了更好地滿足用戶的需要。主要表現在：1)縮短了作業的周轉時間；2)

提供人機交互能力；3)多個用戶共享?臺計算機。

(批處理系統的主要推動力是不斷提高系統的資源利用率和提高系統的吞吐量。)

5答：是分時技術。例如，將一臺物理處理機虛擬為多臺邏輯上的處理機，是靠多道程序分

時地使用同一臺物理處理機來實現的。微觀上，該處理機在每一時刻只運行一道程序，它們

分時地運行；然而在宏觀上，系統中確有幾道程序在同時運行，從而給用戶的感覺是系統中

同時同時有多臺處理機在為其中的每一道程序服務，顯然用戶所感覺到的處理機并不實際存

在。

6答：是在實時環境規定的時間限額內對用戶作出相應的反應，否則就有可能導致系統的崩

潰。因此，在設計時必須保證所采用的調度策略及相關技術不會使響應時間超過實時環境所

規定的時間限額。

7答：重新排列后順序為：i裸機；kCPU調度和P、V操作；n內存管理；m作業管理;

。設備管理；1文件管理；p命令管理。

8解：(DC(2)B(3)A(4)C(5)B

9答：1并發：指兩個或兩個以上事件在同一時間間隔內發生；2共享：指系統中硬件和軟

件資源可為多個用戶同時使用(互斥共享、同時訪問)；3虛擬：指物理上的一個實體變成

邏輯上的多個時應物：4異步性：指內存中的多個進程均按照各自獨立的、不可預知的速度

向前推進。10答：操作系統是計算機系統中的一個系統軟件，用來管理和控制計算機系統

中的軟硬件資源，合理地組織計算機工作流程，提供用戶和計算機之間的軟件接口，方便用

戶使用計算機。

11答；操作系統的基本類型有：1多道批處理系統；2分時系統；3實時系統。其中多道

批處理系統的特征：多道性、無序性、調度性；分時系統的特征：多路性、獨立性、及時性、

交互性。實時系統的特征：多路性、獨立性、及時性、交互性、高可靠性。

12答：分時系統的響應時間指從終端用戶發出一條命令開始，到系統處理完這條命令并做

出回答為止所需的最大時間間隔。它與下列因素有：系統開銷、用戶數目、時間片、信息對

換量。

13答：實時系統的類型：1實時控制系統；2實時信息處理系統

14答：多道程序multiprogramming是作業之間自動調度執行、共享系統資源，并不是真正

地同時執行多個作業：而多重處理multiprocessing系統配置多個CPU,能真正同時執行多道

程序。要有效使用多重處理，必須采用多道程序設計技術，而多道程序設計原則上不一定要

求多重處理系統的支持。

第二章用戶接口

教學內容

1.作業的基本概念

2.用戶接口概述

3.命令接口

4.程序接口

5.圖形接口

教學要求

了解作業的基本概念；了解操作系統提供給用戶的接口類型及各種接口的實現方法；熟

悉命令接口在不同工作方式下的主要功能，作業和作業管理的基本概念；掌握系統調用的定

義及其執行過程。

自學要點

重點是作業的基本概念和建立；用戶接口的概念和類型；系統調用的概念和過程

學時分配

3學時（自學學時：6學時）

2.1作業的基本概念

?作業

?作業（Job）是用戶提交給計算機進行加工的一個任務，由三部分組成，即程序、數據

及作業說明書。通常一個作業又可分為若干個順序處理的作業步，其中每個作業步又可細分

為若干個作業步任務。

?作業的類型

?根據調度和控制的需要，可對作業進行分類。

?從調度的角度，可把作業分成：①計算型作業，指任務中包含大量的計算，而其I/O

較少的作業，如通常的科學計算；②I/O型作業，要求少量的計算而需大量I/O的作業，如

通常的事務處理。

?從控制的角度，可把作業分成：①脫機作業，在整個作業的運行過程中，只需根據作

業說明書中的說明對作業進行控制，脫機作業通常是在批處理操作環境下運行，故也稱為批

量型作業；②聯機作業，通常是用鍵盤命令直接控制作業的運行，聯機作業通常在分時操作

環境下運行，故也稱為終端型作業。

?作業的建立過程

?一個作業的建立過程包括兩個子過程，即作業的輸入方式和JCB的建立。

?作業的輸入指將作業的程序、數據和作業說明書從輸入設備（如鍵盤）輸入到外存，

并形成有關的初始信息。其輸入方式主要有：①聯機輸入方式②脫機輸入方式③直接耦合方

式④SPOOLing系統⑤網絡輸入方式。

?作業的組織

?程序、數據和作業說明書。程序和數據完成用戶所要求的業務處理工作的具體內容,

作業處理的說明是用戶要求計算機所作的步驟。

?作業的狀態及其轉換

?作業從提交給系統直到它完成后離開系統前的整個活動過程，可分為：提交狀態；后

備狀態；運行狀態；完成狀態。

2.2用戶接口概述

?操作系統是用戶和計算機之間的接口，用戶通過操作系統的幫助可以快速、有效和安

全可靠地使用計算機各類資源。通常操作系統為用戶控制其作業提供命令接口、程序接口和

圖形接口。

2.3命令接口

?命令接口

?命令接口是操作系統為用戶提供的各種操作命令，用戶利用它來組織作業的工作流程

和控制作業的運行。類型有：脫機命令接口聯機命令接口。

?脫機命令接口

?脫機命令接口是操作系統為脫機工作方式下的用戶提供的?種接口。利用JCL語言將

用戶對作業的控制要求寫成作業控制卡或作業說明書的形式。

?JCL：作業控制語言，是種用來表達申請作業控制意圖和步驟的語言。JCL的語句

就是作業控制命令。不同批處理提供不同的JCL。

?聯機命令接口

?聯機命令接口指用戶通過控制臺或終端，采用人一機會話的方式，直接控制作業的運

行。又分為：1鍵盤命令方式；2命令文件方式。

?鍵盤命令方式：是通過逐條輸入鍵盤命令語句，經解釋后執行，以控制作業運行的一

種方式，通常包括：1系統管理；2環境設置；3編輯修改、編譯、連接和運行命令；4文

件管理命令；5操作員專用命令（執行權限管理）；6通信；7資源要求。

?命令文件方式：是用鍵盤命令語言編寫的?個鍵盤命令語言程序——命令文件。一旦

建立命令文件后，系統可連續執行若干條命令并且可以多次重復執行。命令文件中可以進行

參數傳遞，也可以嵌套的方式調用其他的命令文件。

2.4程序接口（系統調用）

?程序接口

?程序接口是OS專門為用戶程序設置的，也是用戶程序取得OS服務的唯一途徑，程序

接口通常由各種各樣的系統調用所組成。

?系統調用

?系統調用的基本概念：是OS提供給編程人員的唯一接口，是由操作系統中的一段程

序來完成特定功能的，屬于一種特殊的過程調用。有的計算機系統中，把它稱為廣義指令。

?調用的方式：采用訪管方式來實現。通過產生一個訪管中斷，使處理機山目態（用戶

態）轉為管態（系統態）。（當中央處理器處于目態時不允許執行特權指令；而處于管態時可

這些包括特權指令在內的一切機器指令）

?常用的訪管指令的形式：SVCN

?系統調用與一般過程調用的主要區別

?系統調用本質上一種過程調用，但它是一種特殊的過程調用，主要區別有：

①運行狀態不同：一般的過程調用，其調用和被調用過程或者都是子程序，或者都是

系統程序，故運行在同系統狀態下：系統態或用戶態。系統調用的調用過程是用戶程序，

它運行在用戶態；其被調用過程是系統過程，運行在系統態下。

②進入的方式不同：一般過程調用可以直接通過過程調用語句將控制轉移到被調用的

過程；而執行系統調用時，由于調用和被調用過程處于不同的系統狀態，必須通過訪管中斷

進入。

③代碼層次不同：一般的過程調用中的被調用程序是用戶級程序，而系統調用是操作

系統中的代碼程序，是系統級程序。

?系統調用的實現過程

?用戶在源程序中使用系統調用，給出系統調用名和函數后，即產生i條相應的陷入指

令，通過陷入處理機制調用服務，引起處理機中斷，然后保護處理機現場，取系統調用功能

號并尋找子程序入口，通過入口地址表來調用系統子程序。執行完畢后，退出中斷，返回到

用戶程序的斷點，恢復現場，繼續執行用戶程序。

2.5圖形接口

?圖形用戶接口?圖形用戶接口的引入：主要是在使用命令接口時，要求用戶熟悉并記住

系統所提供各種命令的名稱、功能和格式；此外還要求用戶按照規定的格式準確的鍵入，這

不僅不方便，而且需花費較多的時間；同時利用命令接口來進行文字處理、圖形的繪制和編

輯也是極為不便的。

?圖形用戶接口元素：窗口；圖標；菜單；對話框

?圖形用戶接口元素的基本操作：菜單操作；窗口操作；對話框操作。

練習題：

1：在分時系統中是否應設置作業調度?為什么?實時系統呢？

2：為什么說SPOOLING對批處理（多道程序）是必需的？對分時系統也是需要的嗎？

3：作業控制方式可分為兩種，它們是—⑴_、_⑵

⑴-⑵：A.命令方式B.程序方式C.聯機方式D.脫機方式E.后備方式F.執行

方式G.批量方式H.調用方式

4：用戶作業被SPOOLing系統輸入到外存時，稱此作業處于—⑴在外存后備隊列上的作

業處于—⑵作業在內存處于—⑶

⑴-⑶：A.進入狀態B.運行狀態C.完成狀態D.后備狀態E.就緒狀態

5：什么是作業？

6：操作系統為用戶提供哪些接口？

7：什么是系統調用？系統調用與一般過程的區別？

8:作業由哪幾部分組成？各有什么功能？

9：簡述系統調用的實現過程？

10：什么是作業？作業步？

11：試述SPOOLING系統的工作原理？

參考答案：1答：分時系統最重要的目標是實現人機交互，因此系統中所有的作業都是

由用戶從鍵盤終端直接輸入到內存，從而保證在一較短的時間內，各終端作業都能被處理。

如果將終端作業先送到外存輸入井上再等待作業調度后，才將作業調入內存，則既不能保證

人機交互的及時性，又顯然是多此一舉，故在分時系統中沒有作業控制表，不需設置作業調

度。

在實時系統中，由于實時任務往往是其實時性更高的任務，它們一般常住內存，因而也

不需要作業調度。

2答：是。理由是它允許事先從輸入設備上讀入信息并將輸出文件暫存于輸出設備中，直到

輸出設備準備接收它們為止。山于許多作業可能同時到達，所以，CPU將一個作業的計算與

其他作業的I/O操作并發執行。分時系統則不需要。理由是每個事務通常較短，而且輸出信

息一般直接輸出到打印設備上。

3解:(DC,(2)D

4解:(DA,(2)1),(3)B

5答：作業(Job)是用戶提交給計算機進行加工的一個任務，由三部分組成，即程序、數據

及作業說明書。

6答：命令接口(又分脫機命令接口聯機命令接口)：程序接口(即系統調用)、圖形接口。

7答：系統調用的基本概念：是OS提供給編程人員的唯一接口，是由操作系統中的?段程

序來完成特定功能的，屬于一種特殊的過程調用。主要區別：①運行狀態不同：一般的過程

調用，其調用和被調用過程或者都是子程序，或者都是系統程序，故運行在同一系統狀態下：

系統態或用戶態。系統調用的調用過程是用戶程序，它運行在用戶態；其被調用過程是系統

過程，運行在系統態下。②進入的方式不同：?般過程調用可以直接通過過程調用語句將控

制轉移到被調用的過程；而執行系統調用時，由于調用和被調用過程處于不同的系統狀態，

必須通過訪管中斷進入。③代碼層次不同：一般的過程調用中的被調用程序是用戶級程序，

而系統調用是操作系統中的代碼程序，是系統級程序。

8答：程序、數據和作業說明書。程序和數據完成用戶所要求的業務處理工作的具體內容，

作業處理的說明是用戶要求計算機所作的步驟。

9答：用戶在源程序中使用系統調用，給出系統調用名和函數后，即產生一條相應的陷入指

令，通過陷入處理機制調用服務，引起處理機中斷，然后保護處理機現場，取系統調用功能

號并尋找子程序入口，通過入口地址表來調用系統子程序。執行完畢后，退出中斷，返回到

用戶程序的斷點，恢復現場，繼續執行用戶程序。10答：作業是用戶提交給計算機進行加

工的一個任務，由三部分組成，即程序、數據及作業說明書。作業由不同順序相連的作業步

組成。作業步是在一個作業的處理過程中，計算機所做的相對獨立的工作。

11答：當用戶提交一批作業后，操作員鍵入“預輸入命令”啟動預輸入程序工作，預輸入程

序啟動輸入機讀出作業信息，并把它們存放到輸入井中。當主存儲器可以裝入作業時就從輸

入井中選擇若干作業裝入主存儲器。被裝入主存儲器中的作業在執行中可請求井管理程序從

輸出井讀需處理的信息或把處理結果寫到輸出井中。緩輸出程序利用處理器空閑時間把作業

執行結果在打印機上輸出。

第三章進程管理

教學內容

1.進程的基本概念

2.進程的實現

3.進程控制

4.進程的同步與互斥

5.利用信號量機制解決經典進程同步問題

6.進程通信

7.線程的概念

教學要求

了解引入進程的原因，進程控制的方法；熟悉進程的基本狀態及變遷，進程控制塊和組

織，信號量和P、V原語，進程通信的類型和方法；掌握用信號量機制解決各種互斥同步問

題的方法。

自學要點

進程的基本概念、描述、基本狀態及其轉換；原語及其執行特點，進程控制原語的工作

流程；臨界區、信號量并發進程間的制約方式及原因。重點為信號量和P、V原語，并能解

決一些各種同步互斥以及前趨圖等實際問題。

學時分配

9學時（自學學時：18學時）

3.1進程的基本概念

?進程的引入

①程序的順序執行

?程序的順序執行指一個具有獨立功能的程序獨占處理機直到得到最終結果的過程。具

有：順序性、封閉性和可再現性。

②程序的并發執行

?程序的并發執行指一組在邏輯上相互獨立的程序或程序段在執行過程中其執行時間在

客觀上互相重疊。程序的并發執行增強了計算機系統的處理能力和提高了資源的利用率。具

有：間斷性、失去了封閉性及不可再現性。

例1：

Intn=0

程序A

條件為真

1n=n+1;

程序A的其余部分

程序B

條件為真

1print（n）;

2n=0;

程序B的其余部分

討論可能出現的結果（三種情況：A1,B1,B2；B1,A1,B2;B1,B2,A1）

?程序并發執行的Bernstein條件

?定義有關程序的讀集和寫集

R(Pi)={a1,a2,…,am},用來表示程序Pi在執行期間所需引用的變量集合，稱為Pi的讀

集。

W(Pi)={a1,a2,…,am},用來表示程序R在執行期間所需改變的變量集合，稱為R的寫

集。

?Bernstein條件：若兩個程序P1和P2能滿足下述條件，R(P1)nW(P2)UR(P2)n

W(P1)UW(P1)CW(P2A{}它們便能并發執行，否則不能。

例2：

有四條語句：

S1:a=x+y

S2:b=z+1

S3:c=a-b

S4:w=c+1

R(s1)={x,y},W(S1)={a}

R(s2)={z},W(S2)={b}

R(s3)={a,b},W(S3)={c}

R(s4)={c},W(S4)={w}

S1和S2能滿足Bernstein條件，所以能并發執行而對于S1和S3不能滿足Bernstein

條件，因為R(S3)nw(Sl)={a},所以不能并發執行。同理，S2和S3,S3和S4也不能并發

執行。

前趨圖為：S1

\

S3fS4

/

S2

?前趨圖

?前趨圖是一個有向無循環圖，圖中每個結點可表示一個語句、一個程序段或一個進程,

結點間的有向邊表示結點之間的前趨關系。

?幾個概念：1直接前趨；2直接后繼；3初始結點；4終止結點

?進程的定義和特征

?進程的定義

?進程的概念是60年代初期，首先在MIT的Multics系統中引入的，進程的定義有很多種。

其中一種為進程是可并發執行的程序在一個數據集合上的運行過程。

?進程的特征

?進程具有五個基本特征，而程序則沒有。具體為：

①動態性。進程的實質是程序的一次執行過程，因此動態性是進程的最基本特征。它

還表現為有生命周期的，即由創建而產生，有調度而執行，由撤消而消亡。而程序只是一組

有序指令的集合，是靜態的。

②并發性。指多個進程能在一段時間內同時運行，并發性是進程的重要特性。引入進

程的目的也正是為了使其程序能和其它進程的程序并發執行。

③獨立性。指進程是?個能獨立運行、獨立分配資源和獨立調度的基本單位，凡未建

立進程的程序，都不能作為一個獨立的單位參加運行。

④異步性。指進程按各自獨立的、不可預知的速度向前推進，即按異步的方式運行。

⑤結構特征。從結構上看，進程是由程序段、數據段及進程控制塊(PCB)三部分組成,

這也是進程的靜態描述。PCB是操作系統中最重要的數據結構，它存放了操作系統所需的、

用于描述進程情況和控制進程運行所需的全部信息，是進程存在的唯一標志。

?作業和進程的關系

①作業是用戶向計算機提交任務的任務實體。在用戶向計算機提交作業之后，系統將

它放入外存中的作業等待隊列中等待執行：而進程則是完成用戶任務的執行實體，是向系統

申請分配資源的基本單位。

②一個作業可由多個進程組成，且必須至少由?個進程組成，反之不然。

③作業的概念主要用在批處理系統中，而進程的概念則用在幾乎所有的多道系統中。

?進程的基本狀態及其轉換

?由進程運行的間斷性，決定了進程至少具有下述三種狀態：

①就緒狀態。當進程已分配到除CPU以外的所有必要資源后，只要能再獲得處理機，便

能立即執行所處的狀態。一個系統中，可以有多個進程同時處于就緒狀態，通常將它們排成

一個隊列，稱為就緒隊列。

②執行狀態。指進程已獲得處理機，其程序正在執行。在單處理機系統中，只能有一

個進程處于執行狀態。

③等待(阻塞)狀態。進程因等待某事件而暫停執行時的所處的狀態。通常將處于等

待狀態的進程排成?個隊列，稱為等待隊列。

?進程狀態的轉換及原因

①就緒f執行調度：

②執行一等待等待某個事件發生而睡眠;

③等待f就緒因等待的時間發生而喚醒;

④執行一就緒時間片用完。

?新狀態和終止狀態

?新（New）狀態：是一個進程剛剛建立，但還未將它送入就緒隊列時的狀態）。

?終止（Terminated）狀態：當一個進程已經正常結束或異常結束，OS已將它從就緒

隊列中移出，但尚未將它撤消時的狀態。

?新f就緒狀態：當就緒進程能夠接納新進程時,OS就把處于新狀態的進程移入就緒

隊列。

?執行f終止狀態：當-?個進程已經完成或發生某事件（地址越界等）而異常終止時，

進程將由執行轉為終止狀態。

3.2進程的實現

?進程的結構描述

?進程由三部分組成，即PCB、有關程序段和該程序段對其進行操作的數據結構集。各

部分的作用：

①進程控制塊：用于描述進程情況及控制進程運行所需的全部信息。

②程序段：是進程中能被進程調度程序在CPU上執行的程序代碼段。

③數據段：一個進程的數據段，可以是進程對應的程序加工處理的原始數據，也可以

是程序執行后產生的中間或最終數據。

?進程控制塊

?進程控制塊PCB：是OS中最重要的數據結構，用于描述進程情況及控制進程運行所

需的全部信息。系統根據PC8感知進程的存在和通過PCB中包含的各項變量的變化，掌握

進程所處的狀態以達到控制進程活動的目的，是進程存在的唯一標志。其基本內容是：有關

進程的描述信息；控制信息；資源管理信息；CPU現場保護結構。

?PCB是有一定的生命期的。在創建一個進程時，應先創建PCB：然后才能根據PCB

的信息對進程管理和控制；進程結束時，回收PCB,進程也隨之消亡。在一個系統中，系

統進程加上用戶進程，進程數可達數十百個，為了有效的管理，應將它們組織起來。常用的

組織方式有：鏈接方式；索引方式。

3.3進程控制

?進程控制機構

?進程控制主要任務：對進程生命期控制及實現進程狀態的轉換，是由操作系統內核中

相應程序實現的。

?處理機的執行狀態：系統態、用戶態。系統態（核心態或管態），具有較高的特權，

能執行一切硬件指令，訪問所有寄存器和內存儲器。用戶態（目態），具有較低特權的執行

狀態，只能執行規定的指令，訪問指定的寄存器和內存儲器。

?操作系統內核：OS的內核通常運行在系統態，是計算機硬件擴充的第一層軟件，主

要是一些與硬件密切相關的模塊，常駐內存。內核的功能：1支撐功能；中斷處理、時鐘管

理、原語操作。2資源管理功能：進程管理、存儲器管理、設備管理。

?原語：是OS系統內核中山若干條指令構成，用于完成特定功能的一個過程。

?與一般過程的區別：它們是“原子操作”。原子操作：一個操作中的所有動作，要么

全做，要么全不做。即是一個不可分割的操作，是不可中斷的。

?進程控制原語

是對進程生命期控制和進程狀態轉換的原語，目的是達到多進程高效率并發執行和協

調、實現資源共享。主要有：創建原語；撤消原語；阻塞原語；喚醒原語。

?進程創建原語

?創建方式：由系統程序模塊統一創建；由父進程創建。

?進程圖：用于描述進程家族關系的有向樹。（了解父進程、子進程、祖父進程、祖先

等概念）

?引起創建進程的典型事件：1用戶登錄；2作業調度；3提供服務；4應用請求；

?進程創建的步驟：

1申請空白PCB；

2為新進程分配資源；

3初始化PCB；

4將新進程插入就緒隊列；

5將新進程插入進程家族或進程鏈。

?進程撤消原語

?引起進程撤消的事件：1正常結束；2異常結束；（指在進程運行期間，由于出現某

些錯誤和故障迫使進程終止，如越界錯誤、I/O故障等）3外界干預；（指進程應外界的請求

而終止運行，這些干預有：操作員或OS干預；父進程請求；父進程終止）

?進程撤消過程：

1根據被撤消進程的標識符，從PCB集合中檢索出該進程的PCB,讀出其狀態；

2若為執行狀態，應立即終止其執行，并在其撤消后應重新調度，選擇一新進程，

把處理機分配給它；

3若該進程有子孫進程，還應將其所有的子孫進程預以撤消，以防成為不可控；

4將該進程全部資源，歸還父進程或系統；

5釋放撤消進程的PCB結構本身。

?進程阻塞和喚醒原語

?引起進程阻塞和喚醒的事件：1請求系統服務；2啟動某種操作；3新數據尚未到達;

4無新工作可做；

?Block原語和Wakeup原語是一對作用剛好相反的原語。?般來說，如果某進程調用

了阻塞原語，則必須在與之合作的另一進程或相關進程中，調用喚醒原語；否則被阻塞進程

將會因不能被喚醒而長久處于阻塞狀態，從而再無機會運行。

?進程阻塞過程：（這是進程自身的一種主動行為）

1因進程處于執行狀態，故應先中斷處理機和保存該進程的CPU現場；

2將進程的狀態有“執行”改為“阻塞”；

3將阻塞進程插入到阻塞（等待）隊列；（若系統中設置了因不同事件而阻塞的多

個阻塞隊列，則應將進程插到具有相同事件的阻塞隊列）

4轉進程調度；（防止處理機空轉，而出現資源浪費）

?進程喚醒過程：

1從阻塞（等待）隊列中摘下需被喚醒的進程；

2將其PCB的現行狀態，山阻塞改為就緒；

3并將該進程插入到就緒隊列；

4轉進程調度或返回；

3.4進程的同步與互斥

?主要任務

?進程的同步和互斥機制的主要任務：控制并發執行的諸進程之間能有效地共享和相互

協作，同時使并發執行的程序仍具有可再現性。

?進程互斥

?并發系統中諸進程由于資源共享、進程合作，而產生進程之間的相互制約；又因共享

資源的方式不同，而導致兩種不同的制約關系：

①間接相互制約。這種制約主要源于資源共享（進程互斥）；

②直接相互制約。這種制約主要源于進程合作（進程同步）。

?臨界資源：一次僅允許?個進程訪問的資源。

?臨界區：每個進程中訪問臨界資源的那段代碼。（不允許多個并發進程交叉執行的?

段程序）

?進程互斥：不允許兩個以上的共享該資源的并發進程同時進入臨界區。

?同步機制的準則：空閑讓進；忙則等待；讓權等待；有限等待；

例3：

（與時間有關的錯誤）二個進程P1,P2共享變量count（Rl,R2是處理機中的寄存器）：

P1：①Rl=count;

②RI=R1+1;

③count=Rl;

P2:：①R2=count;

②R2=R2+1;

（3）count=R2;

結果應該count增加了2,正確。

但若執行順序按P1①，P2①，P1②，P1③，P2②，P2③，雖然P1,P2各自對count進

行了加1操作，但最后結果count僅增加了1。

?進程同步

?定義：指多個合作進程為了完成同一個任務，它們在執行速度上必須相互協調，即一

個進程的執行依賴于另一個進程的消息，當沒有消息時要等待，直到消息到達被喚醒。

?合作進程指具有同步關系的一組并發進程，合作進程間互相發送的信號稱為消息或事

件。

?進程同步和互斥間的關系

?同步互斥相似處：進程的互斥實際上是進程同步的?種特殊情況；進程的互斥和同步

統稱為進程同步。

?差別：進程互斥是進程間共享資源的使用權，這種競爭沒有固定的必然聯系，哪個進

程競爭到使用權就歸那個進程使用，直到不需要使用時在歸還；而進程同步則涉及共享資源

的并發進程間有種必然的聯系，當進程必須同步時，即使無進程在使用共享資源時，那么

尚未得到同步消息的進程也不能去使用這個資源。

?利用信號量機制解決問題

?信號量機制：山Diskstra提出的一種解決進程的同步與互斥的工具。

?建立一個信號量必須經過說明所代表的意義，賦初值以及建立相應的數據結構以便指

向那些等待使用該臨界區的進程。

?信號量的值只能通過P、V原語操作來改變。

?記錄型的信號量機制：是一個記錄型的數據結構，包含兩個數據項，一是記數值域,

另一是等待該信號量的進程隊列首指針域。描述如下：

typedefstructsemaphore

intvalue;

PCB*p;

?P(s)和V(s)操作原語

voidv(s)

structsemaphores;

(

s.value=s.value+1;

if(s.value<=0)wakeup(s.p);

)

voidP(s)

structsemaphores;

(

s.value=s.value-1;

if(s.value<0)block(s.p);

)

?s.value的物理含義

?當s.value>0數值時，表示某類可用資源的數量。而當s.value<0數值時，表示該類

資源己分配完。若有進程請求該類資源，則被阻塞，其絕對值等于等待該類資源的進程數。

?每次的P(s)操作，意味著進程請求分配該類資源的一個單位資源。相反，執行一次

V(s)操作意味著進程釋放相應資源的一個單位資源。當值小于等于0時，表明有進程被阻

塞，需要喚醒。

?用信號量解題的關鍵

?1信號量的設置

?2給信號量賦初值(常用的互斥和同步信號量值的大小)

?3P、V操作安排的位置(其中，P的順序不能顛倒，V的順序任意)

?用信號量機制解決前趨圖問題

?方法：若圖中存在結點S1指向結點S2的有向邊，表示進程P1中的程序段S1應該

先執行，而進程P2中的程序段S2后執行。設置一個信號量S,初值為0,將V(s)放在S1

后面，而在S2前面先執行P(s)。

?進程P1的語句序列為:S1;V(s)

?進程P2的語句序列為：P⑸;S2

例4：(利用信號量機制解決前趨圖問題)

具有8個結點的前趨圖。例子中的前趨圖中共有有向邊10條，可設10個信號量，初值

均為0；有8個結點，可設計成8個并發進程，具體描述如下：

structsemaphorea,b,c,d,e,f,g,h,I,j=0,0,0,0,0,0,0,0,0,0

cobegin

{al;V(a);V(b);V(C);}

{P(a);S2;V(d);)

{P(b);S3;V(e);V(f);)

{P(c);S4;V(g);}

{P(d);P(e);S5;V(h);}

{P(f);P(g);S6;V(i)}

{P(h);P⑴;S7;V(j);}

{P(j)；S8;}

coend

?利用互斥信號量實現二個進程互斥

structsemaphoremutex=1

cobeginvoidprocessA(void)

{

while(TRUE){

P(mutex);

criticalsectionA;

V(mutex);

Remaindersection;}

)

voidprocessA(void)

{

while(TRUE){

P(mutex);

criticalsectionA;

V(mutex);

Remaindersection;}

)

coend

?利用信號量實現二個進程同步問題

(計算進程和打印進程)

structsemaphoresc,sp=l

numberx,y,buffer;

cobeginvoidCP(void)

(

while(TRUE){

computernextnumbeintox;

P(sc);

Buffer=x;

V(sp);}

voidpp(void)

{

while(TRUE){

P(sp)；

y=bufler;

V(sc);

Printynumber;}

}

coend

?經典的進程同步問題

例5：生產者一消費者問題

?(一個最著名的進程同步問題)

?問題描述：?組生產者向一組消費者提供消息，它們共享一個有界緩沖池,產者存

入消息，消費者從中取得消息。

structsemaphores1,s2,empty,full=1,1,n,0;

messagebuffer[n];

intin,out=0,0;

cobegin

voidproduceri(void)(i=1,2,...,k)

{messagex;

while(TRUE){

produceanewmessageintox;

P(empty);

P(sl)；

bufler[in]=x;

in=(in+l)modn;

V(sl);

V(full);)

)

voidconsumeij(void)(j=l,2,...,m)

{messagey;

while(TRUE){

P(full);

P(s2);

y=buffer[in];

out=(out+l)modn;

V(s2);

V(empty);

consumemessagey;}

coend

例6：讀者一寫者問題

?問題描述：多個進程共享一個文件，其中只讀文件的稱為讀者，其余只寫文件的稱為

寫者。讀者可以同時讀，但寫者只能獨立地寫。(即是互斥的，一個進程在寫的時候，其它

進程即不能讀，也不能寫)

structsemaphoremutex,wrt=1,1;

intreadcount=0;

cobegin

voidreaderi(void)(i=l,2,...,k)

(

while(TRUE){

P(mutex);

if(readcount=0)thenP(wrt);

readcount:=readcount-i-1;

V(mutex);

performreadoperation;

P(mutex);

Readcount:=readcount-1;

if(readcount=0)thenV(wrt);

V(mutex);}

)

voidwriteij(void)(j=l,2,...,m)

{

while(TRUE){

P(wrt);

performwriteoperation;

V(wrt);}

}

coend

例7：圖書館閱覽室問題

?問題描述：假定閱覽室最多可同時容納100個人閱讀，讀者進入時，必須在閱覽室

門口的一個登記表上登記，內容包括姓名、座號等，離開時要撤掉登記內容。用P、V操作

描述讀者進程的同步算法。

(解題分析：讀者有任意多個，但進入閱覽室閱讀最多為100人，為此可設一個信號量

s,代表空座位的數目；另登記表為臨界資源，需設一個用于互斥的信號量mutex,防止2個

及以上的讀者進程同時對此表訪問。對于每個讀者的動作包括進入、閱讀、離開。)

structsemaphores,mutex=100,1;

cobegin

voidreaderi(void)(i=l,2,...,k)

(

while(TRUE){

P(s)；

P(mutex);

查登記表，置某座位為占用；

V(mutex);

reading;

P(mutex);

查登記表，置某座位為空；

V(mutex);

V(s);)

}

coend

例8：吃水果問題

?問題描述：桌上有一只盤子，每次只能放一個水果，爸爸專向盤中放蘋果，媽媽專向

盤中放桔子，兒子專等吃盤里的桔子，女兒專等吃盤里的革果。只要盤子空，則爸爸或媽媽

可向盤中放水果，僅當盤中有自己需要的水果時，兒子或女兒可從中取出，請給出四人之間

的同步關系，并用PV操作實現四人正確活動的程序。

解：四人之間的關系：1爸爸，媽媽要互斥使用盤子，所以兩者之間是互斥關系；2爸爸放

的蘋果，女兒吃，所以兩者是同步關系；3媽媽放的桔子，兒子吃，所以兩者也是同步關系。

structsemaphores,sp,so=1,0,0；

cobegin

voidfather(void)

(

while(TRUE){

haveanapple;

P(s)；

putanapple;

V(sp);)

}

voidmother(void)

{

while(TRUE){

haveanorange;

P(s)；

putanorange;

V(so);}

)

voidson(void)

{

while(TRUE){

P(sp)；

getanorange;

V(s);

eatanorange;}

voiddaught(void)

while(TRUE){

P(sp);

getanapple;

V(s);

eatanapple;}

}

coend

例9：司機一售票員問題

?問題描述：設公共汽車上，司機和售票員的活動分別是:

司機：售票員：

啟動車輛上下乘客

正常行車關車門

到站停車售票

開車門

上下乘客

在汽車不斷到站，停車，行駛過程中，這兩個活動的同步關系？

解法一：

structsemaphoresl,s2=0,0;

cobcgin

voiddriver(void)

{

while(TRUE){

P(s2);

啟動車輛；

正常行車；

到站停車；

V(sl);)

}

voidconductor(void)

{

while(TRUE){

上、下乘客；關車門；

V(s2);

售票；

P(sl)；

開車門;上、下乘客;}

)

coend

解法二：

structsemaphoresl,s2=1,0;

cobegin

voiddriver(void)

(

while(TRUE){

P(s2);

啟動車輛；

正常行車；

到站停車；