《操作系统原理(ch)》由会员分享，可在线阅读，更多相关《操作系统原理(ch)（339页珍藏版）》请在金锄头文库上搜索。
1、操作系统原理操作系统原理张德海张德海 E-mail:2011年年3月月7日日云南大学软件学院2023/8/311第三章第三章 进程管理进程管理3.1 3.1 进程的概念进程的概念 3.2 3.2 进程的描述进程的描述 3.3 3.3 进程状态及其转换进程状态及其转换 3.4 3.4 进程控制进程控制 3.5 3.5 进程互斥进程互斥 3.6 3.6 进程同步进程同步 3.7 3.7 进程通信进程通信 3.8 3.8 死锁问题死锁问题 3.9 3.9 线程线程2023/8/3123.1 进程的概念现代操作系统的特点：现代操作系统的特点：程序的并发性程序的并发性系统资源共享系统资源共享用户操作的随
2、机性用户操作的随机性2023/8/3133.1 进程的概念问题：操作系统在多用户随机使用的环境问题：操作系统在多用户随机使用的环境下进行资源分配、资源共享和控制程序并下进行资源分配、资源共享和控制程序并发执行的基本单位是什么？发执行的基本单位是什么？进程刚好是这样一个基本单位进程刚好是这样一个基本单位2023/8/3143.1.1 程序的并发执行程序的执行有两种方式：程序的执行有两种方式：顺序执行顺序执行和和并发执行并发执行。顺序执行是单道批处理系统的执行方式，也用于简顺序执行是单道批处理系统的执行方式，也用于简单的单片机系统；单的单片机系统；Repeat IR Repeat IR MpcMp
3、c pc pc+1 pc pc+1 Until CPU haltUntil CPU halt现在的操作系统多为并发执行，具有许多新的特征。现在的操作系统多为并发执行，具有许多新的特征。引入并发执行的目的是为了提高资源利用率。引入并发执行的目的是为了提高资源利用率。2023/8/315顺序执行的特征顺序执行的特征顺序性：顺序性：按照程序结构所指定的次序（可能有按照程序结构所指定的次序（可能有分支或循环）分支或循环）封闭性：封闭性：独占全部资源，计算机的状态只由于独占全部资源，计算机的状态只由于该程序的控制逻辑所决定该程序的控制逻辑所决定可再现性：可再现性：初始条件相同则结果相同。如：可初始条件相
4、同则结果相同。如：可通过空指令控制时间关系。通过空指令控制时间关系。3.1.1 程序的并发执行2023/8/316多道程序执行环境的特点：多道程序执行环境的特点：独立性：独立性：在多道环境下执行的每道程序逻辑上在多道环境下执行的每道程序逻辑上是独立的；是独立的；随机性随机性：多道环境下，程序和数据的输入与执：多道环境下，程序和数据的输入与执行的开始时间都是随机的；行的开始时间都是随机的；资源共享资源共享：多道程序共享：多道程序共享硬件硬件和和软件软件资源。硬资源。硬件资源包括件资源包括CPU、I/O设备、存储器设备、存储器等；软件等；软件资源包括资源包括例程、可共享的数据例程、可共享的数据等。
5、等。3.1.1 程序的并发执行2023/8/3173.1.1 程序的并发执行程序的并发执行：一组在逻辑上互相独立的程序或程序的并发执行：一组在逻辑上互相独立的程序或程序的并发执行：一组在逻辑上互相独立的程序或程序的并发执行：一组在逻辑上互相独立的程序或程序段在执行过程中，其执行时间在客观上互相重程序段在执行过程中，其执行时间在客观上互相重程序段在执行过程中，其执行时间在客观上互相重程序段在执行过程中，其执行时间在客观上互相重叠，即一个程序段的执行尚未结束，另一个程序段叠，即一个程序段的执行尚未结束，另一个程序段叠，即一个程序段的执行尚未结束，另一个程序段叠，即一个程序段的执行尚未结束，另一个程
6、序段的执行已经开始的这种执行方式。的执行已经开始的这种执行方式。的执行已经开始的这种执行方式。的执行已经开始的这种执行方式。2023/8/318程序并发执行的描述程序并发执行的描述 cobegin P1;P2;P3;.;PN coend;Pi(i=1,2,3,.,n)表示表示n个语句（程序段），个语句（程序段），这这n个语句用个语句用cobegin和和coend括起来表示括起来表示这这n个语句是可以并发执行的。个语句是可以并发执行的。co是是concurrent的头两个字符。的头两个字符。这是这是Dijkstra提出的提出的。3.1.1 程序的并发执行2023/8/319假设有一个程序由假设有
7、一个程序由假设有一个程序由假设有一个程序由S0-Sn+1S0-Sn+1个语句，其中个语句，其中个语句，其中个语句，其中 S1-SnS1-Sn语句是并发执行语句是并发执行语句是并发执行语句是并发执行的，程序如下：的，程序如下：的，程序如下：的，程序如下：S0;S0;cobegin cobegin S1;S2;S3;.;SN S1;S2;S3;.;SN coend;coend;Sn+1;Sn+1;3.1.1 程序的并发执行2023/8/3110并发执行带来的问题：并发执行带来的问题：间断间断(异步异步)性：性：走走停停走走停停，一个程序可能走一个程序可能走到中途停下来，失去原有的时序关系；到中途停
8、下来，失去原有的时序关系；失去封闭性：失去封闭性：共享资源，受其他程序的控制逻共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。可能被另一个程序修改，失去原有的不变特征。失去可再现性：失去可再现性：失去封闭性失去封闭性 失去可再现性；失去可再现性；外界环境在程序的两次执行期间发生变化，失外界环境在程序的两次执行期间发生变化，失去原有的可重复特征。去原有的可重复特征。3.1.1 程序的并发执行2023/8/3111程程序序 P(i)针针对对共共享享变变量量的的读读集集和和写写集集 R(i)和和W(
9、i)条件：任意两个程序条件：任意两个程序P(i)和和P(j)，有：，有：R(i)W(j)=;W(i)R(j)=;W(i)W(j)=;并发执行的条件：达到封闭性和可再现性并发执行的条件：达到封闭性和可再现性并发执行的条件：达到封闭性和可再现性并发执行的条件：达到封闭性和可再现性并发执行失去封闭性的原因是共享资源的影响，去掉这种影响并发执行失去封闭性的原因是共享资源的影响，去掉这种影响就行了。就行了。1966年，由年，由Bernstein给出并发执行的条件。给出并发执行的条件。（这里没（这里没有考虑执行速度的影响。）有考虑执行速度的影响。）前两条保证一个程序的两次读之间数据不变化；最后一条保证写的
10、结果不丢掉。现在的问题是这个条件不好检查。现在的问题是这个条件不好检查。2023/8/3112举例：栈的读、写程序段并发执行举例：栈的读、写程序段并发执行Procedure getaddr(top)Procedure getaddr(top)begin begin local r local r r (top)r (top)top top-1 top top-1 return(r)return(r)end endProcedure reladdr(blk)begin top top+1 (top)blk end2023/8/3113读、写并发可能导致错误：读、写并发可能导致错误：a ab be
11、 ef fTop(a)a ab be ef fTop(b)(Reladdr()执行语句：top top+1后)a ab be ef fTop(c)geladdr()取数据失败2023/8/31143.1.2 进程的定义进程的定义在多道程序设计的环境下，为了描述程序在多道程序设计的环境下，为了描述程序在计算机系统内的执行情况，必须引入新在计算机系统内的执行情况，必须引入新的概念进程。的概念进程。进程的概念来自于麻省理工的进程的概念来自于麻省理工的MULTICS、IBM的的 TSS/360，在，在IBM的的OS/360/370系系统中也曾叫过任务（统中也曾叫过任务（task)。2023/8/311
12、5 进程是可以并行执行的计算部分进程是可以并行执行的计算部分进程是可以并行执行的计算部分进程是可以并行执行的计算部分(Madnick,Donovan)(Madnick,Donovan)进程是一个独立的可以调度的活动（进程是一个独立的可以调度的活动（进程是一个独立的可以调度的活动（进程是一个独立的可以调度的活动（Cohen,JoffersonCohen,Jofferson）进程（有时称为任务）是一个程序与其数据一道通过处理进程（有时称为任务）是一个程序与其数据一道通过处理进程（有时称为任务）是一个程序与其数据一道通过处理进程（有时称为任务）是一个程序与其数据一道通过处理机的执行所发生的活动。（机
13、的执行所发生的活动。（机的执行所发生的活动。（机的执行所发生的活动。（Alan.C.Shaw)Alan.C.Shaw)进程是执行中的程序。（进程是执行中的程序。（进程是执行中的程序。（进程是执行中的程序。（Ken Thompson and Dennis Ken Thompson and Dennis Ritchie)Ritchie)行为的一个规则叫做程序，程序在处理机上执行时所发生行为的一个规则叫做程序，程序在处理机上执行时所发生行为的一个规则叫做程序，程序在处理机上执行时所发生行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为进程（的活动称为进程（的活动称为进程（的活动称为进程（D
14、ijkstra)Dijkstra)。教材上给出的进程的定义：教材上给出的进程的定义：教材上给出的进程的定义：教材上给出的进程的定义：进程，即是一个具有一定独立功能的程序对某个数据集进程，即是一个具有一定独立功能的程序对某个数据集进程，即是一个具有一定独立功能的程序对某个数据集进程，即是一个具有一定独立功能的程序对某个数据集合在处理机上的执行过程和分配资源的基本单位。合在处理机上的执行过程和分配资源的基本单位。合在处理机上的执行过程和分配资源的基本单位。合在处理机上的执行过程和分配资源的基本单位。3.1.2 进程的定义进程的定义2023/8/3116 进程与程序的区别进程与程序的区别进程是动态的
15、，程序是静态的进程是动态的，程序是静态的进程是动态的，程序是静态的进程是动态的，程序是静态的：程序是有序代码：程序是有序代码：程序是有序代码：程序是有序代码的集合；进程是程序的执行。程序可以作为软件的集合；进程是程序的执行。程序可以作为软件的集合；进程是程序的执行。程序可以作为软件的集合；进程是程序的执行。程序可以作为软件资料长期保存，而进程是有生命周期的。资料长期保存，而进程是有生命周期的。资料长期保存，而进程是有生命周期的。资料长期保存，而进程是有生命周期的。如果把程序比作菜谱，那么进程则是按照菜如果把程序比作菜谱，那么进程则是按照菜如果把程序比作菜谱，那么进程则是按照菜如果把程序比作菜谱
16、，那么进程则是按照菜谱炒菜的过程谱炒菜的过程谱炒菜的过程谱炒菜的过程进程具有并行特征，而程序没有进程具有并行特征，而程序没有进程具有并行特征，而程序没有进程具有并行特征，而程序没有：程序不反映执：程序不反映执：程序不反映执：程序不反映执行过程，所以不具有并行特征。行过程，所以不具有并行特征。行过程，所以不具有并行特征。行过程，所以不具有并行特征。进程是竞争系统资源的基本单位进程是竞争系统资源的基本单位进程是竞争系统资源的基本单位进程是竞争系统资源的基本单位；进程与程序的对应关系进程与程序的对应关系进程与程序的对应关系进程与程序的对应关系：通过多次执行，一个程：通过多次执行，一个程：通过多次执行，一个程：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可序可对应多个进程；通过调用关系，一个进程可序可对应多个进程；通过调用关系，一个进程可序可对应多个进程；通过调用关系，一个进程可包括多个程序。包括多个程序。包括多个程序。包括多个程序。2023/8/31173.2 进程的描述进程的描述进程的静态描述：进程的静态描述：进程控制块进程控制块PCB：进程控制块包含了进程的描述信息、控制
