計(jì)算機(jī)操作系統(tǒng)第四版教案ppt課件(PPT 1255頁)

1、高等學(xué)校計(jì)算機(jī)類“十二五”規(guī)劃教材部級(jí)優(yōu)秀教材 計(jì)算機(jī)操作系統(tǒng) (第四版)1.第1頁，共1255頁。目 錄 第一章 操作系統(tǒng)引論第二章 進(jìn)程的描述與控制第三章 處理機(jī)調(diào)度與死鎖第四章 存儲(chǔ)器管理第五章 虛擬存儲(chǔ)器第六章 輸入輸出系統(tǒng)第七章 文件管理第八章 磁盤存儲(chǔ)器的管理第九章 操作系統(tǒng)接口第十章 多處理機(jī)操作系統(tǒng)第十一章 多媒體操作系統(tǒng)第十二章 保護(hù)和安全2.第2頁，共1255頁。第一章 操作系統(tǒng)引論1.1 操作系統(tǒng)的目標(biāo)和作用1.2 操作系統(tǒng)的發(fā)展過程1.3 操作系統(tǒng)的基本特性1.4 操作系統(tǒng)的主要功能1.5 OS結(jié)構(gòu)設(shè)計(jì)習(xí)題.第3頁，共1255頁。1.1 操作系統(tǒng)的目標(biāo)和作用操作系統(tǒng)的目

2、標(biāo)與應(yīng)用環(huán)境有關(guān)。例如在查詢系統(tǒng)中所用的OS，希望能提供良好的人機(jī)交互性；對(duì)于應(yīng)用于工業(yè)控制、武器控制以及多媒體環(huán)境下的OS，要求其具有實(shí)時(shí)性；而對(duì)于微機(jī)上配置的OS，則更看重的是其使用的方便性。.第4頁，共1255頁。1.1.1 操作系統(tǒng)的目標(biāo)1. 方便性2. 有效性 3. 可擴(kuò)充性4. 開放性.第5頁，共1255頁。1.1.2 操作系統(tǒng)的作用 1. OS作為用戶與計(jì)算機(jī)硬件系統(tǒng)之間的接口OS作為用戶與計(jì)算機(jī)硬件系統(tǒng)之間接口的含義是：OS處于用戶與計(jì)算機(jī)硬件系統(tǒng)之間，用戶通過OS來使用計(jì)算機(jī)系統(tǒng)?；蛘哒f，用戶在OS幫助下能夠方便、快捷、可靠地操縱計(jì)算機(jī)硬件和運(yùn)行自己的程序。圖1-1是OS作為

3、接口的示意圖。 .第6頁，共1255頁。圖1-1 OS作為接口的示意圖.第7頁，共1255頁。2. OS作為計(jì)算機(jī)系統(tǒng)資源的管理者在一個(gè)計(jì)算機(jī)系統(tǒng)中，通常都含有多種硬件和軟件資源。歸納起來可將這些資源分為四類：處理機(jī)、存儲(chǔ)器、I/O設(shè)備以及文件(數(shù)據(jù)和程序)。相應(yīng)地，OS的主要功能也正是對(duì)這四類資源進(jìn)行有效的管理。處理機(jī)管理是用于分配和控制處理機(jī)；存儲(chǔ)器管理主要負(fù)責(zé)內(nèi)存的分配與回收；I/O設(shè)備管理是負(fù)責(zé)I/O設(shè)備的分配(回收)與操縱；文件管理是用于實(shí)現(xiàn)對(duì)文件的存取、共享和保護(hù)?？梢?，OS的確是計(jì)算機(jī)系統(tǒng)資源的管理者。.第8頁，共1255頁。3. OS實(shí)現(xiàn)了對(duì)計(jì)算機(jī)資源的抽象對(duì)于一臺(tái)完全無軟件的

4、計(jì)算機(jī)系統(tǒng)(即裸機(jī))，由于它向用戶提供的僅是硬件接口(物理接口)，因此，用戶必須對(duì)物理接口的實(shí)現(xiàn)細(xì)節(jié)有充分的了解，這就致使該物理機(jī)器難于廣泛使用。為了方便用戶使用I/O設(shè)備，人們?cè)诼銠C(jī)上覆蓋上一層I/O設(shè)備管理軟件，如圖1-2所示，由它來實(shí)現(xiàn)對(duì)I/O設(shè)備操作的細(xì)節(jié)，并向上將I/O設(shè)備抽象為一組數(shù)據(jù)結(jié)構(gòu)以及一組I/O操作命令，如read和write命令，這樣用戶即可利用這些數(shù)據(jù)結(jié)構(gòu)及操作命令來進(jìn)行數(shù)據(jù)輸入或輸出，而無需關(guān)心I/O是如何具體實(shí)現(xiàn)的。 .第9頁，共1255頁。圖1-2 I/O軟件隱藏了I/O操作實(shí)現(xiàn)的細(xì)節(jié).第10頁，共1255頁。1.1.3 推動(dòng)操作系統(tǒng)發(fā)展的主要?jiǎng)恿?1不斷提高計(jì)算

5、機(jī)資源利用率2. 方便用戶3. 器件的不斷更新?lián)Q代4. 計(jì)算機(jī)體系結(jié)構(gòu)的不斷發(fā)展5. 不斷提出新的應(yīng)用需求.第11頁，共1255頁。1.2 操作系統(tǒng)的發(fā)展過程在20世紀(jì)50年代中期，出現(xiàn)了第一個(gè)簡(jiǎn)單的批處理OS；60年代中期開發(fā)出多道程序批處理系統(tǒng)；不久又推出分時(shí)系統(tǒng)，與此同時(shí)，用于工業(yè)和武器控制的實(shí)時(shí)OS也相繼問世。20世紀(jì)70到90年代，是VLSI和計(jì)算機(jī)體系結(jié)構(gòu)大發(fā)展的年代，導(dǎo)致了微型機(jī)、多處理機(jī)和計(jì)算機(jī)網(wǎng)絡(luò)的誕生和發(fā)展，與此相應(yīng)地，也相繼開發(fā)出了微機(jī)OS、多處理機(jī)OS和網(wǎng)絡(luò)OS，并得到極為迅猛的發(fā)展。.第12頁，共1255頁。1.2.1 未配置操作系統(tǒng)的計(jì)算機(jī)系統(tǒng) 1. 人工操作方式早

6、期的操作方式是由程序員將事先已穿孔的紙帶(或卡片)，裝入紙帶輸入機(jī)(或卡片輸入機(jī))，再啟動(dòng)它們將紙帶(或卡片)上的程序和數(shù)據(jù)輸入計(jì)算機(jī)，然后啟動(dòng)計(jì)算機(jī)運(yùn)行。僅當(dāng)程序運(yùn)行完畢并取走計(jì)算結(jié)果后，才允許下一個(gè)用戶上機(jī)。這種人工操作方式有以下兩方面的缺點(diǎn)：(1) 用戶獨(dú)占全機(jī)，即一臺(tái)計(jì)算機(jī)的全部資源由上機(jī)用戶所獨(dú)占。(2) CPU等待人工操作。當(dāng)用戶進(jìn)行裝帶(卡)、卸帶(卡)等人工操作時(shí)，CPU及內(nèi)存等資源是空閑的。.第13頁，共1255頁。2. 脫機(jī)輸入/輸出(Off-Line I/O)方式為了解決人機(jī)矛盾及CPU和I/O設(shè)備之間速度不匹配的矛盾，20世紀(jì)50年代末出現(xiàn)了脫機(jī)I/O技術(shù)。該技術(shù)是事先

7、將裝有用戶程序和數(shù)據(jù)的紙帶裝入紙帶輸入機(jī)，在一臺(tái)外圍機(jī)的控制下，把紙帶(卡片)上的數(shù)據(jù)(程序)輸入到磁帶上。當(dāng)CPU需要這些程序和數(shù)據(jù)時(shí)，再從磁帶上高速地調(diào)入內(nèi)存。.第14頁，共1255頁。圖1-3 脫機(jī)I/O示意圖.第15頁，共1255頁。1.2.2 單道批處理系統(tǒng) 1. 單道批處理系統(tǒng)(Simple Batch Processing System)的處理過程為實(shí)現(xiàn)對(duì)作業(yè)的連續(xù)處理，需要先把一批作業(yè)以脫機(jī)方式輸入到磁帶上，并在系統(tǒng)中配上監(jiān)督程序(Monitor)，在它的控制下，使這批作業(yè)能一個(gè)接一個(gè)地連續(xù)處理。 .第16頁，共1255頁。圖1-4 單道批處理系統(tǒng)的處理流程.第17頁，共125

