2.2_4_调度算法：先来先服务、最短作业优先、最高响应比优先.md
2.2_5_调度算法：时间片轮转、优先级、多级反馈队列.md
- 负责管理协调硬件、软件等计算机资源的工作
- 为上层用户、应用程序提供简单易用的服务
- 是一种系统软件
-
资源的管理者
- 处理机管理
- 存储器管理
- 文件管理
- 设备管理
-
向用户提供服务
-
命令接口
- 联机命令接口
- 脱机命令接口
-
程序接口
- 由一组系统调用组成
-
GUI用户图形界面
-
-
对硬件机器的扩展
- 扩充机器
-
并发
-
共享
- 互斥共享方式（如对摄像头设备的共享使用）
- 同时共享方式（如对硬盘资源的共享使用）
-
虚拟
- 空分复用技术（如虚拟存储技术
- 时分复用技术（如虚拟处理机技术）
-
异步
-
手工操作系统
- 缺：人机速度矛盾
-
批处理阶段
-
单道批处理系统（引入脱机输入输出技术）
- 优：缓解人机速度矛盾
- 缺：资源利用率依然很低
-
多道批处理系统（操作系统开始出现）
- 优：多道程序并发执行，资源利用率高
- 缺：不提供人机交互功能
-
-
分时操作系统
- 优：提供人机交互功能
- 缺：不能优先处理紧急任务
-
实时操作系统
-
硬实时系统
- 必须在严格的规定时间内完成处理
-
软实时系统
- 能接受偶尔违反时间规定
-
优：能优先处理紧急任务
-
-
网络操作系统
-
分布式操作系统
-
个人计算机操作系统
-
运行机制
-
两种指令
-
特权指令
- 如内存清零指令
-
非特权指令
- 如普通的运算指令
-
-
两种处理机状态
- 核心态（管态）
- 用户态（目态）
-
两种程序
- 内核程序
- 应用程序
-
-
操作系统内核
-
时钟管理
-
中断处理
-
原语
- 是一种特殊的程序
- 处于操作系统最底层，是最接近硬件的部分
- 这种程序的运行具有原子性——其运行只能一气呵成，不可中断
- 运行时间较短、调用频繁
-
对系统资源进行管理的功能
- 进程管理
- 存储器管理
- 设备管理
-
-
体系结构
-
大内核
- 将操作系统的主要功能模块都作为操作系统内核，运行在核心态
- 优点：性能高
- 缺点：内核代码庞大，结构混乱，难以维护
-
微内核
- 只把最基本的功能保留在内核
- 优点：内核功能少，结构清晰，方便维护
- 缺点：需要频繁地在核心态和用户态之间切换，性能低
-
-
中断机制的诞生
- 为了实现多道程序并发执行而引入的一种技术
-
中断的概念和作用
- 发生中断，意味着需要操作系统介入开展管理工作，CPU会立即进入核心态
- “中断“是CPU从用户态进入核心态的唯一途径
-
中断的分类
-
内中断（也称异常、例外、陷入）
-
自愿中断——指令中断
-
强迫中断
- 硬件故障
- 软件中断
-
-
外中断（中断）
- 外设请求
- 人工干预
-
注意：通过中断信号来自CPU外部还是内部判断是内/外中断
-
-
补充：内中断的另一种分类方式
- 陷阱、陷入（trap）
- 故障（fault）
- 终止（abort）
-
外中断的处理过程
- 每条指令结束后，CPU检查是否有外部中断信号
- 若有外部中断信号，则需要保护中断进程的CPU环境
- 根据中断信号类型转入相应的中断处理程序
- 恢复原进程的CPU环境并退出中断，返回原进程继续向下执行
-
什么是系统调用，有何作用？
-
操作系统踢狗给应用程序使用的接口
-
应用程序通过系统调用来请求获得操作系统的服务
-
系统调用会使得处理器从用户态进入核心态
-
分类
-
设备管理
- 完成设备的 请求/释放/启动等功能
-
文件管理
- 完成文件的读/写/创建/删除等功能
-
进程控制
- 完成进程的创建/撤销/阻塞/唤醒等功能
-
进程通信
- 完成进程间的消息传递/信号传递等功能
-
内存管理
- 完成内存的分配/回收等功能
-
-
注意：凡是与资源有关的操作、会直接影响到其他进程的操作，一定需要操作系统介入，即需要通过系统调用来实现
-
-
系统调用和库函数的区别
- 系统调用是操作系统向上层提供的接口
- 有些库函数是对系统调用的进一步封装
- 当今编写的应用程序大多是通过高级语言提供的库函数间接地进行系统调用
-
系统调用背后的过程
- 1.传递系统调用参数
- 2.执行陷入指令
- 3.执行系统调用相应服务程序
- 4.返回用户程序
- 注意：系统调用发生在用户态，对系统调用的处理发生在核心态。执行陷入指令会产生内中断，使得处理器从用户态进入核心态
-
定义
- 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
-
组成
-
PCB
- 进程描述信息
- 进程控制和管理信息
- 资源分配清单
- 处理机相关信息
-
程序段
- 存放要执行的程序代码
-
数据段
- 存放程序运行过程中处理的各种数据
-
-
组织形式
-
链接方式
- 按进程状态将PCB分为多个队列
-
索引方式
- 按照进程状态建立几张索引表，各表项指向一个PCB
-
-
特征
-
动态性
- 进程的最基本特征，进程是程序的一次执行过程，是动态地产生、变化和消亡的
-
并发性
- 内存中有多个进程实体，各进程可并发执行
-
独立性
- 进程是系统进行资源分配、调度的独立单位
-
异步性
- 各进程以不可预知的速度向前推进，可能导致运行结果的不确定性
-
结构性
- 每个进程都会配置一个PCB，结构上看，进程由程序段，数据段，PCB组成
-
-
状态
-
运行状态
- CPU✅，其他所需资源✅
-
就绪状态
- CPU❌，其他所需资源✅
-
阻塞状态
- CPU❌，其他所需资源❌
-
创建状态
- 操作系统为新进程分配资源、创建PCB
-
终止状态
- 操作系统回收进程的资源、撤销PCB
-
-
进程状态间的转换
-
就绪态—>运行态
- 进程被调度
-
运行态—>就绪态
- 时间片到，或者CPU被其他高优先级的进程抢占
-
运行态—>阻塞态
- 等待系统资源分配，或等待某事件发生（主动行为）
-
阻塞态—>就绪态
- 资源分配到位，等待事件发生（被动行为）
-
创建态—>就绪态
- 系统完成创建进程相关的工作
-
运行态—>终止态
- 进程运行结束，或运行过程中遇到了不可修复的错误
-
-
基本概念
- 进程控制就是要实现进程状态的转换
- 进程控制用原语实现
-
相关原语
-
进程的创建
-
创建原语
- 1.申请空白的PCB
- 2.为新进程分配所需资源
- 3.初始化PCB
- 4.将PCB插入就绪队列
-
引起进程创建的事件
-
用户登录
- 分时系统中，用户登录成功，系统会为其建立一个新的进程
-
作业调度
- 多道批处理系统中，有新的作业放入内存时，会为其建立一个新的进程
-
提供服务
- 用户向操作系统提出某些请求时，会创建一个进程处理该请求
-
应用请求
- 由用户进程主动请求创建一个子进程
-
-
-
进程的终止
-
撤销原语
- 1.从PCB集合中找到终止进程的PCB
- 2.若进程正在运行，立即剥夺CPU,将CPU分配给其他进程
- 3.终止其所有子进程
- 4.将该进程的所有资源归还给父进程或操作系统
- 5.删除PCB
-
引起进程终止的事件
- 正常结束
- 异常结束
- 外界干预
-
-
进程的阻塞和唤醒（成对使用）
-
进程的阻塞
-
阻塞原语
- 1.找到要阻塞的进程对应的PCB
- 2.保护进程运行现场，将PCB状态信息设置为”阻塞态“，暂时停止进程运行
- 3.将PCB插入相应事件的等待队列
-
引起进程阻塞的事件
- 需要等待系统分配某种资源
- 需要等待相互合作的其他进程完成工作
-
-
进程的唤醒
-
唤醒原语
- 1.在事件等待队列中找到PCB
- 2.将PCB从等待队列移除，设置进程为就绪态
- 3.将PCB插入就绪队列，等待被调度
-
引起进程唤醒的事件
- 等待的事件发生
-
-
-
进程的切换
-
切换原语
- 1.将运行环境信息存入PCB
- 2.PCB移入相应队列
- 3.选择另一个进程执行，并更新其PCB
- 4.根据PCB恢复新进程所需的运行环境
-
引起进程切换的事件
- 当前进程时间片到
- 有更高优先级的进程到达
- 当前进程主动阻塞
- 当前进程终止
-
-
-
共享存储
-
设置一个共享空间
-
要互斥地访问共享空间
-
两种方式
- 基于数据结构（低级）
- 基于存储区（高级）
-
-
消息传递
-
传递结构化的消息（消息头/消息体）
-
系统提供”发送/接受原语“
-
两种方式
-
直接通信方式
- 消息直接挂到接收方的消息队列里
-
间接（信箱）通信方式
- 消息先发到中间体（信箱）
-
-
-
管道通信
- 设置一个特殊的共享文件（管道），其实就是一个缓冲区
- 一个管道只能实现半双工通信
- 实现双向同时通信要建立两个管道
- 各进程要互斥访问管道
- 写满时，不能再写。读空时，不能再读
- 没写满，不能读。没读空，不能写
-
什么是线程，为什么要引入线程？
-
引入线程机制后，有什么变化？（和传统的进程机制相比）
-
资源分配、调度
- 传统进程机制中，进程是资源分配、调度的基本单位
- 引入线程后，进程是资源分配的基本单位，线程是调度的基本单位
-
并发性
- 传统进程机制中，只能进程间并发
- 引入线程后，各线程间也能并发，提升了并发度
-
系统开销
- 传统进程间并发，需要切换进程的运行环境，系统开销大
- 线程间并发，如果是同一进程内的线程切换，则不需要切换进程环境，系统开销小
- 引入进程后，并发所带来的系统开销减小
-
-
线程有哪些重要的属性？
- 线程是处理机调度的单位
- 多CPU计算机中，各个线程可以占用不同的CPU
- 每个线程都有一个线程ID、线程控制块（TCB）
- 线程也有就绪、阻塞、运行三种基本状态
- 线程几乎不拥有系统资源
- 同一进程的不同线程共享进程的资源
- 由于共享内存地址空间，同一进程中的线程间通信甚至无需操作系统的干预
- 同一进程间的线程切换，不会引起进程切换
- 不同进程间的线程切换，会引起进程切换
- 切换同进程内的线程，系统开销小
- 切换进程，系统开销较大
-
线程的实现方式
-
用户级线程
- 从用户角度看的线程
-
内核级线程
- 从操作系统角度看的线程（内核级线程才是处理机分配的单位）
-
组合方式
- 上述两种方式的组合
-
-
多线程模型
-
多对一模型
- 优点：进程管理开销小，效率高
- 缺点：一个线程阻塞会导致整个进程都被阻塞（并发度低）
-
一对一模型
- 优点：各个线程可分配到多核处理机并行执行，并发度高
- 缺点：进程管理开销大
-
多对多模型
- 集二者之所长
-
-
基本概念
- 按某种算法选择一个进程将处理及分配给它
-
三个层次
-
高级调度（作业调度）
- 按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程
-
中级调度（内存调度）
- 按照某种规则，从挂起队列中选择合适的进程将其数据调回内存
-
低级调度（进程调度）
- 从就绪队列中选择一个进程为其分配 处理机
-
-
三层调度的联系、对比
-
高级调度
- 外存—>内存（面向作业）
- 发生频率：最低
-
中级调度
- 外存—>内存（面向进程）
- 发生频率：中等
-
低级调度
- 内存—>CPU
- 发生频率：最高
-
-
补充知识
- 为减轻系统负载，提高资源利用率，暂时不执行的进程会被调到外存从而变为”挂起态“
- 七状态模型：在五状态模型的基础上加入了”就绪挂起“和”阻塞挂起“两种状态
-
时机
-
什么时候需要进程调度？
-
主动放弃
- 进程正常终止
- 运行过程发生异常而终止
- 主动阻塞（如等待I/O）
-
被动放弃
- 分给进程的时间片用完
- 有更紧急的事情需要处理（如I/O中断）
- 有更高优先级的进程进入就绪队列
-
-
什么时候不能进行进程调度？
- 在处理中断的过程中
- 进程在操作系统内核程序临界区中
- 原子操作过程中（原语）
-
-
切换与过程
-
”狭义的进程调度“和”进程切换“的区别
- 狭义的进程调度指的是从就绪队列中选中一个要运行的进程，这个进程可能是刚刚被暂停的进程，也可能是另外一个进程
- 进程切换是指一个进程让出处理机，由另外一个进程占用处理机的过程
-
切换过程
- 对原来运行进程各种数据的保存
- 对新的进程各种数据的恢复
-
重要结论：进程调度、切换是有代价的，并不是调度越频繁，并发度就越高
-
-
方式
-
非剥夺调度方式（非抢占式）
- 只能当前运行的进程主动放弃CPU
-
剥夺调度方式（抢占式）
- 可由操作系统剥夺当前进程的CPU使用权
-
-
CPU利用率
- 利用率=忙碌的时间/总时间
-
系统吞吐率
- 系统吞吐率=总共完成了多大道作业/总共花了多少时间
-
周转时间
- 周转时间 = 作业完成时间 - 作业提交时间
- 平均周转时间 = 各作业周转时间之和 / 作业数
- 带权周转时间 = 作业周转时间 / 作业实际运行的时间
- 平均带权周转时间 = 各作业带权周转时间之和 / 作业数
-
等待时间
- 作业/进程 等待被服务的时间之和
- 平均等待时间即各个进程/作业等待时间的平均值
-
响应时间
- 从用户提交请求到首次产生响应所用的时间
-
先来先服务（FCFS）
- 算法思想：主要从“公平”的角度考虑
- 算法规则：按照作业/进程到达的先后顺序进行服务
- 用于作业调度时，考虑的是那个作业先到达后备队列；用于进程调度时，考虑的是哪个进程先到达就绪队列
- 非抢占式算法
- 优点：公平、算法实现简单；缺点：对长作业有利，对短作业不利（排在后面的短作业需要等待很长时间）
- 不会导致饥饿
-
短作业优先（SJF）
- 算法思想：追求最少的平均等待时间，最少的平均周转时间、最少的平均带权周转时间
- 算法规则：最短的作业/进程优先得到服务
- 既可以用于作业调度，也可以用于进程调度
- 非抢占式算法
- 优点：“最短”的平均等待时间，平均周转时间；缺点：不公平，对短作业有利，对长作业不利。另外，短作业是由用户提供的，不一定真实
- 可能会产生饥饿现象，长作业长时间得不到服务
-
高响应比优先（HRRN）
- 算法思想：要综合考虑作业/进程大的等待时间和要求服务的时间
- 算法规则：在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程进行服务。其中响应比 = （等待时间+要求服务时间）/ 要求服务时间
- 既可以用于作业调度，也可以用于进程调度
- 非抢占式算法
- 优点：综合考虑了等待时间和运行时间（要求服务时间）
- 不会导致饥饿
-
时间片轮转调度算法（RR）
- 算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
- 算法规则：按照各进程到达就绪队列的顺序，轮流让每个进程执行一个时间片。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队
- 用于进程调度
- 抢占式算法
- 优点：公平，响应快，适用于分时操作系统；缺点：由于高频率的进程切换，因此有一定的开销，另外，不区分任务的紧急程度
- 不会导致饥饿
- 时间片的选择要合适，过大或过小均不行
-
优先级调度算法
- 算法思想：根据任务的优先级决定处理的顺序
- 算法规则：调度时选择优先级最高的作业/进程
- 既可以用于作业调度，也可以用在进程调度，甚至I/O调度
- 抢占式或者非抢占式都有
- 优点：用优先级区分紧急程度，适用于实时操作系统；缺点：可能导致进程饥饿
- 会导致饥饿
-
多级反馈队列调度算法
-
算法思想：对其他调度算法的这种权衡
-
算法规则
- 1.设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
- 2.新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片。若用完时间片还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾
- 3.只有第k级队列为空时，才会为k+1级队头分配时间片
-
用于进程调度
-
抢占式算法
-
优点：相对公平
-
会导致进程饥饿
-
-
同步
- 并发现带来了异步性，有时需要通过进程同步解决这种异步问题。有的进程之间需要相互配合地完成工作，各进程地工作推进需要遵循一定的先后顺序
-
互斥
-
对临界资源地访问，需要互斥地进行。即同一时间段内只能允许一个进程访问该资源
-
四个部分
-
进入区
- 检查是否可以进入临界区，若可进入，需要“上锁”
-
临界区
- 访问临界资源地那段代码
-
退出区
- 负责“解锁”
-
剩余区
- 其余代码部分
-
-
需要遵循的原则
-
空闲让进
- 临界区空闲时，应允许一个进程访问
-
忙则等待
- 临界区正在被访问时，其他试图访问地进程需要等待
-
有限等待
- 要在有限时间内进入临界区，保证不会饥饿
-
让权等待
- 进不了临界区的进程，要释放处理机，防止忙等待
-
-
-
单标志位
- 在进入区只检查，不上锁
- 在退出区把临界区的使用权转交给另一个进程
- 主要问题：不遵循“空闲让进”原则
-
双标志先检查
- 在进入区先检查后上锁，退出区解锁
- 主要问题：不遵循“忙则等待”原则
-
双标志后检查
- 在进入区先加锁后检查，退出区解锁
- 主要问题：不遵循“空闲让进、有限等待”原则，可能导致饥饿
-
Peterson算法
- 在进入区“主动争取—主动谦让—检查对方是否想进—自己是否谦让”
- 主要问题：不遵循“让权等待”原则，会发生忙等待
-
中断屏蔽方法
- 使用“开/关中断”指令实现
- 优点：简单高效
- 缺点：只适用于单处理机；只适用于操作系统内核进程
-
TestAndSet（TS指令/TSL指令）
- 优点：实现简单，适用于多处理机环境
- 缺点：不满足“让权等待”
-
Swap指令
- 逻辑上与TSL一致
-
整型信号量
- 用一个整数型变量作为信号量，数值表示某种资源数
- 整型信号量与普通整型变量的区别：对信号量只能执行初始化、P、V三种操作
- 整型信号量存在的问题：不满足让全等待原则
-
记录型信号量
- S.value表示某种资源数，S.L指向等待该资源的队列
- P操作中，一定是先S.value--，之后可能是执行block原语
- V操作中，一定是先S.value++，之后可能是执行wakeup原语
- 注意：要能够自己推断在什么条件下需要执行block或wakeup
- 可以用记录型信号量实现系统资源的“申请”与“释放”
- 可以用记录型信号量实现进程互斥、进程同步
-
实现进程互斥
- 1.分析问题，确定临界区
- 2.设置互斥信号量，初值为1
- 3.临界区之前对信号量执行P操作
- 4.临界区之后对信号量执行V操作
-
实现进程同步
- 1.分析问题，找出哪里需要实现“一前一后”的同步关系
- 2.设置同步信号量，初值为0
- 3.在“前操作”之后执行V操作
- 4.在“后操作”之前执行P操作
-
实现进程的前驱关系
- 1.分析问题，画出前驱图，把每一对前驱关系都看成一个同步问题
- 2.为每一对前驱关系设置同步信号量，初值为0
- 3.在每个“前操作”之后执行V操作
- 4.在每个“后操作”之前执行P操作
- 1.生产者消费者问题
- 2.多生产者多消费者问题
- 3.吸烟者问题
- 4.读者写者问题
- 5.哲学家进餐问题
-
为什么要引入管程
- 为了解决信号量机制编程麻烦、易出错的问题
-
组成
- 共享数据结构
- 对数据结构初始化的语句
- 一组用来访问数据结构的过程（函数）
-
基本特征
- 各外部进程/线程只能通过管程提供的特定“入口”才能访问共享数据
- 每次仅允许一个进程在管程内执行某个内部过程
-
补充
- 各进程必须互斥访问管程的特性是由编译器实现的
- 可在管程中设置条件变量及等待/唤醒操作以解决同步问题
-
什么是死锁
- 各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进
-
死锁、饥饿、死循环的区别
- 死锁：至少是两个进程一起死锁，死锁进程处于阻塞态
- 饥饿：可能只有一个进程饥饿，饥饿进程可能阻塞也可能就绪
- 死循环：可能只有一个进程发生死循环，死循环的进程可上处理机
- 死锁和饥饿是操作系统要解决的问题，死循环是应用程序员要解决的
-
死锁产生的必要条件
-
互斥条件：对必须互斥使用的资源的争抢才会导致死锁
-
不剥夺条件：进程保持的资源只能主动释放，不可强行剥夺
-
请求和保持条件：保持着某些资源不放的同时，请求别的资源
-
循环等待条件（前三个条件产生的结果）
- 存在一种进程资源的循环等待链
- 循环等待未必死锁，死锁一定循环等待
-
-
什么时候会发生死锁
- 对不可剥夺的资源的不合理分配，可能导致死锁
-
死锁的处理策略
-
预防死锁
- 破坏死锁产生的四个必要条件
-
避免死锁
- 避免系统进入不安全状态（银行家算法）
-
死锁的检查和解除
- 允许死锁发生，系统负责检测出死锁并解除
-
-
不允许死锁发生
-
静态策略：预防死锁
-
破坏互斥条件
- 将临界资源改造为可共享使用的资源（如SPOOLing技术）
- 缺点：可行性不高，很多时候无法破坏互斥条件
-
破坏不剥夺条件
- 方案一：申请的资源得不到满足时，立即释放拥有的所有资源
- 方案二：申请的资源被其他进程占有时，由操作系统协助剥夺（考虑优先级）
- 缺点：实现复杂；剥夺资源可能导致部分工作失效；反复申请和释放导致系统开销大；可能导致饥饿
-
破坏请求和保持条件
- 运行前分配好所有需要的资源，之后一直保持
- 缺点：资源利用率低；可能导致饥饿
-
破坏循环等待条件
- 给资源编号，必须按编号从小到大的顺序申请资源
- 缺点：不方便增加新设备；会导致资源浪费；用户编程麻烦
-
-
动态策略：避免死锁
-
什么是安全序列
- 如果系统按照这种序列分配资源，则每个进程都能顺利完成，这种序列就是安全序列
-
什么是系统的不安全状态，与死锁有何联系
- 只要能找到一个安全序列，系统就处于安全状态，如果找不到，系统就处于不安全状态
- 系统处于安全状态，就一定不会发生死锁
-
如何避免系统进入不安全状态——银行家算法
- 思想：在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源的分配请求
- 步骤
-
-
-
允许死锁发生
-
死锁的检测和解除
-
如何检测
-
数据结构：资源分配图
-
两种结点
- 进程结点
- 资源结点
-
两种边
- 进程结点—>资源结点（请求边）
- 资源结点—>进程结点（分配边）
-
-
死锁检测算法
- 依次消除与不阻塞进程相连的边，直到无边可消
- 注意：所谓的不阻塞进程是指其申请的资源数足够的进程
- 死锁定理：若资源分配图是不可完全简化的，说明发生了死锁
-
-
如何解除
- 资源剥夺法
- 撤销进程法（终止进程法）
- 进程回退法
-
-
-
什么是内存，有何作用
- 存储单元、内存地址的概念和联系
- 按字节编址 vs 按字编址
-
进程运行的基本原理
-
指令的工作原理
- 操作码+若干参数（可能包含地址参数）
-
逻辑地址（相对地址） vs 物理地址（绝对地址）
-
从写程序到程序运行
-
编辑源代码文件
-
编译
- 由源代码文件生成目标模块（高级语言“翻译”为低级语言
-
链接
- 由目标模块生成装入模块，链接后形成完整的逻辑地址
-
装入
- 将装入模块装入内存，装入后形成物理地址
-
-
三种链接方式
-
静态链接
- 装入前链接成一个完整装入模块
-
装入时动态链接
- 运行前边装入边链接
-
运行时动态链接
- 运行时需要目标模块时才装入并链接
-
-
三种装入方式
-
绝对装入
- 编译时产生绝对地址
-
可重定位装入
- 装入时将逻辑地址转换为物理地址
-
动态运行时装入
- 运行时将逻辑地址转换为物理地址，需设置重定位寄存器
-
-
-
连续分配管理方式
-
单一连续分配
- 只支持单道程序，内存分为系统区和用户区，用户程序放在用户区
- 无外部碎片，有内部碎片
-
固定分区分配
-
支持多道程序，内存用户空间分为若干个固定大小的分区，每个分区只能装入一道作业
-
无外部碎片，有内部碎片
-
两种分区方式
- 分区大小相等
- 分区大小不等
-
-
动态分区分配
-
支持多道程序，在程序装入内存时，根据进程的大小动态地创建分区
-
无内部碎片，有外部碎片
-
外部碎片可以通过“紧凑”技术来解决，但是时间代价较高
-
回收内存分区时，可能遇到四种情况
- 回收区之后有相邻的空闲分区
- 回收区之前有相邻的空闲分区
- 回收区前、后都有相邻的空闲分区
- 回收区前、后都没有相邻的空闲分区
- 注意：相邻的空闲分区要合并
-
动态分区分配算法
- 首次适应算法
- 最佳适应算法
- 最坏适应算法
- 临近适应算法
-
-
-
非连续分配管理方式
-
基本分页存储管理
-
思想：把进程分页、各页面可以离散地放到各个的内存块中
-
重要概念
- “页框、页帧、内存块、物理块”与“页、页面号“
- ”页框号、页帧号、内存块号、物理块号“与”页号、页面号“
-
如何实现地址转换
- 1.计算出逻辑地址对应的页号
- 2.找到相应页面在内存中的存放位置
- 3.算出逻辑地址对应的页内偏移量
- 4.物理地址 = 页面起始地址 + 页内偏移量
-
页号、页内偏移量的计算
- 页号 = 逻辑地址/页面大小；页内偏移量 = 逻辑地址%页面大小
- 或者根据逻辑地址结构计算（二进制表示），逻辑地址 = 【页号，页内偏移量】
-
页表
- 页表记录进程页面和实际存放的内存块之间的对应关系
- 一个进程对应一张页表，进程的每一页对应一个页表项。每个页表项由页号和块号组成
- 每个页表项的长度是相同的，页号是”隐含“的
-
基本地址变换机构（硬件）
-
页表寄存器的作用
- 存放页表起始地址
- 存放页表长度
-
地址变换过程
- 1.根据逻辑地址算出页号、页内偏移量
- 2.页号的合法性检查（与页表长度相比）
- 3.若页号合法，再根据页表起始地址、页号找到相应页表项
- 4.根据页表项中记录的内存块号、页内偏移量得到最终的物理地址
- 5.访问物理内存对应的内存单元
-
其他小细节
- 页内偏移量位数与页面大小的关系
- 实际应用中，通常使得一个页框恰好能放入整数个页表项
- 为了方便找到页表项，页表一般是放在连续的内存块中的
-
-
具有快表的地址变换机构（硬件）
-
局部性原理
-
快表（TLB）
- 一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项
-
地址变换过程
-
-
两级页表
-
单级页表存在的问题
- 所有页表项必须连续存放，页表过大时需要很大的连续空间
- 在一段时间内并非所有页面都用得到，因此没有必要让整个页表项常驻内存
-
两级页表
- 将长长的页表再分页
- 逻辑地址结构：（一级页号，二级页号，页内偏移量）
- 几个术语：页目录表/外层页表/顶级页表
-
如何实现地址变换
- 1.按照地址结构将逻辑地址拆分成三部分
- 2.从PCB中读出页目录表起始地址，根据一级页号查找页目录表，找到下一级页表在内存中的存放位置
- 3.根据二级页号查找，找到最终想要访问的内存块号
- 4.结合页内偏移量得到物理地址
-
几个细节
- 多级页表中，各级页表的大小不能超过一个页面。若两级页面不够，可以分更多级
- 多级页表的访存次数（假设没有快表结构）——N级页表访问一个逻辑地址需要N+1次访存
-
-
-
基本分段存储管理
-
分段
- 将地址空间按照程序自身的逻辑关系划分为若干个段，每段从0开始编址
- 每个段在内存中占据连续空间，但是各段之间可以不相邻
- 逻辑地址结构：【段号，段内地址】
-
段表
- 记录逻辑段到实际存储地址的映射
- 每个段对应一个段表项。各段表项长度相等，由段号（隐含）、段长、基址组成
-
地址变换
- 1.由逻辑地址得到段号、段内地址
- 2.段号与段表寄存器中的段长度比较，检查是否越界
- 3.由段表起始地址、段号找到相应的段表项
- 4.根据段表中记录的段长，检查段内地址是否越界
- 5.由段表中的”“基址+段内地址”得到最终的物理地址
- 6.访问目标单元
-
分段 VS 分页
- 分页对用户不可见，分段对用户可见
- 分段更容易实现信息的保护和共享（纯代码/可重入代码可以共享）
- 分页（单级页表）、分段访问一个逻辑地址都需要两次访存；分段存储也可以进入快表机构
-
-
段页式存储管理
-
分段+分页
- 将地址空间按照程序自身的逻辑关系划分为若干个段，再将各段分为大小相等的页面
- 将内存空间分为与页面大小的一个个内存块，系统以块为单位为进程分配内存
- 逻辑地址结构【段号，页号，页内偏移量】
-
段表与页表
- 每个段对应一个段表项。各段表项长度相同，由段号（隐含）、页表长度、页表存放地址组成
- 每个页对应一个页表项。各页表项长度相同，由页号（隐含）、页面存放的内存块号组成
-
地址变换
- 1.由逻辑地址得到段号、页号、页内偏移量
- 2.段号与段表寄存器中的段长度比较，检查是否越界
- 3.由段表起始地址、段号找到对应的段表项
- 4.根据段表项中记录的页表长度，检查页号是否越界
- 5.由段表中的页表起始地址、页号查询页表，得到相应的页表项
- 6.由页面存放的内存块好、页内偏移量得到最终的物理地址
- 7.访问目标单元
-
访问一个逻辑地址所需要的访存次数
- 第一次查段表，第二次查页表，第三次访问目标单元
- 可以引入快表机构优化，以段号和页号为关键字查询快表，即可直接找到最终的目标页面存放位置。引入快表后仅需一次访存
-
-
-
覆盖技术
-
一个固定区
- 存放最活跃的程序段
- 固定区中的程序段在运行过程中不会调入调出
-
若干覆盖区
- 不可能同时被访问的程序段可共享一个覆盖区
- 覆盖区的程序段在运行过程中会根据需要调入调出
- 必须由程序员声明覆盖结构，操作系统完成自动覆盖
- 缺点：对用户不透明，增加了用户编程负担
-
-
交换技术
- 内存紧张时，换出某些进程以腾出内存空间，再换入某些进程
- 磁盘分为文件区和对换区，换出的进程放在对换区
-
覆盖和交换的区别
- 覆盖是同一个程序或进程中的
- 交换是在不同进程（或作业）之间的
-
虚拟存储技术
-
传统存储管理方式的特征、缺点
- 一次性：作业数据必须一次性全部调入内存
- 驻留性：作业数据在整个运行期间都会常驻内存
-
局部性原理
-
时间局部性
- 现在访问的指令、数据在不久之后很可能会被再次访问
-
空间局部性
- 现在访问的内存单元周围的空间，很可能在不久后会被访问
-
高速缓存技术
- 使用频繁的数据放到更高速的存储器中
-
-
虚拟内存的定义和特征
-
定义：程序不需要全部装入内存即可运行，运行时根据需要动态调入数据，若内存不够，还需要换出一些数据
-
特征
- 多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存
- 对换性：无需在作业运行时一直常驻内存，而是允许在作业运行过程中，将作业换入/换出
- 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量远大于实际的容量
-
-
如何实现虚拟内存技术
-
访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存（请求调页功能）
-
内存空间不够时，将内存中暂时用不到的信息换出到外存（页面置换功能）
-
页面置换算法
- 最佳置换算法
- 先进先出置换算法
- 最近最少使用算法
- 时钟置换算法
- 改进型的时钟置换算法
-
-
虚拟内存的实现
-
请求分页存储管理
-
页表机制
- 在基本分页的基础上增加了几个表项
- 状态位：表示页面是否在内存中
- 访问字段：记录最近被访问过几次，或记录上次访问的时间，供置换算法选择换出页面时参考
- 修改位：表示页面调入内存后是否被修改过，只有修改过的页面才需要在置换时写回内存
- 外存地址：页面在外存中存放的位置
-
缺页中断机构
- 找到页表项后检查页面是否已在内存，若没在内存，产生缺页中断
- 缺页中断处理中，需要将目标页面调入内存，有必要时还需要换出页面
- 缺页中断属于内中断，属于内中断中的“故障”，即可能被系统修复的异常
- 一条指令在执行过程中可能产生多次缺页中断
-
地址变换机构
- 找到页表项需要检查页面是否在内存中
- 若页面不在内存中，需要请求调页
- 若内存空间不够，还需要换出页面
- 页面调入内存后，需要修改相应的页表项
-
-
请求分段存储管理
-
请求段页式存储管理
-
-
虚拟存储技术下的页面分配策略
-
驻留集
- 请求分页存储管理中给进程分配的内存块的集合
-
页面分配、置换策略
-
固定分配 vs 可变分配
- 区别在于进程运行期间驻留集大小是否可变
-
局部置换 vs 全局置换
- 区别在于发生缺页时是否只能从进程自己的页面中选择一个换出
-
固定分配局部置换
-
可变分配全局置换
-
可变分配局部置换
-
-
何时调入页面
- 预调页策略：一般用于进程运行前
- 请求调页策略：进程运行时，发现缺页再调页
-
从何处调页
- 对换区——采用连续存储方式，速度更快；文件区——采用离散存储方式，速度慢
- 对换区足够大：运行将数据从文件区复制到对换区，之后所有的页面调入、调出都是在内存与对换区之间进行
- 对换区不够大：不会修改的数据每次都从文件区调入；会修改的数据调出到对换区，需要时再从对换区调入
- UNIX方式：第一次使用的页面都从文件区调入；调出的页面都写回对换区，再次使用从对换区调入
-
抖动（颠簸）现象
- 页面频繁换入换出的现象。主要原因是分配给进程的物理块不够
-
工作集
- 在某段时间间隔里，进程实际访问页面的集合。驻留集大小一般不能小于工作集大小
- 通过工作集可以解决抖动现象
-
-
-
-
操作系统负责实现逻辑地址到物理地址的转换
-
三种方式
- 绝对装入：编译器负责地址转换（单道程序阶段，无操作系统）
- 可重定位装入：装入程序负责地址转换（早期多道批处理阶段）
- 动态运行时装入：运行时才进行地址转换（现代操作系统）
-
保证各进程在自己的内存空间内运行，不会越界访问
-
两种方式
- 设置上下限寄存器
- 利用重定位寄存器、界地址寄存器进行判断
-
文件的定义：一组有意义的信息的集合
-
文件的属性：文件名、标识符、类型、位置、大小、保护信息……
-
文件内部应该如何被组织起来的（文件的逻辑结构）
-
文件之间应该如何被组织起来（目录结构）
-
操作系统应该向上提供哪些功能（create、delete、open、close、read、write系统调用）
-
文件应如何存放在外存中（文件的物理结构）
-
操作系统如何管理 外存中的空闲块（存储空间的管理）
-
操作系统需要提供的其他文件管理功能
- 文件共享
- 文件保护
-
无结构文件
- 文件内部的数据就是一系列二进制流或字符流组成，又称为“流式文件”。比如文本文件.txt。无明显的逻辑结构
-
有结构文件
-
由记录组成，分为定长记录、可变长记录，又称记录式文件
-
逻辑结构
-
顺序文件
-
串结构
- 记录之间的顺序与关键字无关
-
顺序结构
- 记录之间的顺序按关键字顺序排列
-
-
索引文件
-
索引顺序文件
-
-
-
文件目录的实现
- 一个文件对应一个FCB，一个FCB就是一个目录项，多个FCB组成文件目录
- 对目录的操作：搜索、创建文件、删除文件、显示文件、修改文件
-
目录结构
-
单级目录结构
- 一个系统只有一张目录表，不允许文件重名
-
两级目录结构
- 不同用户的文件可以重名，但不能对文件进行分类
-
多级（树形）目录结构
- 不同目录下的文件可以重名，可以对文件进行分类，不方便文件共享
- 系统根据“文件路径”找到目标文件
- 从根目录出发的路径是“绝对路径”
- 从“当前目录”出发的是“相对路径”
-
无环图目录结构
- 在树形目录的基础上，增加一些指向同一节点的有向边，使得整个目录成为一个有向无环图
- 为共享节点设置一个共享计数器，计数器为0时才真正删除该节点
-
-
索引结点
- 除了文件名之外的所有信息都放在索引结点中，每个文件对应一个索引结点
- 目录项中只包含文件名、索引结点指针，因此每个目录项的长度大幅度减小
- 由于目录项长度减小，因此每个磁盘块可以存放更多的目录项，因此检索文件对磁盘I/O的次数就减少了很多
-
连续分配
- 要求每个文件在磁盘上占有一组连续的块
- 优点：支持顺序访问和随机访问；连续分配的文件在顺序访问时速度最快
- 缺点：不方便文件拓展，存储空间利用率低，会产生磁盘碎片
-
链接分配
-
采用离散分配方式，分为显式链接与隐式链接
-
隐式链接
- 除文件最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针
- 优点：方便文件拓展，没有碎片问题，外存利用率高
- 缺点：只支持顺序访问，不支持随机访问，查找效率低
-
显式链接
-
文件分配表（FAT）
- 一个磁盘仅设置一张FAT
- 常驻内存
-
优点：支持随机访问，不会产生外部碎片，也方便文件扩展
-
-
-
索引分配
-
系统为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块
-
如果文件太大，索引表太大，一个索引块装不下
- 链接方案
- 多层索引
- 混合索引
-
-
存储空间的划分与初始化
- 文件卷（逻辑卷）、目录区与文件区的概念
- 目录区包含文件目录、空闲表、位示图、超级块等用于文件管理的数据
-
几种管理方法
-
空闲表法
- 空闲表中记录连续空闲区的其实盘块号、盘块数
- 分配时可以采用首次适应、最佳适应等策略；回收时注意表项的合并问题
-
空闲链表法
-
空闲盘块链
- 以盘块为单位组成一条空闲链
- 分配时从链头依次取出空闲块，回收时将空闲块放在链尾
-
空闲盘区链
- 以盘区为单位组成一条空闲链表
- 分配时可采用首次使用、最佳适应等策略；回收时注意相邻空闲盘区的合并问题
-
-
位示图法
- 一个二进制位对应一个盘块
-
成组链接法
- UNIX采用的策略，适合大型文件系统
-
-
创建文件create
-
- 在外存中找到文件所需的空间
-
- 创建该文件对应的目录项
-
-
删除文件delete
-
- 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项
-
- 根据该目录项记录的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盘块
-
- 从目录表中删除文件对应的目录项
-
-
打开文件open
-
- 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项，并检查该用户是否有指定的操作权限
-
- 将目录项复制到内存中的“打开文件表”中，并将对应表目的编号返回给用户。之后用户使用打开文件表的编号来指明要操作的文件
-
-
关闭文件close
-
- 将进程的打开文件表相应表项删除
-
- 回收分配个该文件的内存空间等资源
-
- 系统打开文件表的打开计数器count减1，若count=0，则删除对应表项
-
-
读文件read
-
- 进程提供文件在打开文件表中的索引号与读入多少数据，指明读入的数据要放在内存的什么位置
-
- 从外存向内存复制数据
-
-
写文件write
-
- 进程通过打开文件表中的文件索引号指明文件，指明要写出多少数据，写回外存的数据放在内存的什么位置
-
- 操作系统从用户指定的内存区域将指定大小的数据写回写指针指向的外存
-
-
基于索引结点的共享方式（硬链接）
- 各个用户的目录项指向同一个索引结点
- 索引结点中需要有链接计数count
- 若用户想删除文件，只是删除该用户的目录项，且count--
- 只有count == 0 时才能真正删除文件数据和索引结点，否则会导致指针悬空
-
基于符号链的共享方式（软链接）
- 在一个Link型文件中记录共享文件的存放路径（比如Windows的快捷方式）
- 操作系统根据路径一层层查找目录，最终找到共享文件
- 即使软链接指向的共享文件已被删除，Link型文件依然存在，只是通过该Link文件去查找会失败而已
- 由于用软链接的方式访问共享文件时访问共享文件时要查询多级目录，会有多次磁盘I/O，因此用软链接访问共享文件的速度会更慢
-
口令保护
- 为文件设置一个”口令“，用户想要访问文件时需要提供口令，由系统验证口令是否正确
- 实现开销小，但是”口令“一般存放在FCB或 索引结点中，因此不太安全
-
加密保护
- 用一个”密码“对文件加密，用户想访问文件时，需要提供正确的密码才能够解密
- 安全性高，但是加密/解密需要耗费一定的时间（Eg：异或加密）
-
访问控制
- 用一个访问控制快（ACL）记录各个用户（或各组用户）对文件的访问权限
- 对用户的访问类型可以分为：读/写/执行/删除等
- 实现灵活，可以实现复杂的文件保护功能
- 用户接口
- 文件目录系统
- 存取控制模块
- 逻辑文件系统与文件信息缓冲区
- 物理文件系统
- 设备管理模块
- 设备
-
磁盘、磁道、扇区的概念
- 磁盘由表面涂有磁性物质的圆形盘片组成
- 每个盘片被划分为一个个磁道，每个磁道又划分为一个个扇区
-
如何在磁盘中读/写数据
- 磁头移动到目标位置，盘片旋转，对应扇区划过磁道才能完成读/写
-
盘面、柱面的概念
- 磁盘由多个盘片”摞“起来，每个盘片有两个盘面
- 所有盘面中相对位置相同的磁道组成柱面
-
磁盘的物理地址
- （柱面号，盘面号，扇区号）
-
磁盘的分类
-
根据磁头是否可移动
-
固定头磁盘
- 每个磁道有一个磁头
-
移动头磁盘
- 每个盘面只有一个磁头
-
-
根据盘片是否可更换
- 固定盘磁盘
- 可换盘磁盘
-
-
一次磁盘读/写操作需要的时间
- 寻道时间：启动磁臂、移动磁头所花的时间
- 延迟时间：将目标扇区转到磁头下面所花的时间
- 传输时间：读/写数据花费的时间
-
磁盘调度算法
-
先来先服务（FCFS）
- 按访问请求到达的先后顺序进行处理
-
最短寻找时间优先（SSTF）
- 每次都优先响应距离磁头最近的磁道访问请求
- 贪心算法的思想，能保证眼前最有，但无法保证总的寻道时间最短
- 缺点：可能导致饥饿
-
扫描算法（SCAN、电梯算法）
- 只有磁头移动到最边缘的磁道时才可以改变磁头移动方向
- 缺点：对各个位置磁道的响应频率不平均
-
循环扫描算法（C-SCAN）
- 只有磁头超某个方向移动时才会响应请求，移动到边缘后立即让磁头返回起点，返回途中不响应任何请求
-
-
交替编号
- 具体做法：让编号相邻的扇区在物理上不相邻
- 原理：读取完一个扇区后需要一段时间处理才可以继续读入下一个扇区
-
错位命名
- 具体做法：让相邻盘面的扇区编号”错位“
- 原理：与”交替编号“的原理相同。错位命名法可降低延迟时间
-
磁盘地址结构的设计
- 使用（柱面号，盘面号，扇区号）的结构
- 不使用（盘面号，柱面号，扇区号）的结构
- 原因：在读取地址连续的磁盘块时，前者不需要移动磁头
-
磁盘的初始化
- 低级格式化/物理格式化：划分扇区
- 磁盘分区（C盘、D盘、E盘）
- 逻辑格式化：建立文件系统（建立根目录文件、建立用于存储空间管理的数据结构）
-
引导块
- 计算机启动时需要运行初始化程序（自举程序）来完成初始化
- ROM中存放很小的自举装入程序
- 完整的自举程序放在初始块（引导块）中
-
坏块的管理
- 简单的磁盘：逻辑格式化时将坏块标记出来
- 复杂的磁盘：磁盘控制器维护一个坏块链，并管理备用扇区
-
什么是I/O设备
- 将数据Input/Output（输入/输出）计算机的设备
-
按使用特性分类
- 人机交互类外部设备
- 存储设备
- 网络通信设备
-
按传输速率分类
- 低速设备
- 中速设备
- 高速设备
-
按信息交换的单位分类
- 块设备（传输快、可寻址）
- 字符设备（传输慢、不可寻址、常采用中断驱动方式）
-
机械部件
-
电子部件（叫做I/O控制器，又称设备控制器）
-
主要功能
- 接受和识别CPU发出的命令（要有控制寄存器）
- 向CPU报告设备的状态（要有状态寄存器）
- 数据交换（要有数据寄存器、暂存输入/输出的数据）
- 地址识别（由I/O逻辑实现）
-
组成
- CPU与控制器之间的接口（实现控制器与CPU之间的通信）
- I/O逻辑（负责识别CPU发出的命令，并向设备发出命令）
- 控制器与设备之间的接口（实现控制器与设备之间的通信）
-
两种寄存器编址方式
-
内存映像I/O
- 控制器中的寄存器与内存同一编址
- 可以采用对内存进行操作的指令来对控制器进行操作
-
寄存器独立编址
- 控制器中的寄存器独立编址
- 需要设置专门的指令来操作控制器
-
-
-
程序直接控制方式
- CPU发出I/O命令后需要不断轮询
- CPU干预频率极高
- 每次I/O的数据传输单位为字
- 数据流向：设备—>CPU—>内存;内存—>CPU—>设备
-
中断驱动方式
- CPU发出I/O命令后可以做其他事，本次I/O完成后设备控制器发出中断信号
- CPU干预频率高
- 给次I/O的数据传输单位为字
- 数据流向：设备—>CPU—>内存;内存—>CPU—>设备
-
DMA方式
- CPU发出I/O命令后可以做其他事，本次I/O完成后DMA控制器发出中断信号
- CPU干预频率中
- 给次I/O的数据传输单位为块
- 数据流向：设备—>内存;内存—>设备
-
通道控制方式
- CPU发出I/O命令后可以做其他事，通道会执行通道程序以完成I/O，完成后通道向CPU发出中断信号
- CPU干预频率低
- 给次I/O的数据传输单位为一组块
- 数据流向：设备—>内存;内存—>设备
-
用户软件层
-
设备独立性软件
-
- 向上层提供统一的调用接口（如read/write系统调用）
-
- 设备的保护
-
- 差错处理
-
- 设备的分配与回收
-
- 数据缓冲区管理
-
- 建立逻辑设备名到物理设备名的映射关系；根据设备类型选择调用相应的驱动程序
-
-
设备驱动软件
- 主要负责对硬件设备的具体控制，它将上层发出的一系列命令（如read，write）转化为特定设备“能听懂”的一系列操作，包括设置设备寄存器，检查设备状态等
- 不同的I/O设备有不同的硬件特性，具体细节只有厂家知道，所以这些厂家需要根据设备的硬件特性设计并提供相应的驱动程序
- 驱动程序一般会以一个独立进程的方式存在
-
中断处理程序
- 进行中断处理
-
硬件
- 执行I/O操作，由机械部件、电子部件组成
- 包括设备独立性软件、设备驱动程序、中断处理程序三层
- 需要实现的功能：I/O调度、设备保护、假脱机技术（SPOOLing技术）、设备分配与回收、缓冲区管理
-
脱机技术
- 外围控制机+更高速的设备——磁带
- 作用：缓解设备与CPU的速度矛盾，实现预输入、输出
-
假脱机技术的实现原理
- 又叫SPOOLing技术，用软件的方式模拟脱机技术
- 输入井和输出井——模拟脱机输入/输出时的磁带
- 输入进程和输出进程——模拟脱机输入.输出时的外围控制机
- 输入缓冲区和输出缓冲区——内存中的缓冲区，输入、输出时的”中转站“
-
共享打印机的原理分析
-
子主题 1
- 用SPOOLing技术将独占式打印机”虚拟"称共享打印机
-
-
应考虑的因素
-
固有属性
- 独占设备、共享设备、虚拟设备（SPOOLing）
-
分配算法
- 先来先服务、优先级高者优先、短任务优先等
-
安全性
- 安全分配方式、不安全分配方式
-
-
静态分配与动态分配
- 静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源
- 动态分配：进程运行过程中动态申请设备资源
-
设备分配管理中的数据结构
-
设备控制表（DCT）
- 每个设备对应一张DCT，关键字段：类型/标识符/状态/指向COCT的指针/等待队列指针
-
控制器控制表（COCT）
- 每个控制器对应一张COCT，关键字段：状态/指向CHCT的指针/等待队列指针
-
通道控制表（CHCT）
- 每个通道对应一张CHCT，关键字段：状态/等待队列指针
-
系统设备表（SDT）
- 记录整个系统中所有设备的情况，每个设备对应一个表目，关键字段：设备类型/标识符/DCT/驱动程序入口
-
-
设备分配的步骤
- 根据进程请求的物理设备名查找SDT；根据SDT找到DCT并分配设备；根据DCT找到COCT并分配控制器；根据COCT找到CHCT并分配通道
- 注意：只有设备、控制器、通道三者都分配成功后，这次设备的分配才成功
-
设备分配步骤的改进
- 引入逻辑设备名到物理设备名的映射表（LUT）
- 用户编程时使用逻辑设备名代替物理设备名
-
缓冲区的概念
- 一般利用内存作为缓冲区
- 作用：环节CPU与设备的速度矛盾、减少对CPU的中断频率、解决数据粒度不匹配的问题、提高CPU与I/O设备之间的并行性
-
单缓冲
-
双缓冲
-
循环缓冲
-
缓冲池
XMind - Trial Version