进程的同步与互斥

image_fcd5508d.png

进程同步

  • 同步也称为接制约关系。
  • 在多道程序环境下,进程是并发执行的,不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系,如等待、传递信息等,引入了进程同步的概念。进程同步是为了解决进程的异步问题。
  • 一个简单的例子来理解这个概念。
  • 例如,让系统计算1 + 2x3,假设系统产生两个进程: 一个是加法进程,一个是乘法进程。要让计算结果是正确的,一定要让加法进程发生在乘法进程之后,但实际上操作系统具有异步性,若不加以制约,加法进程发生在乘法进程之前是绝对有可能的,因此要制定一定的机制去约束加法进程,让它在乘法进程完成之后才发生。

异步性:进程具有异步性的特征。异步性是指,各并发执行的进程以各自独立的、不可预知的速度向前推进。

进程互斥

  • 互斥,亦称间接制约关系进程互斥指当一个进程访问某临界资源时,另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束,释放该资源之后,另一个进程才能去访问临界资源。
  • 在这里需复习一下临界资源的概念。
  • 我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备(比如摄像头、打印机)都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。
  • 对临界资源的访问,必须互斥地进行。
    image_aa51d3b0.png
  • 为了禁止两个进程同时进入临界区,需遵循以下准则
    image_838d4189.png

实现临界区进程互斥的软件实现方法

image_b88aaee7.png

  • 软件实现方法的思想:在进入区设置并检查一些标志来标明是否有进程在临界区中,若已有进程在临界区,则在进入区通过循环检查进行等待,进程离开临界区后则在退出区修改标志。入区通过循环检查进行等待,进程离开临界区后则在退出区修改标志。

单标志法

image_a1ccdd96.png
image_617e2dd7.png

双标志先检查法

image_52618e01.png

双标志后检查法

image_61b13ea3.png

Peterson算法

image_3f6ad904.png
image_f8d82e11.png

实现临界区进程互斥的硬件实现方法

image_deb1827f.png

中断隐藏方法

image_34ed8a89.png

TestAndSet指令

  • 执行TSL指令时,它的内部运转逻辑:
  • 假设lock现在为false,代表临界资源A空闲,那么我就可以访问这个资源,同时将lock=true,提醒别的进程,这个临界资源A我正在使用,让他们等等
  • 假设lock为true,代表临界资源正在有人使用,所以我必须等待,并且将lock=true,并不影响什么,所以没关系,只是为了让lock为false时可以上锁,将上锁与检查在一个TSL指令完成。
    image_0193543e.png

Swap指令

  • old是每个进程都要进行的一步,都必须将old=true
  • 分析一下这样做的原因:
  • 因为lock是某一特定临界资源的共享变量,当每一个进程准备访问这个特定的临界资源时,初始化old=true,然后进入while循环进行交换,如果当前lock是false,则交换后old=false,则当前进程可以跳出循环进入临界区代码段,同时因为交换,lock=old=true上锁,不让别的进程来打扰,别的进程会因为lock变为true,一直在while循环等待,当我使用完临界资源,则将lock=false,此时别的进程再交换old和lock就能判断old=false,可以跳出循环,使用临界资源。
    image_1d36f4cd.png

信号量机制

image_87a0ac0a.png

为什么引入信号量机制?

  • 为了更好的解决进程互斥与同步的问题
    image_41b1f6f8.png

什么是信号量机制?

image_203edab6.png

整型信号量

image_ea749638.png

记录型信号量

image_04904d3c.png

举一个生动形象的例子了解记录型信号量

  • 一张图咱们回忆一下进程的状态
    image_677830ec.png
  • 一个例子
    image_c343ca7a.png
    image_8e3dafcc.png

image_2f34d6e8.png
image_882498fa.png
image_846ba015.png

梳理一下记录型信号量的知识点(P、V)

image_241871a9.png

信号量机制实现进程的互斥、同步与前驱关系image_f74ca578.png

信号量机制实现进程互斥

image_7cd41f4e.png

信号量机制实现进程同步

  • 想象一下四则运算的顺序,加减乘除;
    image_45000965.png
  • 要想理解这一部分知识,必须知道P、V操作的内部实现原理
    image_b10cde41.png

信号量机制实现前驱关系

image_c381886a.png

进程同步与互斥经典问题

  • 同步时,前V后P。

image_6b4c77de.png

生产者-消费者问题

问题描述

  • 系统中有一组生产者进程一组消费者进程,生产者进程每次生产一个产品放入缓冲区,消费者进程每次从缓冲区中取出一个产品并使用。(注: 这里的“产品”理解为某种数据)
  • 生产者、消费者共享一个初始为空、大小为n的缓冲区
  • 只有缓冲区没满时,生产者才能把产品放入缓冲区,否则必须等待。
  • 只有缓冲区不空时,消费者才能从中取出产品,否则必须等待。
  • 缓冲区是临界资源,各进程必须互斥地访问。

