[操作系统] Week 6 Note 2

2、读者-写者问题

A data set is shared among a number of concurrent processes

• Readers （读者）– only read the data set; they do not perform any updates //不对数据作修改
• Writers （写者） – can both read and write //可以进行读和写两种操作

一个数据集（如文件）如果被几个并行进程所共享：

• 有些进程只要求读数据集内容，它称读者
• 一些进程则要求修改数据集内容，它称写者
• 几个读者可以同时读些数据集，而不需要互斥
• 一个写者不能和其它进程（不管是写者或读者）同时访问些数据集，它们之间必须互斥。

MEMO:新闻从业者的缩减、网络新闻的门槛低导致新闻的质量降低。

The first readers-writers problem

• allow multiple readers to read at the same time. Only one single writer can access the shared data at the same time //只允许一个写者操作
  • writers may starve

The second readers-writers problem

• Once a writer is ready the writer performs write as soon as possible //一旦有读者需要写就让他尽快写
  • readers may starve

do {
wait(mutex);
readcount++;
if (readcount == 1)
wait(wrt);
signal(mutex);
…
reading is performed
…
wait(mutex);
readcount--;
if (readcount == 0)
signal(wrt);
signal(mutex)；
} while (TRUE);

do {
wait (wrt) ;
// writing is performed
signal (wrt) ;
} while(true);

3、Dining-Philosophers Problem

哲学家就餐问题

Problem Statement: N Philosophers sitting at a round table Each philosopher shares a chopstick with neighbor Each philosopher must have both chopsticks to eat Neighbors can’t eat simultaneously Philosophers alternate between thinking and eating
Shared data Bowl of rice (data set) Semaphore chopstick [5] initialized to 1
Philosopher i: do { wait(chopstick[i]) wait(chopstick[(i+1) % 5]) … eat … signal(chopstick[i]); signal(chopstick[(i+1) % 5]); … think … } while (1);

Clearly deadlock is rampant ( and starvation possible. )

Several solutions are possible:

• Allow only 4 philosophers to be hungry at a time. //只有四个人吃饭
• Allow pickup only if both chopsticks are available. ( Done in critical section ) //只在两个筷子都可用时吃饭
• Odd# philosopher always picks up left chopstick 1st, even# philosopher always picks up right chopstick 1 st .
• 为了避免死锁，把哲学家分为三种状态：思考、饥饿、吃饭，并且一次拿到两只筷子，否则不拿。（Dijkstra）
• 每个哲学家拿起第1根筷子一定时间后，若拿不到第2根筷子，再放下第1根筷子。 //网络通信常见，os不可

P0	P1	P2	P3	P4
P(c[0])	P(c[1])	P(c[2])	P(c[3])	P(c[0])
P(c[1])	P(c[2])	P(c[3])	P(c[4])	P(c[4])

*可以解决饥饿

6.8 OS Synchronization

习题课

1、10个生产者和20个消费者 critical section of the buffer is initialized to 1

2、excusion section should be initialize to 5

4、D