操作系統(tǒng)原理課件

操作系統(tǒng)概述

1.1操作系統(tǒng)的地位計算機(jī)系統(tǒng)由硬件和軟件組成操作系統(tǒng)在硬件基礎(chǔ)上的第一層軟件是其它軟件和硬件的接口1.2操作系統(tǒng)的定義操作系統(tǒng)是計算機(jī)系統(tǒng)中的一個系統(tǒng)軟件，是一些程序模塊的集合——

它們能以盡量有效合理方式組織和管理計算機(jī)的軟硬件資源，合理的組織計算機(jī)的工作流程，控制程序的執(zhí)行并向用戶提供各種服務(wù)功能，使得用戶能夠靈活，方便，有效的使用計算機(jī)，使整個計算機(jī)系統(tǒng)能高效的運行。有效：系統(tǒng)效率 （如CPU用的充足與否） 資源利用率

（如內(nèi)存，外部設(shè)備是否忙碌）合理： 公平與否，如果不公平則回產(chǎn)生“死鎖”或“饑餓”。方便： 用戶界面1.3操作系統(tǒng)的特征并發(fā)：在計算機(jī)系統(tǒng)中同時存在多個程序，從宏觀上看這些程序是同時在執(zhí)行的。從微觀上講任何時刻只有一個程序在執(zhí)行，微觀上說這些程序在CPU上輪流執(zhí)行。并行：(與并發(fā)相同，但多指硬件支持）共享：

操作系統(tǒng)與多個用戶的程序共同使用計算機(jī)上的資源。操作系統(tǒng)特征1.4操作系統(tǒng)的發(fā)展操作系統(tǒng)發(fā)展是隨著計算機(jī)硬件技術(shù)的發(fā)展而發(fā)展的目標(biāo)：充分利用硬件操作系統(tǒng)歷史劃分為4個階段第0階段硬件非常昂貴，沒有操作系統(tǒng)

控制臺一個用戶一次完成一個功能（計算，I/O，用戶思考/反應(yīng)程序通過卡片裝入用戶在控制臺前調(diào)試程序工作效率非常低每一用戶都要自行編寫涉及到硬件的源代碼。

工作量大，難度高，易出錯需要大量人力和物力。第1階段硬件昂貴，人力便宜

簡單批處理：裝入程序、運行、打印結(jié)果、撤出、再重復(fù)用戶把程序（卡片或磁帶）交給負(fù)責(zé)調(diào)度的操作員（系統(tǒng)管理員）常駐監(jiān)控程序自動地裝入程序、運行、撤出作業(yè)需要存儲管理、重定位和保護(hù)機(jī)制硬件使用較為高效，但（從輸出）調(diào)試?yán)щyCPU與I/O操作交叉覆蓋后期：Spool

數(shù)據(jù)到磁盤上早期：將慢速設(shè)備轉(zhuǎn)到同CPU相連的快速磁帶驅(qū)動器上增加：緩沖,DMA,中斷處理作業(yè)被送（spool）到磁盤仍然是單個作業(yè)，利用率低

多道程序批處理系統(tǒng)在磁盤上多個作業(yè)等待運行多道程序

-同時運行多個作業(yè)-選擇若干作業(yè)準(zhǔn)備運行（調(diào)度）并裝入內(nèi)存（存儲管理）-運行一個作業(yè)，當(dāng)它等待時（如需安裝磁帶，等鍵按下），切換至內(nèi)存中的另一個作業(yè)多道程序設(shè)計：多個用戶共享系統(tǒng)增加：存儲保護(hù)，重定位利用率高（多個作業(yè)）有必要采用并發(fā)程序設(shè)計技術(shù)操作系統(tǒng)成為研究焦點：需要處理復(fù)雜性首次面對重大失?。?MULTICS于1963年開始，直至1969年才發(fā)布-IBM的OS/360發(fā)布時，帶著已知的1000個錯誤早期計算機(jī)：單控制方式-CPU負(fù)責(zé)計算，也負(fù)責(zé)傳輸早期計算機(jī)的使用方式-一個用戶獨占全部資源-浪費：CPU與外設(shè)速度不匹配手工操作方式和高速機(jī)器之間的不匹配提高資源利用率-多部件并行，多任務(wù)共享

通道引入：傳輸和CPU相對獨立中斷引入：各部件的協(xié)調(diào)動作成為可能

體系結(jié)構(gòu)的發(fā)展可以支持OS

多道程序運行模式第2階段硬件較以前便宜，人力昂貴

交互式分時處理一臺計算機(jī)，多個便宜終端-所有用戶可與系統(tǒng)立即交互-調(diào)試比較方便磁盤便宜，故可在線存放程序和數(shù)據(jù)-1張穿孔卡片=100個字節(jié)-1MB=10K卡片-OS/360有若干英尺長度的卡片新問題-易于使用，提高人的生產(chǎn)力-合理的響應(yīng)時間-引入文件系統(tǒng)，使用戶可存取數(shù)據(jù)

解決-需要搶占式調(diào)度以便保持適當(dāng)?shù)捻憫?yīng)時間-需要避免抖動（程序在內(nèi)存中過于頻繁的對換）-需要提供適用的安全檢測成功：

一群計算機(jī)迷(Tomson,Ritchie)在貝爾實驗室發(fā)展出了UNIX。（這樣他們可以在一臺無人使用的DECPDP-7小型計算機(jī)上玩星際探險游戲）成功：KenThompson，DennisRitchie1983年圖靈獎獲得者1999年4月美國國家技術(shù)金獎第3階段硬件非常便宜，人力昂貴目標(biāo)：

充分利用人和時間個人計算CPU便宜到可在每臺終端上安裝，功能強(qiáng)大有效-成為大眾的計算機(jī)放棄多道程序、并發(fā)和保護(hù)機(jī)制，使OS回歸簡單使用戶再次與系統(tǒng)交互增強(qiáng)文件系統(tǒng)響應(yīng)時間、保護(hù)成更為重要網(wǎng)絡(luò)允許不同機(jī)器很容易共享資源-共享，安全操作系統(tǒng)的歷史:

變化!意味著技術(shù)總在改變要適應(yīng)、折衷權(quán)衡1.4.3操作系統(tǒng)的分類批處理操作系統(tǒng)（多道批處理）分時操作系統(tǒng)實時操作系統(tǒng)個人計算機(jī)操作系統(tǒng)網(wǎng)絡(luò)操作系統(tǒng)分布式操作系統(tǒng)

批處理操作系統(tǒng)工作方式：用戶將作業(yè)交給系統(tǒng)操作員系統(tǒng)操作員將許多用戶的作業(yè)組成一批作業(yè)之后輸入到計算機(jī)中，在系統(tǒng)中形成一個自動轉(zhuǎn)接的連續(xù)的作業(yè)流啟動操作系統(tǒng)系統(tǒng)自動、依次執(zhí)行每個作業(yè)最后由操作員將作業(yè)結(jié)果交給用戶卡片早期批處理系統(tǒng)IBM1401IBM7094IBM1401輸入磁帶磁帶機(jī)卡片閱讀機(jī)輸出磁帶打印機(jī)$END$RUNDataforprogram$LOADFortranprogram$FORTRAN

$JOB,10,429754

CherryChen

典型的FMSJOB結(jié)構(gòu)批處理操作系統(tǒng)

特點：多道：（注：多道指某個作業(yè)占用CPU，若由于某種原因暫時不用CPU則系統(tǒng)讓第二個作業(yè)占用CPU）成批處理：批處理操作系統(tǒng)特點成批處理：用戶自己不能干預(yù)自己作業(yè)的運行，一旦發(fā)現(xiàn)作業(yè)錯誤不能及時改正，并延長開發(fā)軟件時間，所以適用于成熟的程序。Spooling系統(tǒng)（技術(shù)）1961年，英國曼徹斯特大學(xué)，Atalas機(jī)SimultaneousPeripheralOperationOn-Line同時的外圍設(shè)備聯(lián)機(jī)操作--假脫機(jī)技術(shù)利用磁盤作緩沖，將輸入、計算、輸出分別組織成獨立的任務(wù)流，使I/O和計算真正并行Spooling系統(tǒng)工作原理-作業(yè)進(jìn)入到磁盤上的輸入井-按某種調(diào)度策略選擇幾種搭配得當(dāng)?shù)淖鳂I(yè)，并調(diào)入內(nèi)存-作業(yè)運行的結(jié)果輸出到磁盤上的輸出井-再由磁盤上的輸出井將結(jié)果送到打印機(jī)批處理操作系統(tǒng)-優(yōu)點：作業(yè)流程自動化效率高，吞吐率高吞吐量：單位時間內(nèi)處理作業(yè)的個數(shù)-缺點：無交互手段，調(diào)試程序困難

