MODERN OPERATING SYSTEMS Third Edition ANDREW S. TANENBAUM Chapter 4 File Systems Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Essential requirements for long-term information storage: • It must be possible to store a very large amount of information. • The information must survive the termination of the process using it. • Multiple processes must be able to access the information concurrently. File Systems (1) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Think of a disk as a linear sequence of fixed-size blocks and supporting reading and writing of blocks. Questions that quickly arise: • How do you find information? • How do you keep one user from reading another’s data? • How do you know which blocks are free? File Systems (2) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 4-1. Some typical file extensions. File Naming Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 4-2. Three kinds of files. (a) Byte sequence. (b) Record sequence. (c) Tree. File Structure Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 4-3. (a) An executable file. (b) An archive. File Types Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 4-4a. Some possible file attributes. File Attributes Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639The most common system calls relating to files: File Operations Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639 • Append • Seek • Get Attributes • Set Attributes • Rename • Create • Delete • Open • Close • Read • WriteFigure 4-5. A simple program to copy a file. Example Program Using File System Calls (1) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639 . . .Figure 4-5. A simple program to copy a file. Example Program Using File System Calls (2) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 4-6. A single-level directory system containing four files. Hierarchical Directory Systems (1) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 4-7. A hierarchical directory system. Hierarchical Directory Systems (2) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 4-8. A UNIX directory tree. Path Names Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639System calls for managing directories: Directory Operations Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639 • Readdir • Rename • Link • Uplink • Create • Delete • Opendir • ClosedirFigure 4-9. A possible file system layout. File System Layout Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 4-10. (a) Contiguous allocation of disk space for 7 files. (b) The state of the disk after files D and F have been removed. Contiguous Allocation Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 4-11. Storing a file as a linked list of disk blocks. Linked List Allocation Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 4-12. Linked list allocation using a file allocation table in main memory. Linked List Allocation Using a Table in Memory Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 4-13. An example i-node. I-nodes Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 4-14. (a) A simple directory containing fixed-size entries with the disk addresses and attributes in the directory entry. (b) A directory in which each entry just refers to an i-node. Implementing Directories (1) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 4-15. Two ways of handling long file names in a directory. (a) In-line. (b) In a heap. Implementing Directories (2) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 4-16. File system containing a shared file. Shared Files (1) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 4-17. (a) Situation prior to linking. (b) After the link is created. (c) After the original owner removes the file. Shared Files (2) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Operations required to remove a file in UNIX: • Remove the file from its directory. • Release the i-node to the pool of free i-nodes. • Return all the disk blocks to the pool of free disk blocks. Journaling File Systems Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 4-18. Position of the virtual file system. Virtual File Systems (1) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 4-19. A simplified view of the data structures and code used by the VFS and concrete file system to do a read. Virtual File Systems (2) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 4-20. Percentage of files smaller than a given size (in bytes). Disk Space Management Block Size (1) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 4-21. The solid curve (left-hand scale) gives the data rate of a disk. The dashed curve (right-hand scale) gives the disk space efficiency. All files are 4 KB. Disk Space Management Block Size (2) Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639Figure 4-22. (a) Storing the free list on a