EECS 482 Winter '02 
Homework 3
Due in discussion 3/31 or 4/2

1) RPC is used like procedure calls because marshalling of parameters
and return values is transparently done by the stubs of client and
server.

For simplicity, let's assume that the client and server have the same
architecture (i.e. the same data representation). An RPC needs to pass a
linked list as a parameter, which may be changed upon return.

Come up with an approach of marshalling and unmarshalling the linked
list in client stub. (Hints: how to tell where the list ends? Using
size in the header of message like in project 3 or using a simple
protocol or sentinel.)

Each node in the linked list is a single name (no spaces) and age
and has this structure:

struct node
{
    char name[20]; /* Names do not contain spaces */
    int age;
    struct node* next;
}


2) Suppose that the block size is 1000 bytes.  A program makes the
following read requests via different system calls:
- Request 1: read a single byte from offset 8,000 within the file
- Request 2: read a single byte from offset 15,000 within the file

Each file has a file header (inode), which takes up one disk block and
is not in memory.  What is the number of disk accesses required to
process each of the requests for the following file structure schemes.
Assume that there is no caching of any disk blocks from request to
request.

a) Sequential (contiguous) allocation

b) Non-uniform depth multi-level indexed file inodes (UNIX-like file
inodes).  The inode contains 10 direct pointers and 2 indirect
pointers.  The direct pointers point to data blocks.  An indirect
pointer points to one disk block (called indirect block) that contains
pointers to data blocks.  Assume that size of each pointer in the
indirect block is 4 bytes and there is no caching.

c) How would b) change if all disk blocks are cached after being fetched
from disk?

d) What is the largest file size in bytes that can be supported by the
system in part (b)?

e) If the block size were changed to 2000 bytes, would the new maximum
file size be

   i) twice the maximum for 1000 byte blocks
   ii) more than twice the maximum for 1000 byte blocks
   iii) less than twice the maximum for 1000 byte blocks

3)
a) What is the most common single-file access pattern in typical file
systems?

b) Recall that the physical sources of delay in disk accesses are seek
time and rotational delay.  How are files laid out on disk to minimize
physical delay for the common case?  You may assume that your disk has
ample free space for your layout policy.

c) In light of your answers to parts a and b, what does the operating
   system typically do when asked for the first block of a file?  Why?

Suppose you had a set of applications whose most common access pattern
was a "strided read".  In a strided read, the application first reads
blocks 1, 1+n, 1+2n, and so on to the end of the file.  N can take any
constant value for a particular execution of an application.  This
scenario applies to both parts d and e.

d) What problem does this introduce for the algorithm in part c?  When
   do you know the value of n? How would you modify the algorithm in
   part c to eliminate this drawback, but provide all of the
   algorithm's benefits as soon as possible?

e) Suppose you knew that N was always a non-negative integral power of
two.  How would you change the way files were laid out on disk?  What
are the additional space requirements of your new layout policy,
expressed in terms of the nominal space requirements.