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

1、操作系統(tǒng)原理與實訓(xùn)教程第一章 操作系統(tǒng)概述1.1 操作系統(tǒng)的概念 1.2 操作系統(tǒng)的發(fā)展和分類 1.3 現(xiàn)代主流操作系統(tǒng)簡介 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)軟件，是硬件層的第一次擴充，在這一層上實現(xiàn)了操作系統(tǒng)的全部功能，并提供相應(yīng)的接口，其他各層軟件都是在操作系統(tǒng)的基礎(chǔ)上開發(fā)的。 1.1.2 操作系統(tǒng)的作用 1.OS作為用戶與計算機硬件系統(tǒng)之間的接口 OS作為用戶與計算機硬件系統(tǒng)之間接口的含義是：OS處于用戶與計算機硬件系統(tǒng)之間，用戶通過OS來使用計算機系統(tǒng)?；蛘哒f，用戶在OS幫助下，能

2、夠方便、快捷、安全、可靠地操縱計算機硬件和運行自己的程序。應(yīng)注意，OS是一個系統(tǒng)軟件，因而這種接口是軟件接口。 2. OS作為計算機系統(tǒng)資源的管理者 在一個計算機系統(tǒng)中，通常都含有各種各樣的硬件和軟件資源。歸納起來可將資源分為四類：處理器、存儲器、 I/O設(shè)備以及信息(數(shù)據(jù)和程序)。相應(yīng)地，OS的主要功能也正是針對這四類資源進(jìn)行有效的管理，即：處理機管理， 用于分配和控制處理機；存儲器管理，主要負(fù)責(zé)內(nèi)存的分配與回收；I/O設(shè)備管理，負(fù)責(zé)I/O設(shè)備的分配與操縱；文件管理，負(fù)責(zé)文件的存取、共享和保護(hù)?？梢?，OS確是計算機系統(tǒng)資源的管理者。事實上，當(dāng)今世界上廣為流行的一個關(guān)于OS作用的觀點，正是把O

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

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

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

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

7、“及時”，而實時系統(tǒng)(Real-Time System)是指系統(tǒng)能及時(或即時)響應(yīng)外部事件的請求，在規(guī)定的時間內(nèi)完成對該事件的處理，并控制所有實時任務(wù)協(xié)調(diào)一致地運行。 應(yīng)用需求 實時控制。 (2) 實時信息處理。 1.2.5 網(wǎng)絡(luò)操作系統(tǒng) 網(wǎng)絡(luò)操作系統(tǒng)（NOS）可以看作是在網(wǎng)絡(luò)環(huán)境下工作的操作系統(tǒng)軟件，可簡單地定義為管理整個網(wǎng)絡(luò)資源和方便網(wǎng)絡(luò)用戶的軟件集合。網(wǎng)絡(luò)操作系統(tǒng)是計算機網(wǎng)絡(luò)的心臟和靈魂，是向網(wǎng)絡(luò)計算機提供服務(wù)的特殊的操作系統(tǒng)。它在計算機操作系統(tǒng)下工作，使計算機操作系統(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)，包括個人操作系統(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) 一個分布式系統(tǒng)是一些獨立的計算機的集合，但是

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

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

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

12、解釋模塊(COMMAND.COM)。為滿足用戶對操作更方便、直接和靈活的要求，微軟公司推出了一種采用圖形用戶界面（Graphics User Interface，GUI）的新穎的操作系統(tǒng)，Windows操作系統(tǒng)。在近20年的發(fā)展過程中，微軟主要推出的版本有Windows3.X，Windows 9X，Windows NT，Windows 2000，Windows Me，Windows XP和Windows 2003。Windows操作系統(tǒng)以其靈活、快速、便宜等優(yōu)點，逐漸占據(jù)了PC微型計算機上的主導(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ù)的分時操作系統(tǒng)。最初由貝爾實驗室開發(fā)在PDP-7上實現(xiàn)的。貝爾實驗室和其他一些部門在Unix上的開發(fā)工作，導(dǎo)致一系列Unix版本的產(chǎn)生。后來，又憑借其性能的完善和良好的可移植性，經(jīng)歷不斷的發(fā)展、演變，并廣泛的應(yīng)用于小型計算機、超級小型計算機乃至大型計算機上。2. UNIX的發(fā)展1.3.3自由軟件LinuxLinux是一套免費使用和自由傳播的類Unix操作系統(tǒng)，Linux系統(tǒng)是由全世界各地的成千上萬的程序員

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

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

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

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

