操作系統(tǒng)原理與實(shí)訓(xùn)教程課件(完整版)

1、操作系統(tǒng)原理與實(shí)訓(xùn)教程第一章 操作系統(tǒng)概述1.1 操作系統(tǒng)的概念 1.2 操作系統(tǒng)的發(fā)展和分類 1.3 現(xiàn)代主流操作系統(tǒng)簡(jiǎn)介 1.4 操作系統(tǒng)的特征1.5 操作系統(tǒng)的功能1.6 本章小結(jié)1.1 操作系統(tǒng)的概念1.1.1 操作系統(tǒng)的地位 操作系統(tǒng)是以硬件為基礎(chǔ)的系統(tǒng)軟件，是硬件層的第一次擴(kuò)充，在這一層上實(shí)現(xiàn)了操作系統(tǒng)的全部功能，并提供相應(yīng)的接口，其他各層軟件都是在操作系統(tǒng)的基礎(chǔ)上開(kāi)發(fā)的。 1.1.2 操作系統(tǒng)的作用 1.OS作為用戶與計(jì)算機(jī)硬件系統(tǒng)之間的接口 OS作為用戶與計(jì)算機(jī)硬件系統(tǒng)之間接口的含義是：OS處于用戶與計(jì)算機(jī)硬件系統(tǒng)之間，用戶通過(guò)OS來(lái)使用計(jì)算機(jī)系統(tǒng)?；蛘哒f(shuō)，用戶在OS幫助下，能

2、夠方便、快捷、安全、可靠地操縱計(jì)算機(jī)硬件和運(yùn)行自己的程序。應(yīng)注意，OS是一個(gè)系統(tǒng)軟件，因而這種接口是軟件接口。 2. OS作為計(jì)算機(jī)系統(tǒng)資源的管理者 在一個(gè)計(jì)算機(jī)系統(tǒng)中，通常都含有各種各樣的硬件和軟件資源。歸納起來(lái)可將資源分為四類：處理器、存儲(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è)備的分配與操縱；文件管理，負(fù)責(zé)文件的存取、共享和保護(hù)。可見(jiàn)，OS確是計(jì)算機(jī)系統(tǒng)資源的管理者。事實(shí)上，當(dāng)今世界上廣為流行的一個(gè)關(guān)于OS作用的觀點(diǎn)，正是把O

3、S作為計(jì)算機(jī)系統(tǒng)的資源管理者。 3. OS用作擴(kuò)充機(jī)器 對(duì)于一臺(tái)完全無(wú)軟件的計(jì)算機(jī)系統(tǒng)(即裸機(jī))，即使其功能再?gòu)?qiáng)，也必定是難于使用的。如果我們?cè)诼銠C(jī)上覆蓋上一層I/O設(shè)備管理軟件，用戶便可利用它所提供的I/O命令，來(lái)進(jìn)行數(shù)據(jù)輸入和打印輸出。此時(shí)用戶所看到的機(jī)器， 將是一臺(tái)比裸機(jī)功能更強(qiáng)、使用更方便的機(jī)器。通常把覆蓋了軟件的機(jī)器稱為擴(kuò)充機(jī)器或虛機(jī)器。操作系統(tǒng)的定義 可見(jiàn)，操作系統(tǒng)是計(jì)算機(jī)系統(tǒng)中的一個(gè)系統(tǒng)軟件，是一些程序和模塊的集合，它們以最有效合理的方式組織和管理計(jì)算機(jī)的軟硬件資源，合理地組織計(jì)算機(jī)的工作流程，控制程序的執(zhí)行并向用戶提供各種服務(wù)功能，使用戶能夠靈活、方便、有效地使用計(jì)算機(jī)，使整個(gè)

4、計(jì)算機(jī)系統(tǒng)能高效地運(yùn)行，從而在計(jì)算機(jī)與用戶之間起到接口的作用。 總結(jié)：OS是一組控制和管理計(jì)算機(jī)硬件和軟件資源，合理地對(duì)各類作業(yè)進(jìn)行調(diào)度，以及方便用戶使用的程序的集合。1.2 操作系統(tǒng)的發(fā)展和分類1.2.1 無(wú)操作系統(tǒng)的計(jì)算機(jī)系統(tǒng) 1. 人工操作方式 CPU和I/O串行操作。 2. 脫機(jī)輸入/輸出方式 這種脫機(jī)I/O方式的主要優(yōu)點(diǎn)如下：減少了CPU的空閑時(shí)間。 (2) 提高I/O速度。 圖 1-2 脫機(jī)I/O示意圖在無(wú)OS的階段，即在人工操作方式和脫機(jī)I/O方式下，都離不開(kāi)人的監(jiān)控。1.2.2 批處理系統(tǒng) 1. 單道批處理系統(tǒng)的處理過(guò)程 單道批處理系統(tǒng)的特征 單道批處理系統(tǒng)是最早出現(xiàn)的一種OS

5、，嚴(yán)格地說(shuō)，它只能算作是OS的前身而并非是現(xiàn)在人們所理解的OS。盡管如此，該系統(tǒng)比起人工操作方式的系統(tǒng)已有很大進(jìn)步。 該系統(tǒng)的主要特征如下： (1) 自動(dòng)性。 (2) 順序性。 (3) 單道性。 2. 多道批處理系統(tǒng) 多道程序設(shè)計(jì)的基本概念 在單道批處理系統(tǒng)中，內(nèi)存中僅有一道作業(yè)，它無(wú)法充分利用系統(tǒng)中的所有資源，致使系統(tǒng)性能較差。為了進(jìn)一步提高資源的利用率和系統(tǒng)吞吐量，在60年代中期又引入了多道程序設(shè)計(jì)技術(shù)，由此而形成了多道批處理系統(tǒng)。在該系統(tǒng)中， 用戶所提交的作業(yè)都先存放在外存上并排成一個(gè)隊(duì)列，稱為“后備隊(duì)列”；然后，由作業(yè)調(diào)度程序按一定的算法從后備隊(duì)列中選擇若干個(gè)作業(yè)調(diào)入內(nèi)存，使它們共享C

6、PU和系統(tǒng)中的各種資源。 (2) 可提高內(nèi)存和I/O設(shè)備利用率。 (3) 增加系統(tǒng)吞吐量。在OS中引入多道程序設(shè)計(jì)技術(shù)可帶來(lái)以下好處：提高CPU的利用率。 多道批處理系統(tǒng)的特征 多道性。 (2) 無(wú)序性。 (3) 調(diào)度性。 多道批處理系統(tǒng)的優(yōu)缺點(diǎn) 資源利用率高。 (2) 系統(tǒng)吞吐量大。 (3) 平均周轉(zhuǎn)時(shí)間長(zhǎng)。 (4) 無(wú)交互能力。 1.2.3 分時(shí)系統(tǒng) 1. 分時(shí)系統(tǒng)的產(chǎn)生 用戶的需求具體表現(xiàn)在以下幾個(gè)方面： (1) 人機(jī)交互。 (2) 共享主機(jī)。 (3) 便于用戶上機(jī)。 2. 分時(shí)系統(tǒng)的特征 多路性。(2) 獨(dú)占性。 (3)交互性。(4)及時(shí)性。 1.2.4 實(shí)時(shí)系統(tǒng) 所謂“實(shí)時(shí)”，是表示

