Chapter 3: Memory Management: Recent Systems, Flynn and McHoes, Understanding Operating Systems, Second Edition, PWS Publishing Co. (1997)

Lesson A: Paged Memory Allocation, Demand Paging, First in First Out, Least Recently Used.

Problems 3, 4, 5, 6, 8, 10 (Problem 1 needs information from lesson 3B, so its solution will be given in another set.)

Problem 3.  What purpose does the "modified" bit serve in a demand paging system?

Answer:  If you require a page to be swapped out and must allow for the possibility of it being swapped back in, you need to make sure that the page has the latest changes when it is again swapped in.  If changes have been made to a page selected for swapping out, you must save the page to disk.  If changes have NOT been made to a page selected for swapping out, you can immediately overwrite memory with a new page, without writing the old page back to disk.  Disk access is sl.o..w... .   You do not want to spend time writing to disk unless you really have to.  The "modified" bit tells you if a change has been made to a page since it has been loaded into memory.  As usual, a little bit of information can save you a lot of seek time.

Problem 4.  Answer these questions:

1. What is the cause of thrashing?
2. How does the operating system detect thrashing?
3. Once thrashing is detected, what can the operating system do to eliminate it?

Thrashing is act of an operating system wasting a significant proportion of its time accessing secondary storage to retrieve referenced pages that are not in memory.

a.  Thrashing can occur both in a demand paging system, and in a circular job stream.  In a demand paging system, thrashing can be caused by a loop that references a page that is not resident in memory.  This has two causes: a loop within a process that is not assigned enought memory to contain its working set, and a loop of context switching that swaps out a job that is quickly swapped back in.  The working set problem can occur, for example, if a logic loop subtends three pages, but the job is only permitted two pages.

b.  The text does not tell us in Chapter 3 how to detect if the operating system is thrashing.  If you were an operating system, what would you need to know in order to detect thrashing? 

For the case of a logic loop within a process, if crossing a page boundary consistently results in swapping in a page that has been in before, that is an indication of thrashing.   So, how do you detect if a page has been in memory before?  You could set a bit in the page map table when a page is swapped out to make room for another page.   If a page is swapped in that has that bit set, you know that page has been in memory at least once before.  That is a possible indication of thrashing.   Alternately, you could keep a count of how many times a page has been swapped out, use a shift register for a counter, or the job time at which a page has last been swapped out.

A shift register counter is very fast compared to a normal counter, but the number of states you can count is limited to just the number of bits in the shift register. The shift register below shifts everything left by one bit, and then sets the right-most bit.   This can be done in one machine cycle.  The number of times it has been shifted is the number of bits turned on.  For the register below, the left-most bit is turned on during the eighth shift.  You can efficiently test the most significant bit, and the least significant bit.  On the other hand, a counter has to handle carries from one bit position to the next.

The text's answer key suggests monitoring the input and output queues as well as CPU and device utilization.  An indication that the CPU is not working efficiently is the condition of the input queues become congested while the output queues become empty.  High CPU utilization without corresponding peripheral devices utilization may be an indication of thrashing.  Poor response time or low throughput may also be indications of thrashing.

c.  You can reduce thrashing by increasing the working set of a job so the offending page remains in memory longer.  If you run out of memory, you can suspend one or more jobs to make room for the working set.  By reducing thrashing, you increase system efficiency, and provide overall better service to all jobs in the queue, including the jobs you must suspend temporarily.

Problem 5. What purpose does the referenced bit serve in a demand paging system?

Answer:  The "referenced" bit indicates whether or not the page has been referenced.  Since this bit is periodically reset to zero by the operating system, a "set" condition implies that it has been recently set.  This bit is used by the "Least Recently Used" algorithm to determine which pages are to be swapped out.  This can be particularly useful in detecting a change in the working set of a job as the job proceeds from one phase (possibly a segment) to another. 

Problem 6.  Given that main memory is composed of three page frames for public use and that a program requests pages in the following order:  dcbadcedcbae:

1. Using the FIFO page removal algorithm, do a page trace analysis indicating page faults with asterisks (*).  Then compute the failure and success ratios.

The page frames in the table above represent the page frame in memory in which the page is stored.  Once a page is placed into a page frame, the page is not relocated in the scheme above. 

For the First In First Out scheme, the position of a page in the stack above represents the age of the page since it was last fetched into memory.  A page is placed onto the top of the stach when a page is fetched (retrieved from secondary storage).  The position of a page in the stack is not changed if the page is referenced while already in memory.

For this example, there are 9 page faults for 12 page references.  Declare a "success" for our strategy if it results in a reference without generating a page fault.  Declare a "failure" for our strategy if it results in a reference that generates a page fault. We then compute:

• Success Ratio = 3/12 = 0.25 = 25%
• Failure Ratio = 9/12 = 0.75 = 75%

2. Increase the size of memory so it contains four page frames for public use.  Using the same page requests as above and FIFO, do another page trace analysis and compute the failure and success ratios.

• Success Ratio = 2/12 = 0.17 = 17%
• Failure Ratio = 10/12 = 0.83 = 83%

3. Did the result correspond with your intuition?  Explain.

This result is counterintuitive.  I expected to increase the success ratio by adding more memory.

Problem 8.  To implement LRU each page needs a referenced bit.  If we wanted to implement a "least-frequently-used" (LFU) page removal algorithm, in which the page that was used the least would be removed from memory, what would we need to add to the tables?  What software modifications would have to be made to support this new algorithm?

1. Least Recently Used:

Keep a stack of all pages ever loaded for the specific job.  Suppose memory has 4 page frames. Then the top 4 pages of the stack are those currently in memory.  When a page is referenced (whether in memory or retrieved from secondary storage), move its token to the top of the stack.  If a page needs to be removed to make room for a referenced page, the page to be removed is the one that shifts to position 5 of the stack.

Compared to the previous problem, no additional data is needed.  The algorithm for stack handling must be modified slightly.

2. Least Frequently Used

This method requires something more than just a stack.  Some method is needed to record a function of frequency, such as a count over some specified period of time.   A count may be implemented either as an incrementing register or by a shift register.  You just have to interpret the contents of the register differently.   A practical issue is to determine how far into the past to consider.  Do you want a sliding window average, an exponential forgetting factor over time, or some other means to emphasize the recent past?  As a process ages, the rate at which it is referenced is likely to change.

Problem 10.   Given that main memory is composed of four page frames and that a program has been divided into eight pages (numbered 0 through 7):

1. How many page faults will occur using FIFO with a request list of:  0, 1, 7, 2, 3, 2, 7, 1, 0, 3  if the four page frames are initially empty?