操作系统概论
2023-02-24 21:52:21 0 举报自考操作系统概率重点总结
作者其他创作
大纲/内容
操作系统简介
操作系统是一种复杂的系统软件，是不同程序代码、数据结构、数据初始化文件的集合，可执行。
用户与硬件之间的接口
与硬件部分相互作用，为包含在硬件平台上的所有底层可编程部件提供服务。
为运行在计算机系统上的应用程序执行提供运行环境
资源的管理者
一方面保证用户程序的顺利执行，另一方面使计算机系统资源得到尽可能高效的利用，保证计算机系统的高性能
处理机管理
任意时刻处理机都只能执行一个程序流
内存管理
设备管理
文件管理
操作系统发展
无操作系统
使用电子管作为主要的器件 特点需要人工干预、没有存储功能、不能连续自动工作状态
单道批处理系统
使用晶体管作为主要的器件 特点自动性、顺序性和单道性
多道批处理系统
使用集成电路芯片作为主要的器件 特点多道性、无序性、调度性和复杂性
分时系统(CTSS)
多道批处理的加强版，特点 多路性、及时性、独立性和交互性
实时操作系统
支持实时计算的系统 特点多路性、独立性、及时性、交互性和可靠性
操作系统产品现状
主机操作系统
服务器操作系统
微机操作系统
嵌入式操作系统
特征 小巧、实时性、可装卸、代码固化、弱交互性、强稳定性、接口统一和低能耗
应用领域掌上电脑、智能手机、数码相机、自动售货机、自动取款机、工业控制设备和医疗设备等
操作系统体系结构
简单的监控程序模型---FMS和IB-SYS
单体结构模型
特点 结构简单、便于理解和实现
UNIX系统、MS-DOS、Linux、MacOsX和BOS等系统
层次结构模型
特点 单向调用、组织结构清晰
THE系统
客户/服务器模型和微内核模型
特点 系统结构清晰、较高的灵活性、可靠性和可维护性
缺点 效率不高
Match操作系统、Vxworks系统
动态可扩展结构模型
思想 在运行过程中动态的实现系统行为扩展的结构
UPCALL 微内核操作系统中通过核心层到用户服务层的调用方式来实现扩展的技术
DOWNLOAD技术 将软件构件动态的下载到内核中以达到改变操作系统行为的目的
VINO系统
操作系统的特征
并发
两个或多个事件在同一时间间隔内发生
共享
系统的资源可供内存中多个并发执行的进程共同使用
互斥共享 任意时刻一种资源只能被一个进程访问
同时共享
虚拟
通过某项技术把物理实体变成若干逻辑上的对应物（用户感觉到的）
异步性
进程已不可知的速度向前推进
指令的执行
指令周期
取指令周期 从程序计数器pc中取下一个指令存放的地址
执行周期 取到指令存放在指令寄存器中
操作系统的功能
操作系统内核
支撑功能
中断处理
定义 中断是改变处理机器执行指令顺序的一种事件
好处
使CPU可以与其他设备并行工作，能有效提高CPU的利用率
改善系统性能，支持系统的异步性
类型
同步中断 -》异常
当指令执行时由CPU控制单元产生
异步中断 -》中断
异步中断是由其他硬件设备随机产生
外部可屏蔽中断 --》由I/O设备产生的中断
外部不可屏蔽中断 --》紧急事件引起的中断
中断的原因
人为设备中断
程序性事故
硬件故障
I/O设备
外部事件
中断响应
响应中断的条件 对于可屏蔽中断，开中断是响应中断的前提
响应中断的时机
对于外部中断，CPU每执行完一条指令都会检测是否有外部中断信号的到来
单重中断的处理过程
系统关闭中断，保护断点
转中断处理程序
保护完现场 根据中断向量描述表找到相关信息并执行
恢复现场、开中断，CPU返回断点处继续执行被中断的程序
中断服务程序
中断向量 对不同中断源到来的信号编号，该编号是一个无符号整数
不可屏蔽中断的向量和异常的向量是固定的，而可屏蔽中断的向量可以通过对中断控制器的编程改变
中断描述表（IDT）是一个系统表，每一个中断或异常与向量相联系 IDT的每一项对应一个中断或异常向量，每个表由8个字节组成
中断子程序的入口地址相关信息在内存总的地址=IDTR中的地址+8*中断向量的值
时钟管理
重要性 时钟是计算机系统的脉搏
作用 时钟机制防止了一个进程垄断CPU的资源 系统可以利用时钟机制限制一个用户进程在CPU上运行的时间
分类
实时时钟（RTC）-》CMOS时钟
定义 时钟芯片，靠电池续命，最原始、最底层的数据
OS时钟
定义 PC主板上的定时/计时芯片
功能
保存当前的日期和时间，以便能通过系统调用把它们返回给用户程序
维持定时器
时钟机制
OS时钟管理硬件（可编程间隔定时器PIT）
PIT的功能是按照指定的时间间隔产生时钟中断
组成 晶振、计数器、保存寄存器
晶振能够产生固定的脉冲，每产生一次脉冲，计数器的值减一
时钟驱动程序
定义 时钟中断程序也称为时钟中断处理程序
功能
维护日期和时间
递减当前进程在一个时间内的剩余执行时间
对CPu的使用情况记账
递减报警计数器
原语操作
系统调用
定义 预先定义好的模块，它们提供一条管道让应用程序或一般用户能由此得到核心程序的服务
系统调用和函数调用
区别
用户态执行在用户态，系统态运行在系统态
系统调用与一般函数调用的执行过程不同
系统调用要进行中断处理，比一般函数多了一些系统开销
关联 Linux内核利用了一个系统调用分派表
类型
进程控制类系统调用。创建、撤销进程；获得、改变进程属性
文件操作类系统调用。创建文件、删除文件、打开文件、关闭文件和读/写文件
设备管理类系统调用。请求、释放设备
通信类系统调用。打开、关闭连接，交换信息。
信息维护类系统调用。返回系统当前日期、时间、版本号、用户数、空间内存和磁盘空间大小
过程
fork创建新进程
clone 按指定条件创建子进程
execve 运行可执行文件
exit 终止进程
getpgid 获取指定进程的设备号
open 打开文件
creat 创建新文件
read 读文件
write 写文件
优点
使编程更加容易，把用户从学习硬件设备的低级编程特性中释放出来
极大的提高了系统的安全性
进程管理
进程概念
定义 允许并发程序在某个数据集合上的运行过程
组成 进程是有正文段、用户数据段以及进程控制快组成的
进程映象
定义 进程是一个动态的实体，它随着程序中的指令的执行而不断的发生变化，在某个时刻的进程内容称为进程映像
进程特征
并发性 多个进程实体能在一段时间间隔内同时运行
动态性 创建、撤销、终止是进程实体的执行过程
独立性 进程是独立运行和资源调度的基本单位
异步性 进程的执行时断时续
结构特征 包括用户正文段、用户数据和进程控制块
进程与程序
区别
程序是静态的 进程是动态的
程序是永久的 进程是暂时的
联系
进程是程序的一次执行进程总对应至少一个特定的程序
一个程序可以对应多个进程
进程控制块
定义 进程控制块是进程实体的一部分，是操作系统中最重要的结构
内容 进程控制块记录了操作系统需要的、用于描述进程情况及控制进程运行所需要的全部信息
作用 进程实体存在的标志是--》进程控制块
信息
进程标识信息 进程标识符用于唯一标识的进程
处理机状态
通用寄存器 用户可以访问的寄存器-》暂存信息
指令计数器 存放CPU要访问下一条指令的地址
程序状态字PSW 状态信息、执行方式和找中断标识符
用户栈指针
进程调度信息 包括进程状态信息】进程优先级和进程调度所需要的其他信息
进程控制信息 程序和数据的地址、进程同步和通信机制、资源清单以及链接指针
进程状态
就绪态 -》执行
阻塞态-》就绪
运行态-》就绪 和阻塞
LINUX2.4状态
可运行状态（TASK_RUNNING）
可中断状态（TASK_INTERRUPTIBLE）
不可中断状态（TASK_UNINTERRUPTIBLE）
暂停状态（TASK_STOPPED）
跟踪状态（TASK_TRACED）--》LINUX2.6
僵尸状态（TASK_ZOMBIE）
僵尸_撤销状态（EXIT_DEAD）--》LINUX2.6
进程的组织
链接方式
系统中具有相同状态的进程的PCB用其中的链接字形成一个队列
索引方式
根据进程的状态，建立几张索引表，索引表每一个表指向一个PCB的物理块
进程队列
具有不同状态的进程就形成了不同的进程队列 就绪队列、阻塞队列
进程控制
进程创建
原因
用户登录
作业调度
提供服务
应用请求
父子进程
定义 被创建的新进程成为创建该新进程的子进程，创建者进程和非创建者进程称为父子进程
父子进程创建时候执行
父进程和子进程并发执行
父进程等待子进程的执行
父子进程地址空间使用
子进程共享父进程的空间
子进程拥有独立的地址空间
创建进程过程
申请空白的PCB
为新进程分配资源
初始化进程控制块
将新进程插入就绪队列
进程阻塞
出现进程阻塞和唤醒的可能
请求系统服务
启动某种操作
新数据尚未到达
无新工作可以做
进程阻塞的过程
将进程的状态改为阻塞态
将进程插入阻塞队列
转进程调度程序，从就绪队列中选择进程为其分配CPU
进程唤醒
进程唤醒的过程
将进程从阻塞队列中移除
将进程状态由阻塞态改为就绪态
将进程插入就绪队列
进程终止
原因
进程正常执行完毕
一个进程调用适当的系统调用，终止另外一个进程
父进程终止子进程的原因
子进程使用了超过它所分配的一些资源
分配给子进程的任务已不需要
父进程退出，父进程终止->子进程也终止
进程终止的过程
从PCB读取进程状态
若进程正在执行、则终止进程的执行
若进程有子孙进行，则终止子孙进行
释放资源
将进程的PCB移出
进程同步
定义 多任务的操作系统支持多个进程并发执行，并发执行的进程共享系统的软件和硬件资源
任务 保证在多任务共享系统资源的情况下，程序执行能够得到正常的结果
保证进程以互斥访问的方式访问临界资源（必须以互斥方式访问的资源）
具有相互合作关系的进程保证相互合作的诸进行协调进行
说明
进入区 在临界区代码之前执行，检查进程是否需要加速
临界区 进程访问临界区的代码
退出区 临界区代码之后执行，完成释放临界区访问权的功能
同步机制的准备
空闲等待
忙则等待
有限等待
让权等待
信号量机制
整形信号量机制
定义 整形信号量表示共享资源状态且只能由特殊的原子操作改变整形量
整型信号量只能通过原子操作wait和signal来改变
核心思想
为互斥访问临界资源的CS定义一个互斥信息变量，初始为1，将变量放在wait和singal之间。CS访问时wait才能正常结束使进程进入CS
记录型信号机制
value表示资源的数量 >0 可用资源数量 <0 绝对值的数量是阻塞进程的数量
value值是一表示只允许一个进程访问的进程
优点 不存在忙等，采取了让全等待
AND型信号量
核心 进程在运行过程中所需要的资源一次性的全部分配给进程，进程使用完后在全部释放
生成-消费者问题
问题描述
实现任意俩个进程对缓冲池的互斥访问
实现对生产者进程和消费者进程的协调
信号量设置
设置一个互斥信号量初始为1 实现对公共缓冲池的互斥访问
设置两个资源信号量，分别表示可用资源数量
管程
定义 描述共享资源的数据结构和在数据结构上的共享资源管理程序的集合
特征
提供程序员调用的包
任意时刻只能活跃一个管程
管程是编程语言的构件
条件变量
组成
变量的定义
变量初始化的代码
管理共享资源
进程通信
共享存储器系统
类型
基于共享数据结构的通信方式 -》间接通信方式
组成 通过有界缓冲区实现
基于共享存储区的通信方式
组成 通过对共享存储区的数据的读或写来实现通信
消息传递系统
类型
直接通信方式 操作系统利用发送程序直接把消息发送给目标程序
间接通信方式 进程之间的通信需要通过用于暂存消息的共享数据结构来实现
管道通信
定义 连续读写进程的特殊文件
位置 存在外存中
特征 没有固定长度 用于进程间的大量信息通信
消息缓冲队列
定义 消息缓冲队列机制广泛用于本地进程之间的通信
组成 数据结构、发送原语、接收原语
线程
概要 进程是进行资源是分配和独立执行的单位，线程就是把进程任务划分更小、具有独立功能的单位。
线程的描述
概念 线程是进程的实体，是被系统独立调度和分派的基本单位。
组成 运行必须的资源、程序计数器、一组寄存器和栈
分类 用户级线程和内核级线程
区别
线程的调度与切换速度 内核慢用户快
系统调用 内核级系统调用只阻塞该线程，用户级系统调用阻塞线程所属的进程
线程执行时间的分配 内核级线程CPU时间以线程为单位（独享） 用户级线程CPU时间以进程为单位（共享）
状态
就绪态 -》执行态
阻塞态-》就绪态
执行态 -》就绪态（时间片用完） -》阻塞态（申请资源）
线程控制块
定义 每个进程都是由一个数据结构表示-》基本状态、标识及记账信息-》TCB
包含的信息
线程标识符信息
处理机状态信息
线程调度信息
线程控制信息
组织方式
采用链接方式，把进程中有同一状态的TCB用指针连接成队列
线程控制
线程创建
用户级线程的创建 -》调用线程库中的实用程序完成的
过程
应用程序创建线程控制块
初始化线程控制块
将线程插入所属进程的就绪线程队列中
内核线程的创建 -》 内核创建完成
过程
申请空白线程控制块
初始化线程控制块
将线程控制块所属的线程插入所属进程的线程就绪队列中
线程终止
原因
正常结束
异常结束
外界干预
过程
根据被终止线程的标识符，从TCB集合中检索该线程的TCB，读取线程状态
若运行-》终止-》调度标志为真-》执行线程调度程序
终止线程的TCB从所在队列中移除
线程调度和切换
类型
用户线程的调度与切换
内核线程的调度与切换
线程的阻塞和唤醒
引起线程阻塞的事件
请求系统服务
启动某种操作
新数据尚未到达
阻塞过程
停止该线程的执行，将线程的状态改为阻塞态
将线程控制块插入相应的线程阻塞队列
将线程所属的进程状态改为阻塞态
将进程控制块插入相应的进程阻塞队列
调用进程调度程序，重新执行进程
用户线程唤醒过程
将改线程所属进程的状态由阻塞态改为就绪态
将该线程的所属进程的PCB从阻塞队列中移出去
将该线程的所属的进程PCBinsert到就绪队列中去
将该线程状态由阻塞改为就绪
将该线程TCB从阻塞队列remove
将该线程TCB insert到就绪队列中
内核线程阻塞过程
stop线程，change线程状态为阻塞态
TCB插入阻塞队列
重新执行线程调度
内核线程唤醒
线程状态阻塞态改成就绪态
TCB阻塞队列移除
TCB插入就绪队列
线程同步
原语操作
信号量机制
线程通信
概念 线程之间的信息交换
方式
共享内存和文件资源
读取全局变量
进程与线程的关系
资源和调度 线程是程序执行的基本单位，进程是拥有资源的基本单位
地址空间资源 不同的进程地址空间是相互独立的，同一进程的线程共享同一地址空间
通信关系 进程通信必须依靠操作系统的进程通信机制，线程通过读写全局变量来进行通信，无需操作系统干预
并发性 多进程之间可以并发执行，多线程可以，同一进程下的多个线程也可以并发执行
系统开销 创建进程的开销要大于创建线程的开销 ，线程的上下文切换要比进程的上下文切换更快
进程调度
进程调度功能
概念 进程调度是由操作系统内核的进程调度程序完成 -》schedule(）开始
功能 从就绪队列中选出在CPU上运行的新进程
调度时机
进程运行结束
进程阻塞
中断返回
优先级更高的进程到来
时间片用完
进程调度算法
选择准则
周转时间短
概念 作业被提交给系统开始到作业完成为止的这段时间
组成
作业在外存后备队列上等待调度的时间
进程在就绪队列上等待进程调度的时间
进程在CPU上执行的时间
进程等待I/O操作完成的时间
响应时间快
概念 用户提交一个请求开始到系统首次产生响应为止的这段时间
组成
输入设备的请求信息到处理机的时间
处理机对请求信息进程处理的时间
形成的响应信息回到终端显示器的时间
意义 衡量系统时间性能的重要指标
截止时间保证
概念 某个任务必须开始执行的最迟时间或必须完成的最迟时间
意义 评价实时系统性能的重要指标
系统吞吐量高
概念 单位时间内完成的作业数
处理机利用率好
概念 CPU是计算机系统中影响时间性能最重要的硬件资源
先来先服务算法（FCFS）
概念 从就绪队列的队首选择最先到达就绪队列的进程
分析 适合长进程，不利于短进程
缺点 短进程等待时间相对运行时间而言太长
短进程优先算法（SPF）
概念 从就绪队列中选择估计运行时间最短的进程
优点 适合短进程与FCFS相比降低了进行平均等待时间，提高系统吞吐量
缺点
对长进程不利，长进程可能长时间得不到调度
不能保证紧迫进程的及时处理
进程的长短根据用户的估计而定
优先权调度算法
概念 每个进程都有一个与之关联的优先权，CPU分配给就绪队列中优先级最高的进程
类型
非抢占式优先权调度算法
解释 高优先权进程一旦得到处理机，则进程一直运行-》完成或由某事件主动放弃处理机
缺点 难以保证高进程优先权进程得到及时的调度
抢占式优先权调度算法
解释 高游仙区进程的到来可以抢占CPU
策略 基于时钟中断的抢占策略
优先权的类型
静态优先权
定义 在创建时确定
进程类型
进程需要的资源数量
用户的要求
动态优先权
定义 创建时被赋予优先权随着推进或随其他等到时间的增加而改变使系统获得更好的调度性能
问题
无穷阻塞或称饥饿问题 （就绪态进程因得不到CPU而等待的时间）
解决方案
老化技术 逐渐增加系统中等待很长时间的优先权
时间片轮转调度算法
定义 系统将所有的就绪队列按先来先服务的原则，排成一个队列，每次调度把CPU分配给队首进程，执行一个时间片
时间片大小的确定
系统对响应时间的要求 进程一定 响应时间越短，时间片取值越小
就绪队列中进程的数目
系统的处理能力
评价
依赖时间片的大小 时间片大等于先来先服务算法 时间片很小 频繁的进程切换和进程调度
多级队列调度算法
定义 进程通过不同特点进行分类，每一类进程属于一个就绪队列
解释 就绪队列分为多个独立的队列
举例
优先级最高-》任务队列
优先级次之-》服务进程队列
优先级最低-》用户队列
优点 降低了进程调度的开销
缺点 对低优先权的算法存在饥饿问题
多级反馈队列调度
定义 基于多级队列调度算法 为每个队列分配一个时间片
反馈策略 队列优先级越高 时间片越短 响应时间越快
设计中考虑的问题
就绪队列的数量
根据优先权确定进程应该进去那个就绪队列的算法
确定进程何时转移到较高优先权队列的算法
确定进程何时转移到较低优先权的算法
确定进程在需要服务时应该进入那个队列的算法
实时系统的调度
提供信息
就绪时间
开始截止时间和完成截止时间
处理时间
资源要求
优先级
系统处理能力强
单处理机满足求和ΣCi/Pi<=1
n个处理机满足ΣCi/Pi<=n
抢占式调度机制
基于时钟中断的抢占
说明 高优先权进程到来之后等最近的一次时钟中断-》CPU进行重新分配
立即抢占
说明 接收外部中断信号-》立刻进行CPU重新分配
优点 比基于时钟中断抢占能够更快的获取响应速度
快速切换的机制
对外部中断的快速响应能力
快速的进程切换能力
基本条件
提供必要的调度信息
系统处理能力强
采用抢占式调度机制
具有快速切换的机制
实时调度的算法
最早截止时间优先EDF
定义 根据开始时间和截止时间来确定进程的优先级
最低松弛度优先LLF
松弛度用来表示一个实时进程的紧迫程度
完成截止时间为T 当前时间为Tc 处理完任务还需要的时间Ts
L=T-Tc-Ts
过程 选择松弛度最小的进程，把CPU分配给该进程
进程切换
定义 进程调度选择一个新的进程后要进行进程切换用新选择的进程替换原来的执行进程
过程
保存包括程序计数器和其他寄存器在内的CPU上下文环境
更新被替换进程的进程控制块
修改进程状态、把执行态改为就绪态或者阻塞态
将被替换进程的进程控制块移动到就绪队列或阻塞队列
执行进程调度选择新进程，更新进程控制块
更新内存管理的数据结构
恢复被调度程序选中进程的硬件context
多处理器调度
耦合程度分类
紧密耦合多处理器系统
组成 通过高速总线或高速交叉开关实现多个处理器之间的互连。
特征 共享主存系统个I/O设备 划分独立访问的存储器，多个处理器同时访问
松弛耦合多处理器系统
组成 通过通道或通道线路来实现多台计算机之间的互连
特征 每台计算机有自己的I/O设备和存储器 独立工作 设备通信、信息交换
连接方式 通过通道或通道线路来实现多台计算机之间的互连
处理器结构分类
对称多处理器系统
组成 属于同构的多处理器系统，在功能和结构上都是相同的
进程分配方式
静态分配
优点 进程调度开销小
定义 每个处理机建立一个专门的就绪队列
缺点 不能动态的平衡各处理器的负载，系统存在各处理器忙闲不均的情况
动态分配
定义 设置一个公共的就绪队列
特征 每个进程经过多次调度，每次获得的不一定是同一处理器
非对称多处理器系统
组成 功能和结构不相同，只有一个主处理器，多个从处理器
特征 核心部分留在主机上，只有主机执行进程调度，从机的进程是主机分配的
优点 系统处理简单
缺点 不可靠性，系统瓶颈
解决 多台处理机 集群
进程线程调度方式
自调度
概念 设置一个公共的就绪队列，任何空闲的处理器都可以自行从该就绪队列中选取一个进程或者线程运行
优点
易移植
有利于提高CPU的利用率
缺点
瓶颈问题
低效性
线程切换频繁
成组调度
概念 系统将一组相互合作的进程或线程同时分配到一组处理器上运行，进程或者线程与处理器一一对应
优点
减少线程切换、改善系统性能
减少调度开销
时间分配
面向所有应用程序平均分配处理器时间
面向所有线程平均分配处理器时间
专用处理器分配
概念 在应用程序的执行期间，专门为该应用程序分配一组处理器
优点
加速了应用程序的运行速度
避免了进程切换
死锁
概念 多个进程竞争共享资源而引起的进程不能向前推进的僵死状态-》死锁
原因 竞争共享资源且分配资源的顺序不当
条件
互斥条件 访问临界资源
请求和保持条件 进程已经保持了一个资源，提出新资源，新资源被别的进程占用，此时进程阻塞等待资源释放
不剥夺条件 进程已经获得的资源只能自己去释放
环路等待 -》存在一个环形链
死锁预防
定义 通过保证至少其中一个条件不成立来达到预防死锁的目的
实现方式
摒弃请求和保持条件 一次性获取需要的所有资源
摒弃不剥夺条件 提出新资源请求不满足立即释放已经持有的资源
摒弃环路等待条件 按序申请资源
缺点
限制了新设备的增加
系统为资源分配序号与进程实际使用资源的序号不同，造成资源的浪费
给用户编程带来了麻烦
死锁避免
定义 避免系统的资源分配状态变成不安全的状态
分类
安全状态 -》不会发生死锁
不安全状态 -》可能会发生死锁
实现方式
银行家算法
概念 进程提出资源后，系统先进行资源的试分配 安全状态-》分配 不安全状态-》不分配
实现 通过数据结构的实现
死锁的检测
检测时机
死锁可能发生的频率
死锁发生时影响的进程数量
资源分配图
描述 由一组结点和一组边组成
死锁定理
用途 用于检测系统所处的资源状态s是否为死锁状态
概念 当且仅当S状态的资源分配图是不可完全简化的
死锁的解除
终止处于死锁状态的进程
终止所有死锁进程
一次只终止一个处于死锁的进程，直到死锁解除
抢占进程所占用的资源
抢占那个进程和那些资源
回滚
饥饿
内存管理
内存结构
存储器的层次结构
定义 存储器系统是一个具有不同容量、成本和访问时间的存储设备的层次结构
层次结构 高层到低层 价格更便宜、速度更慢、容量更大
L0-》快速的CPU寄存器 -》一个时钟周期访问-》常用的数据
L1-》L1SRAM高速缓存存储器
L2-》L2SRAM高速缓存存储器
L3-》基于DRAM的主存
L4-》本地磁盘
L5-》远程服务器磁盘-》网络访问
局部性原理
定义 程序在执行时呈现局部性规律
分类
空间局部性原理 一旦程序访问了某个单元，不久之后附件的存储单元也将被访问
时间局部性原理 某条指令一旦执行，不久后该指定再次执行
意义
具有良好局部性的程序会经常访问相同的数据集合
具有良好局部性的程序比局部性差的程序能更好的利用处于高层次的存储器-》运行速度快
内存分配
程序链接
概念
将编译后的目标模块装配成一个可执行的程序
意义 链接程序不属于操作系统的构成部分，但是它为操作系统提供可装入的程序模块
分类
静态链接
概念 在程序运行前，用链接程序将目标模块链接成一个完整的装入模块
任务
对逻辑地址进行修改
变换外部调用符号
优点
程序运行的速度快
缺点
可执行文件大、占用内存空间
程序开发不够灵活、方便
修改某一模块需要重新链接
动态链接
概念 将某些目标模块的链接推迟到这些模块中的函数被调用执行时才进行-》在调用的时候才进行链接程序
优点
节省内存和外存时间
缺点
需要运行时的时间开销
程序运行时的速度变慢
程序装入
概念 系统将可运行的二进制文件装入内存中的过程
在物理地址的时机不同分类
绝对装入方式
概念 编译时产生物理地址的目标代码，绝对装入程序按照程序装入模块的物理地址将程序和数据装入内存
优点 无需对程序和数据的地址进行修改
缺点 需要预留已知程序在内存中的驻留位置
可重定位装入方式（静态方式）
概念 在编译时生成可重定位的代码，其中地址都是逻辑地址，在装入内存中再变成物理地址
特点
编译程序使目标模块的起使地址从0开始
程序装入时，装入程序根据内存的使用情况将装入到内存的某个位置，并对模块进行重定位
物理地址 = 有效逻辑地址+程序在内存的起始地址
动态运行时装入方式
概念 在程序运行的时候，通过地址映射机制，将逻辑地址变成物理地址后完成装入
优点 减少的内存的使用
缺点 增加了地址映射 增加了系统运行的时间
连续分配存储管理方式
概念 连续分配是指操作系统分配内存时，为每一个进程分配一块物理地址连续的内存空间
类型
单一连续分配方式
使用 单用户、单任务的操作系统
分类
系统区
用户区
安全 —》存储器保护机制
基址寄存器 ->存放程序在物理内存中的最小地址
界限寄存器 ->存放装入用户区程序的地址范围
固定分区分配方式
说明 将用户内存空间划分为若干个固定大小的区域，在每个用户区可以装入一道用户程序
特征
划分几个分区，允许几个进程并发执行
划分区的方法-》数量是固定的，大小可以相等也可以不相等
分区大小相等
分区大小不等
数据结构
定义记录用户分区大小和使用情况的数据结构
包含 分区编号、分区大小、分区起始地址和分区状态
分配过程
操作系统执行内存分配程序，搜索内存分区使用表
找到进程所需要的空闲分区
将该分区分配给该进程
分区状态改为已占用-》state字段置1
回收过程
执行内存回收程序完成回收操作
把回收分区的状态改为空闲-》state置为0
动态分区分配方式
说明 为进程分配大小合适的内存区域，系统中用户分区的数量和大小都是动态变化的
原理
系统只有一个初始的大空闲区，当进程请求空间后，由系统根据进程需要的空间大小划分一片空闲区
特征
分区大小是动态变化的
分区数量是动态变化的
数据结构 为实现动态分配，系统需要建立并维护记录空闲分区情况的数据结构
分类
空闲分区表
组成
分区编号
分区大小
分区起始地址
缺点
表设置多浪费内存空间
表设置少，无法记录所有空闲分区的情况
数组的大小不容易确定-》根据系统管理的最大分区确定
空闲分区链
组成
每个空闲分区建立一个节点
分区大小
分区起始地址
指向前一个空闲分区节点的指针
指向后一个空闲分区结点的指针
优点 克服空闲分区的缺点
分配算法
首次适应算法
定义 空闲分区链已递增的顺序链接，从队首寻找符合要求的空闲分区
缺点
先分配低地址部分的空闲分区
搜索空闲分区，时间开销比较大
容易留下外部碎片 -》难以被利用小的空闲分区
内部碎片不可利用 -》分区内存在一部分不被利用的空间
循环首次适应算法
定义 由首次适应算法演变而来，从上一次找到的空闲分区开始
缺点
容易使系统缺乏大空闲区
优点
空间分布均匀
查找开销小
最佳适应算法
定义 总把大小与进程所请求内存空间大小最接近的空闲分区进行分配
特征 空闲分区按照递增的顺序形成一个空闲区链
优点
避免大材小用
提高了内存利用率
缺点
容易留下内部碎片
分配流程
检索空闲分区链
寻找合适的空闲分区
将分配给进程的分区起始地址返回给内存分配的程序的调用者
修改空闲分区链表
内存回收流程
释放一块连续的内存区域
如果被释放区域与其他空闲区间相邻，则合并空闲区
修改空闲分区链
内存管理
离散内存管理 把进程离散的存储在内存中物理地址不连续的区域中
分页存储管理
基本概念
页 将一个进程的逻辑地址空间分为若干大小的片
页框 将物理内存空间分成与页大小相同的若干存储块 页=》页框
分页存储 以页框为单位将进程的若干页分别装入多个可以不相邻的页框中
页内碎片 进程的最后一页一般装不满一个页框，而形成不可利用的碎片-》内部碎片
页表 系统为进程建立的数据结构，
作用 页号到页框号的映射
特征 在内存中连续存放
地址结构
组成
页号P m（逻辑地址）-n(页内偏移量)-》INT（A/L） ---A是逻辑地址
页内偏移量W MOD（A/L)
分页地址变换
定义 将用户地址空间中的逻辑地址变换为内存空间的物理地址
任务 实现逻辑地址->物理地址的变换
过程
进程执行，PCB中页表起始地址和页表长度送CPU的页表寄存器
CPU访问逻辑单元A
由分页地址将逻辑单元转换为页号和页内偏移量
由硬件检索页表，得到A所在的页对应的页框号
页框号也页内偏移地址送物理地址寄存器 物理地址=页框大小*页框号+页内偏移量
页大小的选择
决定 机器的体系结构和操作系统共同决定的
大小 4KB
因素
管理内存的开销
内存的利用率
快表
前置条件
CPU访问内存读写数据或指令，必须访问两次内存。
第一次从内存页表中获取仿存单元所在的页框号，计算物理地址
第二次根据计算出的物理地址实现对内存单元的访问
原因
为了减少CPU的访问时间，提高访存速度
概念 -》转换后援缓冲（TLB）
目的
提高CPU访存速度而采用的专用缓存
存放最近被访问过的页表项
组成 键和值
键对应页号
值对应页所在的页框号
变换过程
CPU产生分页的逻辑地址页号和页内偏移后，将该逻辑地址的页号提交给TLB
查找TLB，如果找到，则把该页所在的页框号用于形成物理地址，否则查找内存页表找到相应的页表项，形成物理地址
查找的页表项如果不在TLB，访问完内存页表后，要把找到的页表项中的页号和页框号写到TLB中，TLB采用最近最少使用算法选择TLB的条目置换
保证TLB使用
每当进程切换时就刷新一次TLB，保证TLB中只有当前进程的页表项
在每个TLB页表项中保存地址空间标识符ASID，ASID用来标记唯一的进程
TLB性能
定义 TLB中找到某一个页号对应的页表项的百分比称为TLB命中率
有效访问时间 等于一次访问TLB的时间加上一次访问内存的时间
无效的访问时间 等于一次访问TLB的时间加上两次访问内存的时间
两级页表
定义 页表在进行分页，每个页表分页的大小与内存页框的大小相同，并为他们编号
逻辑地址结构
外层页表-》页目录表
定义 存放了每一个页表在物理内存中所在的页框号
目的 实现了逻辑地址到物理地址的映射
页表寻址过程
硬件从逻辑地址中分离出页目录号P1、页号P2和页内地址
通过页表寄存器的值和页目录号，从存放页目录的页框中找到页表所在的页框号
由页表所在的页框号和页号，从存放页表的页框号中找到进程页所在的页框号
计算物理地址 = 进程页所在的页框号*页框大小+页内地址
多级页表
定义 将外层页表再分若干页，然后为外层页表建立连续存放的索引表
反置页表
定义 每一页框设一个表项，表项中存放进程号和页号
优点
减少了页表占用的空间
地址映射过程
用进程号（进程标志符）和页号找到页框号
计算物理地址 = 页框号*页框大小+页内偏移地址
空闲页框管理
位图管理空闲页框
位图中的每一位对应一个页框
页框占用 位置->1
页框空闲 位置->0
空闲页框的链表
系统维护记录空闲页框信息的链表
空闲页框链表按递增的顺序排序
结点包含页框的地址信息、指向后面结点的指针、指向前面结点的指针
分页虚拟存储系统
定义
具有请求调入功能和置换功能，能从逻辑上对内存进行扩充的一种存储器系统
核心思想
只把一部分装入内存 需要时候装入 ->请求调入
没有足够的空间 选择换出到外存 ->置换
优点
提高内存的利用率
提高多道程序度
把逻辑地址空间和物理地址空间分开
特征
离散性 -> 进程可以分散地存储在物理内存中
多次性 ->不必把进程一次性全部装入内存
对换性 -> 内存在进程中可以换进换出
虚拟性 -> 虚拟存储系统为用户提供比实际物理地址大的逻辑内存空间
硬件支持
定义 为了实现请求分页，需要特殊的页表、缺页异常机构和支持请求分页的地址变换机构
页表
支持请求分页系统的数据结构
作用
记录描述页的各种数据
实现逻辑地址到物理地址映射时需要的页号和页框号的对应关系
页表项字段说明
页框号 ->存放页所在的页框号
状态位P->用来标识页是否在内存中
访问字段A->用于记录也最近被访问的情况
修改位M->用于标识页最近是否被修改过
保护位->用于标识页的访问权限
缺页异常机构
作用 在访问内存过程中发现缺页时产生缺页异常信号，使CPU中断当前控制流的执行，执行缺页异常处理程序，完成请求调页。
过程
分页硬件通过页表完成逻辑地址到物理地址的映射，检查页表中的状态位P，判断是否在内存中，如果不在产生缺页异常
执行操作系统的缺页异常处理过程（发生缺页异常，系统保护中断的进程状态、包括寄存器和程序计数器的内容）
修改页表
重新开始执行因缺页而中断的指令
地址变换
由分页地址变换机构从逻辑地址中分离出页号和页内偏移地址
以页号为索引查找快表，若快表中有该页的页表项，读出页框号，计算物理地址
快表中不存在，通过内存页表去查找，判断页表中的状态位P已调入内存，读取页所在的页框号，计算物理地址把该页表写入到快表中
若该页尚未调入内存，则产生缺页异常，将外存中的页调度内存，修改页表，重新执行中断指令
页的分配策略
最少页框数
定义 保证进程正常运行所需要的最少的页框数
特点
计算机的硬件结构有关
取决于指令的格式、功能和寻址地址
页分配
固定分配方式
可变分配方式
置换策略
局部置换
发生置换时，只能从请求调页进程本身的内存页中选择一个被淘汰的页，以腾出内存页框，装入请求调入的页
全局置换
发生置换时，从系统中所有进程的内存页中选择被淘汰的页
固定分配局部置换
进程创建时分配一定数量的页框
可变分配全局置换
在操作系统中广泛使用
可变分配局部置换
当进程发生缺页时，只允许从该进程在内存中的页中选出一页换出
分配算法
平均分配算法
如果系统有n个进程，m个可，平均
按比例分配算法
页框数=进程页数/所有进程页数的总和*页框数
考虑优先权的分配算法
优先权高分配多
页调入策略
调入页时机
预先调入页策略
将预计不久后会访问的页和相邻的页预先调入内存
调入页位置
对换区调入
UNIX方式
调入页过程
当调入页不在内存
产生缺页异常，通过缺页异常处理
判断内存是否满，没满缺页调入
满了选页换出，缺页调入内存
修改页表项，将页表项写入快表
页表置换算法
最佳置换算法
选择以后永远不会被访问的页或者在未来最长时间内不在被访问的页做成换出页
先进先出置换算法
每个页记录该页调入内存的时间，选择换出页进入内存时间最早的页
缺点
效率低、导致较高的缺页率
最近最久未使用算法（LRU）
选择最近最久未使用的页换出
优点
性能较好
实现简单
实现方式
寄存器
栈
技术器
附件引用位算法
为每个内存中的页增加一个8位的字节
简单Clock置换算法
每个页设置一位访问位，再将内存中的所有页都通过链接指针链接成一个循环队列
改进Clock算法
不考虑该页被修改的情况，选择最近既没有被访问过又没有被修改过的换出页
优点
提高页置换的效率
最少使用置换算法
选择最近时期内使用次数最少的页作为淘汰页
页缓冲算法
采用FIFO算法选择换出页，并为换出页表建立两个链表，被换出的页要放入两个链表中的一个
分页系统的性能分析
缺页率对有效访问时间的影响
进程执行中访问发生缺页时，需要请求从外存调入缺页。如果内存没有空闲页还需要页置换
有效访问时间 = （1-P）*mx+P*缺页异常时间
缺页异常时间=缺页异常服务时间+缺页读入时间+进程重新执行时间
工作集
基本原理
有效降低缺页率，从而提高放存的时间效率
工作集机制
进程第一次被创建，为进程指定最小工作集和最大工作集
当某进程在内存中的页数小于最大工作集，发生缺页，系统从空闲页框队列中取一页框分配
当某进程在内存中的页数大于最大工作集，发生缺页，系统从该进程的页中按照FIFO的原则，换出一个该进程的页
当空闲页框队列中空闲页数减到一个最低值，系统检查进程，对工作集大于最小工作集的进程，淘汰进程的页，是该进程的工作集等于小于最小工作集
抖动
定义 多道程序度太高，运行进程的大部分时间都用于进行页的换入、换出，而几乎不能完成任何有效工作的状态
原因
系统中的进程数量太多
进程分配到的页框太少
预防
采取局部置换策略
在CPU调度程序中引入工作集算法
挂起若干线程
分段存储管理
定义 程序员使用二维的逻辑地址，一个数用来表示段，另一个数表示段内偏移量
组成 段是一个实体
一个过程
一个数组
一堆栈
一些数值变量
优点
方便编程
分段共享
动态链接
存储空间的动态增长
基本原理
分段
定义 进程的地址空间被划分成若干片段
段表
特征
每个进程建立一张段表
记录
段号
段长
段的基址
分段的逻辑地址
特征
分段的逻辑地址是二维的
组成
段号
段内地址
段表
定义
操作系统维护的用于支持分段存储管理地址映射的数据结构
组成
段表项
段号
段基址（段的起始地址）->段界限
段长（段大小）
地址变换
段表项的起始地址=段表起始地址+段号S*段表长度
过程
以段号S作索引，从段表中找到段号为S的段表项
从找到的段表项中读出s段的基地址和段大小
如果d<=段大小，则将段基地址与段内偏移量相加，得到与逻辑单元相对应得物理单元地址
分页和分段的比较
联系
都属于离散分配
都要通过数据结构与硬件的配合实现逻辑地址到物理地址的映射
区别
页是按照物理单位划分的，分页主要是为了提高内存的利用率和支持虚拟存储
段是按逻辑单位划分的，引入段方便程序员编程
页的大小是固定的，段的大小不固定
页的空间地址是一维的，段的空间地址是二维的
分段机制比分页机制更容易实现信息的共享
段页式存储管理
出现原因
使存储系统既具有分段系统便于编程、分段共享、易于保护及可动态链接等优点
又能像分页系统那样很好的解决内存的外部碎片
基本原理
将用户的进程空间划分若干个段
将段划分若干页
特征
进程以页为单位在物理内存中存放
每个段中被离散存放的页具有逻辑相关性
地址映射
每个进程建立一个段表
每个段建立一个页表
段表存放某个段的起始地址和页表长度
地址变换过程
以段号S作索引，找到段表项，得到该段页表的起始地址
通过分页机制从段内偏移D中分离出页号P和页内偏移W
段内页号P作索引，从段S的页表中搜索页号P对应的页表项
从页表项中得到页所在的页框号
通过页框号和页内偏移得到逻辑地址对应的物理地址
LINUX伙伴系统
定义
内核应该分配一组连续的页框而建立一种稳定、高效的分配策略
特征
两个块具有相同的大小
它们的物理地址是连续的，起始地址是2b的整数倍
文件管理
文件存储器空间管理
文件命名
文件名向用户提供了简单、直观的文件访问方式
操作系统支持文件名用圆点隔开分为两部分
圆点前面的是文件名字
圆点后面的是文件扩展名
文件结构
无结构字节序列
定义
无结构字节序列文件也称为流式文件
优点
灵活性高
固定长度记录序列
定义
构成文件的基本单位具有固定长度的记录，每个记录都有内部结构
中心思想
读操作返回一个记录
写操作重写或追加记录
树形结构
定义
由一颗记录树构成，记录长度不定，在记录的固定位置包号一个关键字域，记录树按关键字域排序
文件类型
正规文件
包含
用户信息
ASCII文件
组成
多行正文组成，在某项系统中每行用回车符结束
优点
可以显示和打印
可以用通常的文本编辑器进行编辑
统一程序之间的输入和输出
二进制文件
具有一定的内部结构
使用专门的二进制文件编译器
目录文件
用于管理文件的系统文件
字符设备文件
输入输出有关
用于串行化I/O类设备
块设备文件
用于磁盘类设备
文件存取
顺序存取
磁带顺序存储方便
随机存取
任意顺序读取文件中的字节或记录
文件属性
除了保存文件名和文件数据外还保存其他文件相关的信息
组成
文件的创建日期
文件大小
修改信息
常用的属性
保护 -> 0正常，1进程退出删除该文件
口令->0未加锁 1加锁
创建者->记录中的字节数
所有者->记录中键的偏移量
只读标志->0读写1只读
隐藏标志->0正常1不在列表中显示
系统标志->0普通文件1系统文件
存档标志->0已经备份 1需要备份
ASCII二进制标志 0ASCII文件 1二进制文件
随机存取标志 0顺序存取 1随机存取
文件操作
CREATE
创建文件，并设置一些属性
DELETE
不需要某个文件，删除该文件并释放磁盘空间
OPEN
使用文件必须打开文件
将文件属性和文件地址的信息装入主存
CLOSE
存取结束，关闭文件释放内部空间表
READ
从文件中读取数据
WRITE
往文件中写数据
APPEND
向文件中追加数据
SEEK
随机存取文件
GETATTRIBUTES
获取文件属性
SETATTRIBUTES
设置文件属性
RENAME
重命名
目录管理
使用
文件系统中实现按名访问文件的重要数据结构
目录文件结构
属性放在目录项中
属性放在i结点中
目录结构
单层目录
根目录
在整个系统中设置一张线性目录表
两级目录
为每个用户提供一个私有目录
主目录
给出了用户名和用户子目录所在的物理位置
用户目录
所有文件的文件控制块
优点
解决了文件重名和文件共享问题
增加了系统的开销
缺点
增加了系统存储的开销
树形结构
多级目录->树形结构
优点
便于文件的分类
层次结构清晰，便于管理和保护
解决了重名问题，查找速度加快
缺点
查找一个文件名按路径名逐层检查
多次访问会影响速度，结构复杂
路径名
绝对路径
从根目录到文件的路径组成
相对路径
当前目录下访问
..->目录的父目录
目录操作
CREATE
创建目录
除了目录项.和..外目录为空
DELETE
删除目录
OPENDIR
目录内容读取
列出目录中的所有文件和子目录
CLOSEDIR
读目录结束后
关闭目录释放内部表空间
READDIR
标准格式返回打开目录的下一级目录项
RENAME
更换目录名
文件的读写管理和存取控制
文件系统的实现
定义 文件系统通常以2的n个连续的扇区为单位对文件进行磁盘空间的分配
簇 分配给文件的连续扇区构成的磁盘块
连续分配
定义 就是把每个文件作为一连串数据块存储在磁盘上
优点
实现简单，记录每个文件用到的簇金需要存储两个数字
读操作性能好
缺点
随着时间的推移，磁盘会变得零碎
空闲的连续簇形成空洞
使用磁盘链接表分配
定义 每个文件构造簇的链接表
优点
充分的利用每个簇
缺点
随机存取相当缓慢
使用内存的链接表分配
定义 将文件所在的磁盘簇号存放在内存的表中
MS-DOS使用这种方法进行磁盘分配
缺点
必须把整个表都存放在内存中
i结点
定义 为每个文件赋予一个被称为i结点的数据结构
特征
文件属性
文件块的磁盘地址
Liunx的Ex2文件系统
i结点包括15个地址项，每个地址存32位地址
12个地址项存直接地址
一个地址项存一次间接地址
一个地址项存二次空间地址
一个地址存三次间接地址
实现目录
前置条件
读文件前，先打开文件，操作系统利用用户给出的路径名找到相应的目录项
CP/M目录
CP/M是一个微机操作系统
特征
只有一层目录
属性
用户码->记录了文件所有者
文件名->存放文件名
扩展名->标识文件类型
范围->由该域可知某目录项是文件的第几项
块数->文件实际使用的簇的数量
最后16个域记录了簇号
MS-DOS中的目录
MS-DOS文件系统曾经是IBMPC系列所采用的文件系统
它和它的拓展（FAT32）被嵌入式系统广泛使用
MS-DOS用文件分配表即FAT作为索引表来存放文件数据所在簇的簇号
FAT文件三个版本：FAT-12，FAT-16，FAT-32
UNIX中的目录
目录结构简单
目录项包含一个文件名及其i结点
文件类型
长度
时间
所有者
簇号信息
磁盘空间管理
组成文件系统的重要功能
功能
记录空闲磁盘信息
设计文件的存放方式
规定文件系统的簇大小
簇大小
文件系统分配磁盘空间是以簇为单位的
簇太大，容易造成空间浪费
簇太小，使访问文件的时间延长
记录空闲块
空闲簇链接表
用一些空闲簇存放空闲簇的簇号通过指针链接
位图
用n位位图对应磁盘的n个簇
空闲簇 1表示
已分配簇 0表示
设备管理
定义
计算机系统中的I/O设备即输入/输出设备用于计算机系统与人通信或其他机器通信的所有设备，以及所有设备
缓冲功能
缓冲区 用来保存两个设备之间或设备与应用程序之间传输的内存区域
目的
使CPU与设备并行工作
提高系统性能
缓冲引入
数据到达速率与数据离去速率不同的地方引入缓冲区
原因
处理数据流的生产者与消费者之间的差异
协调传输数据大小不一致的设备
单缓冲
操作系统提供的最简单的缓冲类型是单缓冲区
操作系统为该操作分配一个位于主存的缓冲区
面向块设备
输入数据被传送进入系统缓冲区,当传输完成，进程把该块移到用户空间，并立即请求另一块系统缓冲区
面向流的I/O
对于每次传送一行的I/O，可以利用缓冲区保存一行数据
在输入期间用户进程被阻塞
输出期间用户进程可以把一行输出防止在缓冲区
双缓冲
通过给操作系统指定两个系统缓冲区
一个进程向这个缓冲区中传送数据时，操作系统清空或填充另一个缓冲区
优点
比单缓冲性能有所提高
缺点
增加了复杂性
循环缓冲
使用多于两个的缓冲区->循环缓冲
组成
多个缓冲区
空缓冲区 R
以装满数据的缓冲区 G
现行工作缓冲区 C
多个指针
Nextg 用于指示消费者进程下一个可用的装有数据的缓冲区
Nexti 用于指示生产者进程下一个可用的空缓冲区
Current 用于指示进程正在使用的工作缓冲区
使用
Getbuf过程
消费者使用缓冲区的数据
Releasebuf过程
进程使用完缓冲区，释放缓冲区
进程同步
使用缓冲可使生成者进程和消费者进程并行执行
nexti追上nextg阻塞生产者
nextg追上nexti阻塞消费者进程
缓冲池
组成
公共缓冲池
3种队列
空缓冲队列 emq
输入队列 inq
输出队列 outq
4种工作缓冲区
收容输入数据的缓冲区
提取输入数据的缓冲区
收容输出数据的缓冲区
提取输出数据的缓冲区
过程
Getbuf过程
Putbuf过程
工作方式
收容输入
Getbuf（emp）
将输入数据写入缓冲区
putbuf（inq，hin）
提取输入
Getbuf（inq）
从缓冲区提取数据
收容输出
要从空缓冲队列提取一个空缓冲区
Getbuf（emq）
将输出数据写入缓冲区
putbuf（outq，hout）
提取输出
Getbuf（outq）
输出数据
putbuf（emq，sout）
I/O设备
I/O系统的组成
I/O设备
设备相连的设备控制器
通道
专门输入/输出控制的专用处理器
I/O系统要通过总线与CPU、内存相连
I/O系统的结构
微机I/O系统
cpu与内存之间可以直接进行信息交换
不能与设备直接进行信息交换
需要通过设备控制器
主机I/O系统
四级结构
主机
通道
一个通道可以控制多个设备控制器
控制器
一个控制器页可以控制多个设备
设备
I/O设备的分类
按传输速率分类
低速设备
键盘和鼠标，传输速率几个-几百个字节
中速设备
打印机
数千个-数万个字节/秒
高速设备
磁带机、磁盘机、光盘机
传输速率 几十万-几兆字节/秒
按信息交换的单位分类
块设备
数据的存取以数据块为单位
字符设备
传送字节流
按设备的共享属性分类
独占设备
必须作为临界资源以互斥方式访问的设备
共享设备
允许多个进程共同访问的设备
虚拟设备
通过某种虚拟技术把一台物理设备变成若干逻辑设备
设备处理
设备控制器
组成
机械
电子 ->设备控制器->可编程
定义
设备控制器是CPU与I/O设备之间的接口，接收I/O的命令并控制设备完成I/O工作
设备控制器是一个可编址的设备，连接多个设备时可能有多个设备地址
功能
接收和识别命令
接收CPU的命令和参数放在控制器的控制寄存器中，并对命令和地址译码
数据交换
通过数据寄存器进行数据交换
将驱动器的比特流汇聚在控制器的缓冲区中形成字节块
实现CPU到控制器、控制器到CPU的双向数据传输
将控制器对设备的控制命令传输给设备控制器
设备状态的了解和报告
cpu读取设备状态
地址识别
识别它所控制的每个设备的地址
数据缓冲
在设备存储器中可以存储数据，作为CPU和I/o设备之间的缓冲
差错控制
具有差错检测功能
设备控制器组成
设备控制器与处理机的接口
数据线、控制线和地址项
设备控制器与设备的接口
设备与设备控制器的接口3类信号
数据
状态
控制信号
I/O逻辑地址
指令译码器
地址译码器
I/O通道
I/O通道是一种特殊的处理机
功能
具有执行I/O指令的能力，通过执行通道程序来控制I/O操作
大型主机系统专门用于I/O的专用计算机
优点
使CPU从控制I/O的任务中解脱
使CPU与I/O并行工作
提高CPU的利用率和系统的吞吐量
I/O控制方式
轮询
主机试图发送I/O控制命令之前，先通过反复检检测设备控制器状态寄存器的忙/闲标志位
缺点
CPU经常处于由输入/输出而造成的循环测试状态
CPU的浪费
影响系统吞吐量
中断
中断控制方式完成对I/O的控制
缺点
传输数量大，频繁中断
优点
CPU与IO设备在某些时间段上并行工作
提高CPU利用率
提高系统吞吐量
DMA控制
DMA控制需要特殊结构的设备控制器
DMA控制组成
主机与DMA接口
DMA与设备的接口
I/O控制逻辑
实现主机与设备控制器之间的数据传送
命令/状态寄存器CR
接收从CPU发来的I/O命令或有关控制信息、设备状态
内存地址寄存器MAR
存放输出数据在内存的起始地址->输出数据
存放输入数据将要被放入内存的起始地址->输入数据
数据寄存器DR
指示DMA，本次向CPU发中断信号前要读或写数据的次数
数据计数器DC
用于暂存DMA传输中要输入或输出的数据
没有使用DMA设备读取的过程
首先控制器一个比特一个比特低从设备完整地读出一块数据放入内部缓冲区中
确认该数据的正确性
控制器发中断信号，CPU执行中断处理程序，从控制器的设备寄存器中将数据读入内存
使用DMA设备读取的过程
设置MAR和DC初值
启动DMA
挪用存储周期传数据子
存储器地址MAR增1
字计数存储器DC减1
DC==0 ->请求中断
DC!=0->继续执行
设备分配
数据结构
设备控制表DCT
设备类型
设备标识符
设备状态 忙/闲
指向控制器表的指针
重复指向的次数或时间
设备队列的队首指针
控制器控制表COCT
控制器标识符
控制器状态
与控制器相连接的通道表指针
控制器队列的队首指针
控制器队列的队尾指针
系统设备表SDT
设备类型
设备标识符
设备控制表
设备驱动程序的入口地址
分配的因素
设备的固有属性
独占设备 ->独占分享策略
共享设备->同时分配多进程
可虚拟设备->物理设备采用虚拟技术变成多台逻辑上的虚拟设备
设备分配算法
先来先服务
基于优先权的分配算法
设备分配是的安全性
安全分配方式
进程发出请求就阻塞
不安全分配方式
进程发出请求继续执行
仅当所请求的设备被占用才阻塞
设备独立性和虚拟设备
定义
应用程序独立于具体使用的物理设备
逻辑设备
物理设备
目的
将逻辑设备对应的名称转换为物理设备名称
设备独立软件
执行所有设备的公有操作
向用户层软件提供统一的接口
独占设备分配程序
分配设备
分配控制器
分配通道
SPOOLing技术
定义 在多道程序环境下利用一道程序来模拟脱机输入时的外围控制机的功能
把低速I/O设备上的数据传送到高速磁盘上
利用一道程序来模拟脱机输出时外围控制机的功能
组成
输入井
输出井
输入缓冲区
输出缓冲区
输入进程spi
输出进程sp
请求I/O队列
共享打印机
由输出进程在输出井中申请空闲盘块区，并将要打印的数据送入其中
输出进程在为用户申请并填写一直用户请求打印表，将表挂到请求队列上
特点
提高了I/O速度
将独占设备改造为共享设备
实现了虚拟设备功能
I/O软件原理
目的
将软件组织成一种层次结构，低层软件用来屏蔽硬件的具体细节，高层软件提供简洁、规范的界面
分类
用户层软件
与设备无关的软件层
设备驱动程序
中断处理程序
功能
实现I/O设备的独立性
错误处理
异步传输
缓冲管理
设备的分配和释放
实现I/O控制方式
中断处理程序
作用
将发出I/O请求而被阻塞的进程唤醒
设备驱动程序
I/O进程与设备控制器之间的通信程序
接受上层软件发来的请求，发送给设备控制器
启动设备执行
属于操作系统的内核程序
与硬件无关的I/O软件
功能
设备命名
设备保护
提供独立于设备的块大小
为块设备和字符设备提供必要的缓冲技术
块设备的存储分配
分配和释放独立设备
错误处理
磁盘管理
定义
容量大、存取速度快实现随机存取
目标
提高磁盘空间利用率
提高磁盘的访问速度
磁盘结构
数据的组织和格式
磁盘设备组成
一个或多个物理盘片
磁盘片分一个或两个存储面
磁道和扇区
物理记录组成
扇区数
磁道数
磁盘面数
磁盘类型
固定头磁盘
每条磁道上都有读写磁头所有的磁头都被装在一个刚性的磁臂中
移动头磁盘
每一个盘面仅配一个磁头也被装入磁臂中
磁盘的访问时间
寻到时间
把磁臂移动在指定磁面上的时间
旋转延时时间
将指定扇区移动到磁头下面所经历的时间
传输时间
数据从磁盘读出或向磁盘写入数据时所经历的时间
磁盘调度
先来先服务
定义
根据进程请求磁盘访问磁盘的先后顺序进行调度
最短寻到时间优先
定义
根据进程请求磁盘访问磁盘磁道最近寻到时间最短进行调度
扫描算法（SCAN）
进程饥饿现象
定义
访问的磁道与当前磁道的距离
更优先考虑磁头当前的移动方向
循环扫描算法
防止了饥饿现象
自里向外扫描
NStepSCAN算法
磁臂粘着
进程反复请求对某一磁道的I/O操作，垄断了整个磁盘设备
FSCAN算法
将磁盘请求队列分为两个字队列
提高磁盘I/O速度的方法
提前读
延迟写
优化物理块的分布
虚拟盘
利用内存空间去仿真磁盘，又称RAM盘
磁盘高速缓存
内存中的一块存储空间，用来暂存从磁盘中读出的一系列盘块中的信息
0 条评论
下一页
