計(jì)算機(jī)操作系統(tǒng)(修訂版)

計(jì)算機(jī)操作系統(tǒng)(修訂版)

學(xué)習(xí)即將開始......目錄第一章

操作系統(tǒng)引論第二章

進(jìn)程管理第三章

處理機(jī)調(diào)度與死鎖第四章

存儲器管理第五章

設(shè)備管理

第六章

文件管理第七章

操作系統(tǒng)接口第八章

網(wǎng)絡(luò)操作系統(tǒng)第九章

系統(tǒng)安全性第十章

UNIX系統(tǒng)內(nèi)核結(jié)構(gòu)第一章

操作系統(tǒng)引論(章節(jié)圖)操作系統(tǒng)引論1.1

操作系統(tǒng)的目標(biāo)和作用1.2

操作系統(tǒng)的發(fā)展過程1.3

操作系統(tǒng)的基本特性

1.4

操作系統(tǒng)的主要功能1.5

操作系統(tǒng)的結(jié)構(gòu)設(shè)計(jì)習(xí)題1.1

操作系統(tǒng)的目標(biāo)和作用1.1.1

操作系統(tǒng)的目標(biāo)

操作系統(tǒng)的作用

推動操作系統(tǒng)發(fā)展的主要動力

1.1.1

操作系統(tǒng)的目標(biāo)方便性:可使計(jì)算機(jī)系統(tǒng)更容易使用。有效性:可以充分利用CPU和I/O設(shè)備,并可以把數(shù)據(jù)有序的存放在內(nèi)存和外存而節(jié)省了存儲空間。可擴(kuò)充性:os應(yīng)采用層次化結(jié)構(gòu),以便于增加新的功能層次和模塊,并能修改老的功能層次和模塊。開放性:要求系統(tǒng)能遵循世界標(biāo)準(zhǔn)規(guī)范,特別是遵循開放系統(tǒng)互連osi國際標(biāo)準(zhǔn)。1.1.2

操作系統(tǒng)的作用Os作為用戶與計(jì)算機(jī)硬件系統(tǒng)間的接口.接口方式有:命令方式;系統(tǒng)調(diào)用(有些教材還包括了圖形方式)Os作為計(jì)算機(jī)系統(tǒng)資源的管理者.主要功能有:處理機(jī)管理;存儲器管理;I/O管理;文件管理;(作業(yè)管理).Os用作擴(kuò)充機(jī)器.通常把覆蓋了軟件的機(jī)器稱為擴(kuò)充機(jī)器或虛擬機(jī)器。計(jì)算機(jī)硬件操作系統(tǒng)應(yīng)用程序用戶推動操作系統(tǒng)發(fā)展的主要動力不斷提高計(jì)算機(jī)資源利用率的需要.方便用戶.器件的不斷更新?lián)Q代.計(jì)算機(jī)體系結(jié)構(gòu)的不斷發(fā)展.1.2

操作系統(tǒng)的發(fā)展過程1.2.1

無操作系統(tǒng)的計(jì)算機(jī)系統(tǒng)1.2.2

單道批處理系統(tǒng)1.2.3

多道批處理系統(tǒng)1.2.4

分時(shí)系統(tǒng)1.2.5

實(shí)時(shí)系統(tǒng)

1.2.1

無操作系統(tǒng)的計(jì)算機(jī)系統(tǒng)人工操作方式.脫機(jī)輸入/輸出(OFF-lineI/O)方式.脫機(jī)I/O工作示意圖輸入設(shè)備外圍機(jī)主機(jī)外圍機(jī)輸出設(shè)備磁盤磁盤1.2.2

單道批處理系統(tǒng)單道批處理系統(tǒng)的處理過程.開始

停止

單道批處理系統(tǒng)的特征:自動性,順序性,單道性.還有下一個(gè)作業(yè)源程序有錯(cuò)么？把下一個(gè)作業(yè)的源程序轉(zhuǎn)換為目標(biāo)程序裝配目標(biāo)程序運(yùn)行目標(biāo)程序是否是否1.2.3

多道批處理系統(tǒng)多道程序設(shè)計(jì)的基本概念.多道批處理系統(tǒng)帶來的好處有:提高CPU利用率,提高內(nèi)存和I/O設(shè)備利用率,增加系統(tǒng)吞吐量.多道批處理系統(tǒng)的特征:多道性,無序性,調(diào)度性.多道批處理系統(tǒng)的優(yōu)缺點(diǎn):資源利用率高,系統(tǒng)吞吐量大;平均周轉(zhuǎn)時(shí)間長,無交互能力,可能出現(xiàn)爭用CPU.多道批處理系統(tǒng)需要解決的問題:處理機(jī)管理問題,內(nèi)存管理問題,I/O設(shè)備管理問題,文件管理問題,作業(yè)管理問題.多道批處理系統(tǒng):在該系統(tǒng)中，用戶所提交的作業(yè)都先存放在外存上并排成一個(gè)隊(duì)列，稱為“后備隊(duì)列”；然后，有作業(yè)調(diào)度程序按一定的算法從后備隊(duì)列中選擇若干個(gè)作業(yè)調(diào)入內(nèi)存，是它們共享CPU和系統(tǒng)中的各種資源。我們通過以下的圖片來看看多道運(yùn)行的情況(這里假設(shè)處理機(jī)有4個(gè)通道,調(diào)度程序采用先來先服務(wù)的算法處理作業(yè),作業(yè)序列為A,B,C,D,E,F)。

程序A提出I/O請求程序A完成通道1BF通道2CE通道3D通道4調(diào)度程序四通道程序運(yùn)行情況(黑實(shí)線—進(jìn)程進(jìn)行;綠實(shí)線—CPU正處理I/O請求;淺藍(lán)實(shí)線—進(jìn)程得到CPU批準(zhǔn)后正進(jìn)行I/O操作.)1.2.4

分時(shí)系統(tǒng)分時(shí)系統(tǒng)的產(chǎn)生.分時(shí)系統(tǒng)指在一臺主機(jī)上連接了多個(gè)帶有顯示器和鍵盤的終端,同時(shí)允許多個(gè)用戶通過自己的終端,以交互方式使用計(jì)算機(jī),共享主機(jī)資源.分時(shí)系統(tǒng)時(shí)間中的關(guān)鍵問題:如何使用戶能與自己的作業(yè)進(jìn)行交互----人機(jī)交互.分時(shí)系統(tǒng)的特征:多路性;獨(dú)立性;及時(shí)性;交互性.1.2.5

實(shí)時(shí)系統(tǒng)應(yīng)用需求:實(shí)時(shí)系統(tǒng)的誕生主要是為了滿足在實(shí)時(shí)控制;實(shí)時(shí)信息處理方面的需求。實(shí)時(shí)任務(wù):分為周期性任務(wù)與非周期性任務(wù);硬實(shí)時(shí)任務(wù)與軟實(shí)時(shí)任務(wù).實(shí)時(shí)系統(tǒng)與分時(shí)系統(tǒng)特征的比較分時(shí)系統(tǒng)實(shí)時(shí)系統(tǒng)多路性按分時(shí)原則為多個(gè)終端用戶服務(wù)不僅按分時(shí)原則為多個(gè)終端用戶服務(wù),而且系統(tǒng)經(jīng)常對多路的現(xiàn)場信息進(jìn)行采集,以及對多個(gè)對象或多個(gè)執(zhí)行機(jī)構(gòu)進(jìn)行控制.獨(dú)立性每個(gè)終端用戶獨(dú)立地向系統(tǒng)提出請求;對信息的采集和對對象的控制也也彼此互不干擾.及時(shí)性以人所能接受的等待時(shí)間確定,通常為2—3秒.以控制對象要求的開始截止時(shí)間來確定,一般為秒,百毫秒,毫秒甚至低于100微秒級.交互性可以向用戶提供數(shù)據(jù)處理,資源共享等服務(wù),進(jìn)行廣泛的人機(jī)交互.僅限于訪問系統(tǒng)中某些特定的專用服務(wù)程序.可靠性對可靠性要求不是很嚴(yán)格。對可靠性要求嚴(yán)格.采用多級容錯(cuò)措施保障系統(tǒng),數(shù)據(jù)的安全.1.3

操作系統(tǒng)的基本特性1.3.1

并發(fā)(Concurrence)1.3.2

共享(Sharing)1.3.3

虛擬(Virtual)1.3.4

異步性(Asynchronism)

1.3.1

