精华内容
参与话题
问答
  • 进程互斥与进程同步

    2018-03-29 23:48:07
    进程互斥与进程同步 多个并发的进程存在两种类型的关系:无关的和相关的,无关进程各自执行但不会影响到其他的进程,相关的进程因为进程之间直接和间接的制约关系导致进程执行的时候因为不确定性使得得到的结果具有...

    进程互斥与进程同步

    多个并发的进程存在两种类型的关系:无关的和相关的,无关进程各自执行但不会影响到其他的进程,相关的进程因为进程之间直接和间接的制约关系导致进程执行的时候因为不确定性使得得到的结果具有不可预知性

    相关的进程并发执行后具有不可再现性,这是因为并发执行的进程之间的两种制约关系:直接制约关系,间接制约关系

    直接制约关系:因为进程直接的执行具有先后关系,即需要的执行的进程和其他进程之间需要相互合作,才能正确执行进程,这也导致了进程之间的直接制约

    间接制约关系:因为执行进程是需要资源的,而资源有限,这也导致了需要使用同一资源的进程之间具有制约关系,这也称为间接制约关系

    而因为资源共享的普遍存在,因此资源之间的竞争的间接关系是一种最简单、最基本的制约关系

    理解资源共享和导致的间接关系先从资源的使用步骤来看,用户程序使用资源的步骤是申请,使用,归还,但因为有些资源只能一次被一个进程使用,因此在申请资源时就有了先后问题,在使用资源时其他的进程必须排队

    这种一次只能被一个进程使用的资源称为临界资源,而进程对应的程序在访问临界资源时的一段程序代码又称为临界区,就是进程在资源的一次使用过程中从申请开始至归还为止的一段程序代码

    也就是说进程在临界区中执行的时候其他要进入临界区执行的进程必须等待,不允许处理器在临界区内轮流交替的执行,这也称为互斥执行

    而具有一组互斥关系的进程称为互斥进程

    详说直接制约关系

    直接制约关系具有几种分类:单向依赖关系,互相依赖关系,同步关系

    单向依赖关系:进程B执行之前必须执行进程A

    相互依赖关系:进程A和进程B相互依赖,如进程A中的L1指令的执行依赖于进程B中的L4指令的执行,而进程B中的L3指令的执行依赖于进程A中L1指令的执行,而若是进程A的第一次执行不受限制,那么可以反复的执行进程A和进程B中的指令,这就是相互依赖关系

    同步关系:具有单向依赖关系或者相互依赖关系的进程就是同步的关系,也称为同步进程

    引入制约关系的用处

    因为相关进程的正确执行需要按照一定的顺序才能保证确定的执行结果,而这些依赖关系则保证的进程的正确顺序的执行,因此有了根据这些关系执行进程的机制,这个机制称为进程同步机制

    常用的进程同步机制:加锁机制、标志位机制、信号量机制、管程机制

    加锁机制

    因为进程之间具有互斥关系,因此用加锁机制来控制进程的执行就是对进程互斥关系的实现,也就是说因为临界区一次只能执行一个进程,通过控制进程进入临界区来控制进程的执行的顺序,也就是对临界区执行的控制,其他的进程同步机制也是由此来控制进程的执行顺序

    先来讲讲临界区管理的四个准则:空闲让进,忙则等待,有限等待,让权等待

    空闲让进是指临界区没有进程执行时就让其他进程进入,忙则等待是指临界区中有进程执行是其他的想要进入临界区的进程要排队等待,有限等待是指要进入临界区的进程在等待有限的时间之后就能够进入临界区,让权等待是指进程在离开临界区之后就会让其他的进程进入临界区

    加锁机制原理

    加锁机制顾名思义就是在进程进入临界区之后在临界区的入口加锁使得其他要进入临界区的进程不能进入临界区,在进程离开临界区的时候才解锁

    加锁机制需要用到的几个内容:锁变量key,加锁操作lock(key),解锁操作unlock(key)

    锁变量key

    就和钥匙一样,用来开锁的一个变量,锁变量取0的时候能开锁,此时临界资源是空闲的,进程可以进入临界区执行,锁变量取1的时候不能开锁,此时临界资源已经被某个进程占用,不能进入临界区执行

    加锁操作lock(key)

    加锁操作的定义如下:

    lock(key)

    {

    while(key==1);

    key=1;

    }

    如上定义,如果说锁变量key为1,那么进入lock之后将会执行while语句,一直执行下去,无法执行下一条指令,也就是无法使得进程进入临界区,如果说锁变量key为0,那么进入lock之后将不会执行while语句,key变为1,执行下一条指令,进程进入临界区,而由于key变成了1,使得其他的进程无法进入临界区

    解锁操作unlock(key)

    解锁操作的定义如下:

    unlock(key)

    {

    key=0;

    }

    当进程从临界区出来的时候执行解锁操作,key由1变成0,则下一个进程就能进入临界区了

    普通加锁机制的问题

    假如说有A,B两个进程,在执行进程A中的加锁操作lock(key)中的while语句后直接跳转执行进程B,而此时key仍然为0,因此进程B进入临界区而且加上了锁key变成了1,但此时若再回到进程A中恢复现场,直接执行了while语句后的key=1语句,进程A也加上锁进入临界区,此时进程之间的执行就出错了,因此为了改进这种错误,可以借助硬件实现加锁操作,就不会存在这种问题

    加锁机制分析(互斥关系)

    一、普通的加锁机制容易出问题,不能实现互斥关系,因此需要借助硬件的加锁机制才能实现进程的互斥关系

    二、存在“忙等待”现象,浪费了处理器的时间

    什么意思呢,就是说因为while语句的循环是持续不断的,只有等待其他的进程出了临界区的时候while语句才会停止,这就使得处理器虽然被分配给这个进程,但是因为不断的执行while循环导致处理器被浪费了

    三、存在“饥饿”现象

    比如进程A在执行while循环,进程B在临界区中执行,当进程B出来之后可能并不执行进程A而是去执行进程C,以此类推,某些进程可能永远得不到执行而一直处于循环之中,就像不能吃饭一样,因此叫做饿死现象

    四、多个锁变量加锁操作可能造成进程死锁

    信号量机制(互斥关系)

    简单的说就是利用变量—信号量的值(大于0或者小于0或者等于0)来作为判定条件,通过增减信号量的值来控制进程的唤醒,执行,和堵塞

    信号量机制原理

    三个定义:信号量,P操作,V操作

    信号量

    一种变量,一个信号量有整型变量value和等待队列bq两部分组成,信号量数据类型简化定义如下

    struct semaphore{

    int value;

    PCB *bq;

    }

    P操作

    通俗的讲就是执行P操作来判定是否将该进程放入临界区,具体定义如下

    P(s)

    {

    s.value=s.value-1;

    if(s.value<0) blocked(s);

    }

    这里block(s)是阻塞原语,将当前p(s)操作的进程设置为阻塞状态并加入到信号量s对应的等待队列,这里不好理解,下面会举例分析

    V操作

    就是进程从临界区出来的时候会执行的操作,定义如下

    V(s)

    {

    s.value=s.value+1;

    if(s.value<=0) wakeup(s);

    }

    这里wakeup(s)是唤醒语句,就是从信号量s对应的等待队列bq中唤醒一个进程,也就是从等待队列bq中选择一个进程将其转化为就绪状态

    在信号量机制中p和v操作都被定义为原语,即不可被打断

    PV操作中的s是互斥变量,初始值为1

    下面关于信号量机制的分析

    s.value一开始是1,那么执行P操作的时候,s.value--,变成了0,那么不执行P操作中的if语句,即执行P操作所在的进程,而在执行完进程之后执行V操作,因为s.value++,s.value变成了1,显然就又回到了原本的s.value的值

    加如有几个进程A,B,C...在执行完进程A的P操作,然后再去执行进程B的P操作,此时s.value的值经过s.value--,s.value--此时其值为-1,则执行进程B中的if语句,将进程B变为阻塞状态加入到信号s对应的等待队列中,等到进程A执行V操作时由于s.value<=0,则执行V操作中的if语句,从而唤醒等待队列中的一个进程

    如此实现了进程之间的互斥执行

    接下来讲一讲信号量机制和同步关系

    从上文可以知道同步关系是由单向依赖关系和相互依赖关系,其中单向依赖关系又称为简单同步关系,相互依赖关系又称为一般同步关系

    信号量机制和简单同步关系

    先假设由两个进程A,B,其中进程A单向依赖于进程B,此时进程A仅有P操作,进程B仅有V操作,我们将s的初值定义为0,即s.value=0,那么在执行进程A中的P操作的时候,因为s.value=0则进程A阻塞进入等待队列而执行进程B,而因为此时s.value=-1则执行进程B中的if语句唤醒进程A,从而两进程之间符合单向依赖关系

    若是进程B先执行,那么此时s.value=0执行完进程B的V操作之后s.value=1就能直接执行进程A了

    信号量机制和一般同步关系

    因为有两个依赖关系,所以定义两个信号量s1=1和s2=0,则进程A的L1指令中有P(s1)和L2指令中有V(s2)进程B有L3指令中有P(s2)和L4指令中有V(s1),则进程A一开始不需要条件即可执行,即s1=1时执行进程A中的L1指令则s1变成0,待执行到进程A的L2指令中V操作时由于s2为0,则s2变成1,从而执行进程B中的L3指令时s2为1,则可执行,执行到进程B中的L4指令是s1由0变成1,关系图如下,读者自行领会即可

    进程A 进程B

    L1:P(s1) L3:P(s2)

    L2:P(s2) L4:P(s1)

    《计算机操作系统原理分析》笔记

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • 进程互斥与同步

    2016-11-30 14:43:09
    利用Windows提供的API函数,编写程序,解决生产者消费者问题,实现进程互斥与同步
  • 进程同步与互斥

    2013-12-19 10:17:14
    有关于进程同步互斥的C语言实现,希望对你们有帮助!
  • 进程同步与互斥基础

    千次阅读 2013-11-02 15:07:53
    同步:为了完成某个任务而建立的两个或多个进程,这些进程为了需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。进程间的制约关系就是源于它们之间的相互合作。 互斥:当一个进程进入临界区...

    一、基本概念

    同步:为了完成某个任务而建立的两个或多个进程,这些进程为了需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。进程间的制约关系就是源于它们之间的相互合作。

    互斥:当一个进程进入临界区使用临界资源是,另一个进程必须等待,当占用临界区资源的进程退出临界区以后才允许进入临界区,访问资源。注意,这里的一个并非卡死就一次只能一个进程访问临界资源。当信号量个数大于1的时候,一次可以有多个进程同时访问临界资源。前文的互斥定义只是最原始的定义。

    二、同步准则

    1)空闲让进:临界区空闲时,应该允许某个进程立即进入临界区访问临界资源。

    2)忙则等待:当临界区进程访问数达到方位上限时,其他试图进入临界区的进程应该等待。

    3)有限等待:应该避免进程一直等待永远进入不了临界区的情况。

    4)让权等待:“权”即CPU使用权,当进程不能进入临界区的时候,应该放弃使用CPU,进入等待队列,而不是“忙等待”。

    为了记忆,我们做个比喻:假设厕所就是临界区,擦屁股纸就是CPU。很不幸一个厕所只有一卷擦屁股纸。然后突然来了一群尿急的人在外面排队。厕所里没人了,当然应该让外面等的人进去(空闲让进);厕所里有人了,外面的人再尿急也应该等待(忙则等待);但是外面的人总不可能一直憋着不让上吧(有限等待);你不上厕所,就别把擦屁股纸抓在手里,拿给别人用用呗(让权等待)。

    三、信号量实现同步

    信号量课分为整性信号量和记录型信号量,二者的区别是整型信号量使用的是while循环不断测试,会产生“忙等待”。记录型信号量则是将等待进程加入等待队列,避免了“忙等待”。具体定义请自己Google。

    进程同步互斥的三种基础模型

    1)利用信号量实现同步

    设有两个进程p1,p2 ,p2的Y语句需要等待p1中X语句的执行结果,说白了就是p2要等p1中x 语句执行完毕才能执行Y语句(Y→X )

    semaphore s=0;
    p1()
    {
      ...
      x;//语句x
      v(s);//通知进程p2,语句x已经执行完毕
      ...
    }
    p2()
    {
      ...
      p(s);//当x未执行则陷入等待
      y;//此时x语句已执行完,可以执行y语句了
      ...
    }
    2)利用信号量实现互斥

    假设一次只能有一个进程进入临界区,则设置信号量S=1(即可用资源数为1)。假设此时有两个进程P1,P2(实际上可以有多个进程),那么实现临界资源互斥访问的算法如下:

    semaphore s=1;
    p1()
    {
       ...
       p(s);
       ...//临界区
       v(s);
       ...
    }
    p2()
    {
       ...
       p(s);
       ...//临界区
       v(s);
       ...
    }
    3)利用信号量实现前驱关系

    下图给出了s1,s2,s3...s6六个进程间的依赖关系,为使六个进程得到有序的运行,需要对每个“依赖”用一个信号量来保证,为此我们针对这七个依赖设了七个信号量,分别是:a1,a2,b1,b2,c,d和e(均展示在图上)


    s1()
    {
      ...
      v(a1);v(a2);//告知s2、s3已执行完
    }
    s2()
    {
      ...
      p(a1);//等待s1执行完
      ...
      v(b1);v(b2);//告知s4、s5已执行完
    }
    s3()
    {
      ...
      p(a2);//等待s1执行完
      ...
      v(c);//告知s6已执行完
    }
    s4()
    {
      ...
      p(b1);//等待s2执行完
      ...
      v(d);//告知s6已执行完
    }
    s5()
    {
      ...
      p(b2);//等待s1执行完
      ...
      v(e);//告知s6已执行完
    }
    s6()
    {
      ...
      p(c);p(d);p(e);//等待s3,s4,s5执行完
      ...
    }

    四、分析进程同步互斥的步骤

    1)关系分析:找出进程数目,分析进程之间的依赖关系。弄清进程间是同步、互斥还是前驱关系的?最好展示在一张图上,分别用不同的符号表示不同的关系。

    2)整理思路:找出解决问题的关键点,并根据做过的题目找出解决的思路,根据操作流程确定P、V的大致顺序。

    3)设置信号量:根据上面两步,确定信号量的个数以及每个信号量的初始值。

    展开全文
  • 进程互斥与同步

    2019-10-05 09:59:46
    1、解释并发并行,并说明两者关系。 并发:在操作系统中,是指一个时间段中有几个程序都处于已启动运行到运行完毕之间,且这几个程序都是在同一个处理机上运行,担任一个时刻点上只有一个程序在处理机上运行。 ...

    1、解释并发与并行,并说明两者关系。

    并发:在操作系统中,是指一个时间段中有几个程序都处于已启动运行到运行完毕之间,且这几个程序都是在同一个处理机上运行,担任一个时刻点上只有一个程序在处理机上运行。

    并行:当系统有一个以上CPU时,则线程的操作有可能非并发。当一个CPU执行一个线程时,另一个CPU可以执行另一个线程,两个线程互不抢占CPU资源,可以同时进行,这种方式我们称之为并行。

    并发是多个事件在同一时间段执行,而并行是多个事件在同一时间点执行。

     

    2、进程间有哪几种关系?分别要采取什么策略?

    有竞争关系和协助关系。

    竞争关系:批处理系统中建立多个批处理进程,分时系统中建立多个交互式进程,他们共享一套计算机系统资源,使得原本不存在逻辑关系的诸进程因共享资源而产生交互和制约关系,这是间接制约关系,又称互斥关系,操作系统必须协调进程对共享资源的争用。
    协作关系:为了完成共同的任务需要分工协作,由于每个进程都独立地以不可预知的速度推进,在执行的先后次序上就要有约束,需要相互协作的进程在某些关键点上协调各自的工作。当其中的一个进程到达关键点后,在尚未得到其伙伴进程发来的消息或信号之前应阻塞自己,等待协作者发来信号或消息后方被唤醒并继续执行。这种协作进程之间需要排定执行先后次序的协调关系是直接制约关系,称为进程同步。

     

    3、为什么说进程的互斥也是一种同步?

    在操作系统中,当某一进程正在访问某一存储区域时,就不允许其他进程进行读写或者修改该存储区的内容,否则就会发生后果无法估计的错误。进程之间的这种相互制约的关系成为进程互斥。

    并发进程在一些关键点上可能需要互相等待与互通消息,这种相互制约的等待与互通信息称为进程同步。

    实际上进程互斥也是一种同步,他协调多个进程互斥进入同一个临界资源对应的临界区。

     

    4、解释死锁与“饥饿”,并说明两者关系。

    死锁是因进程竞争资源或推进顺序不当而有可能造成的一种僵局,即系统中两个或多个进程无限期地等待永远不会发生的条件,这些进程都不能向前推进,这就叫死锁。

    “饥饿”是指系统中的每个资源占用者都在有限的时间内释放它所占用的资源,但是仍然存在申请者永远得不到资源的现象。

    死锁和“饥饿”二者都是由于竞争资源而引起的。

     

    5、什么叫做临界区?如何解决进程对临界资源的访问冲突?

     临界区:指的是一个访问共用资源的程序片段,而这些共用资源又无法同时被多个线程访问的特性。当有线程进入临界区段时,其他线程或是进程必须等待,有一些同步的机制必须在临界区段的进入点与离开点实现,以确保这些共用资源是被互斥获得使用,例如:semaphore。只能被单一线程访问的设备,例如:打印机。

    为禁止两个进程同时进入临界区,同步机制应遵循以下准则:

    空闲让进。临界区空闲时,可以允许一个请求进入临界区的进程立即进入临界区。

    忙则等待。当已有进程进入临界区时,其他试图进入临界区的进程必须等待。

    有限等待。对请求访问的进程,应保证能在有限时间内进入临界区。

    让权等待。当进程不能进入临界区时,应立即释放处理器,防止进程忙等待。

     

    6、信号量的物理意义是什么?

    信号量:有时被称为信号灯,是在多线程环境下使用的一种设施,是可以用来保证两个或多个关键代码段不被并发调用。在进入一个关键代码段之前,线程必须获取一个信号量;一旦该关键代码段完成了,那么该线程必须释放信号量。其它想进入该关键代码段的线程必须等待直到第一个线程释放信号量。

    转载于:https://www.cnblogs.com/chenwenchao123/p/10756787.html

    展开全文
  • 进程同步与进程互斥

    2020-02-18 18:35:39
    (1)什么是进程同步 (2)什么是进程互斥 2.什么是进程同步 进程具有异步性的特征。异步性是指,各并发执行的进程以各自独立的、不可预知的速度向前推进。 再看另一个例子:进程通信--------管道通信 读进程和写...

    1. 知识一览

    同步、互斥问题
    (1)什么是进程同步
    (2)什么是进程互斥

    2.什么是进程同步

    进程具有异步性的特征。异步性是指,各并发执行的进程以各自独立的、不可预知的速度向前推进。
    在这里插入图片描述再看另一个例子:进程通信--------管道通信
    在这里插入图片描述
    读进程和写进程并发地运行,由于并发必然导致异步性,因此“写数据"和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中,又必须按照“写数据≥读数据”的顺序来执行的。

    如何解决这种异步问题,就是“进程同步”所讨论的内容。

    同步亦称直接制约关系,它是指为完成某种任务而建立的两个或多个进程,这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

    3 .什么是进程互斥

    进程的“并发"需要“共享”的支持。各个并发执行的进程不可避免的需要共享一些系统资源(比如内存,又比如打印机、摄像头这样的I/O设备)

    两种资源共享方式

    互斥共享方式
    系统中的某些资源,虽然可以提供给多个进程使用,但一个时间段内只允
    许一个进程访问该资源

    同时共享方式
    系统中的某些资源,允许一个时间段内由多个进程“同时”对它们进行访问

    我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备( 比如摄像头、打印机)都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。

    对临界资源的访问,必须互斥地进行。互斥,亦称间接制约关系。进程互斥指当一个进程访问某临界资源时,另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束,释放该资源之后,另一个进程才能去访问临界资源。

    对临界资源的互斥访问,可以在逻辑上分为如下四个部分:
    在这里插入图片描述
    注意:
    临界区是进程中访问临界资源的代码段。
    进入区和退出区是负责实现互斥的代码段。
    临界区也可称为“临界段”。

    为了实现对临界资源的互斥访问,同时保证系统整体性能,需要遵循以下原则:
    1.空闲让进。临界区空闲时,可以允许一个请求进入临界区的进程立即进入临界区
    2.忙则等待。当已有进程进入临界区时,其他试图进入临界区的进程必须等待
    3. 有限等待。对请求访问的进程,应保证能在有限时间内进入临界区(保证不会饥饿)
    4. 让权等待。当进程不能进入临界区时,应立即释放处理机,防止进程忙等待。
    在这里插入图片描述

    4. 小结

    在这里插入图片描述

    展开全文
  • 乐观锁和悲观锁 首先我们理解下两种不同思路的锁,乐观锁和悲观锁。 这两种锁机制,是在多用户环境并发控制的两种所机制。下面看百度百科对乐观锁和悲观锁两种锁机制的定义: 乐观锁( Optimistic Locking ) ...
  • 进程同步与互斥

    2018-09-13 20:49:17
    进程同步互斥  临界资源:多个进程或者线程都能操作的共享资源  临界区:操作临界资源的代码段  同步是一种合作关系:为完成某个任务,多进程和多线程之间形成一种协调,按照约定或条件执行操作临界资源  互斥:...
  • 进程互斥与同步

    千次阅读 2017-05-15 22:18:21
    进程互斥与同步实验题目:进程间的互斥与同步 实验内容:编写算法,实现进程间对临界资源的互斥访问以及进程间的同步关系 实验要求: 1、要求进程互斥使用文本文件; 2、假定文本文件txt1最大可写入30个字符; ...
  • [OS复习]进程互斥与同步1

    千次阅读 2016-08-03 10:47:49
    进程互斥与同步 1.引言:多道程序设计存在的问题? 采用多道程序设计技术的操作系统,允许多个进程同时驻留内存并发执行。思考: A.如何协调多个进程对系统资源,如内存空间、外部设备等的竞争和共享? B.如何解决...
  • 软件方法是指由进程自己,通过执行相应的程序指令,实现与别的进程同步与互斥,无须专门的程序设计语言或操作系统的支持。实践证明,该方法很难正确控制进程间的同步与互斥,而且可能会大大地增加系统的额外开销。

空空如也

1 2 3 4 5 ... 20
收藏数 20,240
精华内容 8,096
关键字:

互斥 同步