Example: bankruptcy

Chapter 11: File System Implementation

The image cannot be displayed. Your computer may not have enough memory to open the image, or the image may have been corrupted. Restart your computer, and then open the file again. If the red x still appears, you may have to delete the image and then insert it 11: File System Implementation ! !Silberschatz, Galvin and Gagne 2005! operating System Concepts! Chapter 11: File System Implementation ! File- System Structure" File- System Implementation " Directory Implementation " Allocation Methods" Free-Space Management " Efficiency and Performance" Recovery" Log-Structured File Systems" NFS" Example: WAFL File System " !

Operating System Concepts! 11.2! Silberschatz, Galvin and Gagne ©2005! Chapter 11: File System Implementation! File-System Structure" File-System Implementation "

Tags:

  Operating, System, Chapter, Implementation, Life, Operating systems, Chapter 11, File system implementation

Information

Domain:

Source:

Link to this page:

Please notify us if you found a problem with this document:

Other abuse

Transcription of Chapter 11: File System Implementation

1 The image cannot be displayed. Your computer may not have enough memory to open the image, or the image may have been corrupted. Restart your computer, and then open the file again. If the red x still appears, you may have to delete the image and then insert it 11: File System Implementation ! !Silberschatz, Galvin and Gagne 2005! operating System Concepts! Chapter 11: File System Implementation ! File- System Structure" File- System Implementation " Directory Implementation " Allocation Methods" Free-Space Management " Efficiency and Performance" Recovery" Log-Structured File Systems" NFS" Example: WAFL File System " !

2 Silberschatz, Galvin and Gagne 2005! operating System Concepts!Objectives! To describe the details of implementing local file systems and directory structures" To describe the Implementation of remote file systems" To discuss block allocation and free-block algorithms and trade-offs" !Silberschatz, Galvin and Gagne 2005! operating System Concepts!User program & Kernel interface in Linux!Note: This picture is excerpted from Write a Linux Hardware Device Driver, Andrew O Shauqhnessy, Unix world !Silberschatz, Galvin and Gagne 2005!

3 operating System Concepts!File- System Structure! File structure" Logical storage unit" Collection of related information" File System resides on secondary storage (disks or SSD)" File System organized into layers" File control block storage structure consisting of information about a file" !Silberschatz, Galvin and Gagne 2005! operating System Concepts!Layered File System ! !Silberschatz, Galvin and Gagne 2005! operating System Concepts!A Typical File Control Block! !Silberschatz, Galvin and Gagne 2005!

4 operating System Concepts!In-Memory File System Structures! !Silberschatz, Galvin and Gagne 2005! operating System Concepts!Virtual 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 ." Basic operations are open, close, read & write" !Silberschatz, Galvin and Gagne 2005! operating System Concepts!

5 Schematic View of Virtual File System ! !Silberschatz, Galvin and Gagne 2005! operating System Concepts!VFS & Device Driver interface!Note: This picture is excerpted from Write a Linux Hardware Device Driver, Andrew O Shauqhnessy, Unix world !Silberschatz, Galvin and Gagne 2005! operating System Concepts!VSF & Major number! principal interface between a device driver and Linux kernel "" !Silberschatz, Galvin and Gagne 2005! operating System Concepts!Directory Implementation ! Linear list of file names with pointer to the data blocks.

6 " simple to program" time-consuming to execute " Hash Table linear list with hash data structure." decreases directory search time" collisions situations where two file names hash to the same location" fixed size" !Silberschatz, Galvin and Gagne 2005! operating System Concepts!Allocation Methods! An allocation method refers to how disk blocks are allocated for files:" Contiguous allocation! Linked allocation! Indexed allocation! !Silberschatz, Galvin and Gagne 2005! operating System Concepts!Contiguous Allocation!

7 Each file occupies a set of contiguous blocks on the disk" Simple only starting location (block #) and length (number of blocks) are required " Random access " Wasteful of space (dynamic storage-allocation problem) " Files cannot grow" !Silberschatz, Galvin and Gagne 2005! operating System Concepts!Contiguous Allocation! Mapping from logical to physical"LA/512"Q"R"Block to be accessed = Q + starting address Displacement into block = R !Silberschatz, Galvin and Gagne 2005! operating System Concepts!Contiguous Allocation of Disk Space!

8 !Silberschatz, Galvin and Gagne 2005! operating System Concepts!Extent-Based Systems! Many newer file systems ( Veritas File System ) use a modified contiguous allocation scheme" Extent-based file systems allocate disk blocks in extents" An extent is a contiguous block of disks" Extents are allocated for file allocation" A file consists of one or more extents." !Silberschatz, Galvin and Gagne 2005! operating System Concepts!Linked Allocation! Each file is a linked list of disk blocks: blocks may be scattered anywhere on the disk.

9 "pointer"block =" !Silberschatz, Galvin and Gagne 2005! operating System Concepts!Linked Allocation (Cont.)! Simple need only starting address" Free-space management System no waste of space " No random access" Mapping"Block to be accessed is the Qth block in the linked chain of blocks representing the file."Displacement into block = R + 1"File-allocation table (FAT) disk-space allocation used by MS-DOS and OS/2."LA/511"Q"R" !Silberschatz, Galvin and Gagne 2005! operating System Concepts!Linked Allocation!

10 !Silberschatz, Galvin and Gagne 2005! operating System Concepts!File-Allocation Table! !Silberschatz, Galvin and Gagne 2005! operating System Concepts!Indexed Allocation! Brings all pointers together into the index block." Logical view."index table" !Silberschatz, Galvin and Gagne 2005! operating System Concepts!Example of Indexed Allocation! !Silberschatz, Galvin and Gagne 2005! operating System Concepts!Indexed Allocation (Cont.)! Need index table" Random access" Dynamic access without external fragmentation, but have overhead of index block.


Related search queries