7、“及時(shí)”，而實(shí)時(shí)系統(tǒng)(Real-Time System)是指系統(tǒng)能及時(shí)(或即時(shí))響應(yīng)外部事件的請(qǐng)求，在規(guī)定的時(shí)間內(nèi)完成對(duì)該事件的處理，并控制所有實(shí)時(shí)任務(wù)協(xié)調(diào)一致地運(yùn)行。 應(yīng)用需求 實(shí)時(shí)控制。 (2) 實(shí)時(shí)信息處理。 1.2.5 網(wǎng)絡(luò)操作系統(tǒng) 網(wǎng)絡(luò)操作系統(tǒng)（NOS）可以看作是在網(wǎng)絡(luò)環(huán)境下工作的操作系統(tǒng)軟件，可簡(jiǎn)單地定義為管理整個(gè)網(wǎng)絡(luò)資源和方便網(wǎng)絡(luò)用戶的軟件集合。網(wǎng)絡(luò)操作系統(tǒng)是計(jì)算機(jī)網(wǎng)絡(luò)的心臟和靈魂，是向網(wǎng)絡(luò)計(jì)算機(jī)提供服務(wù)的特殊的操作系統(tǒng)。它在計(jì)算機(jī)操作系統(tǒng)下工作，使計(jì)算機(jī)操作系統(tǒng)增加了網(wǎng)絡(luò)操作所需要的能力。 網(wǎng)絡(luò)操作系統(tǒng)具有網(wǎng)絡(luò)通信、資源管理、網(wǎng)絡(luò)服務(wù)、網(wǎng)絡(luò)管理和相互操作能力等功能。 目前局域網(wǎng)

8、中主要存在以下幾類網(wǎng)絡(luò)操作系統(tǒng)： 1. Windows類 ：Windows NT 4.0 Server、Windows 2000 Server/Advance Server，以及最新的Windows 2003 Server/ Advance Server等，工作站系統(tǒng)可以采用任一Windows或非Windows操作系統(tǒng)，包括個(gè)人操作系統(tǒng)，如Windows9x/ME/XP等。2. NetWare類3. Unix系統(tǒng) 4. Linux ：中文版本的Linux，如Redhat(紅帽子)，紅旗Linux等，體現(xiàn)在安全性和穩(wěn)定性。 1.2.6 分布式操作系統(tǒng) 一個(gè)分布式系統(tǒng)是一些獨(dú)立的計(jì)算機(jī)的集合，但是

9、對(duì)這個(gè)系統(tǒng)的用戶來(lái)說(shuō)，系統(tǒng)就象一臺(tái)計(jì)算機(jī)一樣。從硬件角度來(lái)講，每臺(tái)計(jì)算機(jī)都是自主的；從軟件角度來(lái)講，用戶將整個(gè)系統(tǒng)看作是一臺(tái)計(jì)算機(jī)。許多現(xiàn)代操作系統(tǒng)都提供分布處理功能， 如Solaris MC。1.2.7 嵌入式操作系統(tǒng)嵌入式操作系統(tǒng)是嵌入式系統(tǒng)的操作系統(tǒng)。它們通常被設(shè)計(jì)非常緊湊有效，嵌入式操作系統(tǒng)多數(shù)也是實(shí)時(shí)操作系統(tǒng)。 從應(yīng)用角度可分為通用型嵌入式操作系統(tǒng)和專用型嵌入式操作系統(tǒng)。常見(jiàn)的通用型嵌入式操作系統(tǒng)有Linux、Windows CE等。常用的專用型嵌入式操作系統(tǒng)有Symbian等。 嵌入式系統(tǒng)是以嵌入式計(jì)算機(jī)為技術(shù)核心，面向用戶、面向產(chǎn)品、面向應(yīng)用，軟硬件可裁減的；適用于對(duì)功能、可靠性

10、、成本體積、功耗等綜合性能有嚴(yán)格要求的專用計(jì)算機(jī)系統(tǒng)。 嵌入式系統(tǒng)應(yīng)具有的特點(diǎn)是：高可靠性；實(shí)時(shí)性；嵌入式系統(tǒng)和具體應(yīng)用有機(jī)地結(jié)合在一起，它的升級(jí)換代也是和具體產(chǎn)品同步進(jìn)行；嵌入式系統(tǒng)中的軟件代碼要求高質(zhì)量、高可靠性；一般都固化在只讀存儲(chǔ)器中而不是存儲(chǔ)在磁盤(pán)等載體中。 Microsoft Windows CE為微軟針對(duì)個(gè)人電腦以外的計(jì)算機(jī)產(chǎn)品所研發(fā)的嵌入式操作系統(tǒng)。 目前最新的Windows CE為Windows CE 6.0，為微軟的.NET最新家族成員，除100%兼容于Windows CE外，并強(qiáng)化許多功能；讓正在學(xué)習(xí).NET或已擁有.NET程序開(kāi)發(fā)技術(shù)的開(kāi)發(fā)人員能迅速而順利的在搭載Win

11、dows CE .NET系統(tǒng)的裝置上開(kāi)發(fā)應(yīng)用程序。 用于掌上電腦（Pocket PC）以及智能手機(jī)（Smart Phone）上的Windows CE系統(tǒng)稱為Windows Mobile，目前的最新版本為Windows Mobile 5.0，代號(hào)為Magneto。 1.3 現(xiàn)代主流操作系統(tǒng)簡(jiǎn)介 1.3.1 MS-DOS及Windows系列1. MS-DOSMS-DOS是Microsoft Disk Operating System的簡(jiǎn)稱，最基本的MS-DOS系統(tǒng)由一個(gè)基于MBR的BOOT引導(dǎo)程序和三個(gè)文件模塊組成。這三個(gè)模塊是輸入輸出模塊(IO.SYS)、文件管理模塊(MSDOS.SYS)及命令

12、解釋模塊(COMMAND.COM)。為滿足用戶對(duì)操作更方便、直接和靈活的要求，微軟公司推出了一種采用圖形用戶界面（Graphics User Interface，GUI）的新穎的操作系統(tǒng)，Windows操作系統(tǒng)。在近20年的發(fā)展過(guò)程中，微軟主要推出的版本有Windows3.X，Windows 9X，Windows NT，Windows 2000，Windows Me，Windows XP和Windows 2003。Windows操作系統(tǒng)以其靈活、快速、便宜等優(yōu)點(diǎn)，逐漸占據(jù)了PC微型計(jì)算機(jī)上的主導(dǎo)地位。2. Windows 3.x、Windows 95/98及Windows Me的發(fā)展歷史Win

13、dows NT系列、Windows CE系列和Windows 2000/2003Windows Vista1.3.2UNIX大家族UNIX概述Unix系統(tǒng)于1969年問(wèn)世，是一個(gè)多用戶、多任務(wù)的分時(shí)操作系統(tǒng)。最初由貝爾實(shí)驗(yàn)室開(kāi)發(fā)在PDP-7上實(shí)現(xiàn)的。貝爾實(shí)驗(yàn)室和其他一些部門(mén)在Unix上的開(kāi)發(fā)工作，導(dǎo)致一系列Unix版本的產(chǎn)生。后來(lái)，又憑借其性能的完善和良好的可移植性，經(jīng)歷不斷的發(fā)展、演變，并廣泛的應(yīng)用于小型計(jì)算機(jī)、超級(jí)小型計(jì)算機(jī)乃至大型計(jì)算機(jī)上。2. UNIX的發(fā)展1.3.3自由軟件LinuxLinux是一套免費(fèi)使用和自由傳播的類Unix操作系統(tǒng)，Linux系統(tǒng)是由全世界各地的成千上萬(wàn)的程序員

14、設(shè)計(jì)和實(shí)現(xiàn)的。Linux的出現(xiàn)，最早開(kāi)始于一位名叫Linus Torvalds的計(jì)算機(jī)業(yè)余愛(ài)好者，當(dāng)時(shí)他是芬蘭赫爾辛基大學(xué)的學(xué)生。他的目的是想設(shè)計(jì)一個(gè)代替Minix的操作系統(tǒng)，這個(gè)操作系統(tǒng)具有Unix操作系統(tǒng)的全部功能，因而開(kāi)始了Linux雛形的設(shè)計(jì)。 發(fā)展至今Linux有很多發(fā)行版本，較流行的有：RedHat Linux、Debian Linux、RedFlag Linux等。 1Linux的興起2Linux概述3Linux的優(yōu)勢(shì) 4Linux應(yīng)用領(lǐng)域 1.4 操作系統(tǒng)的特性1.4.1 并發(fā)性 并行性和并發(fā)性是既相似又有區(qū)別的兩個(gè)概念。 并行性是指兩個(gè)或多個(gè)事件在同一時(shí)刻發(fā)生； 并發(fā)性是指兩