并發(fā)(Concurrence)并發(fā)(兩個(gè)以上事件在同一時(shí)間間隔內(nèi)發(fā)生)≠并行(兩個(gè)以上事件在同一時(shí)刻發(fā)生)!并發(fā)并行單CPU多CPU單CPU多CPU單通道每個(gè)時(shí)刻僅能有一道程序運(yùn)行,所以微觀上這些程序只能是分時(shí)地交替執(zhí)行.//因?yàn)橛卸鄠€(gè)處理機(jī),所以這些可以并發(fā)執(zhí)行的程序當(dāng)然也可以被分配到多個(gè)CPU上實(shí)現(xiàn)并行執(zhí)行,即每個(gè)CPU處理一個(gè)可并發(fā)執(zhí)行的程序,這樣多個(gè)程序就實(shí)現(xiàn)了并行執(zhí)行.多通道一段時(shí)間內(nèi)宏觀上有多個(gè)程序在運(yùn)行1.3.2

共享(Sharing)共享定義:指系統(tǒng)中的資源可供內(nèi)存中多個(gè)并發(fā)執(zhí)行的進(jìn)程(線程)共同使用.由于資源屬性的不同,進(jìn)程對資源共享的方式也不同,目前主要有:互斥共享方式同時(shí)訪問方式1.3.3

虛擬(Virtual)1.3.4

異步性(Asynchronism)由于內(nèi)存中的每個(gè)進(jìn)程在何時(shí)能獲得處理機(jī)運(yùn)行,何時(shí)又因提出某種資源請求而暫停,以及進(jìn)程以怎樣的速度推進(jìn),每道程序總共需要多少時(shí)間才能完成等等都是不可預(yù)知的,所以進(jìn)程是以人們不可預(yù)知的速度向前推進(jìn)的,這就是進(jìn)程的異步性.1.4

操作系統(tǒng)的主要功能1.4.1

處理機(jī)管理功能1.4.2

存儲器管理功能1.4.3

設(shè)備管理功能1.4.4

文件管理功能1.4.5

用戶接口1.4.1

處理機(jī)管理功能進(jìn)程控制:為作業(yè)創(chuàng)建進(jìn)程,撤消已結(jié)束的進(jìn)程,以及控制進(jìn)程在運(yùn)行過程中的狀態(tài)轉(zhuǎn)換.在現(xiàn)代OS中進(jìn)程控制還要能為一個(gè)進(jìn)程創(chuàng)建若干個(gè)線程以及撤消已完成的線程.進(jìn)程同步:為多個(gè)進(jìn)程(包括線程)的運(yùn)行進(jìn)行協(xié)調(diào).有兩種協(xié)調(diào)方式:進(jìn)程互斥和進(jìn)程同步.進(jìn)程通信:用來實(shí)現(xiàn)在相互合作的進(jìn)程之間的信息交換.調(diào)度:分為作業(yè)調(diào)度(從后備隊(duì)列中按照一定的算法,選擇若干個(gè)作業(yè),為它們分配必需的資源.在將它們調(diào)入內(nèi)存后,再分別為它們建立進(jìn)程,再按照一定算法把它們插入就緒隊(duì)列);進(jìn)程調(diào)度(從進(jìn)程的就緒隊(duì)列中選出一新進(jìn)程,把處理機(jī)分配給它,并為它設(shè)置運(yùn)行現(xiàn)場,使進(jìn)程運(yùn)行.).1.4.2

存儲器管理功能1.4.3

設(shè)備管理功能緩沖管理:管理緩沖區(qū).設(shè)備分配:根據(jù)用戶進(jìn)程的I/O請求,系統(tǒng)的現(xiàn)有資源情況以及按照某種設(shè)備分配策略,為之分配其所需的設(shè)備.如果在I/O設(shè)備與CPU間還有設(shè)備控制器和I/O通道時(shí),還要為分配出去的設(shè)備分配相應(yīng)的控制器和通道.設(shè)備處理:用于實(shí)現(xiàn)CPU和設(shè)備控制器間的通信.1.4.4

文件管理功能文件存儲空間的管理.目錄管理.文件的讀/寫管理和保護(hù).1.4.5

用戶接口命令接口.程序接口.圖形接口.1.5

操作系統(tǒng)的結(jié)構(gòu)設(shè)計(jì)1.5.1

軟件工程的基本概念1.5.2

傳統(tǒng)的操作系統(tǒng)結(jié)構(gòu)1.5.3

微內(nèi)核OS結(jié)構(gòu)

1.5.1

軟件工程的基本概念1.5.2

傳統(tǒng)的操作系統(tǒng)結(jié)構(gòu)無結(jié)構(gòu)操作系統(tǒng)模塊化操作系統(tǒng)結(jié)構(gòu)分層式操作系統(tǒng)結(jié)構(gòu)1.5.3

微內(nèi)核OS結(jié)構(gòu)OS內(nèi)核的基本功能新版教材進(jìn)程管理存儲器管理進(jìn)程通信管理I/O設(shè)備管理老版教材支撐功能資源管理功能中斷處理時(shí)鐘管理原語操作進(jìn)程管理存儲器管理設(shè)備管理原語:由若干機(jī)器指令組成的并用于完成特定功能的一段程序,這段程序在執(zhí)行期間不可分割.機(jī)器指令級的特點(diǎn):執(zhí)行期間不允許中斷;功能級的特點(diǎn):不允許并發(fā)執(zhí)行.第一章習(xí)題A,B兩個(gè)程序,程序A按順序使用CPU10S,使用設(shè)備甲5s,使用CPU5s,使用設(shè)備乙10s,最后使用CPU10s;程序B按順序使用設(shè)備甲10s,使用CPU10s,使用設(shè)備乙5s,使用CPU5s,使用設(shè)備乙10s。試問:在順序環(huán)境下執(zhí)行程序A和程序B，CPU利用率多少?在多道程序環(huán)境下,CPU的利用率是多少?

答案是.第二章

進(jìn)程管理(章節(jié)圖)進(jìn)程管理

2.1

進(jìn)程的基本概念2.2

進(jìn)程控制2.3

進(jìn)程同步2.4經(jīng)典進(jìn)程的同步問題2.5

管程機(jī)制習(xí)題2.6

進(jìn)程通信2.7

線程2.1

進(jìn)程的基本概念2.1.1

程序的順序執(zhí)行及其特征2.1.2

前趨圖2.1.3

程序的并發(fā)執(zhí)行及其特征2.1.4

進(jìn)程的特征與狀態(tài)2.1.5

進(jìn)程控制塊(PCB)2.1.1

程序的順序執(zhí)行及其特征定義:把一個(gè)應(yīng)用程序分成若干個(gè)程序段,各程序段間必須按照某種先后次序逐個(gè)執(zhí)行,僅當(dāng)一個(gè)操作執(zhí)行完成后才能執(zhí)行后繼操作.特征:順序性封閉性可再顯性2.1.2

前趨圖定義:有向無環(huán)圖,記為DAG,用來描述進(jìn)程間執(zhí)行的前后關(guān)系.(圖中結(jié)點(diǎn)描述一個(gè)程序段或進(jìn)程;結(jié)點(diǎn)間有向邊表示結(jié)點(diǎn)間存在偏序或前趨關(guān)系)PiPj={(Pi,Pj)|PimustcompletebeforePjmaystart}2.1.3

程序的并發(fā)執(zhí)行及其特征定義:一組在邏輯上互相獨(dú)立的程序或程序段在執(zhí)行過程中其執(zhí)行時(shí)間在客觀上互相重疊,即一個(gè)程序段的執(zhí)行還沒結(jié)束,另一個(gè)程序段的執(zhí)行已經(jīng)開始的方式.特征:間斷性;失去封閉性;不可再現(xiàn)性.并發(fā)執(zhí)行的條件:假設(shè)R(Pi)為讀集;W(Pi)為寫集.我們知道要保證并發(fā)執(zhí)行的程序“可再現(xiàn)性”應(yīng)具備的條件是—R(P1)∩W(P2)∪R(P2)∩W(P1)∪W(P1)∩W(P2)=知道了P1,P2可并發(fā)執(zhí)行應(yīng)具備的條件,那么請大家想想要P1,P2,P3三者可以并發(fā)執(zhí)行應(yīng)具備的條件是？這里Ij,Cj,Pj,表示第j個(gè)作業(yè)的輸入程序段,計(jì)算程序段,打印程序段.2.1.4

