北工大操作系統(tǒng)作業(yè)合集

1、第八次作業(yè)基礎作業(yè)1.假設一個磁盤驅動器有 5000 個柱面，從 0 到 4999。驅動器正在為 143 的一個請求服務， 且前面的一個請求在 125。按照 FIFO的順序， 即將到來的請求是 86，1470 ，913，1774，948， 1509， 1022，1750，130。請按照 FCFS、SSTF、SCAN、LOOK、C-SCAN、C-LOOK， 要滿足隊 列中的服務要求磁頭總的移動距離是多少。143 86 1470 913 1774 948 1509 1022 1750 130a. FCFS : 143, 86, 1470, 913, 1774, 948, 1509, 1022, 1

2、750, 130.總尋道距離 7081.b. SSTF : 143, 130, 86, 913, 948, 1022, 1470, 1509, 1750, 1774.總尋道距離 1745.c. SCAN ：143, 913, 948, 1022, 1470, 1509, 1750, 1774, 4999, 130, 86.總尋道距離 9769.d. LOOK:143, 913, 948, 1022, 1470, 1509, 1750, 1774, 130, 86.總尋道距離 3319.e. C-SCAN : 143, 913, 948, 1022, 1470, 1509, 1750, 1774

3、, 4999, 0, 86, 130.總尋道距離 9813f. C-LOOK : 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 86, 130.總尋道距離 3363.2. 為什么文件分配的位圖必須保存在大容量存儲器中，而不是主存中？ 答：因為如果保存在內存中，當系統(tǒng)崩潰時， 這些空閑區(qū)間的信息將會被丟失，而如果保存 在大容量存儲器中就可以解決這個問題。3假設要為一個文件換一個名字。一種選擇是使用操作系統(tǒng)提供的RENAME 方法，另一種方法是：把文件復制為新文件，然后刪除原來的文件以實現(xiàn)重命名。請問，這兩種方法在 實現(xiàn)上有什么不同？答：RENAME方法

4、是修改目錄文件的文件名部分， 而刪除原來文件再重命名則需要再創(chuàng)立一 個新文件， 目錄文件中增加一項，分配新空間；刪除目錄文件中的文件項目，然后回收占用 的空間。4請解釋使用索引節(jié)點有什么好處 答：減小目錄文件的大小，提高查找文件的效率 5在 UNIX 中 open 系統(tǒng)調用絕對需要么？如果沒有會產生什么結果。答：如果沒有 open 命令， 那么每個 read 命令都需要確定要打開的文件名。系統(tǒng)必須找到文 件的 i 節(jié)點， 雖然這個數據放入 cache 可以減少一些時間， 但是當數據變化的時候， i 節(jié)點的 數據需要刷新到磁盤上。6UNIX 系統(tǒng)中有關盤塊的分配與釋放是借助超級塊中的棧來進行的。

5、假如某個時刻系統(tǒng)狀況如下圖所示， 若此時某個進程要刪除文件 A，并歸還它所占用的盤塊 220，110，645，549， 176。請說明過程，并給出刪除完畢后有關數據及表目的更改情況。786278802301106457. 考慮一個索引節(jié)點所表示的 UNIX文件的組織。 假設有 12 個直接塊指針，在每個索引節(jié) 點中有一個單重、雙重和三重間接指針。此外，假設系統(tǒng)塊大小和磁盤扇區(qū)大小都是8K，如果磁盤塊指針是 32 位，其中 8 位表示物理磁盤， 24 位表示物理塊，那么a. 該系統(tǒng)支持的最大文件大小是多少？b. 該系統(tǒng)支持的最大文件分區(qū)是多少？c. 假設主存中除了文件索引節(jié)點外沒有其他信息，訪問

6、在位置12423956 中的字節(jié)需要多少磁盤訪問？ 答：a. 通過用塊大小除以指針大小得到盤塊指針的數目： 每塊 8K/4 = 2K這樣 I節(jié)點可以支持的最大文件容量是 :12+2k+2k*2k+2k*2k*2k=(12+2K+4M+8G)*8K( 塊大小 )= 96KB + 16MB + 32GB + 64TB 直接尋址 一級間接尋址 二級間接尋址 三級間接尋址b. 在一個分區(qū)中識別一個塊需要 24位。所以 :*8K =16M*8K=128GBc. 使用從 (a) 得到的信息 , 發(fā)現(xiàn)直接塊只能表示 96KB, 而一次間接塊表示 16MB. 題目中要求的 請求位置在 13M 左右，使用一次間

