第3章 进程管理(1)

第3章进程管理3.1进程的概念3.2进程的描述3.3进程状态及其转换3.4进程控制3.5进程互斥3.6进程同步3.7进程通信3.8死锁问题3.9线程的概念3.10线程分类与执行3.1进程的基本概念3.1.1程序的顺序执行与并发执行3.1.2进程的定义3.1.3进程的特征3.1.4作业和进程的关系程序的顺序执行程序是一个静态的概念，是严格按次序执行的计算机操作序列的集合，体现了编程人员要求计算机完成相应功能时所应采取的顺序步骤。一个较大的程序通常都是由若干个程序段组成。在程序执行时，必须按照某种先后次序逐个执行，仅当前一操作执行完后，才能执行后继操作。例如：在进行计算时，总是先输入用户的程序和数据，然后才能计算，计算完成后再将结果打印出来。程序的顺序执行程序的顺序执行如图在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响。一道程序执行完后另一道才能开始。程序的顺序执行一个程序的多条语句的顺序执行：程序顺序执行的特点顺序性：一个程序开始执行必须要等到前一个程序已执行完成。封闭性：程序一旦开始执行，其计算结果不受外界因素影响。可再现性：程序的结果与它的执行速度无关（即与时间无关），只要给定相同的输入，一定会得到相同的结果。多道程序系统中程序执行环境的变化计算机能够同时处理多个具有独立功能的程序（批处理系统，分时系统、实时系统、网络与分布式系统）。这样的执行环境具有三个特点：1.独立性:每道程序都是逻辑上独立的，之间不存在制约关系。2.随机性：程序和数据的输入与执行开始时间都是随机的。这种随机性形成了操作系统必须同时处理多道程序的客观要求。3.资源共享–硬件资源：CPU、输入输出设备，存储器–软件资源：各种例行程序、各种共享的数据–多道程序环境下执行程序的道数计算机系统中CPU的个数–单CPU中，则有N－1道程序处在等待CPU的状态–输入输出设备有限将导致这些设备被共享、内存有限将导致内存被共享程序的并发执行所谓程序的并发执行是指：若干个程序同时在系统中执行，这些程序的执行在时间上是重叠的，一个程序的执行尚未结束，另一个程序的执行已经开始。程序的并发执行一个程序的多条语句的并发执行：程序并发执行的特点间断性:“走走停停”，一个程序可能走到中途停下来，失去原有的时序关系失去程序的封闭性:多个程序共享系统中的资源，这些资源的状态将由多个程序来改变。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。不可再现性:失去封闭性ψ失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特征。程序并发执行的特点例：程序A、B，共享变量N，程序A，执行N:=N+1；程序B执行Print(N)，然后将N置0。两个程序以不同速度运行，可能出现三种情况：N:=N+1在Print(N)和N=0之前，此时N值分为N+1,N+1,0N:=N+1在Print(N)和N=0之后，此时N值分为N,0,1N:=N+1在Print(N)和N=0之间，此时N值分为N,N+1,0问题：并发与并行的区别是什么？并行与并发的概念差别并行（Parallel）同一时刻，两个事物均处于活动状态示例：CPU中的超流水线设计和超标量设计并发（Concurrency）宏观上存在并行特征，微观上存在顺序性同一时刻，只有一个事物处于活动状态示例：分时操作系统中多个程序的同时运行并发所带来的效率提升并发所带来的效率提升顺序执行模式下的系统工作效率系统总运行时间：80CPU使用效率：CPU占用时间/总时间＝40/80=50%DEV1使用效率：15/80＝18.75%DEV2使用效率：25/80=31.25%并发执行模式下的系统工作效率系统总运行时间：45CPU使用效率：40/45=89%DEV1使用效率：15/45=33%DEV2使用效率：25＝55.6%并发执行的条件：达到封闭性和可再现性并发执行失去封闭性的原因是共享资源的影响，去掉这种影响就行了。1966年，由Bernstein给出并发执行的条件（这里没有考虑执行速度的影响）:将程序中任一语句Si划分为两个变量的集合R（Si）和W（Si）其中R（Si）＝{a1,a2,……am}是语句Si在执行期间必须对其进行读的变量W（Si）＝{b1,b2,……bn}是语句Si在执行期间必须对其进行修改的变量如果对于语句S1和S2，有①R(S1)∩W(S2)＝{Φ}②W(S1)∩R(S2)＝{Φ}③W(S1)∩W(S2)={Φ}同时成立,则语句S1和S2可并发执行前两条保证一个程序的两次读之间数据不变化；最后一条保证写的结果不丢掉。现在的问题是这个条件不好检查。例：若有两条语句c＝a－b和w＝c＋1，判断它们是否可以并发执行？解：它们的“读集”和“写集”分别为R（c＝a－b）＝{a，b}；R（w＝c＋1）＝{c}W（c＝a－b）＝{c}；W（w＝c＋1）＝{w}R（c＝a－b）∩W（w＝c＋1）={Φ}R（w＝c＋1）∩W（c＝a－b）={c}所以：两条语句不能并发执行。进程的引入并发执行的各程序段由于同时存在于主存中，共享软硬件资源，造成其执行结果受执行速度影响的局面。在多道程序系统所带来的复杂环境中，程序段具有了并发、制约、动态的特性，原来的程序概念，难以刻画系统中的情况。程序本身完全是静态的概念程序概念也反映不了系统中的并发特性为了控制和协调各程序段执行过程中的软硬件资源共享和竞争，必须有一个描述各程序执行过程和共享资源的基本单位。（这个单位被称为进程，或任务task）进程的定义进程的概念是60年代初首先由MIT的MULTICS系统和IBM公司的TSS/360系统引入的。进程有很多各式各样的定义，如：（1）进程是可以并发执行的计算部分（2）进程是一个独立的可以调度的活动（3）进程是一个抽象的实体，当它执行某个任务时，将要分配和释放各种资源（4）行为的规则叫程序，程序在处理机上执行的活动称为进程。（5）一个进程是一系列逐一执行的操作，而操作的确切含义则有赖于以何种详尽程度来描述进程。进程同程序的比较进程同程序的比较程序是指令的有序集合，其本身没有任何运行的含义，是一个静态的概念。而进程是程序在处理机上的一次执行过程，它是一个动态的概念；程序可以作为一种软件资料长期存在，而进程是有一定生命期的。程序是永久的，进程是暂时的；进程同程序的比较进程更能真实地描述并发，而程序不能；进程是由程序和数据、进程控制块三部分组成的；进程具有创建其他进程的功能，而程序没有同一程序同时运行于若干个数据集合上，它将属于若干个不同的进程。也就是说同一程序可以对应多个进程进程的特征结构特征：由程序段、数据段、进程控制块三部分组成；动态性：进程是程序的执行；并发性：多个进程可同存于内存中，能在一段时间内同时运行；独立性：独立运行的基本单位，独立获得资源和调度的基本单位；异步性：各进程按各自独立的不可预知的速度向前推进。作业和进程的关系1.作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业之后，系统将它放入外存中的作业等待队列中等待执行；而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。2.一个作业可由多个进程组成，且必须至少由一个进程组成，反之不然。3.作业的概念主要用在批处理系统中，而进程的概念则用在几乎所有的多道系统中。作业、作业步、进程的关系3.2进程的描述进程的静态描述：由三部分组成,进程控制块、有关程序段和该程序段对其进行操作的数据结构集。1.进程控制块：包含了有关进程的描述信息、控制信息以及资源信息，是进程动态特征的集中反映。2.程序段：是进程中能被进程调度程序选中，并在CPU上执行的程序代码段。3.数据段：一个进程的数据段，可以是进程对应的程序加工处理的原始数据，也可以是程序执行后产生的中间或最终数据。进程控制块为了描述一个进程与其它进程以及系统资源的关系，为了刻画一个进程在各个不同时期所处的状态，人们采用了一个与进程相联系的数据结构，称为进程控制块（PCB）。其作用是将一个不能独立运行的程序变成一个可以独立运行的基本单位，一个能与其他进程并发执行的进程。OS利用PCB来对并发执行的进程进行控制和管理的，PCB是OS感知进程存在的唯一标志。进程与PCB是一一对应的。PCB应常驻内存。PCB的内容进程描述信息：进程标识符(processID)，唯一，通常是一个整数进程名，通常基于可执行文件名（不唯一）用户标识符(userID)：指示该进程由哪个用户拥有进程组（家族）关系：父进程标识符以及子进程标识符PCB的内容进程控制信息：当前状态优先级(priority)进程间同步和通信；阻塞原因程序的外存地址进程的队列指针运行统计信息（执行时间、页面调度）进程的消息队列指针资源管理信息:1.占用内存大小及其管理用数据结构指针2.共享程序段大小及其起始地址。3.输入、输出设备的设备号，所要传送的数据长度、缓冲区地址、缓冲区长度及所用设备的有关数据结构指针等。4.指向文件系统的指针及有关标识。CPU现场保护结构:当前因等待某个事件而进入等待状态或因某种事件发生被终止在处理机上的执行时，为了以后该进程能在被打断处恢复执行，需要保护当前进程的CPU现场。CPU中设有专门的CPU现场保护结构，以存储退出执行时的进程现场数据。PCB表组织方式PCB表：系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表。PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度。链接结构相同状态的进程其PCB组成一个链表，多个状态对应多个不同的链表。就绪链表、阻塞链表索引结构对具有相同状态的进程，分别设置各自的PCB索引表，表明PCB在PCB表中的地址（由index指向PCB）。多个状态对应多个不同的index表：就绪索引表、阻塞索引表索引表在内存的首地址记录在内存中的一些专用单元中。进程上下文是一个与进程切换和处理机状态发生变换有关的概念。包含每个进程执行过的、执行时的以及待执行的指令和数据在指令寄存器、堆栈、状态寄存器等中的内容。已执行过的进程指令和数据在相关寄存器与堆栈中的内容称为上文，正在执行的指令和数据在寄存器与堆栈中的内容称为正文，待执行的指令和数据在寄存器与堆栈中的内容称为下文。不发生进程调度时，进程上下文的改变都是在同一进程内进行的，每条指令的执行对进程上下文的改变较小，反映为指令寄存器、程序计数器以及保存调用子程序返回接口用的堆栈值等的变化。同一进程的上下文的结构由与执行该进程有关的各种寄存器中的值、程序段经过编译后形成的机器指令代码集（正文段）、数据集以及各种堆栈值与PCB结构构成。进程上下文切换进程上下文切换发生在不同进程之间而不是同一个进程内进程上下文切换包含三个部分，涉及三个进程：进程空间任何一个进程，都有自己的地址空间，把该空间称为进程空间或虚空间。进程空间的大小只与处理机的位数有关。程序的执行都在进程空间内进行。用户程序、进程的各种控制表格都按一定的结构排列在进程空间里。在Unix和Linux系统中，进程空间还被划分为用户空间和系统空间两大部分.在进程空间被划分为两大部分后，用户程序在用户空间内执行，操作系统内核程序在进程的系统空间内执行。为了防止用户程序访问系统空间，造成访问出错，计算机系统还通过程序状态寄存器设置不同的执行模式，用户模式和系统模式来进行保护，即用户态和系统态。思考􀂄请说说PCB的作用。􀂄为什么要引入进程的概念？