Problem Set 2
UNIVERSITY OF CALIFORNIA
College of Engineering
Department of Electrical Engineering
and Computer Sciences
Computer Science Division
CS 162 Prof. Alan J. Smith
Problem Set 2
Please place the work for this assignment online, and submit in
the usual manner.
1. Suppose a system has a virtual address containing 28 bits.
Suppose that the page size is 1024 bytes, that physical addresses
contain 24 bits, and that the system uses a segmented-and-paged
scheme with 256 segments and a segment size of one megabyte.
(a) Describe the address translation mechanism, using a picture
to show the relevant tables and operations. Don't worry
about a TLB. Be sure to show the exact size of each table
(how many entries, how many bits wide).
(b) Suppose that a byte of physical memory is to be shared by
two processes. Describe how the tables could be arranged to
permit this.
(c) Suppose that a particular segment in this system contains
4800 bytes. How much memory will the segment cause to be
wasted in internal and external fragmentation? Consider
only the memory allocated to the segment itself; do not
worry about memory used in the mapping tables.
(d) Now suppose that the owner of the 4800-byte segment wishes
to expand it by 200 bytes. What must the operating system
do in order to increase its size? Compare this to a system
based on pure segmentation.
(e) Suppose that the segment is expanded again, from 5000 bytes
to 5500 bytes. What must the operating system do to accom-
plish this?
2. Consider a program that generates the following set of page
references:
A A A A B B C A C B B D D A E B C E A E D E
Assuming that the program is given 3 page frames, how many page
faults are generated using the following replacement algorithms:
(a) FIFO
(b) MIN
(c) LRU
(d) Working Set. Tau = 6 (if six references have been made
without accessing a page then it is no longer in the working
set). For this case, the program may need to use more than
3 page frames. Indicate how large the working set is at
each point in time. Assume that pages are thrown out of
memory as soon as they leave the working set.
3. Consider the clock algorithm for LRU page replacement (also
called "FINUFO" (first in, not used, first out), also called
"first chance" replacement). Suppose that there are P pages of
physical memory in the system and that over a particular interval
of time F page faults have occurred. What are the minimum and
maximum number of times that the clock hand could possibly have
been advanced during the time interval? Give your answer in
terms of P and F.
4. Consider a demand paging system. Pages that are not in main
memory are stored on the "paging device", which may be a portion
of a hard disk, an electronic disk, or something else. The size
of the paging device is its capacity. Measured utilizations (in
terms of time, not space) are:
CPU utilization 20%
Paging device 99.7%
Other I/O devices 5%
Which of the following, if any, will probably improve the CPU
utilization? Why or why not?
(a) Get a faster CPU.
(b) Get a bigger paging device.
(c) Increase the degree of multiprogramming.
(d) Decrease the degree of multiprogramming.
(e) Get faster other I/O devices.
5. This question concerns translation lookaside buffers (TLBs).
(a) In almost all computers with translation lookaside buffers,
the TLB must be flushed (all the entries must be
invalidated) during each context switch. Why?
(b) Are large TLBs better than small ones from a performance
standpoint?
(c) A new computer has 32-bit virtual addresses, but uses 30-bit
values as the input to the TLB. The high-order 8 bits are a
process identifier that is unique for each process, and the
low-order 22 bits are the virtual page being referenced (the
high-order 22 bits of the virtual address; pages are 1024
bytes long). What is the purpose of inputting the process
identifier to the TLB?
(d) Does this use of process IDs simplify or complicate the
translation lookaside buffer?
6. In this problem, all numbers are given in decimal. Suppose
three object files, A, B, and C, are to be linked together. Each
of the object files contains two segments, code and data, and the
output of the linker will also contain two segments. A contains
1400 bytes of code and 600 bytes of data. B contains 420 bytes
of code and 20 bytes of data. C contains 2600 bytes of code and
112 bytes of data. The file A defines one external symbol, X,
which is at location 760 in A. One external symbol is defined in
B: its name is Y and its location is 430. C defines 2 external
symbols: Z is at 2216 and W is at 2704. Suppose the linker pro-
cesses the files in the order A, B, C, so that A's segments end
up before B’s which end up before C's.
(a) Suppose that file A has an address at location 134 that is
supposed eventually to refer to symbol X. What will be the
contents of location 134 in A? What will its contents be
after linking, and where will the contents be in the output
file?
(b) Suppose that file A has an address at location 136 that is
supposed eventually to refer to symbol Y. What will be the
contents of location 136 in A? What will its contents be
after linking, and where will the contents be in the output
file?
(c) Suppose that file B has an address at location 430 that is
supposed eventually to refer to symbol Z. What will be the
contents of location 430 in B? What will its contents be
after linking, and where will the contents be in the output
file?