Lab 4：并发控制

byml2025-05-06OS

伴随着并发的高效而来的，是并发的不可预料。并发的引入，无法避免地将程序从“从一个状态机跳向另一个状态机~~（折射出一缕晶莹的光……）~~”变成了“在揭开黑布前，我也不知道下一个状态机是啥~~（薛定谔的进程调度）~~”。如何解决这种由进程调度带来的不确定性？人们给出了答案——不并发不就行了！显然我们并不能完全抛弃并发，而是要做到“有限度地并发”。由此，“锁”的概念应运而生。“要么不做，要么独占”，这是锁的基本思想，这能够解决共享资源的访问与修改正确性问题（即互斥）。在此基础上，我们还得解决时间上的发生先后控制问题（即同步）。于是，人们提出了“条件锁”和“信号量”两种方法。

条件锁

条件锁，顾名思义就是“直到条件满足才继续向下执行的锁”。设存在全局锁（🔒）和用于线程间同步的条件变量（condition_var），则有：等待同步：

mutex_lock(🔒);
while (!condition) { // 这里可以是任意函数
	cond_wait(&condition_var, 🔒);
}
mutex_unlock(🔒);

唤起同步：

mutex_lock(🔒);
condition = true; // 这里修改条件
cond_broadcast(&condition_var); // 唤醒所有可能继续的线程
mutex_unlock(🔒);

值得注意的是，等待同步和唤起同步的过程必须在互斥锁的保护下进行，以免出现未知的问题。

信号量

如果同步问题可以建模成“对有限的资源消耗计数”，例如停车场停车、餐厅等位，我们就可以将资源建模为“信号量”，通过对信号量的请求-释放，实现并发同步。通过条件锁来实现信号量：

void P(sem_t *sem){
	// Prolaag - try + decrease/down/wait/acquire
	mutex_lock(&sem->lk);
	while (!(sem->count > 0)){
		cond_wait(&sem->cv, &sem->lk); // 无座？排队等着先！
	}
	sem->count--; // 老板里边请……
	mutex_unlock(&sem->lk);
}

void V(sem_t *sem){
	// Verhoog - increase/up/post/signal/release
	mutex_lock(&sem->lk);
	sem->count++; // 欢迎下次光临……
	cond_broadcast(&sem->cv); // 下一位！
	mutex_unlock(&sem->lk);
}

系统控制

站在用户程序视角，并发等待就是个不断循环的过程。但操作系统可不能将宝贵的 CPU 资源浪费在程序的自旋等待上。站在操作系统层面，我们可以这么做：

cond_wait() -> blocked：将程序置于阻塞状态，不去调度这个进程/线程
cond_broadcast() -> runnable：将所有有关程序重新置于可运行状态，下次调度到时检查条件

这样就可以有效减小自旋带来的开销。信号量的实现也是同理。

经典并发同步问题

哲学家就餐问题

问题描述：有 5 个哲学家坐在一张圆桌上，桌上摆了 5 把叉子。每个哲学家有两个状态：就餐和思考。只有一个哲学家同时拿起左右手两把叉子时，他才能顺利就餐。我们的目标是让所有哲学家能够有序在就餐和思考状态下切换。可能的问题：如果同步处理不当，会出现所有哲学家分别握着一把叉子的情况，此时既没有人能够就餐，也没有人能够思考，会僵持在中间状态。问题解决：将每一把叉子建模为一个信号量，每个哲学家是一个线程。对于奇数编号的哲学家，先取左手叉子，再取右手叉子；偶数则反之（这一步是避免所有哲学家同时握着同侧手叉子的关键）。

生产者-消费者问题

问题描述：一个或多个生产者将生产产物放在缓冲区中，单个消费者能够从缓冲区取出数据处理。任何时刻只有一个生产者或消费者能够访问缓冲区。可能的问题：如果同步处理不当，会出现消费者访问到空缓冲区的情况，也可能会出现生产者向满缓冲区写入的情况。问题解决：可以使用三个信号量解决：用作互斥锁的信号量 mutex，空缓冲区 bufferA，满缓冲区 bufferB。初始状态可以看作有 n 个球在空缓冲区中，生产者的作用是每次从空缓冲区取一个球，将其搬运到满缓冲区中；而消费者的作用是每次从满缓冲区取一个球，放回空缓冲区。

读者-写者问题

问题描述：读者和写者对数据的访问遵循如下规则：

允许同一时刻有多个读者同时读取数据
没有写者时才能读，没有读者时才能写
同一时刻只能有一个写者在写入数据

可能的问题：丢失修改、脏读、不可重复读问题解决：使用两个信号量和一个变量：读者写者互斥锁 RWmutex，读者计数修改线程互斥锁 CountMutex，读者计数变量 Rcount。对于写者进程：

P(RWmutex);
// 写操作
V(RWmutex);

对于读者进程：

P(CountMutex);
if(Rcount == 0) P(RWmutex);
++Rcount;
V(CountMutex);
// 读操作
P(CountMutex);
--Rcount;
if(Rcount == 0) V(RWmutex);
V(Countmutex);

Lab 4：并发控制