进程互斥的软件实现方法-第二十六天

目录

前言

单标志法（谦让）

双标志先检查法（表达意愿）

双标志后检查法（表达意愿）

Peterson算法（集大成者）

本节思维导图

---

前言

????????单标志法、双标志的先后检查法中，如果单个进程能一气呵成的执行完是没有问题的，但是如果出现进程切换的问题就会导致它们产生问题

单标志法（谦让）

谦让

基本思想：两个进程在访问完临界区后会把适用临界区的权限转交给另一个进程，即每个进程进入临界区的权限只能被另一个进程赋予

int turn = 0; //表示当前允许进入临界区的进程号

//P0进程
while (turn != 0)①   //进入区
critical section;②   //临界区
turn = 1;        ③   //退出区
remainer section;④   //剩余区


//P1进程
while(true != 1)  ⑤   //进入区
ctritical section;⑥   //临界区
true = 0;         ⑦   //退出区
remainder section;⑧   //剩余区

解释：trun初始值为0，即刚开始只允许P0进程进入临界区。若P0进程分配的时间片用完，P1进程要上处理机运行，则它会一直停留在⑤，直到分配给P1的时间片耗尽，然后又切换P0上处理机运行。只有在P0在退出区将true改为1后，P1才能进入临界区

结论：该算法可以实现“同一时刻最多只允许一个进程访问临界区”

缺点：违反“空闲让进”原则（只能按p0->p1->p0->p1->...这样轮流访问，这就会导致如果此时允许进入临界区的进程是p0，而p0一直不访问临界区，，那么虽然此临界区空闲，但是并不允许p1访问）

双标志先检查法（表达意愿）

表达意愿

基本思想：设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想要进入临界区的意愿，比如"flag[0] = true" 意味着0号进程P0现在想要进入临界区，每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志“flag[i]”设置为true，之后开始访问临界区

bool flag[2];      //表示进入临界区意愿的数组
flag[0] = false;   
flag[1] = false;   //初始时两进程都不想进入临界区

//P0进程
while(flag[1]);  ① //P0进程检查P1进程是否要访问临界区，如果对方不想访问就就进行②
flag[0] = true;  ② //P0进程将自己的意愿修改为true"上锁"，此时P1进程就循环等待
critical section;③ //P0进程访问临界区
flag[0] = flase; ④ //P0进程完成对临界区的访问"解锁"
remainder section;

//P1进程
while(flag[0]);  ⑤ //P1进程检查P0进程是否要访问临界区，如果对方不想访问就就进行⑥
flag[1] = true;  ⑥ //P1进程将自己的意愿修改为true"上锁"，此时P0进程就循环等待
critical section;⑦ //P1进程访问临界区
flag[1] = flase; ⑧ //P1进程完成对临界区的访问"解锁"
remainder section;

缺点：违反”忙则等待“原则（如果两个进程并发执行，当P0进程执行完①还未执行②时时间片用完，切换至P1进程执行⑤但是P1进程执行完⑤未执行⑥时时间片也用完，然后重新切换至P0进程执行②，此时P0进程的意愿被改变为true，然后再切换至P1进程执行⑥，此时P1进程的意愿也被改为true，然后可能暂时不发生进程切换而是进入临界区，但是P1进程在访问临界区过程中又发生了进程切换此时P0进程也进入临界区访问资源，这就会导致P0与P1进程会同时访问临界区，这是不对的）

产生原因：”检查“和”上锁“两个处理不是一气呵成的，在”检查“后”上锁“前，可能会发生进程切换

双标志后检查法（表达意愿）

表达意愿

基本思想：双标志检查法的改版，前者的问题在于是先”检查“后”上锁“，但是这样两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题，双标志后检查法是先”上锁“后”检查“的方法来避免上述问题

bool flag[2];      //表示进入临界区意愿的数组
flag[0] = false;   
flag[1] = false;   //初始时两进程都不想进入临界区

//P0进程
flag[0] = true;  ① //P0进程将自己的意愿修改为true"上锁"，此时P1进程就循环等待
while(flag[1]);  ② //P0进程检查P1进程是否要访问临界区，如果对方不想访问就就进行③
critical section;③ //P0进程访问临界区
flag[0] = flase; ④ //P0进程完成对临界区的访问"解锁"
remainder section;

//P1进程
flag[1] = true;  ⑤ //P1进程将自己的意愿修改为true"上锁"，此时P0进程就循环等待
while(flag[0]);  ⑥ //P1进程检查P0进程是否要访问临界区，如果对方不想访问就就进行⑦
critical section;⑦ //P1进程访问临界区
flag[1] = flase; ⑧ //P1进程完成对临界区的访问"解锁"
remainder section;

优点：解决了”忙则等待“原则

缺点：违反了”空闲让进“和”有限等待“原则（如果由于进程切换导致要按照①⑤②⑥...的顺序执行那么两个进程都长期无法访问临界资源而产生“饥饿”现象）

Peterson算法（集大成者）

表达意愿 + 谦让

基本思想：结合单标志法、双标志的先后表示法的思想，如果双方都争着想要进入临界区，那可以让进程尝试“谦让”

bool flag[2];   //表示进入临界区意愿的数组，初始值均为false，表达“意愿”
int turn = 0;   //turn表示优先让哪个进程进入临界区，表达“谦让”

//P0进程
flag[0] = true;             ①   //主动争取，将自己的意愿改为true
turn = 1;                   ②   //主动谦让，将先优先执行进程设置为1
while(flag[1] && turn == 1);③   //检查对方食肉也想使用，且最后一次是不是自己说了“客气话”
critical section;           ④
flag[0] = false;            ⑤
remainder section;

//P1进程
flag[1] = true;             ⑥
turn = 0;                   ⑦
while(flag[0] && turn == 0);⑧
critical section;           ⑨
flag[1] = false;            ⑩
remainder section;

解释：对于一气呵成的P0进程，P0进程将自己的意愿修改为true，然后将turn修改为P1进程表示自己的谦让，然后再检查“P1进程是否想要使用并且自己也表示了谦让”如果是那么P0进程就循环等待，如果不是那么P0进程就访问临界区最后再将自己的意愿设置为false

谁最后说了“客气话”，谁就失去了行动的优先权

优点：遵循了“空闲让进”、“忙则等待”、“优先等待”三个原则（如果按照①⑥②⑦⑧③...的顺序并发的执行进程：初始turn=0，P0进程修改意愿为true，P1进程也修改意愿为true，P0进程主动谦让将turn改为1表示让P1进程先执行，然后P1进程也主动谦让将turn改为0表示让P0进程先执行，接着P1进程检查发现“P0进程有执行的意愿并且我（P1）也表示了谦让让P0进程先执行”，所以P1进程就会进入循环等待，然后P0进程检查时就会发现“P1进程虽然也有执行的意愿但是P1进程表示了谦让让我（P0）先执行”，也就是说我（P0）就可以向下单独的访问临界区，即使再次切换至P1进程也只是在循环而不会进入临界区，直到我（P0）结束访问临界区后将自己的意愿改为false，P1进程在检查时才会跳出循环区访问临界区）

缺点：未遵循“让权等待”原则（当进程无法进入临界区，就立即释放处理机资源，令该进程下CPU，但是该算法是让该进程依然位于处理机上循环等待）

本节思维导图

~over~