1、課程主要內容課程主要內容操作系統引論（第操作系統引論（第1 1章）章）進程管理（第進程管理（第2-32-3章）章）存儲管理（第存儲管理（第4 4章）章）設備管理（第設備管理（第5 5章）章）文件管理（第文件管理（第6 6章）章）操作系統接口（第操作系統接口（第7 7章）章）UnixUnix操作系統（第操作系統（第1010章）章）Process Management Process Management 進程管理進程管理u進程的基本概念與控制進程的基本概念與控制v進程的基本概念進程的基本概念v進程控制進程控制v線程的基本概念線程的基本概念vUNIXUNIX中進程的描述與控制中進程的描述與控制u進

2、程同步與通信進程同步與通信v進程同步進程同步v經典進程的同步問題經典進程的同步問題v管程機制管程機制v進程通信進程通信vUNIXUNIX中進程的同步與通信中進程的同步與通信u處理機調度與死鎖（第處理機調度與死鎖（第3 3章）章）第第3 3章章 處理機調度與死鎖處理機調度與死鎖 在多道程序環境下，一個作業從提交到執行，通常在多道程序環境下，一個作業從提交到執行，通常都要經歷多級調度，如都要經歷多級調度，如高級調度高級調度、低級調度低級調度、中級調度中級調度等。而系統的運行性能在很大程度上取決于調度，因此等。而系統的運行性能在很大程度上取決于調度，因此調度便成為多道程序的關鍵。調度便成為多道程序的

3、關鍵。 在多道程序環境下，由于多個進程的并發執行，改在多道程序環境下，由于多個進程的并發執行，改善了系統資源的利用率并提高了系統的處理能力，然而，善了系統資源的利用率并提高了系統的處理能力，然而，多個進程的并發執行也帶來了新的問題多個進程的并發執行也帶來了新的問題-死鎖。死鎖。第第3 3章章 處理機調度與死鎖處理機調度與死鎖u處理機調度的層次處理機調度的層次u調度隊列模型和調度準則調度隊列模型和調度準則u調度算法調度算法u實時調度實時調度uUNIXUNIX系統中進程的調度系統中進程的調度v產生死鎖的原因和必要條件產生死鎖的原因和必要條件v預防死鎖的方法預防死鎖的方法v死鎖的避免死鎖的避免v死鎖

4、的檢測與解除死鎖的檢測與解除v本章作業本章作業3.1 3.1 處理機調度的層次處理機調度的層次 在多道程序環境下，一個作業從提交直到完成，在多道程序環境下，一個作業從提交直到完成，往往要經歷多級調度。往往要經歷多級調度。 在不同操作系統中所采用的調度層次不完全相在不同操作系統中所采用的調度層次不完全相同。同。 有些系統中：僅采用一級調度；有些系統中：僅采用一級調度； 另一些系統：可能采用兩級或三級調度。另一些系統：可能采用兩級或三級調度。 在執行調度時所采用的調度算法也可能不同。在執行調度時所采用的調度算法也可能不同。一、調度的層次一、調度的層次 如圖所示。如圖所示。中級調度中級調度新建態新建

5、態掛起就緒掛起就緒態態掛起等待掛起等待態態高級調度高級調度低級調度低級調度運行態運行態就緒態就緒態等待態等待態終止終止態態二、高級調度（二、高級調度（1 1） 一個作業從提交開始，往往要經歷三級調一個作業從提交開始，往往要經歷三級調度：度：高級調度高級調度、低級調度低級調度、中級調度中級調度。有關作業的幾個基本概念有關作業的幾個基本概念（1 1）作業）作業（2 2）作業步）作業步（3 3）作業流）作業流（4 4）作業控制塊（）作業控制塊（JCBJCB） 是作業在系統中存在的標志，其中保存了系是作業在系統中存在的標志，其中保存了系統對作業進行管理和調度所需的全部信息。統對作業進行管理和調度所需的

6、全部信息。二、高級調度（二、高級調度（2 2）高級調度高級調度（長程（長程/ /作業作業/ /宏觀調度）宏觀調度）（1 1）用于決定把外存上處于后備隊列中的哪些作）用于決定把外存上處于后備隊列中的哪些作業調入內存，并為它們創建進程、分配必要的業調入內存，并為它們創建進程、分配必要的資源，排在就緒隊列上。資源，排在就緒隊列上。（2 2）在批處理系統中）在批處理系統中, ,大多配有作業調度大多配有作業調度, ,但在分但在分時系統及實時系統中時系統及實時系統中, ,一般不配置一般不配置. .（3 3）作業調度執行頻率很低）作業調度執行頻率很低, ,通常為幾分鐘一次通常為幾分鐘一次, ,甚至更久。甚至

