操作系统设计与实现(第五章)

1、操作系统设计与实现,主讲教师：徐战亚 Email ：zhanyaxu,第五章 文件系统,文件概念的引入： 由于进程的运行空间太小，使得进程运行后的结果无法存放，应用系统中的重要数据无法保存，另外单个进程控制的数据无法同时被其他进程使用提出了必须对这些信息有控制性的组织和存放的要求。 需要满足的条件： *能够存储大量的信息； *进程使用信息后，即使结束，也该保存好信息； *多个进程可以并发的存取信息。 在此基础上，引入了文件的概念。,文件的控制和管理,文件在操作系统中，作为信息的一种组织者和承担者存在，它不受一般进程的影响，为进程提供信息，也可以在权限的允许下被进程修改或添加； 文件的管理是由操

2、作系统来实现的，因此，文件的组织结构、命名规则、存取控制、安全保护等等都是由操作系统设计时要考虑解决的，整个处理文件的模块称为文件系统（file system）。,5.1 文件,文件: 一组带标识的在逻辑上有完整意义的信息项的序列，这个标识为文件名。 信息项：构成文件内容的基本单位 长度：单个字节，或多个字节 文件内容的意义：由文件的建立者和使用者解释 把信息以一种单元，即文件的形式存储在磁盘或其他外部介质上。 文件是通过操作系统来管理的，包括： 命名，文件的结构，存取，使用，保护和实现方法。,5.1.1 文件命名,相同点： 都支持18个字母组成的字符串作为合法文件名。 不同点： 系统不同，规

3、则不同： 文件名长度、文件名大小写、 文件扩展名：一个或多个、特殊扩展名的使用 aa.tar.gz .cpp .c,5.1.2 文件结构,文件可由很多方式构成，常见的有三种：,a ：无结构字节序列：操作系统不关心文件内容，所有的含义都在用户的程序中，用户可以方便的修改文件的内容，任意删减，同时，系统也无法提供帮助和支持。在UNIX、DOS、及WIN95中使用。 b ： 记录序列结构：文件有一些固定长度的记录序列组成，每次读都返回一条记录，写操作是对记录的修改或追加。 如CP/M系统即是用这种思想，每条记录由128个字符组成一条记录。 c ： 记录树结构：文件由一棵记录树构成，每个记录的长度可不

4、同，但每个记录的固定位置都有一个关键字域，记录树按照关键字排序，这种结构非常便于检索信息，而且此时操作系统负责记录存放的位置。,5.1.3 文件类型,操作系统一般都支持多种类型的文件，对于UNIX系统，文件一般包括正规文件、目录文件、设备文件（字符设备、块设备)。 正规文件：包含有用户信息的文件（与用户使用紧密相关的，包含有用户数据）。 目录文件：使用来管理文件系统结构的文件； 设备文件：用来模拟外部I/O设备或磁盘。 主要研究正规文件。,一般的正规文件ASCII文件或二进制文件， 对于ASCII文件，一般文件由多行组成，换行的时候可以用回车符，也可以用换行符，依系统而定，每行长度可不同，优点

5、为：方便编辑，可以原样打印。 对于二进制文件，很难直接读懂，均由混乱的字符组成，不同的二进制文件，有着不同的内部结构，有对应的程序去读取、修改、执行。 看课本 P295 图5.3 （中文） P406 图5.3（英文）,第一种可执行文件，由五部分组成，每部分有不同含义，程序装入内存后，根据这五部分的内容进行重定位，来运行程序。 第二种存档文件，由许多编译过但未链接的库过程或模块组成，每个模块以模块头开始，列出了模块名、创建时间、拥有者、保护代码、模块长度等信息。 操作系统中的可执行文件：操作系统自己的执行文件，保持最新的文件执行，采用检查源文件的方式，类似于makefile文件的思想。,WIND