進(jìn)程的特征與狀態(tài)進(jìn)程的定義:可并發(fā)執(zhí)行的程序在一個(gè)數(shù)據(jù)集合上的運(yùn)行過程.進(jìn)程的特征:結(jié)構(gòu)特征(進(jìn)程由程序段,相關(guān)數(shù)據(jù)段,PCB組成);動態(tài)性;并發(fā)性;獨(dú)立性;異步性.進(jìn)程的狀態(tài)基本狀態(tài)特殊狀態(tài)就緒(Ready)狀態(tài)執(zhí)行狀態(tài)阻塞狀態(tài)掛起狀態(tài)進(jìn)程得到除CPU以外的所有資源而呈現(xiàn)的狀態(tài).可以有多個(gè)進(jìn)程獲得CPU的狀態(tài).有多少個(gè)處理機(jī)就可以有多少個(gè)進(jìn)程處在執(zhí)行狀態(tài).正在執(zhí)行的進(jìn)程由于發(fā)生某事件而暫時(shí)無法繼續(xù)執(zhí)行,而放棄CPU處于暫停的狀態(tài).引入是為了滿足終端用戶的需要,父進(jìn)程的需要,OS的需要,對換的需要,負(fù)荷調(diào)節(jié)的需要.進(jìn)程與程序的區(qū)別,進(jìn)程與作業(yè)的區(qū)別.進(jìn)程三種基本狀態(tài)的轉(zhuǎn)換;引入掛起后進(jìn)程狀態(tài)的轉(zhuǎn)換.進(jìn)程與程序,進(jìn)程與作業(yè)的區(qū)別進(jìn)程與程序的區(qū)別:進(jìn)程是一個(gè)動態(tài)概念,程序是一個(gè)靜態(tài)概念.進(jìn)程具有并行特性,程序沒有并行特性.進(jìn)程是競爭計(jì)算機(jī)資源的基本單位,而程序不是.同一程序可以對應(yīng)不同的進(jìn)程.進(jìn)程與作業(yè)的區(qū)別:作業(yè)是用戶向計(jì)算機(jī)提交的任務(wù)實(shí)體.一個(gè)作業(yè)可以由多個(gè)進(jìn)程組成.作業(yè)的概念主要用在批處理系統(tǒng)中.進(jìn)程三種基本狀態(tài)的轉(zhuǎn)換接納進(jìn)程調(diào)度I/O請求或某等待事件發(fā)生I/O完成或事件發(fā)生時(shí)間片完舉例:首先我們給各個(gè)狀態(tài)的轉(zhuǎn)換編號如上圖.假設(shè)你在排隊(duì)買票,售票大廳只有一個(gè)門,門外的人必須先通過門衛(wèi)才能入內(nèi)買票—相當(dāng)于1;扶手之間的人是排了隊(duì)的,只要窗口空閑,他們就可以買票—相當(dāng)于2;你在買票過程中被朋友叫出—相當(dāng)于3;若你買票時(shí)剛好身后一位老人家要買票,大家請你讓老人家先買,你就讓老人家先買了—相當(dāng)于4;如果你剛被朋友叫出隊(duì)伍,現(xiàn)在回來買票了就要重新排隊(duì)—相當(dāng)于5;12345引入掛起后進(jìn)程狀態(tài)的轉(zhuǎn)換釋放接納進(jìn)程調(diào)度I/O請求或某等待事件發(fā)生掛起激活掛起激活掛起釋放2.1.5

進(jìn)程控制塊(PCB)作用:用于描述進(jìn)程情況及控制運(yùn)行所需的全部信息,是系統(tǒng)感知進(jìn)程存在的唯一途徑,隨進(jìn)程創(chuàng)建而被系統(tǒng)建立,隨進(jìn)程消亡而被系統(tǒng)收回.PCB中的信息:進(jìn)程標(biāo)識符:唯一標(biāo)識進(jìn)程(內(nèi)部標(biāo)識,外部標(biāo)識符)處理機(jī)狀態(tài):指通用寄存器,指令計(jì)數(shù)器,程序狀態(tài)字PSW,用戶棧指針,這些個(gè)寄存器中內(nèi)容的集合.進(jìn)程調(diào)度信息:進(jìn)程狀態(tài),進(jìn)程優(yōu)先級,其他信息以及事件.進(jìn)程控制信息:程序和數(shù)據(jù)的地址,進(jìn)程同步和通信機(jī)制,資源清單,鏈接指針.PCB的組織方式:鏈接方式索引方式鏈接方式執(zhí)行指針就緒隊(duì)列指針阻塞隊(duì)列指針空閑隊(duì)列指針PCB14PCB23PCB30PCB48PCB5PCB67PCB79PCB80PCB91索引方式PCB1PCB2PCB3PCB4PCB5PCB6PCB7執(zhí)行指針就緒表指針阻塞表指針就緒索引表阻塞索引表2.2

進(jìn)程控制2.2.1

進(jìn)程的創(chuàng)建2.2.2

進(jìn)程的終止2.2.3

進(jìn)程的阻塞與喚醒2.2.4

進(jìn)程的掛起與激活2.2.1

進(jìn)程的創(chuàng)建進(jìn)程圖:描述進(jìn)程家族關(guān)系的有向樹.引起創(chuàng)建進(jìn)程的事件:用戶登陸;作業(yè)調(diào)度;提供服務(wù);應(yīng)用請求.進(jìn)程的創(chuàng)建:申請空白PCB;為新進(jìn)程分配資源;初始化進(jìn)程控制塊;將新進(jìn)程插入新就緒隊(duì)列.下面我們分別通過創(chuàng)建原語流程圖;撤消原語流程圖;阻塞原語流程圖;喚醒原語流程圖.來講解進(jìn)程的創(chuàng)建過程.創(chuàng)建原語流程圖入口查PCB鏈表有空PCB是否返回創(chuàng)建失敗取空表PCB(i)將有關(guān)參數(shù)填入PCB(i)相應(yīng)項(xiàng)PCB(i)入就緒隊(duì)列PCB(i)入進(jìn)程家族或進(jìn)程鏈撤消原語流程圖入口查進(jìn)程鏈表或進(jìn)程家族有些PCB返回出錯(cuò)處理釋放該進(jìn)程所占有的資源釋放該P(yáng)CB結(jié)構(gòu)本身該P(yáng)CB有子進(jìn)程是否有無阻塞原語流程圖;喚醒原語流程圖入口保存當(dāng)前進(jìn)程的CPU現(xiàn)場置該進(jìn)程的狀態(tài)被阻塞進(jìn)程入等待隊(duì)列轉(zhuǎn)進(jìn)程調(diào)度入口從等待隊(duì)列中摘下被喚醒進(jìn)程將被喚醒進(jìn)程置為就緒態(tài)將被喚醒進(jìn)程送入就緒隊(duì)列轉(zhuǎn)進(jìn)程調(diào)度或返回2.2.2

進(jìn)程的終止引起進(jìn)程終止的事件:正常結(jié)束;異常結(jié)束;外界干預(yù).進(jìn)程的終止過程.2.2.3

進(jìn)程的阻塞與喚醒引起阻塞和喚醒的事件:請求系統(tǒng)服務(wù);啟動某種操作;新數(shù)據(jù)尚未到達(dá);無新工作可做.進(jìn)程阻塞過程.進(jìn)程喚醒過程.2.2.4

進(jìn)程的掛起與激活進(jìn)程的掛起.進(jìn)程的激活過程.2.3

進(jìn)程同步2.3.1

進(jìn)程同步的基本概念2.3.2

信號量機(jī)制2.3.3

信號量的應(yīng)用2.3.1

進(jìn)程同步的基本概念兩種形式的制約關(guān)系:間接相互制約關(guān)系—資源公享;直接相互制約關(guān)系—進(jìn)程間的合作.臨界資源:一次只允許一個(gè)進(jìn)程使用的資源,而不能同時(shí)共享的資源(CriticalResouce).詳見教材P39頁的生產(chǎn)者—消費(fèi)者問題描述.臨界區(qū):每個(gè)進(jìn)程中訪問臨界資源的那段代碼叫臨界區(qū).同步機(jī)制應(yīng)遵循的規(guī)則:空閑讓進(jìn);忙則等待;有限等待;讓權(quán)等待.RepeatCriticalsection;Remaindersection;Untilfalse;EntrysectionExitsection2.3.2

信號量機(jī)制整型信號量:P,V操作.記錄型信號量:P,V操作的修改版.引入一個(gè)代表資源數(shù)目的整型變量VALUE和一個(gè)進(jìn)程鏈表L.AND型信號量:將進(jìn)程在整個(gè)運(yùn)行過程中需要的所有資源,一次全分給進(jìn)程,待進(jìn)程用完后再一起釋放.在wait操作中增加一個(gè)〝AND〞條件,所以稱為AND同步.信號量集:AND信號量機(jī)制的擴(kuò)充.2.3.3

信號量的應(yīng)用軟件方法解決互斥問題利用硬件方法解決進(jìn)程互斥問題利用信號量實(shí)現(xiàn)進(jìn)程互斥利用信號量實(shí)現(xiàn)前趨關(guān)系軟件方法解決互斥問題這是早期的方法,現(xiàn)在已經(jīng)很少用了.這里介紹它是為了讓大家了解在早期解決進(jìn)程互斥問題是多么不容易!假如有兩個(gè)進(jìn)程Pi和Pj,它們共享一個(gè)臨界資源R;起程序段如下:BeginparbeginPi;Pj;parendend為簡單起見,下面我們羅列的4個(gè)算法中只是寫出了Pi這個(gè)部分.算法一;算法二;算法三;算法四.軟件方法解決互斥—算法一RepeatCriticalsectionRemaindersectionUntilfalse;Whileturn≠idono_opTurn:=j;缺點(diǎn):強(qiáng)制Pi,Pj輪流使用臨界資源,沒考慮實(shí)際情況.不滿足空閑讓進(jìn)原則.軟件方法解決互斥—算法二Varflag:array[0,1,……,n]ofboolean;Repeat

