Chapter 11: File System ImplementationChapter 11: File System ImplementationObjectivesFile-System StructureFile System Structure - LayersStructure of a Layered File SystemA Typical File Control BlockSlide 8Layered File SystemsSome Standard File System Implementation TerminologySlide 11In the Unix World:In-Memory File System StructuresIn-Memory File System Structures OverviewIn-Memory File System Structures Creating the FileIn-Memory File System Structures Reading a fileIn-Memory File System Structures Closing the FilePartitions and Mounting (1 of 3)Partitions and Mounting (2 of 3)Partitions and Mounting (3 of 3)11.3 Directory ImplementationDirectory Implementation11.4 Allocation MethodsContiguous Allocation of Disk SpaceSlide 25Slide 26Extent-Based SystemsLinked Allocation of Disk SpaceSlide 29Linked AllocationLinked Allocation with File Allocation Table.File-Allocation TableIndexed Allocation of Disk SpaceSlide 34Example of Indexed AllocationStructure of the Index BlockIndexed Allocation – Mapping (Cont.)Slide 38Slide 39PerformancePerformance - 2End of Chapter 11.1Chapter 11: File System Chapter 11: File System ImplementationImplementation11.2/40Silberschatz, Galvin and Gagne ©2005Operating System Concepts Chapter 11: File System ImplementationChapter 11: File System ImplementationChapter 11.1File-System StructureFile-System Implementation Directory ImplementationAllocation MethodsChapter 11.2Free-Space Management RecoveryLog-Structured File System11.3/40Silberschatz, Galvin and Gagne ©2005Operating System ConceptsObjectivesObjectivesHere we are going to discuss secondary storage – the disk, which holds files permanently, if desired.There are many issues dealing w/ file storage and access.So we need to understand how files are structured (their organization), how they are accessed (sequentially, randomly), how disk space is allocated and freed up when no longer needed, and how to interface other parts of the operating system to secondary storage.Essentially, this is a chapter dealing with implementation.11.4/40Silberschatz, Galvin and Gagne ©2005Operating System ConceptsFile-System StructureFile-System StructureUnlike tapes and other storage devices, data on disk can be rewritten in place.And, unlike sequential storage media, such as a magnetic tape, a disk allows us to access any file and/or records in a file either Sequentially, orRandomly.Data TransferAs discussed, input and output to/from a disk is performed in blocks. This is simply a hardware constraint, although we have some control over this, as we shall discuss in more detail in Chapter 12.Block size can vary considerably from a very small block (book offers 32 bytes) to thousands of bytes (I have personally seem blocks of 28.000 bytes). But a disk must be organized, and typically (not always) has a file system that is used to provide such an organization to facilitate storage and retrieval.11.5/40Silberschatz, Galvin and Gagne ©2005Operating System ConceptsFile System Structure - LayersFile System Structure - LayersAs communications protocols, the file system is structured.Each ‘layer’ of the file system adds to the features of the lower levels, while abstracting other features... Layers typically start with very primitive operations and features.Lowest Level: I/O Control consists of device drivers and interrupt handlers.Device drivers are very low level routines consisting of very special commands facilitating data transfer between primary memory and (typically) a disk device or other storage device.Inputs to device drivers are high level, such as ‘retrieve block 123” but outputs are very specific instructions to the I/O Control Unit specifying which device to act on, what to do (read, write, etc.)These control units execute very low level instructions such as testing to see if the device is ready and such; timing, and more.11.6/40Silberschatz, Galvin and Gagne ©2005Operating System ConceptsStructure of a Layered File SystemStructure of a Layered File System Inputs to the device drivers are high level as statedGoing ‘upward,’ instructions from the basic file system might include a request to read some physical block by supplying desired items numeric disk address, such as drive 1, cylinder 73, track 2, sector 10. Of course, this begs the question, where does the basic file system ‘get’ that numeric disk address?The file organization module knows location of the file, the type of organization and allocation, and the location of the file’s storage blocks. This module can then translate (map) logical block addresses into physical block numbers, which is how the disk is organized, and pass this to the basic file system.Continuing upwards, given some kind of symbolic file name, such as junk.txt, the logical file system manages the directory structure that supplies info the file organization organization module needs for its mappings. :FS maintains the file structure via file control blocks, which have much file information: ownership, permissions, location, and more.11.7/40Silberschatz, Galvin and Gagne ©2005Operating System ConceptsA Typical File Control BlockA Typical File Control BlockIn the logical file system, a file control block (FCB) is a structure which maintains the the state of an open file. (WIKI)A full FCB is generally about 36 bytes long.The meanings in the different fields differ from one OS to another.Drawing below is from your book. Note the next slide:11.8/40Silberschatz, Galvin and Gagne ©2005Operating System ConceptsOffset Size Contents00 Byte Drive number — 0 for default, 1 for A:, 2 for B:,...01 8 bytes File name and file type — together these form a file-name09 3 bytes0C 20 bytesImplementation dependent — should be initialized to zero before the FCB is opened.20 1 byte Record number in the current section of the file — used when performing sequential access.21 3 bytes Record number to use when performing random access.Another format of a File Control BlockNote this is 36 bytes!11.9/40Silberschatz, Galvin and Gagne ©2005Operating System ConceptsLayered File SystemsLayered File SystemsThe nice thing about a layered file system is that other file systems on the same computing system can still use the same low-level modules, such as the basic file system code and the I/O control, since these are very low level,
View Full Document