Transcript Document
Princess Nora University Faculty of Computer & Information Systems Computer science Department Operating Systems (CS 340 D) Dr. Abeer Mahmoud (Chapter-12) File System Implementation Chapter 12: File System Implementation 1. Allocation Methods 2. Free Space Management 3 Dr. Abeer Mahmoud OBJECTIVES: Introduction to file system structure. To discuss block allocation and free-block algorithms 4 Dr. Abeer Mahmoud File-System Structure 5 Dr. Abeer Mahmoud File systems File systems provide efficient and convenient access to the disk by allowing data to be stored, located, and retrieved easily. A file system poses two quite different design problems. 1. The first problem is defining how the file system should look to the user. This task involves defining a file and its attributes, the operations allowed on a file, and the directory structure for organizing files. 2. The second problem is creating algorithms and data structures to map the logical file system onto the physical secondary-storage devices File system organized into layers 6 Dr. Abeer Mahmoud File-System Structure File structure Logical storage unit Collection of related information File system resides on secondary storage (disks) Provided user interface to storage, mapping logical to physical Provides efficient and convenient access to disk by allowing data to be stored, located retrieved easily File control block–storage structure consisting of information about a file Device driver controls the physical device File system organized into layers 7 Dr. Abeer Mahmoud Layered File System Logical file system manages metadata information Translates file name into file number, file handle, location by maintaining file control blocks Directory management, Protection Layering useful for reducing complexity and redundancy, understands files, logical address, and physical blocks Translates logical block # to physical block # Manages free space, disk allocation needs only to issue generic commands to the appropriate device driver to read and write physical blocks on the disk. Each physical block is identified by its numeric disk address (for example, drive 1, cylinder 73, track 2, sector 10). This layer also manages the memory buffers and caches The I/O control level consists of device drivers and interrupt handlers to transfer information between the main memory and the disk system. controls the physical device 8 Dr. Abeer Mahmoud File-System Implementation We have system calls at the API level, but how do we implement their functions? On-disk and in-memory structures Boot control block: contains info needed by system to boot OS from that volume Volume control block (superblock, master file table) contains volume details Total # of blocks, # of free blocks, block size, free block pointers or array Directory structure organizes the files File Control Block (FCB) contains many details about the file number, permissions, size, dates 9 Dr. Abeer Mahmoud Virtual File Systems Virtual File Systems (VFS) on Unix 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 o o Separates file-system generic operations from implementation details Implementation can be one of many file systems types, or network file system o 10 Dr. Abeer Mahmoud Schematic View of Virtual File System 11 Dr. Abeer Mahmoud Directory Implementation Linear list of file names with pointer to the data blocks Simple to program Time-consuming to execute Linear search time Could keep ordered alphabetically via linked list Hash Table–linear list with hash data structure 12 Decreases directory search time Collisions–situations where two file names hash to the same location Dr. Abeer Mahmoud Allocation Methods 13 Dr. Abeer Mahmoud Allocation Methods An allocation method refers to how disk blocks are allocated for files: 1. Contiguous allocation 2. Linked allocation 3. Indexed allocation 14 Dr. Abeer Mahmoud 1-Contiguous Allocation 15 Dr. Abeer Mahmoud Contiguous Allocation Each file occupies a set of contiguous blocks on the disk Simple – only starting location (block #) and length (number of blocks) are required The directory entry for each file indicates the address of the starting block and the length of the area allocated for this file ------------------------------------------------------------ Random access Wasteful of space (dynamic storage-allocation problem) External fragmentation Files cannot grow 16 Dr. Abeer Mahmoud Contiguous Allocation of Disk Space 17 Dr. Abeer Mahmoud Extent-Based Systems Many newer file systems (I.e. 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 18 Extents are allocated for file allocation A file consists of one or more extents. Dr. Abeer Mahmoud 2-Linked Allocation 19 Dr. Abeer Mahmoud Linked Allocation Each file is a linked list of disk blocks: blocks may be scattered anywhere on the disk. block = pointer Simple – need only starting address Free-space management system – no waste of space No random access a space is required for the pointers. 20 Dr. Abeer Mahmoud Linked Allocation 21 Dr. Abeer Mahmoud Linked Allocation 22 Dr. Abeer Mahmoud 3-Indexed Allocation 23 Dr. Abeer Mahmoud Indexed Allocation Method Each file has its own index block(s) of pointers to its data blocks Logical view Need index table Random access Dynamic access without external fragmentation, but have overhead of index block 24 Dr. Abeer Mahmoud Example of Indexed Allocation 25 Dr. Abeer Mahmoud Free-Space Management 26 Dr. Abeer Mahmoud Free-Space Management File system maintains free-space list to track available blocks/clusters (Using term “block” for simplicity) Bit vector or bit map (nblocks) 27 Dr. Abeer Mahmoud Efficiency and Performance Efficiency dependent on: disk allocation and directory algorithms types of data kept in file’s directory entry Performance 28 disk cache – separate section of main memory for frequently used blocks free-behind and read-ahead – techniques to optimize sequential access improve PC performance by dedicating section of memory as virtual disk, or RAM disk. Dr. Abeer Mahmoud Thank you End of Chapter 12 29 Dr. Abeer Mahmoud