OS复习：同步与互斥

[TOC]

同步与互斥概念

在多道程序下，继承是并发执行，不同进程之间存在着不的相互制约关系；为协调进程之间的相互制约关系，引入进程同步概念，当我们计算1+2*3，加法进程一定是在乘法后的，但是OS具有异步性。

临界资源

我们将一次只能给一个进程服务的资源称为临界资源

分为四部分：进入区、临界区、退出区、剩余区

1
2
3
4
5
6
7
while(true){
      entry section //进入区：进入临界区资源，在进入区要检查可否进入临界区，若能进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区
      critical section //临界区： 进程访问临界资源的那段代码，又称临界段
      esxit section  //退出区： 将正在访问临界区的标志清除
      remainder section //剩余区

}

同步

同步也称直接制约关系，指为完成某种人物而建立的两个或多个进程，这些进程因为要协调它们的运行词语而等待、传递信息所产生的制约关系。同步关系源于进程之间的相互合作。

互斥

互斥是间接制约关系。当一个进程进入临界区使用临界资源，另一个进程必须等待；

在一台打印机系统中，两个进程A和B，当A需要打印时，系统已将打印机分配给进程B，则进程A必须阻塞。一旦进程B将打印机释放，系统便将A唤醒，将其由阻塞态变为就绪态

临界区互斥的准则

为禁止两个进程同时进入临界区，同步机制应该遵循以下原则：

  • 空闲让进：临界区空闲，允许一个请求进入临界区
  • 忙则等待：已有进程进入临界区，其他试图进入的进程必须等待
  • 有限等待： 对请求访问的进程，应保证能在有限时间内进入临界区，防止进程无限等待
  • 让权等待：当进程不能进入临界区时，应立即释放处理器，防止进程忙等待

实现临界区互斥的基本方法

软件实现方法

在进入区设置一些标志来标明是否由进程在临界区，若已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后再退出区修改标志

单标志法

1
2
3
4
5
6
7
8
9
10
11
12
进程P0；
While(turn!=0);
critical section;
turn=1;
remainder section;


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

这样的问题是：当P0进入临界区并离开了，此时turn=1；但是P1不打算进入临界区了，那么之后P0就一直无法拿到临界资源。也就是说，两个进程必须交替进入临界区，很可能造成违背空闲让进的原则

双标志先检查法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//我们用flag[2]数组，标记各个进程想进入临界区的意愿
进程P0
while(flag[1]);   1
flag[0]=true;    2 // p0想进入临界区
critical section;
flag[0]=false;
remainder section

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

优点：可以不交替进入了

缺点：当执行顺序是1324的时候，在检查对方标识和设置自己的标识前可能发生进程转换，违背了忙则等待

双标志后检查法

1
2
3
4
5
6
7
8
9
10
11
12
13
//进程P0
flag[0]=true;   1
while(flag[1]);   2
critical section;
flag[0]=false;
remainder section

//进程P1
flag[1]=true;    3
while(flag[0]);   4
critical section;
flag[1]=false;
remainder section;

这里我们先设置自己的标志后检查，但是1342的顺序会导致双方都竞争进入临界区，违背了空闲让进的原则，也会导致两个进程产生饥饿

Peterson算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//进程P0
flag[0]=true;   
turn=1
while(flag[1]&&turn==1);   
critical section;
flag[0]=false;
remainder section

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

我们用flag解决互斥访问，用turn解决饥饿问题；

当两个进程的flag都为true，此时turn会决定临界区分配给哪个进程：turn值为1时，P1拿到临界资源；当P1退出临界资源时，将flag[1]设置为flase，允许P0进入临界区；如果P1不想进入临界区了，flag[1]是false，P0也能拿到临界资源

可见Peterson满足了空闲让进、忙则等待、有限等待，但是没有满足让权等待

因为在while循环中使用了忙等待(busy waiting)机制。当进程i发现无法进入临界区时，它并不会主动释放CPU，而是不断循环检查条件。CPU时间被浪费在无效的循环检查上

硬件方法

中断屏蔽方法

1
2
3
4
5
...
关中断;
临界区;
开中断;
...

注意：关中断是关闭中断

