操作系统常见问题整理

操作系统

操作系统问的比较多的就是进程线程的区别, 作业调度算法, 分页分段, 死锁很关键, 假脱机这部分也需要重视起来. 文中有部分算法的细节没有提到, 只是列出来名字, 需要自己补充. 当时整理的排版可能比较乱, 以后有空再整理.

计算机系统概述

操作系统的基本概念

操作系统: 是指控制和管理整个计算机系统的硬件与软件, 合理地组织, 调度计算机的工作与资源的分配, 进而为用户和其他软件提供方便接口与环境的程序集合. 操作系统是计算机系统中最基本的系统软件.

操作系统的特征:

• 并发
• 共享
• 虚拟: 物理资源的虚拟化.
• 异步

操作系统的目标和功能:

1. 计算机系统资源的管理者
2. 用户与计算机硬件系统之间的接口
3. 用作扩充机器

操作系统的发展与分类

1. 手工操作阶段: 无操作系统

2. 批处理阶段: 用户脱机使用计算机. 单道批处理 - 顺序执行, 多道批处理 - 多道程序并行, 共享资源, 不利于人机交互 但效率高

3. 分时操作系统: 时间片轮转, 多用户通过终端共享一台主机, 具有可交互性, 响应时间短. 且用户之间彼此独立互不干扰.

4. 实时操作系统: 嵌入式和工业界, 紧急状态常用. 注重响应时间.

5. 网络操作系统和分布式计算机操作系统

6. 个人计算机操作系统: 现在用, Widnows等.

   

操作系统运行的环境

CPU执行两种程序: 操作系统的内核程序,用户APP.

因此CPU执行时常分为用户态和核心态, 一些与硬件关联比较紧密或者权限比较大的都是处于核心态执行.

内核主要包括四方面:

• 时钟管理

• 中断机制

• 原语: 底层可以被调用的一些小程序, 距离硬件很近, 运行具有原子性, 执行时间短, 调用频繁.

• 系统控制的数据结构及处理: 进程管理, 存储器管理, 设备管理. 分别对应不同的数据结构, 需要进行有效管理和操作.

中断和异常:

• 异常: 内中断(指令中断或强迫中断). 异常通常出现立即处理, 依赖于当前程序的运行现场. 一般是出现意想不到的错误, 如程序非法操作码, 地址越界等.

• 中断: 外中断(强迫中断). 来自CPU指令以外的事件发生, 主要是设备的I/O处理完成,希望能向下一个设备发出I/O请求.

中断处理流程:

系统调用: 当用户在程序中调用操作系统的一些特殊子功能(包括异常), 必须切换到内核态, 比如设备管理, 内存管理, 文件管理, 进程控制, 进程通信. 用户执行”陷入指令trap”将CPU使用权交给操作系统内核. 等到执行完成后, 内核会将使用权交还给用户, 即返回.

操作系统体系结构

大内核和微内核: 大内核将操作系统功能作为紧密的整体放倒内核, 性能高, 各种信息共享, 但耦合度高, 管理复杂. 微内核架构下, 操作系统的一部分功能被移出内核降低内核复杂度, 移出去的分层分成若干相互独立的服务. 操作系统被划分为若干个小的定义良好的木块. 只有一个模块在内核态, 其余在用户态. 操作系统因需要频繁在用户态和核心态进行切换有性能损失.

并行性和并发性: 并行性是多个事件在同一时刻发生, 并发性指多个事件在同一时间间隔内发生. 多道程序环境下, 宏观上程序同时运行, 微观上是交替进行, 即并发性. 若想满足并行性, 可以分配到多个处理器上并行执行.

进程管理

进程与线程

在多道程序环境下, 允许多个进程并发执行, 此时他们将失去封闭性, 并具有间断性及不可再现 性的特征. 为此引入了进程的概念, 以便更好地描述和控制程序的并发执行, 实现操作系统的并发性和共享性. 进程是程序的运行过程, 是系统进行资源分配和调度的一个独立单位.

