实用操作系统概念 张惠娟 副教授 Ms.zhj@163.com 1.

Presentation on theme: "实用操作系统概念 张惠娟 副教授 Ms.zhj@163.com 1."— Presentation transcript:

1 实用操作系统概念 张惠娟 副教授 1

2 内容框架 概述 体系结构 进程管理 内存管理 文件管理 外设管理 2

3 内容 Chp 13: Mass storage Structure Chp 11: File system 3

4 Module 11: File-System File Concept Directory Structure
Free-Space Management File Implementation Efficiency and Performance Protection Recovery 4

5 File Concept 引言 文件定义 文件系统定义 File Attributes File Operations File type
File Structure Access Methods 5

6 File Concept 引言 计算机应用程序都要：存储信息和检索信息 能够存储大量的信息 长期保存信息 可以共享信息 6

7 File Concept 解决方法 文件 信息以一种单元，即文件的形式存储在磁盘或其他外部介质上。
文件是通过操作系统来管理的，包括：文件的结构、命名、存取、使用、保护、实现方法。 7

8 File Concept 文件系统 负责信息组织、存储和访问，提供高效、快速和方便的信息存储和访问功能。 8

9 File Concept 用户观点 文件系统如何呈现在其面前，如：一个 文件由什么组成、如何命名，如何保护 文件、可进行何种操作等。
操作系统观点 文件目录怎样实现、怎样管理存储空间、文件存储位置、磁盘实际运作方式(与设备管理的接口)等等 9

10 File Concept 文件定义 其中： 标识是文件名 是一组带标识的、在逻辑上有完整意义的信息项的序列。 信息项是构成文件内容的基本单位
长度是单个字节或多个字节 文件内容由文件建立者和使用者解释 10

11 File Concept 文件的各信息项之间具有顺序关系 编号： …… i …… n-1 信息项 ……... 读写指针 11

12 File Concept 文件系统 是操作系统中统一管理信息资源的一种软件。
管理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并且方便用户使用。 12

13 File Concept 文件系统的功能 统一管理文件的存储空间，实施存储空间的分配与回收。 实现文件的按名存取 名字空间 映射 存储空间
名字空间 映射 存储空间 实现文件信息的共享，并提供文件保护和保密措施 13

14 File Concept 向用户提供方便使用的接口 如提供对文件系统操作命令、提供对文件的操作命令：信息存取、加工等
系统维护及向用户提供有关信息 文件系统的执行效率 提供与I/O的统一接口 14

15 File Concept File Attributes
Information about files are kept in the directory structure, which is maintained on the disk. Name – only information kept in human-readable form. Type – needed for systems that support different types. Location – pointer to file location on device. 15

16 File Concept Size – current file size.
Protection – controls who can do reading, writing, executing. Time, date, and user identification – data for protection, security, and usage monitoring. 16

17 File Concept File Operations create write read
reposition within file – file seek delete truncate 17

18 File Concept open(Fi) – search the directory structure on disk for entry Fi, and move the content of entry to memory. close (Fi) – move the content of entry Fi in memory to directory structure on disk. 18

19 File Concept File type 临时文件；永久文件；档案文件 只读文件；读写文件；可执行文件 分类目的
对不同文件进行管理,提高系统效率； 提高用户界面友好性 按信息保存期限分类 临时文件；永久文件；档案文件 按文件保护方式分类 只读文件；读写文件；可执行文件 19

20 File Concept 按文件性质和用途分类 系统文件 用户文件 库文件 20

21 File Concept 按文件的逻辑结构分类 流式文件；记录式文件 按文件的物理结构分类 顺序（连续）文件；链接文件；索引文件 21

22 File Concept 22

23 File Concept File Structure 逻辑结构 物理结构 23

24 File Concept 逻辑结构 是从用户角度研究文件的组织形式 无结构文件 有结构文件 24

25 File Concept 一条记录 一个字节 字节序列 记录序列 树 25

26 File Concept 无结构文件：流式文件 构成文件的基本单位是字符，文件是有逻辑意义的、无结构的一串字符的集合。 文件
一个无结构字节序列 好处 提供很大的灵活性 26