18、作系統(tǒng)是配置在計算機硬件上的第一層軟件，是對硬件系統(tǒng)的首次擴充。操作系統(tǒng)是一組控制和管理計算機硬件和軟件資源，合理地組織計算機工作流程，并為用戶使用計算機提供方便的程序和數(shù)據(jù)的集合。操作系統(tǒng)從形成發(fā)展至今可分為批處理系統(tǒng)、分時系統(tǒng)、實時系統(tǒng)、網(wǎng)絡(luò)操作系統(tǒng)和分布式操作系統(tǒng)等等，其中批處理操作系統(tǒng)、分時操作系統(tǒng)、實時操作系統(tǒng)是操作系統(tǒng)的三種基本類型。每個操作系統(tǒng)均具有自身的特點，但各種操作系統(tǒng)又都具有四個共同的基本特征，即并發(fā)性、共享性、虛擬性和異步性。其中并發(fā)性是操作系統(tǒng)最重要的特征，其他三個特征是以并發(fā)性為前提的。從系統(tǒng)資源的角度看，操作系統(tǒng)有處理機管理、存儲管理、設(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)行計算時，總須先輸入用戶的程序和數(shù)據(jù)，然后進(jìn)行計算，最后才能打印計算結(jié)果。 S1: a=x+y; S2: b=a-5; S3: c=b+1;圖 2-1 程序的順序執(zhí)行 程序順序執(zhí)行時的特征 順序性：(2) 封閉性： (3) 可再現(xiàn)性： 2.1.2 程序的并發(fā)執(zhí)行圖 2-2

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

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 動態(tài)性：進(jìn)程有生命周期。 并發(fā)性：可以并發(fā)執(zhí)行。 獨立性：獨立分配資源和調(diào)度的基本單位。 異步性：進(jìn)程按各自獨立的、不可預(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ā)生某事件而暫時無法繼續(xù) 執(zhí)行時，放棄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)換掛起活動就緒靜止就緒執(zhí)行掛起激活事件發(fā)生掛起活動阻塞靜止阻塞激活事件發(fā)生等待事件2.1.5 進(jìn)程控制塊PCB1. 進(jìn)程控制塊的定義及作用 (1)PCB是進(jìn)程實體的一部分。(2) OS是根據(jù)PCB來對并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的。(3)PCB是進(jìn)程存在的唯一標(biāo)志。(4)PCB應(yīng)常駐內(nèi)存，存放在OS中專門開辟的PCB區(qū)內(nèi)。2. 進(jìn)程控制塊中的信息 1) 進(jìn)程標(biāo)識符 進(jìn)程標(biāo)識符用于惟一地標(biāo)識一個進(jìn)程。2)

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

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

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

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

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

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

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

30、如果都對x進(jìn)行減1操作，這兩個操作在用機器指令實現(xiàn)時， 可用下面的形式描述： 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í)行左列的三條機器語言語句，然后T2進(jìn)程再執(zhí)行右列的三條語句， 則最后共享變量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)作臨界資源處理，即要互斥地訪問x。 2. 臨界區(qū)(critical section) 可把一個訪問臨界資源的循環(huán)進(jìn)程描述如下：repeat critical section; remainder section;until false; entry sectionexit section臨界區(qū)：一個進(jìn)程訪問臨界資源的那段代碼