之前的软件算法会违背了一些原则，是因为在程序运行时可能会发生进程切换，而进程切换会发生中断

那我们只需要在进程拿临界资源时关中断就好了，这样不会被进程切换扰乱

当然有些缺点：

  • 限制CPU交替执行程序能力，系统效率降低
  • 对于内核，若将关中断权限给用户是不安全的，若一个进程关中断后不再开中断，系统可能会终止
  • 不适用多CPU系统

TestAndSet指令

1
2
3
4
5
6
bool TestAndSet(boolean *lock){
    bool old;
    old=*lock;  //old存放lock旧值
    *lock=true;  //无论之前是否加锁，lock都为true
    return old;  //返回Lock旧值
}

以上是TS指令，它是原子操作。功能是读出标志后将该标志设置为真；

于是，我们可以用TS做互斥

1
2
3
4
while TestAndSet(&lock);
进程的临界区代码;
lock=false;
进程的其他代码;

我们用TS指令管理临界区，为每个临界资源设置一个共享值lock，表欧式该资源两种状态,ture上锁，false为加锁

相比软件实现，TS将加锁和检查用硬件方式变成了原子操作，不会被打断；相比关中断,lock是共享的，使用多CPU

缺点： 暂时无法进入临界区的进程会占用CPU循环，跟Peterson算法一样，违背让权等待

Swap指令

Swap顾名思义，交换两个字节的内容：

1
2
3
4
5
Swap (bool *a, bool *b){
    bool temp=*a;
    *a=*b;
    *b=temp;
}

Swap不能被中断

1
2
3
4
5
6
7
8
9
//lock是共享的
bool key=true;//key是局部的，用于和lock交互信息
while(key!=false){
    Swap(&lcok,&key);
}//key为false时，说明临界区没有进程占用了
进程的临界区代码;
lock=false;
进程其他代码

硬件实现互斥的优点：

  • 简单，支持多CPU；
  • 支持系统有多个临界区，只需为每个临界区设置一个布尔变量

缺点：

  • 进入临界区进程会占用CPU执行While循环，违背“让权等待”
  • 从等待进程随机挑一个进入临界区，可能会造成某些进程饥饿

互斥锁(mutex lock)

1
2
3
4
5
6
7
acquire(){   //获得锁
    while(!available); //忙则等待
    available=false;  //获得锁
}
release(){          //释放锁定义
    available=true;  /释放锁
}

进程进入临界区调acquire获得锁，退出临界区调release，释放锁；当进程获取不可用的锁，会被阻塞

acquire和release都是原子操作，通常用硬件实现

上面的mutex lock也称自旋锁，缺点是忙等待；当多个进程共享一个CPU时，连续循环浪费了CPU周期，因此Mutex lock多用于多CPU系统，一个线程可以在一个处理器上旋转，而不影响其他线程的执行。自旋锁优点是，进程在等待锁期间，没有上下文切换，若上锁时间短，则等待代价不高

PV 信号量

两个标准原语wait()和signal()访问，简写为P(),V()

整型信号量

1
2
3
4
5
6
7
wait(S){
 while(S<=0);
    S=S-1;
}
signal(S){
    S=S+1;
}

在整型信号量机制中的wait操作，只要信号量S<=0，就会不断循环测试，没有让权等待

记录型信号量

记录型就不存在忙等；采用记录型的数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//记录型信号量
typedef struct{
    int value;
    struct process *L;
} semaphore;

//对信号量S一次P操作，表示进程请求一个资源，因此value--；系统可供分配的资源数减少，当value小于0，表示资源分配完毕，调用BLOCK进行自我阻塞，主动放弃CPU，并插入该类资源的等待队列，遵循了让权等待
void wait(semaphore S){
    S.value--;
    if(S.value<0){
        add this process to S.L;
        block(S.L);
    }
}
//做一次V操作，表示进程释放了一资源，；加1后，value任然小于等于0，说明有进程在等待这个资源；要调用wakeup将S.L第一个进程唤醒（到就绪态）
void Signal(semaphore S){
    S.value++;
    if(S.value<=0){
        remove this process P from S.L;
        wakeup(P);
    }
}

信号量实现进程互斥

