Download presentation
Presentation is loading. Please wait.
1
临界区软件互斥软件实现算法 主讲教师：夏莹杰
2
Algorithm 1 定义两进程共享数据 进程 Pi int turn; 并且取初值 turn = 0
turn = i 进程Pi 可以进入临界区 进程 Pi do { while (turn != i) ; critical section turn = j; remainder section } while (1);
3
Algorithm 1（续） 进程 Pj do { while (turn != j) ; critical section
turn = i; remainder section } while (1); 满足Mutual Exclusion, 但不满足Progress 为什么 ？
4
Algorithm 2 两进程共享数据 boolean flag[2]; 并且取初值 flag [0] = flag [1] = false
flag [i] = true 表示进程Pi 发出申请，希望进入临界区执行
![Algorithm 2 两进程共享数据 boolean flag[2]; 并且取初值 flag [0] = flag [1] = false](http://slidesplayer.com/slide/15525100/93/images/4/Algorithm+2+%E4%B8%A4%E8%BF%9B%E7%A8%8B%E5%85%B1%E4%BA%AB%E6%95%B0%E6%8D%AE+boolean+flag%5B2%5D%3B+%E5%B9%B6%E4%B8%94%E5%8F%96%E5%88%9D%E5%80%BC+flag+%5B0%5D+%3D+flag+%5B1%5D+%3D+false.jpg "flag [i] = true. 表示进程Pi 发出申请，希望进入临界区执行.")
5
Algorithm 2（续） 进程 Pi do { flag[i] = true; while (flag[j]) ; critical section flag [i] = false; remainder section } while (1);
![Algorithm 2（续） 进程 Pi. do { flag[i] = true; while (flag[j]) ; critical section. flag [i] = false;](http://slidesplayer.com/slide/15525100/93/images/5/Algorithm+2%EF%BC%88%E7%BB%AD%EF%BC%89+%E8%BF%9B%E7%A8%8B+Pi.+do+%7B+flag%5Bi%5D+%3D+true%3B+while+%28flag%5Bj%5D%29+%3B+critical+section.+flag+%5Bi%5D+%3D+false%3B.jpg "remainder section. } while (1);")
6
Algorithm 2（续） 进程 Pj do { flag[j] := true; while (flag[i]) ; critical section flag [j] = false; remainder section } while (1); 满足Mutual Exclusion, 但不满足Progress 为什么 ？
![Algorithm 2（续） 进程 Pj. do { flag[j] := true; while (flag[i]) ; critical section. flag [j] = false;](http://slidesplayer.com/slide/15525100/93/images/6/Algorithm+2%EF%BC%88%E7%BB%AD%EF%BC%89+%E8%BF%9B%E7%A8%8B+Pj.+do+%7B+flag%5Bj%5D+%3A%3D+true%3B+while+%28flag%5Bi%5D%29+%3B+critical+section.+flag+%5Bj%5D+%3D+false%3B.jpg "remainder section. } while (1); 满足Mutual Exclusion, 但不满足Progress. 为什么 ？")
7
Peterson算法 两进程共享数据 int turn; Boolean flag[2]
变量turn(只能取 i 或 j )指示两个进程中的哪一个可以进入临界区 数组flag指示进程是否申请进入临界区。也就是说，flag[i] = true 表示进程Pi申请进入临界区
![Peterson算法 两进程共享数据 int turn; Boolean flag[2]](http://slidesplayer.com/slide/15525100/93/images/7/Peterson%E7%AE%97%E6%B3%95+%E4%B8%A4%E8%BF%9B%E7%A8%8B%E5%85%B1%E4%BA%AB%E6%95%B0%E6%8D%AE+int+turn%3B+Boolean+flag%5B2%5D.jpg "变量turn(只能取 i 或 j )指示两个进程中的哪一个可以进入临界区. 数组flag指示进程是否申请进入临界区。也就是说，flag[i] = true 表示进程Pi申请进入临界区.")
8
Peterson算法定义进程Pi while (true) { flag[i] = TRUE; turn = j;
while ( flag[j] && turn == j); CRITICAL SECTION flag[i] = FALSE; REMAINDER SECTION }
![Peterson算法定义进程Pi while (true) { flag[i] = TRUE; turn = j;](http://slidesplayer.com/slide/15525100/93/images/8/Peterson%E7%AE%97%E6%B3%95%E5%AE%9A%E4%B9%89%E8%BF%9B%E7%A8%8BPi+while+%28true%29+%7B+flag%5Bi%5D+%3D+TRUE%3B+turn+%3D+j%3B.jpg "while ( flag[j] && turn == j); CRITICAL SECTION. flag[i] = FALSE; REMAINDER SECTION. }")
9
Peterson算法定义进程Pj while (true) { flag[j] = TRUE; turn = i;
while ( flag[i] && turn == i); CRITICAL SECTION flag[j] = FALSE; REMAINDER SECTION }
![Peterson算法定义进程Pj while (true) { flag[j] = TRUE; turn = i;](http://slidesplayer.com/slide/15525100/93/images/9/Peterson%E7%AE%97%E6%B3%95%E5%AE%9A%E4%B9%89%E8%BF%9B%E7%A8%8BPj+while+%28true%29+%7B+flag%5Bj%5D+%3D+TRUE%3B+turn+%3D+i%3B.jpg "while ( flag[i] && turn == i); CRITICAL SECTION. flag[j] = FALSE; REMAINDER SECTION. }")
10
Peterson算法满足： “互斥”(Mutual Exclusion)。为什么？ “空闲让进”(Progress) 。为什么？
“有限等待”(Bounded Waiting) 。为什么？
11
END
Similar presentations
