Chapter 11 File System Implementation Chapter 11 File System Implementation Chapter 11 1 File System Structure File System Implementation Directory Implementation Allocation Methods Chapter 11 2 Free Space Management Recovery Log Structured File System Operating System Concepts 11 2 40 Silberschatz Galvin and Gagne 2005 Objectives Here 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 Operating System Concepts 11 3 40 Silberschatz Galvin and Gagne 2005 File System Structure Unlike 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 or Randomly Data Transfer As 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 Operating System Concepts 11 4 40 Silberschatz Galvin and Gagne 2005 File System Structure Layers As 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 Operating System Concepts 11 5 40 Silberschatz Galvin and Gagne 2005 Structure of a Layered File System Inputs to the device drivers are high level as stated Going 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 Operating System Concepts 11 6 40 Silberschatz Galvin and Gagne 2005 A Typical File Control Block In 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 Operating System Concepts 11 7 40 Silberschatz Galvin and Gagne 2005 Another format of a File Control Block Offset Size Contents 00 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 name 09 3 bytes 0C 20 bytes Implementation 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 Note this is 36 bytes Operating System Concepts 11 8 40 Silberschatz Galvin and Gagne 2005 Layered File Systems The 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 machine dependent and generally file system independent Important because most operating systems support one file system Other devices such as CD ROMS have a different kind of file systems using a different standard formats that CD ROM manufacturers subscribe to Same for jump drives etc Will see next chapter the disk structure is different All operating systems however have at least one disk based file system Unix uses its own the Unix File System UFS Operating System Concepts 11 9 40 Silberschatz Galvin and Gagne 2005 Some Standard File System Implementation Terminology We know applications use system calls for open close etc to access data in files Now we need to look into the various structures operations needed to implement all this There is a number of data structures and algorithms needed to implement a file system and these are very OS dependent But there is some common definitions that must be understood File system must as a starter contain data as to how to boot the operating system stored on disk its size in bytes number and location of blocks the directory structure and many supporting files not necessarily part of the kernel Consider the following Operating System Concepts 11 10 40 Silberschatz Galvin and Gagne 2005 Some Standard File System Implementation Terminology Boot Control Block per volume This block is physically normally the first block on a volume It contains information telling the system how to boot the operating system from this volume If not found on this volume this first block is typically empty Volume Control Block per volume describes the number of blocks size of the blocks free block count and free block pointers and free FCB count and FCB