操作系统,第二章 进程管理 P34,2.1 进程(PROCESS) 2.2 线程(THREAD) 2.3 进程互斥和同步 2.4 死锁问题(DEADLOCK) 2.5 处理机调度,操作系统,2.1 进程(PROCESS),2.1.1 前趋图(Procedence Graph, PG) PG是一个有向无环图(DAG图)，图中结点表示一条语 句，一个程序段或进程，结点间的有向边表示两结点之间存在的偏序(Partial Order)关系或前趋关系(Precedence Relation),P35,表示P1P2，P1 must complete before P2 may start,前趋图不存在循环。,操作系统,1. 顺序执行 按先后顺序依次执行程序中各条语句的操作 程序在执行时，必须按照先后次序逐个执行每一个程序段，仅当前一操作执行完后，才能执行后继操作。 是单道批处理系统的执行方式；,程序的两种执行方式（顺序执行，并发执行）,2.1.2 程序的顺序执行及其特征,操作系统,按先后顺序依次执行程序中各条语句的操作,例 三条语句的程序段：,S1: a=x+y;,S2: b=a-5;,S3: c=b+1;,三条语句顺序执行时的前趋图：,操作系统,CPU执行程序过程的描述：,Repeat IR M pc pc pc + 1 Until CPU halt 其中： IR：指令寄存器 pc：程序计数器 M：存储器,操作系统,2. 程序顺序执行时的特征,按顺序执行各操作; 程序运行时独占全机资源， 各资源状态只有本程序才能改变; 只要程序执行环境和初始条件相同，无论以何种方式(连续/走停)运行其结果相同;,顺序性,封闭性,可再现性,操作系统,2.1.3 程序的并发执行及其特征,并发执行是一组逻辑上互相独立的程序或程序段在执行过程中其执行时间在客观上互相重叠，即一个程序段的执行尚未结束，另一个程序段的执行已经开始。 现在的操作系统多为并发执行，具有许多新的特征。引入并发执行的目的是为了提高资源利用率。,1.并发执行,操作系统,2.1.3 程序的并发执行及其特征,1.并发执行,S1: a=x+2;,S2: b=y+4;,S3: c=a+b;,S4: d=c+b;,多个程序在执行时间上是重叠的(同一时间段内多个 程序运行),4条语句的前趋关系由前趋图描述：,例 四条语句的程序段：,操作系统,并发执行过程描述,S0 Cobegin P1;P2;Pn Coend Sn,操作系统,在顺序环境下: CPU利用率= 40/80 = 50% DEV1利用率= 15/80=18.75% DEV2利用率= 25/80=31.25%,例:,在并发环境下 : CPU利用率=40/45=89% DEV1并发环境下利用率=15/45= 33% DEV2并发环境下利用率=25/45= 56%,操作系统,2. 程序并发执行时的特征,“走走停停”，一个程序可能走到中途停下来，失去原有的时序关系；,间断(异步)性,失去封闭性,失去可再现性,共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征;,外界环境在程序的两次执行期间发生变化，失去原有的可重复特征。,操作系统,例如：两个循环程序A 和B, 共享一个变量N。 程序A每执行一次时，都要执行N:=N+1； 程序B每执行一次时，都要执行print(N)操作，然后再将N置成“0”。 程序A和B以不同的速度运行。这样，会出现以下三种情况：,举例说明不可再现性,A： N:=N+1,B(1): Print(N),B(2): N:=0,A：N:=N+1,A :N:=N+1,执行的环境和初始条件相同，得到的结果各不相同,B(1): Print(N),B(1): Print(N),B(2): N:=0,B(2): N:=0,操作系统,3、多道程序并发,可见，实现多道程序并发是有条件的，并发执行需要考虑很多因素：,如何对CPU进行调度，保证每个用户相对公平地得到CPU （CPU是一个只可调度，不可分配的资源） 如何管理其他资源 当各用户对资源使用上发生冲突时，如何处理竞争 对CPU只能通过调度来解决竞争问题，而对于其他资源通过申请分配使用回收的办法进行管理。 在并发程序之间如何正确传递消息（通信）,最终是一个资源共享问题,操作系统,2.1.4 进程,引入进程:来描述程序执行时的动态特征,从而解决程序在并发执行时对系统资源的共享问题.,1.定义：Process P38 a process is a program in execution.,进程是程序的一次执行过程 进程是一个程序及其数据在处理机上顺序执行所发生的活动 进程是程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位 ,操作系统,2.1.4 进程 operating system concepts一书,A process is more than the program code (sometimes known as the text section). It also includes the current activity, as represented by the value of the program counter and the contents of the processors registers. A process generally also includes the process stack, which contains temporary data (such as subroutine parameters, return addresses, and temporary variables), and a data section containing global variables. and also include a heap, which is memory that is dynamically allocated during process run time.,进程包括程序段、数据段和一个称为进程控制块（PCB）的数据结构,操作系统,进程控制块的内容,Information associated with each process： Process Identify (PID) 进程标识符 Process state 进程状态 Program counter 程序计数器 CPU registers CPU寄存器 CPU scheduling information CPU调度信息 Memory-management information 内存管理信息 Accounting information 计账信息 I/O status information I/O状态信息,进程由程序、数据、进程控制块三部分组成！,操作系统,2.进程控制块 (PCB, process control block)2,进程控制块是由OS维护的用来记录进程相关信息的一块内存。 它是进程实体的一部分,是OS感知进程存在的唯一依据，是操作系统中最重要的记录型数据结构。,创建一进程时，应首先创建其PCB，然后才能根据PCB中信息对进程实施有效的管理和控制，当一个进程完成其功能之后，系统则释放PCB，进程也随之消亡。 处于核心段，通常不能由应用程序自身的代码来直接访问，而要通过系统调用，或OS来访问,操作系统,3.进程的特征,结构特征：从结构上说，进程包括程序段、数据段和一个称为进程控制块（PCB）的数据结构（用以对并发执行的程序加以控制和描述） 动态性：进程具有动态的地址空间 并发性：指多个进程实体，同存于内存中，能在同一段时间内同时运行。 独立性：各进程的地址空间相互独立，除非采用进程间通信手段；也是系统中独立获得资源、独立调度的基本单位。 异步性：进程按各自独立、不可预知的速度向前推进。,操作系统,进程与程序的区别,进程是主动的（active）、动态的，程序是被动的（passive） 、静态的：程序是指令的有序集合，没有任何执行的含义。而进程则强调执行过程，它动态地创建，并被调度执行后消亡。 进程是暂时的，程序是永久的：进程是一个状态变化的过程，程序可长久保存。 进程与程序的组成不同：进程的组成包括程序。 进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。,操作系统,begin - - - - - - end,C compiler,Process 1 (data section),Source code1,Object code1,Process 2 (data section),Source code2,Object code2,stack1,stack2,一个程序对应两个进程例,操作系统,Main( ) - - open( ) - -,Open( ) - - - - return,System call,Process1(user mode),User stack,Process1 (monitor mode),Kernel stack,一个进程对应多个程序例,操作系统,4.进程的状态转换 P38,进程并非一直处于执行状态，它有“执行暂停执行”的活动规律。 进程的生命周期可以划分为一组状态。,操作系统,3个进程A、B和C在内存中，假设没有使用虚存。,进程轨迹（trace）举例：,进程在内存中的存储情况：,有一个小的分派程序 （dispatcher）使处理器从一个进程切换到另一个进程。,操作系统,进程单独执行时的轨迹：,操作系统,进程A、B和C的联合轨迹：,1 5000 2 5001 3 5002 4 5003 5 5004 6 5005 -超时 7 100 8 101 9 102 10 103 11 104 12 105 13 8000 14 8001 15 8002 16 8003 -I/O请求 17 100 18 101,37 5008 38 5009 39 5010 40 5011 -超时 41 100 42 101 43 102 44 103 45 104 46 105 47 12006 48 12007 49 12008 50 12009 51 12010 52 12011 -超时,19 102 20 103 21 104 22 105 23 12000 24 12001 25 12002 26 12003 27 12004 28 12005 -超时 29 100 30 101 31 102 32 103 33 104 34 105 35 5006 36 5007,A,A,B,C,C,A,操作系统,（1）五种基本的进程状态,就绪态（Ready）：进程已获得除CPU以外的其他资源。,执行态（Run）：进程获得CPU正在运行的状态。,阻塞态（waiting）：进程因等待某事件而暂时不能运行的状态,新建状态（new）：进程刚刚被创建。,终止状态（Terminated）：进程的执行刚刚结束，还未撤消。,操作系统,（2）进程状态的转换,新进程,就绪,执行,结束,阻塞,接纳,进程调度,中断或 时间片用完,完成,I/O请求或 等待某事件,I/O完成或 事件发生,操作系统,操作系