跳到主要内容

同步和互斥

同步和互斥是进程之间竞争和协作的解决方法（两种进程关系）。

大多数情况下, 同步是建立在互斥的基础之上的. 同步是一种更为复杂的互斥，而互斥是一种特殊的同步。

备注

消费者和消费者是互斥关系，消费者和生产者是同步关系。

  1. 同步是直接制约关系，在异步环境下进行，可以用信号量实现同步。
  2. 互斥是间接制约关系，满足
    1. 空闲让进: 独占资源有空, 你才能进入使用
    2. 忙则等待: 独占资源没空, 你就得等待
    3. 有限等待: 但我承诺你不会一直等
    4. 让权等待: 但如果你等待的时候, 请把CPU让出来
临界区(critical section)

是指包含有共享数据的一段代码，这些代码可能被多个线程访问或修改。临界区的存在就是为了保证当有一个线程在临界区内执行的时候，不能有其他任何 线程被允许在临界区执行。对临界资源的访问必须互斥的进行

互斥的实现​

使用互斥锁(互斥量)Mutex实现.

/*
 *强制交换次序访问，不交换不能访问
*/
int turn = 0; 
P0:{
    while(turn != 0);
    do critical section;
    turn = 1;
}
P1:{
    while turn != 1;
    do critical section;
    turn = 0;
}

同步的实现​

管程Monitor​

monitor Demo{
    sharing_struct S;//系统中某种资源定义的共享数据结构
    condition x;//阻塞原因条件变量,保存一个等待队列.实现同步
    condition y;//多个条件变量的设置
    init_code(){
        S = 5;
    }
    take_away(){
        if(S<=0) x.wait(); //资源不够,在x上阻塞等待
        --S;
    }
    give_back(){
        ++S;
        if(x.hasNext) x.signal();//唤醒一个阻塞进程
    }
};
  1. 共享资源的操作封装起来,管程内的共享数据结构只能被管程内的过程所访问
  2. 每次仅允许一个进程进入管程,从而实现进程互斥
  3. 使用条件变量这种同步机制

信号量Semaphore(PV)​

// 整型信号量
wait(S){
    while(S<=0);
    S = S - 1;
}
signal(S){
    S = S + 1;
}

//记录型信号量
typedef struct{
	int value;
	struct process *Q;//阻塞进程的排队链表
} semaphore;

void wait(semaphore S){
    S.value --;
    if(S.value <0){
        block(S.Q);//运行态进入阻塞态
        add this process to S.Q;
    }
}

void signal(semaphore S){
    S.value ++;
    if(S.value<=0){
        remve a process P from S.Q;
        wakeup(P);//唤醒阻塞队伍中的第一个进程
    }
}


//同步实现
semaphore S = 0;
P1(){
     x;
     V(S);
 }
P2(){
    P(S);
    y;
}

// 互斥实现
semaphore S = 1;
P1(){
    P(S);
    critical section;
    V(S);
}
P2(){
    P(S);
    critical section;
    V(S);
}

经典同步问题的处理方法​

  1. 生产者和消费者问题
  2. 申请资源P操作一定在互斥加锁P操作之前，否则会导致死锁。
  3. 生产者消费者问题中如果生产者和消费者都是唯一，mutex互斥信号量可以不要。
  4. 读者写者问题：写者优先、读者优先、顺序访问
  5. 哲学家进餐问题：死锁问题解决：
    1. 最多允许n-1个同时进餐
    2. 仅当一个哲学家左右两边的筷子同时可用，才会拿起筷子
    3. 哲学家编号，奇数先拿左筷子，偶数先拿右筷子
//生产者消费者问题
Semaphore filledBuffer = 0;
Semaphore emptyBuffer = n;
Semaphore mutex = 1;

//读者写者问题
Semaphore mutex = 1; //read or write mutex
Semaphore rmutex = 1; //change count mutex in readers
Semaphore wmutex = 1; //顺序锁，当有writer等待读写锁时，后来的reader不再进入count
int count = 0;

