操作系统的定义：操作系统是一组计算机软硬件资源的控制和管理 调度各种作业，方便用户使用的程序集合。

1. 操作系统使计算机更容易使用。
2. 有效性：操作系统允许以更有效的方式使用计算机系统资源。
   • 提高系统资源利用率（important）
   • 提高系统吞吐量(important)
3. 可扩展性：允许在操作系统中有效开发、测试和引入新的系统功能。
4. 开放性：实现应用程序的可移植性和可操作性，需要统一的开放环境。

1. 无操作系统(人工操作) 缺点：
2. 用户独占全机
3. CPU等待人工操作
4. 单道批处理操作系统 定义:系统对操作的处理是分批进行的，内存中只有一个操作，操作结束或出错后才会自动调整另一个操作。 主要特点:自动性、顺序性、单道性 优点：
5. 减少人工操作
6. 解决了操作的自动连续性

缺点：

1. 平均周转时间长
2. 没有互动能力
3. 多批处理操作系统 定义:将多个操作存储在内存中，操作结束或出错，自动 调度内存中的另一个操作。 主要特点:多道性、无序性、调度性(过程调度和作业调度) 优点：
4. 提高CPU的利用率。
5. 提高内存和I/O设备利用率。
6. 增加系统吞吐率

例题：

解答：

4. 分时操作系统 特点：
5. 多路性：主机连接多个终端
6. 独立性独立操作，不干扰对方
7. 及时性:系统可以在很短的时间内回答
8. 互动：可实现人机对话（与批处理系统不同）
9. 实时操作系统 定义：计算机应及时响应外部事件的要求，并在规定的时间内完成 处理事件，控制所有实时设备和实时任务的协调运行。 特点:
10. 多路性:可以控制多个对象。
11. 独立：独立运行，不混淆，不破坏。
12. 交互性：仅限于访问系统中某些特定的特殊服务程序。
13. 可靠性：高可靠性，应具有多级容错保护能力。（与分时系统不同）
14. 及时性：不同的系统要求不同，控制对象必须在截止日期内完成。

1. 并发性（最重要的特征） 并发：并发性和并发性，并发执行过程。

• 并行性：指同时发生的两个或多个事件。
• 并发性：在同一时间间隔内发生两个或多个事件。

2. 共享性 共享：指内存中多个并发执行过程中系统中的资源。

• 互斥共享方式 可以为多个过程提供系统中的临界资源，但一段时间内只允许一个进入
• 同时访问 从宏观上看，资源共享是指系统中软硬件资源可以同时使用多个任务。 从微观上看，系统中的交替使用系统中的资源。例如磁盘。 程序使用称为互斥共享模式

3. 虚拟性 虚拟:指物理实体通过某种技术(映射)变成几个逻辑 对应物

• 时间复用技术
• 空分复用技术

4. 异步性 异步:程序(进程)在多个程序环境下以异步的形式执行，每个程序在哪里？ 时间执行、各自执行顺序、完成时间不确定，也不可预测 并发是最重要的特征，其他特征都是以并发为前提的。 例题： 解答：C

1. 处理机管理（CPU）
2. 存储器管理
3. 设备管理
4. 文件管理
5. 用户接口方便。

1. 顺序：严格按照程序规定的顺序操作处理机。
2. 封闭性程序运行时独占全机资源，一旦程序开始执行，其执行结果不受外部因素影响 影响。
3. 可再现性：只要程序执行的环境和初始条件相同，就会得到相同的结果。（无论是从头到尾还是停止）

1. 间歇性:由于共享系统资源，相互合作完成同一任务， 这些并发程序之间形成了相互限制的关系。相互限制会导致并发 发程序具有间歇性活动规律，如执行-暂停-执行。
2. 失去封闭：它是多个程序共享系统中的各种资源，因此这些资源的状态将由 多个程序改变，导致程序运行失去封闭性。
3. 不可再现性：当程序并发执行时，由于失去了封闭性，不可再现性 。

1. 流程是程序的执行。
2. 在处理机上按顺序执行程序执行程序及其数据时发生的活动。
3. 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度 独立单位。

1. 结构特征 程序段、相关的数据段和PCB三部分构成了进程实体。
2. 动态性 过程由创建产生，由调度执行，由撤销而消亡
3. 并发性 指内存中存储的多个过程实体，并能在一段时间内同时运行。
4. 独立性 是指进程实体能够独立运行、分配资源资源，独立接受调度 基本单位
5. 异步性 指过程以独立、不可预测的速度向前推进，或过程实体 按异步运行。

