进程互斥软件实现方法学习卡片

🔄

单标志法

轮流访问临界区

单标志法

核心机制

通过turn变量实现进程轮流访问

代码实现

                                    int turn = 0; // 允许进入的进程号

                                    while(turn != 进程号); // 进入区

                                    critical_section(); // 临界区

                                    turn = 对方进程号; // 退出区

                                    remainder_section(); // 剩余区

优点

简单，保证互斥

缺点

必须严格轮流访问，违反"空闲让进"原则
若某进程不再访问，另一进程将永远无法进入

忙则等待有限等待空闲让进让权等待

🔍

双标志先检查法

先检查后上锁

双标志先检查法

核心机制

使用flag数组标记进程意愿，先检查后上锁

代码实现

                                    bool flag[2] = {false, false};

                                    while(flag[对方进程号]); // 先检查

                                    flag[本进程号] = true; // 后上锁

                                    critical_section();

                                    flag[本进程号] = false;

问题

检查与上锁非原子操作
可能导致两进程同时进入临界区
违反"忙则等待"原则

空闲让进忙则等待有限等待让权等待

🔒

双标志后检查法

先上锁后检查

双标志后检查法

核心机制

改进为先上锁后检查

代码实现

                                    bool flag[2] = {false, false};

                                    flag[本进程号] = true; // 先上锁

                                    while(flag[对方进程号]); // 后检查

                                    critical_section();

                                    flag[本进程号] = false;

问题

可能导致两进程互相阻塞而死锁
违反"空闲让进"和"有限等待"原则
可能出现饥饿现象

忙则等待空闲让进有限等待让权等待

🤝

Peterson算法

主动谦让机制

Peterson算法

核心机制

结合flag数组和turn变量，实现主动谦让

代码实现

                                    bool flag[2] = {false, false};

                                    int turn = 0;

                                    flag[本进程号] = true; // 表达意愿

                                    turn = 对方进程号; // 主动谦让

                                    while(flag[对方进程号] && turn == 对方进程号);

                                    critical_section();

                                    flag[本进程号] = false;

优点

满足空闲让进、忙则等待、有限等待三原则
不会死锁

缺点

不满足"让权等待"原则(进程会忙等待)

空闲让进忙则等待有限等待让权等待

📊

算法对比

四种方法比较

算法对比总结

单标志法

轮流访问(turn变量)
违反"空闲让进"
必须轮流，资源利用率低

双标志先检查

先检查后上锁(flag数组)
违反"忙则等待"
可能同时进入临界区

双标志后检查

先上锁后检查
违反"空闲让进"和"有限等待"
可能死锁

Peterson算法

flag数组+turn变量
仅违反"让权等待"
软件实现中最优解