操作系统习题2.2

第二章,进程管理,2.1.1程序的顺序执行及特征一、程序执行有固定的时序。（图2-1p27）I表示输入，C表示计算，P表示打印S1:a:=x+y;S2:b:=a-5;S3:c:=b+1二、特征：顺序性、封闭性、可再现性,2.1进程的基本概念,I1,C1,P1,I2,C2,P2,S1,S2,S3,2.1.2前趋图定义,有向无循环图DAG,描述进程间执行的前后关系。表示方式：（1）p1-p2（2）-=(p1,p2)|p1必须在p2开始前完成节点表示：一条语句，一个程序段，一进程。没有前驱的结点称初始结点，没有后继的结点称为终止结点。,P1,P2,P4,P3,2.1.3程序的并发执行,一、多个程序的并发执行（可能性分析）,I1,I2,I3,I4,C1,C2,C3,C4,P1,P2,P3,P4,t,2.1.3程序的并发执行,举例：现有四个语句S1:a:=x+2S2:b:=y+4S3:c:=a+bS4:d:=c+b,S1,S2,S3,S4,程序的并发执行(2),二、特征间断性程序间相互制约导致并发程序具有“执行暂停执行”这种间断性的活动。失去封闭性主要由共享资源引起不可再现性：P29例，设N的初值为n。有2个循环程序A和B，它们共享一个变量N，程序A每执行一次时，都要做N:=N+1;B则每次要执行Print(N),然后再做N:=0.若程序A,B以不同的速度运行有以下三种不同的结果,程序的并发执行(3),N:=N+1在print(N)和N:=0之前.N:=N+1在print(N)和N:=0之后，N:=N+1在print(N)和N:=0之间，,则N值分别为n+1,n+1,0,则N值分别为n,0，1,则N值分别为n,n+1,0.,2.1.4进程的特征和状态,1.进程的特征和定义一、定义：进程实体的运行过程，是系统进程资源分配和调度的一个独立单位1.结构特征进程：由程序段、数据段及进程控制块（PCB）三部分构成，总称“进程实体”UNIX“进程映像”2.动态性由“创建”而产生，由“调度”而执行；由得不到资源而阻塞；由撤消而消亡。（而程序是静态的,只是一组有序的指令的集合）。,2.1.4进程的特征和状态(2),3.并发性是进程的重要特征只有建立了进程，才能并发执行（程序因为没有建立PCB是不能并发执行的）。4.独立性。指进程实体是一个能独立运行，独立获得资源和独立接受调度的基本单位。5.异步性：（间断性）,2.1.4进程的特征和状态(3),2.进程的三种基本状态（图2-5）就绪状态进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，便可立即执行的状态处于就绪状态的进程可能有多个=就绪队列执行状态进程已获得CPU，其程序正在执行阻塞状态（等待状态）正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，亦即进程的执行收到阻塞的状态如请求I/O，申请缓冲空间等处于阻塞状态的进程有一列，或者多个列。,2.1.4进程的特征和状态(3),进程的三种基本状态的转换,就绪,阻塞,执行,时间片完,进程调度,I/O请求,I/O完成,图25进程的三种基本状态及其转换,2.1.4进程的特征和状态(4),3.挂起状态（被换出内存的状态）引入原因(了解)终端用户请求父进程请求负荷调节需要操作系统需要进程状态的转换(图2-6),活动,静止,挂起(Suspend原语),阻塞,就绪,唤醒(Active原语),图26具有挂起状态的进程状态图,执行,活动就绪,静止就绪,活动阻塞,静止阻塞,激活,挂起,激活,挂起,唤醒,唤醒,挂起,请求I/O,2.1.5进程控制块（PCB）,1.进程控制块的作用（使进程并发）PCB(processcontrolblock)常驻内存是进程存在的唯一标志；为系统提供可并发的独立运行单位为OS管理和控制提供一切信息2.进程控制块中的信息标识、处理机状态，进程调度信息，进程控制信息,2.1.5进程控制块（PCB）,进程控制块中的信息进程标识符惟一标示一个进程通常分两种内部标识符=OS赋予，为方便系统使用外部标识符=创建者提供，由用户在访问该进程时使用用户标识家族关系描述处理机状态通用寄存器（用户可视寄存器）用户程序可以访问，暂存信息指令计数器存放要访问的下一条指令的地址状态寄存器PSW如条件码、执行方式、中断屏蔽标志用户栈指针指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。,2.1.5进程控制块（PCB）,进程控制块中的信息进程调度信息进程状态进程优先级进程调度所需的其他信息进程执行状态转变为阻塞状态所等待发生的事件进程控制信息程序和数据的地址（内存或外存地【首】址）进程同步和通信机制资源清单链接指针本进程（PCB）所在队列中的下一个进程的PCB的首地址,2.1.5进程控制块(2),3.PCB的组织链接（p33图2-7）,执行指针,就绪队列指针,阻塞队列指针,空闲队列指针,2.1.5进程控制块(3),3.PCB的组织索引(p34图2-8),执行指针,就绪表指针,阻塞表指针,2.2进程控制,处理机的执行状态分成两种：系统态又称核心态，管态具有较高的特权能执行一切指令访问所有寄存器和存储区用户态又称目态具有较低特权的执行状态只能执行规定的指令访问指定的寄存器和存储区,将一些与硬件紧密有关的模块诸如中断处理程序，各种常用设备的驱动程序，以及运行频率较高的模块（如时钟管理、进程调度以及许多模块公用的一些基本操作）都安排在仅靠硬件的软机层次中，并使它们常驻内存，以便提高OS的运行效率，并对它们加以特殊的保护。这一部分称OS的内核。内核是计算机硬件的第一层扩充软件。,2.2.1操作系统内核,大多数OS的内核包含如下功能：支撑功能中断处理时钟管理原语操作资源管理功能进程管理存储器管理设备管理,2.2.1操作系统内核,2.2.2进程创建,进程图进程图是用于描述一个进程的家族关系的有向图。在进程Pi创建了进程Pj之后，称Pi是Pj的父进程（ParentProcess），Pj是Pi的子进程（ProgenyProcess）。树的根结点作为进程家族的祖先（Ancestor）。,A,B,C,D,E,F,G,I,J,K,L,H,M,引起创建进程的事件用户登录。作业调度。提供服务。应用请求。进程的创建申请空白PCB。为新进程分配资源。初始化进程控制块。将新进程插入就绪队列。,2.2.2进程创建,2.2.3进程的终止,引起进程终止的事件正常结束异常结束越界错误保护错如：进程试图去写一个只读文件非法指令程序试图去执行一条不存在的指令。特权指令错运行超时等待超时算术运算错如：被0除。I/O故障外界干预,进程的终止过程根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真。若该进程还有子孙进程，应将其所有子孙进程予以终止。将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。将被终止进程从所在队列中移出，等待其他程序来搜集信息。,2.2.3进程的终止,2.2.3进程的阻塞与唤醒,引起进程阻塞和唤醒的事件请求系统服务启动某种操作新数据尚未到达无新工作可做进程阻塞过程进程唤醒过程,进程的挂起挂起原语suspend()将指定进程或处于阻塞状态的进程挂起挂起原语的执行过程：见书P进程的激活激活原语active()将指定进程激活。激活原语执行过程：见书P,2.2.4进程的挂起与激活,2.3.1进程同步的基本概念,2.3.2信号量机制,任务：使并发执行的各进程之间能有效的共享资源和相互合作，使程序的执行具有可再现性。,2.3.3信号量的作用,2.3进程同步,2.3.1进程同步的基本概念,两种形式的制约关系间接制约关系互斥共享打印机；等待其他进程释放打印机直接制约关系进程间合作；等待其他进程输入数据临界资源只允许一个进程使用的资源。否则可能造成系统混乱，结果不可再现。,P39程序，生产者和消费者共享变量counter,生产者：向缓冲区投入产品，counter=counter+1;消费者：从缓冲区取出产品，counter=counter-1;,设counter的初值为5register1:=counter;register2:=counter;register1:=register1+1;register2:=register2-1;counter:=register1;counter:=register2;,先执行左三列，再执行右三列，共享变量counter=5；,先执行右三列，再执行左三列，共享变量counter=5；,2.3.1进程同步的基本概念,2.3.1进程同步的基本概念,register1:=counter;(register1:=5)register1:=register1+1;(register1:=6)register2:=counter;(register2:=5)register2:=register2-1;(register2:=4)counter:=register1;(counter:=6)counter:=register2;(counter:=4),但是按照下列顺序执行，counter值为4；可能性也可以为6,2.3.1进程同步的基本概念,结论：,应把共享变量counter作为临界资源处理，即生产者和消费者互斥的访问变量counter，才会使计算结果具有可再现性。,两个程序并发执行，并共享变量counter，会出错。因为机器语言具体描述时，使用寄存器变量。,出现问题,临界区每个进程中访问临界资源的代码称为临界区(criticalsection)。临界区前增加一段用于进行检查的代码称进入区。临界区后加上的用于恢复正被访问的标志为未被访问的标志的代码称退出区。进程中除进入区、临界区及退出区外其他代码称为剩余区。,2.3.1进程同步的基本概念,repeat,Entrysection,Criticalsection；,Exitsection,Remaindersection；,Untilfalse；,同步机制应遵循的准则空闲让进忙则等待有限等待应保证为有限等待，不会产生死等。让权等待不能进入临界区的执行进程应放弃CPU执行权。,2.3.1进程同步的基本概念,2.3.2信号量机制,1965年，荷兰学者Dijkstra提出信号量(semaphores)机制是一种卓有成效的进程同步工具已被广泛应用于单处理机和多处理机系统及计算机网络中整型信号量记录型信号量信号量集信号量=资源初值=资源数量,整型信号量wait（s）：whileS=0dono-op；s:=s-1;/*申请资源，减1操作判断是否有可用资源，也叫P操作*/signal（s）:s:=s+1；/*释放资源，加1操作，也叫V操作*/,2.3.2信号量机制,记录型信号量S中，增加了value和阻塞队列指针LTypesemaphore=recordvalue:integer;L:listofprocess;endwait（S）：S.value=S.value-1；/*判断系统中是否有该类资源*/ifS.value0thenblock（S.L）/*解决“忙等”，做到了“让权等待”*/；signal（S）：S.value=S.value+1；/*归还某类资源给系统*/ifS.value=0thenwakeup（S.L）；,2.3.2信号量机制,AND型信号量解决进程共享两个或更多共享资源的问题,2.3.2信号量机制,如P43页的访问顺序，会进入死锁状态作业1：自行分析死锁的产生,作业2：分析and运算作用,解决办法使用AND型同步机制：要么全部分配到进程，要么一个也不分配给它,信号量集解决每次需要N个某类资源的问题作业3：分析Swait函数中各变量含义，以及各条语句的功能；分析并体会Swait（S，d，d）；Swait（S，1，1）；Swait（S，1，0）；,2.3.2信号量机制,2.3.3信号量的应用,1.利用信号量实现互斥（wait和signal要成对出现）varmutex:semaphore:=1beginparbeginprocess1:beginrepeatwait(mutex);criticalsetionsignal(mutex);remaindersectionuntilfalse;end,wait(mutex);criticalsetion；signal(mutex);,process2:beginrepeatwait(mutex);criticalsetionsignal(mutex);remaindersectionuntilfalse;endparend,2.3.3信号量的应用,利用信号量实现前趋关系,2.3.3信号量的应用,inta=0,b=0,c=0,d=0,e=0;S1;signal(a);sigal(b);wait(a);S2;signal(c);signal(d);wait(b);S3;signal(e);wait(c);S4;signal(f);wait(d);S5;signal(g);wait(e);wait(f);wait(g);S6;,S1释放资源供S2和S3使用，所以S1先执行,小结,1.两种形式制约关系2.临界资源把共享变量counter作为临界资源来访问临界区3.同步机制遵循原则（了解）4.信号量机制（1）整型信号量PV缺点（2）记录型信号量S.value0,=0以及绝对值含义block(S.L);wakeup(S.L)含义5.信号量作用（1）实现互斥（2）实现前趋关系,小结,使并发的程序结果具有可再现性,进程,对并发的进程进行协调，使程序执行具有可再现性,进程同步机制,进程对打印机和共享变量counter必须互斥访问,临界资源,临界区criticalsection,信号量机制,整型信号量,S=1(一台打印机);wait(s);申请资源；减1加锁signal(s);释放资源；加1解锁,只要S1)thenwait(sofa);在沙发中就座；wait(empty);在沙发上起来；signal(sofa);elsewait(empty);,处理问题,在理发椅上就座；signal(full);理发；付费；signal(payment);wait(receipt);从理发椅子上起来；signal(empty);wait(mutex);count-;signal(mutex);离开理发店；,处理问题,barber:while(1)wait(full)；替顾客理发；wait(payment);收费；signal(receipt);,习题2,有一间酒吧里有3个音乐爱好者队列，第1队的音乐爱好者只有随身听，第2队的音乐爱好者只有音乐磁带，第3队的音乐爱好者只有电池。然而，要听音乐就必须随身听、磁带、电池这三种物品俱全。酒吧老板一次出售这三种物品中的任意两种。当一名音乐爱好者得到这三种物品并听完一首乐曲后，酒吧老板才能再一次出售这三种物品中的任意两种，于是第二名音乐爱好者得到这三种物品，并开始听音乐。全部买卖就这样进行下去。试用信号量实现他们的同步关系。,解答,semaphores1,s2,s3,m_over;,voidfan1()买磁带和电池；听音乐；,voidfan2()买随身听和电池；听音乐；,voidfan1()买随身听和磁带；听音乐；,wait(s1);,signal(m_over);,wait(s2);,wait(s3);,signal(m_over);,signal(m_over);,解答,voidboss()while(1)提供任意两种物品销售；if(提供磁带和电池)elseif(提供随身听和电池)else,signal(s1);,signal(s2);,signal(s3);,wait(m_over);,2.5管程机制,引入原因使用信号量处理同步问题时，同步操作wait(s)和signal(s)分散在各个进程中，并遍布整个程序。这不仅给系统的管理和程序的维护和修改带来了麻烦，而且还会因同步操作使用不当造成死锁。管程的定义一组局部共享变量，以及对这些局部变量进行的操作的函数，一并称为管程。说明：共享变量和函数，一并封装在管程内，任何进程只有通过管程才能够访问共享变量，任一时刻，最多只能有一个进程在管程中执行。,条件变量引入目的：为了描述阻塞原因定义格式：Varx，y：condition执行的操作（1）waitx.wait（2）signalx.signal注意：若没有等待进程，x.signal不起任何作用，空操作。,2.5管程机制,利用管程解决生产者消费者问题,2.5管程机制,建立管程管程名：p_c；put投入产品get取出产品count产品数目notfull缓冲池不全满notempty缓冲池不全空,producer:beginrepeatproduceaitemnextpPC.put(item);untilfalse.EndConsumer:beginrepeatPC.get(item);Consumetheiteminnextc;Untilfalseend,回顾,经典进程同步问题生产者消费者问题empty=n;full=0;mutex=1哲学家进餐问题只有拿到两双筷子哲学家才能就餐读者写者问题允许多个读者同时读；写者必须与其他任何进程互斥。,回顾,semaphoremutex=1公共缓冲池（临界资源，互斥访问）,full=0；满缓冲区数目为0,生产者：生产商品；wait(empty)；/*是否有空缓冲区*/wait(mutex)；/*缓冲池是否可用*/向缓冲区投入产品；signal(mutex)；/*释放缓冲池*/signal(full)；/*满缓冲区数目+1*/,消费者：wait(full)；/*是否有满缓冲区*/wait(mutex)；/*缓冲池是否可用*/从缓冲区取出产品；signal(mutex)；/*释放缓冲池*/signal(empty)；/*空缓冲区数目+1*/,empty=n；有n个空缓冲区,2.6进程通信,进程通信是指进程之间的信息交换，其所交换的信息量，少者是一个状态或者数值，多者是成千上百万个字节。低级通信：进程间交换信息量少。效率低通信对用户不透明高级通信：用户可直接利用操作系统所提供的一组通信命令，高效地传送大量数据的一种通信方式。操作系统隐藏了进程通信的实现细节。通信过程对用户是透明的。,2.6进程通信,进程通信类型（高级通信）共享存储器系统相互通信的进程共享空间进行通信消息传递系统最广泛的一种进程间通信机制管道通信共享文件UNIX系统首创，能有效地传送大量数据,2.6进程通信,共享存储器系统基于共享存储区数据结构的通信方式要求诸进程公用某些数据结构，借以实现诸进程间的信息交换。-公用数据结构的设置及对进程间同步的处理都由程序员完成效率较低，只适于传递相对少量的数据。基于共享存储区的通信方式在存储器中划出一块共享存储区，通过共享存储区中的数据的读写来实现通信。,2.6进程通信,消息传递系统进程间的数据交换以格式化的消息为单位。消息分为消息头：包括消息在传输时所需的控制信息（源进程名、目标进程名、消息长度、消息类型、发送时间等）消息正文：发送进程实际所发送的数据。根据实现方式，又可分为直接通信和间接通信。,2.6进程通信,消息传递系统直接通信方式发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。要去发送进程和接收进程都以显式方式提供对方的标识符。通信命令（原语）：send（receiver，message）receive（sender，message）,2.6进程通信,消息传递系统间接通信方式进程间的通信需要通过作为共享数据结构的实体。该实体用来暂存发送进程发送给目标进程的消息；接收进程则从该实体中，取出对方发送给自己的消息，这个实体称为信箱。OS提供若干条原语分别用于信箱的创建、撤销和消息的发送和接收。,消息传递系统间接通信方式信箱可由操作系统创建，也可由用户进程创建，创建者是信箱的拥有着。信箱种类：私用信箱：用户进程为自己建立的一个新信箱，作为该进程的一部分。公用信箱：操作系统创建，并提供给系统中的所有核准进程使用。共享信箱：由某个进程创建，在创建时或者创建后，指明它是可共享的，同时须指出共享进程（用户）的名字。,2.6进程通信,消息传递系统间接通信方式通信链路（communicationlink）通信链路的建立发送进程通信前用显示的“建立连接”命令请求系统为之建立一条通信链路；用完后，显示方式拆除=主要用于计算机网络发送进程无须明确提出建立链路，只须利用系统提供的发送命令，系统自动为之建立一条链路。=主要用于单机系统。,2.6进程通信,消息传递系统通信链路（communicationlink）类型根据通信链路连接方法点-点连接通信链路多点连接链路根据通信方式单向通信链路=私用信箱双向链路=公用信箱根据通信链路容量无容量通信链路=无缓冲区有容量通信链路=有缓冲区,2.6进程通信,消息传递系统进程同步方式发送进程阻塞、接收进程阻塞发送进程和接收进程平时都处于阻塞状态，直到有消息传递。主要用于进程间紧密同步，发送进程和接收进程之间无缓冲时。这种同步方式叫汇合（rendezrous）发送进程不阻塞、接收进程阻塞发送进程和接收进程均不阻塞,2.6进程通信,2.6进程通信,消息缓冲队列通信机制通过内存中公用的消息缓冲区进行进程通信，属于直接通信方式。发送过程发送：申请一个缓冲区，并把自己的进程标识符和消息内容填入缓冲区，然后将该消息缓冲区，插入到接收进程的消息缓冲队列中；接收时：从自己的消息缓冲队列中摘下一个消息缓冲区，取出消息，然后把消息缓冲区归还给系统。,2.6进程通信,消息缓冲队列通信机制消息缓冲队列通信机制中的数据结构消息缓冲区PCB中增加的数据项,Typemessage_buffer=recordsender;发送进程标识符size;消息长度text;消息正文next;指向下一个消息缓冲区,mq：消息缓冲队列队首指针mutex：消息队列的互斥信号量；sm：消息队列的资源信号量,2.6进程通信,消息缓冲队列通信机制发送原语receiver为接收进程的标识符；a为发送区地址。,proceduresend(receiver,a)begingetbuf(a.size,i);根据a.size申请消息缓冲区i；i.sender:=a.sender;i.text:=a.size;i.next:=0;getid(PCBset,receiver,j);获得接收进程receiver的内部标识符jwait(j.mutex);insert(j.mq,i);将消息缓冲插入接收进程的消息缓冲队列mq中signal(j.mutex);signal(j.sm)end,2.6进程通信,消息缓冲队列通信机制接收原语b为接收区地址。,procedurereceive(b)beginj:=current;j为接收进程内部的标识符；wait(j.sm);wait(j.mutex);remove(j.mq,i);将消息队列中第一个消息移出；signal(j.mutex);b.sender=i.se