并发进程

与时间有关的错误

• 并发错
• 永远等待

进程中基本关系

• 竞争关系
  因共享资源而产生交互和制约关系，又称互斥关系
  资源竞争会引发两个控制问题：死锁和饥饿
• 协作关系
  进程同步指为完成共同任务的并发进程基于某个条件来协调其活动，因为需要在某些位置上排定执行的先后次序而等待、传递信号或消息所产生的协作制约关系

进程互斥关系是一种特殊的进程同步关系

临界区

并发进程中与共享变量有关的程序段

信号量与PV操作

一般信号量

设s为一个记录型数据结构,一个分量为整型量value,另一个为信号量队列queue

P(s)

将信号量s减1，若结果 <0，则执行P操作的进程被阻塞

V(s)

将信号量s加1，若结果 ≤0，则唤醒该信号量等待list中的一个进程

• 信号量 s>0，s代表实际可用的物理资源数
• 信号量 s<0，s代表等待队列中的进程数

typedef struct semaphore {
    int value;             /*信号量值*/
    struct pcb *list;    /*信号量队列指针*/
 }; 
void P(semaphore &s) {
     s.value--;            
     if(s.value<0)      // s.value--前小于或等于0     
         sleep(s.list);      
}                     
void V(semaphore &s) {
    s.value++;            
    if(s.value<=0)      // s.value++ 前小于0
        wakeup(s.list);        
}                      

二值信号量

信号量的value只能取值0,1

信号量实现互斥

semaphore mutex;
mutex = 1;
cobegin
    process Pi(){
        P(mutex);
        /* 临界区 */
        V(mutex);
    }
coend

信号量例子

自己看书

进程通信（IPC）

内存进程中，大多数都是无关的（互不干扰），只有少数有关

通信方式（机制）

• 信号
• 管道
• 消息传递
• 信号量
• 共享内存

死锁

死锁防止

产生条件

• 互斥条件
  进程互斥排他使用独占型资源
• 占有和等待条件
  进程在请求资源得不到满足而等待时，不释放占有资源
• 不剥夺条件
  已获得资源不允许被其它进程剥夺
• 循环等待条件
  每个进程都在等待链中等待下一个进程所持有的资源，造成这组进程永远处于等待状态

死锁防止策略

破坏产生条件中的一个或多个

死锁避免

动态地确定是否分配资源给提出请求的进程，如果一个资源分配会导致系统下一步死锁，便拒绝本次分配

死锁防止跟死锁避免的区别

• 死锁防止会降低系统并发性，导致低效的资源利用率
• 死锁避免允许系统同时存在前三个必要条件（互斥、占有和等待、不剥夺），通过合适的资源分配方法确保不会出现进程循环等待链，从而避免死锁

银行家算法

• Request<=Need，否则申请量超过最大需求数，报错
• Request<=Available，否则申请量超过当前拥有的可分配量，让进程等待
• 试探性分配
  • Allocation = Allocation + Request
  • Available = Available - Request
  • Need = Need - Request
• 安全性测试算法
  • Work = Available possible = true
  • 从进程集合中找出满足 Need <= Work
    • 如果不存在，停止，possible = false，返回不安全
    • 存在，回收已分配内存，Work = Work + Allocation，找下一个
  • 返回安全

进程-资源分配图

无环——无死锁
有环——可能死锁

image.png

资源指向已分配的进程（已经分配了）
进程箭头指向请求的资源（还没请求到）

死锁的检测算法

• Work = Available
• 如果 Allocation ！= 0 finish[k] = false 否则 finish[k] = true
• 寻找一个未完成的进程， Request <= Work
  • 找不到，处于死锁状态，finish=false 的进程是处于死锁的进程
  • Work = Work + Allocation，finish = true ，找下一个

死锁的恢复方法

• 结束所有进程的执行并重新启动操作系统
• 撤消陷于死锁的所有进程，解除死锁，继续运行
• 逐个撤消陷于死锁的进程，回收其资源并重新分配，直至死锁解除