并发进程的互斥,同步与死锁

并行和并发的区别

并行(parallel)：指在同一时刻，有多条指令在多个处理器上同时执行。所以无论从微观还是从宏观来看，二者都是一起执行的。

并发(concurrency)：指在同一时刻只能有一条指令执行，但多个进程指令被快速的轮换执行，使得在宏观上具有多个进程同时执行的效果，但在微观上并不是同时执行的，只是把时间分成若干段，使多个进程快速交替的执行。

并行在多处理器系统中存在，而并发可以在单处理器和多处理器系统中都存在，并发能够在单处理器系统中存在是因为并发是并行的假象，并行要求程序能够同时执行多个操作，而并发只是要求程序假装同时执行多个操作（每个小时间片执行一个操作，多个操作快速切换执行）。

并发进程

并发进程分为无关的并发进程和交互的并发进程.

无关的并发进程不会相互影响,交互的并发进程在执行时间上可能导致:1.结果不唯一,2.进程永远等待

交互的并发进程的关系

1. 竞争关系:(可能导致死锁问题,饥饿问题)
   1. 解决方案是进程互斥
2. 协作关系:为相同任务而共享某些资源
   1. 解决方案是进程同步

进程互斥

采用临界区管理方式:互斥使用,有空让进,忙则等待,有限等待,择一而入,算法可行

1. 实现临界区管理的Peterson算法:

bool inside[2] = {false,false};
enum {0,1} turn;
cobegin://下面两个进程并发
process P0(){
    inside[0] = true;
    turn = 1;
    while(inside[1]&&turn==1);
    {临界区}
    inside[0] = false;
}
process P1(){
    inside[1] = true;
    turn = 0;
    while(inside[0]&&turn==0);
    {临界区}
    inside[1] = false;
}
coend;//上面都是伪代码

1. 实现临界区管理的硬件设施:
2. 关中断
3. 测试并建立指令
4. 对换指令

进程同步

1. PV操作和信号量
   1. P操作申请一个资源
   2. V操作释放一个资源
2. 管程
3. 进程通信
   1. 管道通信
   2. 共享内存通信
   3. 消息传递通信
   4. 套接字通信

死锁

定义:资源共享的条件下产生的资源需求冲突,进程因等待其他进程释放资源而陷入僵持的情况.

避免策略: 银行家算法(没有实际意义)

检测和解除:释放不阻塞不独立的进程,回收资源分配给其他需要的进程,重复上面的操作,如果最后所有进程不独立,则该并发进程可能陷入死锁

解除死锁的方法:

1. 结束所有进程,重启操作系统
2. 剥夺死锁进程占用的资源
3. 撤销死锁进程(所有/逐个)
4. 根据系统检查点,进程回退
5. 抑制未陷入死锁的进程释放资源,尝试解开陷入死锁的进程