分時操作系統(tǒng)工作方式:一臺主機(jī)連接了若干個終端每個終端有一個用戶在使用交互式的向系統(tǒng)提出命令請求系統(tǒng)接受每個用戶的命令采用時間片輪轉(zhuǎn)方式處理服務(wù)請求并通過交互方式在終端上向用戶顯示結(jié)果用戶根據(jù)上步結(jié)果發(fā)出下道命令主機(jī)終端

分時操作系統(tǒng)時間片：操作系統(tǒng)將CPU的時間劃分成若干個片段,稱為時間片.操作系統(tǒng)以時間片為單位,輪流為每個終端用戶服務(wù),每次服務(wù)一個時間片.(其特點是利用人的錯覺,使人感覺不到.)分時操作系統(tǒng)特點多路性交互性“獨占”性及時性分時操作系統(tǒng)多路性：同時有多個用戶使用一臺計算機(jī)宏觀上看是多個人同時使用一個CPU微觀上是多個人在不同時刻輪流使用CPU分時操作系統(tǒng)交互性：用戶根據(jù)系統(tǒng)響應(yīng)結(jié)果進(jìn)一步提出新請求(用戶直接干預(yù)每一步)分時操作系統(tǒng)“獨占”性：用戶感覺不到計算機(jī)為其他人服務(wù)（OS提供虛機(jī)器，各個用戶的虛機(jī)器互不干擾）及時性系統(tǒng)對用戶提出的請求及時響應(yīng)。分時操作系統(tǒng)實現(xiàn)（條件）：終端設(shè)備輪轉(zhuǎn)算法會話語言一般資源獨占，“滾進(jìn)滾出”方法分時操作系統(tǒng)追求目標(biāo)：及時響應(yīng)

(根據(jù)指標(biāo)是響應(yīng)時間)響應(yīng)時間：從終端發(fā)出命令到系統(tǒng)給予回答所經(jīng)歷的時間分時操作系統(tǒng)影響響應(yīng)時間的因素：

-機(jī)器處理能力

-請求服務(wù)的時間長短

-系統(tǒng)中連接的終端數(shù)目

-服務(wù)請求的分布

-調(diào)度算法（時間片的選?。┩ㄓ貌僮飨到y(tǒng)分時系統(tǒng)與批處理系統(tǒng)結(jié)合原則：分時優(yōu)先，批處理在后“前臺”：需頻繁交互的作業(yè)“后臺”：時間性要求不強(qiáng)的作業(yè)

實時操作系統(tǒng)分類：第一類：實時過程控制工業(yè)控制，軍事控制，...第二類：實時通信（信息）處理電訊（自動交換），銀行，飛機(jī)訂票實時操作系統(tǒng)主要追求目標(biāo)：對外部請求在嚴(yán)格時間范圍內(nèi)作出反應(yīng)有高可靠性完整性實時系統(tǒng)必須和先進(jìn)的技術(shù)裝備相結(jié)合

個人計算機(jī)操作系統(tǒng)

(單用戶多任務(wù))計算機(jī)在某一時間內(nèi)為單用戶服務(wù),其追求目標(biāo)是界面友好,使用方便.

網(wǎng)絡(luò)操作系統(tǒng)它是基于計算機(jī)網(wǎng)絡(luò)的,是在各種計算機(jī)操作系統(tǒng)上,按網(wǎng)絡(luò)體系結(jié)構(gòu)協(xié)議標(biāo)準(zhǔn)開發(fā)的軟件,包括網(wǎng)絡(luò)管理,通訊,安全,資源共享和各種網(wǎng)絡(luò)應(yīng)用。其目標(biāo)是相互通訊及資源共享。網(wǎng)絡(luò)操作系統(tǒng)網(wǎng)絡(luò)服務(wù)應(yīng)用程序

通信軟件（協(xié)議支持）單機(jī)操作系統(tǒng)用戶應(yīng)用程序局域網(wǎng)操作系統(tǒng)的結(jié)構(gòu)

通信軟件（協(xié)議支持）

分布式操作系統(tǒng)它基于兩種環(huán)境:多機(jī)(CPU)系統(tǒng)或網(wǎng)絡(luò)是網(wǎng)絡(luò)操作系統(tǒng)的更高級的形式,它保持了網(wǎng)絡(luò)操作系統(tǒng)的全部功能分布式操作系統(tǒng):特征:1.是一個統(tǒng)一的操作系統(tǒng)2.資源進(jìn)一步共享3.透明性:

資源共享,分布.用戶并不知道,對用戶來講是透明的.4.自治性:

處于分布式系統(tǒng)的多個主機(jī)處于平等地位

網(wǎng)絡(luò)和分布式的區(qū)別:(1)分布具有各個計算機(jī)間相互通訊,

無主從關(guān)系;網(wǎng)絡(luò)有主從關(guān)系

(2)分布式系統(tǒng)資源為所有用戶共享;而網(wǎng)絡(luò)有限制地共享

(3)分布式系統(tǒng)中若干個計算機(jī)可相互協(xié)作共同完成一項任務(wù)1.5研究操作系統(tǒng)的幾種觀點作為軟件來看的觀點資源管理的觀點進(jìn)程的觀點虛機(jī)器觀點1.5.1作為軟件來看的觀點軟件的特性外在特性： 軟件是種語言,是界面 界面:使用方式（命令,系統(tǒng)調(diào)用等)內(nèi)在特性： 軟件的結(jié)構(gòu)

a.由有幾部分組成

b.每個部分的功能

c.部分之間的關(guān)系1.5.2資源管理的觀點操作系統(tǒng)---資源管理者硬件資源：CPU,內(nèi)存,外部設(shè)備(I/O設(shè)備，外存，時鐘等)軟件資源：硬盤上的文件,信息.管理資源記錄資源狀況如哪些資源空閑,好壞與否,被誰使用,使用多長時間等合理的分配資源：靜態(tài)分配策略(在程序運行前分配,但效率不高)動態(tài)分配策略(在程序運行過程中何時用資源,何時分配.其缺點時會出現(xiàn)死鎖)具體執(zhí)行分配回收資源資源管理的目的實現(xiàn)資源共享提高資源利用率1.5.3進(jìn)程的觀點是從操作系統(tǒng)運行時動態(tài)的觀察操作系統(tǒng),從這個觀點來看：操作系統(tǒng)是由某個可同時獨立運行的進(jìn)程和一個對這些進(jìn)程進(jìn)行協(xié)調(diào)的核心組成.進(jìn)程：某一特定功能的程序它是程序的一次執(zhí)行過程它是有生命的,當(dāng)它執(zhí)行時存在,否則消失.1.5.4虛機(jī)器觀點從操作系統(tǒng)內(nèi)部結(jié)構(gòu)來看：把操作系統(tǒng)分成若干層每個層完成其特定功從而構(gòu)成一個虛機(jī)器.并對上一層提供支持通過逐層功能擴(kuò)充,最終完成整個操作系統(tǒng)虛機(jī)器而操作系統(tǒng)虛機(jī)器向用戶提供完全功能,完成用戶請求1.5.5提供服務(wù)在操作系統(tǒng)之外從用戶角度來看：操作系統(tǒng)為用戶提供一組功能強(qiáng)大的、方便易用的命令或系統(tǒng)調(diào)用1.6操作系統(tǒng)功能CPU(進(jìn)程)管理存儲管理文件管理設(shè)備管理作業(yè)管理操作系統(tǒng)的硬件環(huán)境 操作系統(tǒng)在硬件之上,軟件之下,直接與硬件打交道CPU中斷系統(tǒng)堆棧:通道地址映射機(jī)制存儲保護(hù)設(shè)施CPUCPU狀態(tài)：CPU狀態(tài)的轉(zhuǎn)換CPU指令系統(tǒng)兩類指令..特權(quán)指令：允許操作系統(tǒng)使用,不允許一般用戶使用(如修改程序狀態(tài)字;設(shè)置中斷屏蔽：啟動I/O設(shè)備;清內(nèi)存;設(shè)置時鐘等).非特權(quán)指令：用戶均可用的CPU狀態(tài)：在PSW中專門設(shè)置一位,它是根據(jù)運行程序使用指令權(quán)限而設(shè)置.管態(tài)(特態(tài))：能執(zhí)行指令全集(包括特權(quán)，非特權(quán)指令),具有改變CPU狀態(tài)的能力,操作系統(tǒng)在管態(tài)下運行.目態(tài)(普態(tài))：只能執(zhí)行非特權(quán)指令,用戶程序在目態(tài)下運行.(如果在目態(tài)下用戶執(zhí)行了特態(tài)指令,則產(chǎn)生中斷,由操作系統(tǒng)得到控制權(quán),而特權(quán)指令被停止.)（這兩種狀態(tài)時可轉(zhuǎn)換的）CPU狀態(tài)的轉(zhuǎn)換目態(tài)--管態(tài)其轉(zhuǎn)換的唯一途徑是通過中斷.管態(tài)--目態(tài)可用設(shè)置PSW(修改程序狀態(tài)字)可實現(xiàn).中斷特點:中斷系統(tǒng)的概念中斷源中斷類型中斷響應(yīng)中斷處理中斷優(yōu)先級中斷屏蔽中斷嵌套中斷概述：中斷是現(xiàn)代計算機(jī)系統(tǒng)中基本設(shè)施之一,它起著通訊聯(lián)絡(luò)作用,協(xié)調(diào)系統(tǒng)對各種外部事件的響應(yīng)和處理.中斷是實現(xiàn)多道程序的必要條件.引入中斷的目的解決主機(jī)與外設(shè)的并行工作問題提高可靠性實現(xiàn)多機(jī)聯(lián)系實現(xiàn)實時控制中斷定義：CPU對系統(tǒng)發(fā)生的某個事件作出的一種反應(yīng):CPU暫停正在執(zhí)行的程序,保留現(xiàn)場后自動轉(zhuǎn)去進(jìn)行相應(yīng)事件的處理程序,處理完成后返回斷點,繼續(xù)執(zhí)行被打斷的程序.特點:1)中斷隨機(jī)的

