L16 进程同步与信号量

例子：生产者和消费者

通过程序“走走停停”来保证多进程合作的合理有序即为进程同步

#define BUFFER_SIZE 10
typedef struct {...} item;
item buffer[BUFFER_SIZE];
int in = out = counter = 0;
//========生产者==========
while (true) {
while(counter== BUFFER_SIZE)
  ; 
    buffer[in] = item;
    in = (in + 1) % BUFFER_SIZE;
    counter++;
}
//==========消费者============
while (true) {
while(counter== 0) 
                ; 
    item = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    counter--;
}

:::tips 如果是多个用户，那么上述的仅使用信号的方式不可行 ::: :::info 信号只有有和没有两种状态;需要用信号量来保证更丰富的信息 :::

信号量

不仅希望知道有多少剩余的资源；还需要知道有多少进程在停滞等待 :::info 信号量：记录一些信息，并根据这个信息决定睡眠还是唤醒 :::

缓冲区满，P1执行，P1sleep，sem=-1；
P2执行，P2sleep，sem=-2
C执行，wakeupP1，sem=-1
C执行，wakeupP2，sem=0；
C执行，sem=1；（还有一个资源or缓冲区）
实现

struct semaphore 
{
    int value; //记录资源个数
    PCB *queue;//记录等待在该信号量上的进程
}
P(semaphore s); //消费资源
V(semaphore s); //产生资源
P(semaphore s)
{
   s.value--;
    if(s.value<0){
        sleep(s.queue);
    }
}
V(semaphore s){
    s.value++;
    if(s.value<=0){
    wakeup(s.queue);
    }
}

L17 信号量的临界保护

:::info 多个进程对于同一个变量修改，容易出错

前一个进程尚未完全将变量修改，即切到另一个进程了，此时出错了
时间片到了，直接切换了
……

错误是因为共享数据竞争造成的错误 ::: :::tips 在写共享变量empty时，阻止其他进程也访问empty :::

临界区

:::info 一次只允许一个进程进入的那一段代码；读写信号量的代码一定是临界区 :::

//进入区
//临界区
//退出区

基本原则：

互斥进入
有空让进

有限等待

实现方法1：轮换法

while (turn!=0);
//临界
turn =1;
//-----------
while(turn!=1);
//临界
turn=0;

满足互斥进入
不满足有空让进，进了一个另一个就进不来了
实现方法2：标记法
```
//-------------------------
flag[0]=true;
while(flag[1]);
//临界区
flag[0]=false;
//--------------------------
flag[1]=true;
while(flag[0]);
//临界区
flag[1]=false;
```
会出现两人都在等待的情况！ :::tips 让其中一个人更加勤劳！—非对称的标记 :::
Peterson算法
```cpp flag[0]=true; turn =1; while(flag[1]&&turn==1); //临界 flag[0]=flase; //———————- //———————- flag[1]=true; turn=0; while(flag[0]&&turn==0); // flag[1]=false;

满足三个原则！<br />turn起到轮换的作用
<a name="Q7uay"></a>
## 多个进程：面包店算法
:::info
标记和轮转结合<br />类似取号的想法
-  如何轮转: 每个进程都获得一个序号， 序号最小的进入  
-  如何标记: 进程离开时序号为0，不为0的 序号即标记  
-  面包店: 每个进入商店的客户都获得一个号码，号码最小的先得到服务；号码相 同时，名字靠前的先服务。  
:::
```cpp
choosing[i] = true; num[i] = max(num[0], …, num[n-1])+1;
choosing[i] = false; for(j=0; j<n; j++) { while(choosing[j]);
while ((num[j] != 0) && (num[j], j)<(num[i], i])); }
//临界区
num[i] = 0;

硬件版本：中断法

:::info 核心：阻止调度，阻止中断（只有在中断中才能调用schedule函数，才能切换到了另一进程） :::

cli();//关中断
//临界区
sti();//开中断

:::tips 多CPU情况下不好用 :::

硬件原子指令法

:::info 锁：本质是变量； ::: 指令不能被打断—原子指令；

boolean TestAndSet(boolean &x){
    boolean rv=x;
    x=true;
    return rv;
}

L18 信号量的代码实现

Producer(item){
P(empty);
    //...
V(full);
    //生成两个信号量
}
typedef struct {
char name[20];int value;//信号量的名字，值
task_struct * queue;    //存需要睡眠的进程的队列
} semtable[20];
sys_sem_open(char *name)
{ 
//在semtable中寻找name对上的;
//没找到则创建;
//返回对应的下标; 
}

用户态的程序

main(){
    sd=sem_open(“empty”);
    for(i=1 to 5)
    sem_wait(sd);
    write(fd,&i,4);
}
sys_sem_wait(int sd){
    cli();
    //进入临界区
    if(semtable[sd].value-- < 0){
        \\设置自己为阻塞;将自己加入semtable[sd].queue中;
        schedule();
    }
    sti(); 
}

Linux0.11中的实现

:::info 启动磁盘读以后睡眠，等待磁盘读完由磁盘中断将其唤醒，也是一种同步
:::

bread(int dev,int block){ 
    struct buffer_head * bh;
    ll_rw_block(READ,bh);
    wait_on_buffer(bh);
}
lock_buffer(buffer_head*bh){
    cli();
    while(bh->b_lock)//??? b_lock起到信号量的作用
        sleep_on(&bh->b_wait);
    bh->b_lock = 1;
    sti(); 
} 
void sleep_on(struct task_struct **p){
    struct task_struct *tmp;
    tmp = *p;
    *p = current;//这里形成了一种队列，因为当前的指针会存在当前进程对应的PCB中，
    //这种隐含的链式关系可以形成队列
    current->state = TASK_UNINTERRUPTIBLE;
    schedule();
    if (tmp)
    tmp->state=0;
}

L19 死锁

:::info 我们将这种多个进程由于互相等待对方持有的资源而造成的谁都无法执行的情况叫死锁
:::

死锁发生的原因

死锁的4个必要条件

互斥使用(Mutual exclusion)

资源的固有特性，如道口

不可抢占(No preemption)

资源只能自愿放弃，如车开走以后

请求和保持(Hold and wait)

进程必须占有资源，再去申请

循环等待(Circular wait)

在资源分配图中存在一个环路

如何解决

死锁预防破坏死锁出现的条件
死锁避免检测每个资源请求，如果造成死锁就拒绝
死锁检测+恢复检测到死锁出现时，让一些进程回滚，让出资源
死锁忽略就好像没有出现死锁一样

银行家算法
:::info 如果系统中的所有进程存在一个可完成的执行序列P1，…Pn，则称系统处于安全状态
:::
每次申请时假装分配，然后调用银行家算法
代价太大！每次申请都要测
死锁检测+恢复
定时检测或者发现资源利用率低才检测

Computer Science

🎊Part 06 进程同步与合作