File System ImplementationAdministrativeContentsLinked List Allocation IssuesIndexed AllocationSlide 6Slide 7Linked Indexed FilesMultilevel Indexed FileThe UNIX V7 File System (2)Typical File Systems –circa 1990Free Space ManagementFree Space Management – Bit VectorFree Space Management – Linked ListFree Space Management – Linked List 2Free Space Management - indexingDirectoriesPowerPoint PresentationDirectories and InodesReminder: File ImplementationThe UNIX V7 File System (3)Implementing DirectoriesShared FilesShared Files (2)UNIX Files– Write semanticsSummaryCS 241 Spring 2007System Programming 01/14/19 CS241 © 2006 RHC and YZ, All Rights Reserved1File System ImplementationCS 241 Lecture 27S: Ch 12 pp562-569, 535-561Lawrence Angrave2AdministrativeLMP1Self AssessmentLquizSurvey3ContentsFile Representation and AllocationDirectory implementationFree SpaceShared FilesAccess LevelsProtection4Linked List Allocation IssuesSummary: linked allocation solves the external fragmentation and size-declaration problems of contiguous allocation,However, it can't support efficient direct access5Indexed Allocation6Indexed AllocationSolves external fragmentationSupports sequential, direct and indexed accessAccess requires at most one access to index block first. This can be cached in main memory7Indexed AllocationFile can be extended by rewriting a few blocks and index blockRequires extra space for index block, possible wasted spaceExtension to big files issues8Linked Indexed FilesLinkfu llindexblockstogetherusinglas tentry.9Multilevel Indexed FileMultiplelev els ofindex blocks10The UNIX V7 File System (2)A UNIX i-node11Typical File Systems –circa 1990Median file size for UNIX in was 1680 bytesMean was 10,845 bytesSimilar results for NT12Free Space Management13Free Space Management – Bit VectorA bit map is kept of free blocks Each bit in a vector represents one blockIf the block is free, the bit is zeroSimple to find n consecutive free blocksOverhead is bit map Example BSD file system14Free Space Management – Linked ListFree list –Keep a linked list of free blocks–Not very efficient because linked list needs traversal –Example system V R115Free Space Management – Linked List 2Linked list of contiguous blocks that are free The free list node consists of a pointer and the number of free blocks starting from that addressBlocks are joined together into larger blocks as necessary16Free Space Management - indexingLinked list of indicesA linked list of index blocks is kept Each index block contains addresses of free blocks and A pointer to the next index blockUse inode-like structure and triple indexingA large number of free blocks can be found quickly17Directories(a) A simple directoryfixed size entriesdisk addresses and attributes in directory entry(b) Directory in which each entry just refers to an i-node18/bin dev lib etc usr tmpdick erik jim ast bal.profile binDirectory Hierarchy19Directories and InodesInode list: each inode may point to a file20Reminder: File ImplementationAddress of Block 0Address of Block 1Address of Block 2Address of Block 3Address of Block 4Address of Block 5Address of Block 6 Address of Block 7 Address Indirect BlockAddress Double Indirect BlockAddress Triple Indirect BlockFile AttributesINODE NNOTE INODE 1 will be Root21The UNIX V7 File System (3)The steps in looking up /usr/ast/mbox22Implementing DirectoriesTwo ways of handling long file names in directory(a) In-line or (b) In a heap23Shared FilesFile system containing a shared file – Directories point to same Inode24Shared Files (2)(a) Situation prior to linking(b) After the link is created(c) After the original owner removes the file25UNIX Files– Write semanticswrites to file immediately visible to other users reading from filecan share current location into file through open file tablesNOTE: Networked Files do not have UNIX write semantics26SummaryAllocation of disk spaceFree space managementDirectory implementationFree SpaceShared
View Full Document