1. 实验背景与核心目标

死锁问题是操作系统课程中最为经典的并发控制难题之一。在重庆理工大学操作系统实验四中，我们将通过实践深入理解死锁产生的必要条件，并掌握预防、避免、检测与解除死锁的具体方法。这个实验不仅对理解操作系统内核机制至关重要，也是后续学习数据库系统、分布式系统等课程的重要基础。

死锁的四个必要条件早已由计算机科学家Coffman在1971年明确提出：

1. 互斥条件：资源一次只能被一个进程占用 2.占有并等待：进程持有资源的同时等待其他资源 3.非抢占条件：已分配的资源不能被强制剥夺 4.循环等待条件：存在进程-资源的循环等待链

在Linux环境下，我们可以通过pthread线程库模拟多线程竞争资源的过程。实验要求使用C语言编写程序，人为构造死锁场景，然后分别采用银行家算法、资源预分配、超时检测等不同策略来解决死锁问题。

2. 死锁场景构造实验

2.1 基础环境搭建

实验推荐使用Ubuntu 20.04 LTS系统，通过以下命令安装必要工具：

sudo apt update sudo apt install build-essential gdb

创建实验目录并初始化C程序：

#include <pthread.h> #include <stdio.h> #include <unistd.h> pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER; pthread_mutex_t mutex2 = PTHREAD_MUTEX_INITIALIZER; void *thread1(void *arg) { pthread_mutex_lock(&mutex1); printf("Thread 1 acquired mutex1\n"); sleep(1); // 人为制造延迟 pthread_mutex_lock(&mutex2); printf("Thread 1 acquired mutex2\n"); // 临界区操作 pthread_mutex_unlock(&mutex2); pthread_mutex_unlock(&mutex1); return NULL; } void *thread2(void *arg) { pthread_mutex_lock(&mutex2); printf("Thread 2 acquired mutex2\n"); sleep(1); pthread_mutex_lock(&mutex1); printf("Thread 2 acquired mutex1\n"); // 临界区操作 pthread_mutex_unlock(&mutex1); pthread_mutex_unlock(&mutex2); return NULL; } int main() { pthread_t t1, t2; pthread_create(&t1, NULL, thread1, NULL); pthread_create(&t2, NULL, thread2, NULL); pthread_join(t1, NULL); pthread_join(t2, NULL); return 0; }

编译并运行这个程序，你会观察到程序卡死——这就是典型的死锁现象。两个线程分别持有mutex1和mutex2，同时请求对方持有的锁，形成循环等待。

2.2 死锁检测技巧

在Linux下，我们可以使用以下方法验证死锁发生：

1. 使用ps -aux | grep a.out查找进程ID
2. 通过pstack <PID>查看线程堆栈
3. 或者使用gdb附加到进程：

gdb -p <PID> thread apply all bt

典型死锁的堆栈信息会显示两个线程分别在pthread_mutex_lock处阻塞。

3. 死锁解决方案实现

3.1 银行家算法实现

银行家算法是最经典的死锁避免算法，其核心是确保系统始终处于安全状态。我们需要实现以下数据结构：

#define PROCESS_NUM 5 #define RESOURCE_NUM 3 int available[RESOURCE_NUM] = {3, 3, 2}; int max[PROCESS_NUM][RESOURCE_NUM] = { {7, 5, 3}, {3, 2, 2}, {9, 0, 2}, {2, 2, 2}, {4, 3, 3} }; int allocation[PROCESS_NUM][RESOURCE_NUM] = {0}; int need[PROCESS_NUM][RESOURCE_NUM]; // 计算需求矩阵 void calculate_need() { for(int i=0; i<PROCESS_NUM; i++) { for(int j=0; j<RESOURCE_NUM; j++) { need[i][j] = max[i][j] - allocation[i][j]; } } } // 安全性检查算法 int is_safe() { int work[RESOURCE_NUM]; int finish[PROCESS_NUM] = {0}; // 初始化工作向量 for(int i=0; i<RESOURCE_NUM; i++) { work[i] = available[i]; } // 寻找可满足的进程 int count = 0; while(count < PROCESS_NUM) { int found = 0; for(int i=0; i<PROCESS_NUM; i++) { if(!finish[i]) { int j; for(j=0; j<RESOURCE_NUM; j++) { if(need[i][j] > work[j]) break; } if(j == RESOURCE_NUM) { // 可以分配 for(int k=0; k<RESOURCE_NUM; k++) { work[k] += allocation[i][k]; } finish[i] = 1; found = 1; count++; } } } if(!found) break; } return (count == PROCESS_NUM); }

重要提示：银行家算法虽然理论完美，但在实际系统中往往难以应用，因为需要预先知道进程的最大资源需求，这在动态环境中很难准确预估。

3.2 锁顺序标准化

对于前面演示的死锁案例，最简单的解决方案是统一锁的获取顺序：

