最好用一个例子来说明。
假设我们有一个简单的任务,我们希望并行执行多次,并且希望全局跟踪任务执行的次数,例如,对网页的点击进行计数。
当每个线程到达计数递增点时,其执行将如下所示:
从内存中读取命中数到处理器寄存器中
增加该数字。
将该号码写回内存
请记住,每个线程都可以在此过程中的任何时候暂停。因此,如果线程A执行步骤1,然后被挂起,接着线程B执行所有三个步骤,则线程A恢复时,其寄存器的命中数将错误:它将恢复其寄存器,将愉快地增加旧数的点击数,并存储该递增的数字。
另外,在线程A挂起期间,可能有任何数量的其他线程运行,因此末尾线程A写入的计数可能远低于正确的计数。
因此,必须确保如果线程执行步骤1,则必须在允许任何其他线程执行步骤1之前执行步骤3,这可以由所有等待开始单个锁的线程在开始此过程之前完成。 ,并且仅在过程完成后才释放锁定,以使该“关键部分”代码不会被错误地交错,从而导致错误的计数。
但是,如果操作是原子的怎么办?
是的,在神奇的独角兽和彩虹之地,增量操作是原子的,因此上面的示例不需要锁定。
但是,重要的是要意识到,我们在神奇的独角兽和彩虹世界中只花了很少的时间。在几乎每种编程语言中,增量操作都分为上述三个步骤。这是因为,即使处理器支持原子增量操作,该操作也要昂贵得多:它必须从内存中读取,修改数字并将其写回到内存中……通常,原子增量操作是一种可能失败,这意味着上面的简单序列必须替换为循环(如下所示)。
因为即使在多线程代码中,许多变量也保持在单个线程本地,所以如果程序假设每个变量在单个线程本地,则程序效率会大大提高,并让程序员负责保护线程之间的共享状态。尤其是考虑到原子操作通常不足以解决线程问题,我们将在后面介绍。
易变变量
如果我们想避免针对此特定问题的锁定,我们首先必须意识到,第一个示例中描述的步骤实际上并不是现代编译代码中发生的事情。因为编译器假定只有一个线程正在修改变量,所以每个线程将保留其自己的变量的缓存副本,直到需要处理器寄存器进行其他操作为止。只要它具有缓存的副本,就假定它不需要返回内存并再次读取它(这会很昂贵)。只要将变量保存在寄存器中,它们也不会将其写回内存。
我们可以通过将变量标记为volatile来回到在第一个示例中给出的情况(具有上面确定的所有相同的线程问题),这告诉编译器该变量正在被其他人修改,因此必须从中读取或在访问或修改时将其写入内存。
因此,标记为volatile的变量不会使我们进入原子增量操作的领域,只会使我们与我们已经认为的接近。
使增量成为原子
一旦使用了volatile变量,我们就可以通过使用大多数现代CPU支持的低级条件设置操作(通常称为compare和set或compare和swap)来使增量操作成为原子操作。例如,在Java的AtomicInteger类中采用了这种方法:
197 /**
198 * Atomically increments by one the current value.
199 *
200 * @return the updated value
201 */
202 public final int incrementAndGet() {
203 for (;;) {
204 int current = get();
205 int next = current + 1;
206 if (compareAndSet(current, next))
207 return next;
208 }
209 }
上面的循环重复执行以下步骤,直到步骤3成功:
直接从内存中读取易失变量的值。
增加价值。
仅当主存储器中的当前值与我们最初读取的值相同时,才使用特殊的原子操作来更改(主存储器中的)值。
如果第3步失败(因为在第1步之后值被另一个线程更改),它将再次直接从主内存中读取变量,然后重试。
尽管比较交换操作很昂贵,但在这种情况下,它比使用锁定要好一些,因为如果在步骤1之后挂起了线程,则到达步骤1的其他线程不必阻塞并等待第一个线程,可以防止代价高昂的上下文切换。当第一个线程恢复时,它将在第一次尝试写入变量时失败,但是将能够通过重新读取变量来继续执行,这又可能比需要锁定的上下文切换便宜。
因此,我们可以通过比较和交换来获得原子增量(或对单个变量进行的其他操作)的领域,而无需使用实际的锁定。
那么什么时候严格需要锁定呢?
如果您需要在一个原子操作中修改多个变量,那么锁定将是必要的,您将不会为此找到特殊的处理器指令。
只要您正在处理单个变量,并且您为失败所做的一切工作做好了准备,并且不得不读取该变量并重新开始,那么“比较并交换”就足够了。
让我们考虑一个示例,其中每个线程首先将2加到变量X,然后将X乘以2。
如果X最初为1,并且运行两个线程,则我们期望结果为(((1 + 2)* 2)+ 2)* 2 = 16。
但是,如果线程交织,即使所有操作都是原子操作,我们也可以先执行两个加法运算,然后执行乘法运算,从而得到(1 + 2 + 2)* 2 * 2 = 20。
发生这种情况是因为乘法和加法不是交换运算。
因此,仅原子操作本身是不够的,我们必须使原子操作组合起来。
我们可以通过使用锁定序列化过程来做到这一点,或者可以在开始计算时使用一个局部变量存储X的值,在中间步骤中使用另一个局部变量,然后使用compare-and-swap进行操作。仅当X的当前值与X的原始值相同时才设置一个新值。如果失败,我们将不得不通过读取X并再次执行计算来重新开始。
需要进行一些权衡:随着计算时间的延长,正在挂起的线程变得更有可能被挂起,并且在恢复之前,该值将被另一个线程修改,这意味着失败的可能性变得更大,从而导致浪费处理器时间。在极端的情况下,大量的线程需要很长时间运行计算,我们可能有100个线程读取该变量并参与计算,在这种情况下,只有第一个完成的线程才能成功写入新值,其他99个仍将完成他们的计算,但是完成后发现他们无法更新该值...这时他们将各自读取值并重新开始计算。我们可能会让其余的99个线程重复同样的问题,浪费大量的处理器时间。
在这种情况下,通过锁对关键部分进行完全序列化会更好:在没有锁的情况下,有99个线程将挂起,并且我们将按到达锁点的顺序运行每个线程。
如果序列化不是很关键(例如在递增情况下),并且在更新数量失败时将丢失的计算量很小,那么使用比较交换操作可能会获得显着优势,因为该操作比锁定便宜。