《操作系统原理进程通信》由会员分享，可在线阅读，更多相关《操作系统原理进程通信（204页珍藏版）》请在金锄头文库上搜索。
1、第四章进程通信一、进程的同步和互斥1、进程的间的相互作用相关进程：逻辑上具有某种联系的进程无关进程：逻辑上没有任何联系的进程2、相关进程间的关系1）直接作用(相互合作）同步关系同步关系：合作进程之间再执行次序上的协调关系2）间接作用（资源共享）互斥关系互斥关系：一个进程正在访问共享资源，另一个要访问该资源的进程必须等待。3、与时间有关的错误例4-24、临界资源和临界区 临临界界资资源源：一次仅允许一个进程所使用的资源。如物理设备。（CR:criticalresource）临界区临界区：每个进程中访问临界资源的那段程序代码。(CS:criticalsection)进进程程的的互互斥斥关关系系：当
2、一个进程进入临界区使用临界资源时，另外的进程必须等待；当占有临界资源的进程推出临界区后，另一个进程才被允许进入其临界区。entrysectioncriticalsectionexitsectionremaindersection临界区(criticalsection)：进程中访问临界资源的一段代码进入区(entrysection)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应“正在访问临界区”标志退出区(exitsection)：用于将“正在访问临界区”标志清除剩余区(remaindersection)：代码中的其余部分。同步机构设计准则1、空闲让进2、忙则
3、等待3、多中则一4、有限等待5、让权等待 原则2反映了互斥的基本含义，即使用临界区资源的排他性，原则1表示要有效利用临界资源；原则3是原则1和2的一个特殊情况；原则4和5是为了避免进程间发生等待或死锁。三、硬件指令体制1、测试与设置技术利用TS指令实现的进程互斥算法是：每个临界资源设置一个公共布尔变量lock，True表示正被占用，False表示空闲，初值为False.进程使用临界资源时，应该按照如下三步：1）测试lock值，如果为真，表示资源已经被占用，则不断等待测试；如果为假，则表示资源可用，这时候把lock设置为真，用来排斥其他进程使用资源，我们可以把这个过程叫做关锁关锁。2）进程进入临
4、界区，访问临界资源3）使用完毕，推出临界区，再把lock设置为假，以释放资源，让其他进程使用。这个过程可以叫做开锁开锁。2、TS指令FunctionTS（Varlock:boolean）:BooleanBeginTS:=lock;Lock:=true;EndTS指令的执行是不可分割的，它实际上是一条原语。利用TS指令可以简单有效的实现互斥，以上指令是TS指令的功功能能描描述述，并非软件实现，事实上，TS指令的实现是由硬硬件件直直接接完完成成的，并由硬件保证其原子原子操作性能。3、利用TS指令完成进程互斥 每个临界资源设置一个公共布尔变量lock，初值为FALSE。在进入区利用TS进行检查：有进
5、程在临界区时，TS为TURE,则重复检查；直到其它进程退出时,TS为FALSE,检查通过；whileTS(lock);entry sectioncriticalsection;lock:=false;exit sectionremaindersection;例4-5硬件方法的优点1）适用于任意数目的进程，在单处理器或多处理器上2）简单，容易验证其正确性3）可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量硬件方法的缺点1）等待要耗费CPU时间，不能实现让权等待2）可能饥饿：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上 3）可能死锁四、信号量机制一个进程强制的被停在一个
6、特定的地方直到收到一个专门的信号，这个信号就是信信号号量量，其工作方式类似于铁路交通管理中的信号灯。信号量是一种特殊的变量，它表面形式是一个整型变量或者一个整型变量附加一个队列，它只能被特定的原语操作来执行。1、整型信号量将信号量定义为一个整型变量s信号量s=0表示可用的临界资源实体数信号量s0表示等待使用该资源的进程数可执行的两个标准原子操作为wait（s）和signal（s）Wait（s）：While s=0 do no-op当当 发发 生生 s0，表示还有临界资源，可以被使用，表示还有临界资源，可以被使用，则将临界资源数减则将临界资源数减1Signal(s):s:=s+1临界资源数加临界
7、资源数加一一整型信号量的不足之处在于，若s=0，则进程必须不断循环测试，陷入忙等状态。因此用整型信号量作为同步机制的实现技术不符合“让权等待”的原则。2、记录型信号量用一个整型变量value表示资源数量，用一个进程链表L表示所有等待该信号量的进程的PCB。初始化指定一个非负整数值value，表示空闲资源总数（又称为“资源信号量”）若为非负值表示当前的空闲临界资源数空闲临界资源数；若为负值其绝对值表示当前等等待待临临界界资资源的进程数。源的进程数。wait(s)s.value=s.value-1;if(s.value0)该进程状态置为等待状态将该进程的PCB插入相应的等待队列s.list末尾si
8、gnal(s)s.value=s.value+1;if(s.value=0，该值表示此时资源的空闲数量s.value0，则|s.value|表示因为得不到资源而被阻塞的进程数量2）每执行一次wait操作，意味着要求分配一次资源；因此把s.value-1,如果s.value0，进程由于得不到资源而自行阻塞，此时需要重新调度进程。3)每执行一次signal操作，意味着释放一个资源；因此把s.value+1,如果s.value=0,则表示链表中有因为请求资源而阻塞的进程，因此要把队列中的第一个进程唤醒放到就绪队列中。4)注意要保证wait和singal操作的原子性，如果不能保证，会引起与时间有关的错
9、误。利用信号量实现互斥设置互斥信号量mutex，并赋初值为1，表示任何时刻只能有一个进程获得临界资源。mutex=1,资源未被占用；mutex=0,资源被占用；mutex0,资源被占用，且有等待进程。wait(mutex)；进入区临界区signal(mutex)；退出区剩余区 必须成对使用wait和signal原语：遗漏wait原语则不能保证互斥访问，遗漏signal原语则不能在使用临界资源之后将其释放（给其他等待的进程）；wait、signal原语不能次序错误、重复或遗漏。用信号量实现同步例：设有计算和打印两个进程Pc和Pp,共同使用同一缓冲区Buffer，Pc向Buffer中存放计算结果，
10、Pp从Buffer取计算结果送打印机输出。这两个进程的执行是相互制约的。即Pc的执行结果是Pp的执行条件；而Pp的执行结果也是Pc的执行条件，它们是相互制约的。我们把一组在异步环境中由于以各自的执行结果而限制其它进程的执行速度的现象称为并发进程的直接制约，解决这种直接制约的方法称为同步同步。具体分析本问题中的同步问题：1、pc进程不能向满的缓冲区放置数据2、pp进程不能从空的缓冲区取计算结果因此，需要两个信号量，分别用来记录pc和pp进程 进程互斥引入了信号量的概念，它是与所有并发进程都相关的，因此我们称其为公有信号量公有信号量。那么在进程同步中，我们同样也引入信号量的概念，但它只是与制约进程
11、和被制约进程有关，并不涉及所有的并发进程，因此我们称其为私有信号量私有信号量。a.为并发进程设置私有信号量b.为私有信号量赋初值；c.用wait、signal原语和私有信号量实现同步。a.设Bufferempty为Pc进程的私有信号量，Bufferfull为Pp进程的私有信号量，b.赋初值；Bufferempty=n,Bufferfull=0;c.实现：pc：beginP(Bufferempty)DatatoBufferI;V(Bufferfull);end;pp：BeginP(Bufferfull);BufferItoData;V(Bufferempty);end;wait和signal操作
12、必须成对出现，有一个wait操作就有一个signal操作，当为互斥操作时，他们处于同一个进程，当为同步操作时，则不在一个进程出现。3、AND信号量集机制信号量集用于同时需要多个资源时的信号量操作AND型信号量集用于同时需要多种资源且每种占用一个时的信号量操作；一段处理代码需要同时获取两个或多个临界资源可能死锁：各进程分别获得部分临界资源，然后等待其余的临界资源，各不相让假定有两个进程A和B，都要求访问共享数据D和E，这两个数据都为临界资源，为此，可为这两个数据设置用于互斥的信号量Dmutex和Emutex，并另他们的初值都为1。相应的，在这两个进程中都要包含对Dmutex和Emutex的操作。
13、也就是：ProcessA:ProcessB:wait（Dmutex）；wait（Emutex）；wait（Emutex）；wait（Dmutex）；如果进程A和B交替执行Wait操作：ProcessA:wait(Dmutex);则Dmutex0ProcessB:wait(Emutex);则Emutex0ProcessA:wait(Emutex);则Emutex1A阻塞ProcessB:wait(Dmutex);则Dmutex1B阻塞最后，进程A和B都进入僵持状态，在无外力作用下，两者都将无法从僵持的状态中解脱出来，我们称此刻的进程A和B已经进入死锁状态。显然，当进程同时要求的共享资源愈多时，发
14、生进程死锁的可能也愈大。AND信号量基本思想：在一个原语中，将一段代码同时需要的多个临界资源，要么全部分配给 它，要 么 一 个 都 不 分 配。称 为Swait(SimultaneousWait)。在Swait时，各个信号量的次序并不重要，虽然会影响进程归入哪个阻塞队列，但是由于是对资源全部分配或不分配，所以总有进程获得全部资源并在推进之后释放资源，因此不会死锁。p49定义5、经典进程同步问题（1）生产者-消费者问题问题描述：设有一组生产者Producer和一组消费者Consumer通过一个容量为n的有界缓冲区Buffer共同完成“生产和消费”任务。每个缓冲区可以存放一个产品，生产者负责向其
15、中投放产品Product，而消费者负责消费其中的产品。互斥问题：同时只能有一个进程访问某个缓冲区，即缓冲区资源是临界资源缓冲区资源是临界资源。同步问题：1）生产者进程生产产品的速度不能超过缓冲区的有效容量，即生产进程不能往“满”的缓冲区放产品。2）消费者进程消费的速度不能快于生产者的速度，即消费者进程不能从“空”的缓冲区消费产品。由此得到生产者和消费者进程应该满足以下同步规则：1）若生产者企图把产品放入满的缓冲区，则必须阻塞等待，直到消费者从缓冲区中取走一个产品后将他唤醒。2）若消费者企图从空的缓冲区取走商品，则必须阻塞等待，直到生产者放入一个产品后将其唤醒。为了让缓冲区得到循环利用，将缓冲区
16、做成环形的，以方便每个区域都可以循环利用采用信号量机制：full是满缓冲区数目，初值为0，empty是空缓冲区数目，初值为N。记为同步信号量。实际上，full和empty是同一个含义：full+empty=Nmutex用于访问缓冲区时的互斥，初值是1 另外设置整形变量in，out，分别用于指示空缓冲区和满缓冲区的位置对环状缓冲区，放数据和取数据都有一个模操作In：（In1）modnOut：（out1）modn每个进程中各个P操作的次序是重要的：先检查资源数目，再检查是否互斥否则可能死锁(为什么？)分析：生产者进程：P（mutex）消费者进程：P（mutex）P（empty）P（full）当进行了n次生产之后，缓冲区占满，empty=0。这时再执行生产者进程，p（mutex），mutex=0，可以执行，再执行p（empty），则empty=-1，生产者进程因为没有空的缓冲区而进入等待状态。如果此时有一个消费者进程来，首先执行p（mutex），则mutex=-1，消费者进程也进入等待，彼此都等待对方来唤醒自己，处于循环等待的状态，形成了死锁。如果进程中wait（s1）和wait（s2）两个
