File Systems ImplementationGoals for TodayFile System ImplementationFile Control BlockImplementing File OperationsSlide 6Other file operationsMultiple users of a fileFiles Open and ReadVirtual File SystemsSlide 11File System LayoutStoring FilesImplementing FilesContiguous AllocationLinked List AllocationSlide 17MS-DOS File SystemFAT DiscussionIndexed AllocationUFS - Unix File SystemUnix inodesImplementing DirectoriesSlide 24Managing file names: ExampleDirectory SearchShared FilesSharing Files: SolutionsHard vs Soft LinksSlide 30Managing Free Disk SpaceTracking free spaceDisk Space ManagementManaging Disk QuotasEfficiency and PerformanceFile System ConsistencyA changing problemInconsistent FS examplesCheck Directory SystemLog Structured File SystemsSlide 41FS PerformanceBlock Cache ReplacementOther ApproachesOther File Systems: LFS, NFS, and AFSAnnouncementsLog-Structured File SystemsLFS Basic IdeaLFS vs. UFSLFS CleaningDistributed File SystemsTransfer ModelNaming transparencyFile Sharing SemanticsCachingSlide 57Network File System (NFS)ExampleNFS Mount ProtocolNFS ProtocolNFS ImplementationNFS Layer StructureHow NFS works?Cache coherencyAndrew File System (AFS)AFS OverviewAFS DetailsAFS: Shared Name SpaceAFS: Operations and ConsistencyAFS ImplementationSummaryFile Systems Implementation2Goals for Today•Filesystem Implementation•Structure for –Storing files–Directories–Managing free space–Shared files–Links–Consistency–Journaling–Performance•Some Implementations–Log structured file system (LFS)–Distributed FS’s (NFS/AFS)3File System Implementation•How exactly are file systems implemented?•Comes down to: how do we represent–Volumes–Directories (link file names to file “structure”)–The list of blocks containing the data–Other information such as access control list or permissions, owner, time of access, etc?•And, can we be smart about layout?4File Control Block•FCB has all the information about the file–Linux systems call these i-node structures5Implementing File Operations•Create a file: –Find space in the file system, add directory entry.•Open file–System call specifying name of file. –system searches directory structure to find file. –System keeps current file position pointer to the location where next write/read occurs–System call returns file descriptor (a handle) to user process•Writing in a file:–System call specifying file descriptor and information to be written–Writes information at location pointed by the files current pointer •Reading a file:–System call specifying file descriptor and number of bytes to read (and possibly where in memory to stick contents).6Implementing File Operations•Repositioning within a file:–System call specifying file descriptor and new location of current pointer –(also called a file seek even though does not interact with disk)•Closing a file:–System call specifying file descriptor–Call removes current file position pointer and file descriptor associated with process and file•Deleting a file:–Search directory structure for named file, release associated file space and erase directory entry•Truncating a file:–Keep attributes the same, but reset file size to 0, and reclaim file space.7Other file operations•Most FS require an open() system call before using a file.•OS keeps an in-memory table of open files, so when a reading or writing is requested, they refer to entries in this table via a file descriptor.•On finishing with a file, a close() system call is necessary. (creating & deleting files typically works on closed files)•What happens when multiple files can open the file at the same time?8Multiple users of a file•OS typically keeps two levels of internal tables:•Per-process table–Information about the use of the file by the user (e.g. current file position pointer)•System wide table–Gets created by first process which opens the file–Location of file on disk–Access dates–File size–Count of how many processes have the file open (used for deletion)9Files Open and Read10Virtual File Systems•Virtual File Systems (VFS) provide an object-oriented way of implementing file systems.•VFS allows the same system call interface (the API) to be used for different types of file systems.•The API is to the VFS interface, rather than any specific type of file system.1112File System Layout•File System is stored on disks–Disk is divided into 1 or more partitions–Sector 0 of disk called Master Boot Record–End of MBR has partition table (start & end address of partitions)•First block of each partition has boot block–Loaded by MBR and executed on boot13Storing Files•Files can be allocated in different ways:•Contiguous allocation–All bytes together, in order•Linked Structure–Each block points to the next block•Indexed Structure–An index block contains pointer to many other blocks•Rhetorical Questions -- which is best?–For sequential access? Random access?–Large files? Small files? Mixed?14Implementing Files•Contiguous Allocation: allocate files contiguously on disk15Contiguous Allocation•Pros:–Simple: state required per file is start block and size–Performance: entire file can be read with one seek•Cons:–Fragmentation: external is bigger problem–Usability: user needs to know size of file•Used in CDROMs, DVDs16Linked List Allocation•Each file is stored as linked list of blocks–First word of each block points to next block–Rest of disk block is file data17Linked List Allocation•Pros:–No space lost to external fragmentation–Disk only needs to maintain first block of each file•Cons:–Random access is costly–Overheads of pointers18MS-DOS File System•Implement a linked list allocation using a table–Called File Allocation Table (FAT)–Take pointer away from blocks, store in this table–Can cache FAT in-memory19FAT Discussion•Pros:–Entire block is available for data–Random access is faster since entire FAT is in memory•Cons:–Entire FAT should be in memory•For 20 GB disk, 1 KB block size, FAT has 20 million entries•If 4 bytes used per entry  80 MB of main memory required for FS20Indexed Allocation•Index block contains pointers to each data block•Pros?–Space (max open files * size per I-node)•Cons?–what if file expands beyond I-node address space?21UFS - Unix File System22Unix inodes•If data blocks are 4K …–First 48K reachable from the