三类读者写者问题 |
您所在的位置：网站首页 › read的读者形式 › 三类读者写者问题 |
|
前言
读者-写者问题(Readers-Writers problem)是经典的同步-互斥问题。本文使用信号量解决三类读者写者问题，分别是读者优先(readers-preference)、写者优先(writers-preference)和公平(fairness)。 本文笔者采用比喻的方式进行讲解，并且规范变量名，以便读者理解。 wikipedia 中没有给出第三种情况的名字，公平和 fairness 是我自己起的名字。wikipedia 中给出了三种情况的特点，分别是 ‘no reader shall be kept waiting if the share is currently opened for reading’, ‘no writer, once added to the queue, shall be kept waiting longer than absolutely necessary’, ‘no thread shall be allowed to starve’. 1 问题描述 1.1 名词解释 1.1.1 临界区临界区是一种特殊资源，同一时刻只允许一个进程访问。临界区可以是一段代码，也可以是一块数据。在本问题中，临界区是一块数据，可以形象化地理解为一块没有势力占领的地区，简称为空地。 1.1.2 读者读者是一个进程，它从临界区读取数据。可以形象化地理解为实行禅让制的仁君集合。 1.1.3 写者写者是一个进程，它向临界区写入数据、或修改数据。可以形象化地理解为实行继承制的暴君集合。 1.2 基本规则描述读者-写者问题是指多个进程同时访问临界区的问题。在本问题中，读者和写者共享一块数据，读者可以同时访问，写者只能单独访问。读者和写者的访问顺序可以是任意的，但是不能同时访问。读者和写者之间的互斥关系见如下表格： readerwriterreader不互斥互斥writer互斥互斥tips: 互斥是指同一时刻只能有一个进程访问临界区。 延伸：了解数据库中锁的机制的话，可以将不互斥理解为 Shared_lock(S 锁)，互斥理解为 Exclusive_lock(X 锁)。 readwritereadSXwriteXX 2 读者优先（瑕疵版）先理解大体流程，再修修补补细节。所以先放一个瑕疵版。 2.1 规则描述 当空地没人占领时，仁君和暴君都可以占领这块地。当空地被仁君占领时，其他仁君也可以进入这块地，但是暴君不能进入。当空地被暴君占领时，其他仁君和暴君一律不能进入。只有等所有仁君都走了，之前一直等待的暴君才能进来。如何实现有读者时不让其他写者进来呢？形象化的理解如下。 想象一个古代战争场景。仁君和暴君在争夺这片地盘。如果仁君先来了，那么就要打上标记（一般的做法是建城墙、插旗帜表示自己的领地）。这样一来，只其他仁君进来，不让暴君进来。 同样，如果暴君先来，那么也要打上标记，但是暴君与仁君不同的是，暴君打上标记后，不仅不让仁君进来，也不让其他暴君进来。毕竟，不能将自己打下来的江山拱手送给别的家族。 当仁君或暴君放弃这片土地时，就要将标记清除，这样新来的人就可以重新占领这片土地。 所以大体上来看，就是谁先来，就打上标记，走的时候清除标记。 所以重要的一点其实就是打标记和清除标记。这里的标记就是信号量。 2.2 变量声明 信号量说明Resource临界区互斥 变量说明Rcount读者计数 2.3 伪代码 // variables // 1表示剩余空地数量为1，即没有人占领 // 0表示剩余空地数量为0，即有人占领 semaphore Resource = 1; // 读者计数，第一个读者要打标记，最后一个读者要清除标记 int Rcount = 0; // reader reader() { while (true) { if (Rcount == 0) P(Resource); (1) // 第一个进来的读者要打标记 Rcount++; read(); Rcount--; if (Rcount == 0) V(Resource); (2) // 最后一个读者要清除标记 } } // writer writer() { while (true) { P(Resource); // 写者要打标记 write(); V(Resource); // 写者要清除标记 } } 2.4 存在的问题观察代码的(1)部分，考虑到进程是并发执行的，则会出现如下情况。 由两个读者进程 R 1 R_1 R1和 R 2 R_2 R2，当 R 1 R_1 R1执行完(1)后， R 1 R_1 R1时间片结束，开始执行 R 2 R_2 R2。然后 R 2 R_2 R2也正好执行完(1)，随后时间片结束。然后 R 1 R_1 R1执行P(Resource)， R 2 R_2 R2执行P(Resource)。这样一来，Resource的值就会减 2 次，变成-1，会出现问题。同理，在清除标记时（即代码(2)），也会出现同样的问题。如果 V(Resource)因并发的原因执行两次，那么Resource的值就会加 2 次，变成2，也会出现问题。 什么问题？ 假设 Resource 变为-1 后，退出时正常退出，则 Resource 变为 0.这说明读者已经全部退出了，但是 Resource 的值却不为 1，这就说明资源没了，这不合理。继续考虑，在 Resource 为 0 的情况下来了个写者，那么就会在 P(Resource)的时候阻塞。这是异常行为。同理，如果 Resource 变为 2，那么就会出现异常行为。 所以我们要解决这个问题。问题出在并发执行 P(Resource)和 V(Resource)上，那么为了确保正确性，就要对这两个操作加锁。加锁方式和对 Resource 的操作一致，新引入一个信号量即可。我们称之为Rmutex。在3部分完善代码。 3 读者优先（完善版）上文中分析了并发执行 P(Resource)和 V(Resource)的问题，所以我们要对这两个操作加锁。加锁方式和对 Resource 的操作一致，新引入一个信号量即可。我们称之为Rmutex。 3.1 变量声明 信号量说明Resource临界区互斥Rmutex读者计数互斥，不允许同时改变 Rcount 变量说明Rcount读者计数 3.2 伪代码 // variables // 1表示剩余空地数量为1，即没有人占领 // 0表示剩余空地数量为0，即有人占领 semaphore Resource = 1; // 读者计数互斥 semaphore Rmutex = 1; // 读者计数，第一个读者要打标记，最后一个读者要清除标记 int Rcount = 0; // reader reader() { while (true) { P(Rmutex); (1) // 读者计数互斥 if (Rcount == 0) P(Resource); // 第一个进来的读者要打标记 Rcount++; V(Rmutex); (2) // 读者计数互斥 read(); P(Rmutex); (1) // 读者计数互斥 Rcount--; if (Rcount == 0) V(Resource); // 最后一个读者要清除标记 V(Rmutex); (2) // 读者计数互斥 } } // writer writer() { while (true) { P(Resource); // 写者要打标记 write(); V(Resource); // 写者要清除标记 } }可以看到对 Rcount 进行操作时，都使用(1)(2)加了锁。这样一来，就可以保证 P(Resource)和 V(Resource)不会被执行两次。 这里为什么不存在并发的问题了？ 如果 R 1 R_1 R1执行(1)后时间片结束，轮到 R 2 R_2 R2执行(1)，那么会发现此时 Rmutex=0，那么 R 2 R_2 R2会被阻塞。当 R 1 R_1 R1执行完(2)后， R 2 R_2 R2才可以继续执行下去。那么此时 R 2 R_2 R2就会发现 Rcount 值为 1（那个 1 是谁？就是 R 1 R_1 R1），那样就不会执行 P(Resource)。V(Resource)同理。 3.3 存在的问题考虑这种情况。当前已经有仁君占领了这片土地，此时来了一个暴君，那么暴君只能等待。然后在暴君等待的过程中，仁君源源不断的来，那么暴君只能永远等待下去。我们称这种情况为饥饿（或饿死）。 为了避免暴君饥饿，我们介绍写者优先的算法。 4 写者优先 4.1 规则描述版本更新了，暴君氪金买装备，把仁君按着头往地上摩擦，然后暴君就可以占领这片土地了。 当空地没人占领时，仁君和暴君都可以占领这块地。当空地被仁君占领时，其他仁君都可以进入这块地。但是一旦有暴君来了，其他仁君就不能进来了。等当前占领的仁君退出后，暴君宣布占领这块地。当空地被暴君占领时，其他仁君和暴君一律不能进入。只有等所有暴君都走了，之前一直等待的仁君才能进来。这样就解决了暴君饥饿的问题，一旦暴君请求占领这块地，那么其他仁君就不能再进来了，需要等待暴君离开后，才能重新占领这块地。 如何实现呢？我们再增加一个信号量readTry。readTry=1 表示暴君没来，仁君可以进入；readTry=0 表示暴君来了，仁君不能进入。那么也就是说，当暴君申请占领这块地时，要将readTry设置为 0，当暴君离开这块地时，要将readTry设置为 1. 为啥起名为 readTry? 当其他读者来时，要检查一下当前排队的里面有没有暴君，这个动作相当于试一试能不能读，所以叫 readTry。 4.2 变量声明 信号量说明Resource临界区互斥Rmutex读者计数互斥，不允许同时改变 RcountWmutex写者计数互斥，不允许同时改变 WcountreadTry是否允许读者访问，即是否有写者正在排队readQueue读者队列，用于排队读者 变量说明Rcount读者计数Wcount写者计数这里为什么添加了写者计数呢？思考设置Rcount的原因。我们要使第一个读者打标记，最后一个读者清除标记。同样，这里我们要使第一个写者打标记(readTry=0)，最后一个写者清除标记(readTry=1)。所以我们需要一个计数器来计数写者的数量。同样，设置一个Wmutex与Wcount配套使用。 读者读代码时可以先不管readQueue，readQueue的作用将在代码后面说明。 4.3 伪代码 //variables // 1表示剩余空地数量为1，即没有人占领 // 0表示剩余空地数量为0，即有人占领 semaphore Resource = 1; // 读者计数互斥 semaphore Rmutex = 1; // 写者计数互斥 semaphore Wmutex = 1; // 是否允许读者访问，即是否有写者正在排队 semaphore readTry = 1; // 允许写者插队 semaphore readQueue = 1; // 读者计数，第一个读者要打标记，最后一个读者要清除标记(Resource) int Rcount = 0; // 写者计数，第一个写者要打标记，最后一个写者要清除标记(readTry) int Wcount = 0; // reader reader() { while (true) { P(readQueue) P(readTry) (1) //试一下能不能访问 P(Rmutex); if (Rcount == 0) P(Resource); Rcount++; V(Rmutex); V(readTry) (2) // 访问成功了，恢复一下，让别的读者也能访问 V(readQueue) read(); P(Rmutex); Rcount--; if (Rcount == 0) V(Resource); V(Rmutex); } } // writer writer() { while (true) { P(Wmutex); Wcount++; if (Wcount == 1) P(readTry); // 第一个写者要打标记，不让读者进 V(Wmutex); P(Resource); write(); V(Resource); P(Wmutex); Wcount--; if (Wcount == 0) V(readTry); // 最后一个写者要清除标记，让读者进 V(Wmutex); } }没有找到权威的解释，以下对于readQueue的解读全凭自己理解，也请各位大神在评论区发表看法。感谢！ 介绍一下readQueue的作用。假设现在没有readQueue，考虑这样一个进程顺序： w1() → \rightarrow → w1.P(Wmutex) → \rightarrow → … → \rightarrow → w1.write() → \rightarrow → w2() → \rightarrow → w2.P(Wmutex) → \rightarrow → … → \rightarrow → w2.P(Resource) → \rightarrow → r1() → \rightarrow → r2() → \rightarrow → w1.V(Resource) → \rightarrow → w1.V(readTry) → \rightarrow → w1.V(Wmutex) → \rightarrow → … 写的有些跳跃，说实话我也不知道如何表达比较好，建议大家自己画个图。 解释一下，当w1运行到V(readTry)之前，如果有r进程申请，那么r进程会被阻塞，直到w1.V(readTry)才可以运行；如果有w进程申请，那么只需等待w1.V(Resource)即可接着运行。所以在w1运行到V(readTry)之前，其他w进程都是可以插队的。但是当w1运行到V(readTry)时，如果有w进程申请，那么就晚了。因为w1.V(readTry)运行后，被readTry阻塞的进程就会恢复运行，那么在这时候来的w进程就不能插队了，得等之前阻塞掉的r进程执行完。这是和写者优先的思想的矛盾的。 为什么要等待之前的r进程都执行完？ 假设w1运行完V(readTry)后，被调入了优先级低的就绪队列。而因P(readTry)而阻塞的r1进程被调入了优先级高的就绪队列。然后r1执行完V(readTry)后，r2也被调入了优先级高的就绪队列…这样一来，就会出现r进程源源不断的来，w进程永远也插不上队了。所以要等待之前的r进程都执行完。 这种情况不是百分百的，仍有概率发生。所以要考虑这种情况。 现在来看一下如果加入了readQueue信号量的话，会发生什么。 无论w1运行到什么时候，只有一个r1进程可以执行到P(readTry)，剩下的r进程都在P(readQueue)上被阻塞掉了。只有当r1.V(readQueue)被执行后，第二个被readQueue阻塞的r进程才可以执行P(readTry)。writer()端和readQueue是无关的，且保证了任何时刻只有1个r进程阻塞在readTry上，这就保证了w进程可以插队（或者说最多阻塞1个r进程的时间）。 为什么最多阻塞1个r的进程的时间？ 假设现在w1运行到末尾的V(readTry)部分，这个时候有一个r1在P(readTry)被阻塞，还有一堆r被P(readQueue)阻塞，还有一个w在最开始的P(Wmutex)处被阻塞。 这个时候w1运行完V(readTry)，那么r1会进入就绪队列。此时没有r在readTry处阻塞，还是原来那一堆r在readQueue处阻塞，那个w仍在P(Wmutex)处阻塞。 然后w1继续运行V(Wmutex)，那么那个在最开始P(Wmutex)处被阻塞的w就会进入就绪队列。此时这个就绪队列的队首是r1，下一个才是w。 然后r1运行到V(readQueue)，那么那一堆r中的一个r会进入就绪队列。此时就绪队列的队首是w，下一个才是r。 然后w运行到P(Resource)，那么w就可以进入临界区了。这就是所谓的延迟一个r进程的时间。如果w来的时间早于w1第二次P(Wmutex)，那么就不需要经历这个延迟，直接进入队首了。 4.4 存在的问题考虑这种情况，当前这块地被暴君占领，然后门外有暴君源源不断的来，那么仁君只能永远等待下去，这下，饥饿现象发生在了仁君身上。 所以我们看到，读者优先情况下，读者可以源源不断的来，写者饥饿；写者优先情况下，写者可以源源不断的来，读者饥饿。那么有没有一种情况，既不让读者饥饿，也不让写者饥饿呢？答案是有的，那就是第三种读者-写者问题：公平的情况。 5 公平在考虑读者或者写者源源不断到来的情况时，读者优先将读者排在了前面，写者优先将写者排在了前面。在公平的情况下，保留了读者和写者到来的顺序，即先来的先访问(FIFO)。 5.1 规则描述版本又更新了，玉皇大帝来了，管你仁君还是暴君，都得排队。先来的先访问。 公平，公平，还是***公平！ 空地视为始终被玉皇大帝占领。无论是暴君还是仁君都要排队申请使用权。当这块地里有仁君时，排在第一个暴君前的所有仁君都可以进来，如果没有暴君在排队，那么所有仁君都可以进来。当这块地里有暴君时，所有仁君和暴君都不能进来。 5.2 变量声明 信号量说明Resource临界区互斥Rmutex读者计数互斥，不允许同时改变 RcountserviceQueue服务队列，用于排队 变量说明Rcount读者计数 5.3 伪代码 // variables // 1表示剩余空地数量为1，即没有人占领 // 0表示剩余空地数量为0，即有人占领 semaphore Resource = 1; // 读者计数互斥 semaphore Rmutex = 1; // 只有队首可以申请，其他的先阻塞着，等队首进入了，再依次申请 semaphore serviceQueue = 1; // 读者计数，第一个读者要打标记，最后一个读者要清除标记 int Rcount = 0; // reader reader() { while (true) { P(serviceQueue); (1) // 申请使用权 P(Rmutex); if (Rcount == 0) P(Resource); Rcount++; V(Rmutex); V(serviceQueue); (2) // 申请成功，恢复一下，让别人也能申请 read(); P(Rmutex); Rcount--; if (Rcount == 0) V(Resource); V(Rmutex); } } // writer writer() { while (true) { P(serviceQueue); (1) // 申请使用权 P(Resource); write(); V(Resource); V(serviceQueue); (2) // 申请成功，恢复一下，让别的人也能申请 } }wikipedia中V(serviceQueue)的位置和我的代码中的位置不太一样。wikipedia给出的代码中将V(serviceQueue)的位置提前了。对于这个问题，笔者认为在正确性上没有区别，但是有没有什么其他问题，笔者不太清楚。欢迎大神来评论解答。感谢。 6 引用wikipedia 以上就是本篇文章的全部内容。感谢读者的观看。欢迎大家对本文任何内容的错误进行指正或提出任何方面的建议。笔者会及时修改。谢谢。 |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |