1、會計學1計算機操作系統進程和處理機管理計算機操作系統進程和處理機管理的調度方法；最后還要了解的調度方法；最后還要了解Windows XP的進程和線程管理。的進程和線程管理。第1頁/共83頁第第3章章 進程和處理機管理進程和處理機管理q 3.1 進程的基本概念進程的基本概念q 3.2 進程管理進程管理q 3.3 線程的概念線程的概念q 3.4 進程間的同步與互斥進程間的同步與互斥q 3.5進程通信進程通信q 3.6死鎖死鎖q 3.7處理機調度處理機調度q 3.8Windows XP的進程和線程管理的進程和線程管理第2頁/共83頁I1 作業作業1 作業作業2 .C1P1I2C2P2圖3-1 程序的

2、順序執行2. 2. 程序順序執行的特點程序順序執行的特點 (1)(1)順序性順序性 (2) (2)封閉性封閉性 (3) (3)可再現性可再現性第3頁/共83頁I2C2P2I3C3P3I4C4P4I1C1P1圖3-2 程序段并發執行第4頁/共83頁BCA圖3-3 并發進程間的通信第5頁/共83頁第6頁/共83頁第7頁/共83頁第8頁/共83頁第9頁/共83頁第10頁/共83頁圖圖3-4 進程基本狀態變遷進程基本狀態變遷條件發生條件發生進程調度進程調度等待條件發生等待條件發生就緒就緒等待等待執行執行第11頁/共83頁進程標識符進程當前狀態現場保護區程序和數據地址進程優先級資源清單進程通信信息互斥和

3、同步機構家族聯系鏈接字總鏈指針 表3-1 PCB信息 表3-1 PCB信息 第12頁/共83頁 表3-1 PCB信息 PCB12PCB23PCB34PCB413PCB56PCB67PCB79PCB8PCB910PCB10PCB1112PCB12iPCB13就緒指針執行指針等待指針空閑指針圖3-5 按鏈接方式組織PCB第13頁/共83頁就緒指針等待指針空閑指針1234135679101112PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9PCB10PCB11PCB12PCB13索 引 表圖3-6 按索引方式組織PCB第14頁/共83頁第15頁/共83頁算法：算法：crea

4、te輸入：新進程的符號名，優先級，開始執行地址輸入：新進程的符號名，優先級，開始執行地址輸出：新創建進程的內部標識符輸出：新創建進程的內部標識符PID在總鏈隊列上查找有無同名的進程；在總鏈隊列上查找有無同名的進程；if (有同名進程有同名進程) return （錯誤碼）（錯誤碼） /*帶錯誤碼返回帶錯誤碼返回*/在空閑在空閑PCB隊列申請一個空閑的隊列申請一個空閑的PCB結構；結構；if (無空無空PCB結構結構) return （錯誤碼）；（錯誤碼）； /*帶錯誤碼返回帶錯誤碼返回*/用參數填充用參數填充PCB內容；內容；置進程為就緒狀態；置進程為就緒狀態；將新進程的將新進程的PCB插入到就

5、緒隊列；插入到就緒隊列；將新進程的將新進程的PCB插入到總鏈隊列中；插入到總鏈隊列中；設置進程的家族關系；設置進程的家族關系；return （新進程（新進程PID）；）； /* create(name, priority, start-addr) */第16頁/共83頁void kill輸入：進程標識符輸入：進程標識符PID輸出：無輸出：無 由參數由參數PID查找到當前進程的查找到當前進程的PCB； 釋放本進程所占用的資源給父進程；釋放本進程所占用的資源給父進程； 將該進程從總鏈隊列中摘除；將該進程從總鏈隊列中摘除；釋放此釋放此PCB結構；結構；釋放所占用的資源；釋放所占用的資源；轉進程調度程

6、序；轉進程調度程序； /* kill */第17頁/共83頁void void suspsusp( (chanchan) )輸入：輸入：chanchan / /* *等待的事件（等待原因）等待的事件（等待原因）* */ / 保護現行進程保護現行進程CPUCPU現場到現場到PCBPCB結構中；結構中； 置該進程為置該進程為“等待等待/ /阻塞阻塞”態；態； 將該進程將該進程PCBPCB插入到等插入到等chanchan的等待隊列；的等待隊列； 轉進程調度；轉進程調度； / /* * suspsusp( (chanchan) ) * */ /第18頁/共83頁void wakeup(chan) 輸入