6、OWS系统执行时，根据文件的扩展名来判断该启动哪个应用程序，当扩展名不正确时，无法启动那个应用程序，如果强制转换，那么修改后的文件即使能启动程序，也不能正确的读取。,5.1.4 文件存取,早期的系统只能够进行顺序读取，从文件的开始处读取文件中的信息，如果需要的话，就多次读取，这种方式非常适合磁带。 现在的系统利用磁盘来存储，故顺序读取不是种高效的方式，即出现了随即存储，这时可以以任意的顺序来读取文件（数据库系统中尤为重要）。,5.1.5 文件属性,文件除了文件名和数据外，还有很多操作系统赋予的属性，创建日期、文件长度等，这些额外的属性称为文件属性。,flag length time,5.1.6

7、 文件操作,文件作为信息的载体，即为了存储也为了检索，系统不同，采用的手段也有差异，通用的操作一般 有： 1.CREATE 7.APPEND 2.DELETE 8.SEEK 3.OPEN 9.GET ATTRIBUTE 4.CLOSE 10.SET ATTRIBUTE 5.READ 11.RENAME 6.WRITE,5.2 目录,在多数系统中，目录也是一种文件。,1. 文件控制块（FCB）：文件控制块是操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息，文件控制块是文件存在的标志。,文件控制块的内容： 文件名，文件号，用户名，文件地址，文件长度，文件类型，文件属性，共享计

8、数，文件的建立日期，保存期限，最后修改日期，最后访问日期，口令，文件逻辑结构，文件物理结构,2. 文件目录：把所有的FCB组织在一起，就构成了文件目录，即文件控制块的有序集合 3. 目录项：构成文件目录的项目（目录项就是FCB）,5.2.1 层次目录系统,a ：最早最简单的组织方式：这种系统，只需要维护一个单独的目录，里面包含着所有用户的文件，如果用户变多，当使用同样的文件名时，就出现了混乱，系统就无法工作。 b ：较好的方式：按照用户来管理，给每一个用户一个目录，每个用户的文件就放在他们自己的目录下，此时所有的文件都是平行的，相互的关系没法组织管理，缺乏条理性。 c ：较为理想的方式：每个用

9、户有自己的目录，并且可以在自己的目录下创建新的目录，并且可以按照自己的方式组织自己的文件。,5.2.2 路径名,绝对路径: 最常见且是最直接的方式，来指明文件的具体位置; DOS中的分隔符 / UNIX中的分隔 E:Backupexecfiletest.exe /etc/xinetd.d/telnet / 表示根目录（限于UNIX）,相对路径：和工作目录一起使用，相对于工作目录的路径； 如工作目录为： /usr/ast cp /usr/ast/mailbox /usr/ast/mailbox.bak 等效于 cp mailbox mailbox.bak,特殊目录： 在创建目录的时候，默认会出现

10、的目录： . 表示当前的目录 . 表示父目录 如果用cd . 表示退回到父目录 /usr 如果用cd . /lib/dict 表示到了 /usr/lib/dict/ cp /usr/lib/dict . 将/usr/lib/dict 下所有文件拷贝到/usr/ast/下，文件名不变化,5.2.3 目录操作,不同的系统，对目录操作也有很大差别，通用的操作一般有： 1.CREATE (MKDIR) 6.RENAME 2. DELETE 7.LINK 3.OPENDIR 8.UNLINK 4.CLOSEDIR 5.READDIR,5.3 文件系统的实现,主要包括文件如何存储、磁盘空间如何分配管理、系

11、统如何高效。,5.3.1 实现文件,文件的实现主要指文件中的数据如何在磁盘上存储的，系统怎样对数据进行添加、修改、检索。,常用的方法一般有以下几种： 连续分配、链接表分配、使用索引的链接表分配、i节点等,*连续分配 将文件做成连续的数据块放到磁盘上，根据磁盘上块的大小来划分本身。 优点：记录每一个文件只需要记录每个文件的第一个存储块地址，在一次操作中就可以完成整个文件的读取。 缺点：一次存储困难，除非文件的大小不再变动，而且文件的大小必须预先知道；另外，此方案会产生磁盘碎片，浪费空间。,*链接表分配 是第一种方案的改进，存放不再连续，而是通过链接表来将各个分散的块链接起来，每块的第一个字用来指

