[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

1. Main task

Your task is to build an RPC mechanism and a remote filesystem using the RPC mechanism. You can use the provided local filesystem as a basis, or you can throw it away and replace it with an extended version of your own filesystem from HW4 (if it works!); the same goes for the provided cache and mbox implementations. You may also rearrange the current division of the filesystem into fs.c, fs_local.c, and fs_remote.c if it is helpful. The only thing we ask is that you preserve the interface to each system component as defined in the appropriate header files so that the test programs will continue to work.

1.1. RPC mechanism

Your RPC mechanism should be built to match the description in rpc.h using UDP packets as its communication mechanism. We recommend use of the provided UDP library in network.c and network.h for creating UDP sockets. Note that while we have provided two convenience routines for handling receiving UDP packets with timeouts and replying to messages sent to a server, much of your use of UDP sockets (especially on the client side) will probably involve standard system calls like write or read. See test_network.c for examples.

Note that UDP packets are limited in size; for this reason, your RPC routines should also limit the size of arguments and return values. UDP packets may also be lost or duplicated. Your RPC library is responsible for resending lost UDP packets (which can be detected by not receiving a reply packet within some reasonable timeout) up to some fixed maximum number of times. You are not responsible for catching duplicate packets; instead, any user of the RPC library (including your remote filesystem) should expect that duplicate RPC calls might occur from time to time and should structure their operations to be appropriately idempotent in response. You are, however, responsible for making sure that RPC return values are delivered to the proper caller—you must include some mechanism to discard duplicate any possible reply packets from previous RPC calls.

In order to implement your RPC mechanism you will need to make some choices about how to organize the data in each UDP packet, what packets are sent and when, and so forth. You should document the resulting protocol and explain why it is structured the way that it is. To make things easier, you may assume that any use of the RPC mechanism is between clients and servers running on identical machines with identical programming environments, so that you can transmit raw binary structs without worrying about issues like endianness or encoding of various data types.

1.2. Remote filesystem

Your remote filesystem should provide essentially the same operations as the filesystem in CS422/Assignments/HW4. Creating and opening remote files should be transparent to the user; the only indication that a file is remote is that the filename has a different syntax, of the form hostname:port-number:remote-filename, e.g. lion.zoo.cs.yale.edu:9997:big-ugly-file. A call to fs_open with such a filename should return an integer file descriptor that can then be used for standard file operations like fs_seek, fs_write, etc. exactly as if it were a local file. It is up to you to decide how to handle ill-formed or ambiguous filenames (e.g. is is:local:file? a bad remote filename or just a confusing local filename?). Please document whatever choice you make.

Because large read or write operations will need to be broken up into smaller operations to fit inside the RPC argument and return value size limits, you may need to relax slightly the semantics of read and write operations provided by the local filesystem. You do not need to ensure that large read or write operations are atomic: as in NFS, it is acceptable if fragments of two simultaneous large writes appear to be interleaved. However, you should try to ensure that read or write operations small enough to fit within the RPC limits are still atomic.

Your implementation will consist of two parts, plus a utility program. The two parts are the client-side library extending the filesystem routines whose interface is given in fs.h to allow remote access, and a server program. The provided files assume that you will put your client-side routines in fs_remote.c; however, you may choose to modify this structure, and are permitted to do so as long as you document your design. The server is assumed to be implemented in fs_remote.c; we have provided a skeletal argument parser but not much else. The utility program is in fs_remote_shutdown.c; this should send an RPC that cleanly shuts down the server program (e.g. by calling exit(0)).

You will need to design a protocol for encoding file operations as remote procedure calls. The file fs_protocol.h is provided to allow the various components of the remote filesystem implementation to share details of the protocol. You should provide separate documentation of your protocol design.

2. Multiple virtual machines

The provided disk and kmem simulators from the previous assignment allowed only a single simulated disk and shared-memory segment per machine. To make debugging your system easier, we have provided a modified version of these simulators that allows multiple virtual machines with their own simulated disks and shared memory segments to appear on the same physical machine. These are selected by setting the VIRTUAL_ID environment variable; see the Makefile for examples. If VIRTUAL_ID is not set, a default empty id is used.

You can also test your implementation by running it between two machines. The provided Makefile contains an example of this in the rules for run_sieve_client and run_sieve_server which set up the sieve program to be run on one machine while the filesystem it uses runs on another. See the comment in the Makefile for details on how to use these rules.

3. No design review

There is no required design review for this assignment. Instead, you are required to thoroughly document your design and the choices that went into it as part of your final submission. The quality of this documentation will provide the basis for the part of your grade that would otherwise be determined by the design review.

4. Extra credit

You may earn up to 4 points of extra credit, 1 for each of:

Mandatory file locking
Provide fs_lock and fs_unlock routines that work on open file descriptors, with the property that any operation on a locked file by a process that doesn't hold the lock blocks until it the lock is released. These should work on both local and remote files.
Named pipes (local filesystem)

Provide a routine fs_create_pipe that creates a named pipe, which can be opened like a normal file but whose fs_write and fs_read operations act like mbox_send and mbox_recv. In particular it should be the case that each call to fs_read returns the data written by a single fs_write call, in FIFO order, and that fs_read blocks until data is available. (Note that these message-oriented named pipes are different from Posix named pipes, which are character-based streams). As with mboxes, you may put an upper bound on the number of pending items in a named pipe and block senders that attempt to send too much.

Named pipes (remote filesystem)
Provide named pipes across the network, so that messages need not be sent and received on the same machine. Your implementation should tolerate duplication or loss of packets in the underlying UDP system without corresponding duplication or loss of messages.
Some new feature or application we haven't thought of
You can do pretty much anything here, as long as it (a) has a clear connection to the rest of the assignment, (b) demonstrably works, (c) is well-documented, and (d) is cool. As always, Rodrigo is the ultimate judge of coolness, so you may wish to run any ideas by him before you go and implement them.

In each case you are responsible for documenting your improvement and demonstrating that it works.

2014-06-17 11:58