Transcript 第六章文件系统
Operating Systems 软件学院 高海昌 [email protected] Operating Systems Contents 1. Introduction ** 2. Processes and Threads ******* 3. Deadlocks ** 4. Memory Management ***** 5. Input/Output *** 6. File Systems **** 8. Multiple Processor Systems * 9. Security ** Gao Haichang , Software School, Xidian University 2 Operating Systems Chapter 6: File Systems 6.1 Files 6.2 Directories 6.3 File system implementation 6.4 Example file systems Gao Haichang , Software School, Xidian University 3 Operating Systems Long-term Information Storage Three essential requirements: 1. Must be possible to store a large amount of information 2. Information stored must survive the termination of the process using it 3. Multiple processes must be able to access the information concurrently The usual solution to all these problems is to store information on disks and other external media in units called files. Gao Haichang , Software School, Xidian University 4 Operating Systems File Naming The extra rules for naming vary somewhat from system to system. bruce, device, multimedia 123, urgent!, fig.2-1 longlongagotherewasawarbetweentthebirdsandthebeasts (<255) Some file systems distinguish between upper and lower ease letters (UNIX), whereas others do not (MS-DOS). Many OS support two-part file names, with the two parts separated by a period, as in prog.c. The part following the period is called the file extension. Gao Haichang , Software School, Xidian University 5 Operating Systems File Naming Typical file extensions. Gao Haichang , Software School, Xidian University 6 Operating Systems File Structure (a) byte sequence (UNIX and Windows) (b) record sequence (80-character punched card) (c) tree (commercial data processing large mainframe computers) Three kinds of files Gao Haichang , Software School, Xidian University 7 Operating Systems File Types Sort by usage system files user files library files Sort by data format source files object files executable files Sort by access control attribution executable-only files read-only files read/write files Gao Haichang , Software School, Xidian University 8 Operating Systems File Types (2) Sort by file logical structure structured files unstructured files Sort by file physical structure sequential files linking files index files Gao Haichang , Software School, Xidian University 9 Operating Systems File Types (3) UNIX and Windows have regular files and directories. UNIX also has character and block special files. Regular files: contain user information. Directories: system files for maintaining the structure of the file system. Character special files: related to I/O. Block special files: used to model disks. Regular files are generally either ASCII files or binary files. Gao Haichang , Software School, Xidian University 10 Operating Systems File Types (4) (a) An executable file (b) An archive 存档文件 Gao Haichang , Software School, Xidian University 11 Operating Systems File Types (exercise) In an executable file, the instructions are usually put into text segment. the _______ header, text, data, relocation bits, symbol table Gao Haichang , Software School, Xidian University 12 Operating Systems File Access Sequential access read all bytes/records from the beginning cannot jump around, could rewind or back up convenient when medium was mag tape Random access bytes/records essential for read in any order data base systems Gao Haichang , Software School, Xidian University 13 Operating Systems File Attributes Possible file attributes Gao Haichang , Software School, Xidian University 14 Operating Systems File Operations 1. Create 7. Append 2. Delete 8. Seek 3. Open 9. Get attributes 4. Close 10. Set Attributes 5. Read 11. Rename 6. Write Gao Haichang , Software School, Xidian University 15 Operating Systems An Example Program Using File System Calls (1/2) copyfile abc xyz argc=3, argv[0]=“copyfile”, argv[1]=“abc”, argv[2]=“xyz” Gao Haichang , Software School, Xidian University 16 Operating Systems An Example Program Using File System Calls (2/2) Gao Haichang , Software School, Xidian University 17 Operating Systems Memory-Mapped Files Access file as above is inconvenient. Map files into the address space of a running process. (a) Segmented process before mapping files into its address space (b) Process after mapping existing file abc into one segment creating new segment for xyz Gao Haichang , Software School, Xidian University 18 Operating Systems Chapter 6: File Systems 6.1 Files 6.2 Directories 6.3 File system implementation 6.4 Example file systems Gao Haichang , Software School, Xidian University 19 Operating Systems Single-Level Directory Systems A single level directory system contains 4 files owned by 3 different people, A, B, and C Problem: different users may accidently use the same names for their files. Gao Haichang , Software School, Xidian University 20 Operating Systems Two-level Directory Systems Letters indicate owners of the directories and files open (“x”) open (“nancy/x”) Problem: it is not satisfactory for users with a large number of files. Gao Haichang , Software School, Xidian University 21 Operating Systems Hierarchical Directory Systems A hierarchical directory system (a tree of directories) Gao Haichang , Software School, Xidian University 22 Operating Systems Path Names – Absolute path name /usr/ast/mailbox (UNIX) \usr\ast\mailbox (Win) – Relative path name mailbox – Working directory ( current directory) /usr/ast – . , .. A UNIX directory tree Gao Haichang , Software School, Xidian University 23 Operating Systems Directory Operations 1. Create 2. Delete 3. Opendir 4. Closedir 5. Readdir 6. Rename 7. Link (hard link/symbol link) 8. Unlink Gao Haichang , Software School, Xidian University 24 Operating Systems Exercise In the file system shown in the following figure, rectangle represents directory, circle represents file, “/” represents the delimiter（分隔符）in the path name which represents the root directory when placed on the head of path name. In the figure （1） . If the present directory is ‘D1’, process A opens the ‘f1’ by the two ways listed blow: ① fd1=open(“ （2） /f1”, O_RDONLY) ② fd1=open(“/D1/W1/f1”, O_RDONLY) ① is more efficient than ②, / D1 the reason is （3） : f1 W1 W2 f1 f2 D2 f2 Gao Haichang , Software School, Xidian University W3 f4 25 Operating Systems Exercise （1）A. f2 in subdirectory W2 is the same as the f2 in subdirectory D2 B. f2 in subdirectory W2 is different from the f2 in subdirectory D2 C. f2 in subdirectory W2 and f2 in subdirectory D2 may be same and may be different D. tree-shaped file system didn’t allow appear the file with same name （2）A. /D1/W1 B. D1/W1 C. W1 D. f1 （3）A. ① can directly access the f1 in the root directory B. ① can access the f1 started from searching the present directory C. To get f1, ① needs only one time to access disk, but ② needs 2 times D. To get f1, ① needs only one time to access disk, but ② needs 3 times Gao Haichang , Software School, Xidian University 26 Operating Systems Lesson 2 Operating Systems Chapter 6: File Systems 6.1 Files 6.2 Directories 6.3 File system implementation 6.4 Example file systems Gao Haichang , Software School, Xidian University 28 Operating Systems File System layout 布局 File system are stored on disk. Most disks can be divided up into one or more partitions, with independent file systems on each partition. Sector 0 of the disk is called MBR (Master Boot Record) and is used to boot the computer. Gao Haichang , Software School, Xidian University 29 Operating Systems File System layout A possible file system layout Partition table: gives the starting and ending addresses of each partition. Boot block: locate the active partition Superblock: magic number, number of blocks, … Free space mgmt: free blocks in the form of bitmap or a list of pointers. i-nodes: an array of data structure, one per file. Gao Haichang , Software School, Xidian University 30 Operating Systems Implementing Files various methods are used in different systems Contiguous allocation Linked list allocation Linked list allocation using a table in memory i-nodes Gao Haichang , Software School, Xidian University 31 Operating Systems Implementing Files (a) Contiguous allocation of disk space for 7 files (b) State of the disk after files D and E have been removed Ad: simple to implement; read performance is excellent. Dis: in time, the disk becomes fragmented. Contiguous allocation is feasible in CD-ROM file system. Gao Haichang , Software School, Xidian University 32 Operating Systems Implementing Files (2) Storing a file as a linked list of disk blocks Dis: random access is extremely slow. Gao Haichang , Software School, Xidian University 33 Operating Systems Implementing Files (3) Such a table in main memory is called a FAT (File Allocation Table) Linked list allocation using a file allocation table in RAM Dis: entire table must be in memory all the time to make it work. Gao Haichang , Software School, Xidian University 34 Operating Systems Implementing Files (4) Associate with each file a data structure called an inode (index-node), which lists the attributes and disk addresses of the file’s blocks. Ad: i-node need only be in memory when the corresponding file is open. An example i-node Gao Haichang , Software School, Xidian University 35 Operating Systems Implementing Directories The main function of the directory system is to map the ASCII name of the file onto the information needed to locate the data. Where the attributes should be stored? Store them directly in the directory entry. For systems that use i-nodes, store the attributes in the inodes. Gao Haichang , Software School, Xidian University 36 Operating Systems Implementing Directories (2) (a) A simple directory, fixed size entries, disk addresses and attributes in directory entry (Windows) (b) Directory in which each entry just refers to an i-node (UNIX) Gao Haichang , Software School, Xidian University 37 Operating Systems Implementing Directories (3) So far we have assumed that files have short, fixed-length names. However, nearly all modern OS support longer, variable- length file names. How can these be implemented? Simplest way: set a limit on file name length (255), and use one of the designs above for each file name. (Waste) Second, give up the same size. Each dir entry contains a fixed portion, followed by the actual file name, however long it may be. - dis: when a file is removed, a variable-sized gap is introduced into the dir into which the next file to be entered may not fit. Third, make the dir entries themselves all fixed length and keep the file names together in a heap at the end of the dir. Gao Haichang , Software School, Xidian University 38 Operating Systems Implementing Directories (4) (a) In-line (b) In a heap Two ways of handling long file names in directory Gao Haichang , Software School, Xidian University 39 Operating Systems Shared Files File system containing a shared file Gao Haichang , Software School, Xidian University 40 Operating Systems Shared Files (2) If dir really do contain disk address, then a copy of the disk address will have to be made in B’s dir when the file is linked. If either B or C subsequently appends to the file, the new blocks will be listed only in the dir of the user doing the append. Problem can be solved in two ways: Disk blocks are not listed in dir, but in a little data structure associated with the file itself (i-node in UNIX). B links to C’s files by having the system create a new file, of type LINK, and entering that file in B’s dir. The new file contains just the path name of the file to which it is linked. (symbolic linking) Gao Haichang , Software School, Xidian University 41 Operating Systems Shared Files (3) (a) Situation prior to linking (b) After the link is created (c)After the original owner removes the file Gao Haichang , Software School, Xidian University 42 Operating Systems Shared Files (4) Drawbacks of first solution: If C tries to remove a file, OS removes the file and clears the i-node, B will have a dir entry pointing to an invalid i-node. If the i-node is later reassigned to another file, B’s link will point to the wrong file. The system can see from the count in the i-node that the file is still in use, but there is no way for it to find all the dir entries for the file, in order to erase them. The problem with symbolic links is the extra overhead required. Drawbacks for both: programs that start at a given dir and find all the files in that dir and its subdir will locate a linked file multiple times. Gao Haichang , Software School, Xidian University 43 Operating Systems Disk Space Management Two general strategies are possible for storing an n byte file: n consecutive bytes of disk space are allocated or the file is split up into a number of blocks. Nearly all file systems chop files up into fixed-size blocks that need not be adjacent. Gao Haichang , Software School, Xidian University 44 Operating Systems Block size Block size The solid curve gives data rate of a disk. (data rate 数据速率 goes up with block size) The dashed curve gives disk space efficiency. (With small blocks that are powers of two and 2-KB files, no space is wasted in a block) All files are 2KB. Gao Haichang , Software School, Xidian University 45 Operating Systems Keeping track of free blocks (a) Storing the free list on a linked list (b) A bit map Bitmap requires less space, since it uses 1 bit per block, VS 32 bits in the linked list model. Gao Haichang , Software School, Xidian University 46 Operating Systems Lesson 3 Operating Systems Disk Space Management (4) When the block of pointers is almost empty, a series of short-lived temporary files can cause a lot of disk I/O. (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 blocks Gao Haichang , Software School, Xidian University 48 Operating Systems Disk Quotas 磁盘配额 Quotas for keeping track of each user’s disk use Gao Haichang , Software School, Xidian University 49 Operating Systems File System Reliability Backups is very important It is usually desirable to back up only specific dir and everything in them rather than the entire file system. Incremental dumps 增量转储 It may be desirable to compress the data before writing them to tape, but a single bad spot on the backup tape can foil the decompression algorithm and make an entire file unreadable. It is difficult to perform a backup on an active file system. Making rapid snapshots of the file system state by copying critical data structures. Backup tapes should be kept off-site. Gao Haichang , Software School, Xidian University 50 Operating Systems File System Reliability (2) Two strategies can be used for dumping a disk to tape: Physical dump: start at block 0 of the disk, writes all the disk blocks onto the output tape in order, and stops when it has copied the last one. Advantages: Easy, fast. Disadvantages are the inability to skip selected dir, make incremental dumps, and restore individual files upon request. Logical dump: start at one or more specified dir and recursively (递归地) dumps all files and dir found there that have changed since some given base data. Gao Haichang , Software School, Xidian University 51 Operating Systems File System Reliability (3) File that has not changed A file system to be dumped squares are directories, circles are files shaded items, modified since last dump each directory & file labeled by i-node number Gao Haichang , Software School, Xidian University 52 Operating Systems File System Reliability (4) Bit maps used by the logical dumping algorithm Step 1: examine all the entries. For each modified file, its inode is marked in the bitmap. Each dir is also marked. Step 2: unmark any dir that have no modified files or dir in them or under them. Step 3: dump all the dir that are marked for dumping. Step 4: the files marked are also dumped. Gao Haichang , Software School, Xidian University 53 Operating Systems File System Reliability (5) Tricky issues 棘手之处: Since the free block list is not a file, it is not dumped and hence it must be reconstructed from scratch after all the dumps have been restored. If a file is linked to two or more dir, it is important that the file is restored only one time. UNIX files may contain holes. The blocks in between are not part of the file and should not be dumped and not be restored. Special files, named files, and the like should never be dumped. Gao Haichang , Software School, Xidian University 54 Operating Systems File System Consistency If the system crashes before all the modified blocks have been written out, the file system can be left in an inconsistent state. File system states (a) Consistent (c) duplicate block in free list (b) missing block (d) duplicate data block Gao Haichang , Software School, Xidian University 55 Operating Systems File System Performance Access to disk is much slower than access to memory. Many file system designed with various optimizations to improve performance: Caching Block read ahead Reducing disk arm motion Gao Haichang , Software School, Xidian University 56 Operating Systems Caching The block cache data structures When a block has to be loaded into a full cache, some block has to be removed. (like paging, use LRU) By writing critical blocks quickly, we greatly reduce the probability that a crash will wreck the file system. Gao Haichang , Software School, Xidian University 57 Operating Systems Caching It is undesirable to keep data blocks in the cache too long before writing them out. Systems take two approaches: UNIX, have a system call, sync, which forces all the modified blocks out onto the disk immediately. Sleeping 30 sec between calls, thus no more than 30 sec work is lost due to a crash. MS-DOS, write every modified block to disk as soon as it has been written. Write-through caches 通写高速缓存. Gao Haichang , Software School, Xidian University 58 Operating Systems Block read ahead Try to get blocks into the cache before they are needed to increase the hit rate. Read ahead strategy only works for files that are being read sequentially. Gao Haichang , Software School, Xidian University 59 Operating Systems Reducing disk arm motion By putting blocks that are likely to be accessed in sequence close to each other. Easy to choose in bitmap record. Even with a free list, some block clustering can be done. For i-node system, reading even a short file requires two disk accesses. One for the i-node, and one for the block. i-node are usually near the beginning of the disk. Put the i-nodes in the middle of the disk. Divide the disk into cylinder groups, each with its own inodes, blocks, and free list. Gao Haichang , Software School, Xidian University 60 Operating Systems Reducing disk arm motion I-nodes placed at the start of the disk Disk divided into cylinder groups each with its own blocks and i-nodes Gao Haichang , Software School, Xidian University 61 Operating Systems Log-Structured File Systems LFS, 日志结构文件系统 With CPUs faster, memory larger disk caches can also be larger increasing number of read requests can directly come from file system cache, with no disk access needed thus, most disk accesses will be writes LFS Strategy structures entire disk as a log have all writes initially buffered in memory periodically write these to the end of the disk log when file opened, using map to locate i-node, then find blocks LFS has a cleaner thread that spends its time scanning the log circularly to compact it. Gao Haichang , Software School, Xidian University 62 Operating Systems Chapter 6: File Systems 6.1 Files 6.2 Directories 6.3 File system implementation 6.4 Example file systems Gao Haichang , Software School, Xidian University 63 Operating Systems CD-ROM File Systems Simple, have no provision for keeping track of free blocks. There is a single continuous spiral containing the bits in a linear sequence. The ISO 9660 directory entry Restriction: The max depth of dir nesting is 8 Rock Ridge extensions (UNIX) Joliet extensions (Windows) Gao Haichang , Software School, Xidian University 64 Operating Systems The CP/M File System Control Program for Microcomputers, CP/M 微机控制程 序. A surprisingly powerful disk-based OS. It is a historically very important system and was the direct ancestor of MS-DOS. The system can ran quite well in 16KB of RAM. (The size of OS in CP/M 2.2 is 3584 bytes!) Embedded systems are going to be extremely widespread. Memory layout of CP/M Gao Haichang , Software School, Xidian University 65 Operating Systems The CP/M File System (2) 1KB each block, maximum file size is 16KB. The CP/M directory entry format (only 1 dir in CP/M) Gao Haichang , Software School, Xidian University 66 Operating Systems The MS-DOS File System Run only on Intel platforms and only in the PC’s real mode. Does not support multiprogramming. MS-DOS was patterned closely on the CP/M file system including the use of 8+3 character file names. From MS-DOS 2.0, has a hierarchical file system in which dir could be nested. Unlike CP/M, there is no concept of different users in MS-DOS. Unlike CP/M, MS-DOS store the exact file size. MS-DOS does not store a file’s disk address in its dir entry. It keeps track of file blocks via a file allocation table (FAT) in main memory. Gao Haichang , Software School, Xidian University 67 Operating Systems The MS-DOS File System 32-bit number is used, file size is 4GB largest in theory. The MS-DOS directory entry Gao Haichang , Software School, Xidian University 68 Operating Systems The MS-DOS File System (2) Maximum partition for different block sizes (The empty boxes represent forbidden combinations) Gao Haichang , Software School, Xidian University 69 Operating Systems The Windows 98 File System Win98 use long file names and FAT-32. Files created using Win98 can be accessible from Win3.x. It was backward compatible with the old MS-DOS 8+3 naming system. When a file is created whose name does not obey the MS-DOS naming system. Win98 invents an MS-DOS name for it according to a certain algorithm. Bytes The extended MS-DOS directory entry used in Windows 98 Gao Haichang , Software School, Xidian University 70 Operating Systems The Windows 98 File System (2) Every file has an MS-DOS file name. If a file also has a long name, the name is stored in one or more dir entries directly preceding the MS-DOS file name. Each longname entry holds up to 13 characters. Bytes Checksum An entry for (part of) a long file name in Windows 98 Gao Haichang , Software School, Xidian University 71 Operating Systems The Windows 98 File System (3) An example of how a long name is stored in Windows 98 “The quick brown fox jumps over the lazy dog” Gao Haichang , Software School, Xidian University 72 Operating Systems The UNIX V7 File System Multiuser file system. The file system is in the form of a tree starting at the root dir, with the addition of links, forming a directed acyclic graph. A UNIX V7 directory entry Gao Haichang , Software School, Xidian University 73 Operating Systems The UNIX V7 File System (2) A UNIX i-node Gao Haichang , Software School, Xidian University 74 Operating Systems The UNIX V7 File System (3) The steps in looking up /usr/ast/mbox Gao Haichang , Software School, Xidian University 75 Operating Systems Linux文件系统 EXT2 (Linux Second Extend File System, ext2fs). superblock：记录文件系统的整体信息，包括inode/block 的总量、使用量、剩余量， 以及文件系统的格式与相关 信息等； inode：记录文件的属性，一个文件占用一个inode，同时 记录此文件的数据所在的 block 号码； block：实际记录文件的内容，若文件太大时，会占用多 个 block 。 Gao Haichang , Software School, Xidian University 76 Operating Systems Linux文件系统 EXT2 所支持的 block 大小有 1K, 2K 及 4K 三种 文件最大限制 最大容量 1KB 2KB 4KB 16GB 256GB 2TB 2TB 8TB 16TB Gao Haichang , Software School, Xidian University 77 Operating Systems Linux文件系统 可以使用 dumpe2fs 这个命令来查询EXT2 文件系统 Gao Haichang , Software School, Xidian University 78 Operating Systems Linux文件系统 在 Linux 下的 ext2 文件系统创建一个目录时， ext2 会分配 一个 inode 与至少一块 block 给该目录。 可以使用 ls -i 这个选项来查看 root家目录内的文件所占用的 inode 号码 使用ll 查看 Gao Haichang , Software School, Xidian University 79 Operating Systems Linux文件系统 EXT3是一个日志文件系统. 性能（速度）不如它的竞争对手，例如JFS2和XFS，但它具 有重要的优势，那就是它允许在适当的时候从流行的ext2文 件系统升级，而无需备份和恢复数据；除此之外，它还具 有比XFS更低的的CPU使用率. EXT3的增强特性： 日志 位目录跨越多个块提供基于树的目录索引 在线系统增长 文件最大限制 最大容量 1KB 2KB 4KB 8KB* 16GB 256GB 2TB 16TB 2TB 8TB 16TB 32TB Gao Haichang , Software School, Xidian University 80 Operating Systems Linux文件系统 EXT3跟EXT2一样，还是使用15个inode来查找数据块，前 12个为直接数据块，直接指向存储数据的数据块，接下来 分别为一级间接块，二级间接块，三级间接块，如图 Gao Haichang , Software School, Xidian University 81 Operating Systems Linux文件系统 EXT4扩展日志文件系统(Linux Kernel 2.6.28后支持)，特点： 兼容EXT3 更大的文件系统和更大的文件。 Ext4 分别支持 1EB （1,048,576TB）的文件系统，以及 16TB 的文件 无限数量的子目录 引入了现代文件系统中流行的 extents 概念，每个 extent 为一组连续的数据块 多块分配，支持一次调用分配多个数据块 延迟分配。现代文件系统都尽可能地延迟分配，直到文 件在 cache 中写完才开始分配数据块并写入磁盘 快速 fsck 日志校验 无日志模式 … Gao Haichang , Software School, Xidian University 82 Operating Systems Linux文件系统 XFS日志文件系统(CentOS7缺省)，特点： 支持超大文件和文件系统，特别擅长处理大文件（大数 据时代？） 分配组 条带化分配 支持extents 可变块尺寸 延迟分配 稀疏文件 原生备份/恢复工具 … Gao Haichang , Software School, Xidian University 83 Operating Systems Linux文件系统 Linux支持的文件系统： 传统文件系统：ext2 / minix / MS-DOS / FAT (用 vfat 模块) / iso9660 (光盘) 日志式文件系统： ext3 / ReiserFS / Windows' NTFS / IBM's JFS / SGI's XFS 网络文件系统： NFS / SMBFS 支持的文件系统查看命令 查看已经加载到内存中支持的文件系统 Gao Haichang , Software School, Xidian University 84 Operating Systems Linux虚拟文件系统VFS 整个 Linux 系统通过 Virtual Filesystem Switch 的核心功能去 读取 filesystem。整个 Linux 认识的 filesystem 都是 VFS 在 进行管理，使用者并不需要知道每个 partition 的 filesystem 是什么 Gao Haichang , Software School, Xidian University 85