精华内容
下载资源
问答
  • 同步和互斥

    2018-05-01 22:09:00
    同步和互斥的区别 1. 同步,又称直接制约关系,是指多个线程(或进程)为了合作完成任务,必须严格按照规定的 某种先后次序来运行。(必须有先后顺序) 2. 互斥,又称间接制约关系,是指系统中的某些共享资源,一次只...

    同步和互斥的区别

    1. 同步,又称直接制约关系,是指多个线程(或进程)为了合作完成任务,必须严格按照规定的 某种先后次序来运行。(必须有先后顺序)
    2. 互斥,又称间接制约关系,是指系统中的某些共享资源,一次只允许一个线程访问。当一个线程正在访问该临界资源时,其它线程必须等待。(我只想你不能执行)

    转载于:https://www.cnblogs.com/dengyongkang/p/8977770.html

    展开全文
  • 本文主要讲述了操作系统中同步和互斥这两个概念,并说明了操作系统中是如何实现同步和互斥的。除此之外,本文还重点讲述了线程和进程的概念。


    在讲同步和互斥之前,需要先熟悉一些计算机相关的基础概念

    计算机基础知识

    进程和线程

    • 进程(Process),顾名思义就是正在执行的应用程序,是软件的执行副本。而线程是轻量级的进程。

    • 进程是分配资源的基础单位。而线程是程序执行的基本单位。

    每一种应用,比如游戏,执行后是一个进程。但是游戏内部需要图形渲染、需要网络、需要响应用户操作,这些行为不可以互相阻塞,必须同时进行,这样就设计成线程。现代的CPU以多线程为主,如下内容也主要是说多线程,我们讲的调度更多的也是线程的调度。

    计算机的资源

    我们经常讲操作系统需要分配资源,最重要的 3 种资源是:计算资源(CPU)内存资源文件资源。计算机的CPU是有限的,而需要执行的任务往往有多个,CPU无法同时执行所有的任务,只能挨个执行,这就相当于是给任务(线程)分配了计算资源,得到了计算资源的任务就可以被执行。文件资源比如计算机中存储的文件是文件资源。

    归根到底不管是计算机的组成还是操作系统,都面临着资源有限,而使用资源的任务(用户)却非常多,如何合理的安排资源,使得任务都能得到更好的执行,不管是线程和进程的设计也好,还是计算机的三级存储结构也好,都是在权衡利弊以及成本的基础上,为了更好的统筹规划资源而设计出来的。

    内核

    操作系统的内核

    在这里插入图片描述

    用户态和内核态

    在这里插入图片描述

    内核线程和用户线程

    线程设计出来后,因为只被分配了计算资源(CPU),因此被称为轻量级进程。被分配的方式,就是由操作系统调度线程。操作系统创建一个进程后,进程的入口程序被分配到了一个主线程执行,这样看上去操作系统是在调度进程,其实是调度进程中的线程。

    这种被操作系统直接调度的线程,我们也成为内核级线程。另外,有的程序语言或者应用,用户(程序员)自己还实现了线程。相当于操作系统调度主线程,主线程的程序用算法实现子线程,这种情况我们称为用户级线程。Linux 的 PThread API 就是用户级线程,KThread API 则是内核级线程。

    进程的开销比线程大在了哪里?

    以Linux为例:Linux 中创建一个进程自然会创建一个线程,也就是主线程。创建进程需要为进程划分出一块完整的内存空间,有大量的初始化操作,比如要把内存分段(堆栈、正文区等)。创建线程则简单得多,只需要确定 PC 指针和寄存器的值,并且给线程分配一个栈用于执行程序,同一个进程的多个线程间可以复用堆栈。因此,创建进程比创建线程慢,而且进程的内存开销更大。

    线程的同步和互斥

    什么是同步,什么是互斥?

    同步:线程同步并不是说线程同时运行,而是让线程按照一定的顺序执行,使得最后的数据能达到同步。考虑这么一个场景,教室里很多学生,每个学生都在说话,七嘴八舌的,一片混论。如果这些同学挨个起来发言,或者是是以一个组为单位来发言 ,就会显得井然有序,大家也都能听到他们在说什么。同理,多线程的情况下,如果不加以控制,多个线程一起对数据进行添加或者是修改,数据会异常混论,就像是七嘴八舌的声音一样。我们写程序的目的,无非就是为了处理数据,处理数据的输入和输出,如果最后得到的输出不受你的控制,这个程序还有什么用?

    互斥:有一些资源,比如:打印机。一次只能被一个线程访问,不允许多个线程同时访问,这种资源叫做临界资源。因此一个线程在访问这种资源的时候,其它线程不能访问,这就叫做互斥。【临界区:访问临界资源的那一段代码就叫做临界区。线程只有先进入临界区的才能访问到临界资源。】

    一般来说:要实现同步,就得先实现互斥。比如上面同步中所举的那个场景,我们要让学生挨个起来发言,就得先保证一个同学发言的时候,其它同学不要发言,这就是一种互斥

    操作系统实现同步的方式

    1. 使用互斥量(Mutex):采用互斥对象机制,只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个,所以可以保证公共资源不会被多个线程同时访问。比如Java中的synchronized关键词和各种Lock都是这种机制。

    2. 使用信号量(Semphares) :它允许同一时刻多个线程访问同一资源,但是需要控制同一时刻访问此资源的最大线程数量

    什么是信号量呢?可以看一下如下的例子

    考虑有两个函数up和down。uplock增 1,downlock减 1。当 lock 为 0 时,如果还在down这个函数里,那么会自旋。

    其中的cas是指CPU中的原子操作其伪代码形式可以这样表示:cas(&oldValue, expectedValue, targetValue)。比如我们要执行a++;假设a的初值为0,则可以这么写cas(&a, 0, 1),表示什么意思呢?先去存储a的地址空间中取出a的值,如果a的值是0,我就执行更新操作,使得a的值变为1,然后再写回去,否则不更新a的值。为什么执行一个a++都要这么麻烦呢?为的就是再多线程并发的情况下防止其它线程更改a的值

    up(&lock){
      while(!cas(&lock, lock, lock+1)) { }
    }
    
    down(&lock){
      while(!cas(&lock, lock, lock - 1) || lock == 0){}
    }
    

    考虑到多线程的情况下执行下面这个程序

    int lock = 2;
    down(&lock);
    // 临界区
    up(&lock);
    

    如果只有一个线程在临界区,那么lock等于 1,第 2 个线程还可以进入。 如果两个线程在临界区,第 3 个线程尝试down的时候,会陷入自旋锁。当然我们也可以用其他方式来替代自旋锁,比如让线程休眠。

    lock初始值为 1 的时候,这个模型就是实现互斥(mutex)。如果 lock 大于 1,那么就是同时允许多个线程进入临界区。这种方法,我们称为信号量(semaphore)

    1. 使用事件(Event) : 比如Wait/Notify:通过通知操作的方式来保持多线程同步。

    操作系统实现互斥的方法:

    • 软件实现互斥的方法
    1. 单标志法:设置一个公共的整形变量:turn。比如turn = 1则表示运行1这个进程进入临界区获得临界资源,其它线程则不允许进入。

    2. 双标志法先检查:每个线程在进入临界区访问临界资源之前,先查看临界资源是否正在被访问,若正在被访问,该线程需要进行等待;若临界资源没有被访问,该线程则进入临界区访问临界资源。我们可以设置一个标志数组flag[],flag[i] = true,则表示i这个线程在访问临界资源,flag[i] = false则表示该线程没有访问临界资源。当i线程检测到没有其它线程在访问临界资源时,则进入临界区,并将flag[i]设置为true。

      可能出现的问题:两个线程同时进入临界区。因为线程是先查看有没有其它线程在访问临界资源,然后在没有其它线程访问临界资源时再进入临界区访问临界资源,这两个步骤间是有一定的时间间隔的。考虑两个线程T1和T2。T1先检查有没有线程没有访问临界资源,检查结果发现,没有其它线程访问临界资源,于是准备进入临界区访问临界资源,T1正准备进入却还没有进入的时候。【发生这样原因除了是因为执行的过程中存在时间间隔,还有个原因就是可能会发生线程切换】T2也开始检查有没有线程访问临界资源,检查结果发现没有线程访问临界资源,于是T2也开始准备进入临界区访问临界资源。这下好了,T1和T2都检测到没有其它线程在访问临界资源,于是,都进入了临界区,很显然违背了互斥。

    3. 双标志法后检查:双标志法先检查是先检测临界资源的状态,然后再设置自己的标志。双标志后检查则相反:若一个线程准备访问临界资源,先将自己的标志位设置为true,然后再检查其它的线程的标志位,若检测到其它某个线程的标志位为true,则该线程等待,否则进入临界区。

      可能出现的问题:导致饥饿状态,没有一个线程能进入临界区。考虑两个线程T1和T2。T1准备访问临界资源,于是将自己的标志位设置为true。在T1还未开始检测其它线程的状态时,T2刚好也准备访问临界资源,于是T2也赶紧将自己的标志位设置为true。这下好了,这两个线程检查是否有其它线程访问临界资源的时候,都能检查到对方的标志位为true,这两个线程就这样僵持着,互相都无法访问临界资源

    4. Peterson(彼得森)算法:除了用一个flag[]数组来标志线程是否在访问临界资源或者是是否正准备访问临界资源,还设置了一个公共变量turn。

      伪代码如下:

      考虑两个线程i和j。
      在这里插入图片描述
      首先考虑3的那种情况。首先是i线程准备访问临界资源,于是将自己的标志位设置为true。然后呢,i线程假设此刻是j线程在访问临界区,于是将true设置为j。就在此时,j线程也准备访问临界资源,于是将自己的标志位设置为true,j线程也同样做了一个假设,假设此刻是i线程在访问临界区,于是把true的值设置为了i。最终,true的值变成了i。紧接着i线程开始在while循环中判断条件了,flag[j] == true成立,但是turn的值已经被j线程设置为了i,于是turn == j不成立,因此该循环条件不满足,i线程不执行该循环,i线程成功进入到临界区,避免了双标志法后检查产生的饥饿问题。

    • 硬件实现方法
    1. 中断屏蔽方法

      当一个线程获得了CPU的计算资源时,除非发生中断,否则,是不会发生线程切换的。我们的计算机能同时运行多个程序,并不是说这些程序同时获得了CPU的计算资源,而是CPU在不停地切换线程或者是进程,比如先执行A线程,执行了一会以后,然后对A线程发起中断请求,A线程被中断了,然后交出了运行权,接着发生线程切换。然后CPU又赶紧去执行B线程。B线程执行了一会有切换到其它线程。CPU的运算速度非常快,很短的时间内就能执行大量的代码,而线程切换的速度又非常快,所以给我们造成了一种程序在并行执行的现象。

      一个线程准备访问临界资源时,先屏蔽中断,屏蔽了中断就意味着这样该线程不会被中断,某种程度上就意味着该线程是独占CPU了,其它线程不会被得到执行,只有当该线程执行完毕,再开启中断以后,其它线程才可能得到执行。

    2. 硬件指令方法

      在计算机中,有一些指令是原子级的指令,也就是说指令在执行的过程中,不会发生线程切换而导致执行过程被中断。比如TAS(Test and Set),CAS(Compare and Swap)。回想我们用软件实现互斥的方法的时候,比如双标志检查法,不管是先检查还是后检查。都存在着被打断的问题。比如T1线程先检测,发现没有其它线程使用临界资源,正当T1准备进入还没有进入的时候,T2线程却来捣乱了,偷偷将一些标志位给发生了改变。由于T1已经检测过了,所以它以为一切正常,继续执行,殊不知有些内容已经被修改了。如果我们把T1检测是否有其它线程使用中断,如果没有,将自己的值设置为true,否则,继续轮询这些操作封装成一个原子过程,也就是T1在执行这些代码的时候,一气呵成的执行完毕,不允许其它线程插进来捣乱,就不会发生同时进入临界区或者是发生饥饿的现象了。

    参考
    《王道操作系统考研复习指导》

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

    万次阅读 多人点赞 2018-10-01 09:18:20
    2.9 进程同步的基本概念:临界资源、同步和互斥 在多道程序环境下,进程是并发执行的,不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系,引入了进程同步的概念。 临界资源 虽然多个进程...
    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/bigpudding24/article/details/48608537

    2.9 进程同步的基本概念:临界资源、同步和互斥

    在多道程序环境下,进程是并发执行的,不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系,引入了进程同步的概念

    临界资源

    虽然多个进程可以共享系统中的各种资源,但其中许多资源一次只能为一个进程所使用,我们把一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源,如打印机等。此外,还有许多变量、数据等都可以被若干进程共享,也属于临界资源。

    对临界资源的访问,必须互斥地进行,在每个进程中,访问临界资源的那段代码称为临界区。为了保证临界资源的正确使用,可以把临界资源的访问过程分成四个部分:
    • 进入区。为了进入临界区使用临界资源,在进入区要检查可否进入临界区,如果可以进入临界区,则应设置正在访问临界区的标志,以阻止其他进程同时进入临界区。
    • 临界区。进程中访问临界资源的那段代码,又称临界段。
    • 退出区。将正在访问临界区的标志清除。
    • 剩余区。代码中的其余部分。
      1. do {
      2. entry section; //进入区
      3. critical section; //临界区
      4. exit section; //退出区
      5. remainder section; //剩余区
      6. } while (true)

    • 同步

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

      例如,输入进程A通过单缓冲向进程B提供数据。当该缓冲区空时,进程B不能获得所需数据而阻塞,一旦进程A将数据送入缓冲区,进程B被唤醒。反之,当缓冲区满时,进程A被阻塞,仅当进程B取走缓冲数据时,才唤醒进程A。

      互斥

      互斥亦称间接制约关系。当一个进程进入临界区使用临界资源时,另一个进程必须等待, 当占用临界资源的进程退出临界区后,另一进程才允许去访问此临界资源。

      例如,在仅有一台打印机的系统中,有两个进程A和进程B,如果进程A需要打印时, 系统已将打印机分配给进程B,则进程A必须阻塞。一旦进程B将打印机释放,系统便将进程A唤醒,并将其由阻塞状态变为就绪状态。

      为禁止两个进程同时进入临界区,同步机制应遵循以下准则:
      • 空闲让进。临界区空闲时,可以允许一个请求进入临界区的进程立即进入临界区。
      • 忙则等待。当已有进程进入临界区时,其他试图进入临界区的进程必须等待。
      • 有限等待。对请求访问的进程,应保证能在有限时间内进入临界区。
      • 让权等待。当进程不能进入临界区时,应立即释放处理器,防止进程忙等待。

    • 2.10 实现临界区互斥的基本方法

      软件实现方法

      在进入区设置和检查一些标志来标明是否有进程在临界区中,如果已有进程在临界区,则在进入区通过循环检查进行等待,进程离开临界区后则在退出区修改标志。

      1) 算法一:单标志法。

      该算法设置一个公用整型变量turn,用于指示被允许进入临界区的进程编号,即若turn=0,则允许P0进程进入临界区。该算法可确保每次只允许一个进程进入临界区。但两个进程必须交替进入临界区,如果某个进程不再进入临界区了,那么另一个进程也将进入临界区(违背“空闲让进”)这样很容易造成资源利用的不充分。
      1. </pre><pre name="code" class="cpp">// P0进程
      2. while(turn!=0);
      3. critical section;
      4. turn=1;
      5. remainder section;
      
      
      
      
      
      
      1. // P1进程
      2. while(turn!=1); // 进入区
      3. critical section; // 临界区
      4. turn = 0; // 退出区
      5. remainder section; // 剩余区

      
      

      2) 算法二:双标志法先检查。

      该算法的基本思想是在每一个进程访问临界区资源之前,先查看一下临界资源是否正被访问,若正被访问,该进程需等待;否则,进程才进入自己的临界区。为此,设置了一个数据flag[i],如第i个元素值为FALSE,表示Pi进程未进入临界区,值为TRUE,表示Pi进程进入临界区。
      1. // Pi 进程
      2. while(flag[j]); // ①
      3. flag[i]=TRUE; // ③
      4. critical section;
      5. flag[i] = FALSE;
      6. remainder section;

      
      
      1. // Pj 进程
      2. while(flag[i]); // ② 进入区
      3. flag[j] =TRUE; // ④ 进入区
      4. critical section; // 临界区
      5. flag[j] = FALSE; // 退出区
      6. remainder section; // 剩余区

      
      优点:不用交替进入,可连续使用;缺点:Pi和Pj可能同时进入临界区。按序列①②③④ 执行时,会同时进入临界区(违背“忙则等待”)。即在检查对方flag之后和切换自己flag 之前有一段时间,结果都检查通过。这里的问题出在检查和修改操作不能一次进行。
      

      3) 算法三:双标志法后检查。

      算法二是先检测对方进程状态标志后,再置自己标志,由于在检测和放置中可插入另一个进程到达时的检测操作,会造成两个进程在分别检测后,同时进入临界区。为此,算法三釆用先设置自己标志为TRUE后,再检测对方状态标志,若对方标志为TURE,则进程等待;否则进入临界区。
    1. // Pi进程
    2. flag[i] =TRUE;
    3. while(flag[j]);
    4. critical section;
    5. flag[i] =FLASE;
    6. remainder section;

    
    
    1. // Pj进程
    2. flag[j] =TRUE; // 进入区
    3. while(flag[i]); // 进入区
    4. critical section; // 临界区
    5. flag [j] =FLASE; // 退出区
    6. remainder section; // 剩余区

    
    当两个进程几乎同时都想进入临界区时,它们分别将自己的标志值flag设置为TRUE,并且同时检测对方的状态(执行while语句),发现对方也要进入临界区,于是双方互相谦让,结果谁也进不了临界区,从而导致“饥饿”现象。
    

    4)算法四:Peterson’s Algorithm。

    为了防止两个进程为进入临界区而无限期等待,又设置变量turn,指示不允许进入临界区的进程编号,每个进程在先设置自己标志后再设置turn 标志,不允许另一个进程进入。这时,再同时检测另一个进程状态标志和不允许进入标志,这样可以保证当两个进程同时要求进入临界区,只允许一个进程进入临界区。
    1. // Pi进程
    2. flag[i]=TURE; turn=j;
    3. while(flag[j]&&turn==j);
    4. critical section;
    5. flag[i]=FLASE;
    6. remainder section;

    1. // Pj进程
    2. flag[j] =TRUE;turn=i; // 进入区
    3. while(flag[i]&&turn==i); // 进入区
    4. critical section; // 临界区
    5. flag[j]=FLASE; // 退出区
    6. remainder section; // 剩余区

    
    本算法的基本思想是算法一和算法三的结合。利用flag解决临界资源的互斥访问,而利用turn解决“饥饿”现象
    

    硬件实现方法

    本节对硬件实现的具体理解对后面的信号量的学习很有帮助。计算机提供了特殊的硬件指令,允许对一个字中的内容进行检测和修正,或者是对两个字的内容进行交换等。通过硬件支持实现临界段问题的低级方法或称为元方法。

    1) 中断屏蔽方法

    当一个进程正在使用处理机执行它的临界区代码时,要防止其他进程再进入其临界区访问的最简单方法是禁止一切中断发生,或称之为屏蔽中断、关中断。因为CPU只在发生中断时引起进程切换,这样屏蔽中断就能保证当前运行进程将临界区代码顺利地执行完,从而保证了互斥的正确实现,然后再执行开中断。其典型模式为:…关中断;临界区;开中断;…这种方法限制了处理机交替执行程序的能力,因此执行的效率将会明显降低。对内核来说,当它执行更新变量或列表的几条指令期间关中断是很方便的,但将关中断的权力交给用户则很不明智,若一个进程关中断之后不再开中断,则系统可能会因此终止。

    2) 硬件指令方法

    TestAndSet指令:这条指令是原子操作,即执行该代码时不允许被中断。其功能是读出指定标志后把该标志设置为真。指令的功能描述如下:
    1. boolean TestAndSet(boolean *lock){
    2. boolean old;
    3. old = *lock;
    4. *lock=true;
    5. return old;
    6. }
    
    可以为每个临界资源设置一个共享布尔变量lock,表示资源的两种状态:true表示正被占用,初值为false。在进程访问临界资源之前,利用TestAndSet检查和修改标志lock;若有进程在临界区,则重复检查,直到进程退出。利用该指令实现进程互斥的算法描述如下:
    1. while TestAndSet (& 1 ock);
    2. // 进程的临界区代码段;
    3. lock=false;
    4. // 进程的其他代码
    
    Swap指令:该指令的功能是交换两个字节的内容。其功能描述如下。
    1. Swap(boolean *a, boolean *b){
    2. boolean temp;
    3. Temp=*a;
    4. *a = *b;
    5. *b = temp;
    6. }
    
    注意:以上对TestAndSet和Swap指令的描述仅仅是功能实现,并非软件实现定义,事实上它们是由硬件逻辑直接实现的,不会被中断。应为每个临界资源设置了一个共享布尔变量lock,初值为false;在每个进程中再设置一个局部布尔变量key,用于与lock交换信息。在进入临界区之前先利用Swap指令交换lock 与key的内容,然后检查key的状态;有进程在临界区时,重复交换和检查过程,直到进程退出。利用Swap指令实现进程互斥的算法描述如下:
    1. key=true;
    2. while(key!=false)
    3. Swap(&lock, &key);
    4. // 进程的临界区代码段;
    5. lock=false;
    6. // 进程的其他代码;
    
    硬件方法的优点:适用于任意数目的进程,不管是单处理机还是多处理机;简单、容易验证其正确性。可以支持进程内有多个临界区,只需为每个临界区设立一个布尔变量。硬件方法的缺点:进程等待进入临界区时要耗费处理机时间,不能实现让权等待。从等待进程中随机选择一个进入临界区,有的进程可能一直选不上,从而导致“饥饿”现象。

    2.11 信号量:整型、记录型信号量以及利用信号量实现进程互斥和前驱关系

    信号量机构是一种功能较强的机制,可用来解决互斥与同步的问题,它只能被两个标准的原语wait(S)和signal(S)来访问,也可以记为“P操作”(通过)和“V操作(释放)”。原语是指完成某种功能且不被分割不被中断执行的操作序列,通常可由硬件来实现完成不被分割执行特性的功能。如前述的“Test-and-Set”和“Swap”指令,就是由硬件实现的原子操作。原语功能的不被中断执行特性在单处理机时可由软件通过屏蔽中断方法实现。原语之所以不能被中断执行,是因为原语对变量的操作过程如果被打断,可能会去运行另一个对同一变量的操作过程,从而出现临界段问题。如果能够找到一种解决临界段问题的元方法,就可以实现对共享变量操作的原子性。

    整型信号量

    整型信号量被定义为一个用于表示资源数目的整型量S,wait和signal操作可描述为:
    1. wait(S){
    2. while (S<=0);
    3. S=S-1;
    4. }
    5. signal(S){
    6. S=S+1;
    7. }
    
    wait操作中,只要信号量S<=0,就会不断地测试。因此,该机制并未遵循“让权等待” 的准则,而是使进程处于“忙等”的状态。
    

    记录型信号量

    记录型信号量是不存在“忙等”现象的进程同步机制。除了需要一个用于代表资源数目的整型变量value外,再增加一个进程链表L,用于链接所有等待该资源的进程,记录型信号量是由于釆用了记录型的数据结构得名。记录型信号量可描述为:
    1. typedef struct{
    2. int value;
    3. struct process *L;
    4. } semaphore;
    
    相应的wait(S)和signal(S)的操作如下:
    1. void wait (semaphore S) { //相当于申请资源
    2. S.value--;
    3. if(S.value<0) {
    4. add this process to S.L;
    5. block(S.L);
    6. }
    7. }
    
    wait操作,S.value--,表示进程请求一个该类资源,当S.value<0时,表示该类资源已分配完毕,因此进程应调用block原语,进行自我阻塞,放弃处理机,并插入到该类资源的等待队列S.L中,可见该机制遵循了“让权等待”的准则。
    void signal (semaphore S) {  //相当于释放资源
        S.value++;
        if(S.value<=0){
            remove a process P from S.L;
            wakeup(P);
        }
    }
    signal操作,表示进程释放一个资源,使系统中可供分配的该类资源数增1,故S.value++。若加1后仍是S.value<=0,则表示在S.L中仍有等待该资源的进程被阻塞,故还应调用wakeup 原语,将S.L中的第一个等待进程唤醒。

    利用信号量实现同步

    信号量机构能用于解决进程间各种同步问题。设S为实现进程P1、P2同步的公共信号量,初值为0。进程P2中的语句y要使用进程P1中语句x的运行结果,所以只有当语句x执行完成之后语句y才可以执行。其实现进程同步的算法如下:
    semaphore S = 0;  //初始化信号量
    P1 ( ) {
        // …
        x;  //语句x
        V(S);  //告诉进程P2,语句乂已经完成
    }
    P2()){
        // …
        P(S) ;  //检查语句x是否运行完成
        y;  // 检查无误,运行y语句
        // …
    }

    利用信号量实现进程互斥

    信号量机构也能很方便地解决进程互斥问题。设S为实现进程Pl、P2互斥的信号量,由于每次只允许一个进程进入临界区,所以S的初值应为1(即可用资源数为1)。只需把临界区置于P(S)和V(S)之间,即可实现两进程对临界资源的互斥访问。其算法如下:
    semaphore S = 1;  //初化信号量
    P1 ( ) {
        // …
        P(S);  // 准备开始访问临界资源,加锁
        // 进程P1的临界区
        V(S);  // 访问结束,解锁
        // …
    }
    P2() {
        // …
        P(S); //准备开始访问临界资源,加锁
        // 进程P2的临界区;
        V(S);  // 访问结束,解锁
        // …
    }
    互斥的实现是不同进程对同一信号量进行P、V操作,一个进程在成功地对信号量执行了P操作后进入临界区,并在退出临界区后,由该进程本身对该信号量执行V操作,表示当前没有进程进入临界区,可以让其他进程进入。

    利用信号量实现前驱关系

    信号量也可以用来描述程序之间或者语句之间的前驱关系。图2-8给出了一个前驱图,其中S1, S2, S3, …, S6是最简单的程序段(只有一条语句)。为使各程序段能正确执行,应设置若干个初始值为“0”的信号量。例如,为保证S1 -> S2、 S1 -> S3的前驱关系,应分别设置信号量a1、a2。同样,为了保证 S2 -> S4、S2 ->S5、S3 -> S6、S4 -> S6、S5 -> S6,应设置信号量bl、b2、c、d、e。 

    图2-8 前驱图举例



    实现算法如下:
    1. semaphore al=a2=bl=b2=c=d=e=0; //初始化信号量
    2. S1() {
    3. // …
    4. V(al); V(a2) ; //S1已经运行完成
    5. }
    6. S2() {
    7. P(a1); //检查S1是否运行完成
    8. // …
    9. V(bl); V(b2); // S2已经运行完成
    10. }
    11. S3() {
    12. P(a2); //检查S1是否已经运行完成
    13. // …
    14. V(c); //S3已经运行完成
    15. }
    16. S4() {
    17. P(b1); //检查S2是否已经运行完成
    18. // …
    19. V(d); //S4已经运行完成
    20. }
    21. S5() {
    22. P(b2); //检查S2是否已经运行完成
    23. // …
    24. V(e); // S5已经运行完成
    25. }
    26. S6() {
    27. P(c); //检查S3是否已经运行完成
    28. P(d); //检查S4是否已经运行完成
    29. P(e); //检查S5是否已经运行完成
    30. // …;
    31. }

    
    

    分析进程同步和互斥问题的方法步骤

    1) 关系分析。找出问题中的进程数,并且分析它们之间的同步和互斥关系。同步、互斥、前驱关系直接按照上面例子中的经典范式改写。2) 整理思路。找出解决问题的关键点,并且根据做过的题目找出解决的思路。根据进程的操作流程确定P操作、V操作的大致顺序。3) 设置信号量。根据上面两步,设置需要的信号量,确定初值,完善整理。

    2.12 管程:管程的定义、组成及基本特性

    管程的定义

    系统中的各种硬件资源和软件资源,均可用数据结构抽象地描述其资源特性,即用少量信息和对资源所执行的操作来表征该资源,而忽略了它们的内部结构和实现细节。管程是由一组数据以及定义在这组数据之上的对这组数据的操作组成的软件模块,这组操作能初始化并改变管程中的数据和同步进程。

    管程的组成

    1) 局部于管程的共享结构数据说明。2) 对该数据结构进行操作的一组过程。3) 对局部于管程的共享数据设置初始值的语句。

    管程的基本特性

    1) 局部于管程的数据只能被局部于管程内的过程所访问。2) 一个进程只有通过调用管程内的过程才能进入管程访问共享数据。3) 每次仅允许一个进程在管程内执行某个内部过程。由于管程是一个语言成分,所以管程的互斥访问完全由编译程序在编译时自动添加,无需程序员关注,而且保证正确。

    2.13 经典进程同步问题1:生产者-消费者问题

    问题描述

    一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区,只有缓冲区没满时,生产者才能把消息放入到缓冲区,否则必须等待;只有缓冲区不空时,消费者才能从中取出消息,否则必须等待。由于缓冲区是临界资源,它只允许一个生产者放入消息,或者一个消费者从中取出消息。

    问题分析

    1) 关系分析。生产者和消费者对缓冲区互斥访问是互斥关系,同时生产者和消费者又是一个相互协作的关系,只有生产者生产之后,消费者才能消费,他们也是同步关系。2) 整理思路。这里比较简单,只有生产者和消费者两个进程,正好是这两个进程存在着互斥关系和同步关系。那么需要解决的是互斥和同步PV操作的位置。3) 信号量设置。信号量mutex作为互斥信号量,它用于控制互斥访问缓冲池,互斥信号量初值为1;信号量full用于记录当前缓冲池中“满”缓冲区数,初值为0。信号量empty 用于记录当前缓冲池中“空”缓冲区数,初值为n。生产者-消费者进程的描述如下:
    1. semaphore mutex=1; //临界区互斥信号量
    2. semaphore empty=n; //空闲缓冲区
    3. semaphore full=0; //缓冲区初始化为空
    4. producer () { //生产者进程
    5. while(1){
    6. produce an item in nextp; //生产数据
    7. P(empty); //获取空缓冲区单元
    8. P(mutex); //进入临界区.
    9. add nextp to buffer; //将数据放入缓冲区
    10. V(mutex); //离开临界区,释放互斥信号量
    11. V(full); //满缓冲区数加1
    12. }
    13. }
    14. consumer () { //消费者进程
    15. while(1){
    16. P(full); //获取满缓冲区单元
    17. P(mutex); // 进入临界区
    18. remove an item from buffer; //从缓冲区中取出数据
    19. V (mutex); //离开临界区,释放互斥信号量
    20. V (empty) ; //空缓冲区数加1
    21. consume the item; //消费数据
    22. }
    23. }
    该类问题要注意对缓冲区大小为n的处理,当缓冲区中有空时便可对empty变量执行P 操作,一旦取走一个产品便要执行V操作以释放空闲区。对empty和full变量的P操作必须放在对mutex的P操作之前。如果生产者进程先执行P(mutex),然后执行P(empty),消费者执行P(mutex),然后执行P(fall),这样可不可以?答案是否定的。设想生产者进程已经将缓冲区放满,消费者进程并没有取产品,即empty = 0,当下次仍然是生产者进程运行时,它先执行P(mutex)封锁信号量,再执行P(empty)时将被阻塞,希望消费者取出产品后将其唤醒。轮到消费者进程运行时,它先执行P(mutex),然而由于生产者进程已经封锁mutex信号量,消费者进程也会被阻塞,这样一来生产者、消费者进程都将阻塞,都指望对方唤醒自己,陷入了无休止的等待。同理,如果消费者进程已经将缓冲区取空,即 full = 0,下次如果还是消费者先运行,也会出现类似的死锁。不过生产者释放信号量时,mutex、full先释放哪一个无所谓,消费者先释放mutex还是empty都可以

    下面再看一个较为复杂的生产者-消费者问题:

    问题描述

    桌子上有一只盘子,每次只能向其中放入一个水果。爸爸专向盘子中放苹果,妈妈专向盘子中放橘子,儿子专等吃盘子中的橘子,女儿专等吃盘子中的苹果。只有盘子为空时,爸爸或妈妈就可向盘子中放一个水果;仅当盘子中有自己需要的水果时,儿子或女儿
    可以从盘子中取出。

    问题分析

    1) 关系分析。这里的关系稍复杂一些,首先由每次只能向其中放入一只水果可知爸爸和妈妈是互斥关系。爸爸和女儿、妈妈和儿子是同步关系,而且这两对进程必须连起来,儿子和女儿之间没有互斥和同步关系,因为他们是选择条件执行,不可能并发,如图2-8所示。

    2) 整理思路。这里有4个进程,实际上可以抽象为两个生产者和两个消费者被连接到大小为1的缓冲区上。



    图2-9  进程之间的关系

    3) 信号量设置。首先设置信号量plate为互斥信号量,表示是否允许向盘子放入水果,初值为1,表示允许放入,且只允许放入一个。信号量 apple表示盘子中是否有苹果,初值为0,表示盘子为空,不许取,若apple=l可以取。信号量orange表示盘子中是否有橘子,初值为0,表示盘子为空,不许取,若orange=l可以取。解决该问题的代码如下:
    1. semaphore plate=l, apple=0, orange=0;
    2. dad() { //父亲进程
    3. while (1) {
    4. prepare an apple;
    5. P(plate) ; //互斥向盘中取、放水果
    6. put the apple on the plate; //向盘中放苹果
    7. V(apple); //允许取苹果
    8. }
    9. }
    10. mom() { // 母亲进程
    11. while(1) {
    12. prepare an orange;
    13. P(plate); //互斥向盘中取、放水果
    14. put the orange on the plate; //向盘中放橘子
    15. V(orange); //允许取橘子
    16. }
    17. }
    18. son(){ //儿子进程
    19. while(1){
    20. P(orange) ; //互斥向盘中取橘子
    21. take an orange from the plate;
    22. V(plate); //允许向盘中取、放水果
    23. eat the orange;
    24. }
    25. }
    26. daughter () { //女儿进程
    27. while(1) {
    28. P(apple); // 互斥向盘中取苹果
    29. take an apple from the plate;
    30. V(plate); //运行向盘中取、放水果
    31. eat the apple;
    32. }
    33. }
    进程间的关系如图2-9所示。dad()和daughter()、mam()和son()必须连续执行,正因为如此,也只能在女儿拿走苹果后,或儿子拿走橘子后才能释放盘子,即V(plate)操作。

    2.14 经典进程同步问题2:读者-写者问题

    问题描述

    有读者和写者两组并发进程,共享一个文件,当两个或以上的读进程同时访问共享数据时不会产生副作用,但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。因此要求:①允许多个读者可以同时对文件执行读操作;②只允许一个写者往文件中写信息;③任一写者在完成写操作之前不允许其他读者或写者工作;④写者执行写操作前,应让已有的读者和写者全部退出。

    问题分析

    1) 关系分析。由题目分析读者和写者是互斥的,写者和写者也是互斥的,而读者和读者不存在互斥问题

    2) 整理思路。两个进程,即读者和写者。写者是比较简单的,它和任何进程互斥,用互斥信号量的P操作、V操作即可解决。读者的问题比较复杂,它必须实现与写者互斥的同时还要实现与其他读者的同步,因此,仅仅简单的一对P操作、V操作是无法解决的。那么,在这里用到了一个计数器,用它来判断当前是否有读者读文件。当有读者的时候写者是无法写文件的,此时读者会一直占用文件,当没有读者的时候写者才可以写文件。同时这里不同读者对计数器的访问也应该是互斥的。

    3) 信号量设置。首先设置信号量count为计数器,用来记录当前读者数量,初值为0; 设置mutex为互斥信号量,用于保护更新count变量时的互斥;设置互斥信号量rw用于保证读者和写者的互斥访问。

    代码如下:
    1. int count=0; //用于记录当前的读者数量
    2. semaphore mutex=1; //用于保护更新count变量时的互斥
    3. semaphore rw=1; //用于保证读者和写者互斥地访问文件
    4. writer () { //写者进程
    5. while (1){
    6. P(rw); // 互斥访问共享文件
    7. Writing; //写入
    8. V(rw) ; //释放共享文件
    9. }
    10. }
    11. reader () { // 读者进程
    12. while(1){
    13. P (mutex) ; //互斥访问count变量
    14. if (count==0) //当第一个读进程读共享文件时
    15. P(rw); //阻止写进程写
    16. count++; //读者计数器加1
    17. V (mutex) ; //释放互斥变量count
    18. reading; //读取
    19. P (mutex) ; //互斥访问count变量
    20. count--; //读者计数器减1
    21. if (count==0) //当最后一个读进程读完共享文件
    22. V(rw) ; //允许写进程写
    23. V (mutex) ; //释放互斥变量 count
    24. }
    25. }

    在上面的算法中,读进程是优先的,也就是说,当存在读进程时,写操作将被延迟,并且只要有一个读进程活跃,随后而来的读进程都将被允许访问文件。这样的方式下,会导致写进程可能长时间等待,且存在写进程“饿死”的情况。

    如果希望写进程优先,即当有读进程正在读共享文件时,有写进程请求访问,这时应禁止后续读进程的请求,等待到已在共享文件的读进程执行完毕则立即让写进程执行,只有在无写进程执行的情况下才允许读进程再次运行。为此,增加一个信号量并且在上面的程序中 writer()和reader()函数中各增加一对PV操作,就可以得到写进程优先的解决程序
    1. int count = 0; //用于记录当前的读者数量
    2. semaphore mutex = 1; //用于保护更新count变量时的互斥
    3. semaphore rw=1; //用于保证读者和写者互斥地访问文件
    4. semaphore w=1; //用于实现“写优先”
    5. writer(){
    6. while(1){
    7. P(w); //在无写进程请求时进入
    8. P(rw); //互斥访问共享文件
    9. writing; //写入
    10. V(rw); // 释放共享文件
    11. V(w) ; //恢复对共享支件的访问
    12. }
    13. }
    14. reader () { //读者进程
    15. while (1){
    16. P (w) ; // 在无写进程请求时进入
    17. P (mutex); // 互斥访问count变量
    18. if (count==0) //当第一个读进程读共享文件时
    19. P(rw); //阻止写进程写
    20. count++; //读者计数器加1
    21. V (mutex) ; //释放互斥变量count
    22. V(w); //恢复对共享文件的访问
    23. reading; //读取
    24. P (mutex) ; //互斥访问count变量
    25. count--; //读者计数器减1
    26. if (count==0) //当最后一个读进程读完共享文件
    27. V(rw); //允许写进程写
    28. V (mutex); //释放互斥变量count
    29. }
    30. }

    2.15 经典进程同步问题3:哲学家进餐问题

    问题描述

    一张圆桌上坐着5名哲学家,每两个哲学家之间的桌上摆一根筷子,桌子的中间是一碗米饭,如图2-10所示。哲学家们倾注毕生精力用于思考和进餐,哲学家在思考时,并不影响他人。只有当哲学家饥饿的时候,才试图拿起左、 右两根筷子(一根一根地拿起)。如果筷子已在他人手上,则需等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐,当进餐完毕后,放下筷子继续思考。

    问题分析

    1) 关系分析。5名哲学家与左右邻居对其中间筷子的访问是互斥关系。

    2) 整理思路。显然这里有五个进程。本题的关键是如何让一个哲学家拿到左右两个筷子而不造成死锁或者饥饿现象。那么解决方法有两个,一个是让他们同时拿两个筷子;二是对每个哲学家的动作制定规则,避免饥饿或者死锁现象的发生。



    图2-10 5名哲学家进餐

    3) 信号量设置。定义互斥信号量数组Ch0PstiCk[5] = {l, 1, 1, 1, 1}用于对5个筷子的互斥访问。

    对哲学家按顺序从0~4编号,哲学家i左边的筷子的编号为i,哲学家右边的筷子的编号为(i+l)%5。
    1. semaphore chopstick[5] = {1,1,1,1,1}; //定义信号量数组chopstick[5],并初始化
    2. Pi(){ //i号哲学家的进程
    3. do{
    4. P (chopstick[i] ) ; //取左边筷子
    5. P (chopstick[(i+1) %5] ) ; //取右边篌子
    6. eat; //进餐
    7. V(chopstick[i]) ; //放回左边筷子
    8. V(chopstick[(i+l)%5]); //放回右边筷子
    9. think; //思考
    10. } while (1);
    11. }
    该算法存在以下问题:当五个哲学家都想要进餐,分别拿起他们左边筷子的时候(都恰好执行完wait(chopstick[i]);)筷子已经被拿光了,等到他们再想拿右边的筷子的时候(执行 wait(chopstick[(i+l)%5]);)就全被阻塞了,这就出现了死锁。

    为了防止死锁的发生,可以对哲学家进程施加一些限制条件,比如至多允许四个哲学家同时进餐;仅当一个哲学家左右两边的筷子都可用时才允许他抓起筷子;对哲学家顺序编号,要求奇数号哲学家先抓左边的筷子,然后再转他右边的筷子,而偶数号哲学家刚好相反。正解制定规则如下:假设釆用第二种方法,当一个哲学家左右两边的筷子都可用时,才允许他抓起筷子。
    1. semaphore chopstick[5] = {1,1,1,1,1}; //初始化信号量
    2. semaphore mutex=l; //设置取筷子的信号量
    3. Pi(){ //i号哲学家的进程
    4. do{
    5. P (mutex) ; //在取筷子前获得互斥量
    6. P (chopstick [i]) ; //取左边筷子
    7. P (chopstick[ (i+1) %5]) ; //取右边筷子
    8. V (mutex) ; //释放取筷子的信号量
    9. eat; //进餐
    10. V(chopstick[i] ) ; //放回左边筷子
    11. V(chopstick[ (i+l)%5]) ; //放回右边筷子
    12. think; // 思考
    13. }while(1);
    14. }
    此外还可以釆用AND型信号量机制来解决哲学家进餐问题,有兴趣的读者可以查阅相关资料,自行思考。

    2.16 经典进程同步问题4:吸烟者问题

    向题描述

    假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它,但是要卷起并抽掉一支烟,抽烟者需要有三种材料:烟草、纸和胶水。三个抽烟者中,第一个拥有烟草、第二个拥有纸,第三个拥有胶水。供应者进程无限地提供三种材料, 供应者每次将两种材料放到桌子上,拥有剩下那种材料的抽烟者卷一根烟并抽掉它,并给供应者一个信号告诉完成了,供应者就会放另外两种材料在桌上,这种过程一直重复(让三个抽烟者轮流地抽烟)。

    问题分析

    1) 关系分析。供应者与三个抽烟者分别是同步关系。由于供应者无法同时满足两个或 以上的抽烟者,三个抽烟者对抽烟这个动作互斥(或由三个抽烟者轮流抽烟得知)

    2) 整理思路。显然这里有四个进程。供应者作为生产者向三个抽烟者提供材料。

    3) 信号量设置。信号量offer1、offer2、offer3分别表示烟草和纸组合的资源、烟草和 胶水组合的资源、纸和胶水组合的资源。信号量finish用于互斥进行抽烟动作。

    代码如下:
    1. int random; //存储随机数
    2. semaphore offer1=0; //定义信号量对应烟草和纸组合的资源
    3. semaphore offer2=0; //定义信号量对应烟草和胶水组合的资源
    4. semaphore offer3=0; //定义信号量对应纸和胶水组合的资源
    5. semaphore finish=0; //定义信号量表示抽烟是否完成
    6. //供应者
    7. while(1){
    8. random = 任意一个整数随机数;
    9. random=random% 3;
    10. if(random==0)
    11. V(offerl) ; //提供烟草和纸
    12. else if(random==l)
    13. V(offer2); //提供烟草和胶水
    14. else
    15. V(offer3) //提供纸和胶水
    16. // 任意两种材料放在桌子上;
    17. P(finish);
    18. }
    19. //拥有烟草者
    20. while(1){
    21. P (offer3);
    22. // 拿纸和胶水,卷成烟,抽掉;
    23. V(finish);
    24. }
    25. //拥有纸者
    26. while(1){
    27. P(offer2);
    28. // 烟草和胶水,卷成烟,抽掉;
    29. V(finish);
    30. }
    31. //拥有胶水者
    32. while(1){
    33. P(offer1);
    34. // 拿烟草和纸,卷成烟,抽掉;
    35. v(finish);
    36. }



    展开全文
  • 同步和互斥的关系

    千次阅读 2019-03-27 19:36:03
    同步和互斥描述的都是线程之间的交互关系。 多个线程可能: 都需要访问/使用同一种资源 多个任务之间有依赖关系,某个任务的运行依赖于另一个任务 互斥用于解决第一类问题,同步用于解决第二类问题。 个人觉得,...

    同步和互斥描述的都是线程之间的交互关系。

    多个线程可能:

    1. 都需要访问/使用同一种资源
    2. 多个任务之间有依赖关系,某个任务的运行依赖于另一个任务

    互斥用于解决第一类问题,同步用于解决第二类问题。

    个人觉得,同步和互斥并不是包含关系,而是并列关系。网上大部分都说同步是复杂的互斥,这一点,本人不敢苟同。

    如果各位有不同意见,欢迎大家留言讨论。

    展开全文
  • 在Windows等操作系统下,使用的VC、VB、java或C等编程语言,采用进程(线程)同步和互斥的技术编写程序实现生产者-消费者问题或哲学家进餐问题或读者-写者问题或自己设计一个简单进程(线程)同步和互斥的实际问题。
  • 线程的同步和互斥

    2018-05-24 11:06:34
    学习线程的同步和互斥,我们首先需要明白的就是同步和互斥,它们是为了什么。同步是为了在安全的条件下,使线程具有顺序性,而互斥是为了保证数据的安全性。 线程互斥(mutex) 为神马需要线程互斥? 大多数...
  • 线程间的同步和互斥

    2020-12-10 00:40:17
    总之,同步和互斥就是确保线程在访问变量的存储内容时候,不会访问到无效的值。 a.什么时候不需要同步? (1)原子操作 (2)全局共享变量仅仅可读 (3)变量私有 b.了解下什么叫做增量操作? (1)数据从内存单元...
  • windows多线程的同步和互斥
  • 六、进程同步和互斥 1、进程同步和互斥原则 2、进程互斥的软件实现方法 3、进程互斥的硬件实现方法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,599
精华内容 4,239
关键字:

同步和互斥