计算机操作系统入门第二章.ppt

第3课进程管理本次课学习如下知识 进程的概念 程序的并发执行 进程及其特征 进程的状态 进程控制块FCB 进程调度 进程控制 进程协作 进程间的通信 线程 第2章进程管理处理机是计算机系统中最重要的资源之一 操作系统对处理机的管理是最重要的功能之一 操作系统负责如下活动和进程管理 创建 删除用户进程和系统进程 进程调度 进程同步 进程通信 以及进程死锁的处理 本章将讨论如下几个方面的知识 1 进程的概念 进程的状态 进程的调度 进程操作与协作 进程的通讯 进程的特征 2 进程的同步 同步的概念 同步的实现 3 处理机调度 调度标准 调度算法 多处理机调度 实时调度 算法评估 4 死锁 死锁的定义 死锁的特点 死锁的处理 死锁的预防 死锁避免 死锁检测 死锁的恢复 2 1进程的概念2 1 1程序的并发执行1 程序的顺序执行的特点 顺序性 封闭性 可再现性 2 程序的并行执行 并发程序比起顺序程序具有高得多的复杂性 程序与计算不再一一对应 计算之间存在复杂的相互制约关系 2 1 3进程的状态进程包含以下几个状态 运行状态 就绪状态 阻塞状态 进程的三种关系是可以转换的 它们之间的转换关系如下图所示 进程状态的转换 2 1 4进程控制块PCB 进程控制块是用于对当前系统中的进程进行控制和管理 进程控制块描述和记录了进程在整个生命周期内动态变化的数据结构特征 PCB是进程存在的惟一标志 1 进程控制块中的信息 进程标识 进程状态 程序计数器 CPU调度信息 CPU寄存器 内存管理信息 输入 输出状态信息 2 PCB的组织方式 链接方式 索引方式 2 1 5进程调度1 调度队列 进程的作业队列 进程的就绪队列 由一个链表组成 链表的头包含着指向第一个进程PCB的指针和指向最后一个进程PCB的指针 进程的等待队列 2 进程调度程序 进程调度 作业调度程序3 进程切换系统要储存老进程的状态信息 同时还要装入新进程的状态信息 2 1 6进程控制操作系统的进程创建和撤消机制 1 进程创建 子进程 父进程 导致一个进程去创建另一个进程的典型事件 用户登录 作业调度 提供服务 2 进程撤消 进程的删除 进程的终止 引起进程终止的事件 正常结束 异常结束 外界干预 2 1 7进程协作 独立进程与是协作进程 允许进程协作的原因 信息共享 加快运算速度 模块化 方便 2 1 8进程间的通信 协作进程通过共享内存实现它们之间的通信 操作系统提供的进程通信设施IPC实现进程之间的通信 IPC的最佳方案是消息传递系统 1 消息传递系统 直接通信 模式1 对称地址形式 在直接通信方式中每一个要通信的进程必须显示接收信息进程名和发送信息进程名 其定义形式为 Send P Message 给进程P发送信息 Receive Q Message 从进程Q接收信息 模式2 非对称地址形式 由发送进程指定通信进程名 而接收进程则不要求 其格式为 Send P Message 给进程P发送信息 Receive ID Message 从任何进程接收信息 其中 变量ID将会被进程名所代替 间接通信对于间接通信 发送和接收的消息都是放在信箱中 每个信箱都有惟一的标识 其Send和Receive可定义如下 Send A Message 将信息发送至A信箱 Receive A Message 从A信箱接收信息 这种模式下 其通信链有如下特点 仅仅当一对进程具有共享信箱时 他们之间可建立连接 一个连接也可能与两个以上的进程有关 每一对通信进程之间 可能有许多不同的连接 而每一个连接对应一个信箱 如果信箱属于一个进程 也就是信箱是进程的地址空间的一部分 则当这个进程终止时 它的信箱也就随之消失 如果一个信箱属于操作系统 则它是独立的而不属于任何进程 因此操作系统提供了一种机制而允许进程作如下操作 创建新信箱 通过信箱发送和接收信息 删除信箱 2 缓冲区无论通信是直接还是间接 进程间的信息交换都驻留在缓冲区中的临时队列中 这种队列有三种实现方法 零容量 有界容量 无界容量 2 1 9线程为了减少系统的开销 提高程序的并发执行效率 而产生了线程的概念 1 线程简介 轻量级进程 是被系统独立调度和CPU的基本运行单位 多线程 2 多线程的优点多线程编程的优点可有以下四点 响应 资源共享 经济 多处理器结构的应用 3 用户线程和内核线程 线程的实现方式 用户线程 内核线程 用户线程 内核线程 小结进程的概念是操作系统最重要的概念 处理机的管理主要是进程的管理 学习本章时 首先要理解进程的概念 处理机调度的概念 死锁的概念 重点知识是 一是与进程管理有关的的知识 包括进程状态 进程调度 进程协作 进程通讯 进程同步 二是与处理机有关的知识 包括处理机调度的标准 算法 多处理机调度 算法评估 本讲应掌握的知识 进程及其特征 进程的状态 进程控制块PCB 进程调度 进程控制难点知识 进程的概念 进程协作 进程间的通信 进程同步的实现和处理机调度算法的评估 第4课进程的同步本次课学习如下知识 同步的概念 临界资源 临界区问题 同步的实现 2 2进程的同步进程的引入虽然改善了系统的资源利用率和提高了系统的吞吐量 但是进程的异步性 特别是它们在争用临界资源时 会给系统造成一定的混乱 为了解决这个问题 提出了进程同步的概念 2 2 1同步的概念系统中存在着许多进程 它们之间可以有两种关系 1 资源共享 进程是独立运行的基本单位 各个进程彼此之间没有联系 但它们同处于一个系统中 共享系统资源 进程在访问这些资源时 可能会被系统中运行的其它进程所影响 2 相互协作 协作进程可能直接共享逻辑地址空间 比如代码和数据 或通过文件共享数据 并发访问共享数据 可能会导致数据的不一致性 3 进程同步的任务 保证各进程能互斥地访问这些资源 有效地共享资源 保证协作进程或线程的顺序执行 使它们不会出现与时间有关的差错 对数据的一致性进行维护 有效地相互合作 2 2 2临界资源 临界资源的概念 在一段时间内只允许一个进程访问的资源 对临界资源的访问必须采用互斥的方式进行 以实现对资源的共享 生产者 消费者问题 一个经典同步问题来说明进程同步的必要性 这个问题的主要描述如下 有一个生产者进程在生产消息 并提供给消费者进程进行消费 所生产的消息存放在一个有几个缓冲区的缓冲池中 生产者进程可将它所生产的消息放入一个缓冲区中 消费者进程则从一个缓冲区中取走一个消息 它们之间必须保持同步 即不允许消费者进程到一个空缓冲区中去取消息 也不允许生产者进程向一个已装满消息而尚未取走的缓冲区中投放消息 其代码如下 生产者代码 While Count Buffer SIZE Count 增加一项至缓冲区Buffer in item in in Buffer SIZE 消费者代码 While count 0 Count 从缓冲区减去一项item Buffer out out out 1 Buffer SIZE 其中指针in来指示下一个可存放消息的缓冲区 每存放一个消息 in 1 指针out来指示下一个可获得消息的缓冲区 每当取走一个消息后 输出指针out 1 由于缓冲池是循环缓冲 因此输入指针in in Buffer SRE 输出指针out out Buffer SRE 尽管两段代码是正确的 但当他们并行运行时 其结果也许不正确 原因是两段进程共享变量Count Count是缓冲区中项目的计数 Count和 Count用机器语言实现为如下操作 r1 Count r1 r1 1 Count r1 r2 Count r2 r2 1Count r2 假设Count为5 如果两段进程是按顺序执行 则不会产生错误 即可得到结果 Count 5 然而如果我们按如下顺序执行 则我们会得到错误的结果 即 Count 4 T0 生产者进程执行 r1 Count T1 生产者进程执行 r1 r1 1 T2 消费者进程执行 r2 Count T3 消费者进程执行 r2 r2 1 T4 生产者进程执行 Count r1 T5 消费者进程执行 Count r2 而如果我们交换T4和T5的顺序 我们又会得到count 6的错误结果 2 2 3临界区问题 临界区的概念 将多个进程访问临界资源的那一段程序代码称为临界区 在临界区中 进程能改变变量的值 更新数据表或写文件等 系统只允许一个进程在临界区执行 而不允许其它进程进入临界区 解决临界区问题必须遵循的原则 1 当某一时刻没有进程处于临界区内时 相应的临界资源处于空闲状态 因而可允许一个请求进入临界区进程立即进入临界区 以有效地利用临界资源 2 如果此时已有进程进入临界区 则其它试图进入临界区的进程必须等待 以保证各进程互斥地访问临界资源 3 当某个进程申请进入临界区时 它应在有限时间内获得系统的响应 而能够进入临界区 以免进程陷入无限等待状态 4 当进程不能进入临界区时 应立即释放处理机 以免进程陷入忙等待状态 2 2 4同步的实现解决临界区问题可以用软件或硬件实现 使用硬件实现进程的同步 可以使用户的编程任务更容易且系统的效率更高 1 关中断 使用关中断解决单处理器环境下临界区的问题 使用关中断不能解决多处理器环境下临界区的问题 关闭中断将延误处理器的处理时间 使系统性能下降 2 锁变量的测试与设置 锁变量Lock 测试锁变量Lock 设置锁变量 测试与设置 指令 3 信号量 信号量 PV操作 P操作P S S if S 0 继续执行 else阻塞并进入等待队列 V操作V S S S 1 if S 0 继续运行 else唤醒等待队列中的一个进程 并继续运行 PV操作实现进程的互斥 小结本次课应掌握的知识 进程之间和资源共享和进程相互协作的概念 进程同步的必要性 临界资源的概念以及对临界资源访问的解决方案 临界区的概念和解决临界区问题必须遵循的原则 锁变量的设置与测试 难点知识 如何实现进程的同步 关闭中断的概念及其优缺点 P操作和V操作的实现和如何使用PV操作实现进程的互斥 第5课处理机调度本次课学习如下知识 基本概念 调度标准 调度算法 多处理器调度 实时调度 算法评估 2 3处理机调度2 3 1基本概念调度是操作系统的基本功能 几乎所有的系统资源都是通过调度而被使用 1 调度程序 操作系统做出选择进程的决定是由调度程序来实现的 调度程序面临的问题 2 调度类型从作业进入系统到作业运行完毕 它要经历以下调度过程 高级调度作业调度 长程调度 接纳调度 每次执行作业调度时 都需要做出以下两个决定 接纳多少个作业 接纳哪些作业 低级调度进程调度是最基本的一种调度 依据下面四种情况决定是否进行CPU重新调度 当进程从运行态转到等待态 当进程从运行态转到就绪态 当进程从等待状态转到就绪状态 当进程终止时 进程调度的非抢占方式 进程调度的抢占方式 进程调度抢占的原则 时间片原则 优先权原则 短作业优先原则 中级调度 2 3 2调度标准1 CPU利用 2 吞吐量 3 周转时间 4 等待时间 5 响应时间 2 3 3调度算法1 先来先服务调度 按进程进入等待队列的先后顺序进行分配CPU CPU总是选择就绪队列中的第一个进程 将处理机分配给它 FCFS算法比较有利于长作业 而不利于短作业 假设有进程P1 P2和P3 他们到达的时间顺序和CPU脉冲时间长短如下所示 进程与脉冲时间表进程脉冲时间 毫秒 P23P33各进程按FCFS算法的执行顺序如下图所示 P124 0242730FCFS算法中进程的运行顺序进程P1的等待时间是零 进程P2需等待24 P3是27 则它们的平均等待时间是 0 27 27 3 3 FCFS调度是非抢占式 2 最短作业优先 从就绪队列中选出一个估计在下一个CPU脉冲时间最短的进程 将处理机分配给它 使它立即执行并一直执行到完成 或发生某事件而被阻塞后放弃处理机时 系统再重新调度 如果两个进程运行时间相同 则采用FCFS算法选一个较早到达的进程 该算法也存在着不容忽视的缺点 长作业得不到及时调度 不能保证紧急性的作业会得到及时处理 算法较难实现 3 优先权调度 系统按某种原则将进程指定一个优先权来表示进程所享有的调度优先权 优先权调度算法的类型优先权调度算法有抢占式和非抢占式两种 抢占式优先权调度算法 非抢占式优先权调度算法 优先权的类型 静态优先权 动态优先权 优先权调度算法的主要问题 4 时间片轮转法调度 时间片轮转调度算法的含义 决定时间片轮转算法的性能的因素 系统对响应时间的要求 就绪队列中进程的数目 系统的处理能力 5 多级队列调度 多级队列调度算法的含义 多级队列调度算法的实现 6 多级反馈队列调度 多级反馈队列调度的含义 多级反馈调度的实现 2 3 4多处理器调度 多处理器情况下要解决的问题 对称式多处理调度 2 3 5实时调度 硬实时系统的概念 软实时系统的概念 2 3 6算法评估 选择算法的标准 在最大响应时间为1秒的限制下 CPU最大利用率 在平均周转时间为线性总执行时间的条件下 CPU的最大吞吐量是多少 分解评估法对以下五个进程到达的时间为0 其顺序及CPU脉冲时间如下表所示 五个进程的脉冲时间表 FCFS算法进程的执行顺序如下图所示 01039424961FCFS算法中进程的运行顺序各进程的等待时间为 P1 0 毫秒 P2 10 毫秒 P3 39 毫秒 P4 42 毫秒 P5 49 毫秒 平均等待时间是 0 10 39 42 49 5 28 毫秒 SJF算法各进程的执行顺序如下图所示 0310203261SJF算法中进程的运行顺序各进程的等待时间为 P1 10 毫秒 P2 32 毫秒 P3 0 毫秒 P4 3 毫秒 P5 20 毫秒 平均等待时间是 10 32 0 3 20 5 13 毫秒 RR算法各进程执行顺序如下图所示 假设RR时间片 10毫秒 01020233040505261RR算法中进程的运行顺序各进程的等待时间为 P1 0 毫秒 P2 32 毫秒 P3 20 毫秒 P4 23 毫秒 P5 40 毫秒 平均等待时间是 0 32 20 23 40 5 23毫秒 队列模型 模拟模拟的概念 实现 小结本次课应掌握如下知识 操作系统调度程序的功能 高级调度和低级调度的作用及其实现过程 恒量调度优劣的五个标准 调度算法 时间片轮转法调度 优先权调度 最短作业优先 先来先服务调度 多级反馈队列调度 多级队列调度 多处理器调度 实时调度了解以下知识 多处理器调度 实时调度难点知识 算法评估 分解评估法的几种算法的含义及其进程的执行顺序 第6课死锁本次课学习如下知识 死锁的定义 产生死锁的原因 死锁的特点 死锁的处理方法 死锁的预防 死锁的避免 死锁的检测 死锁的恢复 2 4死锁2 4 1死锁的定义 死锁的概念 几个并发进程为竞争系统资源而进入了等待状态 且它们永远不会改变这种状态 系统资源的分配过程 为什么会出现死锁 2 4 2产生死锁的原因 产生死锁的原因 可剥夺资源 不可剥夺资源 2 4 3死锁的特点 死锁产生的后果 发生死锁的必要条件 互斥条件 占有和等待 非抢占 循环等待 资源分配图 用有向图来表示资源分配与死锁的关系 称之为系统资源分配图 如下图所示 资源分配图图中 P P1 P2 P3 Pn 表示进程的圆形结点集 R R1 R2 Rn 表示资源的方形结点集 有向边P1 R1表示进程P1正在申请资源R1 有向边R1 P1表示资源R1已分配给进程P1 从资源分配图中我们可以看出 如果图中没有环路 则表明系统中没有死锁发生 如果图中包括一个环路 则说明系统中有可能存在死锁现象 将上图加以修改 就产生了两个环路 如下图所示 P1 R1 P2 R2 P3 R3 P1 P2 R2 P3 R3 P2有死锁的资源分配图 从图中的两个环路可以看出 进程P1 P2和P3处于死锁状态 P2等待资源R2 而R2已分配给进程P3 P3正等待P1和P2释放资源R3 进程P1正等待进程P2释放R1 现在我们看下图 虽然图中有环路P1 R1 P3 R2 P1 但却不会发生死锁 因为 P2释放R1后 系统可重新分配给P1 同样P4释放R2后 再分配给P3就打破了环路 无死锁环路的资源分配图 2 4 4死锁的处理方法解决死锁问题的方法有 1 预防 使用一种协议来保证系统永远不会进入死锁状态 2 避免 采用动态分配资源 以避免死锁的发生 3 恢复 允许系统进入死锁状态 然后再恢复 4 忽略 假设系统不会发生死锁 2 4 5死锁的预防使产生死锁的四个