操作系统第六章同步
进程同步的概念
进程同步：互相协作的进程之间有共享的数据，于是这里就有一个并发情况下，如何确保有序操作这些数据、维护一致性的问题。
竞争条件：多个进程并发访问和操作同一数据且执行结果与访问发生的特定顺序有关。
如果内核是非抢占内核，从根本上不会导致竞争条件，对于抢占内核需要认真设计以确保其内核数据结构不会导致竞争条件。
临界区
每个进程有一个代码段（code segment）称为临界区（critical section），在该区中进程可能改变共同变量、更新一个表或写一个文件等。这种系统的重要特征是当一个进程进入临界区，没有其他进程可被允许在临界区内执行，即没有两个进程可同时在临界区内执行
临界资源（Critical resource）每次只能被一个进程访问。而临界区则是能够访问临界资源的代码片段。
临界区问题（critical-section problem）是设计一个以便进程协作的协议。每个进程必须请求允许进入其临界区。实现请求的代码段称为进入区（entry section），临界区之后可有退出区（exit section），其他代码段成为剩余区（remainder section）
进程pi的通用结构
do{
进入区
临界区
退出区
剩余区
}while(TRUE);
临界区要满足的条件
-
互斥（mutual exclusion）：
如果进程Pi在其临界区内执行，那么其他进程都不能在其临界区内执行； -
前进（progress）：
如果没有进程在其临界区内执行且有进程需进入临界区，那么只有那么不在剩余区内执行的进程可参加选择，以确定谁能下一个进入临界区，且这种选择不能无限推迟； -
有限等待（bounded waiting）：
从一个进程做出进入临界区的请求，直到该请求允许为止，其他进程允许进入其临界区内的次数有上限。
Peterson算法
Peterson算法适用于两个进程在临界区与剩余区间交替执行
当使用Pi时，Pj来标示另一个进程，即j=i−1。Peterson算法需要在两个进程之间共享两个数据项
int turn;
boolean flag[2];
变量turn表示哪个进程可以进入其临界区
数组flag表示哪个进程想要进入临界区
//进程Pi的Peterson算法
do{
flag[i]=TRUE;
turn=j;
while(flag[j]&&turn==j);
临界区
flag[i]=FALSE;
剩余区
}while(TRUE)；
其实peterson就是孔融让梨，我想要你也想要，我让给你，你让给我，那我就收下临界区了（每个人只能让一次）
硬件同步
通过要求临界区用锁来防护，就可以避免竞争条件，即一个进程在进入临界区之前必须得到锁，而其退出临界区时释放锁
do{
请求锁
临界区
释放锁
剩余区
}while(TRUE)；
硬件特性能简化编程任务且提高系统效率
对于单处理器环境，临界区问题可简单地加以解决：在修改共享变量时要禁止中断出现。这样其他指令不可能执行，所以共享变量也不会被意外修改。这种方法通常为抢占式内核所采用。
在多处理器环境下，这种解决方法是不可行的，低效且影响系统时钟。
特殊硬件指令以允许能原子地（不可中断的）检查和修改字的内容或交换两个字的内容。如TestAndSet()，当两个指令同时执行在不同的CPU上，那么它们会按任意顺序来顺序执行。
TestAndSet指令定义：
boolean TestAndSet(boolean *target)
{
boolean rv=*target;
*target=TRUE;
return rv;
}
使用TestAndSet的互斥实现,声明一个Boolean变量lock，初始化为false
do{
while(TestAndSetLock(&lock))
;//do nothing
//critical section
lock=FALSE;
//remainder section
}while(TRUE);
Swap指令的定义：
void Swap(boolean *a,boolean *b)
{
booleab temp=*a;
*a=*b;
*b=temp;
}
使用Swap的互斥实现：key为每个进程局部变量，lock为全局变量,初始化为false
do{
key=TRUE;
while(key==TRUE)
Swap(&lock,&key);
//critical section
lock=FALSE;
//remainder section
}while(TRUE);
这些算法解决了互斥，但是并没有解决有限等待要求，因为所有的程序执行都是随机执行的问题。
下面介绍的使用TestAndSet的算法，该算法满足所有的临界区的三个要求。
公用的数据结构如下
boolean waiting[i] = TRUE;
boolean lock;
初始化均为false。
do{
//如果进程i想要进入临界区而且此时临界区开放，那么就进入临界区给临界区上锁
waiting[i]=TRUE;
key=TRUE;
while(waiting[i]&&key)
key=TestAndSet(&lock);
waiting[i]=FALSE;
//critical section
//假设有n个进程都想进入临界区，根据顺序指派下一个等待进程作为下一次进入临界区的进程
j=(i+1)%n;
while((j!=i)&&!waiting[j])
j=(j+1)%n;
if(j==i)
lock=FALSE;
else
waiting[j]=FALSE
//remainder section
}while(TRUE);
信号量(semaphore)
应用层面解决临界区问题：信号量
信号量S是个整数变量，除了初始化外，它只能通过两个标准原子操作：wait()和signal()来访问。即P和V。
wait()就是等待资源的过程，定义可表示为：
wait(S)
{
while(S<=0)
;//no-op
S--;
}
signal()就是释放资源的过程，定义可表示为：
signal(S)
{
S++;
}
在wait()和signal()操作中，对信号量整型值的修改必须不可分地执行。即当一个进程修改信号量值时，不能有其他进程同时修改同一信号量的值。另外，对于wait(S)，对于S的整数值测试(S≤0)和对其可能的修改(S–)，也必须不被中断地执行。
信号量的应用
计数信号量：用来访问具有多个实例的某种资源。
二进制信号量：值只能为0或1,有的系统，将二进制信号量成为互斥锁。
do
{
wait(mutex);
//critical section
signal(mutex);
//remainder section
}while(TRUE);
解决各种同步问题
先执行Pi的S1语句，然后再执行Pj的S2语句，可以通向一个信号量，初始化为0。
进程P1中插入语句：
S1;
signal(synch);
在进程P2中插入语句：
wait(synch);
S2;
信号量的缺点
信号量的主要缺点是要求忙等待（busy waiting）。即在进入代码段中连续地循环。忙等待浪费了CPU时钟，这种类型的信号量也称为自旋锁（spinlock），这是因为进程在其等待锁的时还在运行(自旋锁有其优点，进程在等待锁时不进行上下文切换，而上下文切换可能需要花费相当长的时间。因此如果锁占用的时间短，那么锁就有用了，自旋锁常用于多处理器系统中，这样一个线程在一个处理器自旋时，另一线程可在另一个处理器上在其临界区内执行).
解决方案
信号量定义为如下：
typedef struct
{
int value; //记录了这个信号量的值
struct process *list; //储存正在等待这个信号量的进程（PCB链表指针）
}semaphore;
每个信号量都有一个整型值和一个进程链表，当一个进程必须等待信号量时，就加入到进程链表上，操作signal()会从等待进程链表中取一个进程以唤醒。
wait()实现：
wait(semaphore *S)
{
S->value--;
if(S->value<0) //没有资源
{
add this process to S->list; //进入等待队列
block(); //堵塞
}
}
signal()实现：
signal(semaphore *S)
{
S->value++;
if(S->value<=0)
{ //上面++后，S仍然还<=0，说明资源供不应求，等待者还有很多，于是唤醒等待队列中的一个
remove a process P from S->list;
wakeup(P); //切换到就绪状态
}
}
操作block()挂起调用他的进程。
操作wakeup(P)重新启动阻塞进程Ｐ的执行。
在具有忙等的信号量经典定义下，信号量的值绝对不能为负数，但是本实现可能造成信号量为负值。如果信号量为负值，那么其绝对值就是等待该信号量的进程的个数。
等待进程的链表可以利用进程控制块PCB中的一个链接域来加以轻松实现。即每个信号量包括一个整型值和一个PCB链表的指针。
信号量的关键之处是它们原子的执行。必须确保没有两个进程能同时对一个信号量进行操作，在单处理器情况下，可以在执行wait()和signal()的时候简单的关闭中断，保证只有当前进程进行。
多处理器下，若禁止所有CPU的中断，则会严重影响性能，SMP系统必须提供其他加锁技术（如自旋锁），以确保wait()与signal()可原子地执行。
死锁和饥饿
两个或多个进程无限地等待一个事件，而该事件只能由这些等待进程之一来产生。这里的事件是signal()操作的执行。当出现这样的状态时，这些进程就称为死锁（deadlocked）
进程p1
wait(S);
wait(Q);
//……
signal(S);
signal(Q);
进程p2
wait(Q);
wait(S);
//......
signal(Q);
signal(S);
死锁(deadlock)
指的是两个或者两个以上的进程相互竞争系统资源，导致进程永久阻塞
饥饿(starvation)
指的是等待时间已经影响到进程运行，此时成为饥饿现象。如果等待时间过长，导致进程使命已经没有意义时，称之为“饿死”
经典同步问题
有限缓存问题
假设缓冲池有n个缓冲项，每个缓冲项能存在一个数据项。
信号量mutex提供了对缓冲池访问的互斥要求，并初始化为1。
信号量empty用来表示空缓冲项初始化为n
信号量full用来表示满缓冲项初始化为0
生产者：
do
{
…
//produce an item in next p
…
//顺序不能颠倒
wait(empty);
wait(mutex);
…
//add next p to buffer
…
signal(mutex);
signal(full);
}while(TRUE);
消费者：
do
{
wait(full);
wait(mutex);
…
//remove an item from buffer to next c
…
signal(mutex);
signal(empty);
…
//consume the item in next c
…
}while(TRUE);
读者-写者问题
只读数据库的进程称为读者；更新（读和写）数据库的称为写者
读者进程共享以下数据结构：
semaphore mutex, wrt;
int readcount;
信号量mutex和wrt初始化为1，readcount初始化为0，信号量wrt为读者和写者进程所共有
写者进程结构：
do
{
wait(wrt);
…;
//writing is performed
…;
signal(wrt);
}while(TRUE);
读者进程结构：
do
{
wait(mutex);
readcount++;
if(readcount==1)
wait(wrt);
signal(mutex);
…;
//reading is performed
…;
wait(mutex);
readcount--;
if(readcount==0)
signal(wrt);
signal(mutex);
}while(TRUE);
在以下情况下最为有用：
一是，当可以区分哪些进程只需要读共享数据，哪些进程只需要写共享数据；
二是，当读者进程数比写进程多时。
哲学家进餐问题
会发生死锁的解决方案
共享数据为：semaphore chopstick[5];其中所有chopstick的元素初始化为1。
do
{
wait(chopstick[i]);
wait(chopstick[(i+1)%5]);
…;
//eat
…;
signal(chopstick[i]);
signal(chopstick[(i+1)%5]);
…;
//think
…;
}while(TRUE);
多种可以解决死锁的方法：
①最多只允许4个哲学家同时坐在桌子上；
②只有两只筷子都可用时才允许一个哲学家拿起它们（他必须在临界区内拿起两只筷子）；
③使用非对称解决方法，即技术哲学家先拿起左边的筷子，接着拿起右边的筷子，而偶数哲学家先拿起右边的筷子，接着拿起左边的筷子。