7、接塊 .就可以了。所以要用兩次磁盤訪問，一次訪問一次 間接塊，另一次訪問包含數據的盤塊第七次作業(yè)1什么是設備無關性？ 應用程序只按套路調用操作系統(tǒng)提供的功能即可，不關心實際的設備是什么，這就是 與設備無關性2以下各項工作由 I/O 軟件的哪一層完成？a. 為一個磁盤讀操作計算磁道、扇區(qū)、磁頭；設備驅動程序b. 向設備寄存器寫命令；中斷處理程序c. 檢查用戶是否允許使用設備；設備獨立性軟件d. 將二進制整數轉換成 ASCII碼以便打印硬件3為什么在要打印的文件通常都假脫機輸出到磁盤上？答：達到緩沖的目的，實現(xiàn)提高 I/O 設備性能的目的。為了打印一個文件，一個進程首先要生成需要打印的整個文件并把

8、它放在假脫機目錄里。由守護進程打印該目錄下的文件， 該進程是允許使用打印機設備文件的唯一進程。 通過保護設備文件來防止用戶直接使用， 可以解決某些進程不必要地長期空占打印機的問題。第六次作業(yè)1假設頁表在內存保存的分頁系統(tǒng)，a.如果一次訪問內存用 200ns，那么訪問一個頁內的一次數據訪問用多少時間？b.如果加入 TLB，有 75%的命中率，那么內存有效訪問時間是多少？ a）訪問一個頁內數據需要訪問兩次內存，第一次訪問內存中的頁表，第二次根據頁表中的信息形成的物理地址訪問內存訪問數據，所以要用 200*2=400nsb）加入 TLB，獲得物理地址的過程為：先在 TLB 中查找，如果 TLB中命中

9、，則直接獲得 物理地址，如果 TLB 中不存在，則去訪問頁表，所以需要的訪問時間為0.25*200=50ns總共需要的時間為 50ns+200ns=250ns2. 在一個虛擬存儲管理系統(tǒng)中采用頁式方法對內存空間進行管理，它有 24 位的虛擬地址 空間，而實際的物理地址空間是 16 位，頁框大小為 2k。假設有兩個進程 A 和 B。其中 A 進 程的 0、2頁已經調入到內存的 2、3 號頁框； B進程的 1、3頁已經調入到內存的 7、8 號頁 框。請問： A 進程的虛擬地址 12FF可以轉換成什么物理地址？ B進程的虛擬地址 17BA可以 轉換成什么物理地址？如果不能轉換，操作系統(tǒng)會執(zhí)行什么操作

10、？頁框大小為 2k=211, 有 11 位的位移 。A 進程： 12FF=0001 0010 1111 1111 ,00010=2,A 進程中 2 頁調進 3 號框，因此物理地址為： 0001 1010 1111 1111B 進程： 17BA=0001 0111 1011 1010 ，在進程 2 中沒有 2 號頁，需要的頁面不在內存時，請 求調入所需的頁面 判斷對錯如果缺頁率太高，通常說明一個進程分得的頁框太多了。第五次作業(yè)基礎作業(yè)1內部碎片與外部碎片之間的區(qū)別？內部碎片： 內存分頁時， 最后一頁未裝滿的部分就是內部碎片。 或因調入的數據小于分 區(qū)而產生分區(qū)空間的浪費，稱為內部碎片。外部碎片：

11、 共享時要分段， 在段的換入換出時未使用的部分就是外部碎片。 一開始運行 得很好，但是在執(zhí)行一段時間后 , 會出現(xiàn)一些小的洞。這種在分區(qū)外的洞稱為外部碎片。內 存按順序有 100k，500k， 200k，300k，600k，用首次適應、最佳適應和最差適應如何放置 212k，417k，112k ，426k 的進程？首次適應： 212k 分配給 500k，417k 分配給 600k ，112k 分配給 200k，426k 沒有可分配最佳適應：首先將 212k 分配給 300k ，將 417k 分配給 500k，將 112k 分配給 200k，將 426k 分配給 600k ；最差適應：將 212k

