操作系統(tǒng)課件：06_file system

1、1File SystemsChapter 44.1 Files 4.2 Directories 4.3 File system implementation File System in Unix System V 4.4 File System Management and Optimization 4.5 Example file systems 2Long-term Information StorageMust store large amounts of dataInformation stored must survive the termination of the proces

2、s using itMultiple processes must be able to access the information concurrentlyDisk OperationsBlockFixed-size unit in disk storage and data transfer, eg. 512B4KBOperationsRead block kWrite block k34File NamingTypical file extensions.5File StructureThree kinds of filesbyte sequencerecord sequencetre

3、e6File Types(a) An executable file (b) An archiveRegular FilesASCII FilesBinary FilesDirectoriesCharacter Special FilesBlock Special Files7File AccessSequential accessread all bytes/records from the beginningcannot jump around, could rewind or back upconvenient when medium was mag tapeRandom accessb

4、ytes/records read in any orderessential for database systemsread can be move file marker (seek), then read or read and then move file marker8File AttributesPossible file attributes9File System CallsPrinciple Win32 API functions for file I/OSecond column gives nearest UNIX equivalentCopyfile Program

5、in Figure 4-510DirectoriesSingle-Level Directory SystemsA single level directory systemcontains 4 filesowned by 3 different people, A, B, and C11Two-level Directory SystemsLetters indicate owners of the directories and files12Hierarchical Directory SystemsA hierarchical directory system13A UNIX dire

6、ctory treePath NamesAbsolute path nameRelative path nameCurrent directory (working directory)Current directory: .Parent directory: .14Directory System CallsPrinciple Win32 API functions for directory managementSecond column gives nearest UNIX equivalent, when one existsVirtual File SystemsVirtual Fi

7、le Systems (VFS) provide an object-oriented way of implementing file systems.VFS allows the same system call interface (the API) to be used for different types of file systems.The API is to the VFS interface, rather than any specific type of file system.17File System ImplementationA possible file sy

8、stem layoutMaster Boot Record18Implementing FilesMain goals:SimplicityFast and flexible accessEfficient use of spaceContiguous AllocationAllocate files contiguously on diskContiguous AllocationPros:Simple: state required per file is start block and sizePerformance: entire file can be read with one s

9、eekCons:Fragmentation: external is bigger problemUsability: user needs to know size of fileUsed in CDROMs, DVDsLinked List AllocationEach file is stored as linked list of blocksFirst word of each block points to next blockRest of disk block is file dataLinked List AllocationPros:No space lost to ext

10、ernal fragmentationDisk only needs to maintain first block of each fileCons:Random access is costlyOverheads of pointers.MS-DOS file systemImplement a linked list allocation using a tableCalled File Allocation Table (FAT)Take pointer away from blocks, store in this table FAT DiscussionPros:Entire bl

11、ock is available for dataRandom access is faster than linked list.Cons:Many file seeks unless entire FAT is in memoryFor 20 GB disk, 1 KB block size, FAT has 20 million entriesIf 4 bytes used per entry 80 MB of main memory required for FSIndexed AllocationIndex block contains pointers to each data b

12、lockPros?Cons?UFS - Unix File SystemUnix inodesIf data blocks are 4K First 48K reachable from the inodeNext 4MB available from single-indirectNext 4GB available from double-indirectNext 4TB available through the triple-indirect blockAny block can be found with at most 3 disk accessesExercise 5.11Siz

13、e (in bytes)OwnerRelevant timeLink and block countspermissioninodeDirect pointer to beginning file blocksSingle indirect pointerdouble indirect pointertriple indirect pointerPointers to next file blocks128B68B12B48B (12 pointers) 12*8K=96Kbytes8K/4=2K pointers 2K*8K=16Mbytes8K/4=2K pointers8K/4=2K p

14、ointers2K*2K=4MDouble indirect blocks and 4M*8K=32GBytes29Implementing Directories (1)(a) A simple directoryfixed size entriesdisk addresses and attributes in directory entry(b) Directory in which each entry just refers to an i-node30Implementing Directories (2)Two ways of handling long file names i

15、n directory(a) In-line(b) In a heapDifferent LengthDirectory and File12345name1inodenameDirectory entry in /dirASize (in bytes)OwnerRelevant timeLink and block counts=1permissionDirect pointer to beginning file blocks(23567)“This is the text”inode 12345Block 2356732File System Architecture in UNIX S

16、ystem Vgetblk, brelse, bread, breada, bwriteBlock Cache Managementiget, iput, bmapnameialloc, freeialloc, ifreeLow Level File OperationsOpenCreatDupPipecloseLinkChdirChrootChownChmodeMknodLinkunlinkstatReadWriteLseekMountunmountChdirchownSystem Calls莫里斯.貝奇，UNIX操作系統(tǒng)設(shè)計(jì)Maurice J. Bach, Design of UNIX O

17、perating System33Block Cache in UNIXThe unique block cache in the systemBlock is identified by device_no and block_noFor one block on the disk, there is ONLY ONE in the bufferBlock status:Locked: used by one process;Valid: The data in the cache block is validDelayed Write: The data in the cache bloc

