浙大遠程教育操作系統(tǒng)原理離線作業(yè)參考答案

1、浙江大學(xué)遠程教育學(xué)院操作系統(tǒng)原理課程作業(yè)姓名：學(xué) 號：年級：學(xué)習(xí)中心：一、單選題1. 進程P0和P1的共享變量定義及其初值為boolean flag2；int turn=0；flag0=FALSE；flag1=FALSE； 若進程P0和P1訪問臨界資源的類C代碼實現(xiàn)如下：void P0() /P0進程 while（TURE）flag0=TRUE; turn = 1;while (flag1 && turn = 1) ; 臨界區(qū); flag0 = FALSE; void P1() /P1進程 while（TURE）flag1=TRUE; turn = 0;while (flag0

2、 && turn = 0) ; 臨界區(qū); flag1 = FALSE; 則并發(fā)執(zhí)行進程P0和P1時產(chǎn)生的情況是： DA不能保證進程互斥進入臨界區(qū)、會出現(xiàn)“饑餓”現(xiàn)象B不能保證進程互斥進入臨界區(qū)、不會出現(xiàn)“饑餓”現(xiàn)象C能保證進程互斥進入臨界區(qū)、會出現(xiàn)“饑餓”現(xiàn)象D能保證進程互斥進入臨界區(qū)、不會出現(xiàn)“饑餓”現(xiàn)象2.有兩個進程P1和P2描述如下:shared data：int counter = 6; P1 :Computing;counter=counter+1;P2 :Printing;counter=counter-2;兩個進程并發(fā)執(zhí)行，運行完成后，counter的值不可能為

3、C 。 A. 4B. 5C. 6D. 73.某計算機采用二級頁表的分頁存儲管理方式，按字節(jié)編址，頁大小為210字節(jié)，頁表項大小為2字節(jié)，邏輯地址結(jié)構(gòu)為：頁目錄號頁號頁內(nèi)偏移量邏輯地址空間大小為216頁，則表示整個邏輯地址空間的頁目錄表中包含表項的個數(shù)至少是 BA64B128C256D5124.在動態(tài)分區(qū)系統(tǒng)中，有如下空閑塊:空閑塊塊大小（KB）塊的基址18060275150355250490350此時,某進程P請求50KB內(nèi)存,系統(tǒng)從第1個空閑塊開始查找，結(jié)果把第4個空閑塊分配給了P進程 ，請問是用哪一種分區(qū)分配算法實現(xiàn)這一方案? CA. 首次適應(yīng)B. 最佳適應(yīng)C. 最差適應(yīng) D. 下次適應(yīng)5

4、.在一頁式存儲管理系統(tǒng)中，頁表內(nèi)容如下所示。頁號幀號021128若頁大小為1K，邏輯地址的頁號為2，頁內(nèi)地址為451，轉(zhuǎn)換成的物理地址為 AA. 8643B. 8192C. 2048D. 24996.采用段式存儲管理的系統(tǒng)中，若地址用32位表示，其中20位表示段號，則允許每段的最大長度是 BA 224B. 212C. 210D. 2327.在一段式存儲管理系統(tǒng)中，某段表的內(nèi)容如下: 段號段首址 段長0100K35K1560K20K2260K15K3670K32K若邏輯地址為(2, 158)，則它對應(yīng)的物理地址為_B_。A. 100K+158 B. 260K+158 C. 560K+158 D.

5、 670K+1588.一個分段存儲管理系統(tǒng)中，地址長度為32位，其中段長占8位，則最大段長是 CA. 28字節(jié)B. 216字節(jié)C. 224字節(jié) D. 232字節(jié)9.有一請求分頁式存儲管理系統(tǒng)，頁面大小為每頁100字節(jié)，有一個50×50的整型數(shù)組按行為主序連續(xù)存放，每個整數(shù)占兩個字節(jié)，將數(shù)組初始化為0的程序描述如下：int A5050;for (int i = 0; i < 50; i+) for (int j = 0; j < 50; j+)Ai,j = 0; 若在程執(zhí)行時內(nèi)存只有一個存儲塊用來存放數(shù)組信息，試問該程序執(zhí)行時產(chǎn)生 B 次缺頁中斷。A1 B. 50 C. 1

6、00 D. 250010.一臺計算機有4個頁框，裝入時間、上次引用時間、和每個頁的訪問位R和修改位M，如下所示： 頁 裝入時間 上次引用時間 R M 0 126 279 0 0 1 230 260 1 0 2 120 272 1 1 3 160 280 1 1采用FIFO算法將淘汰 C 頁；A. 0B. 1C. 2D. 311.一臺計算機有4個頁框，裝入時間、上次引用時間、和每個頁的訪問位R和修改位M，如下所示： 頁 裝入時間 上次引用時間 R M 0 126 279 0 0 1 230 260 1 0 2 120 272 1 1 3 160 280 1 1采用NRU算法將淘汰 A 頁；A.

