Homework 6 is due 04/30 at 12:01am EDT
The written problems and programming problems are to be done individually(4/12 updated). All homework submissions are to be made via Courseworks. Refer to the homework policy section on the class web site for further details.
Written Assignment (40 pts)
Exercise numbers refer to the course textbook, Modern Operating Systems. Each problem is worth 5 points. Make your answers concise. You'll lose points for verbosity.
- MOS 4.27
- MOS 4.32
- MOS 4.33
- Describe when you run an unlink() operation to remove a file on the ext3 file system. Be specific about what disk blocks have to be written where in what order. State your assumptions.
- The ext3 fsck program recovers a crashed ext3 file system by scanning the journal of this file system and replaying each record in the journal. The ext3 fsck program also clears the journal to save space for new journal records. Is there a strict order between the two steps? Why or why not?
- In the software v.s. hardware virtualization paper, the author discussed the problem with popf in Section 4.4. What exactly is the problem?
- As the number of cores keeps increasing, the probability that some cores fail at any given moment also increases. What are the implications of this trend on Barrelfish?
- Write pseudo code to implement the pthread_create wrapper of the Tern memoizer. Note you need to describe your data structure for maintaining deterministic thread IDs. In addition, think of what may go wrong when the child thread calls self().
The performance of a file system depends upon the cache hit rate (fraction of blocks found in the cache). If it takes 1 msec to satisfy a request from the cache, but 40 msec to satisfy a request if a disk read is needed, give a formula for the mean time required to satisfy a request if the hit rate is h. Plot this function for values of h varying from 0 to 1.0.
A UNIX file system has 1-KB blocks and 4-byte disk addresses. What is the maximum file size if i-nodes contains 10 direct entries, and one single, double, and triple indirect entry each?
How many disk operations are needed to fetch the i-node for the file /usr/ast/courses/os/handout.t? Assume that the i-node for the root directory is in memory, but nothing else along the path is in memory. Also assume that all directories fit in one disk block.
Programming Assignment: Tagging The Files (60 pts)
Programming assignments are to be done individually. In this programming assignment, you'll implement a mechanism to tag files in xv6.
The files needed for this assignment are distributed using the Git distributed version control software. To learn about Git, take a look at the Git user's manual, or, if you are already familiar with other version control systems, you may find this Git overview useful.
To get started, run the following commands
$ git clone http://debug.cs.columbia.edu/xv6.git xv6
$ cd xv6
$ git checkout -b hw6 origin/hw6
Submission instructions
When you are ready to hand in your solution, put your UNI in conf.mk, commit all your changes, and run make handin in the xv6 directory. This will generate hw6-programming-<your uni>.tar.gz for you, which you can then upload via courseworks. This tar ball includes a snapshot of all xv6 source code and a patch generated using git diff origin/hw6 hw6. Thus, be sure you commit all your changes (including the new files you add) before running make handin. Double-check the patch in the generated tar ball. It should contain all your changes in the source code.
We will be grading your solutions with a grading program. You can run make grade to test your solutions with the grading program. Note that it takes a while to run the test programs, so please be patient.
Description
In this assignment, you will add a new feature to the xv6 file system to allow users to tag files with arbitrary key-value pairs they define. This tagging feature can be very useful. (I'm sure you can come up with many applications of this feature, e.g., desktop search.) It actually exists in many applications already. For example, you can add tags to PDF, JPG, MP3 and many other media files. However, these application-specific implementations are ad hoc and must be re-implemented for new applications. In this assignment, you'll provide a general implementation in the xv6 file system so that it applies to all file types.
You'll need to implement the following three system calls:
- int ftag(int fd, char *key, char *buf, int len);
System call ftag() tags a file identified by file descriptor fd with a new key-value pair, with the key being key and value buf. Argument key is a null-terminated string with a maximum length of 10 and minimum length of 2, counting the ending null byte. Argument buf specifies the value in the key-value pair, and len specifies the length of buf. If key already exists in file fd's tags, this system call should overwrite the old tag with the new one.
- int funtag(int fd, char *key);
System call funtag() removes a tag with key key from the file fd. If there is no key-value pair matching key, funtag() should return an error.
- int gettag(int fd, char *key, char *buf, int len);
System call gettag() retrieves the value mapped to key from the file fd. The retrieved value is stored in buf whose length is specified via len. gettag() should return the length of the value if it exists and -1 otherwise. If the value is longer than len, gettag should return an error.
To implement these system calls, you'll need to change the on-disk representation of an inode and add code to fs.c. Depending on your design, you may need to change mkfs.c so that the layout of new file system created by mkfs is consistent with the file system layout expected by fs.c.
Your implementation should consider different corner cases and return errors correspondingly.
To give you more time to study for your final exams, we've decided to simplify things for you: all tags of a file fit within one 512-byte disk block. You never have to allocate more than one disk block to store the tags for each file.
Hint: You can reserve one inode entry for file tagging. In fs.h, change NDIRECT to 11, and add a special entry in struct dinode.