Ready：准备执行

Running：占用处理机(在单处理机环境中，只占用一个进程)

Blocked：等待事件发生后才能实施，比如等待I/O完成等

New：该过程已创建，但尚未创建OS接纳为可执行进程，并且程序还在辅存， PCB在内存

Exit：因停止或取消OS释放执行状态

挂起状态(Suspend):暂停执行并静止执行过程。我们称这种静态状态为悬挂状态。

引入悬挂状态的原因

1. 终端用户的请求。
2. 父亲的过程请求。
3. 负荷调节的需要。当实时系统中的工作负荷较重时，挂起一些不重要的过程， 以保证系统能正常运行。
4. 操作系统的需要。操作系统有时希望悬挂一些过程，以检查运行中的资源使用情况或记账

1. 进程标识符

内部标识符。为每一个进程赋予一个惟一的 数字标识符。设置内部标识 符主要是为了方便系统使用。
• 外部标识符。它由创建者提供，通常是由字母、数字组成，往往是由用 户（进程）在访问该进程时使用。

2. 处理机状态

• 通用寄存器
• 指令计数器
• 程序状态字PSW
• 用户栈指针

3. 进程调度信息

• 进程状态
• 进程优先级
• 进程调度所需的其它信息
• 事件，阻塞原因

4. 进程控制信息

• 程序和数据的地址
• 进程同步和通信机制
• 资源清单
• 链接指针

1. 线性方式
2. 链接方式
3. 索引方式

1. 整形信号量 定义为一个整型量 ,仅能通过两个标准的原子操作 wait（S）和signal（S）来访问。 又称为P、V操作。
2. 记录型信号量
3. AND型信号量 原子操作：要么全部分配到进程，要么一个也不分配。
4. 信号量集

1. 生产者/消费者问题

• 利用记录型信号量解决
• 利用AND信号量解决

2. 哲学家进餐问题

• 利用记录型信号量解决
• 利用AND信号量解决

3. 读者 — 写者问题

1. 直接通信方式 这是指发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。 系统提供下述两条通信命令（原语）

• Send （Receiver， message）
• Receive（Sender， message）

2. 间接通信方式 写进程 -> 信箱（中间实体） -> 读进程原语 优点：在读/写时间上的随机性 Send (mailbox, message) Receive (mailbox, message)

例题：

解答：

1. 高级调度

• 调度对象：作业
• 又称作业调度、长程调度、接纳调度
• 实现：作业管理程序
• 将外存作业调入内存，创建PCB等，插入就绪队列。
• 用于批处理系统，分/实时系统一般直接入内存，无此环节。
• 频度：最低，分钟级

2. 低级调度

• 又称进程调度或短程调度
• 对象：就绪进程（或内核线程）
• 功能：决定就绪队列中的那个进程应获得处理机，并将处理机分配给选中 的进程。
• 实现者 ：分派程序（dispatcher)
• 应用范围：都有
• 频度：最频繁，毫秒级

3. 中级调度

• 又称内存调度
• 对象：挂起的进程
• 功能：把外存上那些已经具备运行条件的就绪进程重新载入内存。从静止 就绪到活动就绪。
• 实现：内存管理中的对换进程
• 应用范围：具有对换功能的操作系统
• 频度：中等

公式：

1. 先来先服务（FCFS) 作业调度时，优先选择后备作业中最先进入队列的作业。 进程调度时，每次调度从就绪队列中选择一个最先进入该队列的进程。 有利于长作业（进程），而不利于短作业（进程）
2. 短作业（短进程）优先（SPF、SJF） 是从后备队列中选择一个或若干个估计运行时间 最短的作业，将它们调入内存运行,立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。
3. 时间片轮转（RR） 原理： FCFS策略+时钟中断+时间片原则 进程切换时机

• 时间片内进程结束，进程结束事件激活进程调度，新进程可运行一个时间 片；
• 时间片用完，时钟中断激活调度，旧进程到就绪队列尾，队头进程投入运 行一个时间片。

