Assignment 6, due Mar. 4
Part of
the homework for 22C:112, Spring 2011
|
On every assignment, write your name and the course number legibly. Exceptions will be by advance arrangement unless there is what insurance companies call "an act of God" (something outside your control). Homework must be turned in on paper, either in class or in the teaching assistant's mailbox. Never push late work under someone's door!
a) The need to set aside the queue before serving it is the result of what could otherwise happen if disk requests were enqueued in the queue for the cylinder currently being served. What is the problem and why is it solved by setting the queue aside before beginning to serve it? (0.5 points)
b) Consider this alternative approach: The queue is maintained as a binary search tree, sorted by linearized disk address (of the various BST organizations, a splay-tree works best, but this is not relevant to the problem). The left child is for all requests less than or equal to a node. A unidirectional elevator algorithm is used, traversing the tree from left to right and deleting each node as it is served. Does this approach suffer from the problem identified above? Explain why or why not. (0.5 points)
One way to organize the sectors of a file on disk is to use this 64-bit sector number as the key in a search tree, where the leaves are the disk sectors of files, and the internal nodes of the tree are index sectors used to locate the correct leaf. The B-tree data structure is particularly appealing for this purpose (see the Wikipedia entry on B-trees).
Assume that disk sectors are 512 bytes, and that linearized sector numbers are 64 bits long.
a) If the aggregate content of all data in all disk files occupies 1 gigabyte (that is 230 bytes), how many disk sectors would be occupied by the B-tree needed to provide access to this data. (0.5 points)
b) If the aggregate content of all data in all disk files occupies 1 gigabyte, How many disk accesses would be required to find the location of a randomly selected disk sector. (0.5 points)
a) If the file system uses some kind of index sectors to locate the data sectors of a file, how would you modify the above scheme to allow files to be read as quickly as possible? (0.5 points)
b) Suppose your application has multiple files open for output and it occasionally adds sectors to each of them. Suggest an allocation policy that tries to appoximate an optimal allocation pattern without knowing in advance which files will end up being large files and which will stay small. (0.5 points)
Modify the code for Machine Problem 1 to support double-quotes around arguments, used to group those arguments into a single argument, and add the following built-in commands to your shell:
See man 3 exit and man 2 wait for documentation on how to set and test the exit status of a program.
See man 2 lseek and man 3 fseek for tools that allow you to mark the current position in a file or change the position to the marked position. These pages also document the return values that result from attempts to seek on devices that do not allow seeking.
See man 1 test for documentation of a command that will be the most popular command to execute as the argument of a while command.
tcsh -c "tcsh command" will call tcsh to execute a single command from its command line argument. If you create a directory with some files in it, you can make a loop that successively deletes files from the directory using the following shell command as a loop body:
tcsh -c "rm `ls | tail -1`"
All of the above assumes that you have the search path mechanism assigned for machine problem 1 debugged.
Submission instructions, as with machine problem 1, but call your shell mp2.c and submit it in the mp2 directory.