为了多个进程能互斥访问某个临界资源，对临界资源设置一个互斥信号量S

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
semaphore S=1;
P1(){
    ...
    P(S);
    进程P1临界区；
    V(S);
    ...    
}
P2(){
    ...
    P(S);
    进程P2的临界区；
    V(S);
    ...
}

//S取值范围(-1,0,1)

  • 对不同临界资源要设置不同的互斥信号量
  • PV必须成对出现，少P无法保证互斥访问临界资源，少V使得临界资源无法被释放，使等待该资源的进程无法被唤醒
  • 有多少资源就将信号量设置为多少

利用信号量实现同步

我们假设情形：Y一定在X后执行

1
2
3
4
5
6
7
8
9
10
11
12
13
semaphore S=0;
P1(){
    X;
    V(S); //告诉进程P2，语句x已经完成
    ... //S=1
}

P2(){
    ...
    P(S);//检查x是否允许完成，操作完P不执行block
    Y; 
    ...
}

总而言之，在某个行为会提供某种资源，则这个行为后V；当某个行为要用这个资源，执行P；在互斥问题中，PV操作要夹紧临界资源的行为，中间不能有其他冗余代码

信号量实现前驱关系

信号量也可以用来描述语句之间的前驱关系；

我们可以把每队前驱关系都是一个同步问题，因此为每对前驱关系设置一个同步信号量，初始值均为0；

具体过程不赘述，非常好理解

用信号量实现同步和互斥是常考点，分析步骤如下：

  • 关系分析：找出进程数，分析它们的同步和互斥关系
  • 整理思路：根据进程流程，确定大致PV操作
  • 设置信号量

经典同步问题

生产者-消费者问题

producers 和 consumers共享一个初始为空、大小为n的缓冲区。操作逻辑与管道相同，只有当缓冲区未满，producer才能将消息放入缓冲；只有当缓冲区未空，consumer才能从缓冲区读消息；除此之外，都要被阻塞；由于缓冲区是临界资源，必须互斥访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
semaphore mutex=1; //临界区互斥信号量
semaphore empty=n; //空闲缓冲区
semaphore full=0; //缓冲区初始化为空
producer(){
    while(1){
        produce an item in nextp;
        P(empty); //获取缓冲区单元
        P(mutex); //进入临界区
        add nextp to buffer;
        V(mutex); //离开临界区，释放互斥信号
        V(full); //满缓冲区+1
    }
}

consumer(){
    while(1){
        P(full); //获取缓冲区单元
        P(mutex); //进入临界区
        remove an item from buffer;
        V(mutex); //离开临界区，释放互斥信号
        V(empty); //空闲缓冲区+1
        consume the item;
    }
}

注意对empty和full的P操作一定是在P(mutex)之前的

如果先P（mutex）会发生死锁：

当procuser 将buffer放满，此时empty=0; consumer未取走item，下一次调producer先执行了p(mutex), mutex被producer锁了,但是遇到p(empty)阻塞了；然而consumer无法V(empty),因为mutex被Producer锁了，产生死锁现象；同理，当consumer将buffer读完，full=0;producer生产item,还是调consumer ，那么mutex被consumer锁了,full=0 ，consumer自身阻塞；producer因为mutex被锁了无法进入临界区，也是死锁

读者-写者问题

读者和写着两组并发进程，共享一个文件；要求

  • 允许多个读者同时对文件执行读操作
  • 只允许一个写者往文件写信息；
  • 任意一个写者在完成写操作前不允许其他读者或写者工作
  • writer执行写操作前，应让已有reader和writer全部退出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int count=0; //记录当前读者数量
semaphore mutex=1; //用于保护更新count变量的互斥
semaphore rw=1;  //保证读者和写者互斥访问文件
writer(){
    while(1){
        P(rw);
        writing;
        V(rw);
    }
}
reader(){
    while(1){
        P(mutex);
        if(count==0){ //第一个读者来，要阻止writer
            P(rw);
        }
        count++; //reader 数量+1
        V(mutex); //已经更新完count了，释放mutex
        reading;
        P(mutex); //读完了，这个读者要退出了，所以我们要更新count,先上锁
        count--;
        if(count==0){
            V(rw);
        }
        V(mutex);
    }
}

这样的话，reader优先，很可能造成writer饥饿

