Chap 11 File-Systems 文件系统

Presentation on theme: "Chap 11 File-Systems 文件系统"— Presentation transcript:

1 Chap 11 File-Systems 文件系统
Applied Operating System Concepts

2 Applied Operating System Concepts
Contents内容 File Concept（文件概念） Logical File Access Methods（逻辑文件存取方法） Directory Structure （目录结构） Protection（保护） File-System Structure （文件系统结构） Physical File Allocation Methods（物理文件分配方法） Free-Space Management （自由空间管理） Efficiency and Performance（效率和性能） Recovery（恢复） Summary（总结） Applied Operating System Concepts

3 Applied Operating System Concepts
File Concepts（文件概念） Contiguous logical address space（相邻的逻辑地址空间） Types： （类型） Data（数据） Numeric（数字） Character（字符） Binary（二进制） Program（程序） A file is a named collection of related information that is recorded on secondary storage.(文件是存放在2级存储器上的 命名的相关信息的集合。） Applied Operating System Concepts

4 Applied Operating System Concepts
File Structure（文件结构） None - sequence of words， bytes（顺序的字和字节） Simple record structure（简单的记录结构） Lines （线性） Fixed length（固定长度） Variable length（可变长度） Complex Structures（复杂结构） Formatted document（规格化的文档） Relocatable load file（可重定位文件） Can simulate last two with first method by inserting appropriate control characters. （可以用第一个方法通过增加适当的控制字符来模拟后两种方法） Applied Operating System Concepts

5 File Attributes（文件属性）
Name – only information kept in human-readable form. （文件名：唯一的以人们可以理解的方式保存的信息） Type – needed for systems that support different types. （类型：需要可以支持多种类型的系统） Location – pointer to file location on device. （位置：指向文件在设备上的存储位置的指针） Size – current file size. （大小：当前文件的大小） Protection – controls who can do reading， writing， executing. （保护：控制对文件的读取，改写和执行的权限） Time， date， and user identification – data for protection， security， and usage monitoring.（时间，日期和用户身份：保护和安全需要的数据） Information about files are kept in the directory structure， which is maintained on the disk.（文件的信息保存在磁盘上的目录结构中） Applied Operating System Concepts

6 File Operations（文件操作）
Create（创建） Write（改写） Read（读取） reposition within file – file seek（重定位文件，文件搜索） Delete（删除） Truncate（截去） open（Fi） – search the directory structure on disk for entry Fi， and move the content of entry to memory. （打开（Fi）：在磁盘上的目录结构中搜寻Fi的表项，然后把表项的内容移动到内存中） close （Fi） – move the content of entry Fi in memory to directory structure on disk. （关闭（Fi）：把Fi在内存中的表项内容移动到磁盘中） Applied Operating System Concepts

7 File Types – name， extension 文件类型，名称，扩展名
Applied Operating System Concepts

8 File Logical Structure---Access Methods （逻辑文件---存取方法）
File Organization types:文件组织（逻辑文件、逻辑结构）的类型 Sequential File(顺序文件) : Sequential Access（顺序存取） Direct/Hashed File（直接或散列文件） : Direct Access（直接存取） Indexed File（索引文件） : Indexed Access (索引存取) File Organization Criteria:文件组织的准则 Rapid access访问快速 Ease of update易于更新 Economy of storage节约存储空间 Simple maintenance维护简单 Reliability可靠 Applied Operating System Concepts

9 Applied Operating System Concepts
Sequential File顺序文件 Information in the file is processed in order, one record after the other. 文件中的信息是顺序处理的，一个记录接一个记录。 …… …… n n n+1 record Read/write record n: read record 0 read record 1 …… read record n-1 read/write record n Applied Operating System Concepts

10 Sample of Sequential File顺序文件例子
王一，男，00计算机1班，20， 。 1 赵尔，女，00电子技术1班，20， 。 … …… i-1 李立理，男，00英语1班，18， 。 i 黄湖，男，00英语1班，18， 。 I+1 Applied Operating System Concepts

11 Applied Operating System Concepts
Direct File直接文件 A file is made up of fixed-length logical records that allow program to read and write records rapidly in no particular order. 文件采用固定长度的记录，使得可以直接程序读/写记录。 Record Length=R First read record i : ptr=(i)*R, read Then read record j : ptr=(j)*R, read n n n+1 …… …… Applied Operating System Concepts

12 Sample of Direct File直接文件例子
王一 ，男，00计算机1班 ，20， 1 赵尔 ，女，00电子技术1班 ，20， … …… i-1 李立理 ，男，00英语1班 ，18， i 黄湖 ，男，00英语1班 ，18， I+1 35 (i-1)*35 i*35 length=35 Applied Operating System Concepts

13 Applied Operating System Concepts
Indexed File索引文件 The index contains pointers to the various blocks. To find a record in the file, we first search the index, and then use the pointer to access the file direct and to find the desired record.索引包含指向对应数据块的指针，要在文件中找到一个记录，我们实现检索索引，根据索引的指针直接定位到对应的记录。 Index Logical File(Sequential File) P0 1 P1 …… i Pi R0 R1 …… Ri Applied Operating System Concepts

14 Sample of Indexed File索引文件例子
1 34 … i-1 2456 i 2490 i+1 王一，男，00计算机1班，20， 1 赵尔，女，00电子技术1班，20， … …… i-1 李立理，男，00英语1班，18， i 黄湖，男，00英语1班，18， I+1 Applied Operating System Concepts

15 Directory Structure（目录结构）
Directory -A collection of nodes containing information about all files. （一个包含着所有文件信息的节点的集合） Directory item/FCB 目录项/文件控制块 Directory 目录 Files 文件 F 1 F 2 F 3 F 4 F n Both the directory structure and the files reside on disk.（目录结构和文件都在磁盘上） Applied Operating System Concepts

16 Information in File Control Block (FCB) FCB中的信息
File control block – storage structure consisting of information about a file.文件控制块FCB：由一个文件的相关信息组成的存储结构 Information in FileControl Block： Name （名称） Type（类型） Address （地址） Current length（当前长度） Maximum length（最大长度） Date last accessed （for archival）（最后访问时间） Date last updated （for dump）（数据最后更新时间） Owner ID （who pays）（所有者ID） Protection information （discuss later）（保护信息） …… Applied Operating System Concepts

17 Directory Performance目录效率
If Directory item size = ds bytes目录项大小ds Max directory item number in a directory file = n目录文件最多n个目录项 Block size=b块大小b Then Directory file size=ds*n bytes目录文件大小ds*n A directory file need blocks= ds*n/b一个目录文件占ds*n/b块 Search a file need to read blocks=(ds*n/b+1)2查找一个文件（平均）需要读(ds*n/b+1)2块 So Reduce ds reduce read blocks减少目录项的大小可以减少读块的数目，提高目录的效率 Applied Operating System Concepts

18 Applied Operating System Concepts
i Node i结点 Directory item/i node 目录项/i结点 FCB 文件控制块 Files 文件 F 1 F 2 F 3 F n F 4 Applied Operating System Concepts

19 Operations Performed on Directory 操作系统的目录行为
Search for a file（寻找一个文件） Create a file（建立一个文件） Delete a file（删除一个文件） List a directory（（列出目录的列表） Rename a file（重命名文件） Traverse the file system（整体操作文件系统） Applied Operating System Concepts

20 Organize the Directory （Logically） to Obtain 组织目录的逻辑结构
Efficiency – locating a file quickly.（效率：快速的定位一个文件） Naming – convenient to users.（命名：方便用户） Two users can have same name for different files. （两个用户可以有相同名字的不同文件） The same file can have several different names. （相同的文件可以有不同的名字） Grouping – logical grouping of files by properties， （e.g.， all Pascal programs， all games， …） （分组：从逻辑上对文件按属性进行分组，比如所有的Pascal程序，游戏） Applied Operating System Concepts

21 Single-Level Directory（单级目录）
A single directory for all users.（一个对所有用户的简单目录结构） Naming problem（命名问题） Grouping problem（分组） Applied Operating System Concepts

22 Two-Level Directory（二级目录）
Separate directory for each user.（每个用户有单独的目录结构） Path name（路径名） Can have the same file name for different user（不同的用户可以有相同 Efficient searching（有效率的搜索） No grouping capability（无法分组） Applied Operating System Concepts

23 Tree-Structured Directories（树型目录）
Applied Operating System Concepts

24 Tree-Structured Directories （Cont.） 树型目录（续）
Efficient searching（有效的搜索） Grouping Capability（分组的可能） Current directory （working directory）（当前目录—工作目录） cd /spell/mail/prog type list Applied Operating System Concepts

25 Tree-Structured Directories （Cont.）
Absolute or relative path name（绝对或相对路径名） Creating a new file is done in current directory. （建立新文件在当前路径下） Delete a file（删除一个文件） rm <file-name> Creating a new subdirectory is done in current directory.（建立新子目录在当前路径下） mkdir <dir-name> Example： if in current directory /spell/mail mkdir count mail prog copy prt exp count Deleting “mail”  deleting the entire subtree rooted by “mail”. Applied Operating System Concepts

26 Acyclic-Graph Directories （无环图结构目录）
Have shared subdirectories and files.（有共享的子目录和文件） Applied Operating System Concepts

27 Acyclic-Graph Directory （Cont.） 无环图结构目录（续）
Acyclic-graph directory can share files and subdirectory.无环图结构目录可以共享文件和目录 Share file can maintain consistency if the file is modified.共享文件能保持数据的一致性 Acyclic-Graph Directory structure is more flexible , but it’s also more complex.无环图结构目录更加灵活，但也更加复杂。 Two types of share file: Symbolic Link符号链接 Windows的快捷方式 Hard Link硬链接 UNIX 的基于索引结点方式 Applied Operating System Concepts

28 General Graph Directory （普通图结构目录）
Applied Operating System Concepts

29 General Graph Directory （Cont.） 普通图结构目录（续）
How do we guarantee no cycles?（如何保证无环） Allow only links to file not subdirectories. （只允许链接到文件而不允许链接到子目录） Garbage collection.（碎片收集） Every time a new link is added use a cycle detection algorithm to determine whether it is OK. （每次添加一个链接时都用一个检测算法判断是否不正确） Applied Operating System Concepts

30 Applied Operating System Concepts
Protection（保护） File owner/creator should be able to control （文件所有者应当有权限控制：） what can be done（去做什么） by whom（由谁来做） Types of access（存取的类型） Read（读） Write（写） Execute（执行） Append（添加） Delete（删除） List（列表） Applied Operating System Concepts

31 Access Lists and Groups （访问列表或分组）
Mode of access： read， write， execute访问模式：读写执行） Three classes of users（三种类型的用户） RWX a） owner access （所有者）7  RWX b） groups access（组用户）6  1 1 0 c） public access（公共用户）1  0 0 1 Ask manager to create a group （unique name）， say G， and add some users to the group.（建立一个组，加入一些用户） For a particular file （say game） or subdirectory， define an appropriate access.（对特定文件或目录，定义适当的访问） owner group public chmod 761 game Attach a group to a file（加入组的信息到文件） chgrp G game Applied Operating System Concepts

32 File-System Structure （文件系统结构）
File structure（文件结构） Logical storage unit（逻辑存储单元） Collection of related information（相关信息的集合） File system resides on secondary storage （disks）. （文件系统存在于辅助存储器中—磁盘） File system organized into layers.（文件系统按层组织） Application Programs Logical File System File-Organization Module Basic File System I/O Control Devices Applied Operating System Concepts

33 Physical File Structure 物理文件结构
The files are stored on the disk , physical file structure decide how to allocate space to files so that the disk space is utilized effectively and files can be accessed quickly. 文件存储在磁盘上，物理文件结构决定如何分配空间给文件以便使得空间的利用是高效的，文件的访问是快速的。 Three major Methods: Contiguous连续分配 Linked链接分配 Indexed索引分配 Applied Operating System Concepts

34 Contiguous Allocation（顺序分配）
Each file occupies a set of contiguous blocks on the disk. （每一个文件占用一个连续的磁盘块的集合） Simple – only starting location （block #） and length （number of blocks） are required.（简单：只需要起始块号和长度） Random access.（可以随机存取） Wasteful of space （dynamic storage-allocation problem）. （浪费空间：动态存储分配问题） Files cannot grow.（文件不能增长） Mapping from logical to physical.（从逻辑地址映射到物理地址） Block to be accessed = Q + starting address Displacement into block = R Q LA/512 R Applied Operating System Concepts

35 Linked Allocation（链接分配）
Each file is a linked list of disk blocks： blocks may be scattered anywhere on the disk. 每个文件是一个的磁盘块的链接列表：块可以分散在磁盘各处。 block = pointer Applied Operating System Concepts

36 Applied Operating System Concepts
A Sample 例子 Allocate as needed， link together; e.g.， file starts at block 9 按所需分配磁盘块，链接在一起。文件起始于第九块 Applied Operating System Concepts

37 Linked Allocation （Cont.） （链接分配，续）
Simple – need only starting address（简单：只需要起始地址） Free-space management system – no waste of space （自由空间管理系统：没有磁盘空间浪费） No random access（无法随机存取） Mapping（映射） Q LA/511 R Block to be accessed is the Qth block in the linked chain of blocks representing the file. Displacement into block = R + 1 File-allocation table （FAT） – disk-space allocation used by MS-DOS and OS/2.（文件分配表：被MS-DOS和OS/2所采用） Applied Operating System Concepts

38 Indexed Allocation（索引分配）
Brings all pointers together into the index block. （把所有的指针都一起放在索引块里） Logical view.（逻辑形式） index table 索引表 Applied Operating System Concepts

39 Example of Indexed Allocation （索引分配的例子）
Applied Operating System Concepts

40 Indexed Allocation （Cont.） （索引分配，续）
Need index table（需要索引表） Random access（随机存取） Dynamic access without external fragmentation， but have overhead of index block.（可以动态存取而没有外部碎片） Mapping from logical to physical in a file of maximum size of 256K words and block size of 512 words. We need only 1 block for index table.（为了从逻辑映射到实际的文件系统，一个256K字的文件，块为512字，我们只需一个块作为索引表） Q = displacement into index table R = displacement into block Q LA/512 R Applied Operating System Concepts

41 Indexed Allocation – Mapping （Cont.） 索引分配—映射（续）
Mapping from logical to physical in a file of unbounded length （block size of 512 words）. （无限长度的文件从逻辑向物理的映射） Linked scheme – Link blocks of index table （no limit on size）.（链接策略—把索引块链接起来）（没有长度限制） Q1 LA / （512 x 511） R1 Q1 = block of index table R1 is used as follows： Q2 R1 / 512 R2 Q2 = displacement into block of index table R2 displacement into block of file： Applied Operating System Concepts

42 Indexed Allocation – Mapping （Cont.） 索引分配—映射（续）
Two-level index （maximum file size is 5123）（两极索引） Q1 LA / （512 x 512） R1 Q1 = displacement into outer-index R1 is used as follows： Q2 R1 / 512 R2 Q2 = displacement into block of index table R2 displacement into block of file： Applied Operating System Concepts

43 Indexed Allocation – Mapping （Cont.） 索引分配—映射（续）
 outer-index 外部索引 index table 索引表 File 文件 Applied Operating System Concepts

44 Combined Scheme：UNIX 联合策略：UNIX（4K字节每个块）
Applied Operating System Concepts

45 Free-Space Management （自由空间管理）
Bit vector （n blocks）（位图） 1 2 n-1 … 0  block[i] free 1  block[i] occupied bit[i] =  Block number calculation（块数计算） （number of bits per word） * （每个字的bit数） （number of 0-value words） （值为0的字的个数） + offset of first 1 bit 第一个bit的偏移量 Applied Operating System Concepts

46 Free-Space Management （Cont.） 自由空间管理（续）
Bit map requires extra space. Example（位图需要额外空间） block size = 212 bytes disk size = 230 bytes （1 gigabyte） n = 230/212 = 218 bits （or 32K bytes） Easy to get contiguous files （比较容易得到连续的文件） Linked list （free list）（链接表—自由空间表） Cannot get contiguous space easily（得到连续空间困难） No waste of space（没有浪费空间） Grouping （分组） Counting（计数） Applied Operating System Concepts

47 Efficiency and Performance （效率和性能）
Efficiency dependent on：（效率取决于） disk allocation and directory algorithms （磁盘分配和目录算法） types of data kept in file’s directory entry （保存在文件目录项中的数据结构） Performance（性能） disk cache – separate section of main memory for frequently sued blocks （磁盘高速缓存—主存中用于存放经常访问块的单独区域） free-behind and read-ahead – techniques to optimize sequential access （free-behind&read-ahead：优化顺序存取的技术） improve PC performance by dedicating section of memroy as virtual disk， or RAM disk. （改进PC性能可以靠用内存来模拟磁盘，即RAM） Applied Operating System Concepts

48 Various Disk-Caching Locations 可变的磁盘高速缓存分配
Applied Operating System Concepts

49 Applied Operating System Concepts
Recovery（恢复） Consistency checker – compares data in directory structure with data blocks on disk， and tries to fix inconsistencies. （一致性检查：比较目录结构中的数据和磁盘块中的数据，尝试着去修正不一致） Use system programs to back up data from disk to another storage device （floppy disk， magnetic tape）. （应用系统程序来备份数据到其他的存储设备，软盘，磁带） Recover lost file or disk by restoring data from backup. （通过从备份重建来恢复丢失的文件或磁盘） Applied Operating System Concepts

50 Applied Operating System Concepts
Summary（总结） Files are the most obvious object that operating systems manipulate. Everything is typically stored in files: programs, data, output, and so on. (文件是操作系统操作的最明显的对象。每样东西都作为特色存放在文件中：程序、数据、输出等等。) In this chapter we discuss various methods for storing information on secondary storage.(本章讨论了二级存储系统中的多种存储信息的方法。) The basic issues are device directory, free space management, and space allocation on a disk.(基本问题是设备目录，空闲空间管理和磁盘空间分配。) Applied Operating System Concepts

51 Applied Operating System Concepts
作业 P P Applied Operating System Concepts