4. 基于优先级的调度算法(PSA) 响应比Rp=（等待时间＋服务时间）/服务时间 作为优先权 Rp越高，优先级越高
5. 剩余时间最短者优先
6. 高响应比优先调度算法 赋予作业动态优先级，优先级随作业等待时间延长而增加，从而使长作业的 优先级在等待期间不断增加
7. 多级反馈队列调度法

• 设置多个就绪队列，并为各个队列赋予不同的优先级。
• 优先级愈高的队列的进程的执行时间片就愈小。
• 新进程首先进入最高优先级的队列。每个队列采用FCFS算法。队列中的进 程运行一个时间片后未结束则降级排到下一个队列的末尾。最低优先权队 列中的进程则按RR方式运行。
• 按队列优先级调度。仅当1~(i-1)所有队列均空时，才会调度第i队列中的 进程。

• 可剥夺性资源: 是指某进程在获得这类资源后，该资源可以再被其他进程 或系统剥夺。如：处理机、内存等
• 非剥夺性资源: 当系统把这类资源分配给某进程后，再不能强行收回，只 能在进程用完后自行释放。如打印机等

1. 互斥条件：指进程对所分配到的资源进行排它性使用
2. 请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源 请求
3. 不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能 在使用完时由自己释放。
4. 环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链 。

1. 预防死锁：是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的 一个或几个条件，来预防发生死锁。
2. 避免死锁：是在资源的动态分配过程中，用某种方法去防止系统进入不安全 状态，从而避免发生死锁。
3. 检测死锁：通过系统所设置的检测机构，及时地检测出死锁的发生，并精确 地确定与死锁有关的进程和资源；
4. 解除死锁：当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。 常用的实施方法是撤消或挂起一些进程。

数据结构

该图是由一组结点N和一组边E所组成的一个对偶G＝（N,E）

其中： 把N分为两个互斥的子集，即一组进程结点P={P1,P2，…，Pn）和一组资源 结点R={r1,r2，…，rn}，N＝PUR。

凡属于E中的一个边e∈ E都连接着P中的一个结点和R中的一个结点

• e＝{Pi,rj}

它表示进程pi请求一个单位的rj资源。

• e={rj，Pi}

它表示把一个单位的资源rj分配给进程Pi

首先去掉图a中的p1结点，去掉p1的两条分配边和一条请求边，成为图b； 从而，进程p2可获得所需要的资源并顺利完成，简化p2结点的分配边和申请边，成为图c。

若能消去资源分配图中所有结点的连接边，使全部结点都成为孤立结点，则 称该图是可完全简化图；若不能使该图完全简化，则称该图是不可完全化简 图

死锁定理：当且仅当系统某状态S所对应的资源分配图是不可完全化简的， 则S是死锁状态。

1. 撤消死锁进程。该方法是目前操作系统中解除死锁的常用方法。
2. 把死锁进程恢复到前一个检查点，重新执行每个进程。
3. 按照某种原则逐个选择死锁进程进行撤消，直到解除系统死锁。
4. 按照某种原则逐个剥夺进程资源，直到解除死锁。

由源程序到可在内存中执行的程序

编译 -> 链接 -> 装入

编译:由编译程序（Compiler）将用户源代码编译成若个目标模块 。

链接:由链接程序（Linker）将编译后形成的一组目标模块，以及它们所需 要的库函数链接在一起，形成一个完整的装入模块 。

装入:由装入程序（Loader）将装入模块装入内存

1. 绝对装入方式 按照装入模块中的地址，将程序和数据装入内存。装入模块 被装入内存后，由于程序中的逻辑地址与实际内存地址完全相同，故不需对 程序和数据的地址进行修改
2. 可重定位装入方式 由装入程序将装入模块装入内存后，装入模块中程序所访问的所有逻辑地 址与实际装入内存的物理地址不同 ，必须进行变换 把在装入时对目标程序中指令和数据的变换过程称为重定位。
3. 动态运行时装入方式 装入程序将目标模块装入内存后，并不立即把装入模块中的相对地址转换为 绝对地址，而是把这种地址转换推迟到程序执行时进行，在硬件地址变换机构 的支持下，随着对每条指令或数据的访问自动进行地址变换

根据链接时间的不同，进行分类

1. 静态链接方式 在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块（又称执行模块），以后不再拆开
2. 装入时动态链接 是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式 分别装入各模块，并且在装入的过程中修改相对地址和外部引用地址。 优点：
3. 便于修改和更新
4. 便于实现对目标模块的共享
5. 运行时动态链接 各模块被独立装入系统，而且也不进行链接，运行时发现引用的地址是相对地址或者外部地址时，才发起链接，寻找正确的引用地址 优点： 凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。 该方法时最常用的方法

1. 单一连续分配方式 单用户系统在一段时间内，只有一个进程在内存 内存分为两个区域，一个供操作系统使用（系统区），一个供用户使用（用户区） 优点：

• 易于管理

缺点：

• 对要求内存空间少的程序，造成内存浪费
• 程序全部装入，很少使用的程序部分也占用内存

2. 分区式分配方式 把内存用户区划分为若干分区 分区大小可以相等，也可以不等

• 固定分区 将内存用户空间划分为若干个固定大小的区域，每个区域称为一个分区（region），在每个分区中只装入一道作业 ，从而支持多道程序并发设计
  • 分区大小

（1）分区大小相等。当程序太小时，会造成内存空间的浪费 。当程序太大时，一个分区又不足以装入该程序，致使该程序无法运行。 （2）分区大小不等。可把内存区划成含有多个较小的分区、适量的中等分区及少量的大分区。

• 分区分配

内存分配程序检索分区描述表，从中找出尚未使用的最接近大小的分区分配给该作业，然后修改分区的状态。

缺点：存在“内零头”会造成存储空间的浪费。

内零头——在分区内没有利用的部分称为内零头

• 动态（可变）分区
  • 分区分配数据结构

（1）空闲分区表。在系统中设置一张空闲分区表，用于记录每个空闲分区的情况（包含空闲分区号、分区大小、起始地址）。 （2）空闲分区链表。为了实现对空闲分区的分配和链接，设置前向指针和后向指针，通过前、后向链接指针将所有的空闲分区链接成一个双向链

3. 可重定位分区分配

合并相邻的空闲分区，形成大的分区

1. 首次匹配(首次适应算法FF) 要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止 优点：

• 利用内存低地址部分空闲分区，为大作业分配大的内存空间创造了条件。

缺点

• 低址部分不断被划分，会留下许多难以利用的、很小的空闲分区
• 增加查找开销

2. 循环匹配(循环首次适应算法) 将所有的空闲分区构成一个循环链表。每次查找时不是从头开始，而是从上次结束位置开始 优点：

• 使内存中的空闲分区分布得更均匀
• 减少了查找空闲分区的开销

缺点：

• 缺乏大的空闲分区

3. 最佳匹配(最佳适应算法） 该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。从头开始查找，将表中第一个大于所需求空间大小的空闲区分配给作业。 优点：

• 为大作业分配大的内存空间创造了条件

缺点：

• 在存储器中会留下许多难以利用的小空闲区

4. 最坏适应算法 空闲分区按其容量从大到小排成空闲分区表 总是挑选一个最大的空闲分区分割给作业使用 优点：

• 使剩下的空闲分区不至于太小，产生碎片几率最小
• 对中、小作业有利，查找效率高

缺点：

• 会使存储器中缺乏大的空闲分区

5. 快速适应算法（分类搜索法） 对于每一类相同容量的空闲分区单独设立一个空闲分区链表 设置管理索引表，每个表项对应一种空闲分区类型，并记录该类空闲分区链表表头指针 优点：

• 查找效率高
• 不会对任何分区产生分割，能保留大的分区，也不会产生内存碎片

缺点：

• 分区归还主存时算法复杂，系统开销较大。
• 内零头

紧凑： 动态重定位 增加重定位寄存器（分区首址寄存器），保存分区起始地址，当进行紧凑内存空间时，只需移动分区内容，然 后用新的分区起始地址重置分区首址寄存器。

程序中的相对地址=重定位寄存器+相对地址

1. 分页储存管理

概念： 页面或页：一个进程的逻辑地址空间分成若干个大小相等的片 (物理)块或页框：内存空间分成与页面相同大小的若干个存储块 页内碎片：由于进程的最后一页经常装不满一块而形成了不可利用的碎片 页表：每个进程所对应的一张页面映像（射）表 地址变换 页表寄存器PTR：存放当前运行的进程的页表在内存中的起始地址，和此进程的页表长度。

地址变换过程

1. 根据逻辑地址,计算出页号和页内偏移量；
2. 从PTR中得到页表首址，然后检索页表，查找指定页面对应的页框号；
3. 用页框号乘以页面大小获得其对应页框的起始地址，并将其送入物理地址的 高端。
4. 将页内偏移量送入物理地址低端，形成完整的物理地址。

优点：

1. 彻底消除了外零头,仅存在很少的内零头, 提高了内存利用率

缺点:

1. 分页操作由系统自动进行,一个页面不能实现某种逻辑功能

2. 用户看到的逻辑地址是一维的，无法调试执行其中的某个子程序或子函数。

3. 采用分页技术不易于实现存储共享

4. 不便于程序的动态链接

5. 段式储存管理

程序由若干逻辑段组成，每个段有自己的名字和长度。程序的逻辑地址是由段名（段号）和段内偏移量决定。每个段的逻辑地址从0开始编址。 概念： 段表 : 每个进程建立一个段表，用于描述进程的分段情况，记载进程的各个段到物理内存中分区的映射情况。其中包含段号、段基址、段长以及对本段的存取控制权限等信息。 空闲分区表 : 用于记载物理内存中的空闲分区情况。

地址变换

1. 根据逻辑地址中的段号检索进程段表，获得指定段对应的段表项；
2. 判断是否地址越界。比较逻辑地址中的段内偏移量与段表项中的段长，若超 过段的长度，则产生存储保护中断（该中断将由操作系统进行处理）；否则， 转（c）；
3. 把逻辑地址中的段内偏移量与段表表项中的段基址相加，从而得到物理地址。

3. 段页式储存管理

采用分段方法组织用户程序，采用分页方法分配和管理内存。 先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。 地址变换

1. 首先，从段表寄存器获得进程段表的起始地址，根据该地址，查找进程的

段表。

2. 然后，根据逻辑地址指定的段号检索段表，找到对应段的页表起始地址。
3. 再根据逻辑地址中指定的页号检索该页表，找到对应页所在的页框号。
4. 最后，用页框号加上逻辑地址中指定的页内偏移量，形成物理地址。

定义： • 当进程运行时，先将当前要运行的部分程序装入内存，其他部分暂留外存； • 当要执行的指令不在内存时，处理器发生中断，通知操作系统将所缺部分从外 存调入内存，保证程序继续执行； • 当内存不足时，允许程序部分换入、换出。

实现：

特征

1. 多次性:多次性是指一个作业被分成多次调入内存运行。
2. 对换性:对换性是指作业的运行过程中进行换进、换出，换进和换出能有效地提高

内存利用率。

3. 虚拟性:虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于

实际内存容量

实现方法

1. 请求分页系统

页表机制 •状态位：也称存在位，标志该页是否驻留内存。 • 访问位：记录一段时间内该页被访问的情况，如一段时间内该页被访问的次数或者多长 时间未被访问。 • 修改位：标记该页是否被修改过。注：为减少置换开销，通常选择未被修改过的页面置 换。 • 外存地址：用于记录该页在外存上的存储地址

2. 请求分段系统

地址变换

3. 段页式虚拟系统

1. 最佳(优)置换算法

所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的 页面

2. 先进先出（FIFO）页面置换算法

该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰 。（总共12次）

3. 最近最久未使用（LRU）置换算法

LRU置换算法是选择最近最少使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。

4. Clock置换算法

当采用简单c1ock算法时，为每页设置一位访问位，再将内存中的所有页面都 通过链接指针链接成一个循环队列。 当某页被访问时，其访问位被置1。 置换程序从上次停止位置开始检查页面的访问位。 – 如果是0，就选择该页换出； – 若为1，则重新将它置0，暂不换出，而给该页第二次驻留内存的机会。

5. 改进型Clock置换算法

换出未修改过的页面比换出被修改过的页面开销小。 ** 显然，我们可以依据上述结论改进CLOCK算法。改进后的CLOCK算法将在置换范围内首选在最近没有被使用过、在驻留内存期间没有被修改过的页面作为被置换页面。**

由访问位A和修改位M可以组合成下面四种类型的页面： 1类（A=0，M=0）：表示该页最近既未彼访问，又未被修改，是最佳淘汰页。 2类（A=0，M=1）：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。 3类（A=1，M=0）：最近已被访问，但未被修改：该页有可能再被访问。 4类（A=1，M=1）：最近已被访问且被修改，该页可能再被访问。

6. 其它置换算法

多道程序度与处理机的利用率

产生“抖动”的原因 发生抖动的根本原因是，同时在系统中运行的进程太多，由此分配给每个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时，频繁地出现缺页，造成每个进程的大部分时间都用于页面的换进换出，从而导致处理机的利用率急剧下降并趋于0.

工作集:指在某段时间间隔内△，进程实际所要访问页面的集合。

“抖动”的预防方法

1. 采取局部置换策略。将“抖动”造成的影响限制在较小的范围
2. 把工作集算法融入到处理机调度中。在调度新作业之前，检查当前驻留进程 的页面是否足够多，判断是否会因为调入新作业导致缺页率增加
3. 利用“L=S”准则调节缺页率。其中L是缺页之间的平均时间，S是平均缺页服 务时间，即置换一个页面所需的时间。
4. 选择暂停的进程。选择暂停或者优先级低的进程，将其页面换出内存，降低 多道程序度，从而预防“抖动

I/O设备一般包括机械部分和电子部件，前者称为I/O设备，后者称为设备控制 器或适配器。

控制一个或多个I/O设备，以实现I/O设备和CPU之间数据交换。

基本功能

1. 接收和识别命令
2. 数据交换
3. 标识和报告设备的状态
4. 地址识别
5. 数据缓冲
6. 差错控制

组成

1. 中断是多道程序的基础，因为进程切换是通过中断来完成
2. 中断也是设备管理的基础，为了实现CPU和I/O设备的并行执行，也必须中断支持
3. 中断处理程序是I/O系统中的最低层，是整个I/O系统的基础

1. 中断：指CPU对I/O设备发来的中断信号的一种响应。中断是外部设备引起的，

因此也称为外中断

2. 陷入：是有CPU内部事件引起的中断，例如执行非法指令，地址越界等。这

类中断称为内中断。

执行步骤

1. 测试是否有未响应的中断信号
2. 保护被中断进程的CPU环境
3. 转入相应的设备处理程序
4. 中断处理
5. 恢复CPU的现场并退出中断

1. 接收由I/O系统高层发来的命令和参数，并将命令中的抽象要求转换为具体要求，例如，将磁盘块号转换为磁盘的盘面、 磁道号及扇区号。
2. 检查用户I/O请求的合法性，了解I/O设备的状态，传递有关参数，设置设备的工作方式。
3. 发出I/O命令，如果设备空闲，便立即启动I/O设备去完成指定的I/O操作；如果设备处于忙碌状态，则将请求者的请求块挂在设备队列上等待。
4. 及时响应由控制器或通道发来的中断请求，并根据其中断类型调用相应的中断处理程序进行 处理。

1. 驱动程序主要是指在请求I/O的进程与设备控制器之间的一个通信和转换程序。
2. 驱动程序与设备控制器和I/O设备的硬件特性紧密相关， 因而对不同类型的 设备应配置不同的驱动程序。
3. 驱动程序与I/O设备所采用的I/O控制方式紧密相关。
4. 由于驱动程序与硬件紧密相关， 因而其中的一部分必须用汇编语言书写。
5. 驱动程序应允许可重入

1. 将抽象要求转换为具体要求 例如，将抽象要求中的盘块号转换为磁盘的盘面、磁道号及扇区。
2. 检查I/O请求的合法性
3. 读出和检查设备的状态 在启动某个设备进行I/O 操作时，其前提条件应是该设备正处于空闲状态。 因此在启动设备之前，要从设备控制器的状态寄存器中，读出设备的状态。
4. 向设备传送必要的参数 • 例如在启动磁盘进行读/写之前，应先将本次要传送的字节数和数据应到达 的主存始址，送入控制器的相应寄存器中。 • 如RS-232串口操作，在启动该设备之前，应先按通信规程设定参数：波特 率、奇偶校验方式、停止位数目及数据字节长度等
5. 启动I/O • 驱动程序可以向控制器中的命令寄存器传送相应的控制命令。 – 对于字符设备，若发出的是写命令，驱动程序将把一个数据传送给控制器； – 若是读命令，则驱动程序等待接收数据，并通过从控制器中的状态寄存器读 入状态字的方法，来确定数据是否到达。 • 通常，I/O操作所要完成的工作较多，需要一定的时间，如读/写一个盘块中的数 据，此时驱动(程序)进程把自己阻塞起来，直到中断到来时才将它唤醒。

1. 轮询的程序I/O方式

CPU要不断地测试I/O设备的状态

2. 中断驱动I/O方式

无须CPU干预 可使CPU与I/O设备并行工作 提高了整个系统的资源利用率及吞吐量

3. DMA

减少了CPU对I/O的干预，进一步提高了CPU与I/O设备的并行操作程度。

4. 通道方式

是DMA方式的发展，它可进一步减少CPU的干预，即把对一个数据块的读(或 写)为单位的干预，减少为对一组数据块的读(或写)及有关的控制和管理为单位的干预。

可实现CPU、通道和I/O设备三者的并行操作

核心思想：在快速辅助存储设备中建立I/O缓冲区，用于缓存从慢速输入设备流入内存的数据，或缓存从内存流向慢速输出设备的数据。

SPOOLing技术是对脱机输入/输出系统的模拟。

特点

1. 提高了I/O的速度。对数据所执行I/O操作，已从对低速的I/O设备执行演变成 对磁盘缓冲区中的数据的存取
2. 将独占设备改造为共享设备。因为在假脱机打印机系统中，实际上并没有为 任何进程分配设备，而只是在磁盘缓冲区中为进程分配一个空闲盘块和建立 一张I/O请求表
3. 实现了虚拟设备。宏观上，虽然是多个进程同时使用一台独占设备，而对每 一个进程而言，它们认为自己独占了一个设备。

1. 缓和CPU与I/O设备间速度不匹配的矛盾。
2. 减少对CPU的中断频率， 放宽对CPU中断响应时间的限制。
3. 解决数据粒度不匹配问题
4. 提高CPU和I/O设备之间的并行性，提高系统吞吐量和设备的利用率。

1. 单缓冲区

于T和C是可以并行的，当T＞C时，系统对每一块数据的处理时间为M＋T；反之则为M＋C，故可把系统对每一块数据的处理时间表示为Max（C，T）十M

2. 双缓冲区

在设备输入时，先将数据送入第一缓冲区，装满后便转向第二缓冲区。此时操作系统可以从第一缓冲区中移出数据，并送入用户进程 在双缓冲时，如果假设缓冲区的数据传送到用户区时间M远小于输入时间T或计算 时间C， 系统处理一块数据的最大时间可粗略地认为max(C，T)。 如果C＜T，可使磁盘数据连续输入； 如果C＞T，可使CPU不必等待数据输入；

1. 磁盘性能参数：转速、寻道时间、磁盘缓存；
2. 磁盘控制器：IDE、SCSI、SATA磁盘控制器；
3. RAID等磁盘容错技术；
4. 磁盘管理算法：磁盘调度算法、磁盘高速缓存、高性能的文件系统；环形缓冲区方式

寻道时间：磁盘接收到读指令后，磁头从当前位置移到目标磁道位置，所需的时间。 旋转延迟：旋转磁盘，定位数据所在的扇区，所需的时间。 传输时间:从磁盘上读取数据，所需的时间称为数据。 访问时间＝寻道时间＋旋转延迟＋传输时间 对一般的温盘， 其寻道时间将随寻道距离的增加而增大

指旋转磁盘将指定扇区移动到磁头下面所需要的时间。 设Tτ为平均旋转延迟，r为磁盘转速（转数/单位时间） 那么 Tτ ＝ 1/(2r) （因为平均情况下，需要旋转半圈 ）

传输时间 r为磁盘每秒钟的转数；N为一条磁道上的字节数， 当一次读/写的字节数相当于半条磁道上的字节数时，Tt与Tτ相同。

访问时间Ta表示为

影响I/O性能的主要因素

1. 平均寻道时间
2. 转速

1. 先来先服务（FCFS）

2. 最短寻道时间优先算法（SSTF）

优先为距离磁头当前所在位置最近的磁道服务。

3. 扫描（SCAN)算法（电梯调度算法）

该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。

其欲访问的磁道既在当前磁道之外，又是距离最近的。

算法过程

1. 假定当前磁头向外磁道方向移动。
2. 在磁头移动过程中，如果经过的磁道有访问请求，则为其服务。
3. 然后判断当前磁道以外的磁道是否还有访问请求，如果有，则磁头继续向 外磁道方向移动；否则，判断当前磁道以内的磁道是否有访问请求，若有， 则磁头掉转方向朝内移动。
4. 若此时当前磁道内外均无访问请求，则磁头引臂停止不动

4. 循环扫描(CSCAN)算法

只是自里向外移动，当磁头移到最外的磁道并访问后，磁头立即返回到最里的欲访问的磁道，亦即将最小磁道号紧接着最大磁道号构成循环，进行循环扫描

1. 实现“按名存取”。
2. 提高对目录的检索速度。
3. 文件共享。
4. 允许文件重名。 实现“按名存取”。
5. 提高对目录的检索速度。
6. 文件共享。
7. 允许文件重名。

基本信息：文件名、文件类型等； 地址信息：卷（存储文件的设备）、起始地址（起始物理地址）、文件长度（以字节、字或块为单位）等。 访问控制信息：文件所有者、访问信息（用户名和口令等）、合法操作等； 使用信息：创建时间、创建者身份、当前状态、最近修改时间、最近访问时间等。

1. FCB存储全部目录内容
2. 存储部分目录信息，如文件名、索引节点指针等，其余部分保存在索引节点（i节点）。打开文件时将索引节点从磁盘读到内存中。

所有用户的全部文件目录保存在一张目录表中，每个文件的目录项占用一个表项。 优点

1. 简单且能实现目录管理的基本功能——按名存取

缺点

1. 查找速度慢
2. 不允许重名
3. 不便于文件共享

主文件目录MFD、用户文件目录UFD 优点

1. 一定程度解决了重名问题
2. 提高了文件目录检索效率
3. 简单的文件共享

缺点

1. 不便用户文件的逻辑分类

多级目录结构又称为树型目录结构，主目录在这里被称为根目录，把数据文件称为树叶，其它的目录均作为树的结点。

路径名：从树的根（即主目录）开始，把全部目录文件名与数据文件名，依次地用“/”连接起来，即构成该数据文件的路径名（path name）。 – 系统中的每一个文件都有惟一的路径名。 当前目录：为每个进程设置一个“当前目录”，又称为“工作目录”进程对各文件的访问都相对于“当前目录”而进行。

线性检索法又称为顺序检索法。 ①在单级目录中，利用用户提供的文件名，用顺序查找法直接从文件 目录中找到指名文件的目录项。 ②在树型目录中，用户提供的文件名是由多个文件分量名组成的路径 名，此时须对多级目录进行查找。

建立了一张Hash索引文件目录，系统利用用户提供的文件名并将它变换为文件目录的索引值，再利用该索引值到目录中去查找。

可以从不同地方打开同一个文件

1. 利用链接目录项实现

文件目录项中设置一个链接指针，用于指向共享文件的目录项。 访问文件时，根据链接指针内容找到共享文件的目录项，读取该目录项中文件起始位置等信息，操作该文件。 每当有用户（进程）共享文件时，共享文件目录项中的“共享计数”加1；当用户不再共享该文件，撤消链接指针时，“共享计数”减1。 只有当共享文件用户数为1时，才能删除共享文件。

2. 利用索引节点实现

文件的物理地址及其它的文件属性等信息，不再是放在目录项中，而是放在索引结点中。在文件目录中只设置文件名及指向相应索引结点的指针。

当用户需要共享文件时，在自己的文件目录中新建一个目录项，为共享文件命名(也可用原 名)，并将索引节点指针指向共享文件的索引节点。

3. 利用符号链实现

利用符号链方式实现文件共享时，只是文件主才拥有指向其索引结点的指针,而共享该文件的其它用户，则只有该文件的路径名，并不拥有指向其索引结点的指针。

为每一个文件分配一组相邻接的盘块。一组盘块的地址定义了磁盘上的一段线性地址。 把逻辑文件中的数据顺序地存储到物理上邻接的各个数据块中，这样形成的物理文件可以进行顺序存取 优点

1. 顺序访问容易
2. 访问速度快

缺点

1. 要求有连续的存储空间
2. 要事先知道文件长度

通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表

1. 隐式链接

在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针。 每个盘块中都含有一个指向下一个盘块的指针

2. 显式链接

把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中。 整个磁盘仅设置一张文件分配表（FAT）。

1. 单级索引

为每个文件分配一个索引块(表)，再把分配给该文件的所有盘块号都记录在该索引块中，因而该索引块就是一个含有许多盘块号的数组。

2. 两级索引

当文件太大，其一级索引块太多时，这种方法是低效的。 此时，应为这些索引块再建立一级索引，形成两级索引分配方式