Average = 9.7
Median = 10.0
X
X X X X X
___________X_X_X___X_X_X_X_X___X_X___________
5 . 6 . 7 . 8 . 9 . 10. 11. 12. 13. 14. 15
Part A: (2 points) Given a linear disk address (sector number on disk), a search would need to be performed to find out what group of cylinders the address falls in. All cylinders in each group would have the same number of sectors per track, so what we need is an array with one entry per group giving the number of sectors per track in that group, the starting cylinder number for that group, and the starting (linearized) sector number for that group.
If there are many groups, a binary search would be appropriate, followed by a normal conversion computation within the group. (Subtract the starting sector number, divide by that group's sectors per track to get track-in-group and sector in track, then divide the former by surfaces to get track-in-cylinder and cylinder-in-group. Add the base cylinder for that group to the latter, and the conversion is complete.
Part B: (2 points) The nonlinear data rate has the consequences that more I/O would be directed to the outer cylinders of the disks than to the inner cylinders. This skewed distribution of requests does not change the appropriateness of algorithms such as the elevator algorithm, and in fact, given that I/O on outer cylinders is faster than I/O on inner cylinders, the actual distribution of time spent doing I/O per cylinder will most likely be uniform despite the skew in I/O requests towards the outer rim.
Part A: (2 points) How can instructional computing be managed on the CAP system?
Users C-lists Files
Instructor I --------------
Assistant A --------- |
Student S ---- | |
| | |-RW----- Exams being prepared
| | |-RW----- Private file of I
| |-RW-| ------- Private file of A
| |-RW-|-RW----- Gradebook
|-RW-|-R--|-R------ Not so private File of S
|-RW-|-R--|-R------ Not so private File of S
Part B: (2 points) User A can give user B access to some specific file F without giving F to C if we assume the following initial directory structure: we assume the follo,
Users C-lists Files
A ----------------
B ----------- |------------------F
C ------ | |----
| |---------|
| | |
To allow A to transfer files to B in a secure way, A and B must share access
to a privat communications channel. In this case, this channel is a shared
capability list accessable from A and B but not from C.
To transfer the file F, A copies the capability for F into the shared list, and then B copies the capability for F into B's private list. Typically, all members of a project, class or other group would share access to a capability list so that members of that group could securely transfer files among themselves without giving outsiders access.
Part C: (2 points) If user A on the CAP system has given rights to file F to user B and user A wants to make changes to F that should not be seen by B, user A must make those changes to a copy of F. Typically, A would give the name of F to this copy and either delete or rename F in A's capability list. User A cannot deny user B access to the original file F once B takes a copy of the capability for F.
Part A: (2 points) The following code will deadlock quite trivially:
pipe(fildes);
if (pid = fork()) { /* parent */
read(fildes[0], ... );
} else { /* child */
read(fildes[0], ... );
}
The following deadlock is more interesting:
pipe(fildes);
if (pid = fork()) { /* parent */
char bufa[513];
write(fildes[1], bufa, 513);
read(fildes[1], bufa, 2);
} else { /* child */
char bufb[513];
write(fildes[1], bufb, 513);
read(fildes[1], bufb, 2);
}
Here, the blocking occurs because each process tries to overfill the pipe
before consuming any data from it. A larger buffer inside the pipe would
break this deadlock.
Part B: (2 points) The or-model is applicable to deadlock detection involving Unix pipes. If a process is blocked reading from a pipe, any of the processes with that pipe open for output may unblock the reader. If a process is blocked trying to write a pipe, any process with that pipe open for input may unblock the writer.
The set of processes able to read or write a pipe is clearly well defined, and it is documented in the open-file lists of each process. Maintaining back pointers from each open file to the processes that have that file open is quite feasible, and these back pointers provide exactly the data required for deadlock detection algorithms.
So, the data is available and it is an or-model. Thus, when a process blocks reading or writing a pipe, an examination of the pipe-process graph looking for a knot will detect deadlocks. Note, in this examination, that the read and write ports of a pipe must be viewed as separate resources! A process blocked on a read port must see if any of the processes able to write are running, and a process blocked on a write port must see if any of the processes able to read are running.
Finally, note that the only question is, is some process with an incoming edge to the knot still running? There is no deadlock if a process in the knot is still running, even if that process never unblocks the processes that are waiting for it! There may be an error in such a case, but that error is not a deadlock!
Part C: (2 points) If a deadlock is detected while reading or writing a pipe, aborting some process would do nothing! Note the UNIX read and write services have well defined error returns (they return the count of characters actually read or written). In case of deadlock, therefore, a read that might otherwise have blocked should return immediately, indicating that there was a problem by returning a character count less than the expected count (the buffer size).
Part A: (2 points) Here is a basic page fault handler, assuming all pages are read-write. We assume an array state indexed by page number and used to record which pages in the address space are currently allocated or deallocated. This array may be packed with one bit per entry, although later, we will assume that each entry has a more states.
proc(va) -- a fault handler, registered with on_va_fault
r = alloc(va) -- try to get a page frame
while r = no_mem
va1 = target for replacement
-- assert state[va1/pagesize] = allocated!
lseek( file, va1, 0 )
write( file, va1, pagesize )
r = dealloc(va1)
-- assert r = success because va1 is a target to replace!
state[va1/pagesize] = deallocated
r = alloc(va)
-- r may not be no_mem! there may be competing processes!
endloop
state[va/pagesize] = allocated
lseek( file, va, 0 )
read( file, va, pagesize )
return
Part B: (2 points) We cannot use LRU because there is no hardware assistance offered. We cannot rely on a mark bit for mark-sweep collection because no assistance is offered. Because the only access rights settings permitted for allocated pages are read-only and read-write, we cannot use soft page faults to mark pages. Thus, random replacement seems to be the only viable policy.
But, we can use soft page faults to distinguish between clean and dirty pages. This requires that pages have three states in the state array maintained by the fault handler -- deallocated, clean and dirty are good names for those states. With this, we can randomly replace clean pages. The following pseudocode illustrates this:
proc(va) -- a fault handler, registered with on_va_fault
if state[va] = clean -- soft page fault
state[va] = dirty
r = set_ar(va, read_write)
else -- hard page fault
r = alloc(va) -- try to get a page frame
while r = no_mem
loop
va1 = (va1 + pagesize) mod memsize
exit loop when state[va1/pagesize] = clean
if state[va1/pagesize] = dirty
-- clean a page
lseek( file, va1, 0 )
write( file, va1, pagesize )
r = set_ar(va1, read_only)
endif
endloop
-- assert state[va1/pagesize] = clean!
r = dealloc(va1)
state[va1/pagesize] = deallocated
r = alloc(va)
-- alloc may fail because of a competing processes
endloop
state[va/pagesize] = clean
lseek( file, va, 0 )
read( file, va, pagesize )
endif
return