进程对临界资源的访问需要互斥，其需要遵从以下四个原则：
1、空闲让进：临界区空闲时应该允许一个进程访问；
2、忙则等待：临界区被访问时，其余想访问他的进程必须等待；
3、有限等待：等待的进程在外等待的时间必须是有限的；
4、让权等待：若等待进程一直等待，迟迟进不到临界区时，应该让出cpu处理机，防止忙等。
下面将介绍三种经典的软件实现的算法：
1、单标志法，使用一个标志位，标志此时访问临界区的进程，进入时先判断若另一进程未进入时才进去临界区，该进程访问完之后，把标志位转成另一进程，如此交替访问即可，用java的线程模拟该过程代码如下：
public class OneFlagMutex {
int turn = 0;
public void m0() {
while(turn != 0) {
System.out.println("m0正在等待");
};
System.out.println("m0在访问临界区");
turn = 1;
}
public void m1() {
while(turn != 1) {
System.out.println("m1正在等待");
};
System.out.println("m1在访问临界区");
turn = 0;
}
public static void main(String[] args) {
OneFlagMutex o = new OneFlagMutex();
new Thread(new Runnable() {
public void run() {
o.m0();
}
}).start();
new Thread(()->{
o.m1();
}).start();;
}
}
该方法有一个最大的问题是，需要两个进程不断交替访问，当turn == 1时，若此时进程一不访问的话，进程0将一直得不到访问临界区的权限，从而违背了“空闲让进”原则。
2.1、双标志先检查法：
设置两个标志位，flag = [false,false],此时哪个进程进入了就把哪个位置上的flag置为true，大体算法如下：“先检查再加锁”，进入临界区时先检查另一进程是否进去，若未进去，则进入后立刻给把自己的位置置为true，访问完之后把自己的flag置为false。代码如下：
class T{
private boolean[] flag = {false,false};//表示各进程是否想进去临界区
public void p0() {//p0访问临界区
while(flag[1]) {
System.out.println("p0在等待");
};
try {
Thread.sleep(10);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
flag[0] = true;
System.out.println("p0在访问临界区");
try {
Thread.sleep(10);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("p0访问完了");
flag[0] = false;
}
public void p1() {
while(flag[0]) {
System.out.println("p1在等待");
};
try {
Thread.sleep(10);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
flag[1] = true;
System.out.println("p1在访问临界区");
try {
Thread.sleep(10);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("p1访问完了");
flag[1] = false;
}
}
public class TwoFlagPredetect {
public static void main(String[] args) {
T t = new T();
new Thread(()->{
t.p0();
}).start();
new Thread(t::p1).start();
}
}
当第一个进程经过检测进入临界区时，此时它还没来得及将自己的标志位置true加锁第二个进程获得处理机，如此第二个进程也进入了临界区了，如此违背了“忙则等待”的原则。
2.2、双标志位后检查
由于“先检测后加锁”使得两个进程都进入到了临界区，人们很自然的想到了一种“先加锁，再检测”的方法，大体与2.1类似，其代码如下：
class P{
private boolean[] flag = {false,false};
public void p0() {
flag[0] = true;
try {
Thread.sleep(10);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
while(flag[1]) {
System.out.println("p0在等待");
};
System.out.println("p0在访问临界区");
try {
Thread.sleep(10);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
flag[0] = false;
}
public void p1() {
flag[1] = true;
try {
Thread.sleep(10);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
while(flag[0]) {
System.out.println("p1在等待");
};
System.out.println("p1在访问临界区");
try {
Thread.sleep(10);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
flag[1] = false;
}
}
public class TwoFlagAfterdetect {
public static void main(String[] args) {
P p = new P();
new Thread(p::p0).start();
new Thread(p::p1).start();
}
}
该方法虽然解决了2.1的问题（违背“忙则等待”），但是当第一个进程刚加完锁，还没来得及进入临界区时，后面的进程获得了处理机，然后其也对自己的flag加上锁，于是便出现了0进程和1进程都只能再外面死等着。都进不去临界区。如此又违背了“空闲让进”和“有限等待”。
3、Peterson算法
该算法集单标志和双标志之长，在双标志后检查的基础上又添加了一个标志turn，当两个进程都想访问临界区时，其会将turn置为对方，让对方先访问有一个“孔融让梨”的机制。大体算法如下：当一个进程想访问临界区时，其会先进行争抢（把自己的flag置为true），再进行礼让（把turn置为对方），然后进行检测如若（另一进程的flag = true && turn = 另一进程）由于另一进程flag = true说明另一进程也想访问临界区，然后将礼让出去。
实现代码如下：
class Process implements Runnable{
private static boolean[] flag = {false,false};
private static int turn;
private int id;
public Process(int id) {
this.id = id;
}
@Override
public void run() {
if(id == 0) {
flag[0] = true;//先争取
turn = 1; //再谦让
try {
Thread.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
while(flag[1] && turn == 1) {
System.out.println("进程0正在等待");
};
System.out.println("进程0正在访问临界区");
flag[0] = false;
}else {
flag[1] = true;//先争取
turn = 0; //再谦让
while(flag[0] && turn == 0) {
System.out.println("进程1正在等待");
};
System.out.println("进程1正在访问临界区");
flag[1] = false;
}
}
}
public class PetersonA {
public static void main(String[] args) {
new Thread(new Process(0)).start();
new Thread(new Process(1)).start();
}
}
以上就是软件实现进程互斥访问的三个算法。但是这三个算法都违背了“有限等待”的原则，对于满足“有限等待”的新的算法将在后续的信号量中加以介绍。