7、：輸入：chan /*等待的事件（等待原因）等待的事件（等待原因）*/輸出：無輸出：無 保護現行運行進程的保護現行運行進程的CPU現場到它的現場到它的PCB結構中；結構中； 置該進程為就緒狀態；置該進程為就緒狀態； 將該進程插入就緒隊列；將該進程插入就緒隊列； 找到該阻塞原因的隊列指針；找到該阻塞原因的隊列指針； for(該隊列上的每一個等待進程該隊列上的每一個等待進程) 將進程移出此等待隊列；將進程移出此等待隊列；置進程狀態為置進程狀態為“就緒就緒”并將進程放入就緒隊列；并將進程放入就緒隊列； 轉進程調度；轉進程調度； /* wakeup(chan) */第19頁/共83頁第20頁/共83頁

8、第21頁/共83頁第22頁/共83頁比較角度比較角度內核支持線程內核支持線程用戶級線程用戶級線程線程的調度與線程的調度與切換速度切換速度與進程的調度和切與進程的調度和切換十分相似換十分相似切換無須通過中斷進入操作切換無須通過中斷進入操作系統的內核，切換規則簡單系統的內核，切換規則簡單系統調用系統調用把系統調用只看作把系統調用只看作是該線程的行為是該線程的行為把系統調用看做是整個進程把系統調用看做是整個進程的行為的行為線程的執行時線程的執行時間間以進程為單位進以進程為單位進行行調度是以線程為單位進行的調度是以線程為單位進行的第23頁/共83頁第24頁/共83頁上鎖原語上鎖原語開鎖原語開鎖原語 v

9、oid lock(鎖變量鎖變量w) test: if(w為為1) goto test /*測試鎖位的值測試鎖位的值*/ else w=1; /*上鎖上鎖*/ /* lock(w) */ void unlock(鎖變量鎖變量w) w=0; /* 開鎖開鎖 */ /* unlock(w) */第25頁/共83頁改進后的上鎖原改進后的上鎖原語語改進后的開鎖原語改進后的開鎖原語void lock(鎖變量鎖變量) while(w=1) 保護現行進程保護現行進程CPU現場；現場； 現行進程入現行進程入w的等待隊列；的等待隊列； 置進程為置進程為“等待等待”狀態；狀態； 轉進程調度；轉進程調度； w=1;

10、/* 上鎖上鎖 */ /* lock(w) */void lock(鎖變量鎖變量) while(w=1) 保護現行進程保護現行進程CPU現場；現場； 現行進程入現行進程入w的等待隊列；的等待隊列； 置進程為置進程為“等待等待”狀態；狀態； 轉進程調度；轉進程調度； w=1; /* 上鎖上鎖 */ /* lock(w) */第26頁/共83頁進程A上鎖原語進入A的臨界區CSa開鎖原語進程B上鎖原語進入B的臨界區CSb開鎖原語圖3-7 進程使用臨界資源時的操作第27頁/共83頁main() int w=0;/系統初啟時置鎖狀態系統初啟時置鎖狀態cobeginppa();/進程進程Appb();/進

11、程進程Bcoendppa()/進程進程A ;lock(w);進程進程A的臨界區的臨界區CSa；unlock(w);ppb()/進程進程B ;lock(w);進程進程B的臨界區的臨界區CSb；unlock(w);第28頁/共83頁第29頁/共83頁第30頁/共83頁void p(變量變量s)/變量變量s為信號燈為信號燈 s-; if(s0) /進程進入相應的等待隊進程進入相應的等待隊列列保留調用進程保留調用進程CPU現場；現場； 將該進程進入將該進程進入s的等待隊列；的等待隊列； 置置“等待等待”狀態；狀態； 轉進程調度；轉進程調度； /* p(s) */1 1）P P操作過程操作過程void

12、v(變量變量s) /變量變量s為信號燈為信號燈 s+;if(s=0) 移出移出s等待隊列首元素；等待隊列首元素；將該進程入就緒隊列；將該進程入就緒隊列；置置“就緒就緒”狀態；狀態；/* v(s) */2 2）V V操作過程操作過程第31頁/共83頁第32頁/共83頁main()int mutex=1;/互斥信號燈互斥信號燈cobeginpa();/進程進程Apb();/進程進程Bcoendpa();/進程進程A;P(mutex)；進程進程A的臨界區的臨界區CSa;V(mutex)；;pb();/進程進程B;P(mutex)；進程進程B的臨界區的臨界區CSb;V(mutex)；;第33頁/共83