2)中斷是可恢復(fù)的

3)中斷是自動處理的中斷系統(tǒng)的概念中斷由軟硬件協(xié)同處理中斷裝置：指發(fā)現(xiàn)中斷,響應(yīng)中斷的硬件

中斷處理程序：是由軟件來完成的中斷系統(tǒng)=中斷裝置+中斷處理程序中斷源：引起中斷發(fā)生的事件中斷寄存器：記錄中斷中斷字：中斷寄存器的內(nèi)容系統(tǒng)堆棧:

在內(nèi)存開辟的一塊區(qū)域，用于臨時保存現(xiàn)場中斷類型強(qiáng)迫性中斷輸入/輸出(I/O)中斷：主要來自外部設(shè)備通道程序性中斷：運行程序中本身的中斷(如溢出,缺頁中斷,缺段中斷,地址越界)時鐘中斷：控制臺中斷：硬件故障：自愿性中斷中斷類型強(qiáng)迫性中斷

正在運行的程序所不期望的，由于某種硬件故障或外部請求引起的。自愿性中斷用戶在程序中有意識安排的中斷,是由于用戶在編制程序時因為要求操作系統(tǒng)提供服務(wù)，有意使用“訪管”指令或系統(tǒng)調(diào)用,使中斷發(fā)生。中斷響應(yīng):

發(fā)現(xiàn)中斷、接收中斷的過程

（硬件完成）*發(fā)現(xiàn)中斷源(識別中斷原因)*保存現(xiàn)場,將中斷向量推入系統(tǒng)堆棧*引出中斷處理程序中斷響應(yīng)具體做法:CPU在執(zhí)行每條指令后掃描中斷寄存器，查看有無中斷請求。如果沒有，則運行下一條指令；如果有中斷請求，則通過交換中斷向量引出（進(jìn)入）中斷處理程序.程序狀態(tài)字指令計數(shù)器

系統(tǒng)堆棧PSW1PC1PSW2PC2PSW3PC3PSW4PC4PSW5PC5PC1PC2PC3中斷處理*保存現(xiàn)場(保存未被硬件保存的現(xiàn)場)*識別中斷具體原因*根據(jù)中斷原因處理中斷事件*中斷返回強(qiáng)迫性中斷事件自愿性中斷事件保存現(xiàn)場信息保存現(xiàn)場信息取出中斷碼取出訪管號分析中斷原因分析何種系統(tǒng)調(diào)用轉(zhuǎn)相應(yīng)處理程序是否中斷嵌套由系統(tǒng)恢復(fù)現(xiàn)場由系統(tǒng)恢復(fù)現(xiàn)場轉(zhuǎn)低級調(diào)度程序返回上層中斷返回目態(tài)程序需要切換進(jìn)程TFFT輸入輸出中斷處理1、I/O正常結(jié)束 如果要繼續(xù)傳輸，準(zhǔn)備好數(shù)據(jù)，啟動通道 如果有進(jìn)程等待I/O結(jié)束，將其喚醒2、I/O傳輸錯誤 進(jìn)行I/O復(fù)執(zhí)，多次不成功，通知系統(tǒng)操作員 設(shè)備故障時鐘中斷處理進(jìn)行系統(tǒng)管理及維護(hù)有關(guān)的工作：1、進(jìn)程管理2、作業(yè)管理3、資源管理4、事件處理5、系統(tǒng)維護(hù)6、實現(xiàn)軟件時鐘控制臺中斷處理系統(tǒng)操作員利用控制臺向系統(tǒng)發(fā)出中斷請求： 按下控制臺上某一個按紐，產(chǎn)生一個中斷信號（相當(dāng)于一個操作命令），操作系統(tǒng)轉(zhuǎn)到相應(yīng)的處理程序（與具體系統(tǒng)有關(guān)）。硬件故障中斷處理 主要工作是保存現(xiàn)場，并向系統(tǒng)操作員報告故障信息，以及估計對系統(tǒng)造成的破壞，對系統(tǒng)進(jìn)行可能的恢復(fù)。 排除故障必須有人工干預(yù)。1、電源故障處理2、主存故障處理 內(nèi)存校驗線路發(fā)現(xiàn)奇偶校驗錯誤或海明校驗錯誤而引起的中斷，停止相關(guān)進(jìn)程的執(zhí)行，向系統(tǒng)操作員報告錯誤及單元號程序性中斷處理兩種策略：1、由系統(tǒng)處理 該中斷事件可能影響其它進(jìn)程或操作系統(tǒng) （內(nèi)存訪問地址越界，執(zhí)行非法特權(quán)指令， 缺頁，缺段等）

*報告出錯的進(jìn)程號、出錯位置和錯誤性質(zhì)

*調(diào)入段或頁2、由用戶處理 該中斷事件只影響其自身

(浮點溢出、階碼下溢、除數(shù)為零等） 如果用戶程序不提供特定的處理程序，操作系統(tǒng)將按照標(biāo)準(zhǔn)處理方法進(jìn)行處理

on<中斷條件><中斷續(xù)元入口>

例：ondevide_zerogotoLA;

運行前，編譯系統(tǒng)為每個用戶生成一個中斷續(xù)元入口表，規(guī)定好每個中斷事件對應(yīng)的表目中斷事件0：中斷續(xù)元運行環(huán)境0中斷續(xù)元入口0中斷事件1：中斷續(xù)元運行環(huán)境1中斷續(xù)元入口1中斷事件2：中斷續(xù)元運行環(huán)境2中斷續(xù)元入口2………...中斷事件m中斷續(xù)元運行環(huán)境m中斷續(xù)元入口m自愿性中斷處理訪管指令：SVCn

SVC：指令碼n：訪管中斷號（整數(shù)）中斷發(fā)生時，硬件中斷裝置將訪管中斷號送入老的程序狀態(tài)字中的內(nèi)中斷碼字段，訪管中斷總控程序從系統(tǒng)堆棧中將其取出，并根據(jù)它轉(zhuǎn)入對應(yīng)的服務(wù)程序。自愿性中斷處理用戶使用訪管指令的一般形式為： 準(zhǔn)備參數(shù) SVCn

取返回值根據(jù)具體訪管要求約定，參數(shù)及返回值可以通過寄存器或內(nèi)存?zhèn)鬟f自愿性中斷處理在高級語言中一般表現(xiàn)為與過程調(diào)用類似的形式： 返回值=系統(tǒng)調(diào)用名（參數(shù)1，參數(shù)2，…）

編譯程序會將

翻譯成

的形式，其中系統(tǒng)調(diào)用名對應(yīng)

，不同的系統(tǒng)調(diào)用對應(yīng)不同的整數(shù)n。用戶程序用戶堆棧中斷續(xù)元表中斷續(xù)元運行程序中斷向量處理程序硬件系統(tǒng)堆棧寄存器溢出訪問PSWLA......LAPSWPCPSW1PC1PC1......RET..............................

操作系統(tǒng)

中斷優(yōu)先級

中斷優(yōu)先級是由硬件規(guī)定的,系統(tǒng)根據(jù)引起中斷事件的重要性與緊迫程度將中斷源劃分為若干個級別.

