进程

进程、线程、协程的概念

进程：是并发执行的程序在执行过程中分配和管理资源的基本单位，是一个动态概念，竞争计算机系统资源的基本单位。
线程：是进程的一个执行单元，是进程内的调度实体。比进程更小的独立运行的基本单位。线程也被称为轻量级进程。
协程：是一种比线程更加轻量级的存在。一个线程也可以拥有多个协程。其执行过程更类似于子例程，或者说不带返回值的函数调用。

进程间通信

六种方式

管道/消息队列/信号/信号量/共享内存/socket/

• 管道
  管道分为命名管道和无名管道，在内核中申请一块固定大小的缓冲区，程序拥有写入和读取的权利，都可以看成一种特殊的文件，具有固定的读端和写端，也可以使用普通的read、write 等函数。但是它不是普通的文件，并不属于其他任何文件系统，并且只存在于内存中；无名管道一般使用fork函数实现父子进程的通信，命名管道用于没有血缘关系的进程也可以进程间通信；面向字节流、自带同步互斥机制、半双工，单向通信，两个管道实现双向通信。

• 消息队列
  在内核中创建一队列，队列中每个元素是一个数据报，不同的进程可以通过句柄去访问这个队列；消息队列独立于发送与接收进程，可以通过顺序和消息类型读取，也可以fifo读取；消息队列可实现双向通信。

• 信号量
  在内核中创建一个信号量集合（本质是个数组），数组的元素（信号量）都是1，使用P操作进行-1，使用V操作+1，通过对临界资源进行保护实现多进程的同步

• 共享内存
  将同一块物理内存一块映射到不同的进程的虚拟地址空间中，实现不同进程间对同一资源的共享。目前最快的IPC形式，不用从用户态到内核态的频繁切换和拷贝数据，直接从内存中读取就可以，共享内存是临界资源，所以需要操作时必须要保证原子性。使用信号量或者互斥锁都可以。

• socket
  是应用层与TCP/IP协议族通信的中间软件抽象层，它是一组接口，把复杂的TCP/IP协议族隐藏在Socket接口后面，对用户来说，一组简单的接口就是全部，让Socket去组织数据。socket起源于UNIX，在Unix一切皆文件哲学的思想下，socket是一种”打开—读/写—关闭”模式的实现，服务器和客户端各自维护一个”文件”，在建立连接打开后，可以向自己文件写入内容供对方读取或者读取对方内容，通讯结束时关闭文件。是一种可以网间通信的方式。

管道通信

匿名管道

管道的四种情况
如果管道内部是空的并且写端没有关闭，此时读取条件不具备，读端会被阻塞，等待写入数据
如果管道内部被写满了并且读端没有关闭，此时写入条件不具备，写端会被阻塞，等待读端读取数据
如果管道一直在读，但是已经关闭了写端，此时读端read返回值会一直读到0，表示读到了文件末尾
如果管道一直在写，但是已经关闭了读端，此时OS会直接使用13号信号杀死进程，代表进程异常
2.5 管道的五种特征
匿名管道只能进行有血缘关系的进程之间进行通信，因为匿名管道是依靠子进程继承父进程的文件描述符表实现的（通常用于实现父子进程之间的通信）
管道内部自带进程的同步机制，多执行流执行代码时具有明显的顺序性，写入管道的数据直到被读取之前会保持在管道缓冲区中（如果缓冲区未满），而读取操作则会等待直到有数据可读，这种机制避免了同时读写导致的数据损坏问题
管道文件的生命周期是随进程的，当所有打开该文件的进程都退出后，该文件资源也会被释放
管道文件在进行通信时是面向字节流的，读与写的次数不是一 一匹配的，数据没有明确的分割，一次拿多少数据都行
管道通信是一种特殊的半双工模式。半双工通信允许数据在两个方向上传输，但不能同时进行。这意味着在任何时候，数据只能在一个方向流动。一旦一方开始发送数据，另一方必须等待接收完毕后才能开始发送。全双工通信允许数据同时在两个方向上进行传输，无需等待。由于半双工模式是可以双向传输数据的，但是管道只能单向通信，所以是特殊的半双工模式

