2022年操作系统复习笔记 .pdf

第一章操作系统引论OS作为用户与计算机硬件系统之间的接口， OS处于用户与计算机硬件系统之间，用户通过 OS来使用计算机系统单道批处理系统：单道性顺序性自动性多道批处理系统：多道性无序性调度性分时系统满足用户请求特征：多路性独立性及时性交互性实时系统即时处理完成截止时间开始截止时间操作系统的特征并发性：与并行不同共享性：互斥共享同时访问异步性：表现为“走走停停”虚拟性：指通过某种技术把一个物理实体变为若干个逻辑上的对应物通过虚拟存储器技术，将一台机器的物理存储器变为虚拟存储器，以便从逻辑上来扩充存储器的容量。操作系统功能处理机管理：进程管理（进程控制进程同步进程通信进程调度）存储管理：内存分配内存保护内存扩充地址映射设备管理：缓冲管理（单缓冲双缓冲缓冲池）设备分配（设备控制器通道）设备处理虚拟设备文件管理操作系统和用户接口用户接口脱机用户接口联机用户接口程序接口图形接口第二章进程管理程序的顺序执行及其特征顺序性：封闭性：可再现性：前趋图 (Precedence Graph) 是一个 有向无循环图 ， 记为 DAG(Directed Acyclic Graph) ，用于描述进程之间执行的前后关系名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 32 页 - - - - - - - - - 偏序关系程序的并发执行及其特征间断性失去封闭性不可再现性进程的特征和定义进程是程序在 一个数据集合上 运行的过程，它是系统进行资源分配和调度的一个独立单位结构特征动态性并发性独立性异步性进程的三种基本状态就绪执行阻塞挂起态 ：把暂时无法执行的进程从内存调出到外出提高内存利用率进程控制块 PCB 进程标识符用于惟一地标识一个进程名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 32 页 - - - - - - - - - 处理机状态信息主要是由处理机的各种寄存器中的内容组成的OS是根据 PCB来对并发执行的进程进行控制和管理的进程控制块的组织方式链接方式索引方式原语：由若干条指令组成的，完成一定功能的一段程序。原子性进程的创建 (Creation of Progress) (1)申请空白 PCB 。(2) 为新进程分配资源。(3) 初始化进程控制块。(4) 将新进程插入就绪队列，如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列进程的终止正常结束异常结束外界干涉进程的终止过程(1) 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB ，从中读出该进程的状态。(2) 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。(3) 若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程 。(4) 将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。(5) 将被终止进程 (它的 PCB) 从所在队列 (或链表 )中移出，等待其他程序来搜集信息。进程阻塞过程阻塞原语 block 进程的阻塞是进程自身的一种主动行为先立即停止执行， 把进程控制块中的现行状态由“ 执行” 改为阻塞， 并将 PCB插入阻塞队列进程唤醒过程调用唤醒原语wakeup( )，将等待该事件的进程唤醒。唤醒原语执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪， 然后再将该 PCB插入到就名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 32 页 - - - - - - - - - 绪队列中进程的挂起系统将利用挂起原语suspend( )将指定进程或处于阻塞状态的进程挂起进程的激活过程系统将利用激活原语active( )将指定进程激活。激活原语先将进程从外存调入内存， 检查该进程的现行状态， 若是静止就绪， 便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞进程同步两种形式的制约关系间接相互制约关系：竞争临界资源比如打印机直接相互制约关系：协同工作临界资源：一次只允许一个进程访问进入区临界区退出区剩余区同步机制应遵循的 规则：空闲让进忙则等待有限等待让权等待信号量机制解决进程问题整型信号量：违反了“让权等待”规则名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 32 页 - - - - - - - - - 记录型信号量： wait（s） ，signal（s）语句AND型信号量：将进程在整个运行过程中需要的所有资源，一次性全部 地分配给进程，待进程使用完后再一起释放。 只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。 亦即，对若干个临界资源的分配， 采取原子操作方式： 要么全部分配到进程，要么一个也不分配Swait(S1, S2, , Sn) if Si1 and and Sn1 then for i = 1 to n do Si= Si-1; endfor else place the process in the waiting queue associated with the first Sifound with Si1, and set the program count of this process to the beginning of Swait operation endif Ssignal(S 1, S 2, , S n) for i= 1 to n do Si=Si+1; Remove all the process waiting in the queue associated with Si into the ready queue. endfor; 信号量机制Swait(S1, t1, d1, , Sn, tn, dn) if Sit1and and Sntn then for i=1 to n do Si=Si-di; endfor else Place the executing process in the waiting queue of the first Si with Siti and set its program counter to the beginning of the Swait Operation. endif signal(S1, d1, , Sn, dn) for i =1 to n do Si = Si+di; Remove all the process waiting in the queue associated with Si into the ready queue Endfor 一般“ 信号量集 ” 的几种特殊情况：(1) Swait(S, d, d)。 此时在信号量集中只有一个信号量S， 但允许它每次申请 d 个资源，当现有资源数少于d 时，不予分配。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 32 页 - - - - - - - - - (2) Swait(S, 1, 1)。 此时的信号量集已蜕化为一般的记录型信号量(S 1时)或互斥信号量 (S=1时)。(3) Swait(S, 1, 0) 。这是一种很特殊且很有用的信号量操作。当S1 时，允许多个进程进入某特定区； 当 S变为 0 后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。Var mutex:semaphore = 1; begin parbegin process 1: begin repeat wait(mutex); critical section signal(mutex); remainder seetion until false; end process 2: begin repeat wait(mutex); critical section signal(mutex); remainder section until false; end parend 利用信号量实现前趋关系管程机制 局部于管程的共享变量说明； 对该数据结构进行操作的一组过程 对局部于管程的数据设置初始值的语句。此外，还须为管程赋予一个名字。进程通信（1）共享存储器系统基于共享数据结构的通信方式。基于共享存储区的通信方式（2）消息传递系统直接通信方式Send(Receiver, message); 发送一个消息给接收进程；Receive(Sender, message); 接收 Sender发来的消息名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 32 页 - - - - - - - - - 间接通信方式Send(mailbox, message); 将一个消息发送到指定 信箱；Receive(mailbox, message); 从指定信箱中接收一个消息邮箱分为私有邮箱，公共邮箱，共享邮箱。（3）管道 (Pipe)通信所谓“ 管道” ，是指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件，又名 pipe 文件。向管道(共享文件 )提供输入的发送进程(即写进程 )， 以字符流形式将大量的数据送入管道；而接受管道输出的接收进程 (即读进程 )，则从管道中接收 (读)数据。由于发送进程和接收进程是利用管道进行通信的，故又称为管道通信。这种方式首创于UNIX系统，由于它能有效地传送大量数据，因而又被引入到许多其它操作系统中借助外存实现线程轻型实体独立调度和分派的基本单位可并发执行共享进程资源第三章处理机调度和死锁调度类型高级调度：将作业从外存后备队列中调入内存中级调度：对应于 挂起状态 ，提高内存的利用率和系统的吞吐量低级调度：进程调度调度方式抢占式（高优先权，短道作业（进程）优先，时间片）非抢占式面向用户的准则(1) 周转时间短(2) 响应时间快。(3) 截止时间的保证。(4) 优先权准则。面向系统的准则(1)系统吞吐量高(2) 处理机利用率好(3) 各类资源的平衡利用周转时间：完成时间 到达时间带权周转时间：周转时间/ 服务时间=（等待时间 +服务时间） / 服务时间名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 32 页 - - - - - - - - - 调度算法先来先服务 FCFS ：按作业到达顺序，顺序执行短道作业（进程）优先SJF/SPF 对长作业不利高优先权 HPF ：抢占式非抢占式时间片轮转系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把 CPU 分配给队首进程，并令其执行一个时间片。时间片的大小从几 ms 到几百 ms。当执行的时间片用完时，由一个计时器发出时钟中断请求， 调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾； 然后，再把处理机分配给就绪队列中新的队首进程， 同时也让它执行一个时间片。 这样就可以保证就绪队列中的所有进程，在一给定的时间内， 均能获得一时间片的处理机执行时间高响应比优先既考虑了短作业，又考虑了长作业如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务多级反馈队列调度算法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 32 页 - - - - - - - - - (1) 应设置多个就绪队列，并为各个队列赋予不同的优先级(2) 当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。 当轮到该进程执行时， 如它能在该时间片内完成， 便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列， ，如此下去，当一个长作业(进程)从第一队列依次降到第n 队列后，在第 n 队列中便采取按时间片轮转的方式运行。(3) 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第 1(i-1) 队列均空时，才会调度第i 队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第 1(i-1)中的任何一个队列 )，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i 队列的末尾，把处理机分配给新到的高优先权进程。注意是时间片用完的情况还是外界干预情况，区别对待。优先权类型：静态动态死锁：多个进程因竞争临界资源而陷入僵局的状态产生死锁的原因竞争资源进程间推进顺序非法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 32 页 - - - - - - - - - 产生死锁的必要条件互斥条件请求和保持条件不可剥夺条件环路等待条件处理死锁的方法预防死锁1. 摒弃“请求和保持”条件采用资源一次性分配方式2. 摒弃“不剥夺”条件如果无法获取其他资源，立即释放现在已申请到的资源3. 摒弃“环路等待”条件避免死锁：安全性算法找进程执行的安全序列检测死锁：资源分配图解除死锁：剥夺资源撤销进程系统的安全状态安全状态，是指系统能按某种进程顺序(P1, P2, ，Pn)(称P1, P2, , Pn序列为安全序列 )，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态死锁检测：资源分配图（找到一个既不阻塞又不独立的进程结点开始简化）利用银行家算法避免死锁(1) 可利用资源向量 Available 这是一个含有m 个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目Availablej=K (2) 最大需求矩阵 Max 这是一个 nm 的矩阵，它定义了系统中n 个进程中的每一个进程对m 类资源的最大需求。如果Maxi,j=K，则表示进程 i 需要 Rj类资源的最大数目为K (3) 已分配矩阵 Allocation 这也是一个 nm 的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数(4) 需求矩阵 Need 一个 nm 的矩阵，用以表示每一个进程尚需的各类资源数。如果 Need i,j=K，则表示进程 i 还需要 Rj类资源 K个，方能完成其任务Needi,j=Maxi,j- Allocation i,j执行过程系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Availablej=Availablej-Requestij; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 32 页 - - - - - - - - - Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi， 以完成本次分配； 否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待P1请求资源： P1发出请求向量 Request1(1，0，2)，系统按银行家算法进行检查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2) 第四章存储器管理程序的装入绝对装入方式：物理内存的地址可重定位装入方式：动态装入方式： 把装入模块装入内存后， 并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。程序的链接方式静态链接装入时动态链接运行时动态链接：运行时由OS去找该模块并装入内存，这样未用到的都不会被调入内存内存分配方式连续分配方式（1）单一连续分配把内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间，提供给用户使用名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 32 页 - - - - - - - - - （2）固定分区分配划分分区（分区大小相等或不等）内存碎片（3）动态分区分配涉及的数据结构：空闲分区表空闲分区链分区分配算法首次适应算法：循环适应算法最佳适应算法最坏适应算法分配内存操作可重定位分区分配，使用紧凑技术动态重定位分区分配名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 32 页 - - - - - - - - - 内存回收对换技术（ swapping）所谓“ 对换” ， 是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上， 以便腾出足够的内存空间， 再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是提高内存利用率的有效措施。对应于挂起状态提高内存的利用率将具有对换功能的OS ，外存分为文件区和对换区文件区：存放文件目的是实现对文件存储空间的利用率对换区：存放从内存中对换出来的进程提高进程换入换出的速度基本分页存储管理方式页面：对应于逻辑地址空间， 将一个进程的逻辑地址空间分成若干个大小相等的片，称为 页面或页物理块： 对应于物理内存空间， 把内存空间分成 与页面相同 大小的若干个存储块，称为(物理)块或页框 (frame) 由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“ 页内碎片 ”页面大小：地址转换 ： （逻辑地址 物理地址）页号 +偏移量若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号 P 和页内名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 32 页 - - - - - - - - - 地址 d 可按下式求得：物理地址 =由页号索引得到的块号 *页面大小 +偏移量的 d 页表：页号 +块号地址变换机构名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 32 页 - - - - - - - - - 越界中断：是指计算的页号值大于页表的索引值，而发生中断缺页中断：所申请访问的页面不在内存，产生中断将其从外存调入具有快表的地址转换机构两级和多级页表基本分段存储管理方式段号+段内地址名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 32 页 - - - - - - - - - 分页和分段的主要区别(1) 页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。或者说，分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。(2) 页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件 实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。(3) 分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址段页式存储管理方式虚拟存储器虚拟存储器， 是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。特点：对换性多次性虚拟性名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 32 页 - - - - - - - - - 程序运行的局部性原理内存分配算法最小物理块数：指能保证进程正常运行所需的最小物理块数。单地址指令直接寻址2 个其他的将多于 2 个分配策略1) 固定分配局部置换2) 可变分配全局置换3) 可变分配局部置换物理块分配算法1）平均分配算法2）按比例分配算法3）考虑优先权的分配算法调页策略预调策略请求调入策略外存分为两部分，用于存放文件的文件区 ，和用于存放对换页面的 对换区(1) 系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度(2) 系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时， 由于它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入(3) UNIX 方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面， 由于是被放在对换区，因此在下次调入时，应从对换区调入每当程序所要访问的页面未在内存时，便向CPU 发出一 缺页中断 。中断处理程序首先保留 CPU环境，分析中断原因后，转入缺页中断处理程序。该程序通过查找页表，得到该页在外存的物理块后，如果此时内存能容纳新页，则启动磁盘 I/O 将所缺之页调入内存，然后修改页表。如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出页面置换算法1）最佳置换算法 Opt 向后看算法2）先进先出置换算法FIFO 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 32 页 - - - - - - - - - 3）最近最久未使用置换算法LRU 向前看算法此处涉及缺页率计算Clock置换算法简单的 Clock置换算法改进的 Clock置换算法在虚拟内存中， 页面在内存和外存之间频繁的调度，以至于调度页面所需要的时间比进程实际运行的时间还多，此时，系统效率剧烈下降， 甚至导致系统崩溃，这种现象被称为 抖动或颠簸。分段保护越界检查存取控制检查等第五章设备管理I/O 设备分类按传输速率分为低速设备中速设备高速设备按信息交换的单位分为块设备（ DMA）字符设备按共享属性分为独占设备共享设备虚拟设备设备控制器 的基本功能：接收和识别命令数据交换标识和报告设备状态地址识别数据缓冲差错控制结构：与处理机的接口与设备的接口I/O 逻辑I/O 通道设备目的将 CPU从繁忙的 IO操作中解脱出来名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 32 页 - - - - - - - - - I/O 通道是一种特殊的处理机。它具有执行I/O 指令的能力，并通过执行通道(I/O)程序来控制 I/O 操作一是其指令类型单一 ，这是由于通道硬件比较简单，其所能执行的命令，主要局限于与 I/O 操作有关的指令；二是通道没有自己的内存 ，通道所执行的通道程序是放在主机的内存中的，换言之，是通道与CPU共享内存通道类型字符多路通道不适合连接高速设备数组选择通道可连接多台高速设备，但只含一个分配型子通道，一段时间内只能执行一道通道程序，控制一台设备。不允许抢占。数组多路通道它含有多个非分配型子通道，因而这种通道既具有很高的数据传输速率，又能获得令人满意的通道利用率瓶颈问题名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 32 页 - - - - - - - - - 单通路 I/O 系统解决瓶颈问题，是多通路 IO系统多通路 I/O 系统PCI 总线？I/O 控制方式程序查询方式在该方式中， CPU要不断地测试 I/O 设备的状态， 致使 CPU的绝大部分时间都处于等待 I/O 设备完成数据 I/O 的循环测试中，造成对 CPU的极大浪费中断驱动方式使 CPU与 I/O 设备并行工作，仅当输完一个数据时，才需CPU花费极短的时间去做些中断处理DMA 方式特点是：数据传输的基本单位是 数据块 ，即在 CPU与 I/O 设备之间，每名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 32 页 - - - - - - - - - 次传送 至少一个数据块；所传送的数据是从 设备直接送入内存的 ，或者相反； 仅在传送一个或多个数据块的开始和结束时，才需CPU 干预，整块数据的传送是在控制器的控制下完成的(1) 命令/状态寄存器 CR 。用于接收从 CPU发来的 I/O 命令或有关控制信息，或设备的状态(2) 内存地址寄存器 MAR。在输入时，它存放把数据从设备传送到内存的起始目标地址；在输出时，它存放由内存到设备的内存源地址(3) 数据寄存器 DR。用于暂存从设备到内存，或从内存到设备的数据(4) 数据计数器 DC。 存放本次 CPU要读或写的字 (节)数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 32 页 - - - - - - - - - I/O 通道控制方式I/O 通道方式是 DMA 方式的发展，它可进一步减少CPU的干预，即把对一个数据块的读 (或写)为单位的干预，减少为 对一组数据块 的读(或写)及有关的控制和管理为单位的干预。同时，又可实现 CPU 、通道和 I/O 设备三者的并行操作，从而更有效地提高整个系统的资源利用率缓冲管理(1) 缓和 CPU与 I/O 设备间速度不匹配的矛盾。(2) 减少对 CPU的中断频率，放宽对 CPU中断响应时间的限制。(3) 提高 CPU和 I/O 设备之间的并行性缓冲首部 ：管理缓冲区缓冲体 ：存放缓冲数据（1）单缓冲 single buffer 处理时间 =MAX(C,T)+M 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 32 页 - - - - - - - - - （2）双缓冲 Double buffer （3）循环缓冲在此机制中，设置多个缓冲区，每个缓冲区大小相同，包括：多个缓冲区用于输入数据空缓冲区R：已装满数据的缓冲区G 计算进程正在使用的现行缓冲区C 多个指针指示计算进程下一个可用缓冲区G的指针 Nextg 指示输入进程下次可用的空缓冲区R的指针 Nexti 指示进程现在正在使用的缓冲区C的指针 Current (1) Nexti 指针追赶上 Nextg 指针。已把全部可用的空缓冲区转满(2) (2) Nextg指针追赶上 Nexti 指针。全部被转满的缓冲区已被抽空Getbuf 过程Releasebuf过程（4）缓冲池 buffer pool 既可用于输入又可用于输出的公用缓冲池名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页，共 32 页 - - - - - - - - - 三个队列指针（1）空缓冲队列 emq。(2) 输入队列 inq。(3) 输出队列 outq。四个缓冲区收容输入提取输入收容输出提取输出设备驱动程序：即设备处理程序，是I/O 进程与设备控制器之间的通信程序。设备独立性：即设备无关性，应用程序独立于具体使用的物理设备引入概念：物理设备，逻辑设备优点：设备分配灵活易于实现 I/O 重定向设备分配设备控制表 DCT 控制器控制表 COCT 通道控制表 CHCT 系统设备表 SDT 独占设备的分配程序独立设备分配过程： SDT DCT COCT CHCT 设备的固有属性：独占性共享性虚拟性设备分配算法： FCFS HPF SPOOLing 技术：即假脱机技术，实现脱机输入、输出功能名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 24 页，共 32 页 - - - - - - - - - 输入井 ：模拟脱机输入的磁盘设备，暂存I/O 设备输入的数据输出井 ：模拟脱机输出的磁盘设备，暂存用户程序的输出数据在输入输出设备与磁盘之间设置输入输出缓冲区 ，进行速度上的匹配输入进程输出进程以打印机为例说明该技术当用户进程请求打印输出时，SPOOLing系统同意为它打印输出，但并不真正立即把打印机分配给该用户进程，而只为它做两件事： 由输出进程在输出井中为之申请一个空闲磁盘块区 ，并将要打印的数据送入其中； 输出进程再为用户进程 申请一张空白的用户请求打印表，并将用户的打印要求填入其中 ， 再将该表挂到请求打印 队列上。特点：提高了 I/O 操作将独占设备改造为共享设备实现了虚拟设备功能磁盘存储管理固定头磁盘在每条磁道上都有一读 /写磁头，所有的磁头都被装在一刚性磁臂中。通过这些磁头可访问所有各磁道， 并进行 并行读/写，有效地提高了磁盘的I/O 速度。这种结构的磁盘主要用于大容量磁盘上固定头磁盘每一个盘面仅配有一个磁头， 也被装入磁臂中。 为能访问该盘面上的所有磁道，该磁头必须能 移动以进行寻道 。可见，移动磁头仅能以串行方式读 /写，致使其 I/O 速度较慢；但由于其结构简单，故仍广泛应用于中小型磁盘设备中磁盘访问时间寻道时间：指把磁臂 (磁头)移动到指定磁道上所经历的时间Ts=mn+s 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 25 页，共 32 页 - - - - - - - - - 旋转延迟时间：指定扇区移动到磁头下面所经历的时间传输时间：把数据从磁盘读出或向磁盘写入数据所经历的时间r 为转速， b 所读/写字节数， N 一条磁道上的字节数可访问时间为磁盘调度算法先来先服务 FCFS ：从当前盘块顺序执行完毕最短寻道优先 SSTF ：同时双向查找距当前位置最近的盘块，导致“饥饿”现象扫描 SCAN ：先沿盘块号增大的方向执行SSTF 算法， 然后在反向执行 SSTF算法循环扫描 CSCAN ：先沿单向执行 SSTF 算法，反向时无操作，然后继续按第一次的执行过程进行操作计算平均寻道长度第六章文件管理记录：是一组相关数据项的集合， 用于描述一个对象在某方面的属性，一个记录可包括多个 数据项文件：指由创建者所定义的，具有文件名的一组相关元素的集合，可分为 有结构文件（记录型文件）和无结构文件（流式文件）两种。在有结构的文件中，文件由若干个相关记录 组成；而无结构文件则被看成是一个字符流UNIX 系统中，所有的文件都被看作是流式文件；即使是有结构文件，也被视为流式文件；系统不对文件进行格式处理。文件类型用途系统文件用户文件库文件数据形式源文件目标文件可执行文件名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 26 页，共 32 页 - - - - - - - - - 存取控制属性只执行文件只读文件读写文件组织形式和处理方式普通文件目录文件特殊文件 （linux 和 unix 中）特指系统中的 各类 I/O 设备文件系统接口：命令接口程序接口对于任何一个文件，都存在着以下两种形式的结构文件逻辑结构文件物理结构：即存储结构，是指文件在外存上的存储组织形式顺序文件：分为串结构的和顺序结构的缺点：不利于记录的增删链接分配方式隐式链接： 指针隐藏 在存放文件数据的盘块中访问方式：顺序访问文件的大小访问后才知道文件目录项中要给出起始盘块号和终止盘块号。显式链接：指针显式的存放在内存的一张链接表中文件目录只给出起始盘号单级索引多级索引名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 27 页，共 32 页 - - - - - - - - - 目录管理 ：实现按名存取，提高检索速度，文件共享文件和文件控制块一一对应单级目录简单但是查找速度慢不允许重名多级目录绝对路径把从树根开始的路径名相对路径从当前目录开始直到数据文件为止所构成的路径名当前目录工作目录FAT表的大小取决于磁盘驱动器为半个字节的整数倍计算 FAT表的大小FAT与 NTFS FCB文件控制块文件存储空间管理空闲表法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 28 页，共 32 页 - - - - - - - - - 空闲链表法位示图法需要分配盘块时，顺序扫描位示图，找到值为“0”的二进制位b=n(i-1)+j修改位示图，令 mapi,j=1。回收过程：i=(b-1)DIV n+1 j=(b-1)MOD n+1 成组链接法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 29 页，共 32 页 - - - - - - - - - 文件的共享和保护基于索引结点的文件共享只设置文件名和指向相应索引节点的指针可能访问的文件是错误的利用符号链实现文件共享只是文件主才拥有指向其索引结点的指针；而共享该文件的其他用户， 则只有该文件的路径名，并不拥有指向其索引结点的指针。这样，也就不会发生在文件主删除共享文件后留下一悬空指针的情况。当文件的拥有者把一个共享文件删除后，其他用户试图通过符号链去访问一个已被删除的共享文件时，会因系统找不到该文件而使访问失败， 于是再将符号链删除， 此时不会产生任何影响。磁盘容错技术第一级容错技术SFT- 双份目录和双份文件分配表文件目录和文件分配表FAT ， 是文件管理所用的重要数据结构在不同的磁盘上