15、個(gè)或多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生。 1.4.2 共享性 在操作系統(tǒng)環(huán)境下，所謂共享是指系統(tǒng)中的資源可供內(nèi)存中多個(gè)并發(fā)執(zhí)行的進(jìn)程(線程)共同使用。由于資源屬性的不同，進(jìn)程對(duì)資源共享的方式也不同，目前主要有以下兩種資源共享方式。 互斥共享方式 系統(tǒng)中的某些資源，如打印機(jī)、磁帶機(jī)，雖然它們可以提供給多個(gè)進(jìn)程(線程)使用，但為使所打印或記錄的結(jié)果不致造成混淆，應(yīng)規(guī)定在一段時(shí)間內(nèi)只允許一個(gè)進(jìn)程(線程)訪問(wèn)該資源。把在一段時(shí)間內(nèi)只允許一個(gè)進(jìn)程訪問(wèn)的資源稱為臨界資源或獨(dú)占資源。 計(jì)算機(jī)系統(tǒng)中的大多數(shù)物理設(shè)備，以及某些軟件中所用的棧、變量和表格，都屬于臨界資源，它們要求被互斥地共享。 同時(shí)訪問(wèn)方式 系統(tǒng)中還有

16、另一類資源，允許在一段時(shí)間內(nèi)由多個(gè)進(jìn)程“同時(shí)”對(duì)它們進(jìn)行訪問(wèn)。這里所謂的“同時(shí)”往往是宏觀上的，而在微觀上，這些進(jìn)程可能是交替地對(duì)該資源進(jìn)行訪問(wèn)。典型的可供多個(gè)進(jìn)程“同時(shí)”訪問(wèn)的資源是磁盤(pán)設(shè)備。 并發(fā)和共享是操作系統(tǒng)的兩個(gè)最基本的特征，它們又是互為存在的條件。1.4.3 異步性 在多道程序環(huán)境下，允許多個(gè)進(jìn)程并發(fā)執(zhí)行， 但只有進(jìn)程在獲得所需的資源后方能執(zhí)行。由于資源等因素的限制，使進(jìn)程的執(zhí)行通常都不是“一氣呵成”，而是以“停停走走”的方式運(yùn)行。 很可能是先進(jìn)入內(nèi)存的作業(yè)后完成； 而后進(jìn)入內(nèi)存的作業(yè)先完成。 1.4.4 虛擬性 操作系統(tǒng)中的所謂“虛擬”，是指通過(guò)某種技術(shù)把一個(gè)物理實(shí)體變?yōu)槿舾蓚€(gè)邏

17、輯上的對(duì)應(yīng)物。物理實(shí)體(前者)是實(shí)的， 即實(shí)際存在的；而后者是虛的，是用戶感覺(jué)上的東西。相應(yīng)地，用于實(shí)現(xiàn)虛擬的技術(shù)，稱為虛擬技術(shù)。在OS中利用了多種虛擬技術(shù)，分別用來(lái)實(shí)現(xiàn)虛擬處理機(jī)、虛擬內(nèi)存、 虛擬外部設(shè)備和虛擬信道等。 1.5 操作系統(tǒng)的功能 1.5.1 處理機(jī)管理 1. 進(jìn)程控制 2. 進(jìn)程同步 3. 進(jìn)程通信 4. 進(jìn)程調(diào)度1.5.2 存儲(chǔ)器管理內(nèi)存分配內(nèi)存保護(hù)地址映射內(nèi)存擴(kuò)充1.5.3 設(shè)備管理功能緩沖管理設(shè)備分配設(shè)備處理設(shè)備獨(dú)立性和虛擬設(shè)備1.5.4 文件管理文件存儲(chǔ)空間的管理目錄管理文件讀/寫(xiě)管理文件存取控制1.5.5 用戶接口命令接口脫機(jī)命令接口程序接口圖形接口1.6 本章小結(jié)操

18、作系統(tǒng)是配置在計(jì)算機(jī)硬件上的第一層軟件，是對(duì)硬件系統(tǒng)的首次擴(kuò)充。操作系統(tǒng)是一組控制和管理計(jì)算機(jī)硬件和軟件資源，合理地組織計(jì)算機(jī)工作流程，并為用戶使用計(jì)算機(jī)提供方便的程序和數(shù)據(jù)的集合。操作系統(tǒng)從形成發(fā)展至今可分為批處理系統(tǒng)、分時(shí)系統(tǒng)、實(shí)時(shí)系統(tǒng)、網(wǎng)絡(luò)操作系統(tǒng)和分布式操作系統(tǒng)等等，其中批處理操作系統(tǒng)、分時(shí)操作系統(tǒng)、實(shí)時(shí)操作系統(tǒng)是操作系統(tǒng)的三種基本類型。每個(gè)操作系統(tǒng)均具有自身的特點(diǎn)，但各種操作系統(tǒng)又都具有四個(gè)共同的基本特征，即并發(fā)性、共享性、虛擬性和異步性。其中并發(fā)性是操作系統(tǒng)最重要的特征，其他三個(gè)特征是以并發(fā)性為前提的。從系統(tǒng)資源的角度看，操作系統(tǒng)有處理機(jī)管理、存儲(chǔ)管理、設(shè)備管理和文件管理的功能，從

19、用戶角度看，操作系統(tǒng)還要具有為用戶提供接口，方便用戶使用的功能。第二章 進(jìn)程管理 2.1 進(jìn)程的引入 2.2 進(jìn)程控制 2.3 進(jìn)程同步與互斥2.4 進(jìn)程通信 2.5 進(jìn)程調(diào)度2.6 死鎖 2.7 線程2.8 本章小結(jié)2.1 進(jìn)程的引入 2.1.1 程序的順序執(zhí)行 僅當(dāng)前一操作(程序段)執(zhí)行完后，才能執(zhí)行后繼操作。例如，在進(jìn)行計(jì)算時(shí)，總須先輸入用戶的程序和數(shù)據(jù)，然后進(jìn)行計(jì)算，最后才能打印計(jì)算結(jié)果。 S1: a=x+y; S2: b=a-5; S3: c=b+1;圖 2-1 程序的順序執(zhí)行 程序順序執(zhí)行時(shí)的特征 順序性：(2) 封閉性： (3) 可再現(xiàn)性： 2.1.2 程序的并發(fā)執(zhí)行圖 2-2

20、并發(fā)執(zhí)行時(shí)的前趨圖 程序的并發(fā)執(zhí)行的特征（1）間斷性（2）失去封閉性（3）不可再現(xiàn)性 例如，有兩個(gè)循環(huán)程序A和B，它們都要對(duì)一個(gè)變量N進(jìn)行操作。程序A：N:=N+1; 程序B：print(N); N:=0當(dāng)程序A、B并發(fā)執(zhí)行時(shí)，可能會(huì)出現(xiàn)三種情況： 1.進(jìn)程的定義：較典型的進(jìn)程定義有： (1) 進(jìn)程是程序的一次執(zhí)行。 (2) 進(jìn)程是一個(gè)程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行時(shí)所發(fā)生的活動(dòng)。 (3) 進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過(guò)程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。 在引入了進(jìn)程實(shí)體的概念后，我們可以把傳統(tǒng)OS中的進(jìn)程定義為：“進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過(guò)程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單

21、位”。 2.1.3 進(jìn)程2. 進(jìn)程的結(jié)構(gòu)：由程序段、數(shù)據(jù)段和PCB組成。PCB程序段數(shù)據(jù)段數(shù)據(jù)段1PCB程序段PCB1PCB2數(shù)據(jù)段2程序段1PCB數(shù)據(jù)段PCB1PCB2程序段2數(shù)據(jù)段PCB程序段PCB圖2-3進(jìn)程的結(jié)構(gòu)表征3. 進(jìn)程的特征 結(jié)構(gòu)特征：程序段、數(shù)據(jù)段、PCB 動(dòng)態(tài)性：進(jìn)程有生命周期。 并發(fā)性：可以并發(fā)執(zhí)行。 獨(dú)立性：獨(dú)立分配資源和調(diào)度的基本單位。 異步性：進(jìn)程按各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)。2.1.4 進(jìn)程的三種狀態(tài)及其轉(zhuǎn)換 1.進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換 (1)就緒(Ready)狀態(tài)：得到了除了CPU以外的所有必要資源。 (2)執(zhí)行狀態(tài)：已獲得CPU，其程序正在執(zhí)行。

