Fork me on GitHub

经典进程同步问题

发表于 | 分类于
字数统计 2,017 | 阅读时长 8

前言

经典进程同步问题：生产者-消费者问题、哲学家进餐问题、读者-写者问题，通过信号量来实现进程之间的同步。

生产者-消费者问题

1.利用记录型信号量解决生产者-消费者问题

假定在生产者和消费者之间的公用缓冲池中具有n个缓冲区，这时可利用互斥信号mutex实现诸进程对缓冲池的互斥使用；利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。

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 in = 0,out = 0;
item buffer[n];
semaphore mutex = 1,empty = n,full=0;
void producer{
    do{
        producer an item nextp;
        ...
        wait(empty);
        wait(mutex);
        buffer[in] = nextp;
        in = (in+1)%n;
        signal(mutex);
        signal(full);
    }while(true);
}
void consumer(){
    do{
        wait(full);
        wait(mutex);
        nextc = buffer[out];
        out = (out+1)%n;
        signal(mutex);
        signal(empty);
        consumer the item in nextc;
        ...
    }while(true);
}
void main(){
    cobegin
        producer(); consumer();
    coend
}

2.利用And信号量解决生产者-消费者问题

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
int in = 0,out = 0;
item buffer[n];
semaphore mutex = 1,empty = n,full=0;
void producer{
    do{
        producer an item nextp;
        ...
        Swait(empty,mutex);
        buffer[in] = nextp;
        in = (in+1)%n;
        Ssignal(mutex,full);
    }while(true);
}
void consumer(){
    do{
        Swait(full,mutex);
        nextc = buffer[out];
        out = (out+1)%n;
        Ssignal(mutex,empty);
        consumer the item in nextc;
        ...
    }while(true);
}
void main(){
    cobegin
        producer(); consumer();
    coend
}

哲学家进餐问题

五个哲学家共用一张圆桌，分别坐在周围的五个椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替的进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐完毕，放下筷子继续思考。

1.利用记录型信号量解决哲学家进餐问题

经分析，放在桌子上的筷子时临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。其描述如下：

1
semaphore chopstick[5] = {1,1,1,1,1};

所有信号量均被初始化为1，第i为哲学家的活动可描述为：

1
2
3
4
5
6
7
8
9
10
11
12
do{
    wait(chopstick[i]);
    wait(chopstick[(i+1)%5]);
    ...
    //eat
    ...
    signal(chopstick[i]);
    signal(chopstick[(i+1)%5]);
    ...
    //think
    ...
}while(true);

假如五位哲学家同时各自拿起左边的筷子时，就会使五个信号量chopstick为0，当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限期地等待。对于这种死锁问题，可采取一下几种解决方法。

首先给出两个断言：

（1）系统中有N个并发进程。若规定每个进程需要申请2个某类资源，则当系统提供N+1个同类资源时，无论采用何种方式申请资源， 一定不会发生死锁。分析：N+1个资源被N 个进程竞争， 由抽屉原理可知， 则至少存在一个进程获2个以上的同类资源。这就是前面提到的哲学家就餐问题中5个哲学家提供6支筷子时一定不会发生死锁的原因。

（2）系统中有N个并发进程。若规定每个进程需要申请R个某类资源，则当系统提供K＝N*（R-1）+1个同类资源时，无论采用何种方式申请使用，一定不会发生死锁。分析：在最坏的情况下，每个进程都申请到R-1个同类资源， 此时它们均阻塞。 试想若系统再追加一个同类资源， 则 N 个进程中必有一个进程获得R个资源，死锁解除。

(1)破坏请求保持条件

利用原子思想完成。即只有拿起两支筷子的哲学家才可以进餐，否则，一支筷子也不拿。

解法一：利用AND机制实现第i位哲学家的活动描述为：

1
2
3
4
5
6
7
8
philosopher (int i){
    while(true){
        think;
        swait(chopstick[(i+1)]%5，chopstick[i])；
        eat;
        Ssignal(chopstick[i]，chopstick[(i+1)%5]);
    }
}

解法二：利用记录型信号量机制实现在初始化中增加一个信号量定义：semaphore mutex=1：
该方法将拿两只筷子的过程作为临界资源，一次只允许一个哲学家进入。

第I位哲学家的活动描述：

