【正文】 (2’)7關(guān)于存儲(chǔ)管理，試問：（1） 在分頁、分段和段頁式存儲(chǔ)管理中，當(dāng)訪問一條指令或數(shù)據(jù)時(shí)，需要訪問內(nèi)存幾次？各做什么處理？（2） 假設(shè)一個(gè)分頁存儲(chǔ)系統(tǒng)具有快表，多數(shù)活動(dòng)頁表都可以存在其中，頁表放在內(nèi)存中，內(nèi)存訪問時(shí)間是1us。1） 該作業(yè)運(yùn)行中總共出現(xiàn)多少次缺頁？2） 若每個(gè)作業(yè)進(jìn)程在主存擁有4頁，又將產(chǎn)生多少次缺頁？3） 如何解釋所出現(xiàn)的現(xiàn)象？解：先進(jìn)先出算法的實(shí)質(zhì)是：總是選擇作業(yè)中在主存駐留時(shí)間最長(zhǎng)的一頁進(jìn)行淘汰。3）如果物理空間減少一半時(shí)，主存地址需要19位表示，仍大于邏輯空間的大小，故頁表結(jié)構(gòu)可以不變。每頁2KB，占11位。查頁表可知，其主存塊號(hào)為14。答：虛地址0A3CH轉(zhuǎn)換成十進(jìn)制數(shù)為2620，每個(gè)頁為200H，即512B，由2620/512可得，頁號(hào)為5，頁內(nèi)地址為60。這樣10，205，110，735，603，50，815，314，432，320，225，80，130，720，通過除以頁的大小100，頁號(hào)分別為0，2，1，7，6，0，8，3，4，2，0，1，2。 (1’)FIFO0 1 0 3 1 2 4 30 0 0 3 3 3 4 2 1 1 1 1 2 2 3 (2’)LRU0 1 0 3 1 2 4 30 0 0 0 1 1 4 4 1 1 3 3 2 2 3 (2’)OPT0 1 0 3 1 2 4 30 0 0 3 3 3 3 3 1 1 1 1 2 4 4 (2’)算法 FIFO LRU OPT缺頁次數(shù) 6 7 5缺頁率 6/12= 7/12= 5/12= (3’)3設(shè)某頁系統(tǒng)中，頁幀大小為100字。被掛起的進(jìn)程將在以后適當(dāng)時(shí)機(jī)重新開始執(zhí)行。 操作系統(tǒng)監(jiān)督每個(gè)進(jìn)程的工作集，并給它分配工作集所需的內(nèi)存塊。 11何謂工作集？它有什么作用？答：工作集是一個(gè)進(jìn)程在某一小段時(shí)間內(nèi)訪問頁面的集合。10為什么分段技術(shù)比分頁技術(shù)更容易實(shí)現(xiàn)程序或數(shù)據(jù)的共享和保護(hù)？答： 每一段在邏輯上是相對(duì)完整的一組信息，分段技術(shù)中的共享是在段一級(jí)出現(xiàn)的。 8什么是belady現(xiàn)象？答：belady現(xiàn)象是指在使用FIFO算法進(jìn)行內(nèi)存頁面置換時(shí) ，在未給進(jìn)程或作業(yè)分配足它所要求的全部頁面的情況下，有時(shí)出現(xiàn)的分配的頁面數(shù)增多，缺頁次數(shù)發(fā)而增加的奇怪現(xiàn)象。 頁表的作用是:實(shí)現(xiàn)從頁號(hào)到物理塊號(hào)的地址映射。 ②頁面的大小由系統(tǒng)確定，并且各頁大小都相同；各段長(zhǎng)度因段而已，由用戶決定。另外，虛、實(shí)地址分開，用戶程序不能干擾實(shí)地址的生成，從而實(shí)現(xiàn)了存儲(chǔ)器的保護(hù) 。部分裝入——每個(gè)作業(yè)不是全部一次性地裝入內(nèi)存,而是只裝入一部分。當(dāng)調(diào)度該進(jìn)程在cpu上執(zhí)行時(shí)，操作系統(tǒng)就自動(dòng)將該進(jìn)程在內(nèi)存的起始地址裝入基址寄存器，將進(jìn)程的大小裝入限長(zhǎng)寄存器 。內(nèi)部碎片和外部碎片出現(xiàn)的位置不同 。答：固定分區(qū)法——內(nèi)存中分區(qū)的個(gè)數(shù)固定不變，各個(gè)分區(qū)的大小也固定不變，但不同分區(qū)的大小可以不同。22換頁指系統(tǒng)根據(jù)某種策略選擇某頁出主存，將某頁調(diào)入主存的過程。為了提高地址變換速度，在地址變換機(jī)構(gòu)中增設(shè)一個(gè)具有并行查找能力的高速緩沖存儲(chǔ)器，用以存放當(dāng)前訪問的頁表項(xiàng)。這種現(xiàn)象就叫做程序局部性原理。可是調(diào)入不久又再被淘汰出去，這樣再訪問，再調(diào)入，如此反復(fù)，使得整個(gè)系統(tǒng)的頁面替換非常頻繁，以致大部分機(jī)器時(shí)間都用在來回進(jìn)行的頁面調(diào)度上，只有一小部分時(shí)間用于進(jìn)程的實(shí)際運(yùn)算方面。17抖動(dòng)頁面抖動(dòng)是系統(tǒng)中頻繁進(jìn)行頁面置換的現(xiàn)象。13固定分區(qū)法內(nèi)存中分區(qū)的個(gè)數(shù)固定不變，各個(gè)分區(qū)的大小也固定不變，但不同分區(qū)的大小可以不同，每個(gè)分區(qū)只可裝入一道作業(yè)。9外部碎片在所有分區(qū)之外新產(chǎn)生的碎片稱作外部碎片，如在動(dòng)態(tài)分區(qū)法實(shí)施過程中出現(xiàn)的越來越多的小空閑塊，由于它們太小，無法裝入一個(gè)小進(jìn)程，因而被浪費(fèi)掉。6靜態(tài)重定位在目標(biāo)程序裝入內(nèi)存時(shí)所進(jìn)行的重定位。2邏輯地址用戶程序經(jīng)編譯之后的每個(gè)目標(biāo)模塊都以0為基地址順序編址，這種地址稱為邏輯地址。 當(dāng)6x=9時(shí)，作業(yè)的運(yùn)行順序應(yīng)為C(3),D(5),B(6),E(x),A(9)。試問采用哪種運(yùn)行次序使得平均響應(yīng)時(shí)間為最短？（答案依賴于x）解答：由于短作業(yè)優(yōu)先調(diào)度算法可以使作業(yè)的平均周轉(zhuǎn)時(shí)間最短，同樣使作業(yè)的平均響應(yīng)時(shí)間為最短。其數(shù)值越小，優(yōu)先級(jí)越高。表 作業(yè)列表作 業(yè) 運(yùn) 行 時(shí) 間 優(yōu) 先 級(jí)1 10 32 1 13 2 34 1 45 5 2作業(yè)到來的時(shí)間是按作業(yè)編號(hào)順序進(jìn)行的（即后面作業(yè)依次比前一個(gè)作業(yè)遲到一個(gè)時(shí)間單位）。進(jìn)程調(diào)度從就緒隊(duì)列中選出一個(gè)進(jìn)程來，并把它的狀態(tài)改為運(yùn)行態(tài)，把cpu分配給它。實(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)的性能。 低級(jí)調(diào)度的主要功能是根據(jù)一定的算法將cpu分派給就緒隊(duì)列中的一個(gè)進(jìn)程。（3）作業(yè)的概念主要用在批處理系統(tǒng)中。而進(jìn)程則是完成用戶任務(wù)的執(zhí)行實(shí)體，是向系統(tǒng)申請(qǐng)分配資源的基本單位。一個(gè)作業(yè)的完成要經(jīng)過作業(yè)提交、作業(yè)收容、作業(yè)執(zhí)行和作業(yè)完成4個(gè)階段。簡(jiǎn)答題1作業(yè)由哪幾部分組成？各有什么功能？答：作業(yè)由三部分組成：程序、數(shù)據(jù)和作業(yè)說明書。7剝奪式調(diào)度當(dāng)一個(gè)進(jìn)程正在執(zhí)行時(shí)，系統(tǒng)基于某種策略強(qiáng)行將處理機(jī)從占有者進(jìn)程剝奪而分配給另一個(gè)進(jìn)程的調(diào)度。5進(jìn)程調(diào)度也稱低級(jí)調(diào)度程序，它完成進(jìn)程從就緒狀態(tài)到運(yùn)行狀態(tài)的轉(zhuǎn)化。(1’) 第四章 調(diào)度名詞解釋1作業(yè)用戶在一次上機(jī)過程中要求計(jì)算機(jī)系統(tǒng)所做工作的集合。當(dāng)分配給P3一個(gè)資源時(shí)，系統(tǒng)剩余資源向量A=(1 ,2 ,2 , 0)?，F(xiàn)在需求出各進(jìn)程的剩余資源請(qǐng)求矩陣: (2’)(1) 詳細(xì)步驟省略。由此可見，p2請(qǐng)求的25個(gè)資源可以滿足，且能找到完成序列：p3，p1，p2，p4，…(4’)(2) 當(dāng)p4再提出35個(gè)資源請(qǐng)求時(shí)，系統(tǒng)還剩15，顯然不能滿足它的請(qǐng)求，讓其阻塞等待。如不安全，請(qǐng)說明原因。系統(tǒng)喚醒p3，滿足它的資源請(qǐng)求，最終p3完成，釋放資源，使資源數(shù)量恢復(fù)為10個(gè)。首先將p3喚醒，滿足它的4個(gè)資源，系統(tǒng)還剩4個(gè)，可以喚醒p2，滿足它的2個(gè)請(qǐng)求。次序 進(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è)，不能滿足，等待。 (2’)3系統(tǒng)有同類資源10個(gè)，進(jìn)程pp2和p3需要該類資源的最大數(shù)量分別為8，6，7。由此可見，系統(tǒng)狀態(tài)是安全的(2’)。(3’)2在銀行家算法中，系統(tǒng)有5個(gè)進(jìn)程和3個(gè)資源。②在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ù)量不夠。 綜合題1設(shè)系統(tǒng)中有三種類型的資源（A,B,C）和五個(gè)進(jìn)程（P1,P2,P3,P4,P5）,A資源的數(shù)量為17，B資源的數(shù)量為5，C資源的數(shù)量為20。由于Pi+1占有資源Ri,又申請(qǐng)資源Ri+1,從而一定存在F(i)F(i+1), 該式對(duì)所有的i都成立。 “系統(tǒng)是安全的”是指系統(tǒng)中的所有進(jìn)程能夠按照某種次序分配資源，并且依次運(yùn)行完畢。 循環(huán)等待條件——存在一個(gè)進(jìn)程等待序列{P1,P2,…,Pn}，其中，P1等待P2所占有的某個(gè)資源，P2等待P3所占有的某個(gè)資源，……，而Pn等待P1所占有的某個(gè)資源，從而形成一個(gè)進(jìn)程循環(huán)等待。2簡(jiǎn)述發(fā)生死鎖的四個(gè)必要條件?答： 四個(gè)必要條件是：互斥條件、占有且等待條件（請(qǐng)求保持條件）、不可搶占條件（非剝奪條件）和循環(huán)等待條件（環(huán)路條件）。這種方法的關(guān)鍵是確定資源分配的安全性。2饑餓在系統(tǒng)中，每個(gè)資源占有者都在有限時(shí)間內(nèi)釋放它所占有的資源，但資源中存在某些申請(qǐng)者由于某種原因卻永遠(yuǎn)得不到資源的一種錯(cuò)誤現(xiàn)象。請(qǐng)用P、V操作為三進(jìn)程的正確執(zhí)行寫出同步算法。(2’) x = 5。試用P/V操作實(shí)現(xiàn)司機(jī)與售票員間的同步?！　?2)根據(jù)所定義的信號(hào)量，把應(yīng)執(zhí)行的PV操作填入下述空格中，以保證進(jìn)程能夠正確地并發(fā)執(zhí)行。解：這是典型的讀者——寫者問題，查詢信息的用戶是讀者，訂票用戶是寫者，并且要求寫者優(yōu)先。各用戶可以同時(shí)查詢信息，若有一個(gè)用戶要訂票，須更新數(shù)據(jù)庫時(shí)，其余所有用戶都不可以訪問數(shù)據(jù)庫。 R=R1。 If R==1 P(S)。(2’)同步算法描述如下： procedure goriver() begin L:P(S1)。過河時(shí)，只要對(duì)岸無人過，就可以過；但不允許河對(duì)岸的兩個(gè)人同時(shí)過，以防止出現(xiàn)死鎖。若干讀者希望進(jìn)入閱覽室時(shí)，調(diào)用登記過程，退出閱覽室時(shí)，調(diào)用擦除過程(1’)。表中共有100項(xiàng)。為了很好地利用它，讀者進(jìn)入時(shí)必須先在登記表上進(jìn)行登記。empty:=100。解：1）購票者之間是互斥關(guān)系。(4’)當(dāng)有進(jìn)程希望從任一隊(duì)列取一個(gè)緩沖區(qū)時(shí)，過程get_buf(type,numb)的動(dòng)作如下： get_buf(type,numb) (`3’) begin p(s) p(mutex) numb=take_buf(type,numb) v(mutex) end當(dāng)有進(jìn)程希望向任一隊(duì)列送一個(gè)緩沖區(qū)時(shí)，過程put_buf(type,numb)的動(dòng)作如下： put_buf(type,numb) (`3’) begin p(mutex) add_buf(type,numb) v(mutex) v(s)end. 3設(shè)有一個(gè)售票廳，可容納100人購票。假定三個(gè)隊(duì)列的初值分別為n1,n2,n3。2設(shè)用三個(gè)隊(duì)列管理緩沖區(qū)池的使用情況，分別為空白緩沖隊(duì)列em，輸入緩沖隊(duì)列in，以及輸出緩沖隊(duì)列out。B2S2=0。B0S2=1。答：這是一個(gè)生產(chǎn)者/消費(fèi)者問題，而且每個(gè)進(jìn)程既是生產(chǎn)者，也是消費(fèi)者。就是說，管程自身能有效地實(shí)現(xiàn)互斥。不同進(jìn)程的線程間要利用消息通信的辦法實(shí)現(xiàn)同步。 線程和進(jìn)程之間有如下關(guān)系： ① 一個(gè)進(jìn)程可以有多個(gè)線程，但至少有一個(gè)線程；而一個(gè)線程只能在一個(gè)進(jìn)程的地址空間內(nèi)活動(dòng)。如果S0,則把該進(jìn)程的狀態(tài)置為阻塞態(tài)，把相應(yīng)的PCB連入該信號(hào)量隊(duì)列的末尾，并放棄處理機(jī)，進(jìn)行等待（直到其他進(jìn)程在S上執(zhí)行V操作，把它釋放出來為止）。（2分）信號(hào)量通?？梢院?jiǎn)單反映出相應(yīng)資源的使用情況，它與P、V操作原語一起使用可實(shí)現(xiàn)進(jìn)程的同步和互斥。7什么是臨界區(qū)和臨界資源？進(jìn)程進(jìn)入臨界區(qū)的調(diào)度原則是什么？答：臨界資源——一次僅允許一個(gè)進(jìn)程使用的資源臨界區(qū)——在每個(gè)進(jìn)程中訪問臨界資源的那段程序一個(gè)進(jìn)程進(jìn)入臨界區(qū)的調(diào)度原則是：① 如果有若干進(jìn)程要求進(jìn)入空閑的臨界區(qū)，一次僅允許一個(gè)進(jìn)程進(jìn)入② 任何時(shí)候，處于臨界區(qū)內(nèi)的進(jìn)程不可多于一個(gè)。進(jìn)程狀態(tài)轉(zhuǎn)換如下圖：運(yùn)行態(tài)進(jìn)程調(diào)度所需要的資源未被滿足（如等待 I/O）時(shí)間片到所需資源得到滿足（如I/O完成）運(yùn)行態(tài)運(yùn)行態(tài)5并發(fā)進(jìn)程間的制約有哪兩種？引起制約的原因是什么？答：并發(fā)進(jìn)程所受的制約有兩種：直接制約和間接制約。 （2）進(jìn)程具有并行特征（獨(dú)立性、異步性），程序則沒有。 因?yàn)閭翁幚頇C(jī)的概念只有在執(zhí)行時(shí)才存在，它表示多個(gè)進(jìn)程在單處理機(jī)上并發(fā)執(zhí)行的一個(gè)調(diào)度單位。 進(jìn)程和程序是兩個(gè)完全不同的概念。17同步機(jī)制同步機(jī)構(gòu)是負(fù)責(zé)處理進(jìn)程之間制約關(guān)系的機(jī)制，即操作系統(tǒng)中負(fù)責(zé)解決進(jìn)程之間協(xié)調(diào)工作的同步關(guān)系（直接制約關(guān)系），以及共享臨界資源的互斥關(guān)系（間接制約關(guān)系）的執(zhí)行機(jī)構(gòu)。在單cpu系統(tǒng)中，任何時(shí)候最多只能有一個(gè)進(jìn)程處于運(yùn)行狀態(tài)。11進(jìn)程控制塊進(jìn)程控制塊是進(jìn)程存在的唯一標(biāo)識(shí)，它保存了系統(tǒng)管理和控制進(jìn)程所必須的信息，是進(jìn)程動(dòng)態(tài)特性的集中表現(xiàn)。7臨界資源一次僅允許一個(gè)進(jìn)程使用的資源。4進(jìn)程程序在并發(fā)環(huán)境中的執(zhí)行過程。而系統(tǒng)調(diào)用不是機(jī)器指令，它往往以函數(shù)調(diào)用的形式出現(xiàn)，實(shí)現(xiàn)操作系統(tǒng)提供的子功能，它是操作系統(tǒng)與用戶的編程接口 。過程調(diào)用在用戶程序中調(diào)用，并直接在用戶空間內(nèi)執(zhí)行；而系統(tǒng)調(diào)用可以在用戶程序中調(diào)用，但是在用戶程序中執(zhí)行到系統(tǒng)調(diào)用時(shí)，會(huì)產(chǎn)生異常事件。 不同點(diǎn)：①代碼層次不同，過程調(diào)用不屬于操作系統(tǒng)的一部分，而系統(tǒng)調(diào)用是操作系統(tǒng)的一部分。它有較高的特權(quán)，可以執(zhí)行所有的指令，包括一般