当一个进程以读和写的方式分别打开一个文件，由于打开方式的不同，就会创建两个struct file，每个文件都有自己的属性、数据、更重要的是存在内核级的文件缓冲区，两个struct file除了打开方式字段不同，其余信息都是相同的，所以操作系统不会将文件的信息在拷贝一份，两个struct file指向的文件信息是一份。当该进程创建子进程，子进程会继承父进程的文件描述符表，此时父子进程可以对同一个文件进行读取操作，该文件中的缓冲区就相当于一个共享资源，这个缓冲区也成为道，两个进程间就可以进行通信了

命名管道

当一个进程以读的方式打开一个文件，该进程会有自己的进程PCB和文件描述符表，同时会创建一个struct file
当另一个进程以写的方式也打开这个文件，该进程也会有自己的进程PCB、文件描述符表，并且也会创建一个struct file，但是由于这两个进程打开的文件是一样的，而struct file也就是打开文件的方式不同，所以两个struct file都是指向的同一份文件信息，也指向了同一个内核级文件缓冲区，那么这两个毫无关系的进程就指向了同一段空间，就可以进行通信了。

怎么确保两个进程打开的是同一个文件呢？---------文件的路径

进程和线程的区别

• 根本区别

  • 进程是操作系统（OS）资源分配（内存，文件，网络，设备）的基本单位，
  • 线程是处理器（CPU）任务调度和执行的基本单位。

• 资源开销：

  • 每个进程都有独立的代码和数据空间（程序上下文）,程序之间的切换会有较大的开销；
  • 线程可以看做轻量级的进程，同一类线程共享代码和数据空间，每个线程都有自己独立的运行栈和程序计数器（PC),线程之间切换的开销小。

• 包含关系：
  如果一个进程内有多个线程，则执行过程不是一条线的，而是多条线程共同完成的；
  线程是进程的一部分，所行过程不是一条线的，而是多条线（线耗）其被称为轻权进程或者轻量级进程。

• 内存分配：
  同一进程的线程共享本进程的空间和资源，而进程之间的地址空间和资源是相互独立的。

• 影响关系：
  一个进程崩溃后，在保护模式下不会对其他进程产生影响，但是一个线程崩溃整个进程都死掉。所以多进程要比多线程健壮。

• 执行过程：
  每个独立的进程有程序运行的入口、顺序执行序列和程序出口。但是线程不能独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制，两者均可并发执行。

线程

线程的状态转换

参考文章

线程在一定条件下，状态会发生变化。线程一共有以下几种状态：

1、新建状态(New)：新创建了一个线程对象。

2、就绪状态(Runnable)：线程对象创建后，其他线程调用了该对象的start()方法。该状态的线程位于“可运行线程池”中，变得可运行，只等待获取CPU的使用权。即在就绪状态的进程除CPU之外，其它的运行所需资源都已全部获得。

3、运行状态(Running)：就绪状态的线程获取了CPU，执行程序代码。

4、阻塞状态(Blocked)：阻塞状态是线程因为某种原因放弃CPU使用权，暂时停止运行。直到线程进入就绪状态，才有机会转到运行状态。

阻塞的情况分三种：

(1)、等待阻塞：运行的线程执行wait()方法，该线程会释放占用的所有资源，JVM会把该线程放入“等待池”中。进入这个状态后，是不能自动唤醒的，必须依靠其他线程调用notify()或notifyAll()方法才能被唤醒。

(2)、同步阻塞：运行的线程在获取对象的同步锁时，若该同步锁被别的线程占用，则JVM会把该线程放入“锁池”中。

(3)、其他阻塞：运行的线程执行sleep()或join()方法，或者发出了I/O请求时，JVM会把该线程置为阻塞状态。当sleep()状态超时、join()等待线程终止或者超时、或者I/O处理完毕时，线程重新转入就绪状态。

——当线程试图获取某个对象的同步锁时，如果该锁被其他线程所持有，则当前线程进入阻塞状态，如果想从阻塞状态进入就绪状态必须得获取到其他线程所持有的锁。
——当线程调用了一个阻塞式的IO方法时，该线程就会进入阻塞状态，如果想进入就绪状态就必须要等到这个阻塞的IO方法返回。
——当线程调用了某个对象的wait（）方法时，也会使线程进入阻塞状态，notify（）方法唤醒。
——调用了Thread的sleep（long millis）。线程睡眠时间到了会自动进入阻塞状态。
——一个线程调用了另一个线程的join（）方法时，当前线程进入阻塞状态。等新加入的线程运行结束后会结束阻塞状态，进入就绪状态。