12、 分配給 600k ，將 417 分配給 500k ，將 112 分配給 300k ，最后 426 沒有可分配的。2假設一個有 8 個 1k 頁面的邏輯地址空間，映射到一個32 個頁框的物理內存，問：邏輯地址多少位？物理地址多少位？邏輯地址： 13 位物理地址： 15 位4（ 8.12 ）有段表段基地址長度02196001230014290100313275804195296下面的物理地址是多少？a)0,430; b)1,10; c)2,500; d)3,400; e)4,122a、 649 b 、 2310 c 、 590 d 、1727 e 、 2074 5在頁面大小為 4k 的系統(tǒng)中，根

13、據圖中所示 頁表，下面的邏輯地址經過重定位之后的物理地址是什么？a)20; b)4100; c)8300A、49172 b 、 53252 c 、615486一臺計算機為每個進程提供 65536 字節(jié)的地址空間，頁面的大小為 4k。 一個程序有 32768 字節(jié)的正文， 16386 字節(jié)的數據， 15870 字節(jié)的堆棧，此 程序是否能裝入此地址空間？若頁面大小為 512 字節(jié)呢？4k 不能， 512 字節(jié)可以；解析過程：65536/4096=16 ，共計 16 個頁面；正文需要頁面： 32768/4096=8數據需要頁面： 16386/4096=5對戰(zhàn)需要： 15870/4096=4共需 17

14、 個頁面，所以不能裝入512 字節(jié)同理可得正好能夠裝入 補充作業(yè)判斷對錯 編譯時綁定是大多數通用操作系統(tǒng)使用的地址綁定方法。 X 最佳適配法可以在內存分配過程中留下最小的洞。 為解決內存分配時導致的外部碎片可以采用壓縮的方法來解決， 因此需要在地址綁定的時候 采用靜態(tài)重定位方法。 X如果現(xiàn)在基地址寄存器的值是 1200，界限寄存器的值是 350，那么當前進程產生對絕對地址 1551 的訪問是合法的。 X可重入代碼不可以被共享。 X基礎作業(yè)1考慮下面一組進程， 進程占用的 CPU區(qū)間長度以毫秒計算。 假設在 0時刻進程以 P1, P2,P3, P4, P5的順序到達。進程區(qū)間時間優(yōu)先級P1103

15、P211P323P414P552（1）畫出 4 個 Gantt 圖，分別演示使用 FCFS, SJF, 非搶占優(yōu)先級（數字越小表示優(yōu)先級 越高）和 RR（時間片 =1）算法調度時進程的執(zhí)行過程。（2）每個進程的周轉時間是多少？（3）每個進程在每種調度算法下的等待時間是多少？解：（ 1） GANTT圖FCFS：P1 P2 P3 P4 P5SJF：P2 P4 P3 P5 P1非搶占優(yōu)先級： P2 P5 P1 P3 P4RR：P1 P2 P3 P4 P5 P1 P3 P5 P1 P5 P1 P5 P1 P5 P1（2）周轉時間：FCFSSJF非搶占優(yōu)先級RRP110191619P211112P313

16、4187P4142194P5199614（3） 等待時間：FCFSSJF非搶占優(yōu)先級RRP10969P210001P3112165P4131183P5144192考慮下面一個系統(tǒng)在某一個時刻的狀態(tài)。AllocationMax AvailableA B C DA B C DA B C DP00 0 1 20 0 1 2 1 5 2 0P11 0 0 01 7 5 0P21 3 5 42 3 5 6P30 6 3 20 6 5 2P40 0 1 40 6 5 6使用銀行家算法回答下面的問題：（1） Need 矩陣的內容（2） 系統(tǒng)是否處于安全狀態(tài)（3） 如果從進程 P1 發(fā)來一個請求（ 0，4，2

17、， 0），這個請求是否可以立即滿足？解：1） Need 矩陣ABCDP00000P10750P21002P30020P406422)處于安全狀態(tài)，先是 P0完成，之后 P3，之后 P2，之后 P1，之后 P4。(3) 可以立即滿足，滿足后仍處于安全狀態(tài)。補充作業(yè)判斷對錯在 RR調度中，上下文切換的時間應該小于時間片的長度。XSJF調度算法是最適合分時系統(tǒng)的調度算法。XFCFS調度算法只能是非搶占式的。如果資源分配圖中有環(huán)，那么就一定有死鎖。X死鎖的時候系統(tǒng)一定處于非安全狀態(tài)。第三次作業(yè)一、基礎作業(yè)1. 什么是忙等待？ 持續(xù)地檢測一個變量直到它具有某一個特定值稱為忙等待。2吸煙者問題：有 3 個