8、5頁。2. 單道批處理系統(tǒng)的缺點(diǎn)單道批處理系統(tǒng)最主要的缺點(diǎn)是，系統(tǒng)中的資源得不到充分的利用。這是因?yàn)樵趦?nèi)存中僅有一道程序，每逢該程序在運(yùn)行中發(fā)出I/O請(qǐng)求后，CPU便處于等待狀態(tài)，必須在其I/O完成后才繼續(xù)運(yùn)行。又因I/O設(shè)備的低速性，更使CPU的利用率顯著降低。圖1-5示出了單道程序的運(yùn)行情況，從圖可以看出：在t2t3、t6t7時(shí)間間隔內(nèi)CPU空閑。.第18頁，共1255頁。圖1-5 單道程序的運(yùn)行情況.第19頁，共1255頁。1.2.3 多道批處理系統(tǒng)(Multiprogrammed Batch Processing System)1. 多道程序設(shè)計(jì)的基本概念為了進(jìn)一步提高資源的利用率和系

9、統(tǒng)吞吐量，在20世紀(jì)60年代中期引入了多道程序設(shè)計(jì)技術(shù)，由此形成了多道批處理系統(tǒng)。圖1-6示出了四道程序時(shí)的運(yùn)行情況。.第20頁，共1255頁。圖1-6 多道程序的運(yùn)行情況.第21頁，共1255頁。2. 多道批處理系統(tǒng)的優(yōu)缺點(diǎn)多道批處理系統(tǒng)的優(yōu)缺點(diǎn)如下：(1) 資源利用率高。引入多道批處理能使多道程序交替運(yùn)行，以保持CPU處于忙碌狀態(tài)；在內(nèi)存中裝入多道程序可提高內(nèi)存的利用率；此外還可以提高I/O設(shè)備的利用率。(2) 系統(tǒng)吞吐量大。能提高系統(tǒng)吞吐量的主要原因可歸結(jié)為： CPU和其它資源保持“忙碌”狀態(tài)； 僅當(dāng)作業(yè)完成時(shí)或運(yùn)行不下去時(shí)才進(jìn)行切換，系統(tǒng)開銷小。.第22頁，共1255頁。(3) 平均周

10、轉(zhuǎn)時(shí)間長(zhǎng)。由于作業(yè)要排隊(duì)依次進(jìn)行處理，因而作業(yè)的周轉(zhuǎn)時(shí)間較長(zhǎng)，通常需幾個(gè)小時(shí)，甚至幾天。(4) 無交互能力。用戶一旦把作業(yè)提交給系統(tǒng)后，直至作業(yè)完成，用戶都不能與自己的作業(yè)進(jìn)行交互，修改和調(diào)試程序極不方便。.第23頁，共1255頁。3. 多道批處理系統(tǒng)需要解決的問題多道批處理系統(tǒng)是一種十分有效，但又非常復(fù)雜的系統(tǒng)，為使系統(tǒng)中的多道程序間能協(xié)調(diào)地運(yùn)行，系統(tǒng)必須解決下述一系列問題：(1) 處理機(jī)爭(zhēng)用問題。既要能滿足各道程序運(yùn)行的需要，又要能提高處理機(jī)的利用率。(2) 內(nèi)存分配和保護(hù)問題。系統(tǒng)應(yīng)能為每道程序分配必要的內(nèi)存空間，使它們“各得其所”，且不會(huì)因某道程序出現(xiàn)異常情況而破壞其它程序。(3) I

11、/O設(shè)備分配問題。系統(tǒng)應(yīng)采取適當(dāng)?shù)牟呗詠矸峙湎到y(tǒng)中的I/O設(shè)備，以達(dá)到既能方便用戶對(duì)設(shè)備的使用，又能提高設(shè)備利用率的目的。.第24頁，共1255頁。(4) 文件的組織和管理問題。系統(tǒng)應(yīng)能有效地組織存放在系統(tǒng)中的大量的程序和數(shù)據(jù)，使它們既便于用戶使用，又能保證數(shù)據(jù)的安全性。(5) 作業(yè)管理問題。系統(tǒng)中存在著各種作業(yè)(應(yīng)用程序)，系統(tǒng)應(yīng)能對(duì)系統(tǒng)中所有的作業(yè)進(jìn)行合理的組織，以滿足這些作業(yè)用戶的不同要求。(6) 用戶與系統(tǒng)的接口問題。為使用戶能方便的使用操作系統(tǒng)，OS還應(yīng)提供用戶與OS之間的接口。.第25頁，共1255頁。1.2.4 分時(shí)系統(tǒng)(Time Sharing System) 1. 分時(shí)系統(tǒng)的

12、引入如果說推動(dòng)多道批處理系統(tǒng)形成和發(fā)展的主要?jiǎng)恿κ翘岣哔Y源利用率和系統(tǒng)吞吐量，那么，推動(dòng)分時(shí)系統(tǒng)形成和發(fā)展的主要?jiǎng)恿?，則是為了滿足用戶對(duì)人機(jī)交互的需求，由此形成了一種新型OS。用戶的需求具體表現(xiàn)在以下幾個(gè)方面：(1) 人機(jī)交互。(2) 共享主機(jī)。 .第26頁，共1255頁。2. 分時(shí)系統(tǒng)實(shí)現(xiàn)中的關(guān)鍵問題在多道批處理系統(tǒng)中，用戶無法與自己的作業(yè)進(jìn)行交互的主要原因是：作業(yè)都先駐留在外存上，即使以后被調(diào)入內(nèi)存，也要經(jīng)過較長(zhǎng)時(shí)間的等待后方能運(yùn)行，用戶無法與自己的作業(yè)進(jìn)行交互。 1) 及時(shí)接收2) 及時(shí)處理.第27頁，共1255頁。3. 分時(shí)系統(tǒng)的特征分時(shí)系統(tǒng)與多道批處理系統(tǒng)相比，具有非常明顯的不同特性

13、，可以歸納成以下四個(gè)方面：(1) 多路性。(2) 獨(dú)立性。(3) 及時(shí)性。(4) 交互性。 .第28頁，共1255頁。1.2.5 實(shí)時(shí)系統(tǒng)(Real Time System) 1. 實(shí)時(shí)系統(tǒng)的類型隨著計(jì)算機(jī)應(yīng)用的普及，實(shí)時(shí)系統(tǒng)的類型也相應(yīng)增多，下面列出當(dāng)前常見的幾種：(1) 工業(yè)(武器)控制系統(tǒng)。(2) 信息查詢系統(tǒng)。(3) 多媒體系統(tǒng)。(4) 嵌入式系統(tǒng)。 .第29頁，共1255頁。2. 實(shí)時(shí)任務(wù)的類型(1) 周期性實(shí)時(shí)任務(wù)和非周期性實(shí)時(shí)任務(wù)。(2) 硬實(shí)時(shí)任務(wù)和軟實(shí)時(shí)任務(wù)。 .第30頁，共1255頁。3. 實(shí)時(shí)系統(tǒng)與分時(shí)系統(tǒng)特征的比較(1) 多路性。(2) 獨(dú)立性。(3) 及時(shí)性。(4)

14、交互性。(5) 可靠性。 .第31頁，共1255頁。1.2.6 微機(jī)操作系統(tǒng)的發(fā)展 1單用戶單任務(wù)操作系統(tǒng)1) CP/M 2) MS-DOS.第32頁，共1255頁。2. 單用戶多任務(wù)操作系統(tǒng)單用戶多任務(wù)操作系統(tǒng)的含義是，只允許一個(gè)用戶上機(jī)，但允許用戶把程序分為若干個(gè)任務(wù)，使它們并發(fā)執(zhí)行，從而有效地改善了系統(tǒng)的性能。 .第33頁，共1255頁。3. 多用戶多任務(wù)操作系統(tǒng)多用戶多任務(wù)操作系統(tǒng)的含義是，允許多個(gè)用戶通過各自的終端，使用同一臺(tái)機(jī)器，共享主機(jī)系統(tǒng)中的各種資源，而每個(gè)用戶程序又可進(jìn)一步分為幾個(gè)任務(wù)，使它們能并發(fā)執(zhí)行，從而可進(jìn)一步提高資源利用率和系統(tǒng)吞吐量。在大、中和小型機(jī)中所配置的大多是

15、多用戶多任務(wù)操作系統(tǒng)，而在32位微機(jī)上，也有不少配置的是多用戶多任務(wù)操作系統(tǒng)，其中最有代表性的是UNIX OS。.第34頁，共1255頁。1.3 操作系統(tǒng)的基本特性 前面所介紹的多道批處理系統(tǒng)、分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)這三種基本操作系統(tǒng)都具有各自不同的特征，如批處理系統(tǒng)有著高的資源利用率和系統(tǒng)吞吐量；分時(shí)系統(tǒng)能獲得及時(shí)響應(yīng)；實(shí)時(shí)系統(tǒng)具有實(shí)時(shí)特征。除此之外，它們還共同具有并發(fā)、共享、虛擬和異步四個(gè)基本特征。.第35頁，共1255頁。1.3.1 并發(fā)(Concurrence) 正是系統(tǒng)中的程序能并發(fā)執(zhí)行這一特征，才使得OS能有效地提高系統(tǒng)中的資源利用率，增加系統(tǒng)的吞吐量。1. 并行與并發(fā)并行性和并發(fā)性是

