《操作系统讲稿2012(第三章)》由会员分享,可在线阅读,更多相关《操作系统讲稿2012(第三章)(94页珍藏版)》请在金锄头文库上搜索。
1、第三章 进程管理,进程的定义、特征、进程控制的基本概念。进程PCB基本结构,作用及进程的状态及转换。进程同步与互斥的基本概念和解决方法。几个经典的进程同步与互斥问题及算法 。进程通信的类型及实现方法线程的基本概念及状态。难点:进程的同步与互斥,本章重点:,进程的基本概念 进程的描述进程的状态及其转换 进程控制 进程互斥进程同步进程通信 管程线程小结,3.1进程的概念,一、程序的顺序执行与特征,1.程序:完成一定功能的、在时间上严格按前后顺序执行的指令集合,它可以分成若干指令串。,2.程序的执行过程:,S1: a=51,3.程序的顺序执行:一个具有独立功能的程序独占处理机直至最终结束的过程称为程
2、序的顺序执行。,Repeat IR,pc,Until CPU Halt, 输入数据, 输出结果, 计算,I,C,P,S2: b=a*5,S4: d=a+b*b+c*2,S3: c=a+b,Mpc,pc+1,Execute (instruction IR),4.程序顺序执行的特征:,(1)顺序性:每一个操作都必须在上一个操作完成之后开始,内:语句之间、指令之间,外:程序之间,(3)可再现性:只要程序的运行环境及输入条件相同,输出结果肯定相同。,(2)封闭性:资源独占,只有运行的程序能够改变资源状态,每个程序的执行不会受到外部因素的影响。,二、前趋图,前趋图(Directed Acyclic Gr
3、aph):,是一个有向非循环图,图中每个节点可以表示一条语句,一个程序或进程,节点之间的有向边表示节点之间的前趋关系(Precedence Relation)或半序关系(Partial Order),(Pi,Pj),没有前趋的节点称为初始节点 。,=,“”,|Pj必须在Pi完成之后开始执行,Pi称为Pj的直接前趋,Pj称为Pi的直接后继。,如果:(Pi,Pj) ,则, Pi Pj,如果:Pi Pk Pj Pi称为Pj的前趋,Pj称为Pi的后继。,没有后继的节点称为终止节点。,S1: a=51,S2: b=a*5,S4: d=b*b+c*2,S3: c=a+6,该图是否为前趋图?为什么?,该图是
4、否为前趋图?为什么?,三、多道程序的并发执行与特征 。,1多道程序并发执行的逻辑分析,但对于多个程序,并不一定存在关系:,Pi Ii+1,可以:第一个程序的输入结束并开始计算时,第二个程序的输入工作开始进行,从而第一个计算和第二个输入可以并行进行。,Ii,Ci,Pi,I1,I2,C1,I3,C2,P1,I4,p2,P3,C3,Ii Ci,Ii Ii+1,Ci Ci+1,Ci Pi,Pi Pi+1,2多道程序并发执行的系统实现,处理器的主要功能是执行驻留在内存中的指令,为了提高效率,处理器可以同时执行多道程序。对于处理器而言,对全部指令的执行是按一定顺序进行的,这个顺序的改变是通过改变程序计数器
5、(PC)或称为指令指示器(IP)的值来完成的。,例:程序A的起始地址为51200,共12条指令;程序B的起始地址为81920,共4条指令,其中第4条指令包括I/O指令;程序C的起始地址为194560,共12条指令;分派程序的起始地址为20480,共6条指令;三个程序以及分派程序均在内存,操作系统每次执行6条用户程序指令后就会自动终止当前用户程序,转去执行分派程序。每条指令需要一个指令周期,则程序的执行过程如下:,20480 2048120482204832048420485 81920 81921 81922 81923 I/O请求,1. 512002. 512013. 512024. 512
6、035. 512046. 51205 超时,204802048120482204832048420485194560194561194562194563194564194565超时,29 2048030 2048131 2048232 2048333 2048434 2048535 5120636 5120737 5120838 5120939 5121040 51211,41 2048042 2048143 2048244 2048345 2048446 2048547 19456648 19456649 19456750 19456851 19456952 194570,3多道程序并发执行
7、的定义,并发执行:为了增强计算机系统的处理能力和提高资源的利用率所采用的一种同时操作技术。使若干进程都处于已经开始执行和尚未执行完成的状态。多道程序的并发执行分两种情况:多道程序系统的程序执行环境变化引起的多道程序的并发执行(多道程序系统环境下,各道程序在逻辑上独立,具备了执行的条件)。在某道程序的几个程序段中,包含着一部分可以同时执行或顺序颠倒执行的代码。,4.多道程序并发执行的特征:,(2)间断性:程序并发执行时,由于(a)它们共享软、硬件资源(b)程序之间相互合作完成一项共同任务,因而使程序之间相互制约。这种制约导致并发程序具有“执行-暂停-执行”这种间断活动的特点。,(1)失去了封闭性
8、:多道程序相互影响。,(3)独立性:系统把每个程序作为一个独立单位来进行分配,并发程序在运行过程中,既然是作为一个独立的运行实体,它也必然具有作为一个单位去获得资源的独立性。,(4)随机性:有可能失去可再现性,由于公用变量的存在,使程序由于微观上的执行顺序不同而产生不同的结果。,四、Bernstain条件 。,程序的不可再现性是绝对不允许的,为此,应采取某种措施使并发程序保持其可再现性。,Si、Sj:程序段或语句。,R(Si):Si所涉及的读变量的集合。,W(Si):Si所涉及的写变量的集合。,Si与Sj可并发执行的条件:, R(Si)W(Sj)=, R(Sj)W(Si)=, W(Sj)W(S
9、i)=,同时成立,例:,S1: C=X+Y+Z,S2:D=C+X,R(S1)=X,Y,Z,R(S2)=C,X,W(S1)=C,W(S2)=D,S1:x=x1+x2,S2:y=x1*x2,S3:z=(x+y)/2,S4:w=z+5,S5:m=w+1,S6:m=m+1,不能并发!,五、进程的定义,进程:一个具有独立功能的程序对某个数据集合在处理机上的一次执行过程。它是操作系统进行资源分配的基本单位。,操作系统所应满足的主要要求都与进程有关:,操作系统必须能够同时执行多个进程以最大限度地利用处理器,并为每个进程提供合适的响应时间。,操作系统必须按一定的策略为进程分配资源并避免死锁。,操作系统应支持进
10、程间的通信并能创建用户进程。,操作系统的主要职责就是控制进程的执行。,六、进程的特征,动态性:进程是程序的一次执行过程。因此,动态特征是进程的最重要特征,并发性:只有建立了进程的程序才能并发执行,引入进程的目的就是为了使它所对应的程序和其他进程并发执行,以提高系统资源的利用率。,独立性:每个进程都有各自独立的功能。进程是一个能独立运行的单位,也就是竞争计算机资源和进行处理机调度的基本单位。,结构特征:每个进程都配有一个PCB,每个进程都有程序段、数据段和PCB三部分组成。,异步性(相互制约性):由于进程之间的相互制约,使其具有执行的间断性。既:进程按各自独立的不可预知的速度向前推进。,七、进程
11、与程序的比较,状态,存在方式,所需资源,包含关系,并发 性,进程,程序,动,静,生命期短,永久,内存、外存、CPU,外存,进程包含程序,程序不包含进程,有,无,3.2进程的描述PCB,进程包括:程序段、数据段、PCB,二、PCB的内容:,1.描述信息:,进程标识符(PID)或进程名:用来唯一标识进程。,家族信息(Family):进程所属家族,即:进程的父进程和子进程等。,用户标识符(UID)或用户名:进程所属用户,利于进行资源共享和信息保护。,一、作用:PCB中包含了进程的控制信息和描述信息,是进程动态特征的集中体现。PCB是系统感知进程存在的唯一标志。,处理机状态(CPU):处理机的各种寄存
12、器的内容,包括:通用寄存器(用户可视寄存器)、指令计数器、程序状态字、用户栈指针。,2.控制信息,进程的状态(Status):进程所处的状态,就绪,运行,等待。,进程优先级(Priority):处理机调度的依据,其值取决于进程执行的紧迫程度以及进程占用CPU的时间,占据内存时间、占据其他资源等情况,程序和数据的起始地址(Start):进程所对应的程序的起始地址。,通信信息( Communication):该进程在运行过程中与其他进程交换信息的情况。消息队列指针、信号量等,记时信息(TIME):记录进程等待CPU的时间、已占有CPU的时间等以及使用其他资源的时间,占内存大小,位置(RAM)及其管
13、理用数据结构。,外存交换区位置(SWAP),共享区位置,大小(SHARE),打开文件情况(FILE),外设情况(DEVICE),PCB指针(PCBPtr),进程控制块PCB是系统感知进程存在的唯一标志。系统对进程的各种操作通过对PCB的操作实现。,三、进程组织:不同系统组织方式不同:链接、索引,四、存在区 :PCB的常用部分常驻内存系统区,其他部分放在外存。,3.3进程的状态及其转换,一、进程的基本状态,就绪状态(READY):进程获得除处理机以外的所 有资源,等待处理机。,2. 运行状态(RUNNING):进程正在占有处理机,其对应的程序正在处理机上运行。单处理机系统中,只能有一个进程处于运
14、行状态。,3.等待状态/阻塞状态(WAITING/BLOCKED):进程正在等待某件事情的发生无法继续运行下去而放弃处理机。,5. 终止(EXIT):进程已正常或异常结束,被OS从可运行进程队列中释放出来,4. 创建/初始(NEW):进程刚刚创建,还没有被处理机提交到可运行进程队列中。,二、进程的状态转换:,1三种状态的进程状态转换图,就绪,阻塞,运行,I/O请求,I/O完成,终止,2五种状态的进程状态转换图,就绪,阻塞,运行,准许,I/O请求,I/O完成,完成,初始,终止,3具有挂起状态的进程状态转换图,活动就绪,活动阻塞,运行,准许,等待某件事情,完成,初始,终止,静止就绪,静止阻塞,挂起
15、,激活,挂起,激活,等待的事情发生,等待的事情发生,挂起,3进程状态间转换关系表,说明:一般的操作系统为了管理方便,根据等待的事件设置多个阻塞队列,将等待不同事件的进程放在不同的等待队列中。,3.4进程控制,进程控制:系统使用一些具有特定功能的程序来创建、撤消进程以及完成进程各状态间的转换,从而达到多进程、高效率、并发执行和协调、实现资源共享的目的。,实现进程控制的程序段被称作进程控制原语。,进程控制是通过原语来实现。,原语:用于完成某种特定功能的不可分割的一段程序。原语的实现是通过关中断来实现的。,一、内核:,1.什么是内核?,在设计OS时把一些与硬件紧密相关的模块或运行频率较高的模块以及被许多模块所公用的一些基本操作,安排在靠近硬件的层次中,并使他们常驻内存,以提高OS的运行效能,通常把这部分叫OS的内核。,2.内核的基本功能:,中断处理:,在OS中,中断处理既是内核最基本功能也是整个OS赖以活动的基础,在内核中对中断进行”有限的处理”然后便转去相关的进程继续处理。应该说OS的重要活动最终都将依赖于中断的进程调度、设备驱动、系统调用等等。,进程管理 :,进程的建立与撤消,