【正文】 就緒阻塞DA:進(jìn)程調(diào)度 B:發(fā)生某事件無(wú)法執(zhí)行 C:時(shí)間片到或優(yōu)先級(jí)高的進(jìn)程到達(dá) D:阻塞的事件消失(5) 簡(jiǎn)述進(jìn)程與程序的區(qū)別。 處理機(jī)狀態(tài)信息216。一個(gè)數(shù)據(jù)對(duì)象（數(shù)據(jù)文件或記錄）可被多個(gè)進(jìn)程共享，其中有些進(jìn)程要求讀（讀者進(jìn)程），而另一些進(jìn)程要求對(duì)數(shù)據(jù)對(duì)象進(jìn)行寫或修改（寫者進(jìn)程）。(12) 什么是原語(yǔ)？★答：由若干條指令所構(gòu)成、用于完成一定功能的一個(gè)過(guò)程，具有原子性。答：系統(tǒng)將所有的就緒進(jìn)程按先來(lái)先服務(wù)的原則，排成一個(gè)隊(duì)列，每次調(diào)度時(shí)把CPU分配給隊(duì)首進(jìn)程，令其執(zhí)行一個(gè)時(shí)間片，時(shí)間片用完，由一個(gè)計(jì)時(shí)器發(fā)出時(shí)鐘中斷，調(diào)度程序停止該進(jìn)程的運(yùn)行，將其送到就緒隊(duì)列的末尾，等待下一次執(zhí)行，然后將處理機(jī)分配給就緒隊(duì)列的新的隊(duì)首進(jìn)程，讓它執(zhí)行一個(gè)時(shí)間片。(18) 進(jìn)程之間存在哪幾種相互制約關(guān)系？各是什么原因引起的？下列活動(dòng)分別屬于哪種制約？（1）若干同學(xué)去圖書館借書（2）兩隊(duì)舉行籃球比賽（3）流水線生產(chǎn)的各道工序（4）商品生產(chǎn)和社會(huì)消費(fèi)。該圖由一組結(jié)點(diǎn)N和一組邊E組成，結(jié)點(diǎn)N被分成兩個(gè)互斥的子集P和R，分別表示進(jìn)程結(jié)點(diǎn)集和資源結(jié)點(diǎn)集，E中的邊連接著P中一個(gè)結(jié)點(diǎn)和R中一個(gè)結(jié)點(diǎn)，e={pi,ri}表示進(jìn)程請(qǐng)求一個(gè)單位的資源， e={rj,pj}表示把一個(gè)單位的資源分配給進(jìn)程。 答：在不同的運(yùn)行推進(jìn)速度下，可能產(chǎn)生死鎖。SSSS4的初值均為0。爸爸專向盤中放蘋果，媽媽專向盤中放桔子，兩個(gè)兒子專等吃盤中的蘋果，兩個(gè)女兒專等吃盤中的桔子。定義信號(hào)量 run，表示司機(jī)是否可以啟動(dòng)車輛，也就是車門的狀態(tài)（0表示門開，1表示門關(guān)），初值為0。 判斷是否可以啟動(dòng)車輛；若售票員已關(guān)門run為1，繼續(xù)； 啟動(dòng)車輛； 若售票員未關(guān)門run為0，阻塞，無(wú)法啟動(dòng)車輛。試給出有關(guān)取水、入水的算法描述?？捎盟皵?shù)目+1 V(full) 水入缸后可供老和尚取水，可取水的桶數(shù)+1此題特別要注意P操作的次序，例如：如果P(empty)和P(count)操作次序顛倒，就有可能產(chǎn)生死鎖。need[i,j]=max[i,j]allocation[i,j]利用銀行家算法對(duì)此資源分配情況進(jìn)行分析，可得此時(shí)刻的安全性分析情況： Work NeedAllocationWork+allocationFinishP4233221204437TrueP54371103147411TrueP174113472129513TrueP2951313440213515TrueP31351500640517520True因?yàn)門0時(shí)刻存在安全序列p4,p5,p1,p2,p3，故T0時(shí)刻安全。 單位：小時(shí)解答：先來(lái)先服務(wù)：作業(yè)提交時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間11：0021：003：00221：1063：009：007．8332：0029：0011：00942：00111：0012：0010平均帶權(quán)周轉(zhuǎn)時(shí)間=（2/2++9/2+10/1）/4= 短作業(yè)優(yōu)先調(diào)度：作?？捎盟皵?shù)目+1 (6) 設(shè)系統(tǒng)中有五個(gè)進(jìn)程、3種資源，總數(shù)分別為A 17，B 5，C 20，T0時(shí)刻系統(tǒng)狀態(tài)如下。同時(shí)，缸中沒(méi)水，老和尚不能取水，要等待小和尚倒水入缸；水缸滿，小和尚不能倒水入缸，要等待老和尚取水，也就是說(shuō)，小和尚倒水入缸和老和尚取水必須同步。水桶總數(shù)為4個(gè)。 判斷是否可以開車門；若司機(jī)已停車，stop為1，繼續(xù)； 開車門； 若司機(jī)未停車，stop為0，阻塞，無(wú)法開車門。設(shè)置信號(hào)量 s1=2，表示盤子中可放水果的空位置； s2=1，表示盤中放、取水果的互斥信號(hào)量； s3=0，表示盤中蘋果的數(shù)目； s4=0，表示盤中桔子的數(shù)目；父親： 母親： 兒子： 女兒： P(S1) P(S1) P(S3) P(S4) P(S2) P(S2) P(S2) P(S2)放蘋果 放桔子 取蘋果 取桔子V(S2) V(S2) P(S2) P(S2)V(S3) V(S4) V(S1) V(S1)(4) 在公共汽車上，司機(jī)和售票員的活動(dòng)分別是司機(jī)：?jiǎn)?dòng)車輛；正常行車；到站停車；售票員：關(guān)車門；售票；開車門；在汽車不斷到站、停車、行駛過(guò)程中，這兩個(gè)活動(dòng)存在著同步關(guān)系，試用信號(hào)量和P、V操作實(shí)現(xiàn)它們的同步。 由發(fā)送者進(jìn)程可知，當(dāng)發(fā)送者將一個(gè)消息放入消息鏈尾后，執(zhí)行V(s)操作，故s表示接收者可取消息的數(shù)量，又因s用于實(shí)現(xiàn)進(jìn)程同步，所以接收者接受消息前，應(yīng)判斷是否有消息可以取，需對(duì)s執(zhí)行P操作，所以C為P(s)，發(fā)送者發(fā)送消息前，接收者無(wú)消息可取，s的初值應(yīng)為0。四. 應(yīng)用題(1) 請(qǐng)用信號(hào)量實(shí)現(xiàn)4*100接力賽的同步過(guò)程P1P2P4P3解答： S1 S2 S3PPP3和P4分別代表四位運(yùn)動(dòng)員，他們的跑步順序受其位置的限制。4）、解除死鎖——將進(jìn)程從死鎖狀態(tài)下解脫。 r1 r2 r3 r4 (20) 舉例描述資源分配圖。設(shè)置工作向量work＝available；finish[j]=false，從進(jìn)程集合中不斷找到滿足finish[j]＝false且need[j]＝work的進(jìn)程，分配資源，當(dāng)其獲得資源可順利執(zhí)行，直至完成，并釋放資源。常用的調(diào)度算法有：先進(jìn)先出法、短執(zhí)行進(jìn)程優(yōu)先法、優(yōu)先級(jí)調(diào)度法、輪轉(zhuǎn)法等。間接通信指進(jìn)程間的通信，需要通過(guò)作為某種共享數(shù)據(jù)結(jié)構(gòu)的實(shí)體——信箱。(9) 簡(jiǎn)述讀者——寫者問(wèn)題的思想。 進(jìn)程標(biāo)識(shí)符信息——外部標(biāo)識(shí)符、內(nèi)部標(biāo)識(shí)符（唯一整數(shù)）。執(zhí)行答：進(jìn)程是可并發(fā)執(zhí)行的程序在一個(gè)數(shù)據(jù)集上的運(yùn)行過(guò)程?？稍佻F(xiàn)性——只要程序執(zhí)行的環(huán)境和初始條件相同，程序多次重復(fù)執(zhí)行，不論是不停頓執(zhí)行，還是走走停停，都將獲得相同的結(jié)果。（9） 進(jìn)程運(yùn)行過(guò)程中，因?yàn)? 、等待I/O操作等事件發(fā)生時(shí)，通過(guò) 原語(yǔ)將它撤下，排入 隊(duì)列，并引起新的 。（3） 在操作系統(tǒng)中，時(shí)鐘常有兩種用途：報(bào)告 和對(duì)__________記時(shí)。（4） 錯(cuò)；應(yīng)為：原語(yǔ)由若干條指令所構(gòu)成、用于完成一定功能的一個(gè)過(guò)程，具有原子性。( )（7） 程序的封閉性是指該程序不允許某些進(jìn)程調(diào)用。（3） 進(jìn)程獲得資源，執(zhí)行并完成，釋放資源work=work+allocationfinish[i]=true（4） 若所有進(jìn)程的finish[i]=true，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 數(shù)據(jù)結(jié)構(gòu)（n個(gè)進(jìn)程，m類資源）可利用資源available[1..m]最大需求矩陣(n*m) max分配矩陣(n*m) allocation需求矩陣(n*m) need[i,j]=max[i,j]allocation[i,j]216。 系統(tǒng)的安全狀態(tài)所謂安全狀態(tài)，是指系統(tǒng)能按某種順序，如P1,P2…Pn，來(lái)為每個(gè)進(jìn)程分配其所需資源，直至最大需求，使每個(gè)進(jìn)程都可順利完成。N被分成兩個(gè)互斥的子集，一組進(jìn)程結(jié)點(diǎn)P={p1，p2,……，pn}，一組資源結(jié)點(diǎn)R={r1，r2,……，rm}E中的邊e連接著P中的一個(gè)結(jié)點(diǎn)和R中的一個(gè)結(jié)點(diǎn)。（2） 請(qǐng)求和保持條件——請(qǐng)求新資源阻塞，保持其它已獲得資源不放。216。 每次調(diào)度需計(jì)算響應(yīng)比，增加系統(tǒng)的開銷。 優(yōu)先權(quán)類型：靜態(tài)優(yōu)先權(quán)、動(dòng)態(tài)優(yōu)先權(quán)178。 系統(tǒng)將所有的就緒進(jìn)程按先來(lái)先服務(wù)原則，排成一個(gè)隊(duì)列，每次調(diào)度時(shí)把CPU分配給隊(duì)首進(jìn)程，令其執(zhí)行一個(gè)時(shí)間片。178。 截止時(shí)間——某任務(wù)必須開始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間。中級(jí)調(diào)度實(shí)際上是存儲(chǔ)器管理中的對(duì)換功能。 高級(jí)調(diào)度——作業(yè)調(diào)度批處理系統(tǒng)中使用，周期較長(zhǎng)。共享信箱——某進(jìn)程創(chuàng)建，指明共享進(jìn)程的名字。 直接通信方式發(fā)送進(jìn)程利用OS所提供的發(fā)送命令，直接把消息發(fā)送給目標(biāo)進(jìn)程。進(jìn)程的同步是低級(jí)通信，效率低，對(duì)用戶不透明。 讀者——寫者問(wèn)題一個(gè)數(shù)據(jù)對(duì)象(數(shù)據(jù)文件或記錄)，可被多個(gè)進(jìn)程共享。 一般“信號(hào)量集”機(jī)制P（Si，ti，di） ti表示資源下限 di表示資源需求或分配數(shù)目條件：Si≥ti 分配：Si:= Si –diJ p(s,d,d) 一般信號(hào)量J p(s,1,1) (s1)一般的記錄型信號(hào)量 (s=1) 互斥信號(hào)量J p(s,1,0) 可控開關(guān)3. 經(jīng)典進(jìn)程的同步問(wèn)題178。 v(s) :=+1。 type semaphore=recordvalue:integer。216。 忙則等待——互斥216。 臨界資源——一段時(shí)間內(nèi)只允許一個(gè)進(jìn)程訪問(wèn)的資源。 進(jìn)程的創(chuàng)建——?jiǎng)?chuàng)建原語(yǔ)申請(qǐng)空白PCB 為進(jìn)程分配資源 初始化PCB 插入就緒隊(duì)列（2） 進(jìn)程的終止——正常結(jié)束、異常結(jié)束、外界干預(yù)（3） 進(jìn)程的阻塞與喚醒178。 進(jìn)程圖——是描述進(jìn)程家族關(guān)系的有向樹。內(nèi)核只對(duì)中斷進(jìn)行“有限的處理”，然后轉(zhuǎn)由有關(guān)進(jìn)程繼續(xù)處理。 PCB的組織方式216。 PCB的內(nèi)容216。178。 獨(dú)立性——進(jìn)程實(shí)體是一個(gè)能獨(dú)立運(yùn)行的基本單位，也是系統(tǒng)中獨(dú)立獲得資源和獨(dú)立調(diào)度的基本單位。R(p1) ∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)={ }二. 進(jìn)程的描述1. 進(jìn)程的定義和特征進(jìn)程是可并發(fā)執(zhí)行的程序在一個(gè)數(shù)據(jù)集合上的運(yùn)行過(guò)程。 程序的并發(fā)執(zhí)行I 輸入C 計(jì)算P 輸出同一數(shù)據(jù)的不同操作之間、不同數(shù)據(jù)的同一操作之間存在著前趨關(guān)系。為了描述并發(fā)執(zhí)行的動(dòng)態(tài)特點(diǎn)，引入進(jìn)程的概念。 ）類型。 ） ）內(nèi)處理來(lái)自外部的事件。4. 多道程序設(shè)計(jì)時(shí)應(yīng)注意什么問(wèn)題？答：處理機(jī)管理問(wèn)題——多道程序之間如何分配CPU，使CPU既能滿足各程序運(yùn)行的需要，又能提高處理機(jī)的利用率。3. 什么是操作系統(tǒng)？它有什么基本特征？ 答：操作系統(tǒng)是一組控制和管理計(jì)算機(jī)硬件和軟件資源、合理組織計(jì)算機(jī)的工作流程，以及方便用戶的程序的集合。（10） 在主機(jī)控制下進(jìn)行的輸入/輸出操作稱為 操作。（2） 操作系統(tǒng)的層次結(jié)構(gòu)中，與 或運(yùn)行頻率較高的模塊都安排在緊靠硬件的軟件層中，這一部分通常稱為 ，它在執(zhí)行基本操作時(shí)，往往是利用 操作來(lái)實(shí)現(xiàn)，該操作具有原子性。（ ）習(xí)題解答：（1） 錯(cuò)；應(yīng)為：實(shí)時(shí)系統(tǒng)能應(yīng)用于生產(chǎn)控制系統(tǒng)，也能應(yīng)用于信息處理系統(tǒng)。）（1） 實(shí)時(shí)系統(tǒng)只能應(yīng)用于生產(chǎn)控制系統(tǒng)，不能應(yīng)用于信息處理系統(tǒng)。（4） 設(shè)備獨(dú)立性和虛擬設(shè)備4. 文件管理程序和數(shù)據(jù)都是以文件的形式存儲(chǔ)在存儲(chǔ)介質(zhì)上。（1） 內(nèi)存分配——為每道程序分配內(nèi)存空間，提高內(nèi)存的利用率。五. 操作系統(tǒng)的功能操作系統(tǒng)引入多道程序設(shè)計(jì)技術(shù)，一方面改善了系統(tǒng)資源的利用率，但另一方面也引發(fā)了復(fù)雜的系統(tǒng)管理問(wèn)題，諸如內(nèi)存中的作業(yè)如何存儲(chǔ)，系統(tǒng)資源如何共享等，操作系統(tǒng)必須具有控制和管理各種并發(fā)活動(dòng)的能力，合理組織計(jì)算機(jī)的工作流程，有效地提高各類資源的利用率。2. 共享系統(tǒng)中的資源可供內(nèi)存中多個(gè)并發(fā)執(zhí)行的進(jìn)程共同使用。實(shí)時(shí)信息處理系統(tǒng)在響應(yīng)時(shí)間上和分時(shí)系統(tǒng)處于同一級(jí)別，但更強(qiáng)調(diào)可靠性和安全性，交互性差。僅當(dāng)前臺(tái)無(wú)作業(yè)運(yùn)行時(shí)，方才運(yùn)行后臺(tái)的作業(yè)。程序A輸入設(shè)備輸出設(shè)備CPU程序B程序A程序B程序A程序B運(yùn)行處理輸入數(shù)據(jù)運(yùn)行處理輸出數(shù)據(jù)運(yùn)行處理輸出數(shù)據(jù)等待CPU運(yùn)行處理圖13多道程序運(yùn)行情況三. 操作系統(tǒng)的分類1. 單用戶操作系統(tǒng)2. 批處理操作系統(tǒng)（1） 單道批處理系統(tǒng)把一批作業(yè)以脫機(jī)方式輸入到磁帶上，在系統(tǒng)中配上監(jiān)督程序，在它的控制下使這批作業(yè)能自動(dòng)地一個(gè)接一個(gè)地順序處理。由于主機(jī)CPU只與高速的輸入輸出設(shè)備打交道，從而有效地減少了CPU等待低速設(shè)備輸入輸出的時(shí)間。在計(jì)算機(jī)系統(tǒng)上覆蓋上一層軟件后，系統(tǒng)功能便增強(qiáng)一級(jí)?；蛘哒f(shuō)，用戶在OS的幫助下能夠方便、快捷、安全、可靠地操縱計(jì)算機(jī)硬件和運(yùn)行自己的程序。應(yīng)用程序?qū)嵱贸绦虿僮飨到y(tǒng)計(jì)算機(jī)硬件（裸機(jī)）用戶圖11 計(jì)算機(jī)系統(tǒng)的層次圖1. 操作系統(tǒng)（Operating System，簡(jiǎn)稱OS）的作用（1） OS作為用戶與計(jì)算機(jī)硬件系統(tǒng)之間的接口OS處于用戶與計(jì)算機(jī)硬件系統(tǒng)之間，用戶通過(guò)OS來(lái)使用計(jì)算機(jī)系統(tǒng)。通常把覆蓋了軟件的機(jī)器稱為擴(kuò)充機(jī)器或虛機(jī)器。類似地，脫機(jī)輸出技術(shù)通過(guò)外圍機(jī)完成數(shù)據(jù)從主機(jī)到磁帶，再到低速輸出設(shè)備上的輸出操作。為解決上述問(wèn)題而設(shè)置的一組軟件就形成了操作系統(tǒng)。前臺(tái)區(qū)存放按時(shí)間片“調(diào)進(jìn)”和“調(diào)出”的作業(yè)流，后臺(tái)區(qū)存放批處理作業(yè)。實(shí)時(shí)控制系統(tǒng)是以計(jì)算機(jī)為中心的生產(chǎn)過(guò)程控制系統(tǒng)，又稱為計(jì)算機(jī)控制系統(tǒng)，要求快速的響應(yīng)時(shí)間，可靠性要求高。要注意區(qū)別并發(fā)和并行兩個(gè)概念。但只要運(yùn)行環(huán)境相同，作業(yè)經(jīng)過(guò)多次運(yùn)行，都會(huì)獲得完全相同的結(jié)果。2. 存儲(chǔ)器管理存儲(chǔ)器管理