操作系统Chapter12-OSFile-Management课件.ppt

《操作系统Chapter12-OSFile-Management课件.ppt》由会员分享，可在线阅读，更多相关《操作系统Chapter12-OSFile-Management课件.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 Directory structureChapter 1212.1 12.2 12.3 Directory Structure12.4 and Protection112.1 Introduction2What is a fileA named collection of related information that is recorded on secondary storage.Content types:DataNumeric,alphabetic,alphanumeric,binaryProgramsource programs,Object formsPropertiesLon

2、g-term existenceSharable between processesStructure3:Attributes(属性)Name:The symbolic in human-readable formIdentifier:to identify the the (Internal)Type:to support different types.Location:the location on the secondary storage device.Size:the current size(and/or its maximum size)Protection:who can d

3、o reading,writing,executing,and so on.Time,date,and user identification:This information may be kept for creation,last modification,and usage monitoring.Typically,the directory entry consists of the files name and its unique identifier.The identifier in turn locates the other.One of the is the locat

4、ion of file.4:Types6:Structure(结构)None-sequence of words,bytes(流式文件)Simple record structureLines,Fixed length,Variable lengthComplex StructuresFormatted documentRelocatable load fileCan be implemented by inserting appropriate control characters.Who decides:Operating system and ProgramConclusion:Too

5、few structures make programming inconvenient,whereas too many cause OS bloat and programmer confusion.7:Operations(操作)Create:to allocate the and allocate the directory entryRead/Write/Seek:to find the directory entry and keep a read/write pointer or seek to a new position.Delete:to find the director

6、y entry and release all and erase the directory entryTruncate:to find the directory entry and release some Open(F)to search the directory structure on disk for entry F,and copy the directory entry into the open-and allocate a.Close(F)to copy the directory entry in the open-to the directory structure

7、 on disk and free the 8:Other accessIndex fileMaster index index file (ISAM:Indexed Sequential-Access Method from IBM)10:Other access11Directory structureA Typical Organization13Directory structuresSingle-level directoryTwo-level directoryTree-structured directoryAcyclic graph directory15Directory s

8、tructure:Single-Level DirectoryA single directory for all users.Naming problemGrouping problem16Directory structure:Tree-Structured Directories18Directory structure:Tree-Structured DirectoriesAbsolute or relative path nameEfficient searchingGrouping Capability19Directory structure:Acyclic-graph dire

9、ctories2012.4 Types of accessReadWriteExecuteAppendDeleteListAccess control lists(访问列表)：1.Difficult to build such a list.2.Complicate space management21Concise Access control lists(精简访问列表）Mode of access:read,write,executeThree classes of users RWXa)owner access(创建者创建者)71 1 1 RWXb)group access(工作组工作组

10、)6 1 1 0 RWXc)public access（其他用户）（其他用户）1 1 0 0“Book DirectoryBoss 111Employees 110Readers 10022 Structure:Layered 24 Structure:Layered I/O control consists of device drivers and interrupt handlers to transfer information between the main memory and the disk system.Input:retrieve drive 1,cylinder 73,

11、track 2,sector 10Output:low-level,hardware-specific instructions that are used by the hardware controllerBasic issues generic commands to the appropriate device driver to read and write physical blocks on the diskInput:retrieve block 123Output:retrieve drive 1,cylinder 73,track 2,sector 1025 Structu

12、re:Layered The module knows about the files and their logical blocks,as well as physical blocks.To translate a files logical block addresses to its physical block addresses.Each files logical block addresses are numbered from 0(or 1)through N.Each files physical block addresses are different,are uni

13、que within a partition.Free-space manager:Tracks unallocated blocksAnd provides these blocks when requested.26 Implementation:OverviewTo open a fileTo pass a to the logical To search the directory for the given To read in the files FCBTo put the files FCB to the system-wide open-To add a new entry i

14、n the per-process open-,with a pointer to the entry in the system-wide open-table and some other fieldsTo return a pointer to the appropriate entry in the per-process table.(or)28 Implementation:Overview29Directory ImplementationLinear listTo reuse a directory entryTo mark the entry as used.To attac

15、h it to a list of free directory entries.To decrease the length of the directory.Discussion:Simple to program,time-consuming to executeThe searching is expensiveBinary searchTo keep it sorted listTo use B-tree31Directory ImplementationHash TableTo use a linear list to store the directory entries and

