Nachos Project: Distributed File System version: 4 Sep 1999 Scott Stoller (stoller@cs.indiana.edu) Indiana University BACKGROUND This project ("DFS project") is offered as an alternative (or supplement) to the Filesystem and Network projects that come with Nachos. Compared to the File System project, the DFS project emphasizes programming experience with different topics (namely, caching and message-based process synchronization, instead of directory data structures), which I think are more beneficial to students. I find the Network project unsatisfying, because it does not involve user programs running on the simulated machine, so it does not build on students' work in the previous projects. I have used nachos-dfs under Solaris with Sun CC and GNU g++, and under Linux (Red Hat 6.0) with GNU g++. To switch between these 3 options, simply comment and uncomment a few lines in code/Makefile.common and code/Makefile.dep. OVERVIEW In this project, you implement a simple distributed file system (DFS). Each machine acts as both a server and a client. (Note: "machine" here refers an entire UNIX process running nachos). When a user process opens a file with a name of the form "integer/string", this refers to a file stored on the server whose network address is the specified integer. For simplicity, you can assume that there are always at most 10 machines, numbered 0-9, so the "integer" here is a single digit. From machine/network.h, we see that network addresses are integers: typedef int NetworkAddress; A filename that does not begin with "integer/" refers to a file stored on the local machine. Thus, for a process running on the machine with network address addr, "string" and "addr/string" refer to the same file. A server with network address addr stores all of its files in a UNIX directory named "addr"; think of this directory as the disk of the fictitious machine on which that instance of nachos is running. For example, the machine with network address 0 would store a file named "testfile" in a UNIX file named "0/testfile". This implies that if (e.g.) machine 0 opens an executable "test-pgm", that executable must be accessible as ./0/test-pgm. I found the easiest way to arrange this is (starting in the directory where you'll run nachos): cd 0; ln -s ../test-pgm test-pgm (and similarly for machines 1, 2, etc.). The file block size BlockSize is defined in openfile.cc. Do not change network/post.h or network/post.cc. To help you get started, openfile.cc contains an implementation of a very limited distributed file system: ReadAt and WriteAt assume that requests are block-aligned and involve at most one block of data. You should eliminate this assumption (so "position" and "numBytes" can be arbitrary), implement caching of blocks of remote files, and implement the remaining file operations (create and remove) for remote files. Also, that code is built on a nachos that does not support multitasking or virtual memory (unlike your code, which will be built on your nachos from proj3). In openfile.cc, mailbox 0 is reserved for receiving DFS requests. Each machine has a thread running function dfs_server, which continuously reads messages from mailbox 0 and handles the requests. Because this thread never terminates, you need to explicitly kill nachos (e.g., using ^C). To help avoid runaway nachoses, machine/network.cc contains code that causes a long-running nachos process to eventually print "Exceeded limit on CPU time!" and stop. NETWORK SEMANTICS It is important to consider the semantics of the nachos network: packet delivery is FIFO (messages between 2 machines arrive in the order they were sent) reliable (ignore comments in the code saying the network is unreliable; we'll always set the reliability parameter to "reliable") asynchronous (there is no bound on how long it takes for a packet to arrive at its destination) In practice, the nachos network is not completely asynchronous (because of the cutoff of 5*mu in exponential_distrib in machine/network.cc), but your DFS must be designed to work correctly with a completely asynchronous network. CACHING When the owner of a file receives a Read request, it sends the data as soon as possible. Network communication is relatively slow, so to improve performance, each client should cache recently-used blocks until a cache replacement occurs (because the cache is full) or the data is too old (see below). If a client writes part (but not all) of a block, the server should send back the entire contents of the block (including, for simplicity, the data just written by the client), so the client can cache it. Caching arbitrary fragments of blocks is more trouble than it's worth. The client (not the server) keeps track of the file position pointer (currentPosition in an OpenFile object). The client must do this, so that read requests satisfied from its cache occur at the right position. Thus, each Open system call still creates an OpenFile object on the client machine. When does written data get sent to the file's owner? Of course, when a cache entry containing modified data gets re-used, the data must be sent to the file's owner. Write-through caching makes the DFS look more like a centralized file system but may increase network traffic (since the data may get overwritten soon). So, you should adopt a delayed-write policy (like Sun NFS does), and use a timer to ensure that modified blocks are sent to the owner within a bounded amount of time. The timer interrupt handler should not send the data itself, since network I/O routines are blocking. Instead, the timer interrupt handler should awaken a dedicated thread that sends the data. P436 ONLY: You are free to implement write-through caching, though you will get less extra credit that way. Use a timer to ensure that data seen by readers is not too old. In the simplest approach, each client periodically invalidates (discards) the blocks that have been in its cache for longer than some threshold. An obvious optimization: When the timer goes off, the client marks the blocks as invalid but keeps the data (until the cache entry is re-used). When the client sends a readBlocks request, it indicates which blocks it has in "invalid" mode and includes a timestamp, indicating when it got the data. If those blocks haven't changed, the server replies "use the cached data". This optimization is not required. You can get extra credit for implementing it, but don't even think about doing this until the required functionality is working. Use a file-block cache with a fixed number of entries. The cache should be in kernel memory (not user space). Use a reasonable policy (e.g., LRU) when a cache entry needs to be re-used. To implement lookup in the cache, a hash table would be best, but you won't be penalized for using linear search. Think about how operations like Create and Remove interact with caching. Think about and briefly discuss in your README the behavior of your cache when multiple user processes in a single machine open the same file. Think about what synchronization (if any) is needed for threads accessing the cache. TESTCASES Introduce a debug flag "-d c" which causes nachos to print messages whenever it reads a remote block, writes a remote block, or replaces a block in the cache. Your testcases should include at least the following 3 kinds of tests: 1. Some application programs that call Create, Read, Write, and Seek on remote files. 2. Some application programs that call Exec on remote files. 3. Add a flag to nachos, with the format "-sm ", where represents an integer. "sm" is an acronym for "swap machine". The effect of this flag is that swap files are located on the machine with the specified network address, instead of on the local machine. Regarding case 1: In addition to testing simple situations, ideally you would also some test some more interesting situations, such as calling Create on an existing file while some other machine is reading or writing it. Since things happen so fast, this would require some work (e.g., deliberately introducing delays). Since time is limited, you don't need to present exhaustive testcases to show the correctness of your DFS; a few simple testcases are sufficient. GETTING STARTED For this project, you should compile nachos in code/network, because code/network/Makefile contains -DNETWORK and -DDISTRIB_FILESYS. Please do not modify the FileSystem class (unless you really need to; if so, mention this in your README!). The communicating nachoses run as separate UNIX processes on a single UNIX workstation. test/dfs-test.c is a simple example of how to use the distributed filesystem. The code in ~os/nachos-dfs is sufficient to run dfs-test correctly. Ideally, you should do this project by extending your nachos that supports multitasking and virtual memory. If your implementation of virtual memory does not work, you can do this project by extending your nachos that does not support virtual memory. However, the synchronization issues in this project are simpler when virtual memory is not supported, so teams that take this approach will receive a 10% penalty on this project. filesys/openfile.cc is probably a sufficient example of nachos network communication, but if you'd like to see another example, have a look at network/nettest.cc.