當(dāng)有多個中斷同時發(fā)生時,系統(tǒng)根據(jù)中斷優(yōu)先級決定響應(yīng)中斷次序,優(yōu)先響應(yīng)級別高的中斷；對同級中斷按硬件規(guī)定次序.中斷屏蔽中斷發(fā)生時,CPU輸出不予響應(yīng)的狀態(tài),常用于必須連續(xù)運行的程序,防止任務(wù)被中斷干擾.或執(zhí)行處理某一類中斷,防止其它中斷干擾.

在PSW中設(shè)置一個中斷屏蔽位,通過設(shè)置中斷屏蔽指令完成開中斷與管中斷來進(jìn)行中斷屏蔽中斷嵌套在處理中斷時又響應(yīng)新的中斷.時鐘硬件時鐘軟件時鐘硬件時鐘：某個寄存器來模擬.(根據(jù)脈沖頻率定時加1)絕對時鐘：絕對時間,一般不會中斷.相對時鐘：如鬧鐘,每隔固定時間發(fā)一次中斷.每個脈沖使計數(shù)器減1用來裝入計數(shù)器初值軟件時鐘：做相對時鐘,(用內(nèi)存單元來模擬時鐘)引入通道的目的

為了使CPU從I/O事務(wù)中解脫出來,

同時為了提高CPU與設(shè)備、設(shè)備與設(shè)備之間的并行度。通道定義：

獨立于CPU的專門負(fù)責(zé)數(shù)據(jù)輸入/輸出傳輸工作的處理機(jī),對外部設(shè)備實現(xiàn)統(tǒng)一管理,代替CPU對輸入/輸出操作進(jìn)行控制,從而使輸入/輸出操作可和CPU并行操作。地址映射機(jī)制同時有多個程序在內(nèi)存，程序在內(nèi)存的位置不是固定的而是隨機(jī)的.存儲保護(hù)設(shè)施

問題的提出：多個程序同時在同一臺機(jī)器上運行，怎樣才能互不侵犯？保護(hù)的目的：防止用戶程序破壞OS防止用戶程序互相干擾保護(hù)的硬件支持：為了保證軟件程序只影響程序的內(nèi)部，硬件提供兩項功能地址轉(zhuǎn)換兩種狀態(tài)運行CPUTranslationBox(MMU)虛擬地址物理地址物理空間數(shù)據(jù)讀或?qū)懀ú恍柁D(zhuǎn)換）現(xiàn)代體系結(jié)構(gòu)中的地址轉(zhuǎn)換codedataheapstack程序2虛地址空間data2stack1code1heap1code2stack2data1heap2OScodeOSdataOSheap&stacks程序1虛地址空間codedataheapstack內(nèi)存地址轉(zhuǎn)換地址轉(zhuǎn)換：地址空間：

一個程序可以訪問的所有地址限制程序做什么可以通過限制它的訪問達(dá)到看內(nèi)存的兩種角度：從CPU的角度：程序所能看到的是虛存從存儲角度：物理內(nèi)存兩種狀態(tài)運行操作系統(tǒng)中：可以做任何事（核心態(tài)）用戶程序中：限制只能訪問屬于它自己的空間（用戶態(tài)）劃分每一地址空間，使其行為不能造成破壞2.1多道程序設(shè)計順序程序并發(fā)程序多道程序設(shè)計2.1.1．順序程序程序:指令或語句序列,體現(xiàn)了某種算法,所有程序是順序的順序環(huán)境:

在計算機(jī)系統(tǒng)中只有一個程序在運行,這個程序獨占系統(tǒng)中所有資源,其執(zhí)行不受外界影響。2.1.1．順序程序特征：程序執(zhí)行的順序性程序執(zhí)行的封閉性獨占資源，執(zhí)行過程中不受外界影響程序結(jié)果的可再現(xiàn)性程序運行結(jié)果與程序執(zhí)行速度無關(guān)，只要初始狀態(tài)相同，結(jié)果應(yīng)相同2.1.2并發(fā)程序并發(fā)環(huán)境：在一定時間內(nèi)物理機(jī)器上有兩個或兩個以上的程序同處于開始運行但尚未結(jié)束的狀態(tài)，并且次序不是事先確定的ABABBAAB2.1.2并發(fā)程序特征：（1）程序結(jié)果的不可再現(xiàn)性并發(fā)程序執(zhí)行的結(jié)果與其執(zhí)行的相對速度有關(guān)，是不確定的（2）在并發(fā)環(huán)境下程序的執(zhí)行是間斷性的

執(zhí)行——停——執(zhí)行特征：

（3）資源共享

系統(tǒng)中資源被多個進(jìn)程使用

（4）獨立性和制約性

獨立的相對速度、起始時間

進(jìn)程之間可相互作用（相互制約）

可分為直接作用和間接作用

（5）程序和計算不再一一對應(yīng)

（計算：一個程序的執(zhí)行）2.1.2并發(fā)程序引入并發(fā)的目的：引入并發(fā)是為了提高資源利用率，從而提高系統(tǒng)效率。并發(fā)與并行概念的區(qū)別：concurrency,parallel在順序環(huán)境下

CPU利用率=40/80=50%DEV1利用率=18.75%DEV2利用率=31.25%例:例：在并發(fā)環(huán)境下CPU利用=89%DEV1并發(fā)環(huán)境下利用=33%DEV2并發(fā)環(huán)境下利用=66%2.1.3多道程序設(shè)計定義：Multiprogramming多道程序設(shè)計是指允許多個程序同時進(jìn)入內(nèi)存并運行（引入目的是為了提高系統(tǒng)效率）與并發(fā)不完全是一個概念,但效果相似2.1.3多道程序設(shè)計考慮因素：在多道程序環(huán)境下如何向用戶提供服務(wù)在并發(fā)程序之間如何正確傳遞消息（通訊）如何對CPU進(jìn)行調(diào)度，保證每個用戶相對公平地得到CPU（CPU是一個只可調(diào)度，不可分配的資源。）2.1.3多道程序設(shè)計如何管理其它資源當(dāng)各用戶對資源使用上發(fā)生沖突時，如何處理競爭。 對CPU只能通過調(diào)度來解決競爭問題，而對于其它資源通過申請—分配—使用—回收的辦法進(jìn)行管理，當(dāng)且僅當(dāng)占有CPU的時候才可以申請，否則要排隊等候。2.1.4與時間有關(guān)的錯誤一個飛機(jī)訂票系統(tǒng)，兩個終端，運行T1、T2進(jìn)程T1:T2:......Read(x);Read(x);ifx>=1thenifx>=1thenx:=x-1;x:=x-1;write(x);write(x);......2.1.4與時間有關(guān)的錯誤Cobeginget;copy;put;Coendgetcopyputfstg復(fù)制一個記錄2.1.4與時間有關(guān)的錯誤fstg初始狀態(tài)3,4,...,m22(1,2)g,c,p4,5,...,m33(1,2,3)

g,p,c4,5,...,m33(1,2,2)

c,g,p4,5,...,m32(1,2,2)

c,p,g4,5,...,m32(1,2,2)

p,c,g4,5,...,m32(1,2,2)

p,g,c4,5,...,m33(1,2,2)

設(shè)信息長度為m，有多少種可能性？cpcgpcgpg并行環(huán)境下程序間的制約關(guān)系2.2進(jìn)程進(jìn)程的概念進(jìn)程的狀態(tài)及其轉(zhuǎn)換進(jìn)程控制塊（ProcessControlBlock）進(jìn)程的特征2.2.1進(jìn)程的概念定義：Process

進(jìn)程是具有獨立功能的程序關(guān)于某個數(shù)據(jù)集合上的一次運行活動，是系統(tǒng)進(jìn)行資源分配和調(diào)度的獨立單位。2.2.1進(jìn)程的概念程序與進(jìn)程之間的區(qū)別：進(jìn)程更能真實地描述并發(fā)，而程序不能進(jìn)程是由程序和數(shù)據(jù)兩部分組成的程序是動態(tài)的，進(jìn)程是動態(tài)的進(jìn)程有生命周期，有誕生有消亡，短暫的。而程序是相對長久的一個程序可對應(yīng)多個進(jìn)程，反之亦然進(jìn)程具有創(chuàng)建其它進(jìn)程的功能，而程序沒有2.2.1進(jìn)程的概念進(jìn)程的分類：系統(tǒng)進(jìn)程用戶進(jìn)程（系統(tǒng)進(jìn)程優(yōu)先于用戶進(jìn)程）2.2.2進(jìn)程的基本狀態(tài)及其轉(zhuǎn)換進(jìn)程的三種基本狀態(tài)： 進(jìn)程在生命消亡前處于且僅處于三種基本狀態(tài)之一 不同系統(tǒng)設(shè)置的進(jìn)程狀態(tài)數(shù)目不同運行態(tài)（Running）： 進(jìn)程占有CPU，并在CPU上運行就緒態(tài)（Ready）： 一個進(jìn)程已經(jīng)具備運行條件，但由于無CPU暫時不能運行的狀態(tài)。（當(dāng)調(diào)度給其CPU時，立即可以運行）等待態(tài)（Blocked）：阻塞態(tài)、掛起態(tài)、封鎖態(tài)凍結(jié)態(tài)、睡眠態(tài) 指進(jìn)程因等待某種事件的發(fā)生而暫時不能運行的狀態(tài)。（即使CPU空閑，該進(jìn)程也不可運行）運行就緒等待進(jìn)程的狀態(tài)及其轉(zhuǎn)換

