进程同步

process synchronization

多个进程在操作系统中并发向前推进，多个进程并发执行过程中，并不一定完全独立，会相互依赖。

如何在操作系统中实现这些依赖关系，就是进程同步问题。

一个公交车程序，有司机进程和售票员进程。司机进程负责驾驶和停车，售票员负责售票开关门。

开关门要在司机停车后进行，司机开车要在关门后进行。两个进程存在等待和唤醒，因此，等待和唤醒实现了进程之间的相互依赖。司机和售票员合作共同推进公交的正常运行。

司机等一个信号，售票员发一个信号，这个信号去同步两个进程。停车到站也是一样，到站停车司机发一个信号，售票员等到这个信号后，开门。

同步就是一个进程在需要同步的地方停下来等待依赖的进程。进程同步就是通过对进程等待和唤醒的控制来让多个进程步调一致。

进程同步和信号自然而然就引出来了。

信号到信号量

生产者-消费者问题

等待是进程同步的核心，对于生产者消费者的例子，下面伪代码的 WHILE 就是要表达等待的含义。进程走走停停，关键在停，让几个进程协同工作。

#define BUFFER_SIZE  10
typedef struct { ... } item_t;

item_t buffer[BUFFER_SIZE];
item_t item;
int in = out = counter = 0;

/* 生产者 */
while(1)
{
    while(counter == BUFFER_SIZE); /* 缓冲区满，等待 */

    buffer[in] = item;
    in = (in + 1)%BUFFER_SIZE;
    counter++;   /* 启动消费者的信号 */
}

/* 消费者 */
while(1)
{
    while(counter == 0); /* 缓冲区空，等待 */

    item = buffer[out];
    out = (out+1)%BUFFER_SIZE;
    counter--;  /* 启动生产者的信号 */    
}

上面是伪代码，buffer像是个环形缓冲队列，counter记录了数据个数，通过%实现了环形缓冲。

更靠近编程的实现：

/* Producer */
while(true)
{
    if (counter == BUFFER_SIZE)
        sleep_on(empty);
    buffer[in] = item;
    in = (in+1) % BUFFER_SIZE;
    counte++;
    if (counter == 1)
        wake_up(full);
}

/* Consumer */
while(true)
{
    if (counter == 0)
        sleep_on(full);
    item = buffer[out];
    out = (out+1) % BUFFER_SIZE;
    counte--;
    if (counter == BUFFER_SIZE - 1)
        wake_up(empty);
}

操作系统要去实现睡眠和唤醒这两个事情。

信号扩展为信号量

counter可以记录的东西太少了，用信号记录进行走停位置不够应付更复杂的情况，counter表达出来的语义不够，无法反映阻塞在empty信号上的进程个数信息。

还应该记录更全面的东西，这就是信号量。

信号量(semaphore)就是在信号上关联一个整数，根据这个整数来决定进程阻塞或者唤醒。

根据信号量的观点来重新考虑信号empty。

对于生产者进程，正数表示还有资源，不用阻塞，继续执行；零或负数表示没有资源，阻塞等待唤醒。

这个问题有了信号量的解决方案。由于是共享缓存区，每个时刻只能被一个进程修改，因此要互斥进入。

semaphore full  = 0;
semaphore empty = BUFFER_SIZE;
semaphore mutex = 1;

信号量的数据结构与操作伪代码

struct semaphore
{
    int value;
    PCB *queue;
}
P(semaphore s)
{
    s.value--;
    if(s.value<0)
        sleep_on(s.queue);
}
V(semaphore s)
{
    s.value++;
    if(s.value<=0)
        wake_up(s.queue);
}

/* Producer */
while(true)
{
    if (counter == BUFFER_SIZE)
        sleep_on(empty);
    buffer[in] = item;
    in = (in+1) % BUFFER_SIZE;
    counte++;
    if (counter == 1)
        wake_up(full);
}

/* Producer */
while(true)
{
    if (counter == BUFFER_SIZE)
        sleep_on(empty);
    buffer[in] = item;
    in = (in+1) % BUFFER_SIZE;
    counte++;
    if (counter == 1)
        wake_up(full);
}

/* Consumer */
while(true)
{
    if (counter == 0)
        sleep_on(full);
    item = buffer[out];
    out = (out+1) % BUFFER_SIZE;
    counte--;
    if (counter == BUFFER_SIZE - 1)
        wake_up(empty);
}

临界区——信号量保护

信号量的作用就是根据信号量数值表达出来的语义来决定进程的停与走。

