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

1、第八次作業(yè)基礎作業(yè)1.假設一個磁盤驅(qū)動器有5000個柱面，從0到4999。驅(qū)動器正在為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, 1750, 130. 總尋道距離70

2、81.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, 4999, 0, 86, 130

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

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

5、45，549，176。請說明過程，并給出刪除完畢后有關數(shù)據(jù)及表目的更改情況。1001997862788023011064525491767. 考慮一個索引節(jié)點所表示的UNIX文件的組織。假設有12個直接塊指針，在每個索引節(jié)點中有一個單重、雙重和三重間接指針。此外，假設系統(tǒng)塊大小和磁盤扇區(qū)大小都是8K，如果磁盤塊指針是32位，其中8位表示物理磁盤，24位表示物理塊，那么a.該系統(tǒng)支持的最大文件大小是多少？b.該系統(tǒng)支持的最大文件分區(qū)是多少？c.假設主存中除了文件索引節(jié)點外沒有其他信息，訪問在位置12423956中的字節(jié)需要多少磁盤訪問？答：a.通過用塊大小除以指針大小得到盤塊指針的數(shù)目：每塊8K

6、/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 左右，使用一次間接塊.就可以了。所以要用兩次磁盤訪問，一次訪問一次間接塊，另一次訪問包含數(shù)據(jù)的盤塊第七次作業(yè)1 什么是設備無關性？ 應用程序只按套路調(diào)用操作系統(tǒng)提供

7、的功能即可，不關心實際的設備是什么，這就是 與設備無關性2以下各項工作由I/O軟件的哪一層完成？a.為一個磁盤讀操作計算磁道、扇區(qū)、磁頭；設備驅(qū)動程序b.向設備寄存器寫命令； 中斷處理程序c.檢查用戶是否允許使用設備； 設備獨立性軟件d.將二進制整數(shù)轉換成ASCII碼以便打印 硬件3 為什么在要打印的文件通常都假脫機輸出到磁盤上？答：達到緩沖的目的，實現(xiàn)提高I/O設備性能的目的。為了打印一個文件，一個進程首先要生成需要打印的整個文件并把它放在假脫機目錄里。由守護進程打印該目錄下的文件，該進程是允許使用打印機設備文件的唯一進程。通過保護設備文件來防止用戶直接使用，可以解決某些進程不必要地長期空占

8、打印機的問題。第六次作業(yè)1假設頁表在內(nèi)存保存的分頁系統(tǒng)，a.如果一次訪問內(nèi)存用200ns，那么訪問一個頁內(nèi)的一次數(shù)據(jù)訪問用多少時間？b.如果加入TLB，有75%的命中率，那么內(nèi)存有效訪問時間是多少？a)訪問一個頁內(nèi)數(shù)據(jù)需要訪問兩次內(nèi)存，第一次訪問內(nèi)存中的頁表，第二次根據(jù)頁表中的信息形成的物理地址訪問內(nèi)存訪問數(shù)據(jù)，所以要用200*2=400nsb)加入TLB，獲得物理地址的過程為：先在TLB中查找，如果TLB中命中，則直接獲得物理地址，如果TLB中不存在，則去訪問頁表，所以需要的訪問時間為0.25*200=50ns總共需要的時間為50ns+200ns=250ns2. 在一個虛擬存儲管理系統(tǒng)中采用

9、頁式方法對內(nèi)存空間進行管理，它有24位的虛擬地址空間，而實際的物理地址空間是16位，頁框大小為2k。假設有兩個進程A和B。其中A進程的0、2頁已經(jīng)調(diào)入到內(nèi)存的2、3號頁框；B進程的1、3頁已經(jīng)調(diào)入到內(nèi)存的7、8號頁框。請問：A進程的虛擬地址12FF可以轉換成什么物理地址？B進程的虛擬地址17BA可以轉換成什么物理地址？如果不能轉換，操作系統(tǒng)會執(zhí)行什么操作？頁框大小為2k=211,有11位的位移 。A進程：12FF=0001 0010 1111 1111 ,00010=2,A進程中2頁調(diào)進3號框，因此物理地址為：0001 1010 1111 1111B進程：17BA=0001 0111 1011

