Chapter 11 2 File System Implementation Chapter 11 File System Implementation Chapter 11 1 File System Structure File System Implementation Directory Implementation Allocation Methods Chapter 11 2 Free Space Management Recovery Log Structured File Systems Chapter 12 An Introduction Overview of Mass Storage Disk Magnetic Tapes Operating System Concepts 11 2 Silberschatz Galvin and Gagne 2005 Free Space Management We ve talked about file space structure and file space implementation Now how free space is managed What space is available how much and where are the free blocks are located In other words we need some kind of storage map Keeping track of free space requires a free space list Free space list is a list of unallocated disk blocks Free space list a list Some other kind of structure Let s consider a couple of alternative structures used to manage free disk Operating System Concepts 11 3 Silberschatz Galvin and Gagne 2005 Bit Vector Approach used for space allocation Bit vector used to represent n blocks is one approach Each block is represented by a singe bit 1 block is available 0 block is in use allocated 0 1 2 n 1 bit i 0 block i free 1 block i occupied A sample bit vector might appear as 0011110011111100110011 This is a very simple approach but very efficient in finding the first free block Too a number of instruction sets contain instructions for bit manipulation We can see also how hardware features drives software functionality Downside to be efficient in searching the bit map must be kept in primary memory For small disks there is not a problem but for larger disks say a 40GB disk with 1KB blocks a bit map of 5MB is needed Operating System Concepts 11 4 Silberschatz Galvin and Gagne 2005 Linked List Approach used for Allocation This approach links all free space together via a linked list All we really need in memory cached is a pointer to the first free block All blocks then contain a pointer to the next free block It is easy however to quickly see inefficiencies To allocate a lot of disk we must read each block This is an incredible amount of I O and is very inefficient from a performance perspective If only a small amount of storage is necessary as is usually the case the linked list approach to disk allocation may be reasonably efficient Very often only a single block is requested FAT approach uses this approach each entry in the FAT points to the next block With the linked list approach we cannot get contiguous space easily Operating System Concepts 11 5 Silberschatz Galvin and Gagne 2005 Implementing the Bit Mapped Approach Need to protect these structures very closely We can implement the bit mapped approach with a pointer to this free list Bit map itself should be kept on disk Must ensure that the copy in memory and disk do not differ Cannot allow for block i to have a situation where bit i 1 in memory and bit i 0 on disk Solution Set bit i 1 in disk Allocate block i Set bit i 1 in memory Operating System Concepts 11 6 Silberschatz Galvin and Gagne 2005 Implementation of Linked List and Similar Schemes First Block Maintain pointer to first block in memory preferably in cache simple to program time consuming to execute Each link points to next link Grouping Store addresses of the first n free blocks in the first free block where the first n 1 blocks are actually free but where the last block contains addresses of another n free blocks This greatly improves performance over the standard linked list Counting Know usually several contiguous blocks may be allocated freed at the same time particularly when space is allocated using a contiguous allocation scheme or via clustering If this is the case we can keep the address of the first free block and the number of free contiguous blocks that follow the first block As a result the free space list contains a disk address and a count of blocks starting at that spot thus shortening the list considerably Operating System Concepts 11 7 Silberschatz Galvin and Gagne 2005 Linked Free Space List on Disk Shows that address of first free block points to the disk area where other blocks are linked from one to the next Operating System Concepts 11 8 Silberschatz Galvin and Gagne 2005 Recovery I cannot say enough about Recovery It is absolutely essential in any non trivial computing environment It is easy and it does indeed happen that disks fail for any number of reasons power losses surges back sectors on disk dust weather and even malicious intent There is nothing more sacred in the world of computers than our data Programs can usually be reproduced people replaced but safeguarding our data and having it consistent is critical Backup and Recovery two topics are often not covered in detail in academic environments But rest assured in a production environment these activities and procedures constitute a daily activity and involve planning and established procedures I cannot emphasize these topics enough Operating System Concepts 11 9 Silberschatz Galvin and Gagne 2005 Consistency Checking Recovery During operations directory information is kept both in memory and on disk and it is usually more current in memory If the directory is kept in cache it is usually not written back to memory every time it is updated This would negate the performance gains of cache Systems can and do crash at the absolute worst times If When so files directories caches buffers can easily be left in a very inconsistent state Operating systems such as Unix and MS DOS provide systems programs to run consistency checks when needed These compare directory data with data blocks on disk and attempt to repair any inconsistencies these programs may find Operating System Concepts 11 10 Silberschatz Galvin and Gagne 2005 Consistency Checking Recovery The degree of success in running these system supplied programs is largely dependent upon the type of allocation contiguous linked indexed as well as free space management routines used to allocate disk Sometimes broken links can be repaired sometimes not Loss of directory entries in an indexed organization can be disastrous because the blocks are linked from one to the next If link is broken we have big trouble Interestingly Unix caches directory entries for reads but any writes that cause any kind of space allocation are done synchronously This simply means that the allocation is successfully completed before the write takes place Can still have a problem if crash occurs during this process too But we always try