进程与进程管理.ppt

操作系统,第三章 进程与进程管理,第三章 进程与进程管理,3-1 进程的引入3-2 进程3-3 进程调度3-4 线程的基本概念3-5 Linux的进程与进程管理,3.1 进程的引入,3-1-1前趋图的定义 前趋图（Procedence Graph）是一个有向无循环图（DAG）。图中的每个结点可用于表示一条语句、一个程序段或进程；结点间的有向边则表示在两结点之间存在的偏序或前趋关系“”，=(Pi，Pj)|Pi必须在Pj开始前完成。,3.1 进程的引入,3-1-2 程序顺序执行 定义 程序在执行时，必须按照某种先后次序逐个执行，仅当前一操作执行完后，才能执行后继操作。程序顺序执行的特征 程序执行的顺序性 处理机的操作严格按程序规定的顺序执行，即只有前一操作结束后才能执行后继操作。程序执行的封闭性 程序一旦开始运行，其执行结果不受外界因素的影响。,3.1 进程的引入,程序执行结果的确定性 程序执行的结果与它的执行速度、时间无关。程序结果的可再现性 程序执行时的环境和初始条件相同，当程序多次重复执行时，都将获得相同的结果。3-1-3 程序并发执行 定义图中对一个作业的输入、计算和打印三个操作必须顺序执行，但并不存在PiIi+1关系，因而在对几批数据进行处理时，可使它们并发执行,3.1 进程的引入,程序并发执行特征 程序执行的间断性 程序执行的相互制约将导致并发程序具有“执行暂停执行执行”这种间断性的活动规律 程序执行失去封闭性 因多个程序共享系统中的资源，所以某程序在执行时必然会受到其他程序的影响 程序执行结果的不可再现性 由于失去了封闭性，也将导致失去其可再现性,3.1 进程的引入,例如,共享变量n a=n;b=n;a+;b+;n=a;n=b;程序和计算不再一一对应 程序和计算是两个不同的概念，在程序并发执行中一个共享程序可对应多个“计算”，程序与“计算”已不再一一对应.,3.1 进程的引入,3-1-4 多道程序设计 定义 在采用多道程序设计的计算机系统中，允许多个程序同时进入一个计算机系统的主存储器并运行，这种让多个程序同时进入计算机计算的方法称为多道程序设计。目的 提高处理器的效率，从而提高整个系统的效率 必须解决的问题 存储保护与程序浮动 处理器的管理和调度 系统资源的管理和调度,3.2 进程,3-2-1 引入进程的原因 为了使程序在多道程序环境下能够并发执行，并对并发执行的程序加以控制和描述，引入进程的概念.程序段、数据段及进程控制块三部分构成了一个进程的实体.3-2-2 进程的概念 进程的定义 进程是具有独立功能的可并发执行的程序在一个数据集合上的运行过程，是系统进行资源分配和调度的独立单位”。或者说，“进程”是进程实体的运行过程。,3.2 进程,程序与进程的区别与联系 进程是程序的一次执行，是一个动态的概念，程序是完成某个特定功能的指令的有序序列，是一个静态的概念;一个进程可以执行一个或几个程序，同一程序也可能由多个进程同时执行 进程是系统进行资源分配和调度的一个独立单位，程序则不是 程序可以作为一种软件资源长期保存，而进程是程序的一次执行过程，它是临时的，有生命期的 进程是具有结构的,3.2 进程,进程的特征 _ 动态性 _ 并发性 _ 独立性 _ 异步性 _ 结构特征3.2.2 进程的基本状态及其转换进程的三种基本状态 就绪状态 当进程已分配到除CPU以外的所有必要的资源后，只要能再获得处理机便可立即执行，这时的状态称为就绪状态,3.2 进程,执行状态 指进程已获得处理机，其程序正在执行 阻塞状态 进程因发生某种事件（如I/O请求、申请缓冲空间等）而暂停执行时的状态，亦即进程的执行受到阻塞，故称这种状态为阻塞状态，有时也称为“等待”状态或“睡眠”状态。进程状态的转换 就绪执行状态 处于就绪状态的进程，当进程调度为之分配了处理机后,3.2 进程,执行阻塞状态 正在执行的进程因发生某种事件而无法执行 执行就绪状态 正在执行的进程如因时间片用完或一个优先权高的进程到来而被暂停执行 阻塞就绪状态 处于阻塞状态的进程，其等待的事件已经发生,3.2 进程,进程的挂起状态 挂起状态的引入 终端用户的需要 父进程的需要 操作系统的需要 对换的需要 负荷调节的需要 进程状态的转换 活动就绪静止就绪 活动阻塞静止阻塞 静止就绪活动就绪 静止阻塞活动阻塞,3.2 进程,3.2 进程,3-2-3 进程控制块PCB 进程控制块的作用 进程控制块的作用是使一个在多道程序环境下不能独立运行的程序（含数据）成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程 操作系统是根据进程控制块PCB来对并发执行的进程进行控制和管理的 PCB是进程存在的唯一标志,3.2 进程,进程控制块中的信息 进程标识符信息 进程标识符用于唯一地标识一个进程，通常有外部标识符和内部标识符 处理机状态信息 处理机状态信息主要是由处理机各种寄存器中的内容所组成 进程调度信息 存放了一些与进程调度和进程对换有关的信息 进程控制信息,3.2 进程,PCB的组织方式-链接方式思考：如何申请一个进程PCB，算法怎么写？,练习,进程控制块区域：struct pcbdata data;/pcb中其他信息 int next;/指向下一个pcb pcbarean;写出：进程控制块区域初始化；pcb队列中出队和入队操作；,3.2 进程,-索引方式,3.2 进程,3-2-4 进程控制 进程控制的主要任务是创建和撤消进程以及实现进程的状态转换 操作系统内核 定义 通常，将一些与硬件紧密相关的模块诸如中断处理程序、各种常用设备的驱动程序以及运行频率较高的模块（诸如时钟管理、进程调度以及许多模块公用的一些基本操作）都安排在紧靠硬件的软件层次中并使它们常驻内存，以便提高操作系统的运行效率，并对它们加以特殊的保护，把这一部分称为操作系统的内核 操作系统内核的功能 中断处理、进程管理、资源管理中的基本操作,3.2 进程,原子操作 所谓原子操作是指：一个操作中的所有动作，要么全做，要么全不做。换言之，原子操作是一个不可分割的操作 进程的创建 进程图 进程图是用于描述进程家族关系的有向树 子进程可以继承父进程所拥有的资源，当子进程撤销时，应将从父进程那里获得的资源归还给父进程；在撤销父进程时，也必须同时撤销其所有的子进程,3.2 进程,引起创建进程的事件 用户登录、作业调度、提供服务、应用请求 进程的创建过程 调用进程创建原语create()创建进程 申请空白PCB 为新进程分配资源 初始化进程控制块 将新进程插入就绪队列 进程的终止 引起进程终止的事件 正常结束、异常结束、外界干预,3.2 进程,进程的终止过程 调用进程终止原语destroy()终止进程 根据被终止进程的标识符从PCB集合中检索出该进程的PCB，从中读出该进程的状态 若被终止进程正处于执行状态，应立即终止该进程的执行并设置调度标志为真 若该进程还有子孙进程，还应将其所有子孙进程予以终止 将该进程所拥有的全部资源，或者归还其父进程或者归还给系统 将被终止进程的PCB从所在队列中移出，等待其他程序来搜集信息,3.2 进程,进程的阻塞与唤醒 引起进程阻塞和唤醒的事件 请求系统服务、启动某种操作、新数据尚未到达、无新工作可作 进程阻塞过程 进程便通过调用阻塞原语block（）把自己阻塞 立即停止当前进程的执行 把进程控制块中的现行状态由“执行”改为“阻塞”，并把它插入到阻塞队列 调度程序进行重新调度，保留被阻塞进程的处理机状态（在PCB中），再按新进程的PCB中的处理机状态设置CPU环境,3.2 进程,进程唤醒过程 调用唤醒原语wakeup()将等待该事件的进程唤醒 把被阻塞进程从等待该事件的阻塞队列中移出 将其PCB中的现行状态由“阻塞”改为“就绪”然后再将该进程插入到就绪队列中 进程的挂起与激活 进程的挂起过程 当出现了引起进程挂起的事件时，系统就利用挂起原语suspend()将指定进程或处于阻塞状态的进程挂起 检查被挂起进程的状态，若正处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将其改为静止阻塞,3.2 进程,如被挂起的进程正在执行，则转调度程序重新调度 进程的激活过程 当发生激活进程的事件时系统将利用激活原语active()将指定进程激活 将进程从外存调入内存，检查该进程的现行状态：若是静止就绪，便将其改为活动就绪；若为静止阻塞，便将其改为活动阻塞 假如采用的是抢占调度策略，检查是否要进行重新调度,3.3 进程调度,3-3-1 调度的基本概念 高级、中级和低级调度 一个作业从提交开始直到完成，往往要经历三级调度 高级调度 高级调度又称为作业调度，它决定将哪些在外存上处于后备状态的作业调入主机内存，准备执行 低级调度 低级调度又称为进程调度。它决定就绪队列中哪个进程将获得处理机，并实际执行将处理机分配给该进程的操作 中级调度 在有的系统中，可能增加一中级调度，主要作用是在内存和外存对换区之间进行进程对换，以解决内存紧张问题,3.3 进程调度,进程调度的功能 进程调度就是系统按照某种算法把CPU动态地分配给某一就绪进程。进程调度工作是通过进程调度程序来完成的。进程调度程序的主要功能 选择占有处理机的进程 进行进程上下文的切换 调度方式非剥夺方式 该方式规定，分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件（如提出I/O请求）而阻塞时才把处理机分配给另一进程 优点：简单，系统开销小，貌似公正 缺点：可能导致系统性能的恶化,3.3 进程调度,剥夺方式 该方式规定，当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程 剥夺原则：优先权原则、短进程优先原则、时间片原则3-3-2 进程调度算法 先进先出（FIFO）算法 算法：把处理机分配给最先进入就绪队列的进程 优点：易于实现、表面上公平 缺点：服务质量不佳、对短进程不利 最短处理机执行期优先调度算法 算法：从就绪队列中选出“下一个处理机执行期”最短的进程，为之分配处理机使之执行 优点：可获得较好的调度性能 缺点：进程的处理机执行期难以准确得到、对长进程不利,3.3 进程调度,最高响应比优先调度算法 算法：响应比=（等待时间+要求的服务时间）/要求的服务时间，每次选取响应比最高的进程调度 优点：所以对短进程有利，并且考虑了等待时间 缺点：计算响应比有一定的系统开销 优先级调度算法 算法：将处理机分配给就绪队列中优先级最高的进程 优先级 静态优先级 再进程创建时确立，确定后运行期间保持不变。确立依据有：进程的类型、进程对资源的需求、用户申请的优先级 优点：简单 缺点：不能动态反映进程特点，系统调度性能差,3.3 进程调度,动态优先级 进程在开始创建时，根据某种原则确定一个优先级后，随着进程执行时间的变化，其优先级不断地进行动态调整 确定依据：根据进程占有的CPU时间的长短来决定，占有时间越长优先级越低；根据进程等待CPU的时间来决定，时间越长优先级越高 时间片轮转调度算法 算法：通常用在分时系统，它轮流地调度系统中所有就绪进程，使就绪进程依次获得一个时间片的运行时间 时间片长短确定遵循原则 既要保证系统各个用户进程及时地得到响应，又不要由于时间片太短而增加调度的开销，降低系统的效率 进程依次执行时可能发生的三种情况 进程未用完一个时间片便结束，这时系统应提前进行调度,3.3 进程调度,进程在执行过程中提出I/O请求而阻塞，系统应将它放入相应的阻塞队列并引起调度 进程用完一个时间片后尚未完成。系统应将它重新放到就绪队列的末尾，等待下次执行 前后台调度算法 算法：该方法用在批处理和分时相结合的系统中。将分时用户作业放在前台，把批处理作业放在后台。系统对前台作业按照时间片轮转法进行调度，仅当前台无作业时，才把处理机分配给后台作业的进程。后台进程通常按先来先服务方式运行 优点：使分时用户进程得到及时响应，又提高了系统资源的利用率,3.3 进程调度,多级反馈队列轮转算法 算法：系统设置多个不同优先级的就绪队列，每次调度总是先调度优先级高的队列，仅当该队列空时，才调度次高优先级队列 优点：能较好地满足各类作业的用户要求，既能使分时用户作业得到满意的响应，又能使批处理用户的作业获得较合理的周转时间,3.3 进程调度,3-3-3 进程调度的时机和过程 进程调度的时机 正在执行的进程运行完毕 正在执行的进程调用阻塞原语将自己阻塞起来进入等待状态 在采用抢占式优先级调度时，有优先级高于正在运行进程的进程进入就绪队列 在分时系统中时间片已经用完 进程调度的过程 进程调度所依赖的数据结构通常是调度队列，由于调度的原因不同，在单处理器系统中设置了多种等待队列 只有就绪队列中的进程能够获得处理器而最终运行，其他队列中的进程从队列中调度出来后，必须进入就绪队列才能分配处理器,3.3 进程调度,队列数据结构的建立结构与调度算法密切相关 进程调度算法只是决定哪一个进程将获得处理机，而将处理机分配给该进程的具体操作是由分派程序完成的 例：假定就绪队列中的进程，已按其优先权的大小排列并允许剥夺调度，当就绪队列的队首出现其优先权比当前正在执行进程j的优先权更高的进程i时，应立即停止当前进程j的执行并将它按其优先权的大小，插入到就绪队列中的适当位置上（调用enqueue(RQ,j)），然后用进程i所保存的CPU现场信息去恢复CPU现场。采用最高优先级优先的调度算法可描述如下：,3.3 进程调度,void dispatcher()if(RQ=0)if(EP=0)idler();else continue;enqueue(RQ,i);if(EP=0)go to L;j=EP;if(i.priorityj.priority),stop(j);j.status=ready;j.sdata=Epdata;enqueue(RQ,j);L:dequeue(RQ,i);i.status=executing;EPdata=i.sdata;EP=i;else continue;,3.4 线程的基本概念,3-4-1 线程的引入 在操作系统中引入进程的目的是为了使多个程序并发执行以改善资源利用率及提高系统的吞吐量；那么，在操作系统中再引入线程，则是为了减少程序并发执行时所付出的时空开销，使操作系统具有更好的并发性3-4-2 线程的定义和属性 线程的定义 在引入线程的操作系统中，线程是进程的一个实体，是被系统独立调度和分派的基本单位。线程自己基本上不拥有系统资源，只拥有一点在运行中必不可少的资源（如程序计数器、一组寄存器和栈），但它可与同属一个进程的其他线程共享进程所拥有的全部资源。一个线程可以创建和撤销另一个线程；同一进程中的多个线程之间可以并发执行,3.4 线程,线程的属性 线程的状态 由于线程之间的相互制约，致使线程在运行中也呈现出间断性。相应地，线程也同样有就绪、阻塞和执行三种基本状态 线程的属性 每个线程有一个惟一的标识符和一张线程描述表，线程描述表记录了线程执行的寄存器和栈等现场状态 不同的线程可以执行相同的程序 同一进程中的各个线程共享该进程的内存地址空间 线程是处理器的独立调度单位，多个线程是可以并发执行的 一个线程被创建后便开始了它的生命周期，直至终止，线程在生命周期内会经历等待状态、就绪态和运行态等各种状态变化引入线程的好处 创建一个新线程花费时间少（结束亦如此）两个线程的切换花费时间少,3.4 线程,由于同一进程内的线程共享内存和文件，线程之间相互通信无须调用内核，故不需要额外的通信机制，使通信更简便，信息传送速度也快 线程能独立执行，能充分利用和发挥处理器与外围设备并行工作能力3-3-3 线程与进程的比较 线程具有许多传统进程所具有的特征，故又称为轻型进程（Light-Weight Process）或进程元；而把传统的进程称为重型进程（Heavy-Weight Process）调度 在引入线程的操作系统中，线程是调度和分派的基本单位；在同一进程中，线程的切换不会引起进程切换；在由一个进程中的线程切换到另一进程中的线程时，将会引起进程切换 并发性 在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，因而使操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统吞吐量,3.4 线程,拥有资源 不论是传统的操作系统，还是设有线程的操作系统，进程都是拥有资源的一个独立单位，它可以拥有自己的资源。一般地说，线程自己不拥有系统资源（也有一点必不可少的资源），但它可以访问其隶属进程的资源 系统开销 创建、撤销以至于切换进程时付出的系统开销显著大于创建、撤销、切换线程时的系统开销3-4-4 线程的实现机制 用户级线程 仅存在于用户级中，对于这种线程的创建、撤销和切换，都不利用系统调用来实现，因而这种线程与内核无关。相应地，内核也并不知道有用户级线程的存在 内核支持线程 依赖于内核，它们的创建、撤销和切换都由内核实现。在内核中保留了一张线程控制块，内核根据该控制块而感知该线程的存在并对线程进行控制,3.4 线程,用户级线程和内核支持线程的比较 线程的调度与切换速度 用户级线程的调度切换速度高于内核支持线程的速度 系统调用 用户级线程的系统调用将看作整个进程的行为，该进程将被阻塞；内核支持线程的系统调用看作该线程的行为，仅仅阻塞该线程 线程执行时间 对于只设置了用户级线程的系统，调度是以进程为单位进行的；设置的内核支持线程的系统，其调度是以线程为单位进行的,