void *thread1(void *arg) { pthread_mutex_lock(&mutex1); pthread_mutex_lock(&mutex2); // 临界区操作 pthread_mutex_unlock(&mutex2); pthread_mutex_unlock(&mutex1); return NULL; } void *thread2(void *arg) { pthread_mutex_lock(&mutex1); // 与thread1相同的顺序 pthread_mutex_lock(&mutex2); // 临界区操作 pthread_mutex_unlock(&mutex2); pthread_mutex_unlock(&mutex1); return NULL; }

这种方法虽然简单，但在复杂系统中可能难以维护锁的顺序关系。

3.3 尝试锁与超时机制

pthread提供了pthread_mutex_trylock函数，可以实现非阻塞的锁获取：

void *thread1(void *arg) { while(1) { if(pthread_mutex_trylock(&mutex1) == 0) { if(pthread_mutex_trylock(&mutex2) == 0) { // 成功获取两个锁 printf("Thread 1 acquired both locks\n"); pthread_mutex_unlock(&mutex2); pthread_mutex_unlock(&mutex1); break; } // 获取mutex2失败，释放mutex1避免死锁 pthread_mutex_unlock(&mutex1); } sleep(1); // 避免忙等待 } return NULL; }

更完善的方案可以结合pthread_mutex_timedlock实现带超时的锁获取：

#include <time.h> void *thread1(void *arg) { struct timespec ts; clock_gettime(CLOCK_REALTIME, &ts); ts.tv_sec += 2; // 2秒超时 if(pthread_mutex_timedlock(&mutex1, &ts) == 0) { clock_gettime(CLOCK_REALTIME, &ts); ts.tv_sec += 2; if(pthread_mutex_timedlock(&mutex2, &ts) == 0) { // 成功获取 pthread_mutex_unlock(&mutex2); pthread_mutex_unlock(&mutex1); } else { // 超时 pthread_mutex_unlock(&mutex1); } } return NULL; }

4. 实验进阶与问题排查

4.1 死锁检测算法实现

除了预防和避免，我们还可以实现死锁检测算法。基于资源分配图的简化算法如下：

int detection() { int work[RESOURCE_NUM]; int finish[PROCESS_NUM] = {0}; // 初始化工作向量 for(int i=0; i<RESOURCE_NUM; i++) { work[i] = available[i]; } // 标记已完成的进程 for(int i=0; i<PROCESS_NUM; i++) { int all_zero = 1; for(int j=0; j<RESOURCE_NUM; j++) { if(allocation[i][j] != 0) { all_zero = 0; break; } } finish[i] = all_zero; } // 寻找可满足的进程 int found; do { found = 0; for(int i=0; i<PROCESS_NUM; i++) { if(!finish[i]) { int j; for(j=0; j<RESOURCE_NUM; j++) { if(need[i][j] > work[j]) break; } if(j == RESOURCE_NUM) { // 可以分配 for(int k=0; k<RESOURCE_NUM; k++) { work[k] += allocation[i][k]; } finish[i] = 1; found = 1; } } } } while(found); // 检查是否有未完成的进程 for(int i=0; i<PROCESS_NUM; i++) { if(!finish[i]) { printf("Deadlock detected involving process %d\n", i); return 0; } } return 1; }

4.2 常见实验问题与解决

1. 线程不同步问题：

   • 现象：死锁现象不稳定，有时出现有时不出现
   • 解决：确保所有线程同时启动，可以使用屏障同步：

   pthread_barrier_t barrier; // 初始化 pthread_barrier_init(&barrier, NULL, 3); // 2个线程+主线程 // 在线程函数开始处 pthread_barrier_wait(&barrier);

2. 锁泄漏问题：

   • 现象：程序运行后资源未释放
   • 解决：确保所有代码路径都有解锁操作，可以使用RAII模式封装锁：

   typedef struct { pthread_mutex_t *mutex; } MutexGuard; void guard_init(MutexGuard *guard, pthread_mutex_t *m) { guard->mutex = m; pthread_mutex_lock(guard->mutex); } void guard_destroy(MutexGuard *guard) { pthread_mutex_unlock(guard->mutex); } // 使用示例 void foo() { MutexGuard guard; guard_init(&guard, &mutex1); // 自动释放 guard_destroy(&guard); }

3. 性能问题：

   • 现象：使用trylock导致CPU占用高
   • 解决：在尝试失败后添加适当的休眠：

   while(pthread_mutex_trylock(&mutex) != 0) { usleep(1000); // 休眠1毫秒 }

5. 实验报告撰写要点

一份优秀的实验报告应包含以下内容：

1. 实验环境：

   • 操作系统版本：uname -a
   • 编译器版本：gcc --version
   • CPU核心数：nproc

2. 实验设计：

   • 死锁场景的构造原理
   • 采用的解决方案及其理论依据
   • 关键数据结构说明

3. 实验结果：

   • 死锁现象截图（使用pstack或gdb）
   • 解决方案的效果对比
   • 性能数据（使用time命令测量）

4. 分析讨论：

   • 不同解决方案的优缺点比较
   • 在实际系统中的适用性分析
   • 实验中遇到的特殊问题及解决方法

5. 核心代码片段：

   • 关键算法的实现
   • 有创新性的解决方案
   • 测试用例设计

实验技巧：使用Git管理实验代码，每次重大修改都提交一个版本，这样可以在报告中清晰展示开发过程，也方便回退到之前的状态。