22、(3)等待狀態(tài)（阻塞狀態(tài)）：由于發(fā)生某事件而暫時(shí)無(wú)法繼續(xù) 執(zhí)行時(shí)，放棄CPU而處于暫停狀態(tài)。 進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換 或中斷（等待事件）（事件發(fā)生）進(jìn)程的狀態(tài)轉(zhuǎn)換2具有掛起狀態(tài)的進(jìn)程狀態(tài)轉(zhuǎn)換掛起活動(dòng)就緒靜止就緒執(zhí)行掛起激活事件發(fā)生掛起活動(dòng)阻塞靜止阻塞激活事件發(fā)生等待事件2.1.5 進(jìn)程控制塊PCB1. 進(jìn)程控制塊的定義及作用 (1)PCB是進(jìn)程實(shí)體的一部分。(2) OS是根據(jù)PCB來(lái)對(duì)并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的。(3)PCB是進(jìn)程存在的唯一標(biāo)志。(4)PCB應(yīng)常駐內(nèi)存，存放在OS中專門(mén)開(kāi)辟的PCB區(qū)內(nèi)。2. 進(jìn)程控制塊中的信息 1) 進(jìn)程標(biāo)識(shí)符 進(jìn)程標(biāo)識(shí)符用于惟一地標(biāo)識(shí)一個(gè)進(jìn)程。2)

23、處理機(jī)狀態(tài) 通用寄存器， 指令計(jì)數(shù)器， 程序狀態(tài)字PSW， 用戶棧指針。3) 進(jìn)程調(diào)度信息 進(jìn)程狀態(tài)， 進(jìn)程優(yōu)先級(jí)， 進(jìn)程調(diào)度所需的其它信息（它們與所采用的進(jìn)程調(diào)度算法有關(guān)） 事件，即阻塞原因。4) 進(jìn)程控制信息 程序和數(shù)據(jù)的地址， 進(jìn)程同步和通信機(jī)制，指實(shí)現(xiàn)進(jìn)程同步和進(jìn)程通信時(shí)必需的機(jī)制， 如消息隊(duì)列指針、信號(hào)量等； 資源清單， 鏈接指針，3. 進(jìn)程控制塊的組織方式 （1）線性表方式3. 進(jìn)程控制塊的組織方式 （2）鏈接表方式 圖2-7 PCB的鏈接組織方式 （3）索引表方式圖2-8 PCB的鏈接組織方式2.2進(jìn)程控制進(jìn)程控制是指系統(tǒng)使用一些具有特定功能的程序段來(lái)創(chuàng)建、撤消進(jìn)程以及完成進(jìn)程各

24、狀態(tài)間的轉(zhuǎn)換，從而達(dá)到各進(jìn)程高效率地并發(fā)執(zhí)行和協(xié)調(diào)、實(shí)現(xiàn)資源的共享。2.2.1 原語(yǔ)進(jìn)程控制一般是由OS的內(nèi)核來(lái)實(shí)現(xiàn)的。內(nèi)核是OS中最常用最核心的部分，它是由具有各種功能的程序模塊組成的，是對(duì)整個(gè)OS起指揮和控制作用的，是對(duì)裸機(jī)的首次擴(kuò)充。 內(nèi)核中所包含的原語(yǔ)主要有進(jìn)程控制原語(yǔ)、進(jìn)程通信原語(yǔ)、資源管理原語(yǔ)以及其他方面的原語(yǔ)。 原語(yǔ)：是指由若干條機(jī)器指令構(gòu)成的并用以完成特定功能的一段程序，這段程序在執(zhí)行期間是不可分割的。 2.2.2 進(jìn)程的創(chuàng)建與撤銷1.創(chuàng)建進(jìn)程原語(yǔ) 在多道程序環(huán)境中，只有（作為）進(jìn)程（時(shí)）才能在系統(tǒng)中運(yùn)行。因此，為使程序能運(yùn)行就必須為它創(chuàng)建進(jìn)程。導(dǎo)致一個(gè)進(jìn)程去創(chuàng)建另一進(jìn)程的典型

25、事件，可有以下四類：用戶登錄作業(yè)調(diào)度提供服務(wù)應(yīng)用請(qǐng)求（由應(yīng)用進(jìn)程自己創(chuàng)建一個(gè)新進(jìn)程）由系統(tǒng)內(nèi)核創(chuàng)建進(jìn)程創(chuàng)建原語(yǔ)流程圖 2.撤消進(jìn)程原語(yǔ) 以下幾種情況導(dǎo)致進(jìn)程被撤消：該進(jìn)程已完成所要求的功能而正常終止。由于某種錯(cuò)誤導(dǎo)致非正常終止。祖先進(jìn)程要求撤消某個(gè)子進(jìn)程。無(wú)論哪一種情況導(dǎo)致進(jìn)程被撤消，進(jìn)程都必須釋放它所占用的各種資源和PCB 結(jié)構(gòu)本身，以利于資源的有效利用。另外，當(dāng)一個(gè)祖先進(jìn)程撤消某個(gè)子進(jìn)程時(shí)，還需審查該子進(jìn)程是否還有自己的子孫進(jìn)程，若有的話，還需撤消其子孫進(jìn)程的 PCB結(jié)構(gòu)和釋放它們所占有的資源。 2.2.3 進(jìn)程的阻塞與喚醒1.阻塞進(jìn)程原語(yǔ) 阻塞原語(yǔ)在一個(gè)進(jìn)程期待某一事件發(fā)生，但發(fā)生條件尚

26、不具備時(shí)，被該進(jìn)程自己調(diào)用來(lái)阻塞自己。阻塞原語(yǔ)在阻塞一個(gè)進(jìn)程時(shí)，由于該進(jìn)程正處于執(zhí)行狀態(tài)，故應(yīng)先中斷處理機(jī)和保存該進(jìn)程的CPU現(xiàn)場(chǎng)。然后將被阻塞進(jìn)程置“阻塞”狀態(tài)后插入等待隊(duì)列中，再轉(zhuǎn)進(jìn)程調(diào)度程序選擇新的就緒進(jìn)程投入運(yùn)行。這里，轉(zhuǎn)進(jìn)程調(diào)度程序是很重要的，否則，處理機(jī)將會(huì)出現(xiàn)空轉(zhuǎn)而浪費(fèi)資源。 圖 2-10 阻塞原語(yǔ)圖2.喚醒進(jìn)程原語(yǔ) 當(dāng)?shù)却?duì)列中的進(jìn)程所等待的事件發(fā)生時(shí)，等待該事件的所有進(jìn)程都將被喚醒。喚醒一個(gè)進(jìn)程有兩種方法：一種是由系統(tǒng)進(jìn)程喚醒。另一種是由事件發(fā)生進(jìn)程喚醒。當(dāng)由系統(tǒng)進(jìn)程喚醒等待進(jìn)程時(shí)，系統(tǒng)進(jìn)程統(tǒng)一控制事件的發(fā)生并將“事件發(fā)生”這一消息通知等待進(jìn)程。從而使得該進(jìn)程因等待事件已發(fā)生

27、而進(jìn)入就緒隊(duì)列。由事件發(fā)生進(jìn)程喚醒時(shí)，事件發(fā)生進(jìn)程和被喚醒進(jìn)程之間是合作關(guān)系。圖 2-11 喚醒原語(yǔ)2.2.4 進(jìn)程的掛起和激活 掛起進(jìn)程原語(yǔ) 當(dāng)出現(xiàn)了引起進(jìn)程掛起的事件時(shí)，系統(tǒng)將利用掛起原語(yǔ)將處于阻塞狀態(tài)的進(jìn)程掛起。引起掛起狀態(tài)的原因：終端用戶的請(qǐng)求。父進(jìn)程的請(qǐng)求。負(fù)荷調(diào)節(jié)的需要。OS的需要。掛起原語(yǔ)的執(zhí)行過(guò)程是：首先檢查被掛起進(jìn)程的狀態(tài)，若處于活動(dòng)就緒狀態(tài)，便將其改為靜止就緒；對(duì)于活動(dòng)阻塞狀態(tài)的進(jìn)程，則將之改為靜止阻塞。若被掛起的進(jìn)程正在執(zhí)行，便將其改為靜止就緒，然后轉(zhuǎn)向調(diào)度程序重新調(diào)度。2.激活進(jìn)程原語(yǔ) 當(dāng)發(fā)生激活進(jìn)程的事件時(shí)，若進(jìn)程駐留在外存而內(nèi)存已有足夠的空間，則可將在外存上處于靜止