5、死亡状态(Dead)：线程执行完了或者因异常退出了run()方法，该线程结束生命周期。

线程变化的状态转换图如下：
image.png
注：拿到对象的锁标记，即为获得了对该对象(临界区)的使用权限。即该线程获得了运行所需的资源，进入“就绪状态”，只需获得CPU，就可以运行。因为当调用wait()后，线程会释放掉它所占有的“锁标志”，所以线程只有在此获取资源才能进入就绪状态。
下面小小的作下解释：
1、线程的实现有两种方式，一是继承Thread类，二是实现Runnable接口，但不管怎样， 当我们new了这个对象后，线程就进入了初始状态；
2、当该对象调用了start()方法，就进入就绪状态；
3、进入就绪后，当该对象被操作系统选中，获得CPU时间片就会进入运行状态；
4、进入运行状态后情况就比较复杂了
4.1、run()方法或main()方法结束后，线程就进入终止状态；
4.2、当线程调用了自身的sleep()方法或其他线程的join()方法，进程让出CPU，然后就会进入阻塞状态（该状态既停止当前线程，但并不释放所占有的资源即调用sleep ()函数后，线程不会释放它的“锁标志”。）。当sleep()结束或join()结束后，该线程进入可运行状态，继续等待OS分配CPU时间片。典型地，sleep()被用在等待某个资源就绪的情形：测试发现条件不满足后，让线程阻塞一段时间后重新测试，直到条件满足为止。
4.3、线程调用了yield()方法，意思是放弃当前获得的CPU时间片，回到就绪状态，这时与其他进程处于同等竞争状态，OS有可能会接着又让这个进程进入运行状态； 调用 yield() 的效果等价于调度程序认为该线程已执行了足够的时间片从而需要转到另一个线程。yield()只是使当前线程重新回到可执行状态，所以执行yield()的线程有可能在进入到可执行状态后马上又被执行。
4.4、当线程刚进入可运行状态（注意，还没运行），发现将要调用的资源被synchroniza（同步），获取不到锁标记，将会立即进入锁池状态，等待获取锁标记（这时的锁池里也许已经有了其他线程在等待获取锁标记，这时它们处于队列状态，既先到先得），一旦线程获得锁标记后，就转入就绪状态，等待OS分配CPU时间片；

4.5.suspend() 和 resume()方法：两个方法配套使用，suspend()使得线程进入阻塞状态，并且不会自动恢复，必须其对应的resume()被调用，才能使得线程重新进入可执行状态。典型地，suspend()和 resume() 被用在等待另一个线程产生的结果的情形：测试发现结果还没有产生后，让线程阻塞，另一个线程产生了结果后，调用 resume()使其恢复。
4.6、wait()和 notify() 方法：当线程调用wait()方法后会进入等待队列（进入这个状态会释放所占有的所有资源，与阻塞状态不同），进入这个状态后，是不能自动唤醒的，必须依靠其他线程调用notify()或notifyAll()方法才能被唤醒（由于notify()只是唤醒一个线程，但我们由不能确定具体唤醒的是哪一个线程，也许我们需要唤醒的线程不能够被唤醒，因此在实际使用时，一般都用notifyAll()方法，唤醒有所线程），线程被唤醒后会进入锁池，等待获取锁标记。

wait() 使得线程进入阻塞状态，它有两种形式：

一种允许指定以毫秒为单位的一段时间作为参数；另一种没有参数。前者当对应的 notify()被调用或者超出指定时间时线程重新进入可执行状态即就绪状态，后者则必须对应的 notify()被调用。当调用wait()后，线程会释放掉它所占有的“锁标志”，从而使线程所在对象中的其它synchronized数据可被别的线程使用。waite()和notify()因为会对对象的“锁标志”进行操作，所以它们必须在synchronized函数或synchronizedblock中进行调用。如果在non-synchronized函数或non-synchronizedblock中进行调用，虽然能编译通过，但在运行时会发生IllegalMonitorStateException的异常。