10、 1010，在進程2中沒有2號頁，需要的頁面不在內(nèi)存時，請求調(diào)入所需的頁面判斷對錯如果缺頁率太高，通常說明一個進程分得的頁框太多了。 X第五次作業(yè)基礎作業(yè)1 內(nèi)部碎片與外部碎片之間的區(qū)別？ 內(nèi)部碎片：內(nèi)存分頁時，最后一頁未裝滿的部分就是內(nèi)部碎片。或因調(diào)入的數(shù)據(jù)小于分區(qū)而產(chǎn)生分區(qū)空間的浪費，稱為內(nèi)部碎片。 外部碎片：共享時要分段，在段的換入換出時未使用的部分就是外部碎片。一開始運行得很好，但是在執(zhí)行一段時間后,會出現(xiàn)一些小的洞。這種在分區(qū)外的洞稱為外部碎片。內(nèi)存按順序有100k，500k，200k，300k，600k，用首次適應、最佳適應和最差適應如何放置212k，417k，112k，426k的

11、進程？首次適應：212k分配給500k，417k分配給600k，112k分配給200k，426k沒有可分配 最佳適應：首先將212k分配給300k，將417k分配給500k，將112k分配給200k，將426k分配給600k；最差適應：將212k分配給600k，將417分配給500k，將112分配給300k，最后426沒有可分配的。2 假設一個有8個1k頁面的邏輯地址空間，映射到一個32個頁框的物理內(nèi)存，問：邏輯地址多少位？物理地址多少位？邏輯地址：13位物理地址：15位4（8.12）有段表段基地址長度02196001230014290100313275804195296下面的物理地址是多少？

12、a)0,430; b)1,10; c)2,500; d)3,400; e)4,122a、649 b、2310 c、590 d、1727 e、20745在頁面大小為4k的系統(tǒng)中，根據(jù)圖中所示頁表，下面的邏輯地址經(jīng)過重定位之后的物理地址是什么？a)20; b)4100; c)8300A、49172 b、53252 c、615486 一臺計算機為每個進程提供65536字節(jié)的地址空間，頁面的大小為4k。一個程序有32768字節(jié)的正文，16386字節(jié)的數(shù)據(jù)，15870字節(jié)的堆棧，此程序是否能裝入此地址空間？若頁面大小為512字節(jié)呢？4k不能，512字節(jié)可以；解析過程：65536/4096=16，共計16

13、個頁面；正文需要頁面：32768/4096=8數(shù)據(jù)需要頁面：16386/4096=5對戰(zhàn)需要：15870/4096=4共需17個頁面，所以不能裝入512字節(jié)同理可得正好能夠裝入補充作業(yè)判斷對錯編譯時綁定是大多數(shù)通用操作系統(tǒng)使用的地址綁定方法。 X最佳適配法可以在內(nèi)存分配過程中留下最小的洞。 為解決內(nèi)存分配時導致的外部碎片可以采用壓縮的方法來解決，因此需要在地址綁定的時候采用靜態(tài)重定位方法。 X如果現(xiàn)在基地址寄存器的值是1200，界限寄存器的值是350，那么當前進程產(chǎn)生對絕對地址1551的訪問是合法的。 X可重入代碼不可以被共享。 X基礎作業(yè)1 考慮下面一組進程，進程占用的CPU區(qū)間長度以毫秒計

14、算。假設在0時刻進程以P1, P2, P3, P4, P5的順序到達。進程區(qū)間時間優(yōu)先級P1 10 3P2 1 1P3 2 3P4 1 4P5 5 2（1）畫出4個Gantt圖，分別演示使用FCFS, SJF, 非搶占優(yōu)先級（數(shù)字越小表示優(yōu)先級越高）和RR（時間片=1）算法調(diào)度時進程的執(zhí)行過程。（2）每個進程的周轉時間是多少？（3）每個進程在每種調(diào)度算法下的等待時間是多少？解：（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 P