PCB是进程存在的唯一标志.

进程的五个状态: 运行态, 就绪态, 阻塞态, 创建态, 结束态.

阻塞也就是挂起, 即使处理器空闲, 没有触发挂起结束的信号, 就不能运行. 就绪态是缺资源.

进程的通信:

1. 共享存储: 有一块直接访问的共享空间, 直接读写, 互斥访问.
2. 消息传递: 通过消息来通知另一个进程要做什么. 有直接和间接, 间接就是邮箱通信, 消息队列.
3. 管道通信: 读写一个共享的pip文件(也可以视为缓冲区), 以字符流形式写入和取出.

线程和进程的比较:

1. 进程是系统进行资源分配和调度的基本单位, 线程是CPU调度和分配资源的基本单位.
2. 线程依赖于进程存在. 每个进程至少有一个线程.
3. 进程有自己的独立地址空间, 线程共享进程的地址空间.
4. 进程是用于系统资源的独立单位, 线程基本自己不拥有系统资源, 只有一些运行必不可少的资源, 其他的资源由线程共享进程的资源.
5. 进程切换开销大, 涉及CPU环境的保存和设置. 线程保存少量寄存器内容.
6. 线程通信直接共享数据即可, 进程通信需要通过进程间通信.
7. 多线程程序若有一个线程崩溃则整个程序崩溃. 多进程程序进程崩溃不影响其他进程.

处理机调度

调度往往分为三个层次:

• 作业调度(高级调度): 按照某个原则从后备状态的作业中选一个, 分配资源建立进程.
• 内存调度(中级调度): 将暂时不运行的进程调到外存等待, 挂起. 提高内存使用率和吞吐量.
• 进程调度(低级调度): 操作系统中最基本的调度, 选取进程分配.

进程调度方式: 抢占和非抢占.

经典调度算法:

1. 先来先服务 FCFS: 效率低, 非抢占 长作业有利, CPU密集型有利

2. 短作业优先 SJF: 非抢占, 长作业不利, 容易触发死锁. 作业运行时间是估计的, 不一定真正最短. 而且未考虑作业的紧迫程度.

3. 优先级调度: 设立一个优先级, 每当当前进程让出处理机时(可以是主动或被动的, 也就是抢占和非抢占), 把处理机分配给更紧迫的进程. 优先级也可以是动态的和静态的, 静态的在创建进程时就已经被确定, 动态的可以根据情况调整.

4. 高响应比优先级调度: 计算响应比, 将响应比最高的作业投入运行.

   响应比为(1+等待时间/要求服务时间).

   • 等待时间相同, 有利于短作业.
   • 要求服务时间相同, 等待时间越长响应比越高, 是先来先服务.
   • 长作业可以通过等待时间增加而提高.

5. 时间片轮转调度: 将系统所有就绪进程按到达时间分为先后次序排成一个队列, 每次都选队列中第一个进程执行, 仅能运行一个时间片, 即使未运行完成也要强制释放处理机给下一个就绪进程, 自身回到就绪队列尾端. 性能严重依赖于时间片大小的选取.

6. 多级队列: 设置多个就绪队列1、2、3…, 优先级递减, 时间片递 增. 只有等到优先级更高的队列为空时才会调度当前队列中的进程. 如果进程用完了当前队列的时间片还未执行, 则会被移到下一队列. 抢占式(时间片用完时), 开销可能较大, 对IO型进程有利, 可能会出现饥饿问题.

进程同步

• 同步: 串行执行的先后顺序不能乱.
• 互斥: 共享的临界资源只能同时由一个进程访问.

信号量 P为申请, V为释放, 互斥即信号量为1

同步问题:

1. 生产者-消费者
2. 读者-写者
3. 哲学家进餐
4. 吸烟者

死锁

死锁: 多进程的并发执行, 进行资源竞争导致的僵局, 无外力作用则每个进程都无法向前执行.

原因:

1. 系统资源竞争
2. 进程推进顺序非法(释放资源顺序不当)
3. 死锁产生的必要条件: 互斥, 非抢占, 请求并保持(要了还要), 循环等待(资源分配图有环, )

死锁避免

安全状态: 按照某个序列分配资源能够使得当前所有进程全部执行完.

只要系统处于安全状态, 就不会进入死锁. 处于不安全不一定死锁.

算法: 银行家算法

解决死锁三个方法: 死锁避免, 死锁检测, 死锁解除

饥饿和死锁的区别:

等待时间给进程推进和响应带来明显影响时成为进程饥饿. 饥饿并不代表系统已经死锁, 但至少有一个程序的执行被无限期地推迟. 差别: ① 进入饥饿的进程可以只有一个, 但是死锁必须大于等于两个; ② 出于饥饿状态的进程可以是一个就绪进程, 但是死锁状态的进程必定是阻塞进程.

内存管理

内存管理概念

由源程序变为内存中可以执行的程序通常需要:

1. 编译: 由编译程序将用户源代码编译成若干目标模块
2. 链接: 由链接程序将编译后形成的一组目标模块及所需的库函数链接在一起, 形成一个完整的装入模块.
3. 装入: 由装入程序将装入模块装入内存中运行

链接可以分为静态链接, 装入时动态链接, 运行时动态链接.

1. 静态链接: 在程序运行之前, 先把各个目标模块及所需库链接为一个完整的可执行程序, 以后不再拆开.
2. 装入时动态链接: 将应用程序编译后所得到的一组目标模块在装入内存时采用边装入边链接的 链接方式.
3. 运行时动态链接: 知道程序运行过程中需要一些模块时, 才对这些模块进行链接.

内存装入分为绝对装入, 可重定位装入,动态运行时装入.

1. 绝对装入: 在编译时就知道程序将要驻留在内存的物理地址, 编译程序产生含有物理地址的目 标代码, 不适合多道程序设计.
2. 可重定位装入: 根据内存当前情况, 将装入模块装入到内存的适当位置, 地址变换通常在装入时一次完成, 之后不再改变, 也称静态重定位. 当操作系统为程序分配一个以某地址为起始地址的连续主存区域后, 重定位时将程序中指令或操作数的逻辑地址加上这个起始地址就得到了物理地址. 在作业装入内存时, 必须分配全部的内存空间, 如果没有足够的内存, 则不能装入该作业. 相应的, 因为采用了相对地址, 一旦进入内存, 作业在运行期间也不能移动和申请新的内存空间.
3. 动态运行装入: 允许程序运行时在内存中移动位置, 把装入模块装入到内存后的所有地址都是 相对地 址, 在程序执行过程中每当访问到相应指令或数据时, 才将要访问的程序或数据的相对地址转换为物理地址. 动态重定位的实现要依靠硬件地址变换机构.

物理地址转换成逻辑地址的过程称为地址重定位.

内存保护: 主要目标还是为了保护程序地址不越界, 需要用额外寄存器维护.(不常)

覆盖与交换

• 覆盖: 把一个大的程序划分为一系列覆盖, 每个覆盖是一个相对独立的程序单位, 把程序执行时并不要求同时装入内存的覆盖组成一组, 成为覆盖段, 这个覆盖段分配到同一个存储区域, 这个存储区域成为覆盖区, 它与覆盖段一一对应. 覆盖段的大小由覆盖段中最大的覆盖来确定. (为了解决内存容量太小的问题, 打破了必须将一个程序全部信息装入内存后才能运行的限制)

• 交换: 把暂时不用的某个程序及数据部分从内存移到外存中去, 以便腾出必要的内存空间; 或者把指定 的程序或数据从外存读到相应的内存中, 并将控制权交给他, 让其在系统上运行的一种内存扩充技术. 处理器的中级调度就是采用交换技术

区别:

1. 与覆盖技术相比, 交换技术不要求程序员给出的 程序段之间的覆盖结构;
2. 交换技术主要在进程和作业之间进行, 覆盖技术主要在同一个进程或作业中进行;
3. 覆盖技术只能覆盖于覆盖程序段无关的程序段, 交换进程由换出和换入两个过程组成.

连续分配管理

1. 单一连续分配: 内存在此方式下分为系统区和用户区, 系统区仅提供给操作系统使用, 通常在低地址部分; 用户区是为用户提供的、除系统区之外的内存空间. 这种方式无需进行内存保护. 这种方式的优点是简单、无外部碎片, 可以釆用覆盖技术, 不需要额外的技术支持. 缺点是只能用于单用户、单任务的操作系统中, 有内部碎片, 存储器的利用率极低.

2. 固定连续分配: 固定分区分配是最简单的一种多道程序存储管理方式, 它将用户内存空间划分为若干个固定大小 的区域, 每个分区只装入一道作业. 当有空闲分区时, 便可以再从外存的后备作业队列中,选择适 当大小的作业装入该分区, 如此循环. 固定分区分配在划分分区时, 有两种不同的方法. (1) 分区大小相等: 用于利用一台计算机去控制多个相同对象的场合, 缺乏灵活性. (2) 分区大小不等: 划分为含有多个较小的分区、适量的中等分区及少量的大分区.

3. 动态分区分配: 动态分区分配又称为可变分区分配, 是一种动态划分内存的分区方法. 这种分区方法不预先将内存划分, 而是在进程装入内存时, 根据进程的大小动态地建立分区, 并使分区的大小正好适合进 程的需要. 因此系统中分区的大小和数目是可变的. 由于大内存的进程被换出, 若小内存进程被换入, 则容易产生更小内存的碎片.

   

   所以必须考虑下面四种内存管理算法:

   1. 首次适应算法(First fit): 空闲分区地址递增查找, 找第一个大小能满足要求的空闲分区. UNIX采用了这种, 不花里胡哨, 性能也不错.
   2. 最佳适应算法(Best fit): 空闲分区按容量递增排列, 找第一个大小满足要求的. 内存空间不一定每次都完美契合, 每次都产生很小的外部碎片, 根本无法利用.
   3. 最坏适应算法(Worst fit): 与最佳相反, 按照容量递减排列. 把大的连续内存划分开了, 导致没有大的内存块.
   4. 邻近适应(Next fit): 是首次适应的升级版, 在上次查找结束的位置继续查找.

非连续分配管理

将作业要求的内存空间分散地分配开

基本分页存储管理

分页思想: 主存空间划分为大小相等且固定的块, 块相对小, 作为主存的基本单位. 进程也按照块为单位进行划分, 进程在执行的时候, 也以块为单位逐个申请主存空间.

分页不会产生外部碎片, 但容易产生内部碎片(很小, 也称页内碎片).

进程中的块称为页, 内存中的块称为页框或页帧. 外存也按照块划分, 直接称为块. 为了方便地址转换, 页面大小设置为$2^k$. 页面大小也应该适中, 过大会导致页内碎片过多, 过小会导致交换频繁从而降低页面换入换出的效率.

地址结构分为两部分: 页号和页内偏移量. 地址长度为32位, 则011为页内地址, 即每页大小4KB, 1231位页号, 即地址空间最多允许$2^{20}$页.

地址结构决定了虚拟内存的寻址空间.

页表是便于在内存中找到指定进程所对应的每个页面的物理块, 系统为每个进程建立一个页表, 记录页面在内存中的物理块号(页帧号).

页表由页表项组成. 页表项和物理地址都由两部分组成, 第一部分都是页号, 页表项第二部分是物理内存的块号, 地址的第二部分是页内偏移量.

一页对应多个地址单元, 所以地址结构是由页内偏移量和页号组成的. 页表的作用是实现页号到物理块号的地址映射.

基本地址变换机构

系统中的页表寄存器PTR, 有页表存放在内存的起始位置F, 页表长度M. 进程执行前F和M放在PCB中, 执行时将其调入页表寄存器. 设页面大小L., 逻辑地址A到物理地址E的变化如下:

1. 计算页号P, P = A / L, 页内偏移量W, W = A % L.
2. 检查P和M是否满足P < M, 否则产生越界中断.
3. 然后找P对应的页表项地址 = F + P * 页地址长度. 取出该地址对应的物理块号, 在内存中找到内容
4. E = b * L + W, 就得到了物理地址E. 然后取E中的数据或指令.

这个过程中只需要给出逻辑地址就能确定物理地址, 地址结构是页号和页内偏移量组成的, 不同的页号会映射到不同的位置, 所以说页面管理的地址是一维的.

快表: 上述过程访问了两次内存, 第一次是访问页表, 第二次是根据地址取数据或指令. 加一个高速缓存, 也叫相联存储器TLB, 用来存放当前访问的若干页表项, 只访问一次主存.

两级页表: 继续延伸页表映射的思想, 页表项过多时, 存在内存中十分浪费空间. 于是引入二级页表的结构来完成空间压缩. 地址结构变为一级页号, 二级页号, 页内偏移量. 每次进程执行时, 只需要调入一级页号其中的一页就能完成对应的地址转换. 大大降低了内存使用量(实际上就是构造页表的页表). 多级页表同理.

基本分段存储管理

分段是为了满足用户和程序员方便编程, 信息保护等需要. 不是通过硬件实现的.

分段将进程分为多个段, 段间可不连续, 段内连续. 每段从0开始编址, 分配一段 连续的地址空间. 分段的逻辑地质结构是段号和段内偏移量. 段表的地址结构为段号, 段长, 本段在主存的起始地址. 在访问某地址时, 需要给出段号和段内偏移量, 结合段表的本段起始地址, 就能找到对应的物理地址单元.

分段管理不能根据给出的一个整数确定物理地址, 因为每段的段长是不固定的, 所以无法求出段内偏移, 因此说分段管理的地址空间是二维的.

段页式管理

分页能提高内存利用率, 分段能反映程序的罗结构, 有利于段的共享.

在分段管理的基础上给每个段添加一个页表.

段页式的逻辑地质结构为段号, 页号, 页内偏移量. 段表只有一个, 页表可能有多个.

进行地址转换时, 先从段表查询到页表的起始地址, 再从页表中找到页帧号, 最后结合页内偏移量能找到对应的物理地址. 访问三次主存. 段页式的地址空间是二维的, 主要通过段号和页内偏移量就能访问对应的物理单元.

虚拟内存

传统内存有一次性和驻留性, 必须一次装入内存, 且装入后就一直留在内存直到作业运行结束.

局部性原理

• 时间局部性: 某条指令一旦被执行, 不久后可能被再次执行, 数据同理.
• 空间局部性: 程序访问某存储单元, 不久后 附近的存储单元也会被访问, 集中在一定范围内.

虚拟存储器是基于局部性原理设计的, 程序装入时只将一部分装入内存, 就可以执行程序, 访问内容不在内存时将那部分调入内存然后继续执行. 还有一个就是把暂时不用的调出内存.

请求分页管理方式

页表机制

请求分页的页表和普通也表不同, 因为不需要一次性将程序调入内存. 所以就一定会有缺页的情况, 因此必须给页表项加上标志位.

因此页表项变为: 页号, 物理块号, 状态位P, 访问字段A, 修改位M, 外存地址.

状态位P: 是否已调入内存.

访问字段A: 记录本页在一段时间内被访问的次数, 供页面置换算法参考.

修改位M: 调入内存后是否被修改过.

外存地址: 用于指出该页在外存上的地址.

