进程同步

进程互斥

一个进程访问某临界资源时，另一个想访问该临界资源的进程必须等待

进程互斥软件实现

单标志法

违反 空闲让进

双标志先检查法

违反 忙则等待

双标志后检查法

违 反空闲让进 和 有限等待

Peterson算法

未遵循 让权等待

进程互斥硬件实现

中断屏蔽法

进程开始访问临界区到结束为止都不允许被中断，就不会发生进程切换

TestAndSet指令

TSL把上锁并检查用硬件方式变成了原子操作

优点：实现简单，适用于多处理机环境

缺点：不满足让权等待，暂时无法进入临界区的进程会占用cpu循环执行TSL

Swap指令

也是原子操作，与TSL基本一样都是把lock记录在old中然后lock变为true

信号量机制

整型信号量

记录型信号量

信号量实现进程同步

生产者-消费者

同步是不同进程间同步，互斥是对临界资源的互斥

读者-写者

读-写互斥，写-写互斥，但是读-读不互斥

上述方法如果在读者读期间不断有读者进入会导致写进程饿死

下面可以让写进程进入后，先阻塞读进程的排队但不影响已经开始读的进程，只要在写进程之前进入的读者读完就可以开始写

哲学家进餐

只有互斥关系，主要是避免死锁

第三种方案就是使用一个全局的互斥锁（Mutex）来保护“拿筷子”这个动作。哲学家在拿筷子前，先查看左右邻居是否在吃饭（设置 THINKING, HUNGRY, EATING 三种状态）。只有左右邻居都不在吃饭时，他才把自己的状态改为 EATING 并同时拿起两根筷子。

管程

为了解决信号量（Semaphore）机制带来的“程序编写难、易出错”而诞生的高级同步原语。由以下四部分组成

共享数据：就是VIP室里的那笔钱（临界资源）。它是私有的，外部绝不能直接修改。

入口函数：也就是操作这笔钱的方法（比如存钱、取钱）。外部线程只能通过调用这些特定的方法来访问共享数据。

对共享数据进行初始化的语句。

管程的名字。

自动互斥机制（最核心）：管程天生自带一把互斥锁。任何时刻，最多只能有一个线程在管程内部执行入口函数。 其他试图进去的线程会被自动挡在门外排队（入口队列）。

条件变量（Condition Variables）：用于线程间的同步（等待/唤醒）。如果一个线程进了管程，发现条件不满足（比如想取钱但余额不足），它不能占着茅坑不拉屎，必须调用 wait() 把自己挂起，并自动交出管程的控制权，去“条件队列”里等，直到别的线程调用 signal() 或 notify() 把它唤醒。

死锁

必要条件：

互斥：每个资源要么已经分配给了一个进程，要么就是可用的。

不可剥夺：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。

请求和保持：已经得到了某个资源的进程可以再请求新的资源。

循环等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。

处理策略：

预防死锁（破坏四个必要条件中一个或多个）

避免死锁（阻止系统进入不安全状态，银行家算法）

死锁的检测和解除（允许死锁发生，os会检测出死锁然后解除）

预防死锁

破坏互斥：SPOOLing技术把独占设备逻辑上改为共享设备，但并不是所有资源都可以，为了系统安全有时要保护这种互斥性；

破坏不剥夺：主动释放或抢占，释放会导致前一阶段工作失效，适用于易保存和恢复的资源；反复申请释放会增大系统开销降低系统吞吐量；主动释放可能会导致饥饿

破坏请求和保持：静态分配，运行前申请完全部资源；资源利用率低，也可能导致某些进程饥饿

破坏循环等待：顺序资源分配，进程只有在已经占有小编号资源后才能申请大编号资源；不方便增加新资源，进程实际使用资源顺序可能与编号递增不一致，会导致资源浪费

避免死锁

安全序列：系统按照这种序列分配资源，每个进程都能顺利完成；

安全状态：能找出至少一个安全序列；

银行家算法

进程申请资源时，先预判此次分配是否会使系统进入不安全状态，如果会进入不安全则不答应此次请求，先阻塞进程

Max - Allocation = Need

Available表示可用资源，Request_i表示进程 i 本次申请的资源量

死锁检测与解除

矩形内为资源总量，绿色边为已经分配量，蓝色边为还需分配量