G5BADS formal coursework 2006-2007

File System. Deadline: 6 December 16:00

The coursework consists of two parts:
  1. a Java program which implements a simplified file system (see below)
  2. an essay (in pdf - other formats will not be marked!) which explains how your program works, a big-Oh complexity analysis of the file() method, and your reasons for choosing the data structure(s) used in your program. I expect approximately 2 pages, no strict page limit.
There is no fixed proportion of the mark associated with each of the two components, because they cannot be marked separately from each other.

Java program: File System

The coursework involves writing a very simplified file system. A filesystem is a record, held in memory, of the relationships between directories and files and which disk blocks are allocated to which files - you don't have to write anything complicated to do with the actual file content or storing file information on the disk.

A file system consists of directories and files allocated to disk blocks. Directories can contain other directories and files. For simplicity we assume that only files occupy disk space. The disk is partitioned in blocks of size 1 KB and blocks are numbered 0, 1, 2,... For simplicity we assume that file size is always an integer and that a file of n KB occupies n disk blocks, not necessarily consecutive.

The top level directory is called root. You may assume that names of files and directories are strings which only contain 26 ASCII lower case characters and numerals 0-9 (in any order, no spaces, no other symbols). The unique name of a file or directory is an array of strings which describes the path from the root to the file, the last string in the array being the file name (see example below). For example, the full name of file4 is [root,mail,inbox,file4]. added 10/11/06 There can be several things called file4, so long as they are in different directories they have different file names.


                   /  |  \
                  /   |   \
                 /    |    \
              mail  docs   java
              / \     |        \
             /   \ file1 (2 KB) \
            /     \              \ 
     file0 (3 KB) inbox         file2 (2 KB)  
                  / \
                 /   \
      file3 (1 KB)  file4 (1 KB)

block 0 - [root,mail,file0]
block 1 - [root,mail,inbox,file3]
block 2 - [root,mail,file0]
block 3 - [root,docs,file1]
block 4 - [root,mail,file0]
block 5 - [root,mail,inbox,file4]
block 6 - null (this block is free)
block 7 - [root,docs,file1]
block 8 - null
block 9 - [root,java,file2]
block 10 - [root,java,file2]

The methods of the
class are:
  1. constructor
    FileSystem(int m) 
    intitializes a file system with the empty root directory and m KB of disk blocks.
  2.  void file(String[] name, int k) 
    creates the file of size k KB in the directory indicated by the file name, and allocates disk blocks to it. If any of the directories in the file name don't exist, they are also created. If there are not enough free blocks for the file, throws OutOfSpaceException. If the first directory is not root, throws BadFileNameException. You do not have to check that the file name contains only lower case alphanumeric characters. Added 8/11/2006: if the file already exists, removes the old version (de-allocates disk blocks) and creates the new one. If it is a name of an existing directory, throws BadFileNameException. Added 10/11/2006: if the existing file takes less disk space than the version which is being created, and the current version causes OutOfSpaceException, this is thrown without deleting the old version of the file.
  3.  void dir(String[] name) 
    creates an empty directory with the given name. Added 8/11/2006: if the directory already exists, does nothing. If there is already a file with the same name or the name of the directory does not start with root, throws BadFileNameException.
  4.  void rmfile(String[] name) 
    removes the file and frees the disk space. If the file does not exist does nothing.
  5.  void rmdir(String[] name) 
    removes the directory if it does not contain any files, otherwise throws DirectoryNotEmptyException. If the directory does not exist does nothing.
  6.  String[] lsdir(String[] name) 
    returns the list of names of files and subdirectories in the directory (short names, e.g. below lsdir([root,mail]) should return [file0,inbox]). If the directory does not exist returns null.
  7.  String[][] disk() 
    returns an array where each index corresponds to a disk block and the entry is either null if the block is free or an array of strings which is the name of the file which occupies that block.
Just to save you a bit of typing, here are the exception classes: You may use Java API classes such as ArrayList in your program. If you use code you found in a textbook or on the web, you must acknowledge it. I will run the JPLag or Moss plagiarism detector tool to check for similarities between submissions and web-based material.

You are reminded of the School's Policy on Plagiarism.

Programs will be marked by humans, but I will also run correctness and timing tests. A simple test harness is available here: SimpleTest.java Note that it will only compile if you have the FileSystem class (with at least a dummy implementation of all methods).

Here is TimingTest.java . On marian, the first timed operation - creating an array of 100000 file names - takes about 300 ms. The second (real) timing test, creating the corresponding files, took about 40 seconds for an inefficient version and about 900 ms for a more efficient one.


There will be a prize for the best solution (traditionally a bottle of wine, but it can be replaced by beer or a Java book on request).

How to submit

Use CW submission system. G5BADS coursework is number 17. Please submit the essay pdf file (it can have any name), FileSystem.java, and any other java files you need to make FileSystem.java compile. You don't have to submit exception classes I provided. Please note that you have to submit all files in one go, because every next submission overwrites the previous one (you can have multiple submissions, just make sure the last one includes all the files). Also please note that you have to have the files on a School Unix machine in order to submit; put them in the Private directory or set permissions to make them unreadable by the rest of the world.

Last changed 23/11/2006 after the lecture.