12、向下一个指针，其余部分存放数据。,优点：除了内零头外，可以充分利用磁盘空间，不再有明显的碎片，记录此文件的位置只需要记录第一块的地址即可，顺序读取方便。 缺点：随机的存取困难，另外由于指针占用了字节，在寻址和取数据时要花费时间来把他们分开，由于不再是2的幂，效率很难提升。,*使用索引的链接表分配 在内存中建立每个磁盘块的指针，并通过在内存中建立索引，将指针放入索引表，就可以方便地检索到每个文件所有的磁盘块实现随机存取。,内存表的链接表分配,每一项中的内容都是指向了下一物理块的地址，在这个表中检索很快，虽然也要顺着链移动，但在内存中的速度就实现的很快。,缺点：磁盘大的时候，链接表就变得很庞大，放

13、入内存就要占用很大的空间。（MS-DOS利用了大块的方法来避免过大的表）,*i节点 给每个文件赋予一张小型索引表，列出文件的属性和各个块在磁盘上的地址。（每个文件包含哪些磁盘块） 每个文件都有这样的表，当文件小的时候，开始的磁盘地址都可以在这个节点表中获得，当文件大的时候，就需要间接块。,一级间接块包含着附加的磁盘地址，二级间接块包含很多一次间接块的地址，同样，三级间接块包含很多二级间接块的地址。,5.3.2 实现目录,目录文件：为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存，这个文件就叫目录文件。 目录项：构成文件目录的项目（目录项就是FCB） 根据用户给出的路径名找到相应的

14、目录项，从中找到所需要的信息。系统不同，提供的信息也有差别，总之，目录项的功能就是将用户提供文件名映射成为查找文件数据所需要的信息。 相关的问题就是文件的属性该放到何处，是放到目录项中还是放到别的地方？,*CP/M中的目录,用户码,1,8,3,1,2,块数,文件类型（扩展名）,范围,磁盘块号（16）,该系统的目录结构最为简单，系统中只有一个目录，文件系统只需查找这个唯一的目录，当找到对应的目录项的时候，也就知道了文件的磁盘号。 当文件过大，目录项中容不下过多的磁盘号的时候，就为这个文件分配额外的目录项。,*MS-DOS中的目录,属于层次目录系统，这个目录项中保存第一个磁盘块的块号，参照5.9中

15、的链接方式可以找到文件的所有的磁盘块。,*UNIX中的目录,UNIX的目录结构简单，每个目录项包含一个文件名和这个文件的i节点号,打开文件的时候，文件系统根据给出的文件名找到它所在的磁盘块。,对于查找路径名/usr/ast/mbox , 具体的步骤为： 先找到根目录（UNIX中，根目录的i节点的位置是固定的），根据根目录中查找路径的第一部分/usr，随即获得/usr 的i节点号，然后根据此节点号定位到此节点，根据此i节点，找到目录/usr，接着查找下一部分ast，同样地，一直定位到mbox，将文件mbox的节点读入内存， 并保存，直至关闭此文件。,5.3.3 磁盘空间管理,磁臂,由于连续的存储

16、文件会导致文件增大时文件的整体移动，一般的系统的文件都采用分块存储的方式。但这又会引入新的问题：块大小的衡量 *块大小 块过大，对于平均文件较小的系统来说，磁盘空间的浪费是非常严重的，但如果块过小，每个文件则需要许多个块才能存储，那取出时的效率则会非常低。而磁盘空间的利用率和读取磁盘数据的速率是相背 的。,当空间利用率降低的同时，磁盘数据的读取速率也在提高，因此时间效率和空间效率本质上是相背的。 故需要些折中的办法，把块分为512、1K或2K字节，如果在扇区大小为512自己的磁盘选择1K大小的磁盘块时，系统常连续需要连续读取两个扇区，并把他们认为是一个单元。,*记录空闲块,常用的方法是链接表和

