Problem set 03 Solution

    1. Definitions:

        a. s a memory-management scheme that splits the address space into equal sized units called pages.
        b.  ​is one solution to the external fragmentation problem, which shuffles the memory contents so as to place all free memory together in one large block.

        c. ​is a memory-management scheme that splits the memory into unequal units that may have sizes more meaningful or appropriate to the program. It actually maps the programmer’s view to the actual physical memory. Consequently, it provides more freedom for the system to manage memory while the programmer would have a more natural programming environment.

        d. makes a process to be moved temporarily out of memory to a backing store and then brought back into memory for continued execution.
        e. is one of severe performance problems that happens for a process if it is spending more time paging than executing.

    2. Suppose two processes need to be mapped into main memory using pages. Process P1 consists of 7 pages, and process P2 consists of 4 pages. Assume main memory consists of 16 frames, a logical page is the same size as a physical frame, and that 4 entries in a page table fills up a frame of memory. Assume also that within the process' allocated address spaces, there are two pages of shared code 'X' and 'Y' common to both address spaces of Frame #10 and #12, respectively.

Complete the following design for a memory management system that can store these two processes and their page tables in RAM by dragging the answers to their corresponding position in the following tables.

P1’s Page Table

P2’s Page Table







Logical
Physical
Shared
Logical
Physical
Shared
Page
Frame
Code
Page
Frame
Code






0
1

0
0







1
2

1
11







2
3

2
10







3
8

3
12







4
9










5

Y









6

X









Frame #
RAM



0





1





2





3





4
P1
Page Table entries 0-3


5




6
P2
Page Table entries 0-3


7




8





9





10
P1
-and P2 -
11





12
P1
- ​​and P2 - ​
13



14




15
P1
Page Table entries​


    3. Suppose on-demand paging is employed in addition to TLB caching. The time for a TLB hit is T = 1 ns, a memory read M = 10 ns, and a disk read D = 10 ms. Let P_TLB = 90% the probability of a TLB hit, and P = 0.001 the probability of a page fault given a TLB miss.

What is the probability of a TLB miss?



What is the probability of a NO page fault?



What is the calculated average memory access time in Nanoseconds (up to 3 decimal places)?

​ns
    4. The Least Recently Used (LRU) page replacement policy does not suffer from Belady’s Anomaly. Intuitively, given the following sequence of page references:

1234215671

And assuming main memory is initially unloaded. Fill in the following table to show the page faulting behavior using the LRU page replacement policy. Case 1: Given a frame allocation of 2


1
2
3
4
2

1
5
6

7

1













































































Case 2: Given a frame allocation of 4
























1
2

3

4
2

1
5
6

7

1

















































































































































Call

        ◦ A = Number of page faults in Case 1

        ◦ B = Number of page faults in Case 2 A is ​B

    5. Given a frame allocation of 3, and the following sequence of page references 324342234567765456721

and assuming main memory is initially unloaded, show the page faulting behavior using the following page replacement policies. How many page faults are generated by each page replacement algorithm?

    a. FIFO



    b. OPT



    c. LRU



    d. Which generates the fewest page faults?



    6. A memory manager for a variable-sized region strategy has a free list of blocks of size 600, 400, 1000, 2200, 1600, and 1050 bytes. What block will be selected to honor a request for:

        a. 1603 bytes using a best-fit policy?

        b. 949 bytes using a best-fit policy?



        c. 1603 bytes using a worst-fit policy?



        d. 349 bytes using a worst-fit policy?



        e. 1603 bytes using a first-fit policy? (assume the free list is ordered as listed above)


        f. 1049 bytes using a first-fit policy?