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

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

2、法被連續(xù)分配，這樣會造成即使碎片大小之和大于新進程所需內存，但是也無法給新進程分配的情況，這就是外部碎片。外部碎片可以通過緊縮來解決。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大小的內存空間（按順序），對于首次適應，最佳適應和最差適應算法，要按順序放置212kB，417kB，112kB和426kB大小的進程會是怎樣安排的？哪個算法的內存利用率最高？答：首次適應是每次從頭開始找，直到找到第一個比當前要放置的內存大小要大的內存空間時，放置該內存。最佳適應是每次遍歷內存空間一次，找大于當前要放置的內存塊大小要大的中間的最小者，放置該內存。最差適應則相反，是取大于當前內存大小中的最大者。下面給出三種存儲分配方式的最終分配結果：首

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

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

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

7、內存利用率為（212+417+112）/（100+500+200+300+600） *100%=43.6%綜上所述，本例中最佳適應的內存利用率最高，為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.)考慮一個分頁系統(tǒng)將頁表存在內存中A 如果一個內存訪問占用200ns，那么一個頁面內存查詢占用多少時間？B 如果添加相關寄存器，且所有頁表中的75%的訪問可以在寄存器中找到，那么

9、有效內存訪問時間為多少？（假設尋找頁表條目不花時間）答：A 首先訪問內存中的頁表項，耗時200ns，然后在頁表項中查詢對應的物理地址（0ns），然后根據對應物理地址去訪問內存，耗時200ns，一共耗時為400ns。B （書上翻譯associative registers是TLB，感覺不是很恰當，但是只能當作TLB來理解）首先去查找TLB表，如果命中（75%的概率），就直接得到了物理地址，此時可以直接訪問物理地址，耗時200ns。如果TLB不命中（25%的概率），此時要按照A中的步驟先訪問頁表再訪問主存，耗時400ns。所以耗時期望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考慮下面的段表，要求對應邏輯地址的物理地址是多少答：A 0，430 先查詢段號為0的基地址為219，然后判斷是否在段內，由于430600，所以在段內，對應物理地址為219+4

11、30=649B 1，10，首先查找段號為1的基地址2300，然后判斷是否在段內，由于10100，所以不在段內，訪問非法D 3，400，首先查找段號為3的基地址1327，然后判斷是否在段內，由于40096，所以不在段內，訪問非法第九章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.某電腦提供給虛擬存儲一個232b大小的空間，電腦只有218b大小的物理存儲，虛擬存儲以分頁存儲，頁面大小4096b，一個用戶進程產生虛擬地址11123456，解釋系統(tǒng)如果建立對應的物理地

13、址，區(qū)分硬件和軟件的操作。答：11123456化成二進制表示為0001 0001 0001 0010 0011 0100 0101 0110 由于虛存有32位地址，頁面大小為212b，所以頁偏移就有12位，取虛擬地址的后12位為頁偏移，這也是物理地址上的偏移，而虛擬地址剩余的20位則是頁號，物理地址剩余的6位是物理頁號在查詢11123456時，操作系統(tǒng)先根據前20位0001 0001 0001 0010 0011查詢頁表，查找到對應的物理頁號，這是軟件操作；然后找到物理頁號后計算出對應的物理地址，這也屬于軟件操作。而在查詢頁表時，如果發(fā)生缺頁，此時對頁面的調度則是硬件操作。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.頁面調度算法應該最小化頁面錯誤，我們可以通過分配常被使用的頁面給其他內存來做最小化操作，而不是讓他們競爭一小片內存?？梢越o每個頁幀設置一個計數(shù)器來記錄和他相關的頁數(shù)，然后，為了調換頁面，在所有頁幀中選擇計數(shù)值最小的那個。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.設計一個頁面調換算法使用這個基礎思想；特別要注意的問題是：1 計數(shù)器的初值，2 何時計數(shù)器增加，3 何時計數(shù)器減少，4 頁面應該怎么被替換和選擇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個頁幀里調度以下順序的頁面會出多少錯？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個頁幀調度上述順序會出現(xiàn)多少個頁面錯誤？答：A 考慮這樣一個頁面調度算法，初始化各頁幀counter值均為0，每個頁幀每一次調入一個新的頁時，counter+1，這個值在調入的頁面不會再次出現(xiàn)時還原，即counter-1，每次有新的頁面需要調入頁幀時，先對所有頁幀進行判斷，選擇當前counter值最小的頁幀作為置換頁，如果有多個相同counter值的頁幀，則選取最先進入頁幀的頁面作為置換頁。B 1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2.以A中的調度算法來調度這些頁面，調度順序如下：（表中M代表Miss，即

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

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

21、M)8(M)8(H)8(H)4(M)4(H)2(M)頁幀22(M)5(M)5(H)5(H)頁幀33(M)3(H)7(M)7(H)7(H)頁幀44(M)4(H)9(M)9(H)共出現(xiàn)11次頁面錯誤。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?假設一個請求調頁系統(tǒng)具有一個平均訪問和傳輸時間為 20ms 的分頁磁盤。 地址轉換是通過在主存中的頁表來運行的，每次內存訪問時間為 1s。 返樣，每個通過頁表進行的內存引用都要訪問內存兩次。為了提高性能，加入一個相關內存，當頁表項在相關內存中時，可以減少內存引用的訪問次數(shù)。假設 80%的訪問發(fā)生在相關內存中，而且剩下中的 10%（總量的 2%）會導致頁錯誤。內存的有效訪問時間是多少？答：80%可以在相關內存中