13、頁第34頁/共83頁第35頁/共83頁PaPcPbsfPcPbPasf緩沖區緩沖區buffcpiop圖圖3-9計算進程和打印進程之計算進程和打印進程之間的同步間的同步 (a) 進程同步例1(b) 進程同步例2圖圖3-8 進程合作例進程合作例子子3.4.4 進程同步進程同步 1. 1.進程同步概念進程同步概念 合作進程的兩種同步關系：合作進程的兩種同步關系：1 1）在執行次）在執行次序序上的同步；上的同步；2 2）共享緩沖的同步）共享緩沖的同步 第36頁/共83頁第37頁/共83頁main()int Sb=0; int Sc =0; cobeginPa ();Pb ();Pc ();coendP

14、a ()/進程進程 Pa ;V(Sb);V(Sc);Pb ()/進程進程 PbP(Sb);Pc ()/進程進程 PcP(Sc);main()int Sa=0; cobeginPa ();Pb ();Pc ();coendPa ()/進程進程 Pa ;V(Sa);V(Sa);Pb ()/進程進程 PbP(Sa);Pc ()/進程進程 PcP(Sa);第38頁/共83頁第39頁/共83頁mainint Sa =0;/緩沖中沒有數據緩沖中沒有數據int Sb =1;/緩沖中有空位置緩沖中有空位置cobegincp();iop();coendcp()/計算進程計算進程while (計算沒有完成計算沒有

15、完成) 計算一個結果數據；計算一個結果數據；P(Sb);將結果數據送到緩沖區；將結果數據送到緩沖區；V(Sa);iop()/打印進程打印進程while (打印工作沒有完成打印工作沒有完成) P(Sa);將結果數據從緩沖區中取出；將結果數據從緩沖區中取出；V(Sb);在打印機上輸出；在打印機上輸出；第40頁/共83頁c1c2ckp1p2pm圖圖3-10 生產者生產者消費者問題消費者問題緩沖區緩沖區第41頁/共83頁main()full=0； /緩沖區中存放的產品數量緩沖區中存放的產品數量empty=n； /緩沖區空位置的數量緩沖區空位置的數量 mutex=1； /對有界緩沖區進行操作的互斥信號燈

16、對有界緩沖區進行操作的互斥信號燈cobeginProducer ()；Consumer()；coendProducer () while(生產未完成生產未完成) 生產一個產品；生產一個產品； P(empty)；P(mutex)； 送一個產品到有界緩沖區；送一個產品到有界緩沖區； V(mutex)；V(full)； Consumer() while(還要繼續消費還要繼續消費) P(full)；P(mutex)；從有界緩沖區中取產品；從有界緩沖區中取產品；V(mutex)；V(empty)； 消費一個產品；消費一個產品；第42頁/共83頁第43頁/共83頁main()int Rcount=0;in

17、t Rmutex=1;int Wmutex=1;cobeginreader();writer();coendreader()/讀者進程讀者進程while (1)P(Rmutex);if (Rcount=0) P(Wmutex);Rcount+;V(Rmutex);完成讀操作完成讀操作;P(Rmutex);Rcount-;if (Rcount=0) V(Wmutex); V(Rmutex);writer()/寫者進程寫者進程while (1) P(W mutex);完成寫操作；完成寫操作；V(Wmutex);第44頁/共83頁第45頁/共83頁發送進程發送進程接收進程接收進程信箱頭信箱頭信箱信箱

18、1信箱信箱2圖圖3-11 間接通信方式間接通信方式 3) 3) 利用共享文件（管道）的通信方式利用共享文件（管道）的通信方式 發送進程發送進程接收進程接收進程圖圖3-12 利用共享文件（管道）通信利用共享文件（管道）通信第46頁/共83頁發送進程發送進程 id=5接收進程接收進程 id=5send(m);id: 6size: 5text: hello接收進程接收進程pcb中的中的hptrSptr: 4Nptr:Size: 3Text: byeSptr: 5Nptr: nullSize: 5Text: helloreceive(n, sid);id: 4size:3text:bye發送進程地址空

