Homework 12 Solved, at last

22C:116, Fall 1999

Douglas W. Jones

Here is a series of experiments that could be incorporated into a program to determine the following characteristics of /dev/hdb:
- To find the size of /dev/hdb, do an lseek(d,0,L_XTND); this sets the file position of the device to one byte before the end of file, and returns the number of bytes in the device.
- To find the sector size, or at least, the block size used by the system for I/O to the file, repeatedly do lseek(d,-2,L_INCR) followed by read(d,c,1), and measure how long it takes. This reads the file, one byte at a time, working backwards from the end of the file.
  The first read will take a moment for disk access, but successive reads after that should read from the same buffer because the system keeps a cache of blocks recently read from the disk. So, every n reads, working backward, there should be a pause for disk access, where n is the size of a block.
  Doing this backwards should defeat optimization tricks that many systems incorporate to make sequential reads work faster. For example, on many systems, when block n of a file is being referenced, the system will automatically request blocks n+1 and n+2 in anticipation of their being needed.
- To find the capacity of the disk in sectors, divide the disk size in bytes by the sector or block size in bytes.
- To find the composite capacity of any RAM caches, read the disk sequentially from start to end, guaranteeing that all sectors of the disk have been moved into cache and that the first sector is the least recently used, while the last is the most recently used. If the disk is bigger than the available cache and if either FIFO or LRU replacement are used, only the final sectors of the disk should be in the cache.
  Now, start reading backwards, one sector at a time, measuring how long each read takes. The delays should all be short and very similar to each other until you get back far enough that you hit a sector that was used long enough ago that it was ejected from the cache, so that you need to do disk I/O. That read and all following reads should take a longer time.
  It is hard to do an experiment that distinguishes between RAM cache maintained by the operating system and RAM cache that is part of the disk controller itself.
- To measure things like interleave factor, sectors per track and sectors per cyclinder, first flush out the cache, as above, so none of the sectors you're about to read are in the cache, and then start reading backward, as above, measuring the time per sector, starting with a sector you know isn't in the cache.
- To measure the number of sectors per cylinder, note that the time for successive backward reads within a track will typically be smaller than the time per read if a seek to a new cylinder is required. If the number of sectors per cylinder is n, there should be a seek every n reads.
- To measure the number of tracks per cylinder, try reading backward within a cylinder with different step sizes. If there are n sectors per cylinder, sector kn-1 is the last sector in some cylinder, if the time between reading sector kn-1 and kn-2 is t, and the time between reading kn-1 and kn-(2+t) is the same, where t is less than n, then t is a multiple of the number of sectors per track. Find the smallest value of t that satisfies this relationship, and you have the number of sectors per track; t should divide evenly into n, and n/t gives the number of surfaces.
Part A What prevents the given model from being used in Amoeba? The fact that the "get request" and "put reply" primitives in Amoeba must be in the same thread. The given code handled the request in the main thread and did the reply in a different thread.
On page 606, in the second to the last paragraph, it says that get request and put reply must be strictly paired. Two consecutive get request operations are forbidden. The only reasonable way to enforce this is to limit each thread to one RPC at a time, adding a state word to the status of each thread what request it is currently processing. If NIL, the thread is not processing a request. If non-NULL, the word points to the header buffer of the request currently being processed. Get request is only legal when this pointer is NULL, and it sets this pointer. Put reply is only legal if the header pointer matches this pointer, and it resets this pointer.
Part B The following alternate code has an appropriate population limit and conforms to the restriction inferred above:
```
	fork N threads, each running the following code
	  repeat
	    wait( get request semaphore )
	    get request
	    signal( get request semaphore )
	    process transaction
	    put reply
          forever
```
Here, we used the get request semaphore to guarantee that only one thread at a time will wait for an incoming RPC. This may be unnecessary, but it doesn't hurt, and it gives exactly the same mutual exclusion as we had with a single thread doing all get-requests.
A Problem There are several similarities between the use of capabilities in Amoeba and Demos, but
- Amoeba capabilities may be treated just like any user data type, while the Demos kernel manages capabilities in a separate address space (the Link List).
- Amoeba enforces an RPC protocol, Demos merely allows users to use RPCs if they wish.
- Amoeba allows any number of capabilities to be included in a message, while Demos has strict restrictions on inclusion of capabilities in messages.
- Amoeba uses server-side authentication, while Demos relies on the kernel to protect capabilities.
- The Amoeba kernel does not define the meanings of the access rights, while the Demos kernel defines them.
- The Demos kernel allows the distribution of capabilities to be limited by such restrictions as "use once" and "do not duplicate", no such restrictions can be enforced by Amoeba.
This list is not exhaustive.