27 File Concept 有结构文件：记录文件 文件是由若干个记录组成，每个记录有一个键，可按键进行查找。 文件
一个固定长度记录的序列，每条记录有其内部结构 27

28 File Concept 物理结构 从系统角度来看文件，从文件在物理介质上的存放方式来研究文件. 连续（顺序）结构 链接结构 索引结构 28

29 File Concept 连续结构（顺序） 文件信息存放在若干连续的物理块中 29

30 File Concept 文件目录 文件名 始址 块数 count 0 2 tr 14 3 mail 19 6 list 28 4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 文件名 始址 块数 count tr mail list f 文件目录 count f tr mail list 30

31 File Concept 优点 简单 支持顺序存取和随机存取 顺序存取速度快 所需的磁盘寻道次数和寻道时间最少 31

32 File Concept 缺点 文件不能动态增长 预留空间:浪费 重新分配和移动 不利于文件插入和删除 外部碎片问题 存储压缩技术 32

33 File Concept 链接结构 文件信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。 33

34 File Concept 文件目录 文件名 始址 末址 jeep 9 25 1 2 3 4 5 6 7 8 9 10 11 12 13 14
文件名 始址 末址 jeep 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 -1 34

35 File Concept 优点 提高了磁盘空间利用率,不存在外部碎片问题 有利于文件插入和删除 有利于文件动态扩充 35

36 File Concept 缺点 存取速度慢，不适于随机存取 可靠性问题，如指针出错 更多的寻道次数和寻道时间 链接指针占用一定的空间 36

37 File Concept 索引结构 文件信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构--索引表，并将这些块的块号存放在一个索引表中 一个索引表就是磁盘块地址数组,其中第i个条目指向文件的第i块 37

38 文件目录 文件名 索引表地址 Jeep 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 9 16 1 10 25 -1 19 38

39 File Concept 优点 保持了链接结构的优点,又解决了其缺点： 即能顺序存取,又能随机存取 满足了文件动态增长、插入删除要求
能充分利用外存空间 39

40 File Concept 缺点 较多的寻道次数和寻道时间 索引表本身带来了系统开销 如：内外存空间，存取时间 40

41 File Concept 索引表组织 链接模式 一个盘块一个索引表,多个索引表链接起来 多级索引
将一个大文件的所有索引表（二级索引)的地址放在另一个索引表（一级索引)中 综合模式 UNIX文件系统采用多级索引结构(综合模式)。 41

42 File Concept 综合模式 每个文件索引表为13个索引项，每项2个字节。最前面10项直接登记存放文件信息的物理块号（直接寻址）
如果文件大于10块，则利用第11项指向一个物理块，该块中最多可放256个文件物理块的块号（一次间接寻址）。对于更大的文件还可利用第12和第13项作为二次和三次间接寻址 UNIX采用了三级索引结构后，文件最大可达16兆个物理块 42

43 43

44 File Concept Access Methods 顺序存取方式 随机(直接)存取方式 44

45 File Concept 存储介质 物理结构 存取方式 磁带 连续结构 顺序存取 磁盘 连续 链接 索引 顺序 随机 45

46 Directory Structure 基本概念 目录结构 文件访问方法 目录结构改进 46

47 Directory Structure 基本概念 文件控制块（FCB）
文件控制块是操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息（文件属性） 文件控制块是文件存在的标志 47

48 Directory Structure 文件控制块内容 Name Type Address Current length
Maximum length Date last accessed (for archival) Date last updated (for dump) Owner ID (who pays) Protection information (discuss later) 48

49 Directory Structure 文件目录 把所有FCB组织在一起，就构成了文件目录，即文件控制块的有序集合 目录项
目录文件 为实现对文件目录的管理，通常将文件目录以文件形式保存在外存，这个文件就叫目录文件。 49

50 Directory Structure 目录结构 目的 一级目录 二级目录 树型目录（多级目录） 其它方法 50

51 Directory Structure 目的 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, …) 51

52 Directory Structure 一级目录结构 A single directory for all users. 52

