CS162 Operating Systems and Systems Programming Lecture 18 File Systems Naming and Directories April 7 2008 Prof Anthony D Joseph http inst eecs berkeley edu cs162 Review Magnetic Disk Cylinder all the Characteristic tracks under the head at a given point on all surface Head Read write data is a three stage process Track Sector Cylinder Platter Seek time position the head arm over the proper track into proper cylinder Rotational latency wait for the desired sector to rotate under the read write head Transfer time transfer a block of bits sector under the read write head Seek Rot Xfer Joseph CS162 UCB Spring 2008 Result 4 7 08 Queue Device Driver Hardware Controller Request Disk Latency Queueing Time Controller time Seek Time Rotation Time Xfer Software Time Media Time Lec 18 2 Review 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 4 7 08 Joseph CS162 UCB Spring 2008 Lec 18 3 Review 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 seeks Very large files must read many indirect blocks four I Os per block 4 7 08 Joseph CS162 UCB Spring 2008 Lec 18 4 Review 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 needed 4 7 08 Joseph CS162 UCB Spring 2008 Lec 18 5 Goals for Today File Systems Structure Naming Directories Caching in File Systems Note Some slides and or pictures in the following are adapted from slides 2005 Silberschatz Galvin and 4 7 08 Josephgenerated CS162 UCB Spring Lec 18 6 Gagne Many slides Gagne from2008 my lecture notes File Allocation for Cray 1 DEMOS disk group 1 3 2 1 3 3 1 3 4 Basic Segmentation Structure 1 3 5 1 3 6Each segment contiguous on disk 1 3 7 1 3 8 1 3 9 file header basesize 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 4 7 08 Joseph CS162 UCB Spring 2008 Lec 18 7 Large File Version of DEMOS basesize basesize file header indirect block group disk group 1 3 2 1 3 3 1 3 4 1 3 5 1 3 6 1 3 7 1 3 8 1 3 9 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 ptrs 1024 groups ptr 1000 blocks group 8K 80GB Discussion of DEMOS scheme Pros Fast sequential access Free areas merge simply Easy 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 4 7 08 Joseph CS162 UCB Spring 2008 Lec 18 8 How 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 4 7 08 Since seeks so expensive for performance this is a very good tradeoff Joseph CS162 UCB Spring 2008 Lec 18 9 Administrivia 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 and Structure CPU Scheduling Kernel and Address Spaces Address Translation Caching and TLBs Demand Paging I O Systems Filesystems Disk Management Naming and Directories Distributed Systems Email cs162 cory with conflicts Projects have a grading standard 4 7 08 Joseph CS162 UCB Spring 2008 Lec 18 10 UNIX BSD 4 2 Same as BSD 4 1 same file header and triply indirect blocks except incorporated ideas from DEMOS Uses bitmap allocation in place of freelist Attempt to allocate files contiguously 10 reserved disk space Skip sector positioning mentioned next slide Problem When create a file don t know how big it will become in UNIX most writes are by appending How much contiguous space do you allocate for a file In Demos power of 2 growth once it grows past 1MB allocate 2MB etc In BSD 4 2 just find some range of free blocks Put each new file at the front of different range To expand a file you first try successive blocks in bitmap then choose new range of blocks Also in BSD 4 2 store files from same directory near each other Fast File System FFS Allocation and placement policies for BSD 4 2 Joseph CS162 UCB Spring 2008 4 7 08 Lec 18 11 Attack of the Rotational Delay Problem 2 Missing blocks due to rotational delay Issue Read one
View Full Document
Unlocking...