操作系统原理第四章并发处理B.ppt

1 第四章 并发处理24.5 进程互斥 4.5.2 锁和上锁、开锁操作这样当一个进程使用某个临界资源之前必须完成下列操作：1、考察锁位的值；2、若原来的值是为“0”，将锁位置为“1”（占用该资源）；3、若原来值是为“1”，（该资源已被别人占用），则转到1。当进程使用完资源后，将锁位置为“0”，称为开锁操作。34.5 进程互斥 4.5.2 锁和上锁、开锁操作44.5 进程互斥 4.5.2 锁和上锁、开锁操作 改进的算法54.5 进程互斥4.5.3 用上锁原语和开锁原语实现互斥假设有两个进程共享打印机，两个进程中使用打印机的程序段为临界区。为保证打印的正确，设置打印机的锁位print，其初值为“0”，表示打印机可。64.5 进程互斥4.5.3 用上锁原语和开锁原语实现互斥74.6 信号灯和P、V操作4.6.1 信号灯的概念信号灯的概念是由Dijkstra提出的（1968）。他把互斥的关键概念抽象到信号量这个概念中，信号量是一个被保护的变量，只有P操作、V操作和一种称为信号量初始化操作才能访问和改变它的值。84.6 信号灯和P、V操作4.6.1 信号灯的概念 信号灯的定义：信号灯是一个确定的二元组（s,q），s 是一个具有非负初值的整型变量，q 是一个初始状态为空的排队站。S代表资源的实体。在实际应用中应准确地说明s的意义和初值，每个信号灯都有一个队列，其初始状态为空。94.6 信号灯和P、V操作 4.6.2 P、V操作信号灯的值仅能由P、V操作来改变，对信号灯的P操作记为：P(S)，P操作是一个原子操作。对信号灯的V操作记为：V(S),V操作是一个原子操作。在实际操作系统中，一般情况下是由机器硬件提供P、V操作的指令，当然是原子操作，若机器不提供P、V操作的指令，则操作系统提供P、V操作原语。104.6 信号灯和P、V操作 4.6.2 P、V操作P操作：（1）s值减1；（2）若相减结果大于等于0，则进程继续执行；（3）若结果小于0，则该进程挂起。注：推起该进程包括：保留调用进程CPU现场；置“等待”状态；入等待队列；转进程调度；114.6 信号灯和P、V操作 4.6.2 P、V操作V操作：（1）s值加1；（2）若相加结果大于0，进 程继续执行；（3）否则，唤醒一个（或多个）等待该信号灯的进程，然后本进程继续执行。124.6 信号灯和P、V操作4.6.3 用信号灯实现进程互斥用两个进程共享打印机的例子设信号灯print表示打印机，初值为1，表示打印机可用(也可理解为有一台打印机)。(print也是用于互斥的信号灯，教材上设置为mutex。)134.6 信号灯和P、V操作4.6.3 用信号灯实现进程互斥144.7 进程同步4.7.1 同步的例子引例 1：两位同学约好星期天去东湖，早上8:00在校门口，不见不散。当一个同学先来到校门口，要等另一个同学，到齐后一道打的去东湖154.7 进程同步 4.7.2 同步的概念互斥的概念来自于诸进程对独占使用资源（设备）的竞争，同步来源于多个进程的合作。在人类社会中竞争与合作是永恒的。同步：所谓同步就是并发进程在一些关键点上可能需要相互等待与互通消息，这样的相互制约关系称为进程同步。164.7 进程同步 4.7.3 用信号灯实现进程的同步在操作系统中，同步有各种各样，但归纳起来有两类：诸进程合作完成某工作的逻辑顺序，如考研问题；对系统资源的共享。如两个进程共享一个缓冲区完成誊抄问题174.7 进程同步 4.7.3 用信号灯实现进程的同步（一）合作进程的执行次序 用进程流图来描述诸进程合作完成某一任务的次序，其规则如下184.7 进程同步 4.7.3 用信号灯实现进程的同步用信号灯及P、V操作来描述左图1、说明进程的同步关系 进程P1、P2可并行执行，P3的执行必须等待P1、P2都完成后才能开始执行。2、设置信号灯，说明含义、初值。s13=0 表示进程P1尚未执行完成；s23=0 表示进程P2尚未执行完成；194.7 进程同步 4.7.3 用信号灯实现进程的同步204.7 进程同步 4.7.3 用信号灯实现进程的同步(二）共享缓冲区的合作进程的同步 设有一个缓冲区buffer，大小为一个字节，CP进程不断产生字符，送buffer，IOP进程从buffer中取出字符打印。如不加控制，会有多种打印结果，这取决于这两个进程运行的相对速度。在这众多的打印结果中，只有CP、IOP进程的运行刚好匹配的一种是对的，其它均为错误，并且不能重现。214.7 进程同步 4.7.3 用信号灯实现进程的同步要保证打印结果的正确，CP、IOP必须遵循以下同步规则：(1)当CP把结果送入buffer后，IOP才能从buffer中取，否则IOP必须等待；(2)当IOP从buffer中取走数据后，CP才能将新产生数据送buffer，否则也必须等待。解决这个问题的步骤：(1)分析问题，弄清楚同步关系，如上分析；(2)设置信号灯，说明含义、初值；(3)写出程序描述。224.7 进程同步 4.7.3 用信号灯实现进程的同步234.7 进程同步4.7.4 生产者消费者问题我们把上面的例子扩充，假定缓冲区buffer是一个有界缓冲区，可存放n个数据，同时假定有n个CP进程不断地产生数据，并送buffer；有m个IOP进程从缓冲区中取数据打印。在我们生活中有很多这样的例子。244.7 进程同步4.7.4 生产者消费者问题对于生产者进程：产生一个数据，当要送入缓冲区时，要检查缓冲区是否已满，若未满，则可将数据送入缓冲区，并通知消费者进程；否则，等待；对于消费者进程：当它去取数据时，要看缓冲区中是否有数据可取，若有则取走一个数据，并通知生产者进程，否则，等待。这种相互等待，并互通信息就是典型的进程同步。同时，缓冲区是个临界资源，因此，诸进程对缓冲区的操作程序是一个共享临界区，因此，还有个互斥的问题。254.7 进程同步4.7.4 生产者消费者问题264.7 进程同步4.7.4 生产者消费者问题274.7 进程同步4.7.4 生产者消费者问题28补充题1：有十个读者和两个编辑同时处理一篇文章，对于读操作是可以同时进行的，若有读者正在读这篇文章，编辑就不能工作，若编辑正在处理这篇文章，读者就不能作读操作，编辑与编辑的工作也是互斥的，试用信号灯及P、V操作写出读者与编辑之间协同工作的程序描述。2930解：mutex:用于读者与编辑、编辑与编辑的互斥信号灯，初值为1；mutex1:用于对couter操作的互斥的信号灯，初值为1。31补充题2：理发师睡觉问题理发店里有一位理发师、一把理发椅和n把供顾客等候理发坐的椅子。如果没有顾客，则理发师便在理发椅上睡觉，当一顾客来到时，他必须先叫醒理发师，如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，他们就坐下来等，如果没有空椅子，他就离开。用信号灯和P、V操作写出理发师和顾客行为的程序描述。32补充题3：哲学家就餐问题五个哲学家围坐在一个园桌周围，每个哲学家面前都有一盘通心面，由于面条很滑，所以要两把叉子才能夹住。相邻两个盘子间有一把叉子，餐桌如右图。哲学家的生活包括两种活动：即吃面条和思考。当哲学家觉得饿时，他就试图分两次去取他左边和右边的叉子，每次拿一把，不分先后次序，如果成功，他就开始吃面条，吃完后放下叉子，继续思考。试用信号灯及P、V操作写出哲学家行为的程序描述，要求不能让某个（或某些哲学家饿死）。33补充题3：哲学家就餐问题344.9 UNIX系统的进程管理4.9.1 UNIX系统的进程的图象(image)（一）进程图象的组成 1、进程控制块PCB基本进程控制块 proc结构：存放进程的最基本的控制和管理信息，不论该进程是否处于运行状态，系统都要访问的信息，必须常驻内存；扩充进程控制块 user结构：存放进程的管理和控制信息，这些信息只有当进程处于运行状态时，系统才访问，不一定常驻内存。354.9 UNIX系统的进程管理 4.9.1 UNIX系统的进程的图象2、正文段（共享正文段）它是进程执行程序的一部分，可为多个进程共享执行，作为正文段的程序必须是可重入的。3、数据段包括：正文段程序的处理对象数据、进程执行程序（私有）及数据和ppda(进程数据区）。4、用户栈364.9 UNIX系统的进程管理 4.9.1 UNIX系统的进程的图象（二）UNIX系统进程数据结构1、proc结构,在UNIX系统的/sys/proc.h文件中；2、user结构,在UNIX系统的/sys/user.h文件中；3、text结构（用来管理正文段的数据结构）text结构在UNIX系统的/sys/text.h文件中374.9 UNIX系统的进程管理 4.9.2 UNIX进程的状态及变迁一、UNIX进程的两种运行态 核心态：指进程正在执行UNIX核心程序；用户态：指进程正在执行用户程序；384.9 UNIX系统的进程管理 4.9.2 UNIX进程的状态及变迁在UNIX系统中，一个进程有两种态，在执行用户程序时称为用户态，当发生中断（或自陷）时，自动转去处理中断，即开始执行中断处理程序（UNIX核心代码），进程由用户转为核心态，处理完中断完后返回用户程序执行，进程又由核心态转为用户态。在UNIX系统中除0进程外的所有进程都有两种态。394.9 UNIX系统的进程管理 4.9.2 UNIX进程的状态及变迁二、UNIX进程树404.9 UNIX系统的进程管理 4.9.2 UNIX进程的状态及变迁二、UNIX进程树0进程：系统初启时由系统初启程序建立，完成系统初启的相应工作后，创建1进程；然后的工作有两项，其一是进程交换（进程图象的管理）；其二是进程切换（进程调度）。1 进程：为系统的每个联机终端创建一个终端进程，然后就做托管工作。2、3、n、n+1进程：终端进程，执行程序是shell，该进程执行是接受和执行用户键入的shell命令，或shell命令程序。用户创建的进程：用户的shell命令或shell程序所创建的进程；用户在其程序中创建的进程。414.9 UNIX系统的进程管理 4.9.2 UNIX进程的状态及变迁三、UNIX进程状态（一）运行状态运行状态表示进程正在处理机上运行。其特征是：p_stat 为SRUNp_flag 中号SLOAD位为1，表示该进程图象在内存（在目前的UNIX系统中表示该进程的U区在内存）。核心态下的内存管理机制的指针指向ppda，即该进程的USER结构。核心态运行用户态运行424.9 UNIX系统的进程管理 4.9.2 UNIX进程的状态及变迁三、UNIX进程状态（二）就绪状态在内存中就绪：指进程处于就绪状态，且进程图象在内存（现代：进程的U区在内存）；就绪且换出：指进程处于运行状态，且进程图象不在内存。p_stat为SRUN；p_flag的SLOAD为1，表示在内存中就绪；为0，表示就绪且换出；核心态下的内存管理机制的指针不指向ppda。434.9 UNIX系统的进程管理 4.9.2 UNIX进程的状态及变迁三、UNIX进程状态（三）睡眠状态睡眠状态是进程等待某事件发生而被迫暂时让出处理机时所取的状态。p_stat为SSLEEP 高优先级睡眠状态；SWAIT 低优先级睡眠状态；p_flag中的SLOAD为1，表示该进程图象在内存，否则不在内存。在UNIX系统中，当进程进入睡眠状态时，系统会根据该进程等待事件的轻重缓急的程度赋予不同的优先数，该进程在被唤醒后，就以系统赋予的优先数参与处理机的竞争。若系统赋予的优先数是小于0（负数），进程进入高优先级睡眠状态，否则，进程进入高优先级睡眠状态。进程的优先数:p_pri(-127127)444.9 UNIX系统的进程管理 4.9.2 UNIX进程的状态及变迁三、UNIX进程状态进程进入高优先级睡眠的原因：（1）0进程（100优先数）；（2）因资源请求得不到满足的进程，磁盘(80)，打印机 (20），；（3）等待块设备I/O完成的进程，（50）。进程进入低优先级睡眠的原因：(1）因等待字符设备I/O完成的进程，（020的优先数）；(2)所有处于用户态运行的进程，优先数一般情况下为大于100。这样做的目的是为什么？为使系统资源得到充分的利用，换句话说，是为了提高系统资源的使用效率。454.9 UNIX系统的进程管理 4.9.2 UNIX进程的状态及变迁三、UNIX进程状态（四）创建状态父进程创建子进程时所取的状态，目的是保证子进程能完全复制父进程的图象。在UNIX系统中，父进程创建一个子进程时，子进程要复制父进程的全部的进程图象（除proc结构外），当有内存空间时，能很快完成复制工作，但若无内存空间时，就要在交换区中建立子进程图象的复本，这时父进程将自己置为创建状态，以保证自己的图象不被调出内存。464.9 UNIX系统的进程管理 4.9.2 UNIX进程的状态及变迁三、UNIX进程状态（五）僵死状态僵死状态是子进程等待父进程作善后处理时所处的状态。特征：进程转换成僵死状态后，就不能再转换成其它任何状态；进程已释放它占用的所有资源（除proc结构外）。p_stat 为SZOMB(zombi,zombie 还魂尸，僵尸）。474.9 UNIX系统的进程管理 4.9.2 UNIX进程的状态及变迁三、UNIX进程状态（六）进程状态变迁484.9 UNIX系统的进程管理 4.9.3 进程创建进程控制的操作有进程创建fork()、进程睡眠sleep()、进程唤醒wakeup()、进程终止exit()和等待进程终止wait()。进程创建fork()调用形式：pid=fork();功能：创建一个子进程，被创建的子进程是父进程进程图象的一个副本（除proc结构外），在UNIX系统中，除了0进程外，其它进程都是调用进程创建系统调用创建的。返回：1 创建失败 0 从子进程返回 0 从父进程返回，且返回值为子进程号494.9 UNIX系统的进程管理 4.9.3 进程创建执行这个程序有两种可能的结果：从子进程返回：打印:这是子进程的执行程序。这是父、子进程的共有执行程序从父进程返回：打印：这是父进程执行程序。这是父、子进程的共有执行程序504.9 UNIX系统的进程管理 4.9.3 进程创建系统调用的C语言形式在编译时以调用变成汇编形式，fork的汇编子程序中包含有：sys fork clr r0子进程从sys fork指令返回时执行clr r0指令，所以子进程从fork()中返回值为0；父进程处理部分使栈中保护的pc值加2，于是，从trap处理返回时跳过clr r0指令，所以父进程从fork中返回值为子进程的pid。514.9 UNIX系统的进程管理 4.9.3 进程创建524.9 UNIX系统的进程管理 4.9.3 进程创建534.9 UNIX系统的进程管理 4.9.3 进程创建 指子进程这时在磁盘上就绪，当某时刻子进程被调入内存后，被调度到，当调度程序发现p_flag为SSWAP，表示该进程是从磁盘上调入的且是第一次被调度，从u.u_ssav中恢复栈指针和环境指针，要直接从调用newproc处作非常返回。54 4.9.4 进程的终止与等待（一）进程自我终止例子：假定copy是一个将源文件复制到目标文件的可执行程序,且该执行文件在当前目录中。554.9.4 进程的终止与等待UNIX系统中进程的自我终止就是指进程撤消操作，格式为：exit(status);其中：status 是终止进程向其父进程传递的参数。564.9.4 进程的终止与等待(二）等待进程终止一个进程创建了子进程后，在完成它的工作后，就等待子进程的终止，这是一对同步操作。格式：pid=wait(stat_addr);其中：stat_addr:是一个地址指针，它将含有子进程的退 出状态码；pid:僵死子进程号；wait和exit是UNIX系统向用户程序提供的进程实施同步的主要手段。574.9.4 进程的终止与等待584.9.5 进程睡眠与唤醒 进程因等待某事件发（或申请资源得不到满足、或等待I/O完成），进程由运行状态转换成睡眠状态，这个工作由进程睡眠操作sleep()完成，当等待的事件发生后，要把等待在该事件上的进程唤醒，即将进程的状态置为就绪状态。594.9.5 进程睡眠与唤醒（一）进程睡眠 sleep(pri,chan);其中：pri:系统将给睡眠进程设置的优先数，当该进程被唤醒后，进程就以这个优先数去参与处理机的竞争；chan:进程睡眠的原因。604.9.5 进程睡眠与唤醒(二）进程唤醒 在UNIX系统中进程唤醒操作将唤醒所有等待在相应事件上的所有进程，其格式如下：wakrup(chan)；chan:与sleep中的相同61