并行与指令：同步

任务之间相互独立的时候，任务的并行执行是比较容易的，但往往任务之间需要相互协作，这种协作通常意味着某些任务写的结果是其他任务需要读的值。这时执行读任务的一方要知道写任务什么时候完成了写操作，才能安全读回数据。就是说，任务之间需要同步，否则就发生数据竞争（data race）的危险，导致读数据错误而引起程序运行结果的改变。

数据竞争：假如来自不同线程的两个访存请求访问同一个地址，他们连续出现，并且至少其中一个是写操作，那么这两个储存访问形成数据竞争。

在计算机中，同步机制要依赖硬件提供的同步指令，这些指令可由用户调用。这里重点讨论加锁（lock）和解锁（unlock）同步操作的实现。采用加锁和解锁可以直接创立一个仅允许单处理器操作的区域，叫作互斥（mutual exclusion）区。更复杂的同步机制也是与此类似。

在多处理器中实现同步需要一组硬件原语，提供对存储单元进行原子读和原子写的能力，使得在进行存储器原子读或原子写操作时任何其他操作都不得插入。如果没有这样的硬件原语，那么建立同步机制的代价将会变得很高，并且随着处理器数量的增加情况更为恶化。

我们用原子交换原语来演示如何建立基本同步机制，这个原语是将寄存器中的一个值和存储器中的一个值相互交换。

为了展示该原语建立同步原理的基本过程，假定使用存储器中某个单元来表示一个锁变量：其数值为0时表示解锁，为1时表示加锁。一个处理器尝试对锁单元加锁，方法是用一个存储器中的1与该锁单元的值进行交换，交换以后该锁单元的新值为1，返回值为（锁单元原值）如果是1，表明这个锁已被其他处理器占用；否则返回值0，表示锁是自由的，尝试过加锁成功。此时锁单元被修改为1，以防止任何其他的处理器再来占用。

例如，考虑有两个处理器同时尝试进行交换操作，它们的竞争关系就会被破坏。因为其中只有一个处理器先执行交换操作，并且返回0.那么第二个处理器执行交换操作的时候返回值就变成了1.用交换原语实现同步的关键是操作的原子性；交换操作是不可分割的，并且由硬件对两个同时执行的交换操作数进行排序。有可能两个处理器同时尝试置位同步变量，但是这两个处理器不可能同时认为它们成功设置了同步变量是不可能的。

实现单个的原子存储器操作给处理器的设计者带来了若干挑战。因为这要求存储器的读写操作都是由单条不可被中断的指令完成。

一种可行的方法是采用指令对，其中第二条指令返回一个表明这对指令是否原子执行的标志值。假如处理器的操作都是在这指令之前或之后执行的，这对指令就是原子的，因此，当一个指令对是原子的，没有哪个处理器能改变这两个指令执行之间的数据值。

在MIPS处理器种这一指令对包括一条叫做连接取数（load linked）的特殊取数指令和一条叫做条件存数（store conditional）的特殊指令。我们顺序的使用这两条指令：如果连接取数指令所指定的锁单元的内容在相同地址的条件存数指令执行前已经被改变，那么条件存数指令就执行失败。我们定义条件存数指令执行完成以下功能：保存寄存器的值，并且如果执行成功则将寄存器的值修改为1，如果失败则修改为0.因为链接取数指令返回锁单元的原始值，条件数指令执行成功的时候才返回1，下面的指令序列实现了存储器单元的原子交换。存储器单元的地址由$s1的值指出。

again: addi $t0, $zero,1 ;copy lockes value
II $t1, 0($s1) ;load linked
sc $t0, 0($s1) ;store conditional
beq $t0, $zero,again ;branch if store fails
add $s4, $zero, $t1 ;put load value in $s4

在ii和sc两条指令之间任何时候有处理器插入，并修改了该锁单元的值，指令sc都会将$t0置换为0，引起这段指令序列重新执行。在指令序列的最后，寄存器$s4中的值和$s1指向的锁单元的值发生了原子交换。