李某人的笔记
0%

3.3：同步互斥

发表于 分类于 ，

背景

并发的好处

  • 共享资源（一个硬件资源，同时实现多种功能）

  • 加速，效率高（I/O操作和计算可以重叠，拆分小任务，流水）；

  • 模块化：大程序分解成小程序，使系统易于扩展

并发的问题

  • 同步干扰：例如一个写，一读，造成了数据的不一致

  • 死锁

相关名词

  • 原子操作：一次不存在任何中断或者失败的执行

  • 临界区：只能有一个进程可执行的代码区域

  • 死锁：进程相互等待资源，程序无法执行

  • 饥饿：进程得不到资源

临界区

锁机制

中断禁用

万不得已而为之，略

原子操作锁——基于原子指令

主存保证不会被打断

  • test-and-set 测试和置位：从内存中读值，判断是否为1并返回，同时设置内存值为1

  • exchange 交换：输入两个内存单元，交换其值并返回

  • 优缺点

    • 优点：简单，支持多临界区，适用于共享主存的多处理器的并行进程

    • 缺点：不是有序的，可能导致饥饿

软件锁

Peterson算法简介
1
2
3
4
5
flag[i] = true;   //我要进去
turn = j;      //下次是他
while (flag[j] && turn == j) ;   //我想进，并且轮到我
//临界区
flag[i] = false;    //我走了
Dekkers算法
1
2
3
4
5
6
7
8
9
10
flag[i] = true;       //我想进去
while(flag[i-1] == true){    //等大哥走（防止轮到我，但是大哥没走）
    if turn != i {       //如果还没轮到我
        flag[i] = false;        //放小弟到这里
        while(turn != i);        //大家一起等，轮到自己
        flag[i] = true;       
    }
}
turn = i+1;           //下一个
flag[i] = false;          //我走了

信号量机制

信号量(Semaphore)

  • 用信号量表示系统资源数量

  • 信号量是一种抽象数据类型

  • 由一个整型变量(sem)和两个原子操作组成

  • 原子操作P() sem - 1 若 sem < 0 进入等待否则继续

  • 原子操作V() sem + 1 若 sem <= 0 唤醒一个等待进程

信号量分类

  • 二进制信号量 资源数目为 0 或 1

  • 资源信号量 可为任何非负值

信号量实现条件同步

  • 如当线程A的步骤X必须在线程B的步骤Y后，则sem =0

  • 线程A：P（）;X；

  • 线程B：V（）;Y；

管程

管程的组成

  • 一个锁：控制管程代码的互斥访问

  • 0或者多个条件变量(0个条件变量则和信号量差不多)：管理共享数据的并发访问

条件变量(Condition Variable)

  • 进入管程的线程因资源被占用而进入等待状态

  • 每个条件变量表示一种等待原因，对应一个等待队列

  • Wait()操作

    • 将自己阻塞在等待队列中

    • 唤醒一个等待者或释放管程的互斥访问

  • Signal()操作

    • 将等待队列中的一个线程唤醒

    • 如果等待队列为空 则等同于空操作

管程条件变量的释放

  • Hansen管程（主流的）：唤醒等待进程，但等我退出，你再恢复

  • Hoare管程（多在教材上）：唤醒等待进程，我直接退出，把位置让个你