In
the presentation so far, the page fault rate is not a serious problem, because
each page is faulted for at most one when it is first referenced. This
representation is not strictly accurate.
Consider
that, if a process of 10 pages actually uses only one half of them, than demand
paging saves the I/O necessary t load the five pages that are nevred used.
We
could also increase our degree of multiprogramming by running twice as many
processes thus, if we had 40 frames, we could run eight processes, rather than
the four that could run if each required 10 frames (five of which were never
used).
If
we increase our degree of multiprogramming, we are over-allocating memory. if
we run six processes each of which is 10 pages in size, but actually uses only
five pages, we have higher CPU utilization and throughput, with 10 frames to
spare.
It
is possible however, that each of these processes, for a particular data set,
many suddenly try to use al 10 of its pages, resulting in a need for 60 frames,
when only 40 are available.
Although
this situation may be unlikely as we increase the multiprogramming level, so
that the average memory usage is close to the available physical memory. (in
our example, why stop at the multiprogramming level of six. When we can move to
a level of seven or eight ?).
Over-allocating
will show up in the following way.
While
a user processes is executing, a page fault occurs. The hardware traps to the
operating system, which checks its internal tables to see that this is a page
fault and not an illegal memory access. The operating system determines where
the desired page is residing on the
disk, but then finds there are no free frames on the free frames list all
memory is in use.
The operating system has several option at
this point, it could terminate the user process.
However, demand paging is something that
the operating system is doing the improved the computer system’s utilization
and throughput. Users should not be aware that their processes are running on a
paged system. Paging should be logically transparent to the user. So this
option is not the best choice.
We
cloud swap out a process, freeing all
its frames and reducing the level of multiprogramming. This option is a good
idea at times.
But
there is more interesting possible pagereplacement
Page
replacement takes the following approach if no frames is free, we find one that
is not currently being used and free it.
We
can free the frame by writing is contents to swap space, and changing the page
table (and all other tables) to indicate that the page is no longer in memory.
The freed frame can now be used to hold the
page for which the processes faulted.
The page fault service routine is now
modified to page replacement.
1. Find
the location of the desired page on the disk.
2. Find a free frame:
a. If
there is free frame, use it.
b. Otherwise,
use a page-replacement algorithm to select the victim frame.
c. Write
the victim page to the disk, change the page and frame tables accordingly.
3. Read the desired page into the (newly) free
frame; change the page and frame
tables.
4. Restart
the user process.
If no frames are free, two pages transfers (one out and
one in) are required.
This situation doubles the page fault service time and
will increase the effective access time accordingly.
This overhead can be reduced by the use of the modify
(dirty) bit. Each page or frame any have a modify bit it in the hardware
whenever any word or byte in the page is written.
Modify bit indicates that
the page has been modified.
When we select a page for replacement, we examine its modified
bit.
If the bit is set, we know
that the page has been modified since it was read in from the disk. In this
case, we must write that page to the disk.
If the modify bit is not
set, the page has not been modified since it was read into memory.
Therefore, if the copy of
the page on the disk has not been overwritten, we can avoid writing the memory
page to the disk because it is already there.
This scheme can reduce
significantly the time to service a page fault, since it reduces I/O time by
one –half if the page is not modified.
Page replacement is basic
to demand paging.
With the mechanism, a very
large virtual memory can be provide for programmers on a smaller physical
memory.
With non demand paging,
the size of the logical address space is no longer constrained by physical
memory. If we have a user process of 20 pages,
we can executing it in t 10 frames simply by using demand paging, and a
replacement algorithm to find a free whenever necessary.
If a page that has been
modified is to be replaced, it constant are copied to the disk.
A later reference to tat page will causes a page fault.
At that time the page will be brought back into memory, perhaps replacing some
other page in the process.
We must solve two major
problems to implement demand paging: we must developed a frame allocation
algorithm and a page replacement algorithm.
If we have multiple
process in memory, we must decide how many frames to allocate to each process.
Further, when page
replacement is required we must select the frames that are to be replaced.
Designing appropriate
algorithm to solve these problems is an important task, because disk I/O is so
expensive. Even slight improvements in demand paging methods yield large gains
in system performance.