Memory Management Problems

1. Consider a logical address space of 64 pages of 1,024 words each. How many bits are there in the logical address?

2. Given an n-bit processor and a page size of K, what is the formula that gives the number of entries in the page table? If n is 64 and K is 16KB, what is the number of entries in the page table?

3. Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600KB (in order), how would the first-fit, best-fit, and worst-fit algorithms place processes of 212 KB, 417KB, 112 KB, and 426 KB (in order)? Which algorithm makes the most efficient use of memory?

4. Assuming a 1-KB page size, what are the page numbers and offsets for the following address references (provided as decimal numbers) for a 32-bit CPU: 2375, 19366, 30000, 256, 16385.

5. Consider a paging system with the page table stored in memory. Refer to the page 318 or thereabouts of the textbook which discusses one such example problem for answering the problems below:

1. If a memory reference takes 200 nanoseconds, how long does a paged memory reference take?

2. If we add TLBs, and 75 percent of all page-table references are found in the TLBs, what is the effective memory reference time? (Assume that finding a page-table entry in the TLBs takes zero time if the entry is there.)

6. Consider the following page reference string: 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 replacement algorithms, assuming one, two, three, four, five, six, and seven frames? Remember that all frames are initially empty, so your first unique pages will cost one fault each.

• FIFO

• LRU

• Optimal

• Second chance algorithm with 3 and 4 frames

7. A 32-bit system uses a TLB of size 4MB. Assume that each entry in the TLB occupies 4B. If the entire page table has to fit into the TLB, what should be the size of the page? (Hint: You need to calculate how many entries the TLB can hold first. Then, derive the page size from this using the formula from Question 2)

8. Program P1 of size 18KB uses 3 library modules M1 (6KB), M2(4KB) and M3(16KB). Program P2 of size 22KB uses 5 library modules M4(2KB), M1, M5(12KB), M3 and M6(10KB). If the programs use static linking, what is the size of the executables assuming that it is simple addition of the sizes of all the object module sizes given above? What is the size of the executables if dynamic linking is used assuming that the stubs occupy negligible space? How much memory is saved through dynamic linking?