Sunday, 20 December 2020

OS Free Space Management: Bit Vector, Linked List, Grouping and Counting

 

v FREE SPACE MANAGEMENT:

 

o   Since disk space is limited we need to reuse the space from deleted files for new files if possible.

o   To keep track of free disk space the system maintains free space list. The free space list records all free disk blocks- those not allocated to some file or directory.

o   To create a file we search the free space list for the required amount of space and allocate that space to the new file. This space is then removed from the free space list.

o   When a file is deleted its disk space is added to free space list.  The free space list despite its name might not be implemented as a list.

 

1.     Bit Vector:

o   Frequently the free space list is implemented as a bit map or bit vector. Each block is represented by 1 bit.

 

o   If the block is free, the bit is 1; if the block is allocated, the bit is 0. For example consider a disk where disc blocks 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26 and 27 are free and the rest of the blocks are allocated.  The free space bit map would be:0011111001111110001100000011100000...

 

o   The main advantage of this approach is its relative simplicity and efficiency in finding the first free block or ‘n’ consecutive free blocks on the disk.

 

o   Many computers supply bit manipulation instructions that can be used effectively for that purpose.  For example,  the Intel family starting with 80386 and the Motorola family starting with 68020 have instructions that return the offset in a word of first bit with value 1.

 

2.    Linked List:

o   Another approach to free space management is to link together all the free disk blocks, keeping a pointer to the first free block in a special location on the disc and caching it in the memory.

 

o   This first block contains a pointer to the next free disk block and so on. However this scheme is not efficient; to traverse the list, we must read each block, which requires substantial IO time.

 

o   The FAT method incorporates free block accounting into the allocation data structure. No separate method is needed.

 

3.     Grouping:

o   A modification of the free-list approach is to store the address of ‘n’ free blocks in the first free block.

o   The first n-1 of these blocks are actually free. The last block contains the addresses of other ‘n’ free blocks and so on.

o   The importance of this implementation is that the addresses of a large number of free blocks can be found quickly unlike in the standard linked list approach.

 

4.     Counting:

o   Another approach is to take advantage of the fact that generally several contiguous blocks may be located or freed simultaneously particularly when space is allocated with the contiguous allocation algorithm or through clustering.

o   So rather than keeping a list of ‘n’ free disk addresses, we keep the addresses of the first free block and the number ‘n’ of free contagious blocks that follow the first block.

o   Each entry in the free space list then consists of a disc address and count.

o   Although each entry requires more space than would a simple disc address, the overall list will be shorter as long as the count is generally greater than 1.


OS File Allocation Methods: Contiguous, Linked and Indexed Allocation

 

v FILE ALLOCATION METHODS:

 

1.    Contiguous Allocation:

o   The contiguous allocation method requires each file to occupy a set of contiguous blocks on the disk.

 

o   Disk address defines a linear ordering on the disc. With this ordering assuming that only one job is accessing the disk assessing block b+1  after block ‘b’ normally requires no head movement.

 

o   When head movement is needed it is only one track.  So the number of disc seeks required for assessing contiguously allocated files is minimal as is seek time when seek is finally needed.

 

o   The IBM VM/CMS OS uses contiguous allocation because it provides such good performance.

 

o   Contiguous allocation of a file is defined by the disc address and length of the first block.

 

o   If the file is ‘n’ blocks long  and starts at location ‘b’,  then it occupies blocks b,b+1,b+2,...,b+n-1.

 

o   The directory entry for each file indicates the address of the starting block and length of the area allocated for this file.

Contiguous allocation

(Contiguous allocation of disk space)


o   Contiguous allocation has some problems however. One difficulty is finding a space for new file.

 

o   Simulations have shown that both first fit and a best fit are more efficient than worst fit in terms of both time and storage utilization.  Neither first fit nor best fit is clearly based in terms of storage utilization but first fit is generally faster.

 

o   The algorithms suffer from the problem of external fragmentation.  As files are allocated and deleted the free disk space is broken into little pieces.

 

o   External fragmentation exists whenever free space is broken into chunks. It becomes a problem when the largest contiguous chunk is insufficient for a request; storage is recommended into number of holes, no one of which is large enough to store the data.

 

o   Another problem with contiguous allocation is determining how much space is needed for a file.  When the file is created, the total amount of space it will need must be found and allocated.  If we allocate too little space to a file, we may find that the file cannot be extended.

 

o   Even if the total amount of space needed for a file is known in advance, pre-allocation maybe inefficient.  A file that grows slowly over a long period must be allocated a space for its final size even though much on that space may be induced for a long time. The file therefore has a large amount of internal fragmentation.

 

o   To minimize drawbacks some use a modified contiguous allocation scheme in which a contiguous chunk of space is allocated initially and then when that amount is not large enough another chunk of continuous space, an extent, is added to the initial allocation.


2.    Linked Allocation:

o   Linked allocation solves all problems of contiguous allocation. With linked allocation a file is a linked list of disc blocks, the disk blocks may be scattered anywhere on the disc.

 

o   The directory contains a pointer to the first and last blocks of the file.

 

o   Each block contains a pointer to the next block.  These pointers are not made available to the user.

 

o   To create a new file, we simply create a new entry in the directory.

 

o   With linked allocation, each directory entry has a pointer to the first disc block of the file.  This pointer is initialized to nil to signify an empty file. The size field is also set to 0.

 

o   Write to the file causes every block to be found by the free space management system and this new block is then written to and is linked to the end of the file.

 

o   To read a file, we simply read blocks by following the pointers from block to block. There is no external fragmentation with linked allocation and any free block on the free space list can be used to satisfy a request.

 

o   The size of a file does not need to be declared when that file is created.  A file can continue to grow as long as free blocks are available.

 

o   The major problem is that it can be used effectively only for sequential access files.

 

o   To find the ‘ith’ block of a file, we must start at the beginning of that file and follow the pointers until we get to the ‘ith’ block.

 

o   Each access to a pointer requires a disk read and sometimes a disk seek.  Consequently it is inefficient to support a direct access capability for a linked allocation files.

 

o   The usual solution to this problem is to collect blocks into multiples called clusters and allocate the clusters rather than blocks.  This method allows the logical to physical block mapping to remain simple but improve disk throughput and decreases the space needed for a block allocation and free list management.


o   Yet another problem of linked allocation is reliability.  Since the files are linked together by pointers scattered all over the disc consider what would happen if a pointer were lost or damaged.

 

o   Partial solutions are to use doubly linked list or to store the filename and relative block number in each block; however these schemes require even more overhead for each file.

 

o   An important variation on the linked allocation method is the use of file allocation table (FAT).  This simple but efficient method of disk space allocation is used by MS DOS and OS/2 operating systems.

 

o   A section of disc at the beginning of each partition is set aside to contain the table.  The table has one entry for each disk block and is indexed by block number.  The FAT is used much as is a linked list.  The directory entry contains the block number of the first block of the file.  The table entry indexed by that block number then contains the block number of the next block in the file.  This chain continues until the last block which has a special end of file value as the table entry.  Unused blocks are indicated by a 0 table value.


Linked allocation

(Linked allocation of disk space)


3.    Indexed Allocation:

o   Linked allocation solves the external fragmentation and size declaration problems of contiguous allocation.

 

o   However in the absence of a FAT, linked allocation cannot support efficient direct access since the pointers to the blocks are scattered with the blocks themselves all over the disk and need to be retrieved in order.

 

o   Indexed allocation solves this problem by bringing all the pointers together into one location:  the index block.


o   Each file has its own index block which is an array of disk block addresses. The ‘ith’ entry in the index block points to the ‘ith’ block of the file. The directory contains the addresses of the index block.


Indexed allocation

(Indexed allocation of disk space)


o   To read the ith block, we use the pointer in the ith index block entry to find and read the desired block.

 

o   When the file is created, all pointers in the index block are set to nil.  When the ith block is first written, a block is obtained from the free space manager, and its address is put in the ith index block entry.

 

o   Indexed allocation supports direct access without suffering from external fragmentation because any free block on the disk may satisfy a request for more space.

 

o   Indexed allocation does suffering from wasted space.  The pointer overhead of the index block is generally greater than the pointer overhead of linked allocation.

 

o   If the index block is too small, however it will not be able to hold enough pointers for a large file and a mechanism will have to be available to deal with this issue.




OS Directory Structure: Single Level, Two Level and Tree Structured Directories

 

v DIRECTORY STRUCTURE:

 

o   The file systems of computers can be extensive. Some systems store millions of files on terabytes of disc.  To manage all this data we need to organize them.  This organization is usually done in two parts.

 

o   First disks are split into one or more partition also known as ‘minidisks’ in the IBM world, for ‘volumes’ in the PC and Macintosh arenas.  Typically each disk on a system contains at least one partition which is a low level structure in which files and directories reside.

 

o   Sometimes partitions are also used to provide several separate areas within one disc each treated as a separate storage device whereas other system allows partitions to be larger than a disk to group disk into one logical structure.

 

o   Partitions can also store multiple OS allowing a system to boot and run more than one.

 

o   Second, each partition contains information about files within it.  This information is kept in entries in a device directory or volume table of contents.  The device directory records information such as name, location, size and type for all files on that partition.

 

o   The directory can be viewed as a symbol table that translates filenames into their directory entries.

Typical file system organization

(Typical file system organization)


o   When considering a particular directory structure, we need to keep in mind the operations that are to be performed on a directory:

 

1.    Search for a file:  we need to be able to search a directory structure to find the entry for a particular file.

2.    Create a file:  new files need to be created and added to the directory.