Criticalsection

RemaindersectionUntilfalse;Whileflag[j]dono_opFlag[i]:=true;Flag[i]:=false;

問題在于:當(dāng)進(jìn)程Pi觀察到Pj的標(biāo)志為false后,便將自己的標(biāo)志改為true,但這個(gè)改動需要一極短的時(shí)間,而在這個(gè)極短時(shí)間內(nèi)它仍然表現(xiàn)為false而被Pj觀察到.軟件方法解決互斥—算法三RepeatCriticalsectionRemaindersectionUntilfalse;Flag[i]:=true;Flag[i]:=false;Whileflag[j]dono_op

該算法解決了同時(shí)進(jìn)入臨界區(qū)的問題,但可能會出現(xiàn)雙方都不能進(jìn)入的問題.這就違反了空閑讓進(jìn)和有限等待的原則.軟件方法解決互斥—算法四RepeatCriticalsectionRemaindersectionUntilfalse;Flag[i]:=true;turn:=j;While(flag[j]andturn=j)dono_op;Flag[i]:=false;若某個(gè)Pi進(jìn)入,其他能否進(jìn)入?若兩個(gè)或以上的p幾乎同時(shí)執(zhí)行第一個(gè)while時(shí),是否會有同時(shí)進(jìn)出的情況?是否存在相互等待的情況?利用硬件方法解決進(jìn)程互斥問題利用Test-and-Set指令實(shí)現(xiàn)互斥利用Swap指令實(shí)現(xiàn)進(jìn)程互斥RepeatCricticalsectionRemaindersectionUntilfalse;WhileTs(lock)doskip;Lock:=false;FunctionTs(varlock:boolean):boolean;beginTs:=lock;lock:=true;endRepeatCricticalsectionRemaindersectionUntilfalse;Key:=true;repeatSwap(lock,key);untilkey=false;Lock:=false;ProcedureSwap(vara,b:boolean)Vartemp:boolean;begintemp:=a;a:=b;b:=temp;end利用信號量實(shí)現(xiàn)進(jìn)程互斥Varmutex:semaphore:=1;Beginparbeginprocess1:beginrepeatwait(mutex);criticalsectionsignal(mutex);remaindersectionuntilfalse;endProcess2:beginrepeatwait(mutex);criticalsectionsignal(mutex);remaindersectionuntilfalse;endparendEnd利用信號量實(shí)現(xiàn)前趨關(guān)系Vara,b,c,d,e,f,g;semaphore:=0,0,0,0,0,0,0;beginparbeginbeginS1;signal(a);signal(b);end;beginwait(a);S2;signal(c);signal(d);end;beginwait(b);S3;signal(e);end;beginwait(c);S4;signal(f);end;beginwait(d);S5;signal(g);end;beginwait(e);wait(f);wait(g);S6;end;parendend2.4

經(jīng)典進(jìn)程的同步問題2.4.1

生產(chǎn)者—消費(fèi)者問題2.4.2

哲學(xué)家進(jìn)餐問題

讀者—寫者問題2.4.4理發(fā)師問題2.4.1

生產(chǎn)者—消費(fèi)者問題生產(chǎn)者—消費(fèi)者問題說的是生產(chǎn)者和消費(fèi)者公用一個(gè)具有n個(gè)緩沖區(qū)的緩沖池(表示可以存放n個(gè)物品);只要緩沖池未滿,生產(chǎn)者便可以向里面投放物品.只要緩沖池不空,消費(fèi)者就可以從里面取出物品使用.但要保證只要有人在使用緩沖池時(shí),其他任何人都不能使用緩沖池.一般來說我們有兩種方法來解決這個(gè)問題:利用記錄型信號量;利用AND信號量.但不管那種方法,開始的時(shí)候我們都要先定義互斥信號量mutex;記錄信號量empty和full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量.以及定義一個(gè)緩沖池buffer:array.程序段如下:Varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,….,n-1]ofitem;(定義一個(gè)容量為n的緩沖池)in,out:integer:=0,0;(開始是假設(shè)緩沖池中的輸入/輸出指針都指向緩沖區(qū)頭部)生產(chǎn)-消費(fèi)者—利用記錄型信號量Beginparbeginproceduer:beginrepeat……

produceranitemnextp;……wait(empty);wait(mutex);buffer(in):=nextp;in:=(in+1)modn;signal(mutex);signal(full);untilfalse;end這里的wait操作詳見課本第42頁上部.大家想想這里的兩組wait()語句(1)和(2)的順序可以對調(diào)么?1Consumer:beginrepeatwait(full);wait(mutex);nextc:=buffer(out);out:=(out+1)modn;signal(mutex);signal(empty);……

consumertheiteminnextc;

……untilfalse;endparendEnd2生產(chǎn)-消費(fèi)者—利用AND信號量Beginparbeginproducer:beginrepeat…….produceaniteminnextp;……Swait(empty,mutex);buffer(in):=nextp;in:=(in+1)modn;Ssignal(mutex,full);untilfalse;endConsumer:beginrepeatSwait(full,mutex);nextc:=buffer(out);out:=(out+1)modn;Ssignal(mutex,empty);consumertheiteminnextc;untilfalse;endparendend2.4.2

哲學(xué)家進(jìn)餐問題該問題描述有五個(gè)哲學(xué)家公用一張圓桌,分別坐在周圍的五張椅子上,在圓桌上有五個(gè)碗和五根筷子,他們的生活方式是交替地進(jìn)行思考和進(jìn)餐.平時(shí),一個(gè)哲學(xué)家進(jìn)行思考,饑餓時(shí)便試圖取用其左右最靠近他的筷子,只有在他拿到兩只筷子時(shí)才能進(jìn)餐.進(jìn)餐完放下筷子繼續(xù)思考.在這里很明顯—筷子就是臨界資源,所以程序開頭要把每個(gè)筷子定義為一個(gè)信號量:varchopstick:array[0,….,4]ofsemaphore;同樣這里我們也可以使用記錄型信號量,AND信號量這兩種方法來解決問題.Repeatwait(chopstick[i]);wait(chopstick[(i+1)mod5]);…….eat;…….signal(chopstick[i]);signal(chopstick[(i+1)mod5]);…….think;Untilfalse;varchopstick:array[0,…,4]ofsemaphore:=(1,1,1,1,1);processirepeatthink;Sswait(chopstick[(i+1)mod5],chopstick[i]);eat;Ssignal(chopstick[(i+1)mod5],chopstick[i]);untilfalse;記錄型信號量AND信號量2.4.3

讀者—寫者問題一個(gè)數(shù)據(jù)文件或記錄,可被多個(gè)進(jìn)程共享,我們把只要求讀該文件的進(jìn)程叫Reader進(jìn)程;其他進(jìn)程叫Writer進(jìn)程.允許多個(gè)進(jìn)程同時(shí)讀一個(gè)共享對象,但不允許一個(gè)Writer進(jìn)程和其他Reader或Writer進(jìn)程同時(shí)訪問共享對象;既保證一個(gè)Writer進(jìn)程必須與其他進(jìn)程互斥地訪問共享對象的同步問題就叫讀者—寫者問題!這里我們還是用記錄型信號量和信號量集機(jī)制兩個(gè)方法來解決問題.讀-寫者問題—利用記錄型信號量Varrmutex,wmutex:semaphore:=1,1;readcount:integer:=0;beginparbeginreader:beginrepeatwait(rmutex);ifreadcount=0thenwait(wmutex);readcount:=readcount+1;signal(rmutex);…….performreadoperation;…….wait(rmutex);readcount:=readcount-1;ifreadcount=0thensignal(wmutex);signal(rmutex);untilfalse;endWriter:beginrepeatwait(wmutex);performwriteoperation;signal(wmutex);untilfalse;endparendend如無這兩句,則可令兩個(gè)IF語句同時(shí)運(yùn)行而出錯(cuò)!讀-寫者問題—利用信號量集機(jī)制VarRNinteger;L,mx:semaphore:=RN,1;beginparbeginreader:beginrepeatSwait(L,1,1);Swait(mx,1,0);…….Performreadoperation;……Ssignal(L,1);untilfalse;endWriter:beginrepeatSwait(mx,1,1;L,RN,0);performwriteoperation;Ssignal(mx,1);untilfalse;endparendend2.4.4理發(fā)師問題理發(fā)師問題是使用信號量實(shí)現(xiàn)并發(fā)的另一個(gè)例子,它同OS中的實(shí)際問題非常相似.設(shè)理發(fā)店有三個(gè)理發(fā)師,三個(gè)理發(fā)師和一個(gè)可容納4個(gè)人的等候室.還有一個(gè)供其他顧客休息的地方,如下圖.理發(fā)店中顧客總數(shù)不超過20,在這個(gè)例子中假定理發(fā)店最終接待5名顧客時(shí)刻,登記本只能記錄一個(gè)顧客的付款,理發(fā)師的全部時(shí)間用在理發(fā),收款和在理發(fā)椅上睡眠以等待顧客.請大家想想怎么用某種信號量機(jī)制來模擬這個(gè)理發(fā)店的運(yùn)作?理發(fā)椅1理發(fā)椅2理發(fā)椅3沙發(fā)1沙發(fā)2沙發(fā)3沙發(fā)4收款臺入口出口2.5