18、k is updated, and need to be written to the disk before reclaimReading/Writing: Kernel is reading or writing the cache blockWaiting: A process is waiting for this block34Data Structure of the Block CacheHash0Hash3Hash2Hash1Idle_list01726234255029285984535getblk algorithmInput: device_no, block_no;Ou

19、tput: Locked Blockwhile(1)if(block in the hash list)if(block is locked) sleep(block, unclocked); continue;Lock the block;Remove it from Idle_list;return(block);elseif(idle_list is empty) sleep(idle_list is not empty); continue;Remove one block from the idle_list;if(block is Delayed Wirite) Asynchron

20、ized Write; continue;Remove it form old hash list;Insert it to the new hash list;Lock the block; return(block);36Five Cases for getblkThe block is in the hash list, and it is NOT locked;The block is in the hash list, and it is locked;The block is NOT in the hash list, and the idle list is empty;The

21、block is NOT in the hash list, and a free block is allocated;The block is NOT in the hash list, and a Delayed Write block is allocated;37brelse AlgorithmInput Locked blockwakeup processes waiting for this block;wakeup processes waiting for idle_list empty;disable interrupt;if(block is Valid)put it t

22、o tail of idle_list;elseput it to head of idle_list;enable interrupt;Unlock the block;Block is organized by LRU;Valid block stays in the hash list as long as possible;Block can be in hash list AND idle list;Block in hash list and NOT in idle list is locked;Block is always in hash list until it is sw

23、itched to the other one.Race conditions: continue in the getblk algorithm38bread AlgorithmInput: device_no, block_noOutput: block with the valid data block=getblk(device_no, block_no);if(block is valid)return(block);Read block from disk;sleep(disk read);set block to valid;return block;Check the bloc

24、k cache at first39breada AlgorithmINPUT: block_no1 for immediate read;block_no2 for asynchronized read;Output: block1 for block_no1if(block_no1 is not in cache)block1=getblk(block_no1);Read block_no1 from disk;if(block_no2 is not in cache)block2=getblk(block_no2);if(the block2 is valid) brelse(block

25、2);else Read block_no2 from disk;if(block_no1 in the cache)bread(block1);return(block1);sleep(block 1 is valid);return block1;For block_no2, kernel only read it tothe cache, and release it for the otherprocesses.Questions:1.Why block2 can be valid?2.If the other process lock block2, how to release i

26、t?3. Why check the block_no1 in the cache again?40bwrite AlgorithmInput: blockif(block is delayed write) release the block to head of idle list;elseWrite the block to disk;if (synchronized I/O) sleep(I/O complete); brelse(block);For asynchronized I/O, the block is released by interrupt handler, so t

27、he interrupt is disabled in brelse algorithmDelayed Write:Write is delayed until the block cache is assigned to the other block;Block is released to the head of idle list by kernel after the write disk completed;41File System Architecturegetblk, brelse, bread, breada, bwriteBlock Cache Managementige

28、t, iput, bmapnameialloc, freeialloc, ifreeLow Level File OperationsOpenCreatDupPipecloseLinkChdirChrootChownChmodeMknodLinkunlinkstatReadWriteLseekMountunmountChdirchownSystem Calls42InodesIndex nodeControl structure that contains key information for a particular file43inode addressingBlock_no=(inod

29、e_no-1)/(inode number per block)+first block of inode listOffset=(inode_no-1) mod (inode number per block)* inode size)Boot BlockSuper BlockInode listData Blocks44iget AlgorithmInput: inode_noOutput: locked inodewhile(1)if(inode_no in inode cache) if(inode is locked) sleep(inode unlocked); continue;

30、if(inode in idle list) remove it from idle list;inode.ref+;return(inode);if(idle list is empty)return(ERROR);Get a inode from idle list;Set inode_no and file system;Remove inode form old hash list, and insert it to new hash list;bread(inode_no);Lock the inode;Initialize the inode;Return inode;inode

31、is unlocked between two system callsinode is insert to idle list while its ref=045iput AlgorithmInput: inodeIf(inode is unlocked) lock it;Inode.ref-;If(inode.ref=0)if(inode.conref=0)free();set file type to 0;ifree();if(inode is updated)write it to disk;release inode to idle list;Unlock the inode;464

32、7bmap AlgorithmInput: inode, offsetOutput: block_no, block_offet, block size, breada block noBlock size=1KB256 block pointer in one block10 direct blocks 10KB1 Single indirect256K1 Double indirect64MB1 Triple indirect16GB48.init49namei AlgorithmInput: pathnameOutput: Locked inodecur_inode=iget(root)

33、;while(pathname not finished)get next_path from pathname;check cur_inode (it is a directory?)read directory by bmap, bread, brelse; match next_path with directory;if (matched)get the inode_no of the matched one;iput(cur_inode); cur_inode=iget(inode_no);elsereturn(NO_SUCH_DIRECTORY);50Super BlockSize

