湖南大學(xué)操作系統(tǒng)作業(yè)-(5)7頁(yè)

1、操作系統(tǒng)第五次作業(yè)第八章8.1 Explain the difference between internal and external fragmentation.簡(jiǎn)述內(nèi)部碎片和外部碎片的區(qū)別答： 內(nèi)部碎片存在于塊的內(nèi)部，如內(nèi)存塊大小為512k，而某邏輯內(nèi)存要求一個(gè)200k大小的塊，此時(shí)操作系統(tǒng)會(huì)分配給它一個(gè)大小為512k的塊（由于塊是內(nèi)存分配的最小單元），所以會(huì)造成了312k大小的內(nèi)存碎片，這部分碎片即使是空的也無(wú)法使用，稱作內(nèi)部碎片。減少內(nèi)部碎片可以通過(guò)減小塊的大小來(lái)解決。 外部碎片是指在連續(xù)內(nèi)存分配的進(jìn)程裝入和移出內(nèi)存的過(guò)程中，空閑的內(nèi)存空間被分成了較多小片段，這些小片段不連續(xù)，所以無(wú)

2、法被連續(xù)分配，這樣會(huì)造成即使碎片大小之和大于新進(jìn)程所需內(nèi)存，但是也無(wú)法給新進(jìn)程分配的情況，這就是外部碎片。外部碎片可以通過(guò)緊縮來(lái)解決。8.3 Given five memory partitions of 100 KB, 500 KB, 200 KB,300 KB, and 600KB (in order), how would each of the first-fit,best-fit, and worst-fit algorithms place processes of 212 KB,417 KB, 112 KB, and 426 KB (in order)? Which algori

3、thm makes the most efficient use of memory?給出100kb，500kB，200kB，300kB，600kB大小的內(nèi)存空間（按順序），對(duì)于首次適應(yīng)，最佳適應(yīng)和最差適應(yīng)算法，要按順序放置212kB，417kB，112kB和426kB大小的進(jìn)程會(huì)是怎樣安排的？哪個(gè)算法的內(nèi)存利用率最高？答：首次適應(yīng)是每次從頭開(kāi)始找，直到找到第一個(gè)比當(dāng)前要放置的內(nèi)存大小要大的內(nèi)存空間時(shí)，放置該內(nèi)存。最佳適應(yīng)是每次遍歷內(nèi)存空間一次，找大于當(dāng)前要放置的內(nèi)存塊大小要大的中間的最小者，放置該內(nèi)存。最差適應(yīng)則相反，是取大于當(dāng)前內(nèi)存大小中的最大者。下面給出三種存儲(chǔ)分配方式的最終分配結(jié)果：首

4、次適應(yīng)：對(duì)于212kB的進(jìn)程，選擇第一個(gè)大于它大小的內(nèi)存空間，為500kB，并分配給它相應(yīng)大小的空間，該部分剩余大小500-212=288KB對(duì)于417kB的進(jìn)程，選擇第一個(gè)大于它的大小的內(nèi)存空間，為600kB，分配給它相應(yīng)大小的空間，該部分剩余大小為600-417=183KB對(duì)于112kB的進(jìn)程，選擇第一個(gè)大于它大小的內(nèi)存空間，為288kB，分配給它相應(yīng)大小的空間，該部分剩余大小288-112=176KB對(duì)于426kB的進(jìn)程，找不到比他大的內(nèi)存空間，無(wú)法分配，只能等待其他進(jìn)程釋放空間才能為它分配空間。內(nèi)存利用率為 （212+417+112）/（100+500+200+300+600） *10

5、0%=43.6%最佳適應(yīng)：對(duì)于212kB的進(jìn)程，選擇大于它大小的內(nèi)存空間中的最小者，為300kB，并分配給它相應(yīng)大小的空間，該部分剩余大小300-212=88KB對(duì)于417kB的進(jìn)程，選擇大于它大小的內(nèi)存空間中的最小者，為500kB，分配給它相應(yīng)大小的空間，該部分剩余大小為500-418=83kB對(duì)于112kB的進(jìn)程，選擇大于它大小的內(nèi)存空間中的最小者，為200kB，分配給它相應(yīng)大小的空間，該部分剩余大小200-112=88kB對(duì)于426kB的進(jìn)程，選擇大于它大小的內(nèi)存空間中的最小者，為600kB，分配相應(yīng)大小的空間，該部分生育大小為600-426=174kB內(nèi)存利用率為 （212+417+1

