操作系统-同步互斥机制与通信机制

  • 管程 monitor
  • 进程间通信 IPC
  • 典型操作系统的IPC机制

  1. 管程，为什么引入了信号量和PV操作之后，又出现管程？

    信号量机制的不足：程序编写难，易出错（pv操作顺序不对，导致死锁）

    解决：在程序设计语言中引入管程成分–高级同步机制

  2. 管程

    是一个特殊模块

    有一个名字

    由关于共享资源的数据结构及在其上操作的一组过程组成

  3. 进程与管程

    进程只能通过调用管程中的过程来间接访问管程中的数据结构

  4. 管程要保证什么？

    作为一种同步机制，管程满足两个条件：

    互斥：管程是互斥进入的，有一个进程调用管程中的过程，就不允许其他过程调用，保证管程中数据结构的数据完整性。管程的互斥性是由编译器负责保证的。

    同步：管程中设置条件变量，及等待/唤醒操作，以解决同步问题。可以让一个进程或线程在条件变量上等待（此时，应先释放管程的控制权），也可以通过发送信号将等待在条件变量上的进程或线程唤醒。

  5. 应用管程的时候遇到的问题

    场景：

    当一个进入管程的进程执行等待操作时，它应当释放管程的互斥权

    当后面的进入管程的进程执行唤醒操作时（例如P唤醒Q），管程中便存在两个同事处于活动状态的进程。

    3种解决方法：

    1 P等待Q执行 (Hoare)

    2 Q等待P继续执行(MESA)(不在一个地方等待，本来Q是等在条件变量上)

    3 规定唤醒操作作为管程中最后一个可执行的操作 （Hansen）

  6. Hoare管程：

    因为管程是互斥进入的，所以当一个进程试图进入一个已被占用的管程时，应当在管程的入口处等待

    为此，管程入口处设置了一个进程等待队列，称作入口等待队列

    如果进程P唤醒了Q，则P等待Q执行；如果进程Q执行中唤醒了R，Q等待R执行；…，因此在管程内部可能会出现多个等待进程

    为此，在管程内需要设置一个进程等待队列，称为紧急等待队列，紧急等待队列的优先级高于入口等待队列的优先级

  7. Hoare管程——条件变量的实现：

    条件变量–在管程内部说明和使用的一种特殊类型的变量

    var c : condition;声明了一个条件变量c

    对于条件变量c，可以执行wait和signal操作

    wait(c)：

    • 如果紧急等待队列非空，则唤醒紧急等待队列的第一个等待者；
    • 否则释放管程的互斥权，执行此操作的进程进入c链末尾

    signal(c)：

    • 如果c链为空，则相当于空操作，执行此操作的进程继续执行
    • 否则唤醒第一个等待者，执行此操作的进程进入紧急等待队列的末尾

  8. 用管程解决生产者消费者问题:

    c和c++没有支持管程，但java中有类似的机制

  9. Mesa管程

    针对Hoare管程的缺点，两次额外的进程切换，而提出的，效率略高于Hoare管程

    解决办法：

    signal——notify

    notify——当一个正在管程中的进程执行notify(x)时，它使得x条件队列得到通知，发信号的进程继续执行

    使用notify要注意的问题：

    • notify的结果：位于条件队列头的进程在将来合适的时候且当处理器可用时恢复执行

    • 由于不能保证在它之前没有其他进程进入管程，因而这个进程必须重新检查条件

      用while循环取代if语句

    • 导致对条件变量至少多一次额外的检测（但不再有额外的进程切换），并且对等待进程在notify之后何时运行没有任何限制

  10. 改进notify

    • 给每个条件原语关联一个监视计时器，不论是否被通知，一个等待时间超时的进程将被设为就绪态

      当该进程被调度执行时，会再次检查相关条件，如果条件满足就继续运行

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

    • broadcast：使所有在该条件上等待的进程都被释放，并进入就绪队列：当一个进程不知道有多少进程将被激活时，这种方式是非常方便的；当一个进程难以准确判定将激活哪个进程时，也可使用广播

  11. Hoare管程和Mesa管程比较

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

  12. 管程

    管程：是一个抽象数据类型，有一个明确定义的操作集合，通过它且只有通过它才能曹总该数据类型的实例

    实现管程结构必须保证：

    • 只能通过管程的某个过程才能访问资源
    • 管程是互斥使用的，某个时刻只能有一个进程或线程调用管程中的过程

    条件变量：为提供进程与其他进程通信或同步而引入 wait/signal 或 wait/notify 或 wait/broadcast

  13. 线程库pthread中的同步机制

    互斥量，通过对互斥量进行操作，保护临界区

    1
    2
    3
    4
    5
    Pthread_mutex_init  新建一个锁（互斥量）
    Pthread_mutex_destroy 销毁一个已存在的锁
    Pthread_mutex_lock 加锁
    Pthread_mutex_trylock 试图加锁，加锁没加上就出错返回，转去等待
    Pthread_mutex_unlock 解锁

    解决同步问题，用的是条件变量，以及在条件变量上的操作：

    1
    2
    3
    4
    5
    Pthread_cond_init 创建一个条件变量
    Pthread_cond_destroy 销毁一个条件变量
    Pthread_cond_wait 等待信号（block wait for a signal）
    Pthread_cond_signal 向另一个线程发信号并唤醒它（signal another thread and wake it up）
    Pthread_cond_broadcast 向多个线程发信号并唤醒它们（signal multiple threads and wake all of them）

  14. 进程间通信机制

    为什么需要通信机制？

    • 信号量和管程的不足：只能传递简单信息，不能传送大信息

    • 管程不适用于多处理器情况

    • 需要引入通信机制：

      消息传递：send和receive原语；适用于：分布式系统、基于共享内存的多处理机系统、单处理机系统；可以解决进程间的同步问题、互斥问题、通信问题

  15. 基本通信方式

    • 消息传递
    • 共享内存
    • 管道
    • 套接字（适合网络、分布式系统）
    • 远程过程调用（适合网络、分布式系统）

  16. 消息传递

    发送进程S：

    1
    2
    3
    > send(destination,message);
    > message:text,size
    >

    接收进程R：

    1
    2
    3
    4
    > receive(source,message);
    > message:text,size
    > 接收进程的PCB中消息队列指针
    >

    操作系统空间：

    有一组消息缓冲区，每个消息缓冲区buffer结构：消息头（消息类型、接收进程ID、发送进程ID、消息长度、控制信息）；消息体（消息内容）

    发送原语：发送进程陷入操作系统，由操作系统完成发送的过程。发送进程S陷入内核，操作系统把发送进程准备好的消息，拷贝到某一个缓冲区buffer里头（复制消息），就是找个空的缓冲区把消息内容拷贝过去；然后把消息挂接到接收进程R的消息队列的末尾（消息入队）。到了这一步，发送进程已经完成发送工作，可以接着做其他事情了。什么时候接收进程上CPU了，执行到receive接收原语，陷入操作系统（陷入内核），有操作系统完成相应的工作，操作系统帮助他把消息复制到接收进程的地址空间（复制消息）。完成一个发送和接收的过程。

  17. 用PV操作实现send原语

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    send(destination,message){
        根据destination找接进程；
        如果未能找到，出错返回；
        申请空缓冲区P(buf-empty);
        
        P(mutex1);
        取空缓冲区
        V(mutex1);
        
        把消息从message处复制到空缓冲区；
            
    	P(mutex2);
        把消息缓冲区挂接到接收进程的消息队列；
        V(mutex2);
        
        V(buf-full);
    }

    信号量：
    buf-empty初值为N
    buf-full初值为0
    mutex1初值为1
    mutex2初值为1

  18. 共享内存

    读者写者解决互斥问题

    同一块物理地址中的一块内存，映射到两个进程空间，在进程1和进程2中分别为A和B，那么进程1对于共享内存的读写，其实就是对A的读写，同样，进程2对于共享内存的读写，其实就是对B的读写。

    进程1读A的同时，进程2可以读B；可同时读，但不可同时写。

  19. 管道通信方式pipe

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

    （一个或多个）发送进程—-往管道尾巴里写—-接收进程从管道头上读

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

  20. 典型操作系统的IPC机制

    Unix:

    Linux:

    用户能调用：管道、消息队列、共享内存、信号量、信号、套接字

    内核同步机制：原子操作、自旋锁、读写锁、信号量、读写信号量、互斥体、完成变量、顺序锁、屏障…

    Windows:

  21. 原子操作

    不可分割，执行完成前不会被其他任务或事件中断

    常用语实现资源的引用计数

    1
    2
    3
    4
    5
    atomic_t v = atomic_init(0);
    atomic_set(&v,4);
    atomic_add(2,&v);
    atomic_inc(&v);
    printk("%d\n",atomic_read(&v));

  22. 屏障（栅栏、关卡）

    一种同步机制

    用于对一组线程进行协调

    应用场景：一组线程协同完成一项任务，需要所有线程都到达一个汇合点后再一起向前推进。

  23. 重点内容

    管程

    • 如何保证互斥
    • 如何保证同步——条件变量和 wait/signal
    • Hoare管程
    • Mesa管程

    进程间通信

    • 消息传递、共享内存、管道

    Pthread中的同步机制

    Linux的IPC机制

    重点概念：管程、Hoare管程、Mesa管程、条件变量、wait/signal、Pthread中的互斥锁与条件变量、共享内存、消息传递、管道、Linux中的原子操作、屏障、读写锁

赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码