CS162 Operating Systems and Systems Programming Lecture 18 File Systems, Naming, and DirectoriesReview: Magnetic Disk CharacteristicReview: Multilevel Indexed Files (UNIX 4.1)Review: Example of Multilevel Indexed FilesReview: Multilevel Indexed Files (UNIX 4.1)Goals for TodayFile Allocation for Cray-1 DEMOSLarge File Version of DEMOSHow to keep DEMOS performing well?AdministriviaUNIX BSD 4.2Attack of the Rotational DelayHow do we actually access files?DirectoriesDirectory OrganizationDirectory StructureDirectory Structure (Con’t)Where are inodes stored?Slide 19BREAKIn-Memory File System StructuresFile System CachingFile System Caching (con’t)Slide 24SummaryCS162Operating Systems andSystems ProgrammingLecture 18File Systems, Naming, and DirectoriesApril 7, 2008Prof. Anthony D. Josephhttp://inst.eecs.berkeley.edu/~cs162Lec 18.24/7/08 Joseph CS162 ©UCB Spring 2008Review: Magnetic Disk Characteristic•Cylinder: all the tracks under the head at a given point on all surface•Read/write data is a three-stage process:–Seek time: position the head/arm over the proper track (into proper cylinder)–Rotational latency: wait for the desired sectorto rotate under the read/write head–Transfer time: transfer a block of bits (sector)under the read-write head•Disk Latency = Queueing Time + Controller time +Seek Time + Rotation Time + Xfer Time•Highest Bandwidth: –transfer large group of blocks sequentially from one trackSectorTrackCylinderHeadPlatterSoftwareQueue(Device Driver)HardwareController Media Time(Seek+Rot+Xfer)RequestResultLec 18.34/7/08 Joseph CS162 ©UCB Spring 2008Review: Multilevel Indexed Files (UNIX 4.1) •Multilevel Indexed Files: Like multilevel address translation (from UNIX 4.1 BSD)–Key idea: efficient for small files, but still allow big files•File hdr contains 13 pointers –Fixed size table, pointers not all equivalent–This header is called an “inode” in UNIX•File Header format:–First 10 pointers are to data blocks–Ptr 11 points to “indirect block” containing 256 block ptrs–Pointer 12 points to “doubly indirect block” containing 256 indirect block ptrs for total of 64K blocks–Pointer 13 points to a triply indirect block (16M blocks)Lec 18.44/7/08 Joseph CS162 ©UCB Spring 2008Review: Example of Multilevel Indexed Files•Sample file in multilevel indexed format:–How many accesses for block #23? (assume file header accessed on open)?»Two: One for indirect block, one for data–How about block #5?»One: One for data–Block #340?»Three: double indirect block, indirect block, and data•UNIX 4.1 Pros and cons–Pros: Simple (more or less)Files can easily expand (up to a point)Small files particularly cheap and easy–Cons: Lots of seeksVery large files must read many indirect blocks (four I/Os per block!)Lec 18.54/7/08 Joseph CS162 ©UCB Spring 2008Review: Multilevel Indexed Files (UNIX 4.1)•Basic technique places an upper limit on file size that is approximately 16Gbytes–Designers thought this was bigger than anything anyone would need. Much bigger than a disk at the time…–Fallacy: today, EOS producing 2TB of data per day•Pointers get filled in dynamically: need to allocate indirect block only when file grows > 10 blocks –On small files, no indirection neededLec 18.64/7/08 Joseph CS162 ©UCB Spring 2008Goals for Today•File Systems–Structure, Naming, Directories•Caching in File SystemsNote: Some slides and/or pictures in the following areadapted from slides ©2005 Silberschatz, Galvin, and Gagne Note: Some slides and/or pictures in the following areadapted from slides ©2005 Silberschatz, Galvin, and Gagne. Many slides generated from my lecture notes by Kubiatowicz.Lec 18.74/7/08 Joseph CS162 ©UCB Spring 2008File Allocation for Cray-1 DEMOS•DEMOS: File system structure similar to segmentation–Idea: reduce disk seeks by »using contiguous allocation in normal case»but allow flexibility to have non-contiguous allocation–Cray-1 had 12ns cycle time, so CPU:disk speed ratio about the same as today (a few million instructions per seek)•Header: table of base & size (10 “block group” pointers)–Each block chunk is a contiguous group of disk blocks–Sequential reads within a block chunk can proceed at high speed – similar to continuous allocation•How do you find an available block group? –Use freelist bitmap to find block of 0’s. basesizefile header1,3,21,3,31,3,41,3,51,3,61,3,71,3,81,3,9disk groupBasic Segmentation Structure: Each segment contiguous on diskLec 18.84/7/08 Joseph CS162 ©UCB Spring 2008Large File Version of DEMOS•What if need much bigger files?–If need more than 10 groups, set flag in header: BIGFILE»Each table entry now points to an indirect block group–Suppose 1000 blocks in a block group 80GB max file»Assuming 8KB blocks, 8byte entries(10 ptrs1024 groups/ptr1000 blocks/group)*8K =80GB•Discussion of DEMOS scheme–Pros: Fast sequential access, Free areas merge simplyEasy to find free block groups (when disk not full)–Cons: Disk full No long runs of blocks (fragmentation), so high overhead allocation/access –Full disk worst of 4.1BSD (lots of seeks) with worst of continuous allocation (lots of recompaction needed) file headerbasesize1,3,21,3,31,3,41,3,51,3,61,3,71,3,81,3,9disk groupbasesizeindirectblock groupLec 18.94/7/08 Joseph CS162 ©UCB Spring 2008How to keep DEMOS performing well?•In many systems, disks are always full–CS department growth: 300 GB to 1TB in a year»That’s 2GB/day! (Now at 65+50 TB!)–How to fix? Announce that disk space is getting low, so please delete files?»Don’t really work: people try to store their data faster–Sidebar: Perhaps we are getting out of this mode with new disks… However, let’s assume disks full for now•Solution:–Don’t let disks get completely full: reserve portion»Free count = # blocks free in bitmap»Scheme: Don’t allocate data if count < reserve–How much reserve do you need?»In practice, 10% seems like enough–Tradeoff: pay for more disk, get contiguous allocation»Since seeks so expensive for performance, this is a very good tradeoffLec 18.104/7/08 Joseph CS162 ©UCB Spring 2008Administrivia•Plan Ahead: this month will be difficult!!–Project deadlines every week•Project #3 design doc due today at 11:59pm•Midterm #2 is next Wednesday (April 16th)–6-7:30pm in 10 Evans–All material from projects 1-3, lectures #9 (2/25) to #19 (4/9)»OS History, Services,
View Full Document
Unlocking...