【HIT-SC-MEMO7】哈工大2022软件构造 复习笔记7

七、并行

7.1 并发Concurrent

并发：

Two Models for Concurrent Programming：

• 共享内存：在内存中读写共享数据

  • 两个处理器，共享内存
  • 同一台机器上的两个程序，共享文件系统
  • 同一个Java程序内的两个线程，共享Java对象
    

• 消息传递：通过channel交换消息

  • 网络上的两台计算机，通过网络连接通讯
  • 浏览器和Web服务器，A请求页面，B发送页面数据给A
  • 即时通讯软件的客户端和服务器
  • 同一台计算机上的两个程序，通过管道连接进行通讯

进程和线程

Process 进程

• 私有空间，彼此隔离
• 拥有整台计算机的资源
• 多进程之间不共享内存
• 一般来说，进程 = 程序 =应用
• JVM通常运行单一进程，但也可以创建新的进程

Threads 线程

• 程序内部的控制机制
• 共享内存
• 区分：进程 = 虚拟机；线程=虚拟CPU
  

常见应用：

Java中创建线程的两种方式
注意：要使用.start()方法，而不是.run()

从Thread类派生出子类：

• 这个方法由于是通过继承来实现的，所以如ADT已经有父类了，就不能使用这种方法了，所以应用较少。

//从Thread类派生子类
public class HelloThread extends Thread {
    
	public void run() {
     //待做的事都放在这个方法中，所以这个方法必须实现
		System.out.println("Hello from a thread!");
	}
	public static void main(String args[]) {
    //两种启动线程的方式
		HelloThread p = new HelloThread();
		p.start(); //注意是使用start()方法来启动的
        //或者可以直接这样
    	(new HelloThread()).start();
	}
}

从Runnable接口构造Thread对象：

• 更常用

//实现Runnable接口
public class HelloRunnable implements Runnable {
    
	public void run() {
     //与方法一相同
		System.out.println("Hello from a thread!");
	}
	public static void main(String args[]) {
    
		(new Thread(new HelloRunnable())).start(); //启动方式略有不同
	}
}
//另一种实现方式是实现匿名类来实现Runnable接口
new Thread(new Runnable() {
    
	public void run() {
    
		System.out.println("Hello");
	}
}).start();

交错和竞争

Time slicing 时间分片

• 通过时间分片，在多个进程/线程之间共享处理器
• 时间分片是由OS自动调度的
• 程序应该在任何调度方案下正常执行
  

共享内存和消息传递都会带来交错和竞争

并行程序难以测试和调试：

• 很难测试和调试因为竞争条件导致的bug
• 因为交错的存在，导致很难复现bug
• 增加print语句甚至导致这种bug消失！

利用某些方法调用来主动影响线程之间的交错关系

• Thread.sleep(time)：线程的休眠
• Thread.interrupt()：向线程发出中断信号
• Thread.yield()：使用该方法，线程告知调度器放弃CPU的占用权，从而可能引起调度器唤醒其他线程。尽量避免使用该方法。
• Thread.join()：让当前线程保持执行，直到其执行结束。

t.isInterrupted()检查t是否已在中断状态中
当某个线程被中断后，一般来说应停止其run()中的执行，取决于程序员在run()中处理

7.2 线程安全策略

• 线程之间的“竞争条件”：作用于同一个mutable数据上的多个线程，彼此之间存在对该数据的访问竞争并导致interleaving，导致post-condition可能被违反，这是不安全的。
  

紧闭 Confinement

线程之间不共享mutable数据类型
如果一个ADT的rep中包含mutable的属性且多线程之间对其进行mutator操作，那么就很难使用confinement策略来确保该ADT是线程安全的

不可变 Immutability

使用不可变数据类型和不可变引用，避免多线程之间的race condition
final：变量只读，不可写
如果ADT中使用了beneficent mutation，必须要通过“加锁”机制来保证线程安全

线程安全数据类型

如果必须要用mutable的数据类型在多线程之间共享数据，要使用线程安全的数据类型
集合类都是线程不安全的

一般来说，JDK同时提供两个相同功能的类，一个是threadsafe，另一个不是。原因：threadsafe的类一般性能上受影响

