I 进程/线程的同步1 项目概述2 创建竞态3 临界区问题的解决办法4 实现一般信号量5 有界缓冲区6 具体任务总结7 附加任务的建议1 项目概述在本项目中，我们将使用不同的方法来解决临界区问题和有界缓冲区问题。

第一个任务是建立两个访问同一个共享资源的并发线程。

我们将证明没有同步机制时，线程执行的一些操作可能会丢失。

然后我们实现两种不同的解决方案：（1）利用Pthreads提供的互斥锁(mutex locks)；（2）使用一种软件解决方案(Peterson方法)，并比较这两种方法的性能。

然后我们会实现两种不同的作用于一般信号量的P操作和V操作；（1）利用Pthreads提供的互斥锁(mutex locks)和环境变量；（2）使用软件解决方法。

再比较两者的性能。

最后，我们利用上面的平台开发的P操作和V操作在两个并发线程之间实现一个有界缓冲区。

2 创建竞态在本项目中，我们采用POSIX的Pthreads，当然也可以使用能够提供一个进程中有多个线程的其它程序包。

POSIX标准没有规定在多个线程之间具体的并发需求。

我们首先假设要实现需要支持RR调度的并发线程。

这就是说，每个线程运行一段时间以后将被自动抢占，另一个线程开始执行。

因此，在一个进程中的所有线程都以不可预知的速度并发运行。

为创建一个竞态，创建两个线程T1和T2。

父线程（主线程）定义了两个全局变量accnt1和accnt2。

每个变量表示一个银行账户，且只有一个值（当前余额），其初值为0。

线程模拟银行事务，即将一定数额的钱从一个账户转移到另一个账户。

这就是说，每个线程都要读取两个账户的数值，产生一个随机数r，把这个数增加到另一个账户上，并从另一个账户上减去该值。

下面的代码框架说明了每个线程的操作：counter=0;do {temp1=accnt1;temp2=accnt2;r=rand();accnt1=temp1+r;accnt2=temp2-r;counter++;}while(accnt1+accnt2==0);print(counter);两个线程执行相同的代码。

中要没有交叉执行，两个余额的和将会是0。

然而，如果线程交叉执行，一个线程可能读取accnt1原来的值和accnt2的新值，或者相反，这就会导致丢失其中一个更新后的值。

如果发现这种情况，线程将停止并打印出发生时的步长（counter）。

也可以利用文件创建一个类似的程序。

主线程创建两个共享文件f1和f2，并利用它们替换共享变量accnt1和accnt2。

每个文件只有一个值——当前账户余额。

线程使用和上面程序相同的方法，利用一个随机数读取和更新余额（注意，在读/写序列中一定不能为了互斥性访问而锁住文件，否则将不能交叉执行）。

为主线程和两个线程代码。

然后测试多长时间会产生一次竞态，从而造成更新值的丢失。

注意：在实现不支持RR调度的线程时，必须通过在线程之间显式地强制实施文境切换来模拟这种行为。

在两个更新语句之间插入一段代码执行如下操作：在指定的范围内（如从0~1）产生一个随机数。

如果该数比某个给定的阈值（如0.1）小，便使用一个yield语句明确地将CPU让给其它线程。

这样平均下来，在10次循环中就会有1次产生文境切换。

3 临界区问题的解决方法在每个线程的代码中都有一个临界区。

解决这个问题有两种可能方法。

如果系统提供了如互斥量的基本同步原语，就可以用它锁住临界区实现互斥访问。

如果系统没有提供任何同步原语，就可以使用软件方法（由Peterson开发的方法，见原理教材的相关章节的介绍）。

下面我们对这两方法进行讨论和比较。

3.1 使用互斥锁的解决方法Pthread库提供了一种二元信号量，被称作互斥量（mutexes）。

互斥量可以被加锁和解锁。

当为一个已被其它线程锁住的互斥量再次上锁时，调用线程将被阻塞直到该互斥量被解锁。

利用这些原语很容易实现临界区。

在进入临界区前，互斥量将被加锁。

我们的实例中，是在第一次读操作之前加锁的。

在离开临界区后，互斥量才被解锁。

实例中是在第二次更新之后解锁的。

由系统事处理正在阻塞（正在等待）和正被解锁的线程。

3.2 软件解决方法现在我们假设系统没有提供互斥量或者其它任何形式的同步原语。

我们只能利用标准编程语言在常规变量上的操作来解决临界区问题。

在原理教材中提到的解决两个进程或线程之间临界区问题的方法使用了3个变量c1、c2和will_wait。

当线程i想进入临界区时，便将变量ci置为1。

为了打破任何可能存在的竞态，也要将will_wait设为j。

以忙等待循不的形式在临界区之前实现阻塞。

当线程离开临界区时，再把变量ci重置为0。

我们的临界区是一段代码，它以第一次读操作开始，以第二次更新操作结束。