16、 to use a hash table to quickly find out the directory entry given a.No collisions allowed(Each hash entry has a single value)Use a hash function to map to a hash value.Hash function should be dynamically changed.Fastest.Collisions allowed(Each hash entry has a list of multiple values)Use a hash fun

17、ction to map to a hash value and use this value to index the hash table and then search the list to find out the directory entry.Faster.32ALLOCATION METHODSAn allocation method refers to how disk blocks are allocated for files:Contiguous allocationLinked allocationIndexed allocation33Allocation Meth

18、ods:Contiguous AllocationThe contiguous-allocation methods requires each occupy a set of contiguous blocks on the diskThe directory for a only its starting location(block#)and length(number of blocks)(See the next slide)Discussions:Supports both sequential access and direct access.Simple to implemen

19、tProblem:How to specify an initial size for a fileUnder estimating its sizeOver estimating its sizeExternal fragmentation(dynamic storage-allocation problem).34Allocation Methods:Contiguous Allocation35Allocation Methods:Contiguous AllocationExtent-based Extent-based allocate disk blocks in extents.

20、An extent is a contiguous block of disks.Extents are allocated for.A of one or more extents.Many newer (I.e.Veritas)use a modified contiguous allocation scheme.Contiguous allocation can be combined with other allocation methods.Contiguous allocation for small filesOther allocations for large files.3

21、6Allocation Methods:Linked AllocationWith linked allocation,Each a linked list of disk blocks;The disk blocks may be scattered anywhere on the disk.The directory contains a pointer to the first and last blocks of the file.(See the next slide)Disk blockAn example linked file(see the next slide)pointe

22、rblock =37Allocation Methods:Linked Allocation38Allocation Methods:Linked AllocationSimple need only starting addressFree-space management system no waste of space Problems:No random accessPointers waste space:to use clusters rather than sectors To improve usageTo speed upPoor reliabilityImagine the

23、 pointer is messed up.39Allocation Methods:Linked AllocationFAT FSFAT(Table)duplicatedSupports direct accessCachedPoor disk utilization40Allocation Methods:Linked Allocation41Allocation Methods:Indexed AllocationProblems:External fragmentation and size-declaration for contiguous allocationDirect acc

24、ess for linked allocationIndexed allocationBringing all the pointers together into one location:index block(See the next slide)Logical viewindex table42Allocation Methods:Indexed Allocation43Allocation Methods:Indexed AllocationNeed index blockAccess methods:sequential access and direct access.How l

25、arge should the index block be?Linked schemeMultilevel indexCombined scheme44Allocation Methods:Indexed AllocationLinked schemeFor a small file,one index blockFor a large file,more index blocks can be linked together.Multilevel index1-level index block:1024*4KB2-level index block:1024x1024*4KB3-leve

26、l index block:1024x1024*1024*4KB(similar to paging)45Allocation Methods:Indexed Allocationouter-indexindex tablefile46Allocation Methods:Indexed AllocationCombined scheme12 for direct pointers1 single-indirect block1 double-indirect block1 triple-indirect block47Allocation Methods:Indexed Allocation

27、48Allocation Methods:PerformanceTwo criteria:Storage utilization efficiencyData block access timeContiguous allocation:Good for known-size fileLinked allocation:Good for storage utilization Indexed allocation:Access time depends on index structure,block positionConclusion:Combining contiguous alloca

28、tion and linked allocation(Some OS)Combining contiguous allocation and index allocation(SUN)49FREE-SPACE MANAGEMENTBit vectorLinked ListsGroupingCounting50Free-Space Management:Bit vectorThe free-space list is implemented as a bit map or bit vector.Each block is represented by 1 bit.If the block is

29、free,the bit is 1;if the block is allocated,the bit is 0.An example 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 051Free-Space Management:Bit vectorDiscussion:Simple to implement Efficient to find the first free blockEasy to get contiguous filesBlock number calculation:(number

30、 of bits per word)*(number of 0-value words)+offset of first 1 bitBit map requires extra space.Example:block size=212 bytesdisk size=230 bytes(1 gigabyte)n=230/212=218 bits(or 32K bytes)52Free-Space Management:Linked ListsLinked list(free list)Cannot get contiguous space easilyNo waste of space53Fre

31、e-Space Management:OthersGrouping To linked blocks to store the addressesTo group n-1 addresses into an address blockTo use the last address in an address block to point to next address block.Easier to find a large number of free blocks.CountingEvery entry is a pair of(starting address,contiguous block number)rather than just a addressThe total list is smaller.54