管程機(jī)制2.5.1

管程的基本概念管程:一個(gè)數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程所執(zhí)行的一組操作,且這組操作能改變管程中的數(shù)據(jù).2.5.2

利用管程解決生產(chǎn)者—消費(fèi)者問題2.6

進(jìn)程通信2.6.1

進(jìn)程通信的類型2.6.2

消息傳遞通信的實(shí)現(xiàn)方法2.6.3

消息傳遞系統(tǒng)實(shí)現(xiàn)中的若干問題

2.6.4

消息緩沖隊(duì)列通信機(jī)制2.6.1

進(jìn)程通信的類型共享存儲器系統(tǒng)(Shared-MemorySystem)消息傳遞系統(tǒng)(Messagepassingsystem)管道(Pipe)通信2.6.2

消息傳遞通信的實(shí)現(xiàn)方法直接通信方式Send(receiver,message);Receive(sender,message);間接通信方式Send(mailbox,message);Receive(mailbox,message);消息傳遞系統(tǒng)實(shí)現(xiàn)中的若干問題通信鏈路消息的格式進(jìn)程同步方式2.6.4

消息緩沖隊(duì)列通信機(jī)制消息緩沖隊(duì)列通信機(jī)制中的數(shù)據(jù)結(jié)構(gòu)消息緩沖區(qū)PCB中有關(guān)通信的數(shù)據(jù)項(xiàng)發(fā)送原語接收原語2.7

線程2.7.1

線程的基本概念2.7.2

線程間的同步和通信2.7.3

內(nèi)核支持線程和用戶級線程2.7.4

線程控制2.7.1

線程的基本概念在OS中引入進(jìn)程的目的是為了使多個(gè)程序能并發(fā)執(zhí)行,以提高資源利用率和系統(tǒng)吞吐量;再引入線程是為了減少程序在并發(fā)執(zhí)行時(shí)所付出的時(shí)空開銷,使OS有更好的并發(fā)性.下面我們通過一個(gè)表格來看下引入線程后進(jìn)程同線程的比較:進(jìn)程線程調(diào)度僅僅是擁有資源的基本單位作為調(diào)度和分配的基本單位并發(fā)性不僅進(jìn)程間可以并發(fā)執(zhí)行,而且一個(gè)進(jìn)程中的多個(gè)線程間也可并發(fā)執(zhí)行.擁有資源進(jìn)程是擁有資源的一個(gè)獨(dú)立單位線程自己不擁有系統(tǒng)資源,但可以訪問隸屬進(jìn)程的資源系統(tǒng)開銷進(jìn)程切換的開銷＞＞線程切換的開銷2.7.2

線程間的同步和通信互斥鎖(mutex)條件變量信號量機(jī)制2.7.3

內(nèi)核支持線程和用戶級線程內(nèi)核支持線程用戶級線程2.7.4

線程控制內(nèi)核支持線程的實(shí)現(xiàn)用戶級線程的實(shí)現(xiàn)第二章習(xí)題一郵件分揀系統(tǒng),若分揀臺上每次只允許放一郵件,以識別該郵件是否航空郵件,若是則放入航空郵包,否則放入陸運(yùn)郵包,在郵件取走后才能對下一個(gè)郵件進(jìn)行識別.只有識別之后,才允許取走.試分析用p,v操作描述此分揀過程.現(xiàn)有四進(jìn)程R1,W1,R2,W2;它們共享可以存放一個(gè)數(shù)的緩沖區(qū)B.進(jìn)程R1每次把從鍵盤讀入的一個(gè)數(shù)存到B中,供進(jìn)程W1打印輸出;進(jìn)程R2每次從鍵盤讀一個(gè)數(shù)存放到B中,供進(jìn)程W2打印輸出;當(dāng)一進(jìn)程把數(shù)存放到B后,在該數(shù)還沒有被打印輸出前不準(zhǔn)任何進(jìn)程再向B中存數(shù),當(dāng)一個(gè)進(jìn)程已把B中的數(shù)打印輸出后,在B中還沒有存入一個(gè)新的數(shù)前,不準(zhǔn)任何進(jìn)程再從緩沖區(qū)中取數(shù)打印,怎樣才能使這四個(gè)進(jìn)程在并發(fā)執(zhí)行時(shí)協(xié)調(diào)工作?有一應(yīng)急公路橋,為單行道,其管理規(guī)則:當(dāng)從某一方向的車輛通過時(shí),只要它還沒有到達(dá)對岸,同一方向的車輛就可以上橋通行.另一方向的車輛要進(jìn)入時(shí),必須等待當(dāng)橋上無車時(shí)才可以通行.試用P,V操作描述其實(shí)現(xiàn)過程.(用記錄型型號量,一般信信號量機(jī)制)在一大型BUS上,司機(jī)和前后門的售票員各司其職—司機(jī)開車,停車,通知售票員;售票員平時(shí)售票,接到通知后先轉(zhuǎn)去后門讓后門售票員開門下客,隨后開前門上客.當(dāng)無下車人時(shí),關(guān)后門再通知前門.當(dāng)無上車人時(shí)關(guān)前門,然后由前門通知司機(jī),司機(jī)開車.用P,V操作描述這一過程.若有一售票廳只能容納300人,當(dāng)少于300人時(shí),可以進(jìn)入;否則,需在外等候.若將每一個(gè)購票者作為一個(gè)進(jìn)程,請用P,V操作編程,并寫出信號量的初值.看答案！第三章

處理機(jī)調(diào)度與死鎖(章節(jié)圖)處理機(jī)調(diào)度與死鎖3.1

處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時(shí)調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度

3.5產(chǎn)生死鎖的原因和必要條件習(xí)題3.6

預(yù)防死鎖的方法3.7

死鎖的檢測與解除3.1

處理機(jī)調(diào)度的基本概念3.1.1

高級、中級和低級調(diào)度3.1.2

調(diào)度隊(duì)列模型3.1.3

選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則3.1.1

高級、中級和低級調(diào)度高級調(diào)度:作業(yè)調(diào)度或長程調(diào)度.在每次執(zhí)行作業(yè)調(diào)度時(shí)都需要做出以下兩個(gè)決定—接納多少個(gè)作業(yè);接納哪些作業(yè).低級調(diào)度:進(jìn)程調(diào)度或短程調(diào)度.進(jìn)程調(diào)度采用兩種調(diào)度方式—非搶占方式;搶占方式(優(yōu)先權(quán)原則,短作業(yè)[進(jìn)程]優(yōu)先原則,時(shí)間片原則).中級調(diào)度:中程調(diào)度.引入它是為了使那些暫時(shí)不能執(zhí)行的進(jìn)程不再占用寶貴的內(nèi)存空間,而將它們調(diào)至外存上等待.3.1.2

調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型(詳見課本P72)具有高級和低級調(diào)度的調(diào)度隊(duì)列模型(P73)同時(shí)具有三級調(diào)度的調(diào)度隊(duì)列模型(P74)3.1.3

選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則面向用戶的準(zhǔn)則周轉(zhuǎn)時(shí)間短.(了解平均周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間)響應(yīng)時(shí)間快截止時(shí)間的保證優(yōu)先權(quán)準(zhǔn)則面向系統(tǒng)的準(zhǔn)則系統(tǒng)吞吐量高處理機(jī)利用率好各類資源的平衡利用3.2

調(diào)度算法3.2.1

先來先服務(wù)和短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法3.2.2

高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.2.3

基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法3.2.1