7、0B. 1C. 2D. 312.一臺計算機有4個頁框，裝入時間、上次引用時間、和每個頁的訪問位R和修改位M，如下所示： 頁 裝入時間 上次引用時間 R M 0 126 279 0 0 1 230 260 1 0 2 120 272 1 1 3 160 280 1 1采用LRU算法將淘汰 B 頁；A. 0B. 1C. 2D. 313.一臺計算機有4個頁框，裝入時間、上次引用時間、和每個頁的訪問位R和修改位M，如下所示： 頁 裝入時間 上次引用時間 R M 0 126 279 0 0 1 230 260 1 0 2 120 272 1 1 3 160 280 1 1 采用第二次機會算法將淘汰_A_

8、頁；A. 0B. 1C. 2D. 3二、綜合題1.4在所列的兩種設(shè)置中，哪些功能需要操作系統(tǒng)提供支持？ (a)手持設(shè)備(b)實時系統(tǒng)。 a. 批處理程序b. 虛擬存儲器c. 分時答：對于實時系統(tǒng)來說，操作系統(tǒng)需要以一種公平的方式支持虛擬存儲器和分時系統(tǒng)。對于手持系統(tǒng)，操作系統(tǒng)需要提供虛擬存儲器，但是不需要提供分時系統(tǒng)。批處理程序在兩種環(huán)境中都是非必需的。1.17列出下列操作系統(tǒng)的基本特點：a. 批處理b.交互式c.分時d.實時e.網(wǎng)絡(luò)f.并行式g.分布式h.集群式i.手持式答：a.批處理：具有相似需求的作業(yè)被成批的集合起來，并把它們作為一個整體通過一個操作員或自動作業(yè)程序裝置運行通過計算機。通

9、過緩沖區(qū)，線下操作，后臺和多道程序，運用嘗試保持CPU和I/O一直繁忙，從而使得性能被提高。批處理系統(tǒng)對于運行那些需要較少互動的大型作業(yè)十分適用。它們可以被更遲地提交或獲得。b.交互式：這種系統(tǒng)由許多短期交易構(gòu)成，并且下一個交易的結(jié)果是無法預(yù)知的。從用戶提交到等待結(jié)果的響應(yīng)時間應(yīng)該是比較短的，通常為1秒左右。c.分時：這種系統(tǒng)使用CPU調(diào)度和多道程序來經(jīng)濟的提供一個系統(tǒng)的人機通信功能。CPU從一個用戶快速切換到另一個用戶。以每個程序從終端機中讀取它的下一個控制卡，并且把輸出的信息正確快速的輸出到顯示器上來替代用soopled card images定義的作業(yè)。d.實時：經(jīng)常用于專門的用途。這個

10、系統(tǒng)從感應(yīng)器上讀取數(shù)據(jù)，而且必須在嚴(yán)格的時間內(nèi)做出響應(yīng)以保證正確的性能。e.網(wǎng)絡(luò)：提供給操作系統(tǒng)一個特征，使得其進入網(wǎng)絡(luò)，比如;文件共享。f.并行式：每一個處理器都運行同一個操作系統(tǒng)的拷貝。這些拷貝通過系統(tǒng)總線進行通信。g.分布式：這種系統(tǒng)在幾個物理處理器中分布式計算，處理器不共享內(nèi)存或時鐘。每個處理器都有它各自的本地存儲器。它們通過各種通信線路在進行通信，比如：一條高速的總線或一個本地的網(wǎng)絡(luò)。h.集群式：集群系統(tǒng)是由多個計算機耦合成單一系統(tǒng)并分布于整個集群來完成計算任務(wù)。i.手持式：一種可以完成像記事本，email和網(wǎng)頁瀏覽等簡單任務(wù)的小型計算機系統(tǒng)。手持系統(tǒng)與傳統(tǒng)的臺式機的區(qū)別是更小的內(nèi)存

11、和屏幕以及更慢的處理能力。2.3討論向操作系統(tǒng)傳遞參數(shù)的三個主要的方法。答：1.通過寄存器來傳遞參數(shù)2.寄存器傳遞參數(shù)塊的首地址3.參數(shù)通過程序存放或壓進堆棧中，并通過操作系統(tǒng)彈出堆棧。2.12采用微內(nèi)核方法來設(shè)計系統(tǒng)的主要優(yōu)點是什么？在微內(nèi)核中如何使客戶程序和系統(tǒng)服務(wù)相互作用？微內(nèi)核方法的缺點是什么？答：優(yōu)點主要包括以下幾點：a）增加一個新的服務(wù)不需要修改內(nèi)核b) 在用戶模式中比在內(nèi)核模式中更安全、更易操作c) 一個簡單的內(nèi)核設(shè)計和功能一般導(dǎo)致一個更可靠的操作系統(tǒng)用戶程序和系統(tǒng)服務(wù)通過使用進程件的通信機制在微內(nèi)核中相互作用，例如發(fā)送消息。這些消息由操作系統(tǒng)運送。微內(nèi)核最主要的缺點是與進程間通

