中科大操作系统原理与实现课件11_FS Implementation1.pdf

《中科大操作系统原理与实现课件11_FS Implementation1.pdf》由会员分享，可在线阅读，更多相关《中科大操作系统原理与实现课件11_FS Implementation1.pdf（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.操作系统原理与设计第11章文件系统的实现1陈香兰中国科学技术大学计算机学院2009年09月01日.提纲File-System StructureFS ImplementationDirectory ImplementationAllocation MethodsFree-Space Management小结和作业.File-System Structure IIFile structureILogical storage unitICollection of related informationIFile system resides on secondary storage(disks)

2、IFile system organizationIHow the file system should look to the userIHow to map the logical file system onto the physicalsecondary-storage devicesIFile system organized into layersILayered File System.File-System Structure II.FS Implementation IIstructures and operations used to implement file syst

3、emoperation,OS-&FS-dependmentIon-disk structuresIin-memory structuresIon-disk structuresIboot control blockIto boot an OS from the partition(volume)Iif empty,no OS is contained on the partitionIvolume control blockIdirectory structureIper-file FCB.FS Implementation IIIin-memory informationIused for

4、both FS management and performence improvementvia cachingIdata are loaded at mount time and discarded at dismountIstructures include:Iin-memory mount tableIin-memory directory-structure cacheIsystem-wide open-file tableIper-process open-file table.In-Memory File System Structures.FCBIA Typical File

5、Control Blockfile permissionsfile dates(create,access,write)file owner,group,ACLfile sizefile data blocks or pointers to file data blocks.partitions and mountingIpartitionIraw(E.g.UNIX swap space&some database)VS.cookedIboot information,with its own formatIboot imageIboot loader unstanding multiple

6、FSes&OSesdual-bootIroot partition is mounted at boot timeIothers can be automatically mounted at boot or manuallymounted later.Virtual File SystemsIVirtual File Systems(VFS)provide an object-oriented way ofimplementing file systems.IVFS allows the same system call interface(the API)to beused for dif

7、ferent types of file systems.IThe API is to the VFS interface,rather than any specific typeof file system.ISchematic View of Virtual File System.Directory ImplementationILinear list of file names with pointer to the data blocks.Isimple to programItime-consuming to executeIHash Table linear list with

8、 hash data structure.Idecreases directory search timeIcollisions situations where two file names hash to the samelocationIFixed&variable size or chained-overflow hash table.Allocation MethodsIAn allocation method refers tohow disk blocks are allocated for filesso thatdisk space is utilized effective

9、ly&files can be accessed quickly1.Contiguous allocation2.Linked allocation3.Indexed allocation4.Combined.1.Contiguous Allocation IIEach file occupies a set of contiguous blocks on the diskISimple directory entry only needIstarting location(block#)I&length(number of blocks)IMapping from logical to ph

10、ysicalLogicalAddress/512=Q.RBlock to be accessed=Q+starting addressDisplacement into block=R.1.Contiguous Allocation II.1.Contiguous Allocation IIIIAdvantages:ISupport both random&sequential accessIStart block:b;Logical block number:iphysical block number:b+iIFast access speed,because of short head

11、movementIDisadvantages:IExternal fragmentationIWasteful of space(dynamic storage-allocation problem).IFiles cannot grow,orFile size must be known in advance.Internal fragmentation.Extent-Based SystemsIMany newer file systems(I.e.Veritas File System)use amodified contiguous allocation schemeIExtent-b

12、ased file systems allocate disk blocks in extentsIAn extent is a contiguous block of disksIExtents are allocated for file allocationIA file consists of one or more extents.2.Linked Allocation IIEach file is a linked list of disk blocks:blocks may bescattered anywhere on the disk.IDirectoryIFirst blo

13、ckILast blockITwo types1.Implicit2.Explicit1.Implicit.2.Linked Allocation IIIAllocate as needed,link togetherISimple need only starting address.2.Linked Allocation IIIIFree-space management system no waste of spaceIDisadvantage:INo random accessILink pointers need disk sapceIE.g.:512 per block,4 per

14、 pointer 0.78%ISolution:clustersdisk throughput But internal fragmentationIMapping512 1=511LogicalAddress/511=Q.RBlock to be accessed is the Qthblock in the linked chain ofblocks representing the file.Displacement into block=R+1.2.Linked Allocation IVIHow to reduce searching time?.File-Allocation Ta

15、ble(FAT)IIFAT:Explicit linked allocationDisk-space allocation used by MS-DOS and OS/2IA section of disk at the beginning of each partition is set asideto contain the tableIEach disk block,an entry,contains the index of the next blockin the fileILast block entry,end-of-fileIUnused,0IDirectory entry c

16、ontains the first block numberINow support random access,but still not very efficientIMay result in a significant disk head seeks:Cached FAT.File-Allocation Table(FAT)II.File-Allocation Table(FAT)IIIICompute FAT sizeDisk space:80GBBlock size:4KBTotalblocknumber:80 230/212=5 2224 222=2245 222 0,the f

17、irst(K+1)thwords first 1 bit has offset L,thenfirst free block#=?first free block number N=K 16+L.1.Bit vector IIIISimpleIMust be kept on diskBit map requires extra space,Example:block size=212bytesdisk size=230bytes(1 gigabyte)n=230/212=218bits(or 32K bytes)ISolution:IClusteringIEfficient to get th

18、e first free block or n consecutive freeblocks,if we can always store the vector in memory.IBUTCopy in memory and disk may differ.E.g.biti=1 in memory&biti=0 on diskISolution:Set biti=1 in memory.Allocate blockiSet biti=1 in disk.1.Bit vector IVINeed to protect:IPointer to free listIBit map.2.Linked

19、 Free Space List on Disk IIlink together all the free disk blocksIFirst free blockINext pointerINot efficientICannot get contiguous space easilyINo waste of space.2.Linked Free Space List on Disk II.3.GroupingITo store the addresses of n free blocks(a group)in the firstfree blockIFirst n-1 group mem

20、bers are actually freeILast one contain the next groupIAnd so onIE.g.:UNIX.4.CountingIAssume:ISeveral contiguous blocks may be allocated or freedsimultaneouslyIEach=first free block number&a counter(number of freeblocks)IShorter than linked list at most time,counter 1.小结File-System StructureFS ImplementationDirectory ImplementationAllocation MethodsFree-Space Management小结和作业.谢谢！