16、既相似又有區(qū)別的兩個(gè)概念。并行性是指兩個(gè)或多個(gè)事件在同一時(shí)刻發(fā)生。而并發(fā)性是指兩個(gè)或多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生。 .第36頁，共1255頁。2. 引入進(jìn)程在一個(gè)未引入進(jìn)程的系統(tǒng)中，在屬于同一個(gè)應(yīng)用程序的計(jì)算程序和I/O程序之間只能是順序執(zhí)行，即只有在計(jì)算程序執(zhí)行告一段落后，才允許I/O程序執(zhí)行；反之，在程序執(zhí)行I/O操作時(shí)，計(jì)算程序也不能執(zhí)行。但在為計(jì)算程序和I/O程序分別建立一個(gè)進(jìn)程(Process)后，這兩個(gè)進(jìn)程便可并發(fā)執(zhí)行。若對(duì)內(nèi)存中的多個(gè)程序都分別建立一個(gè)進(jìn)程，它們就可以并發(fā)執(zhí)行，這樣便能極大地提高系統(tǒng)資源的利用率，增加系統(tǒng)的吞吐量。.第37頁，共1255頁。1.3.2 共享(Sha

17、ring) 一般情況下的共享與操作系統(tǒng)環(huán)境下的共享其含義并不完全相同。 1. 互斥共享方式 系統(tǒng)中的某些資源，如打印機(jī)、磁帶機(jī)等，雖然可以提供給多個(gè)進(jìn)程(線程)使用，但應(yīng)規(guī)定在一段時(shí)間內(nèi)，只允許一個(gè)進(jìn)程訪問該資源。為此，在系統(tǒng)中應(yīng)建立一種機(jī)制，以保證多個(gè)進(jìn)程對(duì)這類資源的互斥訪問。.第38頁，共1255頁。2. 同時(shí)訪問方式系統(tǒng)中還有另一類資源，允許在一段時(shí)間內(nèi)由多個(gè)進(jìn)程“同時(shí)”對(duì)它們進(jìn)行訪問。這里所謂的“同時(shí)”，在單處理機(jī)環(huán)境下是宏觀意義上的，而在微觀上，這些進(jìn)程對(duì)該資源的訪問是交替進(jìn)行的。典型的可供多個(gè)進(jìn)程“同時(shí)”訪問的資源是磁盤設(shè)備。一些用重入碼編寫的文件也可以被“同時(shí)”共享，即允許若干個(gè)

18、用戶同時(shí)訪問該文件。.第39頁，共1255頁。1.3.3 虛擬(Virtual) 1. 時(shí)分復(fù)用技術(shù)(1) 虛擬處理機(jī)技術(shù)。(2) 虛擬設(shè)備技術(shù)。 .第40頁，共1255頁。2. 空分復(fù)用技術(shù)20世紀(jì)初，電信業(yè)中就已使用頻分復(fù)用技術(shù)來提高信道的利用率。它是指將一個(gè)頻率范圍比較寬的信道劃分成多個(gè)頻率范圍較窄的信道(稱為頻帶)，其中的任何一個(gè)頻帶都僅供一對(duì)用戶通話。早期的頻分復(fù)用技術(shù)只能將一條物理信道劃分為幾條到幾十條話路，后來又很快發(fā)展到成千上萬條話路，每條話路供一對(duì)用戶通話。再后來在計(jì)算機(jī)中也把空分復(fù)用技術(shù)用于對(duì)存儲(chǔ)空間的管理，用以提高存儲(chǔ)空間的利用率。 .第41頁，共1255頁。1.3.4

19、異步(Asynchronism) 在多道程序環(huán)境下，系統(tǒng)允許多個(gè)進(jìn)程并發(fā)執(zhí)行。在單處理機(jī)環(huán)境下，由于系統(tǒng)中只有一臺(tái)處理機(jī)，因而每次只允許一個(gè)進(jìn)程執(zhí)行，其余進(jìn)程只能等待。當(dāng)正在執(zhí)行的進(jìn)程提出某種資源要求時(shí)，如打印請(qǐng)求，而此時(shí)打印機(jī)正在為其它進(jìn)程打印，由于打印機(jī)屬于臨界資源，因此正在執(zhí)行的進(jìn)程必須等待，并釋放出處理機(jī)，直到打印機(jī)空閑，并再次獲得處理機(jī)時(shí)，該進(jìn)程方能繼續(xù)執(zhí)行?？梢?，由于資源等因素的限制，使進(jìn)程的執(zhí)行通常都不可能“一氣呵成”，而是以“停停走走”的方式運(yùn)行。.第42頁，共1255頁。1.4 操作系統(tǒng)的主要功能引入OS的主要目的是，為多道程序的運(yùn)行提供良好的運(yùn)行環(huán)境，以保證多道程序能有條不

20、紊地、高效地運(yùn)行，并能最大程度地提高系統(tǒng)中各種資源的利用率，方便用戶的使用。為此，在傳統(tǒng)的OS中應(yīng)具有處理機(jī)管理、存儲(chǔ)器管理、設(shè)備管理和文件管理等基本功能。此外，為了方便用戶使用OS，還需向用戶提供方便的用戶接口。.第43頁，共1255頁。1.4.1 處理機(jī)管理功能 1. 進(jìn)程控制2. 進(jìn)程同步 3. 進(jìn)程通信4. 調(diào)度(1) 作業(yè)調(diào)度。(2) 進(jìn)程調(diào)度。.第44頁，共1255頁。1.4.2 存儲(chǔ)器管理功能 1. 內(nèi)存分配內(nèi)存分配的主要任務(wù)是：(1) 為每道程序分配內(nèi)存空間，使它們“各得其所”。(2) 提高存儲(chǔ)器的利用率，盡量減少不可用的內(nèi)存空間(碎片)。(3) 允許正在運(yùn)行的程序申請(qǐng)附加的內(nèi)

21、存空間，以適應(yīng)程序和數(shù)據(jù)動(dòng)態(tài)增長(zhǎng)的需要。.第45頁，共1255頁。OS在實(shí)現(xiàn)內(nèi)存分配時(shí)，可采取靜態(tài)和動(dòng)態(tài)兩種方式：(1) 靜態(tài)分配方式。每個(gè)作業(yè)的內(nèi)存空間是在作業(yè)裝入時(shí)確定的，在作業(yè)裝入后的整個(gè)運(yùn)行期間不允許該作業(yè)再申請(qǐng)新的內(nèi)存空間，也不允許作業(yè)在內(nèi)存中“移動(dòng)”。(2) 動(dòng)態(tài)分配方式。每個(gè)作業(yè)所要求的基本內(nèi)存空間雖然也是在裝入時(shí)確定的，但允許作業(yè)在運(yùn)行過程中繼續(xù)申請(qǐng)新的附加內(nèi)存空間，以適應(yīng)程序和數(shù)據(jù)的動(dòng)態(tài)增長(zhǎng)，也允許作業(yè)在內(nèi)存中“移動(dòng)”。.第46頁，共1255頁。2. 內(nèi)存保護(hù)內(nèi)存保護(hù)的主要任務(wù)是： 確保每道用戶程序都僅在自己的內(nèi)存空間內(nèi)運(yùn)行，彼此互不干擾。 絕不允許用戶程序訪問操作系統(tǒng)的程序

22、和數(shù)據(jù)，也不允許用戶程序轉(zhuǎn)移到非共享的其它用戶程序中去執(zhí)行。.第47頁，共1255頁。3. 地址映射在多道程序環(huán)境下，由于每道程序經(jīng)編譯和鏈接后所形成的可裝入程序其地址都是從0開始的，但不可能將它們從“0”地址(物理)開始裝入內(nèi)存，致使(各程序段的)地址空間內(nèi)的邏輯地址與其在內(nèi)存空間中的物理地址并不相一致。為保證程序能正確運(yùn)行，存儲(chǔ)器管理必須提供地址映射功能，即能夠?qū)⒌刂房臻g中的邏輯地址轉(zhuǎn)換為內(nèi)存空間中與之對(duì)應(yīng)的物理地址。該功能應(yīng)在硬件的支持下完成。.第48頁，共1255頁。4. 內(nèi)存擴(kuò)充內(nèi)存擴(kuò)充并非是從物理上去擴(kuò)大內(nèi)存的容量，而是借助于虛擬存儲(chǔ)技術(shù)，從邏輯上擴(kuò)充內(nèi)存容量，使用戶所感覺到的內(nèi)存