2.2.2進(jìn)程的基本狀態(tài)及其轉(zhuǎn)換狀態(tài)轉(zhuǎn)換：在進(jìn)程運行過程中，由于進(jìn)程自身進(jìn)展情況及外界環(huán)境的變化，這三種基本狀態(tài)可以依據(jù)一定的條件相互轉(zhuǎn)換。

就緒—運行:被調(diào)度程序選中

運行—就緒:時間片到時,或有更高優(yōu)先級的進(jìn)程出現(xiàn)

運行—等待:等待某事件發(fā)生

等待—就緒:等待的事件發(fā)生了2.2.2進(jìn)程的基本狀態(tài)及其轉(zhuǎn)換其他狀態(tài)：創(chuàng)建狀態(tài)，終止?fàn)顟B(tài)掛起狀態(tài)（調(diào)節(jié)負(fù)載，對換，父進(jìn)程，操作系統(tǒng)，終端用戶）2.2.2進(jìn)程的基本狀態(tài)及其轉(zhuǎn)換狀態(tài)轉(zhuǎn)換：在進(jìn)程運行過程中，由于進(jìn)程自身進(jìn)展情況及外界環(huán)境的變化，這三種基本狀態(tài)可以依據(jù)一定的條件相互轉(zhuǎn)換。

就緒—運行:被調(diào)度程序選中

運行—就緒:時間片到時,或有更高優(yōu)先級的進(jìn)程出現(xiàn)

運行—等待:等待某事件發(fā)生

等待—就緒:等待的事件發(fā)生了2.2.3進(jìn)程控制塊

（ProcessControlBlock）概念：系統(tǒng)為了管理進(jìn)程設(shè)置的一個專門的數(shù)據(jù)結(jié)構(gòu)，用它來記錄進(jìn)程的外部特征，描述進(jìn)程的運動變化過程。系統(tǒng)利用PCB來控制和管理進(jìn)程，所以PCB是系統(tǒng)感知進(jìn)程存在的唯一標(biāo)志。進(jìn)程與PCB是一一對應(yīng)的。PCB的內(nèi)容：調(diào)度信息： 進(jìn)程名；進(jìn)程的內(nèi)部標(biāo)識；用戶名；進(jìn)程狀態(tài)；進(jìn)程優(yōu)先級；進(jìn)程的存儲信息（起始地址，長度）；進(jìn)程資源清單；進(jìn)程家族關(guān)系；進(jìn)程的隊列指針；進(jìn)程的消息隊列指針；進(jìn)程當(dāng)前打開的文件…...現(xiàn)場信息： 記錄了重要的寄存器；(虛)時鐘等內(nèi)容2.2.3進(jìn)程控制塊PCB表：系統(tǒng)把所有PCB組織在一起，并把它們放在內(nèi)存的固定區(qū)域，就構(gòu)成了PCB表。

PCB表的大小決定了系統(tǒng)中最多可同時存在的進(jìn)程個數(shù)，稱為系統(tǒng)的并發(fā)度。（注：多道程序中的多道與系統(tǒng)并發(fā)度不同）2.2.3進(jìn)程控制塊進(jìn)程控制塊（ProcessControlBlock）PCB表組織方式：

常用索引方式，對具有相同狀態(tài)的進(jìn)程，分別設(shè)置各自的PCB索引表，表明PCB在PCB表中的地址。（其他方式：線性表或鏈表） 進(jìn)程隊列：不同狀態(tài)進(jìn)程分別組成隊列 運行隊列、就緒隊列、等待隊列2.2.4進(jìn)程的特征并發(fā)性 任何進(jìn)程都可以同其他進(jìn)程一起向前推進(jìn)動態(tài)性 進(jìn)程對應(yīng)程序的執(zhí)行： 進(jìn)程是動態(tài)產(chǎn)生，動態(tài)消亡的。 進(jìn)程在其生命周期內(nèi)，在三種基本狀態(tài)之間轉(zhuǎn)換。

獨立性

進(jìn)程是CPU調(diào)度的一個獨立單位

交互性

指進(jìn)程在執(zhí)行過程中可能與其它進(jìn)程產(chǎn)生直接或間接的關(guān)系

異步性

每個進(jìn)程都與其相對獨立的不可預(yù)知的速度向前推進(jìn)

結(jié)構(gòu)性： 進(jìn)程的組成：程序+數(shù)據(jù)+PCB可再入程序： 可被多個進(jìn)程同時調(diào)用的程序，具有下列性質(zhì)： 它是純代碼的，即在執(zhí)行過程中自身不改變，調(diào)用它的進(jìn)程應(yīng)該提供數(shù)據(jù)區(qū)。【思考題】：1．如果系統(tǒng)中有N個進(jìn)程，運行的進(jìn)程最多幾個，最少幾個；就緒進(jìn)程最多幾個最少幾個；等待進(jìn)程最多幾個，最少幾個？2.有沒有這樣的狀態(tài)轉(zhuǎn)換，為什么？ 等待—運行；就緒—等待3.一個狀態(tài)轉(zhuǎn)換的發(fā)生，是否一定導(dǎo)致另一個轉(zhuǎn)換發(fā)生，列出所有的可能。4.舉3個日常生活中類似進(jìn)程的例子。2.3進(jìn)程間的相互作用進(jìn)程間的聯(lián)系進(jìn)程的同步機(jī)制──信號量及P.V操作（解決進(jìn)程同步互斥問題）2.3.1進(jìn)程間的聯(lián)系相交進(jìn)程與無關(guān)進(jìn)程相交進(jìn)程：指多個并發(fā)進(jìn)程在邏輯上有某種聯(lián)系。無關(guān)進(jìn)程（不相交進(jìn)程）：在邏輯上無任何聯(lián)系的進(jìn)程。2.3.1進(jìn)程間的聯(lián)系直接作用和間接作用直接作用： 進(jìn)程間的相互聯(lián)系是有意識的安排的，直接作用只發(fā)生在相交進(jìn)程間。間接作用： 進(jìn)程間要通過某種中介發(fā)生聯(lián)系，是無意識安排的，可發(fā)生在相交進(jìn)程之間，也可發(fā)生在無關(guān)進(jìn)程之間。進(jìn)程的同步（直接作用）進(jìn)程的同步：synchronism

指系統(tǒng)中一些進(jìn)程需要相互合作，共同完成一項任務(wù)。具體說，一個進(jìn)程運行到某一點時要求另一伙伴進(jìn)程為它提供消息，在未獲得消息之前，該進(jìn)程處于等待狀態(tài)，獲得消息后被喚醒進(jìn)入就緒態(tài)。例:

司機(jī)P1售票員P2

REPEATREPEAT

啟動關(guān)門

正常運行售票

到站停開門

UNTILFALSEUNTILFALSE

進(jìn)程的互斥（間接作用）mutualexclusion

由于各進(jìn)程要求共享資源，而有些資源需要互斥使用，因此各進(jìn)程間競爭使用這些資源，進(jìn)程的這種關(guān)系為進(jìn)程的互斥。臨界資源：criticalresource

系統(tǒng)中某些資源一次只允許一個進(jìn)程使用，稱這樣的資源為臨界資源或互斥資源或共享變量。臨界區(qū)（互斥區(qū)）：criticalsection

一個程序片段的集合，這些程序片段分散在不同的進(jìn)程中，對某個共享的數(shù)據(jù)結(jié)構(gòu)（共享資源）進(jìn)行操作。在進(jìn)程中涉及到臨界資源的程序段叫臨界區(qū)。a:=a-1print(a)a:=a+1print(a)P1互斥P2互斥Ifa<0thena:=a+1elsea:=a-1P3互斥

進(jìn)程的互斥（間接作用）進(jìn)程的互斥（間接作用）使用互斥區(qū)的原則：有空讓進(jìn)：當(dāng)無進(jìn)程在互斥區(qū)時，任何有權(quán)使用互斥區(qū)的進(jìn)程可進(jìn)入。無空等待：不允許兩個以上的進(jìn)程同時進(jìn)入互斥區(qū)。有限等待：任何進(jìn)入互斥區(qū)的要求應(yīng)在有限的時間內(nèi)得到滿足。使用互斥區(qū)的原則：前提：任何進(jìn)程無權(quán)停止其它進(jìn)程的運行 進(jìn)程之間相對運行速度無硬性規(guī)定解決方法：硬件（當(dāng)一個進(jìn)程進(jìn)入臨界區(qū),就屏蔽所有中斷，但成本高。）軟件（用編程解決，但常常忙等待。）軟件解法(1)