注意区别：初看起来wait() 和 notify() 方法与suspend()和 resume() 方法对没有什么分别，但是事实上它们是截然不同的。区别的核心在于，前面叙述的suspend()及其它所有方法在线程阻塞时都不会释放占用的锁（如果占用了的话），而wait() 和 notify() 这一对方法则相反。

上述的核心区别导致了一系列的细节上的区别

首先，前面叙述的所有方法都隶属于 Thread类，但是wait() 和 notify() 方法这一对却直接隶属于 Object 类，也就是说，所有对象都拥有这一对方法。初看起来这十分不可思议，但是实际上却是很自然的，因为这一对方法阻塞时要释放占用的锁，而锁是任何对象都具有的，调用任意对象的 wait() 方法导致线程阻塞，并且该对象上的锁被释放。而调用任意对象的notify()方法则导致因调用该对象的 wait()方法而阻塞的线程中随机选择的一个解除阻塞（但要等到获得锁后才真正可执行）。

其次，前面叙述的所有方法都可在任何位置调用，但是wait() 和 notify() 方法这一对方法却必须在 synchronized 方法或块中调用，理由也很简单，只有在synchronized方法或块中当前线程才占有锁，才有锁可以释放。同样的道理，调用这一对方法的对象上的锁必须为当前线程所拥有，这样才有锁可以释放。因此，这一对方法调用必须放置在这样的 synchronized方法或块中，该方法或块的上锁对象就是调用这一对方法的对象。若不满足这一条件，则程序虽然仍能编译，但在运行时会出现IllegalMonitorStateException异常。

wait() 和 notify()方法的上述特性决定了它们经常和synchronized方法或块一起使用，将它们和操作系统的进程间通信机制作一个比较就会发现它们的相似性：synchronized方法或块提供了类似于操作系统原语的功能，它们的执行不会受到多线程机制的干扰，而这一对方法则相当于 block和wake up 原语（这一对方法均声明为 synchronized）。它们的结合使得我们可以实现操作系统上一系列精妙的进程间通信的算法（如信号量算法），并用于解决各种复杂的线程间通信问题。

关于 wait() 和 notify() 方法最后再说明两点：

第一：调用notify() 方法导致解除阻塞的线程是从因调用该对象的 wait()方法而阻塞的线程中随机选取的，我们无法预料哪一个线程将会被选择，所以编程时要特别小心，避免因这种不确定性而产生问题。

第二：除了notify()，还有一个方法 notifyAll()也可起到类似作用，唯一的区别在于，调用 notifyAll()方法将把因调用该对象的 wait()方法而阻塞的所有线程一次性全部解除阻塞。当然，只有获得锁的那一个线程才能进入可执行状态。

谈到阻塞，就不能不谈一谈死锁，略一分析就能发现，suspend()方法和不指定超时期限的wait()方法的调用都可能产生死锁。遗憾的是，Java并不在语言级别上支持死锁的避免，我们在编程中必须小心地避免死锁。

为什么线程切换比进程快？

首先我们需要了解一个概念：上下文切换
直接说概念可能有点看不懂，我们来举个例子：比如我们正在洗衣服，这时候突然有人打来电话，那么我们就需要放下手中的衣服去接电话，这就好比是进程切换，从洗衣服的进程换到打电话的进程，打完电话，我们还需要接着洗衣服，那么此时我们有什么呢？有洗了一半的衣服，有打开的洗衣液，有水，衣服还处在刚刚洗了一半的状态，这一系列的状态就可以理解为上下文。

回到计算机的世界里，内核为每一个进程维持一个上下文，上下文就是重新启动一个进程所需的状态，包含以下内容：

• 通用目的寄存器
• 浮点寄存器
• 程序计数器
• 用户栈
• 状态寄存器
• 内核栈
• 各种内核数据结构：比如描绘地址空间的页表，包含有关当前进程信息的进程表，包含进程已打开文件信息的文件表