//哲学家进餐问题
semaphore fork[5] = {1,1,1,1,1};
经典PV模型的算法设计思路
  1. 关系分析：确定问题中存在的同步关系。存在一对同步关系，往往就需要一中资源信号量。资源信号量的初值根据题目。题目中每一句话一般都暗示一种同步关系或暗示一类资源。
  2. 确定临界资源：mutex互斥信号量访问临界资源。
  3. 整理思路。
  4. PV成对出现：具体注意：申请资源P操作一定在互斥加锁P操作之前，否则会导致死锁。生产者消费者问题中如果生产者和消费者都是唯一，mutex互斥信号量可以不要。PV操作要分别紧贴临界区的头尾部，临界区的代码要尽量短，不能有死循环。
  5. 用于mutex的semaphore通常设为1。

具体注意：

  1. PV成对出现
  2. PV操作要分别紧贴临界区的头尾部，临界区的代码要尽量短，不能有死循环
  3. 用于互斥的信号量通常设为1.

死锁​

  1. 参与死锁的进程至少有两个
  2. 每个参与死锁的进程均等待资源
  3. 参与死锁的进程中至少有两个进程占有资源
  4. 死锁进程是系统中当前进程集合的一个子集

死锁产生的原因

  1. 不可剥夺性系统资源不足
  2. 进程推进顺序不当
  3. 信号量使用不当

死锁产生的必要条件

  1. 互斥: 多个进程请求访问的资源是独占的,需要互斥访问
  2. 不剥夺: 不能剥夺访问
  3. 请求与保持: 等待的时间中不会放弃已有的资源
  4. 环路等待: 我等你拥有的资源, 你等我的

死锁预防​

会对系统并发性产生很大的副作用

破坏4个必要条件之一：

  1. 破坏互斥条件：不太可能，资源本身的属性限制
  2. 破坏不剥夺条件：获得了某些资源的进程，若新的资源请求不能立即满足，必须释放所有已有的资源。造成之前一段工作失效，重复申请和释放资源增加系统开销，降低系统吞吐量。通常不用于代价较大的场合
  3. 破坏请求保持条件：预先静态分配方法，一次性申请所有资源，没有满足前不投入运行。简单安全，但是降低了资源利用率。导致其它进程饥饿
  4. 破坏环路条件：有序资源分配方法，资源编号。确定每个进程必须按编号递增的顺序请求资源。同类资源一次申请完。

死锁避免：银行家算法​

将系统的状态分为安全状态和不安全状态，系统进行资源分配前先计算资源分配的安全性，若此次分配不会导致系统进入不安全状态，则分配，否则等待。若某一刻，系统能按某种顺序为每个进程分配所需的资源，直至最大需求，使每个进程都可以顺利完成，则此时的系统状态为安全状态，该序列为安全序列。不存在一个该序列，则此时的系统状态为不安全状态。

银行家算法：

  1. Max matrix最大需求矩阵
  2. Allocation matrix 分配矩阵
  3. Need matrix需求矩阵
  4. Available vector 可利用资源向量
  5. 安全性算法： 7. work := available 8. finish:= {true,false}[]

死锁检测和解除​

  1. 资源分配图：
  2. 死锁定理：资源分配图的简化-删掉请求可获取的进程边
  3. 检测时间：每次分配后，但算法复杂，系统开销大，选取比较长的时间间隔来执行。
  4. 解除方法：剥夺资源-撤消进程-进程回退
几个概念

饥饿：等待时间给进程推进和响应带来明显的影响时。 饿死：饥饿到一定程度，进程所赋予的任务即使完成也不再具有实际意义 活锁：忙时等待条件下发生的饥饿，比如不公平的互斥算法，虽然此时进程仍然在执行，但有些进程由于无法调度执行，好像发生了死锁。

Loading Comments...