何为同步?

两个或两个以上随时间变化的量在变化过程中保持一定的相对关系(并发多线程,把线程想象为我们自己)

并发互斥同步
两个线程各自完成某件事就好比上厕所排队,一个接一个在未来某个约定的时刻,两个线程的执行点互相可知,通常是先到的线程先等待

生产者-消费者问题
系统中有生产者、消费者两种线程,多个线程有一个共享的队列(缓冲区)

生产者(线程)生产资源(一个对象),生产时间不确定

  • 缓冲区里没有空余的空间存放生产的对象时等待
    消费者(线程)消费资源(取走一个对象),消费时间不确定
  • 缓冲区里没有对象可以消费时等待
void consumer_thread(){
    while(1){
        object_t *obj=dequeue(); //spin: queue empty
        if(obj) consume(obj);
    }
}
void producer_thread(){
    while(1){
        object_t *obj=product(); 
        while(enqueue(obj)!=SUCC); //spin: queue full
    }
}

简化一下,如果有两种线程,第一种不断循环打印(,第二种不断打印)

void type1_thread(){
    while(1) printf("("); //enqueue 
}
void type2_thread(){
    while(1) printf(")"); //dequeue
}

具体实现

为了实现临界资源互斥访问,可以在逻辑上讲一个进程对临界资源的访问过程分为四个部分

  • 进入区:对于进程A,想要访问临界资源,首先会在进入区检查是否可以进入,没有其他进程占用临界资源检查通过,同时设一个flag标志自己正在占用;
  • 临界区:实际访问临界资源的代码;
  • 退出区:退出前解除flag;
  • 剩余区:其他处理;
do{
   extry section;   //进入区
   critical section;  //临界区
   exit section;  //退出区
   remainder section;  //剩余区
}while(True)
  • 空闲让进;
  • 忙则等待;
  • 有限等待; 不能让进程一直等着,必须在有限的时间内进入临界区
  • 让权等待; 当进程不能进入自己的临界区时,应当立即释放处理机,防止进程陷入“忙等”状态

如何让多进程之间的同步变得合理有序?
也就是如何实现互斥访问临界资源?

软件层面

1.单标志法

int turn = 0;

P0 进程:                        P1 进程:
while (turn != 0);              while (turn != 1);
critical section;               critical section;
turn = 1;                       turn = 0;
remainder section;              remainder section;

设置一个标志,初始为0,即指向0号进程,对于进程p0,如果turn≠0,则一直空转;等于0,则进入临界区...对于进程p1也是这样。设想有两种可能,p0先上处理机,那么此时不满足while的条件,进入自己的临界区;另一种是p1先上处理机,由于满足了while的条件,陷入了死循环,一直无法进入临界区,直到消耗完了自己的时间片,轮到p0执行,p0由于不满足循环的条件,所以顺利进入临界区,在这个过程中,即使由于p0消耗完了时间片而导致处理机使用权交给了p1,p1也不会实际进入临界区,而是不断循环--这确保了在整个过程中,即使进程不断来回切换,始终都只有p0在使用临界资源,做到了“互斥访问资源”。

需要注意一点是,p0完成之后让权(turn)转交给p1,p1完后也得转交给p0,所以整个过程只能是p0、p1交替执行,也就是说p0运行完后,想要再次运行,就不得不等待p1的完成

另一个问题是p0如果一直不访问临界区,那么就算此时临界区空闲,p1想访问临界区却无法访问,造成了“空闲不让进”,这违背了“空闲让进”原则。

2.双标志先检查法
为了解耦,我们可以设置两个flag,单标志法中,flag只能指向其它进程,为什么不能设置两flag,只针对自己,是否可以执行,完后重置;双标志法不只有一个flag来指示哪个进程可以进入临界区,而是为每个进程都设置一个可以起到开关作用的flag

bool flag[2];
flag[0] = false;
flag[1] = false;

P0 进程:                        P1 进程:
while (flag[1]);                while (flag[0]);
flag[0] = true;                 flag[1] = true;
critical section;               critical section;
flag[0] = false;                flag[1] = false;
remainder section;              remainder section;

