操作系统之进程同步

进程同步
前面我们提到了协作进程，协作进程就是会影响其他进程，即会共享逻辑地址空间，即共享内存系统，对于这种情况，很有可能会同时访问同一变量导致出错。还有一个是独立进程，是不会影响的进程。消息传递的协作进程不会导致进程同步问题。

所以我们这章讨论的是基于共享内存的协作进程。

//生产者-消费者问题解决方案
//生产者
while(true)
{
    while(counter==BUFFER_SIZE);
    buffer[in]=nextProduced;
    in=(in+1)%BUFFER_SIZE;
    counter++;
}
//------------------------------
//消费者
while(true)
{
    while(counter==0);
    nextConsumed=buffer[out];
    out=(out+1)%BUFFER_SIZE;
    counter--;
}

竞争条件：多个进程并发访问同一数据切数据的结果与执行进程先后有关。
临界区：临界区只能允许一个进程执行。
进程分为进入区，临界区，退出区，剩余区。进入区需要有表示请求进入临界区的代码，退出区要有表示退出临界区的代码。
临界区问题：有空则进，无空则等，有限等待。

在操作系统内，执行内核代码也会遇到临界区问题。
在执行内核代码时，分为抢占内核和非抢占内核。
非抢占内核：在一个进程进入内核模式后，不允许另一个进程也进入。 因此不会导致竞争条件。

抢占内核因为允许在内核中执行的进程被抢占，所以会发生数据不一致。

对于SMP结构更难控制，因为进程在不同处理器上。

Peterson算法：用于处理临界区问题。 Peterson算法的宗旨是“谦让”，因为一开始都先把机会留给另一个人。
do
{
flag[i]=true;
turn=j;
while(flag[j]&&turn==j);
...
flag[i]=false;
}while(TRUE);

flag表示想要进入临界区，turn是能进入临界区。

前面讲的是通过软件进行同步，后面开始讲硬件同步。
对于单处理器，在修改共享变量时需要禁止中断出现，从而实现了非抢占内核。

对于多处理器，采用前面通知禁止中断则不可行，因为需要将禁止中断发送给全部的处理器，速度慢。因此需要一个机器指令，能够原子地执行。
原子地：不可中断。

书上直接讲TestAndSet的例子显得太突然，不好上手，所以查了下资料，逐步讲起。

do{

while(turn!=i);

临界区

turn=j;

剩余区

}while(true);

这个例子的问题是在退出区turn=j显得太突兀，因为不满足有空则进的原则。如果j不进，那就谁都进不了了。

下面一个例子是添加了bool变量。

do{

flag[i]=true;

while(flag[j]); //问题在于如果flag[j]没进去，也在等待，那么i就一直不能进，因此也没解决有空则等的条件。

临界区

flag[i]=false;

剩余区

}while(true);

bool TestAndSet(bool *target)
{
bool* r=*target;
*target=true;
return r;
}
do
{
while(TestAndSet(&lock));
...
lock=false;
}while(TRUE);
分析：开始时，lock为false，返回false，则开始进入临界区，因为表明没人加锁；而如果lock为true，则说明有人在临界区，则不能进入。

缺点：虽然能解决互斥和前进。但是没有解决有限等待。

void swap(bool*a,bool *b)
{
bool temp=*a;
*a=*b;
*b=temp;
}
do
{
key=TRUE;
while(KEY==true)
swap(&key,&lock);
...
lock=false;

}while(true);
分析：开始lock为false，key为true，一开始因为临界区没人，所以交换后key为false，则进入临界区。

其实以上两者思想有事一样的，如果一开始lock为false，则都会跳出循环。但是他们不能满足有限等待，因为多进程时，没有一个界定来表明什么时候能进入临界区。缺点和上面一样。

//以下实现了有限等待，因为会像循环队列一样一轮一轮看，如果waiting[j]==true且j!=i 即j在等待，则waiting[j]=false;如果j==i， 则lock=false;

-----------------------

do
{
waiting[i]=true;
key=TRUE;
while(waiting[i]&&key)
key=TestAndSet(&lock);
waiting[i]=false;
....
j=(i+1)%n;
while(j!=i&&!waiting[j])
j=(j+1)%n;
if(j==i)
lock=false;
else
waiting[j]=false;
}while(TRUE);

信号量（即资源，用整数大小来代表多少）可以用来同步，信号量规定为s，表示所拥有的资源的个数，有原子操作wait(S),signal(S)表示--和++。

信号量分为：计数信号量和二进制信号量。
当进程需要使用资源，则调用wait。
但是信号量有个缺点，就是忙等。忙等的意思是在一个进程进入临界区，其他进程必须要在while循环中不断循环，只有当一个进程出临界区时才能进入。而浪费CPU的时间，因此解决方案是当一个进程进入临界区，则可以用自旋锁spinlock，这样就可以让其他进程进入其他临界区，充分利用CPU时间。
wait函数当资源用完时，就把此进程放入等待队列，利用CPU调度调用另一个进程。

