Dekker互斥算法学习笔记

2023-09-22 21:05| 来源: 网络整理| 查看: 265

Dekker算法用来解决进程/线程互斥问题。我们给出以下伪代码：

int n = 2; // n表示进程数，这里以2个进程为例 vector flag(n, false); // 提供所有进程的状态，即是否举手，表明自己想进入临界段。初始都为false。 bool turn; // 轮转变量，表示哪个进程应该坚持进入 // 这里只列举一个进程的代码段 void process(int me) { int other = 1 - me; while(true) { flag[me] = true; // 表明自己进入临界区的意愿 while (flag[other] == true) { // 检查对方是否举手，若举手检查是否礼让 if (turn == other) { // 说明轮到对方进入临界区，我方礼让 flag[me] = false; // 我方放手 while (turn == other) { // 还在使用，我们等待对方结束 // do nothing } flag[me] = true; // 使用结束，我方举手 } } // 此时turn已经为自己的轮次，进入临界区 // enter critical section; turn = other; // 将轮次移交给别人。 flag[me] = false; // 我们使用结束，放手 } } int main() { turn = 1; // parbegin; process(0);process(1); // parend return 0; }

这是一种竞争时轮转的算法，flag保证互斥，用于进程间的状态交流。当有一个进程先设置为true并通过测试时，另一进程无论如何都无法通过测试。

通过turn变量解决了死锁以及无限等待的问题，

while(flag[other] == true){ //检查对方是否举手，若举手检查是否礼让 if(turn == other){ //目前对方的轮次，我方礼让 } }

决定了这样一个竞争时轮转的机制，如果没有这个turn变量，有可能两个进程同时步入while而出现死锁。它决定了当 flag[me] 与 flag[other] 同时为真时，即me和other同时被测试时，me的行为是放手礼让对方，还是等待对方放手。

当两个进程在同时竞争CPU资源时，不会导致假互斥，也不会说一方无限等待，另一方无限占用。可以理解成A与B两个人在门外想吃门内的蛋糕，while测试是一道门，flag是A与B当前意愿，当flag为true时表示想吃**（注意，并不是正在吃）**，false则是不吃，turn则表示刚刚吃完的对方（A刚刚吃过，则turn = B）。

那么我们就可以把算法理解为以下几种行为：

①A已进门后B准备进门：

p.如果A刚刚吃过一次了，B就站在门口等待，并且状态一直为想吃。等待A吃完出门且已将状态设置成不吃后直接进入开吃。

q.如果B刚刚吃过一次了，B就把状态设置为不吃，等A吃完后，重新设置成想吃，在门内重新接受测试**（可能又回到状态①，不过这次将步入p.）**

②A和B同时准备进门：假设这时turn == A，B刚刚吃过蛋糕

1.在接受测试时发现B刚吃过，于是A不礼让，状态一直为想吃，以此阻塞B。同时B在接受测试时发现自己刚刚吃过蛋糕，于是放手，状态设置为不吃并在测试里等待A。

2.A重新接受测试，这时B已经将状态设置为不吃，A进入吃蛋糕，吃好后出门，将状态设置为不吃，并且下一次若重新进入②，将会礼让B（turn == B）

从上面的讨论也可以看出来，轮转只会发生在同时接受测试时，其余情况下谁先拿到资格谁先进入临界区。记得区分状态p和状态q时A和B的行为。

int n = 2; vector flag(n, false); int turn; void process(int me) { int other = 1 - me; while(true) { flag[me] = true; while (father[other] == true) { if (turn == other) { flag[me] = false; while (turn == other) { // do nothing } flag[me] = true; } } // enter critical section turn = other; flag[me] = false; } }

【本文地址】

Dekker互斥算法学习笔记

Dekker互斥算法学习笔记

今日新闻

推荐新闻