23、容量比實(shí)際內(nèi)存容量大得多，以便讓更多的用戶程序能并發(fā)運(yùn)行。這樣既滿足了用戶的需要，又改善了系統(tǒng)的性能。為了能在邏輯上擴(kuò)充內(nèi)存，系統(tǒng)必須設(shè)置內(nèi)存擴(kuò)充機(jī)制(包含少量的硬件)，用于實(shí)現(xiàn)下述各功能：(1) 請(qǐng)求調(diào)入功能。(2) 置換功能。.第49頁，共1255頁。1.4.3 設(shè)備管理功能 設(shè)備管理的主要任務(wù)如下：(1) 完成用戶進(jìn)程提出的I/O請(qǐng)求，為用戶進(jìn)程分配所需的I/O設(shè)備，并完成指定的I/O操作。(2) 提高CPU和I/O設(shè)備的利用率，提高I/O速度，方便用戶使用I/O設(shè)備。為實(shí)現(xiàn)上述任務(wù)，設(shè)備管理應(yīng)具有緩沖管理、設(shè)備分配和設(shè)備處理以及虛擬設(shè)備等功能。1. 緩沖管理2. 設(shè)備分配3. 設(shè)備處理

24、.第50頁，共1255頁。1.4.4 文件管理功能 1. 文件存儲(chǔ)空間的管理2. 目錄管理3. 文件的讀/寫管理和保護(hù)(1) 文件的讀/寫管理。 (2) 文件保護(hù)。.第51頁，共1255頁。1.4.5操作系統(tǒng)與用戶之間的接口 1. 用戶接口(1) 聯(lián)機(jī)用戶接口。(2) 脫機(jī)用戶接口。(3) 圖形用戶接口。 .第52頁，共1255頁。2. 程序接口程序接口是為用戶程序在執(zhí)行中訪問系統(tǒng)資源而設(shè)置的，是用戶程序取得操作系統(tǒng)服務(wù)的唯一途徑。它是由一組系統(tǒng)調(diào)用組成的，每一個(gè)系統(tǒng)調(diào)用都是一個(gè)能完成特定功能的子程序。每當(dāng)應(yīng)用程序要求OS提供某種服務(wù)(功能)時(shí)，便調(diào)用具有相應(yīng)功能的系統(tǒng)調(diào)用(子程序)。早期的系

25、統(tǒng)調(diào)用都是用匯編語言提供的，只有在用匯編語言書寫的程序中才能直接使用系統(tǒng)調(diào)用。 .第53頁，共1255頁。1.4.6現(xiàn)代操作系統(tǒng)的新功能現(xiàn)代操作系統(tǒng)是在傳統(tǒng)操作系統(tǒng)基礎(chǔ)上發(fā)展起來的，它除了具有傳統(tǒng)操作系統(tǒng)的功能外，還增加了面向安全、面向網(wǎng)絡(luò)和面向多媒體等功能。1. 系統(tǒng)安全(1) 認(rèn)證技術(shù)。(2) 密碼技術(shù)。(3) 訪問控制技術(shù)。(4) 反病毒技術(shù)。.第54頁，共1255頁。2. 網(wǎng)絡(luò)的功能和服務(wù)(1) 網(wǎng)絡(luò)通信。(2) 資源管理。(3) 應(yīng)用互操作。 .第55頁，共1255頁。3. 支持多媒體(1) 接納控制功能。(2) 實(shí)時(shí)調(diào)度。(3) 多媒體文件的存儲(chǔ)。 .第56頁，共1255頁。1.5

26、 OS結(jié)構(gòu)設(shè)計(jì)早期OS的規(guī)模很小，如只有幾十KB，完全可以由一個(gè)人以手工方式，用幾個(gè)月的時(shí)間編制出來。此時(shí)，編制程序基本上是一種技巧，OS是否是有結(jié)構(gòu)的并不那么重要，重要的是程序員的程序設(shè)計(jì)技巧。但隨著OS規(guī)模的愈來愈大，其所具有的代碼也愈來愈多，往往需要由數(shù)十人或數(shù)百人甚至更多的人參與，分工合作，共同來完成操作系統(tǒng)的設(shè)計(jì)。這意味著，應(yīng)采用工程化的開發(fā)方法對(duì)大型軟件進(jìn)行開發(fā)。由此產(chǎn)生了“軟件工程學(xué)”。.第57頁，共1255頁。1.5.1 傳統(tǒng)操作系統(tǒng)結(jié)構(gòu) 1. 無結(jié)構(gòu)操作系統(tǒng)在早期開發(fā)操作系統(tǒng)時(shí)，設(shè)計(jì)者只是把他的注意力放在功能的實(shí)現(xiàn)和獲得高的效率上，缺乏首尾一致的設(shè)計(jì)思想。此時(shí)的OS是為數(shù)眾多

27、的一組過程的集合，每個(gè)過程可以任意地相互調(diào)用其它過程，致使操作系統(tǒng)內(nèi)部既復(fù)雜又混亂，因此，這種OS是無結(jié)構(gòu)的，也有人把它稱為整體系統(tǒng)結(jié)構(gòu)。.第58頁，共1255頁。2. 模塊化結(jié)構(gòu)OS1) 模塊化程序設(shè)計(jì)技術(shù)的基本概念模塊化程序設(shè)計(jì)技術(shù)是20世紀(jì)60年代出現(xiàn)的一種結(jié)構(gòu)化程序設(shè)計(jì)技術(shù)。該技術(shù)基于“分解”和“模塊化”的原則來控制大型軟件的復(fù)雜度。為使OS具有較清晰的結(jié)構(gòu)，OS不再是由眾多的過程直接構(gòu)成的，而是按其功能精心地劃分為若干個(gè)具有一定獨(dú)立性和大小的模塊。圖1-7示出了由模塊、子模塊等組成的模塊化OS結(jié)構(gòu)。.第59頁，共1255頁。圖1-7 模塊化結(jié)構(gòu)的操作系統(tǒng).第60頁，共1255頁。2)

28、 模塊獨(dú)立性在模塊-接口法中，關(guān)鍵問題是模塊的劃分和規(guī)定好模塊之間的接口。如果我們?cè)趧澐帜K時(shí)將模塊劃分得太小，雖然可以降低模塊本身的復(fù)雜性，但會(huì)引起模塊之間的聯(lián)系過多，從而會(huì)造成系統(tǒng)比較混亂；如果將模塊劃分得過大，又會(huì)增加模塊內(nèi)部的復(fù)雜性，使內(nèi)部的聯(lián)系增加，因此在劃分模塊時(shí)，應(yīng)在兩者間進(jìn)行權(quán)衡。.第61頁，共1255頁。3) 模塊接口法的優(yōu)缺點(diǎn)利用模塊-接口法開發(fā)的OS，較之無結(jié)構(gòu)OS具有以下明顯的優(yōu)點(diǎn)：(1) 提高OS設(shè)計(jì)的正確性、可理解性和可維護(hù)性。(2) 增強(qiáng)OS的可適應(yīng)性。(3) 加速OS的開發(fā)過程。.第62頁，共1255頁。模塊化結(jié)構(gòu)設(shè)計(jì)仍存在下述問題：(1) 在OS設(shè)計(jì)時(shí)，對(duì)各模

29、塊間的接口規(guī)定很難滿足在模塊設(shè)計(jì)完成后對(duì)接口的實(shí)際需求。(2) 在OS設(shè)計(jì)階段，設(shè)計(jì)者必須做出一系列的決定(決策)，每一個(gè)決定必須建立在上一個(gè)決定的基礎(chǔ)上，但模塊化結(jié)構(gòu)設(shè)計(jì)中，各模塊的設(shè)計(jì)齊頭并進(jìn)，無法尋找一個(gè)可靠的決定順序，造成各種決定的“無序性”，這將使程序人員很難做到“設(shè)計(jì)中的每一步?jīng)Q定”都是建立在可靠的基礎(chǔ)上，因此模塊-接口法又被稱為“無序模塊法”。 .第63頁，共1255頁。3. 分層式結(jié)構(gòu)OS1) 分層式結(jié)構(gòu)的基本概念為了將模塊-接口法中“決定順序”的無序性變?yōu)橛行蛐裕肓擞行蚍謱臃?，分層法的設(shè)計(jì)任務(wù)是，在目標(biāo)系統(tǒng)An和裸機(jī)系統(tǒng)(又稱宿主系統(tǒng))A0之間，鋪設(shè)若干個(gè)層次的軟件A1、

30、A2、A3、An-1，使An通過An-1、An-2、A2、A1層，最終能在A0上運(yùn)行。在操作系統(tǒng)中，常采用自底向上法來鋪設(shè)這些中間層。.第64頁，共1255頁。2) 分層結(jié)構(gòu)的優(yōu)缺點(diǎn)分層結(jié)構(gòu)的主要優(yōu)點(diǎn)有：(1) 易保證系統(tǒng)的正確性。(2) 易擴(kuò)充和易維護(hù)性。分層結(jié)構(gòu)的主要缺點(diǎn)是系統(tǒng)效率降低。由于層次結(jié)構(gòu)是分層單向依賴的，必須在每層之間都建立層次間的通信機(jī)制，OS每執(zhí)行一個(gè)功能，通常要自上而下地穿越多個(gè)層次，這無疑會(huì)增加系統(tǒng)的通信開銷，從而導(dǎo)致系統(tǒng)效率的降低。.第65頁，共1255頁。1.5.2 客戶/服務(wù)器模式(Client/Server Model) 簡(jiǎn)介1. 客戶/服務(wù)器模式的由來、組成和

