计算机操作系统课件(第四版)第二章资料

第二章进程管理2.1前驱图和程序执行2.2进程的描述2.3进程控制2.4进程同步2.5经典进程同步问题2.6进程通信2.7线程的基本概念2.1前驱图和程序执行程序的顺序执行前趋图与前趋关系程序的并发执行1、程序顺序执行的特征(1)程序的顺序执行语句1语句2语句3语句4语句5I1C1P1I2C2P2程序1程序2(2)特征①顺序性②封闭性③可再现性2、前趋图与前趋关系前趋图(PrecedenceGraph)一个有向无循环图描述程序或程序段之间执行的前后关系前趋关系“”如果：(Pi,Pj)∈，也可以写成：PiPj则称：Pi是Pj的直接前趋,Pj是Pi的直接后继初始结点：没有前趋终止结点：没有后继P1P2P3P8P6P5P7P4P9观察下图，初始结点是哪个？终止结点是哪个？有哪些前驱关系？思考：下图是否为前趋图？S1S2S33、程序的并发执行I1C1P1I2C2P2I3C3P3I4C4P4输入程序计算程序打印程序对于下述四条语句的程序段：S1：a:=x+2;S2：b:=y+4;S3：c:=a+b;S4：d:=c+b;S2S1S3S4并发执行时的特征间断性——“停停走走”失去封闭性——原因：多个程序共享资源不可再现性程序A{n=n+1;}程序B{print(n);n=0;}例如:有两个循环程序A和B，共享一个变量n。程序A和B以不同的速度运行。可能出现的情况如下：1、A快B慢，得到的n值为：n+1,n+1,02、B快A慢，得到的n值为：n,0,13、n:=n+1在print(n)和n:=0之间，如图，得到的n值为n,n+1,02.2进程的描述进程的定义和特征进程的基本状态和转换挂起操作和状态转换进程管理中的数据结构2.2.1、进程的定义和特征进程的定义进程的特征进程的定义进程：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。进程实体＝程序段＋相关的数据段＋PCB进程组成系统数据段，PCB程序段数据段LinuxLinux的进程实体组成Linux进程是由三部分组成：正文段、用户数据段和系统数据段。(1)正文段（text）——程序段正文段是只能读不能修改的指令代码，它允许系统中多个进程共享这一代码段。(2)用户数据段（usersegment）——数据段用户数据段是进程执行时直接操作的所有数据（包括全部变量在内），这些信息是可以被修改的。(3)系统数据段（systemsegment）——PCB系统数据段存放着进程的控制信息，即进程控制块（PCB），它存放了程序的运行环境。PCB程序段数据段进程的结构图示：进程控制块动态特征的集中反映描述要完成的功能操作对象及工作区进程的其他定义：进程是一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。进程是并发程序的一次执行过程。是系统进行资源分配和调度的独立单位。进程是可以和别的计算并发执行的计算。进程与程序的区别进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。进程是暂时的，程序的永久的：进程是一个状态变化的过程，程序可长久保存。进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。进程的特征动态性：“它由创建而产生，由调度而执行，由撤销而消亡”。进程具有动态的地址空间（数量和内容），地址空间上包括：代码（指令执行和CPU状态的改变）数据（变量的生成和赋值）系统控制信息（进程控制块PCB的生成和删除）独立性：进程是一个能独立运行、独立分配资源和独立调度的基本单位。各进程的地址空间相互独立。并发性：引入进程的目的正是为了使其程序能和其他进程的程序并发执行；异步性：进程按各自独立的、不可预知的速度向前推进结构性：进程由程序段、数据段及PCB三部分组成，在Linux中称为“进程映像”2.2.2进程的基本状态及转换就绪状态（Ready）得到了除CPU以外的所有必要资源执行状态（Running）已获得处理机，程序正在被执行阻塞状态（Blocked）因等待某事件发生而暂时无法继续执行，从而放弃处理机，使程序执行处于暂停状态1、进程的三种基本状态中断接纳完成进程调度事件发生等待某事件创建终止就绪执行阻塞进程基本状态转换图创建状态为新进程创建PCB，填写信息，该进程转入就绪状态并插入就绪队列中。引入创建状态可保证进程的调度在创建工作完成后，确保对PCB操作的完整性。终止状态等待OS进行善后处理将PCB清零，将PCB空间返还系统。终止态的进程不能再执行，但需等待其它进程完成对它的信息提取后，OS再将它删除。进程的挂起状态（静止状态）引入父进程考查和修改、协调子进程间的活动操作系统协调资源使用或进行记账终端用户的请求，希望自己的程序暂时静止下来负荷调节的需要，如实时紧急任务，由系统把一些不重要的进程挂起内存外存活动静止进程的挂起状态挂起就绪挂起阻塞活动就绪执行活动阻塞挂起I/O请求挂起激活挂起调度释放激活释放唤醒1、操作系统中用于管理控制的数据结构资源信息表、进程信息表：数据结构表征其实体。包含了资源或进程的标识、描述、状态等信息及一批指针。2.2.4、进程管理中的数据结构内存设备文件进程内存表设备表文件表进程表1进程表n进程1进程n...进程实体及所用资源列表2、PCB(ProcessControlBlock)PCB中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息。OS是根据PCB来对并发执行的进程进行控制和管理的。是进程存在的唯一标志。PCB可被操作系统中的多个模块读或修改，如被调度程序、资源分配程序、中断处理程序以及监督和分析程序读或修改。PCB经常被系统访问，故应常驻内存。2.2.4、进程管理中的数据结构Linux的PCB结构3、PCB中的信息进程标识符：唯一的标识一个进程内部标识（OS）外部标识（由创建者提供，由字母数字组成）处理机状态：由CPU的各种寄存器中的内容组成。通用R指令计数器PC程序状态字PSW用户栈指针进程调度信息：进程状态进程优先级其它信息等待事件（阻塞原因）进程控制信息：程序和数据的地址同步和通信机制资源清单链接指针4、进程控制块的组织方式PCB数目一个系统中的PCB数目可为数十个、数百个甚至数千个线性方式把所有的PCB都组织在一张线性表中，将表的首地址放在内存的专用区中。链接方式把具有同一状态的PCB，用其链接字链接成一个队列就绪队列、若干个阻塞队列、空队列索引方式系统根据所有进程的状态建立相应的索引表就绪索引表、阻塞索引表等，索引表在内存的首地址记录在内存的一些专用单元中。PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9……PCB线性表示示意图PCBn执行指针就绪队列指针阻塞队列指针空闲队列指针PCB14PCB23PCB30PCB48PCB5PCB67PCB79PCB80PCB911……PCB链接队列示意图PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9……执行指针就绪队列指针阻塞队列指针按索引方式组织PCB第三节进程的控制系统内核进程创建进程撤消进程阻塞进程唤醒进程挂起与激活进程管理中最基本功能是进程控制。进程控制的作用：创建新进程，终止已完成进程，并负责进程的状态转换。进程控制是由OS内核中的原语实现的。OS内核：把一些与硬件紧密相关的模块（如中断）、各种常用设备的驱动程序、运行频率较高的模块（时钟管理、进程调度等）以及为许多模块公用的一些基本操作，安排在靠近硬件的软件层次中，以提高OS的运行效率。OS内核是常驻内存的程序和数据。2.3.1操作系统内核原语：是由若干条指令组成的，用于完成一定功能的一个过程。具有不可分割性。具有原子性。即：原语的执行必须是连续的，在执行的过程中不允许被中断。处理机的执行状态具有两种状态：核心态(系统态、管态)：OS的管理程序执行时处理机所处状态。具有较高的特权，能执行一切指令，访问所有寄存器和存储区。OS运行在系统态。用户态（目态）：用户程序执行时处理机所处状态。具有较低特权的执行状态，仅能执行规定的指令访问制定的寄存器和存储区。应用程序一般运行在用户态。1、进程创建（Creat()）进程之间的关系：父、子进程与祖先进程：PCB中标识继承归还资源、“父”创建“子”、父撤子消引起创建进程的事件用户登录、作业调度、提供服务、应用请求进程创建的过程申请空白PCB、为新进程分配资源、初始化PCB、插入就绪进程队列PDPBPEPCPFPAPIPHPGPJPKPLPMPNHD就绪队列指针PCB15PCB2PCB3PCB4PCB513PCB60PCB7PCB89PCB912PCB10PCB11PCB1225PCB136……空PCB队列指针RAM程序+数据PCB80PCB682、进程撤消（Terminat()）引起进程终止（Termination）的事件正常结束：执行到最后的结束指令、中断异常结束：出现错误或因故障而被迫终止外界干扰：进程应外界的请求而终止运行进程撤消的过程检索进程状态、结束并置调度标志、撤销其所有的子进程、归还资源、移出队列一个进程可以向其父进程申请撤消自己；也可以因父进程的被撤销而被同时撤消。PDPBPEPCPFPAPIPHPGPJPKPLPMPN3、进程阻塞（Block()）引起阻塞的事件请求系统服务、启动某种操作、数据尚未到达、无新工作可做进程阻塞的过程发现上述事件，调用阻塞原语把自己阻塞停止进程的执行，修改PCB中的状态信息，并将其插入相应的阻塞队列转调度程序进行重新调度4、进程唤醒（Wakeup()）引起唤醒的事件与引起阻塞的事件相对应进程唤醒的过程阻塞进程所期待的事件出现，有关的进程调用唤醒原语，将等待该事件的进程唤醒将PCB从阻塞队列中移出，修改PCB中的状态信息，再将其插入到就绪进程队列中阻塞与唤醒要匹配使用，以免造成“永久阻塞”5、进程挂起与激活（Suspend()、Active()）进程挂起检查被挂进程的状态，改为相应的挂起状态。把进程的PCB复制到指定的区域。最后，转向调度程序重新调度。进程激活先将进程从外存调入内存。检查该进程的现行状态，改为相应的活动状态。根据优先级确定是否需要重新调度。第四节进程同步进程同步的主要任务是使并发执行的诸进程之间有效地共享资源和相互合作，从而使程序的执行具有可再现性。基本概念硬件同步机制信号量机制信号量的应用进程互斥：一个进程正在访问临界资源，另一个要访问该资源的进程必须等待。并发执行可产生与时间有关的错误2.4.1基本概念两种形式的制约关系直接相互制约：源于进程间的合作间接相互制约：源于进程对资源的共享进程同步：合作完成同一个任务的多个进程，在执行速度或某些时序点上必须相互协调的合作关系。进程同步举例：例1：接力赛例2：司机－售票员司机：P1while(true){启动车辆；正常运行；到站停车；}售票员：P2while(true){关门；售票；开门；}互斥现象火车到站的调度火车1火车2火车3…站台轨道例1：两个同学做抢椅子的游戏。同学甲……if有空椅子then坐下……同学乙……if有空椅子then搬走……例2：民航售票系统主机A窗口B窗口C窗口D窗口每个进程执行的操作：设x表示某航班的票数。……ifx0thenx:=x-1;……在某时刻x=1，有a、b两人分别去A窗口、B窗口买票，分析售票情况：时间片到a人b人例3：交通流量统计统计在一定的时间段之内在路面上通过的车辆数量。利用计算机计数车辆数。S表示车辆数。S:=0;Delay(600);Write(S);中断处理程序：S:=S+1;例4：存储管理分配进程（B）……ifxBthen等待elsex=x-B;……回收进程（B）……x=x+B;唤醒；……(x为可用内存空间)例5：哲学家就餐问题五个哲学家围着桌子坐，工作方式：思考；if饿了{拿左叉子；拿右叉子；吃