28、就緒狀態(tài)的進(jìn)程換入內(nèi)存。這時(shí)，系統(tǒng)將利用激活原語(yǔ)將指定進(jìn)程激活。 激活原語(yǔ)先將進(jìn)程從外存調(diào)入內(nèi)存，檢查該進(jìn)程的現(xiàn)行狀態(tài)，若是靜止就緒便將其改為活動(dòng)就緒，若為靜止阻塞便將其改為活動(dòng)阻塞。 可見(jiàn)，為了使系統(tǒng)內(nèi)部進(jìn)程正常運(yùn)行，進(jìn)程的阻塞和喚醒、掛起和激活要成對(duì)出現(xiàn)。2.3 進(jìn) 程 同 步與互斥 進(jìn)程之間 兩種形式的制約關(guān)系 直接相互制約關(guān)系：進(jìn)程間的合作。間接相互制約關(guān)系：共享系統(tǒng)中的資源。 進(jìn)程同步：是進(jìn)程之間共同完成一項(xiàng)任務(wù)時(shí)直接發(fā)生相互作用的關(guān)系。進(jìn)程互斥：并發(fā)執(zhí)行的進(jìn)程因競(jìng)爭(zhēng)同一資源而導(dǎo)致的相互排斥的關(guān)系稱為進(jìn)程間的互斥。1. 臨界資源 臨界資源：一次僅允許一個(gè)進(jìn)程使用的資源稱為臨界資源。

29、臨界資源分為硬件、軟件臨界資源。硬件臨界資源如打印機(jī)，軟件臨界資源如某些變量、表格，也不允許兩個(gè)進(jìn)程同時(shí)使用。2.3.1 臨界資源與臨界區(qū) 例：假設(shè)一個(gè)飛機(jī)訂票系統(tǒng)有兩個(gè)終端，執(zhí)行并發(fā)進(jìn)程：T1（x） T2（x） begin if x=1 then x=x-1; else printf(“None”); endx=x-1語(yǔ)句的機(jī)器語(yǔ)言實(shí)現(xiàn)：register1:=x;register1:=register1-1; x:=register1; 雖然上面的兩個(gè)終端程序，在分別看時(shí)都是正確的，而且兩者在順序執(zhí)行時(shí)其結(jié)果也會(huì)是正確的，但若并發(fā)執(zhí)行時(shí)，就會(huì)出現(xiàn)差錯(cuò)，問(wèn)題就在于這兩個(gè)進(jìn)程共享變量x。兩個(gè)終端

30、如果都對(duì)x進(jìn)行減1操作，這兩個(gè)操作在用機(jī)器指令實(shí)現(xiàn)時(shí)， 可用下面的形式描述： T1(x) T2(x) register1:=x; register2 := x; register1:=register1-1; register2:=register2-1; x:= register1; x:= register2; 假設(shè)：x的當(dāng)前值是5。如果T1進(jìn)程先執(zhí)行左列的三條機(jī)器語(yǔ)言語(yǔ)句，然后T2進(jìn)程再執(zhí)行右列的三條語(yǔ)句， 則最后共享變量counter的值為3；反之也正確。但是，如果按下述順序執(zhí)行： register1:=x; (register 1=5) register1:=register1-1;

31、 (register 1=4) register2 := x; (register 2=5) register2:=register2-1; (register 2=4) x:= register1; (x=4) x:= register2; (x=4)所以，就要把變量x當(dāng)作臨界資源處理，即要互斥地訪問(wèn)x。 2. 臨界區(qū)(critical section) 可把一個(gè)訪問(wèn)臨界資源的循環(huán)進(jìn)程描述如下：repeat critical section; remainder section;until false; entry sectionexit section臨界區(qū)：一個(gè)進(jìn)程訪問(wèn)臨界資源的那段代碼

32、稱為臨界區(qū)。同步機(jī)制應(yīng)遵循的規(guī)則： 空閑讓進(jìn)。(2) 忙則等待。 (3) 有限等待。 (4) 讓權(quán)等待。 其實(shí), 互斥關(guān)系也是一種協(xié)調(diào)關(guān)系, 從廣義上講它也屬于同步關(guān)系的范疇。 2.3.2 信號(hào)量及P、V操作 1. 信號(hào)量及P、V操作信號(hào)量：一個(gè)具有非負(fù)初值的整型變量，并且有一個(gè)隊(duì)列與它關(guān)聯(lián)。因此，定義一個(gè)信號(hào)量時(shí)，要給出它的初值，并給出與它相關(guān)的隊(duì)列指針。信號(hào)量的定義如下：type semaphore=record /*定義信號(hào)量*/ value:integer； L:list of process； endP(S) 操作可描述為：procedure P(S) var S: semaphor

33、e; begin S.value:=S.value-1; if S.value0 then block(S,L) end V(S)操作可描述為：procedure V(S) var S: semaphore; begin S.value:=S.value+1; if S.value0 then wakeup(S,L); end關(guān)于信號(hào)量和P、V操作的說(shuō)明：信號(hào)量的初值一定是一個(gè)非負(fù)的整數(shù)，但是在運(yùn)行過(guò)程中，信號(hào)量的值可正可負(fù)。P操作和V操作是原語(yǔ)操作。2. 利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥 利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥的進(jìn)程可描述如下：Var s:semaphore:=1; begin parbegin pr

34、ocess 1: begin repeat P(s); critical section V(s); remainder section until false; end process 2: begin repeat P(s); critical section V(s); remainder section until false; endparend end 用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥的特點(diǎn)：要找對(duì)臨界區(qū)，范圍小了會(huì)出錯(cuò)，范圍大了會(huì)影響進(jìn)程運(yùn)行。P、V操作位于臨界區(qū)前后，在一個(gè)進(jìn)程里成對(duì)出現(xiàn)。2個(gè)進(jìn)程對(duì)1個(gè)臨界資源互斥使用時(shí)S初值為1，取值范圍為-1，0，1。3. 利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步: 進(jìn)

35、程可描述如下：Var s1,s2:semaphore:=0,0; begin parbegin process 1: begin repeat 獲得數(shù)據(jù)； 計(jì)算； 送至緩沖區(qū); V(s1); P(s2); until false; end process 2: begin repeat P(s1); 從緩沖區(qū)中取數(shù)據(jù); 輸出; V(s2); until false; endparend end 緩沖區(qū)P1P2用信號(hào)量實(shí)現(xiàn)進(jìn)程同步的特點(diǎn)：配對(duì)的P、V操作分別在不同的進(jìn)程里。初值一般為0，需要設(shè)一個(gè)以上的信號(hào)量。（例如2個(gè)進(jìn)程同步，需要設(shè)2個(gè)信號(hào)量，分別用來(lái)傳遞信息）結(jié)論：當(dāng)n個(gè)進(jìn)程要互斥使用m個(gè)

36、同類臨界資源時(shí)（nm），用信號(hào)量實(shí)現(xiàn)互斥時(shí)，信號(hào)量的初值應(yīng)為m，即該類可用資源的數(shù)目。 S的取值范圍為-(n-m)m。當(dāng)s0時(shí)，s表示還允許進(jìn)入臨界區(qū)的進(jìn)程數(shù)（或剩下的臨界資源個(gè)數(shù)）。執(zhí)行一次P操作，表示請(qǐng)求一個(gè)臨界資源，s-1后，當(dāng)s0時(shí)，表示可用資源沒(méi)有了，阻塞。執(zhí)行一次V操作，表示釋放一個(gè)臨界資源，s+1后，若s=0，表示還有進(jìn)程在阻塞隊(duì)列中，要去喚醒。 2.3.3 經(jīng)典的進(jìn)程同步互斥問(wèn)題1. 生產(chǎn)者消費(fèi)者問(wèn)題 生產(chǎn)者-消費(fèi)者(producer-consumer)問(wèn)題是一個(gè)著名的進(jìn)程同步問(wèn)題。它描述的是：有一群生產(chǎn)者進(jìn)程在生產(chǎn)產(chǎn)品，并將這些產(chǎn)品提供給消費(fèi)者進(jìn)程去消費(fèi)。為使生產(chǎn)者進(jìn)程與消費(fèi)