进程的切换实际上就是上下文切换
那么为什么线程切换比进程快呢？这里我们还需要理解一个概念：虚拟内存
虚拟内存是操作系统为每个进程提供的一种抽象的，私有的，连续地址的虚拟内存空间，但是我们都知道实际上进程的数据以及代码必然要放到物理内存上，那么我们怎么知道虚拟空间中的数组实际上存放的具体位置呢？答案就是页表
每个进程都有属于自己的虚拟内存空间，进程中的所有线程共享进程的虚拟内存空间，所以进程之间互不影响，线程之间可能会相互影响
现在我们可以来回答这个问题了
线程切换比进程块的主要原因就是进程切换涉及虚拟内存地址空间的切换而线程不会。因为每个进程都有自己的虚拟内存地址空间，而线程之间的虚拟地址空间是共享的，因此同一个进程之中的线程切换不涉及虚拟地址空间的转换，然而将虚拟地址转化为物理地址需要查找页表，查找页表是一个很慢的过程，所以线程切换自然就比进程快了。

死锁

死锁是指在并发系统中，两个或多个进程因为互相等待对方释放资源而无法继续执行的状态。
死锁发生的条件通常包括以下四个条件：

• 互斥条件（Mutual Exclusion）：至少有一个资源被标记为只能被一个进程占用，即一次只能有一个进程使用该资源。
• 请求与保持条件（Hold and Wait）：一个进程在持有至少一个资源的同时，又请求其他进程占用的资源。
• 不可剥夺条件（No Preemption）：已经分配给一个进程的资源不能被强制性地剥夺，只能由持有该资源的进程主动释放
• 循环等待条件（Circular Wait）：存在一个进程资源的循环链，每个进程都在等待下一个进程所占用的资源。

当这四个条件同时满足时，就可能发生死锁。为了避免死锁的发生，可以采取一些策略，如资源预分配、避免循环等待、引入资源剥夺等。

内存

在程序中得到逻辑地址，先通过地址转换机构得到物理地址，
也就是通过查找页表找到对应的物理地址，请注意，这里有一个TLB用于加快查找页表的过程
页表中存储的是逻辑页和物理页的映射。页地址加上页内地址才是完整的地址
TLB中存储的是最近访问的页表项，如果TLB命中就停止去内存中查找页表项
如果TLB和页表都没有这个页的物理地址说明这一页没有还没加载到内存中，发生缺页中断。
得到物理地址后，先去查找cache判断这一块是否在cache中（cache中不仅包含数据块还包含了数据标记，也就是一块的地址值），如果在直接命中，
如果不在，再去内存中加载这一块到cache。

虚拟内存

TLB

地址空间：线程共享本进程的地址空间，而进程之间是独立的地址空间。
资源：线程共享本进程的资源如内存、I/O、cpu等，不利于资源的管理和保护，而进程之间的资源是独立的，能很好的进行资源管理和保护。
健壮性：多进程要比多线程健壮，一个进程崩溃后，在保护模式下不会对其他进程产生影响，但是一个线程崩溃整个进程都死掉。
执行过程：每个独立的进程有一个程序运行的入口、顺序执行序列和程序入口，执行开销大。但是线程不能独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制，执行开销小。
可并发性：
两者均可并发执行。
切换时：
进程切换时，消耗的资源大，效率高。所以涉及到频繁的切换时，使用线程要好于进程。同样如果要求同时进行并且又要共享某些变量的并发操作，只能用线程不能用进程。
其他：线程是处理器调度的基本单位，但是进程不是。

三、协程和线程的区别
协程避免了无意义的调度，由此可以提高性能，但程序员必须自己承担调度的责任。同时，协程也失去了标准线程使用多CPU的能力。
线程相对独立有自己的上下文切换受系统控制；协程相对独立有自己的上下文切换由自己控制，由当前协程切换到其他协程由当前协程来控制。

四、何时使用多进程，何时使用多线程？
对资源的管理和保护要求高，不限制开销和效率时，使用多进程。要求效率高，频繁切换时，资源的保护管理要求不是很高时，使用多线程。

五、为什么会有线程？
每个进程都有自己的地址空间，即进程空间，在网络或多用户换机下，一个服务器通常需要接收大量不确定数量用户的并发请求，为每一个请求都创建一个进程显然行不通（系统开销大响应用户请求效率低），因此操作系统中线程概念被引进。

六、*python多线程的问题（面试问题）
存在问题：
python由于历史遗留的问题，严格说多个线程并不会同时执行（没法有效利用多核处理器，python的并发只是在交替执行不同的代码）。多线程在Python中只能交替执行，即使100个线程跑在100核CPU上，也只能用到1个核。所以python的多线程并发并不能充分利用多核，并发没有java的并发严格。