12、信的過度聯(lián)系和為了保證用戶程序和系統(tǒng)服務(wù)相互作用而頻繁使用操作系統(tǒng)的消息傳遞功能。3.2 問:描述一下內(nèi)核在兩個進程間進行上下文功換的動作.答：進程關(guān)聯(lián)是由進程的PCB來表示的，它包括CPU寄存器的值和內(nèi)存管理信息等。當(dāng)發(fā)生上下文切換時，內(nèi)核會將舊進程的關(guān)聯(lián)狀態(tài)保存在其PCB中，然后裝入經(jīng)調(diào)度要執(zhí)行的新進程的已保存的關(guān)聯(lián)狀態(tài)。總的來說，操作系統(tǒng)必須保存正在運行的進程的狀態(tài)，恢復(fù)進程的狀態(tài)。保存進程的狀態(tài)主要包括CPU寄存器的值以及內(nèi)存分配，上下文切換還必須執(zhí)行一些確切體系結(jié)構(gòu)的操作，包括刷新數(shù)據(jù)和指令緩存。3.4 如下所示的程序，說明LINE A可能會輸出什么？#include <std

13、io.h>#include <unistd.h>#include <sys/types.h>int value=8;int main()pid_t pid;/* fork a child process */pid = fork();if (pid = 0) /* child process */value +=15;else /* parent process */* parent will wait for the child to complete */wait(NULL);printf(" Parent :value= %dn",val

14、ue);/*LINE A*/exit(0);答：LINE A可能會輸出：Parent :value= 84.4在多線程程序中，以下哪些程序狀態(tài)組成是被線程共享的？ a.寄存值 b.堆內(nèi)存 c.全局變量 d.棧內(nèi)存答：多線程程序的各線程共享堆內(nèi)存和全局變量，但每個線程都有屬于自己的一組寄存值和棧內(nèi)存。4.7由圖4.11給出的程序使用了Pthread的應(yīng)用程序編程接口（API），在程序的第c行和第p行分別會輸出什么？#include <pthread.h>#include <stdio.h>int value=0;void *runner(void *param); /*

15、the thread */int main(int argc, char *argv)int pid;pthread_t tid;pthread_attr_t attr; pid = fork(); if (pid = 0) /* child process */ pthread_attr_init(&attr); pthread_create(&tid, &attr, runner, NULL); pthread_join(tid, NULL); printf(“CHILD: value = %d”, value); /* LINE C*/ else if (pid

16、> 0) /* parent process */ wait(NULL); printf(“PARENT: value = %d”, value); /* LINE P */ void *runner(void *param) value=10; pthread_exit(0);答：第c行會輸出10，第p行會輸出05.4考慮下列進程集，進程占用的CPU區(qū)間長度以毫秒來計算：進程 區(qū)間時間 優(yōu)先級P1 10 3P2 1 1P3 2 3P4 1 4P5 5 2假設(shè)在時刻0以進程P1，P2，P3，P4，P5的順序到達。a.畫出4個Gantt圖分別演示用FCFS、SJF、非搶占優(yōu)先級（數(shù)字小代表

17、優(yōu)先級高）和RR（時間片1）算法調(diào)度時進程的執(zhí)行過程。b.每個進程在每種調(diào)度算法下的周轉(zhuǎn)時間是多少？c.每個進程在每種調(diào)度算法下的等待時間是多少？d.哪一種調(diào)度算法的平均等待時間對所有進程而言最??？答：a.甘特圖FCFSP1P2P3P4P512345678910111213141516171819SJFP2P4P3P5P112345678910111213141516171819Non-preemptive PriorityP2P5P1P3P412345678910111213141516171819RR(quantum=1)P1P2P3P4P5P1P3P5P1P5P1P5P1P5P1P1P1

18、P1P112345678910111213141516171819b. Turnaround TimeProcessFCFSSJFNPPRR(quantum=1)P110191619P211112P3134187P4142194P5199614Average13.47.2129.2c. Waiting TimeProcessFCFSSJFNPPRR(quantum=1)P10969P210001P3112165P4131183P514419Average9.63.28.25.4d.SJF5.5下面哪些算法會引起饑餓a.先來先服務(wù)b.最短作業(yè)優(yōu)先調(diào)度c.輪轉(zhuǎn)法調(diào)度d.優(yōu)先級調(diào)度答：b.最短作業(yè)優(yōu)

19、先調(diào)度和d.優(yōu)先級調(diào)度算法會引起饑餓5.7考慮一個運行10個I/O約束（型）任務(wù)和一個CPU約束（型）任務(wù)的系統(tǒng)。假設(shè)，I/O約束任務(wù)每進行1毫秒的CPU計算發(fā)射一次I/O操作，但每個I/O操作的完成需要 10毫秒。同時，假設(shè)上下文切換要0.1毫秒，所有的進程都是長進程。對一個RR調(diào)度來說，以下情況時CPU的利用率是多少： a.時間片是1毫秒 b.時間片是10毫秒答：a.時間片是1毫秒：不論是哪個進程被調(diào)度，這個調(diào)度都會為每一次的上下文切換花費一個0.1毫秒的上下文切換。CPU的利用率是1/1.1*100=92%。b.時間片是10毫秒：這I/O限制任務(wù)會在使用完1毫秒時間片后進行一次上下文切換

