网站积分程序怎么建设,惠州seo推广公司,医院网站建设要求是什么,wordpress 主题查询文章目录 I.读者-写者问题1.读者-写者问题和分析2.读者—写者问题基本解法3.饥饿现象和解决方案总结 II.Peterson算法实现1.Peterson算法问题与分析(1).如何无锁访问临界区呢#xff1f;(2).Peterson算法的基本逻辑(3).写对方/自己进程号的区别是#xff1f; 2.只包含意向的解… 文章目录 I.读者-写者问题1.读者-写者问题和分析2.读者—写者问题基本解法3.饥饿现象和解决方案总结 II.Peterson算法实现1.Peterson算法问题与分析(1).如何无锁访问临界区呢(2).Peterson算法的基本逻辑(3).写对方/自己进程号的区别是 2.只包含意向的解决方案3.严格轮换法4.完整的Peterson算法总结 参考资料 I.读者-写者问题
1.读者-写者问题和分析 读者: 读数据写者: 写数据访问规则:多个读者可以同时读数据任何时刻只能有一个写者写数据一个读者与一个写者不能同时在相应的临界区中实质: 一个写者不能与其它的读者或写者同时访问相应的临界资源。 这算是一个非常经典的问题实际上这也是数据库系统中遇到的最重要的一个问题因为对于同一个文件可以多人读但是不能多人写如何才能更好地安排资源的分配呢 对于这个问题首先肯定应该给出一个基本解法那就是保证读者可以读写者在一定情况下也能写因此比较常用的是这样一种解法首先有一把排他锁(写锁)只有一个线程可以获得这把排他锁并且有若干把共享锁(读锁)共享锁可以被任意读线程获取但是这些线程都不能写不过如果用信号量实现的话我们总是需要一个可能无限大的变量进行锁的分配因此可以改变一下思路用一个变量记录读者数量当读者为0时允许获取写锁而当读者不为0时记录数量并且不允许获取写锁因为这个变量本身属于临界区因此只需要对这个变量加一把互斥锁即可。
2.读者—写者问题基本解法 在1中我们已经分析了这个问题的一种基本解法因此可以用C语言实现如下的代码
#include stdio.h
#include semaphore.h
#include pthread.h
#define P sem_wait
#define V sem_post
#define RNUMS 10
#define WNUMS 3
sem_t mutex, x;
int readers_cnt;
int rids[RNUMS], wids[WNUMS];void init()
{sem_init(mutex, 0, 1);sem_init(x, 0, 1);readers_cnt 0;for (int i 0; i RNUMS; i) {rids[i] i 1;} for (int i 0; i WNUMS; i) {wids[i] i 1;}
}void* Treader(void* ID)
{while (1) {P(mutex);readers_cnt;if (readers_cnt 1) P(x);V(mutex);printf(Reader %d: read\n, *(int*)ID);P(mutex);readers_cnt--;if (readers_cnt 0) V(x);V(mutex);}pthread_exit(NULL);
}void* Twriter(void* ID)
{while (1) {P(x);printf(Writer %d: write\n, *(int*)ID);V(x);}pthread_exit(NULL);
}int main()
{init();pthread_t ws[WNUMS], rs[RNUMS];for (int i 0; i WNUMS; i) {pthread_create(ws[i], NULL, Twriter, wids[i]);}for (int i 0; i RNUMS; i) {pthread_create(rs[i], NULL, Treader, rids[i]);}for (int i 0; i WNUMS; i) {pthread_join(ws[i], NULL);}for (int i 0; i RNUMS; i) {pthread_join(rs[i], NULL);}return 0;
}非常简单的实现对于当前设定的10个读者和3个写者的情况下观察一段时间输出会发现几乎根本就不存在写者写入的情况这是由于读者的锁很明显比排他锁更好获得对于更易达成的条件从概率和期望的角度上来说实现的次数也应该会更多 这就有问题了写者想要获取排他锁看样子非常困难甚至说我们可以构造一个读顺序让写者几乎不可能获取到排他锁有五个线程四个读线程和一个写线程两个读线程为了保障读取到的数据永远是最新的总是会每隔一分钟读取一次但是非常巧妙的是这四个读线程始终有一小段时间是重合的在这种情况下因为引用计数一直不能清零所以排他锁一直不能被获取此时就造成了写者的饥饿问题
3.饥饿现象和解决方案 上面已经相对比较详细地描述了饥饿现象的产生那么一个解决方案是这样的我既然饥饿现象起源于读者和写者获取锁的难度不公平那我们就让二者再次公平在写者全程加上wait_mutex锁在读者试图增加读者数量的时候也加上wait_mutex锁因此我们可以写出下面的代码
#include stdio.h
#include semaphore.h
#include pthread.h
#define P sem_wait
#define V sem_post
#define RNUMS 10
#define WNUMS 1
sem_t mutex, x, wait_mutex;
int readers_cnt;
int rids[RNUMS], wids[WNUMS];void init()
{sem_init(mutex, 0, 1);sem_init(x, 0, 1);sem_init(wait_mutex, 0, 1);readers_cnt 0;for (int i 0; i RNUMS; i) {rids[i] i 1;} for (int i 0; i WNUMS; i) {wids[i] i 1;}
}void* Treader(void* ID)
{while (1) {P(wait_mutex);P(mutex);readers_cnt;if (readers_cnt 1) P(x);V(mutex);V(wait_mutex);printf(Reader %d: read\n, *(int*)ID);P(mutex);readers_cnt--;if (readers_cnt 0) V(x);V(mutex);}pthread_exit(NULL);
}void* Twriter(void* ID)
{while (1) {P(wait_mutex);P(x);printf(Writer %d: write\n, *(int*)ID);V(x);V(wait_mutex);}pthread_exit(NULL);
}int main()
{init();pthread_t ws[WNUMS], rs[RNUMS];for (int i 0; i WNUMS; i) {pthread_create(ws[i], NULL, Twriter, wids[i]);}for (int i 0; i RNUMS; i) {pthread_create(rs[i], NULL, Treader, rids[i]);}for (int i 0; i WNUMS; i) {pthread_join(ws[i], NULL);}for (int i 0; i RNUMS; i) {pthread_join(rs[i], NULL);}return 0;
}在原先代码的基础上简单加上了一个新的wait_mutex作为写者的特权当写时就会申请wait_mutex作为特权因此读者和写者在初始状态需要竞争这把互斥锁在写者竞争到后读者就无法继续操作无法增加读者数量直到写线程的写结束由此一来发现由于写者和读者的竞争再次公平因此写者的写入次数明显提升对比原先代码的写读比1:10的情况后者的结果中写入次数明显增加
总结 读者—写者问题是一类非常经典的问题实际上代表了一系列的文件共享的互斥问题在数据库系统当中经常性地查表和写表也属于读者—写者问题的实例数据库还会采取更多的措施来增加数据库的并发效率因为目前我们的解决方案上的锁实际上是整个数据库的锁为了同时让更多读写操作能够进行数据库采取了表级锁和行级锁这些更加细粒度的锁例如同处在同一个文件的一张表中有两行数据但是一个事务读取行1而另一个事务写入行2这两个操作实际上不会冲突而采取简单的锁直接锁住会明显降低这个操作的效率
II.Peterson算法实现
1.Peterson算法问题与分析
(1).如何无锁访问临界区呢 当两个进程/线程希望访问同一个临界区的时候应该怎么让这两个线程能够在不发生冲突的情况下获得临界区的数据呢在Peterson算法之前出现的大部分解决方案实际上都不能完美地解决问题虽然Peterson算法本身也只能用于解决两个进程之间的互斥问题但它的确完成了任务。
(2).Peterson算法的基本逻辑 所以Peterson算法本身究竟做了什么呢Peterson算法融合了意向和严格轮换的想法对于希望访问临界区的变量首先它需要将自己的访问意向设置为true在这之后有两种方案本质一样只是实际意义不同将自己的进程代号放进turn变量将对方的进程代号放进turn变量在这两个步骤之后每个线程就可以去检测对方是否有意向访问 目前轮到了对方访问如果这个条件满足则需要循环等待。
(3).写对方/自己进程号的区别是 所以把对方的和自己的进程号写入turn变量的区别在哪呢其实比较简单因为对于同一个变量的写入有一个先来后到的顺序如果两个进程均写入对方的进程号则手快的进程会优先把对方进程号写在turn中手慢的会在自己进程号已经被写入turn之后把对方的进程号再写入turn当中这种情况下进程对于临界区的访问是抢占式的也就是谁的速度更快谁就能抢到临界区进行访问。 而两个进程均写入自己的进程号则是遵循了让步的原则因为对于上述的情况手快的进程会优先把自己的进程号写在turn中手慢的则会在对方进程号已经被写入turn之后把自己的进程号再写入turn当中这种情况下相当于手快的进程把临界区的访问权让给了手慢的进程。 所以这两种方案其实区别不是很大只要我们没有一个进程放自己进程号一个进程放对方进程号就不会出现很大的问题。
2.只包含意向的解决方案 所以我们知道只包含意向的解决方案是会出问题的我们可以用下面的代码进行尝试
#include stdio.h
#include pthread.h
#include stdbool.h
bool flags[2] {false, false};void* T1()
{while (true) {flags[0] true;while (flags[1]);printf(T1 access!\n);flags[0] false; }pthread_exit(NULL);
}void* T2()
{while (true) {flags[1] true;while (flags[0]);printf(T2 access!\n);flags[1] false; }pthread_exit(NULL);
}int main()
{pthread_t p1, p2;pthread_create(p1, NULL, T1, NULL);pthread_create(p2, NULL, T2, NULL);pthread_join(p1, NULL);pthread_join(p2, NULL);return 0;
}非常好代码T1访问了一次就顺利地进入了死锁的阶段 我用死锁这个词可能都不太好因为这个解决方案连锁都没有用开个玩笑。那到底为什么会出这个问题呢其实很简单因为我们在等待的时候用了一个完全没法完成互斥的操作—我们只关注对方是不是true如果true就不访问那如果两个线程都有意向访问相当于谁都进不去换言之这个方法完全没有解决互斥问题只是检测是否别人可能在访问罢了。
3.严格轮换法 这个方法看起来好像要正确一点点它的代码如下
#include stdio.h
#include pthread.h
#include stdbool.h
int turn;void* T1()
{while (true) {while (turn ! 0);printf(T1 access!\n);turn 1; }pthread_exit(NULL);
}void* T2()
{while (true) {while (turn ! 1);printf(T2 access!\n);turn 0;}pthread_exit(NULL);
}int main()
{turn 0;pthread_t p1, p2;pthread_create(p1, NULL, T1, NULL);pthread_create(p2, NULL, T2, NULL);pthread_join(p1, NULL);pthread_join(p2, NULL);return 0;
}从结果上看它好像还真没出问题严格轮换法的确可以让不同的进程轮流访问临界区但问题在于这种方法会在轮不到某个进程的时候让进程持续进入轮询阶段这会造成CPU的忙等待浪费了CPU的资源这种策略之下快的进程总是不能优先地完成任务从而造成一定的浪费和调度问题。
4.完整的Peterson算法 来吧让竞争更激烈一点。Peterson算法实际上完成了上述两种方法的融合它的代码实现如下
#include stdio.h
#include pthread.h
#include stdbool.h
#include unistd.h
bool flags[2] {false, false};
int turn;
int cnt 0;void* T1()
{while (true) {flags[0] true;turn 1;while (flags[1] turn 1);sleep(1);printf(T1 access! cnt %d\n, cnt);flags[0] false;}pthread_exit(NULL);
}void* T2()
{while (true) {flags[1] true;turn 0;while (flags[0] turn 0);printf(T2 access!\n);flags[1] false;}pthread_exit(NULL);
}int main()
{pthread_t p1, p2;pthread_create(p1, NULL, T1, NULL);pthread_create(p2, NULL, T2, NULL);pthread_join(p1, NULL);pthread_join(p2, NULL);return 0;
}结果看起来已经很正确了它基本完成了Peterson算法的思想好像问题到这儿就解决了对吗这台机器运行在x86-64架构的处理器下实际上x86-64架构的CPU保证了至少对于int类型的load和store操作是原子的如果它们不是原子的会发生什么具体的实例我没有查到相关的资料我也没有成功复现出来之后我可能还会继续研究一下。
总结 Peterson算法的确是真正通过软件的方式完成了临界区互斥访问的问题不过编译器并不一定能够让我们的指令依照顺序执行编译器可能会对我们写的代码进行乱序而这样的乱序可能导致load和store指令顺序调整而导致Peterson算法失效我们可能需要使用
__sync_synchronize();
// 或者
asm(mfence);利用内存屏障指令从而避免对指令顺序进行优化从而避免出现关键指令乱序执行的问题所以Peterson算法的实现可能还是需要一些特别的软硬件结合以避免出现乱序的问题。
参考资料
1.并发控制基础 (Peterson 算法、模型检验、原子操作)2.博客园—内存栅栏memory barrier解救peterson算法的应用陷阱 3.知乎—对int变量赋值的操作是原子的吗
