Homework 3, released
on Oct 17, 2000. CS414
FA2000 Due in class Oct 26, 2000
Please hand in your
answers as follows: not handwritten,
11-pt typefont Times or 10-pt typefont Courier, minimum of .5” margins. Each problem must be answered on a separate sheet of paper.
Your name and id should be written on each sheet
of paper you submit. Please write the
question number in the top of the sheet in bold. Every item is worth 5 points, unless otherwise marked.
Late homeworks accrue 10% penalty for the first 24 hours, 20% if handed
in on Sat between 4-5pm, 30% if handed in Monday before 10am, 40% on Tuesday in
class. Homeworks will not be accepted
after that.
Collaboration is prohibited and will be treated as a violation of the
University's academic integrity code.
1)
Consider a machine with a physical memory size of 2
megabytes (2^21 bytes). A single base
register is available to support virtual memory translation. Draw translation diagrams that describe this
virtual memory scheme for each case below.
Be sure to indicate the required widths (in bits) of the register and of
physical and virtual addresses. Also,
indicate the lengths and widths of any tables you use in your translation
process.
a)
A virtual memory scheme allows up to 8
segments per process. Each segment is
limited to half a megabyte (2^19 bytes) in size. Segments are paged; the page
size is 4096 (2^12) bytes.
b)
A pure-paged 1-level VM system
c)
A 2-level paging system. Explain your choices in terms of sizes of
fields in the tables.
2)
a)
The following list describes the free space available in a
main memory. In each pair (X, Y), X
gives the starting address of a free block, and Y gives the length of the
block.
(10000,4000)
(4000,1000)
(1000,2000)
(15000,1000)
The total size of the memory is 20000 bytes.
Assume that a complete free space compaction occurs. Show what the free space
list looks like after the compaction.
(Show your list in the X, Y format.) Note: there are many possible
answers.
b)
Describe two differences between segments and pages.
c)
Consider again the free space list given in part (a) of this
question (before the compaction). A series of requests are made for 1600, 2000,
1000, and 2000 bytes of storage. Of the First Fit, Best Fit, and Worst Fit
heuristics, which will not allow all of these requests to be satisfied?
d)
A virtual memory scheme uses pure paging, with a page size
of 1000 bytes. The first 5 entries in a process' page table contain the
following page frame numbers 4, 6, 2, 3, 7. (Assume that both page numbering
and frame numbering start at 0.) To which physical address will this process'
virtual address 2200 translate? To which virtual address does the physical
address 3500 correspond?
e)
[BONUS 5pts] Briefly (a sentence or two for each) define load
control and thrashing. You may have to
research these terms, if you have not seen them in class.
3)
A byte-addressable (each data fetched is 1 byte long) computer system is
designed to support segmented paging. It has the following specifications:
1.
The address space allows a maximum of 16
segments, a maximum of 2^19 bytes in each segment.
2.
The segments are paged, with a page size
of 2^12 bytes.
3.
Physical memory has 2^22 addressable
bytes.
4.
The current segment table is assumed to be
resident in memory.
5.
There is a base register for the segment
table (STBR) as well as a limit register (STLR). We may assume these to be
pre-loaded by the system.
6.
There is a base register for the current
segment's page table (PTBR) as well as a limit register (PTLR). These must be
loaded by the memory management hardware.
7.
The page table for each segment is stored
in the 0th page of that segment.
a)
Sketch a segment table entry, displaying
its field(s) and width(s) in bits.
b)
Sketch a page table entry, displaying its
field(s), and width(s) in bits.
c)
The system supports a TLB. Sketch a TLB
entry, displaying its field(s), and width(s) in bits.
4)
Consider the following matrix multiplication program, which runs in a purely
paged system (that is, no segmentation). The page size is 1024 words and each
integer occupies one word. A page fault
occurs when a request to access a word in memory does not find that specific
word in physical memory. Assume that,
when a page fault occurs, the oldest page is overwritten by the incoming page
(the one that contains the requested word).
int A[4096][4096], B[4096][4096], C[4096][4096], sum, i,
j, k;
for (i=0; i<
4096; i++)
for (j=0; j<
4096; j++) {
sum = 0;
for (k = 0; k
< 4096; k++)
sum = sum +
A[i, k]*B[k,j];
C[i,j] = sum;
}
Assume that A, B, and C are all stored in
row-major order.
a)
Assume that 20 page frames are available.
During any one iteration of the j
loop, are we likely to have any more than 30 page faults caused by accessing A,
B or C? Please be specific in your answer.
b)
Is there a better way to store any of the
matrices so that page faults are reduced?
c)
Is there a better way to overwrite pages
in memory so that page faults are reduced?
5)
Explain the difference between external and internal fragmentation. In which memory management policies is each
likely to appear?