📄 homework #3 solution.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0059)http://www.cse.ucsd.edu/classes/fa04/cse120/hw/hw3-sol.html -->
<HTML><HEAD><TITLE>CSE 120 (Fall 2004) -- Homework #3 Solution</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2900.2627" name=GENERATOR></HEAD>
<BODY>
<H2>CSE 120 (Fall 2004) -- Homework #3 Solution</H2><FONT color=blue
size=+1><B>Out: 11/4</B></FONT><BR><FONT color=red size=+1><B>Due:
11/16</B></FONT>
<OL>
<P>
<LI><A
href="http://www.cse.ucsd.edu/classes/fa04/cse120/hw/vm-work-sol.html">Nachos
VM Worksheet Solution</A>
<P></P>
<LI>Chapter 9: 9.10, 9.14
<P>9.10 Consider a paging system with the page table stored in memory.
<P> a. If a memory reference takes 200 nanoseconds, how long does
a paged memory reference take?
<P><FONT color=#0000ff> One memory reference for page table,
another one for actual content: 2 * 200 = 400</FONT>
<P><BR> b. If we add TLBs, and 75 percent of all page-table
references are found in the TLBs, what is the effective memory reference time?
(Assume that finding a page-table entry in the TLBs takes zero time, if the
entry is there.)
<P><FONT color=#0000ff> (1 - 75%) * 200 + 200 = 250</FONT>
<P>9.14 Explain why it is easier to share a reentrant module using
segmentation than it is to do so when pure paging is used.
<H3><SPAN style="FONT-WEIGHT: 400"><FONT color=#0000ff size=3>1. A segment is
a logical entity in modular programming, and programs tend to share code at
segment granularities (e.g., libraries). There is less overhead to set up a
shared segment (one entry per segment) than to share multiple fixed-size pages
(one entry per page).</FONT></SPAN></H3>
<H3><SPAN style="FONT-WEIGHT: 400"><FONT color=#0000ff size=3>2. Pointers
within segments are relative to the segment base. It does not matter where in
the segment table a segment gets loaded, the pointers will remain valid. In
paging, all shared pages have to be loaded at the same virtual addresses in
all processes for pointers within the shared region to remain valid.
</FONT></SPAN></H3>
<P></P>
<LI>Chapter 10: 10.2, 10.9, 10.19
<P>10.2 Assume that you have a page-reference string for a process with
<I>m</I> frames (initially all empty). The page-reference string has length
<I>p</I>; <I>n</I> distinct page numbers occur in it. Answer these questions
for any page-replacement algorithms:
<P> a. What is a lower bound on the number of page faults?
<BR><FONT color=#0000ff> n -- distinct page numbers always
generate a page fault, even if two difference pages refer to the same physical
page frame.<BR></FONT> b. What is an upper bound on the number of
page faults? <BR><FONT color=#0000ff> p -- if we reference p
pages, we will generate at most p page faults..</FONT>
<P>10.9 Consider a demand-paging system with the following time-measured
utilizations:
<P> CPU utilization: 20% <BR> Paging disk: 97.7%
(demand, not storage)<BR> Other I/O devices: 5% <BR>
<P>For each of the following, say whether it will (or is likely to) improve
CPU utilization. Briefly explain your answers.
<P> a. Install a faster CPU<BR><FONT
color=#0000ff> No. Installing a faster CPU might make the
page fault handler run faster. However, processes will also access data more
frequently and the situation becomes worse.</FONT>
<P> b. Install a bigger paging disk <BR><FONT
color=#0000ff> No. We need more memory to relieve our
situation, not more capacity to store pages. <!-- (or Yes, if you claim bigger disk spins faster, which is somewhat true) --></FONT>
<P> c. Increase the degree of multiprogramming <BR><FONT
color=#0000ff> No. Adding more processes will just make the
system thrash more.</FONT>
<P> d. Decrease the degree of multiprogramming<BR><FONT
color=#0000ff> Yes. When thrashing happens, a quick solution
is to swap out some applications.</FONT>
<P> e. Install more main memory<BR><FONT
color=#0000ff> Yes. More memory will reduce page faults,
reduce disk utilization, and thereby improve CPU utilization. </FONT>
<P> f. Install a faster hard disk, or multiple controllers with
multiple hard disks <BR><FONT color=#0000ff> Yes, but not
too much. A faster disk makes page faults faster, but the disk is still
relatively very slow compared to the CPU and memory. </FONT>
<P> g. Add prepaging to the page-fetch algorithms<BR>
<FONT color=#0000ff> No. Although pre-paging might save some page faults,
other processes are penalized for this. When memory is a scarce resource,
pre-paging does not help because the pre-fetched pages will be re-claimed by
some other process after the next context switch. And the situation is worse
if pre-paging loads unnecessary pages (e.g., is not 100% accurate). </FONT>
<P> h. Increase the page size<BR><FONT
color=#0000ff> No. A larger page size will reduce the number
of page faults and relative overhead of performing I/Os. However, a larger
page size increases internal fragmentation, lowering effective memory
utilization. This situation aggravates thrashing.
<P>In general, when resources are scarce, improving a contention algorithm
will not help much. The primary recourse is to increase resources. Swapping
effectively increases memory resources by reducing the number of processes
competing for it. </FONT>
<P>10.19 We have an operating system for a machine that uses base and
limit registers, but we have modified the machine to provide a page table. Can
we set up the page tables to simulate base and limit registers? How can we do
so, or why can we not do so?
<P><FONT color=#0000ff>We can do that by storing base/limit in PTEs and
limiting the segment to be size of multiple pages. For example, suppose we
have a segment S of segment number X and offset Y contains P pages. We use X
to lookup the PTE of the first page and get the base. The PTE also tells us
where is the next page of S so we keep going until we reach the last PTE,
which tells us the limit of S.</FONT>
<P>
<P></P>
<LI>[Crowley] Suppose we have an average of one page fault every 20,000,000
instructions, a normal instruction takes 2 nanoseconds, and a page fault
causes the instruction to take an additional 10 milliseconds. What is the
average instruction time, taking page faults into account? Redo the
calculation assuming that a normal instruction takes 1 nanoseconds instead of
2 nanoseconds.
<P><FONT color=#0000ff>a) Time of 1 instruction = 2 ns <BR>
Time to handle 1 page fault = 10 msec = 10,000 ns<BR>
Frequency of page fault = 1 in 20,000,000 instructions. <BR>
Hence, average time wasted on page fault = 10,000ns/20,000,000 inst. = 0.5
ns/inst. <BR> Thus, average time of an instruction execution
= 2 ns + 0.5 ns = 2.5 ns </FONT></P>
<P><FONT color=#0000ff>b) Time of 1 instruction = 1 ns <BR>
Time to handle 1 page fault = 10 msec = 10,000 ns<BR>
Frequency of page fault = 1 in 20,000,000 instructions. <BR>
Hence, average time wasted on page fault = 10,000ns/20,000,000 inst. = 0.5
ns/inst. <BR> Thus, average time of an instruction execution
= 1 ns + 0.5 ns = 1.5 ns</FONT></P>
<P> </P>
<P></P>
<LI>[Crowley] Suppose we have a computer system with a 44-bit virtual address,
page size of 64K, and 4 bytes per page table entry.
<OL>
<LI>How many pages are in the virtual address space?<BR><FONT
color=#0000ff>2^44 / 64K = 2^28</FONT>
<LI>Suppose we use two-level paging and arrange for all page tables to fit
into a single page frame. How will the bits of the address be divided
up?<BR><FONT color=#0000ff>The first level page table has 64K/4 = 16K = 2^14
entries, so the length of first level paging is 14<BR>The second level page
table has 64K/4 = 16K = 2^14 entries, so the length of second level paging
is 14<BR>The offset field has 44 - 14 - 14 = 16 bits length</FONT>
<LI>Suppose we have a 4 GB program such that the entire program and all
necessary page tables (using two-level pages from above) are in memory.
(Note: It will be a <I>lot</I> of memory.) How much memory, in <B>page
frames</B>, is used by the program, including its page tables? </LI></OL>
<P><FONT color=#0000ff> Pages used
by the program are 4G/64K = 2^(32-16) = 2^16 page
frames<BR> Pages used by the second
level page table are <BR> (# pages
used by the program) / (# pages indexed per page table) * (# page frames used
per page table) = 2^16 / 2^14 * 1 =
4<BR> Pages used by the first level
page table are <BR> (#number of the
second level page table) / (# pages indexed per page table) * (# page
frames used per page table) = 4 / 2^16 *
1<BR> The total page frames used =
2^16 + 4 + 1</FONT></P>
<P> </P>
<P></P>
<LI>[Tanenbaum] If FIFO page replacement is used with four page frames and
eight pages, how many page faults will occur with the reference string
0172327103 if the four frames are initially empty? Now repeat this problem for
LRU. </LI></OL>
<P><FONT color=#0000ff> 6
page faults for FIFO and 7 for LRU, which include 4 cold start page faults in
each case.</FONT></P><PRE></PRE><PRE></PRE>
<HR>
</BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -