程序的并发性 链接到标题

顺序VS并发 链接到标题

顺序执行 链接到标题

一个程序在执行时，所有的指令都按顺序执行，前一条指令执行完毕后，才会执行下一条指令。

  • 优点:
    • 运行资源的独占性
    • 执行结果的确定性(可复现)
  • 缺点:
    • 效率低下(单核CPU)

并发性 链接到标题

将程序设计成若干个可并发执行的软件模块(进程或线程)

信息
实质：充分利用处理器可与外设并行工作的特性来 减少空闲等待的情况
优点：

  • 单处理器系统：处理器和各I/O设备可同时 工作，充分发挥硬件的并行能力
  • 多处理器系统：各进程可在不同处理器上并 行处理，进一步提升计算速度。

缺点：

  • 运行结果可能不唯一！
    警告

    因此可能会出现两种极端的错误情况：

    • 结果不唯一、冲突
    • 永远等待

一个经典例子：飞机售票问题 链接到标题

对于一个程序购票问题我们不难编程

void T1()
{按旅客订票要求找到票数Aj}
int X1=Aj;
if(X1>0)
{
    X1--;
    Aj=X1;
    {输出一张票}
}
else
{
  {提示票已售完}
}

如果是顺序执行的话这个程序没有问题，不过假如有另一个一模一样的程序与这个程序并发执行，就冲突了

void T1()
{按旅客订票要求找到票数Aj}
int X1=Aj;
if(X1>0)
{
    X1--;
    Aj=X1;
    {输出一张票}
}
else
{
  {提示票已售完}
}

void T2()
{按旅客订票要求找到票数Aj}
int X2=Aj;
if(X2>0)
{
    X2--;
    Aj=X2;
    {输出一张票}
}
else
{
  {提示票已售完}
}
  • 如果在最后只有一张票且在T1函数第二行执行之后程序发生调度，CPU给到了T2，那么就会出现两个程序将一张票卖给了两个旅客的情况。

信息
这是程序并发性引发的错误
如果想要解决这个问题，首先要判定哪些程序会出这种bug。

无关的并发进程 链接到标题

信息
一组并发进程分别在不同的变量集合上操作 ，每个进程的执行结果与其他并发进程的进 展无关

Bernstein条件 链接到标题

  • $R(p_i)={a_1,a_2,\cdots,a_n}$称为进程$P_i$的 引用变量集
  • $W(p_i)={b_1,b_2,\cdots,b_m}$称为进程$P_i$的 修改变量集

若两个程序的引用变量集和修改变量集的交集是空集，即 $$ (R(p_i)\bigcap W(p_j))\bigcup (R(p_j)\bigcap W(p_i))\bigcup (W(p_i)\bigcap W(p_j)) =\emptyset $$ 则称这两个程序是无关的，执行结果与时间先后顺序无关，可以并发执行。

提示
举一个例子： $$ S_1:a=x+y $$ 引用变量集与修改变量集分别为$R(S_1)={x,y},W(S_1)={a}$

竞争与协作 链接到标题

字面意思，进程之间因为共享独占资源而引起的竞争关系

临界区管理 链接到标题

一些基本定义 链接到标题

信息
临界资源：共享变量代表的资源
信息
临界区：并发进程中与共享变量有关的程序片段

临界区调度的三个原则 链接到标题

  • 互斥使用，有空让进
  • 忙则等待，有限等待
  • 择一而入，算法可行

几个错误算法示例 链接到标题

虽然下面将要演示的算法都是错误的，但是对于理解并发思维还是很有帮助的。

算法1 链接到标题

信息 
bool inside1=FALSE;
bool inside2=FALSE;
cobegin //并发专用

process P1()
{
  while(inside2);//等待
  inside1=TRUE;
  {临界区}
  inside1=FALSE;
}

process P2()
{
  while(inside1);//等待
  inside2=TRUE;
  {临界区}
  inside2=FALSE;
}

coend
分析可知如果在并发部分第1-2之间发生调度就不满足互斥使用原则，因此程序错误

算法2 链接到标题

那如果将这1与2行调换顺序呢？

信息 
bool inside1=FALSE;
bool inside2=FALSE;
cobegin //并发专用

process P1()
{
  while(inside2);//等待
  inside1=TRUE;
  {临界区}
  inside1=FALSE;
}

process P2()
{
  while(inside1);//等待
  inside2=TRUE;
  {临界区}
  inside2=FALSE;
}

coend
这又会出现另外的极端：两者都无法进入临界区

Peterson算法 链接到标题

上面可见简单的更改简单程序的执行顺序无法解决问题，因此我们需要引入一个新的变量才有可能解决问题，这也就是Peterson算法！

信息 
// 和上面的一样
cobegin

process P1()
{
  inside[0]=true;
  turn=1;
  while(inside[1]&&turn==1);//等待(&&是与)
  {临界区}
  inside[0]=false;
}

process P2()
{
  inside[1]=true;
  turn=0;
  while(inside[0]&&turn==0);//等待
  {临界区}
  inside[1]=false;
}

coend
在这个程序中就不存在之前的因并发导致的错误了。

同步和同步机制 链接到标题

在ppt上还介绍了另外及几种改算法的方法，比如TS等，不过我们这里直接开始信号量等同步机制

生产者与消费者模型 链接到标题

先说一下进程同步的一些概念 进程同步：

并发进程需要 协调彼此推进的速度，从而保证其正确性。

警告
注意，这里是 协调彼此的速度，因此同步并不要求一起进行，而是其运行过程要有一定的联系，比如互斥其实也算是一种同步

这个模型其实很简单：

  • 生产者生产“产品”放入缓冲区,并消耗“空间”。
  • 消费者从缓冲区取出“产品”，返回“空间”。
  • 如果没有空间，生产者就等待；如果没有产品，消费者就等待。

错误代码 链接到标题 

int counter = 0;           // 计数器，表示缓冲区中的产品数量
int buffer[k];             // 缓冲区，大小为k
int in = 0, out = 0;       // 缓冲区的输入和输出指针
cobegin

process producer(void) {
  while (true) {
    {produce an item in nextp};
    if (counter == k)
      sleep(producer);
    buffer[in] = nextp;
    in = (in + 1) % k;
    counter++;
    if (counter == 1)
      wakeup(consumer);
  }
}

process consumer(void) {
  while (true) {
    if (counter == 0)
      sleep(consumer);
    nextc = buffer[out];
    out = (out + 1) % k;
    counter--;
    if (counter == k-1)
      wakeup(producer);
    {consume the item in nextc};
  }
}

coend

为什么错误的原因自己分析，也是因为并行导致的不满足临界条件。也就是说简单的程序还是不行的。

信号量 链接到标题

一种提供P、V两种操作原语的软件资源，用于封锁临界区、进程同步、维护资源计数

注释
原语：内核中执行的不可被中断的过程
如果从程序的角度来看，信号量可以理解为一种特殊的结构体

typedef struct semaphore {
  int value; // 信号量的值
  PCB  * queue; // 等待队列
} semaphore;

由此我们需要两个原子操作(不可能被并发调度打断的程序)。

P、V操作 链接到标题 

void P(semaphore &s)
{
  s.value--;
  if (s.value < 0) //s.value表示资源(比如空间或者产品)
  {
    W(s.queue); // 阻塞进程
  }
}

void V(semaphore &s)
{
  s.value++;
  if (s.value <= 0) 
  {
    R(s.queue); // 唤醒等待队列里面的第一个进程
  }
}
如果是二元信号量的话，s.value的值只能是0或1，表示资源是否被占用。

实际问题 链接到标题

单个生产者单个消费者共享一个缓冲区 链接到标题

信息 
int B;  // 单个缓冲区
semaphore empty = 1;  // 可以使用的空缓冲区数，初始为1表示缓冲区为空
semaphore full = 0;   // 缓冲区内可以使用的产品数，初始为0表示没有产品

cobegin

