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