1CMSC 412File System ImplementationAnnouncements• Reading– Chapter 12– Chapter 14 next time2Virtual File Systems• Virtual File Systems (VFS) provide anobject-oriented way of implementingfile systems.• VFS allows the same system callinterface (the API) to be used fordifferent types of file systems.• The API is to the VFS interface, ratherthan any specific type of file system.Virtual File System3File System Structure• Self-contained: all necessary meta-information is stored on disk along with theactual file system contents.– I.e. must be persistent in case the OS crashes.• Cached: accessing the disk is expensive, sosome information is cached in memory– Meta-data cache for file characteristics, andbuffer cache for file contents– Must be kept in-sync with on-disk copyFile Structure• File contents– Composed of one or more blocks, storedon disk. Block size usually relates todisk’s sector size.• File meta-data– Describes implementation and othercharacteristics of file, like size, last-modified time, location of contents, etc.– File control block (FCB) – meta-datastored on disk, though sometimes cachedin memory.4A Typical File Control BlockCaching Metadata5Allocation Methods• An allocation method refers to howdisk blocks are allocated for files:• Contiguous allocation• Linked allocation• Indexed allocationContiguous Allocation• Each file is a set of contiguous blocks on disk• Pros– Simple – only starting location (block #) andlength (number of blocks) are required.– Random access.• Cons– Wasteful of space (external fragmentation).– Files cannot grow without some headaches6Contiguous Allocation of DiskSpaceLinked Allocation• Each file is a linked list of disk blocks,blocks can be located anywhere– Directory points to first and last block of file– Each block contains a pointer to the next block• Pros:– Simple – need only starting address– No external fragmentation• Cons:– Best for sequential access data structures• requires sequential access whether you want to or not!– Reliability - one bad sector and all portions ofyour file downstream are lost7Linked AllocationModified Linked Allocation(FAT)• Section of disk contains a table– called the file allocate table (FAT)– used in MS-DOS• Directory entry contains the blocknumber of the first block in the file• Table entry contains the number ofthe next block in the file• Last block has a end-of-file value as atable entry8FAT ExampleExtents• An extent combines linked andcontiguous allocation:– Have a contiguous chunk of data, butthen also have a pointer to the nextchunk, if such a chunk is needed.– In other words, blocks can either belinked to, or adjacent to another block9Indexed Allocation• Bring all block pointers together intoan index block– Stored on disk– FCB points to the index block, whichpoints to the individual file blocksExample of IndexedAllocation10Indexed Allocation• Pros– Random access– No external fragmentation• Cons– Must go through index block on dynamicaccesses– May need very large index blocks tosupport large files; depends on the size offile blocks. Imposes per-file overhead.Indexed Allocation• How to make index block extensible?• Linked scheme:– maintain a linked list of indexed blocks• Multilevel index:– Index block can point to other index blocks(which point to index blocks ....), which point tofiles• Hybrid multi-level index (UNIX)– first n blocks are from a fixed index– next m blocks from an indirect index– next o blocks from a double indirect index11UNIX (4K per block)UNIX File Sizes• Assume 4096 byte block:– first 12 blocks (48 KB) from a fixed index– next 1024 blocks (4 MB) from an indirectindex– next 10242 blocks (4 GB) from a doubleindirect index– final 10243 blocks (4 TB) from a tripleindirect index12Performance Comparison• FAT4 simple, easy to implement4 faster to traverse than linked allocation– random access requires following links– files can’t have holes in them• Hybrid indirect4 fast access to any part of the file4 files can have holes in them– more complexFree Space Management• How do we find a disk block toallocate?• Bit Vectors– array of bits (one per block) thatindicates if a block is free– compact so can keep in memory• 100 GB disk, 4K blocks -> 6MB per disk(0.003%)– easy to find long runs of free blocks13Linked List• Each disk block contains the pointer tothe next free block• Pointer to first free block is keep in aspecial location on diskLinked Free Space List on Disk14Run Length Encoding• Pointer to first free block is kept in aspecial location on disk• Each free block also includes a countof the number of consecutive blocksthat are free• Called counting in book– Similar to extents for allocated filesImplementing Directories• Linear List– array of names for files– must search entire list to find or allocate afilename– sorting can improve search performance, butadds complexity• Hash table– use hash function to find filenames in directory– needs a good hash function– need to resolve collisions– must keep table small and expand on demandsince many directories are mostly empty15DOS Directories• Root directory– immediately follows the FAT• Directory is a table of 32 byte entries– 8 byte file name, 3 byte filename extension– size of file, data and time stamp, startingcluster number of the file, file attribute codes– Fixed size and capacity• Subdirectory– This is just a file– Record of where the subdirectory is located isstored in the FATUnix Directories• Space for directories are allocated in unitscalled chunks– Size of a chunk is chosen so that each allocationcan be transferred to disk in a single operation– Chunks are broken into variable-length directoryentries to allow filenames of arbitrary length– No directory entry can span more than one chunk– Directory entry contains• pointer to inode (file data-structure)• size of entry• length of filename contained in entry (up to 255)• remainder of entry is variable length - contains filename16Inodes• File index node• Contains:– Pointers to blocks in a file (direct, singleindirect, double indirect, triple indirect)– Type and access mode– File’s owner– Number of references to file– Size of file– Number of physical blocksUnix directories - links• Each file has unique inode but it may havemultiple directory
View Full Document
Unlocking...