[SOLVED] Operating-System Homework 4

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):

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?

1

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.

2

Part II

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

1. 1  #include <stdlib.h>
2. 2  #include “mm.h”

3
4 void *mymalloc(size_t size) 5{

6 return malloc(size); 7}
8

9. 9  void myfree(void *ptr)
10. 10  {
11. 11  free(ptr);
12. 12  }

13

14. 14  void *myrealloc(void *ptr, size_t size)
15. 15  {
16. 16  return realloc(ptr, size);
17. 17  }

18

19. 19  void *mycalloc(size_t nmemb, size_t size)
20. 20  {
21. 21  return calloc(nmemb, size);
22. 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 11 12 13 14 15 16 17 18 19 20 21

    // your own code

}

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

    // your own code

}

void *mycalloc(size_t nmemb, size_t size)
{

    // your own code

}

Note that mm.h is as given below.

1. 1  #ifndef __MY_MM_H_INCLUDED__
2. 2  #define __MY_MM_H_INCLUDED__

3
4 #include <stddef.h>

3

5

6. 6  void *mymalloc(size_t size);
7. 7  void myfree(void *ptr);
8. 8  void *myrealloc(void *ptr, size_t size);
9. 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.