10、同步互斥机制3(进程通信)(操作系统笔记)

一、管程

一种新的同步机制

1.1 为什么会出现管程

  • 问题
    信号量机制的不足:程序编写困难、易出错
  • 解决
    在程序设计语言中引入管程成分,这是一种高级同步机制

1.2 定义

  • 是一种特殊的模块
  • 有一个名字
  • 由关于共享资源的数据结构及在其上操作的一组过程组成
  • 进程与管程:进程只能通过调用管程中的过程来间接的访问管程中的数据结构

1.3 管程要保证什么

作为一种同步机制,管程要解决两个问题:

  • 互斥
    管程是互斥进入的,主要是为了保证管程中数据结构的数据完整性。管程的互斥性是由编译器负责保证的。

  • 同步
    管程中设置条件变量及等待/唤醒操作以解决同步问题。这两个操作可以让一个进程或线程在条件变量上等待(此时,应先释放管程的使用权),也可以通过发送信号将等待在条件变量上的进程或线程唤醒。

1.4 应用管程时遇到的问题

设问:是否会出现这样一种场景,与多个进程同时在管程中出现?
场景:当一个进入管程的进程执行等待操作时,它应当释放管程的互斥权。当后面进入管程的进程执行唤醒操作时(例如P唤醒Q,即将前面的进程唤醒了),管程中便存在两个同时处于活动状态的进程。
如何解决:有三种处理方法

  • P等待Q执行(Hoare管程)
  • Q等待P继续执行(MESA管程)
  • 规定唤醒操作为管程中最后一个可执行的操作(Hansen管程)

1.4.1 Hoare管程

1

说明:上图中的资源为共享资源,而对资源的操作我们使用多个过程表示。有些进程在进入管程时可能条件不成熟,需要等待,这里为不同的等待进程设置了不同的条件变量,这通过wait操作完成,当然,在后面可能条件成熟了,需要唤醒,这里使用signal操作完成。在这种管程中,前面的进程进入等待,后面被唤醒的进程执行,此时前面的进程是管程内的进程,于是进入的是紧急等待队列。

  • 因为管程是互斥进入的,所以当一个进程试图进入一个已被占用的管程时,应当在管程的入口处等待。为此,管程的入口处设置一个进程等待队列,称为入口等待队列。
  • 如果进程P唤醒进程Q,则P等待Q执行;如果进程Q执行中又唤醒进程R,则Q等待R执行;....,如此,在管程内部可能会出现多个等待进程。于是在管程内需要设置一个进程等待队列,称为紧急等待队列,紧急等待队列的优先级高于入口等待队列。

条件变量的实现

  • 条件变量:在管程内部说明和使用的一种特殊类型的变量。如var c : condition
  • 对于条件变量,可以执行waitsingal操作
  • wait(c)操作:如果等待紧急队列非空,则唤醒第一个等待者;否则释放管程的互斥权,执行此操作的进程进入c链的末尾。
  • singal(c)操作:如果c链为空,则相当于空操作,执行此操作的进程继续执行;否则唤醒第一个等待者,执行此操作的进程进入紧急等待队列的末尾。

二、管程的应用

2.1 管程的实现

管程的实现有两种途径:

  • 直接构造:效率高
  • 间接构造:用某种已经实现的同步机制去构造,例如信号量和PV操作。

2.2 用管程解决生产者消费者问题

2

说明:左边的代码是管程的代码,右边是生产者消费者代码。生产者生产一个进程或线程后只需要调用管程,将其添加进去即可。而消费者只需要从管程中取即可。因为管程每次只允许一个进程或线程执行,所以可以保证同步问题。在Java中有类似的机制,但是C/C++中没有。

三、MESA管程

  • Hoare管程的一个缺点
    两次额外的进程切换
  • 解决
    Hoare管程中的signal改成了notify,就是当一个正在管程中的进程执行notify(x)时,它使得x条件队列得到一个通知,发信号的进程继续执行。
  • notify的结果:位于条件队列的进程在将来合适的视乎且当处理器可用时恢复执行
  • 由于不能保证在它之前没有其他进程进入管程,因而这个进程必须重新检查条件(while循环取代if语句)
  • 导致对条件变量至少一次额外的检测(但不再有额外的进程切换),并且对等待进程在notify之后何时运行没有任何限制,这是其缺点,但是确实比Hoare管程的效率要高。

3.1 生产者/消费者问题

3

说明:从上图可以看到只是判断有所区别,其他的和之前的都差不多。

