操作系统第四章并发处理1 ppt课件

1,第四章 并发处理,（一）并发程序及特点 （二）进程的基本概念 （三）进程控制 （四）进程互斥 （五）进程同步 （六）线程的基本概念,2,（一）并发程序及特点,一、顺序程序及特点 1. 什么是程序的顺序执行 一个程序由若干个程序段组成，而这些程序段的执行必须按照严格的先后次序顺序执行。程序的顺序执行称为顺序程序设计。 顺序环境： 在单道计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响.,3,2. 程序顺序执行的特点,（1）程序执行的顺序性（大多数程序都具有） 处理机的操作严格按照程序所规定的顺序执行。 （2）程序执行的封闭性 独占资源，执行过程中不受外界影响（由执行环境保证） （3）程序执行结果的可再现性（确定性） 程序执行的结果与初始条件有关，而与执行时间无关。即只要程序的初始条件相同，它的执行结果也是相同的，不论它在什么时间执行，也不管计算机的运行速度。（由封闭性保证）,4,二. 并发程序及特点,1.并发环境： 在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的,5,例：用下图说明在多道批处理系统中，大量操作执行的先后次序。,讨论： （1）哪些程序段的执行必须是顺序的？为什么？ （2）哪些程序段的执行是可并行的？为什么？,6,2. 什么是程序的并发执行,程序并发执行 （定义） 若干个程序段同时在系统中运行，这些程序的执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并发执行的。 例：三个并发执行的程序段,7,3. 并行语句的表示,程序并发执行的描述 cobegin S1;S2;S3;.;SN coend; 提问： 语句S1、S2、S3、.、SN 谁先执行？谁后执行？,8,假设有一个程序由S0Sn+1个语句，其中 S1Sn语句是并发执行的，程序如下： S0; cobegin S1;S2;S3;.;SN coend; Sn+1;,9,4. 实例： a 一个循环程序顺序执行的誊抄,算法1： 输入：f 输出：g while (f 不为空） input ; output ; 由这个程序完成誊抄工作是不会出错的。,10,实例： b 两个程序并发执行完成誊抄,设有一台标准输入设备（键盘），和一台标准输出设备（显示器或打印机），输入程序负责从标准设备中读取一个字符，送缓冲区中。输出程序从缓冲区中取数据，送标准设备输出。,11,算法：2 cobegin while (不为结束符）/* 输入程序段 */ input; /* 从标准输入设备读入一个数据 */ send; /* 将读入的数据送到bufferf */ while(不为结束符） /* 输出程序段 */ receive; /* 从bufferf中取数据 */ output; /* 送打印机输出 */ coend ？存在什么问题？,12,这两个程序段并发执行时可能出现如下情况： 1、输出程序运行的速度比输入程序快时，有些输出会重复； 2、输入程序执行的速度比输出程序快时，有些数据会丢失。,13,实例： c 三个并发执行程序的誊抄,缓冲区s,缓冲区t,get程序负责从输入序列f中读取字符并送到缓冲区s中; copy程序把缓冲区s中的数据复制到缓冲区t中去; put程序从缓冲区t中取出数据打印。,14,假定f系列中有记录 f=(R1,R2,.,Rn) g=() 在誊抄完成后： f=() g=(R1,R2,.,Rn),算法中： copyt=s put put(t,g) get get(s,f),15,若程序错写成： while(誊抄未完成） cobegin copy; put; get; coend ,初始状态： f=(R1,R2,.,Rn) s=() t=() g=() 首先执行get(s,f) f=(R1,R2,.,Rn) s=R1,t=(),g=(),与时间有关的错误,16,然后，copy,put,get三个程序段并发执行，有六种组合： 1、copy;put;get 导致结果：g=(R1,R2) 2、copy;get;put 导致结果：g=(R1,R2) 3、put;copy;get 导致结果：g=(R1,R1) 4、put;get;copy 导致结果：g=(R1,R1) 5、get;copy;put 导致结果：g=(R1,R3) 6、get;put;copy 导致结果：g=(R1,R1) 这就是与时间有关的错误： 程序并发执行时，若共享公共变量，其执行结果与各并发程序的相对速度有关，即给定相同的初始条件，若不加以控制，也可能得到不同的结果，此为与时间有关的错误。,17,5. 并发程序的特点,（1）失去了程序的封闭性（程序结果的不可再现性） 如果程序执行的结果是一个与时间无关的函数，即具有封闭性。 若一个程序的执行可改变另一个程序的变量，程序执行的结果不仅依赖于程序的初始条件，还依赖于程序执行时的相对速度，在这种情况下结果是不确定的，即失去了程序的封闭性。 例：讨论共享公共变量的两个循环程序，它们执行时可能产生的不同结果。 设：程序A每执行一次都要做n加1的操作 程序B每隔一段时间打印出n的值，并将n重新置为零,18,（2）程序与计算不再一一对应 一个程序可以对应多个计算：多用户共享使用同一个程序，但处理（计算）的对象却是不同的。 例1： 例2： L1 编译； 输入程序段 L2 C编译程序 编译； Ln 编译。 （3）程序并发执行的相互制约 直接的相互制约关系公共变量 间接的相互制约关系资源共享,19,6. 进程的引入,并发活动进程的引入 操作系统的特性之一是并发与共享，这就会引起一系列的问题，包括：对资源的竞争、运行程序之间的通信、程序之间的合作与协同等。 操作系统的第三个特性：不确定性* 要解决这些问题，用程序的概念已经不能描述程序在内存中运行的状态，必须引入新的概念进程。,20,（二） 进程的基本概念,一、进程定义 在多道程序设计的环境下，为了描述程序在计算机系统内的执行情况，必须引入新的概念进程。 程序并发执行时，新的活动规律： 执行 暂停 执行 进程的概念来自于麻省理工的MULTICS、IBM的 TSS/360，在IBM的OS/360/370系统中也曾叫过任务（task)。 1. 什么是进程 所谓进程，就是一个程序在给定活动空间和初始环境下，在一个处理机上的执行过程。,21,2. 进程与程序的区别与联系：,1、程序是指令的集合，是静态的概念； 进程是程序在处理机上的一次执行的过程，是动态的概念。 进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的 2、进程是一个独立的运行单位，能与其它进程并行活动。而程序则不是。 进程更能真实地描述并发，而程序不能 3、进程是竞争计算机系统有限资源的基本单位，也是进行处理机调度的基本单位。 4、一个程序可以作为多个进程的运行程序，一个进程也可以运行多个程序。 进程具有创建其他进程的功能，而程序没有,22,3. 进程的类型,在系统中同时有多个进程存在，归纳起来有两大类： 1、系统进程 执行操作系统核心代码的进程。 系统进程起着资源管理和控制的作用。 2、用户进程 执行用户程序的进程。,23,系统进程与用户进程的区别：,1、系统进程被分配一个初始的资源集合，这些资源可以为它独占，也能以最高优先权的资格使用； 2、用户进程不能做直接I/O操作，而系统进程可以做显示的、直接的I/O操作。 3、系统进程在核态下活动，而用户进程则在用户态下活动。,24,二、进程的状态,1. 进程的基本状态 进程在系统中的活动规律是： 执行 暂停 执行 进程的三种基本状态： 运行状态 就绪状态 等待状态,25,（1）运行状态 （Running） 该进程已获得运行所必需的资源，它的程序正在处理机上执行。 （2）等待状态 （Wait） 进程正在等待某个事件的发生而暂停执行。这时，即使给它CPU时间，它也无法执行，则称该进程处于等待状态。 （3）就绪状态（Ready) 进程已获得除CPU之外的运行所必需的资源，一旦得到CPU控制权，立即可以运行。,26,在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换： 就绪运行 就绪等待 运行就绪 运行等待 等待就绪 等待运行,27,2. 进程状态的变迁,进程的状态不是固定不变的，而是在不断变换，它随着自身的推进和外界条件的变换而发生变化。,28,新建态 对应进程刚被创建的状态 为一个新进程创建必要的管理信息，它并没有被提交执行，而是在等待操作系统完成创建进程的必要操作 进程何时创建 提交一个作业 用户登录 由已有进程创建 ,29,终止态 进程的终止：先等待操作系统进行善后，然后退出主存 进入终止态的进程不再执行，但依然临时保留在系统中等待善后。一旦其他进程完成了对终止态进程的信息抽取之后，系统将删除该进程 进程何时终止 作业完成 用户退出 程序出错（写只读文件、I/O失败等） 父进程请求终止子进程 父进程终止 ,就绪态终止态 等待态终止态,30,系统中一个进程存在： 进程的执行程序（一个可执行文件） 进程总是位于某个队列(就绪、等待某事件队列) 处于某种状态（运行、就绪、等待） 占用某些系统资源（内存，打开某些文件、处理机、外设）,进程标识信息,进程状态信息,进程控制信息,用户堆栈,共享地址空间,用户私有地址空间 （代码、数据）,进 程 控 制 块,三、进程描述,进程控制块（数据结构）,31,1. 什么是进程控制块,描述进程在各个不同时期所处的状态，与其他进程及系统资源关系的数据结构，称为进程控制块pcb（process control block），也称为进程描述器（process descriptor） 系统为了管理进程而设置的一个专门的数据结构，用来记录进程的外部特征，描述进程的运动变化过程 系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志 进程与PCB是一一对应的,32,2. 进程的组成,程序与数据： 描述进程本身所应完成的功能； PCB： 描述进程的动态特征，该进程与其他进程和系统资源的关系。,进程 控制块 PCB,程 序 与 数 据,33,3. PCB的主要内容,（1）进程标识符：进程符号名或内部id号 （2）进程当前状态（运行、就绪、等待）,系统中进程很多，状态也不一样。如何有效组织PCB方便调度和管理进程？,有三种方法： 把所有PCB组织在一个表格中（简单，但查找不方便，适用于进程数目少的场合） 分别把具有相同状态的进程PCB组织在同一表格中（如就绪进程表，等待进程表，运行进程表） 分别把具有相同状态的所有进程的PCB按优先级排成一个或多个队列（最常用的方法，如就绪队列，等待队列等，可能等待的资源相同，但优先级不同）,34,总链队列结构,（3）当前队列指针next： 登记处于同一状态的下一个进程的pcb地址。 （4）总链队列指针all_q_next： 登记系统总链队列中，下一个进程的pcb地址。,35,3. PCB的主要内容,（5）程序开始地址： 该进程的程序将从此地址开始执行。 （6）进程优先级： 反映了进程要求CPU的紧迫程度。 （7）CPU现场保护区： 当进程由于某种原因释放处理机时，CPU现场信息被保存在pcb的该区域中。 （8）通信信息： 进程间进行通信时所记录的有关信息。 （9）家族联系： 指明本进程与家族的联系。 （10）占有资源清单,36,（三）进程控制,一. 进程控制的概念 进程控制的职责是对系统中全部进程实施有效的管理，它是处理机管理的部分（另一部分是进程调度），当系统允许多进程并发执行时，为了实现共享、协调并发进程的关系，处理机管理必须对进程实行有效的管理。 进程控制包括： 进程创建、进程撤消、进程阻塞、进程唤醒 改变优先数、 调度进程、进程延迟 这些操作都要对应地执行一个特殊的程序段（操作系统核心程序），同时系统也通过系统调用给用户提供进程控制的功能。教材上叫原语（一种特殊的系统调用）。,原语(Primitive)：在管态下执行、完成系统特 定功能的过程 特点：执行过程中不允许被中断，是一个不 可分割的基本单位，原语的执行是顺序的而 不可能是并发的 实现方法：以系统调用方式提供原语接口， 且采用屏蔽中断的方式来实现原语功能，以 保证原语操作不被打断的特性,37,38,二. 进程创建,1. 进程创建原语的形式： create(name,priority,start-addr) 入口参数 name：被创建进程的标识符 priority：进程优先级 start-addr：某程序的开始地址。 2. 进程创建原语的功能： 创建一个指定标识符的进程(形成该进程的进程控制块pcb)。 UNIX系统： fork() 生成进程称父进程(Parent Process) ，被生成进程称子进程(Child Process),即一个父进程可以创建子进程，从而形成树形结构,39,3. 进程创建原语的实现,创建一个PCB 从PCB池中申请一个空的PCB结构： -1 = x 赋予一个统一进程标识符 为进程映象分配空间及资源，读入正文段 初始化进程控制块 设置相应的链接 如: 把新进程加到就绪队列的链表中,40,41,进程创建后相应数据结构变化,42,三. 进程撤消,当进程完成任务后希望终止自己时使用进程撤销原语。 1. 进程撤销原语的形式： Kill（或exit） 该命令没有参数，其执行结果也无返回信息。 2. 进程撤销原语的功能： 撤销当前运行的进程。将该进程所占用的资源归还给父进程，从总链队列中摘除pcb结构，归还到pcb资源池，然后转进程调度程序。 UNIX系统：exit(),43,3. 进程撤消原语的实现,根据撤销进程标识号，从相应队列中找到它的PCB 将该进程拥有的资源归还给父进程或操作系统 若该进程拥有子进程，应先撤销他的所有子孙进程，以防它们脱离控制 被撤销进程出队，将它的PCB归还到PCB池 调用进程调度程序,44,45,四. 进程阻塞,当进程需要等待某一事件完成时，它可以调用等待原语把自己挂起。 1. 进程阻塞原语的形式： susp（chan） 入口参数chan：进程等待的原因。 2. 进程等待原语的功能： 中止调用进程的执行，并加入到等待chan的等待队列中，最后使控制转向进程调度。 UNIX：sleep(chan, pri),46,3. 进程等待原语的实现,算法 susp（chan） 输入：chan 等待的原因 输出：无 进程现场信息PCB； 进程状态置为“阻塞”； 插入到等待 “chan”等待队列； 调用进程调度程序； ,47,48,五. 进程唤醒,1. 进程唤醒原语的形式： 当处于等待状态的进程所期待的事件来到时，由发现者进程使用唤醒原语叫唤醒它。 wakeup（chan） 入口参数chan：进程等待的原因 2. 进程唤醒原语的功能： 当进程等待的事件发生时，唤醒等待该事件的进程。,49,3. 进程唤醒原语的功能 从相应的等待进程队列中取出进程控制块 修改进程控制块的有关信息，如进程状态等 把修改后进程控制块加入有关就绪进程队列 进程唤醒操作会引起就绪队列和等待chan事件的等待队列发生变化。,50,Unix进程,Unix进程树的结构,51,Unix的进程管理,Unix进程由proc结构、数据段和正文段三部分组成,合称进程映像,进程 控制块 PCB,程 序 与 数 据,基本进程控制块 proc结构 存放进程的最基本的管理和控制信息 正文段 （仅共享时存在） 数据段（又称上下文，context） 数据区和用户栈区 共享正文段（text表，正文控制表） U区（PPDA，进程数据区）：核心栈、User结构,52,进程控制块(PCB),proc结构 proc.h (基本的) 进程控制和管理的最基本的信息 常驻内存 user结构 user.h (扩充的) 进程运行时才用到的数据和状态信息 通常和数据段一起放在磁盘上，需要时调入 正文控制表 text.h 管理共享正文区 内存无共享进程映像时调出,53,数据结构之间的关系,54,进程上下文切换,进程上下文：进程的物理实体和支持进程运行的环境合称为进程上下文（context）。 进程的运行被认为是在上下文中执行。 进程上下文的组成： 用户级上下文：由用户程序块、用户数据块和用户堆栈组成的进程地址空间。 系统级上下文：包括进程的标识信息、现场信息和控制信息，进程环境块，及系统堆栈等组成的进程地址空间。 寄存器上下文：由PSW寄存器和各类控制寄存器、地址寄存器、通用寄存器组成。 当系统调度新进程占有处理器时，新老进程随之发生上下文切换。 进程切换:中断处于运行态的进程运行，让出处理器，恢复新进程的状态，使新进程投入运行。,55,进程上下文切换的步骤,保存被中断进程的处理器现场信息 修改被中断进程的进程控制块的有关信息，如进程状态等 把被中断进程的进程控制块加入有关队列 选择下一个占有处理器运行的进程 修改被选中进程的进程控制块的有关信息 根据被选中进程设置操作系统用到的地址转换和存储保护信息 根据被选中进程恢复处理器现场,56,CPU模式切换,模式切换：中断发生时，暂时中断正在执行的用户进程，把进程从用户状态切换到内核状态，去执行操作系统例行程序以获得服务 内核在被中断了的进程的上下文中对这个中断事件作处理，即使该中断可能不是此进程引起的 内核都要保留被中断进程的足够信息以便后来能恢复被中断了的进程执行 保存被中断进程的处理器现场信息 根据中断号置程序计数器 把用户状态切换到内核状态，以便执行中断处理程序,模式切换 vs. 上下文切换 模式切换不同于进程切换，它并不引起进程状态变化，也不一定引起进程的切换，在完成了中断调用之后，完全可以再通过一次逆向的模式切换来继续执行用户进程,57,UNIX中进程上下文切换和模式切换,用户进程因中断和系统调用进入内核态，系统进程开始执行，两个进程使用同一个PCB，实质上是一个进程。但所执行的程序不同，映射到不同物理地址空间、使用不同堆栈,58,Unix进程状态,1运行状态 处理机正在执行该进程的程序时所处的状态 用户态运行状态 (进程执行用户程序) 核心态运行状态 (进程执行核心程序),59,Unix的进程“挂起”,进程不断创建，系统资源已不能满足进程运行的要求，必须把某些进程挂起（suspend），对换到磁盘镜像区中，暂时不参与进程调度，起到平滑系统操作负荷的目的 把一些阻塞进程对换出去，腾出足够内存装入就绪进程运行 系统资源不足，负荷过重，需要挂起部分进程以调整系