File System ImplementationPreludeSome short answers.Why is the UNIX file system organized the way it is?Should we measure performance at the disk level?Slide 6Conceptual levels todayFile System organization requirementsSingle File Access ConceptsSingle File Access Concepts (S12.2)Direct: Go straight to the physical blockDirect. Disk Parameters (Stallings 11A)Operating System needs toLogical view: Mounted File SystemFile System MountingFile System Implementation -PartitionsPartitionsAllocation SchemesAllocation of Disk Space p554-559Contiguous AllocationContiguous Allocation IssuesSlide 22External Fragmentation Solution: Linked allocationLinked AllocationLinked List AllocationSlide 26Linked List Allocation IssuesSlide 28#3. Indexed AllocationIndexed AllocationSlide 31Linked Indexed FilesMultilevel Indexed FileImplementing Files (4)DiscussionAnswersCS 241 Spring 2007System Programming 01/14/19 CS241 © 2007 LA,RHC and YZ, All Rights Reserved1File System ImplementationCS 241 Lecture 25S: Ch 12 pp562-569, 535-561Lawrence Angrave2PreludeHow do create a disk-based file system?Is the UNIX file system the only way to access permanent dataHow is storage allocated for file systems?Why is the UNIX file system organized the way it is?3Some short answers. How do create a disk-based file system?The data structures and access methods are mapped through abstraction layers to the hardwareIs the UNIX file system the only way to access permanent data?No. How is storage allocated for file systems?Indexed (and other) allocation algorithmsWhy is the UNIX file system organized the way it is?Efficient for typical usage patternsC- More detail required4Why is the UNIX file system organized the way it is?Most accesses are to small filesMost data is read/written to large filesShell files and Directories mean small files must be accessed fastOnce a file is read (or written) the rest of it is read (or written)There are more reads than writesNot all access patterns conform to this (e.g. Database)5Should we measure performance at the disk level?6Better… Investigate actual system performance7Conceptual levels todayFile system requirementsSingle file access conceptsDisk layout & block accessPartitionsAllocation schemes8File System organization requirementsLong-termSharableEfficient accessControlled accessStructuredFieldRecordFile – Collection of recordsDatabase9Single File Access ConceptsPile Sequential Indexed SequentialIndexedDirect or Hashed10Single File Access Concepts (S12.2)Pile – a log of data (usually self describing)Sequential – fixed format records. Keyed.UNIX is sequential, record is byte, key is offset.Common operation “Next”. lseek. Additions at end. Indexed Sequential. Key and data record. Find data with key. Add, Delete, Next.Indexed. Many fields are indexedDirect or Hashed. Data hashed to file address11Direct: Go straight to the physical block12Direct. Disk Parameters (Stallings 11A)Sector has k bytes (typical 32-4096 bytes)Track has s sectors (size 4-32 sectors)Surface = j tracks (size 75 to 500 tracks)Cylinder has t tracks (size 4-32 tracks) t is equivalent to the number of surfacesTotal storage = k * s * j * tPhysical Block Addr = sector + s*( surface+ cylinder * t)13Operating System needs to Read/write to physical block addressesPresent user with a coherent, abstract file systemWe need several layers of abstraction (next…)14Logical view: Mounted File SystemAllows # files on system to grow for everFile system must be mounted before it can be available to processes on the system: The OS is given the name of the device, and the location within the file structure at which to attach the files system (mount point)A file system is contained in a partition. A disk can have many partitions.15File System MountingOS verifies that the device contains a valid file systemOS notes in its directory structure that a file system is mounted at the specified mount point16File System Implementation -PartitionsA typical file system layout MBR – master boot record17PartitionsMultiple partitions on disk.Partition can contain file systemFile system within partition must be self-describingMust recover from errorsMust be mountable anywhereMust describe what sort of file system it contains18Allocation Schemes19Allocation of Disk Space p554-559Low level access methods depend upon the disk allocation scheme used to store file data ContiguousLinked listBlock or indexed20Contiguous Allocation21Contiguous Allocation IssuesAccess method suits sequential and direct accessDirectory table maps files into starting physical address and lengthEasy to recover in event of system crashFast, often requires no head movement and when it does, head only moves one track22Contiguous Allocation IssuesFile is allocated large contiguous chunksUser knows size of the fileExpanding the file requires copyingDynamic storage allocation - first fit, best fitExternal fragmentation occurs on diskUsers tend to overestimate space => internal fragmentation23External FragmentationSolution: Linked allocation24Linked Allocation25Linked List AllocationEach file is a linked list of chunksPointers in list are not accessible to userDirectory table maps files into head of list for a fileA node in the list can be a fixed size physical block or a contiguous collection of blocksEasy to use - no estimation of size necessary26Linked List AllocationCan grow in middle and at endsSpace efficient, little fragmentationSlow - defies the principle of locality. Need to read through linked list nodes sequentially to find record of interest blocksSuited for sequential access but not direct access27Linked List Allocation IssuesDisk space must be used to store pointers (if disk block is 512 bytes, and disk address requires 4 bytes, then the user sees blocks of 508 bytes)Not very reliable. System crashes can scramble files being updatedImportant variation on linked allocation method: `file-allocation table' (FAT) - OS/2 and MS-DOS28Linked List Allocation IssuesSummary: linked allocation solves the external fragmentation and size-declaration problems of contiguous allocation,However, it can't support efficient direct access29#3. Indexed Allocation30Indexed AllocationSolves external fragmentationSupports sequential, direct and indexed accessAccess requires at most one access to index block first. This can be cached in main memory31Indexed AllocationFile can be extended by rewriting a few
View Full Document