1994 Problem Set
Problem 1 (18 Points)
The MIPS R4000 microprocessor is a 64-bit RISC CPU with an
unusual memory management unit (MMU). The MMU is implemented
with a 64 entry fully-associative software reloaded TLB(*) that
supports multiple page sizes. Each TLB entry contains a mask
that defines the bits of the virtual page number used for
comparison during a TLB lookup. By the appropriate setting of
the mask bits when an entry is added to the TLB, a page size
between 4 kilobytes and 16 megabytes can be selected. Having the
mask in each TLB entry means that the hardware can support
multiple different page sizes simultaneously. The only
restriction on mappings is that no virtual address may map to
mor than one TLB entry.
a) Describe the advantages of having multiple page
sizes in a system.
b) Assuming that you want to exploit these advantages,
describe the implementation challenges and potential
disadvantages of using this feature.
c) If you were given the job of implementing a virtual
memory system for a high-end compute server being designed with
the R4000, describe how (if at all) you would use tihs
variable-sized page support. Be sure to justify your answer.
(*) A software reloaded TLB is a virtual to
physical mapping table in which misses in the table trap to the
system software which is responsible for loading the needed
translation into the table.
Problem 2 (?? Points)
During the late 1970's and early 1980's, most computing in
university computer science departments was done on an
overloaded timeshared minicomputers such as the DEC VAX
11/780. During the late 1980's, many users abandoned these
timeshared systems in favor of personal workstations that
provided more CPU power than the VAX. Now, going into hte late
1990's, it appears that large multiprocessor compute servers can
provide greater and more cost-efficient computing than the
personal workstation.
Assume that you have been given the job of designing an
operating system to run on these large time-shared
multiprocessors of the late 1990's. One of the main challenges
you face is to convince the old-timers that the return to
time-sharing does not mean the return to overloaded timeshared
systems. In particular, you determine that yuor system must be
responsive enough to satisfy the expectations of users who have
been using personal workstations for the last ten years.
Describe what resource allocation and scheduling
mechanisms and policies you would employ in your system. Focus
on the mechanisms and policies that differ from what was ued in
the 1970's timesharing systems such as Unix. Be sure to indicate
he problems that yuor new mechanism or policy is addressing.
Problem 3 (18 Points)
Recently OS and database researchers have argued that users
should be able to add code to their system to improve
performance or functionality. For example, OS researchers have
found that if a program were able to direct the virtual memory
system to page in or out VM pages, the program can run in less
memory. Similarly, database systems could allow user defined
data types and access methods.
The addition of code to the operating system or
database system exposes the system to errors or malicious
behaviour in the added code. For example, a user could download
code that corrupts or crashes the OS. Three potential solutions
to this problem have been proposed:
1) Run all user added code in its own virtual memory
address space. The operating system uses remote procedure call
(RPC) to invoke the user's functions and the added code uses RPC
to call the OS. Because it runs in its own address space, the
added code can not read or modify any OS data or code.
2) Modify the user's object code so that every memory
access instruction is proceeded by some code that checks the
memory address to insure that the user is permitted to access
it. This can be accomplished on a RISC processor by adding one
or two instructions for ever load or store instruction in an
object file.
3) The third option is to have the user write the
extension code in a type-safe programming language. The type
system of the language, enforced by the compiler, ensures that
no unpermitted memory accesses can be performed.
Compare the advantages and disadvantages of these three
approaches.
Problem 4 (?? Points)
A file system's disk storage management component has the job of
placing file descriptors and file data blocks on disk. File
descriptors are the data structures that contain information
about files such as size, modify date, data block locations, and
protection information. There is a longstanding debate on how
file descriptors and data blocks should be placed on disk. One
side of the debate argues that all file descriptors should be
placed in one separate portion of the disk while the other side
argues that file descriptors should be placed with the data
blocks of the file they describe. What are the advantages and
disadvantages of these approaches.