15、5 P1(2)周轉時間：FCFSSJF非搶占優(yōu)先級RRP110191619P211112P3134187P4142194P5199614(3)等待時間：FCFSSJF非搶占優(yōu)先級RRP10969P210001P3112165P4131183P5144192考慮下面一個系統(tǒng)在某一個時刻的狀態(tài)。AllocationMax AvailableA B C D A B C D A B C DP00 0 1 2 0 0 1 21 5 2 0P11 0 0 0 1 7 5 0P21 3 5 42 3 5 6P30 6 3 20 6 5 2P40 0 1 40 6 5 6使用銀行家算法回答下面的問題：（1）N

16、eed矩陣的內(nèi)容（2）系統(tǒng)是否處于安全狀態(tài)（3）如果從進程P1發(fā)來一個請求（0，4，2，0），這個請求是否可以立即滿足？解：（1）Need矩陣ABCDP00000P10750P21002P30020P40642（2）處于安全狀態(tài)，先是P0完成，之后P3，之后P2，之后P1，之后P4。（3）可以立即滿足，滿足后仍處于安全狀態(tài)。補充作業(yè)判斷對錯在RR調(diào)度中，上下文切換的時間應該小于時間片的長度。XSJF調(diào)度算法是最適合分時系統(tǒng)的調(diào)度算法。XFCFS調(diào)度算法只能是非搶占式的。 如果資源分配圖中有環(huán)，那么就一定有死鎖。X死鎖的時候系統(tǒng)一定處于非安全狀態(tài)。 第三次作業(yè)一、基礎作業(yè) 1.什么是忙等待？ 持

17、續(xù)地檢測一個變量直到它具有某一個特定值稱為忙等待。 2吸煙者問題：有3個吸煙者和一個供應者。第一個吸煙者有自己的煙草；第二個吸 煙者有自己的紙；第三個吸煙者有自己的火柴。供應者每次隨機放兩樣東西到桌子上 提供給3個吸煙者之中的一個以完成吸煙。請用信號量為吸煙者和供應者進程編寫程 序。 Semaphore n2=0; Semaphore s=1; 0代表煙草，1代表紙，2代表火柴. /供應者程序 Void procucer() While(1) 隨機生成一個在02之間的數(shù); Wait(s); 將除了表示的另外兩件東西放在桌子上; Signal(ni); /吸煙者程序 Void smoker(in

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

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

20、。Semaphore cage=1;/可以放入籠子中的動物數(shù)量Semaphore tiger=0;/動物園從籠子中取出老虎的數(shù)量Semaphore pig=0;/飯店從籠子中取出豬的數(shù)量/獵手進程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) wai

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

22、nk() While(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)如果用鎖來保

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

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

25、l(left); 左岸過河； 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è)1、 基礎作業(yè)1. 論述短期、中期、長期調(diào)度之間的區(qū)別 短期調(diào)度從就緒隊列中選擇進程執(zhí)行并

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

27、活性的時候使用用戶級線程好，因為用戶級線程可以自己設計自己的調(diào)度。內(nèi)核級線程則被內(nèi)核知道，所以可以保證一個線程阻塞時可以調(diào)度一個進程的另一個線程，減少系統(tǒng)開銷。三、 補充作業(yè)1假設有一個進程，它的工作流程是先運行150ms，然后進行I/O，最后執(zhí)行250ms結束。如果系統(tǒng)中的進程有三個狀態(tài)，當時間片為200ms時，請寫出進程A從被系統(tǒng)接納到運行結束所經(jīng)歷的狀態(tài)轉換并說明原因。 答：被系統(tǒng)接納之后：就緒-運行（原因：被調(diào)度執(zhí)行）、運行-阻塞（原因：執(zhí)行I/O操作）、阻塞-就緒（原因：I/O操作完成）、就緒-運行（原因：被調(diào)度執(zhí)行）、運行-就緒（原因：時間片到）、就緒-運行（原因：被調(diào)度執(zhí)行）、結束。2. 圖中程序的運行結果。 Value=103. 圖中程序運行完共有多少進程？ 8 4. 判斷對錯（1）程序是活動的實體，進程是被動的實體。 X（