3.    Delete a file:  when a file is no longer needed we want to remove it from the directory.

4.    List a directory:  we need to be able to list the files in a directory and the contents of the directory entry for each file in the list.

5.    Rename a file:  because the name of a file represents its contents to its users, the name must be changeable when the contents or use of file changes.

6.    Traverse the file system: to access every directory and every file within a directory structure.

 

 

A] Single Level Directory Structure:

 

o   The simplest directory structure is the single level directory.

 

o   All files are contained in the same directory which is easy to support and understand.


Single level directory structure


o   A single level directory has significant limitations however, when the number of files increases or when the system has more than one user.

 

o   Since all files are in the same directory, they must have unique names. If two users call their data file ‘test’ then the unique name rule is violated.

 

o   The MS Dos OS allows only 11 character file names; UNIX allows 255 characters.


 

o   Even a single user on a single level directory may find it difficult to remember the names of all the files as the number of files increases.

 

o   It is not uncommon for a user to have hundreds of files on one computer system and an equal number of additional files on another system.  In such an environment, keeping track of so many files is a daunting task.

 

 B] Two Level Directory Structure:

 

o   A single level directory often leads to confusion of filenames between different users.

 

o   The standard solution is to create a separate directory for each user.

 

o   In two level directory structure, each user has her own user file directory (UFD).

 

o   Each UFD has a similar structure, but list only the files of a single user.

 

o   When a user job starts for a user logs in, the systems master file directory (MFD) is searched.

 

o   The MFD is indexed by username or account number. Different users may have files with the same name, as long as all the file names within each UFD are unique.

  

o   To create a file for a user, the OS searches only that user’s UFD to ascertain whether another file of that name exist.  To delete a file, the OS confines its search to the local UFD. Thus it cannot accidentally delete another user’s file that has the same name.

 

o   Although two level directory structure solve the name collision problem, it still has disadvantages.  This structure effectively isolates one user from another.  This isolation is an advantage when the users are completely independent but it is a disadvantage when the users want to co-operate on some task and to access one another’s file.

 

o   If access is to be permitted, one user must have the ability to name a file in another user’s directory.  To name a particular file uniquely in a two level directory, we must give both the username and the file name.


o   If two level directory can be thought of as a tree,   or at least an inverted tree of height 2.

 

o   The root of the tree is the MFD.  It's direct descendants are the UFD. The descendants of the UFDs are the files themselves.  The files are the leaves of the tree.

 

o   Specifying a username and a filename defines a path in the tree from the root to a leaf.  Thus, a username and a filename define a path name.  Every file in the system has a path name.  To name a file uniquely, a user must know the name of the file desired.

 

o   Every system has its own syntax for naming files in directories other than the user’s own. Additional syntax is needed to specify the partition of a file.

 

Two level directory structure


C] Tree Structured Directories:

 

o   MS DOS system for instance is structured as tree. A tree is the most common directory structure

 

o   The tree has a root directory.  Every file in the system has a unique path name.  A path name is the path from the root to all the subdirectories to a specified file.

 

o   A directory or subdirectory contains a set of files or subdirectories.

 

o   A directory is simply another file but it is treated in a special way.

 

o   All directories have the same internal format.

 

o   One bit in each directory entry define the entry as a file (0) or as a subdirectory (1).

 

o   Special system calls are used to create and delete directories.

 

o   In normal use each user has a current directory.  The current directory should contain most of the files that are of current interest to the user.

 

o   When the reference is made to a file, the current directory is searched.  If a file is needed that is not in the current directory, then the user must either specify a path name or change the current directory to the directory holding that file.

 

o   Path names can be of two types:  absolute path names are relative path names.

 

o   An absolute path name begins at the root and follows a path down to the specified file, giving the directory names on the path.

 

o   A relative path defines a path from the current directory.

 

o   An interesting policy decision in a tree structured directory is how to handle the deletion of a directory.  If the directory is empty its entry in its containing directory can simply be deleted.

 

o   However suppose the directory to be deleted is not empty but contains several files or subdirectories:  one of two approaches can be taken.  Some systems such as MS DOS will not delete a directory unless it is empty.  To delete a directory the user must first delete all the files in the directory.  If any subdirectories exist this procedure must be applied recursively so that they can be deleted also.  This approach may result in a substantial amount of work.

 

o   An alternative approach such as that taken by the Unix ‘rm’ command is to provide the option that when a request is made to delete directory all the directories files and subdirectories are also to be deleted.  Though this policy is easy but it is more dangerous because an entire directory structure may be removed with one command.

 

o   With a tree structured directory system users can access in addition to their files, the files of other users. For example user B can access files of user A by specifying their path names.

 

o   User B can specify either an absolute or relative path name.  Alternatively user B could change his current directory to be user A’s directory and access the files by their file names.


Tree Structured directory

(Tree structure directory)