Part I

1. A computer has four page frames. The time of loading, time of last access, and the R and M bits for each page are as shown below (the times are in clock ticks):

• Which page will NRU replace?
• Which page will FIFO replace?
• Which page will LRU replace?
• Which page will second chance replace?

2. A small computer has 8 page frames, each containing a page. The page frames contain virtual pages A, C, G, H, B, L, N, and D in that order. Their respective load times were 18, 23, 5, 7, 32, 19, 3, and 8. Their reference bits are 1, 0, 1, 1, 0, 1, 1, and 0 and their modified bits are 1, 1, 1, 0, 0, 0, 1, and 1, respectively. Which page will the second chance page replacement algorithm replace?
3. What is the difference between a physical address and a virtual address?
4. Are there any circumstances in which clock and second chance choose different pages to replace? If so, what are they?
5. A small computer has four page frames. At the first clock tick, the R bits are 0111 (page 0 is 0, the rest are 1). At subsequent clock ticks, the values are 1011, 1010, 1101, 0010, 1010, 1100, and 0001. If the aging algorithm is used with an 8-bit counter, give the values of the four counters after the last ticks.

Part II

This part requires that you write a memory manager in C. In other words, instead of wrappers as shown below

• #include <stdlib.h>
• #include mm.h

3

• void *mymalloc(size_t size)
• {
• return malloc(size);
• }

8

• void myfree(void *ptr)
• {
• free(ptr);
• }

13

• void *myrealloc(void *ptr, size_t size)
• {
• return realloc(ptr, size);
• }

18

• void *mycalloc(size_t nmemb, size_t size)
• {
• return calloc(nmemb, size);
• }

you are writing your own memory management functions, as follows:

1 #include mm.h

2

• void *mymalloc(size_t size)
• {
• // your own code
• }

7

• void myfree(void *ptr)
• {
• // your own code
• }

12

• void *myrealloc(void *ptr, size_t size)
• {
• // your own code
• }

17

• void *mycalloc(size_t nmemb, size_t size)
• {
• // your own code
• }

Note that mm.h is as given below.

1 #ifndef __MY_MM_H_INCLUDED__ 2 #define __MY_MM_H_INCLUDED__

3

4 #include <stddef.h>

5

• void *mymalloc(size_t size);
• void myfree(void *ptr);
• void *myrealloc(void *ptr, size_t size);
• void *mycalloc(size_t nmemb, size_t size);

10

11 #endif

For an example, please see pp. 185189 of The C Programming Language, Second Edition by Kernighan and Ritchie, Prentice Hall, 1988.