20、。這個時間片要求在所有的進程間都走一遍，因此，10*1.1+10.1(因為每個I / O限定任務(wù)執(zhí)行為1毫秒，然后承擔(dān)上下文切換的任務(wù)，而CPU限制任務(wù)的執(zhí)行10毫秒在承擔(dān)一個上下文切換之前) 。因此，CPU的利用率是20/21.1*100=94%。6.01在生產(chǎn)者和消費者問題中，信號量mutex，empty，full的作用是什么？如果對調(diào)生產(chǎn)者進程中的兩個wait操作和兩個signal操作，則可能發(fā)生什么情況？答：信號量mutex的作用是保證各生產(chǎn)者進程和消費者進程對緩沖池的互斥訪問。信號量empty和full均是資源信號量，它們分別對應(yīng)于緩沖池中的空閑緩沖區(qū)和緩沖池中的產(chǎn)品，生產(chǎn)者需要通過

21、wait(empty)來申請使用空閑緩沖區(qū)，而消費者需要通過wait(full)才能取得緩沖中的產(chǎn)品，可見，這兩個信號量起著同步生產(chǎn)者和消費者的作用，它們保證生產(chǎn)者不會將產(chǎn)品存放到滿緩沖區(qū)中，而消費者不會從空緩沖區(qū)中取產(chǎn)品。在生產(chǎn)者消費者問題中，如果將兩個wait操作，即wait(full)和wait(mutex)互換位置，或者wait(empty)和wait(mutex)互換位置，都可能引起死鎖。考慮系統(tǒng)中緩沖區(qū)全滿時，若一生產(chǎn)者進程先執(zhí)行了wait(mutex)操作并獲得成功，當(dāng)再執(zhí)行wait(empty)操作時，它將因失敗而進入阻塞狀態(tài)，它期待消費者執(zhí)行signal(empty)來喚醒自

22、己，在此之前，它不可能執(zhí)行signal(mutex)操作，從而使企圖通過wait(mutex)進入自己的臨界區(qū)的其他生產(chǎn)者和所有的消費者進程全部進入阻塞狀態(tài)，系統(tǒng)進入死鎖狀態(tài)。類似地，消費者進程若先執(zhí)行wait(mutex)，后執(zhí)行wait(full)同樣可能造成死鎖。signal(full)和signal(mutex)互換位置，或者signal(empty)和signal(mutex)互換位置，則不會引起死鎖，其影響只是使某個臨界資源的釋放略為推遲一些。6.02 一組合作進程，執(zhí)行順序如下圖。請用wait、signal操作實現(xiàn)進程間的同步操作。 各進程的執(zhí)行順序P6P5P2P1P3P4答：合

23、作進程的前趨圖hgfedcbaP1P4P5P6P3P2如圖示并發(fā)進程之間的前趨關(guān)系，為了使上述進程同步，可設(shè)置8個信號量a、b、c、d、e、f、g、h，它們的初值均為0，而相應(yīng)的進程可描述為（其中“”表示進程原來的代碼）：main( )cobeginP1( ) ; signal(a); signal(b); P2( ) wait(a); ; signal(c); signal(d); P3( ) wait(b); ; signal(e); signal(f); P4( ) wait(c); wait(e); ; signal(g); P5( ) wait(d); wait(f); ; sign

24、al(h); P6( ) wait(g); wait(h); ; coend6.03在生產(chǎn)者和消費者問題中，多個生產(chǎn)者進程（Producer Process）和多個消費者進程（Consumer Process）共享一個大小為8的緩沖區(qū)，他們的信號量和共享變量設(shè)置如下：int nextc=0, nextp=0, buf8;semaphore full; empty; mutex;生產(chǎn)者進程和消費者進程問題的算法描述如下：Producer Process: Consumer Process:int itemp; int itemc;while(1) while(1)1 itemp = rand()

25、; / Generate a number 1 wait(full);2 wait(empty); 2 wait(mutex);3 wait(mutex); 3 itemc=bufnextc;4 bufnextp=itemp; 4 nextc=(nextc+1)%8;5 nextp=(nextp+1)%8;5 signal(mutex);6 signal(mutex); 6 signal(empty);7 signal(full); 7 cout << itemc << endl; （1）生產(chǎn)者進程和消費者進程的臨界區(qū)是哪些？（2）信號量full、empty和mutex

