This exam is worth 1/5
of the final grade (20 points; allocate 2 minutes per point).
-
Background:
The gate crossing mechanisms of Multics allowed a function (perhaps running
at a user level) to call a more privileged function (perhaps running at a
system level) that runs in the same address space as the user function.
The calling function may pass any bit pattern as a pointer, to the called
function, even if the bit pattern, when interpreted as a pointer, refers
to memory that the caller should not be allowed to manipulate. The Multics
ring mechanism, as supported by Multics hardware, does nothing to help
prevent misuse of such pointers.
The Problem:
What test should be done by the code for a system call such as
read(f,buffer,len) to verify that it is reading into a buffer the user
is allowed to manipulate, and not, for example, reading from the keyboard
into the memory currently occupied by a system data structure such as the
page table.
(2 points)
-
Background:
On the Hawk machine, user code may call a system function by forcing a trap,
and the system function may easily receive parameters from the user and return
results to the user through the registers. If one of those parameters is
pointer passed by the user to the system, for example the buffer address
passed to a a function such as read, the user must pass a virtual address.
The Problem:
What must the kernel function do to access the memory pointed to by the user's
pointer?
(2 points)
-
Background:
In hierarchically constructed system, most function calls are "down calls" in
the sense that high level functions typically call low level functions. Thus,
user programs usually call system functions. Ocasionally, there are function
calls that can be classified as "up calls" or "callbacks" where low level
functions call high level functions. For example, many window managers
(a lower level in the design hierarchy) include callbacks so that a user
program (a higher level in the hierarchy) may request that some function be
called whenever a particular event is detected by the window manager (for
example, whenever the user clicks the mouse on some "button"). The UNIX
signal mechanism is basically an upcall mechanism, where the user may
ask the operating system to call some user function whenever the system
detects some event.
The Problem:
How could kernel code on the Hawk machine call a user function (this is
modestly easy), and how would the kernel regain control when the
user function attempted to return (this is a little harder!).
(2 points)
-
Background:
Consider a system with an I/O bus such as the SCSI bus,
where some disk drives are attached to this bus, and the bus is controlled
by a DMA controller. Assume that the bus controller requests an interrupt
whenever any device attached to the bus is ready to begin a new operation,
and that the bus controller contains a register to let the CPU find what
device or devices are currently ready. Furthermore, assume that the disk
drives have a seek operation that completes as soon as the disk heads have
reached the correct cylinder, without attempting to read or write any data.
Obviously, something like the elevator algorithm would be appropriate for
scheduling transfers on each disk drive.
The Problem:
Illustrate the potential for parallelism in this sytem with an example.
(2 points)
-
Background:
Some SCSI disks contain on-board controllers that have considerable buffer
capacity; this is used to cache recently read or written sectors. Such a
disk signals operation-complete to the SCSI controller as soon as the written
data has been copied to the buffer, possibly long before the data is actually
written to disk. On read, if a copy of the required sector is in the buffer,
this is returned immediately, without any rotational or head positioning
latency.
The Problem:
Discuss the potential for implementing an on-board disk scheduler for such
a disk. Would on-board scheduling eliminate the need for disk scheduling in
the operating-system? Would it work better for read or for write? Would there
be some tradeoff point, in terms of the amount of pending disk traffic, where
an operating-system level scheduler would become useful.
(2 points)
-
Background:
Consider a virtual memory machine such as the Hawk, where the software
maintains a paged, segmented model of the virtual address space. Each entry
in the frame table, if used to hold a page, contains both the page-number
of the page held in that frame and the address of the segment to which
that page belongs.
The segment table for a user is indexed by the virtual segment number in
that user's address space, and it contains, for each segment, status
information and, if the page table for the segment is in main memory, the
frame number of the page frame used to store that page table.
The page table for each segment occupies one page frame, and if all the
pages in that segment have been rolled out to disk, the page table itself
may be rolled out.
The Problem:
Segments may be shared between multiple address spaces. What information
must be stored in the frame table entry for a frame that holds
the page table for a segment? Specifically consider the information the
system needs in order to fix things up when the page table for the
segment is rolled out to disk.
(2 points)
-
Background:
In the LISP programming language, the classic representation for linked lists
represents each list element as a pair of pointers, one to the next list
element (called the CDR) and one to the item stored in that list element
(called the CAR). If x is the address of a list element, the CDR(x) and CAR(x)
functions returned the pointers in the CDR and CAR fields. Later, when
LISP was implemented on virtual memory systems, it was found that the
page-fault rate was significantly reduced by changing the allocation scheme
to what became known as CDR-coding. In this scheme, CAR(x) returned the
pointer held in memory location x, and CDR(x) returned x+1.
The Problem:
Explain why CDR-coding reduced the page fault rate.
(2 points)
-
Background:
Consider the problem of allocating space for kernel data structures on a
virtual memory machine such as the Hawk. Assume, that the frame
table contains a lock bit used to prevent the page replacement algorithm from
tampering with pages that contain code or kernel data structures. There are
two basic ways to use such a system: In one, a contiguous range of page
frames are locked and used to hold the kernel's heap. In the other, the
kernel claims and locks random free page frames, when needed to hold kernel
data structures and unlocking those frames when they no-longer contain
useful data.
The Problem:
Contrast these alternatives, discussing conditions under which each might
be preferable.
(2 points)
-
Background:
Here is the pseudocode from the notes for Lecture 3 indicating how
to implement the signal operation on a semaphore:
Signal( sem ) or V( sem ):
begin
Disable Interrupts
if empty( sem.queue )
sem.count := sem.count + 1
else
temp := dequeue( sem.queue );
enqueue( temp, ready queue )
endif
Enable Interrupts
return
end
Recall that interrupt service routines can never call the wait() operation
on a semaphore, but that they can call some variant on the signal()
operation.
The Problem:
What is it about the above implementation of the signal() operation that
may preclude it from being called within an interrupt service routine?
semaphores that prevents it from being called by an interrupt service routine.
(2 points)
-
Background:
Our thread manager uses a thread_launch() operation to start a new thread.
The Problem:
Comment on some of the major problems you would have to solve to implement
a UNIX-style fork() operation as part of our thread manager.
(2 points)