网站结构是什么,贵阳网站开发公司,wordpress做登陆界面,陕西网站建设推广公司目录
参考文献
问题
解法与证明
易读版本 参考文献 Dijkstra于1965年发表文章Solution of a Problem in Concurrent Programming Control#xff0c;引出并发系统下的互斥(mutual exclusion)问题#xff0c;自此开辟了分布式计算领域Dijkstra在文中给出了基于共享存储原子…目录
参考文献
问题
解法与证明
易读版本 参考文献 Dijkstra于1965年发表文章Solution of a Problem in Concurrent Programming Control引出并发系统下的互斥(mutual exclusion)问题自此开辟了分布式计算领域Dijkstra在文中给出了基于共享存储原子性访问的解决方案只有十多行代码但阅读起来较难以理解在查阅若干资料后总结了一种较为直观的解释方法 问题 考虑N个节点(进程)每个都在运行一个无限循环的程序每轮循环当中都存在一个临界区(critical section)我们需要设计算法控制多个计算机中同时只有一台可以进入其临界区并需要满足下列条件 1-所有的节点是对称(symmetrical)的即我们不能引入类似于“1号节点优先于2号节点”的静态优先级配置2-各个节点的运行速度可能不同同一个节点在不同时刻的运行速度也可能不同3-任意节点在临界区外停止运行不应引起系统的死锁4-如果多个节点想要访问临界区必须在有限时间内决策出哪个节点优先访问各个节点之间可以通过共享存储(common store)通信共享存储提供以字(word)为单位的原子性读写 当今现在在基于共享内存通信的单机多进程上我们可以很方便的使用基于TAS(TestSet)或CAS(CopySwap)实现的互斥锁mutex来实现临界区互斥访问然而在只有对内存单元原子读写的条件下如何完成互斥访问呢Dijkstra给出了他的解法 解法与证明 在共享存储上Dijkstra使用了两个长度为N的布尔数组和一个整数 其中k 满足 1⩽k⩽Nb[i] 和 c[i] 只被节点 i 修改且初始值为true对于第 i 个节点(1⩽i⩽N)执行下面的代码 Dijkstra原文中给出的证明集中论证两点 第一所有节点互斥访问临界区第二不会出现系统死锁建议大家可以先结合代码看下原文中证明 易读版本 在此为了便于理解对原代码做了如下修改 修改为c语言版本将数组和节点下标修改为通用的 0,1,…,N−1将数组 b 改名为 want_to_enter_critical_section(希望进入临界区)数组 c 改名为 in_critical_section(在临界区)将 b 和 c 数组的初始值改为 false 并翻转代码中所有的布尔值即 false 改为 truetrue 改为 false 证明 1. mutual exclusion(互斥) 如果程序想运行到critical section则必须运行通过 Li4 中的代码且不返回 Li1即除了自身的 in_critical_section[i] 为 true 外其余所有节点的 in_critical_section[i] 均为 false2. non-blocking(非阻塞) 如果第 k 个节点不在 Li0~Li4 的循环中则 want_to_enter_critical_section 为 false所有在循环中的节点会在 Li1 判定 (k ! i)其中的一个或多个节点会执行到 Li3 其中某个节点将设定 k i此后 want_to_enter_critical_section[k] 为 true其他节点无法再更改 k 直至离开critical section后将 want_to_enter_critical_section[k] 为 false在 k 被确定后第k个节点会不断尝试 Li4 中的代码直至其余所有的 in_critical_section[i] 全部为 false这种情况必然会发生不论临界区中的节点离开临界区还是临界区外的发现 Li1: k ! i都会执行 in_critical_section[i] false;证毕并发情况 这里Dijstra原文中没有明确指出的是考虑并发情况下两个节点 x 和 y 同时运行 Li4 中代码则会出现下面的情况此种情况下两个节点都 goto Li1x 和 y 中不等于 k 的节点会执行 Li2从而使得节点 k 在下次执行 Li4 时成功通过进入临界区