缺页中断: 当要访问的页面不在内存时产生缺页中断, 操作系统将缺的页调入内存, 如果有空闲块则分配块, 如果没有则淘汰某页. 并阻塞进程, 在完成调页后唤醒.

地址变换: 在分页地址变换基础上加了一些功能.

地址变换先找快表, 找到后修改访问位, 然后利用物理块号和页内地址形成物理地址. 如果没找到就去内存中找页表, 对比状态位P, 看是否已调入内存, 未调入则调入.

页面置换算法

1. 最佳置换算法: 从主存中移出永远不再需要的页面; 如无这样的页面存在, 则选择最长时间不需要访问的页面. 于所选择的被淘汰页面将是以后永不使用的, 或者是在最长时间内不再被访问的页面, 这样可以 保证获得最低的缺页率. 即被淘汰页面是以后永不使用或最长时间内不再访问的页面. (往后看)

2. 先进先出(FIFO) 置换算法: 是最简单的页面置换算法. 这种算法的基本思想是: 当需要淘汰一个页面时, 总是选择驻留主存 时间最长的页面进行淘汰, 即先进入主存的页面先淘汰. 其理由是: 最早调入主存的页面不再被 使用的可能性最大. 即优先淘汰最早进入内存的页面. (往前看) 但容易产生Belady异常, 即当物理块数增大时, 故障数不减反增.

3. 最近最久未使用(LRU) 算法: 这种算法的基本思想是: 利用局部性原理, 根据一个作业在执行过程中过去的页面访问历史来推 测未来的行为. 它认为过去一段时间里不曾被访问过的页面, 在最近的将来可能也不会再被访 问. 所以, 这种算法的实质是: 当需要淘汰一个页面时, 总是选择在最近一段时间内最久不用的 页面予以淘汰. 即淘汰最近最长时间未访问过的页面. (往前看)

4. 时钟(CLOCK)置换算法: LRU算法的性能接近于OPT,但是实现起来比较困难, 且开销大; FIFO算法实现简单, 但性能差. 所以操作系统的设计者尝试了很多算法, 试图用比较小的开销接近LRU的性能, 这类算法都是 CLOCK算法的变体. 简单的CLOCK算法是给每一帧关联一个附加位, 称为使用位. 当某一页首次装入主存时, 该帧的 使用位设置为1;当该页随后再被访问到时, 它的使用位也被置为1. 对于页替换算法, 用于替换的 候选帧集合看做一个循环缓冲区, 并且有一个指针与之相关联. 当某一页被替换时, 该指针被设 置成指向缓冲区中的下一帧. 当需要替换一页时, 操作系统扫描缓冲区, 以查找使用位被置为0的 一帧. 每当遇到一个使用位为1的帧时, 操作系统就将该位重新置为0; 如果在这个过程开始时, 缓冲区中所有帧的使用位均为0, 则选择遇到的第一个帧替换; 如果所有帧的使用位均为1,则指针 在缓冲区中完整地循环一周, 把所有使用位都置为0, 并且停留在最初的位置上, 替换该帧中的 页. 由于该算法循环地检查各页面的情况, 故称为CLOCK算法, 又称为最近未用(Not Recently Used, NRU)算法.

地址翻译: TLB->页表(TLB不命中) ->Cache->主存(Cache不命中) ->外存

文件管理

文件基本操作

文件属于抽象数据类型. 为了恰当地定义文件, 就需要考虑有关文件的操作. 操作系统提供系统 调用, 它对文件进行创建、写、读、定位和截断.

