計算機操作系統(tǒng)課件1os3

第3章處理器管理一、系統(tǒng)的工作流程1.程序及其特點程序應具體兩個基本特點：順序性可再現(xiàn)性2.系統(tǒng)的工作流程順序執(zhí)行的工作方式及特征順序執(zhí)行指：處理器在開始執(zhí)行一道程序后，只有在這道程序運行結束(程序指令運行完成，或程序運行過程出現(xiàn)錯誤而無法繼續(xù)運行)，才能開始執(zhí)行下一道程序。這種工作流程的外在表現(xiàn)就是單任務。特征：封閉性可再現(xiàn)性

并發(fā)執(zhí)行的工作方式

并發(fā)執(zhí)行是指：在多道程序設計環(huán)境下，處理器在開始執(zhí)行一道程序的第1條指令后，在這道程序完成之前，處理器可以開始執(zhí)行下一道程序，同樣地，更多其他的程序也可以開始運行。

這種工作流程的外在表現(xiàn)就是多任務。3.并發(fā)執(zhí)行的理解宏觀：多道程序“同時”在運行，表現(xiàn)為多任務微觀：多道程序又是輪流交替地在處理器上執(zhí)行4.并發(fā)執(zhí)行的特征隨機性/不確定的：為操作系統(tǒng)管理提供可能不可再現(xiàn)性：程序丟失了可再現(xiàn)性相互制約

并發(fā)執(zhí)行可以發(fā)揮硬件的并行能力，為任務協(xié)作提供可能，但并發(fā)執(zhí)行具有復雜性：

例3-1

已知兩道程序PA和PB，它們對同一個變量count進行操作，PA程序每次運行時對變量count進行加1操作，而PB程序每次運行時對變量count進行減1操作。我們用C語言語法描述PA和PB程序如下：PA(){

intx;①

x=count;②x=x+1;③

count=x;}PB(){

inty;④y=count;⑤y=y-1;⑥count=y;}

可以假定：變量count為int類型，在count=100時PA()和PB()各運行一次，那么，在并發(fā)執(zhí)行方式下，它們運行后count的值是多少？①②③④⑤⑥執(zhí)行：count=100①④⑤⑥②③執(zhí)行：count=101④①②③⑤⑥執(zhí)行：count=99二、進程概念1.進程定義一道程序在一個數(shù)據(jù)集上的一次執(zhí)行過程，稱為一個進程(Process)2.進程的主要特征動態(tài)性并發(fā)性獨立性結構性異步性三、進程的動態(tài)性

1.進程的基本狀態(tài)運行(Running)

就緒(Ready)

阻塞(Blocked)2.進程的狀態(tài)轉換四、進程管理的主要功能1.進程控制塊PCB及組成2.PCB隊列3.進程管理的主要功能對處理器的管理轉化為對進程的管理控制同步通信調度死鎖

五、進程控制1.原子性(AllorNothing)2.原語(Primitive)3.進程控制的含義4.進程創(chuàng)建原語(Create)創(chuàng)建進程的時機創(chuàng)建原語的主要操作建立一個PCB生成pid初始化PCB各項內容(進程狀態(tài)為就緒狀態(tài))加入合適的就緒隊列進程樹

4.進程撤銷原語(Destroy)進程撤銷的時機撤銷原語的主要操作5.進程阻塞原語(Blocked)進程阻塞意義：減少CPU等待時間阻塞原語的主要操作6.進程喚醒原語(Wakeup)喚醒原語的主要操作從等待隊列中移出進程修改PCB的進程狀態(tài)為就緒狀態(tài)進程加入合適的就緒隊列在一個進程被喚醒時，它的阻塞狀態(tài)直接改為運行狀態(tài)，這種作法合理嗎？六、進程同步1.并發(fā)進程的制約關系(例1)

P1程序…打印第1行A1打印第2行A2…打印第n行An…P2程序…打印第1行B1打印第2行B2…打印第m行Bm…間接制約關系--資源共享引起直接制約關系--由任務協(xié)作引起的例22.間接制約與互斥關系資源的使用步驟臨界資源與間接制約臨界區(qū)與互斥關系

臨界區(qū)(CriticalSection，或CriticalRegion)是指進程對應的程序中訪問臨界資源的一段程序代碼，就是進程在資源的一次使用過程中，從申請開始至歸還為止的一段程序代碼。兩個或兩個以上的一組并發(fā)進程，稱它們具有互斥關系，是指這組進程至少共享一類臨界資源，當一個進程在臨界資源對應的臨界區(qū)內執(zhí)行時，其他要求進入相關臨界區(qū)執(zhí)行的進程必須等待。3.直接制約與同步關系在一組并發(fā)進程中，如果每個進程至少與同組中另一個進程存在單向或相互依賴關系，稱這組進程具有同步關系，簡稱同步進程4.進程同步機制常用的進程同步機制加鎖機制、標志位機制、信號量機制和管程機制臨界區(qū)管理準則空閑讓進忙則等待有限等待讓權等待5.互斥關系與加鎖機制

加鎖機制原理：鎖變量key、加鎖操作lock(key)和解鎖操作unlock(key)。lock(key){while(key==1);key=1;}unlock(key){ key=0;}規(guī)定key=0時表示對應的鎖是開的，允許進程進入對應的臨界區(qū)執(zhí)行；key=1表示應對的鎖是關的，禁止進程進入對應的臨界區(qū)加鎖機制應用假定p1、p2、…、pn是一組互斥關系的進程，對應的鎖變量為key，那么，加鎖機制的應用方法是： 置鎖變量初值key=0，對于進程pi，i=1,n，其加鎖機制的控制方法描述如下