我们可以使用软件方法中的代码实施互斥。

为了加快执行速度，忙等待循环应该包含sched_yield语句。

这样阻塞时便会马上释放CPU，而不是在时间片过时前一直在空循环。

现在我们准备比较解决临界区问题的两种方法的效率。

利用两种方法简单地重复相同次数的循环并测量执行时间。

为了消除任何可能的外部干扰，重复试验几次，计算平均时间。

4 实现一般信号量使用更低级的原语，如二元信号量，可以方便地实现一般信号量的P操作和V操作。

换句话说，可以尝试只用常规编程结构的解决方法。

4.1 使用互斥锁和条件变量的解决方法在原理教材中讨论了如何使用二元信号量上的Pb操作和Vb操作来实现一般信号量的P操作和V操作。

这种方法使用了两个二元信号量sb和delay。

它们有着不同的用途。

sb用于互斥。

这种信号量同Pthreads中的互斥锁类似。

这样，我们可以使用Pb(sb)和Vb(sb)分别代替mutex_lock和mutex_unlock。

二元信号量delay用于在P操作中阻塞进程，然后释放进程（使用相应的V操作）。

这种二元信号量可以用条件变量来模拟。

那么，pthread_cond_wait和pthread_cond_signal 将分别对应于Pb(delay)和Vb(delay)。

4.2 软件解决方法在前一节中，我们已经有了解决临界区问题的一种软件方法（就是没有使用任何特殊的同步指令的方法）。

按照如下步骤，我们可以创建用于临界区的P操作和V操作：（1）每个信号量s使用一个整数变量实现。

（2）对共享变量s的访问必须以临界区的方式实现。

（3）当P操作必须阻塞时，线程必须进入一个不停测试s值的while循环（在临界区内），直到s比0大；与此同时它要减少s的值，并继续继续执行。

在等待循环的每次迭代中，线程应该放弃CPU以便提高性能。

（注意：放弃操作不应在临界区内发生。

否则，没有其他进程能够执行V操作，这样系统将会发生死锁。

）（4）V操作会简单地增加s的值（在临界区内）。

现在，我们准备比较两种实现P操作和V操作方法的性能。

开发一些测试用例，它们包括一个或多个执行不同顺序的P操作和V操作的线程。

需要特别指出的是，应当测试一下在P操作中没有线程等待的情况下和在P操作中有一个线程或多个线程等待的情况下P操作和V操作的执行时间。

5 有界缓冲区在原理教材中讨论了在一个生产者线程和一个消费者线程之间实现有界缓冲区的问题。

生产者线程从一个文件f1中反复读取数据（如一个整数），直到到达文件末尾。

它把每个数据存放到利用大小为n的数组所实现的有界缓冲区中，并在两个进程之间共享该数组。

消费者线程不停地从缓冲区中移出数据，并把它们写入到另一个文件f2中。

当两个线程都完成时，文件f2应该是文件f1的完全副本。

记录每次循环中有多少值会在缓冲区里。

如果值大部份时间要么是n要么是0，那么就可以把随机选择睡眠一段时间的sleep语句插入到生产者和消费者线程的循环体中，以模拟消费和生产活动的突发情况。

6 具体任务总结（1）创建两个线程，使它们进入一个竞态。

（2）使用（a）互斥锁；(b)Peterson软件方法来解决竞态问题，并比较两者的性能。

（3）分别使用（a）互斥锁和环境变量；(b)解决临界区问题的软件方法来实现对一般信号量的P操作和V操作的。

并比较两种方法的性能。

（4）在生产者和消费者线程问题之间实现一个有界缓冲。

研究两个线程的并发行为。

（5）将你的试验结果写成报告7 附加任务的建议（1）使用P操作和V操作实现基本的管程功能。

这就需要写一个预编译器。

该预编译器使用原理教材中实现的代码替换所有的c.wait和s.signal操作，并插入互斥代码使其围绕着每一个管程过程。

然后，并发线程可以调用管程过程来协调它们对共享资源的使用。

还有，为了将过程和资源封装在一起建模，可以将管程实现为一个独立的进程。

该进程与其它必须借助于UNIX管道来使用管程的进程进行进行通信。

当一个进程试图调用一个管道过程时，它通过向请求管道写入信息的方式，向管程进程发出请求（包括程序和参数）。

然后从应答管道中读取信息并阻塞自己。

管程进程不断地从请求管程中读取对过程调用的请求，对每一个请求，它都要调用以独立线程存在的相应处理程序。

这种线程可以使用c.wait操作阻塞自己和c.signal 操作去唤醒其他线程。

当线程终止时，管程进程将通过向应答管道写入信息，把结果返回给原先的调用进程。

（2）将临界区问题扩展到多于两个进程的情况。

使用并比较两种解决方法：Pthreads提供的构造和纯软件方案。