26、的初值是多少?（3）如果對調(diào)生產(chǎn)者進程中的兩個P操作即第2行和第3行，以及對調(diào)消費者進程中的兩個P操作即第1行和第2行，如下所示。可能發(fā)生什么情況？Producer Process Consumer Process1 itemp = rand(); / Generate a number 1 wait(mutex);2 wait(mutex); 2 wait(full);3 wait(empty); 3 itemc=bufnextc;（4）上面的生產(chǎn)者和消費者同步算法有一個缺點，在有空緩沖區(qū)時，當(dāng)消費者進程正在臨界區(qū)時，生產(chǎn)者進程必須等待，反之亦然。您如何可以解決這個問題，以提高生產(chǎn)者和消費者

27、進程之間并發(fā)？寫出新的生產(chǎn)者進程和消費者進程的同步算法。答：（1）生產(chǎn)者進程的臨界區(qū)是第4行和第5行；消費者進程的臨界區(qū)是第3行和第4行。（2）信號量full、empty和mutex的初值分別是：empty = 8 ， full = 0 , mutex = 1 。（3）系統(tǒng)可能會產(chǎn)生死鎖。例如，生產(chǎn)者進程得到信號量mutex，但是沒有空緩沖區(qū)即empty0時，此時生產(chǎn)者進程阻塞；而消費者進程又無法得到信號量mutex，此時消費者進程也阻塞，系統(tǒng)產(chǎn)生了死鎖。（4）增加一個信號量mutex1，初值為1，其算法如下：Producer Process Consumer Processint itemp

28、;int itemc;while(1) while(1)1 itemp = rand(); / Generate a number 1 wait(full);2 wait(empty); 2 wait(mutex);3 wait(mutex1); 3 itemc=bufnextc;4 bufnextp=itemp; 4 nextc=(nextc+1)%8;5 nextp=(nextp+1)%8; 5 signal(mutex);6 signal(mutex1); 6 signal(empty);7 signal(full); 7 cout << itemc << end

29、l; 6.04有2個合作的進程P1、P2 。他們從一臺輸入設(shè)備讀入數(shù)據(jù), P1進程讀入數(shù)據(jù)a，P2進程讀入數(shù)據(jù)b。輸入設(shè)備是一臺獨享設(shè)備 。兩個進程做如下計算：P1: x = a + bP2: y = a * b計算完成后結(jié)果的x、y由進程P1輸出。用信號量實現(xiàn)P1、P2同步算法。輸出設(shè)備P2P1Input(a)輸入設(shè)備Input(b)答：設(shè)置三個信號：s1表示數(shù)據(jù)a是否讀入，s2表示數(shù)據(jù)b是否讀入，s3表示數(shù)據(jù)y=a*b計算是否完成。P1和P2兩個進程的同步算法如下：semaphore s1=0, s2=0, s3=0;main()cobeginP1: P2: input (a)； wait

30、(s1)； signal(s1)； input (b)； wait(s2)； signal(s2)；x=a+b； y=a*b；wait(s3)； signal(s3)；Print (x,y,z)； coend7.1 假設(shè)有如下圖所示的交通死鎖情況： (1) 說明產(chǎn)生死鎖的4個必要條件在此處成立。(2) 給出一個避免死鎖的簡單規(guī)則。 答：（1） 在此處，產(chǎn)生死鎖的四個必要條件如下：1） 互斥條件。每個車道的每段道路只能被一輛車占用。2） 請求與保持條件。每個車隊占用了一個車道，并請求前方的車道，即使需等待前方車道上的車隊駛離，它仍將持有已占用的車道。3） 不搶占（剝奪）條件。在前方的車道被其它車

31、隊占用時，因為是單車道，而其它車隊又不會后退，所以無法從其它車隊處搶占車道。4） 環(huán)路等待條件。向東行駛的車隊等待向北行駛的車隊讓出車道，向北行駛的車隊等待向西行駛的車隊讓出車道，向西行駛的車隊等待向南行駛的車隊讓出車道，而向南行駛的車隊則等待向東行駛的車隊讓出車道。故存在一循環(huán)等待鏈。（2） 增加一個約束條件：只有前方兩個路口都空閑時，才能占用第一個路口?；蛘?，可在十字路口設(shè)置一交通信號燈，并使南北方向的兩個車隊和東西方向的兩個車隊互斥地使用十字路口，便可避免交通死鎖。7.11設(shè)有一系統(tǒng)在某時刻的資源分配情況如下：進程號已分配資源 最大請求資源剩余資源 A B C D A B C D A B

32、 C D P0 0 0 1 2 0 0 1 2 1 5 2 0 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 6 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6 請問：（1）系統(tǒng)中各進程尚需資源數(shù)各是多少？（2）當(dāng)前系統(tǒng)安全嗎？（3） 如果此時進程P1提出資源請求（0，4，2，0），系統(tǒng)能分配給它嗎？答：（1）尚需資源數(shù)矩陣如下：Need = Max AllocationNeedABCDP00000P10750P21002P30020P40642（2）系統(tǒng)是安全的，因為可以找到一個安全序列：<P0, P2,P3,P4,P1>（3