32、稱為臨界區(qū)。同步機制應(yīng)遵循的規(guī)則： 空閑讓進(jìn)。(2) 忙則等待。 (3) 有限等待。 (4) 讓權(quán)等待。 其實, 互斥關(guān)系也是一種協(xié)調(diào)關(guān)系, 從廣義上講它也屬于同步關(guān)系的范疇。 2.3.2 信號量及P、V操作 1. 信號量及P、V操作信號量：一個具有非負(fù)初值的整型變量，并且有一個隊列與它關(guān)聯(lián)。因此，定義一個信號量時，要給出它的初值，并給出與它相關(guān)的隊列指針。信號量的定義如下：type semaphore=record /*定義信號量*/ 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)于信號量和P、V操作的說明：信號量的初值一定是一個非負(fù)的整數(shù)，但是在運行過程中，信號量的值可正可負(fù)。P操作和V操作是原語操作。2. 利用信號量實現(xiàn)進(jìn)程互斥 利用信號量實現(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 用信號量實現(xiàn)進(jìn)程互斥的特點：要找對臨界區(qū)，范圍小了會出錯，范圍大了會影響進(jìn)程運行。P、V操作位于臨界區(qū)前后，在一個進(jìn)程里成對出現(xiàn)。2個進(jìn)程對1個臨界資源互斥使用時S初值為1，取值范圍為-1，0，1。3. 利用信號量實現(xiàn)進(jìn)程同步: 進(jìn)

35、程可描述如下：Var s1,s2:semaphore:=0,0; begin parbegin process 1: begin repeat 獲得數(shù)據(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用信號量實現(xiàn)進(jìn)程同步的特點：配對的P、V操作分別在不同的進(jìn)程里。初值一般為0，需要設(shè)一個以上的信號量。（例如2個進(jìn)程同步，需要設(shè)2個信號量，分別用來傳遞信息）結(jié)論：當(dāng)n個進(jìn)程要互斥使用m個

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

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

38、消息送入緩沖池；只要緩沖池未空，消費者便可從緩沖池中取走一個消息。對生產(chǎ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)者消費者問題中應(yīng)注意：首先，在每個程序中用于實現(xiàn)互斥的P(s)和V(s)必須成對地出現(xiàn)； 其次，對資源信號量empty和full的P和V操作，是為了實現(xiàn)同步存在的，同樣需要成對地出現(xiàn)，但它們分別處于不同的程序中。最后，在每個程序中的多個P操作順序不能顛倒。應(yīng)先執(zhí)行對資源信號量的P操作，然后再執(zhí)行對互斥信號量的P操作，否則可能引

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

41、多個Reader進(jìn)程訪問的臨界資源，因此，應(yīng)該為它設(shè)置一個互斥信號量RS。 讀者-寫者問題可描述如下：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. 管程的定義 管程由三部分組成： 局部于管程的共享變量說明； 對該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程； 對局部于管程的數(shù)據(jù)設(shè)置初始值的語句。此外，還須為管程賦予一個名字。 圖 2-16 管程的結(jié)構(gòu)模型 管程的語法如下： 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. 條件變量 管程中對每個條件變量，都須予以說明，其形式為：Var x, y:condition。該變量應(yīng)置于wait和signal之前，即可表示為X.wait和X.signal。例如，由于共享數(shù)據(jù)被占用而使調(diào)用進(jìn)程等待，該條件變量的形式為：nonbusy:condition。此時， wait原語應(yīng)改為nonbusy.wait，相應(yīng)地，signal應(yīng)改為nonbusy.signal。 應(yīng)當(dāng)指出，X.signal操作的作

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

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

46、費者應(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)者-消費者問題時， 其中的生產(chǎn)者和消費者可描述為： 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)程通信的類型 低級通信：控制信息的交換。 (2) 高級通信：大量數(shù)據(jù)的交換。 2.4.1 共享存儲 基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式。（如緩沖區(qū)） (2) 基于共享存儲區(qū)的通信方式。 2.4.2 消息傳遞系統(tǒng) 不論是單機系統(tǒng)、多機系統(tǒng)，還是計算機網(wǎng)絡(luò)，消息傳遞機制都是用得最廣泛的一種進(jìn)程間通信的機制。在消息傳遞系統(tǒng)中，進(jìn)程間的數(shù)據(jù)交換，是以格式化的消息(message)為單位的。程序員直接利用系統(tǒng)提供的一組通信命令(原語)進(jìn)行通信。操作系統(tǒng)隱藏了通信

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

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

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

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

53、實現(xiàn)他們之間通信的一個共享文件，又名pipe文件。向管道(共享文件)提供輸入的發(fā)送進(jìn)程(即寫進(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)雙方的通信，管道機制必須提供以下三方面的協(xié)調(diào)能力： 互斥，即當(dāng)一個進(jìn)程正在對pipe執(zhí)行讀/寫操作時，其它(另一)進(jìn)程必須等待。 同步，指當(dāng)寫(輸入)進(jìn)程把一定數(shù)量(如4 KB)的數(shù)據(jù)寫入pipe，便去睡眠等待， 直到讀(輸出)進(jìn)程取走數(shù)

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

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

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

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

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

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

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