31 Implementation of File Systems

Mary Anitha Rajam

 

34.1 Introduction

 

A file is a collection of related information. Files are organized into a structure called the file-system. The file systems reside on secondary storage (disks). The file systems provide efficient and convenient access to the disk by allowing data to be stored, located and retrieved easily. In this module, we understand the different layers in a layered file system, the on-disk structures and the in-memory structures used for the implementation of file systems and issues related to the implementation of directories.

 

34.2 File-System structure

 

A file system is organized into many layers. The different layers of a file system are shown in Figure 34.1. The application programs written by users are shown in the top most layer. The users’ programs use the logical file system. The logical file system invokes different data structures and the file-organization module. The file-organization module uses the basic file system, which, in turn uses I/O control, which, in turn accesses the I/O devices. We now see the functionalities of each of these layers in the subsequent subsections.

Fig. 34.1 Layered File System (Source: [1])

 

34.2.1  I/O control level

 

This layer is placed just above the I/O devices. This level comprises of the device drivers and the interrupt handlers. The device drivers act as an interface between the devices and the operating system. They help to transfer information between the main memory and the disk. An example of input given to a device driver is – ‘retrieve block 123’. In response to this, the device driver has to send low-level hardware specific instructions to the disk controller. The disk controller assists in reading block 123 from the disk.

 

34.2.2  Basic file system

 

This layer issues generic commands to the device driver to read and write physical blocks on the disk. The input received from the I/O control layer is sent from this layer. Memory buffers and caches are maintained by the operating system in the main memory. The basic file system layer is responsible for managing the memory buffers and caches. Each memory buffer can hold contents equal to the size of a block. Each buffer holds the contents of a disk block. The contents that are read from the disk are copied to the buffers and can even be used later. The cache holds frequently used file-system metadata. This can be the contents of the file or attributes of the file such as the owner of the file, size of the file and so on. If the file is used frequently, the metadata can be used from the cache itself. It is not necessary to read from the disk each time.

 

34.2.3  File-organization module 

 

This layer uses the functionalities of the basic file system layer. This layer knows about files and their logical and physical blocks. The logical blocks are with respect to a particular file. The logical blocks are numbered from 0 to N for a particular file. Physical blocks do not match the logical numbers. Logical block i need not be kept in block number i in the physical memory. It can be kept in any physical disk block. Therefore, it is necessary to know the location of the location of the file in the disk (That is the locations of the disk blocks where the contents of the file are kept in the disk). Therefore, appropriate data structures are maintained by the file-organization module to  know the  mapping  between  the  logical block number and the physical bock number. The file-organization module also has a free-space manager, which tracks unallocated disk blocks.

 

34.2.4  Logical file system

 

This layer lies above the file-organization module. This layer manages the metadata information of a file. The metadata information includes all details about a file except the actual contents of the file, for example, the name of the file, the size of the file and so on. This layer also manages the directory structure. It maintains the file-structure via file-control blocks. A File-control block (FCB) (inode in UNIX) has information about a file – owner, size, permissions, time of access, location of file contents and so on.

 

34.2.5  Advantages of layered file system

 

Duplication of code is minimized. The code for I/O control and basic file-system layers can be used by multiple file systems. The layers above these two layers can be modified for different file systems. That is, each file system can then have its own logical file system and file-organization modules, while the I/O control and basic file-system layers being the same.

 

34.2.6. Disadvantages

 

Having a layered file system can introduce more operating-system overhead, resulting in decreased performance. The decision about how many layers to use, what each layer should do is a challenge.

 

Many file-systems are in use today – UNIX file system, FAT, FAT32, NTFS, ext3, ext4, Google. The FAT, FAT32 and NTFS are used in Windows operating systems. Ext3 and ext4 are used in Linux operating systems. Google has its own distributed file system called the Google File System (GFS).

 

34.3  File-System Implementation

 

In this section, we learn different data structures that used to assist in the implementation of file systems. There are several on-disk and in-memory structures used for the implementation of file systems. The on-disk structures are kept in the disks. The on-disk structures contain information about how to boot an OS stored in the disk, total number of disk blocks, number and location of free disk blocks, directory structure and individual files. The in-memory structures are kept in the main memory. The in-memory structures are helpful for file-system management, caching and so on.

 

34.3.1  On-Disk Structures

 

In this section, we understand the functionalities of different on-disk data structures.

 

34.3.1.1  Boot control block

 

Operating system is kept in the boot control block. If the disk has no operating system, this block is empty. In UNIX, the boot control block is called as a boot block. In NTFS, the boot control block is called as a partition boot sector.The boot control block is usually the first block of the volume where the file system is kept. If a partition of a disk has an operating system, information about how to boot.

 

34.3.1.2  Volume control block

 

This data structure contains details about a volume (partition). The information maintained in the volume control block are number of blocks in the partition, size of each block, number of free blocks in the partition, free-block pointers (addresses of free disk blocks) and so on. In UNIX the volume control block is called a superblock and is the block next to the boot block. In NTFS, these details are stored in the master file table.

 

34.3.1.3  Directory structure (for each file system)

 

The directory structure is used to organize files. In the directory structure, the names of files and associated information are kept. In UNIX, the directory structure includes file names and associated inode numbers. In NTFS, these details are stored in the master file table.

 

34.3.1.4  Per-file file control block (FCB)

 

For each and every file, information about that file is maintained in a file control block. The FCB has a unique identifier number to allow association with a directory entry. In UNIX, the per-file file control block is nothing but the inode. The inode has an inode number, which is the unique identifier. In NTFS, the details about the file is stored in the master file table.

 

