【正文】 3 61 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 7 7 7 2 2 2 2 2 3 4 4 4 5 6 6 6 6 6 6 6 6 6 1 1 1 6 (2’)內(nèi)存塊數(shù) 置換算法 FIFO LRU OPT3 16 15 11 (3’)2考慮下面存儲(chǔ)訪問(wèn)序列，該程序大小為460字：10，11，104，170，73，309，185，245，246，434，458，364 設(shè)頁(yè)面大小是100字，請(qǐng)給出該訪問(wèn)序列的頁(yè)面走向。9請(qǐng)求分頁(yè)技術(shù)的基本思想是什么？它與簡(jiǎn)單分頁(yè)技術(shù)之間有何根本區(qū)別？答：請(qǐng)求分頁(yè)技術(shù)的基本思想是：當(dāng)一個(gè)進(jìn)程的部分頁(yè)面在內(nèi)存時(shí)就可調(diào)度它運(yùn)行；在運(yùn)行過(guò)程中若用到的頁(yè)面尚未在內(nèi)存，則把它們動(dòng)態(tài)換入內(nèi)存。離散分配——不必占用連續(xù)的內(nèi)存空間,而是”見(jiàn)縫插針”。23實(shí)存實(shí)存是指計(jì)算機(jī)配置的物理存儲(chǔ)器，它直接向cpu提供程序和數(shù)據(jù)。即如果一個(gè)進(jìn)程沒(méi)有一定數(shù)量的內(nèi)存塊，它很快就發(fā)生缺頁(yè)。3邏輯地址空間由程序中邏輯地址組成的地址范圍叫做邏輯地址空間。 ①用一個(gè)執(zhí)行時(shí)間圖描述使用非搶占式優(yōu)先級(jí)算法時(shí)各自執(zhí)行這些作業(yè)的情況： ②對(duì)于該算法，各個(gè)作業(yè)的周轉(zhuǎn)時(shí)間是多少?平均周轉(zhuǎn)時(shí)間是多少？③對(duì)于該算法，各個(gè)作業(yè)的帶權(quán)周轉(zhuǎn)時(shí)間是多少？平均帶權(quán)周轉(zhuǎn)時(shí)間是多少？解：⑴ 非搶占式優(yōu)先級(jí) J1 J4 J3 J5 J20 10 11 13 18 19(3’) ⑵和⑶ 非搶占式優(yōu)先級(jí) (`7’=1’*7)JOB ts tr te T WJ1 0 10 10 10 1J2 1 1 19 18 18J3 2 2 13 11 J4 3 1 11 8 J5 4 5 18 14 2在一個(gè)有兩道作業(yè)的批處理系統(tǒng)中，作業(yè)調(diào)度采用短作業(yè)優(yōu)先級(jí)調(diào)度算法，進(jìn)程調(diào)度采用搶占式優(yōu)先級(jí)調(diào)度算法。像UNIX這樣的分時(shí)系統(tǒng)中，則沒(méi)有作業(yè)概念。這種調(diào)度方式系統(tǒng)開銷大，但系統(tǒng)能及時(shí)響應(yīng)請(qǐng)求。由于系統(tǒng)存在一個(gè)進(jìn)程完成的安全序列P1\P3\P4\P2\P5(2’)，故系統(tǒng)狀態(tài)是安全的(2’)。系統(tǒng)還剩2個(gè)。若出現(xiàn)以下資源分配情況： 進(jìn)程 資源最大請(qǐng)求 已分配資源 p0 7, 5, 3 0, 1, 0 p1 3, 2, 2 2, 1, 0 p2 9, 0, 2 3, 0, 2 p3 2, 2, 2 2, 1, 1 p4 4, 3, 3 0, 0, 2系統(tǒng)剩余資源數(shù)量為(3,2,2)。即系統(tǒng)中的進(jìn)程處于安全序列中。3死鎖防止要求進(jìn)程申請(qǐng)資源時(shí)遵循某種協(xié)議，從而打破產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)，保證系統(tǒng)不會(huì)進(jìn)入死鎖狀態(tài)?！　OBEGIN　PROCESS　PI(I=1，2，……)　　　　　　　 begin　　　　　　　　進(jìn)入售票廳； 購(gòu)票； 　　　　　　　　　　　退出；　　　　　　　 end　　　COEND(3)若欲購(gòu)票者最多為n個(gè)人，寫出信號(hào)量可能的變化范圍(最大值和最小值)。 //申請(qǐng)過(guò)河 V(S1)。每當(dāng)有讀者進(jìn)入閱覽室時(shí)，為了正確地登記，各讀者應(yīng)互斥使用(1’)。如果廳內(nèi)不足100人則允許進(jìn)入，進(jìn)入后購(gòu)票，購(gòu)票后退出。B1S1=2。② 資源分配給進(jìn)程，同一進(jìn)程的所有線程共享該進(jìn)程的所有資源。 直接制約是由并發(fā)進(jìn)程相互共享對(duì)方的私有資源所引起的；間接制約是由競(jìng)爭(zhēng)共有資源而引起的。簡(jiǎn)答題1在操作系統(tǒng)中為什么要引入進(jìn)程概念？答: 由于多道程序并發(fā)執(zhí)行時(shí)共享系統(tǒng)資源，共同決定這些資源的狀態(tài)，因此系統(tǒng)中各程序在執(zhí)行過(guò)程中就出現(xiàn)了相互制約的新關(guān)系，程序的執(zhí)行出現(xiàn)“走走停?！钡男聽顟B(tài)。5互斥在邏輯上本來(lái)完全獨(dú)立的進(jìn)程，由于競(jìng)爭(zhēng)同一個(gè)資源而產(chǎn)生的相互制約的關(guān)系。 用戶程序是在用戶態(tài)下執(zhí)行，它的權(quán)限較低，只能執(zhí)行指令集中非特權(quán)指令。4多道程序和多重處理有何區(qū)別？答：多道程序是作業(yè)之間自動(dòng)調(diào)度執(zhí)行、共享系統(tǒng)資源，并不是真正的同時(shí)執(zhí)行多個(gè)作業(yè)；而多重處理系統(tǒng)配置多個(gè)cpu，能真正同時(shí)執(zhí)行多道程序。9實(shí)時(shí)表示“及時(shí)”或“既時(shí)”。它是宏觀上的概念。操作系統(tǒng)的主要功能有5個(gè)方面，即存儲(chǔ)管理、處理機(jī)管理、設(shè)備管理、文件管理和用戶接口。其主要特征是：交互性、多用戶同時(shí)性、獨(dú)立性。而系統(tǒng)調(diào)用不是機(jī)器指令，它往往以函數(shù)調(diào)用的形式出現(xiàn)，實(shí)現(xiàn)操作系統(tǒng)提供的子功能，它是操作系統(tǒng)與用戶的編程接口 。在單cpu系統(tǒng)中，任何時(shí)候最多只能有一個(gè)進(jìn)程處于運(yùn)行狀態(tài)。 （2）進(jìn)程具有并行特征（獨(dú)立性、異步性），程序則沒(méi)有。如果S0,則把該進(jìn)程的狀態(tài)置為阻塞態(tài)，把相應(yīng)的PCB連入該信號(hào)量隊(duì)列的末尾，并放棄處理機(jī)，進(jìn)行等待（直到其他進(jìn)程在S上執(zhí)行V操作，把它釋放出來(lái)為止）。答：這是一個(gè)生產(chǎn)者/消費(fèi)者問(wèn)題，而且每個(gè)進(jìn)程既是生產(chǎn)者，也是消費(fèi)者。假定三個(gè)隊(duì)列的初值分別為n1,n2,n3。為了很好地利用它，讀者進(jìn)入時(shí)必須先在登記表上進(jìn)行登記。(2’)同步算法描述如下： procedure goriver() begin L:P(S1)。解：這是典型的讀者——寫者問(wèn)題，查詢信息的用戶是讀者，訂票用戶是寫者，并且要求寫者優(yōu)先。請(qǐng)用P、V操作為三進(jìn)程的正確執(zhí)行寫出同步算法。 循環(huán)等待條件——存在一個(gè)進(jìn)程等待序列{P1,P2,…,Pn}，其中，P1等待P2所占有的某個(gè)資源，P2等待P3所占有的某個(gè)資源，……，而Pn等待P1所占有的某個(gè)資源，從而形成一個(gè)進(jìn)程循環(huán)等待。②在T0時(shí)刻，若進(jìn)程P2請(qǐng)求資源（0，3，4），能否實(shí)現(xiàn)資源分配？為什么？③在②的基礎(chǔ)上，若進(jìn)程P4請(qǐng)求資源（2，0，1），能否實(shí)現(xiàn)資源分配？為什么?④在③的基礎(chǔ)上，若進(jìn)程P1請(qǐng)求資源（0，2，0），能否實(shí)現(xiàn)資源分配？為什么?表39 T0時(shí)刻系統(tǒng)狀態(tài)進(jìn)程 最大資源需求量 已分配資源數(shù)量 系統(tǒng)剩余資源數(shù)量 A B C A B C A B CP1 5 5 9 2 1 2 2 3 3P2 5 3 6 4 0 2 P3 4 0 11 4 0 5 P4 4 2 5 2 0 4 P5 4 2 4 3 1 4 解：①T0時(shí)刻是安全狀態(tài)，因?yàn)榇嬖谝粋€(gè)安全序列{P4,P5,P1,P2,P3} (2’)②不能實(shí)現(xiàn)資源分配，因?yàn)樗Ｓ嗟馁Y源數(shù)量不夠。次序 進(jìn)程 申請(qǐng)量 次序 進(jìn)程 申請(qǐng)量1 P1 3 5 P2 22 P2 2 6 P1 33 P3 4 7 P3 34 P1 2 8 P2 2解：1）計(jì)算第5次分配后進(jìn)程的狀態(tài)和占用資源情況：(`5’=1’*5)① p1申請(qǐng)3個(gè)，滿足，系統(tǒng)還剩7個(gè)②p2申請(qǐng)2個(gè)，滿足（因?yàn)橄到y(tǒng)的7個(gè)可以使p2運(yùn)行完），系統(tǒng)還剩5個(gè)③p3申請(qǐng)4個(gè)，因?yàn)槿魸M足它的請(qǐng)求，可能使以后的任何進(jìn)程都不能運(yùn)行完，故p3等待④p1申請(qǐng)2個(gè)，滿足（系統(tǒng)還剩5個(gè)可以滿足p1的最大請(qǐng)求），系統(tǒng)還剩3個(gè)⑤ p2申請(qǐng)2個(gè)，不能滿足，等待。由此可見(jiàn)，p2請(qǐng)求的25個(gè)資源可以滿足，且能找到完成序列：p3，p1，p2，p4，…(4’)(2) 當(dāng)p4再提出35個(gè)資源請(qǐng)求時(shí)，系統(tǒng)還剩15，顯然不能滿足它的請(qǐng)求，讓其阻塞等待。5進(jìn)程調(diào)度也稱低級(jí)調(diào)度程序，它完成進(jìn)程從就緒狀態(tài)到運(yùn)行狀態(tài)的轉(zhuǎn)化。而進(jìn)程則是完成用戶任務(wù)的執(zhí)行實(shí)體，是向系統(tǒng)申請(qǐng)分配資源的基本單位。進(jìn)程調(diào)度從就緒隊(duì)列中選出一個(gè)進(jìn)程來(lái)，并把它的狀態(tài)改為運(yùn)行態(tài)，把cpu分配給它。 當(dāng)6x=9時(shí)，作業(yè)的運(yùn)行順序應(yīng)為C(3),D(5),B(6),E(x),A(9)。13固定分區(qū)法內(nèi)存中分區(qū)的個(gè)數(shù)固定不變，各個(gè)分區(qū)的大小也固定不變，但不同分區(qū)的大小可以不同，每個(gè)分區(qū)只可裝入一道作業(yè)。為了提高地址變換速度，在地址變換機(jī)構(gòu)中增設(shè)一個(gè)具有并行查找能力的高速緩沖存儲(chǔ)器，用以存放當(dāng)前訪問(wèn)的頁(yè)表項(xiàng)。當(dāng)調(diào)度該進(jìn)程在cpu上執(zhí)行時(shí)，操作系統(tǒng)就自動(dòng)將該進(jìn)程在內(nèi)存的起始地址裝入基址寄存器，將進(jìn)程的大小裝入限長(zhǎng)寄存器 。 頁(yè)表的作用是:實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射。 操作系統(tǒng)監(jiān)督每個(gè)進(jìn)程的工作集，并給它分配工作集所需的內(nèi)存塊。答：虛地址0A3CH轉(zhuǎn)換成十進(jìn)制數(shù)為2620，每個(gè)頁(yè)為200H，即512B，由2620/512可得，頁(yè)號(hào)為5，頁(yè)內(nèi)地址為60。1） 該作業(yè)運(yùn)行中總共出現(xiàn)多少次缺頁(yè)？2） 若每個(gè)作業(yè)進(jìn)程在主存擁有4頁(yè)，又將產(chǎn)生多少次缺頁(yè)？3） 如何解釋所出現(xiàn)的現(xiàn)象？解：先進(jìn)先出算法的實(shí)質(zhì)是：總是選擇作業(yè)中在主存駐留時(shí)間最長(zhǎng)的一頁(yè)進(jìn)行淘汰。3）如果物理空間減少一半時(shí)，主存地址需要19位表示，仍大于邏輯空間的大小，故頁(yè)表結(jié)構(gòu)可以不變。這樣10，205，110，735，603，50，815，314，432，320，225，80，130，720，通過(guò)除以頁(yè)的大小100，頁(yè)號(hào)分別為0，2，1，7，6，0，8，3，4，2，0，1，2。 11何謂工作集？它有什么作用？答：工作集是一個(gè)進(jìn)程在某一小段時(shí)間內(nèi)訪問(wèn)頁(yè)面的集合。 ②頁(yè)面的大小由系統(tǒng)確定，并且各頁(yè)大小都相同；各段長(zhǎng)度因段而已，由用戶決定。內(nèi)部碎片和外部碎片出現(xiàn)的位置不同 。這種現(xiàn)象就叫做程序局部性原理。9外部碎片在所有分區(qū)之外新產(chǎn)生的碎片稱作外部碎片，如在動(dòng)態(tài)分區(qū)法實(shí)施過(guò)程中出現(xiàn)的越來(lái)越多的小空閑塊，由于它們太小，無(wú)法裝入一個(gè)小進(jìn)程，因而被浪費(fèi)掉。試問(wèn)采用哪種運(yùn)行次序使得平均響應(yīng)時(shí)間為最短？（答案依賴于x）解答：由于短作業(yè)優(yōu)先調(diào)度算法可以使作業(yè)的平均周轉(zhuǎn)時(shí)間最短，同樣使作業(yè)的平均響應(yīng)時(shí)間為最短。實(shí)際上，進(jìn)程調(diào)度完成一臺(tái)物理的CPU轉(zhuǎn)變成多臺(tái)虛擬機(jī)（或邏輯）的CPU的工作，進(jìn)程調(diào)度的實(shí)現(xiàn)策略往往決定了操作系統(tǒng)的類型，其算法優(yōu)劣直接影響整個(gè)系統(tǒng)的性能。一個(gè)作業(yè)的完成要經(jīng)過(guò)作業(yè)提交、作業(yè)收容、作業(yè)執(zhí)行和作業(yè)完成4個(gè)階段。(1’)名詞解釋1作業(yè)用戶在一次上機(jī)過(guò)程中要求計(jì)算機(jī)系統(tǒng)所做工作的集合。如不安全，請(qǐng)說(shuō)明原因。 (2’)3系統(tǒng)有同類資源10個(gè)，進(jìn)程pp2和p3需要該類資源的最大數(shù)量分別為8，6，7。 綜合題1設(shè)系統(tǒng)中有三種類型的資源（A,B,C）和五個(gè)進(jìn)程（P1,P2,P3,P4,P5）,A資源的數(shù)量為17，B資源的數(shù)量為5，C資源的數(shù)量為20。2簡(jiǎn)述發(fā)生死鎖的四個(gè)必要條件?答： 四個(gè)必要條件是：互斥條件、占有且等待條件（請(qǐng)求保持條件）、不可搶占條件（非剝奪條件）和循環(huán)等待條件（環(huán)路條件）。(2’) x = 5。各用戶可以同時(shí)查詢信息，若有一個(gè)用戶要訂票，須更新數(shù)據(jù)庫(kù)時(shí)，其余所有用戶都不可以訪問(wèn)數(shù)據(jù)庫(kù)。過(guò)河時(shí)，只要對(duì)岸無(wú)人過(guò)，就可以過(guò)；但不允許河對(duì)岸的兩個(gè)人同時(shí)過(guò)，以防止出現(xiàn)死鎖。empty:=100。2設(shè)用三個(gè)隊(duì)列管理緩沖區(qū)池的使用情況，分別為空白緩沖隊(duì)列em，輸入緩沖隊(duì)列in，以及輸出緩沖隊(duì)列out。就是說(shuō)，管程自身能有效地實(shí)現(xiàn)互斥。（2分）信號(hào)量通?？梢院?jiǎn)單反映出相應(yīng)資源的使用情況，它與P、V操作原語(yǔ)一起使用可實(shí)現(xiàn)進(jìn)程的同步和互斥。 因?yàn)閭翁幚頇C(jī)的概念只有在執(zhí)行時(shí)才存在，它表示多個(gè)進(jìn)程在單處理機(jī)上并發(fā)執(zhí)行的一個(gè)調(diào)度單位。11進(jìn)程控制塊進(jìn)程控制塊是進(jìn)程存在的唯一標(biāo)識(shí)，它保存了系統(tǒng)管理和控制進(jìn)程所必須的信息，是進(jìn)程動(dòng)態(tài)特性的集中表現(xiàn)。過(guò)程調(diào)用在用戶程序中調(diào)用，并直接在用戶空間內(nèi)執(zhí)行；而系統(tǒng)調(diào)用可以在用戶程序中調(diào)用，但是在用戶程序中執(zhí)行到系統(tǒng)調(diào)用時(shí)，會(huì)產(chǎn)生異常事件。假定有如下的應(yīng)用環(huán)境，請(qǐng)你為它們選擇適合的操作系統(tǒng)。14聯(lián)機(jī)I/O是指作業(yè)的輸入、調(diào)入內(nèi)存及結(jié)果輸出都在cpu直接控制下進(jìn)行。2管態(tài)當(dāng)執(zhí)行操作系統(tǒng)程序時(shí)，處理機(jī)所處的狀態(tài)3目態(tài)當(dāng)執(zhí)行普通用戶程序時(shí)，處理機(jī)所處的狀態(tài)。11特權(quán)指令指指令系統(tǒng)中這樣一些指令，如啟動(dòng)設(shè)備指令、設(shè)置時(shí)鐘指令、中斷屏蔽指令和清內(nèi)存指令，這些指令只能由操作系統(tǒng)使用。多道程序隱含了多任務(wù)處理，但多任務(wù)系統(tǒng)中不一定有多道程序。②運(yùn)行狀態(tài)不同。8臨界區(qū)在每個(gè)進(jìn)程中訪問(wèn)臨界資源的那段程序。然而，進(jìn)程與程序之間存在密切關(guān)系，進(jìn)程的功能是通過(guò)程序的運(yùn)行得以實(shí)現(xiàn)的，進(jìn)程活動(dòng)的主體是程序。如已有進(jìn)程進(jìn)入自己的臨界區(qū)，則其他所有試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待③ 進(jìn)入臨界區(qū)的進(jìn)程要在有限的時(shí)間內(nèi)退出，以便讓其他進(jìn)程能及時(shí)進(jìn)入自己的臨界區(qū)④ 如果進(jìn)程不能進(jìn)入自己的臨界區(qū)，則應(yīng)讓出cpu，避免進(jìn)程出現(xiàn)“忙等”現(xiàn)象.8簡(jiǎn)述信號(hào)量的定義和作用。10什么是管程？它由哪幾部分組成？有什么基本特性?答：一個(gè)管程定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程在其上執(zhí)行的一組操作，這組操作能同步進(jìn)程和改變管程中的數(shù)據(jù)。 (2’) Cobegin (`6’=2’*3) P0 P1 P2 begin begin begin P(B0S2) P(B1S2) P(B2S2) 從B0取一個(gè)數(shù)據(jù) 從B1取一個(gè)數(shù)據(jù) 從B2取一個(gè)數(shù)據(jù) V(B0S2) V(B1S1) V(B2S1) 加工 加工 加工 P(B1S1) P(B2S1) P(B0S1) 將加工結(jié)果送B1 將加工結(jié)果送B2 將加工結(jié)果送B0 V(B1S2) V(B2S2) V(B0S2) end end end coend這道題也可以增加互斥信號(hào)量，以便P0與P1之間互斥使用B0緩沖區(qū)