image_1259ed6c.png

问题分析

  • 1)关系分析。生产者和消费者对缓冲区互斥访问是互斥关系,同时生产者和消费者又是一个相互协作的关系,只有生产者生产之后,消费者才能消费,它们也是同步关系
  • 2)整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
    生产者每次要消耗(P)一个空闲缓冲区,并生产(V)一个产品。
    消费者每次要消耗(P)一个产品,并释放一个空闲缓冲区(V)。
    往缓冲区放入/取走产品需要互斥。
  • 3)信号量设置。设置信号量。设置需要的信号量,并根据题目条件确定信号量初值。( 互斥信号量初值一般为1,同步信号量的初始值要看对应资源的初始值是多少)

image_a16d0dc3.png

如何实现?

image_545017a5.png

实现互斥的P操作一定要在实现同步的P操作之后

image_f8dbd61c.png

知识回顾与重要考点

image_a98868de.png

多生产者-多消费者问题

问题描述

image_728841e5.png

问题分析

image_949bf822.png

实现方法

有mutex

image_d72ddc54.png

无mutex

image_193d3d33.png

为什么有mutex和没有mutex一样呢?

  • 原因在于:本题中的缓冲区大小为1,在任何时刻,apple、 orange、 plate 三个同步信号量中最多只有一个是1。因此在任何时刻,最多只有一个进程的P操作不会被阻塞,并顺利地进入临界区…

如果有两个盘子plate

image_1bed0417.png

知识总结与重要考点

  • 总结:在生产者_消费者问题中,如果缓冲区大小为1,那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。当然,这不是绝对的,要具体问题具体分析。
  • 建议:在考试中如果来不及仔细分析,可以加上互斥信号量,保证各进程一定会互斥地访问缓冲区。但需要注意的是,·实现互斥的P操作一定要在实现同步的P操作之后·,否则可能引起·“死锁”·。

在这里插入图片描述

读者-写者问题

问题描述

image_66d181dc.png

问题分析

image_b728851a.png

实现方法

给count加mutex互斥访问

  • 这里说一下为什么要加mutex。
  • 比如:当count=0时,第一个读者进程执行到p(rw),rw=0,假设此时时间片到了,切换到第二个读者进程,第二个进程发现count=0,则执行p(rw),但是此时rw=0,于是第二个进程被堵在p(rw)这里,同理,后面的可能会有多个进程堵在p(rw),只有当第一个进程再次获得时间片,执行count++,让count不为0,然后其他进程就可以直接绕过if直接进行count++来访问文件,但是第三个读者进程和后面的几个可能堵在p(rw)的多个读者进程则必须得等count–为0后才可以再次和写进程竞争来访问文件,对count的访问没有做到一气呵成,会导致本来一些进程一直堵在p(rw)。
    image_059a4e7b.png

加一个w实现“读写公平法”

  • 在上面的算法中,读进程是优先的,即当存在读进程时,写操作将被延迟,且只要有 一个读进程活跃,随后而来的读进程都将被允许访问文件。这样的方式会导致写进程可能长时间等待,且存在写进程“饿死”的情况。
  • 若希望写进程优先,即当有读进程正在读共享文件时,有写进程请求访问,这时应禁止后续读进程的请求,等到已在共享文件的读进程执行完毕,立即让写进程执行,只有在无写进程执行的情况下才允许读进程再次运行。为此,增加一个信号量并在上面程序的writer()和 reader()函数中各增加一对PV操作,就可以得到写进程优先的解决程序。
    image_9498b739.png

知识回顾与重要考点

image_9bbe5bb3.png

吸烟者问题

问题描述

image_f1dacce7.png

问题分析

image_40170f17.png
image_62c6e602.png

实现方法

image_a14f0f81.png

知识回顾与重要考点

image_1824f83c.png

哲学家进餐问题

问题描述

image_7310f30d.png

问题分析

image_aba73722.png

如何实现

image_c1801d32.png
image_dee08423.png
image_2cf2818f.png

知识回顾与重要考点

image_bcfb79d0.png

管程和java中实现管程的机制

image_a2c1d3ce.png

为什么引入管程?

image_e91a2aa1.png

管程的组成及基本特征

image_c4b738c7.png

管程实现生产者消费者问题

image_d6af983b.png
image_2e8a4f9f.png
image_45b82ef7.png
image_fd80d818.png

java中类似于管程的机制

image_3383aa59.png