18、吸煙者和一個供應者。 第一個吸煙者有自己的煙草； 第二個吸 煙者有自己的紙；第三個吸煙者有自己的火柴。供應者每次隨機放兩樣東西到桌子上 提供給 3 個吸煙者之中的一個以完成吸煙。請用信號量為吸煙者和供應者進程編寫程 序。Semaphore n2=0;Semaphore s=1;0 代表煙草， 1 代表紙， 2 代表火柴 ./ 供應者程序Void procucer()While(1)隨機生成一個在 02之間的數 ;Wait(s);將除了表示的另外兩件東西放在桌子上 ;Signal(ni);/ 吸煙者程序Void smoker(int i)While(1)Wait(ni);Somke();Sign

19、al(s);二、 補充作業(yè)1假設有三個進程 R、W1、W2 共享緩沖區(qū) B。B 中只能存放一個數。 R每次從輸入設 備中讀一個整數放入 B中。如果這個整數是奇數，由 W1 取出打印。如果這個整數是偶數， 則由 W2取出打印。規(guī)定僅當 B中沒有數據或數據已經被打印才會啟動R去讀數。 W1、W2對 B 中的數據不能重復打印，當 B 中沒有數據時也不能打印。要求用信號量操作寫出R、W1、W2 三個進程的程序。(請詳細描述所使用變量的含義)Semaphore s=1;/ 進程 R 可以存入緩沖區(qū) B 的數據個數信號量Semaphore n2=0;/n0/n1 表示進程 W1/W2 可以從緩沖區(qū) B 中

20、取出的數據個數；/ 進程 RVoid R()While(1)讀入一個正數 m;Wait(s);將m放入 B中；if(m/2!=0)Signa(n0);ElseSignal(n1);Void w1()While(1);Wait(n0);從緩沖區(qū) B 取數據 k;Signal(s);打印 K;Void w1()While(1);Wait(n1);從緩沖區(qū) B 取數據 k;Signal(s);打印 K;2 有一個鐵籠子， 獵手放入老虎，農民放入豬，動物園等待取走老虎，飯店等待取走 豬。籠子中只能放入一個動物。請使用信號量方法為獵手、農民、動物園、飯店進程編寫程 序。Semaphore cage=1;

21、/ 可以放入籠子中的動物數量Semaphore tiger=0;/ 動物園從籠子中取出老虎的數量Semaphore pig=0;/ 飯店從籠子中取出豬的數量 / 獵手進程Void hunter()While(1)Wait(cage); 將老虎放入籠子 ; Signal(tiger);Void farmer()While(1)Wait(cage);將豬放入籠子 ; Signal(pig);Void zoo()While(1)wait(tiger); 從籠子中取出老虎 ; signal(cage);Void restaurant()While(1)waitl(pig); 從籠子中取出豬； sign

22、al(cage);3某寺廟，有小、老和尚若干。 有一個水缸，由小和尚提水入缸供老和尚飲用。水缸可容 10 桶水。水取自一個井中，水井窄，每次只能容一個水桶。水桶總數為3。水缸每次進出也僅 1 桶水， 不可以同時進行。 請設置合適的信號量描述小和尚、 老和尚取水、入水的 算法。Semaphore bucket=3;/ 水桶的數量Semaphore tank=1;/ 水缸每次能容水桶的數量 ;Semaphore s=10;/ 水缸容水桶水量 ;Semaphore well=1;/ 井每次能容水桶的數量；Semaphore empty=0;/ 水缸中現(xiàn)有的水量；Void youngmonk()Whi

23、le(1)Wait(bucket);獲得水桶 ;Wait(well); 井中取水； signal(well); Wait(s);Wait(tank);倒水入水缸 ;Signal(tank);Signal(bucket);Signal(empty);Void oldmonk()While(1)Wait(empty);Wait(bucket); 獲得水桶； Wait(tank); 從水缸中取水； Signal(tank); Signal(s); Signal(bucket);4. 判斷對錯(1) 一個系統(tǒng)中進程之間可能是獨立的也可能是合作的。(2) 如果用鎖來保護臨界區(qū)可以防止競爭條件。(3) 一

