Unit 3.5
Classic IPC Problems
Presenter Notes
The Producer-Consumer Problem
Presenter Notes
生产者消费者问题（英语：Producer-consumer problem），也称有限缓冲问题（英语：Bounded-buffer problem），是一个多线程同步问题的经典案例。该问题描述了两个共享固定大小缓冲区的线程——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。生产者的主要作用是生成一定量的数据放到缓冲区中，然后重复此过程。与此同时，消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。
The Producer-Consumer Problem
The producer-consumer problem with a fatal race condition.
Presenter Notes
生产者消费者问题（英语：Producer-consumer problem），也称有限缓冲问题（英语：Bounded-buffer problem），是一个多线程同步问题的经典案例。该问题描述了两个共享固定大小缓冲区的线程——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。生产者的主要作用是生成一定量的数据放到缓冲区中，然后重复此过程。与此同时，消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。
The Producer-Consumer Problem
The producer-consumer problem with a fatal race condition.
Presenter Notes
要解决该问题，就必须让生产者在缓冲区满时休眠（要么干脆就放弃数据），等到下次消费者消耗缓冲区中的数据的时候，生产者才能被唤醒，开始往缓冲区添加数据。同样，也可以让消费者在缓冲区空时进入休眠，等到生产者往缓冲区添加数据之后，再唤醒消费者。通常采用进程间通信的方法解决该问题，常用的方法有信号灯法等。如果解决方法不够完善，则容易出现死锁的情况。出现死锁时，两个线程都会陷入休眠，等待对方唤醒自己。该问题也能被推广到多个生产者和消费者的情形。
The Producer-Consumer Problem
#define N 100 /* number of slots in the buffer */
semaphore mutex = 1; /* controls access to critical region*/
semaphore empty = N; /* counts empty buffer slots */
semaphore full = 0; /* counts full buffer slots */
void producer(void) {
int item;
while (TRUE) {
item = produce_item();
P(empty);
P(mutex);
insert_item(item);
V(mutex);
V(full);
}
}
The Producer-Consumer Problem
void consumer(void) {
int item;
while (TRUE) {
P(full);
P(mutex);
item = remove_item();
V(mutex);
V(empty);
consume_item(item);
}
}
Dining Philosophers Problem
Lunch time in the Philosophy Department.
Presenter Notes
哲学家就餐问题是在计算机科学中的一个经典问题，用来演示在并行计算中多线程同步(Synchronization)时产生的问题。在1971年，著名的计算机科学家艾兹格·迪科斯彻提出了一个同步问题，即假设有五台计算机都试图访问五份共享的磁带驱动器。稍后，这个问题被托尼·霍尔重新表述为哲学家就餐问题。这个问题可以用来解释死锁和资源耗尽。
Dining Philosophers Problem
A nonsolution to the dining philosophers problem.
Presenter Notes
哲学家就餐问题可以这样表述，假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情之一：吃饭，或者思考。吃东西的时候，他们就停止思考，思考的时候也停止吃东西。餐桌中间有一大碗意大利面，每两个哲学家之间有一只餐叉。因为用一只餐叉很难吃到意大利面，所以假设哲学家必须用两只餐叉吃东西。他们只能使用自己左右手边的那两只餐叉。哲学家就餐问题有时也用米饭和筷子而不是意大利面和餐叉来描述，因为很明显，吃米饭必须用两根筷子。 哲学家从来不交谈，这就很危险，可能产生死锁，每个哲学家都拿着左手的餐叉，永远都在等右边的餐叉（或者相反）。即使没有死锁，也有可能发生资源耗尽。例如，假设规定当哲学家等待另一只餐叉超过五分钟后就放下自己手里的那一只餐叉，并且再等五分钟后进行下一次尝试。这个策略消除了死锁（系统总会进入到下一个状态），但仍然有可能发生“活锁”。如果五位哲学家在完全相同的时刻进入餐厅，并同时拿起左边的餐叉，那么这些哲学家就会等待五分钟，同时放下手中的餐叉，再等五分钟，又同时拿起这些餐叉。
Dining Philosophers Problem
#define N 5
#define LEFT (i+N-1)%N
#define RIGHT (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATTING 2
int state[N]; /* array to keep track of everyone's state */
semaphore mutex=1; /* mutual exclusion for critical regions */
semaphore s[N]; /* one semaphore per philosopher */
void philosopher(int i)
{
while (TRUE) {
think(i);
take_forks(i);
eat();
put_forks(i);
}
}
void take_forks(int i)
{
P(mutex)
state[i] = HUNGRY;
test(i);
V(mutex);
P(s[i]);
}
void put_forks(int i)
{
P(mutex)
state[i] = THINKING;
test(LEFT);
test(RIGHT);
V(mutex);
}
void test(int i)
{
if( state[i] == HUNGRY
&& state[LEFT] != EATTING
&& state[RIGTH] != EATTING) {
state[i] = EATTING;
V(s[i]);
}
}
The Readers and Writers Problem
Presenter Notes
有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：①允许多个读者可以同时对文件执行读操作；②只允许一个写者往文件中写信息；③任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让已有的读者和写者全部退出。 分析思想： 读者到： 1）无读者、写者，新读者可以读 2）有写者等，但有其它读者正在读，则新读者也可以读 3）有写者写，新读者等 写者到： 1）无读者，新写者可以写 2）有读者，新写者等待 3）有其它写者，新写者等待
Reader priority solution
semaphore fmutex=1 //fmutex --> access to file;
sepaphore rdcntmutex=1; // rdcntmutex --> access to reader_count
int reader_count = 0; // reader_count --> the number of readers
void reader(){
while ( TRUE ){
P(rdcntmutex);
if( reader_count == 0 ) { P(fmutex); }
reader_count = reader_count + 1;
V(rdcntmutex);
//Do read operation ...
P(rdcntmutex);
reader_count = reader_count - 1;
if( reader_count == 0) { V(fmutex); }
V(rdcntmutex);
}
}
Reader priority solution
void writer(){
while ( TRUE ){
P(fmutex);
//Do write operation ...
V(fmutex);
}
}
Writer priority solution
semaphore fmutex=1, rdcntmutex=1, wtcntmutex=1, queue=1;
int reader_count = 0, writer_count = 0;
void reader(){
while( TRUE ){
P(queue);
P(rdcntmutex);
if( reader_count == 0 ) { P(fmutex); }
reader_count = reader_count + 1;
V(rdcntmutex);
V(queue);
//Do read operation ...
P(rdcntmutex);
reader_count = reader_count - 1;
if( reader_count == 0 ) { V(fmutex); }
V(rdcntmutex);
}
}
Writer priority solution
void writer(){
while( TRUE ){
P(wtcntmutex);
if( writer_count == 0 ) { P(queue); }
writer_count = writer_count + 1;
V(wtcntmutex);
P(fmutex);
//Do write operation ...
V(fmutex);
P(wtcntmutex);
writer_count = writer_count - 1;
if( writer_count == 0 ) { V(queue); }
V(wtcntmutex);
}
}
Fair competition solution
void reader() {
// ... same as reader() in "writer priority solution" ...
}
void writer(){
while( TRUE ){
P(queue);
P(fmutex);
V(queue);
//Do write operation ...
V(fmutex);
}
}
The sleeping barber problem
Presenter Notes
假设有一个理发店只有一个理发师，一张理发时坐的椅子，若干张普通椅子顾客供等候时坐。没有顾客时，理发师就坐在理发的椅子上睡觉。顾客一到，他不是叫醒理发师，就是离开。如果理发师没有睡觉，而在为别人理发，他就会坐下来等候。如果所有的椅子都坐满了人，最后来的顾客就会离开。 在出现竞争的情况下问题就来了，这和其它的排队问题是一样的。实际上，与哲学家就餐问题是一样的。如果没有适当的解决方案，就会导致进程之间的“饿肚子”和“死锁”。 如理发师在等一位顾客，顾客在等理发师，进而造成死锁。另外，有的顾客可能也不愿按顺序等候，会让一些在等待的顾客永远都不能理发。
The sleeping barber problem
#define CHAIRS 5 /* # chairs for waiting customers */
semaphore customers = 0; /* # of customers waiting for service */
semaphore barbers = 0; /* # of barbers waiting for customers */
semaphore mutex = 1; /* for mutual exclusion */
int waiting = 0; /* customers are waiting (not being cut) */
void barber(void)
{
white (TRUE) {
P(customers); /* go to sleep if # of customers is 0 */
P(mutex); /* acquire access to 'waiting' */
waiting = waiting − 1; /* decrement count of waiting customers */
V(barbers); /* one barber is now ready to cut hair */
V(mutex); /* release 'waiting' */
cut_hair(); /* cut hair (outside critical region) */
}
}
The sleeping barber problem
void customer(void)
{
P(mutex); /* enter critical region */
if (waiting < CHAIRS) { /* if there are no free chairs, leave */
waiting = waiting + 1; /* increment count of waiting customers */
V(customers); /* wake up barber if necessary */
V(mutex); /* release access to 'waiting' */
P(barbers); /* go to sleep if # of free barbers is 0 */
get_haircut(); /* be seated and be serviced */
} else {
V(mutex); /* shop is full; do not wait */
}
}
Reference
- Chapter 2: Processes and threads, Modern Operating Systems . Forth Edition, Andrew S. Tanenbaum