17、位图法 链接表： 把所有空闲块链成一个链 位图法： 用一串二进制位反映磁盘空间中分配使用情况, 每个物理块对应一位, 分配物理块为1，否则为0 申请物理块时，可以在位示图中查找为0的位，返回对应物理块号； 归还时；将对应位转置0 描述能力强，适合各种物理结构,5.3.4 文件系统的可靠性 可靠性：系统抵抗和预防各种物理性破坏和人为性破坏的能力 1. 坏块问题 2. 备份 通过转储操作，形成文件或文件系统的多个副本,海量转储：定期将所有文件拷贝到后援存储器。 增量转储：只转储修改过的文件，即两次备份之间的修改，减少系统开销。,*文件系统的一致性 磁盘块-内存-写回磁盘块 若在写回之前，系统崩溃，

18、则文件系统出现不一致 * 设计一个实用程序，当系统再次启动时，运行该程序，检查磁盘块和目录系统,UNIX一致性检查工作过程： 两张表，每块对应一个表中的计数器，初值为0 表一：记录了每块在文件中出现的次数 表二：记录了每块在空闲块表中出现的次数,5.3.5文件系统的性能问题 磁盘服务：其速度和可靠性成为系统性能和可靠 性的主要瓶颈 设计文件系统时应尽可能减少磁盘访问次数,*块高速缓存 系统在内存中保存一些块，逻辑上它们属于磁盘 检查所有的读请求，看所需的块是否在高速缓存中。如果在，则可直接进行读操作。否则，首先要将块读到高速缓存，再拷贝到所需的地方 如果高速缓存已满，则需要进行淘汰,高速缓冲区

19、内 的被修改过的内容得保持更新问题，如果更新的慢的话，系统发生崩溃时，会有大的数据丢失，故系统需要保证数据较及时地被写回磁盘，对于系统不同，方案也不同： UNIX：采用SYNC，在30 s内调用一次，将数据更新，即使崩溃，也是短时间内的数据； MS-DOS：采用直写高速缓存，修改过的数据立即被写回磁盘，但这导致了大量的磁盘I/O访问。,* 合理分配磁盘空间 分配块时，把有可能顺序存取的块放在一起，最好在同一柱面上，从而减少磁盘臂的移动次数。,5.3.6 日志结构的文件系统 随着硬件性能的提高，假想系统可以采用预读方式将文件和所需的数据块全部读入高速缓存，从而减少硬件上磁盘的寻道延迟和旋转延迟，

20、从而使系统的性能提高。,5.7.3 磁盘调度 1. 磁盘调度 当多个访盘请求在等待时，采用一定的策略，对这些请求的服务顺序调整安排，旨在降低平均磁盘服务时间，达到公平、高效 公平：一个I/O请求在有限时间内满足 高效：减少设备机械运动所带来的时间浪费,2. 磁盘调度考虑的问题： 一次访盘时间 = 寻道时间+旋转延迟时间+存取时间 (1) 减少寻道时间（活动头磁盘） (2) 减少延迟时间（固定头磁盘）,3. 磁盘调度算法 (1) 先来先服务：按访问请求到达的先后次序服务 优点：简单，公平； 缺点：效率不高，相临两次请求可能会造成最内到最外的柱面寻道，使磁头反复移动，增加了服务时间，对机械也不利,

21、假设磁盘访问序列：98，183，37，122，14，124，65，67 读写头起始位置：53 安排磁头服务序列 计算磁头移动总距离（道数）,(2) 最短寻道时间优先：优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先 优点：改善了磁盘平均服务时间； 缺点：造成某些访问请求长期等待得不到服务,(3) 扫描算法（电梯算法） 克服了最短寻道优先的缺点，既考虑了距离，同时又考虑了方向 具体做法：当设备无访问请求时，磁头不动；当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务，如此