先來先服務(wù)和短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法在作業(yè)調(diào)度中在進(jìn)程調(diào)度中先來先服務(wù)(FCFS)每次調(diào)度從后備隊(duì)列中選擇一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)把它們調(diào)入內(nèi)存為它們分配資源,創(chuàng)建進(jìn)程,然后放入就緒隊(duì)列.每次調(diào)度從就緒隊(duì)列中,選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程為它分配CPU,讓它投入運(yùn)行.短作業(yè)[進(jìn)程]優(yōu)先(SJ[P]F)SJF就是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)將它們調(diào)入內(nèi)存運(yùn)行.SPF從就緒隊(duì)列中選出一估計(jì)運(yùn)行時(shí)間最短的進(jìn)程,將CPU分配給它,使它立即執(zhí)行并一直執(zhí)行到完成或發(fā)生某事件而被阻塞放棄CPU時(shí),再重新調(diào)度.CPU或內(nèi)存ABCDEFCFSSJ[P]F左圖示出有五個(gè)進(jìn)程A,B,C,D,E到達(dá)時(shí)間分別是0,1,2,3,4;要求的服務(wù)時(shí)間分別為4,3,5,2,4;完成時(shí)間分別是4,7,12,14,18;本圖給出了這5個(gè)分別在FCFS和SJ[p]F算法下的調(diào)度過程.下面我們再通過表格來認(rèn)識.FCFS和SJ(P)F調(diào)度對比表格作業(yè)情況調(diào)度算法進(jìn)程名ABCDE平均到達(dá)時(shí)間01234服務(wù)時(shí)間43524FCFS(a)完成時(shí)間47121418周轉(zhuǎn)時(shí)間461011149帶權(quán)周轉(zhuǎn)時(shí)間1225.53.52.8SJF(b)完成時(shí)間4918613周轉(zhuǎn)時(shí)間4816398帶權(quán)周轉(zhuǎn)時(shí)間12.673.11.52.252.1周轉(zhuǎn)時(shí)間Ti指從作業(yè)被提交給系統(tǒng)開始到作業(yè)完成為止的這段時(shí)間間隔.平均周轉(zhuǎn)時(shí)間T就是所有作業(yè)的Ti的平均值.帶權(quán)周轉(zhuǎn)時(shí)間W是平均周轉(zhuǎn)時(shí)間T和某個(gè)作業(yè)周轉(zhuǎn)時(shí)間Ti的比值.3.2.2

高優(yōu)先權(quán)優(yōu)先調(diào)度算法優(yōu)先權(quán)調(diào)度算法的類型:非搶占式優(yōu)先權(quán)調(diào)度算法搶占式優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)的類型:靜態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán)高響應(yīng)比優(yōu)先調(diào)度算法:Rp===優(yōu)先權(quán)等待時(shí)間+要求服務(wù)時(shí)間要求服務(wù)時(shí)間響應(yīng)時(shí)間要求服務(wù)時(shí)間3.2.3

基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法時(shí)間片輪轉(zhuǎn)法多級反饋隊(duì)列調(diào)度算法多級反饋隊(duì)列調(diào)度算法的性能:有較好的性能,能較好地滿足各類型用戶的需要—終端型作業(yè)用戶;短批處理作業(yè)用戶;長批處理作業(yè)用戶.就緒隊(duì)列1就緒隊(duì)列2就緒隊(duì)列3就緒隊(duì)列nS1至CPUS2至CPUS3至CPU至CPU時(shí)間片S1<S2<S33.3

實(shí)時(shí)調(diào)度3.3.1

實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件提供必要的信息系統(tǒng)處理能力強(qiáng)采用搶占式調(diào)度機(jī)制具有快速切換機(jī)制3.3.2

實(shí)時(shí)調(diào)度算法的分類非搶占式調(diào)度算法搶占式調(diào)度算法3.3.3

常用的幾種實(shí)時(shí)調(diào)度算法最早截止時(shí)間優(yōu)先即EDF算法最低松弛度優(yōu)先度即LLF算法3.4

多處理機(jī)系統(tǒng)中的調(diào)度3.4.1

多處理器系統(tǒng)的類型:緊密耦合MPS和松弛耦合MPS;對稱多處理器系統(tǒng)和非對稱多處理器系統(tǒng).3.4.2

進(jìn)程分配方式:對稱多處理器系統(tǒng)中的進(jìn)程分配方式;非對稱MPS中的進(jìn)程分配方式.3.4.3

進(jìn)程(線程)調(diào)度方式:自調(diào)度方式;成組調(diào)度方式;專用處理器分配.3.5

產(chǎn)生死鎖的原因和必要條件3.5.1

產(chǎn)生死鎖的原因:競爭資源;進(jìn)程間推進(jìn)順序非法.3.5.2

產(chǎn)生死鎖的必要條件:互斥,請求和保持條件,不剝奪條件,環(huán)路等待條件.3.5.3

處理死鎖的基本方法:預(yù)防死鎖,避免死鎖,檢測死鎖,解除死鎖.3.5.1

產(chǎn)生死鎖的原因競爭資源引起進(jìn)程死鎖:可剝奪和非剝奪性資源;競爭非剝奪性資源;競爭臨時(shí)性資源.進(jìn)程推進(jìn)順序不當(dāng)引起死鎖:進(jìn)程推進(jìn)順序合法;進(jìn)程推進(jìn)順序非法.R1R2S1S3S2P2Req(R2)P2Rel(R2)P2Rel(R1)P2Req(R1)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)不安全區(qū)D3.6

預(yù)防死鎖的方法3.6.1

預(yù)防死鎖:摒棄〝請求和保持〞條件;摒棄〝不剝奪〞條件;摒棄〝環(huán)路等待〞條件.3.6.2

系統(tǒng)安全狀態(tài)3.6.3

利用銀行家算法避免死鎖3.6.2

系統(tǒng)安全狀態(tài)安全狀態(tài):是指系統(tǒng)能按某種進(jìn)程順(P1,P2,……,Pn)(稱<P1,P2,……,Pn>序列為安全序列),來為每個(gè)進(jìn)程Pi分配所需資源,直至滿足每個(gè)進(jìn)程對資源的最大需求,使每個(gè)進(jìn)程都可順利地完成.如果系統(tǒng)無法找到這樣一個(gè)安全序列,則稱系統(tǒng)處于不安全狀態(tài).安全狀態(tài)之例:假定系統(tǒng)中有三個(gè)進(jìn)程P1,P2,P3,共有12臺磁帶機(jī).下表列出T0時(shí)刻的資源分配情況.從下表中我們可找到一個(gè)安全序列<P2,P1,P3>.進(jìn)程最大需求已分配可用P11053P242P392有安全狀態(tài)向不安全狀態(tài)轉(zhuǎn)換:在上述的T0時(shí)刻后,如果P3首先要求1臺磁帶機(jī),系統(tǒng)便進(jìn)入不安全狀態(tài).3.6.3

利用銀行家算法避免死鎖銀行家算法中的數(shù)據(jù)結(jié)構(gòu):可利用資源向量-Available;最大需求矩陣-Max;分配矩陣-Allocation;需求矩陣-Need.銀行家算法:如果Requesti[j]=k表示進(jìn)程Pi需要K個(gè)Rj類資源.如果Requesti[j]≤Need[i,j],便裝向2;否則報(bào)錯(cuò),因?yàn)樗蟮馁Y源數(shù)超過它宣布的最大值.如果Requesti[j]≤Available[j],便轉(zhuǎn)向3;否則表示尚無足夠資源,Pi需要等待.系統(tǒng)試探著把資源分配給進(jìn)程Pi,并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值:Available[j]:=Available[j]-Requesti[j];Allocation[i,j]:=Allocation[i,j]+Requesti[j];Need[i,j]:=Need[i,j]-Requesti[j];系統(tǒng)執(zhí)行安全性算法,檢查此次資源分配后,系統(tǒng)是否處于安全狀態(tài).若安全,才正式將資源分配給進(jìn)程Pi;否則將本次的試探分配作廢,恢復(fù)原來的資源分配狀態(tài)讓進(jìn)程Pi等待.安全性算法:設(shè)兩個(gè)向量:工作向量Work-表系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目;Finish-表系統(tǒng)是否有足夠的資源分配給進(jìn)程.從進(jìn)程集合中找出符合下列條件的進(jìn)程:Finish[i]=false;Need[i,j]≤Work[j].如果找到符合條件的進(jìn)程則執(zhí)行步驟3;否則執(zhí)行步驟4.當(dāng)進(jìn)程Pi獲得資源后,可順利執(zhí)行到完成,再釋放占有資源.應(yīng)執(zhí)行:Work[j]:=Work[i]+Allocation[i,j];Finish[i]:=true;gotostep2;如果所有進(jìn)程的Finish[i]=true滿足,則表示系統(tǒng)處于安全狀態(tài);否則系統(tǒng)處于不安全狀態(tài).銀行家算法之例:假定系統(tǒng)有五個(gè)進(jìn)程{P0,P1,P2,P3,P4};三類資源{A,B,C}銀行家算法之例資源情況進(jìn)程MaxAllocationNeedAvailableABCABCABCABCP0753010743332230P1322200122302020P2902302600P3222211011P4433002431上表表示了T0時(shí)刻的資源分配表,按照銀行家的習(xí)慣第一步我們先來評估下這個(gè)時(shí)刻的安全性-運(yùn)用安全性算法!;結(jié)果我們找到安全序列{P1,P3,P4,P2,P0}所以這個(gè)時(shí)候系統(tǒng)是安全的.接下來我們就可以來響應(yīng)進(jìn)程的請求了,不過一定要按安全序列先后來響應(yīng)啊!這里假設(shè)進(jìn)程P1提出了一個(gè)請求向量Request(1,0,2);系統(tǒng)響應(yīng)它,并修改Availabel,Allocation1,Need1向量;做完這些就得到T1時(shí)刻的資源分配表了.接下來就是重復(fù)以上的步驟了!3.7

