操作系统三大经典同步问题

发表于 | 分类于 ， | 热度 ℃
字数统计: 1,893 | 阅读时长 ≈ 8

用专业术语来说, 进程是程序的一次动态执行.说简单点, 就是进程是系统中的某个任务.操作系统中有多个任务需要执行, 那么怎样执行才能使它们同步呢? 即如何让任务并发执行互不影响呢? 这就引出了进程同步中的经典问题: 生产者消费者问题, 哲学家进餐问题, 读写问题

生产者-消费者问题

有一群生产者进程在生产产品, 并将这些产品提供给消费者进程取消费. 为使生产者进程与消费者进程能并发进行, 在两者间设置了一个具有n个缓冲区的缓冲池, 生产者进程将其所生产的产品翻入缓冲区中, 消费者进程可从一个缓冲区中取走产品取消费.生产者消费者进程都以异步方式进行, 但它们之间必须保持同步, 不允许消费者进程到空缓冲区去取产品, 也不允许生产者进程向已满的缓冲区投放产品.

一个缓冲池中有n个缓冲区, 只要缓冲池未满, 生产者便可以投放产品; 缓冲池为空, 消费者便可以消费产品

法一:记录型信号量

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
//生产者消费者问题
//记录型信号量
//缓冲池中有n个缓冲区, 互斥信号量mutex, 
//信号量empty表示空缓冲区数量, full表示满缓冲区的数量
int in = 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
}

注意: 对信号量的wait()和signal()操作必定是成对出现的.

法二: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
29
30
31
32
//AND型信号量
//Swait(empty, mutex)代替wait(empty)和wait(mutex)
//Ssignal(mutex,full)代替signal(mutext)和signal(full)
//Swait(full, mutex)代替wait(full)和wait(mutex)
//Ssignal(mutex, empty)代替signal(mutex)和signal(empty)
int in = 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
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//管程
//建立管程producerconsumer,PC
/*
put(x), 生产者利用该过程将自己生产的产品投放到缓冲池中, 并用整型变量count表示缓冲池中已有的产品数目,当
count>=N时, 表示缓冲池已满,生产者需等待.
get(x), 消费者利用该过程从缓冲池中取出一个产品, 当count<=0时, 表示缓冲池已无可用的产品, 消费者需等待
condition 为notfull和notempty
cwait(condition), 当管程被一个进程占用时, 其他进程调用该进程时阻塞, 并挂在条件condition的队列上
csignal(condition), 唤醒在cwait执行后阻塞在条件condition队列上的进程, 如果这样的进程不止一个, 则选择其中一个
实施唤醒操作, 如果队列为空, 则无操作而返回.
*/
Monitor producerconsumer {
    item buffer[N];
    int in, out;
    condition notfull, notempty;
    int count;
    public:
        void put(item x) {
            if (count >= N) cwait(notfull);
            buffer[in] = x;
            in = (in + 1) % N;
            count++;
            ssignal(notempty);
        }
        void get(item x) {
            if (count <= 0) cwait(notempty);
            x = buffer[out];
            out = (out + 1) % N;
            count--;
            csignal(notfull);
        }
        {
            in = 0;
            out = 0;
            count = 0;
        }
}PC;

void producer() {
    item x;
    while (true) {
        producer an item in nextp;
        PC.put(x);
    }
}
void consumer() {
    item x;
    while (true) {
        PC.get(x);
        consumer the item in nextc;
    }
}
void main() {
    cobegin
        producer();
        consumer();
    coend
}

哲学家进餐问题

五个哲学家公用一张圆桌, 分别坐在周围的五张桌子上, 在圆桌上有五个碗和五只筷子交叉排列, 它们的生活方式是交替的进行思考和进餐. 哲学家进行思考时不用筷子, 饥饿时取一只他两边的任意一只筷子(默认取左边的筷子, 没有时取右边的, 都没有时就取不了), 当他有两只筷子时就能进餐. 进餐后, 放下筷子继续思考.若只有一只筷子, 不放弃该筷子并等待拥有另一只筷子时再进餐.

用一个信号量表示一只筷子, 共五个信号量 semaphore chopsitck[5] = {1, 1, 1, 1, 1}; , 为 1 表示筷子未拿起, 为0表示筷子被拿起.那么第i为科学家的进餐活动就可以描述为

法一:记录型信号量

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

假设五位哲学家都要拿筷子(都拿左手边), 那么将没有人可以 用餐, 就会陷入死锁状态.则哲学家进餐的解决方法:

1.至多允许四位哲学家拿同一边的筷子, 则可让至少一位哲学家先用餐, 用餐完后释放筷子进而让其他哲学家有机会用餐.

2.五位哲学家先竞争奇数(偶数)好筷子, 在竞争偶数(奇数)号筷子, 总会有一位哲学家能进餐.

法二: AND型信号量

1
2
3
4
5
6
7
8
//AND型信号量
semaphore chopstick[5] = {1, 1, 1, 1, 1};
do {
    //think
    Swait(chopsitck[(i + 1) % 5], chopsitck[i]);
    //eat
    Ssignal(chopsitck[(i + 1) % 5], chopsitck[i]);
} while (true);

读者-写者问题

一个数据文件或记录可被多个进程所共享, 则我们称这个文件或记录为共享对象.读文件的进程称为Reader进程, 写文件的进程称为Writer进程.共享对象可以被多个Reader进程, 因为读进程并不会破坏数据, 但是Writer进程在任何时刻只能有一个, 且须与其他对象互斥的访问共享对象, 否则多个写进程会造成冲突. 读写者问题即一个Writer进程必须与其他进程互斥的访问共享对象.

设置写互斥信号量wmutex

设置读互斥信号量rmutex

整型变量readcount表示正在读的进程数目(Reader)

当readcount!=0时, 表示有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
28
29
30
31
32
33
34
35
36
//记录型信号量
semaphore rmutext = 1, wmutext = 1;
int readcount = 0;
void Reader() {
    do {
        wait(rmutex);
        if (readcount == 0) {
            wait(wmutex);
        }
        readcount++;
        signal(rmutex);
        
        perform read operation;
        
        wait(rmutex);
        readcount--;
        if (readcount == 0) {
            signal(wmutext);
        }
        signal(rmutex);
    } while (true);
}

void Writer() {
    do {
        wait(wmutex);
        perform write operation;
        signal(wmutex);
    } while (true);
}
void main() {
    cobegin
        Reader();
        Writer();
    coend
}

法二:

引入RN, 表示最多允许RN个Reader进程同时读

信号量L初始为RN

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 RN;
semaphore L = RN, mx = 1;
void Reader() {
    do {
        Swait(L, 1, 1);
        Swait(mx, 1, 0);
        
        perform read operation;
        
        Ssignal(L, 1);
    } while (true);
}
void Writer() {
    do {
        Swait(mx, 1, 1; L, RN, 0);
        perform write operation;
        Ssignal(mx, 1);
    } while (true);
}

void main() {
    cobegin
        Reader();
        Writer();
    coend
}
文章结束了，但我们的故事还在继续
坚持原创技术分享，您的支持将鼓励我继续创作！