HW 06 Solution

It's that spooky time of year when the dead walk the Earth,

things go bump in the night, and the Centers for Disease

Control (CDC) recognizes the need for zombie preparedness

(http://www.cdc.gov/phpr/zombies.htm). Expect zombies to

be running amok at a town near you! So, hurry up and get

your anti-zombie shots ASAP!




The Clock Page Replacement requires 1 bit (the use bit)

associated with each page. Whenever we load or access a

page we set the use bit to 1. Whenever we want to replace

a page, we scan the buffer (implemented as a circular

linked-list) looking for a page with a use bit set to 0

(which we would remove). If we find a page with a use

bit of 1, we reset that bit to 0 and move on.




The Not-Recently-Used (NRU) page replacement requires 2

additional bits associated with each page (a referenced

bit “R” and modified bit “M”). Whenever we read from or

write to a page we set the R bit to 1. Whenever we write

to a page we set the M bit to 1. When a process is started,

both bits for all of its pages are set to 0. Periodically,

the OS resets the R bit to 0. When a page fault occurs

the OS inspects all pages and assigns them to 1 of 4

categories:




Class 0: R = 0, M = 0

Class 1: R = 0, M = 1

Class 2: R = 1, M = 0

Class 3: R = 1, M = 1




The OS removes (at random or first found) a page from the

lowest non-empty class set.




Your mission (should you choose to accept it) is to implement

a combined Not-Recently-Used & Clock Page Replacement algorithm

that uses 2 bits (M and R) and a circular linked list where

each page is represented by a node in the linked list. We will

call this new invention (my invention) the "Enhanced Second

Chance - Clock" alorithm (ESC-C).




To implement ESC-C, you must modify HW5 as follows:




The circular linked list will have 6 entries (can manage 6

pages) and will be managed by the parent. Each of the 5 threads

will request 1 memory page when they are created (1 free page left).

If the account balance for any thread is negative (after

ANY "W") the thread will set the R and M bits to 1 for that

initially loaded page. If the account balance for any thread

is positive (after ANY "W") the thread will set the R bit to

1 for that initially loaded page and leave the M bit as it

was. The ESC-C algorithm must reset all R bits to 0 on occasion

(I leave this to you to decide).




On occasion (e.g. randomly) each thread will require an

additional page, generating a page fault. At this point the

thread generating the page fault must: 1) print "Page fault in

thread XXX", 2) locate a page to replace and print the details

(R and M bits and ownership) of the page being removed, 3) load

the new page, 4) set the bits to some initial value (see

notes), and 5) treat this page as the "initially" loaded page

(as described in the paragraph above).




Once more than 1 additional page has been loaded, it is very

likely that a thread will have no pages in memory. That

thread will also generate a page fault whenever it encounters

a "W".




You will also need a mutex to protect the links in the linked

list to prevent any possible corruptions of the linked list.




NOTES:

------

Initially loaded pages will need some protection to keep them in

until first used.




REQUIREMENTS:

-------------

1. Your program must run on Linux Mint (Leonard 110/112).




2. Your full name must appear as a comment at the beginning of your

program.




3. Your source code must be named hw6-yourname.c or hw6-yourname.cpp




4. Your program must use mutex(s).




5. Your program must use pthreads.