怎么自己做投票网站,推广公众号,企业网站建设遵循的原则,网站后台基本功能互斥#xff1a;软件解决方法
算法一
算法思路
预留一个全局内存区域#xff0c;并标记为turn。进程#xff08;P0或P1#xff09;想进入它的临界区执行时#xff0c;要先检查turn的内容。若turn的值等于进程号#xff0c;则该进程可以进入它的临界区#xff1b;否则…互斥软件解决方法
算法一
算法思路
预留一个全局内存区域并标记为turn。进程P0或P1想进入它的临界区执行时要先检查turn的内容。若turn的值等于进程号则该进程可以进入它的临界区否则该进程被强制等待。等待进程重复地读取turn的值。直到被允许进入临界区。这一过程称为忙等待busy waiting 或 自旋等待spin waiting进程在获得临界区的访问权并完成访问后必须为另一个进程更新turn的值。
P0 :
while(turn ! 0) {/* busy waiting */}
/* critical section */
turn 1;P1 :
while(turn ! 1) {/* busy waiting */}
/* critical section */
turn 0;缺陷
进程必须严格交替P0临界区执行完后才会更新turn值使得P1跳出忙等待状态同理P0也需等待P1临界区执行完使用它们的临界区因此执行的步调由两个进程较慢的进程决定。 例如若P0在1小时内仅使用临界区1次而P1要以1000次/小时的速率使用临界区则P1就必须适应P0的节奏。
BUG
若一个进程终止则另一个进程就会被永久阻塞。无论进程是在临界区内终止还是在临界区之外终止都会发生这种情况。 例如P0在执行到第二行代码临界区内时终止此时turn值为0且此后不会被更新因此P1将永久处于忙等待状态P0在执行到第三行代码临界区外时终止此时turn值为1于是P1进入临界区执行完后便将turn值置为0而P0进程因为终止便不会再更新turn值因此P1将永久处于忙等待状态。
算法二
算法一仅由一个共享的仲裁变量去实现进程间的互斥因此进程之间必须严格交替执行进程之间的依赖关系过强
算法二为每一个进程都配备了专门的”钥匙“这里定义一个bool数组flagflag[0]与P0关联flag[1]与P1关联每个进程可检查但不能改变另一个进程的flag值
算法思路
一个进程要进入临界区时它会周期性地检查另一个进程的flag直到其值为false这表明另一个进程不在临界区内。检查进程立即设置自己的flag为true进入自己的临界区。离开临界区时将自己的flag设置为false。
P0 :
while(flag[1]) {/* busy waiting */}
flag[0] true;
/* critical section */
flag[0] false;P1 :
while(flag[0]) {/* busy waiting */}
flag[1] true;
/* critical section */
flag[1] false;进步
若一个进程在临界区外终止包括设置flag代码时则另一个进程不会被阻塞。 例如当P1在执行完第4行代码后终止此后flag[1]将一直保持false因此P0将永远不会进入忙等待状态即说明其不会被阻塞
BUG
若一个进程在临界区内或在进入临界区之前已将flag设置为true时终止则另一个进程就会永久阻塞没有保证互斥 例如P1执行完第4行代码后于是P0跳出忙等待状态但P0还未来得及执行第二行代码将flag[0]设置为trueP1便又进入了临界区随后P0也进入临界区便产生了访问冲突
下面采用Java多线程编程模拟算法二并验证BUG-2
package TEST;public class Multithreading {public static void main(String[] args) {Process p0 new Process(P0, 0, 0);Process p1 new Process(P1, 1, 1);p0.start();p1.start();}
}
class Process extends Thread {private static int var;private int var_right;private static boolean[] flag new boolean[2];private String name;private int cnt_test 100;private int No;private int No_other;public Process(String name, int No, int var_right) {super();this.name name;this.No No;this.var_right var_right;this.No_other (No 1) % 2;}public void run() {for(int i 0; i cnt_test; i) {while(flag[No_other]) { /* busy waiting */ }flag[No] true;/*--- critical section begin---*/var var_right;System.out.println(this.name : (var var_right? var : ##));/*--- critical section end---*/flag[No] false;}}
}两个线程任务是将公共变量var赋值为本线程对应正确的值var_right并输出当前var的值若两个线程保证互斥则var总是等于var_rightCondition ‘var var_right’ is always ‘true’即不会输出##
运行结果如下
P0:0
P1:##
P0:0
P1:1
P0:0
P1:##
P0:0
P1:##
P0:0
P0:0
P0:0
P1:##
P1:##
P0:0
P1:1
P1:1
P0:##
P1:1
P1:1
P1:1
P0:##
P0:##
P1:1
P0:0
P1:1
P1:##
P0:0
P1:##
P0:0
P1:1
P1:##
P0:0
P1:1
P0:##
P1:1
P0:##
P1:1
P1:##
P0:0
P0:0
P1:##
P0:0
P1:1
P1:##
P0:0
P0:0
P1:##
P0:0
P1:1
P1:##
P0:0
P1:##
P0:0
P1:1
P1:##
P0:0
P1:##
P0:0
P1:1
P0:0
P1:1
P1:##
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P1:1
P0:0
P1:1
P0:0
P0:0
P1:1
P1:1
P1:1
P0:0
P1:##
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:##
P0:0
P1:1
P1:##
P0:0
P1:1
P1:##
P0:0
P1:1
P1:##
P0:0
P1:1
P1:1
P1:##
P0:0
P1:1
P1:1
P0:0
P1:##
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:##
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P1:1
P0:##
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:1
P1:##
P0:0
P1:1
P1:##
P0:0
P1:1
P1:1
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0
P0:0Process finished with exit code 0可见采用算法二两个线程之间发生了不少次的访问冲突输出##
算法三
算法二由于执行速率不匹配的原因导致两个进程同时处在临界区的位置所以算法二的方案失败
算法三通过简单地交换两条语句来解决这一问题
算法思路
将控制其他进程持续忙等待的语句提到了检查flag值之前确保了同一时刻只有一个进程进入临界区
P0 :
flag[0] true;
while(flag[1]) {/* busy waiting */}
/* critical section */
flag[0] false;P1 :
flag[1] true;
while(flag[0]) {/* busy waiting */}
/* critical section */
flag[1] false;进步
解决算法二造成的访问冲突问题确保了互斥性
BUG
与算法二一样某一进程在临界区内或在设置flag为true时终止会引起其他进程永久阻塞若每个进程在执行while语句前都将flag设置为true则每个进程都会认为另一个进程已经进入临界区进而引发死锁 例如P0执行完第一行代码后还未来得及执行while语句P1也执行完了第一行代码此时flag[0]与flag[1]的值都为true因此两个进程都无法跳出忙等待的状态从而造成死锁
下面采用Java多线程编程模拟算法三并验证BUG-2
package TEST;public class Multithreading {public static void main(String[] args) {Process p0 new Process(P0, 0, 0);Process p1 new Process(P1, 1, 1);p0.start();p1.start();}
}
class Process extends Thread {private static int cnt_busy_wait 0;private static int var;private int var_right;private static boolean[] flag new boolean[2];private String name;private int cnt_test 100;private int No;private int No_other;public Process(String name, int No, int var_right) {super();this.name name;this.No No;this.var_right var_right;this.No_other (No 1) % 2;}public void run() {for(int i 0; i cnt_test; i) {flag[No] true;while(flag[No_other]) {/* busy waiting */System.out.println(this.name BusyWaiting: (cnt_busy_wait));if(cnt_busy_wait 999) return;}/*--- critical section begin---*/var var_right;System.out.println(this.name : (var var_right? var : ##));/*--- critical section end---*/flag[No] false;}}
}运行结果如下
P0:0
P1 BusyWaiting: 1
P1 BusyWaiting: 3
P1 BusyWaiting: 4
P1 BusyWaiting: 5
P0 BusyWaiting: 2
P0 BusyWaiting: 7
P0 BusyWaiting: 8
P0 BusyWaiting: 9
P0 BusyWaiting: 10
P1 BusyWaiting: 6
P1 BusyWaiting: 12
P1 BusyWaiting: 13
P0 BusyWaiting: 11... ...P1 BusyWaiting: 995
P1 BusyWaiting: 996
P1 BusyWaiting: 997
P1 BusyWaiting: 998
P1 BusyWaiting: 999
P1 BusyWaiting: 1000
P0 BusyWaiting: 967Process finished with exit code 0可见结果只被正确输出了一次此后两线程皆处在忙等待状态形成死锁
算法四
算法三中一个进程在设置其状态时是不知道另一个进程的状态的。由于每一个进程坚持要进入临界区导致死锁发生
算法四在算法三的基础上引入**“谦让”**的机制在忙等待中随时重设flag一定程度上避免了死锁发生
算法思路
当出现死锁情况时两者都进入忙等待状态P0进程将flag[0]置为false并在该状态延迟1秒P1便可在这1秒之内跳出忙等待状态从而避免了死锁的情况
P0 :
flag[0] true;
while(flag[1])
{flag[0] false;delay(1); // dalay 1 secflag[0] true;
}
/* critical section */
flag[0] false;P1 :
flag[1] true;
while(flag[0])
{flag[1] false;delay(1); // dalay 1 secflag[1] true;
}
/* critical section */
flag[1] false;进步
一定程度的避免了死锁的出现
缺陷
当两个进程自上而下的语句几乎同时被执行时则两者都不会进入临界区。严格来说这不是死锁因为两个进程执行速率的相对变化会打破这种状况允许其中一个进程进入临界区这种状态称为活锁livelock尽管该场景不会维持很长时间但仍然是一种有可能发生的情形
Dekker 算法
算法四可能会出现 “互相谦让” 的情况
Dekker算法通过turn变量表示哪个进程有权进入它的临界区避免了**“互相谦让”**的情况
算法思路
当P0要进入它的临界区时将其flag设置为true然后检查P1的flag。若为falseP0可以立即进入它的临界区否则P0要检查turn若发现turn为0则P0要持续周期性地检查P1的flag。而P1需要延期执行并将flag设置为false让P0执行。P0完成临界区执行后将其flag设置为false以释放临界区并将turn设置为1把权力转交给P1
bool flag[2];
int turn;
void P0()
{while (true){flag[0] true;while (flag[1]){if (turn 1){flag[0] false;while(turn 1) { /* busy waiting */ }flag[0] true;}}/* critical section */turn 1;flag[0] false;}
}
void P1()
{while (true){flag[1] true;while (flag[0]){if (turn 0){flag[1] false;while (turn 0) { /* busy waiting */ }flag[1] true;}}/* critical section */turn 0;flag[1] false;}
}
int main()
{flag[0] false;flag[1] false;turn 1;parbegin(P0, P1); // concurrent executionreturn 0;
}Peterson 算法
Dekker 算法解决了互斥问题但复杂的程序很难实现且其正确性也很难证明。Peterson提出了一个简单且精致的算法。和前面一样全局数组变量flag表明每个互斥进程的位置全局变量turn解决同时发生的冲突。
bool flag[2];
int turn;
void P0()
{while(true){flag[0] true;turn 1;while(flag[1] turn 1) {/* busy waiting */}/* critical section */flag[0] false;}
}
void P1()
{while(true){flag[1] true;turn 0;while(flag[0] turn 0) {/* busy waiting */}/* critical section */flag[1] false;}
}
int main()
{flag[0] false;flag[1] false;parbegin(P0, P1); // concurrent executionreturn 0;
}最后两种正确算法相关内容验证、说明等待更新… …