有一个问题,由于检查和上锁都不是原子操作,有可能被打断,比如A进程正在执行,在检查完之后,上锁之前,进程跳转到B进程,那么B进程就会在A进程上锁之前跳过了本该陷入的死循环,AB进程同时顺利进入临界区,这与“忙则等待”相违背

3.双标志后检查法
我们如果嫌检查的太慢,不妨先上锁

bool flag[2];
flag[0] = false;
flag[1] = false;

P0 进程:                        P1 进程:
flag[0] = true;                 flag[1] = true;
while (flag[1]);                while (flag[0]);
critical section;               critical section;
flag[0] = false;                flag[1] = false;
remainder section;              remainder section;

这样如果进程p0想执行,那么就可以先上锁。可是,上锁和检查之间有间隙,如果此时,进程p1也来了,那么它也会上锁;这样,p0、p1谁也进不了临界区,有违“空闲让进”“有限等待”原则

4.Peterson
结合了单标志法和双标志后检查法,为了解决双标志后检查法的“忙等”,在抢先上完锁之后又将turn置为对方线程,表示自己虽然想要进入临界区,但不介意把这个机会让给对方;并且while的限制条件增加,turn也是共用的,所以保证了最后只有一方的while满足条件。既做到了互斥访问资源,也避免了双方都访问不到资源。

bool flag[2]; 
flag[0]=false;
flag[1]=false;
int turn = 0;

P0 进程:                        P1 进程:
flag[0] = true;                 flag[1] = true;
turn = 1;                       turn = 0;
while (flag[1] && turn == 1);   while (flag[0] && turn == 0);
critical section;               critical section;
flag[0] = false;                flag[1] = false;
remainder section;              remainder section;

p0首先想要进入临界区,它的flag置为true,同时将turn置为1,表示不介意进程p1也来访问临界资源,如果
flag[1]=true,即p1也想访问临界资源,并且p0允许p1也来访问,turn=1,进入死循环,于是等到时间片结束后,p0谦让地释放权限,跳出了死循环,p1进入临界区。

可是,有一个问题从问题一开始到现在一直存在--让权等待;始终都存在空等的现象

硬件层面

1.中断屏蔽
在双标志法中,有可能出现两个进程同时进入临界区,这时中断屏蔽就可以避免这种情况,它和原语的原理很像,一样是通过“开/关中断指令”来实现原子操作,就是进程在进入临界区之前先执行关中断指令“上锁”,保证了整个执行过程不会被中断,自然不会发生进程的切换、两个进程同时访问临界资源的情况;在访问完临界资源之后,通过开中断指令“解锁”,这样其它进程才有机会访问临界区。但它也有弊端,不适用于多处理机,涉及到开/关终端这两个特权指令,只适用于内核进程,不适于用户进程。

2.TestandSetLock指令
这条指令解决了上锁和检查这两个非原子操作之间间隙的问题,让它们变成了原子操作,这样又做到像中断屏蔽指令那样,一旦进入临界区,执行过程无法被中断。

bool TestAndSet (bool *lock){
    bool old;
    old = *lock;
    *lock = true;
    return old;
}
P0:                                        P1:
while (TestAndSet(&lock));                 while (TestAndSet(&lock));
critical section;                          critical section;
lock = false;                              lock = false;
remainder section;                         remainder section;

lock为全局变量,一开始没上锁为false,如果p0想访问临界区,设置old变量来存放*lock,再将lock的值置为true,上锁!返回old,检查之后退出循环进入临界区,一气呵成。但如果old不是false,而是true,还是会陷入死循环,无法进入临界区,造成“忙等”。

3.swap指令

bool swap(bool *lock,bool *old){
   bool temp;
   temp = *lock;
   lock = *old;
   old = temp;
}

P0:
bool old =  true;                           bool old =  true;
while(old == true)                          while(old == true) 
  swap(&lock,&old);                            swap(&lock,&old);
critical section;                           critical section;
lock=false;                                 lock=false;
remainder section;                          remainder section;

信号量!