21第二章 进程管理

2020/2/25第二章进程管理1第二章进程管理2.1进程的基本概念2.2进程控制2.3进程同步2.4经典进程的同步问题2.5管程机制2.6进程通信2.7线程2020/2/25第二章进程管理22.1进程的基本概念2.1.1前趋图2.1.2程序的顺序执行及其特征2.1.3程序的并发执行及其特征2.1.4进程的特征与状态2.1.5进程控制块2020/2/25第二章进程管理3前驱图(PrecedenceGraph)前驱图是一个有向无循环图，图中的每个结点可用于表示一条语句，一个程序段或进程；结点间的有向边则表示在两结点之间存在的偏序或前驱关系。P1P2P3P4P5P6P7P8P9结点、有向边、直接前驱、直接后继、初始结点、终止结点无循环关系，可实现顺序执行2020/2/25第二章进程管理4程序的顺序执行程序是一个静态的概念，是严格按次序执行的计算机操作序列的集合，体现了编程人员要求计算机完成相应功能时所应采取的顺序步骤。一个较大的程序通常都是由若干个程序段组成。在程序执行时，必须按照某种先后次序逐个执行，仅当前一操作执行完后，才能执行后继操作。例如：在进行计算时，总是先输入用户的程序和数据，然后才能计算，计算完成后再将结果打印出来。2020/2/25第二章进程管理5程序的顺序执行如图I1P1O1I2P2O2作业1作业2在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响。一道程序执行完后另一道才能开始。程序的顺序执行2020/2/25第二章进程管理6程序的顺序执行一个程序的多条语句的顺序执行：S1:a:=x+yS2:b:=a-5S3:c:=b+1S1S2S32020/2/25第二章进程管理7程序顺序执行的特点顺序性：一个程序开始执行必须要等到前一个程序已执行完成。封闭性：程序一旦开始执行，其计算结果不受外界因素影响。可再现性：程序的结果与它的执行速度无关（即与时间无关），只要给定相同的输入，一定会得到相同的结果。2020/2/25第二章进程管理8多道程序系统中程序执行环境的变化计算机能够同时处理多个具有独立功能的程序（批处理系统，分时系统、实时系统、网络与分布式系统）。这样的执行环境具有三个特点：独立性:每道程序都是逻辑上独立的，之间不存在制约关系。随机性：程序和数据的输入与开始执行时间都是随机的。这种随机性形成了操作系统必须同时处理多道程序的客观要求。资源共享硬件资源：CPU、输入输出设备，存储器软件资源：各种例行程序、各种共享的数据多道程序环境下执行程序的道数计算机系统中CPU的个数单CPU中，则有N－1道程序处在等待CPU的状态输入输出设备有限将导致这些设备被共享、内存有限将导致内存被共享2020/2/25第二章进程管理9程序的并发执行I1P1O1I2P2O2I3P3O3所谓程序的并发执行是指：若干个程序同时在系统中执行，这些程序的执行在时间上是重叠的，一个程序的执行尚未结束，另一个程序的执行已经开始。2020/2/25第二章进程管理10程序的并发执行一个程序的多条语句的并发执行：S1:a:=x+2S2:b:=y+5S3:c:=a+bS4:d:=c+6S1S3S4S22020/2/25第二章进程管理11程序并发执行的特点间断性“走走停停”，一个程序可能走到中途停下来，失去原有的时序关系失去程序的封闭性多个程序共享系统中的资源，这些资源的状态将由多个程序来改变。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。不可再现性失去封闭性→失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特征。2020/2/25第二章进程管理12abefabeftopabeftop例：设有堆栈S，栈指针top，栈中存放内存中相应数据块地址，设有两个程序段getaddr（top）和reladdr（blk），其中getaddr（top）从给定的top所指栈中取出相应的内存数据块地址，而reladdr（blk）则将内存数据块地址blk放入堆栈S中。Getaddr接着执行Reladdr先执行top执行top=top＋1后中断2020/2/25第二章进程管理13程序并发执行的特点例：程序A、B，共享变量N，程序A，只有一个语句N:=N+1；程序B由两个语句Print(N)，N=0组成。两个程序以不同速度运行，可能出现三种情况：N:=N+1在Print(N)和N=0之前，此时N值分为N+1,N+1,0N:=N+1在Print(N)和N=0之后，此时N值分为N,0,1N:=N+1在Print(N)和N=0之间，此时N值分为N,N+1,0问题：并发与并行的区别是什么？2020/2/25第二章进程管理14并行与并发的概念差别并行（Parallel）同一时刻，两个事物均处于活动状态并发（Concurrency）宏观上存在并行特征，微观上存在顺序性同一时刻，只有一个事物处于活动状态2020/2/25第二章进程管理15并发所带来的效率提升2020/2/25第二章进程管理16并发所带来的效率提升顺序执行模式下的系统工作效率系统总运行时间：80CPU使用效率：CPU占用时间/总时间＝40/80=50%DEV1使用效率：15/80＝18.75%DEV2使用效率：25/80=31.25%并发执行模式下的系统工作效率系统总运行时间：45CPU使用效率：40/45=89%DEV1使用效率：15/45=33%DEV2使用效率：25/45＝55.6%2020/2/25第二章进程管理17进程的引入并发执行的各程序段由于同时存在于主存中，共享软硬件资源，造成其执行结果受执行速度影响的局面。在多道程序系统所带来的复杂环境中，程序段具有了并发、制约、动态的特性，原来的程序概念，难以刻画系统中的情况。程序本身完全是静态的概念程序概念也反映不了系统中的并发特性为了控制和协调各程序段执行过程中的软硬件资源共享和竞争，必须有一个描述各程序执行过程和共享资源的基本单位。（这个单位被称为进程，或任务task）2020/2/25第二章进程管理18进程的定义进程是可并发执行的程序在一个数据集合上的运行过程。或是指进程实体的运行过程。2020/2/25第二章进程管理19主妇阅读菜谱准备原料烹制菜肴饭菜阅读洗衣机手册准备衣服、洗衣粉设定参数，洗衣服干净衣服程序输入运行输出程序输入运行输出分时切换洗衣进程做饭进程进程同程序的比较2020/2/25第二章进程管理20进程同程序的比较程序是指令的有序集合，其本身没有任何运行的含义，是一个静态的概念。而进程是程序在处理机上的一次执行过程，它是一个动态的概念；程序可以作为一种软件资料长期存在，而进程是有一定生命期的。程序是永久的，进程是暂时的；2020/2/25第二章进程管理21进程同程序的比较进程更能真实地描述并发，而程序不能；进程是由程序和数据、进程控制块三部分组成的；进程具有创建其他进程的功能，而程序没有同一程序同时运行于若干个数据集合上，它将属于若干个不同的进程。也就是说同一程序可以对应多个进程2020/2/25第二章进程管理22进程的特征结构特征：由程序段、数据段、进程控制块三部分组成；动态性：进程是程序的执行；并发性：多个进程可同存于内存中，能在一段时间内同时运行；2020/2/25第二章进程管理23进程的特征独立性：独立运行的基本单位，独立获得资源和调度的基本单位；异步性：各进程按各自独立的不可预知的速度向前推进。2020/2/25第二章进程管理24进程的状态及其转换不同系统设置的进程状态数目不同进程有三种基本状态：进程在生命期内，至少具有三种基本状态：执行状态、等待状态和就绪状态。2020/2/25第二章进程管理25进程的三种基本状态就绪状态（Ready）：已经得到除CPU之外的其他资源的那些进程，它们已经准备就绪，一旦得到CPU，就立即可以运行。这些进程所处的状态为就绪状态。就绪队列：常按照进程优先权的大小排列，把优先权高的进程的PCB排在队列前面。2020/2/25第二章进程管理26进程的三种基本状态运行状态（Running）：正在运行的进程所处的状态为运行状态。单处理机系统，任一时刻只有一个进程处于运行状态多处理机系统有多个进程处于运行状态只有处于就绪状态的进程经调度选中之后才可进入执行状态2020/2/25第二章进程管理27进程的三种基本状态等待状态（Wait/Blocked）：若一进程正在等待某一事件发生（如等待输入输出工作完成），这时，即使给它CPU，它也无法运行，称该进程处于等待状态、阻塞、睡眠、封锁状态。阻塞队列根据阻塞原因可以设置多个队列。2020/2/25第二章进程管理28进程的状态变迁图2020/2/25第二章进程管理29进程的状态转换①就绪→执行：调度②执行→等待：等待某个事件发生而睡眠③等待→就绪：因等待的事件发生而唤醒④执行→就绪：时间片用完问题1：为什么不能从等待态变为运行态呢？问题2：为什么不能从就绪态变为等待态呢？答案：阻塞进程即使被给予CPU，也无法运行。理论上这种状态转换是可行的，只是没有实际价值而被操作系统禁止对于就绪状态的进程，因没有执行，自然无法进入到阻塞状态。这种状态转换理论上不可行2020/2/25第二章进程管理30五状态进程模型增加了“创建”、“终止”两种状态创建状态(New)：创建一个进程要通过两个步骤：首先，为一个新进程创建PCB，并填写必要的管理信息；其次，把该进程转入就绪状态并插入就绪队列中。当一个新进程被创建时，系统已为其分配了PCB，填写了进程标识等信息，但由于该进程所必需的资源或其他信息没有获得，进程自身还未进入主存，即创建工作尚未完成，进程还不能被调度运行。引入创建状态，是为了保证进程的调度必须在创建工作完成后进行，以确保对PCB操作的完整性。同时，也增加了管理的灵活性，操作系统可以根据系统性能或主存容量的限制，推迟创建状态进程的提交。对于处于创建状态的进程，获得了其所必需的资源，以及对其PCB初始化工作完成后，进程状态便可由创建状态转入就绪状态了。2020/2/25第二章进程管理31结束状态(Exit)：进程的结束也要通过两个步骤：首先等待操作系统进行善后处理，然后将其PCB清零，并将PCB空间返还系统。当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，它将进入结束状态。进入结束状态的进程以后不能再执行，但在操作系统中依然保留一个纪录，其中保存状态码和一些计时统计数据，供其他进程收集。一旦其他进程完成了对结束状态进程的信息提取之后，操作系统将删除该进程。对于一个进程来说“创建状态”和“结束状态”只有一次。五状态进程模型2020/2/25第二章进程管理32五状态进程模型2020/2/25第二章进程管理33五状态进程模型创建新进程：创建一个新进程，以运行一个程序。可能的原因为：用户登录、OS创建以提供某项服务、批处理作业。收容(Admit,也称为提交)：收容一个新进程，进入就绪状态。由于性能、内存、进程总数等原因，系统会限制并发进程总数。释放(Release)：由于进程完成或失败而终止进程运行，进入结束状态；运行到结束：分为正常退出Exit和异常退出abort（执行超时或内存不够，非法指令或地址，I/O失败，被其他进程所终止）2020/2/25第二章进程管理34五状态进程模型注：对于五状态进程模型，一个重要的问题是当一个事件出现时如何检查阻塞进程表中的进程状态。当进程多时，对系统性能影响很大。一种可能的作法是按等待事件类型，排成多个队列。2020/2/25第二章进程管理35AdmitReadyQueueDispatchTime-outEventWaitReleaseProcessorBlockedQueueEventOccurs五状态进程模型(单队列结构)2020/2/25第二章进程管理36AdmitRe