1
2
3
4
5
6
7
8
9
10
11
12
philosopher (int I){
    while(true){
        思考;
        wait(mutex)；
        wait(stiCk[I]);
        wait(Stick[(I+1)%5]);
        signal(mutex)；
        进餐；
        signal(stick[I]);
        Signal(Stick[(I+1)%5])；
　　}
}

(2)破坏环路等待条件

解法一：奇数号哲学家先拿他左边的筷子，偶数号哲学家先拿他右边的筷子。这样破坏了同方向环路，一个哲学家拿到一只筷子后，就阻止了他邻座的一个哲学家吃饭。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。算法描述如下：

1)第i个哲学家的活动：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
philosopher (int I){
    while(true){
        思考;
        If I%2==1 then
            wait(Stick[I]);
            wait(stick[(I+1)%5]);
            进餐;
            signal(stick[I])；
            signal(stick[(I+1)%5]);
        else
            wait(stick[(I+1)%5])；
            wait(stick[I]);
            进餐；
            signal(stick[(I+1)%5])；
            signal(stick[I]);
    }
}

解法二：至多允许四位哲学家进餐，将最后一个哲学家停止申请资源，断开环路。最终能保证有一位哲学家能进餐，用完释放两只筷子，从而使更多的哲学家能够进餐。增加一个信号量定义semaphore count=4：算法描述第1个哲学家的活动：

1
2
3
4
5
6
7
8
9
10
11
12
philosopher (int I){
    while(true)
        思考；
        wait(count)；
        wait(chopstiok[I])；
        wait(chopstick[I+1]%5)；
        进餐;
        signal(chopstick[I])；
        signal(chopstick[I+1]%5)
        signal(count);
    }
}

读者-写者问题

允许多个进程同时读一个共享对象，但不允许一个write进程和其他reader进程或writer进程同时访问共享对象。所谓读者-写者问题是指：保证一个writer进程必须与其他进程互斥地访问共享对象的同步问题。

1.记录型信号量解决读者-写者问题

为实现reader和writer之间的互斥而设置一个互斥信号量wmutex。同时，增加一个count计数器，用来记录reader进程的个数，reader进程执行时，并且count==0时，此时wait(wmutex)，禁止写进程去写，然后++count；reader进程执行完毕后，–count，如果count ==0时，此时表示无reader进程，则signal(wmutex)，允许writer去写。同时由于reader进程互斥的共享count，所以我们设置一个rmutex来互斥访问count。

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
seamphore rmutex=1,wmutex=1;
int count=0;
void reader(){
    do{
        wait(rmutex);
        if(count==0) wait(wmutex)
        ++count;
        signal(rmutex);
        ...
        reader
        ...
        wait(rmutex);
        --count;
        if(count==0) signal(wmutex);
        signal(rmutex);
    }while(true);
}
void write(){
    do{
        wait(wmutex);
        ...
        writer
        ...
        signal(wmutex);
    }while(true);
}
void main(){
    cobegin
        reader(); writer();
    coend
}

2.利用信号量集机制解决读者-写者问题

Swait((S,1,0)：是一种很特殊且很有用的信号量操作。当S>=1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个开关。

这里我们增加一个限制，即最多允许RN个读者同时读。为此我们引入一个信号量L，并赋予其初值为RN，通过执行Swait(L,1,1)来控制读者的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int RN;   //最多允许RN个读者同时读
semaphore L = RN,mx = 1;
void reader(){
    do{
        Swait(L,1,1);   //L个资源（读进程），每次分配1个，当L<1时，无法分配资源，阻塞
        SWait(mx,1,0);  //mx>=1,允许多个读进程进程进入
        ...
        read
        ...
        Ssignal(L,1);     //释放L资源（读者数被释放+1）
    }while(true);
}
void writer(){
    do{
        Swait(mx,1,1;L,RN,0);  //表示仅当既无writer进程在写操作（mx=1)、又无reader进程在读操作（L=RN)时，writer进程才能进入临界区
        ...
        writer
        ...
        signal(mx,1);
    }while(true);
}
-------------本文结束感谢您的阅读-------------

本文地址：http://www.wangxinri.cn/2018/01/15/经典进程同步问题/
转载请注明出处，谢谢！

梦想夹带眼泪，咸咸的汗水！