2进程描述与控制(4学时)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第2章 进程描述与控制,2.1 进程的引入,2.2 进程的定义,2.3 进程的描述,2.4 进程控制,2.5 线程,为了描述程序在并发执行时对系统资源的共享，我们需要一个,描述程序执行时动态特征,的概念，这就是,进程,。,1,2.1 进程的引入,2.1.1 程序的顺序执行,2.1.2 程序的并发执行,2.1.3 程序并发执行的条件,返回,2,2.1.1 程序的顺序执行,程序的执行有两种方式：顺序执行和并发执行,。,顺序执行,是,单道,批处理系统的执行方式，也用于,简单的单片机,系统；,现在的操作系统多为,并发执行,，具有许多新的特征。引入并发执行的目的是为了提高,资源利用率,。,3,程序的顺序执行,：具有独立功能的程序,独占,CPU,直至得到最终结果的过程。,视频,1、程序的顺序执行定义,4,2、顺序执行的特征,顺序性,：按照程序结构所指定的次序（可能有分支或循环）,封闭性,：独占全部资源，计算机的状态只由于该程序的控制逻辑所决定,可再现性,：初始条件相同则结果相同。如：可通过空指令控制时间关系。,5,2.1.2 程序的并发执行,1、程序并发执行的目的,：,提高计算机的处理能力,提高资源利用率,2、分为两种形式,：,多道程序环境下的多道程序的并发执行,在某道程序的几个程序段中，包含可同时执行或可颠倒顺序执行的代码。,3、定义,：程序的并发执行是指一组在逻辑上互相独立的程序或程序段在执行时间上客观上互相重叠，即一个程序或程序段的执行尚未结束，另一个程序（段）的执行已经开始的执行方式。,视频,6,程序的并发执行,并发,：在一段时间内的同时并行,并行,：在同一物理时刻的同时,用户程序,监督程序,磁盘设备,磁带设备,用户程序A,用户程序B,监督程序,磁盘设备,磁带设备,时间t,CPU,外设,CPU,外设,请求带输入,启动带,磁带输入,结束中断,中断处理,请求磁盘输入,启动盘,结束中断,中断处理,请求盘输入,启动盘，调度B,请求带输入,启动带,结束中断,中断处理,调度A,结束中断,中断处理,调度B,7,4、并发执行的特征,间断(异步)性,：走走停停，一个程序可能走到中途停下来，失去原有的时序关系；,失去封闭性,：共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。,失去可再现性,：失去封闭性 失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特征。,8,5、不加控制的并发执行所带来的影响,例：两个循环程序A和B它们共享变量N。程序A每执行一次，都要做N:=N+1操作；程序B每执行一次，都要执行Print(N)操作，然后将N置0。程序A和B以不同的速度运行。这样可能出现三种情况（假定某时刻变量N 的值为 n),（1）,N:=N+1在Print(N)和N=0之前执行，此时得到的N值为n+1,n+1,0;,（2） N:=N+1在Print(N)和N=0之后执行，此时得到的N值为n,0,1;,（3） N:=N+1在Print(N)和N=0之间执行，此时得到的N值为n,n+1,0;,9,例的说明,程序A和B的并发执行，产生了错误的结果，不同执行顺序得到不同的结果，程序的执行不再具有封闭性和结果的可再现性。,原因,：对公共变量N的共享引起的。,为了获得结果的可再现性，程序的并发执行是需要条件的。,10,2.1.3 程序并发执行的条件,程序 P(i) 针对的,读变量,集和,写变量,集 为,R(i),和,W(i),R(Pi)=a,1,a,2,a,m,：,表示程序在执行期间所需参考的变量的集合,W(Pi)=b,1,b,2,b,m,：,表示程序在执行期间所需改变的变量的集合,例如：语句c:=a-b，则R(c:=a-b)=a,b,W(c:=a-b)=c,并发执行失去封闭性的原因是共享资源的影响，去掉这种影响就行了。,1966年，由Bernstein给出并发执行的条件,。（这里没有考虑执行速度的影响。）,11,程序 P(i) 针对的,读变量,集和,写变量,集 为,R(i),和,W(i),任意两个程序P(i)和P(j)可并发的条件：,R(i),W(j)=,，and,W(i),R(j)=, and,W(i),W(j)=,前两条保证一个程序的两次读之间数据不变化；最后一条保证写的结果不丢掉。,现在的问题是这个条件不好检查。,12,例如：有四条语句,s1: a:=x+y,，,s2: b:=z+1,，,s3: c:=a-b, s4:w:=c+1,，,则,它们的读集和写集分别为：,R(s1)=x,y, R(s2)=z, R(s3)=a,b, R(s4)=c,W(s1)=a, W(s2)=b, W(s3)=c, W(s4)=w,由上可见：,s1,和,s2,可并发执行,s1,和,s3,不能并发执行，因为,R(s3)W(s1)=a,s2,和,s3,不能并发执行，因为,R(s3)W(s2)=b,s3,和,s4,不能并发执行，因为,R(s4)W(s3)=c,13,2.2 进程的定义,2.2.1 进程的定义,2.2.2 进程的特征,2.2.3 进程与程序的关系,14,进程描述了程序的动态执行过程；,它对应虚拟处理机、虚拟存储器和虚拟外设等,资源的分配和回收,；,反映系统中程序执行的并发性、随机性和资源共享,引入多进程，提高了对硬件资源的,利用率,，但又带来额外的,空间和时间开销,，增加了,OS 的复杂性,；,2.2.1 进程的定义,一个具有一定独立功能的,程序,在一个,数据集合,上的一次,动态执行,过程。简言之，进程是程序的一次执行活动。,15,2.2.2 进程的特征,动态性,：,进程对应程序的执行,进程是动态产生，动态消亡的,进程在其生命周期内，在三种基本状态之间转换,独立性,：各进程的,地址空间相互独立,，除非采用进程间通信手段；,并发性：,任何进程都可以同其他进程一起向前推进,异步性,：,每个进程都与其相对独立的不可预知的速度向前推进,结构化,：进程 = 代码段 + 数据段 + PCB,16,2.2.3 进程与程序的关系,进程是动态的，程序是静态的,：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件、静态和可以复制。,进程是暂时的，程序是永久的,：进程是一个状态变化的过程，程序可长久保存。,进程与程序的组成不同,：进程的组成包括程序、数据和进程控制块（即进程状态信息）。,进程与程序的对应关系,：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。,17,2.3 进程的描述,2.3.1 进程的组成,2.3.2 进程控制块PCB,2.3.3 进程的状态及其转换,18,2.3.1 进程的组成,进程 = 程序 + 数据 + 进程控制块PCB,程序是进程的不可缺少的组成部分；如果一个程序段允许被共享，则它应该是,可重入的,，或,纯代码段,数据是进程处理的对象,进程控制块,是进程的控制结构，包含了进程的,描述信息,、,控制信息,和,资源信息,以及,现场保护区,，是进程的唯一标识，系统通过PCB管理和控制进程。,19,2.3.2 进程控制块PCB,(process control block),进程控制块是由,OS维护,的用来记录,进程相关信息和,管理进程设置的一个专门的数据结构,。,包含进程的描述信息、控制信息和资源信息以及现场保护区；,PCB是进程动态特性的集中反映。系统通过PCB感知进程的存在，通过PCB中所包含的各项变量的变化，掌握进程的状态以达到控制进程活动的目的；,PCB结构的全部或部分常驻内存；,PCB随进程的创建而填写，随进程的撤消而释放；,系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志,;,进程与PCB是一一对应的;,20,进程控制块的内容,进程描述信息,：,进程标识符(process ID)，唯一，,通常是一个整数；,进程名，通常基于可执行文件名,用户标识符(user ID)；进程组关系(process group),进程控制信息,：,当前状态；,优先级(priority)；,代码执行入口地址；,程序的外存地址；,运行统计信息（执行时间、页面调度）；,进程间同步和通信；阻塞原因,资源占用信息,：虚拟地址空间的现状、打开文件列表,CPU,现场保护结构,：寄存器值（通用、程序计数器,PC,、,状态,PSW,，,地址包括栈指针）,21,PCB的组织方式,(扩展),PCB表：,系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表,PCB表的大小决定了系统中最多可同时存在的进程个数，称为,系统的并发度,（注：多道程序中的多道与系统并发度不同）,22,链表,：同一状态的进程其PCB成一链表，多个状态对应多个不同的链表,各状态的进程形成不同的链表,：就绪链表、阻塞链表,索引表,：同一状态的进程归入一个index表（由index指向PCB），,多个状态对应多个不同的index表,各状态的进程形成不同的索引表：就绪索引表、阻塞索引表,PCB Table,Ready,Blocked,PCB Table,Index Table,Ready,Blocked,23,进程控制块,的链式组织,PCB1,PCB2,PCB3,PCB4,PCB5,PCB6,PCB7,PCBn,.,空,PCB,运行态,就绪态,等待,1,等待,2,6,7,5,10,15,24,2.3.3 进程的状态及其转换,2.3.3.1 核心态和用户态,2.3.3.2 进程的三种基本状态,25,2.3.3.1 核心态和用户态,进程的执行状态可分为用户执行状态和系统执行状态,用户执行状态，,又称,用户态,，进程的用户程序段执行时，该程序处于用户态。用户态时不可直接访问受保护的OS代码；,系统执行状态,，又称,系统态，核心态,，进程的系统程序执行时，该进程处于系统态。核心态时执行OS代码，可以访问全部进程空间。,划分用户态和系统态的原因：,把用户程序和系统程序分开，以利程序的,保护和共享,但增加了系统复杂度和系统开销,26,2.3.3.2 进程的三种基本状态,不同系统设置的进程状态数目不同,1. 进程的三种基本状态：就绪态、执行态、等待态,就绪态,（Ready）,：,一个进程已经具备运行条件，但由于无CPU暂时不能运行的状态（当调度给其CPU时，立即可以运行。,“万事俱备，只欠东风”。“就绪队列”,执行态,（Running）,：进程占有了包括CPU在内的全部资源。,进程占有CPU，并在CPU上运行,等待态,（Blocked）,：,阻塞态、挂起态、封锁态、冻结态、睡眠态。指进程因等待某种事件的发生而暂时不能运行的状态（即使CPU空闲，该进程也不可运行）,。处于等待态的进程位于等待队列中。,27,2. 基本状态间的转换,运行,Running,就绪,Ready,等待,Blocked,Dispatch,Timeout,Event,Wait,Event,Occurs,28,在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换,就绪,运行:调度程序选择一个新的进程运行,运行,就绪:,运行进程用完了时间片,运行进程被中断，因为一高优先级进程处于就绪状态,运行,等待:当一进程等待某一事件的发生时，如,OS尚未完成服务,对一资源的访问尚不能进行,初始化I/O 且必须等待结果,等待某一进程提供输入 (IPC),等待,就绪：当所等待的事件发生时,进程状态转换,29,其他状态：,创建状态,:,创建( 新new)状态,OS 已完成为创建一进程所必要的工作,已构造了进程标识符,已创建了管理进程所需的表格,但还没有允许执行该进程 (尚未同意),因为资源有限,终止状态,(Exit):,终止后进程移入该状态,它不再有执行资格,表格和其它信息暂时由辅助程序保留,例子: 为处理用户帐单而累计资源使用情况的财务程序,30,2.4 进程控制,2.4.1 进程控制的功能,2.4.2 进程控制的主要原语,返回,31,2.4.1 进程控制的功能,完成创建和撤消进程，完成进程状态的转换。,原语(primitive)：,由若干条指令构成的“,原子操作,(atomic operation)”过程，作为一个,整体,而,不可分割,-要么全都完成，要么全都不做。许多系统调用就是原语。,注意：,系统调用并不都是原语。,进程A调用read()，因无数据而阻塞，在read()里未返回。然后进程B调用read()，此时read()被重入。系统调用不一定一次执行完并返回该进程，有可能在特定的点暂停，而转入到其他进程。,32,2.4.2 进程控制的主要原语,进程创建与撤消原语,进程阻塞与唤醒原语,33,1,.,进程创建与撤消原语,为进程创建一个PCB,赋予一个统一进程标识符,为进程映象分配空间,初始化进程控制块,设置相应的链接,把新进程加到就绪队列的链表中,插入家族队列,主要任务：,需要的参数：,被创建进程的外部标识符,n,处理机的初始状态,S,0,（,包括,CPU,的工作方式、进程起始地址及屏蔽码等）；,进程优先级,P,0,；,初始内存数,M,0,；,其它所需资源清单,R,0,。,1） 进程创建原语,：,34,进程树,A,B,C,D,J,F,G,H,I,E,K,L,M,进程树是有向树,父子关系表示创建与被创建的关系,父子关系不表示执行的先后关系,35,2） 进程撤消原语Destroy,导致进程被撤消的原因,一个进程在完成任务而正常终止,由于错误导致非正常终止,祖先进程要求撤消某个子进程,功能：,释放内外存空间,关闭所有打开文件,释放共享内存段和各种锁定lock,撤消其子孙进程,释放其PCB,36,2. 进程阻塞与唤醒原语,原因,：当进程期待的某事件尚未出现时，该进程调用阻塞原语把自己阻塞起来。,过程,：,保护中断现场,置进程的状态为“等待态”,将其插入该事件的等待队列WQ(r),转进程调度,注意,：由自己阻塞自己，但该进程的唤醒则是在该进程所期待的事件发生后，由“发现者”进程调用唤醒原语实现,1）,进程阻塞原语Block,37,2） 唤醒原语Wakeup,原因,：,进程等待的事件发生，等待队列中的进程全部唤醒,唤醒进程的两种方法,：,由,系统进程,唤醒。系统进程统一控制事件的发生，并将“事件发生”这一消息通知等待进程。等待的是公共资源,由,事件发生进程,唤醒。事件发生进程与被唤醒的进程是合作关系， 等待私有资源,38,处理过程,从相应的等待队列中摘下被唤醒的进程,状态置为“就绪态ready”；,插入就绪队列,39,2.5 线程(THREAD),2.5.1 线程的引入,2.5.2 进程和线程的比较(略),2.5.3 线程举例(略),返回,引入线程的目的是,简化线程间的通信,，以小的开销来提高进程内的,并发程度,。,40,2.5.1 线程的引入,进程：,资源分配单位（存储器、文件）和CPU调度（分派）单位。又称为任务(task),线程：,作为CPU调度单位，而进程只作为其他资源分配单位。,只拥有必不可少的资源，如：线程状态、寄存器上下文和栈,同样具有就绪、阻塞和执行三种基本状态,线程的优点：,减小并发执行的时间和空间开销（线程的创建、退出和调度），因此容许在系统中建立更多的线程来提高并发程度。,线程的创建时间比进程短；,线程的终止时间比进程短；,同进程内的线程切换时间比进程短；,由于同进程内线程间共享内存和文件资源，可直接进行不通过内核的通信；,41,进程与线程的关系,42,OS对线程的实现方式,内核维护进程和线程的上下文信息；,线程切换由内核完成；,一个线程发起系统调用而阻塞，不会影响其他线程的运行。,时间片分配给线程，所以多线程的进程获得更多CPU时间。,依赖于OS核心,，由内核的内部需求进行创建和撤销，用来执行一个指定的函数。Windows NT和OS/2支持内核线程；,内核级线程(kernel-level thread),43,用户线程(user-level thread),用户线程的维护由应用进程完成；,内核不了解用户线程的存在；,用户线程切换不需要内核特权；,用户线程调度算法可针对应用优化；,不依赖于OS核心，应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程。如：数据库系统informix，图形处理Aldus PageMaker。调度由应用软件内部进行，通常采用非抢先式和更简单的规则，也无需用户态/核心态切换，所以速度特别快。一个线程发起系统调用而阻塞，则整个进程在等待。时间片分配给进程，多线程则每个线程就慢。,44,轻权进程(LightWeight Process),它是内核支持的用户线程。一个进程可有一个或多个轻权进程，每个轻权进程由一个单独的内核线程来支持。,45,2.5.2 进程和线程的比较,地址空间和其他资源,（如打开文件）：进程间相互独立，同一进程的各线程间共享某进程内的线程在其他进程不可见,通信,：进程间通信IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信需要进程同步和互斥手段的辅助，以保证数据的一致性,调度,：线程上下文切换比进程上下文切换要快得多；,46,线程切换和进程切换,47,