OS test #2: Memory Management. (Memory management slide sets 1 2)

1. In the context of memory management as described in the memory management slide set 1, (i) explain what internal fragmentation and external fragmentation are respectively. (ii) Which kind of fragmentation occurs when adopting the fixed partitioning memory management? (iii) Which kind of fragmentation occurs when adopting the dynamic partitioning memory management?

2. Consider the Buddy system as a way of memory management as described in the memory management slide set 1. Assuming that we have a 1-Mbyte free block initially, what would the Buddy system looks like after serving three memory requests for 300 Kbytes, 150Kbytes, and 100Kbytes one after another in that order. Please draw a corresponding memory allocation diagram like the one depicted in the slide set and explain why that is the result.

3. In the context of memory management as described in the memory management slide set 2, (i) what are the benefits of having virtual memory? (ii) Explain why virtual memory could be extremely slow if implemented naively? (iii) How do modern operating systems deal with these performance challenges to make virtual memory work efficiently? (iv) What is thrashing? What is locality? How does locality affect the performance of virtual memory?

4. On a 32-bit hardware platform, suppose we want to use paging to support a virtual memory address space of 4GB for each process and the page size is 1 K bytes. In the context of memory management as described in the memory management slide set 2, consider the use of flat page tables. (i) How many bits are necessary to address an address space of 4GB? (ii) If we use a one-level flat page table to support paging, how many entries are there in the table? How big would be each flat page table (in terms of bytes) if each page table entry contains a 32-bit physical address? (iii) Is it feasible for the operating system to keep in the main memory such a flat page table for each process all the time when it may have up to one thousand processes running? Why or why not?

5. On a 32-bit hardware platform, suppose we want to use paging to support a virtual memory address space of 4GB for each process and the page size is 1 K bytes. Under the exactly same context of problem #4 above and based on page 22 of slide set #2, assume we use two-level page tables instead of flat page tables and each outer table (the directory) contains 2048 entries to the next level page tables. (i) How many bits (encoding p₁) are needed to index into an outer table (a directory)? How many bits (encoding p₂) are needed to index into an inner table (a second level page table)? (ii) How big would be each outer page table (in terms of bytes) if each page table entry contains a 32-bit physical address? (iii) Is it feasible for the operating system to keep in the main memory the outer page table (the directory) for each process all the time when it may have up to one thousand processes running? Why or why not?

1. Continue with problems #4 and #5 above. Instead of creating separating page tables for the processes. Another approach to support a paging system is to use one single inverted page table. (i) Briefly explain how it works. (ii) Assume that the total physical memory is 512 Mbytes, each process ID is encoded in 12 bits (to allow up to 4096 processes), and we have a virtual memory address space of 4GB for each process and the page size is 10 K bytes. How many entries should be there in the inverted page table? How big would be the inverted page table (in terms of bytes) ?