… lock(key);

臨界區(qū); unlock(key); …加鎖機制分析普通的加鎖機制不能實現(xiàn)互斥關系

tsl: movax,1 xchgax,key cmp ax,0 jne tsl存在“忙等待”現(xiàn)象，浪費了處理器時間存在“饑餓”(Starvation)現(xiàn)象多個鎖變量的加鎖操作可能造成進程死鎖6.信號量機制與互斥關系信號量機制原理：信號量(semaphore)、p()和v()操作.structsemaphore{intvalue;PCB*bq;}p(s){ s.value=s.value–1;if(s.value＜0)blocked(s);}v(s){s.value=s.value+1;if(s.value≤0)wakeup(s);}p()和v()操作定義為原語，p()和v()操作的作用？信號量機制實現(xiàn)互斥關系

假定進程p1、p2、…、pn共享某一個臨界資源，定義一個信號量s，初值為1，那么，應用信號量機制實現(xiàn)p1、p2、…、pn互斥關系的模型如下：對于進程pi，i=1,n，其信號量機制的控制描述如下：

… p(s);

臨界區(qū); v(s); …7.信號量機制與同步關系

簡單同步關系一般同步關系并發(fā)程序設計

對于給定的一組進程，應用同步機制實現(xiàn)它們的并發(fā)執(zhí)行例3-4

兩個進程P1和P2共享一個緩沖區(qū)

buf，進程P1反復地計算，并把計算結果存入緩沖區(qū)buf，進程P2每次從緩沖區(qū)中取出計算結果并送向打印機。規(guī)定：P1把結果存入緩沖區(qū)buf后，P2才能打印，P1的一次計算的結果只能打印一次，只有在結果被打印后，P1新的計算結果才能存入緩沖區(qū)。試用信號量機制實現(xiàn)P1和P2的并發(fā)執(zhí)行。7.經典同步問題-生產者/消費者問題PC問題的描述PC問題的分類生產者進程數(shù)為n，消費者進程數(shù)為m，緩沖區(qū)容量為k簡單PC問題：n=1,m=1,k=1一般PC問題：n=1,m=1,k>1復雜PC問題：n>1,m>1,k>1特殊PC問題：其他，主要有n+m=3或4，k=1或者2；條件消費或重復消費等

在并發(fā)程序設計中，如果有兩個或多個連續(xù)的p操作，就必須認真分析，合理安排它們的執(zhí)行順序。7.經典同步問題-讀者/寫者問題問題描述

假設有一個寫者進程Writer和若干個讀者進程Reader，他們共享一組數(shù)據(jù)，寫者進程Writer對數(shù)據(jù)進行寫操作(如修改、刪除、添加等)，讀者進程Reader對數(shù)據(jù)進行讀操作，規(guī)定：

(1)寫操作與任一讀操作之間，必須互斥執(zhí)行；

(2)多個讀操作可以同時進行。如何用信號量機制實現(xiàn)他們的并發(fā)執(zhí)行？七、進程通信1.進程通信的概念什么是進程通信進程通信類型：低級通信高級通信：沒有特別說明，進程通信是指高級通信，即應用程序之間的數(shù)據(jù)交換為什么需要進程通信任務協(xié)作進程的獨立性進程通信的可行性

2.進程通信方式共享存儲區(qū)通信消息緩沖通信信箱通信管道通信3.消息緩沖通信的設計和實現(xiàn)基本思想設計消息緩沖區(qū)結構發(fā)送進程標識(pid)正文大小(size)正文(data)向下指針(Next)PCB的通信參數(shù)結構消息緩沖區(qū)隊列(mq)互斥信號量(mutex)同步信號量(msg)發(fā)送操作和接收操作send(dest，&mptr)receive(&mptr)實現(xiàn)-典型的簡單同步問題分析直接通信IPC3.信箱通信的設計和實現(xiàn)信箱結構信箱頭基本結構信箱名(boxname)信箱標識符(bid)信箱大小(size)同步信號量(mailnum)同步信號量(freenum)讀互信號量(rmutex)寫互信號量(wmutex)讀信件指針(out)存信件指針(in)信箱體結構由若干個信格組成，一個信格存放一個信件，要交換的數(shù)據(jù)組織成信件發(fā)送操作和接收操作send(dest，&mptr)receive(addr，&mptr)實現(xiàn)-復雜PC同步問題send(dest，&mptr){p(dest.freenum)；

p(dest.wmutex)；

dest.buf[dest.in]←mptr；

dest.in=(dest.in+1)%dest.size；

v(dest.wmutex)；

v(dest.mailnum)；

}receive(addr，&mptr){p(addr.mailnum)；

p(addr.rmutex)；

mptr←addr.buf[addr.out]；

addr.out=(addr.out+1)%addr.size；

v(addr.rmutex)；

v(addr.freenum)；}八、線程1.線程的引入什么是線程把進程細化成若干個可以獨立運行的實體，每一個實體稱為一個線程(Thread)引入線程的目的--引入線程可以減小系統(tǒng)的基本工作單位粒度實現(xiàn)進程內部的并發(fā)執(zhí)行，提高并行程度減少處理器切換