free:表示臨界狀態(tài)

true:無進(jìn)程在臨界區(qū)(初值)

false:有進(jìn)程在臨界區(qū)

....

L:iffreethen

begin

free:=false;

‘進(jìn)入臨界區(qū)’

end

elsegotoL;

free:=true

軟件解法(2)turn:trueP進(jìn)入臨界區(qū)

falseQ進(jìn)入臨界區(qū)

....P:repeatuntilturn;

‘進(jìn)入臨界區(qū)’

turn:=flase;Q:repeatuntilnotturn;

‘進(jìn)入臨界區(qū)’

turn:=true;

軟件解法：(3)pturn,qturn:初值為falseP進(jìn)入臨界區(qū)的條件:pturn∧notqturnQ進(jìn)入臨界區(qū)的條件:notpturn∧qturnP....Q.....pturn:=true;pturn:=ture;repeatuntilnotqturn;repeatuntilnotpturn‘進(jìn)入臨界區(qū)’

‘進(jìn)入臨界區(qū)’pturn:=false;qturn:=false

......

軟件解法(4)Dekker算法:在解法(3)基礎(chǔ)上引入turn枚舉類型初值任意

P:Repeat

pturn:=true;

whileqturndo

ifturn=2thenbegin

pturn:=false;

whileturn=2do

pturn:=true

end;

'進(jìn)入臨界區(qū)'

turn:=2;

ptum:=false;

.....Untilfalse

(4)Dekker算法:Q:Repeat

qturn:=true;

whilepturndo

ifturn=1thenbegin

qturn:=false;

whileturn=1do

qturn:=true

end;

'進(jìn)入臨界區(qū)'

turn:=1;

qtum:=false;

.....Untilfalse軟件解法的缺點:1.忙等待

2.實現(xiàn)過于復(fù)雜,需要高的編程技巧

硬件解法(1)

“測試并建立”指令FunctionTest_and_Set(vartarget:boolean):booleanbeginTest_and_Set:=target;target:=trueend

硬件解法(1)

Varlock:boolean;進(jìn)入臨界區(qū)前執(zhí)行：WhileTest_and_Set(lock)doskip;離開臨界區(qū)后執(zhí)行：lock:=false;硬件解法(2)

“交換”指令FunctionSwap(vara,b:boolean)Vartemp:boolean;begintemp:=a;a:=b;b:=tempend

每一組共享變量定義一個全局變量Varlock:boolean;每個進(jìn)程定義一個局部變量Varkey:boolean;進(jìn)入臨界區(qū)前執(zhí)行：

key:=true;repeatswap(lock,key);untilkey=false;離開臨界區(qū)后執(zhí)行：lock:=false;硬件解法(3)

“開關(guān)中斷”指令進(jìn)入臨界區(qū)前執(zhí)行：執(zhí)行“關(guān)中斷”指令離開臨界區(qū)后執(zhí)行：執(zhí)行“開中斷”指令2.3.2進(jìn)程的同步機(jī)制──

信號量及P.V操作（解決進(jìn)程同步）同步機(jī)制：信號量及P、V操作；管程；條件臨界域；路徑表達(dá)式等（用于集中式系統(tǒng)中）會合；通信順序進(jìn)程；分布進(jìn)程；遠(yuǎn)程過程調(diào)用等（適用于分布式系統(tǒng)中）2.3.2進(jìn)程的同步機(jī)制──

信號量及P.V操作（解決進(jìn)程同步）同步機(jī)制應(yīng)滿足的基本要求：*描述能力*可以實現(xiàn)*效率高*使用方便2.3.2進(jìn)程的同步機(jī)制──

信號量及P.V操作（解決進(jìn)程同步）信號量：semaphore

是一個數(shù)據(jù)結(jié)構(gòu)。定義如下：TYPEsemaphore=RECORD Value：integer Queue：Pointer_PCBEND信號量說明：

VAR：S：semaphoreP.V操作P操作P(s):s.Value:=s.Value-1;IFs.Value<0then

將該進(jìn)程狀態(tài)置為等待狀態(tài),然后將該進(jìn)程的PCB插入相應(yīng)的等待隊列末尾。P.V操作V操作V(s):s.Value:=s.Value+1;IFs.Value<=0then喚醒相應(yīng)等待隊列中等待的一個進(jìn)程,改變其狀態(tài)為就緒態(tài)，并將其插入就緒隊列。P、V操作為原語操作原語：primitiveoratomicaction

是由若干多機(jī)器指令構(gòu)成的完成某種特定功能的一段程序，具有不可分割性。

即原語的執(zhí)行必須是連續(xù)的，在執(zhí)行過程中不允許被中斷。實現(xiàn)：開關(guān)中斷信號量的使用：

必須置一次且只能置一次初值，初值不能為負(fù)數(shù)

只能執(zhí)行P、V操作用P.V操作解決進(jìn)程間互斥問題P(S)V(S)P(S)V(S)P(S)V(S)P1P2P2互斥區(qū)經(jīng)典的生產(chǎn)者─消費者問題消費者生產(chǎn)者緩沖區(qū)經(jīng)典的生產(chǎn)者─消費者問題同步問題：

P進(jìn)程不能往“滿”的緩沖區(qū)中放產(chǎn)品，設(shè)置信號量為S1Q進(jìn)程不能從“空”的緩沖區(qū)中取產(chǎn)品，設(shè)置信號量S2P：Q：RepeatRepeat

生產(chǎn)一個產(chǎn)品；P(s2);

送產(chǎn)品到緩沖區(qū)；從緩沖區(qū)取產(chǎn)品；

V(s2);V(s1);P(s1)消費產(chǎn)品Untilfalse;Untilfalse;S1初值為0，S2初值為0P：RepeatP(s1);

生產(chǎn)一個產(chǎn)品；

送產(chǎn)品到緩沖區(qū)；

V(s2)Untilfalse;S1初值為1，S2初值為02.3.2進(jìn)程的同步機(jī)制──

信號量及P.V操作（解決進(jìn)程同步）【思考題】要不要對緩沖區(qū)（臨界資源）進(jìn)行互斥操作？P：

I:=0

REPEAT

生產(chǎn)產(chǎn)品；

P(S1)

往Buffer[I]中放產(chǎn)品；

V(S2)

I:=(I+1)modn

UNTILfalseQ：

J:=0REPEATP(S2)

從Buffer[J]取產(chǎn)品；

V(S1)

消費產(chǎn)品

J:=(J+1)modnUNTILfalseP.V操作討論1)信號量的物理含義：S>0表示有S個資源可用；S=0表示無資源可用；S<0則|S|表示S等待隊列中的進(jìn)程個數(shù)。P(S):表示申請一個資源;V(S)表示釋放一個資源。信號量的初值應(yīng)該大于等于0P.V操作討論2)P.V操作必須成對出現(xiàn)，有一個P操作就一定有一個V操作。當(dāng)為互斥操作時，它們同處于同一進(jìn)程。當(dāng)為同步操作時，則不在同一進(jìn)程中出現(xiàn)。如果P(S1)和P(S2)兩個操作在一起，那么P操作的順序至關(guān)重要,一個同步P操作與一個互斥P操作在一起時同步P操作在互斥P操作前。而兩個V操作無關(guān)緊要。P.V操作討論3）P.V操作的優(yōu)缺點優(yōu)點：簡單，而且表達(dá)能力強(qiáng)（用P.V操作可解決任何同步互斥問題。）缺點：不夠安全；P.V操作使用不當(dāng)會出現(xiàn)死鎖；遇到復(fù)雜同步互斥問題時實現(xiàn)復(fù)雜?！咀鳂I(yè)】1.用P.V操作解決下圖之同步問題:getcopyputfstg2.用P.V操作解決司機(jī)與售票員的問題司機(jī)進(jìn)程：REPEAT啟動車輛正常駕駛到站停車UNTIL…售票員進(jìn)程：REPEAT關(guān)門售票開門UNTIL…2.3.3IPC經(jīng)典問題讀者寫者問題