31、類型客戶/服務(wù)器系統(tǒng)主要由三部分組成。(1) 客戶機(jī)：(2) 服務(wù)器：(3) 網(wǎng)絡(luò)系統(tǒng)：.第66頁，共1255頁。2. 客戶/服務(wù)器之間的交互(1) 客戶發(fā)送請(qǐng)求消息。(2) 服務(wù)器接收消息。(3) 服務(wù)器回送消息。(4) 客戶機(jī)接收消息。 .第67頁，共1255頁。3. 客戶/服務(wù)器模式的優(yōu)點(diǎn)(1) 數(shù)據(jù)的分布處理和存儲(chǔ)。(2) 便于集中管理。(3) 靈活性和可擴(kuò)充性。 (4) 易于改編應(yīng)用軟件。 .第68頁，共1255頁。1.5.3 面向?qū)ο蟮某绦蛟O(shè)計(jì)(Object-Orientated Programming)技術(shù)簡(jiǎn)介1. 面向?qū)ο蠹夹g(shù)的基本概念面向?qū)ο蠹夹g(shù)是20世紀(jì)80年代初提出并很快

32、流行起來的。 .第69頁，共1255頁。1) 對(duì)象在面向?qū)ο蟮募夹g(shù)中，是利用被封裝的數(shù)據(jù)結(jié)構(gòu)(變量)和一組對(duì)它進(jìn)行操作的過程(方法)來表示系統(tǒng)中的某個(gè)對(duì)象的，如圖1-8所示。對(duì)象中的變量(數(shù)據(jù))也稱為屬性，它可以是單個(gè)標(biāo)量或一張表。面向?qū)ο笾械姆椒ㄊ怯糜趫?zhí)行某種功能的過程，它可以改變對(duì)象的狀態(tài)，更新對(duì)象中的某些數(shù)據(jù)值或作用于對(duì)象所要訪問的外部資源。如果把一個(gè)文件作為一個(gè)對(duì)象(見圖1-9)，該對(duì)象的變量便是文件類型、文件大小、文件的創(chuàng)建者等。對(duì)象中的方法包含對(duì)文件的操作，如創(chuàng)建文件、打開文件、讀文件、寫文件、關(guān)閉文件等。.第70頁，共1255頁。圖1-8一個(gè)對(duì)象的示意圖 .第71頁，共1255頁

33、。 圖1-9 類和對(duì)象的關(guān)系 .第72頁，共1255頁。2) 對(duì)象類在實(shí)踐中，有許多對(duì)象可能表示的是同一類事物，每個(gè)對(duì)象具有自己的變量集合，而它們所具有的方法是相同的。如果為每一個(gè)相似的對(duì)象都定義一組變量和方法，顯然是低效的，由此產(chǎn)生了“對(duì)象類”的概念，利用“對(duì)象類”來定義一組大體相似的對(duì)象。一個(gè)類同樣定義了一組變量和針對(duì)該變量的一組方法，用它們來描述一組對(duì)象的共同屬性和行為。類是在對(duì)象上的抽象，對(duì)象則是類的實(shí)例。對(duì)象類中所定義的變量在實(shí)例中均有具體的值。.第73頁，共1255頁。3) 繼承在面向?qū)ο蟮募夹g(shù)中，可以根據(jù)已有類來定義一個(gè)新的類，新類被稱為子類(B)，原來的類被稱為父類(A)，見圖

34、1-10所示。 .第74頁，共1255頁。圖1-10 類的繼承關(guān)系.第75頁，共1255頁。2. 面向?qū)ο蠹夹g(shù)的優(yōu)點(diǎn)在操作系統(tǒng)設(shè)計(jì)時(shí)，將計(jì)算機(jī)中的實(shí)體作為對(duì)象來處理，可帶來如下好處：(1) 通過“重用”提高產(chǎn)品質(zhì)量和生產(chǎn)率。(2) 使系統(tǒng)具有更好的易修改性和易擴(kuò)展性。(3) 更易于保證系統(tǒng)的“正確性”和“可靠性”。.第76頁，共1255頁。1.5.4微內(nèi)核OS結(jié)構(gòu)1. 微內(nèi)核操作系統(tǒng)的基本概念1) 足夠小的內(nèi)核在微內(nèi)核操作系統(tǒng)中，內(nèi)核是指精心設(shè)計(jì)的、能實(shí)現(xiàn)現(xiàn)代OS最基本核心功能的小型內(nèi)核，微內(nèi)核并非是一個(gè)完整的OS，而只是將操作系統(tǒng)中最基本的部分放入微內(nèi)核，通常包含有： 與硬件處理緊密相關(guān)的部

35、分； 一些較基本的功能； 客戶和服務(wù)器之間的通信。這些OS最基本的部分只是為構(gòu)建通用OS提供一個(gè)重要基礎(chǔ)，這樣就可以確保把操作系統(tǒng)內(nèi)核做得很小。.第77頁，共1255頁。2) 基于客戶/服務(wù)器模式由于客戶/服務(wù)器模式具有非常多的優(yōu)點(diǎn)，故在單機(jī)微內(nèi)核操作系統(tǒng)中幾乎無一例外地都采用客戶/服務(wù)器模式，將操作系統(tǒng)中最基本的部分放入內(nèi)核中，而把操作系統(tǒng)的絕大部分功能都放在微內(nèi)核外面的一組服務(wù)器(進(jìn)程)中實(shí)現(xiàn)，如用于提供對(duì)進(jìn)程(線程)進(jìn)行管理的進(jìn)程(線程)服務(wù)器、提供虛擬存儲(chǔ)器管理功能的虛擬存儲(chǔ)器服務(wù)器、提供I/O設(shè)備管理的I/O設(shè)備管理服務(wù)器等，它們都是被作為進(jìn)程來實(shí)現(xiàn)的，運(yùn)行在用戶態(tài)，客戶與服務(wù)器之間

36、是借助微內(nèi)核提供的消息傳遞機(jī)制來實(shí)現(xiàn)信息交互的。圖1-11示出了在單機(jī)環(huán)境下的客戶/服務(wù)器模式。.第78頁，共1255頁。圖1-11 在單機(jī)環(huán)境下的客戶/服務(wù)器模式.第79頁，共1255頁。3) 應(yīng)用“機(jī)制與策略分離”原理在現(xiàn)在操作系統(tǒng)的結(jié)構(gòu)設(shè)計(jì)中，經(jīng)常利用“機(jī)制與策略分離”的原理來構(gòu)造OS結(jié)構(gòu)。所謂機(jī)制，是指實(shí)現(xiàn)某一功能的具體執(zhí)行機(jī)構(gòu)。而策略，則是在機(jī)制的基礎(chǔ)上借助于某些參數(shù)和算法來實(shí)現(xiàn)該功能的優(yōu)化，或達(dá)到不同的功能目標(biāo)。 .第80頁，共1255頁。4) 采用面向?qū)ο蠹夹g(shù)操作系統(tǒng)是一個(gè)極其復(fù)雜的大型軟件系統(tǒng)，我們不僅可以通過結(jié)構(gòu)設(shè)計(jì)來分解操作系統(tǒng)的復(fù)雜度，還可以基于面向?qū)ο蠹夹g(shù)中的“抽象”和

37、“隱蔽”原則控制系統(tǒng)的復(fù)雜性，再進(jìn)一步利用“對(duì)象”、“封裝”和“繼承”等概念來確保操作系統(tǒng)的“正確性”、“可靠性”、“易修改性”、“易擴(kuò)展性”等，并提高操作系統(tǒng)的設(shè)計(jì)速度。正因?yàn)槊嫦驅(qū)ο蠹夹g(shù)能帶來如此多的好處，故面向?qū)ο蠹夹g(shù)被廣泛應(yīng)用于現(xiàn)代操作系統(tǒng)的設(shè)計(jì)中。.第81頁，共1255頁。2. 微內(nèi)核的基本功能微內(nèi)核應(yīng)具有哪些功能，或者說哪些功能應(yīng)放在微內(nèi)核內(nèi)，哪些應(yīng)放在微內(nèi)核外，目前尚無明確的規(guī)定。現(xiàn)在一般都采用“機(jī)制與策略分離”的原理，將機(jī)制部分以及與硬件緊密相關(guān)的部分放入微內(nèi)核中。由此可知微內(nèi)核通常具有如下幾方面的功能：1) 進(jìn)程(線程)管理 2) 低級(jí)存儲(chǔ)器管理3) 中斷和陷入處理.第82頁

