计算机操作系统原理.ppt

计算机操作系统原理 李国2007 12 3 本文档由知识社分享 基本授课内容 一 操作系统引论二 进程管理三 处理机调度与死锁四 存储器管理五 设备管理六 文件管理七 操作系统接口 第一章操作系统引论 1 1操作系统的目标和作用1 2操作系统的发展过程1 3操作系统的基本特性1 4操作系统的主要功能1 5操作系统的结构设计 1 1操作系统的目标和作用 一 操作系统的目标方便性有效性可扩充性开放性 二 操作系统的作用1 作为用户与计算机硬件系统之间的接口 2 作为计算机系统资源的管理者主要包括四类资源 处理机 存储器 I O设备以及信息 数据与程序 3 操作系统用作扩充机器虚拟机 在裸机的基础上 每增加一层新的操作系统的软件 就变成了功能更为强大的虚拟机或虚机器 三 推动操作系统发展的主要动力 1 不断提高计算机资源利用率2 方便用户3 器件的不断更新换代4 计算机体系结构的不断发展 1 2操作系统的发展过程 一 无操作系统的计算机系统1 人工操作方式 1946 50年代 电子管时代 特点 计算机资源昂贵 没有操作系统 工作方式 用户 用户既是程序员 操作员 还是计算机专业人员 编程语言 为机器语言 输入输出 纸带或卡片 计算机的工作特点 用户独占全机 用户独占计算机所有资源 资源利用率低 CPU等待用户 计算前 手工装入纸带或卡片 计算完成后 手工卸取纸带或卡片 CPU利用率低 主要矛盾 计算机处理能力的提高 手工操作的低效率用户独占全机的所有资源 2 脱机输入 输出方式引入外围机控制数据的提前录入和延后输出 具体参照P5图1 2 二 单道批处理系统 1 单道批处理系统的处理过程引入监督程序 成批的作业首先在外存排队等待 由监督程序负责将每一个作业装入内存 处理完成后 再掉调入下一个作业 直至运行完毕 2 单道批处理系统的特征自动性顺序性单道性 三 多道批处理系统 1 多道程序设计的基本概念用户提交的作业都先存放在外存的后备队列中 由作业调度程序按一定的算法选择若干作业调入内存 共享CPU和系统的各种资源 2 多道批处理的特征 1 多道性 在内存中有多个程序 严格而言为进程 同时执行 宏观上 2 无序性 进入内存的顺序与执行完的顺序无关 3 调度性 经过2次调度 先调度到内存 转换为进程后 进行进程调度 要CPU进行执行 3 多道批处理系统的优缺点 1 资源利用率高了 2 系统吞吐量大了 3 平均周转时间长 4 无交互能力 4 多道批处理系统需要解决的问题 1 处理机管理问题 2 内存管理问题 3 I O设备管理问题 4 文件管理问题 5 作业管理问题 处理上述问题组成一系列程序的集合 由此构成了完整意义上的操作系统 操作系统的定义 操作系统是一组控制和管理计算机硬件和软件资源 合理的组织计算机工作流程以及方便用户使用的程序的集合 四 分时系统1 定义 在一台主机上连接了多个带有显示器和键盘的终端 同时允许多个用户通过自己的终端 以交互方式使用计算机 共享主机中的资源 分时系统的结构示意图 2 分时系统实现的关键问题 1 及时接收 多路卡 2 及时处理 分时间片的原则 为此 1 用户作业可以直接进入内存 2 时间片选择大小要适当 3 分时系统的特征 1 多路性 2 独立性 3 及时性 4 交互性 五 实时系统 1 理解 系统能及时响应外部事件的请求 在规定的时间内完成对该事件的处理 并控制所有实时任务协调一致的运行 2 实时系统的应用领域 实时控制 要求与被控制的变化速度相比 其反应速度足够快 工作安全可 需要人工干预时 操作简便 如生产过程控制 宇航自动控制等 实时信息处理系统 要求计算机能够在容许的延迟时间内 相应外部的事件请求 完成对该事件的处理 并控制所有的实时设备和实时任务协调运行 如飞机订票系统 期货 股票交易系统等 3 实时系统与分时系统的比较 1 多路性 2 独立性 3 及时性 4 交互性 5 高可靠性 1 3操作系统的基本特性 一 并发性 concurrency 多个事件在同一时间段内发生 操作系统是一个并发系统 各进程间的并发 系统与应用间的并发 操作系统要完成这些并发过程的管理 并行 parallel 是指在同一时刻发生 在多道程序处理时 宏观上并发 微观上交替执行 在单处理器情况下 程序的静态实体是可执行文件 而动态实体是进程 或称作任务 并发指的是进程 二 共享性 sharing 多个进程共享有限的计算机系统资源 操作系统要对系统资源进行合理分配和使用 资源在一个时间段内交替被多个进程所用 互斥共享方式 如音频设备 资源分配后到释放前 不能被其他进程所用 同时访问方式 如可重入代码 磁盘文件 资源分配难以达到最优化 三 虚拟性 virtual 一个物理实体映射为若干个对应的逻辑实体 分时或分空间 虚拟是操作系统管理系统资源的重要手段 可提高资源利用率 CPU 每个用户 进程 的 虚处理机 存储器 每个进程都占有的地址空间 指令 数据 堆栈 显示设备 多窗口或虚拟终端如虚拟光驱 四 异步性 asynchronism 异步性也称不确定性 指进程的执行顺序和执行时间及执行结果的不确定性 程序执行结果不确定 不可再现 相同输入与环境下多次运行结果不同 多道程序设计环境下 程序按异步方式运行 多个进程并发执行 时走时停 不可预知每个进程的运行推进快慢 引发执行顺序与时间的不确定 1 4操作系统的主要功能 一 处理机管理功能 可归结为进程管理 包括以下方面进程控制 进程的创建和撤消 进程状态的转换等 进程同步 协调进程执行的顺序关系 进程通信 调度 作业调度和进程调度两层 二 存储器管理功能 1 内存分配2 内存保护3 地址映射4 内存扩充三 设备管理功能 1 设备分配2 设备处理 相当于启动 3 缓冲管理4 虚拟设备 四 文件管理功能 1 文件存储空间管理2 目录管理3 文件读写管理4 文件保护 五 用户接口 1 命令接口2 程序接口3 图形接口 1 5操作系统的结构设计 一 传统的操作系统结构1 无结构操作系统操作系统是由一组过程的集合 各过程之间相互调用 在操作系统内部不存在任何结构 也因此称为整体系统结构2 模块化操作系统结构操作系统是由按其功能划分为若干个具有一定独立性和大小的模块 每个模块具有某个方面的管理功能 规定好模块之间的接口 3 分层式操作系统结构从物理机器开始 在上面不断添加新的层次软件 实现若干功能 构成满足需要的操作系统 二 微内核操作系统1 微内核是20世纪90年代发展的现代操作系统内核结构 典型的操作系统如WindowsNT 实现了以微内核为操作系统核心 以客户 服务器为基础 并且采取了面向对象的程序设计方法的新型体系结构 2 客户 服务器模式操作系统划分为两部分 一部分用于提供各种服务的一组服务器 如进程服务器 存储器服务器等 运行在用户态 另一部分是内核 用于处理客户和服务器之间的通信 CPU执行内核程序运行在核心态 3 微内核技术 1 定义 精心设计的 能实现现代操作系统核心功能的小型内核 与一般操作系统不同 更小更精练 运行在核心态 开机长驻内存 并非一个完整的操作系统 是构建通用操作系统的重要基础 2 微内核的基本功能 进程管理 存储器管理 进程通信管理 I O设备管理 第二章进程管理 2 1进程的基本概念一 程序的顺序执行及特征1 参照课本P27图2 12 特征 顺序性封闭性可再现性 二 程序的并发执行及其特征1 前趋图 利用有向无环图中结点描述进程 有向弧描述进程执行顺序 2 并发执行的特征间断性失去并发性不可再现性 三 进程的特征与状态1 进程的特征 1 结构特征 进程实体主要包括程序段 数据段和进程控制块三部分 2 动态性是进程最基本的特征 表现在进程的创建 状态的转换 撤消等进程是有生命周期的 程序本身是静态的 3 并发性 所谓前面提到程序的并发实质上是进程的并发 4 独立性 CPU进行调度的独立单位以及进行资源分配的基本单位 5 异步性 推进顺序是异步的 2 进程的定义 1 进程是程序的一次执行 2 进程是一个程序及其数据在处理机上顺序执行时所发生的活动 3 进程是一个数据集合上运行的过程 是系统进行资源分配和调度的一个独立单位 进程是进程实体的运行过程 是系统进行资源分配和调度的一个独立单位 3 进程的三种基本状态 1 就绪状态 当进程刚刚建立后处于就绪状态 具备所有资源 只差CPU调度就可执行 一个系统中处于就绪状态的进程有多个 构成就绪队列 2 执行状态 获得CPU 进行执行 在单处理机内只有1个执行状态进程 3 阻塞状态 处于执行状态的进程因为发生某事件而暂时无法继续执行 如等待I O 申请缓冲区等 可以根据不同的阻塞原因放到不同的阻塞队列中 从而构成阻塞队列 程序1 程序2 程度段 数据段 程度段 数据段 进程1 进程2 进程1 进程2 Pcb区域 进程1pcb 进程2pcb 进程ipcb 四 进程控制块1 进程控制块的作用进程控制块 PCB 是为了描述和控制进程的运行 为进程定义的数据结构 属于进程实体的一部分 是操作系统中最重要的记录型数据结构 记录了操作系统所需要的 用于描述进程当前情况及控制进程运行的全部信息 操作系统通过PCB来对并发执行的进程来进行控制和管理的 进程存在的唯一标志是PCB 2 进程控制块的基本组成 1 进程标识符 a 内部标识符就是PCB区中的标号 是数字 b 外部标识符就是进程的实际名字 2 处理机的状态 中断时处理状态的保护 断点地址保护 3 进程调度所需信息 如进程状态 优先级 进程等待时间及阻塞原因等 4 进程控制信息 如程序段和数据段的地址 资源清单 进程同步与通信机制 进程队列中各进程的链接指针 3 PCB的组织方式 1 链接方式 2 索引方式 2 2进程控制 一 进程控制中心 操作系统内核通过原语操作实现 1 内核是基于硬件的第一层软件扩充 并长驻内存 它为系统对进程和资源进行控制和管理 提供了良好的环境 内核通常包括中断处理 时钟管理 进程控制 进程通信和调度原语 以及资源管理中的基本操作等 2 所谓原语 是由若干条机器指令构成 用以完成特定功能的一段程序 为了保证其操作的正确性 它应该是原子操作 即原语是一个不可分割的操作 二 基本进程控制原语1 进程创建原语 1 申请空白PCB 2 为新进程分配资源 3 初始化进程控制块 4 将新进程插入到就绪队列 2 进程终止原语 1 根据标识符 从PCB集合中检索出该进程的PCB 读出进程状态 2 若被终止进程属执行状态 需要重新调度新进程执行 3 该进程所有子孙进程一并终止 4 被终止进程的全部资源都被释放 3 进程阻塞原语block 1 将阻塞进程由执行状态变为阻塞状态 并加入到阻塞队列中 2 系统重新调度新进程进行执行 4 进程唤醒原语wakeup 将被唤醒进程状态由阻塞变换为就绪状态 从阻塞队列中删除 加入到就绪队列中 2 3进程同步 一 进程同步的基本概念1 两种形式的制约关系 1 间接相互制约关系 因为临界资源的特性造成进程间的制约 2 直接相互制约关系 进程之间相互协作 互相制约关系 2 临界资源 如打印机 磁带机等一段时间内只允许一个进程进行使用的资源 3 临界区 每个进程中访问临界资源的那段代码成为临界区 整个程序段分为 进入区 临界区 退出区以及剩余区 4 同步机制应遵循的规则 1 空闲让进 2 忙则等待 3 有限等待 4 让权等待 二 信号量机制 1 整型信号量Wait s whiles 0dono ops s 1 Signal s s s 1 2 记录型信号量Wait s s value s value 1 ifs value 0block s l Signal s s value s value 1 ifs value 0wakeup s l 记录型信号量的物理意义Wait 相当于分配资源的过程 若有资源进行分配 则分配后就不会小于0 因此可以完全执行完Wait原语 然后进入临界区 如减1后出现小于0的情况则表示实际上已经没有资源可以分配了 因此该进程要放到阻塞队列L中 此时S VALUE的绝对值就是阻塞进程的数量 Signal 相当于释放资源的过程 一个进程执行完正常释放资源 但加1后仍小于等于0表示它原来是个负数 因此阻塞队列里有等待该资源没有满足的阻塞进程 因此 在释放资源的同时要唤醒阻塞进程 如加1后正常的正数 就光释放完资源就结束了 3 记录型信号量的应用 1 实现互斥对于N个进程对1个临界资源的互斥共享 每个进程的算法描述 VARMutex 1 进程pi RepeatWait Mutex 临界区 Signal Mutex untilfalse 2 实现前趋关系 见p45图2 10Vara b c d e f g 0 0 0 0 0 0 0S1 s1 signal a signal b S2 wait a s2 signal c signal d S3 wait b s3 signal e S4 wait c s4 signal f S5 wait d s3 signal g S6 wait e wait f wait g s6 3 利用信号量实现进程同步 输入进程 Repeat输入数据 wait P1 放数据入缓冲区 signal P2 untilfalse 计算进程 Repeatwait p2 从缓冲区取数据 signal P1 计算数据 untilfalse 4经典进程同步问题 一 生产者 消费者问题 多个生产者进程和多个消费者进程共享一个有N个缓冲区的缓冲池 生产者进程负责输入数据 消费者进程负责输出数据 两个相互合作 用信号量机制把每个进程的执行过程表达出来 因为缓冲区是临界资源 一段时间内只能有1个进程使用 所以 对缓冲区的放数据及取数据只能有一个进程来使用缓冲区 存在互斥问题 同时 生产 与消费构成同步关系 相互合作 互相制约 VARmutex 1 empty n full 0 buffter 0 n 1 inout 0 0 生产者进程i Repeat生产数据nextp wait empty wait mutex buffer in nextp in in 1 n signal full untilfalse 消费者进程i Repeatwait full wait mutex Nextc buffer out out out 1 n signal empty untilfalse 二 哲学家就餐问题5个哲学家围做一个圆桌 5支筷子分布与每人的两侧 每人先是思考问题 然后拿起左右两边的筷子就餐 后放筷子继续思考问题 用信号量机制描述每人的活动过程 分析 筷子5支 都属于临界资源 因此互斥使用 哲学家i Repeatwait SM wait chopstick i wait chopstick i 1 5 就餐 signal chopstick i signal chopstick i 1 5 signal sm 继续思考 untilfalse Chopstick 0 4 1 sm 4 5支筷子最多允许4个人同时去抢 才总有一个人拿到2支 才能吃饭 他放下后别人可以继续用 若允许5个人都抢 可能会出现一人1支筷子 出现僵持死锁状态 三 读者 写者问题一个数据文件可以同时允许有多个读者进行访问 但每次只允许1个写者进行修改 读者和写者不能同时出现 分析 把多个读者作为一个整体来考虑 则加上n个写者的话 这n 1个对象对数据块互斥访问 需要1个互斥信号量wmutex 1来控制 另外对于读者整体中 考虑与写者互斥的只是第一个读者来时要考虑的 有了第一个 其他读者就可以跟着进来 同样 释放资源时候也只是最后一个读者 其他读者想走就撤就可以 为了表示到底有多少读者 引入记数变量readcount 而对变量的使用 属于临界资源 一次只允许一个进程使用 所以再引入信号量rwmutex 1 读者进程i REPAETwait rmutex ifreadcout 0wait wmutex Readcount signal rmutex 访问数据文件 wait rmutex Readcount ifreadcout 0wait wmutex signal rmutex untilfalse 写者进程i REPAETwait wmutex 修改文件 signal wmutex untilfalse 例题1 司机与售票员的合作问题VARS1 1 S2 0 司机 Wait s1 启动车辆 正常行车 到站停车Signal s2 售票员 Wait s2 开车门 上下乘客 关车门Signal s1 售票 例题2 假定阅览室能容纳100个人阅读 读者进入和离开阅览室时 都必须在阅览室门口的一个登记表上登记 假定每次只允许一个人登记和撤消登记 设阅览室内有100个座位 用信号量机制描述读者进程的同步算法 读者进程i Vars 100 mutex 1 Wait s Wait mutex 查登记表 并置某座位为占用态Signal mutex 在座位上坐下阅读 Wait mutex 查登记表 并置某座位为空闲状态Signal mutex Signal s 例题 桌子上有一只盘子只能放一只水果 爸爸专门向盘子中放苹果 妈妈专门向盘子中放橘子 一个儿子专等吃盘子中的橘子 一个女儿专等吃盘子中的苹果 用信号量机制实现他们之间的同步机制 Vars 1 s1 s2 0 爸爸 准备苹果 wait s 将苹果放在盘子内 signal s1 妈妈 准备橘子 wait s 将橘子放在盘子内 signal s2 女儿 wait s1 从盘子上拿走苹果 signal s 吃苹果 儿子 wait s2 从盘子上拿走橘子 signal s 吃橘子 2 5管程机制 一 定义 一个管程定义了一个数据结构和能为并发进程所执行 在该数据结构上 的一组操作 这组操作能同步进程和改变管程中的数据 引入管程的目的是避免信号量机制书写中的麻烦 具体例子参考P53 2 6进程通信 一 进程通信的类型1 共享存储器系统 1 基于共享数据结构的通信方式 2 基于共享存储区的通信方式2 消息传递系统 1 直接通信方式 Send receiver message Receive sender message 2 间接通信方式Send mailbox message Receive mailbox message 3 管道通信 所谓管道是用于连接一个读进程和一个写进程以实现他们通信的一个共享文件 又名Pipe文件 本身提供了互斥和同步进程的能力 二 消息缓冲队列通信机制1 消息缓冲队列通信机制中的数据结构Typemessagebuffer recordsender 发送者进程标识符 size 消息长度 text 消息正文 next 指向下一个消息缓冲区的指针end2 PCB中有关通信的数据项Mq 消息队列队首指针 Mutex 消息队列互斥信号量Sm 消息队列资源信号量 3 发送原语Proceduresend receiver a BeginGetbuf a size i i sender a sizer i size a size i text a size i next 0 Getid pcbset receiver j Wait j mutex Insert j mq i Signal j mutex Signal j sm End 4 接收原语Procedurereceive b BeginJ internalname Wait j sm Wait j mutex Remove j mq i Signal j mutex b sender i sizer b size i size b text i size End 2 7线程 一 线程的基本概念1 线程的引入进程的两个属性 资源分配的独立单位 CPU调度的独立单位 进一步提高并发程度和减少系统开销引入线程 2 线程的属性 1 轻型实体 2 独立调度和分派的基本单位 3 可并发执行 4 共享进程资源 第三章处理机调度与死锁 3 1处理机调度的基本概念一 高级 中级和低级调度1 高级调度 作业调度 由作业调度程序按照一定算法选择若干作业进入内存 创建出进程 分配必要的资源 将新进程挂到就绪队列中 1 接纳多少作业 2 接纳哪些作业 2 低级调度 进程调度 决定就绪队列的进程谁获得处理机 然后再由分派程序执行把处理机分配给该进程 非抢占方式 一旦处理机分配给某个进程就要它一直执行下去 直至进程完成或者发生某事件而被阻塞时 才再把处理机分配给其他进程 抢占方式 正在执行的进程 若有新的优先级更高的进程到来后则停止正在执行的进程 新进程抢占CPU 抢占的标准为 1 优先权原则 2 短作业优先原则 3 时间片原则 3 中级调度存储管理中的对换功能 把内存中暂时不运行的进程换出到外存对换区 而把外存中具备运行条件的进程换入内存 称为中级调度 二 调度队列模型1 仅有进程调度的调度队列模型2 具有高级和低级调度的调度队列模型3 同时具有三级调度的调度队列模型 三 选择调度方式和调度算法的若干准则1 面向用户的准则 1 周转时间 从作业被提交给系统开始 到作业完成为止的这段时间间隔 包括四部分时间 作业在外存后备队列上等待调度的时间 进程在就绪队列上等待进程调度的时间 进程在CPU上执行的时间 进程等待I O操作完成的时间 平均周转时间平均带权周转时间 2 响应时间 3 截止时间的保证 4 优先权准则 2 面向系统的准则 1 系统吞吐量高 2 处理机利用率好 3 各类资源的平衡利用 3 2调度算法 一 先来先服务和短作业优先调度算法1 先来先服务调度算法算法思想 1 作业调度 每次调度都从后备作业队列中 选择一个或多个最先进入该队列的作业 将它们调入内存 为它们分配资源 创建进程 然后放入就绪队列 2 进程调度 每次调度是从就绪队列中 选择一个最先进入该队列的进程 为之分配处理机 使之投入运行 通常要考虑 目前系统是否满足进程资源要求 例子参考P76 二 短作业 进程 优先调度算法对短作业或短进程进行优先调度的算法 短作业调度算法是从后备队列中选择一个后若干个估计运行时间最短的作业 将它们内调入内存运行 短进程调度是从就绪队列中选出一估计运行时间最短的进程 分配处理机 注 1 FCFS算法不利于短作业 2 SJF算法不利于长作业 FCFS SJF 三 高优先权优先调度算法1 优先权调度算法的类型 1 非抢占方式 一旦处理机分配给某个进程后 该进程一直执行下去 直至完成 其它进程不得抢占CPU 2 抢占方式 把处理机分配给优先权最高的进程执行 若来新进程优先级更高 则抢占CPU 2 优先权的类型 1 静态优先权 创建进程时确定 整个运行期间保持不变 一般用0 255或0 7中的某个整数来表示 有的系统中数字越大 优先级越高 有的系统相反 2 动态优先权 随着进程的推进或等待时间的增加 优先权而发生改变 非强占方式 ACDB强占方式 A B C D B A 3 高响应比优先调度算法 1 优先权的确定 优先权 等待时间 要求服务时间 要求服务时间 2 高响应比优先调度算法既照顾到了短作业 又考虑了长作业 四 基于时间片的轮转调度算法1 时间片轮转法将所有的就绪进程按先来先服务的原则 排成一个队列 每次调度时 把CPU分配给队首进程 并令其执行一个时间片 2 多级反馈队列调度算法是目前公认的一种较好的调度算法 a 设定多个就绪队列 每个队列设定不同优先级 由高到低 每个队列中进程获得时间片有小到大 b 新进程进入内存 先放第1队列的末尾 按FCFS原则进行运行 单位时间片运行完结束 否则放到第2队列末尾 依次类推 直至全部放到最后一级队列 完全采取时间片轮转原则进行运行c 仅当前面队列全部空闲时 才运行后面队列中的进程 若正在执行第I级队列的某进程 来一个新进程 则将当前执行进程放到该级队列的末尾 专而执行新进程 兼顾了长作业和短作业 采用了FCFS以及时间片轮转和优先级高低综合运用的一种调度算法 3 5产生死锁的原因和必要条件 一 死锁的定义和原因1 定义 所谓死锁是指多个进程在运行过程中因争夺资源而造成的一种僵局 若无外力作用 它们都将无法再向前推进 2 产生死锁的原因 1 竞争资源 可剥夺和非剥夺性资源 临时性资源 2 进程间推进顺序非法 二 产生死锁的必要条件 1 互斥条件 资源本身的特性 2 请求和保持条件 在请求不到新资源的时候进程不释放原来的资源 3 不剥夺条件 进程获得的资源 为使用完前不可被剥夺 4 环路等待条件 进程对资源的请求形成一个请求环形链三 处理死锁的基本方法1 预防死锁2 避免死锁3 检测死锁4 解除死锁 3 6预防死锁的方法 一 预防死锁1 打破请求和保持条件 要求进程一次性申请到全部资源后再运行 不会产生死锁 但效率降低2 打破不剥夺条件 要求进程提出新资源要求不被满足后 必须释放原来的保持的资源 损失代价严重 3 打破环路等待条件 对资源进行线性排序编号 要求每个进程必须从低号到高号申请资源 而不考虑进程实际申请资源的先后顺序 二 系统安全状态1 安全状态 系统能按某种进程顺序 p1 p2 pn 序列 来为某个进程pi分配其所需要资源 直至满足每个进程对资源的最大需求 使每个进程都可顺利地完成 如果系统无法找到这样一个安全序列 则称系统处于不安全状态 进入不安全状态 进而会出现死锁状态 但并非所有不安全状态都进入死锁状态 2 安全状态举例 三 利用银行家算法避免死锁1 数据结构 1 n个进程对m类资源的最大需求情况构成最大需求矩阵Max 2 分配矩阵Allocation表示当前已经分配的资源情况 3 目前还差多少资源就可运行完毕构成需求矩阵Need 4 目前系统的m类资源的可用数量Available 一维数组 Need i j Max i j Allocation i j 2 银行家算法 主要用来判断在当前状态下如果有进程提出资源请求request 看是否能满足该请求 a 判断请求的合法性 是否满足小于NEED矩阵中的向量 b 请求的可满足性判断 是否小于available 向量 c 试探分配 修改相应的参数available allocation need d 进行安全性检查 若分配后安全 则进行分配 若判断从此进入了不安全状态 则恢复原来数据 对进程请求不予满足 3 安全性算法检查 1 设定两个向量work available finish i true 2 从进程集合中找到一个能满足下述条件的进程 finish i false need i j work j 若找到 执行步骤3 否则执行步骤4 3 当进程pi获得资源后 可顺利执行 直到执行 并释放出分配给它的资源work j work j allocation i j finish i true Gotostep2 4 如果所有进程finish i true都满足 则系统处于安全状态 否则处于不安全状态 4 银行家算法举例 1 当前状态是否安全 2 p1请求 1 0 2 是否可以分配 3 p4请求 3 3 0 是否可以分配 4 p0请求 0 2 0 是否可以分配 3 7死锁的检测与解除 一 死锁的检测1 资源分配图 2 死锁定理 当且仅当S状态的资源分配图是不可完全简化的 该充分条件被称为死锁定理 3 死锁检测算法 P100 二 死锁的解除1 剥夺资源2 撤消进程 第四章存储器管理 4 1程序的装入和链接一 程序的执行过程 1 编译 2 链接 3 装入 二 程序的装入1 绝对装入方式 编译时知道程序驻留在内存的什么位置 编译后产生绝对地址的目标代码 将程序装入内存 程序的逻辑地址与实际物理地址完全相同 不需要进行地址变换 绝对装入方式只适用于单道程序环境 2 可重定位装入方式 把装入时对目标程序中指令和数据的修改过程称为重定位 又因为地址变换通常是在装入时一次完成的 以后不再改变 故称为静态重定位 不允许程序运行时在内存中移动位置 3 动态运行时装入方式 采取动态重定位方式进行地址变换 三 程序的链接1 静态链接 程序运行前先链接 再装入内存 1 对相对地址的改变 2 变换外部调用符号2 装入时动态链接 装入内存时 边装入边链接 3 运行时动态链接 某些模块的链接推迟到执行时才执行 用不到的模块可以不调入内存 4 2连续分配方式 为程序分配一个连续的存储空间 一 单一连续分配技术 只能应用与单用户单任务操作系统 如DOS 整个内存空间除了常驻内存的操作系统内核所占的系统区外 其他都是分配给用户程序的用户区 系统区 用户区 二 固定分区分配方式 属于最简单的多道程序的存储管理方式 1 划分分区的方法 1 分区大小相等 2 分区大小不等分区的数量的确定也就决定了在内存中只能安排多少程序同时存放和执行 一个分区里只能放一个作业 不管剩余多少空间 都不能再分配给别的作业了 因此内存利用率不会太高 2 内存分配 将各区建立一个分区使用表 表示分区号 分区的大小 分区的起始地址以及分区的状态 即已分配还是未分配 作为将来分配给作业的一个数据结构 三 动态分区分配1 分区分配的数据结构 主要有空闲分区表或者空闲分配链 把每个空闲分区的序号 大小和其始地址 作为一个表目存放在空闲分区表或链结点内 作为分配的依据 2 分区分配算法 1 首次适应算法 把空闲分区按地址递增的顺序排列 从第一个分区开始搜索到第一个满足作业需求的分区进行分配 剩余的空间作为新的空闲区 将来仍然作为分配对象 缺点 每次都从地址低的部分进行搜索 低址部分会比较琐碎 增加系统开销 2 循环首次适应算法 在首次适应算法基础上下一个作业的搜索从上次找到的空闲分区的下一个空闲分区开始查找 该算法会使空闲分区比较均匀 但缺少大分区 3 最佳适应算法 将空闲分区按大小递增的顺序排列 每次选择最恰当的分区分配给作业 但剩余的空间往往是最小的 有可能因为太小就不能满足任何一个作业的内存需求而造成浪费 我们称之为内存 零头 或者 碎片 4 最坏适应算法 要求空闲分区按地址递减的顺序排列 每次选取最大的空闲分区分配给作业 因为由此剩下的空闲区也是最大的 更容易分配出去 但会缺乏大分区 4 分区分配操作 1 分配内存 参考P110图4 6 2 回收内存 当一个作业执行完毕 释放内存空间时 需要涉及和前后空闲区的合并问题 若回收区前面是一个空闲区的 则只修改前空闲区的大小就可以合并了 若回收区后面是空闲区 则需修改后面空闲区的大小和起始地址进行合并 若回收区前后都是空闲区 则回收就要三者合并 将第一空闲区的大小修改 删除后面一个空闲分区表项 造成总的空闲分区表数量减1 若回收区上下都没有空闲区 则在空闲分区表中添加一个新的表项 五 可重定位分区分配1 动态重定位的引入 1 零头 或 碎片 2 拼接 或 紧凑 2 动态重定位的实现 地址变换过程是在程序执行期间 随着对每条指令或数据的访问自动进行的 故称动态重定位 3 动态重定位的分区分配算法 参考P112图4 10 六 对换 所谓对换是把内存中暂时不运行的进程或者暂时不用的程序和数据 调出到外存上 腾出足够的内存空间 把已具备运行条件的进程或进程所需要的程序和数据 调入到内存 对换是提高内存利用率的有效措施 4 3基本分页存储管理方式 一 页面与页表1 页面 块 将一个进程的逻辑地址分成若干个大小相等的片 称为页面或页 每个页面从0开始编号 同时将内存空间也分成与页面大小相等的物理块 也称为页框或块 2 页面大小 每个页面大小是1KB 2KB或者4KB 都是2的幂 3 页表 为了实现页面与物理块的对应 引入一张页面和它存储的物理块的映射表称为页表 页表中主要有页号和它对应的物理块号两项 4 地址结构 1 根据页面大小 从逻辑地址的低位确定出页内偏移量 剩余二进制位表示页号 从而将逻辑地址分解成两部分 如P114 2 数学计算公式 p int A L d A Lp表示页号 d表示页内偏移量 已知页面大小为1024字节 逻辑地址分别是1011 2148 3000 4000 5012 答案 3059 1124 1976 7072 逻辑地址非法 二 地址变换机构1 基本地址变换机构 在进程没有执行前 页表在内存的起始地址和页表的长度存储在进程的PCB内 当进程获得执行后 页表起始地址和页表长度放到了页表寄存器内 2 基本地址变换过程 首先将逻辑地址转换为p和d两部分 根据页表寄存器内页的长度判断该页号是否属于越界访问 若没有越界 根据页表在内存的起始地址找到页表 查找到该页对应的索引项 得出该页号对应的实际物理块 同时 页内偏移量同时也是物理块的偏移量 因此 物理块号 块的大小 1KB或4KB 偏移量 实际物理地址 或者物理块号的二进制编码加上偏移量的二进制代码表示组成实际物理地址 3 具有快表的地址变换机构 1 快表 联想寄存器 在地址变换机构中增设的具有并行查寻能力的特殊的高速缓冲寄存器 用以存放当前访问的那些页表项 2 地址变换过程 给出逻辑地址后 先到快表中查找索引项 若有 直接地址变换就可以形成物理地址而不用访问主存了 若快表中没有 再到内存去查找页表 从中找到物理块号进行地址变换 但同时要把该索引项重新写到联想寄存器内 若已满 则换出认为不再需要的索引项 这样 根据程序执行的局部原理 90 的检索页表索引项的过程可以在联想寄存器内实现 从而提高检索效率 4 4基本分段存储管理方式 一 分段存储管理方式的引入1 方便编程2 信息共享3 信息保护4 动态增长5 动态链接 二 分段系统的基本原理1 分段 将作业的逻辑地址空间分为若干个段 每个段内定义一组逻辑信息 作业的地址空间分为段号 名 段内地址两部分 2 段表 将不同的段分配到内存不连续的存储空间 当然 具体每个段 因为长度可能不同 但是需连续的存储空间 因此 段表内需确定段号 段的长度 段在内存的起始地址 3 地址变换机构给定逻辑地址 段号S和段内地址d 先拿段号和段表寄存器内的段的长度进行比较 看是否越界 然后拿段表寄存器的起始地址到段表中检索到该段段表项 根据段的长度与逻辑地址的段内地址进行比较 再次判断是否越界 若没有越界 根据段的内存的基地址加上段内地址d形成实际物理地址 也需要两次访问内存 也可以引入联想寄存器 逻辑地址 0 430 1 10 2 500 3 400 4 112 5 32 答案 6401360非法1750非法 4 分页与分段区别 1 页是信息的物理单位 为了提高内存利用率引入的 段是信息的逻辑单位 是考虑用户编程需要分成的段 2 页的大小固定 段的大小不确定 3 页的逻辑地址是1维的 段的逻辑地址是2维的 二 信息共享参考P122分段存储管理方式与分页存储管理方式比较更方便于实施信息共享 二 段页式存储管理方式1 基本原理 首先用户程序分成若干个段 每个段内再实施分页 为每个段赋予一个段名 在段页式系统中 其地址结构由段号 段内页号及页内地址三部分组成 2 地址变换过程 详细见P124图4 22 4 5虚拟存储器的基本概念 一 虚拟存储器的引入1 常规存储器的特征 1 一次性 2 驻留性2 程序执行的局部性原理 1 时间的局限性 2 空间的局限性 3 虚拟存储器的定义所谓虚拟存储器是指具有请求调入功能和置换功能 能从逻辑上对内存容量加以扩充的一种存储器系统 其逻辑容量由内存容量和外存容量之和所决定的 二 虚拟存储器的实现方法1 分页请求系统2 请求分段系统 三 虚拟存储器的特征1 多次性2 对换性3 虚拟性 4 6请求分页存储管理方式 一 请求分页中的硬件支持1 页表机制在原来页号和物理块号的基础上增加辅助项 状态位 0表示在外存 没有调入 1表示在内存 访问字段 一段时间内访问次数或是否被访问过 供页面置换出去时参考 修改位 一段时间内是否被修改过 置换时需要回写到外存对换区 外存地址 将来调入内存时使用 2 缺页中断机构 3 地址变换机构参考P130图4 24 二 内存分配策略和分配算法1 最小物理块的确定保证进程正常运行所需要的最小物理块数 2 物理块的分配策略 1 固定分配局部置换 2 可变分配全局置换 3 可变分配局部置换 3 物理块分配算法 1 平均分配算法 2 按比例分配算法 3 考虑优先权的分配算法三 调页策略1 何时调入页面2 从何处调入页面3 页面调入过程 4 7页面置换算法 一 最佳置换算法 OPT 和先进先出置换算法1 OPT算法 选择被淘汰的页面是以后永不使用或者最长时间内不被执行的页面 因为将来的事情不可预知 所以不可实现 2 先进先出置换算法 FIFO 完全考虑进入内存的先后时间 页面引用串 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 二 最近最久未使用 LRU 算法 1 LRU算法 选择淘汰页面选择最近最久未使用的页面予以淘汰 2 LRU置换算法的硬件支持 1 移位寄存器法 2 栈 三 Clock置换算法1 简单的Clock置换算法 只考虑访问位的情况作为置换页面的依据 2 改进型Clock置换算法 除考虑访问位之外 增加考虑修改位的情况 四 其它页面置换算法1 最少使用置换算法2 页面缓冲算法 4 8请求分段存储管理方式 一 请求分段中的硬件支持1 段表机制在段号 段长 段的基地址的基础上 增加存取方式 访问字段 修改位 存在位 增补位以及外存地址 存取方式主要是只读 可写 可读写等对段实施保护 访问字段确定被访问的次数 存在位表示是否在内存 修改位同样是供置换参考 增补位表示该段是否动态增长过 外存地址同样是在外存的盘块号 2 缺段中断机构3 地址变换机构二 分段的共享与保护1 共享段表2 共享段的分配与回收3 分段保护 第五章设备管理 5 1I O系统一 I O设备1 按传输速率分类 1 低速设备 每秒几个字节至数百字节 键盘 鼠标 语音的输入 输出设备 2 中速设备 每秒数千字节至数万字节的设备 如行式 激光打印机 3 高速设备 数百千字节至数十兆字节 磁带机 磁盘机 光盘机 2 按信息交换单位分类 1 块设备 存储信息以数据块为基本单位 典型设备为磁盘 传输速度快 可寻址 I O控制方式为DMA方式 2 字符设备 打印机等 传输速度低 以字符为传送单位 不可寻址 采用中断驱动方式 3 按设备的共享属性分类 1 独占设备 2 共享设备 3 虚拟设备 二 设备控制器设备控制器是在CPU和I O设备之间的接口 一个设备控制器控制几个设备 1 设备控制器的组成 1 设备控制器与处理机的接口 2 设备控制器与设备的接口 3 I O逻辑 2 设备控制器的功能 1 接收和识别命令 2 数据交换 3 标识和报告设备的状态 4 地址识别 5 数据缓冲 6 差错控制 三 通道1 通道是特殊的处理机 是专门通过执行内存中的通道程序来控制I O操作的可与CPU同时工作的处理机 指令单一 只去实现控制I O过程的 2 I O系统 1 主机系统 整个主机中的I O系统包括了三级控制 四级连接 即内存 通道 设备控制器及设备 2 微机系统 没有通道 因此采取CPU与内存通过总线结构与设备控制器连接 3 瓶颈 问题 1 一个通道连接多个设备控制器 一个控制器连接多个设备 这样在实际通路中因为设备控制器和通道数量的递减从而在构造数据通路的时候出现一种 瓶颈 现象 越向内存数量越少 2 解决瓶颈问题的有效方法是增加通路而不增加通道 因为通道价格昂贵 可以将一个设备连接多个控制器 一个控制器连接多个通道 从而尽可能的增加通路 5 2I O控制方式 一 程序I O方式处理机向控制器发出I O指令启动设备输入数据时 把busy信号设定为1 以后不断循环检测该信号 当设备控制器输入数据完成 修改信号为0 由CPU将该数据送入内存 二 中断驱动I O控制方式CPU发送指令给设备控制器后 转而做别的工作去 每接受一个字符到设备控制器的数据寄存器后 就发中断给CPU 要CPU放数据入内存 例如打印机等字符设备采取该中断驱动方式 三 直接存储器访问DMAI O控制方式1 DMA控制方式的引入 块设备的专门的控制器就是DMA控制器 通过控制器接收设备来的数据直接送数据进入内存的存储单元中 不用CPU干涉 只是到连续盘块的数据全部输入或输出完成后才发中断给CPU 1 数据传输基本单位是数据块 2 所传送的数据是从设备直接送入内存或者相反 3 仅在传输一个或多个数据块的开始或结束时 才需要CPU干预 2 DMA控制器的组成 主机与DMA控制器的接口 DMA控制器与块设备的接口 I O控制逻辑四类寄存器 1 命令 状态寄存器CR 2 内存地址寄存器MAR 3 数据寄存器DR 4 数据计数器DC 3 DMA控制器的工作方式 四 I O通道控制方式1 I O通道控制方式的引入进一步减少CPU的干预 将对一个数据块的读写为单位的干预 减少为对一组数据块的读写及有关的控制和管理为单位的干预 2 通道程序 通道是通过执行通道程序 并与设备控制器共同实现对I O设备的控制的 通道程序是由一系列通道指令所构成的 每条指令 1 操作码 2 内存地址 3 计数 4 通道程序结束位 5 记录结束标志 5 3缓冲管理 一 缓冲的引入1 缓和CPU与I O设备间速度不匹配的矛盾2 减少对CPU的中断频率3 提高CPU和I O设备间的并行性二 单缓冲和双缓冲 循环缓冲及缓冲池 5 4设备分配 一 设备分配中的数据结构1 设备控制表DCT2 控制器控制表COCT 通道控制表CHCT3 系统设备表 二 设备分配时应考虑的因素1 设备的固有属性 独享设备 共享设备 虚拟设备2 设备分配算法 1 先来先服务 2 优先级高者优先3 设备分配中的安全性 1 安全分配方式 2 不安全分配方式 4 设备独立性为了提高操作系统的可适应性和可扩展性 应用程序独立于具体使用的物理设备 在应用程序中 使用逻辑设备名称来请求使用某类设备 在系统实际执行时再转换为具体物理设备 特点 1 设备分配时的灵活性 2 考虑多通路情况 三 spooling技术1 定义 SPOOLING技术是在系统中引入多道程序设计技术后 用其中的一道程序模拟脱机输入时的卫星机的功能把低速I O设备数据传送到高速磁盘上 用另一道程序模拟脱机输出时卫星机的功能把高速磁盘上的数据传送出I O设备上 这样在主机直接控制下 实现了脱机输入 输出的功能 因此 我们把这种在联机情况下实现的同时外围操作称为SPOOLING技术或假脱机操作 2 spooling系统组成 1 输入井和输出井 2 输入缓冲区和输出缓冲区 3 输入进程spi和输出进程spo3 共享打印机 4 SPOOLING系统的特点 1 提高了I O的速度 2 将独占设备改造为共享设备 3 实现了虚拟设备功能 5 5设备处理 设备处理程序通常又称为设备驱动程序 是I O进程与设备控制器之间的通信程序 以进程的形式存在 故称为设备驱动进程 一 设备驱动程序的功能1 接收由I O进程发来的命令和参数 转换为具体要求2 检查用户I O请求的合法性3 发出I O命令4 及时响应由控制器或通道发来的中断请求 并根据其中断类型调用相应的中断处理程序进行处理5 对于有通道的计算机系统 驱动程序根据用户I O请求 自动的构成通道程序