Chapter 11.3 File System ImplementationChapter 11.3 : File System ImplementationFree-Space ManagementBit Vector Approach – used for space allocationLinked List Approach used for AllocationImplementing the Bit-Mapped ApproachImplementation of Linked List and Similar SchemesLinked Free Space List on DiskRecoveryConsistency Checking – RecoverySlide 11Backup and RestoreSlide 13Log Structured File Systems – Motivation (1 of 2)Log Structured File Systems – Motivation (2 of 2)Recovery in Log-Structured File SystemsSlide 17Restoring ConsistencyPractical ConsiderationsEnd of Chapter 11.3Chapter 11.3 File System Implementation Chapter 11.3 File System Implementation11.2Silberschatz, Galvin and Gagne ©2005Operating System Concepts Chapter 11.3 : File System ImplementationChapter 11.3 : File System ImplementationChapter 11.1File-System StructureFile-System Implementation Directory ImplementationChapter 11.2Allocation MethodsChapter 11.3.Free-Space Management RecoveryLog-Structured File Systems11.3Silberschatz, Galvin and Gagne ©2005Operating System ConceptsFree-Space ManagementFree-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.11.4Silberschatz, Galvin and Gagne ©2005Operating System ConceptsBit Vector ApproachBit Vector Approach – used for space allocation – 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-1bit[i] =0  block[i] free1  block[i] occupiedDownside: 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!!A sample bit vector might appear as 0011110011111100110011 ….Very simple approach but very efficient in finding the first free block.Too, a number of instruction sets contain instructions for bit manipulation11.5Silberschatz, Galvin and Gagne ©2005Operating System ConceptsLinked List ApproachLinked List Approach used for Allocation 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 also cannot get contiguous space easily11.6Silberschatz, Galvin and Gagne ©2005Operating System ConceptsImplementingImplementing the Bit-Mapped Approach the Bit-Mapped ApproachClearly, we 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 – as we have mentioned.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 memory11.7Silberschatz, Galvin and Gagne ©2005Operating System Concepts ImplementationImplementation of of Linked ListLinked List and Similar and Similar SchemesSchemesFirst Block: Maintain pointer to first free 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 – we often ‘know’ 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 could contains a disk address and a count of blocks ‘starting’ at that spot – thus shortening the list considerably.Perhaps you can see problems with this. Consider the following:11.8Silberschatz, Galvin and Gagne ©2005Operating System ConceptsLinked Free Space List on DiskLinked Free Space List on DiskShows that address of first free block points to the disk area, where other blocks are linked from one to the next.I think this begs the question:Are we generating fragments when we keep track of available disk space this way?This takes us back to worst fit, best fit, first fit, etc….11.9Silberschatz, Galvin and Gagne ©2005Operating System ConceptsRecoveryRecoveryI cannot say enough about Recovery.It is absolutely essential in any non-trivial computing environment.Recover is oftentimes easy (but time consuming), andDisks do fail for any number of reasons – power losses, surges, bad 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!11.10Silberschatz, Galvin and Gagne ©2005Operating System ConceptsConsistency