38、，共1255頁。3. 微內(nèi)核操作系統(tǒng)的優(yōu)點(diǎn)由于微內(nèi)核OS結(jié)構(gòu)是建立在模塊化、層次化結(jié)構(gòu)的基礎(chǔ)上的，并采用了客戶/服務(wù)器模式和面向?qū)ο蟮某绦蛟O(shè)計(jì)技術(shù)，因此，微內(nèi)核結(jié)構(gòu)的操作系統(tǒng)是集各種技術(shù)優(yōu)點(diǎn)之大成，因而使之具有如下優(yōu)點(diǎn)：(1) 提高了系統(tǒng)的可擴(kuò)展性。 (2) 增強(qiáng)了系統(tǒng)的可靠性。(3) 可移植性強(qiáng)。(4) 提供了對(duì)分布式系統(tǒng)的支持。(5) 融入了面向?qū)ο蠹夹g(shù)。 .第83頁，共1255頁。4. 微內(nèi)核操作系統(tǒng)存在的問題應(yīng)當(dāng)指出，在微內(nèi)核操作系統(tǒng)中，由于采用了非常小的內(nèi)核，客戶/服務(wù)器模式和消息傳遞機(jī)制雖給微內(nèi)核操作系統(tǒng)帶來了許多優(yōu)點(diǎn)，但由此也使微內(nèi)核OS存在著潛在缺點(diǎn)，其中最主要的是，較之早期的

39、操作系統(tǒng)，微內(nèi)核操作系統(tǒng)的運(yùn)行效率有所降低。實(shí)際情況是往往還會(huì)引起更多的上下文切換。例如，當(dāng)某個(gè)服務(wù)器自身尚無能力完成客戶請(qǐng)求而需要其它服務(wù)器的幫助時(shí)，如圖1-12所示，其中的文件服務(wù)器還需要磁盤服務(wù)器的幫助，這時(shí)就需要進(jìn)行8次上下文的切換。.第84頁，共1255頁。圖1-12 在傳統(tǒng)OS和微內(nèi)核OS中的上下文切換.第85頁，共1255頁。 習(xí) 題 1. 設(shè)計(jì)現(xiàn)代OS的主要目標(biāo)是什么? 2. OS的作用可表現(xiàn)在哪幾個(gè)方面? 3. 為什么說操作系統(tǒng)實(shí)現(xiàn)了對(duì)計(jì)算機(jī)資源的抽象? 4. 試說明推動(dòng)多道批處理系統(tǒng)形成和發(fā)展的主要?jiǎng)恿κ鞘裁础?. 何謂脫機(jī)I/O和聯(lián)機(jī)I/O? 6. 試說明推動(dòng)分時(shí)系統(tǒng)形成

40、和發(fā)展的主要?jiǎng)恿κ鞘裁础?. 實(shí)現(xiàn)分時(shí)系統(tǒng)的關(guān)鍵問題是什么? 應(yīng)如何解決? .第86頁，共1255頁。8. 為什么要引入實(shí)時(shí)操作系統(tǒng)? 9. 什么是硬實(shí)時(shí)任務(wù)和軟實(shí)時(shí)任務(wù)? 試舉例說明。10. 試從交互性、及時(shí)性以及可靠性方面將分時(shí)系統(tǒng)與實(shí)時(shí)系統(tǒng)進(jìn)行比較。11. OS有哪幾大特征? 其最基本的特征是什么? 12. 在多道程序技術(shù)的OS環(huán)境下的資源共享與一般情況下的資源共享有何不同? 對(duì)獨(dú)占資源應(yīng)采取何種共享方式? 13. 什么是時(shí)分復(fù)用技術(shù)? 舉例說明它能提高資源利用率的根本原因是什么。14. 是什么原因使操作系統(tǒng)具有異步性特征? 15. 處理機(jī)管理有哪些主要功能? 其主要任務(wù)是什么? 16.

41、 內(nèi)存管理有哪些主要功能? 其主要任務(wù)是什么? .第87頁，共1255頁。17. 設(shè)備管理有哪些主要功能? 其主要任務(wù)是什么? 18. 文件管理有哪些主要功能? 其主要任務(wù)是什么? 19. 試說明推動(dòng)傳統(tǒng)OS演變?yōu)楝F(xiàn)代OS的主要因素是什么? 20. 什么是微內(nèi)核OS? 21. 微內(nèi)核操作系統(tǒng)具有哪些優(yōu)點(diǎn)? 它為何能有這些優(yōu)點(diǎn)? 22. 現(xiàn)代操作系統(tǒng)較之傳統(tǒng)操作系統(tǒng)又增加了哪些功能和特征? 23. 在微內(nèi)核OS中，為什么要采用客戶/服務(wù)器模式? 24. 在基于微內(nèi)核結(jié)構(gòu)的OS中，應(yīng)用了哪些新技術(shù)? 25. 何謂微內(nèi)核技術(shù)? 在微內(nèi)核中通常提供了哪些功能? .第88頁，共1255頁。第二章 進(jìn)程的

42、描述與控制 2.1 前趨圖和程序執(zhí)行2.2 進(jìn)程的描述2.3 進(jìn)程控制2.4 進(jìn)程同步2.5 經(jīng)典進(jìn)程的同步問題2.6 進(jìn)程通信2.7 線程(Threads)的基本概念2.8 線程的實(shí)現(xiàn)習(xí)題.第89頁，共1255頁。2.1 前趨圖和程序執(zhí)行在早期未配置OS的系統(tǒng)和單道批處理系統(tǒng)中，程序的執(zhí)行方式是順序執(zhí)行，即在內(nèi)存中僅裝入一道用戶程序，由它獨(dú)占系統(tǒng)中的所有資源，只有在一個(gè)用戶程序執(zhí)行完成后，才允許裝入另一個(gè)程序并執(zhí)行?？梢?，這種方式浪費(fèi)資源、系統(tǒng)運(yùn)行效率低等缺點(diǎn)。 .第90頁，共1255頁。2.1.1 前趨圖為了能更好地描述程序的順序和并發(fā)執(zhí)行情況，我們先介紹用于描述程序執(zhí)行先后順序的前趨圖。

43、所謂前趨圖(Precedence Graph)，是指一個(gè)有向無循環(huán)圖，可記為DAG(Directed Acyclic Graph)，它用于描述進(jìn)程之間執(zhí)行的先后順序。圖中的每個(gè)結(jié)點(diǎn)可用來表示一個(gè)進(jìn)程或程序段，乃至一條語句，結(jié)點(diǎn)間的有向邊則表示兩個(gè)結(jié)點(diǎn)之間存在的偏序(Partial Order)或前趨關(guān)系(Precedence Relation)。.第91頁，共1255頁。進(jìn)程(或程序)之間的前趨關(guān)系可用“”來表示，如果進(jìn)程Pi和Pj存在著前趨關(guān)系，可表示為(Pi，Pj)，也可寫成PiPj，表示在Pj開始執(zhí)行之前Pi 必須完成。此時(shí)稱Pi是Pj的直接前趨，而稱Pj是Pi的直接后繼。在前趨圖中，把

44、沒有前趨的結(jié)點(diǎn)稱為初始結(jié)點(diǎn)(Initial Node)，把沒有后繼的結(jié)點(diǎn)稱為終止結(jié)點(diǎn)(Final Node)。此外，每個(gè)結(jié)點(diǎn)還具有一個(gè)重量(Weight)，用于表示該結(jié)點(diǎn)所含有的程序量或程序的執(zhí)行時(shí)間。 .第92頁，共1255頁。在圖2-1(a)所示的前趨圖中，存在著如下前趨關(guān)系：P1P2，P1P3，P1P4，P2P5，P3P5，P4P6，P4P7，P5P8，P6P8，P7P9，P8P9或表示為：P=P1, P2, P3, P4, P5, P6, P7, P8, P9 =(P1, P2), (P1, P3), (P1, P4), (P2, P5), (P3, P5), (P4, P6), (P

45、4, P7), (P5, P8), (P6, P8), (P7, P9), (P8, P9).第93頁，共1255頁。應(yīng)當(dāng)注意，前趨圖中是不允許有循環(huán)的，否則必然會(huì)產(chǎn)生不可能實(shí)現(xiàn)的前趨關(guān)系。如圖2-1(b)所示的前趨關(guān)系中就存在著循環(huán)。它一方面要求在S3開始執(zhí)行之前，S2必須完成，另一方面又要求在S2開始執(zhí)行之前，S3必須完成。顯然，這種關(guān)系是不可能實(shí)現(xiàn)的。S2S3，S3S2.第94頁，共1255頁。圖2-1 前趨圖.第95頁，共1255頁。2.1.2 程序順序執(zhí)行1. 程序的順序執(zhí)行通常，一個(gè)應(yīng)用程序由若干個(gè)程序段組成，每一個(gè)程序段完成特定的功能，它們?cè)趫?zhí)行時(shí)，都需要按照某種先后次序順序執(zhí)行