33、）如P1申請(0,4,2,0)，則：Request1(0,4,2,0) <=need1(0,7,5,0)Request1(0,4,2,0) <= available(1,5,2,0)新的狀態(tài)為 Allocation Max Need Available P0 0 0 1 2 0 0 1 2 0 0 0 0 1 1 0 0 P1 1 4 2 0 1 7 5 0 0 3 3 0 P2 1 3 5 4 2 3 5 6 1 0 0 2 P3 0 6 3 2 0 6 5 2 0 0 2 0 P4 0 0 1 4 0 6 5 6 0 6 4 2該狀態(tài)是安全的，存在安全序列如<P0,P2,

34、P3,P4, P1>，所以可以分配資源給P1。8.3某系統(tǒng)有五個固定分區(qū)，其長度依次為100K, 500K, 200K, 300K, 600K。今有四個進程，對內(nèi)存的需求分別是212K, 417K, 112K, 426K。當(dāng)分別用First-fit, Best-fit, Worst-fit算法響應(yīng)這四個進程的內(nèi)存申請時，請分別給出系統(tǒng)的內(nèi)存分配動態(tài)。哪種算法最有效？答：First-fit:212K進程裝到500K分區(qū)417K進程裝到600K分區(qū)112K進程裝到200K分區(qū)426K進程暫時等待Best-fit:212K進程裝到300K分區(qū)417K進程裝到500K分區(qū)112K進程裝到200K

35、分區(qū)426K進程裝到600K分區(qū)Worst-fit:212K進程裝到600K分區(qū)417K進程裝到500K分區(qū)112K進程裝到300K分區(qū)426K進程暫時等待僅就本題為例，Best-fit算法是最好的。8.5 對下列問題，試比較連續(xù)內(nèi)存分配方案、純段式分配方案、純頁式分配方案中的內(nèi)存組織方法：a. 外部碎片b. 內(nèi)部碎片c. 共享跨進程代碼的能力答：連續(xù)內(nèi)存分配會產(chǎn)生外部碎片，因為地址空間是被連續(xù)分配的，當(dāng)舊進程結(jié)束，新進程初始化的時候，洞會擴大。連續(xù)內(nèi)存分配也不允許進程共享代碼，因為一個進程的虛擬內(nèi)存段是不被允許闖入不連續(xù)的段的。純段式分配也會產(chǎn)生外部碎片，因為在物理內(nèi)存中，一個進程的段是被連

36、續(xù)放置的，以及當(dāng)死進程的段被新進程的段所替代時，碎片也將會產(chǎn)生。然而，段式分配可以使進程共享代碼；比如，兩個不同的進程可以共享一個代碼段，但是有不同的數(shù)據(jù)段。純頁式分配不會產(chǎn)生外部碎片，但會產(chǎn)生內(nèi)部碎片。進程可以在頁granularity中被分配，以及如果一頁沒有被完全利用，它就會產(chǎn)生內(nèi)部碎片并且會產(chǎn)生一個相當(dāng)?shù)目臻g浪費。在頁granularity，頁式分配也允許進程共享代碼。8.9考慮一個分頁式存儲管理系統(tǒng)，其頁表常駐內(nèi)存。（1）如果內(nèi)存訪問耗時200 ns，那么，訪問內(nèi)存中的數(shù)據(jù)需要多長時間？（2）如果引入聯(lián)想寄存器，而且75%的頁面可以從關(guān)聯(lián)寄存器中找到，那么，此時的有效訪問時間為多少？

37、(假設(shè)訪問關(guān)聯(lián)寄存器的時間可以忽略)答：（1）400納秒，其中，200納秒訪問頁表，200納秒訪問內(nèi)存中的數(shù)據(jù)。（2）有效訪問時間 = 0.75 * (200納秒訪問內(nèi)存數(shù)據(jù)+0納秒訪問關(guān)聯(lián)寄存器) + 0.25 * (200納秒訪問內(nèi)存數(shù)據(jù)+200納秒訪問頁表) = 250納秒8.12假設(shè)有下列段表：段 基地址 段長度0 219 6001 2300 142 90 1003 1327 5804 1952 96下列邏輯地址對應(yīng)的物理地址是什么？（1） 0,430（2）1,10（3）2,500（4）3,400（5）4,112答：（1）219+430=649（2）2300+10=2310（3）第2段

38、的有效長度是100，段內(nèi)偏移量500超過了這個上限，所以這是個非法地址（4）1327+400=1727（5）第4段的有效長度是96，段內(nèi)偏移量112超過了這個上限，所以這是個非法地址9.5假設(shè)一個“按需調(diào)頁”虛擬存儲空間，頁表由寄存器保存。在存在空閑頁幀的條件下，處理一次缺頁的時間是8毫秒。如果沒有空閑頁面，但待換出頁面并未更改，處理一次缺頁的時間也是8毫秒。如果待換出頁面已被更改，則需要20毫秒。訪問一次內(nèi)存的時間是100納秒。假設(shè)70的待換出頁面已被更改，請問缺頁率不超過多少，才能保證有效訪問時間小于或等于200納秒？答：設(shè)缺頁率為P。題目并沒有明確，當(dāng)缺頁中斷時，內(nèi)存中是否有空閑頁幀，所

