搜索
当前位置: 678彩票官网 > 低级互斥 >

进程互斥与同步

gecimao 发表于 2019-04-13 12:54 | 查看: | 回复:

  设有两个计算进程PA、PB,共享内存MS。堆栈s中存放那些空数据块的地址。 资源共享所引起的制约getspace为取空数据块过程; getspace: begin local gstack[top]toptop-1 end release(ad)为释放数据块过程 release(ad): begin toptop+1 stack[top]ad end 把getspace和release(ad)抽象为两个各以一个动作完成的顺序 执行单位,执行结果的正确性是可以保证的。 资源共享所引起的制约一般来说,可以把那些不允许交叉执行的临界区按不同的 公用数据划分为不同的集合 以公用数据栈S划分的临界区集合是 {getspace,release}。 把这些集合称为类(class)。 显然,对类给定一个唯一的标识名,系统就会容易地区分 它们。在程序的描述中,可用下列标准形式来描述临界区: when(类名)do{临界区}od 资源共享所引起的制约设类(getspace,release)的类名为sp,则 getspace和release(ad)可重新描述为: getspace: when sp do gstack[top] toptop-1 od release(ad): when sp do toptop+1 stack[top]ad od 资源共享所引起的制约间接制约: 由于共享某一公有资源而引起的在临界区内不 允许并发进程交叉执行的现象,称为由共享公有 资源而造成的对并发进程执行速度的间接制约, 简称 资源共享所引起的制约互斥: 一组并发进程中的一个或多个程序段,因共享某一 公有资源而导致它们必须以一个不允许交叉执行的单 位执行。即,不允许两个以上的共享该资源的并发进 程同时进入临界区称为互斥。 资源共享所引起的制约一组并发进程互斥执行时必须满足如下准则: (1)不能假设各并发进程的相对执行速度。即各并发进程享有平 等的、独立的竞争共有资源的权利,且在不采取任何措施 的条件下,在临界区内任一指令结束时,其他并发进程可 以进入临界区。 (2)并发进程中的某个进程不在临界区时,它不阻止其他进程进 入临界区。 (3)并发进程中的若干个进程申请进入临界区时,只能允许一个 进程进入。 (4)并发进程中的某个进程申请进入临界区时开始,应在有限时 间内得以进入临界区。 互斥的加锁实现当某个进程进入临界区之后,它将锁上临界区, 直到它退出临界区时为止。 并发进程在申请进入临界区时,首先测试该临界 区是否是上锁的。如果该临界区已被锁住,则该进程 要等到该临界区开锁之后才有可能获得临界区。 设临界区的类名为S。为了保证每一次临界区中只能有一个 程序段被执行,又设锁定位key[S]。key[S]表示该锁定位属于 类名为S的临界区。 加锁后的临界区程序描述如下: lock(key[S]) (临界区) unlock(key[S]) 互斥的加锁实现设key[S]=1时表示类名为S的临界区可用,key[S]=0时 表示类名为S的临界区不可用。 则,unlock(key[S])只用一条语句 即可实现。即: key[S]1 lock(key[S])的一种实现方法是: lock(x) begin local repeatvkey[s] until key[s]0end 注意:这种实现方法是 不能保证并发进程互斥执行 所要求的准则(3)的。 因为当同时有几个进程 调用lock(key[S])时,在 x0语句执行之前,可能已 有两个以上的多个进程由于 key[S]=1而进入临界区。 为了解决这个问题,有些机器在硬件中设置了“测试与设置” (test 互斥的加锁实现用加锁的方法实现进程之间的互斥,存在一些影响系统可 靠性和执行效率的问题,并将导致在某些情况下出现不公平现 unlock(key[S])Goto unlock(key[S])Goto 问题分析用加锁法解决进程互斥的问题时,一个 进程能否进入临界区是依靠自己的测试。 信号量的概念是荷兰科学家E.W.Dijkstra提出 在操作系统中,信号量sem是一整数。在sem大于等于零时代表可供并发进程使用的资源实体数,但sem 小于零时则表示正在等待使用临界区的进程数。 建立一个信号量步骤: 说明所建信号量所代表的意义 赋初值 建立相应的数据结构以便指向那些 等待使用该临界区的进程。 信号量的数值仅能由P,V原语操作改变。采用P,V原语,可以把类名为S的临界区描述为 When doP(sem) 临界区 V(sem) od sem是与临界区内所使用的公用资源有关的信号量。 一次P原语操作使得信号量sem减1,而一次V原语操作将使 得信号量sem加1。 当某个进程正在临界区内执行时,其他进程如果执行了P原语操作,则该进程并不像调用lock时那样因进不了临界区而返 回到lock的起点,等以后重新执行测试,而是在等待队列中等 待有其他进程做V原语操作释放资源后,进入临界区,这时,P 原语的执行才算真正结束。 当有好几个进程执行P原语未通过而进入等待状态之后,如 有某进程作了V原语操作,则等待进程中的一个可以进入临界区, 但其他进程必须等待。 若sem减1后仍大于或等于零,则进程继续执行; 若sem减l后小于零,则该进程被阻塞在与该信 号相对应的队列中,然后 转进程调度。 若相加结果大于零,进程继续执行; 若相加结果小于或等于零,则从该信号的等待 队列中唤醒一等待进程, 然后再返回原进程继续 执行或转进程调度。 P,V过程要以原语实现 的原因 过程描述如下:加锁法 P(sem):begin 封锁中断; lock(lockbit) val[sem]=val[sem]-1 val[sem]<0保护当前进程CPU现场 当前进程状态置为”等待” 将当前进程插入信号sem等待队列转进程调度 fi unlock(lockbit); 开放中断 end V(sem):begin封锁中断; lock(lockbit) va[sem]=val[sem]+1 val[sem]0localk 从sem等待队列中选取一等待进程,将其指针置入k中 将k插入就绪队列 进程状态置“就绪” fi unlock(lockbit); 开放中断 end 设信号量sem是用于互斥的信号量,且其初值为l表示没有 并发进程使用该临界区。 只要把临界区置于P(sem)和V(sem)之间,即可实现进程间 的互斥。 用信号量实现两并发进程PA,PB互斥的描述如下: 设sem为互斥信号量,其取值范围为(1,0,-1)。其中sem=1 表示进程PA和PB都未进入类名为S的 临界区, sem=0 表示进程PA或PB已进入类名为S的 临界区, sem=-1 表示进程PA和PB中,一个进程已进 入临界区,而另一个进程等待进入临界区。 V(sem)进程同步 同步的概念例子: 计算进程和打印进程共同使用同一缓冲区Buf。 计算进程反复地把每次计算结果放入Buf中, 而打印进程则把计算进程每次放入Buf中的数据通过打印 机打印输出。 如果不采取任何制约措施,这两个进程的执行起始时间 和执行速度都是彼此独立的,其相应的控制段可以描述为: 同步的概念 Pc: localBuf RepeatBuf ’Buf Until Buf 计算得到计算结果 Buf计算结果 Goto localPri Repeat PriBuf Until Pri 打印Buf中的数据清除Buf中的数据 Goto 把异步环境下的一组并发进程,因直接制约而互相合作、互相等待,使得各进程按一定的速度执行的过程称为进程间的 同步。 具有同步关系的一组并发进程称为合作进程,合作进程 间互相发送的信号称为消息或事件。 同步的概念 同步的消息实现机制 如果对一个消息或事件赋以唯一的消息 名,则可用过程: wait (消息名) 表示进程等待合作进程发来的消息, 而用过程 signal (消息名) 表示向合作进程发送消息。 利用过程wait和signal,可以简单地描述上面 例子中的计算进程Pc和打印进程Pp的同步关系如下: 同步的概念 同步的概念 Pc: A:wait(Bufempty) 计算 Buf计算结果 Bufemptyfalse signal(Buffull) Goto B:wait(Buffull)打印Buf中的数据 清除Buf中的数据 Buffu11false signal(Bufempty) Goto 过程wait的功能是等待到消息名为true的进程继续执行,而signal的功能则是向合作进程发送合作进程所需要的消息名, 并将其值置为true。 私用信号量 各进程之间发送的消息作为信号量看待。 与进程互斥时不同的是,这里的信号量只与制约进程 及被制约进程有关而不是与整组并发进程有关。因此, 称该信号量为私用信号量(Private Semaphore)。 一个进程Pi的私用信号量Semi是从制约进程发送 来的进程Pi的执行条件所需要的消息。 与私用信号量相对应,称互斥时使用的信号量为 公用信号量。 用P,V原语操作实现同步 利用P,V原语实现进程同步的方法与利用wait和signal过 程时相同,分为三步。 首先为各并发进程设置私用信号量, 然后为私用信号量赋初值, 最后利用P,V原语和私用信号量规定各进程的执行顺序。 用P,V原语操作实现同步 例:设进程P 发送数据时调用发送过程deposit(data),P 接收数据时调用过程remove(data)。且数据的发送和接收过程满足如下条件: 不可能从缓冲区中取出数据(假定数据块长等于缓冲区长度); 发送的数据块在缓冲队列中按先进先出(FIFO)方式排列。用P,V原语操作实现同步 分步描述过程deposit(data)和remove(data): 的私用信号量,Buffull为进程P 令Bufempty的初始值为n(n为缓冲队列的缓冲区个数), Buffu11的初始值为0; 描述:用P,V原语操作实现同步 deposit(data):begin local P(Bufempty);按FIFO方式选择一个空缓 冲区Buf(x); Buf(x)data Buf(x)置满标记 V(Buffull) end remove(data):Begin local P(Buffull);按FIFO方式选择一个 装满数据的缓冲区Buf(x) dataBuf(x) Buf(x)置空标记 V(Bufempty) end (producer-consumerproblems) 把并发进程的同步和互斥问题一般化,可以得到一 个抽象的一般模型,即生产者—消费者问题。 计算机系统中,每个进程都申请使用和释放各种不同类型的 资源。把系统中使用某一类资源的进程称为该资源的消费者, 而把释放同类资源的进程称为该资源的生产者。 把一个长度为n的有界缓冲区(n>0)与一群生产者进程 生产者—消费者问题生产者—消费者问题 设生产者进程和消费者进程是互相等效的,其中,各生产 者进程使用的过程deposit(data)和各消费者使用的过程 remove(data)可描述如下: 生产者—消费者问题是一个同步问题。即生产者和消费者之间满足如下条件: (1)消费者想接收数据时,有界缓冲区中至少有一个单元是 由于有界缓冲区是临界资源,因此,各生产者进程和各消费者进程之间必须互斥执行。 生产者—消费者问题 设:公用信号量mutex保证生产者进程和消费者进程之间的互斥, 信号量avail为生产者进程的私用信号量, 信号量full为消费者进程的私用信号量。 信号量avail表示有界缓冲区中的空单元数,初值为n; 信号量full表示有界缓冲区中非空单无数,初值为0。 信号量mutex表示可用有界缓冲区的个数,初值为1。 从而有: 生产者—消费者问题 deposit(data): begin P(avail) P(mutex) 送数据入缓冲区某单元 V(full) V(mutex) End remove(data): begin P(full) P(mutex) 取缓冲区中某单元数据 V(avail) V(mutex) end 进程通信通信(communication)意味着在进程间传送数据。 进程间的通信根据通信内容可以划分为二种:即 控制信息的传送(低级通信)与大批量数据传送(高级通信)。 低级通信一般只传送一个或几个字节的信息,以达到控制 进程执行速度的作用。 高级通信则要传送大量数据。高级通信的目的不是为了控 制进程的执行速度,而是为了交换信息。 进程的通信方式在单机系统中,进程间通信可分为4种形式: (1)主从式; (2)会线)消息或邮箱机制; (4)共享存储区方式。 主从式(master/servantsystem)通信系统的 主要特点是: 主进程可自由地使用从进程的资源或数据; 从进程的动作受主进程的控制; 主进程和从进程的关系是固定的。 主从式通信系统的典型例子是终端控制进程 和终端进程。 进程的通信方式-会线.会话方式(dialogue system)中,通信进程双方可分别称为使 用进程和服务进程。其中,使用进程调用服务进程提供的服务。 它们具有如下特点: 使用进程在使用服务进程所提供的服务之前,必须得到 服务进程的许可; 服务进程根据使用进程的要求提供服务,但对所提供服 务的控制由服务进程自身完成。 使用进程和服务进程在进行通信时有固定连接关系。 用户进程与磁盘管理进程之间的通信是会话系统的一个例子。 消息或邮箱机制则无论接收进程是否已准备好接收消息,发送进程都将把所要发送的消息送入缓冲区或邮箱。消息具有两 互相通信的进程地位平等的意思。 消息的一般形式为4个部分组成。即: 发送进程名、接收进程名、数据和有关数据的操作(图3.15) 进程的通信方式-消息或邮箱机制消息或邮箱机制的特点是: 与会话系统不同,发送进程和接收进程之间无直接连接关系,接收进程可能在收到某个发送进程发来的消息之后,又转 去接收另一个发送进程发来的消息。 发送进程和接收进程之间存在缓冲区或邮箱(图3.16)用来存放被传送消息。 共享存储区方式不要求数据移动。两个需要互相交换信息的进程通过对同一共享数据区(shared memory)的操作来达到互相 通信的目的。这个共享数据区是每个互相通信进程的一个组成 部分。 几种通信方式都可用于大量数据传送, 而且,由于其通信方式不同,需要使用 不同的控制方式来达到通信进程之间同 步或互斥的目的。 Hansen在1973年首先提出。 发送进程和接收进程采用消息缓冲机制进行数据传送时, 发送进程在发送消息前,先在自己的内存空间设置一个发送区, 把欲发送的消息填入其中,然后再用发送过程将其发送出去。 接收进程则在接收消息之前,在自己的内存空间内设置相 应的接收区,然后用接收过程接收消息。 消息缓冲机制由于消息缓冲机制中所使用的缓冲区为公用缓冲区,使用 消息缓冲机制传送数据时,两通信进程必须满足如下条件: 在发送进程把消息写入缓冲区和把缓冲区挂入消息队列 时,应禁止其他进程对该缓冲区消息队列的访问。否则,将引 起消息队列的混乱。同理,当接收进程正从消息队列中取消息 缓冲时,也应禁止其他进程对该队列的访问。 当缓冲区中无消息存在时,接收进程不能接收到任何消 息。至于发送进程是否可以发送消息,则由发送进程是否申请 到缓冲区决定。 消息缓冲机制设公用信号量mutex为控制对缓冲区访问的互斥信号量, 其初值为1。 设SM为接收进程的私用信号量,表示等待接收的消息个数, 其初值为0。 设发送进程调用过程Send(m)将消息m送往缓冲区, 接收进程调用过程Receive(m)将消息m从缓冲区读往自己的数 消息缓冲机制Send(m): Begin 向系统申请一个消息缓冲区 P(mutex) 将发送区消息m送入新申请的消息 缓冲区 把消息缓冲区挂入接收进程的消息 队列 V(mutex) V(SM) end Receive(m): begin P(SM) P(mutex) 摘下消息队列中的消息n 将消息n从缓冲区复制到接收区 释放缓冲区 V(mutex) end 邮箱通信就是由发送进程申请建立一与接收进程链接 的邮箱。发送进程把消息送往邮箱,接收进程从邮箱中取 出消息,从而完成进程间信息交换。 设置邮箱的最大好处就是发送进程和接收进程之间没 有处理时间上的限制。且邮箱可考虑成发送进程与接收进 程之间的大小固定的私有数据结构。 邮箱通信邮箱由邮箱头和邮箱体组成。其中邮箱头描述邮箱名称、 邮箱大小、邮箱方向以及拥有该邮箱的进程名等。邮箱体主要 用来存放消息 对于只有一发送进程和一接收进程使用的邮箱,则进程间 通信应满足如下条件: 发送进程发送消息时,邮箱中至少要有一个空格能存放 该消息。 接收进程接收消息时,邮箱中至少要有一个消息存在。 邮箱通信设发送进程调用过程deposit(m)将消息发送到邮箱, 接收进程调用过程remove(m)将消息m从邮箱中取出。 为了记录邮箱中空格个数和消息个数, 信号量fromnum为发送进程的私用信号量, 信号量mesnum为接收进程的私用信号量。 fromnum的初值为信箱的空格数n,mesnum的初值为0。 则deposit(m)和remove(m)可描述如下: 邮箱通信deposit(m): begin local P(fromnum)选择空格x 将消息m放入空格x中 V(mesnum)end remove(m): begin local P(mesnum)选择满格x V(fromnum)end 1.管道pipeUNIX系统从System V开始,提供有名管道和无名管道两种 数据通信方式。 利用UNIX提供的系统调用pipe,可建立一条同步通信管道。 其格式为: pipe(fd) int fd[2]; 这里,fd[1]为写入端,fd[0]为读出端。 进程通信的实例——管道:示例12.示例 例1:用C语言编写一个程序;建立一个pipe,同时父进程生 成一个子进程,子进程向pipe中写入一字符串,父进程从pipe 中读出该字符串。 程序如下:#include

  main() intx,fd[2]; Char buf[30],s[30]; pipe(fd);/*创建管道*/ while((x=fork())==-1);/*创建子进程失败时,循环*/ example\n”);write(fd[1],buf,30); exit(0); wait(0);read(fd[0],s,30); printf(”%s”,s); 进程通信的实例——管道:示例2例2:编写一程序,建立一个管道。同时,父进程生成子进程 ;这两个子进程分别向管道中写入各自的字符串,父进程读出它们(如图3.21)。 #include

  main() inti,r,pl,p2,fd[2]; char buf[50],s[50]; 进程通信的实例——管道:示例2pipe(fd); while((pl=fork())==-1); if(p1==0) 1ockf(fd[1],1,0);sprintf(buf,”child process P1 sendingmessages!\n”); printf(“child process P1!\n”); write(fd[l],buf,50); sleep(5); 1ockf(fd[1],0,0); exit(0); while((p2=fork())==-1);if(p2==0) 1ockf(fd[1],l,0);sprintf(buf,”child process P2 sendingmessages\n”); printf(“child process P2!\n”); write(fd[1],buf,50); sleep(5); 1ockf(fd[l],0,0); exit(0); 进程通信的实例——管道:示例2wait(0); if(r=read(fd[0],s,50) -1)printf(“can’t read pipe\n”); else printf(”%s\n”,s); wait(0); if(r=read(fd[0],s,50) printf(“can’tread pipe\n”); else printf(”%s\n”,s); exit(0); endmain() 习题一 Dining-Philosophers Problem Shared data semaphore chopstick[5]; Initially all values Dining-PhilosophersProblem Philosopher P(chopstick[i])P(chopstick[(i+1) V(chopstick[i]);V(chopstick[(i+1) 习题二:设有8个程序prog1,prog2,…prog8.它们 在并发系统中执行时有如图2。1所示的 制约关系,试用P,V操作实现这些程序间 的同步。 程序清单 BEGIN INTEGER S13,S14,S15,S23,S24,S25; INTEGER S36,S48,S57,S68,S78; S13=S14=S15:=0; S23=S24=S25:=0; S36:=0; S48:=0; S57:=0; S68:=0; S78:=0; COBEGIN Prog1: BEGIN do all work; v(s13); v(s14); v(s15); END; prog2: BEGIN do all work; v(s23); v(s24); v(s25); END; Prog3: BEGIN P(S13); P(S23); do all work; v(36); END; Prog4: BEGIN P(S14); P(S24); do all work; v(48); END; Prog5: BEGIN P(S15); P(S25); do all work; v(57); END; prog6: BEGIN P(S36) DO ALL WORK V(S68) END PROG7: BEGIN P(S57) DO ALL WORK V(S78) END PROG8: BEGIN P(S48); P(S68); P(S78); DO ALL WORK; END; COEND; END; 有一个仓库,可以存放X和Y两种产品, 仓库的存储空间足够大,但要求: 1.每次只能存入一种产品(X或Y) 2.-N

本文链接:http://windsorflowers.net/dijihuchi/3.html
随机为您推荐歌词
推荐文章

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部