6、12+426）/（100+500+200+300+600） *100%=68.6%最差適應(yīng)：對(duì)于212kB的進(jìn)程，選擇大于它大小的內(nèi)存空間中的最大者，為600kB，并分配給它相應(yīng)大小的空間，該部分剩余大小600-212=388kB對(duì)于417kB的進(jìn)程，選擇大于它大小的內(nèi)存空間中的最大者，為500kB，分配給它相應(yīng)大小的空間，該部分剩余大小為500-417=83kB對(duì)于112kB的進(jìn)程，選擇大于它大小的內(nèi)存空間中的最大者，為388kB，分配給它相應(yīng)大小的空間，該部分剩余大小388-112=276kB對(duì)于426kB的進(jìn)程，找不到比他大的內(nèi)存空間，無(wú)法分配，只能等待其他進(jìn)程釋放空間才能為它分配空間。

7、內(nèi)存利用率為（212+417+112）/（100+500+200+300+600） *100%=43.6%綜上所述，本例中最佳適應(yīng)的內(nèi)存利用率最高，為68.6%8.9 Consider a paging system with the page table stored in memory.a. If a memory reference takes 200 nanoseconds, how long does a paged memory reference take?b. If we add associative registers, and 75 percent of all page

8、-table references are found in the associative registers, what is the effective memory reference time? (Assume that finding a page-table entry in the associative registers takes zero time, if the entry is there.)考慮一個(gè)分頁(yè)系統(tǒng)將頁(yè)表存在內(nèi)存中A 如果一個(gè)內(nèi)存訪問(wèn)占用200ns，那么一個(gè)頁(yè)面內(nèi)存查詢占用多少時(shí)間？B 如果添加相關(guān)寄存器，且所有頁(yè)表中的75%的訪問(wèn)可以在寄存器中找到，那么

9、有效內(nèi)存訪問(wèn)時(shí)間為多少？（假設(shè)尋找頁(yè)表?xiàng)l目不花時(shí)間）答：A 首先訪問(wèn)內(nèi)存中的頁(yè)表項(xiàng)，耗時(shí)200ns，然后在頁(yè)表項(xiàng)中查詢對(duì)應(yīng)的物理地址（0ns），然后根據(jù)對(duì)應(yīng)物理地址去訪問(wèn)內(nèi)存，耗時(shí)200ns，一共耗時(shí)為400ns。B （書(shū)上翻譯associative registers是TLB，感覺(jué)不是很恰當(dāng)，但是只能當(dāng)作TLB來(lái)理解）首先去查找TLB表，如果命中（75%的概率），就直接得到了物理地址，此時(shí)可以直接訪問(wèn)物理地址，耗時(shí)200ns。如果TLB不命中（25%的概率），此時(shí)要按照A中的步驟先訪問(wèn)頁(yè)表再訪問(wèn)主存，耗時(shí)400ns。所以耗時(shí)期望E（t）=200*0.75+400*0.25=250ns8.12

10、 Consider the following segment table:Segment Base Length0 219 6001 2300 142 90 1003 1327 5804 1952 96What are the physical addresses for the following logical addresses?a. 0,430 b. 1,10 c. 2,500 d. 3,400 e. 4,112考慮下面的段表，要求對(duì)應(yīng)邏輯地址的物理地址是多少答：A 0，430 先查詢段號(hào)為0的基地址為219，然后判斷是否在段內(nèi)，由于430600，所以在段內(nèi)，對(duì)應(yīng)物理地址為219+4

11、30=649B 1，10，首先查找段號(hào)為1的基地址2300，然后判斷是否在段內(nèi)，由于10100，所以不在段內(nèi)，訪問(wèn)非法D 3，400，首先查找段號(hào)為3的基地址1327，然后判斷是否在段內(nèi)，由于40096，所以不在段內(nèi)，訪問(wèn)非法第九章9.4 A certain computer provides its users with a virtual-memory space of 2 32 bytes. The computer has 2 18 bytes of physical memory. The virtual memory is implemented by paging, and th

12、e page size is 4096 bytes. A user process generates the virtual address 11123456. Explain how the system establishes the corresponding physical location. Distinguish between software and hardware operations.某電腦提供給虛擬存儲(chǔ)一個(gè)232b大小的空間，電腦只有218b大小的物理存儲(chǔ)，虛擬存儲(chǔ)以分頁(yè)存儲(chǔ)，頁(yè)面大小4096b，一個(gè)用戶進(jìn)程產(chǎn)生虛擬地址11123456，解釋系統(tǒng)如果建立對(duì)應(yīng)的物理地

