1、精選優(yōu)質(zhì)文檔-傾情為你奉上習題一1、舉例說明為什么對并發(fā)執(zhí)行的程序不加控制會產(chǎn)生與執(zhí)行時間有關的錯誤?解:程序在并發(fā)執(zhí)行時由于資源是共享的,而且常常資源數(shù)少于程序?qū)@些資源的需求數(shù),致使這些并發(fā)執(zhí)行的程序之間因為競爭資源導致存在間接制約關系,這種間接制約使得并發(fā)執(zhí)行的程序具有隨機性(異步性),即“執(zhí)行暫停執(zhí)行”,它們何時啟動、何時停止是未知的。例如:飛機售票系統(tǒng)、堆棧的存數(shù)與取數(shù)過程等(示例說明略)。2、程序并發(fā)執(zhí)行為什么會失去順序執(zhí)行時的封閉性和可再現(xiàn)性?解:所謂“封閉性”是指程序執(zhí)行得到的最終結(jié)果由給定的初始條件決定,不受外界因素的影響。在程序并發(fā)執(zhí)行時由于資源共享,導致這些資源的狀態(tài)將由
2、多個程序來改變,又由于存在程序執(zhí)行的隨機性,所以程序的運行失去封閉性。由于失去了封閉性,也將導致其失去可再現(xiàn)性。即雖然它們執(zhí)行時的環(huán)境和初始條件相同,但得到的結(jié)果卻可能各不相同。習題二1、試用加鎖的方法解決飛機售票系統(tǒng)的問題。例:民航售票系統(tǒng),n個售票處2、用機器指令(testAndset)解決飛機售票系統(tǒng)中任一進程的算法。習題三1、進程在做P、V操作時對自己和其他進程有何影響?進程在信號量上執(zhí)行P操作后,若信號量的值為正,當前進程繼續(xù)執(zhí)行;若信號量的值為負,當前進程變?yōu)榈却隣顟B(tài)、放棄處理機,其它進程則有機會獲得CPU。 進程在信號量上執(zhí)行V操作后,不會對自己有任何影響,但當信號量的值不大于0
3、時,需要喚醒在該信號量上所對應的等待隊列中的進程。2、設課程的前驅(qū)、后繼關系如下,若每修一門課程看作進程Px(x1.6)試用P、V操作算法描述這種前驅(qū)與后繼關系。答:Semaphore:S1:=S2:=S3:=S4:=S5:=S6:=0;Begin Cobegin P1、P2、P3、P4、P5、P6 coend; end.P1() P2() P3()Begin begin begin 修計算機導論; P(S1); P(S2); V(S1); 修高級語言程序設計 修計算機組成原理; V(S2); V(S3) V(S4);End; End; End;P4() P5() P6()Begin begi
4、n begin P(S3); P(S4); P(S5); 修數(shù)據(jù)結(jié)構(gòu); 修86匯編語言; P(S6); V(S5); V(S6); 修操作系統(tǒng);End; End; End;習題四1、有三個進程 R、W1、W2,進程 R 從輸入設備上讀數(shù)據(jù)送緩沖區(qū) B,若是奇數(shù)由 W1 進程從 B 取數(shù)輸出;若是偶數(shù)則由 W2 進程從 B 取數(shù)輸出。設緩沖區(qū) B 只有一個單元,試用信號量機制設計實現(xiàn)算法。1、se,sf1,sf2:semaphore;se:=1;sf1:=sf2:=0; R()、W1()、W2()并發(fā)執(zhí)行Process R process W1 process W2repeat repeat r
5、epeat 讀數(shù); P(sf1); P(sf2); P(se); 從B中取數(shù); 從B中取數(shù); 送數(shù)到B; V(se); V(se); if B mod 2!=0 then until false until false V(sf1); else V(sf2);until false2、設有一臺計算機,掛有一臺輸入機和一臺打印機。現(xiàn)在從輸入機上把數(shù)據(jù)輸入到緩沖區(qū) B 中,處理程序處理后再把結(jié)果送到緩沖區(qū)B中,(設B只能放1個數(shù)據(jù))然后在打印機上輸出。問: (1)系統(tǒng)可設哪些進程來完成這一任務? (2)這些進程之間有什么樣的制約關系? (3)用 PV 操作寫出這些進程的同步算法. 答:(1) 輸入
6、進程、處理進程、輸出進程 (2) 處理進程不能在輸入進程之前執(zhí)行、輸出進程不能在處理進程之前執(zhí)行;輸入進程在未得到處理進程、輸出進程的消息前不能運行。 (3) 輸入()、處理()、輸出()進程并發(fā)執(zhí)行Semaphore:s1、s2、s3;S1:=1;S2:=S3:=0; process 輸入() process 處理() process 輸出() L1: 讀數(shù) L2: P(S2) L3: P(S3) P(S1) 從B取數(shù)處理后再送B 從B取數(shù)輸出 送數(shù)到B V(S3) V(S1) V(S2) Goto L2 Goto L3 Goto L1 習題五1、設系統(tǒng)中有 M 個資源,N 個進程,每個進程
7、都要求 K 個資源;若 M=5、N=5、K=2,問:(1)如何分配會導致死鎖?(2)要不死鎖應該如何分配? 如果對每個進程平均分配1個資源,則系統(tǒng)中的可用資源為 0,而每個進程都還需要1個資源,才能向前推進;因此、系統(tǒng)發(fā)生死鎖。 只要保證有1個進程能獲得2個資源,則它在有限的時間內(nèi)就可以運行完成并釋放資源,這樣系統(tǒng)就不會死鎖。例如、先給4個進程各分配1個資源,讓它們先運行,通過安全性算法測試可以知道第5個進程的資源申請將被拒絕;再把最后1個資源分配給這4個進程中的1個即可。2、假設甲、乙、丙三個并發(fā)進程間的PV操作同步算法如下所示, 信號量S1,S2,S3 的初值都為1,問這些算法在什么情況下
8、發(fā)生死鎖?如何防止死鎖? 甲 乙 丙 . . .L1:P(S1) L2:P(S2) L3:P(S3) P(S2) P(S3) P(S1) . . . V(S2) V(S3) V(S1) V(S1) V(S2) V(S3) . . . goto L1 goto L2 goto L3答:甲P(S1)后暫停、乙P(S2) 后暫停、丙P(S3) 后暫停 采用按序分配,丙改為P(S1)、P(S3)。也可以改甲或乙進程的P、V操作次序,以限制進程的并發(fā)執(zhí)行。習題六1.設有5個哲學家,共享一張放有五把椅子的桌子,每人分得一把椅子。但是,桌子上總共只有5支筷子,在每人兩邊分開各放一支。哲學家們在肚子饑餓時才試
9、圖分兩次從兩邊拾起筷子就餐。條件:(1) 只有拿到兩支筷子時,哲學家才能吃飯。(2) 如果筷子已在他人手上,則該哲學家必須等待到他人吃完之后才能拿到筷子。(3) 任一哲學家在自己未拿到兩支筷子吃飯之前,決不放下自己手中的筷子。試:(1)描述一個保證不會出現(xiàn)兩個鄰座同時要求吃飯的通信算法。(2)描述一個既沒有兩鄰座同時吃飯,又沒有人餓死(永遠拿不到筷子)的算法。(3) 在什么情況下,5 個哲學家全部吃不上飯? 答:使用非對稱解決 即奇數(shù)號的哲學家先拿起他左邊的筷子,接著拿起他右邊的筷子,而偶數(shù)號的哲學家先拿起他右邊的筷子,接著再拿他左邊的筷子。(1)設信號量c0c4,初始值均為1,分別表示i號筷
10、子被拿(i=0,1,2,3,4),send(i):第i個哲學家要吃飯beginthink;P(ci); P(ci+1 mod 5);eat;V(ci+1 mod 5); V(ci);End;該過程能保證兩鄰座不同時吃飯,但會出現(xiàn)5個哲學家一人拿一只筷子,誰也吃不上飯的死鎖情況(2)解決的思路:讓奇數(shù)號的哲學家先取右手邊的筷子,讓偶數(shù)號的哲學家先取左手邊的筷子.這樣,任何一個哲學家拿到一只筷子之后,就已經(jīng)阻止了他鄰座的一個哲學家吃飯的企圖,除非某個哲學家一直吃下去,否則不會有人會餓死.send(i): 第i個哲學家要吃飯Beginthink;If i mod 2=0 then P(ci); P(
11、ci+1mod 5)eat;V(ci; ci+1 mod 5) else P(ci+1 mod 5)P(ci)EatV(ci+1 mod 5)V(ci) End(3)非對稱解決,并發(fā)主程序略Program diningphilosophers; Var chopstick:array0.4 of semaphore(:=1),i:integer;Procedure philosopher(i:integer);BeginRepeatThink;If(i mod 2!=0) thenBeginP(chopsticki);P(chopstick(i+1) mod 5);吃面;V(chopstick
12、(i+1) mod 5);V(chopsticki);EndElseBeginP(chopstick(i+1) mod 5);P(chopsticki);吃面;V(chopstick(i+1) mod 5);V(chopsticki);EndForeverEnd習題七1、某程序在虛擬(邏輯)地址100處有一條取數(shù)指令LOAD 1,500 而500單元存放數(shù)據(jù)51888。若程序分配到的內(nèi)存地址為5000,試畫出下列方式下的該指令及數(shù)據(jù)的物理地址和變換過程。(1)靜態(tài)重定位(2)動態(tài)重定位2、若一個虛擬地址空間占8頁,每個頁大小為1024,需要映射到32個內(nèi)存塊上,試問:(1)虛擬地址要用多少位表
13、示?(2)物理地址要用多少位表示?答(1)邏輯地址需要的位數(shù):8*1024=23*210=213所以需要13位。(2)物理地址需要的位數(shù):32*1024=25*210=215所以需要15位。習題八1、在頁式存儲管理系統(tǒng)中某個時刻某個進程的頁表如下,設地址結(jié)構(gòu)為32位,頁號占據(jù)22位,試把邏輯地址0A5CH轉(zhuǎn)換成物理地址(以十六進制表示)。2、在靜態(tài)頁式下,內(nèi)存總量為65536字節(jié),每個存儲塊為4KB,一程序代碼段長32768字節(jié),數(shù)據(jù)段長16386字節(jié),堆棧段長15870字節(jié),規(guī)定不允許一個塊內(nèi)包含兩個段的內(nèi)容,請問能為該程序分配空間嗎?如果塊長為512字節(jié)呢? 答:習題九1.在某頁式虛擬存儲系統(tǒng)中,頁面大小為100個單元,某作業(yè)占有內(nèi)存塊數(shù)m=2,若它的訪問虛存邏輯地址序列為:55、135、96、227、42、156、330、169、11、252、253假設各個內(nèi)存塊初始為空,試問:(1)按OPT置換算法
評論
0/150
提交評論