7、更久。u高級調度需解決的問題高級調度需解決的問題（1 1）主要任務是從外存后備隊列中）主要任務是從外存后備隊列中選擇多少作業選擇多少作業進入就緒隊進入就緒隊列，即允許多少作業同時在內存中運行（多道程序的列，即允許多少作業同時在內存中運行（多道程序的“道道或度或度” ）。若作業太多，則可能會影響系統的服務質量）。若作業太多，則可能會影響系統的服務質量（如周轉時間太長），若太少，又將導致系統資源利用率（如周轉時間太長），若太少，又將導致系統資源利用率和吞吐量的下降。因此，應根據系統的規模和運行速度來和吞吐量的下降。因此，應根據系統的規模和運行速度來確定，同時確定，同時要求要求I/OI/O型進程型進

8、程與與CPUCPU型進程型進程中和中和調度。調度。（2 2）應）應將哪些作業從外存調入內存將哪些作業從外存調入內存，將取決于調度算法（先，將取決于調度算法（先來先服務、短作業優先等）。來先服務、短作業優先等）。 二、高級調度（二、高級調度（3 3）三、低級調度三、低級調度( (短程短程/CPU/CPU/進程進程/ /微觀調度微觀調度) )（1 1）主要任務是從就緒隊列中選擇）主要任務是從就緒隊列中選擇一個一個進程來執行并分配處理機。進程來執行并分配處理機。（2 2）是）是OSOS中最基本的調度。中最基本的調度。（3 3）調度頻率非常高，一般幾十毫秒一次。）調度頻率非常高，一般幾十毫秒一次。（4

9、 4）常采用）常采用非搶占（非剝奪）方式非搶占（非剝奪）方式和和搶占搶占（剝奪剝奪）方式方式兩種。兩種。（5 5）引起進程調度的因素：）引起進程調度的因素：v進程正常終止或異常終止進程正常終止或異常終止v正在執行的進程因某種原因而阻塞正在執行的進程因某種原因而阻塞v在引入時間片的系統中，時間片用完。在引入時間片的系統中，時間片用完。v在搶占調度方式中，就緒隊列中某進程的優先權變得比當在搶占調度方式中，就緒隊列中某進程的優先權變得比當前正執行的進程高。前正執行的進程高。調度方式調度方式-非搶占式進程調度、搶占式進程調度非搶占式進程調度、搶占式進程調度u非搶占方式非搶占方式：一旦把處理機分配給某進

10、程后，便讓該進：一旦把處理機分配給某進程后，便讓該進程程一直執行一直執行，直到該進程完成或因某事件而被阻塞，才，直到該進程完成或因某事件而被阻塞，才再把處理機分配給其它進程，決不允許某進程搶占已分再把處理機分配給其它進程，決不允許某進程搶占已分配出去的處理機。配出去的處理機。 實現簡單，系統開銷小，常用于批處理系統；但不利實現簡單，系統開銷小，常用于批處理系統；但不利于處理緊急任務，故實時、分時系統不宜采用。于處理緊急任務，故實時、分時系統不宜采用。u搶占方式搶占方式: : 允許調度程序根據某種原則（時間片、優先允許調度程序根據某種原則（時間片、優先權、短進程優先），權、短進程優先），停止停止

11、正在執行正在執行的進程，而將處理機的進程，而將處理機重新分配給另一進程。重新分配給另一進程。 有利于處理緊急任務，故實時與分時系統中常采用。有利于處理緊急任務，故實時與分時系統中常采用。四、中級調度（中程四、中級調度（中程/ /交換調度）交換調度） 在內存和外存對換區之間按照給定的原則和在內存和外存對換區之間按照給定的原則和策略策略選擇進程對換選擇進程對換，以解決內存緊張問題，從，以解決內存緊張問題，從而提高內存的利用率和系統吞吐量，常用于分而提高內存的利用率和系統吞吐量，常用于分時系統或具有虛擬存儲器的系統中。時系統或具有虛擬存儲器的系統中。3.23.2 調度隊列模型和調度準則調度隊列模型和

