Locks and Synchronization锁与同步

Safe from bugs:今天改正,在未来的未知改正。
Easy to understand:与未来的程序员(包括未来的您)进行清晰的沟通。
Ready for change:旨在适应变化而无需重写。

目标:

  • 了解如何使用锁来保护共享的可变数据
  • 能够识别死锁并知道防止死锁的策略
  • 了解监视器模式并将其应用于数据类型

一、介绍

我们定义了一种数据类型或函数的线程安全性,使其在从多个线程中使用时具有正确的行为,而与这些线程的执行方式无关,无需额外的协调。

这是一般原则:并发程序的正确性不应该取决于计时的偶然性

为了实现这种正确性,我们列举了四种使代码安全进行并发的策略:

1.限制:不要在线程之间共享数据。
2.不可变性:使共享数据不可变。
3.使用现有的线程安全数据类型:使用为您进行协调的数据类型。
4.同步:防止线程同时访问共享数据。这就是我们用来实现线程安全类型的方法,但是当时我们没有讨论它。

在本文中,我们将讨论策略4,它使用同步来实现自己的对共享内存并发安全的数据类型。

二、同步化

并发程序的正确性不应该取决于时间安排的偶然性。

由于并发操作共享可变数据导致的竞争条件是灾难性的错误-难以发现,难以再现,难以调试-我们需要一种共享内存的并发模块彼此同步的方法。

锁是一种同步技术。锁是一种抽象,允许至多有一个线程拥有它一次。 持有锁是一个线程告诉其他线程的方式:“我正在使用此东西,请勿立即触摸它。”

锁有两种操作:

acquire允许线程取得锁的所有权。如果一个线程试图获取另一个线程当前拥有的锁,它将阻塞,直到另一个线程释放该锁为止。届时,它将与试图获取该锁的任何其他线程竞争。一次最多只能有一个线程拥有该锁。

release 放弃锁的所有权,允许另一个线程获得其所有权。

使用锁还可以告诉编译器和处理器您正在同时使用共享内存,以便将寄存器和缓存刷新到共享存储中。这避免了重新排序的问题,从而确保了锁的所有者始终在查看最新数据。

通常,阻塞意味着线程等待(不做进一步的工作)直到事件发生。

一个acquire(l)如果另一个线程(比如线程2)保持锁定在线程1将阻塞l。它等待的事件是线程2正在执行release(l)。在这一点上,如果线程1可以获取l,那么它将继续以锁的所有权运行其代码。可能另一个线程(例如线程3)也被阻塞了acquire(l)。线程1或3将获得锁定l并继续。另一个将继续阻止,release(l)再次等待。

银行账户示例

我们第一个共享内存并发的例子是有自动提款机的银行。
Locks and Synchronization锁与同步

银行有几台自动提款机,它们都可以在内存中读取和写入相同的帐户对象。
当然,在并发读取和写入帐户余额之间没有任何协调的情况下,事情就大错特错了。

为了使用锁解决此问题,我们可以添加一个锁来保护每个银行帐户。现在,提款机必须先获取对该帐户的锁定,然后才能访问或更新帐户余额。
在右图中,A和B都试图访问帐户1。假设B首先获得了锁。然后,A必须等待读取或写入余额,直到B完成并释放锁为止。这样可以确保A和B同步,但是另一个自动提款机C可以在另一个帐户上独立运行(因为该帐户受到另一个锁的保护)。Locks and Synchronization锁与同步

三、僵局

如果正确,谨慎地使用锁,可以防止比赛情况发生。但随后又出现了另一个问题。因为使用锁需要线程等待(acquire另一个线程持有该锁时阻塞),所以有可能进入两个线程正在互相等待的情况,因此都无法取得进展。
在下图中,假设A和B在我们银行的两个帐户之间同时进行转帐。
Locks and Synchronization锁与同步
帐户之间的转帐需要锁定两个帐户,以免钱从系统中消失。A和B各自获得对各自“帐户”的锁定:A获得对帐户1的锁定,而B获得对帐户2的锁定。现在,每个人都必须获得其“至”帐户的锁定:所以A在等待以便B释放帐户2锁定,并且B正在等待A释放帐户1锁定。僵局!A和B被冻结在“致命的拥抱”中,并且帐户被锁定。