为了确定两个进程的访问特定数据的顺序
p1
signal(S);
-------------------

p2

wait(S);
-------------------

且将S初始化为0，则一定要p1先执行。

信号量的缺点是忙等待（但可能也是优点，因为上下文切换可能消耗更多的资源）因为wait操作造成的，这种称为自旋锁，因为一直在自旋。。。
自旋锁的方案是当A进程调用wait时，如果资源已用完，则阻塞进入该信号量的等待队列，如果什么时候signal又有资源了，则wakeup把他唤醒，进入内存中的就绪队列。

struct semaphore

{

int value;

struct Process *list; //等待队列，signal会从等待队列中取出一个进程唤醒

};

wait(semaphore *S)

{

s->value--;

if(s->value<0){

block(); //进入等待队列，并重新调入

}

}

signal(semaphore *S)

{

S->value++;

if(s->value>0) {

wakeup(p); //从等待队列中唤醒一个进程

}

}

多处理器可以使用自旋锁来实现同步，即一个进程在一个处理器上运行，一个进程在另一个处理器自旋。

执行PV操作的要求只有一个！就是wait和signal必须是原子的。

在单和多处理器（SMP）都需要禁止中断来解决原子。

死锁：多个进程对于信号量可能产生死锁，死锁就是A进程为了wait（S）信号量必须等待B进程signal（S），而B进程为了wait（T）必须等待A进程signal（T），从而两方都处于死锁状态。

而信号量的等待队列的LIFO实现方法可能会使得无限阻塞或饥饿。即一直不能执行。

经典同步问题：

1.有限缓冲问题：即生产者消费者问题

//empty是空的buffer的个数，full是满的buffer的个数 mutex是互斥锁

//生产者
do
{
//produce
wait(empty);
wait(mutex);

signal(mutex);
signal(full);
}while(true);
//消费者
do
{
wait(full);
wait(mutex);

signal(mutex);
signal(empty);
}while(true);
2.读者写者问题

读者写者问题的要求是可以有多个读者，一个写者。
读者写者有第一读者写者问题和第二读者写者问题。
第一读者写者问题：读者不需要保持等待除非一个写者已经进入临界区。
第二读者写者问题：一旦写者开始等待，那么写者会尽可能快的执行写操作，读操作不能占先。
//已知mutex，wrt都是二进制信号量，初始化为1，readcount是读者的个数
//写者
do
{
wait(wrt);
临界区
signal(wrt);
}while(true);

//读者
do
{
wait(mutex);
readcount++;
if(readcount==1)
wait(wrt);
signal(mutex);

wait(mutex);
readcount--;
if(readcount==0)
signal(wrt);
signal(mutex);
}while(true);

当然比如java就提供了读写锁，可以方便进行进程同步，也可以解决读者写者问题，但是开销较大。
3.哲学家进餐问题

semaphore chopstick[5];
do
{
wait(chopstick[i]);
wait(chopstick[(i+1)%5]);
//eat
signal(chopstick[i]);
signal(chopstick[(i+1)%5]);
//think
}while(true);
这种方法会导致死锁，因为当哲学家都执行第一条语句时，都不能执行下一条语句。舍弃。

解决方法：
1.最多允许4个哲学家同时坐桌子上。。
2.只有两只筷子都能拿起时才拿。
3.奇数哲学家先拿左边筷子，接着拿右边筷子，而偶数哲学家相反。

信号量还是不够安全，因为可能会写错。所以引入管程（monitor）。

管程默认就是只能有一个进程在管程内活动，所以不用人为编写同步代码。

定义condition类型变量可定义额外的同步机制。对于条件变量只有wait和signal操作。

wait只意味着进程block，signal只意味着重新启动进程。condition变量类似于信号量，有一个等待队列。用于挂起进程。

基于管程的哲学家进餐问题实现：

monitor dp
{
enum{THINKING,HUNGRY,EATING}state[5];
condition self[5];

void pickup(int i)
{
state[i]=HUNGRY;
test(i);
if(state[i]!=EATING)
self.wait();
}

void putdown(int i)
{
state[i]=THINKING;
test((i+4)%5);
test((i+1)%5);
}

void test(int i)
{
if(state[(i+4)%5]!=EATING)&&state[i]==HUNGRY&&state[(i+1)%5]!=EATING)
{
state[i]==EATING;
self[i].signal();
}
}

initialization_code() //初始化代码，必有
{
for(int i=0;i<5;i++)
state[i]=THINKING;
}
}

//记住：管程的操作默认是互斥的。

下面讨论的问题是condition variable 的等待队列重启进程的选择方式。

通常用条件队列，经常的优先级如下设定：

进程事先说明资源分配的最大需求，管程优先分配给最短分配请求的进程。

管程的高级操作的正确使用也是要注意的。