OS

经典同步问题

Posted by Joel on September 05,2018

银弹

关系分析

找出有几个进程并分析他们之间的关系（互斥、同步、前驱）

整理思路

根据进程操作流程找出PV操作的大致顺序

设置信号量

设置需要的信号量，设置初值，完善整理

生产者-消费者问题

关系分析

显然这里有两个进程，生产者与消费者，它们之间显然是同步关系，对缓冲池的使用则是互斥的

整理思路 & 设置信号量

  1. 生产者放入数据前应检查缓冲池是否满，此为信号量1，放入后还应更新信号量2

  2. 消费者取出数据前应检查缓冲池是否空，此为信号量2

  3. 信号量mutex用来实现互斥访问缓冲池

伪代码

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 // 互斥锁，初值为1，代表可以访问
semaphore empty = n // 空缓存的数量，初值为n
semaphore full = 0 // 填满的缓存的数量，初值为0

process producer() {
    while(true) {
        create product;
        P(empty); // 获取空缓冲区
        P(mutex); // 申请访问缓冲区
        load product into buffer;
        V(mutex); // 释放缓冲区控制权
        V(full); // 满缓冲区数+1
    }
}

process consumer() {
    while(true) {
        P(full);
        P(mutex);
        get product from buffer;
        V(mutex);
        V(empty);
    }
}

变种生产者-消费者问题

关系分析

显然有四个进程，儿子、爸爸、女儿、妈妈，爸爸和妈妈对于盘子的操作是互斥的，儿子与爸爸、女儿与妈妈分别是同步的

整理思路 & 设置信号量

  1. 首先对盘子的访问是互斥的，即为信号量plate
  2. 爸爸与儿子间需要一个信号量orange实现同步
  3. 同理妈妈与女儿间需要一个信号量apple实现同步
  4. 儿子女儿之间不需要互斥

伪代码

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
33
34
35
36
37
semaphore plate = 1; // 互斥锁，初始值为1，表示可以放水果
semaphore orange = 0;
semaphore apple = 0;

process dad() {
    while(true) {
        prepare orange;
        P(plate);
        put orange on plate;
        V(orange);
    }
}

process mom() {
    while(true) {
        prepare apple;
        P(plate);
        put apple on plate;
        V(apple);
    }
}

process son() {
    while(true) {
        P(orange);
        take orange from plate;
        V(plate);
    }
}

process daughter() {
    while(true) {
        P(apple);
        take apple from plate;
        V(plate);
    }
}

读者写者问题

关系分析

读者之间不需要同步，写者与写者之间，写者与读者之间是互斥的

整理思路 & 设置信号量

  1. 读写文件显然是互斥的，用互斥锁rw来实现

  2. 多个读者可以同时访问文件，而只要有读者在写者就不能访问文件，说明写者与读者之间存在一个计数器count来实现控制rw实现互斥

  3. 不同读者之间访问计数器应是互斥的，用信号量mutex实现

伪代码

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
semaphore mutex = 1;
semaphore rw = 1;
semaphore count = 0;
semaphore w = 1; // 实现写优先

process writer() {
    P(w); // 实现写优先
    P(rw);
    write file;
    V(rw);
    V(w); // 实现写优先
}

process reader() {
    P(w); // 实现写优先
    P(mutex);
    if (count == 0) {
        P(rw);
    }
    count++;
    V(mutex);
    V(w);// 实现写优先
    read file;
    P(mutex);
    count--;
    if (count == 0) {
        V(rw);
    }
    V(mutex);
}

哲学家就餐问题

关系分析

显然相互之间对叉子的访问是互斥的

整理思路 & 设置信号量

  1. 每个叉子用一个信号量实现互斥访问，即有信号量数组forkes[5]
  2. 当两边的叉子都可用时才允许拿起叉子，用互斥锁mutex实现

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 这一实现其实有性能问题，因为同一时刻只能有一人吃，而实际上最多可以有两人
semaphore forkes[5];
semaphore mutex = 1;

process Pi() {
    while (true) {
        P(mutex);
        P(forkes[i]);
        P(forkes[(i + 1) % 5]);
        V(mutex);
        eat;
        V(forkes[i]);
        V(forkes[(i + 1) % 5]);
        think;
    }
}

吸烟者问题

关系分析

四个进程，三个抽烟者，一个供应者，供应者供货与吸烟者卷烟的应同步，供应者供货与吸烟者吸烟应互斥

整理思路 & 设置信号量

  1. 三个吸烟者卷烟需要三个信号量offer1-3来与供应者同步
  2. 抽烟需要一个信号量与供应者实现互斥

伪代码

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
semaphore s1 = 0, s2 = 0, s3 = 0, mutex = 1;

process producer() {
    P(mutex);
    V(oneOf(s1, s2, s3));
    V(mutex);
}

process smoker1() {
    P(s1);
    make();
    P(mutex);
    smoke();
    V(mutex);
}
process smoker2() {
    P(s2);
    make();
    P(mutex);
    smoke();
    V(mutex);
}
process smoker3() {
    P(s3);
    make();
    P(mutex);
    smoke();
    V(mutex);
}

EOF

FEATURED TAGS
OS
FRIENDS
>