File-System Implementation

File-System Implementation

1. File-System layout

   • MBR
     • Sector 0 of the disk, and used to boot the computer. The end of the MBR contains the partition table. This tables gives the starting and ending addresses of each partition.
     • One of the partitions in the table is marked as active. When the computer is booted, the BIOS reads in and executes the MBR. The first thing the MBR does is locate the active partition, read in its first block, which is called the boot block, and execute it.
     • The program in the boot block loads the operating system contained in that partition. For uniformity every partition starts with a boot block, even if it doesn't contain a bootable operating system.
   • disk partition
     • boot block
       • The first block in the active partition. The program in the boot block loads the operating system contained in that partition. For uniformity every partition starts with a boot block, even if it doesn't contain a bootable operating system.
     • super block
       • It contains all the key parameters about the file system and is read into memory when the computer is booted or the file system is first touched.
       • Typical information in the superblock includes a magic number to identify the file-system type, the number of blocks in the file system and other key administrative information.
     • free space mgmt
       • It has information about the free blocks in the file system.
     • I-node
       • An array of data structures, one per file, telling all about the file.
     • root dir
     • files and directories

2. files

   • contiguous allocation
     • The simplest allocation scheme.  It stores each file as a contiguous run of disk blocks.
     • Advantages: 1.It is simple to implement because keeping track of where a file's blocks are is reduced to remembering two numbers: the disk address of the first block and the number of blocks in the file. 2.Read performance is excellent because the entire file can be read from the disk in a single operation. Only one seek is needed.
     • Disadvantages: Over the course of time, the disk becomes fragmented. When a file is removed, its blocks are naturally freed, leaving a run of free blocks on the disk. The disk is not compacted on the spot to squeeze out the hole, since that would involve copying all the blocks following the hole, potentially millions of blocks, which would take hours or even days with large disk.
     • To solve the fragmentation problem we can maintain a list of the holes. However, when a new file is to be created, it is necessary to know its final size in order to choose a hole of the correct size to place it in.
     • CD-ROM/DVDs
       • UDF
         • extents
   • linked list allocation
     • Store each file as a linked list of disk blocks. The first word of each block is used as a pointer to the next one. The rest of the block is for data.
     • Disadvantages: 1.Although reading a file sequentially is straightforward, random access is extremely slow. To get to block n, the operating system has to start at the beginning and read the n-1 blocks prior to it, one at a time. 2.The amount of data storage in a block is no longer a power of two because the pointer takes up a few bytes. While not fatal, having a peculiar size is less efficient because many programs read and write in blocks whose size is a power of two. With the firs few bytes of each block occupied by a pointer to the next block, reads of the full block size require acquiring and concatenating information from two disk blocks, which generates extra overhead due to the copying.
     • linked list using table in memory
       • FAT
         • Disadvantage: The entire table must be in memory all the time to make it work.
   • I-nodes
     • Lists the attributes and disk addresses of the file's blocks.
     • The big advantage of this scheme over linked files using an in-memory table is that the i-node need be in memory only when the corresponding file is open. Because the table for holding the linked list of all disk blocks is proportional in size to the disk itself. In contrast, the i-node scheme requires an array in memory whose size is proportional to the maximum number of files that may be open at once.

3. Directories

   • The directory entry provides the information needed to find the disk blocks. It can be the disk address of the entire file, the number of the first block or the number of the i-node.
   • attributes
     • fixed-size entries
     • i-nodes reference
     • file-name length
       • fixed word length
       • heap
   • search
     • linear
     • hash table
     • cache

4. shared files

   • DAG
     • Directed Acyclic Graph
   • disk address
     • If directories do contain disk addresses, then a copy of the disk addresses will have to be made in B's directory when the file is linked. If either B or C subsequently appends to the file, the new blocks will not be visible to the other user, thus defeating the purpose of sharing.
     • symbolic link
       • Disadvantages: 1- Overhead 2-File can have two or more paths. Programs that start at a given directory and find all the files in that directory and its sub-directories will locate a linked file multiple times. 
     • file data structure
       • The disk blocks are not listed in the directories, but in a little data structure associated with the file itself.
       • Disadvantage: i-node records the owner as one of them., with increasing the link count.  If the owner removes the file the other directory will point to null file or if the i-node is reassigned to another file, it will point to the wrong file. The system can see from the count in the i-node that the file is still in use, but there is no easy way for it to find all the directory entries for the file, in order to erase them. Pointers to the directories cannot be stored in the i-node because there can be an unlimited number of directories.