线程同步技术

可以参考线程同步技术

进程同步技术

进程间同步技术常常利用锁和信号量来解决，而锁页分为悲观锁和乐观锁。

  • 悲观锁：先加锁再操作临界区，适用于冲突概率高的情况
  • 乐观锁：先操作临界区，再检查是否发生了冲突，发生冲突就需要回溯，只适用于冲突概率极低的情况，因为回溯的成本是巨大的

通过pthread_mutex_*等函数来实现，锁一般会放到共享内存中去

一些进程同步模型

生产者消费者模型

存在一个缓冲区，生产者往里面放数据，消费者从里面拿数据，如何保证它们同步

  1. 使用一个空槽信号量和一个满槽信号量，分别用来表示缓冲区空闲位置数和非空闲位置数
  2. 一把全局锁，用来限定对缓冲区的临界访问
  3. 生产者需要消耗（P）空槽资源，释放（V）满槽资源
  4. 消费者需要消耗（P）满槽资源，释放（V）空槽资源

伪代码如下：

constexpr int N = 100; // 缓冲区大小
semaphore emptyBuffers = N; // 初始定义称缓冲区的空槽数量
semaphore fullBuffers = 0; // 初始定义为缓冲区的满槽数量
semaphore mutex = 1; // 定义锁

// 生产者
void producer(){
    while(1){
        P(emptyBuffers);
        P(mutex);

        // 生产

        V(mutex);
        V(fullBuffers);
    }
}

// 消费者
void consumer(){
    while(1){
        P(fullBuffers);
        P(mutex);

        // 消耗

        V(mutex);
        V(emptyBuffers);
    }
}

哲学家进餐模型

哲学家进餐模型为IO设备等有限竞争问题提供了模型。

在一张圆桌上面，有五个哲学家以及五把叉子（扩展到N个哲学家和N把叉子），哲学家和叉子相间分布，每个哲学家可以拿到左右手的叉子。哲学家围坐在一起思考，此时不需要叉子，思考饿了哲学家想要进餐，哲学家必须拿到两边的叉子才能进餐，只有进餐完毕才会把叉子放回原处。

解决方案有如下：

  1. 选择五个信号量，每个哲学家进餐会尝试去P左边的叉子，然后P右边的叉子

      sem fork[N];
  while (1){
      think(); // 思考
      P(fork[i]); // 左边的叉子
      P(fork[(i+1)%N]); // 右边的叉子
      eat(); // 进餐
      V(fork[(i+1)%N]); // 右边的叉子
      V(fork[i]); // 左边的叉子
  }

    不足在于：如果每个哲学家同时P左边的叉子，那么就死锁了

  2. 添加一个全局锁，先P锁，然后再P左叉子，最后P右叉子，然后进餐

      sem fork[N];
  sem mutex = 1;
  while(1){
      think(); // 思考

      P(mutex);
     P(fork[i]); // 左边的叉子
      P(fork[(i+1)%N]); // 右边的叉子
      eat(); // 进餐
      V(fork[(i+1)%N]); // 右边的叉子
      V(fork[i]); // 左边的叉子
      V(mutex);
  }

    不足在于：其实自始至终只有一个哲学家能进餐，效率低下

  3. 参考解决方案1，只有同时拿起一边的叉子才会死锁，那么设定奇数偶数拿起叉子的顺序不一致可解决

      sem fork[N];
  while (1){
      think(); // 思考
      if(index % 2 == 0){  // index是哲学家的编号
          P(fork[i]); // 左边的叉子
          P(fork[(i+1)%N]); // 右边的叉子
          eat(); // 进餐
          V(fork[(i+1)%N]); // 右边的叉子
          V(fork[i]); // 左边的叉子
      }else{
          P(fork[(i+1)%N]); // 右边的叉子
          P(fork[i]); // 左边的叉子
          eat(); // 进餐
          V(fork[i]); // 左边的叉子
          V(fork[(i+1)%N]); // 右边的叉子
      }
  }

  4. 通过哲学家的状态来判定，将哲学家分为进餐状态，思考状态，饥饿状态（试图拿叉子），只有当左右两个邻居都没进餐才可进餐。

读者-写者模型

读者-写者模型为数据库访问提供了模型

其基本描述为：可以多个同时读，但是只要有写的，就会独占，即

  • 读-读：允许，同一时刻，多个读者可读
  • 读-写：互斥，同一时刻，有写就不能读
  • 写-写：互斥，同一时刻，只能一个可写

解决方式会分成，读者优先策略，写者优先策略以及公平策略

  1. 读者优先：只要有读者正在读，那么后来读者可进入，如果读者数为0，写者才能进入。这样会导致写者饥饿
  2. 写者优先：只要有写者要写入，那么读者必须等待，直到全部写者写入完成
  3. 公平策略：优先级相同，读写互斥，只能一个写者到达临界区，可以多个读者到达临界区

死锁避免

死锁只有满足四个条件才会发生：

  1. 互斥条件：多个线程不能同时拥有一种资源
  2. 持有并等待条件：一个线程有了资源1，还要获取资源2，但是资源2正在被别的线程获取了
  3. 不可剥夺条件：资源只能由占用线程释放，其他线程不能释放
  4. 环路等待：死锁发生时，两个线程获取资源的顺序构成环路，即线程-资源-线程-资源环路

避免死锁的方式只需要破坏上面四种条件中的一种即可：

  1. 资源顺序获取：即所有线程都应该按照获取资源1，资源2…的顺序来获取，破坏环路等待
  2. 一次性申请资源：所有进程在一开始都申请全部资源，破坏持有等待
  3. 及时释放资源：如果占用资源的线程再次获得其他资源没有被满足，应该及时释放已获取资源，破坏不可剥夺

银行家算法

银行家算法时迪杰斯特拉提出的一种解决动态资源分配的算法，其核心在于，通过安全算法估量是否分配资源。

具体表现为：

  • 数据结构：银行家算法需要存储以下几个数据结构

    Avaliable向量：表示当前每种资源可使用数量

    Max矩阵：每个进程对每种资源的最大数量

    Allocation矩阵：每个进程已获得每种资源的数量

    Need矩阵：每个进程还需要获得每种资源的数量

    Work向量：初始化为Avaliable向量

    Finish向量：初始化为False

  • 执行过程：假设第$i$个进程开始申请资源，资源数量的向量为Request[i]，并对第$j$种资源做以下判断

    1. Request[i][j]<=Need[i][j]，否则出错，是则继续

    2. Request[i][j]<=Avaliable[j]，否则等待，是则继续

    3. 尝试分配

        Avaliable[j] -= Request[i][j];
  Allocation[i][j] += Request[i][j];
  Need[i][j] -= Request[i][j];

    4. 安全性检查，是则分配且继续，否则回退且阻塞

  • 安全性检查：

    1. 检查第i个进程，查看是否满足Finish[i]==flase and Work>=Need。能找到i执行2，不能找到这样的i执行3
    2. Work+=Allocation[i], Finish[i]=true，执行2
    3. 假如所有进程Finish==true则安全，否则不安全