process producer() {
  while(true) {
    {生产一个产品};
    P(empty);    // 检查是否有空间
    {将产品放入缓冲区B};
    V(full);     // 通知消费者有产品可用
  }
}

process consumer() {
  while(true) {
    P(full);     // 检查是否有产品
    {从缓冲区B取出产品};
    V(empty);    // 通知生产者有空间可用
    {消费产品};
  }
}

coend
显然，这个程序是没有任何问题的。如果是 共享多个缓冲器，那更好！一样的程序，改一下empty=k即可。

多个生产者单个消费者共享多个缓冲区 链接到标题

这时候会出现一种冲突状态：

  • 多个生产者将产品放入同一个缓冲区，
  • 多个消费者同时从同一个缓冲区取出产品。 同样的，与前面借书冲突的解决方法一样：如果不额外引入一个信号量，这就无法解决问题，我们引入mutex，代码如下
信息 
semaphore empty = k;  
semaphore full = 0;
semaphore mutex = 1; // 互斥信号量，初始为1表示可以进入临界区
int in=0, out=0; // 缓冲区的输入和输出指针
cobegin

process producer() {
  while(true) {
    {生产一个产品};
    P(empty);    // 检查是否有空间
    P(mutex);    // 进入临界区
    {将产品放入缓冲区B[in]};
    in = (in + 1) % k; // 更新输入指针
    V(mutex);    // 离开临界区
    V(full);     // 通知消费者有产品可用
  }
}

process consumer() {
  while(true) {
    P(full);     // 检查是否有产品
    P(mutex);    // 进入临界区
    {从缓冲区B[out]取出产品};
    out = (out + 1) % k; // 更新输出指针
    V(mutex);    // 离开临界区
    V(empty);    // 通知生产者有空间可用
    {消费产品};
  }
}

coend

多进程同步关系的解决 链接到标题

首先先来尝试用并发程序来描述

flowchart LR S1 --> S2 S1 --> S3 S1 --> S4 S2 --> S5 S3 --> S5 S4 --> S6 S5 --> S7 S6 --> S7 S7 --> S8

我们可以通过下面的并发程序来描述上面的进程关系

struct semaphore s1_s2,s1_s3,s1_s4,s2_s5,s3_s5,s4_s6,s5_s7,s6_s7,s7_s8;
s1_s2=0,s1_s3=0,s1_s4=0,s2_s5=0,s3_s5=0,s4_s6=0,s5_s7=0,s6_s7=0,s7_s8=0;
cobegin
{S1;V(s1_s2);V(s1_s3);V(s1_s4);}
{P(s1_s2);S2;V(s2_s5);}
{P(s1_s3);S3;V(s3_s5);V(s3_s6);}
{P(s1_s4);S4;V(s4_s6);}
{P(s2_s5);P(s3_s5);S5;V(s5_s7);}
{P(s4_s6);P(s3_s6);S6;V(s6_s7);}
{P(s5_s7);P(s6_s7);S7;V(s7_s8);}
{P(s7_s8);S8;}
coend

于是我们就可以解决一些拥有更复杂进程同步关系的问题了

读者-写者问题 链接到标题

理发师问题 链接到标题

哲学家就餐问题 链接到标题

死锁 链接到标题

如果在一个进程集合中的每个进程都在等待只能由该集合中的其他进程才能引发的事件，而陷入无限僵持的局面，则称这组进程或系统此时发生死锁。

四个必要条件 链接到标题

  • 互斥条件：进程互斥使用资源；
  • 占有和等待条件：申请新资源得不到满足时，不释放已占有资源；
  • 不剥夺条件：一个进程不能抢夺其他进程占有的资源；
  • 环路条件：存在循环等待链；也就是说只要有一条不满足就不能死锁；
信息
言外之意就是只要破坏其中一个条件就可以避免死锁的发生。

解决死锁 链接到标题

  • 死锁防止：通过修改前面三个条件，但是都对系统影响大，且会降低并发性以及资源利用率。
  • 死锁避免：破坏最后一个条件是对系统影响最小最容易实现的；

银行家算法 链接到标题

(相当抽象，先放一下)