网站建设 推广400电话,看盘神器app,wordpress 自动链接,一天能免费看3次的app本篇博客是考研期间学习王道课程 传送门 的笔记#xff0c;以及一整年里对 操作系统 知识点的理解的总结。希望对新一届的计算机考研人提供帮助#xff01;#xff01;#xff01; 关于对 “进程与线程” 章节知识点总结的十分全面#xff0c;涵括了《操作系统》课程里的全… 本篇博客是考研期间学习王道课程 传送门 的笔记以及一整年里对 操作系统 知识点的理解的总结。希望对新一届的计算机考研人提供帮助 关于对 “进程与线程” 章节知识点总结的十分全面涵括了《操作系统》课程里的全部要点本人来来回回过了三遍视频其中还陆陆续续补充了许多内容所以读者可以相信本篇博客对于考研操作系统 “进程与线程” 章节知识点的正确性与全面性但如果还有自主命题的学校还需额外读者自行再观看对应学校的自主命题材料。 食用说明书 第一遍学习王道课程时我的笔记只有标题和截图后来复习发现看只看图片并不能很快的了解截图中要重点表达的知识点。 在第二遍复习中我给每一张截图中 标记了重点以及 每张图片上方总结了该图片 对应的知识点 以及自己的 思考 。 最后第三遍查漏补缺。 所以 我把目录放在博客的前面就是希望读者可以结合目录结构去更好的学习知识点之后冲刺复习阶段脑海里可以浮现出该知识结构做到对每一个知识点熟稔于心 请读者放心目录展示的知识点结构是十分合理的可以放心使用该结构去记忆学习 注意(⊙o⊙)每张图片上面的文字都是该图对应的知识点总结方便读者更快理解图片内容。 《操作系统》第2章 进程与线程 【考纲内容】 王道 P48 ~ 176 (一) 进程与线程 网课耗时2 h 进程与线程的基本概念进程 / 线程的状态与转换线程的实现内核支持的线程线程库支持的线程进程与线程的组织与控制进程间通信共享内存信息传递管道 (二) CPU调度与上下文切换 网课耗时2 h 调度的基本概念调度的目标调度的实现调度器 / 调度程序调度的时机与调度方式抢占式 / 非抢占式闲逛进程内核级线程与用户及线程调度典型调度算法先来先服务调度算法短作业短进程、短线程优先调度算法时间片轮转调度算法优先级调度算法高响应比优先调度算法多级队列调度算法多级反馈队列调度算法上下文及其切换机制 (三) 同步与互斥 网课耗时3.5 h 同步与互斥的基本概念基本的实现方式软件方法、硬件方法锁信号量条件变量经典同步问题生产者-消费者问题读者-写者问题哲学家进餐问题 (四) 死锁 网课耗时1 h 死锁的基本概念死锁预防死锁避免死锁检测和解除 重点
知识点选择题综合题进程的概念✔进程调度✔✔信号量机制实现同步和互斥✔✔进程死锁✔✔
2.1 进程与线程
2.1.1 进程的描述 1. 进程的概念 ① 进程是什么 答进程是 进程实体 的运行过程是系统进行 资源分配和调度 的一个独立单位 其中进程实体进程映像包括PCB 程序段 数据段 三部分 2. 进程的组成 进程的组成部分PCB - 进程控制块、程序段、数据段 创建进程 的本质是 创建进程实体的 PCB 撤消进程 的实质是 撤消进程实体的 PCB 【问题】程序是如何运行的 程序编译流程如下 编译把 源程序高级语言 翻译成 目标程序机器语言连接将目标文件 连接成 可执行文件装入 - 执行 很重要的一句话进程实体 反应了 进程在 动态执行 的 某一时刻状态 (进程实体静态进程动态) 进程的三大组成部分PCB 程序段 数据段 进程的定义进程 是进程实体的 运行过程是系统进程 资源分配 和 调度 的一个独立单位 进程调度就是指 让哪个进程在CPU上运行 3. 进程的特征 小结 本节的知识点就三部分进程的 概念、组成、特征 2.1.2 进程的状态与转换 1. 进程的状态 ① 创建态 ② 就绪态 创建状态的步骤 申请空白PCB向空白PCB中填写相关信息为该进程分配 除CPU以外 必要的资源 已就绪的进程会在 就绪队列 按照 优先级策略 排队等待CPU ③ 运行 (Running) 态 进程在CPU上运行 ④ 阻塞态 阻塞Block状态 等待状态 封锁状态 进程因某一事件暂停运行即使CPU空闲也不能执行。阻塞的进程会在 阻塞队列 里排队等待 注意就绪态仅缺CPU而阻塞态缺其它资源 (除了CPU) 或等待某一事件 ⑤ 终止态 2. 进程状态的转换 P42里引入了 挂起、激活原语 之后的进程状态转换课程 2.2.1 调度的概念 里简单提了提保险起见去课本里看看 注意一个进程运行 - 阻塞 是主动的行为阻塞 - 就绪 是被动的行为需要协助 三个基础状态CPU 资源其它资源就绪态×✔运行态✔✔阻塞态××小结 2.1.3 进程的组织方式 为了方便进程的调度和管理需要将 各进程的PCB用适当的方法组织起来常见的组织方式 线性方式链接方式索引方式 1. 进程的组织方式 - 链接方式 链接方式将同一状态的PCB链接成一个队列 2. 进程的组织方式 - 索引方式 索引方式将同一状态的进程组织在一个索引表中索引表的表项指向相应的PCB 小结 2.1.4 进程控制 1. 进程控制的基本概念 ① 什么是进程控制 进程控制的主要功能是对系统中的所有进程实施有效的管理包含功能 进程的创建进程的终止进程的阻塞进程的唤醒进程状态的切换 ② 如何实现进程控制 使用 原语 实现进程控制原语操作具有原子性不可中断 通俗理解把原语理解成一段封装好的功能函数只不过具有原子性 思考为什么进程控制的过程要 “一气呵成” 下图中举例说明 【问题】如何实现原语的 “原子性” 答使用 关中断指令 和 开中断指令 这两个 特权指令 实现 原子性 2. 进程相关的原语 各类原语的操作步骤不需要死记硬背只需要理解即可不会让你默写 ① 进程的创建 这里第一次遇到 作业调度 这个名词解释一下。作业 就是放在外存还没有被运行的程序。 ② 进程的终止 ③ 进程的阻塞和唤醒 保护进程运行现场 重点内容后面在填坑 ④ 进程的切换 恢复进程运行环境信息 重点内容后面在填坑 接下来举例介绍 运行环境信息 学习完 进程控制相关的原语再来看看之前的问题程序是如何运行的 CPU里设置了很多 寄存器存储各类程序运行时需要的数据 很多的中间计算结果是暂时放在各类寄存器中 例如执行指令3时x2但此时它还没有被写回内存执行完指令4内存中的x才变成2 如果执行完指令3另一个进程上CPU他将通用寄存器里的数据改为250切换回原来的进程不就数据错误了 解决办法在进程切换时先在PCB中保持这个进程的 运行环境进程重新运行时通过PCB恢复当时的运行环境 小结 2.1.5 进程的通信 【问题】什么是进程间通信 答进程通信是指进程之间的信息交换 【问题】为什么进程通信需要操作系统支持 答为了进程安全 1. 共享存储 在共享存储器系统中相互通信的进程 共享某些数据结构 或 共享存储区进程之间能够通过这些空间进行通信 共享存储的两种类型 低级共享基于 数据结构 的共享速度慢、灵活性差高级共享基于 存储区 的共享速度快、灵活性好 2. 消息传递 在 信息传递机制 中进程不必借助任何共享存储区或数据结构而是以 格式化的信息 为单位将通信的数据封装在信息中并利用操作系统提供的一组 通信命令原语在进程间进行信息传递完成进程间的数据交换 说白了就是通过 写信 进行交流 ① 直接通信方式 进程P按要求准备好要发送的信息通过发送原语将信息放进进程Q的消息队列里进程Q从消息队列里读取信息 ② 间接通信方式 间接通信方式进程P只是指明要发信息给信箱A没有指明发给哪一个进程 3. 管道通信 共享存储方式对共享区的读写很自由 管道通信方式读写数据有限制和 循环队列 一样 小结 2.1.6 线程和多线程模型 1. 什么是线程为什么要引入线程 引入进程的目的使得多道程序并行执行以提高资源利用率 引入线程的目的减少程序在并发执行时所付出的时间开销提高OS的并发性能 2. 引入线程机制后有什么变化 课本P83还补充了从 拥有资源、独立性、支持多处理机系统 的角度比较进程与线程的区别王道不提应该不考 3. 线程的属性 4. 线程的实现方式 ① 用户级线程 在上面qq的例子中操作系统只能看见进程程序员利用线程库创建逻辑上的线程就是所谓的 用户级线程 ② 内核级线程 内核级线程操作系统支持的线程无论是系统进程还是用户进程都是在 操作系统内核 的支持下运行 5. 多线程模型 学习了 用户级线程 和 内核级线程各自都有优缺点下面的 多线程模型 就是把他们融合起来 ① 一对一模型 ② 多对一模型 ③ 多对多模型 【大纲新增考点】 6. 线程的状态与转换 7. 线程的组织与控制 小结 王道课本P66页有关于两种 线程调度 的内容 用户级线程调度内核级线程调度 2.2 处理机调度 ⭐
2.2.1 调度的概念 1. 调度的基本概念 处理机调度进程数 处理机个数需要对处理机进行分配 2. 调度的层次 一个作业从提交开始直到完成往往需要经历三级调度 ① 高级调度 (作业调度) ② 低级调度 (进程调度) ③ 中级调度 (内存调度) 3. 三级调度的联系 补充知识进程的挂起态 与 七状态模型 小结 2.2.2 调度的目标 1. CPU利用率 2. 系统吞吐量 3. 周转时间 4. 等待时间 5. 响应时间 小结 2.2.3 调度的实现 1. 进程调度的时机 内核程序临界区 和 临界区这两个不是同一个概念 当某个进程处于普通的临界区eg打印机 根据 当前运行的进程是否可以被强行的剥夺处理机资源 对进程调度的方式分成两类后面会具体介绍 发生引起调度条件且当前进程无法继续运行下去时可以马上进行调度与切换 —— 非可剥夺调度中断处理结束或自陷处理结束后返回被中断进程的用户态程序执行现场前若置换请求调度标志即可马上进行进程调度与切换 —— 可剥夺调度 2. 进程的切换与过程 3. 进程调度的方式 4. 调度程序调度器 调度程序用户调度和分派CPU的组件。调度程序是 操作系统内核程序 需要 调度程序 的调度时机 创建新进程 时调度程序就会出来看下是否需要让他上处理机进程退出 时处理机空闲调度程序就会出来看让谁接着上处理机运行 进程阻塞 时调度程序就会出来看让谁接着上处理机发生 I/O中断时有可能使得某些阻塞进程回到就绪态里一旦就绪队列发生改变时调度程序就会出来根据调度算法判断是否让他上处理机 调度程序的三部分 ① 排队器 将系统中的 所有就绪进程 按照一定的策略排成一个或多个队列以便进程调度 ② 分派器 将选中的进程从就绪队列取出分配CPU ③ 上下文切换器 处理机切换时会发生两对上下文的切换操作 当前进程的上下文保存到其PCB中再装入分派程序的上下文移出分派程序的上下文将新选进程的CPU现场装入处理机的各个相应寄存器 在上下文切换时需要执行大量的 load 和 store指令以保存寄存器的内容 5. 两种线程的调度 对于支持线程调度的操作系统来说分成两种调度 (简单了解、王道课上没提) 用户级线程调度内核不知道线程的存在内核选择一个进程由进程的调度程序决定哪个线程运行内核级线程调度内核选择一个特定线程运行不考虑该线程附属的进程 如果操作系统支持调度线程那么 调度程序 的对象就是 内核级线程 如果操作系统不支持调度线程那么 调度程序 的对象就是 进程 用户级线程 的线程切换在同一个进程中进行仅需少量的机器指令 内核级线程 的 线程切换 需要完整的上下文切换、修改内存映像、使高速缓存失效导致了若干数量级的延迟 6. 闲逛进程 闲逛进程无需CPU之外的资源。说白的就是街溜子CPU闲的没事干就闲逛 小结 2.2.4 典型的调度算法 1. 先来先服务FCFS 算法是否抢占 是否饥饿优点缺点FCFS非抢占不会公平、简单对长作业有利对短作业不利2. 短作业优先SJF 算法是否抢占 是否饥饿优点缺点FCFS非抢占不会公平、简单对长作业有利对短作业不利SJF/SPF非抢占会短对短作业有利对长作业不利SRTN抢占式会短对短作业有利对长作业不利3. 高响应优先HRRN 算法是否抢占 是否饥饿优点缺点FCFS非抢占不会公平、简单对长作业有利对短作业不利SJF/SPF非抢占会短对短作业有利对长作业不利SRTN抢占式会短对短作业有利对长作业不利HRRN非抢占不会4. 时间片轮转调度算法RR 算法是否抢占 是否饥饿优点缺点对象FCFS非抢占不会公平、简单对长作业有利对短作业不利作业/进程SJF/SPF非抢占会短对短作业有利对长作业不利作业/进程SRTN抢占式会短对短作业有利对长作业不利作业/进程HRRN非抢占不会作业/进程RR抢占式不会公平、响应快额外开销进程5. 优先级调度算法 算法是否抢占 是否饥饿优点缺点对象FCFS非抢占不会公平、简单对长作业有利对短作业不利作业/进程SJF/SPF非抢占会短对短作业有利对长作业不利作业/进程SRTN抢占式会短对短作业有利对长作业不利作业/进程HRRN非抢占不会作业/进程RR抢占式不会公平、响应快额外开销进程优先级都有会实时、应急饥饿作业/进程6. 多级反馈队列调度算法 算法是否抢占 是否饥饿优点缺点对象FCFS非抢占不会公平、简单对长作业有利对短作业不利作业/进程SJF/SPF非抢占会短对短作业有利对长作业不利作业/进程SRTN抢占式会短对短作业有利对长作业不利作业/进程HRRN非抢占不会作业/进程RR抢占式不会公平、响应快额外开销进程优先级都有会实时、应急饥饿作业/进程多级反馈队列抢占式会进程7. 多级队列调度算法 小结
算法是否抢占 是否饥饿优点缺点对象FCFS非抢占不会公平、简单对长作业有利对短作业不利作业/进程SJF/SPF非抢占会短对短作业有利对长作业不利作业/进程SRTN抢占式会短对短作业有利对长作业不利作业/进程HRRN非抢占不会作业/进程RR抢占式不会公平、响应快额外开销进程优先级都有会实时、应急饥饿作业/进程多级反馈队列抢占式会进程2.3 同步与互斥 ⭐
2.3.1 同步与互斥的基本概念 前言 在多道程序环境下进程并发运行不同的进程之间存在着不同的相互制约关系 为了协调进程之间的互相制约关系引入了 进程同步 的概念 简单的同步问题举例1 2 × 3需要先计算乘法再计算加法这就是计算中的制约关系 1. 临界资源 一次仅允许一个进程使用的资源称为 临界资源 对于 临界资源 的访问必须是 互斥 进行的每个进程中访问临界资源的那段代码成为 临界区 为了保证 临界资源 的正确使用把临界资源的访问过程分为4部分进入区、临界区、退出区、剩余区 关于 临界资源 和 临界区 的内容将在本节的 3. 进程互斥 会再次提及这里是简单介绍 2. 进程同步 进程同步的大白话理解相关的进程之间按照 某种规则 (前后制约关系)并发执行 【补充】 实际计算机运行中进程同步 需要考虑很多复杂因素但在《操作系统》中只需要关注 临界资源 即可 进程同步就是为了争抢临界资源。按照这个思路去学习 3. 进程互斥 进程同步 是 直接制约关系 进程互斥 是 间接制约关系 临界资源 要求一个时间段内只能一个进程访问也就是 互斥访问 资源 下图对 临界资源互斥访问的四个部分 进行了详细介绍 在对临界资源互斥访问的过程中需要遵守一些原则 空闲让进忙则等待有限等待让权等待 【补充概念】 死等没有进入 临界区 的正在等待的某进程 根本无法获得临界资源 而进入进程这种等待是无结果的 忙等没有进入临界区的正在等待的某进程不断的在测试循环代码段中的变量的值占着处理机而不释放 小结 本节内容临界资源 - 进程同步 - 进程互斥 同步并发进程为 完成同一任务 所进行的 工作顺序协调 互斥并发进程为 竞争临界资源 所进行的 资源分时占用 2.3.2 实现临界区互斥的基本方法 ⭐ 1. 进程互斥 的 软件实现方法 实现临界区互斥我们只需关注 进入区 和 退出区 的操作即可 软件实现方法的思想 进入区的操作 在进入区设置并检查一些 标志 来标明是否有进程在临界区中若已有进程在临界区则在进入区通过 循环检测 进行等待 退出区的操作进程离开临界区后在退出区 修改标志 【问题】 当没有进程互斥时有可能发生什么事故 答两个进程同时操作一个资源很混乱 ① 单标志法 int trun 0; // trun 表示当前允许进入临界区的进程号 主要问题违背了 空闲让进 原则空闲不让进了 只能按照 P0 - P1 - P0 - P1 - …… 这样的顺序访问资源P1必须等待P0访问完才能访问即使临界区空闲 ② 双标志先检查法 bool flag[2]; // 表示进程想进入临界区的意愿flag[0] false;flag[1] false; // 表示P0、P1开始都不需要进入临界区优点 解决了 单标志法 需要 交替进入不可连续使用 的问题 缺点 进入区需要实现两个功能检测 和 上锁但这两个步骤并不是一次性完成的可能出现两个进程 同时进入 临界区的情况 违背了 忙着等待 原则忙着还不等 ③ 双标志后检查法 对 双标志先检查法 进行修改先 上锁 后 检测 缺点 可能出现两个进程 都想进入临界区 又都无法进入 的情况互相争抢长期导致 饥饿 现象 违背了 空闲让进、有限等待 原则空闲不让进、等得老久 ④ Peterson 算法 bool flag[2]; // 表示进程想进入临界区的意愿int trun 0; // trun 表示优先让哪个进程进入临界区 Peterson 单标志法 双标志后检查法 谁最后谦让就失去了行动的优先权 缺点 违背 让权等待 原则出现忙等 例如当P0进程也想进入就必须等待P1进程结束 如果它进不来临界区那么它就会一直被卡在③不断检测自己是否可以进入临界区一直占用着CPU资源 小结 2. 进程互斥 的 硬件实现方法 理解 硬件实现对 信号量 的学习很有帮助 计算机提供了特殊的 硬件指令通过对一个字中的内容进行 检测 和 修正或对两个字的内容进行 交换 实现 进程互斥 通过硬件支持实现临界段问题的方法称为 低级方法元方法 ① 中断屏蔽方法 防止其它进程进入临界区的最简方法就是 关中断简单、高效 缺点 关中断指令只对发出关中断指令的处理机有效。如果是在多处理机关中断指令对于其它处理机是没有效果的关 / 开中断指令是特权指令只能在内核态下执行不适用于用户进程 ② TestAndSet指令 // 布尔型共享变量 lock表示当前临界区是否被加锁是否被占用
// true 表示已加锁false 表示未加锁
bool TestAndSet(bool *lock) {bool old;old *lock;*lock true;retuen old;
}whiel (TestAndSet (lock)); // 上锁 检测// 临界区代码lock false; // 解锁// 剩余区代码 TSL指令就是使用硬件方式实现 上锁 和 检测 的原子操作 缺点违背了 让权等待 原则 ③ Swap指令 缺点违背了 让权等待 原则 小结 2.3.3 互斥锁 1. 互斥锁的概念 这里先简单介绍 互斥锁 的概念之后会介绍使用互斥锁解决经典同步问题 2. 锁的特性 2.3.4 信号量 ⭐ 1. 信号量机制的概念 ① 把系统中的资源抽象化为变量信号量 记录着 资源数 ② 提供一对原语 wait(S) 和 signal(S) 来保证对 信号量S 操作的原子性 2. 信号量的类别 ① 整型信号量 ② 记录型信号量 当执行P0、P1进程时有打印机资源 当执行P2、P3进程时打印机资源缺乏P2、P3执行 block原语被挂在等待队列里 S.value 0资源恰好分配完S.value -1有1个进程在等待资源分配 P0进程使用完打印机执行 signal操作sigal是执行value 若 value之后value 0说明有进程在等待该资源就会执行 wakeup原语就会唤醒等待队列中的一个进程例如唤醒此时的P3 整形信号量 违背 让权等待 原则会出现 忙等 现象 记录型信号量就不会有上述情况 小结 3. 信号量机制的使用 之前学习的几种互斥的软硬件实现方式还有整形信号量都无法解决 让权等待 信号量机制设置了进程的 阻塞、唤醒就刚好解决了这个问题 ① 信号量机制 实现 进程互斥 之前提到过系统中的某一些资源是必须互斥访问的而访问这些系统资源的代码叫做 临界区 所以如果某些资源要互斥访问说明同一时刻只能有一个进程进入临界区 基于上面的理解所以就将 信号量mutex 表示为 进入临界区的名额名额只有1个 需要注意的几个点 semaphore mutex 1默认初始化记录型信号量具有排队阻塞的功能并不会出现忙等对于不同的临界资源需要设置不同的互斥信号量例如打印机、摄像头P、V操作一定要成对出现 ② 信号量机制 实现 进程同步 ③ 信号量机制 实现 前驱关系 每一对前驱关系都是一个进程同步问题就需要一个同步信号量 小结 2.3.5 管程 1. 为什么要引入管程 在引入管程之前计算机使用 信号量机制 解决互斥问题但是信号量机制编写代码太麻烦了所以出现了管程机制 2. 管程的定义 和 基本特征 管程代表共享资源的数据结构以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序 管程 很像面向对象中的 类开头提过 P/V 操作 编写太麻烦了所以引入 管程机制封装了系统资源以及对应的操作 3. 条件变量 当一个进程进入管程后被阻塞直到阻塞的原因解除时在此期间如果该进程还不释放管程那么 其他进程无法进入管程。 (同一时刻管程中只能有一个进程在执行) 为此将阻塞原因定义为 条件变量 condition; 通常一个进程被阻塞的原因可以有多个因此在管程中设置了多个条件变量 每个条件变量保存了一个等待队列用于记录因该条件变量而阻塞的所有进程对条件变量只能进行两种操作 ① x.wait当x对应的条件不满足时正在调用管程的进程调用 x.wait将自己插入x条件的等待队列并释放管程。 此时其他进程可以使用该管程。 ② x.signalx对应的条件发生了变化则调用 x.signal唤醒一个因x条件而阻塞的进程。进程离开管程时才能调用 // 条件变量的定义和使用举例
monitor Demo {共享数据结构 S;condition x; // 定义一个条件变量×init_code() { ... }take away() {if(S0) // 资源不够,在条件变量x上阻塞等待x.wait(O);资源足够,分配资源,做一系列相应处理;}give back() {归还资源,做一系列相应处理;if(有进程在等待) // 唤醒一个阻塞进程x.signal; }
} 条件变量和信号量的比较 相似点条件变量的wait/signal操作类似于信号量的P/V操作可以实现进程的阻塞/唤醒 不同点 条件变量是 没有值 的仅实现了 排队等待 功能信号量是 有值 的信号量的值反映了剩余资源数而在管程中剩余资源数用 共享数据结构 记录。 【拓展】用管程解决生产者消费者问题 管程的互斥由编译器负责实现程序员无需考虑 【拓展】Java中类似管程的机制 小结 2.3.6 经典同步问题 1. 生产者 - 消费者问题 ① 问题描述 ② 问题分析 ③ 如何实现 思考 2. 多生产者 - 多消费者问题 ① 问题描述 ② 问题分析 ③ 如何实现 小结 3. 吸烟者问题 ① 问题描述 ② 问题分析 ③ 如何实现 小结 4. 读者 - 写者问题 ① 问题描述 ② 问题分析 ③ 如何实现 小结 5. 哲学家进餐问题 ① 问题描述 ② 问题分析 ③ 如何实现 ④ 具体代码 小结 2.4 死锁
2.4.1 死锁的概念 1. 什么是死锁 循环等待 2. 死锁、饥饿、死循环的区别 3. 死锁产生的必要条件 4.什么时候会发生死锁 5. 死锁的处理策略 在这里插入图片描述
小结 2.4.2 死锁的处理策略 - 预防死锁 1. 预防死锁 - 破坏互斥条件 2. 预防死锁 - 破坏不剥夺条件 3. 预防死锁 - 破坏请求和保持条件 4. 预防死锁 - 破坏循环等待条件 小结 2.4.3 死锁的处理策略 - 避免死锁 1. 什么是安全序列 2. 安全序列、不安全状态、死锁 的联系 3. 银行家算法 如何避免系统进入不安全状态 举例说明 实际笔算思路 举一个找不到安全序列的例子 伪代码实现银行家算法 小结 2.4.4 死锁的处理策略 - 检测和解除 1. 死锁的检测 2. 死锁的解除 小结 2.5 常见问题和易混淆知识点
1. 进程与程序的区别与联系 ① 进程是程序及其数据在计算机上的一次运行活动是一个动态的概念。 进程的运行实体是程序离开程序的进程没有存在的意义。 从静态角度看进程是由程序、数据和进程控制块PCB三部分组成的。 而程序是一组有序的指令集合是一种静态的概念。 ② 进程是程序的一次执行过程它是动态地创建和消亡的具有一定的生命周期是暂时存在的 而程序则是一组代码的集合是永久存在的可长期保存。 ③ 一个进程可以执行一个或几个程序一个程序也可构成多个进程。进程可创建进程而程序不可能形成新的程序。 ④ 进程与程序的组成不同。进程的组成包括程序、数据和PCB。 2. 死锁与饥饿 具有等待队列的信号量的实现可能导致这样的情况 两个或多个进程无限地等待一个事件而该事件只能由这些等待进程之一来产生。 这里的事件是V操作的执行即释放资源)。出现这样的状态时这些进程称为死锁 (Deadlocked)。 为加以说明考虑一个由两个进程 P0 和 P1 组成的系统每个进程都访问两个信号量S和Q这两个信号量的初值均为1。 P0() {while(1) {P(S);P(Q);...V(S);V(Q);}
}
P1() {while(1) {P(Q);P(S);...V(Q);V(S);}
} 假设进程P0执行 P(S)接着进程P1 执行P(Q)。当进程P0执行PQ)时它必须等待直到进程P1执行 V(Q)。类似地当进程P1执行 P(S)时它必须等待直到进程P0执行 V(S)。由于这两个V操作都不能执行因此进程P0和进程P1就死锁了。 一组进程处于死锁状态是指组内的每个进程都在等待一个事件而该事件只可能由组内的另一个进程产生。这里所关心的主要是事件是资源的获取和释放。 与死锁相关的另一个问题是无限期阻塞 (Indefinite Blocking) 或饥饿 (Starvation)即进程在信号量内无穷等待的情况。 产生饥饿的主要原因是在一个动态系统中对于每类系统资源操作系统需要确定一个分配策略当多个进程同时申请某类资源时由分配策略确定资源分配给进程的次序。 有时资源分配策略可能是不公平的即不能保证等待时间上界的存在。 在这种情况下即使系统没有发生死锁某些进程也可能会长时间等待。 当等待时间给进程推进和响应带来明显影响时称发生了进程“饥饿”当“饥饿”到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被“饿死”。 例如当有多个进程需要打印文件时若系统分配打印机的策略是最短文件优先则长文件的打印任务将由于短文件的源源不断到来而被无限期推迟导致最终“饥饿”甚至“饿死”。 “饥饿”并不表示系统一定会死锁但至少有一个进程的执行被无限期推迟。“饥饿”与死锁的主要差别如下: ① 进入“饥饿”状态的进程可以只有一个而因循环等待条件而进入死锁状态的进程却必须大于等于两个。 ② 处于“饥饿”状态的进程可以是一个就绪进程如静态优先权调度算法时的低优先权进程而处于死锁状态的进程则必定是阻塞进程。 3. 银行家算法的工作原理 银行家算法的主要思想是避免系统进入不安全状态。 在每次进行资源分配时它首先检查系统是否有足够的资源满足要求若有则先进行试分配并对分配后的新状态进行安全性检查。 若新状态安全则正式分配上述资源否则拒绝分配上述资源。这样它保证系统始终处于安全状态从而避免了死锁现象的发生。 4. 进程同步、互斥的区别和联系 并发进程的执行会产生相互制约的关系 一种是进程之间竞争使用临界资源只能让它们逐个使用这种现象称为互斥是一种竞争关系 另一种是进程之间协同完成任务在关键点上等待另一-个进程发来的消息以便协同一致是一种协作关系。 1) 为什么要引入进程 在多道程序同时运行的背景下进程之间需要共享系统资源因此会导致各程序在执行过程中出现相互制约的关系程序的执行会表现出间断性的特征。 这些特征都是在程序的执行过程中发生的是动态的过程而传统的程序本身是一组指令的集合是一个静态的概念无法描述程序在内存中的执行情况即我们无法从程序的字面上看出它何时执行、何时停顿也无法看出它与其他执行程序的关系因此程序这个静态概念已不能如实反映程序并发执行过程的特征。 为了深刻描述程序动态执行过程的性质乃至更好地支持和管理多道程序的并发执行人们引入了进程的概念。 2什么是进程 进程由什么组成 进程是一个具有独立功能的程序关于某个数据集合的一次运行活动。 它可以申请和拥自的统资源是一个动态的概念是一个活动的实体。 它不只是程序的代码本身还包括当前的活动通过程序计数器的值和处理寄存器的内容来表示。 一个进程实体由程序段、相关数据段和PCB三部分构成其中 PCB是标志一个进程存在的唯一标识程序段是进程运行的程序的代码数据段则存储程序运行过程中相关的一些数据。 3进程是如何解决问题 进程把能够识别程序运行态的-一些变量存放在PCB中通过这些变量系统能够更好了解进程的状况并在适当时进行进程的切换以避免一些资源的浪费甚至划分为更小的调度单位—线程来提高系统的并发度。 本节主要介绍了处理机调度的概念。
操作系统主要管理处理机、内存、文件、设备几种资源.只要对资源的请求大于资源本身的数量就会涉及调度。例如在单处理机系统中处理税只有一个而请求服务的进程却有多个所以就有处理机调度的概念出现。而出现调度的概念活、人有了一个问题即如何调度、应该满足谁、应该让谁等待这是调度算法所回答的问题:流该满足谁、应该让谁等待要遵循一定的准则即调度的准则。调度这一概念贯穿于操作系统的娃终读者在接下来的学习中将接触到几种资源的调度问题和相应的调度算法。将它们与处理机调度的内容相对比,将会发现它们有异曲同工之妙。
1为什么要进行处理机调度 若没有处理机调度意味着要等到当前运行的进程执行完毕后下一个进程才能执行向实际情况中进程时常需要等待一些外部设备的输入而外部设备的速度与处理机相比是非常缓慢的若让处理机总是等待外部设备则对处理机的资源是极大的浪费。 而引进处理机调度后可在运行进程等待外部设备时把处理机调度给其他进程从而提高处理机的利用率。 用一句简单的话说就是为了合理地处理计算机的软/硬件资源。 2调度算法有哪些 各自特点是什么 适合哪些操作系统 本节介绍的调度算法有先来先服务调度算法、短作业优先调度算法、优先级调度算法、高响应比优先调度算法、时间片轮转调度算法、多级反馈队列调度算法6种。 先来先服务算法和短作业优先算法无法保证及时地接收和处理问题因此无法保证在规定的时间间隔内响应每个用户的需求也同样无法达到实时操作系统的及时性需求。 优先级调度算法按照任务的优先级进行调度对于更紧急的任务给予更高的优先级适合实时操作系统。 高响应比优先调度算法、时间片轮转调度算法、多级反馈队列调度算法都能保证每个.务在一定时间内分配到时间片并轮流占用 CPU适合分时操作系统。 1为什么要引入进程同步的概念 在多道程序共同执行的条件下进程与进程是并发执行的不同进程之间存在不同的相互制约关系。 为了协调进程之间的相互制约关系引入了进程同步的概念。 2不同的进程之间会存在什么关系 进程之间存在同步与互斥的制约关系。 同步是指为完成某种任务而建立的两个或多个进程这些进程因为需要在某些位置上协调之们的工作次序而等待、传递信息所产生的制约关系。 互斥是指当一个进程进入临界区使用临界资源时另一个进程必须等待当占用临界资源的进程退出临界区后另一进程才允许去访问此临界资源。 3单纯使用本节介绍的方法解决这些问题时会遇到新的问题吗 当两个或两个以上的进程在执行过程中因占有一些资源而又需要对方的资源时会因为争夺资源而造成一种互相等待的现象若无外力作用它们都将无法推进下去。这种现象称为死锁具体介绍和解决方案请参考下一节。 1为什么会产生死锁 产生死锁有什么条件 由于系统中存在一些不可剥夺资源当两个或两个以上的进程占有自身的资源并请求对方的资源时会导致每个进程都无法向前推进这就是死锁。 死锁产生的必要条件有4个分别是互斥条件、不剥夺条件、请求并保持条件和循环等待条件。 互斥条件是指进程要求分配的资源是排他性的即最多只能同时供一个进程使用。 不剥夺条件是指进程在使用完资源之前资源不能被强制夺走。 请求并保持条件是指进程占有自身本来拥有的资源并要求其他资源。 循环等待条件是指存在一种进程资源的循环等待链。 2有什么办法可以解决死锁问题 死锁的处理策略可以分为预防死锁、避免死锁及死锁的检测与解除。 死锁预防是指通过设立一些限制条件破坏死锁的一些必要条件让死锁无法发生。 死锁避免指在动态分配资源的过程中用一些算法防止系统进入不安全壮态从而避免死锁。 死锁的检测和解除是指在死锁产生前不采取任何措施只检测当前系统有没有发生死锁若有则采取一些措施解除死锁。
