【正文】 　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)好車門后，駕駛員才能開車行使。利用信號量機(jī)制保證其正常執(zhí)行。 P(S1)。用S1信號量保護(hù)計數(shù)器，其初值為1，R的初值為0；互斥使用橋的信號量用S表示，其初值為1。下面用兩個過程描述對表格應(yīng)執(zhí)行的動作： 登記過程：(`2’) 擦除過程：(`2’) begin begin P(empty) P(mutex) P(mutex) 找到自己的登記項擦除 找到一個登記項登記 V(mutex) V(mutex) V(empty) end end 為了正確地描述讀者的動作，可以將讀者看成進(jìn)程。(4’)住宿登記及注銷過程的算法描述如下： 住宿登記：(`3’) begin p(empty) //檢查有無床位 p(mutex) //申請登記 找出一個空床位將名字登入表中 v(mutex) end 注銷過程：(`3’) begin p(mutex) //申請退房 找出自己的登記項，并刪除該項的登記 v(mutex) v(empty)end. 5有一個閱覽室，共有100個座位。試問：1） 購票者之間是同步還是互斥？用P、V操作表達(dá)購票者的工作過程。答：假定用信號量s代表任一隊列的可用緩沖區(qū)個數(shù)。B2S1=2。試用P、V操作寫出三個進(jìn)程之間的同步及互斥流程。④ 線程在執(zhí)行過程中，需要協(xié)作同步。⑵如果S=0,則該進(jìn)程繼續(xù)執(zhí)行。 進(jìn)程間的同步是指：異步環(huán)境下的一組并發(fā)進(jìn)程因直接制約相互發(fā)送消息而進(jìn)行相互合作、相互等待，是各進(jìn)程按一定的速度執(zhí)行的過程。 3試比較進(jìn)程和程序的區(qū)別答：（1）進(jìn)程是一個動態(tài)的概念，而程序是一個靜態(tài)的概念，程序是指令的有序集合，無執(zhí)行含義，進(jìn)程則強(qiáng)調(diào)執(zhí)行的過程。為此，人們引入了“進(jìn)程（Process）”這一概念來描述程序動態(tài)執(zhí)行過程的性質(zhì)。14運行態(tài)正在cpu上執(zhí)行的進(jìn)程所處的狀態(tài)。也就是說，這些具有伙伴關(guān)系的進(jìn)程在執(zhí)行次序上必須遵循確定的規(guī)律。答：特權(quán)指令是一類只能在核心態(tài)下執(zhí)行的機(jī)器指令。 11系統(tǒng)調(diào)用與過程調(diào)用在功能及實現(xiàn)上有什么相同點和不同點？答：相同點：兩者都由程序代碼構(gòu)成，可直接用高級程序設(shè)計語言（如C,C++和Perl語言）來編制；使用方式相同——以函數(shù)調(diào)用的形式出現(xiàn)，調(diào)用時傳送參數(shù)。8什么是分時系統(tǒng)，它有什么特征？答：分時系統(tǒng)：把處理機(jī)的運行時間分成很短的時間片，按時間片輪轉(zhuǎn)的方式，把處理機(jī)分配給各進(jìn)程使用。5試說明多道程序設(shè)計和多任務(wù)系統(tǒng)之間的關(guān)系答：多道程序設(shè)計是利用外設(shè)與cpu能夠并行處理的特性，在主存同時存放多個程序，使之在系統(tǒng)中交叉地使用cpu，從而提高系統(tǒng)資源的利用率。簡答題1什么是操作系統(tǒng)？它的主要功能是什么？答：操作系統(tǒng)是控制和管理計算機(jī)系統(tǒng)內(nèi)各種硬件和軟件資源，有效地組織多道程序運行的系統(tǒng)軟件（或程序集合），是用戶與計算機(jī)之間的接口。每一個子功能稱作一條系統(tǒng)調(diào)用命令。5并發(fā)是指兩個或多個活動在同一給定的時間間隔中進(jìn)行。這些作業(yè)共享CPU和系統(tǒng)中的其他資源。10系統(tǒng)調(diào)用是用戶在程序中能以“函數(shù)調(diào)用”形式調(diào)用的、由操作系統(tǒng)提供的子功能的集合。例如，多個進(jìn)程同時占用內(nèi)存，從而對內(nèi)存共享；它們并發(fā)執(zhí)行時對cpu進(jìn)行共享；各個進(jìn)程在執(zhí)行過程中提出對文件的讀寫請求，從而對磁盤進(jìn)行共享等等。要有效使用多重處理，必須采用多道程序設(shè)計技術(shù)，而多道程序設(shè)計原則上不一定要求多重處理系統(tǒng)的支持。其主要特征是：用戶脫機(jī)使用計算機(jī)、成批處理、多道程序運行。（2分）設(shè)置這兩種不同狀態(tài)的目的是為了保護(hù)操作系統(tǒng)程序（特別是其內(nèi)核部分），防止受到用戶程序的損害。 12試說明特權(quán)指令和系統(tǒng)調(diào)用之間的區(qū)別與聯(lián)系。6同步是指進(jìn)程間共同完成一項任務(wù)時直接發(fā)生相互作用的關(guān)系。13就緒態(tài)進(jìn)程已經(jīng)獲得了除cpu之外的全部資源，等待系統(tǒng)分配cpu，一旦獲得cpu，進(jìn)程就可以變?yōu)檫\行態(tài)。用程序這個靜態(tài)的概念已不能如實反映程序并發(fā)執(zhí)行過程中的這些特征。這些并發(fā)進(jìn)程就相當(dāng)于由偽處理機(jī)執(zhí)行的程序。 6什么是進(jìn)程間的互斥？什么是進(jìn)程間同步？答：進(jìn)程間的互斥是指：一組并發(fā)進(jìn)程中的一個或多個程序段，因共享某一共有資源而導(dǎo)致它們必須以一個不許交叉執(zhí)行的單位執(zhí)行，即不允許兩個以上的共享該資源的并發(fā)進(jìn)程同時進(jìn)入臨界區(qū)。P(S)順序執(zhí)行下述兩個動作（1分）：⑴信號量的值減1，即S=S1。③ 處理機(jī)分給線程，即真正在處理機(jī)上運行的是線程。初始時，僅緩沖區(qū)0有一個消息。B1S2=0。試描述進(jìn)程從任一緩沖隊列中得到一個緩沖區(qū)的過程get_buf(type,numb)和釋放一個緩沖區(qū)numb進(jìn)入緩沖隊列的過程put_buf(type,numb)。如果廳內(nèi)已有100人，則在廳外等候。begin p(empty) p(mutex) 進(jìn)入廳內(nèi)購票,購票后退出 v(empty) v(mutex)end. 4某招待所有100個床位，住宿者入住要先登記（在登記表上填寫姓名和床位號）．離去時要注銷登記（在登記表上刪去姓名和床位號）．請給出住宿登記及注銷過程的算法描述．答：某招待所有100個床位，為了正確管理，引入一個信號量empty代表空床位數(shù)，初值為100；住宿者入住要先登記（在登記表上填寫姓名和床位號），顯然，登記表是一個臨界資源，必須互斥訪問，引入一個mutex，其初值為1。為此設(shè)兩個信號量：mutex為互斥信號量，用來制約各讀者互斥地進(jìn)行登記，其初值為1；empty為同步信號量，用來制約各讀者能同時進(jìn)入閱覽室的數(shù)量，其初值為100 (2’)。解：假設(shè)一座橋由N個橋墩，也即最多允許有N個人同向過河，用一個計數(shù)器R記錄同時過河的人數(shù)(2’)。 //釋放計數(shù)器的使用權(quán) (3’) 占有一個橋墩,并順序過河到對岸。要求：當(dāng)一個用戶訂票而需要更新數(shù)據(jù)庫時，不能因不斷有查詢者到來而使其長時間等待。答：(1)定義一信號量S，初始值為20。 z = 9 (6’)11 M8M7M6M5M4M3M2試用信號量機(jī)制來描述下述前趨圖M1 解答：首先定義信號量S12,S13,S14,S26,S36,S47,S57,S38,S78的初值都為0，分別表示相對應(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試用信號量機(jī)制來描述下述前趨圖M1 解答：首先定義信號量S12,S13,S24,S25,S56,S46,S36的初值都為0，分別表示相對應(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)有三個并發(fā)進(jìn)程R,C,P，共享一個能存放n個數(shù)據(jù)的環(huán)形緩沖區(qū)buf。4死鎖避免對進(jìn)程所發(fā)出的每一個申請資源命令加以動態(tài)地檢查，并根據(jù)檢查結(jié)果決定是否進(jìn)行資源分配。 占有且等待條件——進(jìn)程至少已經(jīng)占有一個資源，但又申請新的資源。 6資源按序分配法為什么能夠預(yù)防死鎖？證明：采用反證法來證明。系統(tǒng)采用銀行家算法來避免死鎖。1） 該狀態(tài)是否安全(給出詳細(xì)的檢查過程)?2） 如果進(jìn)程依次有如下資源請求p1:資源請求Request(1,0,2)?p4:資源請求Request(3,3,0)?p0:資源請求Request(0,1,0)?則系統(tǒng)如何進(jìn)行資源分配，才能避免死鎖？解:1)該系統(tǒng)狀態(tài)是否安全,系統(tǒng)只要按照這個序列為進(jìn)程分配資源,所有進(jìn)程就都可順利完成。1） 試給出采用銀行家算法分配資源時，進(jìn)行第5次分配后各進(jìn)程的狀態(tài)及各進(jìn)程占用資源情況。P3申請3個，不能滿足，等待。解答：系統(tǒng)當(dāng)前剩余資源量為：150 – 25 – 40 – 45 = 40 (2’)(1) 可以滿足(2’)，假定先分配p4的25個資源，系統(tǒng)還剩15個。(2) 進(jìn)程P3提出對資源R3的剩余請求為1，由于系統(tǒng)剩余資源向量A=(1,2, 3, 0)，故可以假定分配給它。3響應(yīng)時間是分時系統(tǒng)的一個技術(shù)指標(biāo)，指從用戶輸入命令到系統(tǒng)對命令開始執(zhí)行和顯示所需要的時間。8非剝奪式調(diào)度系統(tǒng)一旦把處理機(jī)分配給某個進(jìn)程之后，該進(jìn)程一直運行下去，直到該進(jìn)程完成或因等待某個事件發(fā)生時，才將處理機(jī)分配給其他進(jìn)程。 其主要區(qū)別關(guān)系如下： （1）作業(yè)是用戶向計算機(jī)提交任務(wù)的任務(wù)實體。則進(jìn)程的概念則用在幾乎所有的多道程序系統(tǒng)中。另外，進(jìn)程調(diào)度相當(dāng)頻繁，而作業(yè)調(diào)度執(zhí)行的次數(shù)一般很少。設(shè)作業(yè)序列如表49所示。 當(dāng)3x5時，作業(yè)的運行順序應(yīng)為C(3),E(x),D(5),B(6),A(9)。4物理地址空間由內(nèi)存中的一系列存儲單元所限定的地址范圍稱作內(nèi)存空間。11緊縮移動某些已分區(qū)的內(nèi)容，使所有作業(yè)的分區(qū)緊挨在一起，而把空閑區(qū)留在另一端，這種技術(shù)稱為緊縮。此時，它必須淘汰某頁。在分頁系統(tǒng)中，由于頁表是存放在主存中的，因此cpu存取一個數(shù)據(jù)時要訪問兩次主存。24虛存虛存是指系統(tǒng)向用戶程序提供的編程空間，其大小由cpu的地址長度決定。外部碎片出現(xiàn)在所有分區(qū)之外，是新增的小分區(qū)，如在動態(tài)分區(qū)法實施過程中會出現(xiàn)外部碎片 。多次對換——所需的全部程序和數(shù)據(jù)要分成多次調(diào)入內(nèi)存。 ④分頁的活動對用戶是不可見的，而分段是用戶可見的活動。這樣，就減少了對換時間和所需內(nèi)存數(shù)量，允許增加程序的道數(shù)。 12什么是頁面抖動？系統(tǒng)怎樣檢測是否出現(xiàn)抖動？一旦檢測到抖動？系統(tǒng)如何消除它？答：頁面抖動是系統(tǒng)頻繁進(jìn)行頁面置換的現(xiàn)象。又設(shè)該程序基本可用內(nèi)存是200字，采用FIFO置換算法，求出缺頁率。缺頁次數(shù)為12次 (2’)4某請求頁式管理系統(tǒng)，用戶編程空間有40個頁面，每個頁面為200H字節(jié)。(2’)5某系統(tǒng)采用頁式存儲管理策略，擁有邏輯空間32頁，每頁2KB；擁有物理空間1MB。在主存忠為每一個作業(yè)進(jìn)程開辟3頁。（2）當(dāng)快表的命中率為85%時，執(zhí)行一次訪內(nèi)操作需要的時間： T=1*+2*()=(us) (3’)當(dāng)快表的命中率為50%時，執(zhí)行一次訪內(nèi)操作需要的時間： T=1*+2*()=(us) (3’)8在一個采用頁式虛擬存儲管理的系統(tǒng)中，有一用戶作業(yè)，它依次要訪問的字地址序列是：115，228，120，88，446，102，321，432，260，167，若該作業(yè)的第0頁已經(jīng)裝入主存，現(xiàn)分配給該作業(yè)的