死锁发生在并发模块被卡住,等待对方做某事时。死锁可能涉及两个以上的模块:死锁的信号特征是依赖关系的循环,例如A正在等待B,正在等待C,而C在等待A。它们都无法取得进展。

您也可以不使用任何锁而具有死锁。例如,当消息缓冲区填满时,消息传递系统可能会遇到死锁。如果客户端使用请求填充了服务器的缓冲区,然后阻止了等待添加另一个请求的请求,则服务器可能随后使用结果填充了客户端的缓冲区,然后阻止了自己。因此,客户端正在等待服务器,而服务器正在等待客户端,并且直到另一台服务器都无法获得进展。再次出现僵局。

四、开发线程安全的抽象数据类型

让我们看看如何使用同步来实现线程安全的ADT。

您可以在GitHub上查看此示例的所有代码:https://github.com/6031-sp17/ex21-editor。您不应阅读并理解所有代码。所有相关部分摘录如下。

假设我们正在建立一个多用户编辑器,例如Google Docs,它允许多个人同时连接并编辑它。我们需要一个可变的数据类型来表示文档中的文本。这是界面;基本上,它代表具有插入和删除操作的字符串:

/** An EditBuffer represents a threadsafe mutable
 *  string of characters in a text editor. */
public interface EditBuffer {
    /**
     * Modifies this by inserting a string.
     * @param pos position to insert at
                      (requires 0 <= pos <= current buffer length)
     * @param ins string to insert
     */
    public void insert(int pos, String ins);

    /**
     * Modifies this by deleting a substring
     * @param pos starting position of substring to delete 
     *                (requires 0 <= pos <= current buffer length)
     * @param len length of substring to delete 
     *                (requires 0 <= len <= current buffer length - pos)
     */
    public void delete(int pos, int len);

    /**
     * @return length of text sequence in this edit buffer
     */
    public int length();

    /**
     * @return content of this edit buffer
     */
    public String toString();
}

此数据类型的非常简单的代表就是一个字符串:

public class SimpleBuffer implements EditBuffer {
    private String text;
    // Rep invariant: 
    //   text != null
    // Abstraction function: 
    //   represents the sequence text[0],...,text[text.length()-1]

该代表的缺点是,每次执行插入或删除操作时,我们都必须将整个字符串复制到一个新字符串中。我们可以使用的另一个代表是一个字符数组,结尾处有空格。如果用户只是在文档末尾键入新文本(我们不必复制任何内容),那很好,但是如果用户在文档末尾键入文本,那么我们将在每个文档的末尾复制整个文档击键。

在实践中,许多文本编辑器都使用了一个更有趣的rep,它称为gap buffer。它基本上是一个字符数组,其中包含额外的空间,但是额外的空间不是在结尾处包含所有额外的空间,而是可以在缓冲区中任何位置出现的间隙。每当需要执行插入或删除操作时,数据类型都会首先将间隙移至该操作的位置,然后再执行插入或删除操作。如果该间隙已经存在,则无需复制任何内容–插入仅会消耗一部分间隙,而删除只会扩大间隙!间隙缓冲区特别适合于表示用户正在使用光标编辑的字符串,因为插入和删除操作往往集中在光标周围,因此间隙很少移动。

/** GapBuffer is a non-threadsafe EditBuffer that is optimized
 *  for editing with a cursor, which tends to make a sequence of
 *  inserts and deletes at the same place in the buffer. */
public class GapBuffer implements EditBuffer {
    private char[] a;
    private int gapStart;
    private int gapLength;
    // Rep invariant: 
    //   a != null
    //   0 <= gapStart <= a.length
    //   0 <= gapLength <= a.length - gapStart
    // Abstraction function: 
    //   represents the sequence a[0],...,a[gapStart-1],
    //                           a[gapStart+gapLength],...,a[length-1]

开发数据类型的步骤
回顾我们设计和实现ADT的方法:

1.指定。 定义操作(方法签名和规格)。我们在EditBuffer界面中做到了这一点。

2.测试。 为操作开发测试用例。请参阅EditBufferTest提供的代码。测试套件包括基于分区操作参数空间的测试策略。

3.销售代表 选择一个销售代表。我们为选择了其中两个EditBuffer,这通常是个好主意:

	a.首先实施一个简单的蛮力代表。 它更容易编写,更可能正确,它会验证您的测试用例和规范,因此您可以在进行更困难的实施之前解决其中的问题。这就是为什么我们SimpleBuffer在继续进行之前实现的原因GapBuffer。也不要丢掉您的简单版本-保留它,以便您可以进行测试并进行比较,以防万一复杂的版本出现问题。

	b.写下rep不变和抽象函数,并实现checkRep()。 checkRep()在每个构造函数,生成器和mutator方法的末尾声明rep不变量。(由于表示没有改变,通常不必在观察者的末尾调用它。)实际上,断言对于测试复杂的实现非常有用,因此在断言中也声明后置条件并不是一个坏主意。复杂方法的结尾。阅读本文后,您将GapBuffer.moveGap()在代码中看到一个示例。

在所有这些步骤中,我们首先都在完全使用单线程。在编写规范和选择销售代表时,多线程客户端应始终在我们的脑海中。(稍后我们将看到,可能有必要谨慎选择操作以避免在数据类型的客户端中出现竞争状况)。但是首先要使其在顺序的单线程环境中正常工作并经过全面测试。

现在我们准备好进行下一步:

4.同步。 声明您的代表是线程安全的。将它作为rep不变式明确记为您的类中的注释,以便维护人员知道您如何将线程安全性设计到该类中。

阅读的这一部分是关于如何执行步骤4的。我们已经了解了如何创建线程安全参数,但是这次,我们将依赖于该参数中的同步。

然后我们在上面暗示了额外的步骤:

5.反复进行。您可能会发现,对操作的选择使编写具有客户端要求的保证的线程安全类型变得很困难。您可能在编写测试的第1步,第2步或实现的第3步或第4步中发现了这一点。如果是这种情况,请返回并优化ADT提供的一组操作。

五、锁定

锁是如此常用,以至于Java将其作为内置语言功能提供。

在Java中,每个对象都有与之隐式关联的锁- String,数组,anArrayList和您创建的每个类,其所有对象实例都有一个锁。即使是谦虚的人Object也有锁,因此,裸露的Objects通常用于显式锁:

Object lock = new Object();

你不能打电话acquire和release不过Java的内在锁。而是使用synchronized语句在语句块的持续时间内获取锁:

synchronized (lock) { // thread blocks here until lock is free
    // now this thread has the lock
    balance = balance + 1;
    // exiting the block releases the lock
}

这样的同步区域提供了互斥:一次只能有一个线程处于由给定对象的锁保护的同步区域中。换句话说,您回到了顺序编程世界,一次仅运行一个线程,至少相对于引用同一对象的其他同步区域而言。

锁定警卫对数据的访问
锁用于保护共享数据变量,例如此处显示的帐户余额。如果所有对数据变量的访问都由同一个锁对象保护(由同步块包围),则将确保这些访问是原子访问,而不会被其他线程中断。

由于Java中的每个对象都有与之隐式关联的锁,因此您可能会认为仅拥有一个对象的锁将阻止其他线程访问该对象。 事实并非如此。 获取与对象相关联的锁obj使用

synchronized (obj) { … }

在线程t中,它仅做一件事和一件事:阻止其他线程进入一个synchronized(obj)块,直到线程t完成其同步块为止。就是这样。

锁仅与获得相同锁的其他线程提供互斥。对数据变量的所有访问都必须由相同的锁保护。您可能会在一个锁后面保护整个变量集合,但是所有模块必须就它们将获取和释放的锁达成一致。

六、监控模式

在编写类的方法时,最方便的锁定是对象实例本身,即this。作为一种简单的方法,我们可以通过包装对rep内部的所有访问来保护类的整个rep synchronized (this)。

/** SimpleBuffer is a threadsafe EditBuffer with a simple rep. */
public class SimpleBuffer implements EditBuffer {
    private String text;
    ...
    public SimpleBuffer() {
        synchronized (this) {
            text = "";
            checkRep();
        }
    }
    public void insert(int pos, String ins) {
        synchronized (this) {
            text = text.substring(0, pos) + ins + text.substring(pos);
            checkRep();
        }
    }
    public void delete(int pos, int len) {
        synchronized (this) {
            text = text.substring(0, pos) + text.substring(pos+len);
            checkRep();
        }
    }
    public int length() {
        synchronized (this) {
            return text.length();
        }
    }
    public String toString() {
        synchronized (this) {
            return text;
        }
    }
}

请注意此处非常谨慎的纪律。 接触代表的每一种方法都必须加锁,即使是看似很小和琐碎的方法(如length()和)也要加锁toString()。这是因为读取和写入都必须受到保护-如果读取不受保护,则他们可能能够看到处于部分修改状态的代表。

这种方法称为监视模式。监视器是一个类,其方法是互斥的,因此一次只能有一个线程位于该类的实例中。

Java为监视模式提供了一些语法糖。如果将关键字添加synchronized到方法签名,则Java的行为就像您synchronized (this)在方法主体周围编写的一样。因此,以下代码是实现synced的等效方法SimpleBuffer:

/** SimpleBuffer is a threadsafe EditBuffer with a simple rep. */
public class SimpleBuffer implements EditBuffer {
    private String text;
    ...
    public SimpleBuffer() {
        text = "";
        checkRep();
    }
    public synchronized void insert(int pos, String ins) {
        text = text.substring(0, pos) + ins + text.substring(pos);
        checkRep();
    }
    public synchronized void delete(int pos, int len) {
        text = text.substring(0, pos) + text.substring(pos+len);
        checkRep();
    }
    public synchronized int length() {
        return text.length();
    }
    public synchronized String toString() {
        return text;
    }
}

请注意,SimpleBuffer构造函数没有synchronized关键字。Java实际上在语法上禁止使用它,因为构造中的对象应被限制在单个线程中,直到它从其构造函数中返回为止。因此,同步构造函数应该是不必要的。

七、具有同步的线程安全参数

现在我们已经SimpleBuffer用锁保护了rep,我们可以编写一个线程安全参数:

/** SimpleBuffer is a threadsafe EditBuffer with a simple rep. */
public class SimpleBuffer implements EditBuffer {
    private String text;
    // Rep invariant: 
    //   text != null
    // Abstraction function: 
    //   represents the sequence text[0],...,text[text.length()-1]
    // Safety from rep exposure:
    //   text is private and immutable
    // Thread safety argument:
    //   all accesses to text happen within SimpleBuffer methods,
    //   which are all guarded by SimpleBuffer's lock

GapBuffer如果我们使用监视模式来同步其所有方法,则相同的参数适用于。

请注意,类的封装(没有rep暴露)对于提出此论点非常重要。如果文字是公开的:

public String text;

那么外面的客户端SimpleBuffer将能够在不知道他们应该首先获得锁的情况下进行读写,并且SimpleBuffer不再是线程安全的。

锁定纪律
锁定规则是一种确保同步代码是线程安全的策略。我们必须满足两个条件:

1.每个共享的可变变量必须由一些锁来保护。除非已获取该锁的同步块内部,否则不能读取或写入数据。

2.如果一个不变量涉及多个共享的可变变量(甚至可能在不同的对象中),则所有涉及的变量都必须由相同的锁保护。线程获得锁后,必须在释放锁之前重新建立不变式。

此处使用的监控器模式满足这两个规则。rep中不变的变量所依赖的rep中所有共享的可变数据都由相同的锁保护。

八、原子操作

考虑对EditBuffer数据类型的查找和替换操作:

/** Modifies buf by replacing the first occurrence of s with t.
 *  If s not found in buf, then has no effect.
 *  @returns true if and only if a replacement was made
 */
public static boolean findReplace(EditBuffer buf, String s, String t) {
    int i = buf.toString().indexOf(s);
    if (i == -1) {
        return false;
    }
    buf.delete(i, s.length());
    buf.insert(i, t);
    return true;
}

此方法对进行了三个不同的调用buf—将其转换为字符串,以便进行搜索s,删除旧文本,然后t在其位置插入。即使每个调用都是原子的,该findReplace方法总体上也不是线程安全的,因为其他线程可能会在findReplace工作时改变缓冲区,从而导致该缓冲区删除错误的区域或将替换项放回错误的位置。

为防止这种情况,findReplace需要与的所有其他客户端同步buf。

授予客户访问锁的权限
使客户端可以使用数据类型的锁有时很有用,以便客户端可以使用它来使用您的数据类型实现更高级别的原子操作。

因此,解决该问题的一种方法findReplace是记录客户端可以使用EditBuffer的锁彼此进行同步:

/** An EditBuffer represents a threadsafe mutable string of characters
 *  in a text editor. Clients may synchronize with each other using the
 *  EditBuffer object itself. */
public interface EditBuffer {
   ...
}

然后findReplace可以在上同步buf:

public static boolean findReplace(EditBuffer buf, String s, String t) {
    synchronized (buf) {
        int i = buf.toString().indexOf(s);
        if (i == -1) {
            return false;
        }
        buf.delete(i, s.length());
        buf.insert(i, t);
        return true;
    }
}

这样做的效果是增大同步区域监视器图案已经把周围的个体toString,delete和insert方法,成确保所有三种方法不受其他线程干扰执行单原子区域。

synchronized到处撒?
那么线程安全仅仅是synchronized在程序中的每个方法上添加关键字的问题吗?不幸的是没有。

首先,您实际上不想随意地同步方法。同步会给您的程序带来很大的成本。由于需要获取锁(以及刷新缓存并与其他处理器进行通信),因此进行同步方法调用可能会花费更长的时间。正是由于这些性能原因,Java默认情况下使许多可变数据类型不同步。当您不需要同步时,请不要使用它。

synchronized以更故意的方式使用的另一个论点是,它最小化了对锁的访问范围。添加synchronized到每个方法都意味着您的锁就是对象本身,并且每个引用您对象的客户端都会自动引用您的锁,这样它就可以随意获取和释放。因此,您的线程安全机制是公开的,并且可能会受到客户端的干扰。与之相反,使用代表您的代表内部对象的锁,并使用synchronized()块适当且少量地获取它。

最后,向synchronized各处洒水实际上还不够。丢弃synchronized到一个方法,无需思维方式,你获取锁不假思索其锁定的,或者它是否是守卫共享数据访问你即将做正确的锁。假设我们试图通过findReplace简单地通过synchronized声明来解决的同步问题:

public static synchronized boolean findReplace(EditBuffer buf, ...) {

这不会做我们想要的。它确实会获取一个锁-因为它findReplace是一个静态方法,所以它将为findReplace碰巧位于其中的整个类获取一个静态锁,而不是实例对象锁。结果,一次只能调用一个线程findReplace-即使其他线程想要在不同的缓冲区上运行(这应该是安全的),它们仍然会被阻塞,直到释放单个锁为止。因此,我们将遭受极大的性能损失,因为大型多用户编辑器中只有一个用户一次只能进行查找和替换,即使他们都在编辑不同的文档也是如此。

但是,更糟的是,它不会提供有用的保护,因为与文档接触的其他代码可能不会获得相同的锁定。它实际上并不能消除我们的比赛条件。

该synchronized关键字也不是万能的。线程安全需要纪律-使用限制,不变性或锁来保护共享数据。而且该纪律需要写下来,否则维护人员将不知道它是什么。

九、设计并发数据类型

findReplace的问题可以用另一种方式来解释:该EditBuffer接口对多个并发客户端确实不是那么友好。它依靠整数索引来指定插入和删除位置,这些位置对于其他突变极为脆弱。如果其他人在索引位置之前插入或删除,则索引将无效。

因此,如果我们要设计一种专门用于并发系统的数据类型,则需要考虑提供一种在交错时具有更好定义的语义的操作。例如,最好EditBuffer与Position代表缓冲区中光标位置的数据类型配对,甚至与Selection代表选定范围的数据类型配对。获得后,aPosition可以保持其在文本中的位置,以防止其周围出现插入和删除,直到客户端准备使用它为止Position。如果其他某个线程删除了周围的所有文本Position,则Position能够通知后续客户发生了什么事情(也许有例外),并允许客户决定要做什么。在设计用于并发的数据类型时,这些考虑因素会起作用。

作为另一个示例,请考虑ConcurrentMapJava中的接口。该接口扩展了现有Map接口,添加了一些常见的方法,这些方法通常是共享可变映射上的原子操作所必需的,例如:

map.putIfAbsent(key,value) 是的原子版本
  if ( ! map.containsKey(key)) map.put(key, value);
map.replace(key, value) 是的原子版本
  if (map.containsKey(key)) map.put(key, value);

十、死锁抬起丑陋的头

线程安全性的锁定方法功能强大,但是(与限制和不变性不同)它在程序中引入了阻塞。线程有时必须等待其他线程离开同步区域,然后才能继续。阻塞会增加死锁的可能性。

当线程同时获取多个锁时,就会发生死锁,并且两个线程最终在持有锁的同时最终被阻塞,而每个锁都在等待对方释放。不幸的是,监视器模式使此操作相当容易。这是一个例子。

假设我们正在建模一系列书籍的社交网络:

public class Wizard {
    private final String name;
    private final Set<Wizard> friends;
    // Rep invariant:
    //    name, friends != null
    //    friend links are bidirectional: 
    //        for all f in friends, f.friends contains this
    // Concurrency argument:
    //    threadsafe by monitor pattern: all accesses to rep 
    //    are guarded by this object's lock

    public Wizard(String name) {
        this.name = name;
        this.friends = new HashSet<Wizard>();
    }

    public synchronized boolean isFriendsWith(Wizard that) {
        return this.friends.contains(that);
    }

    public synchronized void friend(Wizard that) {
        if (friends.add(that)) {
            that.friend(this);
        } 
    }

    public synchronized void defriend(Wizard that) {
        if (friends.remove(that)) {
            that.defriend(this);
        } 
    }
}

像Facebook一样,该社交网络是双向的:如果x是与y的朋友,那么y是与x的朋友。的friend()和defriend()通过修改这两个对象,这是因为它们使用在监视器模式的装置获取所述锁两个对象以及的代表方法执行该不变的。

让我们创建几个向导:

Wizard harry = new Wizard("Harry Potter");
Wizard snape = new Wizard("Severus Snape");

然后考虑两个独立线程重复运行时会发生什么:

// thread A                   // thread B
harry.friend(snape);          snape.friend(harry);
harry.defriend(snape);        snape.defriend(harry);

我们将很快陷入僵局。这就是为什么。假设线程A将要执行harry.friend(snape),线程B将要执行snape.friend(harry)。

线程A获得了锁定harry(因为friend方法已同步)。
然后线程B获得了锁定snape(出于相同的原因)。
他们俩都独立地更新各自的代表,然后尝试调用friend()另一个对象-这要求他们获得对另一个对象的锁定。
因此,A抱着哈利等着斯内普,而B抱着斯内普等着哈利。两个线程都卡在中friend(),因此任何一个都无法退出同步区域并将锁释放给另一个。这是经典的致命拥抱。该程序只是停止。

问题的实质是获取多个锁,并在等待另一个锁释放之前持有其中一些锁。

请注意,线程A和线程B可能交错而不会发生死锁:也许线程A在线程B有足够的时间获取第一个锁之前先获取并释放了这两个锁。如果死锁中涉及的锁也与竞争状况有关(并且通常也是如此),那么死锁将同样难以复制或调试。

死锁解决方案1:锁排序
防止死锁的一种方法是对需要同时获取的锁进行排序,并确保所有代码均按该顺序获取锁。

在我们的社交网络示例中,我们可能总是Wizard通过向导的名称按字母顺序获取对象上的锁。由于线程A和线程B都将需要Harry和Snape的锁,因此它们都将按以下顺序获取它们:Harry的锁,然后是Snape的锁。如果线程A在B之前先获得Harry的锁,它也将在B之前先获得Snape的锁,因为B在A再次释放Harry的锁之前无法进行。锁上的排序会强制对获取它们的线程进行排序,因此无法在等待图中生成周期。

代码如下所示:

  public void friend(Wizard that) {
        Wizard first, second;
        if (this.name.compareTo(that.name) < 0) {
            first = this; second = that;
        } else {
            first = that; second = this;
        }
        synchronized (first) {
            synchronized (second) {
                if (friends.add(that)) {
                    that.friend(this);
                } 
            }
        }
    }

(请注意,按照书名的字母顺序来排序锁的决定在本书中可以正常使用,但在现实生活的社交网络中却行不通。为什么不行呢?使用锁来比名称更好的方法是什么? )

尽管锁排序很有用(特别是在诸如操作系统内核之类的代码中),但在实践中有许多缺点。

首先,它不是模块化的-代码必须知道系统或至少其子系统中的所有锁。
其次,对于代码来说,即使在获取第一个锁之前,也可能很难或不可能准确地知道将需要哪些锁。它可能需要做一些计算才能弄清楚。例如,考虑考虑在社交网络图上进行深度优先搜索–在甚至开始寻找节点之前,您如何知道需要锁定哪些节点?
死锁解决方案2:粗粒度锁定
除锁定顺序外,更常见的方法是使用更粗略的锁定,特别是对于应用程序编程(与操作系统或设备驱动程序编程相反),即使用单个锁定来保护许多对象实例,甚至是程序的整个子系统。

例如,我们可能对整个社交网络只有一个锁,并且使其任何组成部分上的所有操作都在该锁上同步。在下面的代码中,所有都Wizard属于Castle,并且我们仅使用该Castle对象的锁进行同步:

public class Wizard {
    private final Castle castle;
    private final String name;
    private final Set<Wizard> friends;
    ...
    public void friend(Wizard that) {
        synchronized (castle) {
            if (this.friends.add(that)) {
                that.friend(this);
            }
        }
    }
}

粗粒度的锁可能会严重影响性能。如果您使用一个锁来保护大量可变数据,那么您将放弃同时访问任何数据的能力。在最坏的情况下,只有一个锁来保护所有内容,您的程序实际上可能是顺序的—一次只允许一个线程进行处理。

十一、实践中的并发

目标
现在是时候弹出一个关卡,看看我们在做什么。回想一下,我们的主要目标是创建一种可以避免错误,易于理解并且可以更改的软件。

对于所有这三个目标而言,构建并发软件显然是一项挑战。我们可以将问题分为两大类。当我们询问并发程序是否可以避免错误时,我们关心两个属性:

安全。 并发程序是否满足其不变式及其规范?争夺可变数据的竞争威胁了安全性。安全问一个问题:您能证明某些坏事永远不会发生吗?

活泼。 程序是否继续运行并最终执行您想要的操作,还是卡在某个地方永远等待着永远不会发生的事件?你能证明一些好事最终会发生吗?

僵局威胁生机。活动性可能还需要公平性,这意味着并发模块具有处理能力,可以在计算上取得进步。公平性主要是操作系统的线程调度程序的问题,但是您可以通过设置线程优先级来影响它(是好是坏)。

应对策略
实际程序中通常遵循哪些策略?

库数据结构要么不使用同步(为单线程客户端提供高性能,而将其留给多线程客户端以在顶部添加锁),要么使用监视模式。

具有许多部分的可变数据结构通常使用粗粒度锁定或线程限制。大多数图形用户界面工具箱都遵循这些方法之一,因为图形用户界面基本上是可变对象的大可变树。图形用户界面工具箱Java Swing使用线程限制。仅允许一个专用线程访问Swing的树。其他线程必须将消息传递到该专用线程才能访问树。

搜索通常使用不可变的数据类型。我们的布尔公式可满足性搜索将很容易成为多线程的,因为涉及的所有数据类型都是不可变的。不会有种族或僵局的风险。

操作系统通常使用细粒度的锁来获得高性能,并使用锁顺序来处理死锁问题。

我们忽略了一种可变共享数据的重要方法,因为它不在本课程的讨论范围内,但是值得一提:数据库。数据库系统广泛用于Web应用程序之类的分布式客户端/服务器系统。数据库使用事务来避免争用条件,这类似于同步区域,因为它们的影响是原子的,但是它们不必获取锁,尽管如果发现争用发生,则事务可能会失败并回滚。数据库还可以管理锁,并自动处理锁顺序。有关在系统设计中如何使用数据库的更多信息,强烈建议使用6.170 Software Studio。有关数据库如何在内部工作的更多信息,请使用6.814数据库系统。

而且,如果您对并发程序的性能感兴趣(由于性能通常是我们首先在系统上添加并发性的原因之一),那么6.172 Performance Engineering就是您的课程。

十二、概括

产生一个可以避免错误,易于理解并且可以进行更改的并发程序需要仔细考虑。一旦您尝试将Heisenbug固定下来,它们就会迅速消失,因此调试只是获得正确的线程安全代码的一种有效方法。而且线程可以以多种不同的方式交错操作,以致您将无法测试所有可能执行的一小部分。

设置有关数据类型的线程安全参数,并将其记录在代码中。

获取锁可以使线程对该锁保护的数据具有独占访问权,从而迫使其他线程进行阻塞,只要这些线程也试图获取该锁即可。

所述监视器模式守卫与由每一个方法获取的单个锁定一数据类型的代表。

通过获取多个锁引起的阻塞会产生死锁的可能性。

上一篇:boost官方文档同步机制Synchronization mechanisms overview


下一篇:spring boot+SSM项目中JSP页面遇到的问题