导图社区 操作系统期末重点复习思维导图
- 12
- 1
- 0
- 举报
操作系统期末重点复习思维导图
操作系统期末重点复习思维导图，如进程是程序的执行过程，是系统进行资源分配和调度的基本单位。
编辑于2023-06-07 15:46:35 四川省- 操作系统，期末重点
- 相似推荐
- 大纲
操作系统
磁盘存储器管理
外存的组织方式
连续组织方式（与内存管理对比）
为每个文件分配一组相邻接（连续）的磁盘块
形成的文件物理结构是顺序式文件结构
链接组织方式
为文件分配不连续的盘块，通过链接指针将一个文件的所有盘块链接在一起，所形成的物理文件称为链接文件
形成的文件物理结构是链接式文件结构
隐式链接
指针存放在每个盘块中，只适合于顺序访问
显式链接
指针显式地存放在内存的文件分配表FAT中
索引组织方式
把所有的磁盘块号放在一个索引块(表)中
形成的文件物理结构是索引式文件结构
二级索引
磁盘存储器管理（文件存储空间管理）
文件存储空间的基本分配单位是盘块（block）
空闲区管理
空闲区表法
系统为外存上所有空闲区建立一张空闲表，属于连续分配方式
分配与回收
n 分配类似于内存的分区动态分配，如首次适应算法和最佳适应算法等n 回收时，也类似于内存回收方法
空闲链表法
空闲盘块链
以盘块为单位链接起来
空闲盘区链
将所有空闲盘区（每个盘区可包含若干个盘块）链接起来
空闲盘块的分配与回收
分配盘区的方法与内存分区的动态分配方法类似
位视图法
Ø利用二进制的一位来表示磁盘中一个盘块的使用情况p当值为0时，表示对应的盘块空闲p当值为1时，表示已分配Ø磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图
空闲盘块的分配与回收
分配
Ø 顺序扫描位示图，从中找出一个或一组其值为0的二进制位Ø 将所找到的一个或一组二进制位，转换成与之相应的盘块号。假定找到的其值为0的二进制位，位于位示图的第i行、第j列，则其相应的盘块号为：b=n(i-1)+jØ 修改位示图，令map[i,j]=1
回收
Ø 将回收盘块的盘块号b转换成位示图中的行号和列号：l i=(b-1)div n+1 j=(b-1)mod n+1Ø 修改位示图，令map[i,j]=0
成组链接法
空闲盘块的组织
Ø文件区中的所有空闲盘块，被分成若干个组Ø将每一组含有的盘块总数N和该组所有的盘块号，记入其前一组的第一个盘块的S.free(0)~S.free(99)中。Ø将第一组的盘块总数和所有的盘块号，记入空闲盘块号栈中，作为当前可供分配的空闲盘块号Ø最末一组只有99个盘块
空闲盘块的分配与回收
分配
为用户分配文件所需的盘块时，须调用盘块分配过程来完成。该过程首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。若该盘块号已是栈底，即S.free(0)，这是当前栈中最后一个可分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号，因此，须调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。然后，再分配一相应的缓冲区(作为该盘块的缓冲区)。最后，把栈中的空闲盘块数减1 并返回。
回收
在系统回收空闲盘块时，须调用盘块回收过程进行回收。它是将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加1 操作。当栈中空闲盘块号数目已达100 时，表示栈已满，便将现有栈中的100个盘块号记入新回收的盘块中，再将其盘块号作为新栈底。
进程管理
前驱图与程序的执行
前驱图
一个有向无环图，用于描述线程之间执行的先后顺序
程序的顺序执行
顺序执行的三个特征：顺序性、封闭性、可再现性
子主题
程序的并发执行
并发执行的三个特征：间断性、失去封闭性、不可再现性
进程
进程的描述
定义
进程是程序的执行过程，是系统进行资源分配和调度的基本单位
每一个进程都有一个进程控制块PCB
特征
动态性，并发性，独立性，异步性
基本状态与转换
就绪、执行、阻塞
进程控制
基本概念
进程控制就是实现进程状态的转换
原语：一气呵成、不可中断（一种特殊的程序）
主要功能：管理系统中的所有进程
进程的创建
引起进程创建的事件：用户登录、作业调度、提供服务、应用请求
子主题
创建过程
1.申请空白PCB
2.为新进程分配其运行所需的资源
3.初始化PCB
4.若进程就绪队列可以接纳新进程，则将新进程插入就绪队列
进程的终止
引起事件：正常结束、异常结束、外界干预
终止过程
1.根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，并读取状态
2.若为执行状态，则立即终止其执行
3.若其有子孙进程，则还需一并终止
4.将其全部资源归还给父进程或系统
5.将其PCB从所在队列中移出
进程的阻塞与唤醒
引起事件：请求共享资源失败、等待某种操作完成、新数据未到达、等待新任务到达
子主题
阻塞：调用block原语将自己阻塞
唤醒：期待的数据到达时、有关进程调用wakeup原语见将等待该事件的进程唤醒
进程的挂起与激活
挂起：OS利用suspend将指定进程或处于阻塞的进程挂起
激活：OS利用active将指定的进程激活
进程通信
线程
线程的概念
调度的基本单位
并发性：一个进程的多个或所有线程并发执行
可拥有资源的独立单位
可独立调度和分配的基本单位
线程几乎不拥有资源，允许多个线程共享它们共属的进程所拥有的资源
独立性：共享进程的内存地址空间和资源
系统开销小
线程的实现
内核支持线程KST
线程管理的所有工作都由内核完成，应用程序只有一个到内核级线程的编程接口,因此内核级线程的切换必须在核心态下完成
用户级线程
应用程序从单线程开始,通过使用线程库设计成多线程程序，有关线程管理的所有工作都由应用程序完成
两种线程的组合方式
在同时支持用户级线程和内核级线程的系统中，可采用将n个用户级线程映射到m个内核级线程上(n>=m)
处理机调度与死锁
处理机调度
概念
处理机调度是按照一定的算法在就绪队列中选择一个进程并将处理机分配给它
层次
高级调度（作业调度）
低级调度（进程调度）
中级调度（内存调度）
调度算法
先来先服务算法
短作业优先算法
优先级算法
轮转调度算法
最早截止时间优先算法
死锁
概述
死锁的定义：每个参与竞争的进程都在互相等待,没有一个进程获得资源
产生死锁的条件
互斥条件：在一段时间内，某资源只能被一个进程占用
请求和保持条件：进程已占有至少一个资源，又去请求新的资源，但新的资源被其他进程占用，此时请求被阻塞，同时对自己占有的资源不释放
不可抢占条件:已获得的资源在未使用完之前不能被抢占，只能由进程使用完后自己释放
循环等待条件：死锁发生时必须存在一个“进程——资源”循环链
预防
破坏“请求和保持”：当一个进程请求资源时，它不能持有不可抢占资源
协议1：一次性申请运行过程中所需的全部资源
协议2：允许进程获得运行初期所需资源后，便开始运行；运行过程中逐步释放使用完的资源，再申请新的资源
破坏“不可抢占”:当进程申请的临界资源得不到满足时，立即释放所拥有的所有资源;
破坏“循环等待”:给资源编号，必须按编号从小到大的顺序申请资源
避免
安全状态
系统能按照一种资源分配顺序将资源动态地分配给每个进程，使每个进程最终都能顺利完成，就说此时系统处于安全状态
安全序列
资源分配顺序（进程推进顺序）
银行家算法P100
思想
当一个进程申请使用资源的时候，银行家算法通过先 试探 分配给该进程资源，然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待
数据结构
n为进程的数目，m为资源类型的数目Available: 长度为 m的向量。 如果available[j]=k,那么资源Rj有k个实例有效Max: n x m 矩阵。 如果Max[i,j]=k,那么进程Pi可以最多请求资源Rj的k个实例Allocation: n x m 矩阵。 如果Allocation[i,j]=k,那么进程Pj当前分配了k个资源Rj的实例Need: n x m 矩阵。如果Need[i,j]=k,那么进程Pj还需要k个资源Rj的实例Need [i,j] = Max[i,j] – Allocation [i,j]
安全算法
例子
检测与解除
检测
在资源分配图中找到一个既不阻塞也不孤立的进程节点Pi，在顺利的情况下，Pi可获得所需资源而继续运行，直至运行完毕，再释放其所占有得全部资源，这相当于消去pi所有的请求边和分配边，使之成为孤立的结点
解除
终止所有死锁进程
逐个终止死锁进程
进程同步
基本概念
互斥与同步：不同进程并发执行且存在不同的制约关系——互斥（竞争）与同步（协作）
临界区问题
临界资源：一次仅允许一个进程使用的资源称为临界资源，且必须互斥的对临界资源进行访问;在每个进程中，访问临界资源的那段代码称为临界区
临界区：进程中访问临界资源的那段代码
临界区问题
空闲让进
临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
忙则等待
当已有进程进入临界区,其他试图进入临界区的进程必须等待
有限等待
对请求访问的进程，应保证能在有限的时间内进入临界区
让权等待
当进程不能进入临界区时，应立即释放处理器，防止进程忙等待
进程同步机制
软件同步机制
硬件同步机制
信号量机制
信号量机制介绍
整形信号量
信号量S-整型变量-------可作为资源的数量提供两个不可分割的[原子操作]访问信号量wait(S) while s<=0 ; /*do no-op*/ s=s-1;signal(S)： s=s+1; Wait(s)又称为P(S)Signal(s)又称为V(S)
记录型信号量
每个信号量S除一个整数值S.value外，还有一个进程等待队列S.list，存放阻塞在该信号量的各个进程PCB信号量只能通过初始化和两个标准的原语PV来访问－－作为OS核心代码执行，不受进程调度的打断初始化指定一个非负整数值，表示空闲资源总数（又称为"资源信号量")若为非负值表示当前的空闲资源数若为负值其绝对值表示当前等待临界区的进程数，或者OS还欠进程的资源数量
AND型信号量
将进程在整个运行过程中需要的所有资源，一次性全部分配给进程，待进程使用完后再一起释放。对若干个临界资源的分配，采用原子操作。否则，有可能出现死锁在wait(S)操作中增加了一个“AND”条件，故称之为AND同步，或同时wait(S)操作Swait(Simultaneous wait)
信号量集
信号量的应用
利用信号量实现进程互斥/同步
经典问题P123~P131
生产者-消费者问题
哲学家进餐问题
读者-写者问题
存储器管理
存储器的结构层次
程序的装入与链接
地址绑定与内存保护
逻辑地址
由CPU产生的地址，即程序编译后使用的相对于0字节的地址
物理地址
物理内存的地址，内存以字节为单位编址
内存保护
目的
保护OS不被用户访问
实现
硬件，判断判断“基地址≤物理地址＜（基地址+界限地址）”是否成立
程序的运行步骤
编译
由编译程序对源程序进行编译，形成若干个目标模块
链接
由链接程序将目标模块和所需要的库函数链接在一起，形成完整的装入模块
装入
由装入程序将装入模块装入内存
程序的装入
绝对装入
编译时产生的地址使用绝对地址程序或数据被修改时，需要重新编译程序
可重定位装入
编译后的目标模块使用相对地址在装入时，完成重定位（静态重定位）需硬件支持（逻辑地址转换为物理地址的过程，称为重定位，也称为地址变换）
动态运行时装入
编译后的目标模块使用相对地址在运行时，完成重定位（动态重定位）
程序的链接
对换与覆盖
对换
覆盖
连续分配存储管理方式
单一连续分配
为一个用户程序分配一个连续的内存空间
固定分区分配
预先把可分配的主存储器空间分割成若干个连续区域，称为一个分区。每个分区的大小可以相同也可以不同。但分区大小固定不变，每个分区装一个且只能装一个作业。
可变分区分配
动态分区分配
根据进程的实际需要，动态地为之分配内存空间
分配算法
基于顺序搜索的动态分区分配算法Ø 依次搜索空闲分区链上的空闲分区，寻找一个其大小能够满足要求的分区Ø 首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法
基于索引搜索的动态分区分配算法Ø 提高搜索空闲分区的速度，在大、中型系统中采用Ø 快速适应算法、伙伴系统、哈希算法
动态重定位分区分配
紧凑
通过移动内存中的作业位置，以把原来多个分散的小分区拼接成一个大分区的方法，也叫“拼接
动态重定位
在指令运行时，实现地址转换(相对地址转换为绝对地址)
动态重定位分区分配算法
将空闲分区链以地址递增的顺序连接；在进行内存分配时，从链首开始顺序查找，直到找到一块分区的大小可以满足需求时，按照该作业的大小，从该分区中分配出内存，将剩下的空闲分区仍然链在空闲分区链中
离散分配存储管理方式
分页式存储管理方式
页面和物理块
页面
将进程的地址空间分成若干个页，每页加以编号，从0开始物理内存分成大小固定的块，称为物理块(frame)，同样加以编号，从0#开始
页面大小
太小，页表过长，占用内存过大，页内碎片增大大小一般为2的幂，通常为1KB、2KB、4KB、8KB
地址结构
页表
系统为每个进程建立了一张页表。逻辑地址空间内的所有页，依次在页表中有一表项，记录相应页在内存中对应的物理块号。
作用：实现从页号到块号的地址映射。
地址变换机构
基本的地址变换机构
具有快表的地址变换机构
二级页表
分段式存储管理方式
基本原理
在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息每个段都有自己的名字，通常用一个段号来代替段名，每个段都从0开始编址，并存储在一段连续的地址空间内段的长度由相应的逻辑信息组的长度决定，因此各段长度不等
地址结构
段表
在系统中为每个进程建立一张段映射表（段表），用于实现从逻辑段到物理内存区的映射
每个段在表中占有一个表项，记录了该段在内存中的起始地址（基址）和段的长度
段表保存在内存中，由控制寄存器保存其地址
地址映射
段页式存储管理方式
基本原理
分段和分页原理的结合，即先将用户程序分成若干段，再把每个段分成若干个页，并为每个段赋予一个段名
地址空间与结构
虚拟存储器（如何打通内存与外存）
虚拟存储器概述
常规存储器管理方式的特征
一次性
作业必须一次性全部装入内存方能运行
驻留性
作业装入内存后，整个作业一直驻留在内存
局部性原理
时间局部性
一条指令被执行了，则在不久的将来它可能再被执行。
空间局部性
若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用
基于局部性原理
应用程序在运行之前，没有必要全部装入内存，仅须将那些当前要运行的部分页面或段先装入内存便可运行，其余部分暂留在盘上
定义与特征
定义
具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统
特征
多次
作业中的程序和数据允许被分成多次调入内存运行
对换
作业运行时无须常驻内存
虚拟
从逻辑上扩充了内存容量，使用户看到的内存容量远大于实际内存容量
虚拟存储器的实现方法
请求分页系统
Ø 硬件支持：页表、缺页中断、地址变换机构Ø 软件支持：请求调页软件、页面置换软件
请求分段系统
Ø 硬件支持：段表、缺段中断、地址变换机构Ø 软件支持：请求调段软件、段置换软件
请求分页存储管理方式
硬件支持
请求页表机制
缺页中断机构
当要访问的页面不在内存中时，便产生一个缺页中断，请求OS将所缺页调入内存
Ø 在指令执行期间产生和处理中断信号Ø 一条指令在执行期间，可能产生多次缺页中断
地址变换机构
实现检索快表，试图从中找到要访问的页；若能找到，则修改页表项中的访问位，供页面置换算法选择换出页面时参考；对于写指令，还须将修改位置为1，表示该页调入内存后已被修改；最后页表项给出的物理块号和页内地址形成物理地址
内存分配
固定分配 局部（进程内部）置换
Ø 为每个进程分配一固定页数的内存空间，在整个运行期间都不再改变。如果进程在运行中发现缺页，则只能从该进程在内存的固定页面中选出一页换出，然后再调入另一页，保证分配给该进程的内存空间不变
可变分配 全局（全部内存）置换
Ø 为每个进程分配一定数目的内存空间；但当某进程发生缺页时，只允许从该进程所在内存的页面中选出一页换出，而不影响其它进程的运行。Ø OS不断评估该进程的分配情况，增加或减少分配给它的物理块，以提高整体性能
可变分配 局部（进程内部）置换
Ø 系统为每个进程分配一定数目的物理块，OS本身也保持一个空闲物理块队列。Ø 当某进程发现缺页时，系统从空闲物理块队列中，取出一物理块分配给该进程，并将欲调入的缺页装入其中。一个发生缺页的进程所拥有的内存物理块数量会逐渐增大。Ø 仅当空闲物理块队列中的物理块用完时，OS才能从内存中选择一页调出，该页可能是系统中任一进程的页。
物理块分配算法
平均分配
按比例分配
页面调入策略
何时调入
预调页策略
预先调入一些页面到内存
请求调页策略
发现需要访问的页面不在内存时，调入内存
从何处调入
请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区
如系统拥有足够的对换区空间，全部从对换区调入所需页面
如系统缺少足够的对换区空间，凡是不会被修改的文件，都直接从文件区调入；当换出这些页面时，由于未被修改而不必再将它们重写磁盘，以后再调入时，仍从文件区直接调入
UNIX方式：未运行过的页面，从文件区调入；曾经运行过但又被换出的页面，从对换区调入
何时调入
缺页率
访问页面成功(在内存)的次数为S访问页面失败(不在内存)的次数为F总访问次数为A=S+F缺页率为 f= F/A
例子
页面置换算法
最佳页面置换算法OPT
被置换的页将是之后最长时间不被使用的页，这是一种理想情况，无法实现的算法，可用来评价其他算法
先进先出页面置换算法FIFO
总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰
最近最久未使用页面置换算法LRU
选择最近最久未使用的页面予以淘汰
最少使用页面置换算法LFU
为内存中的每个页面设置一个移位寄存器，用来记录该页面的被访问频率，算法将最近时期使用最少的页面进行淘汰LFU 选择在最近时期使用最少的页面作为淘汰页
CLOCK页面置换算法
Ø 每个页都与一个访问位相关联，初始值位0Ø 当页被访问时置访问位为1Ø 置换时选择访问位为0的页 ；若为1，重新置为0
页面缓冲算法
抖动与工作集
抖动
一个进程的页面经常换入换出
根本原因
Ø同时在系统中运行的进程太多；Ø因此分配给每一个进程的物理块太少，不能满足进程运行的基本要求，致使进程在运行时，频繁缺页，必须请求系统将所缺页面调入内存
工作集
定义
在某段时间间隔Δ里进程实际要访问页面的集合
请求分段存储管理方式
硬件支持
请求段表机制
缺段中断机制
地址变换机构
分段的共享与保护
共享段表
共享段表的分配与回收
分段保护
输入/输出系统
I/O系统的功能、模型与接口
I/O系统的基本功能
I/O系统的层次结构与模型
I/O系统的接口
• 块设备
数据的存取和传输都是以数据块为单位的设备，如磁盘、光盘，通常用DMA I/O方式
• 流设备
数据的存取和传输都是以字符（流）为单位的设备，如键盘、打印机
• 网络通信接口
OS提供相应的网络软件和网络通信接口，以使计算机能通过网络同网络上的其他计算机进行通信，或上网浏览信息
I/O设备和设备控制器
I/O设备
设备控制器
概念
设备控制器是CPU与I/O设备之间的接口，接收从CPU发来的命令，并去控制I/O设备工作
主要功能
控制一个或多个I/O设备，以实现I/O设备和计算机之间的数据交换
内存映像I/O
I/O通道
I/O通道设备引入
是一种特殊的处理机，具有执行I/O指令的能力
I/O指令类型单一，与CPU共享内存
通道类型
字节多路通道
数组选择通道
数组多路通道
I/O通道的三种连接方式
多路复用
独立连接
DMA连接
I/O设备的三种控制方式
使用轮询的可编程
① 由CPU定时发出询问，询问设备是否忙，进程进入忙等② 不忙即进行I/O，否则转①
使用中断的可编程
当某进程要启动某个I/O设备工作时，便由CPU向相应的设备控制器发出一条I/O命令，然后立即返回继续执行原来的任务。设备控制器于是按照该命令的要求去控制指定的I/O设备。此时，CPU与I/O设备并行操作
直接存储器访问方式（DMA）
数据传输的基本单位是数据块p 所传送的数据是从I/O设备直接送入内存的，或者相反p 仅在传送一个或多个数据块的开始和结束时，才须CPU干预
I/O通道
引入
是DMA方式的发展，可进一步减少CPU的干预。是对一组数据块以读/写及有关的控制和管理为单位干预；可实现CPU、通道和I/O设备三者的并行操作
通道程序
由一系列通道指令所构成的。通道指令不同于CPU指令。指令包含：操作码、内存地址、计数、通道程序结束位P、记录结束位R
I/O软件
中断处理程序
设备驱动程序
与设备无关的I/O软件
用户层的I/O软件
缓冲区管理
磁盘性能概述与调度
磁盘结构
盘面
磁道
扇区
磁盘性能概述
数据的组织与格式
在磁盘上存储数据，必须先将磁盘格式化
如每条磁道含有30个固定大小的扇区，每个扇区容量为600个字节，其中512个字节存放数据，其余的用于存放控制信息
每个扇区包括2个字段：Ø 标识符字段：其中一个字节的SYNCH具有特定的位图像，作为该字段的定界符，利用磁道号、磁头号及扇区号三者来标识一个扇区；CRC字段用于段校验Ø 数据字段：存放512个字节的数据
磁盘类型
硬盘、软盘
单片盘、多片盘
固定头磁盘：每个磁道上都有一个读写磁头Ø 并行方式读/写，有效提高磁盘的I/O速度Ø 主要用于大容量磁盘移动头磁盘：每个盘面仅配有一个磁头，能移动寻道Ø 串行方式读/写，I/O速度较慢Ø 广泛应用于中、小型磁盘设备中
访问时间Ts+T+Tt
读写过程
Ø 磁头必须移动到所要求的磁道上Ø 并等待所指定的扇区的开始位置旋转到磁头下Ø 开始读写数据
寻道时间Ts
把磁臂（磁头）移动到指定磁道上所经历的时间
Ø 启动磁臂的时间kØ 磁头移动n条磁道所花费的时间
公式Ts=m×n+kØ m:常数，与磁盘驱动器的速度有关，对一般磁盘，m=0.2；对高速磁盘，m<=0.1Ø k:约2msØ 对一般温盘，寻道时间将随寻道距离的增加而增大，大体上是5~30ms
旋转时间T
把指定扇区移动到磁头下所经历的时间
T=1/2r
传输时间Tt
把数据从磁盘读出或向磁盘写入数据所经历的时间Tt的大小与每次所读写的字节数b和旋转速度有关r:磁盘每秒的转数N:一条磁道上的字节数
Tt=b/rN
磁盘调度
先来先服务FCFS
根据进程请求访问磁盘的先后次序进行调度
最短寻道时间优先SSTF
选择这样的进程，其要求访问的磁道，与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但不保证平均寻道时间最短
基于扫描的磁盘调度算法
SCAN
Ø 也称：电梯调度算法。Ø 不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头当前的移动方向。Ø 磁臂从磁盘的一端向另一段移动，沿途响应服务请求。当到达另一端时，磁头改变移动方向，继续处理。磁头在磁盘上来回扫描
CSCAN
Ø 磁头从磁盘一段移到另一端，随着移动不断的处理请求。不过，当磁头移到另一端时，马上返回到磁盘开始，返回时并不处理请求Ø 将柱面当作一个环链，将最后柱面和第一柱面相连
NStepSCAN
Ø “磁臂粘着”现象：进程反复请求对某一磁道的I/O操作；Ø 将磁盘请求队列分为若干个长度为N的子队列；Ø 按FCFS算法依次处理子队列；Ø 每个子队列使用SCAN算法。
FSCAN
Ø 是N步SCAN算法的简化；Ø 请求队列分为两个子队列： 一是当前所有请求队列，按SCAN算法调度； 二是扫描期间，新出现的请求队列，推迟到下一次扫描时处理。
文件管理
文件和文件系统
文件
数据项
基本数据项
描述一个对象的某种属性，又称字段
组合数据项
由若干个基本数据项组
关键字
为唯一标志一个记录，在各个数据项中确定出一个或几个数据项（组成的集合）
记录
记录是一组相关数据项的集合，用于描述一个对象在某方面的属性
文件
定义
具有文件名的一组相关元素的集合
有结构文件中文件由若干相关记录组成、无结构文件则被看成一个字符流
文件的属性
文件类型
文件长度
文件的物理位置
文件的建立时间（最后一次修改时间）
文件系统
层次结构
对象及其属性
对象：文件、目录、磁盘存储空间
对对象操纵和管理的软件集合Ø 文件管理系统的核心部分
文件系统的接口
Ø 命令接口Ø 程序接口
功能
Ø 对文件存储空间的管理Ø 对文件目录的管理Ø 用于将文件的逻辑地址转换为物理地址的机制Ø 对文件读和写的管理Ø 对文件的共享和保护
文件操作
创建文件、删除文件、读文件、写文件
文件的“打开”和“关闭”操作
Ø 打开open：系统将文件从外存拷贝到内存打开文件表的一个表目中。Ø 关闭close：把文件从打开文件表的表目中删除
其他文件操作
Ø 重命名、改文件拥有者、查询文件状态等。Ø 创建/删除目录
文件的逻辑结构
无结构文件（流式文件）
源程序、可执行文件、库函数
有结构文件
定长记录
指文件中所有记录的长度都是相同的（可有效提高检索效率与速度）
变长记录
文件中的各记录长度不相同
有结构文件（按文件的记录方式分类）
顺序文件
顺序文件的排列方式
串结构
顺序结构
寻址
隐式寻址
显式寻址
索引文件
按关键字建立索引
Ø 为变长记录文件建立一张索引表Ø 索引表按关键字排序Ø 实现直接存取
具有多个索引表的索引文件
Ø 为顺序文件建立多个索引表Ø 为每一个可能成为检索条件的域配置一张索引表
索引顺序文件
特征
引入文件索引表
通过该表实现随机访问
增加溢出文件
用于记录新增、删除和修改的记录
一级索引顺序文件
Ø 如果在一个顺序文件中所含有的记录数为N，则为检索到具有指定关键字的记录，平均须查找N/2个记录；Ø 对于索引顺序文件，则为能检索到具有指定关键字的记录，平均只要查找sqrt(N) 个记录数，因而其检索效率比顺序文件约提高sqrt(N)/2倍
二级索引顺序文件
为索引文件再建立一张索引表，从而形成两级索引表两级索引表 (3/2)(N)^(1/3)
直接文件
哈希文件
文件目录
概念
目录是一种数据结构，用于标识文件及其物理地址
对目录管理的要求
Ø 实现“按名存取”Ø 提高对目录的检索速度Ø 文件共享Ø 允许文件重名
文件控制块与索引节点
文件控制块FCB
管理和控制文件的数据结构，与文件一一对应
文件目录
文件控制块的集合，即一个文件控制块就是一个文件目录项
目录文件
文件目录也被看做是一个文件
索引节点
引入目的
减少磁盘访问次数
索引节点
把文件名与文件描述信息分开，文件描述信息用索引节点（iNode）保存，简称为i节点（UNIX）
例子
磁盘索引结点
存放在磁盘上的索引结点
①文件拥有者标识符，②文件类型， ③文件存取权限， ④文件物理地址，⑤文件长度， ⑥文件连接计数，⑦文件存取时间
内存索引结点
存放在内存上的索引结点
①索引节点编号，②状态， ③访问计数， ④文件所属文件系统的逻辑设备号⑤链接指针
单级目录文件
两级目录文件
树型目录
绝对路径名
从根目录开始的路径名
相对路径名
从当前目录开始的路径名
无环图目录
目录查询技术
线性（顺序）检索法
Hash方法
建立一张Hash索引文件目录，则可利用Hash方法进行查询，即系统将用户提供的文件名变换为文件目录的索引值，再利用该索引值到目录中去查询
文件的共享保护
利用有向无环图实现共享
利用符号链接实现共享
分页分段区别