39、以假設(shè)內(nèi)存總是忙的。訪問內(nèi)存中頁面：(1 - P) * 100ns頁面不在內(nèi)存，但不需要保存待換出頁面：P * (1 70%) * (8ms+100ns)頁面不在內(nèi)存，但需要保存待換出頁面：P * 70% * (20ms+100ns)所以，有效訪問時間=(1 - P) * 100ns + P * (1 70%) * (8ms+100ns) + P * 70% * (20ms+100ns) = 200nsP = 0.0000069.10對一個請求調(diào)頁系統(tǒng)測得如下數(shù)據(jù)：l CPU利用率20%l 用作頁面交換的磁盤的利用率97.7%l 其它I/O設(shè)備利用率5%下列措施中，哪些會改善CPU利用率（如果

40、有的話），請說明理由：(1) 安裝一個更快的CPU(2) 安裝一個更大容量的磁盤用作頁面交換(3) 增加并發(fā)進程數(shù)(4) 減少并發(fā)進程數(shù)(5) 安裝更多內(nèi)存(6) 安裝更快的硬盤，或安裝更多的硬盤和控制器(7) 增加一個預(yù)取頁面算法(8) 增加頁面長度答：首先判斷系統(tǒng)正在頻繁地進行換頁操作。所以，減少并發(fā)進程數(shù)會顯著地減少換頁操作，提高CPU的利用率。其它措施也有些效果，例如，安裝更多內(nèi)存。(1) 安裝一個更快的CPU。沒用。(2) 安裝一個更大容量的磁盤用作頁面交換。沒用，交換空間本來就足夠了。(3) 增加并發(fā)進程數(shù)。沒用，情況將會更糟。(4) 減少并發(fā)進程數(shù)。效果明顯。(5) 安裝更多內(nèi)存

41、?？赡軙行Ч?，因為空閑頁幀增加了，換頁的幾率將相對減少。(6) 安裝更快的硬盤，或安裝更多的硬盤和控制器。效果不明顯。(7) 增加一個預(yù)取頁面算法。效果不確定。(8) 增加頁面長度。如果順序訪問居多，則會減少缺頁次數(shù)。如果隨機訪問居多，因為單個頁面占用更大的物理空間，頁幀總數(shù)減少，所以缺頁次數(shù)會增加；因為頁面長度增加，頁面的傳輸時間會增加。綜上，此方案的效果不確定。9.14一頁式虛擬存儲系統(tǒng)，用于頁面交換的磁盤的平均訪問、傳輸時間是20毫秒。頁表保存在主存，訪問時間1微秒。也就是說，每引用一次指令或數(shù)據(jù)，需要訪問兩次內(nèi)存。為改善性能，我們可以增設(shè)一個關(guān)聯(lián)寄存器。如果頁表項在關(guān)聯(lián)寄存器里，則只

42、要訪問一次內(nèi)存就夠了。假設(shè)80的訪問，其頁表項在關(guān)聯(lián)寄存器中；剩下的20里，10的訪問（即總數(shù)的2）會產(chǎn)生缺頁。請計算有效訪問時間。答：有效訪問時間 = 80% * 1微秒 + (1-80%)(1-10%) * 1微秒 * 2 + 10% * (1微秒 * 2 + 20毫秒)= 0.8+0.2 * (0.9 * 2+0.1*20002)= 0.8+0.2 * 2002= 401.2微秒9.01在某請求分頁管理系統(tǒng)中，一個作業(yè)共5頁，作業(yè)執(zhí)行時依次訪問如下頁面：1，4，3，1，2，5，1，4，2，1，4，5，若分配給該作業(yè)的主存塊數(shù)為3，分別采用FIFO、LRU，試求出缺頁中斷的次數(shù)及缺頁率。(

43、要求畫出頁面置換情況表)答：(1)采用FIFO頁面置換算法，其缺頁情況如表所示： FIFO頁面置換算法的缺頁情況頁面走向143125142145塊1111222444塊244455522塊33331115缺頁缺頁中斷次數(shù)為9，缺頁率為9/12=75%。(2)采用LRU頁面置換算法，其缺頁情況如表所示。LRU頁面置換算法的缺頁情況頁面走向143125142145塊111111111塊24422444塊3335525缺頁缺頁中斷次數(shù)為8，缺頁率為8/12=67%。10.1 假設(shè)有一個文件系統(tǒng)，它里面的文件被刪除后，當(dāng)連接到該文件的鏈接依然存在時，文件的磁盤空間會再度被利用。如果一個新的文件被創(chuàng)建在

