操作系统第2章进程管理

第二章进程§2.1进程概念§2.2进程的状态§2.3进程控制块§2.4进程控制原语*§2.5进程同步§2.6经典进程同步问题§2.1进程概念一、顺序程序设计1.顺序程序(冯诺伊曼)Vonnevman匈牙利数学家1946年程序是算法的形式化描述，一个程序的执行过程即一个“计算”，即算法的实现。(1)计算:对某一有限数据的集合所施行的，目的在于解决某一问题的一组有限操作的集合。§2.1进程概念(2)顺序执行：I1C1O1I2C2O2job1job2顺序处理模式计算中的各个操作有一定顺序，否则无法正确执行。§2.1进程概念2.顺序程序的特点：(1).顺序性处理机严格按照程序所规定的顺序执行，即每个操作必须在下一个操作开始之前结束。(2).封闭性程序在封闭环境下运行，独占全机资源。封闭性指的是程序一旦开始运行，其计算结果就只取决于程序本身，除了人为地改变机器的运行状态或机器故障以外，没有其它因素能够对程序的运行过程施加影响(3).可再现性程序执行的结果与初始条件有关，而与执行时间无关。即只要程序的初始条件相同，它的执行结果是相同的，不论它在什么时间执行，也不管计算机的运行速度。§2.1进程概念例：(a+b)(c+d)(e/f)t1=a+bt2=c+dt3=e/ft4=t1t2t5=t4–t3–/++abcdSt1t2t3t4t5F二、前趋图§2.1进程概念前趋图是一个有向无循环图，用于描述进程之间的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序或前趋关系。§2.1进程概念每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。Ii→Ci→Pi和S1→S2→S3图2-2前趋图P1P3P8P9P4P2P5P6P7S1S2S3(a)具有九个结点的前趋图(b)具有循环的前趋图§2.1进程概念三、并行程序设计为了提高系统的利用率和处理能力：采用：(1)硬件–––并行操作(2)软件–––程序段在执行时间上有重叠(不一定全部重叠)。并行性：是指在同一时间间隔内或同一时刻完成两种或两种以上性质相同或不同的工作，只要时间上互相重迭，都存在并行性。并发环境：在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的。§2.1进程概念特征：（1）不可再现性同一程序的多次执行，虽然执行环境和初始条件相同，但得到的结果各不相同。并发程序执行的结果与其执行的相对速度有关，是不确定的（2）间断性并发程序之间存在相互制约关系，导致它们都具有“执行-暂停-执行”活动规律。§2.1进程概念（3）资源共享系统中资源被多个进程使用（4）独立性和制约性独立的相对速度、起始时间进程之间可相互作用（相互制约）可分为直接作用和间接作用（5）程序和计算不再对应（计算：一个程序的执行）§2.1进程概念例：2个循环程序A和B，共享变量N。A:while(1)B:while(1){{N=N+1；print(N)；}N=0；}A和B并发执行，其计算结果与执行速度有关，不唯一，有三种情况（假设某时刻N值为n）。§2.1进程概念(1)N=N+1在print(N)和N=0之前即：N=N+1；print(N)；N=0；则N值分别是：n+1,n+1,0(2)N=N+1在print(N)和N=0之后即：print(N)；N=0；N=N+1；N值分别是：n,0,1(3)N=N+1在print(N)和N=0之间即：print(N)；N=N+1；N=0；N值分别是：n,n+1,0§2.1进程概念程序并发执行，失去了封闭性，虽然执行环境和初始条件相同，但其计算结果与并发程序的执行速度有关，从而失去了可再现性，有可能发生“与时间有关的错误”。因而，必须采取某种措施，使得并发程序能够保持其“可再现性”。§2.1进程概念例：在系统中有n个作业，每个作业都有三个处理步骤，输入数据、处理、输出，即Ii,Ci,Oi(i=1,2,3,...,n)。这些作业系统中执行时是对时间的偏序，有些操作必须在其它操作之前执行，这是有序的，但有些操作是可以同时执行的。如:I1、C1、O1的执行必须严格按照I1，C1，O1的顺序，而O1与I2，C1与I2，I3与O1是可以同时执行的。§2.1进程概念I1、C1、O1的执行必须严格按照I1，C1，O1的顺序，而O1与I2，C1与I2,I3与O1是可以同时执行的。I1I2I3C1C2C3O1O2O3t并行的四、进程的引入§2.1进程概念进程的概念是操作系统中最基本、最重要的概念。它是在多道程序系统出现后，为了刻划系统内部出现的情况，描述系统内部各作业的活动规律而引进的一个新的概念。§2.1进程概念为什么要引入“进程”的概念关键是“共享资源”引起的，从资源观点看，有效管理共享资源（同步操作、异步操作、通信）是操作系统的重要内容。在多道程序设计的环境下，为了描述程序在计算机系统内的执行情况，必须引人新的概念－－进程。五、进程的定义§2.1进程概念进程是一个具有一定独立功能的程序关于某个数据集合的一定次可以并发执行的运行活动。进程的概念来自于麻省理工的MULTICS、IBM的TSS/360，在IBM的OS/360/370系统中也曾叫过任务（task)。§2.1进程概念行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为进程（Dijkstra)。进程是这样的计算部分，它是可以和其它计算并行的一个计算。(Donovan)进程（有时称为任务）是一个程序与其数据一道通过处理机的执行所发生的活动。（Alan.C.Shaw)进程是执行中的程序。（KenThompsonandDennisRitchie)教材上给出的进程的定义：P30进程，是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。六、进程同程序的区别与联系§2.1进程概念程序是指令的集合，是静态的概念。进程是程序在处理机上的一次执行的过程，是动态的概念。程序的存在是永久的。程序可以作为软件资料长期保存。进程的存在是暂时的。进程是有生命周期的。“一次运行活动”，诞生(建立)、死亡(撤消)。进程＝程序+数据+PCB(进程控制块，processcontrolblock)，即进程是一个程序及其数据在处理机上顺序地执行时所发生的活动。进程是一个独立的运行单位，能与其它进程并行（并发）活动。而程序则不是。进程是竞争计算机系统有限资源的基本单位，也是进行处理机调度的基本单位。一个程序可以作为多个进程的运行程序，一个进程也可以运行多个程序。§2.1进程概念程序进程唱歌的曲谱或音乐乐器的乐谱演出或演奏剧本演出菜谱烹调实例§2.1进程概念举例做蛋糕程序：食谱数据：原料（鸡蛋、面粉、糖等）CPU：厨师进程：厨师阅读食谱，将原料加工成蛋糕的一系列活动的总和做到一半，他儿子玩耍受伤进来，厨师记录下他照着食谱做到第几步（保存当前进程状态等现场信息）；然后找出急救手册（调进另一道程序），按其指示处理伤情。§2.1进程概念关键思想：一个进程是某种类型的一个活动，它包括程序、输入\输出、状态。单个CPU被多个进程共享。CPU遵循某种调度算法，以决定何时暂停一个进程的工作，并转而为另一个进程提供服务。程序：急救手册CPU：厨师进程：厨师阅读急救手册，实施救治的一系列活动的总和（该进程优先级别高，单CPU）这里CPU从一个进程切换到另一个进程，每个进程都有各自的程序。厨师处理完伤情，又去做蛋糕，是从他离开的那一步继续做下去。七、进程的五个基本特征§2.1进程概念动态性：进程是程序在并发系统内的一次执行，一个进程有一个从产生到消失的生命期；并发性：正是为了描述程序在并发系统内执行的动态特性才引入了进程，没有并发就没有进程；独立性：每个进程的程序都是相对独立的顺序程序，可以按照自己的方向和速度独立地向前推进；制约性：进程之间的相互制约，主要表现在互斥地使用资源和相关进程之间必要的同步和通讯；结构性：进程=PCB+程序+数据集合。§2.1进程概念动态性是进程最基本的特征表现为：由创建而产生，由调度而执行，因得不到资源而暂停执行，由撤消而消亡。有一定的生命期，动态存在。（与程序比较）1、动态性§2.1进程概念并发性是进程的重要特征，也是OS的重要特征。多个进程实体同存于内存中，在一段时间内同时处于运行状态。并发处理的真正含义是：把系统作为一个整体来观察，则在任一时刻有若干进程存在于系统的内部，这些进程都处在其起点和终点之间。我们把所有这些进程都看成是正在系统中运行着。2、并发性§2.1进程概念进程实体是一个能独立运行的基本单位，也是系统中独立获得资源和独立调度的基本单位。没有建立进程的程序，不能作为独立单位参加运行。3、独立性§2.1进程概念进程在系统中按异步方式运行，即进程按各自独立的、不可预知的速度向前推进。该特征导致程序执行的不可再现性。因此，各个进程也就在不可预测的次序中前进。操作系统外部表现出来的不确定性，就是内部动作序列不可预测、不易复现的反应。4、互斥性§2.1进程概念5、结构特征进程实体由程序段、数据段、进程控制块（PCB）三者组成，统称“进程映象”程序：描述了进程所要完成的功能数据集合：程序运行时所需的数据和工作区。程序和数据集合是进程存在的物质基础PCB：包含进程的描述信息和控制信息（是进程动态特性的集中体现）§2.1进程概念(1).进程是一个能独立运行的单位，能与其它进程并行地活动。(2).进程是竞争计算机系统有限资源的基本单位，是一个可调度的实体。也是进行处理机调度的基本单位。进程的特点：§2.1进程概念OS必须交替执行多个进程，以便最大程度的使用CPU，同时提供合理的响应时间OS必须将资源分配给进程，同时避免死锁OS必须支持进程间通信以及用户进程创建OS对进程的要求§2.1进程概念提交一个批处理作业用户登录由OS创建，用以向一用户提供服务(如：打印文件)由已存在的一进程创建一个用户程序可创建成多个进程进程何时创建?§2.1进程概念批处理作业发出暂停（Halt）指令用户退出登录进程执行一中止服务请求出错及失败因素进程何时终止?§2.1进程概念正常结束●给定时限到缺少内存●存储器出界保护性出错例:写只读文件算术错●超出时间进程等待超过对某事件的最大值进程终止原因§2.1进程概念进程终止原因I/O失败无效指令如：试图执行数据特权指令操作系统干预如：当死锁发生时父进程请求终止某一子进程父进程终止，所以子进程也终止进程的状态及变化§2.2进程的状态进程有着“执行－暂停－执行”的活动规律，一般说来一个进程不是自始至终一口气运行到底的。各进程相互制约，当使它暂停的原因消失后，它又可准备运行。因此进程有多种状态。§2.2进程的状态(1)、就绪状态（Ready)存在于处理机调度队列中的那些进程，它们已经准备就绪，一旦得到CPU，就立即可以运行，这些进程所取的状态为就绪状态。（有多个进程处于此状态）(2)、运行状态(Running）当进程由调度/分派程序分派后，得到CPU控制权，它的程序正在运行，该进程所处的状态为运行状态。（在系统中，总只有一个进程处于此状态）(3)、阻塞状态（Blocked)若一个进程正在等待某个事件的发生（如等待I/O的完成），而暂停执行，这时，即使给它CPU时间，它也无法执行，则称该进程处于等待状态。又称为等待(Wait)（挂起、睡眠）状态。1、进程的3种基本状态§2.2进程的状态阻塞（不能占用CPU）就绪（尚未占用CPU）运行（正在占用CPU）资源不足释放资源得到资源时间片到调度选中进入进入完成执行2、进程的状态模型§2.2进程的状态就绪→运行处于就绪状态的进程，当OS的进程调度程序为其分配了CPU，该进程状态就变换成执行状态，占有了CPU。运行→阻塞处于执行状态的进程由于某事件的发生而无法执行（请求I/O、请求页面、要求通讯、程序故障等），则进程状态就变换成阻塞状态。当一进程必须等待时。3、进程的状态转换