# Chapter 006: Deadlock
# Status: Timeline 1974.5.12
# Location: Bell Labs, Murray Hill
>>> Timeline Jump Complete
>>> Current Location: Bell Labs, 1974
>>> Mission: Fix critical deadlock in Unix V5
>>> Warning: Process scheduling system compromised
>>> Status: Initializing environment...
当世界重新清晰时，我发现自己站在一台PDP-11/45前。显示器上滚动着一连串错误信息：
PANIC: System freeze
PANIC: Process table full
PANIC: Resource unavailable
...
"整个系统都卡住了，"Ken Thompson揉着太阳穴说，"这是这周第三次了。"
我快速浏览着系统日志。这是Unix V5版本，第一个被广泛使用的Unix系统。如果在这个版本中存在严重的死锁问题，那将影响到后来所有的Unix分支。
struct proc {
char p_stat; /* 进程状态 */
char p_flag; /* 标志位 */
char p_pri; /* 优先级 */
char p_sig; /* 信号 */
char p_uid; /* 用户ID */
char p_time; /* 运行时间 */
char p_cpu; /* CPU使用率 */
char p_nice; /* nice值 */
int p_ttyp; /* 控制终端 */
int p_pid; /* 进程ID */
int p_ppid; /* 父进程ID */
int p_addr; /* 数据段地址 */
int p_size; /* 数据段大小 */
int *p_wchan; /* 等待通道 */
};
"让我看看进程调度代码。"我说。
void sched() {
struct proc *p;
int c;
while(1) {
c = -1;
for(p = &proc[0]; p < &proc[NPROC]; p ) {
if(p->p_stat == SRUN && p->p_flag == 0) {
c = p->p_cpu & 0377;
if(c > maxpri) {
maxpri = c;
runproc = p;
}
}
}
if(c < 0) {
// 没有可运行的进程
idle();
continue;
}
swtch();
}
}
"问题在这里，"我指着屏幕说，"系统没有正确处理资源竞争。"
我开始分析死锁发生的场景：
1. 进程A持有资源X，等待资源Y
2. 进程B持有资源Y，等待资源X
3. 两个进程互相等待，形成死锁
"我们需要实现死锁检测和预防机制。"我说着，开始修改代码：
struct resource {
int r_type; /* 资源类型 */
int r_id; /* 资源ID */
int r_owner; /* 当前持有者 */
int r_waiters; /* 等待队列 */
};
struct proc {
// ... 原有字段 ...
int p_resources[NRES]; /* 持有的资源 */
int p_waiting; /* 等待的资源 */
};
int allocate_resource(struct proc *p, struct resource *r) {
if(r->r_owner != 0) {
// 资源被占用，检查是否会造成死锁
if(would_deadlock(p, r)) {
return 0; // 拒绝分配
}
p->p_waiting = r->r_id;
sleep(p);
return 1;
}
r->r_owner = p->p_pid;
p->p_resources[r->r_id] = 1;
return 1;
}
int would_deadlock(struct proc *p, struct resource *r) {
struct proc *owner = &proc[r->r_owner];
int visited[NPROC] = {0};
// 检查是否形成等待环
return check_cycle(p, owner, visited);
}
int check_cycle(struct proc *start, struct proc *current, int *visited) {
if(current == start) {
return 1; // 发现循环
}
if(visited[current->p_pid]) {
return 0;
}
visited[current->p_pid] = 1;
if(current->p_waiting) {
struct resource *r = &resources[current->p_waiting];
if(r->r_owner) {
return check_cycle(start, &proc[r->r_owner], visited);
}
}
return 0;
}
"这个修改增加了资源分配表和死锁检测算法，"我解释道，"在分配资源之前，系统会检查是否会导致死锁。如果检测到潜在的死锁，就拒绝分配资源。"
Ken Thompson认真地看着代码："但这会不会影响性能？"
"性能确实会有一些影响，"我承认道，"但比起系统完全死锁要好得多。而且我们可以优化检测算法..."
为了验证修改的效果，我编写了一个测试程序：
void test_deadlock() {
int pid1, pid2;
pid1 = fork();
if(pid1 == 0) {
// 子进程1
get_resource(1);
sleep(1);
get_resource(2);
exit(0);
}
pid2 = fork();
if(pid2 == 0) {
// 子进程2
get_resource(2);
sleep(1);
get_resource(1);
exit(0);
}
}
>>> Running deadlock test...
>>> Process 1: Acquired resource 1
>>> Process 2: Acquired resource 2
>>> Process 1: Waiting for resource 2
>>> Process 2: Resource 1 denied (deadlock prevention)
>>> Test passed: No deadlock occurred
"系统成功避免了死锁！"我说。但就在这时，熟悉的眩晕感又来了。
>>> Mission Completed
>>> Timeline Stable
>>> Bug Fixed: Process Deadlock Prevention
>>> Historical Impact: Significant
>>> Note: Resource Management Model Established
>>> Preparing for next jump...
在视线模糊之前，我看到Ken Thompson正在他的笔记本上记录这些改动。这些代码将成为后来Unix系统进程调度和资源管理的基础。
死锁问题，操作系统设计中最经典的难题之一。通过这次修复，我不仅帮助Unix避免了一个严重的问题，也为后来的操作系统提供了重要的参考。
这让我想起了那句老话：如果说我能看得更远，那是因为我站在巨人的肩膀上。只是这一次，我有幸帮助巨人避免了一次跌倒。
# End of Chapter 006
# Next Timeline Loading...
梦远书城已将原网页转码以便移动设备浏览
本站仅提供资源搜索服务，不存放任何实质内容。如有侵权内容请联系搜狗，源资源删除后本站的链接将自动失效。
推荐阅读