13、址，區(qū)分硬件和軟件的操作。答：11123456化成二進(jìn)制表示為0001 0001 0001 0010 0011 0100 0101 0110 由于虛存有32位地址，頁(yè)面大小為212b，所以頁(yè)偏移就有12位，取虛擬地址的后12位為頁(yè)偏移，這也是物理地址上的偏移，而虛擬地址剩余的20位則是頁(yè)號(hào)，物理地址剩余的6位是物理頁(yè)號(hào)在查詢11123456時(shí)，操作系統(tǒng)先根據(jù)前20位0001 0001 0001 0010 0011查詢頁(yè)表，查找到對(duì)應(yīng)的物理頁(yè)號(hào)，這是軟件操作；然后找到物理頁(yè)號(hào)后計(jì)算出對(duì)應(yīng)的物理地址，這也屬于軟件操作。而在查詢頁(yè)表時(shí)，如果發(fā)生缺頁(yè)，此時(shí)對(duì)頁(yè)面的調(diào)度則是硬件操作。9.13 A pag

14、e-replacement algorithm should minimize the number of page faults. We can do this minimization by distributing heavily used pages evenly over all of memory, rather than having them compete for a small number of page frames. We can associate with each page frame a counter of the number of pages that

15、are associated with that frame. Then,to replace a page, we search for the page frame with the smallest counter.頁(yè)面調(diào)度算法應(yīng)該最小化頁(yè)面錯(cuò)誤，我們可以通過(guò)分配常被使用的頁(yè)面給其他內(nèi)存來(lái)做最小化操作，而不是讓他們競(jìng)爭(zhēng)一小片內(nèi)存?？梢越o每個(gè)頁(yè)幀設(shè)置一個(gè)計(jì)數(shù)器來(lái)記錄和他相關(guān)的頁(yè)數(shù)，然后，為了調(diào)換頁(yè)面，在所有頁(yè)幀中選擇計(jì)數(shù)值最小的那個(gè)。A Define a page-replacement algorithm using this basic idea. Specifically addre

16、ss the problems of (1) what the initial value of the counters is, (2) when counters are increased, (3) when counters are decreased, and (4) how the page to be replaced is selected.設(shè)計(jì)一個(gè)頁(yè)面調(diào)換算法使用這個(gè)基礎(chǔ)思想；特別要注意的問(wèn)題是：1 計(jì)數(shù)器的初值，2 何時(shí)計(jì)數(shù)器增加，3 何時(shí)計(jì)數(shù)器減少，4 頁(yè)面應(yīng)該怎么被替換和選擇b. How many page faults occur for your algorithm

17、 for the following reference string, for four page frames?1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2.在你的算法用4個(gè)頁(yè)幀里調(diào)度以下順序的頁(yè)面會(huì)出多少錯(cuò)？c. What is the minimum number of page faults for an optimal page-replacement strategy for the reference string in part b with four page frames?最優(yōu)置換算法中用

18、4個(gè)頁(yè)幀調(diào)度上述順序會(huì)出現(xiàn)多少個(gè)頁(yè)面錯(cuò)誤？答：A 考慮這樣一個(gè)頁(yè)面調(diào)度算法，初始化各頁(yè)幀counter值均為0，每個(gè)頁(yè)幀每一次調(diào)入一個(gè)新的頁(yè)時(shí)，counter+1，這個(gè)值在調(diào)入的頁(yè)面不會(huì)再次出現(xiàn)時(shí)還原，即counter-1，每次有新的頁(yè)面需要調(diào)入頁(yè)幀時(shí)，先對(duì)所有頁(yè)幀進(jìn)行判斷，選擇當(dāng)前counter值最小的頁(yè)幀作為置換頁(yè)，如果有多個(gè)相同counter值的頁(yè)幀，則選取最先進(jìn)入頁(yè)幀的頁(yè)面作為置換頁(yè)。B 1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2.以A中的調(diào)度算法來(lái)調(diào)度這些頁(yè)面，調(diào)度順序如下：（表中M代表Miss，即