46、，僅當(dāng)前一程序段執(zhí)行完后，才運(yùn)行后一程序段。例如，在進(jìn)行計(jì)算時(shí)，應(yīng)先運(yùn)行輸入程序，用于輸入用戶的程序和數(shù)據(jù)；然后運(yùn)行計(jì)算程序，對(duì)所輸入的數(shù)據(jù)進(jìn)行計(jì)算；最后才是運(yùn)行打印程序，打印計(jì)算結(jié)果。我們用結(jié)點(diǎn)(Node)代表各程序段的操作(在圖2-1中用圓圈表示)，其中I代表輸入操作，C代表計(jì)算操作，P為打印操作，用箭頭指示操作的先后次序。.第96頁，共1255頁。這樣，上述的三個(gè)程序段間就存在著這樣的前趨關(guān)系：IiCiPi，其執(zhí)行的順序可用前趨圖2-2(a)描述。即使是一個(gè)程序段，也可能存在著執(zhí)行順序問題，下面示出了一個(gè)包含了三條語句的程序段：S1: a :=x+y；S2: b :=a-5；S3: c

47、:=b+1；其中，語句S2必須在語句S1后(即a被賦值)才能執(zhí)行，語句S3也只能在b被賦值后才能執(zhí)行，因此，三條語句存在著這樣的前趨關(guān)系：S1S2S3，應(yīng)按前趨圖2-2(b)所示的順序執(zhí)行。.第97頁，共1255頁。圖2-2程序順序執(zhí)行的前趨圖.第98頁，共1255頁。2. 程序順序執(zhí)行時(shí)的特征由上所述可以得知，在程序順序執(zhí)行時(shí)，具有這樣三個(gè)特征： 順序性：指處理機(jī)嚴(yán)格地按照程序所規(guī)定的順序執(zhí)行，即每一操作必須在下一個(gè)操作開始之前結(jié)束； 封閉性：指程序在封閉的環(huán)境下運(yùn)行，即程序運(yùn)行時(shí)獨(dú)占全機(jī)資源，資源的狀態(tài)(除初始狀態(tài)外)只有本程序才能改變它，程序一旦開始執(zhí)行，其執(zhí)行結(jié)果不受外界因素影響； 可

48、再現(xiàn)性：指只要程序執(zhí)行時(shí)的環(huán)境和初始條件相同，當(dāng)程序重復(fù)執(zhí)行時(shí)，不論它是從頭到尾不停頓地執(zhí)行，還是“停停走走”地執(zhí)行，都可獲得相同的結(jié)果。程序順序執(zhí)行時(shí)的這種特性，為程序員檢測(cè)和校正程序的錯(cuò)誤帶來了很大的方便。.第99頁，共1255頁。2.1.3程序并發(fā)執(zhí)行1. 程序的并發(fā)執(zhí)行我們通過一個(gè)常見的例子來說明程序的順序執(zhí)行和并發(fā)執(zhí)行。在圖2-2中的輸入程序、計(jì)算程序和打印程序三者之間，存在著IiCiPi這樣的前趨關(guān)系，以至對(duì)一個(gè)作業(yè)的輸入、計(jì)算和打印三個(gè)程序段必須順序執(zhí)行。但若是對(duì)一批作業(yè)進(jìn)行處理時(shí)，每道作業(yè)的輸入、計(jì)算和打印程序段的執(zhí)行情況如圖2-3所示。 .第100頁，共1255頁。圖2-3

49、程序并發(fā)執(zhí)行時(shí)的前趨圖 .第101頁，共1255頁。由圖2-3可以看出，存在前趨關(guān)系IiCi，IiIi+1，CiPi，CiCi+1，PiPi+1，而Ii+1和Ci及Pi-1是重疊的，即在Pi-1和Ci以及Ii+1之間，不存在前趨關(guān)系，可以并發(fā)執(zhí)行。對(duì)于具有下述四條語句的程序段：S1: a :=x+2S2: b :=y+4S3: c :=a+bS4: d :=c+b可畫出圖2-4所示的前趨關(guān)系?？梢钥闯觯篠3必須在a和b被賦值后方能執(zhí)行；S4必須在S3之后執(zhí)行；但S1和S2則可以并發(fā)執(zhí)行，因?yàn)樗鼈儽舜嘶ゲ灰蕾嚒?第102頁，共1255頁。 圖2-4 四條語句的前趨關(guān)系 .第103頁，共1255頁

50、。2. 程序并發(fā)執(zhí)行時(shí)的特征在引入了程序間的并發(fā)執(zhí)行功能后，雖然提高了系統(tǒng)的吞吐量和資源利用率，但由于它們共享系統(tǒng)資源，以及它們?yōu)橥瓿赏豁?xiàng)任務(wù)而相互合作，致使在這些并發(fā)執(zhí)行的程序之間必將形成相互制約的關(guān)系，由此會(huì)給程序并發(fā)執(zhí)行帶來新的特征。(1) 間斷性。(2) 失去封閉性。(3) 不可再現(xiàn)性。.第104頁，共1255頁。2.2 進(jìn)程的描述2.2.1 進(jìn)程的定義和特征1. 進(jìn)程的定義 在多道程序環(huán)境下，程序的執(zhí)行屬于并發(fā)執(zhí)行，此時(shí)它們將失去其封閉性，并具有間斷性，以及其運(yùn)行結(jié)果不可再現(xiàn)性的特征。由此，決定了通常的程序是不能參與并發(fā)執(zhí)行的，否則，程序的運(yùn)行也就失去了意義。為了能使程序并發(fā)執(zhí)行，

51、并且可以對(duì)并發(fā)執(zhí)行的程序加以描述和控制，人們引入了“進(jìn)程”的概念。.第105頁，共1255頁。對(duì)于進(jìn)程的定義，從不同的角度可以有不同的定義，其中較典型的定義有：(1) 進(jìn)程是程序的一次執(zhí)行。(2) 進(jìn)程是一個(gè)程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行時(shí)所發(fā)生的活動(dòng)。(3) 進(jìn)程是具有獨(dú)立功能的程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。.第106頁，共1255頁。2. 進(jìn)程的特征進(jìn)程和程序是兩個(gè)截然不同的概念，除了進(jìn)程具有程序所沒有的PCB結(jié)構(gòu)外，還具有下面一些特征：(1) 動(dòng)態(tài)性。(2) 并發(fā)性。(3) 獨(dú)立性。(4) 異步性。.第107頁，共1255頁。2.2.2 進(jìn)程的

52、基本狀態(tài)及轉(zhuǎn)換1. 進(jìn)程的三種基本狀態(tài)由于多個(gè)進(jìn)程在并發(fā)執(zhí)行時(shí)共享系統(tǒng)資源，致使它們?cè)谶\(yùn)行過程中呈現(xiàn)間斷性的運(yùn)行規(guī)律，所以進(jìn)程在其生命周期內(nèi)可能具有多種狀態(tài)。一般而言，每一個(gè)進(jìn)程至少應(yīng)處于以下三種基本狀態(tài)之一：(1) 就緒(Ready)狀態(tài)。(2) 執(zhí)行(Running)狀態(tài)。(3) 阻塞(Block)狀態(tài)。 .第108頁，共1255頁。2. 三種基本狀態(tài)的轉(zhuǎn)換進(jìn)程在運(yùn)行過程中會(huì)經(jīng)常發(fā)生狀態(tài)的轉(zhuǎn)換。例如，處于就緒狀態(tài)的進(jìn)程，在調(diào)度程序?yàn)橹峙淞颂幚頇C(jī)之后便可執(zhí)行，相應(yīng)地，其狀態(tài)就由就緒態(tài)轉(zhuǎn)變?yōu)閳?zhí)行態(tài)；正在執(zhí)行的進(jìn)程(當(dāng)前進(jìn)程)如果因分配給它的時(shí)間片已完而被剝奪處理機(jī)暫停執(zhí)行時(shí)，其狀態(tài)便由執(zhí)行轉(zhuǎn)

53、為就緒；如果因發(fā)生某事件，致使當(dāng)前進(jìn)程的執(zhí)行受阻(例如進(jìn)程訪問某臨界資源，而該資源正被其它進(jìn)程訪問時(shí))，使之無法繼續(xù)執(zhí)行，則該進(jìn)程狀態(tài)將由執(zhí)行轉(zhuǎn)變?yōu)樽枞?。圖2-5示出了進(jìn)程的三種基本狀態(tài)，以及各狀態(tài)之間的轉(zhuǎn)換關(guān)系。.第109頁，共1255頁。圖2-5 進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換.第110頁，共1255頁。3. 創(chuàng)建狀態(tài)和終止?fàn)顟B(tài)1) 創(chuàng)建狀態(tài)如前所述，進(jìn)程是由創(chuàng)建而產(chǎn)生。創(chuàng)建一個(gè)進(jìn)程是個(gè)很復(fù)雜的過程，一般要通過多個(gè)步驟才能完成：如首先由進(jìn)程申請(qǐng)一個(gè)空白PCB，并向PCB中填寫用于控制和管理進(jìn)程的信息；然后為該進(jìn)程分配運(yùn)行時(shí)所必須的資源；最后，把該進(jìn)程轉(zhuǎn)入就緒狀態(tài)并插入就緒隊(duì)列之中。但如果進(jìn)程所