19、間發送進程地址空間接收進程地址空間接收進程地址空間圖圖3-13 消息緩沖通信消息緩沖通信第47頁/共83頁void send(發送區首址發送區首址m) 從發送區從發送區id域得接收進程域得接收進程id號；號； 以此以此id號得接收進程號得接收進程pcb的消息隊列頭；的消息隊列頭； 從發送區從發送區size域得緩沖區大小；域得緩沖區大小； 申請一個消息緩沖區申請一個消息緩沖區area； /建立新的消息緩沖區建立新的消息緩沖區 以此大小加上緩沖區頭得以此大小加上緩沖區頭得area； 發送進程發送進程id送送area的的sptr域；域； 緩沖區大小送緩沖區大小送area的的size域；域； 發送區的

20、發送區的text送送area的的text域；域； 置置area的勾鏈字為鏈尾標記；的勾鏈字為鏈尾標記； p(mutex); /封鎖消息隊列封鎖消息隊列 將將area入消息隊列；入消息隊列； v(mutex); /解鎖消息隊列解鎖消息隊列 v(Si); /與接收進程同步與接收進程同步第48頁/共83頁void receive(接收區首址接收區首址n，發送進程號，發送進程號)p(Si); /有無消息可取有無消息可取p(mutex); /封鎖消息隊列封鎖消息隊列在消息隊列找到發送者為在消息隊列找到發送者為sid的消息；的消息；從消息隊列中摘下此消息緩沖區從消息隊列中摘下此消息緩沖區area;v(mu

21、tex); /解鎖消息隊列解鎖消息隊列area的的sptr送接收區的送接收區的id域；域；/將消息緩沖區的信息復制到接收區將消息緩沖區的信息復制到接收區 area的的size送接收區的送接收區的size域；域；area的的text送接收區的送接收區的text域；域；釋放釋放area給存貯管理模塊；給存貯管理模塊；第49頁/共83頁R1R2P1P2圖圖3-14 I/O設備共享時的死鎖設備共享時的死鎖圖圖3-15 進程之間通信時的死鎖進程之間通信時的死鎖S1S3P1P2P3S2第50頁/共83頁第51頁/共83頁第52頁/共83頁第53頁/共83頁第54頁/共83頁第55頁/共83頁第56頁/共8

22、3頁第57頁/共83頁第58頁/共83頁第59頁/共83頁第60頁/共83頁 圖圖3-16 3-16 執行過程執行過程1 1圖圖3-17 3-17 執行過程執行過程2 2FCFSFCFS調度算調度算法法其他調度算法其他調度算法第61頁/共83頁ATTATT0 1 2 3 4 5 6 7 q圖圖3-18 平均周轉時間平均周轉時間ATT與時間片與時間片q之間的關系之間的關系第62頁/共83頁 第63頁/共83頁第64頁/共83頁第65頁/共83頁第66頁/共83頁第67頁/共83頁第68頁/共83頁圖3-20 Windows XP的進程對象進程進程ID安全描述符基本優先級默認處理器集合定額限制執行

23、時間I/O計數器VM操作計數器異常/調試端口退出狀態創建進程打開進程查詢進程信息設置進程信息當前進程終止進程對象類型對象體屬性服務圖3-21 Windows XP的進程TDB私有堆棧 鏈接指針狀態標志（事件計數）優先級 第69頁/共83頁屬 性 名 稱屬 性 含 義進程ID進程的惟一標識安全描述符描述誰創建對象、誰可以訪問/使用對象或禁止誰訪問對象基本優先級進程中線程的基本優先級默認處理器集合可以運行的進程中線程的默認處理器集合定額限制頁式存儲器及頁式文件空間，進程可使用的處理器最大時間執行時間進程中的所有線程已經執行的時間總量I/O計數器記載進程中線程已執行的I/O操作數量、類型的變量VM操

24、作計數器記載進程中線程已執行的虛擬存儲操作數量、類型的變量異常/調試端口進程中的線程異常時，用于進程管理器發送消息的通信信道退出狀態進程終止的原因表3-2 Windows XP進程對象的屬性第70頁/共83頁線程線程ID動態優先級基本優先級線程處理器集合線程執行警告狀態掛起計數器假冒標志終止端口線程退出狀態創建線程打開線程查詢線程信息當前線程終止線程獲取上下文設置上下文掛起恢復警告線程測試線程警告寄存器終止端口對象類型對象屬性服務圖3-22Windows XP線程對象第71頁/共83頁屬 性 名 稱屬 性 含 義線程ID 當線程調用一個服務程序時，標識該線程的惟一值線程上下文 定義線程執行狀態的一組寄存器值和其他易失的數據動態優先級 任何給定時刻，線程執行優先級基本優先級 線程動態優先級的下限線程處理器集合 可以運行的線程的處理器集合