DOC PREVIEW
CMU CS 15410 - Lecture

This preview shows page 1-2-3-21-22-23-42-43-44 out of 44 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 4415-410, S’04- 1 -File System (Internals)Mar. 31, 2004Dave EckhardtDave EckhardtBruce MaggsBruce MaggsL26_Filesystem15-410“...Does this look familiar?...”15-410, S’04- 1 -SynchronizationProject 3 statusProject 3 statusSeveral groups skipped Checkpoint 3 (the easiest one!)Not everybody took advantage of opportunity to planSeveral groups seem on track to finish earlySeveral groups dangerously close to the “90% problem”First 90% of the work takes the first 90% of the timeLast 10% of the work takes the second 90% of the timeWe want everybody to finish!We want everybody to finish!Project 3 is the core experience of the classCan't bury it and move on!15-410, S’04- 1 -SynchronizationProject 3 / Project 4 “hurdle” test suiteProject 3 / Project 4 “hurdle” test suiteReleased this weekTwo sectionsBasic tests, solidity testsAt P3 deadline, you will run the testsAt P3 deadline, you will run the testsGoal: pass ~80% of each sectionRegister to begin Project 4 (some P3 extensions)Not passing the hurdle?Not passing the hurdle?Extra week to work on P3Cannot submit P4, grade will be 0%15-410, S’04- 1 -SynchronizationTodayTodayChapter 12 (not: Log-structured, NFS)15-410, S’04- 1 -OutlineFile system code layers (abstract)File system code layers (abstract)Disk, memory structuresDisk, memory structuresUnix “VFS” layering indirectionUnix “VFS” layering indirectionDirectoriesDirectoriesBlock allocation strategies, free spaceBlock allocation strategies, free spaceCache tricksCache tricksRecovery, backupsRecovery, backups15-410, S’04- 1 -File System LayersDevice driversDevice driversread/write(disk, start-sector, count)Block I/OBlock I/Oread/write(partition, block) [cached]File I/OFile I/Oread/write (file, block)File systemFile systemmanage directories, free space15-410, S’04- 1 -File System LayersMulti-filesystem namespaceMulti-filesystem namespacePartitioning, names for devicesMountingUnifying multiple file system typesUFS, ext2fs, ext3fs, reiserfs, FAT, 9660, ...15-410, S’04- 1 -Shredding DisksSplit disk into Split disk into partitionspartitions/slices/minidisks/.../slices/minidisks/...–PC: 4 “partitions” – Windows, FreeBSD, Plan 9–Mac: “volumes” – OS 9, OS X, system vs. user dataOr: glue disks together into Or: glue disks together into volumesvolumes/logical disks/logical disksPartition may contain...Partition may contain...–Paging area●Indexed by in-memory structures●“random garbage” when OS shuts down–File system●Block allocation: file #  block list●Directory: name  file #15-410, S’04- 1 -Disk StructuresBoot area (first block/track/cylinder)Boot area (first block/track/cylinder)Interpreted by hardware bootstrap (“BIOS”)May include partition tableFile system control blockFile system control blockKey parameters: #blocks, metadata layoutUnix: “superblock”““File control block” (Unix: “inode”)File control block” (Unix: “inode”)ownership/permissionsdata location15-410, S’04- 1 -Memory StructuresIn-memory partition tablesIn-memory partition tablesSanity check file system I/O in correct partitionCached directory informationCached directory informationSystem-wide open-file tableSystem-wide open-file tableIn-memory file control blocksProcess open-file tablesProcess open-file tablesOpen mode (read/write/append/...)“Cursor” (read/write position)15-410, S’04- 1 -VFS layerGoalGoalAllow one machine to use multiple file system typesUnix FFSMS-DOS FATCD-ROM ISO9660Remote/distributed: NFS/AFSStandard system calls should work transparentlySolutionSolutionInsert a level of indirection!15-410, S’04- 1 -Single File Systemn = read(fd, buf, size)INT 54sys_read(fd, buf, len)rdblk(dev, N)sleep() wakeup()namei() iget() iput()startIDE() IDEintr()15-410, S’04- 1 -VFS “Virtualization”n = read(fd, buf, size)INT 54iget() iput()vfs_read()ufs_read() procfs_read()namei() procfs_domem()15-410, S’04- 1 -VFS layer – file system operationsstruct vfsops { char *name; int (*vfs_mount)(); int (*vfs_statfs)(); int (*vfs_vget)(); int (*vfs_unmount)(); ...}15-410, S’04- 1 -VFS layer – file operationsEach VFS provides an array of methodsEach VFS provides an array of methodsVOP_LOOKUP(vnode, new_vnode, name)VOP_CREATE(vnode, new_vnode, name, attributes)VOP_OPEN(vnode, mode, credentials, process)VOP_READ(vnode, uio, readwrite, credentials)Operating system provides fs-independent codeOperating system provides fs-independent codeValidating system call parametersMoving data from/to user memoryThread sleep/wakeupCaches (data blocks, name  inode mappings)15-410, S’04- 1 -DirectoriesExternal interfaceExternal interfacevnode2 = lookup(vnode1, name)Traditional Unix FFS directoriesTraditional Unix FFS directoriesList of (name,inode #) - not sorted!Names are variable-lengthLookup is linearHow long does it take to delete N files?Common alternative: hash-table directoriesCommon alternative: hash-table directories15-410, S’04- 1 -Allocation / MappingAllocation problemAllocation problemWhere do I put the next block of this file?Near the previous block?Mapping problemMapping problemWhere is block 32 of this file?Similar to virtual memoryMultiple large “address spaces” specific to each fileOnly one underlying “address space” of blocksSource address space may be sparse!15-410, S’04- 1 -Allocation – ContiguousApproachApproachFile location defined as (start, length)MotivationMotivationSequential disk accesses are cheapBookkeeping is easyIssuesIssuesDynamic storage allocation (fragmentation, compaction)Must pre-declare file size at creation15-410, S’04- 1 -Allocation – LinkedApproachApproachFile location defined as (start)Each disk block contains pointer to nextMotivationMotivationAvoid fragmentation problemsAllow file growthIssues?Issues?15-410, S’04- 1 -Allocation – LinkedIssuesIssues508-byte blocks don't match memory pagesIn general, one seek per block


View Full Document

CMU CS 15410 - Lecture

Download Lecture
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?