34、 of file systemNumber of idle blocksNext block number of the idle block listSize of inode listInode list: the cache for inode51inode listIdle inode numbers8348Emptyindex0 18 19 20Idle inode numbers83Emptyindex0 18 19 20iallocreturn 48470EmptyindexIdle inode numbers471472535indexREMEMBER_INODEiallocr

35、eturn 47052inode listIdle inode numbers471472535indexREMEMBER_INODEIdle inode numbers471472499indexREMEMBER_INODEifree(499)Idle inode numbers471472499indexREMEMBER_INODEifree(601)53ialloc AlgorithmOutput: Locked inodeWhile(1)if(super block is locked)sleep(super block is free);continue;if(inode list

36、is empty)Lock the super block;Load inode in disk from REMEMBER_INODE until the inode list is full;unlock the super block;wakeup(super block is free);if(there is no idle inode) return(NULL);update REMEMBER_INODE;get inode_no from inode listinode=iget(inode_no);if(inode is not idle)write the inode to

37、disk;iput(inode_no);continue;initialize the inode;write the inode to disk;idle inode number-;return(inode);54ifree AlgorithmInput: inode_no;idle inode number+;if(super block is locked)return;if(inode list is full)if(inode_noREMEMBER_INODE)REMENBER_INODE=inode_no;elseset inode_no to inode list;55Free

38、 Block Structure4714721201001501064722012001202150Super BlockFree block list56alloc AlgorithmOutput: a free blockwhile(super block is locked)sleep(super block is free);block=one from free block list;if(block is last one)lock the super block;bread(block);copy the block to the free block list;brelse(b

39、lock);unlock super block;wakeup(super block is free);blkp=getblk(block);clear the blkp;number of free blocks-;return(blkp);57File System Architecturegetblk, brelse, bread, breada, bwriteBlock Cache Managementiget, iput, bmapnameialloc, freeialloc, ifreeLow Level File OperationsOpenCreatDupPipecloseL

40、inkChdirChrootChownChmodeMknodLinkunlinkstatReadWriteLseekMountunmountChdirchownSystem Calls58File OperationsCreateDeleteOpenCloseReadWrite59File Table Data Structurefd1=open(“/etc/passwd”, O_RDONLY);fd2=open(“l(fā)ocal”, O_WRONLY);fd3=open(“/etc/passwd”, O_RDWR);User FileDescriptorTable(in u Area)0fd2f

41、d121fd3Ref=1, RDRef=1, WRRef=1,RDWR GlobalFileTableRef=2(/etc/passwd)Ref=1(local) Inode table60File Table Data Structurefd1=open(“/etc/passwd”, O_RDONLY);fd2=open(“private”, O_RDONLY);Process 1 File Descriptor Table0fd2fd121fd3Ref=1, RDRef=1, RDRef=1, WRRef=1,RDWR Global File TableRef=3(/etc/passwd)

42、Ref=1(local) Ref=1(private)Inode tableProcess 2 File Descriptor Table0fd2fd121Ref=1,RD61Read and Write PointersIn normal files, there are read and write pointers in the Global File Tables.In dup(), two file descriptor share one global file entry and its pointers.Main()int i,j;char buf1512, buf2512;i

43、=open(“/etc/passwd”,O_RDONLY);j=dup(i);read(i,buf1,sizeof(buf);read(j,buf2,sizeof(buf);close(i);read(j,buf2,sizeof(buf);62dup() Data StructureUser FileDescriptorTable(in u Area)0ji21Ref=2, RDGlobalFileTableRef=2(/etc/passwd) Inode table63The UNIX V7 File System (1)A UNIX V7 directory entry64The UNIX

44、 V7 File System (2)A UNIX i-node65The UNIX V7 File System (3)The steps in looking up /usr/ast/mbox66Shared Files (1)File system containing a shared fileHard Link: at i-node levelSymbolic Link: Only record path name67Shared Files (2)(a) Situation prior to linking(b) After the link is created(c)After

45、the original owner removes the file68Disk Space Management (1)Dark line (left hand scale) gives data rate of a diskDotted line (right hand scale) gives disk space efficiencyAll files 2KBBlock size69Disk Space Management (2)(a) Storing the free list on a linked list(b) A bit map70Disk Space Managemen

46、t (3)(a) Almost-full block of pointers to free disk blocks in RAM- three blocks of pointers on disk(b) Result of freeing a 3-block file(c) Alternative strategy for handling 3 free blocks- shaded entries are pointers to free disk blocks71Disk QuotaQuotas for keeping track of each users disk use72File

47、 System Reliability (1)A file system to be dumpedsquares are directories, circles are filesshaded items, modified since last dumpeach directory & file labeled by i-node numberFile that hasnot changed73File System Reliability (2)Bit maps used by the logical dumping algorithm74File System Reliability (3)File system statesConsistent missing block 2: add it to free listDuplicate block 4 in free list: rebuild free listDuplicate block 5 in data list: copy block and add it to one fileConsistency Check at Block LevelFS PerformanceAccess to disk is