計算機操作系統(tǒng)算法題（最全）

1、計算機操作系統(tǒng)算法題（最全） 6. 算法題（共32個題目） 200348. 在信號量機制中，若p（s）操作是可中斷的，則會有什么問題？ 此題答案為：答： p（s）的操作如下： begin s.value:= s.value-1; if s.value若p（s）可中斷的，例如進程a在執(zhí)行了語句之后從cpu上退下了，假定此時s.value0；這時換另一進程b，b又將s.value的值減1使之為1，在執(zhí)行語句時，b被阻塞；然后又換回a執(zhí)行，由于a的斷點是語句之后，當它執(zhí)行語句時，由于這時s.value已經(jīng)是1，故進程繼續(xù)執(zhí)行而被阻塞。這就出現(xiàn)了錯誤：本來a操作p（s）操作后，s.value0，是不應

2、該被阻塞的，現(xiàn)在卻被阻塞了。 200350. 何謂臨界區(qū)？下面給出的兩個進程互斥的算法是安全的嗎？為什么？ 1 define true; # define false; int flag2; flag1=flag2=false; enter-crtsec(i) int i; while(flag1-i) flagi=true; feave-crtsec(i) int i; flagi=false; process i; enter-crtsec(i); in critical section; leave-crtsec(i); 2 此題答案為：答：一次僅允許一個進程使用的資源稱為臨界資源，在進

3、程中對臨界資源訪問的程序段稱為臨界區(qū)。 從概念上講，系統(tǒng)中各進程在邏輯上是獨立的，它們可以按各自的速度向前推進。但由于它們共享某些臨界資源，因而產(chǎn)生了臨界區(qū)問題。對于具有臨界區(qū)問題的并發(fā)進程，它們之間必須互斥，以保證不會同時進入臨界區(qū)。 這種算法不是安全的。因為，在進入臨界區(qū)的enter-crtsec（）不是一個原語操作，如果兩個進程同時執(zhí)行完其循環(huán)（此前兩個flag均為false），則這兩個進程可同時進入臨界區(qū)。 200353. 某車站售票廳，任何時刻最多可容納20名購票者進入，當售票少于20名購票者時，則廳外的購票者可立即進入，否則需在外面等待。若把一個購票者看作一個進程，請回答下列問題：

4、 （1）用p、v操作管理這些并發(fā)進程時，應怎樣定義信號量？寫出信號量的初值以及信號量各種取值的含義。 （2）根據(jù)所定義的信號量，把應執(zhí)行的p、v操作填入下述程序中，以保證進程能夠正確地并發(fā)執(zhí)行。 cobegin process pi(i=1,2,) begin 進入售票廳； 購票； 退出； end; 3 coend (3)若欲購票者最多為n個人，寫出信號量可能的變化范圍（最大值和最小值）。 此題答案為：售票廳問題解答如下： （1）定義一信號量s，初始值為20。 s0 s的值表示可繼續(xù)進入售票廳的人數(shù)； s=0 表示售票廳中已有20名購票者； s（3）s的最大值為20，s的最小值為20n，n為某

5、一時刻需要進入售票廳的最多人數(shù)。 200362. 在批處理系統(tǒng)、分時系統(tǒng)和實時系統(tǒng)中，各采用哪幾個進程（作業(yè)）調(diào)度算法？ 此題答案為：答：（1）批處理系統(tǒng)中的作業(yè)調(diào)度算法有：先來先服務算法（fcfs）、短作業(yè)優(yōu)先算法（sjf）、優(yōu)先級調(diào)度算法（hpf）和高響應比優(yōu)先算法（rf）。批處理系統(tǒng)的進程調(diào)度算法有：先進先出算法（fifo）、短進程優(yōu)先算法（spf）、優(yōu)先級調(diào)度算法（hpf）和高響應比優(yōu)先算法（rf）。 （2）分時系統(tǒng)中只設有進程調(diào)度（不設作業(yè)調(diào)度），其進程調(diào)度算法只有輪轉(zhuǎn)法（rr）一種。 （3）實時系統(tǒng)中只設有進程（不設作業(yè)調(diào)度），其進程調(diào)度算法調(diào)度有：輪轉(zhuǎn)法、優(yōu)先級調(diào)度算法。前者適用

6、于時間要求不嚴格的實時 4 系統(tǒng)；后者用于時間要求嚴格的實時系統(tǒng)。后者又可細分為：非搶占式優(yōu)先級調(diào)度、搶占式優(yōu)先級調(diào)度、基于時鐘中斷的搶占式優(yōu)先級調(diào)度。 注意，一個純粹的實時系統(tǒng)是針對特定應用領(lǐng)域設計的專用系統(tǒng)。作業(yè)提交的數(shù)量不會超過系統(tǒng)規(guī)定的多道程序的道數(shù)，因而可全部進入內(nèi)存。若將實時系統(tǒng)與批處理系統(tǒng)結(jié)合的話，就可以讓作業(yè)量超過多道程序道數(shù)，使優(yōu)先級低的作業(yè)呆在外存的后備隊列上。 200372. 假設系統(tǒng)中有5個進程，它們的到達時間和服務時間見下表1，忽略i/o以及其他開銷時間，若按先來先服務（fcfs）、非搶占的短作業(yè)優(yōu)先和搶占的短作業(yè)優(yōu)先三種調(diào)度算法進行cpu調(diào)度，請給出各個進程的完成時間、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間，完成表2。 表1 進程到達和需要服務時間 進程 到達時間 服