37、者進(jìn)程能并發(fā)執(zhí)行，在兩者之間設(shè)置了一個(gè)具有n個(gè)緩沖區(qū)的緩沖池，生產(chǎn)者進(jìn)程將它所生產(chǎn)的產(chǎn)品放入一個(gè)緩沖區(qū)中； 消費(fèi)者進(jìn)程可從一個(gè)緩沖區(qū)中取走產(chǎn)品去消費(fèi)。盡管所有的生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程都是以異步方式運(yùn)行的，但它們之間必須保持同步，即不允許消費(fèi)者進(jìn)程到一個(gè)空緩沖區(qū)去取產(chǎn)品；也不允許生產(chǎn)者進(jìn)程向一個(gè)已裝滿產(chǎn)品且尚未被取走的緩沖區(qū)中投放產(chǎn)品。 inout 假定在生產(chǎn)者和消費(fèi)者之間的公用緩沖池中，具有n個(gè)緩沖區(qū)，這時(shí)可利用互斥信號(hào)量mutex實(shí)現(xiàn)諸進(jìn)程對(duì)緩沖池的互斥使用；利用信號(hào)量empty和full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量。又假定這些生產(chǎn)者和消費(fèi)者相互等效，只要緩沖池未滿，生產(chǎn)者便可將

38、消息送入緩沖池；只要緩沖池未空，消費(fèi)者便可從緩沖池中取走一個(gè)消息。對(duì)生產(chǎn)者消費(fèi)者問(wèn)題可描述如下： Var s, empty, full:semaphore=1,n,0; buffer:array0, , n-1 of item; in, out: integer=0, 0; begin parbegin proceducer:begin repeat producer an item nextp; P(empty); P(s); buffer(in)=nextp; in=(in+1) mod n; V(s); V(full); until false; end consumer:begin r

39、epeat P(full); P(s); nextc:=buffer(out); out:=(out+1) mod n; V(s); V(empty); consumer the item in nextc; until false; end parend end 在生產(chǎn)者消費(fèi)者問(wèn)題中應(yīng)注意：首先，在每個(gè)程序中用于實(shí)現(xiàn)互斥的P(s)和V(s)必須成對(duì)地出現(xiàn)； 其次，對(duì)資源信號(hào)量empty和full的P和V操作，是為了實(shí)現(xiàn)同步存在的，同樣需要成對(duì)地出現(xiàn)，但它們分別處于不同的程序中。最后，在每個(gè)程序中的多個(gè)P操作順序不能顛倒。應(yīng)先執(zhí)行對(duì)資源信號(hào)量的P操作，然后再執(zhí)行對(duì)互斥信號(hào)量的P操作，否則可能引

40、起進(jìn)程死鎖。2. 讀者-寫(xiě)者問(wèn)題 為實(shí)現(xiàn)Reader與Writer進(jìn)程間在讀或?qū)憰r(shí)的互斥而設(shè)置了一個(gè)互斥信號(hào)量WS。另外，再設(shè)置一個(gè)整型變量Readcount表示正在讀的進(jìn)程數(shù)目。由于只要有一個(gè)Reader進(jìn)程在讀，便不允許Writer進(jìn)程去寫(xiě)。因此，僅當(dāng)Readcount=0, 表示尚無(wú)Reader進(jìn)程在讀時(shí)，Reader進(jìn)程才需要執(zhí)行P(WS)操作。若P(WS)操作成功，Reader進(jìn)程便可去讀，相應(yīng)地，做Readcount+1操作。同理，僅當(dāng)Reader進(jìn)程在執(zhí)行了Readcount減1操作后其值為0時(shí)，才須執(zhí)行V(WS)操作，以便讓W(xué)riter進(jìn)程寫(xiě)。又因?yàn)镽eadcount是一個(gè)可被

41、多個(gè)Reader進(jìn)程訪問(wèn)的臨界資源，因此，應(yīng)該為它設(shè)置一個(gè)互斥信號(hào)量RS。 讀者-寫(xiě)者問(wèn)題可描述如下：Var RS, WS:semaphore:=1,1; Readcount:integer:=0; begin parbegin Reader:begin repeat P(RS); if readcount=0 then P(WS); Readcount:=Readcount+1; V(RS); perform read operation; P(RS); readcount：=readcount-1; if readcount=0 then V(WS); V(RS); until false

42、; end writer:begin repeat P(WS); perform write operation; V(WS); until false; end parend end 2.3.4 管 程1. 管程的定義 管程由三部分組成： 局部于管程的共享變量說(shuō)明； 對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過(guò)程； 對(duì)局部于管程的數(shù)據(jù)設(shè)置初始值的語(yǔ)句。此外，還須為管程賦予一個(gè)名字。 圖 2-16 管程的結(jié)構(gòu)模型 管程的語(yǔ)法如下： type monitor-name=monitor variable declarations procedure entry P1(); begin end; procedure

43、 entry P2(); begin end; procedure entry Pn(); begin end; begin initialization code; end 2. 條件變量 管程中對(duì)每個(gè)條件變量，都須予以說(shuō)明，其形式為：Var x, y:condition。該變量應(yīng)置于wait和signal之前，即可表示為X.wait和X.signal。例如，由于共享數(shù)據(jù)被占用而使調(diào)用進(jìn)程等待，該條件變量的形式為：nonbusy:condition。此時(shí)， wait原語(yǔ)應(yīng)改為nonbusy.wait，相應(yīng)地，signal應(yīng)改為nonbusy.signal。 應(yīng)當(dāng)指出，X.signal操作的作

44、用，是重新啟動(dòng)一個(gè)被阻塞的進(jìn)程，但如果沒(méi)有被阻塞的進(jìn)程，則X.signal操作不產(chǎn)生任何后果。這與信號(hào)量機(jī)制中的signal操作不同。因?yàn)?，后者總是要?zhí)行s =s+1操作，因而總會(huì)改變信號(hào)量的狀態(tài)。 如果有進(jìn)程Q處于阻塞狀態(tài)， 當(dāng)進(jìn)程P執(zhí)行了X.signal操作后，怎樣決定由哪個(gè)進(jìn)行執(zhí)行，哪個(gè)等待，可采用下述兩種方式之一進(jìn)行處理： (1) P等待，直至Q離開(kāi)管程或等待另一條件。 (2) Q等待，直至P離開(kāi)管程或等待另一條件。 采用哪種處理方式， 當(dāng)然是各執(zhí)一詞。 但是Hansan卻采用了第一種處理方式。 3.利用管程解決生產(chǎn)者-消費(fèi)者問(wèn)題 在利用管程方法來(lái)解決生產(chǎn)者-消費(fèi)者問(wèn)題時(shí)， 首先便是為

45、它們建立一個(gè)管程，并命名為Proclucer-Consumer, 或簡(jiǎn)稱為PC。其中包括兩個(gè)過(guò)程： (1) put(item)過(guò)程。生產(chǎn)者利用該過(guò)程將自己生產(chǎn)的產(chǎn)品投放到緩沖池中，并用整型變量count來(lái)表示在緩沖池中已有的產(chǎn)品數(shù)目，當(dāng)countn時(shí)， 表示緩沖池已滿， 生產(chǎn)者須等待。 (1) put(item)過(guò)程。 生產(chǎn)者利用該過(guò)程將自己生產(chǎn)的產(chǎn)品投放到緩沖池中， 并用整型變量count來(lái)表示在緩沖池中已有的產(chǎn)品數(shù)目，當(dāng)countn時(shí)，表示緩沖池已滿，生產(chǎn)者須等待。 (2) get(item)過(guò)程。消費(fèi)者利用該過(guò)程從緩沖池中取出一個(gè)產(chǎn)品，當(dāng)count0時(shí)，表示緩沖池中已無(wú)可取用的產(chǎn)品， 消