44、同一個存儲區(qū)域或具有同樣的絕對路徑名，這會產(chǎn)生什么問題？如何才能避免這些問題？答：假設(shè)F1是舊的文件，F(xiàn)2是新的文件。當(dāng)一個用戶通過已存在的鏈接訪問F1，實際卻是訪問F2。這里使用的是對文件F1的存取保護而不是與文件F2相關(guān)的存儲保護。采用刪除指向一個已刪除文件的所有鏈接的方法避免該問題?？梢酝ㄟ^幾種方法實現(xiàn)：1設(shè)置一個記錄指向一個文件的所有鏈接的鏈表，當(dāng)這個文件被刪除時，刪掉這些鏈接。2保留這些鏈接，當(dāng)試圖訪問一個已被刪除的文件時，刪掉這些鏈接。3設(shè)置一個文件的指針鏈表（或計數(shù)器），當(dāng)指向該文件的所有指針被刪除時才真正刪除這個文件。10.9 有些系統(tǒng)文件提供文件共享時候只保留文件的一個拷貝，

45、而另外的一個系統(tǒng)則是保留多個拷貝，對共享文件的每一個用戶提供一個拷貝，論述這種方法的相對優(yōu)點。答：在一個單一的復(fù)制，同時更新了一個文件可能會導(dǎo)致用戶獲得不正確的信息，文件被留在了不正確的狀態(tài). 隨著多份拷貝，它會浪費存儲而且各種副本可能不一致。11.6假設(shè)一個在磁盤上的文件系統(tǒng)，其中邏輯塊和物理塊大小為512字節(jié)。假定每個文件的信息已經(jīng)在內(nèi)存中，對于三種分配策略中的每一種（連續(xù)、鏈接、索引），請回答下面這些問題。（1）說明在這個系統(tǒng)中是如何實現(xiàn)從邏輯地址到物理地址映射的？（對于索引分配，假設(shè)文件的長度總是小于512塊）。（2）如果當(dāng)前位于邏輯塊10（即最后一次訪問的邏輯塊是10），且希望訪問邏

46、輯塊4，必須從磁盤上讀多少個物理塊？答：令Z是開始邏輯地址（塊號）。1. 若使用連續(xù)分配策略。用512去除邏輯地址，則X和Y分別表示得到的整數(shù)和余數(shù)。（1）將X加上Z得到物理塊號，Y為塊內(nèi)的位移（2）12. 若使用鏈接分配策略。用511去除邏輯地址，則X和Y分別表示得到的整數(shù)和余數(shù)。（1）查找鏈表到第X+1塊，Y+1為該塊內(nèi)的位移量。（2）43. 若使用索引分配策略。用512去除邏輯地址，則X和Y分別表示得到的整數(shù)和余數(shù)。（1）把索引塊讀入內(nèi)存中，則物理塊地址存放在索引塊在第X位置中，Y為塊內(nèi)的位移量。（2）211.01 考慮一個含有100塊的文件。假如文件控制塊（和索引塊,當(dāng)用索引分配時）已

47、經(jīng)在內(nèi)存中。當(dāng)使用連續(xù)、鏈接、單級索引分配策略時，各需要多少次磁盤I/O操作？假設(shè)在連續(xù)分配時，在開始部分沒有擴張的空間，但在結(jié)尾部分有擴張空間，并且假設(shè)被增加塊的信息已在內(nèi)存中：（1）在開始增加一塊。（2）在中間增加一塊。（3）在末端增加一塊。（4）在開始刪除一塊。（5）在中間刪除一塊。（6）在末端刪除一塊。答：各種策略相應(yīng)的磁盤I/O操作次數(shù)如表 連續(xù) 鏈接 索引a. 201 1 1b. 101 52 1c. 1 3 1d. 198 1 0e. 98 52 0f. 0 100 011.02有一磁盤組共有10個盤面，每個盤面上有100個磁道，每個磁道有16個扇區(qū)。假設(shè)分配以扇區(qū)為單位。（1）

48、 若使用位示圖管理磁盤空間，問位示圖需要占用多少空間？（2） 若空白文件目錄的每個表目占用5個字節(jié)，問什么時候空白文件目錄大于位示圖？答：空白文件目錄是管理磁盤空間的一種方法，該方法將文件存儲設(shè)備上的每個連續(xù)空閑區(qū)看作一個空白文件，系統(tǒng)為所有空白文件單獨建立一個目錄，每個空白文件在這個目錄中占一個表項；表項的內(nèi)容至少包括第一個空白塊的地址（物理塊號）、空白塊的數(shù)目。 （1）由題設(shè)所給條件可知，磁盤組扇區(qū)總數(shù)為16*100* 10=16000（個） 因此，使用位示圖描述扇區(qū)狀態(tài)需要的位數(shù)為16000（位）/8(位/字節(jié)）=2000（字節(jié)） （2）已知空白文件目錄的每個表項占5個字節(jié)而位示圖需占2000字節(jié)即2000字節(jié)可存放的表項數(shù)為2000/5=400（個）。 因此