1. 创建文件: 创建文件有两个必要步骤, 一是在文件系统中为文件找到空间; 二是在目录中为新 文件创建条目, 该条目记录文件名称、在文件系统中的位置及其他可能信息.
2. 写文件: 为了写文件, 执行一个系统调用, 指明文件名称和要写入文件的内容. 对于给定文件 名称, 系统搜索目录以查找文件位置. 系统必须为该文件维护一个写位置的指针. 每当发生写操 作, 便更新写指针.
3. 读文件: 为了读文件, 执行一个系统调用, 指明文件名称和要读入文件块的内存位置. 同样, 需要搜索目录以找到相关目录项, 系统维护一个读位置的指针. 每当发生读操作时, 更新读指 针. 一个进程通常只对一个文件读或写, 所以当前操作位置可作为每个进程当前文件位置指针. 由于读和写操作都使用同一指针, 节省了空间也降低了系统复杂度.
4. 文件重定位(文件寻址) : 按某条件搜索目录, 将当前文件位置设为给定值, 并且不会读、写 文件.
5. 删除文件: 先从目录中找到要删除文件的目录项, 使之成为空项, 然后回收该文件所占用的存 储空间.
6. 截断文件: 允许文件所有属性不变, 并删除文件内容, 即将其长度设为0并释放其空间. 这6个基本操作可以组合执行其他文件操作. 例如, 一个文件的复制, 可以创建新文件、 从旧文 件读出并写入到新文件.

磁盘调度算法

寻道时间: 跨越磁道数为n, 启动磁臂时间s, m为磁盘驱动器相关的常数, 约为0.2ms
$$
T_s = m \times n + s
$$
延迟时间: 磁头定位到某一磁道的扇区所需的时间. 磁盘旋转速度为r.
$$
T_r = \frac{1}{2r}
$$
传输时间: b为每次读写的字节数和磁盘旋转速度, r为磁盘每秒转数, N为一个磁道上的字节数.
$$
T_t = \frac{b}{rN}
$$
平均存取时间:
$$
T_a = T_s+T_r+T_t
$$
磁盘调度算法:

1. 先来先服务算法(FCFS) First Come First Service 这是一种比较简单的磁盘调度算法. 它根据进程请求访问磁盘的先后次序进行调度. 此算法的优 点是公平、简单, 且每个进程的请求都能依次得到处理, 不会出现某一进程的请求长期得不到满 足的情况. 此算法由于未对寻道进行优化, 在对磁盘的访问请求比较多的情况下, 此算法将降低 设备服务的吞吐量, 致使平均寻道时间可能较长, 但各进程得到服务的响应时间的变化幅度较 小.
2. 最短寻道时间优先算法(SSTF) Shortest Seek Time First 该算法选择这样的进程, 其要求访问的磁道与当前磁头所在的磁道距离最近, 以使每次的寻道时 间最短, 该算法可以得到比较好的吞吐量, 但却不能保证平均寻道时间最短. 其缺点是对用户的 服务请求的响应机会不是均等的, 因而导致响应时间的变化幅度很大. 在服务请求很多的情况 下, 对内外边缘磁道的请求将会无限期的被延迟, 有些请求的响应时间将不可预期.
3. 扫描算法(SCAN) 电梯调度扫描算法不仅考虑到欲访问的磁道与当前磁道的距离, 更优先考虑的是磁头的当前移动方向. 例 如, 当磁头正在自里向外移动时, 扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当 前磁道之外, 又是距离最近的. 这样自里向外地访问, 直到再无更外的磁道需要访问才将磁臂换 向, 自外向里移动. 这时, 同样也是每次选择这样的进程来调度, 即其要访问的磁道, 在当前磁 道之内, 从而避免了饥饿现象的出现. 由于这种算法中磁头移动的规律颇似电梯的运行, 故又称 为电梯调度算法. 此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间 变化比较大的缺点, 而具有最短寻道时间优先算法的优点即吞吐量较大, 平均响应时间较小, 但 由于是摆动式的扫描方法, 两侧磁道被访问的频率仍低于中间磁道.
4. 循环扫描算法(CSCAN) 循环扫描算法是对扫描算法的改进. 如果对磁道的访问请求是均匀分布的, 当磁头到达磁盘的一 端, 并反向运动时落在磁头之后的访问请求相对较少. 这是由于这些磁道刚被处理, 而磁盘另一 端的请求密度相当高, 且这些访问请求等待的时间较长, 为了解决这种情况, 循环扫描算法规定 磁头单向移动. 例如, 只自里向外移动, 当磁头移到最外的被访问磁道时, 磁头立即返回到最里 的欲访磁道, 即将最小磁道号紧接着最大磁道号构成循环, 进行扫描.