46、費(fèi)者應(yīng)等待。 type producer-consumer=monitor Var in,out,count:integer; buffer:array0,n-1 of item; notfull, notempty:condition; procedure entry put(item) begin if countn then notfull.wait; buffer(in) =nextp; in =(in+1) mod n; count =count+1; if notempty.queue then notempty.signal; end procedure entry get(it

47、em) begin if count0 then notempty.wait; nextc =buffer(out); out =(out+1) mod n; count =count-1; if notfull.quene then notfull.signal; end begin in =out =0; count =0 end 在利用管程解決生產(chǎn)者-消費(fèi)者問(wèn)題時(shí)， 其中的生產(chǎn)者和消費(fèi)者可描述為： producer:begin repeat produce an item in nextp; PC.put(item); until false; end consumer:begin re

48、peat PC.get(item); consume the item in nextc; until false; end 2.4 進(jìn) 程 通 信 進(jìn)程通信的類型 低級(jí)通信：控制信息的交換。 (2) 高級(jí)通信：大量數(shù)據(jù)的交換。 2.4.1 共享存儲(chǔ) 基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式。（如緩沖區(qū)） (2) 基于共享存儲(chǔ)區(qū)的通信方式。 2.4.2 消息傳遞系統(tǒng) 不論是單機(jī)系統(tǒng)、多機(jī)系統(tǒng)，還是計(jì)算機(jī)網(wǎng)絡(luò)，消息傳遞機(jī)制都是用得最廣泛的一種進(jìn)程間通信的機(jī)制。在消息傳遞系統(tǒng)中，進(jìn)程間的數(shù)據(jù)交換，是以格式化的消息(message)為單位的。程序員直接利用系統(tǒng)提供的一組通信命令(原語(yǔ))進(jìn)行通信。操作系統(tǒng)隱藏了通信

49、的實(shí)現(xiàn)細(xì)節(jié)，大大減化了通信程序編制的復(fù)雜性，而獲得廣泛的應(yīng)用。消息傳遞系統(tǒng)的通信方式屬于高級(jí)通信方式。又因其實(shí)現(xiàn)方式的不同而進(jìn)一步分成直接通信方式和間接通信方式兩種。 1. 直接通信方式 這是指發(fā)送進(jìn)程利用OS所提供的發(fā)送命令，直接把消息發(fā)送給目標(biāo)進(jìn)程。此時(shí)，要求發(fā)送進(jìn)程和接收進(jìn)程都以顯式方式提供對(duì)方的標(biāo)識(shí)符。通常，系統(tǒng)提供下述兩條通信命令(原語(yǔ))： Send(Receiver, message); 發(fā)送一個(gè)消息給接收進(jìn)程； Receive(Sender, message); 接收Sender發(fā)來(lái)的消息；例如，原語(yǔ)Send(P2, m1)表示將消息m1發(fā)送給接收進(jìn)程P2; 而原語(yǔ)Receive

50、(P1，m1)則表示接收由P1發(fā)來(lái)的消息m1。 消息緩沖通信 2. 間接通信方式 ：郵箱通信信箱的創(chuàng)建和撤消。進(jìn)程可利用信箱創(chuàng)建原語(yǔ)來(lái)建立一個(gè)新信箱。創(chuàng)建者進(jìn)程應(yīng)給出信箱名字、信箱屬性(公用、私用或共享)；對(duì)于共享信箱， 還應(yīng)給出共享者的名字。當(dāng)進(jìn)程不再需要讀信箱時(shí)，可用信箱撤消原語(yǔ)將之撤消。消息的發(fā)送和接收。當(dāng)進(jìn)程之間要利用信箱進(jìn)行通信時(shí)，必須使用共享信箱，并利用系統(tǒng)提供的下述通信原語(yǔ)進(jìn)行通信。 Send(mailbox, message); 將一個(gè)消息發(fā)送到指定信箱； Receive(mailbox, message); 從指定信箱中接收一個(gè)消息； 信箱可由操作系統(tǒng)創(chuàng)建，也可由用戶進(jìn)程創(chuàng)建

51、，創(chuàng)建者是信箱的擁有者。據(jù)此，可把信箱分為以下三類。 1) 私用信箱 用戶進(jìn)程可為自己建立一個(gè)新信箱，并作為該進(jìn)程的一部分。信箱的擁有者有權(quán)從信箱中讀取消息，其他用戶則只能將自己構(gòu)成的消息發(fā)送到該信箱中。當(dāng)擁有該信箱的進(jìn)程結(jié)束時(shí)，信箱也隨之消失。 2) 公用信箱 它由操作系統(tǒng)創(chuàng)建，并提供給系統(tǒng)中的所有核準(zhǔn)進(jìn)程使用。核準(zhǔn)進(jìn)程既可把消息發(fā)送到該信箱中，也可從信箱中讀取發(fā)送給自己的消息。通常，公用信箱在系統(tǒng)運(yùn)行期間始終存在。 3) 共享信箱 它由某進(jìn)程創(chuàng)建，在創(chuàng)建時(shí)或創(chuàng)建后，指明它是可共享的，同時(shí)須指出共享進(jìn)程(用戶)的名字。信箱的擁有者和共享者，都有權(quán)從信箱中取走發(fā)送給自己的消息。 在利用信箱通信

52、時(shí)，在發(fā)送進(jìn)程和接收進(jìn)程之間，存在以下四種關(guān)系： (1) 一對(duì)一關(guān)系。這時(shí)可為發(fā)送進(jìn)程和接收進(jìn)程建立一條兩者專用的通信鏈路，使兩者之間的交互不受其他進(jìn)程的干擾。 (2) 多對(duì)一關(guān)系。允許提供服務(wù)的進(jìn)程與多個(gè)用戶進(jìn)程之間進(jìn)行交互，也稱為客戶/服務(wù)器交互(client/server interaction)。 (3) 一對(duì)多關(guān)系。允許一個(gè)發(fā)送進(jìn)程與多個(gè)接收進(jìn)程進(jìn)行交互，使發(fā)送進(jìn)程可用廣播方式，向接收者(多個(gè))發(fā)送消息。 (4) 多對(duì)多關(guān)系。允許建立一個(gè)公用信箱，讓多個(gè)進(jìn)程都能向信箱中投遞消息；也可從信箱中取走屬于自己的消息。 2.4.3 共享文件 所謂“管道”，是指用于連接一個(gè)讀進(jìn)程和一個(gè)寫(xiě)進(jìn)程以

53、實(shí)現(xiàn)他們之間通信的一個(gè)共享文件，又名pipe文件。向管道(共享文件)提供輸入的發(fā)送進(jìn)程(即寫(xiě)進(jìn)程)， 以字符流形式將大量的數(shù)據(jù)送入管道；而接受管道輸出的接收進(jìn)程(即讀進(jìn)程)，則從管道中接收(讀)數(shù)據(jù)。由于發(fā)送進(jìn)程和接收進(jìn)程是利用管道進(jìn)行通信的，故又稱為管道通信。這種方式首創(chuàng)于UNIX系統(tǒng)，由于它能有效地傳送大量數(shù)據(jù)，因而又被引入到許多其它操作系統(tǒng)中。 為了協(xié)調(diào)雙方的通信，管道機(jī)制必須提供以下三方面的協(xié)調(diào)能力： 互斥，即當(dāng)一個(gè)進(jìn)程正在對(duì)pipe執(zhí)行讀/寫(xiě)操作時(shí)，其它(另一)進(jìn)程必須等待。 同步，指當(dāng)寫(xiě)(輸入)進(jìn)程把一定數(shù)量(如4 KB)的數(shù)據(jù)寫(xiě)入pipe，便去睡眠等待， 直到讀(輸出)進(jìn)程取走數(shù)

