Project on File Systems

ERODD HOME

Operating Systems - CPSC 304
Earl Rodd erodd@malone.edu Extension 8546 www.malone.edu/erodd
Project on File Systems - Introduction

Overview of DSFS

We have invented the new DSFS (Disk Saving File System). This FS has to conserve disk space. It has these characteristics:

NO disk space is used for free space bit-maps or other free space tracking methods.
Directories are not extra files with the associated overhead in disk space.
NO disk space is used for master file tables etc.
Small files fit in one sector (not cluster).
There is no concept of a cluster, the sector is the unit of allocation.

The DSFS uses a filename with a standard sub-directory name. Filenames can up to 400 bytes long.

Thus you can see that this file system saves disk space compared to other file systems we have studied!

Technical Details

These objectives are achieved by:

The BPB in the boot sector has two 4 byte pointers:
1. To the first sector of the first file.
2. To the first free sector on the disk.
The first sector of each file has some control information:
1. A 4 byte pointer to the first sector of the next file or FFFFFFFF if this is the last file.
2. A 4 byte pointer to the next sector of THIS file FFFFFFFF if this is the last sector in the file.
3. A 28 byte control structure with the permissions, date last used, date created, a 4 byte file length, and a 2 byte filename length.
4. The filename which is variable length.
5. The first n bytes of the file. Note that if the filename is 20 bytes long (.e.g. /programs/myfile.exe), the first sector will contain:
  - 4 byte pointer to next file.
  - 4 byte pointer to next sector.
  - 28 byte control structure.
  - 20 byte filename.
  - (512-4-4-28-20) = 456 bytes of filedata.
Subsequent sectors of each file have a 4 byte pointer (or FFFFFFFF if the last sector of the file) to the next sector with data for this file.
Each free sector on the disk begins with a 4 byte pointer to the next free sector on the disk (or FFFFFFFF if this is the last free sector.

Diagram of Control Structures

BPB in sector 0

*----------------------------------------* * 4 Bytes: * * Sector number of first sector of * * first file. * *----------------------------------------* * 4 Bytes: * * Sector number of the first free * * sector on the disk. * * * *----------------------------------------*

First Sector of a File

*----------------------------------------* * 4 bytes: First sector of next file. * * FFFFFFFF: this is last file. * *----------------------------------------* * 4 bytes: Next sector of this file. * * FFFFFFFF: this is last sector * * of this file. * *----------------------------------------* * 28 bytes: Control structure with: * * Permissions. * * Date Last used. * * Date Created. * * Total bytes in file. * * 2 byte length of filename. * *----------------------------------------* * 1-400 bytes: Filename * *----------------------------------------* * 512-4-4-28-FilenameLength bytes of data* *----------------------------------------*

Other Sector of a File

*----------------------------------------* * 4 bytes: Next sector of file. * * FFFFFFFF: last sector of file.* *----------------------------------------* * 1-508 bytes of file data. * *----------------------------------------*

Free Sector

*----------------------------------------* * 4 bytes: Next free sector. * * FFFFFFFF: Last free sector. * *----------------------------------------* * Remaining 508 bytes unused. * *----------------------------------------*

Exercises on DSFS

Answer the following questions about the DSFS.

Draw a diagram of what the disk looks like (this can be hand-written) when there are two files on the disk named "File1" (100 bytes long) and "/sdir1/Number2DataFile" (1000 bytes long).
How might the DSFS perform a DIR function for a certain filename.
1. Follow the BPB pointer to the first free sector and search free sectors for the name.
2. Follow the BPB pointer to the first sector of the first file, read its name. If not correct, follow the pointer to the first sector of the next file etc. until the name is found.
3. Follow the BPB pointer to the first sector of the first file. Follow the pointers through all the sectors of this file until we read a sector of another file and see what its name is etc.
4. Read all the sectors looking for ones which seem like they are the first sectors of a file and read the filenames in the sectors.
On average, about how many sectors would need to be read to do the above DIR for one file?
1. The total number of files on disk / 2.
2. The total number of sectors on the disk.
3. The total number of free sectors on the disk.
4. The total number of files on the disk.
In DSFS, to do a DIR of ALL files on the disk, how many sectors must be read?
1. The total number of files on disk / 2.
2. The total number of sectors on the disk.
3. The total number of free sectors on the disk.
4. The total number of files on the disk.
To create a new file in DSFS, what must be done?
1. Use the BPB to find the first free sector (call it sector A). Then change the BPB to point to the last sector on the disk. Update the BPB pointer to the first sector of the first file to point to sector A (it used to point to sector C). Write file control information in sector A including a pointer to sector C, the filename, and the first data in the file.
2. Use the BPB to find the first free sector (call it sector A). Then change the BPB to point to the free sector (call it sector B) pointed to by that sector making it the first free sector. Update the BPB pointer to the first sector of the first file to point to sector A (it used to point to sector C). Allocate another sector for the file control information and file data.
3. Use the BPB to find the first free sector (call it sector A). Then change the BPB to point to the free sector (call it sector B) pointed to by that sector making it the first free sector. Update the BPB pointer to the first sector of the first file to point to sector A (it used to point to sector C). Write file control information in sector A including a pointer to sector C, the filename, and the first data in the file.
4. Use the BPB to find the first sector of the first file on the disk (call it sector A). Change the control information in sector A to the filename of the new file. Move the file data from sector A to some new sector.
How would you rate this file system with regard to fragmentation?
1. Because of the small cluster (1 sector), and lack of any methods to avoid fragmentation, fragmentation will be severe.
2. Fragmentation will be less than NTFS.
3. Fragmentation will be nearly non-existent because there is so little disk space used for control structures.
4. Even if files are fragmented, reading them will still be fast.
In DSFS, which operations will be especially slow compared to other file systems? (3 are correct)
1. Once having found the first sector of a file, reading the file.
2. Doing an OPEN operation (ie. find the first sector of a file using its name).
3. Finding 1 free sector.
4. Erasing a file.
5. Adding data to the end of a file.
6. DIR of all files in a sub-subdirectory.
In real life, operating systems provide large (100s of MB) memory cache areas so that recently or frequently used sectors are kept in memory. In this file system, what sectors would likely be found nearly permanently in cache?
____________________________________________
____________________________________________
____________________________________________
____________________________________________
Write pseudo code for code to release the last sector of a file.
Write pseudo code for code to implement a "get free sector" subroutine.