搜索
（四）进程互斥一、进程互斥的概念1.临界资源例1：两个进程A、B共享一台打印机若不加以控制，两个进程的输出结果可能交织在一起，很难区分。例2：两个进程共享一个变量x设：x代表某航班已卖出的机座数，初值为0。p1和p2为两个售票进程，功能是对共享变量x的值加1。这两个进程在一个处理机C上并发执行，分别具有内部寄存器r1和r2。两进程并发执行的两种可能次序:序列A序列Bp1:r1:=x;p1:r1:=x;r1:=r1+1;p2:r2:=x;x:=r1;r2:=r2+1;P2:r2:=x;x:=r2;r2:=r2+1;p1:r1:=r1+1;x:=r2;x:=r1;执行结果：x=2执行结果：x=1特点：当两个进程公用一个变量时，它们必须顺序的访问，一个进程对公用变量操作完毕后，另一个进程才能去访问和修改这一变量。（1）什么是临界资源我们把一次（一段时间内）仅允许一个进程使用的资源称为临界资源。许多物理设备，如输入机、打印机、磁带机等都具有这种性质。软件资源，如公用变量、数据、表格、队列等也都具有这一特点。（2）什么是临界区每个进程中访问临界资源的那段程序段称为临界区（临界段）。（3）什么是互斥在操作系统中，当某一进程正在访问某一存储区域时，就不允许其他进程来读出或者修改存储区的内容，否则，就会发生后果无法估计的错误。进程间的这种相互制约的关系称为互斥。例如：进程A正在执行CSa段时，进程B就不能进入CSb段执行。进程A进程B……x=0CSbx=x+1CSa……x=x+1…操作系统如何保证进程的互斥呢？（1）保证进入当有若干个进程欲进入临界区时，应在有限的时间内使其进入；（2）排它性每次至多有一个进程处于临界区；（3）有限性进程在临界区内仅逗留有限的时间。?这些原则如何实现呢？二.锁和上锁、开锁操作1.什么是锁用变量w代表某种资源的状态，w称为“锁”2.进程使用临界资源的操作每个临界资源设置一个锁位:0:资源可用1:资源占用。锁操作：1.考察锁位的值；2.若原来的值是为“0”，将锁位置为“1”（占用该资源）；3.若原来值是为“1”，（该资源已被别人占用），则转到1。开锁操作：进程使用完资源后，将锁位置为“0”，称为开锁操作。3.上锁原语和开锁原语（1）上锁原语算法lock输入：锁变量w输出：无{test：if(w为1)gototest;/*测试锁位的值*/elsew=1;/*上锁*/}（2）开锁原语算法unlock输入：锁变量w输出：无{w=0;/*开锁*/}问题：（1）效率低。当锁已上时，当前上锁的进程忙等；（2）无法实现。当锁已上时，当前上锁（原语）的进程占有CPU不放，谁来开锁呢？死锁！改进的算法算法：lock（w）输入：W（锁变量）输出：无{if（w==1）sleep(pri,w);W=1；/*上锁*/}算法：unlock（w）输入：W（锁变量）输出：无{if（等待W队列不空）wakeup(w)；W=0；/*开锁*/}4.用上锁原语和开锁原语实现进程互斥上锁原语开锁原语进入临界区CSa进程A上锁原语开锁原语进入临界区CSb进程B三.信号灯和P、V操作1.什么是信号灯信号灯是整型变量。a≥0时，表示绿灯，进程可继续执行。a0时，表示红灯，进程停止执行。信号灯是一个确定的二元组（s，q），s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。操作系统利用信号灯的值对并发进程和共享资源进行控制和管理。注意：创建信号灯时，应准确说明信号灯s的意义和初值（这个初值绝不能为负值）。2.P、V操作信号灯的值只能由P、V操作来改变。（1）P操作P操作定义对信号灯s的P操作记为P（s）。P（s）是一个不可分割的原语操作，即取信号灯值减1，若相减结果为负，则调用P（s）的进程被阻，并插入到该信号灯的等待队列中，否则可以继续执行。入口s=s-1s=0入信号灯等待队列置“等待状态”转进程调度返回YN•P操作原语的实现（2）V操作V操作定义对信号灯s的V操作记为V（s）。V（s）是一个不可分割的原语操作，即取信号灯值加1，若相加结果大于零，进程继续执行，否则，要帮助唤醒在信号灯等待队列上的一个进程。入口s=s+1S=0从该信号灯的等待队列中取出首元素置“就绪状态”转进程调度YN入就绪队列返回•V操作原语的实现3.用信号灯的P、V操作实现进程互斥设：mutex为互斥信号灯，初值为1，表示临界资源未被占用。（1）框图描述P(mutex)V(mutex)进入临界区CSa进程PaP(mutex)V(mutex)进入临界区CSb进程Pb（2）程序描述Main(){intmutex=1;/*互斥信号灯*/cobeginPa（）；Pb（）；coend}Pa(){…P(mutex);CSa;V(mutex);…}Pb(){…P(mutex);CSb;V(mutex);…}用两个进程共享打印机的例子设信号灯print表示打印机，初值为1，表示打印机可用(也可理解为有一台打印机)。(print也是用于互斥的信号灯，教材上设置为mutex。)（3）信号灯可能的取值假设有N个并发进程共用一台打印机，设互斥信号灯mutex的初值为1，则：mutex的取值范围为多少？信号灯的值分别代表什么含义？（3）信号灯可能的取值诸N个并发进程，互斥信号灯mutex的初值为1时，则：mutex的取值为：1～-(N-1).其含义为：1：表示有进程进入临界区。有一个资源，无进程等待；0：表示有1个进程进入临界区。无资源，无进程等待；-i：表示一个进程进入临界区。无资源，且有i(i=N)个进程等待进入。（五）进程同步引例1：两位同学约好星期天去东湖，早上8:00在校门口，不见不散。当一个同学先来到校门口，要等另一个同学，到齐后一道打的去东湖。一、进程同步的概念1.进程同步的例子2.什么是进程同步同步：所谓同步就是并发进程在一些关键点上可能需要相互等待与互通消息，这样的相互制约关系称为进程同步。互斥的概念来自于诸进程对独占使用资源（设备）的竞争同步来源于多个进程的合作在人类社会中竞争与合作是永恒的病人就诊的例子病人看病活动：…要病人去化验；…等化验结果；…继续诊病；医生化验活动：…等要化验的病人；…进行化验；开出化验单；…等待等待唤醒后唤醒后3.进程同步的分类在操作系统中，同步有各种各样，但归纳起来有两类：诸进程合作完成某工作的逻辑顺序。对系统资源的共享。如两个进程共享一个缓冲区完成誊抄问题a.合作进程的执行次序用进程流图来描述诸进程合作完成某一任务的次序。1、说明进程的同步关系进程P1、P2可并行执行，P3的执行必须等待P1、P2都完成后才能开始执行。2、设置信号灯，说明含义、初值。s13=0表示进程P1尚未执行完成s23=0表示进程P2尚未执行完成P1(){…;v(s13);}P2(){…;v(s23);}P3(){p(s13);p(s23);….;}3、写出程序描述b.共享缓冲区的合作进程的同步设有一个缓冲区buffer，大小为一个字节，CP进程不断产生字符，送buffer，IOP进程从buffer中取出字符打印。如不加控制，会有多种打印结果，这取决于这两个进程运行的相对速度。在这众多的打印结果中，只有CP、IOP进程的运行刚好匹配的一种是对的，其它均为错误，并且不能重现。要保证打印结果的正确，CP、IOP必须遵循以下同步规则：(1)当CP把结果送入buffer后，IOP才能从buffer中取，否则IOP必须等待；(2)当IOP从buffer中取走数据后，CP才能将新产生数据送buffer，否则也必须等待。解决这个问题的步骤：(1)分析问题，弄清楚同步关系，如上分析；(2)设置信号灯，说明含义、初值；(3)写出程序描述。c.生产者－消费者问题我们把上面的例子扩充，假定缓冲区buffer是一个有界缓冲区，可存放n个数据，同时假定有n个CP进程不断地产生数据，并送buffer；有m个IOP进程从缓冲区中取数据打印。在我们生活中有很多这样的例子。生产者－消费者问题对于生产者进程：产生一个数据，当要送入缓冲区时，要检查缓冲区是否已满，若未满，则可将数据送入缓冲区，并通知消费者进程；否则，等待；对于消费者进程：当它去取数据时，要看缓冲区中是否有数据可取，若有则取走一个数据，并通知生产者进程，否则，等待。这种相互等待，并互通信息就是典型的进程同步。同时，缓冲区是个临界资源，因此，诸进程对缓冲区的操作程序是一个共享临界区，因此，还有个互斥的问题。生产者－消费者问题生产者－消费者问题(六)线程的基本概念在OS中，进程的引入提高了系统资源的利用率。进一步提高进程的并发性时产生问题：进程切换开销越来越大进程间通信效率受限多处理机系统调度在只有进程概念的操作系统中进程是：系统资源分配的单位处理器调度的对象在引入线程的操作系统中：线程是处理机调度的对象；进程是系统资源的分配单位；一个进程可同时具有多个线程。(六)线程的基本概念1.什么是线程线程是比进程更小的活动单位，它是进程中的一个执行路径。线程可以这样来描述：进程中的一条执行路径；它有自己私用的堆栈和处理机执行环境；它与父进程共享分配给父进程的主存；它是单个进程所创建的许多个同时存在的线程中的一个。2.线程的特点创建一个线程比创建一个进程开销要小得多。线程（Thread）是一个动态的对象，是处理机调度的基本单位，表示一个进程中的一个控制点，执行一系列的指令。实现线程间通信十分方便，因为一个进程创建的多个线程可以访问整个进程的所有资源，包括共享地址区域和数据，因此，线程间通信比较简单方便。在进程内创建多线程，可以提高系统的并行处理能力，加快进程的处理速度。同一个进程中线程切换简单。进程中所有线程是共享一个进程图像的。单进程单进程多线程多进程单线程每个进程只有一个线程多进程多线程每个进程只有多个线程线程的实现机制内核线程（Kernel-LevelThread）在OS内核完成创建、撤消、执行一个指定的函数线程。在支持内核线程OS中，内核维护进程和线程上下文，线程切换由内核完成。处理机分配对象是线程。某个线程因中断阻塞不影响其它线程的执行。多线程的进程可获得更多的处理机时间。WindowsServer2003支持内核线程。用户线程（User-LevelThread）不依赖OS核心，由应用进程利用线程库提供创建、同步、调度和管理线程。由于不需要操作系统支持，任何操作系统都可以支持。甚至单用户操作系统。线程实现的机制轻量级进程（Lightweightprocess）由内核支持的用户线程。一个进程可有一个或多个轻量级进程。每个轻量级进程由一个单独的内核线程来支持。由于同时提供内核线程控制机制和用户线程库，可以很好地把内核线程和用户线程的优点结合起来。