53 Directory Structure 优点 简单、易实现 缺点 Naming problem Grouping problem 53

54 Directory Structure 二级目录结构 Separate directory for each user. 54

55 Directory Structure 优点 Path name
Can have the saem file name for different user Efficient searching No grouping capability 缺点 增加系统开销 55

56 Directory Structure 树型目录结构 56

57 Directory Structure 优点 缺点 查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响速度
层次结构清晰，便于管理和保护 有利于文件分类 解决重名问题 提高文件检索速度 能进行存取权限的控制 缺点 查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响速度 57

58 Directory Structure 如B+树 其它方法 哈希表算法 其他算法 目录项信息存在一哈希表中 搜索时根据文件名计算哈希值
得到一个指向表中文件的指针 其他算法 如B+树 58

59 Directory Structure 文件访问方法 目录检索 根据路径名检索： 全路径名：从根开始 相对路径：从当前目录开始
用户给出文件名，按名寻找目录项 根据路径名检索： 全路径名：从根开始 相对路径：从当前目录开始 59

60 Directory Structure 根据FCB中文件物理地址等信息，求出文件的任意记录或字符在存取介质上的地址，称为文件寻址。 文件寻址
60

61 Directory Structure 目录改进 改进目的 加快目录检索 61

62 Directory Structure 改进方法 如：UNIX：I节点（索引节点） 采用目录项分解法，把FCB分成两部分。
符号目录顶（次部） 文件名，文件号 基本目录项（主部） 除文件名外的所有项目 如：UNIX：I节点（索引节点） 62

63 63

64 Directory Structure 例：
一个FCB有48个字节，符号目录项占 8字节，文件名6字节，文件号2字节，基本目录项占 48-6=42字节。 假设，物理块大小512字节 64

65 Directory Structure 解： 分解前：占512/48=10个FCB
分解后：占512/8=64个符号目录项或512/42=12个基本目录项 假设：目录文件有128个目录项 分解前：占13块 分解后：符号文件占2块 基本文件占11块 65

66 Directory Structure 查找一个文件的平均访盘次数 分解前：(1+13)/2=7次 分解后：(1+2)/2 +1 =2.5次
减少了访问硬盘的次数，提高了检索速度 66

67 Free-Space Management
数据结构 管理方法 67

68 Free-Space Management
数据结构 空闲块表 所有空闲块记录在一个表中 空闲块链表 把所有空闲块链成一个链 68

69 Free-Space Management
管理方法 位图法 成组链接法 69

70 Free-Space Management
位示图 用一串二进制位反映磁盘空间中的分配使用 情况, 每个物理块对应一位, 分配物理块为1，否则为0。 申请物理块时，在位示图中查找为0的位，返回对应物理块号； 归还时，将对应位转置0 描述能力强，适合各种物理结构 70

71 Free-Space Management
计算公式 已知字号i，位号j 块号＝i×字长＋j 已知块号 字号＝[ 块号/字长] 位号＝块号 mod 字长 71

72 Free-Space Management
已知块号，则磁盘地址：    柱面号＝[块号/（磁头数×扇区数）]    磁头号＝[（块号mod （磁头数×扇区数））/扇区数]    扇区号＝（块号mod （磁头数×扇区数））mod 扇区数 已知磁盘地址： 块号＝柱面号×（磁头数×扇区数）＋磁头号×扇区数＋扇区号 72

73 Free-Space Management
成组链接法 73

74 74

75 S.free 100 300 299 。。。 201 空闲盘 块栈 1 99 400 399 … 301 500 499 401 75

76 Protection File owner/creator should be able to control:
what can be done by whom Types of access Read Write Execute Append Delete List 76

77 File Implementation 数据结构 文件执行 77

78 File Implementation 数据结构 系统文件表 用户文件表 两种表间的关系 78

79 File Implementation 系统文件表
系统打开文件表（整个系统一张）放在内存，用于保存已打开文件的FCB文件号、共享计数、修改标志 79

80 File Implementation 用户文件表 每个进程一个，进程的PCB中，记录了用户打开文件表的位置。 80

