/ 0
Related Content: CS604 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Operating Systems
Summary
- Thrashing
- The Working Set Model
- Page Fault Frequency Model
- Other Considerations
- Prepaging
- Page size
- Program structure
- Examples of Virtual Memory Systems
Thrashing
If a process does not have enough frames, it will quickly page fault. At this point, if a free
frame is not available, one of its pages must be replaced so that the desired page can be
loaded into the newly vacated frame. However since all its pages are in active use, the
replaced page will be needed right away. Consequently it quickly faults again and again.
The process continues to fault, replacing pages for which it then faults and brings back in
right away. This high paging activity is called thrashing. In this case, only one process is
thrashing. A process is thrashing if it is spending more time paging than executing.
Thrashing results on severe performance problems. The operating system monitors
CPU utilization and, if CPU utilization is too low, the operating system increases the
degree of multiprogramming by introducing one or more new processes to the system.
This decreases the number of frames allocated to each process currently in the system,
causing more page faults and further decreasing the CPU utilization. This causes the
operating system to introduce more processes into the system. As a result CPU utilization
drops even further and the CPU scheduler tries to increase the degree of
multiprogramming even more. Thrashing has occurred and system throughput plunges.
The page fault rate increases tremendously. As a result the effective memory access time
increases. Along with low CPU utilization, there is high disk utilization. There is low
utilization of other I/O devices. No work is getting done, because the processes are
spending all their time paging and the system spend most of its time servicing page fault.
Now the whole system is thrashing—the CPU utilization plunges to almost zero, the
paging disk utilization becomes very high, and utilization of other I/O devices becomes
very low.
If a global page replacement algorithm is used, it replaces pages with no regard to the
process to which they belong. Now suppose that a process enters a phase in its execution
and needs more frames. It starts faulting and taking frames away from other processes.
These processes need those pages however and so they also fault taking frames away from other processes. These faulting processes must use the paging device to swap pages
in and out. As they queue up for the paging device, the ready queue empties. As
processes wait for the paging device, CPU utilization decreases.
The following graph shows the relationship between the degree of multiprogramming
and CPU utilization.
Thus in order to stop thrashing, the degree of multiprogramming needs to be reduced.
The effects of thrashing can be reduced by using a local page replacement. With local
replacement if one process starts thrashing it cannot steal frames from another process
and cause the latter to thrash also. Pages are replaced with regard to the process if which
they are a part. However, if processes are thrashing they will be in the queue for the
paging device most of the time. The average service time for a page fault will increase
due to the longer average queue for the paging device. Thus the effective access time
will increase even for a process that is not thrashing, since a thrashing process is
consuming more resources
Locality of Reference
The locality model states that as a process executes it moves from locality to locality. A
locality is a set of pages that are actively used together. A program is generally composed
of several different localities, which may overlap. The following diagram shows
execution trace of a process, showing localities of references during the execution of the
process.
Working Set Model
The working set model is based on the assumption of locality. This model uses a parameter Δ to define the working set window. The idea is to examine the most recent Δ page references. The set of pages in the most recent Δ page references is called the working set. If a page is in active use it will be in the working set. If it no longer being used it will drop from the working set Δ time units after its last reference. Thus the working set is an approximation of the program’s locality.
In the following example, we use a value of Δ to be 10 and identify two localities of reference, one having five pages and the other having two pages.
We now identify various localities in the process execution trance given in the previous section. Here are the first two and last localities are: L1 = {18-26, 31-34}, L2 = {18-23, 29-31, 34}, and Last = {18-20, 24-34}. Note that in the last locality, pages 18-20 are referenced right in the beginning only and are effectively out of the locality.
The accuracy of the working set model depends on the selection of Δ. If Δ is too
small, it will not encompass the entire locality; if Δ is too large, it may overlap several
localities. In the extreme if Δ is infinite, the working set is the set of pages touched during
the process execution. The most important property of the working set is its size. If we
compute the working set size, WSSi for each process in the system we can consider
D = Σ WSSi
where, D is the total demand for frames. Each process is actively using the pages in its
working set. Thus, process i needs WSSi frames. If the total demand is greater than the
total number of frames (D > m), thrashing will occur, because some processes will not
have enough frames.
Use of the working set model is then simple, the operating system monitors the
working set of each process and allocates to that working set enough frames to provide it
with its working set size. If there are enough extra frames another process can be
initiated. If the sum of the working set sizes increases, exceeding the total number of
available frames, the operating system selects a process to suspend. The process’ pages
are written out and its frames are reallocated to other processes. The suspended process
can be restarted later.
The difficulty with the working set model is to keep track of the working set. The
working set window is a moving size window. At each memory reference a new
reference appears at one end and the oldest reference drops off the other end. We can
approximate the working set model with a fixed interval timer interrupt and a reference
bit.
For example, assume Δ = 10,000 references and the timer interrupts every 5000
references. When we get a timer interrupt we copy and clear the reference bit values for
each page. Thus if a page fault occurs we can examine the current reference bit and 2 in
memory bits to determine whether a page was used within the last 10,000 to 15,000
references. If it was used at least one of these bits will be on, otherwise they will be off.
Thus after Δ references, if one of the bits in memory = 1 then the page is in the working
set. Note that this arrangement is not completely accurate because we cannot tell where
within an interval of 5,000 a reference occurred. We can reduce the uncertainty by
increasing the number of our history bits and the frequency of interrupts. However the
cost to service these more frequent interrupts will be correspondingly higher.
Page Fault Frequency
Page fault frequency is another method to control thrashing. Since thrashing has a high page fault rate, we want to control the page fault frequency. When it is too high we know that the process needs more frames. Similarly if the page-fault rate is too low, then the process may have too many frames. The operating system keeps track of the upper and lower bounds on the page-fault rates of processes. If the page-fault rate falls below the lower limit, the process loses frames. If page-fault rate goes above the upper limit, process gains frames. Thus we directly measure and control the page fault rate to prevent thrashing. The following diagram shows the working of this scheme.
Other considerations
Many other things can be done to help control thrashing. We discuss some of the important ones in this section.
Pre-paging
An obvious property of a pure demand paging system is the large number of page faults
that occur when a process is started. This situation is the result of trying to get the initial
locality into memory. Pre-paging is an attempt to prevent this high level of initial paging.
The strategy is to bring into memory at one time all the pages that will be needed.
Pre-paging may be an advantage in some cases. The question is simply whether the
cost of using pre-paging is less than the cost of the servicing the corresponding page
faults.
Page Size
How do we select a page size? One concern is the size of the page table. For a given
virtual memory space, decreasing the page size increases the number of pages and hence
the size of the page table. Because each active process must have its own copy of the
page table, a large page size is desirable.
On the other hand, memory is better utilized with smaller pages. If a process is
allocated memory starting at location 00000, and continuing till it has as much as it
needs, it probably will not end exactly on a page boundary. Thus, a part of the final page
must be allocated. This causes internal fragmentation and to minimize this, we need a
small page size.
Another problem is the time required to read or write a page. I/O time is composed of
seek, latency and transfer times. Transfer time is proportional to the amount transferred,
and this argues for a small page size. However, latency and seek times usually dwarf
transfer times, thus a desire to minimize I/O times argues for a larger page size. I/O
overhead is also reduced with small page size because locality improves. This is because
a smaller page size allows each page to match program locality more accurately.
Some factors (internal fragmentation, locality) argue for a small page size, whereas
others (table size, I/O time) argue for a large page size. There is no best answer. However
the historical trend is towards larger pages.
Program Structure
Demand paging is designed to be transparent to the user program. However, in some
cases system performance can be improved if the programmer has an awareness of the
underlying demand paging and execution environment of the language used in the
program. We illustrate this with an example, in which we initialize a two dimensional
array (i.e., a matrix).
Consider the following program structure in the C programming language. Also note
that arrays are stored in row-major order in C (i.e., matrix is stored in the main memory
row by row), and page size is such that each row is stored on one page.
Since this code snippet initializes the matrix column by column, it causes 1024 page faults while initializing one column. This means that execution of the code causes 1024 x 1024 page faults.
Now consider the following program structure.
In this case, matrix is accessed row by row, causing 1 page fault per row. This means that execution of the code causes 1024 page faults.
Example Systems
- A demand paging system with the following utilizations:
CPU = 20%
Paging disk = 97.7%
Other I/O devices = 5%
Which of the following will improve CPU utilization?
- Install a faster CPU
- Increase degree of multiprogramming
- Decrease degree of multiprogramming
- Install more main memory
Clearly, the system is thrashing, so the first two are not going to help and the last two will help. Think about the reasons of this answer.
- Which of the following programming techniques and structures are “good” for a demand paged environment? Which are bad? Explain your answer.
- Stack
- Hash table
- Sequential search
- Binary search
- Indirection
- Vector operations
You should try to answer this question on your own. Focus on how the given data structures and techniques access data. Sequential access means “good” for demand paging (because it causes less page faults) and non-sequential access means “bad” for demand paging environment.
Google +