操作系统课件第二章进程管理.ppt

2023/11/3,1,第二章进程管理,2023/11/3,2,为什么要引入进程？,为了提高系统的吞吐量和设备（CPU和I/O设备）的利用率，OS中引入了多道程序设计技术。多道批处理系统和分时系统中，程序不能独立运行，作为资源分配和独立运行的基本单位为进程。问题：为什么？什么是进程？,2023/11/3,3,为什么要引入进程？,程序执行方式顺序执行（无OS,单道批处理系统）并发执行（多道）程序执行方式的分析工具前趋图,2023/11/3,4,为什么要引入进程？,前趋图(Precedence Graph)是一个有向无循环图，记为DAG(Directed Acyclic Graph)，用于描述进程之间执行的前后关系。结点：程序段，进程或者语句；每个结点还包含一个Weight有向边：表示两个结点之间存在的偏序(Partial Order)或前趋关系(Precedence Relation)“”。如果Pi,和Pj存在偏序关系，可写成PiPj，,2023/11/3,5,为什么要引入进程,前趋图说明前趋图中必须不存在循环，为什么？初始结点(Initial Node)终止结点(Final Node),是前趋图吗？,2023/11/3,6,为什么要引入进程,前趋图是存在偏序关系结点的集合,左图可以表示为：G=P,P=P1,P2,P3,P4,P5,P6,P7,P8,P9=(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,P6),(P4,P7),(P5,P8),(P6,P8),(P7,P9),(P8,P9),2023/11/3,7,为什么要引入进程,练习画出前趋图S1:a=5-xS2:b:=a.xS3:c=4.xS4:d=b+cS5:e=d+3,2023/11/3,8,为什么要引入进程,程序的顺序执行及其特征仅当前一操作(程序段)执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。S1:a=x+y;S2:b=a-5;S3:c=b+1;,2023/11/3,9,图 2-1 程序的顺序执行,为什么要引入进程,2023/11/3,10,为什么要引入进程,程序顺序执行时的特征顺序性：一个程序开始执行必须要等到前一个程序已执行完成封闭性：程序一旦开始执行，其计算结果不受外界因素影响可再现性：程序的结果与它的执行速度无关（即与时间无关），只要给定相同的输入，一定会得到相同的结果。,2023/11/3,11,为什么要引入进程,为什么要引入进程程序的并发执行及其特征并发环境：在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的,2023/11/3,12,为什么要引入进程,引入并发的目的：引入并发是为了提高资源利用率，从而提高系统效率并发与并行概念的区别：oncurrency/parallel,2023/11/3,13,为什么要引入进程,2023/11/3,14,在该例中存在下述前趋关系：IiCi，IiIi+1,CiPi,CiCi+1，PiPi+1而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之间，可以并发执行。,为什么要引入进程,2023/11/3,15,为什么要引入进程,程序并发执行时的特征间断性执行停执行失去封闭性 不可再现性并发程序执行的结果与其执行的相对速度有关，是不确定的,2023/11/3,16,例如，有两个循环程序A和B，它们共享一个变量N。程序A每执行一次时，都要做N=N+1操作；程序B每执行一次时，都要执行Print(N)操作，然后再将N置成“0”。程序A和B以不同的速度运行。(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。,为什么要引入进程,2023/11/3,17,为什么要引入进程,与时间有关的错误一飞机订票系统，两个终端，运行T1、T2进程T1:T2:.Read(x);(1)Read(x);(4)if x=1 then if x=1 then x:=x-1;(2)x:=x-1;(5)write(x);(3)write(x);(6).,2023/11/3,18,为什么要引入进程,顺序和并发执行比较,2023/11/3,19,为什么要引入进程,程序并发执行的条件概念读集R（si）写集W（si）程序可并发执行条件（Bernstein条件）R(p1)W(p2)R(p2)W(p1)W(p1)W(p2)为什么无R(p1)R(p2)呢？分析前面订票程序。例P1:N:=N+1P2:PRINT(N);N:=0练习：s1:b=a.xs2:c=4.xs3:d=b+c,2023/11/3,20,为什么要引入进程,在多道程序环境下，通常的程序不能直接参与并发执行，因为结果不可再现的。所以在在OS中为了能对并发执行的程序加以描述和控制，引入了进程（process）的概念,2023/11/3,21,为什么要引入进程,OS 对进程的要求OS 必须交替执行多个进程，以便最大程度的使用CPU，同时提供合理的响应时间OS 必须将资源分配给进程，同时避免死锁OS必须支持进程间通信以及用户进程创建Chap2：进程的描述和控制；进程的同步和通信Chap3：进程的调度；死锁,2023/11/3,22,进程的基本概念,定义：Process 进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位,2023/11/3,23,进程同程序的比较,程序是指令的有序集合，其本身没有任何运行的含义，是一个静态的概念。而进程是程序在处理机上的一次执行过程，它是一个动态的概念。程序可以作为一种软件资料长期存在，而进程是有一定生命期的。程序是永久的，进程是暂时的。进程更能真实地描述并发，而程序不能进程是由程序和数据两部分组成的进程具有创建其他进程的功能，而程序没有同一程序同时运行于若干个数据集合上，它将属于若干个不同的进程。也就是说同一程序可以对应多个进程,2023/11/3,24,进程的特征,动态性：进程是程序的执行并发性：多个进程可同存于内存中，能在一段时间内同时运行独立性：独立运行的基本单位，独立获得资源和调度的基本单位。异步性：各进程按各自独立的不可预知的速度向前推进结构特征：由程序段、数据段、进程控制块（Process Control Block,PCB）三部分组成,2023/11/3,25,进程的状态及转换,进程有三种基本状态不同系统设置的进程状态数目不同(LINUX)TASK_RUNNING(就绪或(执行):RTASK_INTERRUPTIBLE(可中断等待）.STASK_UNINTERRUPTIBLE(不可中断等待):DTASK_STOPPED(暂停).TTASK_ZOMBIE(僵死)Z,2023/11/3,26,进程的三种基本状态,就绪状态（Ready）：存在于处理机调度队列中的那些进程，它们已经准备就绪，一旦得到CPU，就立即可以运行。这些进程所处的状态为就绪状态。运行状态（Running）：正在运行的进程所处的状态为运行状态。等待状态（Wait/Blocked）：若一进程正在等待某一事件发生（如等待输入输出工作完成），这时，即使给它CPU，它也无法运行，称该进程处于等待状态、阻塞、睡眠、封锁状态。,2023/11/3,27,进程的状态图,2023/11/3,28,进程转换,就绪-运行调度程序选择一个新的进程运行运行-就绪运行进程用完了时间片运行进程被中断，因为一高优先级进程处于就绪状态,2023/11/3,29,进程转换（续）,运行-等待当一进程必须等待时OS尚未完成服务对一资源的访问尚不能进行初始化I/O 且必须等待结果等待某一进程提供输入(IPC)等待-就绪当所等待的事件发生时,2023/11/3,30,五状态进程模型,2023/11/3,31,创建(新new)状态,OS 已完成为创建一进程所必要的工作已构造了进程标识符已创建了管理进程所需的表格但还没有允许执行该进程(尚未同意)因为资源有限,2023/11/3,32,终止（退出exit)状态,中止后进程移入该状态它不再有执行资格表格和其它信息暂时由辅助程序保留例子:为处理用户帐单而累计资源使用情况的财务程序当数据不再需要后，进程(和它的表格)被删除,2023/11/3,33,七状态进程模型,2023/11/3,34,挂起状态挂起进程在操作系统中可以定义为暂时被淘汰出内存的进程，机器的资源是有限的，在资源不足的情况下，操作系统对在内存中的程序进行合理的安排，其中有的进程被暂时调离出内存，当条件允许的时候，会被操作系统再次调回内存，重新进入等待状态或者就绪状态 为什么要引入挂起状态？（调节负载，对换，父进程，操作系统，终端用户）,2023/11/3,35,新状态转换(中期调度),阻塞-阻塞挂起当所有进程都阻塞，OS会安排空间让一就绪进程进入内存阻塞挂起-就绪挂起当等待的事件发生时(状态信息已在OS中)就绪挂起-就绪当内存中没有就绪进程时就绪-就绪挂起(较少见)当没有被阻塞的进程，而为了性能上的考虑，必须释放一些内存时,2023/11/3,36,思考题,在单处理机计算机系统中，如果有n个进程，运行状态的进程最多几个？最少几个？等待状态的进程最多几个？最少几个？就绪状态的进程最多几个？最少几个？有没有这样的状态转换，等待运行，就绪等待,2023/11/3,37,进程控制块（Process Control Block）,为了描述一个进程和其它进程以及系统资源的关系，为了刻画一个进程在各个不同时期所处的状态，人们采用了一个与进程相联系的数据块，称为进程控制块（PCB）。系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志进程与PCB是一一对应的常驻内存,2023/11/3,38,进程标识符(在PCB中),可使用一些数字标识符统一进程标识符(必然的)索引至(直接或间接)主进程表用户标识符与某个作业对应的用户创建本进程的某个进程的标识符,2023/11/3,39,处理器状态信息(在PCB中),处理器寄存器内容用户可见寄存器控制和状态寄存器栈指针程序状态字(PSW)包含状态信息例子:在Pentium机中的EFLAGS寄存器,2023/11/3,40,进程控制信息(在PCB中),调度和状态信息进程状态(如:运行，就绪，阻塞.)进程优先级该进程在等待的事件(若被阻塞)数据结构信息进程可能需要有指向其他PCB的指针,父-子进程关系及其它结构,2023/11/3,41,进程控制信息(在PCB中),进程间通信IPC可能需要标志和信号进程特权如:访问特定的内存地址.存储管理指向赋予该进程的段/页表的指针所拥有的资源和使用情况使用中的资源:打开的文件，I/O设备.(CPU,I/O.)的时间使用史,2023/11/3,42,PCB表：系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表 PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度,PCB表组织方式,2023/11/3,43,链接结构,相同状态的进程PCB组成一个链表，不同状态对应多个不同的链表就绪链表、阻塞链表,2023/11/3,44,2023/11/3,45,索引结构,对具有相同状态的进程，分别设置各自的PCB索引表，表明PCB在PCB表中的地址,2023/11/3,46,2023/11/3,47,进程队列,不同状态进程分别组成队列运行队列、就绪队列、等待队列,2023/11/3,48,2023/11/3,49,stuct task_struct 在 include/linux/sched.h中定义，占1680字节task 数组 在 kernel/sched.c中定义使用，长度5121进程标识uid，gid用户标识，用户组标识euid，egid有效用户、用户组标识suid，sgid保留真正的uid，gidfsuid，fsgid文件系统验证检查的uid，gidgroupsNGROUPS用户组标识数组pid，pgrp唯一进程标识号，进程组号,Linux进程 进程控制块(PCB),2023/11/3,50,2调度信息state进程状态flags，ptrace进程标志，进程跟踪标志priority，rt priority 进程优先级（每次获得CPU可用时间数），实时进程优先级policy调度策略 SCHED OTHER，SCHED FIFO，SCHED RRcounter还可运行时间数，初值为priority,Linux进程 进程控制块(PCB),2023/11/3,51,3进程队列指针next task，prev task所有PCB链表前后向指针pidhash next，pidhash prev链入hash表的前后指针p opptr，p pptr原始父进程，父进程指针p cptr，p ysptr，p osptr 子进程，新老兄弟进程指针,Linux进程 进程控制块(PCB),2023/11/3,52,4信号处理和信号量机制进程通信signal挂起信号码blocked信号的位掩码signal struct*sig信号处理程序入口semsleeping信号量等待队列semundo信号量undo操作链,Linux进程 进程控制块(PCB),2023/11/3,53,5内存管理struct mm struct*mm 存储分配数据结构指针struct mm struct*active mm 内核线程所用存储分配数据结构指针swappable内存页面是否可以换出min flt，maj flt进程累计缺页次数nswap进程累计换出页面数swap cnt下一次循环最多可换出的页面数,Linux进程 进程控制块(PCB),2023/11/3,54,2023/11/3,55,2023/11/3,56,6文件系统管理struct fs struct*fs根目录struct files struct*files进程当前打开文件link count文件链的数目locks上锁文件个数7 时间数据real timer一种定时器结构it real value，it real iner 用于软件定时it virl value，it virl iner用户态执行时间的软件定时it prof value，it prof iner核心态执行时间的软件定时per cpu utime，per cpu stime运行的时间片数*times用户态、核心态的运行时间,Linux进程 进程控制块(PCB),2023/11/3,57,8运行数据struct thread struct threadCPU状态信息has cpu，processor正在使用的CPU，是否占有CPUcomm运行的可执行文件的文件名binfmt可执行文件的文件格式rlim 受控资源的可有最大数目，当前最大数目exit code进程退出的返回代码 exit signal 进程退出时引起错误的信号名,Linux进程 进程控制块(PCB),2023/11/3,58,Linux进程状态图,2023/11/3,59,进程控制,进程的控制是进程管理中的最基本的功能。创建、终止、阻塞、唤醒、挂起、激活进程控制和进程状态转换之间的关系进程的控制是通过操作系统内核 原语来实现的。,2023/11/3,60,OS内核,现代OS普遍采用层次结构，将OS的功能设置在不同不同的层次中。OS内核是紧靠硬件的部分。它通常包括：与硬件紧密相关的模块（中断处理程序、设备驱动程序）运行频率较高的模块（时钟管理、进程调度、许多模块公用的基本操作）OS内核常驻内存，以便提高OS效率OS受到特殊的保护，OS内核运行在系统态（核心态、管态）相对应，用户程序运行在用户态（目态），它不能趋执行OS指令和访问OS区域，防止了用户程序对OS的破坏。,2023/11/3,61,OS内核包含以下功能支撑功能中断处理时钟处理原语操作资源管理功能进程管理存储器管理设备管理,返回,2023/11/3,62,原语,原语是机器指令的延伸。由若干机器指令构成，用来完成完成特定功能的程序原子，不可被分割。为了保证操作的正确性，原语在执行过程中是不可被中断的。,返回,2023/11/3,63,进程的创建,进程图：描述进程家族关系的有向树结点：进程有向边：父子关系LINUX中进程家族关系图,2023/11/3,64,进程的创建,引起进程创建的事件用户登录作业调度提供服务系统建立新进程应用请求用户建立新进程 创建的过程：（创建原语CREAT）,2023/11/3,65,2023/11/3,66,终止的原因：正常结束 非正常结束出错，外界强迫终止过程：（终止原语）,进程控制 进程的终止（撤消）,2023/11/3,67,进程控制 进程的终止（撤消）,2023/11/3,68,期望等待某个事件的发生：请求系统服务（I/O）进程同步 空闲（C/S方式）阻塞过程：（block原语）,进程控制 进程阻塞,2023/11/3,69,进程控制 进程的唤醒,阻塞期望的事件发生，由其它进程（或系统）调用唤醒原语Wakeup（）,2023/11/3,70,suspend（）原语,进程控制 进程的挂起,2023/11/3,71,active（）原语,进程控制 进程的激活,2023/11/3,72,LINUX创建进程的方法,使用系统调用FORKfork()创建一个子进程#include pid t fork（void）返回值：失败-1成功子进程pid（父进程中）0（子进程）Fork系统调用的功能:通过对父亲进程的拷贝建立子进程，他们有相同的变量值，打开文件也相同，还有其它一些相同的属性。LINUX中有关进程创建的源代码,2023/11/3,73,.pid=fork();if(!pid)printf(Im the child process!n);else if(pid0)printf(Im the parent process!n);else printf(Fork fail!n);,2023/11/3,74,思考题下面程序执行后能创建多少个进程（不包括现有进程）？并画出它们的家族关系图pid1fork（）；Pid2fork（）；,2023/11/3,75,=#include#include pid_t vfork(void);-*不复制父进程的全部地址空间.*vfork 保证子进程首先运行,直到调用 exec 或 exit 之后,父进程才能得到运行机会.=,2023/11/3,76,exec 函数组,=#include extern char*environ;int execl(const char*path,const char*arg,.);int execlp(const char*file,const char*arg,.);int execle(const char*path,const char*arg,.,char*const envp);int execv(const char*path,char*const argv);int execvp(const char*file,char*const argv);int execve(const char*filename,char*const argv,char*const envp);-*以可变参数形式传递命令行时,最后一个参数应该为 NULL 指针.*execve 是实际的系统调用,而其他的函数以库函数实现,最终要调用 execve.=,2023/11/3,77,execl(/bin/ls,ls,-l,-color,NULL);,2023/11/3,78,exit,exit 调用由 atexit 注册的清除函数,并关闭所有的标准 I/O 流进程的退出状态非常重要.一般以 0 值表示正常退出=#include void exit(int status);=,2023/11/3,79,6.2.4wait 函数进程的退出状态必须用 wait 函数由父进程获取,否则形成僵尸进程 wait/waitpid=#include#include pid_t wait(int*status)pid_t waitpid(pid_t pid,int*status,int options);-*wait 等待某个子进程退出.*waitpid 可等待指定的子进程退出-,2023/11/3,80,shell 执行过程,2023/11/3,81,getpid()获得当前进程的pidgetppid()获得父进程的pid#include pid t getpid()pid t getppid()sleep()阻塞，直到指定时间后，或其它信号唤醒（非系统调用）#include unsigned int sleep(unsigned int seconds)返回值：0指定时间用完0剩余时间数，因其它原因被唤醒,进程控制提供的系统调用,2023/11/3,82,clone()创建一个线程#includeint clone(int(*fn),void*child stack，int flags，void*arg)fn线程执行的函数入口地址，终止时的状态值arg入口函数参数child stack线程堆栈flags和父进程共享标志CLONE VM 共享内存，结构mem structCLONE FS共享文件系统CLONE FILES共享所打开的文件CLONE SIGHAND共享信号处理句柄,进程控制提供的系统调用,2023/11/3,83,进程同步,进程间的相互作用进程间的联系进程的同步机制信号量及P.V操作（解决进程同步互斥问题）,2023/11/3,84,进程间的联系,相交进程与无关进程相交进程：指多个并发进程在逻辑上有某种联系无关进程（不相交进程）：在逻辑上无任何联系的进程,2023/11/3,85,直接作用和间接作用直接作用：进程间的相互联系是有意识的安排的，直接作用只发生在相交进程间InputComputePrint间接作用：进程间要通过某种中介发生联系，是无意识安排的，可发生在相交进程之间，也可发生在无关进程之间,2023/11/3,86,2023/11/3,87,进程的同步（直接作用）,进程的同步：synchronism指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态,2023/11/3,88,例:司机 P1 售票员 P2 while(true)while(true)启动车辆；关门；正常运行；售票；到站停车；开门；,2023/11/3,89,进程的互斥（间接作用）mutual exclusion 由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥临界资源：critical resource 系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量,2023/11/3,90,教材中生产者消费者（PC)问题分析 生产者 消费者(1)register1:=counter;(4)register2:=counter;(2)register1:=register1+1;(5)register2:=register2-1;(3)counter:=register1;(6)counter=register2;Counter的初值为5，则按照以下顺序执行后，123456/456123 counter；142356 counter；124563 counter；124536 counter；142563 counter；,2023/11/3,91,与时间有关的错误:一飞机订票系统，两个终端，运行T1、T2进程T1:T2:.(1)Read(x);(2)Read(x);if x=1 then if x=1 then(3)x:=x-1;(4)x:=x-1;(5)write(x);(6)write(x);.,2023/11/3,92,临界区（互斥区）：critical section一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作 在进程中涉及到临界资源的程序段叫临界区 多个进程的临界区称为相关临界区,2023/11/3,93,a:=a-1 print(a),a:=a+1 print(a),进程的互斥（间接作用）,2023/11/3,94,2023/11/3,95,临界区(critical section),可把一个访问临界资源的循环进程描述如下：repeat critical section;remainder section;until false;,entry section,exit section,2023/11/3,96,使用互斥区的原则：,有空让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入无空等待：不允许两个以上的进程同时进入互斥区多中择一：当没有进程在临界区，而同时有多个进程要求进入临界区，只能让其中之一进入临界区，其他进程必须等待有限等待：任何进入互斥区的要求应在有限的时间内得到满足让权等待：处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权,2023/11/3,97,使用互斥区的原则：前提：任何进程无权停止其它进程的运行 进程之间相对运行速度无硬性规定进程互斥的解决有两种做法:由竞争各方平等协商引入进程管理者，由管理者来协调竞争各方对互斥资源的使用具体方法：硬件（当一个进程进入临界区,就屏蔽所有中断，但成本高）软件（用编程解决，但常常忙等待）,2023/11/3,98,进程互斥的软件方法,通过平等协商方式实现进程互斥的最初方法是软件方法 其基本思路是在进入区检查和设置一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志 其中的主要问题是设置什么标志和如何检查标志,2023/11/3,99,软件解法(1),Turn:能进入临界区进程的编号 while(turni);临界区 turn=j;,2023/11/3,100,软件解法(2),Varflag:array0,1,nof boolean;repeat.Pi:while(flagj);Flagi=true;临界区 flagi=false;,2023/11/3,101,软件解法(3),Pi.Pj.flagi=true;flagj=true;while(flagj);while(flagi);临界区 临界区 flagi=false;flagj=false;.,2023/11/3,102,软件解法(4):,Piflagi:=true;ture=j;while(flagjand turn=j);critical section;flagi:=false;Pj:flagj:=true;ture=i;while(flagiand turn=i);critical section;flagj:=false;,2023/11/3,103,软件解法的缺点：1.忙等待 2.实现过于复杂，需要高的编程技巧,2023/11/3,104,硬件解法(1)“测试并设置”指令,funciton TS(var:lock:boolean):boolean TS:=lock;lock=true;,while TS(lock);临界区 lock=false;,2023/11/3,105,硬件解法(2)“交换”指令,void SWAP(int*a,int*b)int temp;temp=*a;*a=*b;*b=temp;,key=true;do SWAP(,2023/11/3,106,硬件解法(3)“开关中断”指令,进入临界区前执行：执行“关中断”指令离开临界区后执行：执行“开中断”指令,2023/11/3,107,1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test(proberen)和increment(verhogen)）一种卓有成效的进程同步机制最初提出的是二元信号量（互斥）推广到一般信号量（多值）（同步）P、V操作是原语,信号量及P、V操作,2023/11/3,108,信号量：semaphore是一个数据结构整型信号量把信号量定义为一个整型量.除了初始化以外,只能通过PV操作来访问.Wait(s):while(s=0)do no_op;S:=s-1;Signal(s):s:=s+1,2023/11/3,109,记录型信号量定义如下：struc semaphore int value;pointer_PCB queue;信号量说明：semaphore s;,2023/11/3,110,P、V操作为原语操作原语：primitive or atomic action 是由若干多机器指令构成的完成某种特定功能的一段程序，具有不可分割性即原语的执行必须是连续的，在执行过程中不允许被中断 实现：开关中断,2023/11/3,111,信号量的使用：必须置一次且只能置一次初值 初值不能为负数 只能执行P、V操作,2023/11/3,112,P、V操作,P(s)s.value=s.value-;if(s.value 0)该进程状态置为等待状态 将该进程的PCB插入相应的等待队列末尾s.queue;,2023/11/3,113,P、V操作,V(s)s.value=s.value+;if(s.value=0)唤醒相应等待队列s.queue中等待的一个进程 改变其状态为就绪态 并将其插入就绪队列,2023/11/3,114,用P、V操作解决进程间互斥问题,2023/11/3,115,信号量及P、V操作讨论,对于两个并发进程，互斥信号量的值仅取1、0和-1三个值 若1表示没有进程进入临界区若0表示有一个进程进入临界区若-1表示一个进程进入临界区，另一个进程等待进入。,2023/11/3,116,思考,对于N个并发进程，信号量的取值范围是什么，有什么含义。,2023/11/3,117,1)信号量的物理含义：S0表示有S个资源可用S=0表示无资源可用S0则|S|表示S等待队列中的进程个数P(S)：表示申请一个资源 V(S)：表示释放一个资源。信号量的初值应该大于等于0,信号量及P、V操作讨论（续1）,2023/11/3,118,2)P.V操作必须成对出现，有一个P操作就一定有一个V操作当为互斥操作时，它们同处于同一进程当为同步操作时，则不在同一进程中出现如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要。一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前而两个V操作无关紧要,信号量及P、V操作讨论（续2）,2023/11/3,119,3）P、V操作的优缺点优点：简单，而且表达能力强（用P、V操作可解决任何同步互斥问题）缺点：不够安全，P、V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂,信号量及P、V操作讨论（续3）,2023/11/3,120,例:P1:P2:P(s1);P(S2);P(s2);P(S1);cs;CS:V(S2);V(S2);V(S1);V(S1);,2023/11/3,121,信号量集AND型信号量集,AND型信号量集是指同时需要多种资源且每种占用一个时的信号量操作 AND型信号量集的基本思想：在一个原语中申请整段代码需要的多个临界资源，要么全部分配给它，要么一个都不分配AND型信号量集P原语为SwaitAND型信号量集V原语为Ssignal,2023/11/3,122,Swait(S1,S2,Sn)/P原语；if(S1=1,Swait原语,2023/11/3,123,Ssignal(S1,S2,Sn)for(i=1;i=n;+i)+Si;/释放占用的资源；for(在Si.queue中等待的每一个进程P)从等待队列Si.queue中取出进程P;if(判断进程P是否通过Swait中的测试)/重新判断 进程P进入就绪队列;break；else 进程P进入某等待队列；,Ssignal原语,2023/11/3,124,一般“信号量集”,一般信号量集是指同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的信号量处理（一次需要N个某类临界资源时，就要进行N次V操作低效又可能死锁）一般信号量集的基本思路就是在AND型信号量集的基础上进行扩充，在一次原语操作中完成所有的资源申请,2023/11/3,125,进程对信号量Si的测试值为ti（表示信号量的判断条件，要求Si=ti；即当资源数量低于ti时，便不予分配）占用值为di（表示资源的申请量，即Si=Si-di）对应的P、V原语格式为：Swait(S1,t1,d1;.;Sn,tn,dn);Ssignal(S1,d1;.;Sn,dn);,2023/11/3,126,一般“信号量集”可以用于各种情况的资源分配和释放，几种特殊情况：,Swait(S,d,d)表示每次申请d个资源，当少于d个时，便不分配Swait(S,1,1)表示互斥信号量Swait(S,1,0)可作为一个可控开关（当S1时，允许多个进程进入特定区域；当S=0时，禁止任何进程进入该特定区域）,2023/11/3,127,进程同步,同步问题可分为两类：保证一组合作进程按确定的次序执行保证共享缓冲区的合作进程的同步。,2023/11/3,128,合作进程的执行次序,若干个进程为了完成一个共同任务而并发执行，在这些进程中，有些进程之间有次序的要求，有些进程之间没有次序的要求，为了描述方便，可以用一个图来表示进程集合的执行次序。如图,2023/11/3,129,例,如图，试用信号量实现这三个进程的同步。设有两个信号量SB、SC，初值均为Pa：Pb：Pc：P(SB);P(SC)V(SB);V(SC);,2023/11/3,130,【思考题1】,如图，试用信号量实现这三个进程的同步。,2023/11/3,131,解,设有两个信号量S1、S2，初值均为P1：P2：P3：P(S1)V(S1);V(S2);P(S2),2023/11/3,132,【思考题2】,如图，试用信号量实现这6个进程的同步,2023/11/3,133,解,设有5个信号量S2、S3、S4、S5、S6，初值均为P1：P2：P3：P(S2);P(S3)V(S2);V(S3)；V(S4);V(S6);V(S5),P4：P5：P6：P(S4);P(S5);P(S6);P(S5);P(S6);V(S5)；V(S6);,2023/11/3,134,【思考题3】,用P.V操作解决司机与售票员的问题,2023/11/3,135,解,设有两个信号量S1，S2，初值均为0。,2023/11/3,136,共享缓冲区的进程的同步,设某计算进程和打印进程共用一个单缓冲区，进程负责不断地计算数据并送入缓冲区中，进程负责不断地从缓冲区中取出数据去打印。,2023/11/3,137,分析,通过分析可知，、必须遵守以下同步规则：当进程把计算结果送入缓冲区时，IOP进程才 能从缓冲区中取出结果去打印;当IOP进程把缓冲区中的数据取出打印后，进程才能把下一个计算结果送入缓冲区,2023/11/3,138,解,为此设有两个信号量Sa=0，Sb=1，Sa表示缓冲区中有无数据，Sb表示缓冲区中有无空位置。两个进程的同步可以描述如下：,2023/11/3,139,【思考题】,桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子，儿子专等吃盘中的桔子，女儿专等吃苹果。试用P、V操作实现爸爸、儿子、女儿三个并发进程的同步。提示：设置一个信号量表示可否向盘中放水果，一个信号量表示可否取桔子，一个信号量表示可否取苹果。,2023/11/3,140,解,设置三个信号量