原因：
原因就在于GIL ，在Cpython 解释器（Python语言的主流解释器）中，有一把全局解释锁（GIL, Global Interpreter Lock），在解释器解释执行Python 代码时，任何Python线程执行前，都先要得到这把GIL锁。这个GIL全局锁实际上把所有线程的执行代码都给上了锁。这意味着，python在任何时候，只可能有一个线程在执行代码。其它线程要想获得CPU执行代码指令，就必须先获得这把锁，如果锁被其它线程占用了，那么该线程就只能等待，直到占有该锁的线程释放锁才有执行代码指令的可能。多个线程一起执行反而更加慢的原因：同一时刻，只有一个线程在运行，其它线程只能等待，即使是多核CPU，也没办法让多个线程「并行」地同时执行代码，只能是交替执行，因为多线程涉及到上线文切换、锁机制处理（获取锁，释放锁等），所以，多线程执行不快反慢。什么时候GIL 被释放？当一个线程遇到I/O 任务时，将释放GIL。计算密集型（CPU-bound）线程执行100次解释器的计步（ticks）时（计步可粗略看作Python 虚拟机的指令），也会释放GIL。即，每执行100条字节码，解释器就自动释放GIL锁，让别的线程有机会执行。Python虽然不能利用多线程实现多核任务，但可以通过多进程实现多核任务。多个Python进程有各自独立的GIL锁，互不影响。

本条参考博客：http://www.sohu.com/a/230407177_99992472

七、进程通信方式（选读）
管道：速度慢，容量有限，只有父子进程能通讯
FIFO：任何进程间都能通讯，但速度慢
消息队列：容量受到系统限制，且要注意第一次读的时候，要考虑上一次没有读完数据的问题
信号量：不能传递复杂消息，只能用来同步
共享内存区：能够很容易控制容量，速度快，但要保持同步，比如一个进程在写的时候，另一个进程要注意读写的问题，相当于线程中的线程安全，当然，共享内存区同样可以用作线程间通讯，不过没这个必要，线程间本来就已经共享了同一进程内的一块内存
本条参考博客：https://blog.csdn.net/weixin_40283480/article/details/82155704

八、举例说明进程、线程、协程
程序：例如main.py这是程序，是一个静态的程序。
python进程：一个程序运行起来后，代码+用到的资源 称之为进程，它是操作系统分配资源的基本单元。multiprocessing.Process实现多进程
进程池：如果要启动大量的子进程，可以用进程池的方式批量创建子进程。multiprocessing.Pool
进程间通信：各自在独立的地址空间，并不能直接进行全局的数据共享，在创建子进程的时候会将父进程的数据复制到子进程中一份。进程间通信 Python的multiprocessing模块包装了底层的机制，提供了Queue、Pipes等多种方式来交换数据。
python线程：thread是比较低级,底层的模块，threading是高级模块，对thread进行了封装,可以更加方便的被使用。
python协程：线程和进程的操作是由程序触发系统接口，最后的执行者是系统；协程的操作则是程序员,当程序中存在大量不需要CPU的操作时（例如 I/O），适用于协程。
例如yield其中 yield 是python当中的语法。当协程执行到yield关键字时，会暂停在那一行，等到主线程调用send方法发送了数据，协程才会接到数据继续执行。但是，yield让协程暂停，和线程的阻塞是有本质区别的。
协程的暂停完全由程序控制，线程的阻塞状态是由操作系统内核来进行切换。因此，协程的开销远远小于线程的开销。最重要的是，协程不是被操作系统内核所管理，而完全是由程序所控制（也就是在用户态执行）。这样带来的好处就是性能得到了很大的提升，不会像线程切换那样消耗资源。python可以通过 yield/send 的方式实现协程。在python 3.5以后，async/await 成为了更好的替代方案。

优先级队列

数据结构是堆

一. PriorityQueue

PriorityQueue 简介

继承关系

PriorityQueue 示例

二. Comparable 比较器

Compare 接口

三. Comparator 比较器

Comparator 接口

四. 底层原理

一. PriorityQueue
PriorityQueue 简介
PriorityQueue ，即优先级队列。优先级队列可以保证每次取出来的元素都是队列中的最小或最大的元素<Java优先级队列默认每次取出来的为最小元素>。

大小关系：元素的比较可以通过元素本身进行自然排序，也可以通过构造方法传入比较器进行比较。

