操作系统-第2章进程管理.ppt

1 内容回顾 操作系统的基本特征 什么是微内核操作系统 它使用了哪些技术 2 第二章进程管理 学习目标 理解进程的概念以及与程序的异同掌握进程的实体 状态及状态的演变熟练掌握进程的控制与调度掌握进程之间的关系协调 同步与互斥 掌握进程的通信熟练掌握用信号量描述进程的同步 3 第二章进程管理 1进程的基本概念2进程控制3进程同步4经典进程的同步问题5管程机制6进程通信7线程 4 第二章进程管理 2 1进程的基本概念在传统的操作系统中 程序并不能独立运行 作为资源分配和独立运行的基本单位都是进程 在未配置OS的系统中 程序是顺序执行的在多道运行环境下 允许程序的并发执行 5 2 1 1程序的顺序执行及其特征 图2 1 1程序的顺序执行 2特征 顺序性 程序段中的操作和指令按顺序执行封闭性 程序独占资源 结果不受外界因素影响 可再现性 只要程序的运行环境和初始条件相同 无论什么时间执行都能得到相同的结果 6 2 1 2前趋图 图2 2 前趋图 ProcedureGraph 是一个有向无循环图DAG DirectedAcyclicGraph 用于描述进程之间执行的前后关系 图中的每一个结点可以用来表示一条语句 一个程序段或进程 结点间的有向边则表示在两结点之间存在的偏序或前趋关系 7 2 1 3程序的并发执行及其特征程序的并发执行 图2 3特征 间断性 并发性引起资源的共享或相互合作 因此形成了相互制约的关系 因而导致并发程序的 执行 暂停 执行 的间断过程 失去封闭性 并发性引起资源的共享 资源的状态由多个进程改变 这样进程的运行就失去了封闭性 8 不可再现性 并发性使程序的运行失去了封闭性 程序的计算结果与程序的速度有关 从而失去了结果的可再现性 例如两个循环程序A和B 他们共享一个变量N A执行一次N N 1 B执行一次都完成Print N 然后执行N 0 则会出现 N N 1 Print N N 0 Print N N 0 N N 1 Print N N N 1 N 0 9 2 1 4进程的特征与状态为什么要引入进程 并发程序执行的不可再现性 使程序的并发执行失去了意义 为了程序能并发执行 且能够对并发执行的程序进行控制和描述 10 进程的定义 进程是进程实体 程序段 数据段 进程控制块 的运行过程 是系统进行资源分配和调度的独立单位 11 结构特征 程序段 数据段 PCB 进程控制块 为了使程序能够独立运行而存放程序控制信息的数据结构 动态性 进程的实质是进程实体的一次执行过程 由创建而生 由调度而执行 由撤销而消亡 并发性 多个进程同驻内存 在一段时间内同时运行独立性 独立运行 资源分配 调度的单位异步性 独立的 不可预知的速度向前推进 进程的特征 12 思考题 程序与进程的联系与区别 13 进程基本状态及其转换 进程的动态性表明进程在其生存期内会经历一系列的离散状态 运行中的进程可以处于一下三种状态之一 图2 5就绪态 万事具备 只欠CPU执行态 进程获得CPU 正在运行阻塞态 发生事件无法继续 14 状态转换 就绪 进程调度分配CPU 执行执行 时间片用完 就绪执行 因某事件 I O请求 阻塞阻塞 资源满足 I O完成 就绪例题 15 3 具有挂起功能的进程状态及其转换 由于进程的不断创建 系统的资源特别是内存资源不能满足进程运行的需要 这时必须把某个进程对换到磁盘中 释放该进程占有的资源 暂时不参与进程调度 起到平滑系统操作负荷的目的 16 这种对换到磁盘 暂时不进行调度的进程状态叫做挂起状态 静止状态 分为静止就绪和静止阻塞 将进程换出的过程叫挂起将静止的进程换入的过程叫做释放静止就绪 进程具备运行条件 但处于辅存静止阻塞 进程正在等待某事件且在辅存中 17 系统中的进程均处于阻塞状态 处理机空闲 此时需要腾出内存空间 将资源分配给某个等待进程 然后执行 竞争资源 导致资源不足 负荷过重 此时需要将一些进程挂起 释放资源 用户要求挂起的自己的进程 以便对中间结果进行核查 修改 父进程要求修改子进程时 需要将子进程挂起 18 状态转换 如图2 6 活动阻塞 静止阻塞 活动阻塞进程由其自身调用或其他进程调用挂起原语 suspend 在其挂起期间并不影响其等待事件的发生 活动就绪 静止就绪 活动就绪进程由其自身或其他进程调用挂起原语而进入的一种状态 在其挂起期间没有资格竞争cpu 19 创建状态和终止状态 创建一个进程需要 创建PCB 并填写必要的管理信息 分配内存资源 转入就绪状态 终止一个进程需要 首先等待OS进行善后处理 然后将PCB清零 将PCB空间返还系统 20 图2 7进程的五种基本状态及转换 21 1 5进程控制块 图示 记录了操作系统所需要的 用于描述进程的当前状态 本身特性 对资源的占有以及控制进程运行的全部信息 记录了这些信息的数据结构就是进程控制块 PCB 是进程存在的唯一标志 常驻内存 22 2进程控制块中信息 进程标识符 外部标识符 名字 用户使用 内部标识符 数字 系统使用 处理机状态 由处理机各种寄存器中的内容组成 处理机运行时状态信息放在寄存器中 处理机中断时放在PCB中 通用寄存器 指令计数器 程序状态字 PSW 用户栈指针 23 进程调度信息 进程状态 进程优先级 进程调度需要的其它信息 事件 进程控制信息 程序和数据地址 进程同步和通信机制 资源清单和链接指针 24 3PCB的组织方式系统中通常会由多个PCB 这些PCB通常会用某种方式组织起来 才能有效的管理 链接方式 图2 7 索引方式 图2 8 25 2 2进程控制 进程控制是进程管理的最基本的功能 用于创建新进程 终止进程 进程的状态转换 进程控制由OS内核中的原语实现 原语 由若干指令组成的 用于完成一定功能的过程 这些过程是原子操作 原子操作 是一个不可分的基本单位 操作中的动作或者全做或者全不做 26 在操作系统中 通常把进程控制用程序段做成原语 用于进程控制的原语有 创建原语 creat 撤销原语 destory 阻塞原语 block 唤醒原语 wakeup 等 27 2 2 1进程创建 进程在执行过程中可以通过系统调用创建多个子进程 将正在执行的进程叫做父进程 新创建的进程叫做子进程 1进程图 描述进程的家族关系的有向树 图2 9 父进程 子进程 祖先进程 进程图由结点和有向边构成 28 子进程可以继承父进程拥有的资源子进程撤销时要归还父进程的资源父进程撤销时必须同时撤销所有的子进程 在PCB设置了家族关系表项 标明进程的父进程和所有子进程 29 请同学们想一下 使用进程图是为了描述什么 进程图与前趋图的比较 有什么异同 30 2引起进程创建的事件 用户登录作业调度提供服务应用请求 系统创建进程 父进程创建进程 31 3进程的创建调用creat 原语 申请空白PCB和唯一的数字标识符为新进程分配资源 内存空间 初始化PCB 标识信息 处理机状态信息 处理机控制信息将进程插入就绪队列 建立PCB 分配内存 加载程序 入就绪链 32 33 Creat s0 m0 pi p Get New PCB 分配新的PCBpid Get New PID 分配进程IDp ID pid 设置进程IDp CPU State so CPU的状态p Memory m0 p Priority pi p Status Type ready p Status List RL Insert RL p Scheduler 调度程序 34 2 2 2进程终止引起进程终止的事件 1正常结束 计算机系统中 都有一个表示进程已经运行完成的指示 如 批处理 Holt 分时系统中 LogsOff 2异常结束越界错误 保护错 特权指令错 非法指令错 运行超时 等待超时 算术运算错 I O故障3外界干预操作员或操作系统干预父进程请求父进程终止 35 36 2终止过程 调用进程终止原语根据进程标识符 从PCB集合中检索出该进程的PCB 读出该进程的状态 若正处于执行态 立即停止该进程的执行 并设置调度标志为真 把处理机分配给新进程 终止所有子进程 全部资源归还给其父进程或系统 将被终止进程的PCB从所在队列 或链表 中移出归还资源 撤销PCB 通知父进程 37 Destroy pid p Get PCB pid Kill Tree p Scheduler Kill Tree p For eachqinp creation tree child Kill tree q If p status type runing p1 p processor ID Interrupt p1 Remove p status list p release all p memory Releas all p other resources Close all p open files Delete PCB P 38 2 2 3进程的阻塞和唤醒 1进程阻塞一个进程经常要和其他进程通信 这在运行的进程因为提出服务请求 I O 操作 未得到操作系统的立即满足 或者所需数据尚未到达等原因 将转变为阻塞状态 39 2阻塞过程 调用阻塞原语block 是主动行为 停止进程的执行将PCB中的执行态改为阻塞态将PCB插入阻塞队列将处理机分配给另一个就绪进程 40 入口 保存当前进程的CPU现场 置该进程的状态 被阻塞进程入等待队列 转进程调度 阻塞原语 41 Block p Get PCB s p Status Type Cpu p processor ID P CPU State interrupt cpu p status type blocked Insert BL p Scheduler 42 3唤醒过程 唤醒原语wakeup 将等待该事件的进程唤醒 把阻塞的进程从阻塞队列中移出将PCB的状态由阻塞改为就绪将PCB插入就绪队列 43 入口 从等待队列中摘下被唤醒进程 将被唤醒进程置为就绪状态 将被唤醒进程送入就绪队列 进程调度返回 唤醒原语 44 Wakeup pid P Get PCB pid Remove p status list p P status type ready Insert RL p Scheduler 45 2 2 4进程的挂起和激活当出现了引起进程挂起的事件时 用户请求将自己挂起 或者父进程请求挂起自己的子进程 应该利用挂起原语suspend 挂起原语的执行过程 检查被挂起进程的状态 如果处于活动就绪状态 就将它改为静止就绪 如果处于活动阻塞 则改为静止阻塞 进程的激活过程 当发生激活事件后 系统利用激活原语Active 将指定进程激活 激活原语先将进程从外存调入内存 然后检查进程的状态 46 填空题 为使进程由活动就绪转变为静止就绪 应利用 原语 为使进程由执行状态变为阻塞状态 应利用 原语 为使进程由静止就绪变为活动就绪 应利用 原语 从阻塞状态变为就绪状态应利用 原语 suspend block active wakeup 47 知识回顾 什么是进程 进程的三种基本状态及转换条件及其关系 什么是进程控制块PCB 48 2 3进程同步 在多道程序运行环境下 并发执行的进程共享计算机资源 从而导致进程之间存在着一定的制约关系 为了保证执行结果的正确性和资源的充分利用 系统必须提供相应的并发控制机制 进程同步机制 并发进程之间为了完成某个任务而相互等待的关系就是进程同步关系 49 进程同步的任务 对多个相关进程在执行次序上进行协调 使并发进程之间有效的共享资源和相互合作 使执行结果可再现 2 3 1进程同步的基本概念1两种形式的制约关系 直接相互制约 源于相互合作 间接相互制约 源于资源共享 50 1 直接相互制约 发生在相关进程之间 2 间接相互制约 发生在任何进程之间 51 2临界资源 临界资源 一段时间内只允许一个进程访问的资源要求 各进程必须互斥访问临界资源 原因 例如生产者 消费者进程生产者进程 producer 消费者进程 consumer 放产品取产品counter counter 1 counter counter 1 52 机器语言形式为 生产者进程counter counter 1 1register1 counter 2register1 register1 1 3counter register1 消费者进程counter counter 1 4register2 counter 5register2 register2 1 6counter register2 由于生产者和消费者并发运行 且共享变量counter 造成 53 3临界区 临界区 每个进程中访问临界资源的代码称为临界区 进入区 检查临界资源是否正在被使用 退出区 将临界资源使用标志恢复 释放临界资源 剩余区 保证进程互斥的进入临界区 从而保证互斥访问临界资源 54 临界区 CS 每个进程中访问临界资源的那段代码生产者进程 producer 消费者进程 consumer 放产品取产品counter counter 1 CS counter counter 1 CS 为了实现对临界资源的互斥访问 应保证各进程互斥的进入临界区 55 4同步机制应遵循的规则 空闲让进 忙则等待 有限等待 让权等待 56 P操作相当于申请资源 而V操作相当于释放资源 所以要记住以下几个关键字 P操作 申请资源V操作 释放资源 2 3 2信号量机制 57 PV操作的含义 PV操作是由P操作原语和V操作原语组成 原语是不可中断的过程 对信号量进行操作 具体定义如下 P S 将信号量S的值减1 即S S 1 如果S 0 则该进程继续执行 否则该进程置为等待状态 排入等待队列 V S 将信号量S的值加1 即S S 1 如果S 0 则该进程继续执行 否则释放队列中第一个等待信号量的进程 58 一个生产者 一个消费者 公用一个缓冲区 59 empty 表示缓冲区是否为空 初值为1 full 表示缓冲区中是否为满 初值为0 生产者进程while TRUE 生产一个产品 P empty 产品送往Buffer V full 消费者进程while TRUE P full 从Buffer取出一个产品 V empty 消费该产品 60 信号量机制是一种卓有成效的进程同步工具 被广泛应用于单处理机和多处理机系统 以及计算机网络中 信号量机制 61 信号量的含义 信号量是一个用来实现进程同步的整型或记录型变量 除了初始化外 对它只能执行wait和signal这两种原子操作 在学习时 应了解对信号量的wait和signal操作分别是如何实现的 整型信号量存在着什么不足之处 记录型信号量是如何解决整型信号量的不足的 62 信号量的物理意义 一个信号量S通常对应于一类临界资源 在学习时 必须理解S value的值在物理上有什么特殊的含义 而每次wait和signal操作又分别意味着什么 故必须分别对S value进行什么操作 63 用信号量实现互斥 为了实现进程对临界资源的互斥访问 需为每类临界资源设置一初值为1的互斥信号量mutex 在学习时 应清楚在进入临界区前或退出临界区后应对mutex分别执行什么操作 为什么对mutex的wait和signal操作必须成对出现 如少了其中的wait操作或signal操作 会对互斥算法产生什么样的影响 64 用信号量实现前趋关系 为实现前趋关系Pi Pj 可为它们设置一个初值为0的信号量S 在学习时 应清楚对S的wait操作和signal操作应分别安排在什么位置 同时必须注意wait S 操作和signal S 操作也必须成对出现 65 信号量的分类 整型信号量 integersemaphore 信号量是整数 记录型信号量 recordsemaphore 每个信号量s除一个整数值s value 计数 外 还有一个进程等待队列s L 其中是阻塞在该信号量的各个进程的标识 66 1 整型信号量 最初由Dijkstra把整型信号量定义为一个整型量 除初始化外 仅能通过两个标准的原子操作wait s 和signal s 来访问 分别称为P和V操作 wait s whiles 0dono op s s 1 signal s s s 1ifs 0thenwakeup P1 67 2 记录型信号量 在整型信号量中的wait s 只要s 0则会不停地测试 该机制不遵循 让权等待 的准则 记录型的信号量描述如下 typesemaphore recordValue integer L listofprocess end 68 相应的wait s 和signal s 操作描述如下 procedurewait s vars semaphore begins Value s Value 1 ifs Value 0thenblock s L end proceduresignal s vars semaphore begins Value s Value 1 ifs Value 0thenwakeup s L end 当s Value初值为1时表示互斥信号量 69 3 AND型信号量 上述的进程互斥问题是针对进程之间要共享一个临界资源 在某些场合下 一个进程要先获得两类或更多的共享资源方能执行任务 例 有A B进程 它们共享D和E两个临界资源 对这两个数据分别用信号量S1和S2 且S1 S2 1 则在这两个进程中必然会有 processAprocessBwait S1 wait S2 wait S2 wait S1 70 如按如下调度方式 则A B进程进入了死锁 71 AND同步机制的基本思想 将进程在整个运行过程中所需要的所有临界资源一次性分配给进程 使用完后一起释放 只要一个资源没有分配到则其它可能分配到的资源也不分配 已经分配的全部释放 AND原语对资源的分配是原子的 其操作定义如下 72 swait s1 s2 sn ifs1 1ands2 1and sn 1thenfori 1tondosi si 1 endforelse将调用swait的进程置入所有的对应于si的等待该信号的进程队列中 endif ssignal s1 s2 sn fori 1tondosi si 1 将与si有关的进程插入到就绪队列中 endfor 73 4 信号量集 在记录型信号量中 P和V仅执行减1和增1操作 当一次需要N个某类资源时则要进行N次P操作 其效率低下 此外在某些情况下当资源数低于某一下限值便不分配 在每次分配之前 必须测试该资源总数是否大于下限值 下面是对AND信号量机制的改写 74 si 资源总数 ti 下限值 di 所需的资源数swait s1 t1 d1 sn tn dn ifs1 t1and sn tnthenfori 1tondosi si di endfor else将调用swait的进程插入到相应的si的等待队列中 75 ssignal s1 d1 sn dn fori 1tondosi si di 将对应于si的所有进程唤醒到就绪队列中 endfor 76 swait s d d 此时信号量集中仅有一个信号量 允许每次申请d个资源 当少于d时不分配 swait s 1 1 为一般的记录型信号量或互斥信号量 s 1 swait s 1 0 当s 1时允许多个进程进入 当s 0时阻止任何进程进入 77 2 3 3信号量的应用 1 利用信号量实现进程互斥设有2个并发进程P0和P1互斥共享counter变量 78 begincount integer 0 s semaphore 1 processPinprocessPoutr1 integerr2 integer beginbeginp s p s r1 count r2 count r1 r1 1 r2 r2 1 count r1 count r2 v s v s end end coend end 79 2 PV操作实现前趋图 80 定义 vara b c d e f g signal 0 0 0 0 0 0 0processs1processs2processs3s1 P a P b V a s2 s3 V b V c V e end V d end end processs4processs5processs6P c P d P e s4 s5 P f V f V g P g end end s6end 81 例1 桌上有一空盘 允许存放一只水果 爸爸可向盘中放苹果 也可向盘中放桔子 儿子专等吃盘中的桔子 女儿专等吃盘中的苹果 规定当盘空时一次只能放一只水果供吃者取用 请用P V原语实现爸爸 儿子 女儿三个并发进程的同步 82 解 在本题中 应设置三个信号量S So Sa 信号量S表示盘子是否为空 其初值为l 信号量So表示盘中是否有桔子 其初值为0 信号量Sa表示盘中是否有苹果 其初值为0 同步描述如下 83 intS 1 intSa 0 intSo 0 main cobeginfather 父亲进程 son 儿子进程 daughter 女儿进程 coend 84 father while 1 P S 将水果放入盘中 if 放入的是桔子 V So elseV Sa 85 son while 1 P So 从盘中取出桔子 V S 吃桔子 86 daughter while 1 P Sa 从盘中取出苹果 V S 吃苹果 87 三个进程P1 P2 P3互斥使用一个包含N N 0 个单元的缓冲区 P1每次使用produce 生成一个正整数 并用put 送入缓冲区的某一个单元中 P2每次用getodd 从该缓冲区中取走一个奇数 并用countodd 统计奇数的个数 P3每次用geteven 从该缓冲区中取走一个偶数 并用counteven 统计偶数的个数 请用信号量机制实现这三个进程的同步与互斥活动 并说明所定义的信号量的含义 要求用伪代码描述 思考题1 88 89 思考题2四个进程A B C D都要读一个共享文件F 系统允许多个进程同时读文件F 但限制是进程A和进程C不能同时读文件F 进程B和进程D也不能同时读文件F 为了使这四个进程并发执行时能按系统要求使用文件 现用PV操作进行管理 请回答下面的问题 90 1 应定义的信号量及初值 2 在下列的程序中填上适当的P V操作 以保证它们能正确并发工作 A B C D 1 3 5 7 readF readF readF readF 2 4 6 8 91 思考题解答 1 定义二个信号量S1 S2 初值均为1 即 S1 1 S2 1 其中进程A和C使用信号量S1 进程B和D使用信号量S2 2 从 1 到 8 分别为 P S1 V S1 P S2 V S2 P S1 V S1 P S2 V S2 92 内容回顾 什么是进程同步 什么是临界资源和临界区 进程同步遵循的规则 几种常见的信号量机制 93