• Java API提供了进一步的decorator：synchronizedXXX

private static Map<Integer,Boolean> cache = Collections.synchronizedMap(new HashMap<>());

• 在使用synchronizedMap(hashMap)之后，不要再把参数hashMap共享给其他线程，不要保留别名，一定要彻底销毁
• 即使在线程安全的集合类上，使用iterator也是不安全的
• 即使是线程安全的集合类，仍可能产生竞争：执行其上某个操作是threadsafe的，但如果多个操作放在一起，仍旧不安全

Synchronization & Lock

Principle：线程安全不应依赖于偶然

同步机制：通过锁的机制共享线程不安全的可变数据，变并行为串行。

Locks：

• 使用锁机制，获得对数据的独家mutation权，其他线程被阻塞，不得访问
• acquire：允许线程获得锁的所有权
• release：放弃锁的所有权，允许另一个线程获得它的所有权。

使用方法：

• 在Java中，任何对象都可以作为锁。可以创建一个没有意义的对象Object lock = new Object();作为锁来使用，而拥有lock的线程可独占式的执行该部分代码。

Object lock = new Object();
synchronized (lock) {
     // 线程阻塞在这里，直到锁被释放
	// 现在这个线程获得了这把锁
	do1(); //这个块中的所有语句都不能被打断了
	// 退出块的同时释放锁
}
// 此时在另一个线程里有如下代码
synchronized (lock) {
     //要等待lock被释放才能开始执行
	do2(); //与上面线程里的代码操作的是同一个数据
}

作用：

• mutual exclusion互斥
• 拥有lock的线程可独占式的执行该部分代码

• 要互斥，必须使用同一个lock进行保护
• 对synchronized的方法，多个线程执行它时不允许interleave，也就是说“按原子的串行方式执行”

ADT加锁：

• 用ADT自己做lock：synchronized(this)
• 所有对ADT的rep的访问都加锁

Monitor模式：

• ADT所有方法都是互斥访问
• 方法关键字中加入synchronized相当于synchronized(this)

// 将synchronized关键字加在了方法声明里，效果与上面的写法相同
public synchronized void xxx(...){
    
    ...
}

在任何地方synchronized？
No!

• 同步机制给性能带来极大影响
• 尽可能减小lock的范围
• public static synchronized boolean findReplace(EditBuffer buf, ...)
  • 使用static方法意味着在class层面上锁，对性能带来极大损耗。

所有关于threadsafe的设计决策也都要在ADT中记录下来

Locking discipline

• 任何共享的mutable变量/对象必须被lock所保护
• 涉及到多个mutable变量的时候，它们必须被同一个lock所保护
• monitor pattern中，ADT所有方法都被同一个synchronized(this)所保护

方法加synchronized关键字：将多个atomic的操作组合为更大的atomic操作

死锁

死锁：多个线程竞争lock，相互等待对方释放lock。

• 典型的形式：交错申请锁

// T1: 
synchronized(a){
     //T1线程拿到了a锁
    synchronized(b){
     //T1线程等待T2线程释放b锁
        ...
    } 
}
// T2: 
synchronized(b){
     //T2线程拿到了b锁
    synchronized(a){
     //T2线程等待T1线程事放a锁
       ...
    }
}

解决办法：

• lock ordering 锁排序：对所有的锁进行排序，按照排好的顺序来申请锁，所以，就一定会有一个线程最先拿到第一把锁，进而可以拿到所有的锁（因为其他线程拿不到第一把锁，都被挂起了）。

这个办法不是很常用，因为不是所有的对象都可以排序，而如果只是为了增加锁的功能而实现Comparable就太不划算了。

• coarse-grained locking 增加锁：除了原来使用的锁之外，在最外层增加一个新的锁，所有的线程都会先去申请这把锁，没申请到的线程自然就都被挂起了，所以拿到第一把锁的线程就能拿到所有的锁了。这个办法比较常用。

这两个办法的思想都是要让所有的线程在第一次申请锁的时候申请同一把锁，因此当一个线程先拿到一把锁的时候其他线程都被挂起了，所以这个线程就能顺利拿到后面所有的锁，因而避免了死锁。