81 File Implementation 两种表间的关系 用户打开文件表指向系统打开文件表
多个进程共享同一个文件，则多个用户打开文件表目对应系统打开文件表的同一入口 81

82 82

83 File Implementation 文件执行 文件操作 执行过程 文件共享 83

84 File Implementation 文件操作 提供设置和修改对用户文件存取权限的服务 提供建立、修改、改变、删除目录的服务
提供文件共享、设置访问路径的服务 提供创建、打开、读、写、关闭、撤消文件等服务 文件系统维护 文件系统的转储和恢复 84

85 File Implementation 文件执行 Create() Open() Read() …… 85

86 File Implementation Create()
实质是建立文件的FCB，并建立必要的存储空间，分配空FCB，根据提供的参数及需要填写有关内容，返回一个文件描述. 86

87 File Implementation 执行过程： 检查参数的合法性 检查同一目录下有无重名文件 在目录中有无空闲位置 填写目录项内容 返回
87

88 File Implementation Open() 文件使用前都要先打开，即把FCB送到内存。 fd=open（文件路径名，打开方式）
88

89 File Implementation 执行过程： 根据文件路径名查目录，找到FCB主部； 根据打开方式、共享说明和用户身份检查访问合法性；
89

90 File Implementation 在用户打开文件表中取一空表项，填写打开方式等，并指向系统打开文件表对应表项。 返回信息
fd：文件描述符，是一个非负整数，用于以后读写文件。 90

91 File Implementation Read() 检查长度是否为正整数 根据文件名查找目录，确定该文件在目录中的位置。
根据隐含参数中的进程主和目录中该文件的存储权限数据，检查是否有权读？ 由文件内位置与要读的长度计算最末位置，将其与目录中的文件长度比较，超过否？ 91

92 File Implementation 根据参数中的位置、长度和目录中的映射信息，确定块号、块数、块内位移与长度。（多次读盘）
根据下一块号读块至内存缓冲区 根据块内位移长度取出要读的内容，送至参数中的内存目的地址 根据块内长度或起始块号+块数，确定还读下一块吗？同时确定下一块块号 92

93 File Implementation 文件共享 一个文件被多个用户或程序使用 定义 目的 节省时间和存储空间，减少了用户工作量
进程间通过文件交换信息 93

94 File Implementation 实现方法 由系统目录实现对文件的共享 对要共享的文件进行连接
通过“连接（Link）”命令，在用户自己的目录项中对要共享的文件建立起相应的表目，即建立两个文件的等价关系 94

95 95

96 Efficiency and Performance
Efficiency dependent on: disk allocation and directory algorithms types of data kept in file’s directory entry 96

97 Efficiency and Performance
disk cache – separate section of main memory for frequently sued blocks free-behind and read-ahead – techniques to optimize sequential access improve PC performance by dedicating section of memroy as virtual disk, or RAM disk. 97

98 Various Disk-Caching Locations
Efficiency and Performance Various Disk-Caching Locations 98

99 Recovery 一致性检查 安全性写方式 备份 99

100 Recovery 一致性检查 检查必要性 一种检查方法 100

101 Recovery 必要性 磁盘块→内存→写回磁盘块 在写回之前，系统崩溃，则文件系统出现不一致。
因此，需要设计一个实用程序，当系统再次启动时，运行该程序，检查磁盘块和目录系统。 101

102 Recovery 一种检查方法 两张表，每块对应一个表中的计数器，初值为0。 102

103 103

104 104

105 105

106 106

107 Recovery 安全性写方式 对写操作进行逐个排序的写方式 谨慎写 更新磁盘的请求→按一定顺序完成几项子操作→更新磁盘
FAT文件系统：通写 磁盘修改立即写到磁盘 可恢复性好 速度性能差 107

108 Recovery 延迟写 利用回写高速缓存的方法得到高速 可恢复性差 108

109 Recovery 可恢复文件系统 采用事务日志来实现文件系统的写入 既考虑安全性，又考虑速度性能 109

110 Recovery 备份 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. 110