临界区软件互斥软件实现算法 主讲教师：夏莹杰 xiayingjie@zju.edu.cn
Algorithm 1 定义两进程共享数据 进程 Pi int turn; 并且取初值 turn = 0 turn = i 进程Pi 可以进入临界区 进程 Pi do { while (turn != i) ; critical section turn = j; remainder section } while (1);
Algorithm 1（续） 进程 Pj do { while (turn != j) ; critical section turn = i; remainder section } while (1); 满足Mutual Exclusion, 但不满足Progress 为什么 ？
Algorithm 2 两进程共享数据 boolean flag[2]; 并且取初值 flag [0] = flag [1] = false flag [i] = true 表示进程Pi 发出申请，希望进入临界区执行
Algorithm 2（续） 进程 Pi do { flag[i] = true; while (flag[j]) ; critical section flag [i] = false; remainder section } while (1);
Algorithm 2（续） 进程 Pj do { flag[j] := true; while (flag[i]) ; critical section flag [j] = false; remainder section } while (1); 满足Mutual Exclusion, 但不满足Progress 为什么 ？
Peterson算法 两进程共享数据 int turn; Boolean flag[2] 变量turn(只能取 i 或 j )指示两个进程中的哪一个可以进入临界区 数组flag指示进程是否申请进入临界区。也就是说，flag[i] = true 表示进程Pi申请进入临界区
Peterson算法定义进程Pi while (true) { flag[i] = TRUE; turn = j; while ( flag[j] && turn == j); CRITICAL SECTION flag[i] = FALSE; REMAINDER SECTION }
Peterson算法定义进程Pj while (true) { flag[j] = TRUE; turn = i; while ( flag[i] && turn == i); CRITICAL SECTION flag[j] = FALSE; REMAINDER SECTION }
Peterson算法满足： “互斥”(Mutual Exclusion)。为什么？ “空闲让进”(Progress) 。为什么？ “有限等待”(Bounded Waiting) 。为什么？
END