12、調度準則 在在OSOS中的任何一種調度中，都將涉及中的任何一種調度中，都將涉及到到進程隊列進程隊列，由此形成了三種類型的調度，由此形成了三種類型的調度隊列模型。隊列模型。v僅有進程調度的調度隊列模型僅有進程調度的調度隊列模型v具有高級和低級調度的調度隊列模型具有高級和低級調度的調度隊列模型v同時具有三級調度的調度隊列模型同時具有三級調度的調度隊列模型一、僅有進程調度的調度隊列模型一、僅有進程調度的調度隊列模型就就 緒緒 隊隊 列列阻阻 塞塞 隊隊 列列進程調度進程調度時間片完時間片完CPU進程完成進程完成等待事件等待事件事事件件出出現現交互用戶交互用戶二、具有高級和低級調度的調度隊列模型二、具

13、有高級和低級調度的調度隊列模型就就 緒緒 隊隊 列列阻阻 塞塞 隊隊 列列時間片完時間片完后后備備隊隊列列進程調度進程調度CPU進程完成進程完成事事件件出出現現等待事件等待事件1等待事件等待事件2等待事件等待事件n作業作業調度調度 就就 緒緒 隊隊 列列掛掛 起起 就就 緒緒 隊隊 列列時間片完時間片完阻阻 塞塞 隊隊 列列后后備備隊隊列列進程調度進程調度CPU進程完成進程完成事事件件出出現現等待事件等待事件作業作業調度調度掛掛 起起 阻阻 塞塞 隊隊 列列中級調度中級調度事件出現事件出現掛起掛起掛起掛起交互型作業交互型作業批量作業批量作業三、同時具有三級調度的調度隊列模型三、同時具有三級調度

14、的調度隊列模型四、選擇調度方式和算法的若干準則（四、選擇調度方式和算法的若干準則（1 1） 在一個操作系統的設計中，應如何選擇調度方式和在一個操作系統的設計中，應如何選擇調度方式和算法，在很大程度上取決于操作系統的類型及其目標，算法，在很大程度上取決于操作系統的類型及其目標，選擇調度方式和算法的準則有：選擇調度方式和算法的準則有：u 面向用戶的準則面向用戶的準則v周轉時間短周轉時間短v響應時間快響應時間快v截止時間的保證截止時間的保證v優先權準則優先權準則u 面向系統的準則面向系統的準則v系統吞吐量系統吞吐量v處理機利用率好處理機利用率好v各類資源平衡利用各類資源平衡利用u 最優準則最優準則v

15、 最大的最大的CPUCPU利用率利用率v 最大的吞吐量最大的吞吐量v 最短的周轉時間最短的周轉時間v 最短的等待時間最短的等待時間v 最短的響應時間最短的響應時間四、選擇調度方式和算法的若干準則（四、選擇調度方式和算法的若干準則（2 2）CPUCPU利用率利用率=CPU=CPU有效工作時間有效工作時間/CPU/CPU總的運行時間，總的運行時間， CPU CPU總的運行時間總的運行時間=CPU=CPU有效工作時間有效工作時間+CPU+CPU空閑等待時空閑等待時間。間。響應時間響應時間-交互式進程從提交一個請求交互式進程從提交一個請求( (命令命令) )到接收到接收到響應之間的時間間隔稱響應時間。

16、到響應之間的時間間隔稱響應時間。周轉時間周轉時間-批處理用戶從作業提交給系統開始，到作批處理用戶從作業提交給系統開始，到作業完成為止的時間間隔稱作業周轉時間，實際上它業完成為止的時間間隔稱作業周轉時間，實際上它是作業在系統里的等待時間與運行時間之和。應使是作業在系統里的等待時間與運行時間之和。應使作業周轉時間或平均作業周轉時間盡可能短。作業周轉時間或平均作業周轉時間盡可能短。四、選擇調度方式和算法的若干準則（四、選擇調度方式和算法的若干準則（3 3）帶權周轉時間帶權周轉時間周轉時間周轉時間/ /進程要求運行時進程要求運行時間間吞吐量吞吐量-單位時間內處理的作業數。單位時間內處理的作業數。公平性

17、公平性-確保每個用戶每個進程獲得合理的確保每個用戶每個進程獲得合理的CPUCPU份額或其他資源份額，不會出現餓死份額或其他資源份額，不會出現餓死情況。情況。3.3 3.3 調度算法調度算法u先來先服務調度算法先來先服務調度算法u短作業短作業/ /進程優先調度算法進程優先調度算法u時間片輪轉調度算法時間片輪轉調度算法u優先權調度算法優先權調度算法u高響應比優先調度算法高響應比優先調度算法u多級反饋隊列調度算法多級反饋隊列調度算法 進程調度的核心問題就是采用什么樣的算法進程調度的核心問題就是采用什么樣的算法將處理機分配給進程，常用的進程調度算法有：將處理機分配給進程，常用的進程調度算法有：一、先來

