OperatingSystem-Homework 4 Solved

Part I (50%)
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):

Page
Loaded
Last Reference
R M
0
126
279
0        0
1
230
260
1        0
2
120
272
1        1
3
160
280
1        1
(a)    Which page will NRU replace?

(b)    Which page will FIFO replace?

(c)    Which page will LRU replace?

(d)    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 (50%)
This part requires that you write a memory manager in C. In other words, instead of wrappers as shown below

 

1    #include <stdlib.h>

2    #include "mm.h"

3

4               void *mymalloc(size_t size)

5               {

6               return malloc(size);

7               }

8

9                 void myfree(void *ptr)

10               {

11               free(ptr);

12               }

13

14               void *myrealloc(void *ptr, size_t size)

15               {

16               return realloc(ptr, size);

17               }

18

19               void *mycalloc(size_t nmemb, size_t size)

20               {

21               return calloc(nmemb, size);

22               }

 

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

 

1 #include "mm.h"

2

3               void *mymalloc(size_t size)

4               {

5               // your own code

6               }

7

8                void myfree(void *ptr)

9                {

10              // your own code

11              }

12

13              void *myrealloc(void *ptr, size_t size)

14              {

15              // your own code

16              }

17

18              void *mycalloc(size_t nmemb, size_t size)

19              {

20              // your own code

21              }

 

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

6    void *mymalloc(size_t size);

7    void myfree(void *ptr);

8    void *myrealloc(void *ptr, size_t size);

9    void *mycalloc(size_t nmemb, size_t size);

10

11 #endif


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