techtud's picture
File System

Definataion: File is a Collection of logically related entities(records) or file is a collection of related information that is recorded  on a secondary storage.

File will have various attributes 

Attributes :

  1. Name 
  2. Type
  3. Size
  4. Location

File context:All the attributes of the file called as file context.

File context will be stored in FCB(file control block)

File  having  various   types:

  1. .doc
  2. .Txt
  3. .exe
  4. .obj
  5. .class
  6. .pdf etc 

Operations: various operations on  the file 

  1. create 
  2. open 
  3. write
  4. read
  5. append etc 

For the better classification of the files .Files will be stored in the directory

Directory structures:-

  1. Single level directory 
  2. Two level directory
  3. Multilevel/ tree directory 

Single level directory: 

  1. Implementation of this directory  structures is easy or simple .
  2. Two files cannot have same name .
  3. Searching time for the specific files will be more (if 1000000 files).

Two -Level directory:

In this separate directories for each user is maintained.

  • Path name:Due to two levels there is a path name for every file to locate that file.
  • Now,we can have same file name for different user.
  • Searching is efficient in this method



Multilevel /tree directory:

  1. Implementation  of this directory structure is difficult or complicated.
  2. The better classification of the files as per the criteria.
  3. Searching time for the specific files will be  less.
  4. If the same file exists in the two different directories ,if one file is updated then other file has to be updated accordingly otherwise there will be a inconsistency 
  5. Directory is maintained in the form of a tree.
  6. there is grouping capability.
  7. We have absolute or relative path name for a file.


Contributor's Info

Contiguous file allocation

Contiguous Allocation:
 This method stores each file as a contiguous block of data on the disk.
 Allocation is done using first fit or best fit.
 This method has minimal or no disk-head movement.
 Due to minimal seek time, the access time of a file and the I/O performance is greatly improved in this method.
 It allows random access.
 It can be used for both sequential and direct files.

 Finding space for a new file or a resized file.
 Determining size requirements.
 External fragmentation of the hard disk.

Image result for contiguous allocation in files in OS image

Contributor's Info

Linked allocation in files | Advantages and DIs-advantages

Linked Allocation:
 This method solves the problems associated with contiguous allocation.
 Here the blocks of a single file can be scattered anywhere on the disk.
 The reason because the entire file is implemented as a Linked List.
 Each file is a linked list of disk blocks.
 The directory maintained by the Operating System contains a pointer to the first and the last blocks of a file.
 Each block of a file contains a pointer to the next block after it in the list.
 For creating a new file, we need to just create a new entry in the directory and not to search for sufficient space as in contiguous.


Image result for linked file allocation image

 There's no external fragmentation since each request is for one block.


 This method is inefficient for direct files.  It works perfectly for Sequential access only, space needs to be allocated in block for pointers and error in pointer links can lead to Invalid read.

Contributor's Info

Indexed file allocation | Advantages and DIs-advantages

Indexed Allocation:
 In Linked Allocation the pointers along with the blocks were scattered across the disk and needed to be retrieved in order by visiting each block for accessing the file.
 To solve this problem Indexed Allocation is used.
 In indexed allocation method, all the pointers are gathered together into one location known as Index Block.
 Each file has its own index block which stores the addresses of disk space occupied by the file.

 Directory contains the addresses of index blocks of files.
 When a file is created initially, all pointers in the index block are set to null value.
 As new blocks are written, the pointers are modified accordingly.

Image result for indexed file allocation image

Advantage:  Indexed allocation supports direct access and does not suffer from any external fragmentation.
Disadvantage:  Indexed allocation suffers from the problem of wasted space.


Unix I node implementation: It is an extension of Indexed Node implementation













Contributor's Info

Created: Edited:
Disk space management

Free space management:

  1. Operating system maintains a Free disks spaces to keep track all the free disks block which are not used by any file
  2. To reuse the space released from deleting the files ,free space management is used .

there are two methods :

1-Bitmap or Bit vector

2-Free List Approach

Bitmap or Bit vector

  1. In the Bit map approach every disk block will be mapped with a binary bit.
  2.  The bit can take two values: 0 and 1: 0 indicates that the block is allocated and 1 indicates a free block.
  3. To map 20k disks blocks we need 20k bits .
  4. The given instance of disk blocks on the disk in Figure 1 (where green blocks are allocated) can be represented by a bitmap of 16 bits as: 000011100000011

Advantages –

  • It is easy to understand
  • Finding the first free block is efficient. It requires scanning the words (a group of 8 bits) in a bitmap for a non-zero word. (A 0-valued word has all bits 0). The first free block is then found by scanning for the first 1 bit in the non-zero word.
  • The block number can be calculated as:
  • (number of bits per word) *(number of 0-values words) + offset of bit first bit 1 in the non-zero word .
  • For the Figure-1, we scan the bitmap sequentially for the first non-zero word.
  • The first group of 8 bits (00001110) constitute a non-zero word since all bits are not 0. After the non-0 word is found, we look for the first 1 bit. This is the 5th bit of the non-zero word. So, offset = 5.
  • Therefore, the first free block number = 8*0+5 = 5.

Free list approach:

  1. In the free list approach some disks block are used just to store the free disks block addresses
  2. Number of disks blocks addresses possible to store the in a one disk block=(disk block size/disk block address).



Contributor's Info

First Come First Serve

First Come First Serve:

This algorithm performs requests in the same order asked by the system. Let's take an example where the queue has the following requests with cylinder numbers as follows:

98, 183, 37, 122, 14, 124, 65, 67

Assume the head is initially at cylinder 56. The head moves in the given order in the queue i.e., 56→98→183→...→67.

First Come First Serve

Contributor's Info

Shortest Seek Time First (SSTF)

Shortest Seek Time First (SSTF):

Here the position which is closest to the current head position is chosen first. Consider the previous example where disk queue looks like,

98, 183, 37, 122, 14, 124, 65, 67

Assume the head is initially at cylinder 56. The next closest cylinder to 56 is 65, and then the next nearest one is 67, then 3714, so on.

Shortest Seek Time First

Contributor's Info

SCAN Algorithm

SCAN algorithm:

This algorithm is also called the elevator algorithm because of it's behavior. Here, first the head moves in a direction (say backward) and covers all the requests in the path. Then it moves in the opposite direction and covers the remaining requests in the path. This behavior is similar to that of an elevator. Let's take the previous example,

98, 183, 37, 122, 14, 124, 65, 67

Assume the head is initially at cylinder 56. The head moves in backward direction and accesses 37 and 14. Then it goes in the opposite direction and accesses the cylinders as they come in the path.

SCAN algorithm

Contributor's Info



Contributor's Info

  • like SCAN but stops moving inwards (or outwards) when no more requests in that direction exist.
  •  The difference is that the disk arm in spite of going to the end of the disk goes only to the last request to be serviced in front of the head and then reverses its direction from there only.
  • Thus it prevents the extra delay which occurred due to unnecessary traversal to the end of the disk.

Compared to SCAN, LOOK saves going from 23 to 0 and then back.


Contributor's Info

  • As LOOK is similar to SCAN algorithm, in similar way, CLOOK is similar to CSCAN disk scheduling algorithm.
  • In CLOOK, the disk arm inspite of going to the end goes only to the last request to be serviced in front of the head and then from there goes to the other end’s last request.
  • Thus, it also prevents the extra delay which occurred due to unnecessary traversal to the end of the disk.

Head starts at: 50



Contributor's Info