进程互斥遵守的原则
空闲让进:临界区空闲时,应允许一个进程访问。
忙则等待:临界区正在被访问时,其他试图访问的进程需要等待。
有限等待:要在有限时间内进入临界区,包装不会饥饿。
让权等待:进不来临界区的进程,要释放处理机,防止忙等
两个进程在访问完临界区后会把使用临界区的权限交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。
int turn = 0; // turn 表示当前允许进入临界区的进程号
P0进程: while(turn != 0); 1 //进入区 critical section; 2 //临界区 turn = 1; 3 //退出区 remainder section 4 //剩余区
P1进程: while(turn != 1); 5 //进入区 critical section; 6 //临界区 turn = 0; 7 //退出区 remainder section; 8 //剩余区
turn 的初值为0,即刚开始只允许0号进程进入临界区。
若P1先上处理机运行,则会一直卡在5。直到P1的时间片用完,发生调度,切换P0上处理运行。
代码1不会卡住P0,P0可以正常访问临界区,在P0访问临界区期间即使切换回P1,P1依然会卡在5 。
因此,该算法可以实现"同一时刻最多只允许一个进程访问临界区"。
turn 表示当前允许进入临界区的进程号,而只有当前允许进入临界区的进程在访问了临界区之后,才会修改 turn 的值。也就是说,对于临界区的访问,一定是按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]); 1 // 如果P1已经进入临界区,P0就一直循环等待 flag[0] = true; 2 // 标记为P0进程想要进入临界区 critical section; 3 // 访问临界区 flag[0] = false; 4 // 访问完临界区,修改标记P0不想使用临界区 remainder section;
P0进程: while(flag[0]); 1 // 如果P0已经进入临界区,P1就一直循环等待 flag[1] = true; 2 // 标记为P1进程想要进入临界区 critical section; 3 // 访问临界区 flag[1] = false; 4 // 访问完临界区,修改标记P1不想使用临界区 remainder section;
若按照1、5、2、6、3、7......的顺序执行,P0和P1将会同时访问临界区。
因此,双标志先检查法的主要问题是:违法"忙则等待"原则。
原因在于,进入区的"检查"和"上锁"前后可能发生进程的切换。
双标志先检查法的改版。前一个算法的问题是先"检查"后"上锁",但是这两个操作又无法一气呵成,因此导致了两个进程同时进入临界区的问题。因此,人们又想到先"上锁"后"检查"的方法,来避免上述问题。
bool flag[2]; //表示进入临界区意愿的数组 flag[0] = false; flag[1] = false; //刚开始设置为两个进程都不想进入临界区
P0进程: flag[0] = true; 1 while(flag[1]); 2 critical section; 3 flag[0] = false; 4 remainder section;
P1进程: flag[1] = true; 5 //标记为P1进程想进入临界区 while(flag[0]); 6 //如果P0也想进入临界区,则P1循环等待 critical section; 7 //访问临界区 flag[1] = false; 8 //访问完临界区,修改标记为P1不想使用临界区 remainder section;
若按照1、5、2、6...的顺序执行,P0和P1将都无法进入临界区。
因此,双标志后检查法虽然解决了"忙则等待"的问题,但是又违背了"空闲让进"和"有限等待"原则,会因各进程都长期无法访问临界资源而产生"饥饿"现象。
双标志后检查法中,两个进程都争着想进入临界区,但是谁也不让谁,最后谁都无法进入临界区。Gary L.Peterson想到了一种方法,如果双方都争着想进入临界区,那么可以让进入尝试"孔融让梨",主动让对方先使用临界区。
bool flag[2]; //表示进入临界区意愿的数组,初始值都是false int turn = 0; //turn 表示优先让哪个进程进入临界区
P0进程 flag[0] = true; 1 turn = 1; 2 while(flag[1] && turn == 1); 3 critical section; 4 flag[0] = fales; 5 remainder section;
P10进程 flag[1] = true; 6 //表示自己想进入临界区 turn = 0; 7 //可以优先人对方进入临界区 while(flag[0] && turn == 0); 8 //对方想进,且最后一次是自己"让梨",那自己就循环等待 critical section; 9 flag[1] = fales; 10 //访问完临界区,表示自己已经不想访问临界区了 remainder section;
进入区:
Peterson算法用软件方法解决了进程互斥问题,遵守了空闲让进、忙则等待、有限等待三个原则,但是依然为遵守让权等待的原则。