I/O管理

IO的控制方式:

1. 程序直接控制方式

   计算机从外设读取数据到存储器, 每次读一个字, 每读入一个字都对外设进行循环检查, 直到确定该字已在IO控制器的数据寄存器中. CPU利用率很低, 大多数时间都在检查.

   

2. 中断驱动方式

   当某进程要启动某个 I/O 设备工作时, 便由 CPU 向相应的设备控制器发出一条 I/O 命令, 然后立 即返回继续执行原来的任务. 仅当输完一个数据时, 才需 CPU 花费极短的时间去做些中断处理.

   

3. DMA方式

   通过在I/O设备和内存之间开启一个可以直接传输数据的通路, 采用DMA控制器来控制一个数据块 的传输, CPU只需在一个数据块传输开始阶段设置好传输所需的控制信息, 并在传输结束阶段做 进一步处理.

   

IO子系统层次结构

1. 用户层IO软件
2. 设备独立性软件
3. 设备驱动程序
4. 中断处理程序
5. 硬件

假脱机技术

虚拟性是OS的四大特性之一. 如果说可以通过多道程序技术将一台物理CPU虚拟为多台逻辑 CPU, 从而允许多个用户共享一台主机, 那么, 通过SPOOling技术便可将一台物理I/O设备虚拟 为多台逻辑I/O设备, 同样允许多个用户共享一台物理I/O设备. SPOOLing技术是对脱机输入、输出系统的模拟. 相应地, SPOOLing系统必须建立在具有多道程 序功能的操作系统上, 而且还应有高速随机外存的支持, 这通常是采用磁盘存储技术. SPOOLing系统主要有以下三部分:

1. 输入井和输出井. 这是在磁盘上开辟的两个大存储空间. 输入井是模拟脱机输入时的磁盘设 备, 用于暂存I/Q设备输入的数据; 输出井是模拟脱机输出时的磁盘, 用于暂存用户程序的输出数据.
2. 输入缓冲区和输出缓冲区. 为了缓和和CPU和磁盘之间速度不匹配的矛盾, 在内存中要开辟 两个缓冲区; 输入缓冲区和输出缓冲区. 输入缓冲区用于暂存由输入设备送来的数据, 以后再传送到输入井. 输出缓冲区用与暂存从输出井送来的数据, 以后在传送给输出设备.
3. 输入进程SPi 和输入进程SP0. 这里利用两个进程来模拟脱机I/O时的外围控制机. 其中, 进 程SPi模拟脱机输入时的外围控制机, 将用户要求的数据从输入机通过输入缓冲区再送到输入井, 当CPU需要输入数据时, 直接从输入井读入内存; 进程SP0模拟脱机输出时的外围控制机, 把用户 要求输出的数据从先内存送到输出井, 待输出设备空闲时, 在将输出井中的数据经过输出缓冲区 送到输出设备上.

SPOOLing技术的特点:

1. 提高了I/O速度. 从对低速I/O设备进行的I/O操作变为对输入井或输出井的操作, 如同脱机操作 一样, 提高了I/O速度, 缓和了CPU与低速I/O设备速度不匹配的矛盾.
2. 将独占设备改造为共享设备. 因为在SPOOLing系统的系统中, 实际上并没为任何进程分配设 备, 而知识在输入井或输出井中为进程分配一个存储区和建立一张I/O请求表. 这样, 便把独占设 备改造为共享设备.
3. 实现了虚拟设备功能. 多个进程同时使用一独享设备, 而对每一进程而言, 都认为自己独占这 一设备, 从而实现了设备的虚拟分配. 不过, 该设备是逻辑上的设备.