54、需的資源尚不能得到滿足，比如系統(tǒng)尚無足夠的內(nèi)存使進(jìn)程無法裝入其中，此時(shí)創(chuàng)建工作尚未完成，進(jìn)程不能被調(diào)度運(yùn)行，于是把此時(shí)進(jìn)程所處的狀態(tài)稱為創(chuàng)建狀態(tài)。.第111頁，共1255頁。2) 終止?fàn)顟B(tài)進(jìn)程的終止也要通過兩個(gè)步驟：首先，是等待操作系統(tǒng)進(jìn)行善后處理，最后將其PCB清零，并將PCB空間返還系統(tǒng)。當(dāng)一個(gè)進(jìn)程到達(dá)了自然結(jié)束點(diǎn)，或是出現(xiàn)了無法克服的錯(cuò)誤，或是被操作系統(tǒng)所終結(jié)，或是被其他有終止權(quán)的進(jìn)程所終結(jié)，它將進(jìn)入終止?fàn)顟B(tài)。進(jìn)入終止態(tài)的進(jìn)程以后不能再執(zhí)行，但在操作系統(tǒng)中依然保留一個(gè)記錄，其中保存狀態(tài)碼和一些計(jì)時(shí)統(tǒng)計(jì)數(shù)據(jù)，供其他進(jìn)程收集。一旦其他進(jìn)程完成了對(duì)其信息的提取之后，操作系統(tǒng)將刪除該進(jìn)程，即將其

55、PCB清零，并將該空白PCB返還系統(tǒng)。圖2-6示出了增加了創(chuàng)建狀態(tài)和終止?fàn)顟B(tài)后進(jìn)程的五種狀態(tài)及轉(zhuǎn)換關(guān)系圖。.第112頁，共1255頁。圖2-6 進(jìn)程的五種基本狀態(tài)及轉(zhuǎn)換.第113頁，共1255頁。2.2.3 掛起操作和進(jìn)程狀態(tài)的轉(zhuǎn)換1. 掛起操作的引入引入掛起操作的原因，是基于系統(tǒng)和用戶的如下需要：(1) 終端用戶的需要。(2) 父進(jìn)程請(qǐng)求。(3) 負(fù)荷調(diào)節(jié)的需要。(4) 操作系統(tǒng)的需要。 .第114頁，共1255頁。2. 引入掛起原語操作后三個(gè)進(jìn)程狀態(tài)的轉(zhuǎn)換在引入掛起原語Suspend和激活原語Active后，在它們的作用下，進(jìn)程將可能發(fā)生以下幾種狀態(tài)的轉(zhuǎn)換：(1) 活動(dòng)就緒靜止就緒。(2)

56、 活動(dòng)阻塞靜止阻塞。(3) 靜止就緒活動(dòng)就緒。(4) 靜止阻塞活動(dòng)阻塞。.第115頁，共1255頁。3. 引入掛起操作后五個(gè)進(jìn)程狀態(tài)的轉(zhuǎn)換如圖2-8示出了增加了創(chuàng)建狀態(tài)和終止?fàn)顟B(tài)后具有掛起狀態(tài)的進(jìn)程狀態(tài)及轉(zhuǎn)換圖。如圖2-8所示，引進(jìn)創(chuàng)建和終止?fàn)顟B(tài)后，在進(jìn)程狀態(tài)轉(zhuǎn)換時(shí)，與圖2-7所示的進(jìn)程五狀態(tài)轉(zhuǎn)換相比較，要增加考慮下面的幾種情況：(1) NULL創(chuàng)建：(2) 創(chuàng)建活動(dòng)就緒：(3) 創(chuàng)建靜止就緒：(4) 執(zhí)行終止：.第116頁，共1255頁。圖2-7具有掛起狀態(tài)的進(jìn)程狀態(tài)圖 .第117頁，共1255頁。 圖2-8 具有創(chuàng)建、終止和掛起狀態(tài)的進(jìn)程狀態(tài)圖 .第118頁，共1255頁。2.2.4 進(jìn)程

57、管理中的數(shù)據(jù)結(jié)構(gòu)1. 操作系統(tǒng)中用于管理控制的數(shù)據(jù)結(jié)構(gòu) 在計(jì)算機(jī)系統(tǒng)中，對(duì)于每個(gè)資源和每個(gè)進(jìn)程都設(shè)置了一個(gè)數(shù)據(jù)結(jié)構(gòu)，用于表征其實(shí)體，我們稱之為資源信息表或進(jìn)程信息表，其中包含了資源或進(jìn)程的標(biāo)識(shí)、描述、狀態(tài)等信息以及一批指針。通過這些指針，可以將同類資源或進(jìn)程的信息表，或者同一進(jìn)程所占用的資源信息表分類鏈接成不同的隊(duì)列，便于操作系統(tǒng)進(jìn)行查找。 .第119頁，共1255頁。如圖2-9所示，OS管理的這些數(shù)據(jù)結(jié)構(gòu)一般分為以下四類：內(nèi)存表、設(shè)備表、文件表和用于進(jìn)程管理的進(jìn)程表，通常進(jìn)程表又被稱為進(jìn)程控制塊PCB。 .第120頁，共1255頁。圖2-9 操作系統(tǒng)控制表的一般結(jié)構(gòu).第121頁，共1255頁

58、。2. 進(jìn)程控制塊PCB的作用(1) 作為獨(dú)立運(yùn)行基本單位的標(biāo)志。(2) 能實(shí)現(xiàn)間斷性運(yùn)行方式。 (3) 提供進(jìn)程管理所需要的信息。(4) 提供進(jìn)程調(diào)度所需要的信息。(5) 實(shí)現(xiàn)與其它進(jìn)程的同步與通信。.第122頁，共1255頁。3. 進(jìn)程控制塊中的信息在進(jìn)程控制塊中，主要包括下述四個(gè)方面的信息。1) 進(jìn)程標(biāo)識(shí)符進(jìn)程標(biāo)識(shí)符用于唯一地標(biāo)識(shí)一個(gè)進(jìn)程。一個(gè)進(jìn)程通常有兩種標(biāo)識(shí)符：(1) 外部標(biāo)識(shí)符。(2) 內(nèi)部標(biāo)識(shí)符。.第123頁，共1255頁。2) 處理機(jī)狀態(tài)處理機(jī)狀態(tài)信息也稱為處理機(jī)的上下文，主要是由處理機(jī)的各種寄存器中的內(nèi)容組成的。 .第124頁，共1255頁。3) 進(jìn)程調(diào)度信息在OS進(jìn)行調(diào)度時(shí)

59、，必須了解進(jìn)程的狀態(tài)及有關(guān)進(jìn)程調(diào)度的信息，這些信息包括： 進(jìn)程狀態(tài)，指明進(jìn)程的當(dāng)前狀態(tài)，它是作為進(jìn)程調(diào)度和對(duì)換時(shí)的依據(jù)； 進(jìn)程優(yōu)先級(jí)，是用于描述進(jìn)程使用處理機(jī)的優(yōu)先級(jí)別的一個(gè)整數(shù)，優(yōu)先級(jí)高的進(jìn)程應(yīng)優(yōu)先獲得處理機(jī)； 進(jìn)程調(diào)度所需的其它信息，它們與所采用的進(jìn)程調(diào)度算法有關(guān)，比如，進(jìn)程已等待CPU的時(shí)間總和、進(jìn)程已執(zhí)行的時(shí)間總和等； 事件，是指進(jìn)程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)所等待發(fā)生的事件，即阻塞原因。.第125頁，共1255頁。4) 進(jìn)程控制信息是指用于進(jìn)程控制所必須的信息，它包括： 程序和數(shù)據(jù)的地址，進(jìn)程實(shí)體中的程序和數(shù)據(jù)的內(nèi)存或外存地(首)址，以便再調(diào)度到該進(jìn)程執(zhí)行時(shí)，能從PCB中找到其程序和數(shù)

60、據(jù)； 進(jìn)程同步和通信機(jī)制，這是實(shí)現(xiàn)進(jìn)程同步和進(jìn)程通信時(shí)必需的機(jī)制，如消息隊(duì)列指針、信號(hào)量等，它們可能全部或部分地放在PCB中； 資源清單，在該清單中列出了進(jìn)程在運(yùn)行期間所需的全部資源(除CPU以外)，另外還有一張已分配到該進(jìn)程的資源的清單； 鏈接指針，它給出了本進(jìn)程(PCB)所在隊(duì)列中的下一個(gè)進(jìn)程的PCB的首地址。.第126頁，共1255頁。4. 進(jìn)程控制塊的組織方式在一個(gè)系統(tǒng)中，通?？蓳碛袛?shù)十個(gè)、數(shù)百個(gè)乃至數(shù)千個(gè)PCB。為了能對(duì)它們加以有效的管理，應(yīng)該用適當(dāng)?shù)姆绞綄⑦@些PCB組織起來。目前常用的組織方式有以下三種。(1) 線性方式，即將系統(tǒng)中所有的PCB都組織在一張線性表中，將該表的首址存放