死鎖的檢測與解除3.7.1

死鎖的檢測3.7.2

死鎖的解除:常采用的方法有剝奪資源撤消進(jìn)程3.7.1

死鎖的檢測資源分配圖:由一組結(jié)點(diǎn)N和一組邊E組成,記G=(N,E);N=P∪R={P1,P2…Pn}∪{R1,R2…Rn}=進(jìn)程結(jié)點(diǎn)∪資源結(jié)點(diǎn);E=<P,R>或<R,P>;其中請求邊<Pi,Rj>表示進(jìn)程Pi申請資源Rj;分配邊<Rj,Pi>表示把一個(gè)資源Rj分配給Pi.R1R2死鎖定理:利用把資源分配圖簡化檢測系統(tǒng)在S狀態(tài)下是否死鎖在資源分配圖中找出一個(gè)既不阻塞又不獨(dú)立的進(jìn)程結(jié)點(diǎn)Pi.上例中為進(jìn)程P2.P1釋放資源后可使P2順利完成,到P2完成后便釋放占用的所有資源.經(jīng)過一系列的簡化后,若能消去圖中所有邊使得所有進(jìn)程結(jié)點(diǎn)成為孤立結(jié)點(diǎn)稱該圖可完全簡化.這里資源數(shù)為(R1,R2)=(3,2)第三章習(xí)題--1設(shè)有四個(gè)作業(yè)J1,J2,J3,J4,它們的到達(dá)時(shí)間和計(jì)算時(shí)間如下表.作業(yè)到達(dá)時(shí)刻/時(shí)計(jì)算時(shí)間/小時(shí)J18:002J28:301J39:000.25J49:300.5若這四個(gè)作業(yè)在一臺處理機(jī)上按單道方式運(yùn)行,采用響應(yīng)比高優(yōu)先調(diào)度的算法,試寫出各作業(yè)的執(zhí)行順序,各作業(yè)的周轉(zhuǎn)時(shí)間以及平均周轉(zhuǎn)時(shí)間.看答案！設(shè)m為同類資源數(shù),n為系統(tǒng)中的并發(fā)進(jìn)程數(shù),W為每個(gè)進(jìn)程所需要的資源數(shù).試問如下表所示情況中系統(tǒng)會死鎖的是?看答案！mnW(1)431(2)422(3)432(4)423第三章習(xí)題--2下面是兩個(gè)并發(fā)執(zhí)行的進(jìn)程.它們能正確執(zhí)行么？若不能,請舉例說明,并改正.看答案!ProcessP2Vart,u:integer;beginx:=0;t:=0;ifx<1thent:=t+2;u:=t;endcoendcobeginVarx:integer;processP1Vary,z:integer;beginx:=1;y:=0;ifx≥1theny:=y+1;z:=y;end考慮5個(gè)進(jìn)程P1,P2,P3,P4,P5,見下表.規(guī)定進(jìn)程的優(yōu)先數(shù)越小,優(yōu)先級越高.試描述在采用下述幾種調(diào)度算法時(shí)各個(gè)進(jìn)程運(yùn)行過程,并計(jì)算采用每種算法時(shí)的進(jìn)程平均周轉(zhuǎn)時(shí)間.假設(shè)忽略進(jìn)程的調(diào)度時(shí)間.(1)先來先服務(wù)調(diào)度算法;(2)時(shí)間片輪轉(zhuǎn)調(diào)度算法(時(shí)間片為1ms);第(3)非剝奪式優(yōu)先級調(diào)度算法;(4)剝奪式優(yōu)先級調(diào)度算法.看答案!進(jìn)程創(chuàng)建時(shí)刻運(yùn)行時(shí)間/ms優(yōu)先數(shù)P1033P2265P3441P4652P5824第三章習(xí)題--3假設(shè)某系統(tǒng)中有4種資源(R1,R2,R3,R4),在某時(shí)刻系統(tǒng)中共有5個(gè)進(jìn)程.進(jìn)程P1,P2,P3,P4,P5的最大資源需求數(shù)向量和此時(shí)已分配到的資源數(shù)向量如下：進(jìn)程當(dāng)前已分配到資源 最大資源需求 P1(0,0,1,2)(0,0,1,2)P2(2,0,0,0)(2,7,5,0)P3 (0,0,3,4)(6,6,5,6)P4(2,3,5,4)(4,3,5,6)P5(0,3,3,2)(0,6,5,2) 系統(tǒng)中當(dāng)前可用資源向量為(2,1,0,0).問(1)當(dāng)前系統(tǒng)是否安全?(2)如果進(jìn)程P3發(fā)出資源請求向量(0,1,0,0),系統(tǒng)能否將資源分配給它？看答案！

設(shè)有三道作業(yè),它們的提交時(shí)間和運(yùn)行時(shí)間如下表作業(yè)號提交時(shí)刻/時(shí)運(yùn)行時(shí)間/h110.002210.101310.250.25試給出在下面兩種調(diào)度算法下,作業(yè)的執(zhí)行順序,平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間.(1)先來先服務(wù)FCFS調(diào)度算法(2)短作業(yè)優(yōu)先SJF調(diào)度算法.看答案！給定一組作業(yè),假定它們同時(shí)到達(dá),并且在一臺處理機(jī)上按單道方式執(zhí)行.試證明:按最短作業(yè)優(yōu)先算法調(diào)度時(shí),其平均周轉(zhuǎn)時(shí)間最短.看答案！第四章

存儲器管理(章節(jié)圖)存儲器管理4.1

程序的裝入和鏈接4.2連續(xù)分配方式4.3基本分頁存儲管理方式4.4基本分段存儲管理方式4.5虛擬存儲器的基本概念習(xí)題4.6請求分頁存儲管理方式4.7頁面置換算法4.8請求分段存儲管理方式4.1

程序的裝入和鏈接4.1.1

程序的裝入:絕對裝入方式:使用絕對地址的裝入.可重定位裝入方式:采用相對地址的裝入.動態(tài)運(yùn)行時(shí)裝入方式:在把裝入模塊裝入內(nèi)存后并不立即把裝入模塊的相對地址轉(zhuǎn)化為絕對地址而把這個(gè)地址轉(zhuǎn)化過程推遲到真正執(zhí)行它是才進(jìn)行.4.1.2

程序的鏈接:靜態(tài)鏈接:程序運(yùn)行前先將各目標(biāo)模塊及所需的庫函數(shù)鏈接成一個(gè)完整的裝配模塊以后不再拆開.裝入時(shí)動態(tài)鏈接:將用戶源程序編譯后所得到的一組目標(biāo)模塊,在裝入內(nèi)存時(shí)采用邊裝入邊鏈接的方式.運(yùn)行時(shí)動態(tài)鏈接:對某目標(biāo)模塊的鏈接在程序執(zhí)行中需要該模塊時(shí)才對它進(jìn)行鏈接.4.2

連續(xù)分配方式4.2.1

單一連續(xù)分配:只把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分,僅供OS和用戶使用.4.2.2

固定分區(qū)分配:按規(guī)定的大小劃分分區(qū)大小,把分區(qū)一塊塊分給進(jìn)程.4.2.3

動態(tài)分區(qū)分配:根據(jù)進(jìn)程的實(shí)際需要動態(tài)地為之分配內(nèi)存空間.4.2.4

可重定位分區(qū)分配4.2.5

對換(Swapping):把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或暫時(shí)不用的程序和數(shù)據(jù)調(diào)到外存上,以便騰出足夠內(nèi)存空間再把已具備運(yùn)行條件的進(jìn)程或進(jìn)程需要的數(shù)據(jù)和程序調(diào)入內(nèi)存.4.2.3