22、反复,5.4 安全性,5.4.1 安全环境,文件系统是操作系统中用户信息的收集和管理中心，它的安全性的高低直接影响到操作系统的安全性的高低。,1.安全性（security） 确保未经授权的用户不能存取某些文件。涉及到技术、管理、法律、道德和政治等问题。 2.保护机制（protection mechanism） 指用于保护计算机信息的特定操作系统机制。,安全性的两个重要方面： * 数据丢失 灾难 硬件或软件故障 人的失误 可通过备份解决（存放在另一处）,*入侵者 积极的或消极的 非技术人员的偶然窥视 入侵者的窥视 明确的偷窃企图 商业或军事间谍活动 设计安全时要考虑是哪一类入侵者,2.著名的安全

23、缺陷 UNIX lpr 早期的允许打印后删除文件，任何人都可以执行，则打印完后口令文件后即可删除口令文件。 UNIX mkdir mkdir是root用户使用的命令，在创建一个i节点后，将文件的权限由超级用户转为实际的用户，实际的操作有mknod，chown等几个步骤，在这些时间差中把握机会，就可以先删除此文件，再建立一个同名的链接，链接到口令文件，就获得对口令文件的权限。,TENEX,使用分页系统，存取文件时，系统检测用户口令，且是一个一个字符检测，错了就就退出，因此，可以作以下设计：,OS/360 读取文件时的设计缺陷： 第一次判断时需要用户输入口令，然后操作的时候就不需要了，它会再次读文

24、件名（文件名没有被保存在内部），但此时文件名被磁盘驱动器重新修改了，漏洞就出现了。 另外的一些常见安全性问题： 特洛伊木马 Logic bomb：逻辑炸弹 Morris：蠕虫导致了CERT的建立 （Computer Emergency Response Team ） 计算机紧急事件反应组,3.一般性的安全攻击,* 请求内存页、磁盘空间和磁带并读取其内容 （许多系统分配时不清除以前内容） * 尝试非法的系统调用（非法参数 、不合适的参数） ASP早期的安全性漏洞属于此类 * 在登录过程中键入DEL，BREAK * 写一段程序欺骗用户 假的login窗口 * 非法手段人为通过不称职管理员或相关人员

25、获取口令或修改系统。,* 病毒,特殊的安全性攻击，目前最为普遍的，文件病毒、CIH、网页病毒、恶意代码等。 一般的预防方法是利用杀毒软件，但一般只能查杀已知的病毒，对于新出现的无法杀掉，因此必须保证病毒码最新。 另外的办法是对一般的二进制文件进行写保护，这在UNIX系统容可以实现，但在DOS中不能保证。,5.4.4 安全性的设计原则 * 系统设计必须公开 * 缺省属性应该不可访问 * 检查当前权限，不应检查后再在以后使用 * 给每个进程赋予一个最小的可能权限 * 保护机制应简单一致，嵌入到系统底层 * 采取的方案必须可接受，利于用户使用,5.4.5 用户验证 当用户登录时，检验其身份 （用户是

26、谁，用户拥有什么，用户知道什么） （1）口令 最广泛的认证方式，破解的方式一般采用字典，收集可能的组合，去进行尝试，是种很有效的方法，所以只能使用一些方法使破解的速度变慢，比如随机数加密（盐渍），UNIX中使用此方法，另外利用一次性口令（口令书），或者问题集、查问回答等方法都是较为有效地口令加密方法。,（2）物理鉴定 磁卡，容易被破解，因此常跟口令加密一起使用。 指纹、视网膜、声波等加密，很难实现，同样破解也很困难。 签名分析，手指长度分析。 特殊的物理认证DNA。,（3）对 策 对登录的次数进行检测，当超出登陆错误次数的时候即发出警告或采取一定的措施； 也可以采取登陆陷阱，诱捕入侵者。,5.5 保护机制,策略：哪些该保护，禁止谁访问 机制：如何实现保护,5.5.1 保护域 计算机中的需要保护的对象：硬件或软件，CPU、内存、硬盘、文件、数据、