并行模式与算法
仅作为笔记
本文参考博客：https://blog.csdn.net/m0_38109046/article/details/89449305
文章目录
前言
仅作为笔记
一、并行流水线
是一种设计思路，并不是特定的个某种函数实现。
- 应用场景：一项任务无法拆封成多步骤来做的时候。
- 核心思想：让每一个线程只负责一个整体任务中的某一个部分，他们之间存在着任务完成后交接关系，就像流水线那样，这样当流水线满载的时候可以极大的缩短运行时间。如图：
二、并行搜索
也是一种设计思想，当面对无序排序的时候，可以将序列分为多段让各个线程去搜索分段，找到答案就停止。
三、并行排序
3.1 分离数据相关性：奇偶交换排序
以冒泡为例，其每次比较交换都是前后有关联的，那么怎么才能解除这个关联呢？只有解除了关联才能将其中的步骤并行化。使用奇偶分两阶段即可解决。如下图：
此时看来每一次的比较交换都没有了关联，就可以使用多线程了。
3.2 改进的插入排序：希尔排序
希尔排序是一种插入排序，也称为缩小增量排序。
- 基本思想：希尔排序按增量进行分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的元素越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
- 步骤：选择增量变化规则如gap=length/2，这种增量用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。其余步骤如下图：
四、并行算法：矩阵乘法
嗯。。。。我认为这个应该在python中讲比较好
五、BIO
先知道几个东西：
- 同步与异步
同步： 同步就是发起一个调用后，被调用者未处理完请求之前，调用不返回。
异步： 异步就是发起一个调用后，立刻得到被调用者的回应表示已接收到请求，但是被调用者并没有返回结果，此时我们可以处理其他的请求，被调用者通常依靠事件，回调等机制来通知调用者其返回结果。 - 阻塞和非阻塞
阻塞： 阻塞就是发起一个请求，调用者一直等待请求结果返回，也就是当前线程会被挂起，线程无法从事其他任务，只有当条件就绪才能继续。
非阻塞： 非阻塞就是发起一个请求，调用者不用一直等着结果返回，可以先去干其他事情。
注意：不要把同步和阻塞概念搞混了，前者针对的是一件事，而后者针对的是一个线程。
下面这个例子来自https://blog.csdn.net/m0_38109046/article/details/89449305
举个生活中简单的例子，你妈妈让你烧水，小时候你比较笨啊，在哪里傻等着水开（同步阻塞BIO）。等你稍微再长大一点，你知道每次烧水的空隙可以去干点其他事，然后只需要时不时来看看水开了没有（同步非阻塞NIO）。后来，你们家用上了水开了会发出声音的壶，这样你就只需要听到响声后就知道水开了，在这期间你可以随便干自己的事情，你需要去倒水了（异步非阻塞AIO）。
- 传统BIO：同步阻塞I/O模式，数据的读取写入必须阻塞一个线程内等待其完成。一客户一线程，如下图（图片来自https://blog.csdn.net/m0_38109046/article/details/89449305）：
由一个独立的 Acceptor 线程负责监听客户端的连接。一般在 while(true) 循环中服务端会调用 accept() 方法等待接收客户端的连接的方式监听请求，请求一旦接收到一个连接请求，就可以建立通信套接字在这个通信套接字上进行读写操作，此时不能再接收其他客户端连接请求，只能等待同当前连接的客户端的操作执行完成， 不过可以通过多线程来支持多个客户端的连接。 - BIO 通信模型同时处理多个客户端请求：必须使用多线程（主要原因是 socket.accept()、 socket.read()、 socket.write() 涉及的三个主要函数都是同步阻塞的），也就是说它在接收到客户端连接请求之后为每个客户端创建一个新的线程进行链路处理，处理完成之后，通过输出流返回应答给客户端，线程销毁。这就是典型的 一请求一应答通信模型 。这个连接不做任何事情的话就会造成不必要的线程开销，不过可以通过线程池机制改善，线程池还可以让线程的创建和回收成本相对较低。使用FixedThreadPool （实际上还有任务队列）可以有效的控制了线程的最大数量，保证了系统有限的资源的控制，实现了N(客户端请求数量):M(处理客户端请求的线程数量)的伪异步I/O模型（N 可以远远大于 M）。
5.1 伪异步IO
- 简而言之，就是用线程池实现多线程的BIO，如下图
当有新的客户端接入时，将客户端的 Socket 封装成一个Task（该任务实现java.lang.Runnable接口）投递到后端的线程池中进行处理，JDK 的线程池维护一个消息队列和 N 个活跃线程，对消息队列中的任务进行处理。
六、准备好了再通知我：网络NIO
6.1NIO简介
- NIO是一种同步非阻塞的I/O模型，对应 java.nio 包，提供了 Channel , Selector，Buffer等抽象。它支持面向缓冲的，基于通道的I/O操作方法。 NIO提供了与传统BIO模型中的 Socket 和 ServerSocket 相对应的 SocketChannel 和 ServerSocketChannel 两种不同的套接字通道实现,两种通道都支持阻塞和非阻塞两种模式。对于低负载、低并发的应用程序，可以使用同步阻塞I/O来提升开发速率和更好的维护性；对于高负载、高并发的（网络）应用，应使用 NIO 的非阻塞模式来开发。
6.2NIO特性和IO的区别
1）IO流是阻塞的，NIO流是不阻塞的。
Java NIO 可以进行非阻塞IO操作。比如，单线程中从通道读取数据到buffer，同时可以继续做别的事情，当数据读取到buffer中后，线程再继续处理数据。写数据也是一样的。另外，非阻塞写也是如此。一个线程请求写入一些数据到某通道，但不需要等待它完全写入，这个线程同时可以去做别的事情。
Java IO的各种流是阻塞的。这意味着，当一个线程调用 read() 或 write() 时，该线程被阻塞，直到有一些数据被读取，或数据完全写入。该线程在此期间不能再干任何事情了
2）Buffer(缓冲区)——IO 面向流(Stream oriented)，而 NIO 面向缓冲区(Buffer oriented)。
Buffer是一个对象，它包含一些写入写出数据。在NIO类库中加入Buffer对象，体现了新库与原I/O的一个重要区别。在面向流的I/O中，可以将数据直接写入或者将数据直接读到 Stream 对象中。虽然 Stream 中也有 Buffer 开头的扩展类，但只是流的包装类，还是从流读到缓冲区，而 NIO 却是直接读到 Buffer 中进行操作，在NIO厍中，所有数据都是用缓冲区处理的。
3）Channel (通道)
NIO 通过Channel（通道） 进行读写。
通道是双向的，可读也可写，而流的读写是单向的。无论读写，通道只能和Buffer交互。因为 Buffer，通道可以异步地读写（比如这个通道正在读数据到Buffer，但是还没把数据弄完，这时候BIO不会等待任务完成，而是可以同时利用这个Channel进行写）。
4）Selectors(选择器)
NIO有选择器，而IO没有。
简而言之作用就是利用单个线程来维护的一个通道管理器。
6.3 NIO 读数据和写数据方式
- 从通道进行数据读取 ：创建一个缓冲区，然后请求通道读取数据。
- 从通道进行数据写入 ：创建一个缓冲区，填充数据，并要求通道写入数据。
如下所示：
注意：开发中由于JDK提供的NIO太复杂了，所以一般使用Netty（改善了JDK原生NIO）
七、读完了再通知我：AIO
AIO也叫NIO.2，是异步非阻塞I/O。 Java 7 中引入的。异步 IO 是基于事件和回调机制实现的，也就是应用操作之后会直接返回（这时候并没有处理完数据，只是先返回了让线程做其他的事），不会堵塞在那里。
AIO 是异步IO的缩写，虽然 NIO 在网络操作中，提供了非阻塞的方法，但是 NIO 的 IO 行为还是同步的。对于 NIO 来说，我们的业务线程是在 IO 操作准备好时，得到通知，接着就由这个线程自行进行 IO 操作，IO操作本身是同步的。
NIO与AIO对比：
Java NIO ： 用户进程发起一个IO操作以后边可返回做其它事情，但是用户进程需要时不时的询问IO操作是否就绪，这就要求用户进程不停的去询问，从而引入不必要的CPU资源浪费。
Java AIO(NIO.2) ：用户进程只需要发起一个IO操作然后立即返回（此时任务还没完成），等IO操作真正的完成以后，应用程序会得到IO操作完成的通知，此时用户进程只需要对数据进行处理就好了，不需要进行实际的IO读写操作，因为真正的IO读取或者写入操作已经由内核完成了。
NIO方式适用于连接数目多且连接比较短（轻操作）的架构，比如聊天服务器，并发局限于应用中，编程比较复杂，JDK1.4开始支持。
AIO方式使用于连接数目多且连接比较长（重操作）的架构，比如相册服务器，充分调用OS参与并发操作，编程比较复杂，JDK7开始支持