因此信号量的数值非常重要，信号量要被多个进程共享操作，在多个进程“共同”修改信号量时要对信号量进行保护。每个进程对信号量的修改要么一点不做，要么全部做完，即不能中途打断。

调度不知道时什么时候进行的，不知道什么时候发生中断，这种错误不是编程造成的错误，时CPU竞争造成的，因此需要一个保护机制。

一个直观想法是，在写共享变量的时候阻止其他进程的访问。有个概念叫原子操作，即最小操作不可分割，方法是上个锁。

这就要引出临界区的概念了，修改信号量的代码必须在临界区里面，具体到程序，就是进入区的代码和退出区的代码了。

临界区的原则是互斥进入，同时只能有一个进入，保证这段是临界区。

好的临界区：有空就让进，无能无限等待。

临界区软件实现

进入临界区的一个尝试：轮换法。可以解决一些问题，但是不好。

加个标记，但是也有问题，死锁了，两个进程都自旋，临界区都空闲。

解决方法，Peterson算法。轮转+标记

现实情况下，临界区不止两个进程，因此有了Lamport面包店算法，这是个排号算法。

临界区的硬件实现

面包店算法解决了多个进程对临界区的互斥访问问题，但是作为一个软件算法，也要考虑效率问题，号码选取、维护、判断等操作的代价都不小。在产生号码的时候总是比当前所有的号码都要大，这就有可能导致号码溢出。

临界区只允许一个进程进入，是因为调度切换造成的，也可以从调度的角度去考虑，在中断里实现调度，所以直接关掉中断，时间片都不操作了。

这种方法，单CPU好使，多CPU不好使了。

锁是个变量，再用一个变量去控制，这个思路是有问题的，用信号量取保护信号量不被修改。没法这么搞。

因此要求硬件设计上直接有个硬件原子指令，即硬件原子指令法。

修改变量要一步完成。

代码实现

临界区保护了信号量P、V操作的原子性，从而保证信号量数值的语义正确性。操作系统需要给上层用户提供信号量的定义接口和PV操作接口，用户可以直接使用接口完成进程同步。

根据信号量的含义

• 信号量是一个需要被多个进程共享的整数

• 根据信号量的值让相应的进程睡眠或唤醒，操作对象为进程PCB

• 操作这个整数时要进行临界区保护

应该将信号量操作放在操作系统内核，信号量的PV操作应该实现为系统调用，在系统内核里操作PCB、开关中断等动作简单可行、安全可靠，又能屏蔽细节。通常信号量实现为内核中的一个数据对象，PV操作实现为操作系统给上层用户提供的两个系统调用。

POSIX标准针对信号量定义了下面四个基本系统调用：

sem_t *sem_open(const char *name, int oflag, mode_t mode, unsigned int value);
int sem_unlink(count char *name);
int sem_wait(sem_t *sem);
int sem_post(sem_t *sem);

死锁

形成环路等待，自己等待的条件依赖自己向前执行。

死锁：互相等待对方持有的资源而造成的谁都无法执行的情况叫死锁。

死锁原因

死锁的4个必要条件：

• 互斥使用，资源的固有特性

• 不可抢占，资源只能自愿放弃，如车开走后

• 请求和保持，进程必须占有资源，再去申请

• 循环等待，在资源分配图中存在一个环路

死锁处理的方法

• 死锁预防，破坏死锁条件

• 死锁避免，检测资源请求，造成死锁就拒绝

• 死锁检测+回复，重启进程，重新来过，本来就是小概率事件

• 死锁忽略，就当没这回事，有问题重启电脑。

事实上，linux和windows在普通PC机上就是死锁忽略的。

死锁预防

破坏死锁发生的必要条件。

在执行进程前，一次性申请所有需要的资源。不会占有资源再去申请其他资源。

缺点：

• 需要预知未来，编程困难

• 许多资源分配后很长时间才使用，资源使用率低

银行家算法

死锁检测/恢复

让资源随意使用，但是在出现问题的时候，能够检测死锁，并把系统从死锁中回复出来。

需要一个死锁检测算法。

改造银行家算法。

死锁恢复需要进程回滚，回滚也是个大问题，PC指针倒是很容易往前移动，但是已经修改的文件、发出的网络数据包该如何处理，回滚到哪里更合适，选择哪些进程回滚？

死锁忽略

死锁预防和死锁避免对资源产生了许多限制，但是处理起来也很麻烦，因此也就出现了死锁忽略处理方法，就是对死锁不做任何处理，这种方法也称为“鸵鸟算法”。

虽然啥都不做，但是Windows、Linux都是采用这种方法处理的，出现问题只要重启一下PC就好了。