24、個計數信號量的值只能 取 0 或者 1. X(4) 在管程中本地變量只能由本地過程來訪問。5. 選擇題(1) 關于競爭條件那句話是對的？BA. 幾個線程要并發(fā)訪問同樣的數據B. 幾個線程要并發(fā)訪問并修改同樣的數據C. 只有在執(zhí)行結果與執(zhí)行順序無關的時候發(fā)生(2) 關于原子指令那句話是對的？BA. 原子指令只能由一條機器指令組成B. 作為一個單獨的，不可以中斷的單元執(zhí)行C. 不能用于解決臨界區(qū)問題(3) 一個臨界區(qū)的解決方案不需要實現(xiàn)下面的哪一條？CA. 互斥 B. 有空讓進C. 原子性 D. 有限等待(4) 當低優(yōu)先級的進程正在訪問一個數據的時候，若一個高優(yōu)先級的進程需要訪問同樣 的數據，可能

25、發(fā)生 AA. 優(yōu)先級反轉 B. 死鎖C. 競爭條件 D. 臨界區(qū)附加題： 1獨木橋問題：某條河上只有一座獨木橋，兩邊都有人要過河，為保證安全，一個方向 有人過河另一個方向的人就要等待， 并且允許一個方向上的人連續(xù)過河。 請使用信號量實現(xiàn) 正確的管理。Semaphore s=1;/ 兩岸過河能使用的橋的數量；Semaphore left=1,right=1;Int leftcount=0,rightcount=0;/ 左岸過河進程Void Left()While(1)Wait(left); Leftcount+; If(leftcount=1)Wait(s); Signal(left); 左岸過

26、河； Wait(left);Leftcount-;If(leftcount=0)Signal(s); Signal(left);/ 右岸進程Void right()While(1)Wait(right);Rightcount+;If(rightcount=1)Wait(s); Signal(right); 右岸過河 ; Wait(right); Rightcount-; If(rightcount=0) Signal(s); Signal(right);第二次作業(yè)一、基礎作業(yè)1. 論述短期、中期、長期調度之間的區(qū)別短期調度從就緒隊列中選擇進程執(zhí)行并把CPU分配給它。中期調度主要在分時系統(tǒng)中使用

27、。 將內存中的作業(yè)換出到外存中等到內存允許的情況下 再換入到內存中執(zhí)行。長期調度確定把哪個作業(yè)放到內存中執(zhí)行。 它們之間的主要區(qū)別是執(zhí)行的頻率不同。短期調度執(zhí)行頻率高而長期調度執(zhí)行頻率低。2. 兩個進程進行上下文切換的操作通常， 操作系統(tǒng)必須保存當前運行進程的狀態(tài)并恢復下一個要調度的進程的狀態(tài)。保存一個進程的狀態(tài)通常包括 CPU所有寄存器的值和內存的分配情況。3. 用戶級線程和內核級線程之間的區(qū)別？相互對比的優(yōu)勢在哪里？(1) 內核不知道用戶級線程的存在，但內核知道內核級線程的存在(2) 內核調度內核級線程，而用戶級線程則由線程庫調度在要體現(xiàn)系統(tǒng)靈活性的時候使用用戶級線程好， 因為用戶級線程可

28、以自己設計自己的調度。 內核級線程則被內核知道， 所 以可以保證一個線程阻塞時可以調度一個進程的另一個線程，減少系統(tǒng)開銷。三、補充作業(yè)1假設有一個進程，它的工作流程是先運行150ms，然后進行 I/O，最后執(zhí)行 250ms 結束。如果系統(tǒng)中的進程有三個狀態(tài)，當時間片為 200ms 時，請寫出進程 A 從被系統(tǒng)接納到運行 結束所經歷的狀態(tài)轉換并說明原因。答：被系統(tǒng)接納之后：就緒 -運行（原因：被調度執(zhí)行）、運行-阻塞（原因：執(zhí)行 I/O 操作）、阻塞 -就緒（原因： I/O 操作完成）、就緒 -運行（原因：被調度執(zhí)行）、運行 -就緒（原 因：時間片到）、就緒 -運行（原因：被調度執(zhí)行）、結束。2. 圖中程序的運行結果。Val