CSE 120 Principles of Operating Systems Lecture 10 File Systems November 6 2003 Prof Joe Pasquale Department of Computer Science and Engineering University of California San Diego 2003 by Joseph Pasquale 1 Before We Begin Read Chapters 11 12 File Systems Interface Implementation 2 So Far We Have Considered Processes Abstraction of a running program Processing resource Virtual Memory Abstraction of physical short term memory Memory resource Next File system long term storage 3 Motivation for File Systems Long term storage is needed for user data text graphics images audio video user programs system programs including kernel and data Persistent remains forever Large unlimited size Sharing controlled access Security protecting information 4 Goals Support multiple types of storage disks different types remote disks Simple intuitive user interface single name space simple naming access control Archival storage keep forever including previous versions High performance high reliability protection security 5 File System A file system is a collection of files access control name space persistent storage A file is a logical unit of storage unstructured e g array of bytes structured e g records 6 File Naming Name space space of possible names flat no structure structured name has components organized Distinguish between user names and system names user user friendly space managed by user system efficient for system managed by system 7 Hierarchical Name Spaces Most file systems hierarchical name spaces user no size restrictions intuitive for users to manage Name space is organized as a tree name has components branches starting from root actually not strictly a tree links Example UNIX pathnames absolute a b c d relative c d relative to a 8 A File has Attributes Name one or more Type recognized by system or users Times when created last accessed last modified Sizes current size maximum size Structure linear sequence of records indexed records Access control permissions 9 File Operations Creation create delete Prepare for Access open close Use read write append Search move to indexed location find a keyed record Attributes get set e g permissions Mutual exclusion lock unlock Name management rename 10 Typical Usage create filename permissions openfile open filename usage amountread read openfile buffer howmuch amountwritten write openfile buffer howmuch close openfile remove filename 11 Memory Mapped Files Map file into address space Can then use read write memory operations Works best in a segmented virtual memory Problems What is the size of a file being written What if file is to be shared by multiple processes What if file exceeds size of address space 12 Access Control How are files shared without giving away total control Access control who can access file what operations are allowed user interface must be simple and intuitive Example UNIX rwx permissions for owner group and everyone 13 Accessing System Objects System objects need to be accessed by user peripheral resources such as disks networks also OS objects processes memory segments Use file system interface name space access control 14 Storage Abstraction for File System Hide complexity of addressing of underlying storage device model storage as array of randomly accessible blocks block 0 block 1 block 2 File system accesses the storage using simple model read block no block n 1 write block no 15 File System Structure File System Metadata File Metadata Data Blocks 16 File System Metadata Information about the file system Sizes files in use free entries data blocks in use free entries Free lists or bitmaps file control blocks data blocks 17 File Control Block Information about a file Name may or may not be included Attributes type of file size max permissions References to data blocks disk block map 18 Allocation of Storage Space for Files Contiguous blocks single group of blocks that are contiguous Extents multiple groups of contiguous blocks Non contiguous blocks blocks are randomly located 19 Data Structures Map data structure contains pointers to data blocks start block pointer and size Index table of extents table of blocks Linked lists list of blocks list of indexes 20 Block Map UNIX Array of pointers to data blocks 13 pointers 10 direct references 10 data blocks 1 singly indirect references n data blocks 1 doubly indirect references n2 data blocks 1 triply indirect references n3 data blocks For data block of 1024 bytes pointer requires 4 bytes n 256 max 10 256 2562 2563 1024 16 GB 21 Keeping Track of Free Blocks Linked list need 4 bytes per free block if free list is large can take up a lot of space e g 1 GB disk 1 KB blocks say 50 of disk is free free list contains 500K entries 2 MB Bit map 1 bit for every block e g 1 GB storage 1 KB blocks 1 Mbit 130KB if few free blocks search is time consuming 22 Implementing Directories Table where each entry contains name and attributes name and pointer to file control structure Unix name and pointer i node number 2 file name 14 Berkeley Unix uses a more complex scheme to support long names 23 Example of Parsing Names in Unix Consider the file pathname sports tennis agassi root inode inode 22 business 12 entertain 37 politics 25 science sports 67 22 inode 15 inode 88 basketball 62 golf 21 tennis 15 volleyball 44 agassi 88 chang 92 sampras 46 file data 24 Hard Links vs Symbolic Links Hard link directory entry mapping name to inode number may have multiple names mapping to same inode number hard links must be all on same file system Symbolic link directory entry mapping name to pathname 25 File Systems Use Disks for Storage Disks are good for supporting file systems persistent storage random access cheap Relatively slow because they are mechanical devices More about disks when we discuss I O 26 How Disks Work A disk is composed of platters and disk head assembly Addressing is by sector track cylinder track disk head assembly platters cylinder 27 File System Performance Disk accesses are expensive in time Metrics rotational latency and seek time Sample numbers Maxtor Drives 2003 Slow 5400 RPM 11 msec rev 13 msec avg seek Fast 15000 RPM 4 msec rev 3 4 msec avg seek Reduce accesses by read multiple blocks in one access read ahead maintain a cache block or buffer cache Cluster related blocks to reduce seek time 28 Block Cache An in memory cache of recently used blocks Upon read or write check if block is in cache if it is done if not in cache access disk place in cache Eventually cache will
View Full Document
Unlocking...