Skip to content

并发编程

共享模式

  • 共享内存模型，通过读写内存中的共享对象进行交互

    • A 和 B 可能是同一台计算机中的两个处理器（或处理器核心），共享相同的物理内存。
    • A 和 B 可能是在同一台计算机上运行的两个程序，共享一个可以读写的公共文件系统。
    • A 和 B 可能是同一个 Java 程序中的两个线程，共享相同的 Java 对象。

  • 消息传递模型，通过通信通道相互发送消息进行交互

    • A 和 B 可能是网络中的两台计算机，通过网络连接通信。
    • A 和 B 可能是一个网页浏览器和一个网页服务器 — A 向 B 发起连接并请求一个网页，B 则将网页数据发送回 A。
    • A 和 B 可能是即时通讯客户端和服务器。
    • A 和 B 可能是同一台计算机上运行的两个程序，它们的输入和输出通过管道连接，比如在命令提示符中输入的 ls | grep 命令。

防止冲突

  • 避免共享变量

  • 使用 immutable 类型：一个类型被称为不可变的，如果其对象在整个生命周期内始终代表相同的抽象值。这意味着从客户端的角度看，对象的状态从未改变过。（但并不意味内部状态没有发生变化，如缓存导致的）

    • immutable 类型的设计策略：不要提供可以修改字段或字段引用的对象的方法。字段应该被声明为 private 以确保封装性，被声明为 final 确保它们只能被赋值一次。防止子类覆盖方法。不要共享可变对象的引用。

  • 使用线程安全的数据类型

    • 使用包装器 
      private static Map<Integer,Boolean> cache =
                Collections.synchronizedMap(new HashMap<>());
  • 注意不要绕过包装器进行访问
  • 使用包装器并不能保证不出现问题，如先检查 contain 与 get 之间有 pop

  • 同步机制确实可以保证单个方法或代码块在同一时间只能被一个线程访问，从而保证了该方法或代码块内操作的原子性和可见性。但是，同步机制本身并不能保证更高级别的操作序列（即由多个方法调用组成的操作）的线程安全性。

  • 使用 synchronization

锁与 synchroonization

  • 对于抽象数据结构应该在数据结构内实现锁，而不应该对用户的使用方式做出要求

  • 使用 synchronization 实现线程安全的抽象数据类型

    • 指定（Specify）:定义操作（方法签名和规格）。这已经在 EditBuffer 接口中完成。
    • 测试（Test）: 为操作开发测试用例。参见提供的代码中的 EditBufferTest。测试套件基于对操作参数空间的分区来制定测试策略。
    • 选择表示（Rep）:
      • 首先实现一个简单的表示。它更容易编写，更有可能做对，它将验证你的测试用例和规格，因此可以在转移到更难的实现之前修复它们中的问题。这就是为什么我们在转移到 GapBuffer 之前实现了 SimpleBuffer。不要丢弃你的简单版本——保留它，以便在更复杂的版本出现问题时，有东西可以测试和比较。
      • 写下表示不变性和抽象函数，并实现 checkRep()。在每个构造器、生成器和变异器方法的末尾断言表示不变性。
    • 同步（Synchronize）:论证你的表示是线程安全的。将它明确地写下来，作为类中表示不变性旁边的注释，以便维护者知道你是如何在类中设计线程安全性的。
    • 迭代（Iterate）: 你可能会发现，你选择的操作使得很难用客户端需要的保证来编写线程安全类型。你可能在第 1 步中发现这一点，或者在第 2 步编写测试时发现，或者在第 3 步或第 4 步实现时发现。如果是这种情况，返回并细化你的 ADT 提供的操作集。

  • 实现原子操作

安全性论证

  • 列出模块或程序中所有存在的线程以及它们使用的数据。
  • 对于每个数据对象或变量，需要论证你使用了四种技术中的哪一种来防止竞态条件。
    • 当使用线程安全数据类型或同步时，还需要论证所有对数据的访问都是适当的原子性操作。也就是说，需要确保依赖的不变量不会因为线程之间的交错执行而受到威胁。
/** MyString is an immutable data type representing a string of characters. */
public class MyString {
    private final char[] a;
    private final int start;
    private final int len;
    // Rep invariant:
    //    0 <= start <= a.length
    //    0 <= len <= a.length-start
    // Abstraction function:
    //    represents the string of characters a[start],...,a[start+length-1]
    // Thread safety argument:
    //    This class is threadsafe because it's immutable:
    //    - a, start, and len are final
    //    - a points to a mutable char array, which may be shared with other
    //      MyString objects, but they never mutate it
    //    - the array is never exposed to a client

网络编程

  • socket 的分类

    • 监听套接字：服务器进程使用监听套接字等待来自远程客户端的连接。
    • 连接套接字：连接套接字可以向连接另一端的进程发送和接收消息。通过本地 IP 地址和端口号以及远程地址和端口号进行标识，这允许服务器区分来自不同 IP 的并发连接，或者来自同一 IP 的不同远程端口的并发连接。

  • 网络协议的设计

    • 保持消息类型的数量小：更好的方法是有一些可以组合的命令和响应，而不是许多复杂的消息。消息集合必须足以让客户端进行他们需要的请求，让服务器传递结果。
    • 追求协议的平台独立性，协议不涉及如何在磁盘上存储网页、服务器如何准备或生成网页、客户端将使用什么算法来渲染它们等。
    • 安全：安全防错、错误易于理解、如果未来需要对协议进行更改使用的旧版本的旧客户端或服务器可以继续工作。
    • 序列化：序列化是将内存中的数据结构转换为可以容易存储或传输的格式的过程

  • 服务器与客户端的测试测试：

    • 将网络代码与数据结构算法代码分离，确保将客户端/服务器程序中的大部分抽象数据类型（ADT）指定、测试和实现为独立的组件，这些组件不依赖于网络。
    • 将套接字代码与流代码分离，需要读取和写入套接字的函数或模块可能只需要访问输入/输出流，而不是套接字本身。
      • 即在进行测试时使用本地流替代网络流

  • 文本消息协议的描述 

    MESSAGE ::= BOARD | BOOM | HELP | HELLO
BOARD ::= LINE+
LINE ::= (SQUARE SPACE)* SQUARE NEWLINE
SQUARE ::= "-" | "F" | COUNT | SPACE
SPACE ::= " "
NEWLINE ::= "\n" | "\r" "\n"?
COUNT ::= [1-8]
BOOM ::= "BOOM!" NEWLINE
HELP ::= [^\r\n]+ NEWLINE
HELLO ::= "Welcome to Minesweeper. Board: " X " columns by " Y " rows. Players: " N
          " including you. Type 'help' for help." NEWLINE
X ::= INT
Y ::= INT
N ::= INT
INT ::= "-"? [0-9]+

  • “”内的为直接使用的文本，大写字母为进一步定义的"变量"

死锁的处理

  • 需要使用多个锁时保证按照固定的顺序获取锁 (如字典序) 

        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);
                } 
            }
        }
    }

  • 粗粒度锁定，使用单个锁来保护许多对象实例 

    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);
            }
        }
    }
}