9.

1 - Under what circumstances do page faults

occur? Describe the actions taken by the operating
system when a page fault occurs.
A page fault occurs when an access to a page that
has not been brought into main memory takes place.
The operating system verifies the memory access,
aborting the program if it is invalid. If it is valid, a
free frame is located and I/O is requested to read
the needed page into the free frame. Upon
completion of I/O, the process table and page table
are updated and the instruction is restarted.

9.2 - Assume that you have a page-reference string

for a process with m frames (initially all empty). The
page-reference string has length p; n distinct page
numbers occur in it. Answer these questions for any
page-replacement algorithms: (a) What is a lower
bound on the number of page faults? (b) What is an
upper bound on the number of page faults?
(a) n
(b) p
9.3)
Consider the page table shown in Figure 9.30 for a
system with 12-bit virtual and physical addresses
and with 256-byte pages. The list of free page frames
is D, E, F (that is, D is at the head of the list, E is
second,
and F is last).

Page _____________Page Frame

0 _________________ ---
1 _________________ 2
2 _________________ C
3 _________________ A
4 _________________ ---
5 _________________ 4
6 _________________ 3
7 _________________ ---
8 _________________ B
9 _________________ 0

Convert the following virtual addresses to their

equivalent physical addresses in hexadecimal. All
numbers are given in hexadecimal. (A dash for a
page frame indicates that the page is not in
memory.)

• 9EF
• 111
• 700
• 0FF
• 9E F - 0E F
• 111 - 211
• 700 - D00
• 0F F - EFF
9.5)
Discuss the hardware support required to support
demand paging.
For every memory-access operation, the page table
needs to be consulted
to check whether the corresponding page is resident
or not and whether
the program has read or write privileges for
accessing the page. These checks have to be
performed in hardware. A TLB could serve as a cache
and improve the performance of the lookup
operation.
9.6An operating system supports a paged virtual
memory, using a centralprocessor with a cycle time
of 1 microsecond. It costs an additional
1microsecond to access a page other than the
current one. Pages have 1000words, and the paging
device is a drum that rotates at 3000 revolutionsper
minute and transfers 1 million words per second.
The followingstatistical measurements were
obtained from the system:•1 percent of all
instructions executed accessed a page other than
thecurrent page.•Of the instructions that accessed
another page, 80 percent accesseda page already in
memory.
When a new page was required, the replaced page
was modifed 50percent oF the time.Calculate the
eFFective instruction time on this system, assuming
that thesystem is running one process only and that
the processor is idle duringdrum
transFers.Answer:eFFective access
time=0.99×(1msec + 0.008×(2msec)+
0.002×(10,000msec + 1,000msec)+
0.001×(10,000msec + 1,000msec)=(0.99 + 0.016 +
22.0 + 11.0)msec=34.0msec
Question 4:
Consider the following page reference string:

1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6
How many page faults would occur for
replaement by LRU, FIFO, optimal, for
one, two, three, four, five, six and seven
frames? All frames are
initially empty and first unique page reference
causes a page fault.

Answer:
# frames 1 2 3 4 5 6 7
LRU 20 18 15 10 8 7 7
FIFO 20 18 16 14 10 10 7
Optimal 20 15 11 8 7 7 7
9.12)
Consider a demand-paged computer system where
the degree of multiprogramming is currently fixed at
four. The system was recently measured to
determine utilization of the CPU and the paging disk.
Three
alternative results are shown below. 

For each case, what is happening?

Can the degree of multiprogramming be increased to
increase the CPU
utilization?
Is the paging helping?

a. CPU utilization 13 percent; disk utilization 97

percent
b. CPU utilization 87 percent; disk utilization 3
percent
c. CPU utilization 13 percent; disk utilization 3
percent

a. Thrashing is occurring.
b. CPU utilization is sufficiently high to leave things
alone, and increase degree of multiprogramming.
c. Increase the degree of multiprogramming.
9.15)
A simplified view of thread states is Ready, Running,
and Blocked, where a thread is either ready and
waiting to be scheduled, is running on the processor,
or is blocked (for example, waiting for I/O). This is
illustrated
in Figure 9.31. Assuming a thread is in the Running
state, answer the following questions, and explain
your answer:

a. Will the thread change state if it incurs a page

fault? If so, to what state will it change?

b. Will the thread change state if it generates a TLB

miss that is resolved in the page table? If so, to what
state will it change?

c. Will the thread change state if an address

reference is resolved in the page table? If so, to what
state will it change?
a. Yes, a tread changes from the Running state to the
Blocked state when a page fault occurs.
When a page fault occurs, the process starts to wait
for I/O operation to finish. The OS does
several things while the process is waiting. It checks
whether the page is really invalid or just on
disk, finds a free memory frame, schedules a disk
access to load the page into t the frame,
updates the page table with the new logical-physical
mapping, updates the valid bit of that entry,
and eventually restarts the process by change its
state from Blocked to Ready. 

b. Not necessarily. If a page table entry is not found

in the TLB (TLB miss), the page number is
used to index and process the page table. If the page
is already in main memory, then TLB is
updated to include the new page entry, while the
process execution continues since there is no
I/O operation needed. If the page is not in the main
memory, a page fault is generated. In this 
case, the process needs to change to the Blocked
state and wait for I/O to access the disk. This is
the same procedure as in the first question. 

c. No, because no I/O operation is needed is the

address reference is resolved in the page table,
which indicates the page needed is loaded in the
main memory already.

In a demand-paged system, the degree of

multiprogramming is fixed at 4.
Measurements were made to determine the
utilization of cpu and the paging
disk. The result is one of the following. For
each of case a, b, c,
state in one line what is happening?

