进程同步
前面我们提到了协作进程,协作进程就是会影响其他进程,即会共享逻辑地址空间,即共享内存系统,对于这种情况,很有可能会同时访问同一变量导致出错。还有一个是独立进程,是不会影响的进程。消息传递的协作进程不会导致进程同步问题。
所以我们这章讨论的是基于共享内存的协作进程。
竞争条件:多个进程并发访问同一数据切数据的结果与执行进程先后有关。
临界区:临界区只能允许一个进程执行。
进程分为进入区,临界区,退出区,剩余区。进入区需要有表示请求进入临界区的代码,退出区要有表示退出临界区的代码。
临界区问题:有空则进,无空则等,有限等待。
在操作系统内,执行内核代码也会遇到临界区问题。
在执行内核代码时,分为抢占内核和非抢占内核。
非抢占内核:在一个进程进入内核模式后,不允许另一个进程也进入。 因此不会导致竞争条件。
抢占内核因为允许在内核中执行的进程被抢占,所以会发生数据不一致。
对于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 的等待队列重启进程的选择方式。
通常用条件队列,经常的优先级如下设定:
进程事先说明资源分配的最大需求,管程优先分配给最短分配请求的进程。
管程的高级操作的正确使用也是要注意的。