【正文】 （2）提高目錄的檢索速度。鏈接文件消除了外存的碎片，提高了外存的利用率，同時(shí)使文件很容易實(shí)現(xiàn)動態(tài)增長。它又分為“輸入井讀”和“輸出井寫”兩個(gè)程序。③當(dāng)計(jì)算進(jìn)程需要輸出數(shù)據(jù)時(shí)，便從空緩沖隊(duì)列的隊(duì)首摘下一個(gè)空緩沖區(qū)，將數(shù)據(jù)輸出到其中，當(dāng)緩沖區(qū)裝滿輸出數(shù)據(jù)后，再將它掛到輸出隊(duì)列末尾。若通道忙，將進(jìn)程插入通道等待隊(duì)列；否則將該通道分配給進(jìn)程。（2） 中斷驅(qū)動控制方式，它使CPU和設(shè)備可以并行工作，顯著提高了CPU的利用率，至今仍然是字符設(shè)備的I/O控制方式。LRU置換算法考慮了頁面調(diào)入內(nèi)存后的使用情況，具有較好的性能，但要快速的找出最近最久未被使用的頁面，卻要花費(fèi)巨大的系統(tǒng)開銷，往往需要較多的硬件支持，因此在實(shí)際系統(tǒng)中往往使用其近似算法。請計(jì)算下列邏輯地址所對應(yīng)的物理地址：378，15034，5700，30000。進(jìn)程未執(zhí)行時(shí)，其頁表始址和頁表長度存放在它的PCB中；當(dāng)進(jìn)程被調(diào)度執(zhí)行時(shí)，這兩個(gè)數(shù)據(jù)就被裝入頁表寄存器中。3． 動態(tài)分區(qū)分配的常用算法有哪些？各有什么特點(diǎn)？參考答案：動態(tài)分區(qū)分配的常用的內(nèi)存分配算法（1）最先適應(yīng)算法。在引入線程的操作系統(tǒng)中，不僅進(jìn)程之間可以并發(fā)執(zhí)行，而且在一個(gè)進(jìn)程中的多個(gè)線程之間也可以并發(fā)執(zhí)行，因而使系統(tǒng)具有更好的并發(fā)性，從而能更有效地使用系統(tǒng)資源和提高系統(tǒng)吞吐量。若分別采用非搶占式優(yōu)先級調(diào)度算法和可搶占式優(yōu)先級調(diào)度算法，試給出各進(jìn)程的調(diào)度順序以及平均周轉(zhuǎn)時(shí)間。為了能更準(zhǔn)確地評價(jià)系統(tǒng)的性能，引入了另一個(gè)指標(biāo)：帶權(quán)周轉(zhuǎn)時(shí)間，即作業(yè)的周轉(zhuǎn)時(shí)間與系統(tǒng)實(shí)際為其提供的服務(wù)時(shí)間之比。 process Pout ( ) beginL2: P（full）。參考答案：第一步：確定進(jìn)程可以為入庫（Pin）和出庫（Pout）各設(shè)置一個(gè)進(jìn)程Pin進(jìn)程： l 生產(chǎn)了一臺設(shè)備l 使用運(yùn)輸工具入庫Pout進(jìn)程： l 使用運(yùn)輸工具出庫l 提出設(shè)備供應(yīng)客戶第二步：確定進(jìn)程的同步、互斥關(guān)系l 同步：當(dāng)倉庫中有空余位置存放設(shè)備時(shí)，設(shè)備才可以入庫l 同步：當(dāng)倉庫中有存放的設(shè)備時(shí)，設(shè)備才可以出庫l 互斥：運(yùn)輸工具是臨界資源，要互斥訪問第三步：設(shè)置信號量l 倉庫中有空余位置數(shù)量，empty，初值10l 倉庫中有存放的設(shè)備數(shù)量，full，初值 0l 為運(yùn)輸工具設(shè)置互斥信號量S，初值 1，表示當(dāng)前可用第四步：用偽代碼描述begin empty, full, S：semaphore。 登記。 end。 從盤中取出蘋果； V（Sp） 吃蘋果； goto L4； end。Mother ( )。參考答案：由于打印機(jī)是臨界資源，三個(gè)進(jìn)程共享臨界資源，是互斥關(guān)系。,將是1,2號哲學(xué)家競爭1號筷子,3,獲得后,再去競爭偶數(shù)號筷子,最后總會有一個(gè)哲學(xué)家能獲得兩支筷子而進(jìn)餐。 process Busman ( )begin L2: 關(guān)車門； V（close）。 goto L3 end。 full2 :=0。 P（empty2）。empty1 :=m。 P（empty1）。將P（full）與P（mutex）互換位置，系統(tǒng)也可能進(jìn)入死鎖狀態(tài)。參考答案：多個(gè)進(jìn)程之間彼此無關(guān)，它們并不知道其它進(jìn)程的存在，但由于同處于一個(gè)系統(tǒng)中，必然存在著資源共享關(guān)系。（3）現(xiàn)場信息：主要是由處理器的各個(gè)寄存器中的內(nèi)容組成，包括通用寄存器內(nèi)容、指令計(jì)數(shù)器的值、程序狀態(tài)字內(nèi)容以及用戶棧指針。（3） 程序和進(jìn)程無一一對應(yīng)關(guān)系。首先，共享是以并發(fā)執(zhí)行為條件，若系統(tǒng)不支持程序并發(fā)執(zhí)行，則系統(tǒng)中將不存在資源共享；同時(shí)，共享也必然會影響程序的并發(fā)執(zhí)行，若資源共享不當(dāng)，并發(fā)性會減弱，甚至無法實(shí)現(xiàn)。從資源管理的觀點(diǎn)看，操作系統(tǒng)具有五個(gè)方面的功能：處理器管理、存儲器管理、設(shè)備管理、文件管理和提供用戶接口。因?yàn)橥ǔＯ鄳?yīng)硬件配置較低，而且對操作系統(tǒng)提供的功能要求也不高。2． 什么是進(jìn)程？進(jìn)程有哪些特征？其中最基本的特征是什么？參考答案：進(jìn)程是具有一定獨(dú)立功能的程序關(guān)于某個(gè)數(shù)據(jù)集合的一次運(yùn)行活動，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。 （4）阻塞→就緒：處于阻塞狀態(tài)的進(jìn)程，所等待的事情已經(jīng)發(fā)生，如I/O操作已完成或獲得了所需的資源，則進(jìn)程將轉(zhuǎn)變?yōu)榫途w狀態(tài)。（3）進(jìn)程阻塞原語首先停止該進(jìn)程的執(zhí)行，將CPU中各寄存器內(nèi)容填入該進(jìn)程的PCB中，并將其狀態(tài)由“執(zhí)行”改為“阻塞”，然后插入相應(yīng)的阻塞隊(duì)列，最后轉(zhuǎn)進(jìn)程調(diào)度程序重新進(jìn)行調(diào)度。當(dāng)S0時(shí)，其值表示當(dāng)前可供分配的資源數(shù)目；當(dāng)S0時(shí)，其絕對值表示S信號量的等待隊(duì)列中的進(jìn)程數(shù)目。 full2 :=0。 process R ( )begin L3:P（full2）。process P ( )begin L1: 從輸入設(shè)備上讀入信息。 13． 有四個(gè)并發(fā)進(jìn)程：R1，R2，W1和W2，它們共享可以存放一個(gè)數(shù)的緩沖區(qū)。 goto L1 end。 close := 0。 吃面條； V（chopstick[i+1%5] ）。 P（chopstick[i+1%5] ）。（2）桌上一個(gè)盤子，只能放一只水果。 process Mother ( ) begin L2: P（Sp）。process Father ( ) begin L1: P（empty）。參考答案：第一步：確定進(jìn)程可以進(jìn)入閱覽室的讀者可以有很多，這里設(shè)為n，即n個(gè)Reader（讀者）進(jìn)程Reader進(jìn)程： l 登記l 進(jìn)入閱覽室l 讀書l 離開閱覽室l 注銷第二步：確定進(jìn)程的同步、互斥關(guān)系l 同步：當(dāng)教室內(nèi)有空座位時(shí)，讀者才可以登記，并進(jìn)入閱覽室l 互斥：同時(shí)只能有一個(gè)讀者在入口處進(jìn)行登記l 互斥：同時(shí)只能有一個(gè)讀者在出口處進(jìn)行注銷第三步：設(shè)置信號量l 教室內(nèi)空座位數(shù)量，seat，初值100l 為入口處進(jìn)行登記設(shè)置互斥信號量Sin，初值 1，表示當(dāng)前可用l 為出口處進(jìn)行注銷設(shè)置互斥信號量Sout，初值 1，表示當(dāng)前可用第四步：用偽代碼描述begin Sin, Sout, seat：semaphore。 endcoend。P（empty）。21． 高級調(diào)度與低級調(diào)度的主要任務(wù)是什么？為什么要引入中級調(diào)度？參考答案：高級調(diào)度又稱作業(yè)調(diào)度，其任務(wù)是從外存上的后備隊(duì)列中按照一定的原則選擇若干個(gè)作業(yè)調(diào)入內(nèi)存，為他們創(chuàng)建進(jìn)程，分配必要的資源，如內(nèi)存、外設(shè)等，并將新創(chuàng)建的進(jìn)程插入就緒隊(duì)列，準(zhǔn)備執(zhí)行。 所謂系統(tǒng)吞吐量，是指單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)量，主要用于評價(jià)批處理系統(tǒng)。在引入線程的操作系統(tǒng)中，通常一個(gè)進(jìn)程擁有若干個(gè)線程，至少也有一個(gè)線程。它有靜態(tài)重定位和動態(tài)重定位兩種方式。4． 在可變分區(qū)存儲管理中，設(shè)作業(yè)A（30KB），作業(yè)B（70KB），作業(yè)C（50KB）依次請求內(nèi)存分配，內(nèi)存現(xiàn)有兩個(gè)空閑區(qū)：F1（100KB）和F2（50KB），如圖3－18所示。8． 簡述分段系統(tǒng)的地址變換過程。從用戶角度看，該系統(tǒng)所具有的內(nèi)存容量比實(shí)際內(nèi)存容量大得多，但這只是用戶的一種感覺，是虛的，故而得名虛擬存儲器。16． 在一個(gè)請求分頁系統(tǒng)中，假設(shè)一個(gè)作業(yè)的頁面走向?yàn)?，3，2，1，4，3，5，4，3，2，1，5，若分配給該作業(yè)的物理塊數(shù)為4，假設(shè)當(dāng)前沒有任何頁面在內(nèi)存，分別采用FIFO和LRU頁面置換算法，試計(jì)算在運(yùn)行過程中發(fā)生的缺頁次數(shù)和缺頁率，并比較所得結(jié)果。若設(shè)備忙，則查找第二個(gè)該類設(shè)備的控制表，僅當(dāng)所有該類設(shè)備都忙時(shí)，才把進(jìn)程插入該類設(shè)備的等待隊(duì)列上。8． 為什么要引入緩沖？簡述緩沖池的實(shí)現(xiàn)機(jī)制。參考答案：SPOOLing系統(tǒng)包括輸入井和輸出井、預(yù)輸入程序和緩輸出程序、井管理程序幾個(gè)部分，如圖4－6所示。2．什么是文件的邏輯結(jié)構(gòu)？文件的邏輯結(jié)構(gòu)有哪些？參考答案：文件的邏輯結(jié)構(gòu)是從用戶觀點(diǎn)出發(fā)所觀察到的文件結(jié)構(gòu)，它獨(dú)立于文件的物理特性，用戶也是按照邏輯結(jié)構(gòu)來使用文件的。分別給出文件主、伙伴用戶、一般用戶的存取權(quán)限。6．目前常用的目錄結(jié)構(gòu)是哪種結(jié)構(gòu)。其中用戶名主要是指文件主和授權(quán)用戶；而物理地址的內(nèi)容通常與文件的物理結(jié)構(gòu)有關(guān)，對于連續(xù)文件和鏈接文件，應(yīng)說明起始盤塊號，而對于索引文件，應(yīng)給出其索引塊號。所謂文件系統(tǒng)是指被管理的文件、對文件進(jìn)行管理的一組軟件以及實(shí)現(xiàn)管理功能所需要的數(shù)據(jù)結(jié)構(gòu)的總體。重復(fù)上述過程，直到請求打印隊(duì)列為空，緩輸出程序就阻塞等待新的打印請求。另外，驅(qū)動程序與設(shè)備所采用的I/O控制方式緊密相關(guān)，如常用的中斷驅(qū)動方式和DMA方式的驅(qū)動程序就明顯不同。（1）分配設(shè)備。（1）計(jì)算邏輯地址9016所對應(yīng)的物理地址；（2）對邏輯地址12300，試給出其物理地址的轉(zhuǎn)換過程。進(jìn)行地址轉(zhuǎn)換時(shí)，首先檢查段號是否超出段表長度，如果是，產(chǎn)生越界中斷；否則，使用段號檢索段表，找到對應(yīng)的段表項(xiàng)后，從中得到該段的頁表始址和頁表長度，再檢查頁號是否超出頁表長度，如果是，產(chǎn)生越界中斷；否則，使用頁號檢索頁表，找到對應(yīng)的頁表項(xiàng)后，從中得到該頁對應(yīng)的物理塊號，再與頁內(nèi)地址一起組成物理地址。（2） 頁的大小固定且由系統(tǒng)決定，是由機(jī)器硬件實(shí)現(xiàn)的；而段的長度卻不固定，決定于用戶所編寫的程序，通常由編譯程序在對源程序進(jìn)行編譯時(shí)，根據(jù)信息的性質(zhì)來劃分。（3）最壞適應(yīng)算法。同樣，在進(jìn)行進(jìn)程切換時(shí)，需要保存當(dāng)前進(jìn)程的執(zhí)行環(huán)境，設(shè)置和恢復(fù)被調(diào)度進(jìn)程的執(zhí)行環(huán)境，而線程切換只需保存和設(shè)置少量寄存器的內(nèi)容，不涉及存儲管理方面的操作，因而進(jìn)程切換的開銷也遠(yuǎn)大于線程切換的開銷。線程具有許多傳統(tǒng)進(jìn)程的特征，故又稱為輕型進(jìn)程。CPU的利用率可從0％到100％，但在實(shí)際系統(tǒng)中，一般是在40％～90％之間。 end。end。 V(Sout)。讀者進(jìn)入閱覽室時(shí)必須在入口處進(jìn)行登記；離開閱覽室時(shí)必須進(jìn)行注銷。coend。 goto L1。17． ，把題目修改為以下幾種情況，請用PV操作實(shí)現(xiàn)他們之間的同步關(guān)系： （1）桌上一個(gè)盤子，只能放一只水果。cobeginprocess Pi(i=0,2,…,4)begin 思考； P (num)。cobeginprocess Pi(i=0,2,…,4)begin 思考； P（chopstick[i] ）。在汽車不斷地到站、停車、行駛過程中，請用信號量的PV操作實(shí)現(xiàn)司機(jī)與售票員之間的同步關(guān)系。process R1 ( )begin L1: 從磁盤上讀入一個(gè)數(shù)； P（empty）。 goto L3 。coend。將信息放入緩沖區(qū)2； V（full2）。 empty2 :=1。V（S）：將信號量S加1，若結(jié)果大于0，則該進(jìn)程繼續(xù)執(zhí)行；若結(jié)果小于或等于0，則從該信號量的等待隊(duì)列中移出一個(gè)進(jìn)程，使其從阻塞狀態(tài)變?yōu)榫途w狀態(tài)，并插入到就緒隊(duì)列中，然后返回當(dāng)前進(jìn)程繼續(xù)執(zhí)行。如果該進(jìn)程還有子進(jìn)程，則一并予以撤消。 （2）執(zhí)行→就緒：在分時(shí)系統(tǒng)中，正在執(zhí)行的進(jìn)程如果時(shí)間片用完則將暫停執(zhí)行；在搶占調(diào)度方式中，如有更高優(yōu)先級的進(jìn)程需要運(yùn)行，將迫使正在運(yùn)行的進(jìn)程讓出CPU。第二章習(xí)題：1． 進(jìn)程管理主要包括哪些管理功能？參考答案：進(jìn)程管理實(shí)際上就是對處理器的管理，因?yàn)閭鹘y(tǒng)的多道程序系統(tǒng)中，處理器的分配和運(yùn)行都是以進(jìn)程為基本單位的。（6） 分布式操作系統(tǒng)：是配置在分布式處理系統(tǒng)上的操作系統(tǒng)，其最基本的特征是能實(shí)現(xiàn)處理上的分布，而處理分布的實(shí)質(zhì)是資源、功能、任務(wù)和控制都是分布的。2． 操作系統(tǒng)有哪幾種類型？各有什么特點(diǎn)？參考答案：操作系統(tǒng)是隨著計(jì)算機(jī)硬件技術(shù)的不斷發(fā)展和用戶的使用要求的提高而從無到有不斷完善起來的，其主要類型及其特點(diǎn)如下：（1） 批處理操作系統(tǒng)：具有很高的資源利用率和系統(tǒng)吞吐量，但作業(yè)的平均周轉(zhuǎn)時(shí)間較長，也沒有交互性。用戶從鍵盤上輸入命令， 命令解釋程序接收并解釋這些命令，然后調(diào)用操作系統(tǒng)內(nèi)部的相應(yīng)程序，完成相應(yīng)的功能。例如，在分時(shí)系統(tǒng)中多個(gè)終端用戶同時(shí)進(jìn)行C程序編譯，這樣，一個(gè)C編譯程序?qū)?yīng)多個(gè)用戶進(jìn)程；而對每個(gè)用戶進(jìn)程來說，在進(jìn)行編譯的過程中會用到預(yù)處理、詞法及語法分析、代碼生成和優(yōu)化等幾個(gè)程序模塊。（4）管理信息：是進(jìn)程管理和控制所需要的相關(guān)信息，包括程序和數(shù)據(jù)在內(nèi)存或外存的地址、進(jìn)程同步和通信機(jī)制、資源清單（記錄進(jìn)程所需的除CPU外的全部資源和已經(jīng)分配到的資源）、進(jìn)程隊(duì)列的鏈接指針等。多個(gè)進(jìn)程在共享臨界資源時(shí)，必須以互斥方式共享。12． 假設(shè)有三個(gè)并發(fā)進(jìn)程P，Q，R，其中P負(fù)責(zé)從輸入設(shè)備上讀入信息并傳送給Q，Q將信息加工后傳送給R，R則負(fù)責(zé)將信息打印輸出。 goto L1 end。 full1 :=0。 goto L2 end。R2 ( )。將緩沖區(qū)中的數(shù)取出；V（empty）。 開車門；goto L2 end。 將拿筷子的操作做成原子操作，即當(dāng)一個(gè)哲學(xué)家正在拿筷子的時(shí)候，其它的哲學(xué)家不能動筷子，當(dāng)他那好筷子開始吃飯的時(shí)候，其它哲學(xué)家才可以拿筷子。s := 1。Daughter ( )。 empty:=1。 從盤中取出水果。 進(jìn)入閱覽室。full := 0。使用運(yùn)輸工具出庫。從用戶通過鍵盤提交一個(gè)請求開始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間間隔稱為響應(yīng)時(shí)間，主要用于評價(jià)分時(shí)系統(tǒng)。產(chǎn)生死鎖的原因