Chapter 3 Exercise Answers 1 - 6

Chapter 3
1. Compare and contrast internal fragmentation and external fragmentation. Explain the
circumstances where one might be preferred over the other.
Both internal and external fragmentations are a form of wasted space. Internal
fragmentation refers to the wasted space inside of an allocated area of memory. External
fragmentation refers to the wasted space outside of the allocated area of memory.
2. Describe how the function of the Page Map Table differs in paged vs. segmented/demand
paging memory allocation.
The PMT in paged memory allocation correlates each of the jobs pages with its page
frame number. The PMT in segmented/demand memory allocation is similar to paged memory
allocation, but also includes the status (whether in memory or not), modified (whether its been
modified or not), and reference (whether its been recently referenced).
3.
Page requested:
a
b
a
c
d
a
e
f
g
c
b
g
Page frame 1
a
a
a
a
d
d
d
f
f
f
b
b
Page frame 2
b
b
b
b
a
a
a
g
g
g
g
Page frame 3
c
c
c
e
e
e
c
c
c
Interrupt:
*
*
*
*
*
*
*
*
*
*
Describe how the operating system detects thrashing. Once thrashing is detected, explain
what the operating system can do to stop it.
It detects thrashing when the operation becomes inefficient, by an excessive amount of
page swapping (caused when a page is removed from memory but is called back shortly
thereafter) between main memory and secondary storage. To stop it, the page replacement policy
comes into play. Two of the most well known are the first-in-first-out policy (the best page to
remove is the one that has been in memory the longest), and the least recently used policy
(chooses the page least recently accessed to be swapped out).
4. Given that main memory is composed of three page frames for public use and that a
seven-page program (with pages a, b, c, d, e, f, g) requests pages in the following order:
a, b, a, c, d, a, e, f, g, c, b, g
a. Using the FIFO page removal algorithm, do a page trace analysis indicating page
faults with asterisks (*). Then compute the failure and success ratios.
10 page interrupts out of 12 page requests. The failure rate is 83%. The success rate is 17%.
b. 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.
Page requested:
a
b
d
a
f
b
e
c
g
f
b
g
Page frame 1
a
a
a
a
f
f
f
f
g
g
g
g
Page frame 2
b
b
b
b
b
e
e
e
f
f
f
Page frame 3
d
d
d
d
d
c
c
c
b
b
Interrupt:
*
*
*
*
*
*
*
*
*
Page requested:
a
b
d
a
f
b
e
c
g
f
b
g
Page frame 1
a
a
a
a
a
a
e
e
e
f
f
f
Page frame 2
b
b
b
f
f
f
c
c
c
b
b
Page frame 3
d
d
d
b
b
b
g
g
g
g
Interrupt:
*
*
*
*
*
*
*
*
*
*
9 page interrupts out of 12 page requests. The failure rate is 75%. The success rate is
25%.
c. Did the result correspond with your intuition? Explain.

Page requested:
a
b
a
c
d
a
e
f
g
c
b
g
I
Page frame 1
a
a
a
a
a
a
e
e
e
e
e
e
Page frame 2
b
b
b
b
b
b
f
f
f
b
b
Page frame 3
c
c
c
c
c
g
g
g
g
Page frame 4
d
d
d
d
d
c
c
c
Interrupt:
*
*
*
*
*
*
*
*
*
thought it was going to be roughly the same because there are many different page requests
towards the end. The success rate did increase, but it is still too low to be good.
5. Given that main memory is composed of three page frames for public use and that a
program requests pages in the following order:
a, d, b, a, f, b, e, c, g, f, b, g
a. Using the FIFO page removal algorithm, perform a page trace analysis indicating
page faults with asterisks (*). Then compute the failure and success ratios.
9 page interrupts out of 12 page requests. The failure rate is 75%. The success rate is
25%.
b. Using the LRU page removal algorithm, perform a page trace analysis and
compute the failure and success ratios.
10 page interrupts out of 12 page requests. The failure rate is 83%. The success rate is 17%.
c. Which is better? Why do you think it is better? Can you make general statements
from this example? Why or why not?
In this case, the FIFO page removal algorithm came out to be better because it had
one less page interrupt. But, you cannot make any general statements from this example
because both had high failure rates.
6. Let us define most-recently-used (MRU) as a page removal algorithm that removes
from memory the most recently used page. Perform a page trace analysis using three page
frames and the page requests from the previous exercise. Compute the failure and success
ratios and explain why you think MRU is, or is not, a viable memory allocation system.
8 page interrupts out of 12 page requests. The failure rate is 67%. The success rate is 33%. In this
case, MRU worked out better than the other two algorithms, but I dont think its a viable
memory allocation system because programs that arent being used remain in the memory for a
long time. In this case, d remained untouched throughout the whole run.
7. By examining the reference bits for the six pages shown in Figure 3.11, identify which of
the
Page requested:
a
b
d
a
f
b
e
c
g
f
b
g
six
Page frame 1
a
a
a
a
f
f
f
f
f
f
b
b
Page frame 2
b
b
b
b
b
e
c
g
g
g
g
Page frame 3
d
d
d
d
d
d
d
d
d
d
Interrupt:
*
*
*
*
*
*
*
*
pages was referenced most often as of the last time snapshot [shown in (e)]. Which page was
referenced least often? Explain your answer.

Chapter 3 Exercise Answers 1 - 6

Uploaded by

Copyright:

Available Formats

Chapter 3 Exercise Answers 1 - 6

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Chapter 3 Exercise Answers 1 - 6

Uploaded by

Copyright:

Available Formats

What are the differences between internal and external fragmentation?

How does an operating system detect thrashing?

Chapter 3

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

You might also like