動態(tài)分區(qū)分配分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu):系統(tǒng)中配置的相應(yīng)數(shù)據(jù)結(jié)構(gòu)用來描述空閑分區(qū)和已分配分區(qū)的情況為分配提供依據(jù)—空閑分區(qū)表;空閑分區(qū)鏈.分區(qū)分配算法首次適應(yīng)算法FF:分配內(nèi)存時(shí)從鏈?zhǔn)组_始順序查找,找到的第一個(gè)足夠大的空閑區(qū)就按作業(yè)大小劃分空間給該作業(yè),把該空閑區(qū)剩下的空間保留在空閑鏈中;若找不到合適空間就宣告分配失敗.循環(huán)首次適應(yīng)算法:FF的改進(jìn)版,每次查找不是從鏈?zhǔn)组_始而是從上次找到的空閑區(qū)的下一個(gè)空閑區(qū)開始.最佳適應(yīng)算法:每次分配時(shí)都把能滿足要求又是最小的空閑區(qū)分配給作業(yè).分區(qū)分配操作:分配內(nèi)存;回收內(nèi)存.4.2.4

可重定位分區(qū)分配動態(tài)重定位的引入:不同于連續(xù)分配方式下的把程序裝入一個(gè)連續(xù)內(nèi)存空間;而是把內(nèi)存中的零頭利用拼接的方法連接成一個(gè)足夠的空間分配給程序.動態(tài)重定位的實(shí)現(xiàn)動態(tài)重定位分區(qū)分配算法動態(tài)重定位的實(shí)現(xiàn)在動態(tài)運(yùn)行時(shí)裝入方式中,作業(yè)裝入內(nèi)存后的所有地址都是相對地址,只有當(dāng)程序指令要真正執(zhí)行時(shí)才把相對地址轉(zhuǎn)換為物理地址.為了使地址的轉(zhuǎn)換工作不影響到指令的執(zhí)行速度,必須要有硬件地址變換機(jī)構(gòu)—重定位寄存器的支持.0100LOAD1,2500…..2500365……5000…..1000010100LOAD1,2500….12500365……15000相對地址2500重定位寄存器10000作業(yè)J內(nèi)存CPU側(cè)存儲器側(cè)動態(tài)重定位分區(qū)分配算法請求分配u.size分區(qū)檢索空閑分區(qū)鏈(表)找到大于u.size的可用區(qū)否?按動態(tài)分區(qū)方式進(jìn)行分配修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)返回分區(qū)號及首批找到大于u.size的可用區(qū)否?按動態(tài)分區(qū)方式進(jìn)行分配修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)無法分配返回否否是4.2.5

對換(Swapping)對換的引入:為了提高內(nèi)存的利用率而把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或暫時(shí)不用的程序和數(shù)據(jù)調(diào)出到外存上,以便騰出足夠的內(nèi)存空間再把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需的程序和數(shù)據(jù)調(diào)入內(nèi)存.對換空間的管理:祥見課本P113進(jìn)程的換出與換入:祥見課本P1134.3

基本分頁存儲管理方式4.3.1

頁面與頁表4.3.2

地址變換機(jī)構(gòu)4.3.3

兩級和多級頁表4.3.1

頁面與頁表頁面頁面將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的片物理塊(頁框)把內(nèi)存空間分成與頁面相同大小的若干個(gè)存儲塊在為進(jìn)程分配內(nèi)存時(shí),以塊為單位將進(jìn)程中的若干個(gè)頁分別裝入到多個(gè)可以不相鄰接的物理塊中.頁內(nèi)碎片由于進(jìn)程的最后一頁經(jīng)常裝不滿一塊而形成了不可利用的碎片頁面的大小應(yīng)該適中且頁面大小應(yīng)是2的冪通常為512B—8KB.地址結(jié)構(gòu)3112110頁號P位移量W頁表:系統(tǒng)為每個(gè)進(jìn)程建立的一張頁面映像表,用來實(shí)現(xiàn)從頁號到物理號的地址映射.4.3.2

地址變換機(jī)構(gòu)基本的地址變換機(jī)構(gòu):頁表的功能本來可以用一組專門的寄存器實(shí)現(xiàn),但是考慮到成本太高所以我們用地址變換機(jī)構(gòu)完成頁面的訪問.具有快表的地址變換機(jī)構(gòu):快表就是在基本地址變換機(jī)構(gòu)的基礎(chǔ)上增設(shè)的一個(gè)具有并行查尋能力的特殊高速緩沖寄存器.基本的地址變換機(jī)構(gòu)頁表寄存器越界中斷邏輯地址L頁號塊號01123b頁表頁表始址頁表長度頁號(3)頁內(nèi)地址＞B頁內(nèi)地址物理地址具有快表的地址變換機(jī)構(gòu)頁號塊號b頁表頁號塊號b快表頁表寄存器越界中斷邏輯地址L頁表始址頁表長度頁號頁內(nèi)地址＞bd物理地址輸入寄存器4.3.3

兩級和多級頁表兩級頁表:在32位的機(jī)器中,為了解決用連續(xù)的內(nèi)存空間來存放頁表的問題,可以利用將頁表進(jìn)行分頁并離散地將各個(gè)頁面分別存放在不同的物理塊中的辦法來解決,同樣也要為離散分配的頁表再建立一張頁表叫做外層頁表.詳見P118圖4-14多級頁表:對于64位機(jī)器不適用兩級頁表所以引入多級頁表,在二級頁表的基礎(chǔ)上將外層頁表再進(jìn)行分頁,也就是將各分頁離散地裝入到不相鄰接的物理塊中,再利用第2級的外層頁表來映射它們之間的關(guān)系.詳見P118圖4-154.4

基本分段存儲管理方式4.4.1

分段存儲管理方式的引入:方便編程,信息共享,信息保護(hù),動態(tài)增長,動態(tài)鏈接.4.4.2

分段系統(tǒng)的基本原理4.4.3

信息共享4.4.4

段頁式存儲管理方式4.4.2

分段系統(tǒng)的基本原理分段:把作業(yè)的地址空間劃分為若干個(gè)段,每個(gè)段定義一組邏輯信息.段的長度有相應(yīng)的邏輯信息組的長度決定所以各段長度不等.段表:分段系統(tǒng)為每個(gè)段分配一個(gè)連續(xù)的分區(qū),而進(jìn)程中的各個(gè)段可以離散地移入內(nèi)存中不同的分區(qū)中.這樣我們就要在系統(tǒng)中為每個(gè)進(jìn)程建立一張段映射表—段表.每個(gè)段在表中占有一個(gè)表項(xiàng),其中記錄了該段在內(nèi)存中的起始地址和段的長度.地址變換機(jī)構(gòu):詳見P121圖4-16,圖4-17分頁和分段的主要區(qū)別:分頁和分段都采用離散分配方式,都通過地址映射機(jī)構(gòu)實(shí)現(xiàn)地址變換.分頁分段頁是信息的物理單位,分頁是由于系統(tǒng)管理的需要而不是用戶的需要.段是信息的邏輯單位,分段是為了更好的滿足用戶的需要.頁的大小固定而且由系統(tǒng)決定,由系統(tǒng)把邏輯地址劃分為頁號和頁內(nèi)地址兩部分,由機(jī)器硬件實(shí)現(xiàn),所以系統(tǒng)中只能有一種大小頁面.段的大小不固定,決定于用戶編寫的程序,通常由編譯程序在對源程序編譯時(shí)根據(jù)信息的性質(zhì)來劃分.作業(yè)地址空間是一維的,程序員只需利用一個(gè)記憶符就可表示一個(gè)地址.作業(yè)空間是二維的,程序員在標(biāo)識一個(gè)地址時(shí)要給出段名還要給出段內(nèi)地址.4.4.3

信息共享分段系統(tǒng)的一個(gè)突出優(yōu)點(diǎn)是易于實(shí)現(xiàn)段的共享,即允許若干個(gè)進(jìn)程共享一個(gè)或多個(gè)分段,且對段的保護(hù)也十分簡單易行,只需在每個(gè)進(jìn)程的段表中為文本編輯程序設(shè)置一個(gè)段表項(xiàng).這里要注意對進(jìn)程執(zhí)行安全性的保護(hù),也就是把可重入代碼或叫純代碼(允許多個(gè)進(jìn)程同時(shí)訪問的代碼)中的在執(zhí)行中需要被修改的代碼放到局部的數(shù)據(jù)區(qū),以保護(hù)整個(gè)可重入代碼的安全運(yùn)行.4.4.4

段頁式存儲管理方式段頁式的基本原理是分段和分頁原理的結(jié)合,即先將用戶程序分成若干個(gè)段,再把每個(gè)段分成若干個(gè)頁,并為每個(gè)段賦予一個(gè)段名.地址變換過程:顧名思義要經(jīng)過段表和頁表兩次的變換.詳見P124圖4-224.5

虛擬存儲器的基本概念4.5.1

虛擬存儲器的引入:常規(guī)存儲器管理存在一次性;駐留性的特征,這些特征使得許多在程序運(yùn)行中不