首页 > 代码库 > 【操作系统】经典的同步问题(生产者消费者问题, 哲学家进餐问题, 读写问题)
【操作系统】经典的同步问题(生产者消费者问题, 哲学家进餐问题, 读写问题)
用专业术语来说, 进程是程序的一次动态执行.说简单点, 就是进程是系统中的某个任务.操作系统中有多个任务需要执行, 那么怎样执行才能使它们同步呢? 即如何让任务并发执行互不影响呢? 这就引出了进程同步中的经典问题: 生产者消费者问题, 哲学家进餐问题, 读写问题
生产者-消费者问题
有一群生产者进程在生产产品, 并将这些产品提供给消费者进程取消费. 为使生产者进程与消费者进程能并发进行, 在两者间设置了一个具有n个缓冲区的缓冲池, 生产者进程将其所生产的产品翻入缓冲区中, 消费者进程可从一个缓冲区中取走产品取消费.生产者消费者进程都以异步方式进行, 但它们之间必须保持同步, 不允许消费者进程到空缓冲区去取产品, 也不允许生产者进程向已满的缓冲区投放产品.
一个缓冲池中有n个缓冲区, 只要缓冲池未满, 生产者便可以投放产品; 缓冲池为空, 消费者便可以消费产品
法一:记录型信号量
//生产者消费者问题//记录型信号量//缓冲池中有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型信号量
//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}
法三: 管程
//管程//建立管程producerconsumer,PC/*put(x), 生产者利用该过程将自己生产的产品投放到缓冲池中, 并用整型变量count表示缓冲池中已有的产品数目,当count>=N时, 表示缓冲池已满,生产者需等待.get(x), 消费者利用该过程从缓冲池中取出一个产品, 当count<=0时, 表示缓冲池已无可用的产品, 消费者需等待condition 为notfull和notemptycwait(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为科学家的进餐活动就可以描述为
法一:记录型信号量
do { wait(chopstick[i]); wait(chopstick[(i + 1) % 5]); //eat signal(chopstick[i]); signal(chopstick[(i + 1) % 5]); //think} while (true);
假设五位哲学家都要拿筷子(都拿左手边), 那么将没有人可以 用餐, 就会陷入死锁状态.则哲学家进餐的解决方法:
1.至多允许四位哲学家拿同一边的筷子, 则可让至少一位哲学家先用餐, 用餐完后释放筷子进而让其他哲学家有机会用餐.
2.五位哲学家先竞争奇数(偶数)好筷子, 在竞争偶数(奇数)号筷子, 总会有一位哲学家能进餐.
法二: AND型信号量
//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进程.
法一:
//记录型信号量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
//信号量集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}
【操作系统】经典的同步问题(生产者消费者问题, 哲学家进餐问题, 读写问题)