3.2 改进notify

  • notify的一个很有用的改进
    1、给每个条件原语关联一个监视计时器,不论是否被通知,一个等待的时间超时的进程将被设为就绪态。
    2、当该进程被调度时,会再次检查相关条件,如果条件满足则继续执行。

  • 超时可以防止如下情况的发生
    当某些进程产生相关条件的信号之前失败时,等待该条件的进程就会被限制地推迟执行而处于饥饿状态。

  • 引入BROADCAST
    使所有在该条件上等待的进程都被释放并进入就绪队列

    • 当一个进程不知道有多少个进程被激活时,这种方式是非常方便的。
      例子:生产者/消费者问题中,假设insertremove函数都适用于可变长度的字符块,此时,如果一个生产者往缓冲区中添加了一批字符,它不需要知道每个正在等待的消费者准备消耗多少字符,而仅仅执行一个broadcast,所有正在等待的进程都得到通知并再次尝试运行。
    • 当一个进程难以判断将激活哪个进程时,也可以使用这种广播机制

3.3 Hoare管程与MESA管程的比较

  • Mesa管程优于Hoare管程之处在于Mesa管程错误比较少
  • Mesa管程,由于每个过程在收到信号后都重新检查管程变量,并且由于使用了while结构,一个进程不正确的broadcast广播或发信号notify不会导致收到信号的程序出错。收到信号的程序将检查相关的变量,如果期望的条件没有满足,它会重新继续等待

四、PTHREAD中的同步机制

这种同步机制其实就是POSIX Threads同步机制,是一个线程函数库。

4

说明:在这种机制中对于互斥的保证是使用一个互斥量mutex。我们可以可能可以创建init和销毁destroy。可以加锁lock和解锁unlock,还有尝试加锁trylock。在解决同步问题的时候使用的是条件变量。同时是可以进行创建和销毁等操作。

4.1 讨论PTHREAD_COND_WAIT

这个函数执行可以分解为三个主要动作:

  • 1、解锁(释放锁)
  • 2、等待
    当收到一个解除等待的信号(pthread_cond_sinal或者pthread_cond_broad_cast)之后,pthread_cond_wait马上需要做的动作是:
  • 3、上锁

五、进程间通信IPC

5.1 为什么需要通信机制

  • 信号量和管程的不足:不能传递大量的信息
  • 不适用多处理器的情况
  • 进程间通信机制
    消息传递:send & receive原语。适用于分布式系统、基于共享内存的多处理器系统、单处理器系统,可以解决进程间的同步问题、通信问题。

5.2 基本通信方式

  • 消息传递
  • 共享内存
  • 管道
  • 套接字
  • 远程过程调用

5.3 消息传递

5

说明:当发送进程将相关的消息准备好之后,由于其不能直接操作接收进程,所有相关的发送工作需要操作系统来完成,发送进程将消息发送给操作系统之后就不需要管理了。这里执行了陷入内核和复制消息两部操作。而操作系统在接收到消息之后,是将消息队列的指针挂到接收进程的PCB末尾,当接收进程被调度上cpu之后,此进程才会去内核中复制相关的消息。

5.3.1 用PV操作实现send原语

6

说明:对于receive的原语实现这里就多说了。

5.4 共享内存

7

说明:这里有两个问题需要解决

  • 1、两个进程之间如何共享内存,我们可以将两个进程的地址空间映射到同一块物理地址空间上,于是其操作的资源是相同的。
  • 2、读者写者问题。共享的内存不能同时写,但是可以同时读。我们可以使用读者写者方法解决互斥问题。

5.5 管道通信方式PIPE

8

利用一个缓冲传输介质(内存或文件)连接两个相互通信的进程

  • 按字符流的方式写入读出
  • 先进先出顺序
  • 管道通信机制必须提供的协调能力
    互斥、同步、判断对方进程是否存在

六、典型操作系统中的IPC机制

6.1 进程同步/通信实例

9

6.2 Linux的进程通信机制

10

说明:从图中可以看到Linux继承了多个操作系统的IPC机制。同时也是基于POSIX机制。

6.2.1 Linux内核同步机制

11

原子操作

  • 不可分割,在执行之前不会被其他任务或事件中断
  • 常用于实现资源的引用计数
  • atomic_t
    12

屏障

  • 一种同步机制(又称栅栏、关卡)
  • 用于对一组线程进行协调
  • 应用场景
    一组线程协同完成一项任务,需要所有线程都到达一个汇合点后再一起向前推进,比如矩阵运算。
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • ** 本文摘自汤小丹主编《计算机操作系统》(第三版)2.3 进程同步 ** 在 OS 中引入进程后,虽然提高了资源...
    刘帅_阅读 3,144评论 0 0
  • 又来到了一个老生常谈的问题,应用层软件开发的程序员要不要了解和深入学习操作系统呢? 今天就这个问题开始,来谈谈操...
    tangsl阅读 4,176评论 0 23
  • 同步互斥机制和通信机制 管程monitor 进程间通信 Inter-Process Communication 典...
    SeanC52111阅读 1,149评论 0 0
  • 现在的这种状态不是很好,焦虑.迷茫.恐惧来形容现在的我是再合适不过的了。 因为自身不够强大,而没有能力选择自己想要...
    正在改变中韩文绪阅读 254评论 0 0
  • 百泉竞海激两岸, 飞雁越岭不愁寒。 已得骐骥千里才, 无须怨他恐波澜。 2009.03
    玥偊阁阅读 178评论 0 0