34.3.2  In-Memory Structures

 

These are data structures that are maintained inside the main memory.

•  Mount table

– Information about each mounted volume is maintained in the mount table.

•  Directory-structure cache

– Holds directory information of recently accessed directories. If the same directory has to be accessed again, it is not necessary to read from the disk. The details can be taken from the directory-structure cache.

•  System-wide open-file table

– This data structure is common to all the processes present in the system. This contains a copy of the FCB of each open file.

•  Per-process open-file table

– This is a table that is available for each and every process. This per-process open-file table points to the appropriate entry in the system-wide open-file table.

•  Buffers

– These are buffers that are kept in the memory to hold the contents of disk blocks.

 

Each buffer can hold the contents of one disk block. When contents of a disk block are read from the disk, they are stored in these buffers kept in memory. If the contents of the same disk block are needed again, the contents are taken from the buffer and need not be read from the disk. Similarly, the contents present in the buffer may be modified and need not be written to the disk for each and every modification. It is enough to write the contents of the buffer to the disk when the buffer is to be used for some other disk block contents.

 

34.4 File Operations

 

We now see how the data structures that we learnt in the previous sections are used during file operations.

 

34.4.1 Create a new file 

 

The application program calls the logical file system and gives the name of the file to be created to the logical file system. The logical file system knows the name of the directory structures. It finds the name of the directory in which the file is to be created from the file name given by the application program. The logical file system allocates a new FCB. In the case of UNIX, a new inode is allocated. The system reads the appropriate parent directory into memory. It updates the directory with the new file name and FCB and writes the directory back to disk. Figure 34.2 shows a typical file control block. The FCB has information about the file like the owner of the file, file size, file permissions and so on.

Fig.34.2 A Typical File Control Block (Source: [1])

 

34.4.2 Open an Existing File

 

The open() call called by the application program passes a file name to the logical file system. The call first searches the system-wide open-file table to see if the file is already in use by another process. If it is, a per-process open-file table entry is created pointing to the existing system-wide open-file table entry. If file is not already open, the directory structure is searched for the given file name. There is a possibility that parts of the directory structure are cached in memory. If the directory structure is present in the cache, it is taken from the cache. Else, the directory structure is read from the disk.

 

Once the file is found, the FCB is copied into an entry in the system-wide open-file table in memory. The FCB entry also keeps track of the number of processes that have opened the file. An entry is made in the per-process open-file table. This entry points to the system-wide open-file table. The FCB entry also has information about where the next read/write should be done on the file (file offset), access mode in which the file is open. open() returns a pointer to the entry in the per-process file-system table. All file operations after the open() system call use this pointer. In UNIX this pointer is called the file descriptor (file handle in Windows).

 

34.4.3  Close a File

 

When a process closes a file, the per-process open-file table’s entry is removed. The count (count of the number of processes using the file) in the system-wide open-file table entry is decremented. When the count becomes zero, the updated metadata is copied to the directory structure in the disk and the system-wide open-file table entry is removed.

Fig.34.3 In-Memory File System Structures (Source: [1])

 

Figure 34.3 (a) shows that the open call accesses the directory structure in memory. If the directory structure is not cached in memory, it is read from the disk. The file control block is accessed using the directory structure. If a copy of the FCB is not present in the memory, it is read from the disk.

 

Figure 34.3 (b) shows how the read system call uses the in-memory data structures. The read uses the index returned by the open call to access the entry in the per-process open-file table. The entry in the system-wide open-file table is obtained using the pointer from the per-process open-file table. The file control block is accessed from the system-wide open-file table and the data blocks are accessed using the entries in the FCB.

 

34.5  Directory Implementation

 

This section explains two different ways in which a directory can be implemented. In the first method, a linear list of file names is maintained with pointers to the data blocks. This method is simple  to  program  but  time-consuming  to  execute.  To  create  a  new file,  the  directory  is searched to find if another file with a similar name exists. If no such file exists, a new entry is added to the end of the directory. To delete a file, the directory is searched for that file and the space allocated to it is released. To reuse this deleted entry, the entry is marked as unused by assigning it a special name or it is attached to a list of free directory entries or the last entry in the directory is copied to the freed location and the length of the directory is decreased. The entries can also be maintained as a linked list to reduce the time required for deletion. The disadvantage of a linear list is that finding a file requires linear search and this makes access slow.

 

To reduce this search time

  • Operating systems implement a software cache to store the most recently used directory information.
  • Maintaining a sorted list also allows a binary search and reduces the search time.

 

But maintaining a sorted list is difficult. When new entries are added, the new entries should be added to the appropriate position.

  • Using a hash data structure –name and returns a pointer to the file name in the linear list. This reduces the–    In addition to having a linear list for storing the directory entries, a hash data structure can also be used. The hash table takes a value computed from the file search time. But provision must be made for collisions, that is, it is to be ensured that two file names do not hash to the same location.

 

34.6 Summary

 

In this module, we learnt the functionalities of the different layers present in a layered file system. We also learnt the functionalities of the on-disk and in-memory data structures used for the implementation of file systems. We learnt the different methods of implementing a directory.

 

 

 

References

  1. Abraham Silberschatz, Peter B. Galvin, Greg Gagne, “Operating System Concepts”, Sixth Edition, John Wiley & Sons Inc., 2003.
  2. Andrew S. Tanenbaum, Herbert Bos, “Modern Operating Systems”, Fourth Edition, Pearson Education, 2014.
  3. Gary Nutt, “Operating Systems”, Third Edition, Pearson Education, 2009.