Operating Systems Design & Construction
Operating Systems Design & Construction CMPSC 473
Popular in Course
Popular in ComputerScienence
verified elite notetaker
This 0 page Class Notes was uploaded by Isabel Eichmann on Sunday November 1, 2015. The Class Notes belongs to CMPSC 473 at Pennsylvania State University taught by Staff in Fall. Since its upload, it has received 29 views. For similar materials see /class/233061/cmpsc-473-pennsylvania-state-university in ComputerScienence at Pennsylvania State University.
Reviews for Operating Systems Design & Construction
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 11/01/15
4 Operating Systems CMPSC 473 File System Implementation April 1 2008 Lecture 19 Instructor Trent Jaeger Last Class File System Interface Today File System Implementation Disks as Secondary Store 39 What makes them convenient for storing les Rewrite in place Read modify in memory write back to original location Access any block sequentially or random Gotta move the head to get there See Chapter 12 File Control Block Logical le system s representation of a le stored on disk In UNIX called an Mode file permissions file dates create access write file owner group ACL file size file data blocks or pointers to file data blocks Structures That Implement a File System On disk structures Boot control block Info to boot the OS from the disk Typically the first block of the boot partition boot block Partition control block Info about a file system number of blocks fixed size Includes free block information superblock Directory Structure File Control Blocks Structures That Implement a File System In memory structures Partition table Current mounted partitions Directory structure Information on recently access directories System Wide open le table All the currently open files Per process open le table All this process s open files In memory structures for open syscall eagljggm mdl w oamhtlfbmom imam lambg 39 amaift m n 5 Perprocess V Open File all m DescripTor39 Memor Table Inode o ll bll SysTemwide Open File inode of DescripTor39 Table 0 Exercise 39 See how you can implement Create le remove le open Close read write etc for the UNIX le system In Memory File Structures To open and read a le Index is a le descriptor directory structure open file name memory Strucmre filecontrol block user space kernel memory secondary storage a m a CD 39E D data blocks read index l perprocess systemwide filecontrol block openfile table openfile table user space kernel memory secondary storage Partition Structures 39 Layout of a le system on a disk Raw no file system structure Eg swap space database boot Cooked a le system structure Eg directories Boot Partition Contains information to boot the system Image to be loaded at boot time 39 May boot more than one system How is this done Bootloader is booted rst GRUB The you choose the OS to boot Mount Table OS has an in memory table to store Each le system that has been mounted Where it is mounted The type of the le system Physical le system eg ext3 ntfs Some other attributes Eg Read only File System Layers application programs logical file system Virtual File System lfileorganization module Physical File System basic file system lO control Device Drivers i devices Virtual File System File systems have general and storage method dependent parts Virtual file system is specific to the OS File system generic operations Works with inodes FCB les directories superblocks partitions The stuff that we discussed Physical file system is specific to how secondary storage will be used to manage data Converts the objects above into blocks Virtual File System tile system interface VFS interface t t local le system local le system remote le system type 2 type 1 network File System Implementation 39 View the disk as a logical sequence of blocks Al ockisthesnn k ttu tofa ocadon 39 Issues How do you assign the blocks to les Given a le how do you nd its blocks EEEEEEEEEE 39 39 quot File Allocation Direct access of disks gives us exibility in implementing les Relate to memory management problem Choices Contiguous Non contiguous Linked Indexed Contiguous Allocation Allocate a sequence of contiguous blocks to a file Advantages Need to remember only starting location to access any block Good performance when reading successive blocks on disk Disadvantages File size has to be known a priori External fragmentation Linked List Allocation 39 Keep a pointer to rst block of a le The rst few bytes of each block point to the next block of this le 39 Advantages NO external fragmentation 39 Disadvantages Random access is slow Linked List Allocn Using an Index eg DOS In the prev scheme we needed to go to disk to chase pointers since memory cannot hold all the blocks Why not remove the pointers from the blocks and maintain the pointers separately Perhaps then all or most of the pointers can t in memory Allocation is still done using linked list However pointer chasing can be done entirely in memory Disk Blocks EElEE 39 Table of Pointers in memory Called FAT in DOS For each le you directly have a pointers to all its blocks However the number of pointers for a le can itself become Indexed Allocation eg UNIX large UNIX uses i nodes An i node contains File attributes time of creation permissions 10 direct pointers logical disk block ids 1 one level indirect pointer points to a disk block which in turn contains pointers 1 two level indirect pointer points to a disk block of pointers to disk blocks of pointers 1 three level indirect pointer points to a disk block of pointers to disk blocks of pointers to pointers of disk blocks 5 x85 x V32m 980 5 xm V32m 5 xm m xuo m5 xoom x 5 ME 98E E N 980 m5 V32m x v 0 m vmo 3 O s m5 V32m V IH C UO Tracking free blocks List of free blocks bit rnap used When you can store the entire bit map in memory linked list of free blocks each block contains ptrs to free blocks and last ptr points to another block of ptrs in UNIX Pointer to a free FAT entry which in turn points to another free entry etc in DOS Exercise Given that the FAT is in memory nd out how many disk accesses are needed to retrieve block X of a le from disk in DOS 39 Exercise Given that the i node for a le is in memory nd out how many disk access are needed to retrieve block X of this le from disk in UNIX Summary File System Implementation Structure Virtual File System File Allocation Methods 39 Next time More le systems