Final chp 9,10

# Final chp 9,10 ###### tags: `EXAM` ## Page ## Segment table ### 2017 ![](https://i.imgur.com/R6HMZL0.png =60%x) 1. What are the physical addresses for the following logical addresses? a. 0,430 b. 1,10 c. 2,500 d. 3,400 e. 4,112 $ans$ :::info a. 219+430=649 b. 2300+10=2310 c. illegal reference, trap to operating system d. 1327+400=1727 e. illegal refernce, trap to operating system ::: ## Page-replacement algorithm ### 2017 2. Suppose that there are 4 frames. How many page faults are incurred when considering the reference string by each of the following algorithms? 1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2 (a) FIFO 13 ![](https://i.imgur.com/5McgWcl.png =80%x) (b) LRU 13 ![](https://i.imgur.com/UBn5SmC.png =80%x) $c$ The optimal policy 11 ![](https://i.imgur.com/WmekWMh.png =80%x) ### 2018 10. Consider a page reference string as follows: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6 How many page faults would occur for the following page replacement algorithms assuming demand paging with four frames? a. FIFO replacement. ![](https://i.imgur.com/aaSzGnL.png) b. Optimal replacement. ![](https://i.imgur.com/XitVH83.png) c. LRU replacement. ![](https://i.imgur.com/YqV9u25.png) ## virtual memory ### 2017 3. What is the benefit of using sparse addresses in virtual memory ? $ans$ :::info Virtual address spaces that include holes between the heap and stack are known as sparse address spaces. Using a sparse address space is beneficial because the holes can be filled as the stack or heap segments grow, or when we wish to dynamically link libraries (or possibly other shared objects) during program execution. ::: ### 2018 8. Which of the following statements are correct for virtual-memory management (A) Virtual memory makes the task of programming much easier because the programmer no longer needs to worry about the address binding issue. (B) The use of modify (dirty) bit is to determine whether a page reference is a valid or invalid memory access. $C$ When the copy-on-write technique is used, only the pages that are modified by either process are copied; all unmodified pages can be shared by the parent and child processes. (D) The LRU page-replacement algorithm can be thought as the optimal page- replacement one looking backward in time. (E) Page fault rate will always decrease as the number of allocated frames increase, which are known as Belady’s Anomaly. ## illegal page addresses ### 2017 4. How are illegal page addresses recognized and trapped by the operating system $ans$ :::info Illegal addresses are trapped by the use of a valid-invalid bit, which is generally attached to each entry in the page table. When this bit is set to "valid," the associated page is in the process's logical address space and is thus a legal (or valid) page. When the bit is set to "invalid," the page is not in the process's logical address space. The operating system sets this bit for each page to allow or disallow access to the page. ::: ## Effective Access Time (EAT) ### 2017 6. Please explain the meaning of Effective Access Time (EAT)? And please calculate the EAT of the following 1-level paging system. Ignore the overheads to revise the TLB and the page table, and suppose that each page fault involves page replacement (considering both swap-in and swap-out overhead). TLB hit ratio = 90% TLB access time = 200ns Memory access time = 100us Page-fault ratio = 0.001% To access a page on a disk = 15ms (including memory access time) (You only need to list your calculation process, don’t waste your life to calculate the final result.) :::info EAT 指存取一個分頁資料所需的時間，除了記憶體存取時間外，也包含分頁錯誤等處理時間。 (1) TLB hit: 90% * (200ns+100us) (2) TLB miss and the page is in RAM: 10%*99.999%* (200ns+100us+100us) (3) TLB miss and the page is not in RAM (1 swap-out + 1 swap-in): 10%*0.001%*(200ns+100us+15ms+15ms) EAT = (1) + (2) + (3) ::: ### 2018 7. There is a 1-level paging system running with Translation Look-aside Buffer (TLB) whose hit-rate is 90%. We have known that memory access takes 100ns and TLB search takes 10ns. Please calculate the effective memory-access time in this system. $ans$ :::info 0.9*(10+100) + 0.1*(10+100+100) = 120 (ns) ::: ## Segmentation $v.s.$ Paging ## 2017 7. Briefly describe the segmentation memory management scheme. How does it differ from the paging memory management scheme in terms of the user's view of memory? $ans$ :::info Segmentation views a logical address as a collection of segments. Each segment has a name and length. The addresses specify both the segment name and the offset within the segment. The user therefore specifies each address by two quantities: a segment name and an offset. In contrast, in a paging scheme, the user specifies a single address, which is partitioned by the hardware into a page number and an offset, all invisible to the programmer. ::: ## Internal and external fragmentation 8. Distinguish between internal and external fragmentation. $ans$ :::info Fragmentation occurs when memory is allocated and returned to the system. As this occurs, free memory is broken up into small chunks, often too small to be useful. External fragmentation occurs when there is sufficient total free memory to satisfy a memory request, yet the memory is not contiguous, so it cannot be assigned. Some contiguous allocation schemes may assign a process more memory than it actually requested (i.e. they may assign memory in fixed-block sizes). Internal fragmentation occurs when a process is assigned more memory than it has requested and the wasted memory fragment is internal to a process. :::