a. cpu utilization 13%, disk 97%

b. cpu utilization 92%, disk 11%
c. cpu utilization 21%, disk 3%

Answer: a. Thrashing b. okay c. can increase

multiprogramming

+2 for each correct solution.

 +1 for each part if you sort of get it, but didn't
quite explain it.

Question 7:
It has been observed that the number of
instructions executed between
pagefaults is directly proportional to the number
of frames allocated to
the process. If twice the number of frames are
allocated, the mean
interval between page faults is also doubled.
An instruction takes
normally 1 microsec, but with a pagefault it
takes 2001 microsec. The
process takes 60 secs to run during which it gets
15000 page faults. How
long would it take for the process if twice the
memory were made available
to it?

Answer: For 15000 page faults, the overhead at

2 msec per fault is 30 sec.
So, out of the 60 sec, 30 went in paging overhead
and 30 for processrunning.
 If the process had twice the memory, we have
half, i.e., 7500 page faults
and 15 sec paging overhead. The total time for
the process is 30+15=45sec.
+3 if you have the correct equation to find the
total number of
instructions. ie 60s = i*1ms + 15000*2ms
9.27)
Consider a demand-paging system with the following
time-measured utilizations:

CPU utilization 20%

Paging disk 97.7%
Other I/O devices 5%

For each of the following, indicate whether it will (or

is likely to) improve CPU utilization. Explain your
answers.

a. Install a faster CPU.

b. Install a bigger paging disk.
c. Increase the degree of multiprogramming.
d. Decrease the degree of multiprogramming.
e. Install more main memory.
f. Install a faster hard disk or multiple controllers
with multiple hard disks.
g. Add prepaging to the page-fetch algorithms.
h. Increase the page size.
a.
No. The given system's CPU is underutilized, and it
spends a lot of time accessing disk. This
tells us that the system is thrashing. CPU is not the
where the problem is, so a faster CPU will
not help. 

b.Not necessarily, thrashing is more likely caused by

the main memory capacity and disk accessing
speed. Page disk size might not be where the
problem is. 

c.
No. Increasing the degree of multiprogramming
means even fewer frame per process. It worsen
the thrashing. All processes might not be able to get
their pages in a reasonable speed, and
nobody gets to run smoothly. 

d.
Yes. Decreasing the degree of multiprogramming
means more frames per process. It reduces the
thrashing. The remaining processes might be able to
get their pages in a reasonably fast speed,
and get to run smoothly. 

e.
Yes. Installing more main memory means more
frames per process. It reduces the thrashing.
The processes might be able to get their pages in a
reasonably fast speed, and get to run
smoothly.

f.
No. The problem is not the size of hard drive.
Trashing is caused by the main memory capacity
and the accessing speed. 

g.

h.
No likely. Increasing page sizes doesn't change the
fact that the physical memory for each
process's pages is not big enough. Plus, increasing
pages sizes would cause a longer accessing
time to the disk. The extra bits loaded from the disk
increases, which is a waste.
What causes thrashing? How does the system
detect thrashing?
Once it detects thrashing, what can the system
do to eliminate
this problem?

Thrashing is caused by underallocation of the

minimum number of pages required
by a process, forcing it to continuously page fault.
The system can detect
thrashing by evaluating the level of CPU utilization as
compared to the
level of multiprogramming.
It can be eliminated by reducing the level of
multiprogramming.

9.33 Is it possible for a process to have two working

sets, one representing data andanother representing
code? Explain.Yes, in fact many processors provide
two TLBs for this very reason. As an example,
thecode being accessed by a process may retain the
same working set for a long period oftime. However,
the data accesses may change, thus reflecting a
change in the working setfor data accesses
Consider the parameter Δ used to define the
working-set window in the working-set model. When
Δ is set to a small value, what is the effect on the
page-fault frequency and the number of active (non
suspended) processes currently executing in the
system? What is the effect when Δ is set to a very
high value? When Δ is set to a small value, then the
set of resident pages for a process might beunder
estimated, allowing a process to be scheduled even
though all of its required pages are not resident. This
could result in a large number of page faults. When
Δ is set to a large value, then a process’s resident set
is overestimated and this might prevent many
processes from being scheduled even though their
required pages are resident. However, once a
process is scheduled, it is unlikely to generate page
faults since its resident set has been overestimated.

The system obviously is spending most of its time

paging, indicating
over-allocation of memory. If the level of
multiprogramming is reduced
resident processes would page fault less frequently
and the CPU utilization
would improve. Another way to improve
performance would be to get more
physical memory or a faster paging disk.

a. Get a faster CPU - No.

b. Get a bigger paging disk - No.
c. Increase the degree of multiprogramming -
No.
d. Decrease the degree of multiprogramming -
Yes.
e. Install more main memory - Likely to
improve CPU utilization as
more pages can remain resident and not
require paging to or from the
disks.
f. Install a faster hard disk, or multiple
controllers with multiple
hard disks - Also an improvement, for as the
disk bottleneck is
removed by faster response and more
throughput to the disks, the
CPU will get more data more quickly.
 g. Add prepaging to the page fetch algorithms -
Again, the CPU will
get more data faster, so it will be more in use.
This is only the
case if the paging action is amenable
to prefetching (i.e., some of the access is
sequential).
h. Increase the page size - Increasing the page
size will result in
fewer page faults if data is being accessed
sequentially. If data
access is more or less random, more paging
action could ensue because
fewer pages can be kept in memory and more
data is transferred per
page fault. So this change is as likely to
decrease utilization
as it is to increase it.