|
Project Information
|
Lab 3: A "Flat" File Directory for a File System Based on BlockGroup's Team Lab #2 CS 5631, Spring 2011 Doxygen & Diagram for Design Due Monday, February 21 (8 points) C++ Program Due Monday, February 28 (22 points) Revisions None yet. Introduction In this lab you will continue with the File System you have been constructing. So far (in File System Lab 1), you have created a FreeList class that lets you keep track of unused blocks on the Disk and a BlockGroup class that lets you organize other disk blocks into groups. You have likely noticed that so far we are only keeping track on Disk (i.e., in the master block) of location information about the FreeList (the start block number, end block number and number of blocks). That is, we have not yet been storing location information on Disk about BlockGroup's. In this lab, you will be creating a Directory class, and any other support classes that you find useful, in order to eventually do this (store start block number, end block number, and number of blocks for BlockGroups to Disk). Your Directory will contain directory entries. Each directory entry will keep track of two pieces of information. One of the pieces of information in a directory entry will be a name-- these will be used later (File System Lab 3) as file names. The other piece of information that you will include in a directory entry will be the block number for the File Control Block for the file. The File Control Block will contain the start block number, end block number, and number of blocks for the BlockGroup that represents a file. Your Directory should be "flat". This will mean that your Directory will not contain sub-directories. While sub-directories are useful, they require a more complex implementation than a "flat" directory. One consequence of using a "flat" directory is that you will maintain only a single (one) directory on Disk. Resources Chapters 10 and 11 of our course text. I strongly recommend you read these to prepare for this lab. In particular, you should read Section 10.3 on Single-Level Directories. General Doxygen reference Doxygen reference on commenting Doxygen documentation for the BlockGroup, FreeList, BlockLinkedList, Block, and Disk classes. Valgrind: A tool to find memory leaks. Some Unix man pages for directory accessing. These only provide reading, not modifying-- you need to think about modification operations. Also: Don't take these too literally. They are specific to Unix, and yours can be simpler and/or more elegant!! opendir readdir scandir closedir Some details Documentation for C++ Classes I won't be giving you my documentation for my solution this time around. Instead, your first goal in this lab is to come up with a written design for your Directory class API ('application' programming interface). The structure you will follow for this design will be Doxygen. For some information on how to format your C++ code to be suited to Doxygen, see the Resources section above. By using Doxygen, I mean that you will be creating "stub" code for your classes and documenting this stub code. "Stub" code contains the names of all methods and classes, as well as the parameters for all methods, but none of the methods need to have code written in the method bodies. Also, the data members of the classes do not need to be defined yet (except perhaps for the DirectoryEntry class-- see below). Your design will be submitted one week before the C++ program code solution for the lab. See due dates above, and see submission at the bottom of this page. What about the start and end block for my Directory BlockGroup? While you will use a BlockGroup to represent your Directory on Disk, and this Directory BlockGroup will store information for various other BlockGroup's (actually, the Directory will store information about FCB's and the FCB's will store information about other BlockGroup's), there is, of course, the problem of storing the information about the Directory BlockGroup (start block number, end block number, and number of blocks) itself! That is, the Directory is going to be represented as a BlockGroup, and therefore the Directory BlockGroup has start and end block numbers, and a number of blocks. Storing the start and end block numbers for the Directory will entail modifying the information stored in the master block. That is, along with information about the location of the FreeList, information about the Directory will be stored in the master block of the disk. Implict in the fact that a Directory is a BlockGroup is the idea that your Directory may have more than one block in it. For example, if you are representing, say, 20 files, and your file names each can be 40 characters in length, you will likely find it necessary (with 512 byte blocks on Disk) to use more than one block in your Directory BlockGroup. Your Directory must be capable of holding an arbitrary number of entries. The limit on the number of entries should depend only on the number of disk blocks available on the Disk (i.e., in the FreeList for the Disk). That is, you need to code your Directory so that it potentially can have lots of directory entries and those will naturally span multiple disk blocks. What information should I represent per "file" entry in the Directory? Later, you will be using your Directory implementation (in File System Lab 3) to keep track of information for BlockGroup's that are representing files of data, so you should think in those terms. At a minimum, for each directory entry, you will need to represent a file name (use a fixed maximum length on file names), and the block number of a File Control Block. It is possible you will need other information as well. I suggest you design and program a DirectoryEntry class to represent the data that will be in each directory entry. I further suggest that each of the data members for the DirectoryEntry should be public-- this will just be a utility class (analogous to the Block class). You should submit Doxygen documentation for your DirectoryEntry class as part of your design. What about methods for the Directory class? What methods should I have? Well, this is one main thing you will need to decide in your Doxygen-based design. Your Directory needs to let you deal with directory entries, and must enable these to be stored on Disk in the blocks of the BlockGroup associated with the Directory. You must be able to: 1) open the directory, 2) retrieve directory entries from Disk, 3) search for a directory entry by name (i.e., by file name), 4) save entries to Disk, 5) delete a directory entry, 6) rename a directory entry, 7) add a directory entry, and 8) close the directory. I recommend that you store all entries for a Directory in RAM during a "session" in which you are using the Directory. This is very different from the way you previously worked -- with the BlockGroup class and FreeList. In that case, you wanted to not store much of a BlockGroup or the FreeList in RAM. I'll repeat myself: In the case of the Directory, it is reasonable to store all of the directory entries in RAM during a single session of using the Directory. Of course, you will need to provide methods that enable these (possibly changed) directory entries to be "flushed" to (synchronized with the) Disk. The assumption you will be making when you temporarily cache all of the entries for the Directory in RAM is that the total number of bytes for all combined Directory entries is relatively small, and the number of entries will be relatively small (e.g., on the order of 10 to 100 files referenced from a directory). Design of Directory disk blocks In addition to your Doxygen-based design for this lab, you are also required to submit a clearly explained and labeled diagram (preferably drawn with a vector graphics drawing program such as Adobe Illustrator) that illustrates what will be contained in a typical disk block of your Directory BlockGroup. E.g., it should explain how many Directory Entries can be contained per disk block. Just like your linked list nodes in Lab 1 had a particular structure on disk, so too will your Directory disk blocks. Testing Use the same kind of menu driven testing as in the earlier labs. Make sure to be systematic in your testing. For example, make sure you test adding enough "files" (directory entries) to make the Directory span multiple Disk blocks in the BlockGroup that represents the Directory, and also make sure to test deleting all of these "files". Goal Submit your design, including the diagram illustrating the disk layout of your Directory disk blocks, by the due date for the design. Submit your working program code by the due date for the C++ code. After you implement a class (or even better, after implementing one or two methods for a class), write testing code to test the class, and carry out the testing and debugging. I code a static Test method in each class, and put my menu-driven testing code for the class in that method. When you write the C++ code for each of your classes you should create menu driven testing (like in earlier labs) that provides testing of that class. Use proper software engineering style-- (a) Document your methods (Doxygen comments before each method indicating the purpose of the method), and document your program code that implements the methods. (b) Use named constants instead of numeric values where this improves readability (it usually does improves readability!!). (c) Use variable names and method names that have meaning in the context of the program you are writing. Submission By the Design due date, upload your Doxygen (zipped) to https://webdrop.d.umn.edu/ For the Doxygen design, you will be graded on (a) having a complete set of methods that will enable use of a Directory and DirectoryEntry classes, and (b) on your descriptions of your methods. In general, you need to provide clear and complete descriptions of the operations your methods will provide. You should attempt to anticipate (and document) the types of error situations, and reasons for these errors, that will occur when calling the methods you specify for the Directory class. Also upload your design diagram for the Directory disk blocks, unless you have hand drawn this. If it is hand drawn, submit the paper diagram by the due date. If you submit your diagram in a file, it should be in PDF format. By the C++ program due date, turn in hardcopy (a printout) of your running program code (.cpp and .h files). Also turn in hardcopy of your testing output. Make sure to be systematic in your testing. If you have made changes to your earlier classes (e.g., Block, BlockGroup), turn in hardcopies of that too (if you have made no changes to your other classes, you don't need to turn it in again on hardcopy). Also, upload your C++ program (.zip file of all the program code and classes) by the due date to: https://webdrop.d.umn.edu/ If you use Netbeans, be careful that when you zip up your files for submission that you have included the source files. It can be easy for Netbeans to have entirely separate directory locations for your project and your source code. Each team should turn in just one submission, including both hardcopy (please, no line wrap on the code hardcopy output!!) and web drop. Please submit a cover page on your hardcopy that includes all of the names of the team members. For the program code you web drop, please ensure that each of your program code files (i.e., the .cpp and .h files) have all of the names of the team members. |