计算机操作系统 第二章 进程管理(2)

第二章进程管理（2）2.3进程同步多进程并发执行时，由于资源共享或进程合作，使进程间形成间接相互制约和直接相互制约关系，这需要用进程互斥与同步机制来协调两种制约关系。进程同步的主要任务：协调进程执行次序，使并发执行的诸进程间能有效地共享资源和相互合作，使程序的执行具有可再现性。2.3.1进程同步的基本概念1．进程间关系（1）间接相互制约关系：源于资源共享。（2）直接相互制约关系：源于进程间的合作并发的进程间相互竞争资源，当一个进程通过操作系统分配到该资源后，其余的进程就必须等待，直到该进程释放资源。这就形成了间接的相互制约。进程的互斥（间接作用）进程的互斥(MutualExclusion)是解决进程间竞争关系的手段。若干个进程共享使用同一临界资源时，任何时刻最多允许一个进程去使用，其它要使用该资源的进程必须等待，直到占有资源的进程释放该资源。互斥进程不允许交叉执行。进程的同步进程的同步(Synchronization)是解决进程间协作关系的手段。指多个进程间存在某种时序关系，它们必须协同动作、相互配合，以共同完成一个任务。具体地说，一个进程的执行依赖于另一个进程的消息，当一个进程没有得到来自于另一个进程的消息时则等待，直到消息到达才被唤醒。2．临界资源（criticalresouce）P48页：生产—消费者问题，是典型的进程同步问题。例1：进程P1、P2公用一个变量COUNT，初始值为0。进程P1进程P2r1=count;r2=count;r1++;r2--;count=r1;count=r2;P1、P2两个进程的执行顺序是随机的，P1、P2可能顺序执行或交错执行。不同的执行顺序，COUNT值会不同，这是不允许的。例2：系统堆栈s内存放空的数据块地址，进程PA和PB向系统请求空数据块。请求时从栈项取出，释放时将释放块地址压入栈项。Getspace():g=stack[top];(1)top--;(2)returng;release(ad):top++;(3)stack[top]=ad;(4)若按3—1—2—4的顺序执行，就可能出错。解决问题的关键是应将共享的变量或区域作为临界资源处理，让各进程互斥地访问各资源。3．临界区临界资源：一次只能供一个进程使用，使用完毕后归还系统，才能供其他进程使用的资源。使用临界资源的进程必须互斥进行。临界区（criticalsection）：每个进程中访问临界资源的那段代码。临界区代码不允许多个并发进程交叉执行。进程间的互斥可以描述为禁止两个或两个以上的进程同时进入访问同一临界资源的临界区。临界区互斥访问进入区：进程进入临界区前的一段检查代码，用于控制进程是否能进入其后的临界区。如果可以进入临界区，要设置相应的“正在访问”标志。退出区：临界区后面附加的一段代码，用于释放该临界区的被访问标志。进入区临界区退出区4．同步机制应遵循的规则（1）空闲让进：当无进程处于临界区内时，必须让一个要求进入临界区的进程立即进入。（2）忙则等待：当已有进程处于临界区内时，其它试图进入临界区的进程必须等待，以保证互斥。（3）有限等待：对要求进入临界区的进程，应保证能在有限时间内使之进入，以免陷入“死等”。（4）让权等待：处于等待状态的进程应释放处理机，以免进程“忙等”。也使其他进程能得到CPU的使用权。5．进程互斥的软件方法软件方法的基本思路是在进入区检查和设置一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志其中的主要问题是设置什么标志和如何检查标志。软件解法的缺点：1.忙等待2.实现过于复杂3.需要高的编程技巧6．进程互斥的硬件方法当一个进程进入临界区，就屏蔽所有中断。用一条指令完成读和写两个操作，保证读与写操作成为一个整体不被打断。6．进程互斥的硬件方法优点：（1）适用范围广，适用于任何数目的互斥进程，用在单处理器和多处理器环境中完全相同（2）简单：硬件方法标志设置简单，含义明确，容易验证其正确性（3）支持多个临界区：只需要为每个临界区设置一个布尔标志缺点：（1）进程在等待进入临界区时也要耗费处理器时间，不能实现“让权等待”（2）可能出现进程“饥饿”2.3.2信号量机制新的同步工具——信号量和P、V操作。信号量：是一种数据结构，代表可用资源实体的数目。信号量只能通过初始化和两个标准的原语：P（wait(S)）、V（(signal(S)）来访问。P原语相当于进入区操作，V原语相当于退出区操作。两个同步原语：P操作和V操作，也表示为wait和signal。作为操作系统核心代码的一部分，P、V原语以一个整体执行，执行时不受进程调度和执行的打断，即满足原子性1．整型信号量将信号量定义为一个整型量，其初始值代表空闲资源总数。该信号量只能通过初始化和原语：P（wait(S)）、V（signal(S)）来访问。ints=N;P操作：wait(s)V操作：signal(s){while(s=0);{s++;s--;}}wait(s);临界区signal(s);P操作时当s=0时，进程处于忙等状态，未遵循“让权等待”的原则。2．记录型信号量信号量s为一个记录型数据结构，定义如下：structsemaphore{intvalue;pointer_PCBqueue;}信号量说明：semaphores;s.value为资源计数，s.queue为阻塞在该信号量上的进程等待队列。P操作原语的描述P操作：wait(s){s.value--;/*申请一个资源*/if(s.value0)/*没有空闲资源*/{block(s.queue);/*将该进程的PCB插入相应的等待队列s.queue；阻塞调用进程；*/}}V操作原语的描述V操作：signal(s){s.value++;/*释放一个资源*/if(s.value=0)/*有进程处于阻塞状态*/{wakeup(s.queue);/*从阻塞队列s.queue中取出第一个进程P；进程P进入就绪队列*/}}P、V操作说明1．信号量s.value为正值，代表实际还可以使用的物理资源数目。2．信号量s.value为负值，其绝对值表示阻塞在该信号量s队列中的进程个数。3．通常，P操作表示进程请求一个单位的该类资源，V操作表示进程释放一个单位资源。在一定条件下，P操作代表阻塞进程操作，而V操作代表唤醒被阻塞进程的操作。4．在使用信号量进行共享资源访问控制时，必须成对使用P、V原语，使用不能次序错误、重复或遗漏。实现互斥用测试信号量的办法决定是否可以进入临界区。设置s.value的初值为1，表示一个临界资源，此时的信号量可转化为互斥信号量。wait(s);临界区signal(s);实现同步（前趋关系）设置s.value的初值为0，可实现进程间的同步，即前趋关系。并发的进程Pi和Pj中，分别有代码Ci和Cj，要求Ci在Cj开始前完成。为每个前趋关系设计一个互斥信号量Sij，初始值为0。进程PiCiV(Sij)进程PjP(Sij)Cj3．AND型信号量更多应用中，一个进程需要先获得两个或多个共享资源后，才能执行其任务。当一段代码需要同时获取两个以上临界资源时，就可能出现由于各进程分别获得部分临界资源并等待其余临界资源的局面。此时会陷入死锁。AND型信号量是指同时需要多个资源且每种占用一个时的信号量操作。AND同步机制AND同步机制的基本思想是：进程运行时所需要的所有资源，要么全部分配给它，使用完毕后一起释放；要么一个都不分配给它。实现时，采用原子操作：要么全部分配到所有资源，要么一个也不分配到。称AND型信号量P原语为：Swait(Simultaneouswait)V原语为Ssignal(Simultaneoussignal)。SP原语描述Swait(S1,S2,…,Sn)/*SP原语描述*/{while(1){if(S1=1&&S2=1&&…&&Sn=1){for(i=1;i=n;i++)Si--;/*先确信可满足所有资源要求再减1操作*/berak;}else/*资源不够时*/{将进程放入第一个信号量小于1的阻塞队列Si.sqeue;将PC中的地址回退到SP开始处；阻塞进程；}}}SV原语描述Ssignal(S1,S2,…,Sn)/*SV原语描述*/{for(i=1;i=n;i++){Si++;唤醒Si.sqeue队列中的所有进程，进入就绪队列;}}4．信号量集一般信号量集是指同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的信号量处理。基本思路：在一次原语操作中完成所有的资源申请。S表示资源数，t为下限值，d为需求量。当S=t时，为进程分配d个S类资源；当St时，不予分配。SP原语描述Swait(S1,t1,d1,…,Sn,tn,dn)/*SP原语描述*/{while(1){if(S1=t1&&S2=t2&&…&&Sn=tn){for(i=1;i=n;i++)Si-=di;/*先确信可满足资源要求再减1*/berak;}else/*资源不够时*/{将操作进程放入第一个Siti的阻塞队列Si.sqeue;将PC中的地址回退到SP开始处；阻塞进程；}}}SV原语描述Ssignal(S1,d1,…,Sn,dn){for(i=1;i=n;i++){Si+=di;唤醒Si.sqeue队列中的所有进程，进入就绪队列;}}信号量集的特殊应用一般信号量集可用于各种情况的资源分配与回收。下面是几种特殊情况：（1）Swait(S,d,d)。信号量集中只有一个信号量S，每次可申请d个资源。当现有资源数小于d时，不予分配。（2）Swait(S,1,1)。此时已蜕化为一般的记录型信号量（当S1时）或互斥信号量（当S==1时）。（3）Swait(S，1，0)。可作为一个可控开关，当S=1时，允许多个进程进入临界区；当S==0时，禁止任何进程进入临界区。2.3.3信号量的应用1．利用信号量实现进程互斥多个进程互斥访问某临界资源时，只须为该资源设置一互斥信号量mutex，令其初始值为1。每个进程临界区前的进入区加载P(mutex)操作，退出区加载V(nutex)操作，就可实现互斥访问。P2P3P1V(mutex)临界区P(mutex)V(mutex)临界区P(mutex)V(mutex)临界区P(mutex)2．利用信号量实现前趋关系为具有前趋关系的两进程设置信号量，令初值为0。然后在前趋段后加V(Sij)，后继段前加P(Sij)。进程PiCiV(Sij)进程PjP(Sij)Cj3．利用信号量实现进程同步有A、B两进程，A进程从外界读信息到缓冲区，B进程负责加工读进缓冲区的信息。解：设计二元信号量S1，表示缓冲区中有否可供加工的信息，初始值为0；二元信号量S2，表示缓冲区是否为空，初始值为1。二元信号量：仅允许取值为0和1，主要用于解决进程互斥问题。初始化：S1=0;/*表示缓冲区中有否可供加工的信息*/S2=1;/*表示缓冲区是否为空*/2.4经典进程的同步问题主要问题是如何选择信号量和如何安排P、V原语的使用顺序。信号量按其取值可分为两种：二元信号量：仅允许取值为0和1，主要用于解决进程互斥问题。一般信号量：允许取值为非负整数，主要用于解决进程间的同步问题。2.4.1生产者——消费者问题一组生产者向一组消费者提供消息，它们共享一个有界缓冲池，生产者向其中投放消息，消费者从中取得消息。只要缓冲池未满，生产者可将消息送入缓冲池；只要缓冲池未空，消费者可从缓冲池取走一个消息。生产者--消费者问题是指若干进程通过有限的共享缓冲区交换数据时的缓冲区资源使用问题。1．利用记录型信号量解决假设有n个缓冲区，每个缓冲区存放一个消息。设计：缓冲池互斥信号量mutex；计数信号量empty和full，分别表示空缓冲及满缓冲的数量。mutex，empty，full的初始值分别为1，n，0这里每个进程中各个P操作的次序是很重要的。各进程必须首先检查对应的资源数目，在确信有可用资源后再申请对整个缓冲区的互斥操作。否则，先申请对整个缓冲区的互斥操作再