有兩組并發(fā)進(jìn)程:讀者和寫者,共享一組數(shù)據(jù)區(qū),要求：允許多個讀者同時執(zhí)行讀操作；不允許讀者、寫者同時操作；不允許多個寫者同時操作。第一類：讀者優(yōu)先如果讀者來：1）無讀者、寫者，新讀者可以讀。2）有寫者等，但有其它讀者正在讀，則新讀者也可以讀。3）有寫者寫，新讀者等如果寫者來：1）無讀者，新寫者可以寫。2）有讀者，新寫者等待。3）有其它寫者，新寫者等待。讀者與寫者問題讀者：RepeatP(mutex);readcount:=readcount+1;ifreadcount=1thenP(w);V(mutex);讀P(mutex);readcount:=readcount-1;ifreadcount=0thenV(w);V(mutex);Untilfalse寫者：RepeatP(w);寫V(w);Untilfalse2.哲學(xué)家就餐問題

有五個哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前有一只空盤子，每兩人之間放一只筷子。每個哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉。 為了吃通心粉，每個哲學(xué)家必須拿到兩只筷子，并且每個人只能直接從自己的左邊或右邊去取筷子。哲學(xué)家就餐問題Repeat

思考；取fork[i];取fork[(i+1)mod5]；進(jìn)食；放fork[i];放fork[(i+1)mod5]；Untilfalse;2.哲學(xué)家就餐問題

為防止死鎖發(fā)生可采取的措施：最多允許4個哲學(xué)家同時坐在桌子周圍僅當(dāng)一個哲學(xué)家左右兩邊的筷子都可用時，才允許他拿筷子（

