【正文】 在主存忠為每一個(gè)作業(yè)進(jìn)程開辟3頁。缺頁次數(shù)為12次 (2’)4某請(qǐng)求頁式管理系統(tǒng)，用戶編程空間有40個(gè)頁面，每個(gè)頁面為200H字節(jié)。 12什么是頁面抖動(dòng)？系統(tǒng)怎樣檢測(cè)是否出現(xiàn)抖動(dòng)？一旦檢測(cè)到抖動(dòng)？系統(tǒng)如何消除它？答：頁面抖動(dòng)是系統(tǒng)頻繁進(jìn)行頁面置換的現(xiàn)象。 ④分頁的活動(dòng)對(duì)用戶是不可見的，而分段是用戶可見的活動(dòng)。外部碎片出現(xiàn)在所有分區(qū)之外，是新增的小分區(qū)，如在動(dòng)態(tài)分區(qū)法實(shí)施過程中會(huì)出現(xiàn)外部碎片 。在分頁系統(tǒng)中，由于頁表是存放在主存中的，因此cpu存取一個(gè)數(shù)據(jù)時(shí)要訪問兩次主存。11緊縮移動(dòng)某些已分區(qū)的內(nèi)容，使所有作業(yè)的分區(qū)緊挨在一起，而把空閑區(qū)留在另一端，這種技術(shù)稱為緊縮。 當(dāng)3x5時(shí)，作業(yè)的運(yùn)行順序應(yīng)為C(3),E(x),D(5),B(6),A(9)。另外，進(jìn)程調(diào)度相當(dāng)頻繁，而作業(yè)調(diào)度執(zhí)行的次數(shù)一般很少。 其主要區(qū)別關(guān)系如下： （1）作業(yè)是用戶向計(jì)算機(jī)提交任務(wù)的任務(wù)實(shí)體。3響應(yīng)時(shí)間是分時(shí)系統(tǒng)的一個(gè)技術(shù)指標(biāo)，指從用戶輸入命令到系統(tǒng)對(duì)命令開始執(zhí)行和顯示所需要的時(shí)間。解答：系統(tǒng)當(dāng)前剩余資源量為：150 – 25 – 40 – 45 = 40 (2’)(1) 可以滿足(2’)，假定先分配p4的25個(gè)資源，系統(tǒng)還剩15個(gè)。1） 試給出采用銀行家算法分配資源時(shí)，進(jìn)行第5次分配后各進(jìn)程的狀態(tài)及各進(jìn)程占用資源情況。系統(tǒng)采用銀行家算法來避免死鎖。 占有且等待條件——進(jìn)程至少已經(jīng)占有一個(gè)資源，但又申請(qǐng)新的資源。 z = 9 (6’)11 M8M7M6M5M4M3M2試用信號(hào)量機(jī)制來描述下述前趨圖M1 解答：首先定義信號(hào)量S12,S13,S14,S26,S36,S47,S57,S38,S78的初值都為0，分別表示相對(duì)應(yīng)的進(jìn)程是否完成：(2’)COBEGIN (`8’=1’*8)Process M1:begin V(S12) V(S13) V(S14) endProcess M2:begin P(S12) V(26) endProcess M3:begin P(S13) V(S36) V(S38) endProcess M4:beginP(S14) V(S47) endProcess M5:begin V(S57) endProcess M6:begin P(S26) P(S36) endProcess M7:begin P(S47) P(S57) P(S78) endProcess M8:begin P(S38) P(S78) end COEND12 M6M4M3M5M2試用信號(hào)量機(jī)制來描述下述前趨圖M1 解答：首先定義信號(hào)量S12,S13,S24,S25,S56,S46,S36的初值都為0，分別表示相對(duì)應(yīng)的進(jìn)程是否完成(2’)：COBEGIN (`6’=1’*6)Process M1:begin V(S12) V(S13) endProcess M2:begin P(S12) V(24) V(25) endProcess M3:begin P(S13) V(S36) endProcess M4:begin P(S14) V(S46) endProcess M5:begin P(S25) V(S56) endProcess M6:begin P(S36)P(S46) P(S56) end COEND13設(shè)系統(tǒng)有三個(gè)并發(fā)進(jìn)程R,C,P，共享一個(gè)能存放n個(gè)數(shù)據(jù)的環(huán)形緩沖區(qū)buf。要求：當(dāng)一個(gè)用戶訂票而需要更新數(shù)據(jù)庫時(shí)，不能因不斷有查詢者到來而使其長時(shí)間等待。解：假設(shè)一座橋由N個(gè)橋墩，也即最多允許有N個(gè)人同向過河，用一個(gè)計(jì)數(shù)器R記錄同時(shí)過河的人數(shù)(2’)。begin p(empty) p(mutex) 進(jìn)入廳內(nèi)購票,購票后退出 v(empty) v(mutex)end. 4某招待所有100個(gè)床位，住宿者入住要先登記（在登記表上填寫姓名和床位號(hào)）．離去時(shí)要注銷登記（在登記表上刪去姓名和床位號(hào)）．請(qǐng)給出住宿登記及注銷過程的算法描述．答：某招待所有100個(gè)床位，為了正確管理，引入一個(gè)信號(hào)量empty代表空床位數(shù)，初值為100；住宿者入住要先登記（在登記表上填寫姓名和床位號(hào)），顯然，登記表是一個(gè)臨界資源，必須互斥訪問，引入一個(gè)mutex，其初值為1。試描述進(jìn)程從任一緩沖隊(duì)列中得到一個(gè)緩沖區(qū)的過程get_buf(type,numb)和釋放一個(gè)緩沖區(qū)numb進(jìn)入緩沖隊(duì)列的過程put_buf(type,numb)。初始時(shí)，僅緩沖區(qū)0有一個(gè)消息。P(S)順序執(zhí)行下述兩個(gè)動(dòng)作（1分）：⑴信號(hào)量的值減1，即S=S1。這些并發(fā)進(jìn)程就相當(dāng)于由偽處理機(jī)執(zhí)行的程序。13就緒態(tài)進(jìn)程已經(jīng)獲得了除cpu之外的全部資源，等待系統(tǒng)分配cpu，一旦獲得cpu，進(jìn)程就可以變?yōu)檫\(yùn)行態(tài)。 12試說明特權(quán)指令和系統(tǒng)調(diào)用之間的區(qū)別與聯(lián)系。其主要特征是：用戶脫機(jī)使用計(jì)算機(jī)、成批處理、多道程序運(yùn)行。例如，多個(gè)進(jìn)程同時(shí)占用內(nèi)存，從而對(duì)內(nèi)存共享；它們并發(fā)執(zhí)行時(shí)對(duì)cpu進(jìn)行共享；各個(gè)進(jìn)程在執(zhí)行過程中提出對(duì)文件的讀寫請(qǐng)求，從而對(duì)磁盤進(jìn)行共享等等。這些作業(yè)共享CPU和系統(tǒng)中的其他資源。每一個(gè)子功能稱作一條系統(tǒng)調(diào)用命令。5試說明多道程序設(shè)計(jì)和多任務(wù)系統(tǒng)之間的關(guān)系答：多道程序設(shè)計(jì)是利用外設(shè)與cpu能夠并行處理的特性，在主存同時(shí)存放多個(gè)程序，使之在系統(tǒng)中交叉地使用cpu，從而提高系統(tǒng)資源的利用率。 11系統(tǒng)調(diào)用與過程調(diào)用在功能及實(shí)現(xiàn)上有什么相同點(diǎn)和不同點(diǎn)？答：相同點(diǎn)：兩者都由程序代碼構(gòu)成，可直接用高級(jí)程序設(shè)計(jì)語言（如C,C++和Perl語言）來編制；使用方式相同——以函數(shù)調(diào)用的形式出現(xiàn)，調(diào)用時(shí)傳送參數(shù)。也就是說，這些具有伙伴關(guān)系的進(jìn)程在執(zhí)行次序上必須遵循確定的規(guī)律。為此，人們引入了“進(jìn)程（Process）”這一概念來描述程序動(dòng)態(tài)執(zhí)行過程的性質(zhì)。 進(jìn)程間的同步是指：異步環(huán)境下的一組并發(fā)進(jìn)程因直接制約相互發(fā)送消息而進(jìn)行相互合作、相互等待，是各進(jìn)程按一定的速度執(zhí)行的過程。④ 線程在執(zhí)行過程中，需要協(xié)作同步。B2S1=2。試問：1） 購票者之間是同步還是互斥？用P、V操作表達(dá)購票者的工作過程。下面用兩個(gè)過程描述對(duì)表格應(yīng)執(zhí)行的動(dòng)作： 登記過程：(`2’) 擦除過程：(`2’) begin begin P(empty) P(mutex) P(mutex) 找到自己的登記項(xiàng)擦除 找到一個(gè)登記項(xiàng)登記 V(mutex) V(mutex) V(empty) end end 為了正確地描述讀者的動(dòng)作，可以將讀者看成進(jìn)程。 P(S1)?！?1’)　　意義：(`3’=1’*3)　　S0　S的值表示可繼續(xù)進(jìn)入售票廳的人數(shù)　　　S=0　表示售票廳中已有20名顧客(購票者)　　　S0　|S|的值為等待進(jìn)入售票廳的人數(shù)　　(2)上空格為P(S) (2’) ；下空格為V(S)　(2’)　(3)S的最大值為20 (1’ )；S的最小值為20－n　(1’ )9在公共汽車上，司機(jī)和售票員各行其職，司機(jī)負(fù)責(zé)開車和到站停車；售票員負(fù)責(zé)售票和開門關(guān)門，當(dāng)售票員關(guān)好車門后，駕駛員才能開車行使。就是說，在資源分配過程中若預(yù)測(cè)有發(fā)生死鎖的可能性，則加以避免。 若存在循環(huán)等待，設(shè)在環(huán)路上的一組進(jìn)程為{P0,P1,P2,…,Pn}，這里Pi等待進(jìn)程Pi+1占有資源Ri（下角標(biāo)取模運(yùn)算，從而，Pn等待p0占有的資源）。若找不到,可先求出進(jìn)程的剩余請(qǐng)求矩陣. 進(jìn)程 資源最大需求 已分配資源 剩余資源請(qǐng)求 P0 7, 5, 3 0, 1, 0 7, 4, 3 P1 3, 2, 2 2, 1, 0 1, 1, 2 P2 9, 0, 2 3, 0, 2 6, 0, 0 P3 2, 2, 2 2, 1, 1 0, 1, 1 P4 4, 3, 3 0, 0, 2 4, 3, 1 系統(tǒng)剩余資源向量A=(3,2,2)，在進(jìn)程剩余資源請(qǐng)求矩陣中找，是否有一行，選進(jìn)程P1，滿足它的全部資源請(qǐng)求，它在有限時(shí)間內(nèi)能釋放全部資源，并標(biāo)記它為完成使系統(tǒng)剩余資源向量A=(5,3,2).之后再重復(fù)上述過程，從而找到了一個(gè)進(jìn)城完成序列為：P1,P3,P4,P2,P0 (2’)。P2申請(qǐng)2個(gè)，系統(tǒng)滿足它，p2接著運(yùn)行；p2完成，釋放資源，使系統(tǒng)資源變?yōu)?個(gè)。如果能找到一個(gè)安全序列，就可以真正進(jìn)行分配。這種調(diào)度方式實(shí)現(xiàn)簡單，系統(tǒng)開銷小，但系統(tǒng)性能不夠好。3高級(jí)調(diào)度與低級(jí)調(diào)度的主要功能是什么？為什么要引入中級(jí)調(diào)度？答:高級(jí)調(diào)度的主要功能是根據(jù)一定的算法,從輸入的一批作業(yè)中選出若干作業(yè),分配必要的資源,如內(nèi)存、外設(shè)等，為它建立相應(yīng)的用戶作業(yè)進(jìn)程和為其服務(wù)的系統(tǒng)進(jìn)程（如輸入/輸出進(jìn)程），最后把它們的程序和數(shù)據(jù)調(diào)入內(nèi)存，等待進(jìn)程調(diào)度程序?qū)ζ鋱?zhí)行調(diào)度，并在作業(yè)完成后做善后處理工作。表49 作業(yè)列表作業(yè)名 到達(dá)時(shí)間 預(yù)估計(jì)時(shí)間（分鐘） 優(yōu)先數(shù)A 8:00 40 10B 8:20 30 5C 8:30 50 8D 8:50 20 12其中給出的作業(yè)優(yōu)先數(shù)即為相應(yīng)進(jìn)程的優(yōu)先數(shù)。5重定位把邏輯地址轉(zhuǎn)變?yōu)閮?nèi)存物理地址的過程叫做重定位。由于所有這些頁面都正在使用，所以剛被淘汰出去的頁很快又被訪問，因而要把它重新調(diào)入。簡答題1解釋固定分區(qū)法和動(dòng)態(tài)分區(qū)法的基本原理。 5引入虛擬存儲(chǔ)器后，除了獲得主存“擴(kuò)充”的好處，還有什么好處？答：引入虛存后，程序的地址空間都是虛地址的集合，只有在程序運(yùn)行中通過硬件地址轉(zhuǎn)換機(jī)構(gòu)和操作系統(tǒng)的相應(yīng)軟件，才能將虛地址變換成主存的實(shí)地址，這將為主存的分配帶來更大的靈活性。 請(qǐng)求分頁技術(shù)是在簡單分頁技術(shù)基礎(chǔ)上發(fā)展起來的，兩者根本區(qū)別是：請(qǐng)求分頁提供虛擬存儲(chǔ)器，而簡單分頁系統(tǒng)并未提供虛擬存儲(chǔ)器。如果采用LRU算法，缺頁率是多少？如果采用最優(yōu)淘汰算法，其缺頁率又是多少？解: 該序列的頁面走向?yàn)椋?、0、3。1） 寫出邏輯地址的格式2） 若不考慮訪問權(quán)限位，進(jìn)程的頁表有多少項(xiàng)？每項(xiàng)至少多少位？3） 如果物理空間減少一半，頁表結(jié)構(gòu)應(yīng)作怎樣的改？答：1）邏輯空間32頁，占5個(gè)二進(jìn)制位。若快表的命中率是85%，則有效存取時(shí)間為多少？若快表命中率為50%，那么有效存取時(shí)間為多少？解答：（1）分頁需要訪問2次，第一次訪問頁表，第二次執(zhí)行訪內(nèi)操作(2’)；分段需要訪問2次，第一次訪問段表，第二次執(zhí)行訪內(nèi)操作；段頁式需要訪問3次，第一次訪問段表，第二次訪問頁表，第三次執(zhí)行訪內(nèi)操作(2’)。(3’)因此地址為8762的物理地址為14*512+58=7226。綜合題1考慮下面頁面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6 當(dāng)內(nèi)存塊數(shù)量分別為3時(shí)，試問LRU,FIFO,OPT三種置換算法的缺頁次數(shù)各是多少？（注意，所有內(nèi)存最初都是空的，凡第1次用到的頁面都產(chǎn)生一次缺頁）答：LRU1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 61 1 1 4 4 4 5 5 5 1 1 1 7 7 7 2 2 2 2 2 2 2 2 2 1 1 1 2 2 2 2 2 6 6 6 1 1 1 6 3 3 3 3 3 6 6 6 6 3 3 3 3 3 3 3 3 3 (2’)FIFO1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 61 1 1 4 4 4 4 6 6 6 6 3 3 3 3 2 2 2 2 6 2 2 2 2 1 1 1 2 2 2 2 7 7 7 7 1 1 1 1 3 3 3 3 5 5 5 1 1 1 1 6 6 6 6 6 3 3 (2’)OPT1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2