19、出現(xiàn)頁(yè)面錯(cuò)誤，H代表Hit，即頁(yè)面命中）初始狀態(tài)下，頁(yè)幀全空，此時(shí)對(duì)于按順序的訪問(wèn)1、2、3、4均缺頁(yè)，需要調(diào)入頁(yè)面：頁(yè)幀11(M)頁(yè)幀22(M)頁(yè)幀33(M)頁(yè)幀44(M)在調(diào)入頁(yè)面5的時(shí)刻，由于頁(yè)幀1-4的counter值全為1，故選擇最先進(jìn)入的頁(yè)幀1進(jìn)行置換，隨后來(lái)的頁(yè)面3和4的訪問(wèn)，由于仍存在頁(yè)幀中，故均命中：頁(yè)幀11(M)5(M)頁(yè)幀22(M)頁(yè)幀33(M)3(H)頁(yè)幀44(M)4(H)由于完成了3的訪問(wèn)后，頁(yè)面3不會(huì)再次出現(xiàn)，故此時(shí)頁(yè)幀3的counter值已經(jīng)為0，是當(dāng)前頁(yè)幀中的最小值，故此時(shí)對(duì)頁(yè)面1的調(diào)度會(huì)優(yōu)先選擇頁(yè)幀3進(jìn)行置換。由于完成了頁(yè)面1的訪問(wèn)后，頁(yè)面1不會(huì)再次出現(xiàn)，所以

20、頁(yè)幀1的counter值此時(shí)為1，頁(yè)幀3的counter值此時(shí)為0。頁(yè)幀11(M)5(M)頁(yè)幀22(M)頁(yè)幀33(M)3(H)1(M)頁(yè)幀44(M)4(H)同理，按此順序進(jìn)行上述的調(diào)度，下表給出4個(gè)頁(yè)幀所對(duì)應(yīng)的調(diào)度順序。頁(yè)幀11(M)5(M)5(H)5(H)2(M)頁(yè)幀22(M)8(M)8(H)8(H)頁(yè)幀33(M)3(H)1(M)6(M)7(M)7(H)7(H)4(M)4(H)頁(yè)幀44(M)4(H)9(M)9(H)統(tǒng)計(jì)上表可以得到總頁(yè)面錯(cuò)誤次數(shù)為：12次C 基于最優(yōu)置換的調(diào)度頁(yè)面最優(yōu)置換算法會(huì)調(diào)度所有頁(yè)幀，置換最長(zhǎng)時(shí)間不會(huì)使用的頁(yè)。使用最優(yōu)置換算法得到的示意圖如下：頁(yè)幀11(M)1(H)6(

21、M)8(M)8(H)8(H)4(M)4(H)2(M)頁(yè)幀22(M)5(M)5(H)5(H)頁(yè)幀33(M)3(H)7(M)7(H)7(H)頁(yè)幀44(M)4(H)9(M)9(H)共出現(xiàn)11次頁(yè)面錯(cuò)誤。9.14Consider a demand-paging system with a paging disk that has an average access and transfer time of 20 milliseconds. Addresses are translated through a page table inmain memory, with an access time o

22、f 1 microsecond per memory access. Thus, each memory reference through the page table takes two accesses. To improve this time, we have added an associative memory that reduces access time to one memory reference, if the page-table entry is in the associative memory.Assume that 80 percent of the acc

23、esses are in the associative memory and that, of the remaining, 10 percent (or 2 percent of the total) cause page faults. What is the effective memory access time?假設(shè)一個(gè)請(qǐng)求調(diào)頁(yè)系統(tǒng)具有一個(gè)平均訪問(wèn)和傳輸時(shí)間為 20ms 的分頁(yè)磁盤(pán)。 地址轉(zhuǎn)換是通過(guò)在主存中的頁(yè)表來(lái)運(yùn)行的，每次內(nèi)存訪問(wèn)時(shí)間為 1s。 返樣，每個(gè)通過(guò)頁(yè)表進(jìn)行的內(nèi)存引用都要訪問(wèn)內(nèi)存兩次。為了提高性能，加入一個(gè)相關(guān)內(nèi)存，當(dāng)頁(yè)表項(xiàng)在相關(guān)內(nèi)存中時(shí)，可以減少內(nèi)存引用的訪問(wèn)次數(shù)。假設(shè) 80%的訪問(wèn)發(fā)生在相關(guān)內(nèi)存中，而且剩下中的 10%（總量的 2%）會(huì)導(dǎo)致頁(yè)錯(cuò)誤。內(nèi)存的有效訪問(wèn)時(shí)間是多少？答：80%可以在相關(guān)內(nèi)存中