1Lecture 10File SystemsNovember 6, 2003Prof. Joe PasqualeDepartment of Computer Science and EngineeringUniversity of California, San Diego© 2003 by Joseph PasqualeCSE 120: Principles of Operating Systems2Before We Begin …Read Chapters 11-12• File Systems: Interface, Implementation3So Far, We Have Considered …Processes• Abstraction of a running program• Processing resourceVirtual Memory• Abstraction of physical short-term memory• Memory resourceNext• File system: long-term storage4Motivation for File SystemsLong-term storage is needed for• user data: text, graphics, images, audio, video• user programs• system programs (including kernel) and dataPersistent: remains “forever”Large: “unlimited” sizeSharing: controlled accessSecurity: protecting information5GoalsSupport multiple types of storage• disks (different types), remote disksSimple intuitive user interface• single name space, simple naming, access controlArchival storage• keep forever, including previous versionsHigh performance, high reliability, protection, security6File SystemA file system is a collection of files• access control, name space, persistent storageA file is a logical unit of storage• unstructured (e.g. array of bytes)• structured (e.g. records)7File NamingName space• space of possible names• flat: no structure• structured: name has components, organizedDistinguish between user names and system names• user: “user-friendly”, space managed by user• system: efficient for system, managed by system8Hierarchical Name SpacesMost file systems: hierarchical name spaces (user)• no size restrictions• intuitive for users to manageName space is organized as a tree• name has components, branches starting from root• actually, not strictly a tree: linksExample: UNIX “pathnames”• absolute: /a/b/c/d• relative: c/d relative to /a9A File has AttributesName (one or more)Type (recognized by system or users)Times: when created; last accessed; last modifiedSizes: current size; maximum sizeStructure: linear; sequence of records; indexed recordsAccess control (permissions)10File OperationsCreation: create, deletePrepare for Access: open, closeUse: read, write (append)Search: move to indexed location, find a keyed recordAttributes: get, set (e.g., permissions)Mutual exclusion: lock, unlockName management: rename11Typical Usagecreate (filename, permissions)openfile = open (filename, usage)amountread = read (openfile, buffer, howmuch)amountwritten = write (openfile, buffer, howmuch)close (openfile)remove (filename)12Memory Mapped FilesMap file into address spaceCan then use read/write memory operationsWorks best in a segmented virtual memoryProblems• 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?13Access ControlHow are files shared without giving away total control?Access control• who can access file• what operations are allowed• user interface must be simple and intuitiveExample: UNIX• rwx permissions for owner, group, and everyone14Accessing System ObjectsSystem objects need to be accessed by user• peripheral resources such as disks, networks• also OS objects: processes, memory segmentsUse file system interface• name space• access control15Storage Abstraction for File SystemHide complexity of addressingof underlying storage device• model storage as array ofrandomly accessible blocksFile system accesses thestorage using simple model• read (block_no)• write (block_no)block 0...block 1block 2block n-116File System StructureFile System MetadataFile MetadataData Blocks17File System MetadataInformation about the file systemSizes• files in use, free entries• data blocks in use, free entriesFree lists (or bitmaps)• file control blocks• data blocks18File Control BlockInformation about a fileName: may or may not be includedAttributes: type of file, size (+ max), permissionsReferences to data blocks: disk block map19Allocation of Storage Space for FilesContiguous blocks• single group of blocks that are contiguousExtents• multiple groups of contiguous blocksNon-contiguous blocks• blocks are randomly located20Data StructuresMap: data structure contains pointers to data blocks• start block pointer and sizeIndex• table of extents• table of blocksLinked lists• list of blocks• list of indexes21Block Map (UNIX)Array of pointers to data blocks13 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 blocksFor data block of 1024 bytes• pointer requires 4 bytes: n = 256• max: (10 + 256 + 2562 + 2563) * 1024 = 16 GB22Keeping Track of Free BlocksLinked 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-consuming23Implementing DirectoriesTable where each entry contains• name and attributes• name and pointer to file control structureUnix (name and pointer)• i-node number (2), file name (14)• Berkeley Unix uses a more complex scheme tosupport long names24Example of Parsing Names in UnixConsider the file pathname: /sports/tennis/agassibusinessentertainpoliticssciencesports1237256722basketballgolftennisvolleyball62211544agassichangsampras889246rootinodeinode22inode15inode88filedata25Hard Links vs. Symbolic LinksHard link• directory entry mapping name to inode number• may have multiple names mapping to same inodenumber• hard links must be all on same file systemSymbolic link• directory entry mapping name to pathname26File Systems Use Disks for StorageDisks are good for supporting file systems• persistent storage• random access• cheapRelatively slow because they are mechanical devicesMore about disks when we discuss I/O27How Disks WorkA disk is composed of platters and disk head assemblyAddressing is by sector, track, cylindercylinderplatterstrackdisk headassembly28File System PerformanceDisk 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 seekReduce accesses by• read multiple blocks
View Full Document
Unlocking...