如果我们写完writer优先，可以增加两对PV操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int count=0; //记录当前读者数量
semaphore mutex=1; //用于保护更新count变量的互斥
semaphore rw=1;  //保证读者和写者互斥访问文件
semaphore W=1; //实现写进程优先
writer(){
    while(1){
        P(W);
        P(rw);
        writing;
        V(rw);
        V(w);
    }
}
reader(){
    while(1){
        P(w);
        P(mutex);
        if(count==0){ //第一个读者来，要阻止writer
            P(rw);
        }
        count++; //reader 数量+1
        V(mutex); //已经更新完count了，释放mutex
        V(w); //恢复对共享文件的访问，这里如果writer进来了，前一个读进程结束了,writer执行，而不是这个reader；实现writer优先
        reading;
        P(mutex); //读完了，这个读者要退出了，所以我们要更新count,先上锁
        count--;
        if(count==0){
            V(rw);
        }
        V(mutex);
    }
}

哲学家进餐问题

懒，图不放了

五个人围着圆桌坐，每两个人中间都有一根筷子。只有他同时拿到了两根筷子才能进餐；

如果让他们试图同时拿两根筷子，所有人都拿左手边时，发现右手的筷子被强了，死锁

so

我们规定：当一名哲学家左右手的筷子都可用时，才能抓筷子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
semaphore chopstick[5]={};
semaphore mutex=1;
Pi(){
    do{
        P(mutex);
        P(chopstick[i]);
        P(chopsticl[(i+1)%5]);
        V(mutex);
        eat;
        V(chopstick[i]);
        v(chopsticl[(i+1)%5]);
        think;
    }while(1)
}

我们关键时加了互斥锁mutex，告诉你，我要拿筷子了，其他人不许动！

这样能避免死锁

管程

管程能保证进程互斥，无需用户自己实现互斥.

管程(Monitor)是一种用于多线程互斥访问共享资源的程序结构。管程由四部分组成

  • 管程的名称
  • 局部于管程内部的共享数据结构说明；
  • 对该数据结构进行操作的一组过程
  • 对局部与管程内部的共享数据设置初始值的语句
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
monitor Demo{ //定义名称为Demo的管程
    //定义共享数据结构，对应系统中某种共享资源
    共享数据结构S；
     // 对共享数据结构初始化的语句
     init_code(){
        S=5;
        ...
    }
    take_away(){
        对共享数据结构x的一系列处理
        S--
    }
    give_back(){
        对共享数据结构x的一系列处理；
        S++;
        ...
    }
    
}

管程很像一个类

  • 管程将共享资源的操作封装，共享数据结构只能被管程内的过程访问。一个进程只有通过调用管程内的过程，才能进入管程访问共享资源。对于上例，外部进程只能通过take_away()过程来申请一个资源
  • 每次只允许一个进程进入管程，从而实现进程互斥。若多个进程同时调用take_away()，give_back()，则只有某个进程运行完它调用的过程后，下一个进程才能开始它调用的过程

当一个进程进入管程被阻塞，在此期间，如果该进程不释放管程，那么其他进程无法进入管程。为此，将阻塞原因定义为条件变量；每个条件变量保存一个等待队列，用于记录因该条件变量而阻塞的所有进程。对条件变量只能两种操作，wait(),signal()

x是条件变量

x.wait： 当x对应的条件不满足时，正在调用管程的进程调用x.wait将自己插入x条件等大地队列，并释放管程

x.signal: 当x对应条件发生变化，调用x.signal，唤醒一个因x阻塞的进程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
monitor Demo{
    共享数据结构 S;
    condition x;
    init_code(){
        ...
    }
    take_away(){
        if(S<=0) x.wait(); //资源不够，在条件变量x上阻塞等待
        资源足够，分配资源
    }
    give_back(){
        归还资源
        if(有进程在等待) x.signal() //唤醒一个阻塞进程
    }
}

条件变量 compare 信号量

  • 条件变量的wait和signal类似信号量的PV，实现进程的阻塞/唤醒
  • 条件变量没有值，仅仅实现排队等待功能；而信号量有值，反映剩余资源数，在管程中，剩余资源数由共享数据结构来记录