武汉大学 操作系统期末考试复习笔记 - 图文(8)

采用如下引用串讨论页置换算法：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1（分配3个可用帧）

先进先出置换算法（FIFO）

(会有15次页面错误)（注：计算页面错误时，注意前三个必产生3个页面错误） Belady异常：页错误率可能随分配的帧数的增加而增加

最优置换（OPT算法/MIN算法）（不会有belady异常）产生的页错误率最低 置换最长时间不会用到的页（看未来） 难实现

LRU页置换 最近最少使用算法。可以画栈看会有多少页面错误

近似LRU算法：附加引用位算法（被使用过就标记1并添置高位（前八位）舍弃最后一位），二次机会算法，增强型二次机会算法

基于计数的页面置换：最不经常使用算法（LFU），最常使用页置换算法（MFU）

页面缓冲算法：页面缓冲算法是FIFO算法的发展。它在系统中保存一个空闲帧缓冲池。

页面缓冲置换算法采用FIFO选择被置换页面，选择出的页面不是立即换出，而是放入空闲帧池。

帧分配

帧的最小数量：分配的帧要大于最少数量（不然产生太多的页面错误）

分配算法：平均分配，比例分配（根据进程大小，将可用的帧分给每个进程），按优先级分配

全局分配与局部分配 固定分配和可变分配

将分配策略和置换范围组合可得如下三种策略： 固定分配局部置换 可变分配全局置换 可变分配局部置换

颠簸/抖动：频繁的页调度行为而几乎不能完成任何有效的工作。如果一个进程在换页上用的时间多于执行的时间，那么这个进程就在颠簸。

Chapter 10 文件系统接口

文件系统：操作系统中与管理文件有关的软件和数据的集合。 文件系统负责管理外存上的文件，并为用户提供对文件进行存取、共享及保护的手段。

文件是具有文件名的一组相关信息的集合，文件存放在外存上的。 文件由若干记录组成。

记录是一些相关数据项的集合。

数据项是数据组织中可以命名的最小逻辑单位。

文件属性包含：名称，标识符，类型，位置，大小，保护，时间日期和用户标识 所有的文件的属性信息都保存在目录结构中

通常目录项包含文件名及标识号，而标识号定位文件其他属性信息。

文件操作：建立，删除，读，写，打开，关闭（文件的操作除了正常的访问之外，还要包括对目录项的操作）

在文件内重定位：搜索相应的目录表项，设置当前文件指针给定值

文件类型：实现文件类型的常用技术是在文件名称内包含类型：如名称.扩展名

文件分类方法

按用途分类：系统文件（系统软件构成的文件），库文件（系统提供给用户使用的各种标准过程、函数和应用程序），用户文件（用户委托文件系统保存的文件） 按保护级别分类：只读文件，读写文件，执行文件（允许核准用户调用执行，但不允许读写），不保护文件（不加任何访问限制） 按信息流向分类：输入文件（来自输入设备的文件），输出文件，输入输出文件（如磁盘上的文件，可以读也可以写）

按数据形式分类：源文件（由源程序和数据构成的文件），目标文件（源程序经过编译但未链接成可执行代码的目标代码文件），可执行文件（链接过的可运行文件）

文件结构：

逻辑结构：又称文件组织，是从用户观点出发所看到的文件组织形式。 物理结构：又称文件的存储结构，是文件在外存上的存储组织形式。 文件的逻辑结构：记录式文件（有结构文件），流式文件（无结构文件，由字符序列构成）

记录式文件的组织方式：顺序文件（顺序排列，记录通常是定长的），索引文件（有索引表），索引顺序文件（分组顺序排列，索引） 文件的物理结构：顺序结构（连续），链接结构（指针），索引结构（索引表）

文件存取方法：顺序存取法（按照文件中记录的顺序依次访问），直接存取法（任意顺序快速读写），按键存取法

目录：用来组织文件。目录可看作符号表，它能将文件名称转换成目录项。