18、先服務調度算法一、先來先服務調度算法FCFSFCFSu 基本思想基本思想: :按照進程進入就緒隊列的先后次序來分配處理機。按照進程進入就緒隊列的先后次序來分配處理機。 一般采用非剝奪的調度方式。一般采用非剝奪的調度方式。u ExampleExample: :進程名進程名 到達時間到達時間 服務時間服務時間 A 0 1 B 1 100 C 2 1 D 3 100u 該調度的該調度的GanttGantt（甘特）圖為（甘特）圖為: :u 平均周轉時間平均周轉時間=(=(1-0)+(101-1)+(102-2)+(202-3)(1-0)+(101-1)+(102-2)+(202-3)）/4=100/4

19、=100u 平均等待時間平均等待時間=(0-0)+(1-1)+(101-2)+(102-3)/4 = 49.5=(0-0)+(1-1)+(101-2)+(102-3)/4 = 49.5u 平均帶權周轉時間平均帶權周轉時間= =？DBCA0 1 2 3 101 102 202 0 1 2 3 101 102 202 甘特圖甘特圖(Gantt)是作業排序中是作業排序中最常用的一種工具，最早由最常用的一種工具，最早由Henry L. Gantt于于1917年提年提出。這種方法基于作業排序的出。這種方法基于作業排序的目的，是將任務與時間聯系起目的，是將任務與時間聯系起來的表現形式之一來的表現形式之一。

20、 一、一、FCFSFCFS調度算法（續）調度算法（續）u改變到達順序改變到達順序: : 進程名進程名 到達時間到達時間 服務時間服務時間 A 0 1 B 1 100 D 2 100 C 3 1u該調度的該調度的GanttGantt圖為圖為: :u平均周轉時間平均周轉時間= =(1-0)+(101-1)+(202-3)+(201-2)/4=124.25u平均等待時間平均等待時間= =(0-0)+(1-1)+(201-3)+(101-2)/4 = 74.25u平均帶權周轉時間平均帶權周轉時間= =？周轉周轉T100100124.25124.25等待等待T49.549.574.2574.25CBDA

21、0 1 2 3 101 201 202 0 1 2 3 101 201 202 FCFSFCFS調度算法存在的問題調度算法存在的問題 從表面上，先來先服務對于所有作業是公平的，從表面上，先來先服務對于所有作業是公平的，即按照它們到來的先后次序進行服務。但如果一個長即按照它們到來的先后次序進行服務。但如果一個長作業先到達系統，就會使許多短作業等待很長的時間，作業先到達系統，就會使許多短作業等待很長的時間，從而引起許多短作業用戶的不滿。從而引起許多短作業用戶的不滿。 所以，現在操作系統中，已很少用該算法作為主所以，現在操作系統中，已很少用該算法作為主要調度策略，尤其是在分時系統和實時系統中。但它要

22、調度策略，尤其是在分時系統和實時系統中。但它常被結合在其它調度策略中使用。常被結合在其它調度策略中使用。二、短作業二、短作業/ /進程優先調度算法進程優先調度算法SJF/SPFSJF/SPFu 短作業優先調度算法（短作業優先調度算法（SJFSJF）v用于作業調度用于作業調度v主要任務是從后備隊列中選擇一個或若干個估計運行時間最主要任務是從后備隊列中選擇一個或若干個估計運行時間最短的作業，將它們調入內存運行。短的作業，將它們調入內存運行。u 短進程優先調度算法（短進程優先調度算法（SPFSPF）v用于進程調度用于進程調度v主要任務是從就緒隊列中選出一個估計運行時間最短的進程，主要任務是從就緒隊列

23、中選出一個估計運行時間最短的進程，將處理機分配給它。將處理機分配給它。v可采用搶占（剝奪）（有時稱為可采用搶占（剝奪）（有時稱為最短剩余時間優先最短剩余時間優先（shortest-remaining-time-firstshortest-remaining-time-first）調度）或者非搶占）調度）或者非搶占（非剝奪）調度方式。（非剝奪）調度方式。二、二、SJ(P)F -SJ(P)F -非搶占式非搶占式u到達順序到達順序: : 進程名進程名 到達時間到達時間 服務時間服務時間 A 0 1 B 1 100 D 2 100 C 3 1u該調度的該調度的GanttGantt圖為圖為: :u平均周

24、轉時間平均周轉時間= =(1-0)+(101-1)+(102-3)+(202-2)/4=100u平均等待時間平均等待時間= =(0-0)+(1-1)+(101-3)+(102-2)/4 = 49.5u平均帶權周轉時間平均帶權周轉時間=？FCFSFCFSSPFSPF周轉周轉T124.25124.25100100等待等待T74.2574.2549.549.50 1 2 3 101 102 202 0 1 2 3 101 102 202 DBCA二、短作業二、短作業/ /進程優先調度算法進程優先調度算法- -搶占式搶占式u 到達順序到達順序: : 進程名進程名 到達時間到達時間 服務時間服務時間 A

25、 0 1 B 1 100 D 2 100 C 3 1u 該調度的該調度的GanttGantt圖為圖為: :u 平均周轉時間平均周轉時間=(1-0)+(102-1)+(4-3)+(202-2)=(1-0)+(102-1)+(4-3)+(202-2)）/4=75.75/4=75.75u 平均等待時間平均等待時間=(0-0)+(4-3)+(3-3)+(102-2)/4 = 25.25=(0-0)+(4-3)+(3-3)+(102-2)/4 = 25.25u 平均帶權周轉時間平均帶權周轉時間= =？BCDBBA0 1 2 3 4 102 202 0 1 2 3 4 102 202 FCFSFCFSSP

26、F-SPF-非非SPF-SPF-搶搶周轉周轉T124.25124.2510010075.7575.75等待等待T74.2574.2549.549.525.2525.25uEgEg： 進程進程 到達時間到達時間 服務時間服務時間P P1 10.00.07 7 P P2 22.02.04 4 P P3 34.04.01 1 P P4 45.05.04 4uSPF (SPF (非搶占式非搶占式) )u平均周轉時間平均周轉時間=(7-0)+(12-2)+(8-4)+(16-5)/4=8=(7-0)+(12-2)+(8-4)+(16-5)/4=8u平均等待時間平均等待時間 =(0-0)+(8-2)+(7

27、-4)+(12-5)/4 = 4=(0-0)+(8-2)+(7-4)+(12-5)/4 = 4u平均帶權周轉時間平均帶權周轉時間= =？SPFSPF（非搶占式）調度（非搶占式）調度73160812P1P3P2P4SPFSPF搶占式調度搶占式調度進程進程到達時間到達時間服務時間服務時間P P1 10.00.07 7 P P2 22.02.04 4 P P3 34.04.01 1 P P4 45.05.04 4uSPF (SPF (搶占式搶占式) )u平均周轉時間平均周轉時間=(16-0)+(7-2)+(5-4)+(11-5)/4=7=(16-0)+(7-2)+(5-4)+(11-5)/4=7u平

28、均等待時間平均等待時間=(11-2)+(5-4)+(4-4)+(7-5)/4=3=(11-2)+(5-4)+(4-4)+(7-5)/4=3u平均帶權周轉時間平均帶權周轉時間= =？P1P3P242110P457P2P116FCFSFCFS先來先服務調度先來先服務調度進程進程到達時間到達時間服務時間服務時間P P1 10.00.07 7 P P2 22.02.04 4 P P3 34.04.01 1 P P4 45.05.04 4uFCFSFCFSu平均周轉時間平均周轉時間=(7-0)+(11-2)+(12-4)+(16-5)/4=8.75=(7-0)+(11-2)+(12-4)+(16-5)/

29、4=8.75u平均等待時間平均等待時間 =(0+(7-2)+(11-4)+(12-5)/4 =4.75=(0+(7-2)+(11-4)+(12-5)/4 =4.75u平均帶權周轉時間平均帶權周轉時間= =？P142110P257P41612P3SPFSPF與與FCFSFCFS的比較的比較FCFSFCFS非搶占非搶占SPFSPF搶占搶占SPFSPF吞吐量吞吐量0-7ms0-7ms1 11 12 2平均周轉時間平均周轉時間8.758.758 87 7平均等待時間平均等待時間4.754.754 43 3SJ(P)FSJ(P)F短作業短作業/ /進程優先調度的優缺點進程優先調度的優缺點 優點：優點： 1 1）能有效降低作業的平均等待時間；