）給所有哲學(xué)家編號，奇數(shù)號的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號的哲學(xué)家則反之為了避免死鎖，所以把哲學(xué)家分為三種狀態(tài)，思考，饑餓，進(jìn)食，并且一次拿到兩只筷子，否則不拿。哲學(xué)家就餐問題state:array[0..4]of(思考，饑餓，進(jìn)食）；ph:array[0..4]ofsemaphore;mutex:semaphore;i:0..4;哲學(xué)家就餐問題Proceduretest(i:=0…4);beginif(state[i]=饑餓)And(state[(i-1)mod5]<>進(jìn)食)And(state[(i+1)mod5]<>進(jìn)食)thenbeginstate[i]=進(jìn)食

V(ph[i])endendProcedurephilosopher(i:0～4)BeginRepeat

思考；

state[i]:=饑餓；

P(mutex);test(i);V(mutex);P(ph[i]);

拿左筷子；拿右筷子；進(jìn)食；放左筷子；放右筷子；哲學(xué)家就餐問題哲學(xué)家就餐問題P(mutex)state[i]:=思考；test([i-1]mod5);tset([i+1]mod5);V(mutex);untilfalesEndstate[I]=思考ph[I]=0mutex=1【作業(yè)：】1.推廣例子中的消息緩沖問題。消息緩沖區(qū)為k個，有m個發(fā)送進(jìn)程，n個接收進(jìn)程，每個接收進(jìn)程對發(fā)送來的消息都必須取一次。2.第二類讀者寫者問題：寫者優(yōu)先條件：1）多個讀者可以同時進(jìn)行讀2）寫者必須互斥（只允許一個寫者寫，也不能讀者寫者同時進(jìn)行）3）寫者優(yōu)先于讀者（一旦有寫者，則后續(xù)讀者必須等待，喚醒時優(yōu)先考慮寫者）3.有一個系統(tǒng)，定義P、V操作如下：P(s):s:=s-1;ifs<0then

將本進(jìn)程插入相應(yīng)隊列末尾等待；V(s)：

s:=s+1;ifs<=0then

從相應(yīng)等待隊列隊尾喚醒一個進(jìn)程，將其插入就緒隊列；

問題：1）這樣定義P、V操作是否有問題？2）用這樣的P、V操作實現(xiàn)N個進(jìn)程競爭使用某一共享變量的互斥機(jī)制。3）對于2）的解法，有無效率更高的方法。如有，試問降低了多少復(fù)雜性？4.理發(fā)師睡覺問題理發(fā)店里有一位理發(fā)師,一把理發(fā)椅和N把供等候理發(fā)的顧客坐的椅子.如果沒有顧客,則理發(fā)師便在理發(fā)椅上睡覺.當(dāng)一個顧客到來時,他必須先喚醒理發(fā)師.如果顧客到來時理發(fā)師正在理發(fā)，則如果有空椅子，可坐下來等；否則離開。2.3.2進(jìn)程的同步機(jī)制──管程管程的提出采用PV同步機(jī)制來編寫并發(fā)程序，對于共享變量及信號量變量的操作將被分散于各個進(jìn)程中。缺點：（１）易讀性差，因為要了解對于一組共享變量及信號量的操作是否正確，則必須通讀整個系統(tǒng)或者并發(fā)程序（２）不利于修改和維護(hù)，因為程序的局部性很差，所以任一組變量或一段代碼的修改都可能影響全局；（３）正確性難以保證，因為操作系統(tǒng)或并發(fā)程序通常很大，要保證這樣一個復(fù)雜的系統(tǒng)沒有邏輯錯誤是很難的。管程：一種同步機(jī)制

(管程-類程-進(jìn)程)管程定義:指關(guān)于共享資源的數(shù)據(jù)及在其上操作的一組過程或共享數(shù)據(jù)結(jié)構(gòu)及其規(guī)定的所有操作

系統(tǒng)按資源管理的觀點分解成若干模塊，用數(shù)據(jù)表示抽象系統(tǒng)資源，同時分析了共享資源和專用資源在管理上的差別，按不同的管理方式定義模塊的類型和結(jié)構(gòu)，使同步操作相對集中，從而增加了模塊的相對獨立性。

管程：集中式同步機(jī)制，它的基本思想是將共享變量以及對共享變量能夠進(jìn)行的所有操作集中在一個模塊中，一個操作系統(tǒng)或并發(fā)程序由若干個這樣的模塊所構(gòu)成，由于一個模塊通常較短，模塊之間關(guān)系清晰，提高了可讀性，便于修改和維護(hù)，正確性易于保證。管程的形式TYPEmonitor_name=MONITOR;共享變量說明define

本管程內(nèi)所定義、本管程外可調(diào)用的過程（函數(shù)）名字表；use

本管程外所定義、本管程內(nèi)將調(diào)用的過程（函數(shù)）名字表；PROCEDURE過程名（形參表）； 過程局部變量說明；

BEGIN

語句序列；

END;......FUNCTION函數(shù)名（形參表）：值類型； 函數(shù)局部變量說明；

BEGIN

語句序列；

END;......BEGIN

共享變量初始化語句序列；END;

管程的三個主要的特性：（一）模塊化，一個管程是一個基本程序單位，可以單獨編譯；（二）抽象數(shù)據(jù)類型，管程是一種特殊的數(shù)據(jù)類型，其中不僅有數(shù)據(jù)，而且有對數(shù)據(jù)進(jìn)行操作的代碼；（三）信息掩蔽，管程是半透明的，管程中的外部過程（函數(shù)）實現(xiàn)了某些功能，管程中的外部過程（函數(shù)）實現(xiàn)了某些功能，至于這些功能是怎樣實現(xiàn)的，在其外部則是不可見的。

管程有如下幾個要素：（一）管程中的共享變量在管程外部是不可見的，外部只能通過調(diào)用管程中所說明的外部過程（函數(shù)）來間接地訪問管程中的共享變量；（二）為了保證管程共享變量的數(shù)據(jù)完整性，規(guī)定管程互斥進(jìn)入；（三）管程通常是用來管理資源的，因而在管程中應(yīng)當(dāng)設(shè)有進(jìn)程等待隊以及相應(yīng)的等待及喚醒操作。

問題：多個進(jìn)程出現(xiàn)在管程中當(dāng)一個進(jìn)入管程的進(jìn)程執(zhí)行等待操作時，它應(yīng)當(dāng)釋放管程的互斥權(quán)；當(dāng)一個進(jìn)入管程的進(jìn)程執(zhí)行喚醒操作時（如Ｐ喚醒Ｑ），管程中便存在兩個同時處于活動狀態(tài)的進(jìn)程。處理方法有三種：Ｐ等待Ｑ繼續(xù)，直到Ｑ退出或等待；

Ｑ等待Ｐ繼續(xù)，直到Ｐ等待或退出；規(guī)定喚醒為管程中最后一個可執(zhí)行的操作。

因為管程是互斥進(jìn)入的，所以當(dāng)一個進(jìn)程試圖進(jìn)入一個巳被占用的管程時它應(yīng)當(dāng)在管程的入口處等待，因而在管程的入口處應(yīng)當(dāng)有一個進(jìn)程等待隊列，稱作入口等待隊列。

如果進(jìn)程Ｐ喚醒進(jìn)程Ｑ，則Ｐ等待Ｑ繼續(xù)，如果進(jìn)程Ｑ在執(zhí)行又喚醒進(jìn)程Ｒ，則Ｑ等待Ｒ繼續(xù)，……，如此，在管程內(nèi)部，由于執(zhí)行喚醒操作，可能會出現(xiàn)多個等待進(jìn)程，因而還需要有一個進(jìn)程等待隊列，這個等待隊列被稱為緊急等待隊列。它的優(yōu)先級應(yīng)當(dāng)高于入口等待隊列的優(yōu)先級。

由于管程通常是用于管理資源的，因而在管程內(nèi)部，應(yīng)當(dāng)存在某種等待機(jī)制。當(dāng)進(jìn)入管程的進(jìn)程因資源被占用等原因不能繼續(xù)運行時使其等待。為此在管程內(nèi)部可以說明和使用一種特殊類型的變量。稱作條件變量：

VARC:condition;對于條件型變量，可以執(zhí)行wait和signal操作：

wait（c）：如果緊急等待隊列非空，則喚醒第一個等待者；否則釋放管程的互斥權(quán)，執(zhí)行此操作的進(jìn)程的PCB入c鏈尾部。signal（c）：如果c鏈為空，則相當(dāng)于空操作，執(zhí)行此操作的進(jìn)程繼續(xù)；否則喚醒第一個等待者，執(zhí)行此操作的進(jìn)程的PCB入緊急等待隊列的尾部。管程的實現(xiàn)兩個主要途徑：*直接構(gòu)造*間接構(gòu)造，即用某種已經(jīng)實現(xiàn)的同步機(jī)制去構(gòu)造前者效率高例子：用PV操作構(gòu)造管程管程的四個組成部分：名稱數(shù)據(jù)結(jié)構(gòu)說明對該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程/函數(shù)初始化語句TYPEone_instance=RECORDmutex:semaphore;（初值1）

urgent:semaphore;（初值0）

urgent_count:integer;（初值0）

END;TYPEmonitor_elements=MODULE;defineenter,leave,wait,signal;mutex（入口互斥隊列）

urgent（緊急等待隊列）

urgent_count（緊急等待計數(shù)）PROCEDUREenter(VARinstance:one_instance);BEGINP(instance.mutex)END;PROCEDUREleave(VARinstance:one_instance);BEGINIFinstance.urgent_count>0THENBEGINinstance.urgent--;V(instance.urgent)ENDELSEV(instance.mutex)END;PROCEDUREwait(VARinstance:one_instance;VARs:semephore;VARcount:integer);BEGINcount++;IFinstance.urgent_count>0THENBEGINinstance.urgent_count--;V(instance.urgent)ENDELSEV(instance.mutex);P(s);END;PROCEDUREsignal(VARinstance:one_instance;VARs:semaphore;VARcount:integer);BEGINIFcount>0THENBEGINcount--;instance.urgent_count++;V(s);P(instance.urgent)ENDEND;例子：一個信息緩沖區(qū)是一個共享資源抽象成一個數(shù)據(jù)結(jié)構(gòu)：數(shù)組構(gòu)造一些操作（過程或函數(shù)）：發(fā)送：向緩沖區(qū)發(fā)消息接收：從緩沖區(qū)取消息隱藏了內(nèi)部的數(shù)據(jù)結(jié)構(gòu)和實現(xiàn)細(xì)節(jié)例子：讀者-寫者問題TYPEr_and_w=MODULE;VARinstance:one_instance;rq,wq:semaphore;r_count,w_count:integer;reading_count,write_count:integer;definestart_r,finish_r,start_w,finish_w;usemonitor_elements.enter,monitor_elements.leave,monitor_elements.wait,monitor_elements.signal;PROCEDUREstart_r;BEGINmonitor_elements.enter(instance);IFwrite_count>0THENmonitor_elements.wait(instance,rq,r_count);reading_count++;monitor_elements.signal(instance,rq,r_count);monitor_elements.leave(instance);END;PROCEDUREfinish_r;BEGINmonitor_elements.enter(instance);reading_count--;IFreading_count=0THENmonitor_elements.signal(instance,wq,w_count);monitor_elements.leave(instance);END;PROCEDUREstart_w;BEGINmonitor_elements.enter(instance);write_count++;IF(write_count>1)OR(reading_count>0)THENmonitor_elements.wait(instance,wq,w_count);monitor_elements.leave(instance);END;BEGINreading_count::=0;write_count::=0;r_count:=0;w_count::=0;END;讀者的活動：r_and_w.start_r;讀操作；r_and_w.finish_r;寫者的活動：r_and_w.start_w;寫操作；r_and_w.finish_w;管程和進(jìn)程的異同點：（1）設(shè)置進(jìn)程和管程的目的不同（2）系統(tǒng)管理數(shù)據(jù)結(jié)構(gòu)進(jìn)程：PCB

管程：等待隊列（3）管程被進(jìn)程調(diào)用（4）管程是操作系統(tǒng)的固有成分，無創(chuàng)建和撤消2.4進(jìn)程通信概述消息緩沖通信方式2.4.1概述 P.V操作實現(xiàn)的是進(jìn)程之間的低級通訊，所以P.V為低級通訊原語。它只能傳遞簡單的信號，不能傳遞交換大量信息。

如果要在進(jìn)程間傳遞大量信息則要用Send/Receive原語（高級通訊原語）。2.4.1概念進(jìn)程通信的方式共享內(nèi)存：相互通信的進(jìn)程間設(shè)有公共內(nèi)存，一組進(jìn)程向該公共內(nèi)存中寫，另一組進(jìn)程從公共內(nèi)存中讀，通過這種方式實現(xiàn)兩組進(jìn)程間的信息交換。這種通信模式需要解決兩個問題？進(jìn)程通信的方式消息傳遞：系統(tǒng)為進(jìn)程提供了兩個高級通訊原語send和receivesend： 當(dāng)要進(jìn)行消息傳遞時執(zhí)行sendreceive： 當(dāng)接收者要接收消息時執(zhí)行receive共享文件模式：

管道通信消息傳遞模式消息緩沖在內(nèi)存中開設(shè)緩沖區(qū)，發(fā)送進(jìn)程將消息送入緩沖區(qū)，接收進(jìn)程接收傳遞來的緩沖區(qū)信箱通信直接方式：

發(fā)送進(jìn)程發(fā)消息時要指定接收進(jìn)程的名字，反過來，接收時要指明發(fā)送進(jìn)程的名字。

Send(receiver,message)Receiver(sender,message)*對稱形式：一對一*非對稱形式：多對一（顧客/服務(wù)員）有緩沖（有界，無界），無緩沖間接方式：

發(fā)送進(jìn)程發(fā)消息時不指定接收進(jìn)程的名字，而是指定一個中間媒介，即信箱。進(jìn)程間通過信箱實現(xiàn)通信。

發(fā)送原語：send(MB,Message)

接收原語：receive(MB,Message)2.4.2消息緩沖（有界緩沖區(qū)原理）：在操作系統(tǒng)空間設(shè)置一組緩沖區(qū)，當(dāng)發(fā)送進(jìn)程需要發(fā)送消息時，執(zhí)行send系統(tǒng)調(diào)用，產(chǎn)生自愿性中斷，進(jìn)入操作系統(tǒng)，操作系統(tǒng)為發(fā)送進(jìn)程分配一個空緩沖區(qū)，并將所發(fā)送的消息從發(fā)送進(jìn)程copy到緩沖區(qū)中，然后將該載有消息的緩沖區(qū)連接到接收進(jìn)程的消息鏈鏈尾，如此就完成了發(fā)送過程。發(fā)送進(jìn)程返回到用戶態(tài)繼續(xù)執(zhí)行。2.4.2消息緩沖（有界緩沖區(qū)原理）：在以后某個時刻，當(dāng)接收進(jìn)程執(zhí)行到receive接收原語時，也產(chǎn)生自愿性中斷進(jìn)入操作系統(tǒng)，由操作系統(tǒng)將載有消息的緩沖區(qū)從消息鏈中取出，并把消息內(nèi)容copy到接收進(jìn)程空間，之后收回緩沖區(qū)，如此就完成了消息的接收，接收進(jìn)程返回到用戶態(tài)繼續(xù)進(jìn)行。PCB......Send(R,M)......SIZE:消息長度TEXT:消息正文......消息鏈指針............Receive(pid,N)......SIZE:消息長度TEXT:消息正文......M:N:接受進(jìn)程R發(fā)送進(jìn)程S消息消息消息......消息緩沖區(qū)結(jié)構(gòu)：消息長度消息正文發(fā)送者消息隊列指針用P.V操作來實現(xiàn)Send原語:Send（R，M）P(m-mutex);Begin把緩沖區(qū)掛到接收進(jìn)程根據(jù)R找接收進(jìn)程，的消息鏈鏈尾;

如果沒找到出錯返回;V(m-mutex);

申請空緩沖