继承关系

通过继承关系图可以知道 PriorityQueue 是 Queue 接口的一个实现类，而 Queue 接口是 Collection 接口的一个实现类，因此其拥有 Collection 接口的基本操作，此外，队列还提供了其他的插入，移除和查询的操作。每个方法存在两种形式：一种是抛出异常（操作失败时），另一种是返回一个特殊值（null 或 false）。

PriorityQueue 的 peek 和 element 操作的时间复杂度都为常数，add，offer，remove 以及 poll 的时间复杂度是 log（n）。

PriorityQueue 示例
impot java.util.PriorityQueue;

public class PriorityQueueTest{
public static void main(String[] args){
PriorityQueue queue = new PriorityQueue<>();
queue.add(11);
queue.add(22);
queue.add(33);
queue.add(55);
queue.add(44);
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());
}
}
运行结果：

代码中我们依次添加11，22，33，55，44五个数据，然后进行删除，通过结果我们发现，每次删除的都为队列中最小元素，即体现了优先级队列。

结论：优先级队列默认每次获取队列最小的元素，也可以通过 comparator 比较器来自定义每次获取为最小还是最大。

注意:优先级队列中不可以存储 null。

二. Comparable 比较器
Compare 接口
public interface Comparable{
public int compareTo(T o);
}
该接口只存在一个 public int compareTo(T o); 方法，该方法表示所在的对象和 o 对象进行比较，返回值分三种：

1：表示该对象大于 o 对象
0：表示该对象等于 o 对象
-1：表示该对象小于 o 对象

需求：在优先级队列中存储对象学生，每个学生有 id，name 两个属性，并且使优先级队列每次按照学生的 id 从小到大取出。

代码示例：

Student 类：当前类实现了 Comparable 接口，即当前类提供了默认的比较方法。

public class Student implements Comparable{
    private int id;
    private String name;
    public Student(int id,String name,int age){
        this.id = id;
        this.name = name;
    }
    public int getId(){
        return id;
    }
    @Override
    public String toString(){
        return "Student{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
    @Override
    public int compareTo(Object o){
        Student o1 = (Student)o;
        return this.id - o1.id;
    }
}

PriorityQueueTest 类：

public class PriorityQueueTest {
public static void main(String[] args) {
PriorityQueue queue = new PriorityQueue<>();
queue.add(new Student(2,"Jack"));
queue.add(new Student(1,"Mary"));
queue.add(new Student(5,"Mcan"));
queue.add(new Student(4,"Scolt"));
queue.add(new Student(3,"Tina"));
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());
}
}
运行结果：

三. Comparator 比较器
新需求：如果使优先级队列按照学生 id 从大到小取出呢？我们很快就会想到修改 Student 类的compareTo 方法，使 return o1.id - this.id；这样当然可以实现我们的新需求。但是有很多时候类的compareTo 方法是不能修改的，比如 JDK 给我们提供的源代码，在不修改 compareTo 方法的前提下实现需求，只能用 comparator 比较器了。

Comparator 接口
public interface Comparator{
int compare(T o1,T o2);
}
该接口只存在一个 int compare(T o1,T o2);方法，该方法需要参数是两个待比较的对象，返回结果是 int 类型：

1：表示 o1对象 大于 o2 对象
0：表示 o1对象 等于 o2 对象
-1：表示 o1对象 小于 o2 对象

public class PriorityQueueTest {
public static void main(String[] args) {
PriorityQueue queue = new PriorityQueue<>(new Comparator() {

        @Override
        public int compare(Student o1, Student o2) {
            return o2.getId() - o1.getId();
    }
})
queue.add(new Student(2, "Jack"));
queue.add(new Student(1, "Mary"));
queue.add(new Student(5, "Mcan"));
queue.add(new Student(4, "Scolt"));
queue.add(new Student(3, "Tina"));
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());

}
}
运行结果：

四. 底层原理
优先级队列是如何保证每次取出的是队列中最小（最大）的元素的呢？查看源代码，底层的存储结构为一个数组

transient Object[] queue;

表面上是一个数组结构，实际上优先队列采用的是堆的形式来进行存储的，通过调整小堆或大堆来保证每次取出的元素为队列中的最小或最大。

IO

IO多路复用