54、據(jù)后，再把他喚醒。當(dāng)讀進(jìn)程讀一空pipe時(shí)，也應(yīng)睡眠等待，直至寫(xiě)進(jìn)程將數(shù)據(jù)寫(xiě)入管道后，才將之喚醒。 確定對(duì)方是否存在，只有確定了對(duì)方已存在時(shí)，才能進(jìn)行通信。 2.5 進(jìn)程調(diào)度 進(jìn)程調(diào)度的基本概念進(jìn)程調(diào)度的類型進(jìn)程調(diào)度的算法2.5.1 調(diào)度的層次在進(jìn)程狀態(tài)的變化中，從就緒到運(yùn)行的轉(zhuǎn)變是由一個(gè)專門(mén)的程序來(lái)完成的，該程序稱為進(jìn)程調(diào)度程序。進(jìn)程調(diào)度亦可稱為處理機(jī)調(diào)度，它協(xié)調(diào)和控制各進(jìn)程對(duì)CPU的使用。進(jìn)程調(diào)度程序的具體功能如下：記錄系統(tǒng)中所有進(jìn)程的狀態(tài)、優(yōu)先數(shù)和資源需求情況確定調(diào)度算法和調(diào)度方式分配處理器給某進(jìn)程，完成處理器的切換一般來(lái)說(shuō)，一個(gè)作業(yè)從進(jìn)入系統(tǒng)并駐留在外存的后備隊(duì)列上開(kāi)始，直到作業(yè)運(yùn)行完

55、畢，可能要經(jīng)歷以下幾級(jí)調(diào)度：1. 作業(yè)調(diào)度：又稱宏觀調(diào)度，或高級(jí)調(diào)度。其主要任務(wù)是按一定的原則對(duì)外存上的大量后備作業(yè)進(jìn)行選擇，給選出的作業(yè)分配內(nèi)存、輸入輸出設(shè)備等必要的資源，并建立相應(yīng)的進(jìn)程，以使該作業(yè)的進(jìn)程獲得競(jìng)爭(zhēng)處理機(jī)的權(quán)利。另外，當(dāng)該作業(yè)執(zhí)行完畢時(shí)，還負(fù)責(zé)回收系統(tǒng)資源。2. 進(jìn)程調(diào)度：又稱微觀調(diào)度或低級(jí)調(diào)度。其主要任務(wù)是按照某種策略和方法選取一個(gè)處于就緒狀態(tài)的進(jìn)程占用處理機(jī)。在確定了占用處理機(jī)的進(jìn)程后，系統(tǒng)必須建立與該占用處理機(jī)進(jìn)程相適應(yīng)的執(zhí)行環(huán)境。3. 中級(jí)調(diào)度：又稱交換調(diào)度。其主要任務(wù)是按照給定的原則和策略，將處于外存交換區(qū)中的靜止就緒狀態(tài)或靜止等待狀態(tài)的進(jìn)程調(diào)入內(nèi)存，或把處于活動(dòng)就

56、緒狀態(tài)或活動(dòng)等待狀態(tài)的進(jìn)程交換到外存交換區(qū)。交換調(diào)度主要涉及到內(nèi)存管理與擴(kuò)充。三級(jí)調(diào)度模型提交狀態(tài)后備狀態(tài)完成狀態(tài) 運(yùn) 行 狀 態(tài)執(zhí) 行就 緒阻 塞輸入作業(yè)調(diào)度作業(yè)調(diào)度2.5.2 調(diào)度算法的評(píng)價(jià)標(biāo)準(zhǔn) 面向用戶的準(zhǔn)則 (1) 周轉(zhuǎn)時(shí)間短。 可把平均周轉(zhuǎn)時(shí)間描述為： 作業(yè)的周轉(zhuǎn)時(shí)間T與系統(tǒng)為它提供服務(wù)的時(shí)間TS之比，即W=T/TS，稱為帶權(quán)周轉(zhuǎn)時(shí)間，而平均帶權(quán)周轉(zhuǎn)時(shí)間則可表示為: (2) 響應(yīng)時(shí)間快。 (3) 截止時(shí)間的保證。 (4) 優(yōu)先權(quán)準(zhǔn)則。 面向系統(tǒng)的準(zhǔn)則 系統(tǒng)吞吐量高。(2) 處理機(jī)利用率好。 (3) 各類資源的平衡利用。 1. 先來(lái)先服務(wù)調(diào)度算法 FCFS算法有利于長(zhǎng)作業(yè)（進(jìn)程），不利

57、于短作業(yè)（進(jìn)程）；FCFS算法有利于CPU繁忙型的作業(yè)（進(jìn)程），不利于I/O繁忙型的作業(yè)（進(jìn)程）。2.5.3 調(diào)度算法2時(shí)間片輪轉(zhuǎn)（RR）調(diào)度算法 在時(shí)間片輪轉(zhuǎn)調(diào)度算法中，系統(tǒng)把所有就緒進(jìn)程按先后次序排隊(duì)，CPU總是優(yōu)先分配給就緒隊(duì)列中的第一個(gè)就緒進(jìn)程，并分配給它一個(gè)固定的時(shí)間片。當(dāng)該運(yùn)行進(jìn)程用完規(guī)定的時(shí)間片時(shí)，被迫釋放CPU，CPU又優(yōu)先分配給就緒隊(duì)列中的第一個(gè)進(jìn)程，并分配給這個(gè)進(jìn)程相同的時(shí)間片。每個(gè)運(yùn)行完時(shí)間片的進(jìn)程，當(dāng)未遇到任何阻塞時(shí)，就回到就緒隊(duì)列的尾部，等待下次輪到自己時(shí)再投入運(yùn)行。 3. 短進(jìn)程優(yōu)先調(diào)度算法 短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F，是指對(duì)短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法

58、。它們可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先(SJF)的調(diào)度算法，是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。而短進(jìn)程優(yōu)先(SPF)調(diào)度算法，則是從就緒隊(duì)列中選出一估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)，再重新進(jìn)行調(diào)度。FCFS和SJF調(diào)度算法的性能 SPF調(diào)度算法也存在不容忽視的缺點(diǎn)： (1) 該算法對(duì)長(zhǎng)作業(yè)不利。 (2) 不能保證緊迫性作業(yè)(進(jìn)程)會(huì)被及時(shí)處理。 (3) 該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。 1) 靜態(tài)優(yōu)先權(quán) 靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的，且在進(jìn)程的整個(gè)運(yùn)行期間保持不變。

59、一般地，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個(gè)整數(shù)來(lái)表示的，例如，07或0255中的某一整數(shù)， 又把該整數(shù)稱為優(yōu)先數(shù)。只是具體用法各異：有的系統(tǒng)用“0”表示最高優(yōu)先權(quán)，當(dāng)數(shù)值愈大時(shí)，其優(yōu)先權(quán)愈低；而有的系統(tǒng)恰恰相反。 4. 高響應(yīng)比優(yōu)先調(diào)度算法 確定進(jìn)程優(yōu)先權(quán)的依據(jù)有如下三個(gè)方面：進(jìn)程類型。 (2) 進(jìn)程對(duì)資源的需求。 (3) 用戶要求。 2) 動(dòng)態(tài)優(yōu)先權(quán) 動(dòng)態(tài)優(yōu)先權(quán)是指，在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，是可以隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變的，以便獲得更好的調(diào)度性能。優(yōu)先權(quán)的變化規(guī)律可描述為： 由于等待時(shí)間與服務(wù)時(shí)間之和，就是系統(tǒng)對(duì)該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為：

60、(1) 如果作業(yè)的等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。 (2) 當(dāng)要求服務(wù)的時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長(zhǎng)，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來(lái)先服務(wù)。 (3) 對(duì)于長(zhǎng)作業(yè)，作業(yè)的優(yōu)先級(jí)可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí)，其優(yōu)先級(jí)便可升到很高， 從而也可獲得處理機(jī)。 5. 多級(jí)反饋隊(duì)列調(diào)度算法 (1) 應(yīng)設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。 在優(yōu)先權(quán)愈高的隊(duì)列中，為每個(gè)進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就愈小。 (2) 當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(duì)列的末尾，按FCFS原則排隊(duì)等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如它