BFS

BFS出现的常见场景是：让你在一幅「图」中找到从起点 start 到终点 target 的最近距离，这个例子听起来很枯燥，但是 BFS 算法问题其实都是在干这个事儿。

BFS框架：

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {Queue q; // 核心数据结构Set visited; // 避免走回头路q.offer(start); // 将起点加入队列visited.add(start);int step = 0; // 记录扩散的步数while (q not empty) {int sz = q.size();/* 将当前队列中的所有节点向四周扩散 */for (int i = 0; i < sz; i++) {Node cur = q.poll();/* 划重点：这里判断是否到达终点 */if (cur is target)return step;/* 将 cur 的相邻节点加入队列 */for (Node x : cur.adj()) {if (x not in visited) {q.offer(x);visited.add(x);}}}/* 划重点：更新步数在这里 */step++;}
}

队列 q 就不说了，BFS 的核心数据结构；cur.adj() 泛指 cur 相邻的节点，比如说二维数组中，cur 上下左右四面的位置就是相邻节点；visited 的主要作用是防止走回头路，大部分时候都是必须的，但是像一般的二叉树结构，没有子节点到父节点的指针，不会走回头路就不需要 visited。

为什么BFS可以找到最短路径？

BFS的逻辑是，depth每增加一次，队列中的所有节点都向前迈一步，当找到终点时，就返回值，当然就是最小的路径。

而DFS的逻辑是，一颗递归下去的二叉树，找到的是最深的位置，如果想要找到最短的路径，需要把整棵树都遍历一遍，然后取最小值。

计算二叉树最小深度

class Solution {public int minDepth(TreeNode root) {int depth = 1;if(root == null) return 0;Queue q = new LinkedList<>();q.offer(root);while(!q.isEmpty()){int size = q.size();for(int i = 0 ; i < size ; i ++){TreeNode cur = q.poll();if(cur.left == null && cur.right == null){return depth;}if(cur.left != null) q.offer(cur.left);if(cur.right != null) q.offer(cur.right);}depth ++;}return depth;}
}

打开转盘锁

752. 打开转盘锁 - 力扣（LeetCode）

class Solution {//先进先出队列。Queue  q = new LinkedList<>();//保存无法拨到的密码。Set  deads = new HashSet<>();//保存已经试过的密码。Set  visited = new HashSet<>();int step = 0;public int openLock(String[] deadends, String target) {for(int i = 0 ; i < deadends.length; i ++){deads.add(deadends[i]);}q.offer("0000");visited.add("0000");return bfs(deadends , target);}int bfs(String [] deadends , String target){while(!q.isEmpty()){int size = q.size();//每一层for循环的每一个节点，都有八种拨法，每个位置可以向上/下，一共四个位置。for(int i = 0 ; i < size ; i ++){String str = q.poll();if(deads.contains(str)){continue;}if(target.equals(str)) return step;for(int j = 0 ; j < 4 ; j ++){String up = plusOne(str , j);if(!visited.contains(up)){visited.add(up);q.offer(up);}String down = minusOne(str , j);if(!visited.contains(down)){visited.add(down);q.offer(down);}}}step ++;}return -1;}String plusOne(String str ,int j){char [] ch = str.toCharArray();if(ch[j] == '9'){ch[j] = '0';}else{ch[j] += 1;}return new String (ch);}String minusOne(String str , int j){char [] ch = str.toCharArray();if(ch[j] == '0'){ch[j] ='9';}else{ch[j] -= 1;}return new String (ch);}
}

滑动谜题

773. 滑动谜题 - 力扣（LeetCode）

class Solution {int step = 0;Queue q = new LinkedList<>(); Set visited = new HashSet<>();public int slidingPuzzle(int[][] board) {String target = "123450";// 记录一维字符串的相邻索引int[][] neighbor = new int[][]{{1, 3},{0, 4, 2},{1, 5}{0, 4},{3, 1, 5},{4, 2}};StringBuffer sb = new StringBuffer();for(int i = 0 ; i < 2 ; i ++){for(int j = 0 ; j < 3 ; j ++){sb.append(board[i][j]);}}String str = sb.toString();q.offer(str);visited.add(str);while(!q.isEmpty()){int size = q.size();for(int i = 0 ; i < size ; i ++){String cur = q.poll();//找到答案就返回if(target.equals(cur)) return step;//找到数字零的下标int index ;for(index = 0 ; cur.charAt(index) != '0' ; index ++);//拿出0的相邻索引，交换位置for(int adj : neighbor[index]){String new_cur = swap(cur.toCharArray() , adj , index);if(!visited.contains(new_cur)){visited.add(new_cur);q.offer(new_cur);}}}step ++;}return -1;}private String swap(char[] chars, int i, int j) {char temp = chars[i];chars[i] = chars[j];chars[j] = temp;return new String(chars);
}
}

4. 进程管理

进程、线程基础知识

• 什么是进程

  进程是程序执行的基本单位。说简单一点，执行中的程序，就是进程。

• 并行和并发

  虽然单核的 CPU 在某一个瞬间，只能运行一个进程。但在 1 秒钟期间，它可能会运行多个进程，实际上这是并发，在一个CPU核心上运行多个任务。而并行是在多个CPU核心上运行同时多个任务。

• 进程的状态

  • 运行状态（Running）：该时刻进程占用 CPU；
  • 就绪状态（Ready）：可运行，由于其他进程处于运行状态而暂时停止运行；
  • 阻塞状态（Blocked）：该进程正在等待某一事件发生（如等待输入/输出操作的完成）而暂时停止运行，这时，即使给它CPU控制权，它也无法运行；

  两个基本状态

  • 创建状态（new）：进程正在被创建时的状态；
  • 结束状态（Exit）：进程正在从系统中消失时的状态；

• 进程的状态变迁：

  • NULL -> 创建状态：一个新进程被创建时的第一个状态；

  • 创建状态 -> 就绪状态：当进程被创建完成并初始化后，一切就绪准备运行时，变为就绪状态，这个过程是很快的；

  • 就绪态 -> 运行状态：处于就绪状态的进程被操作系统的进程调度器选中后，就分配给 CPU 正式运行该进程；

  • 运行状态 -> 结束状态：当进程已经运行完成或出错时，会被操作系统作结束状态处理；

  • 运行状态 -> 就绪状态：处于运行状态的进程在运行过程中，由于分配给它的运行时间片用完，操作系统会把该进程变为就绪态，接着从就绪态选中另外一个进程运行；

  • 运行状态 -> 阻塞状态：当进程请求某个事件且必须等待时，例如请求 I/O 事件；

  • 阻塞状态 -> 就绪状态：当进程要等待的事件完成时，它从阻塞状态变到就绪状态；

• 挂起状态

  在虚拟内存管理中，通常会把阻塞状态的进程的物理内存空间换出到硬盘，等需要再次运行的时候，再从硬盘换入到物理内存。

  那么，就需要一个新的状态，来描述进程没有占用实际的物理内存空间的情况，这个状态就是挂起状态。这跟阻塞状态是不一样，阻塞状态是等待某个事件的返回。

  另外，挂起状态可以分为两种：

  • 阻塞挂起状态：进程在外存（硬盘）并等待某个事件的出现；

  • 就绪挂起状态：进程在外存（硬盘），但只要进入内存，即刻立刻运行；

• 进程的控制结构

  在操作系统中，是用进程控制块（process control block，PCB）数据结构来描述进程的。

  PCB 是进程存在的唯一标识。这意味着一个进程的存在，必然会有一个 PCB，如果进程消失了，那么 PCB 也会随之消失。

• PCB具体包含的信息

  进程描述信息：

  • 进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符；
  • 用户标识符：进程归属的用户，用户标识符主要为共享和保护服务；

  进程控制和管理信息：

  • 进程当前状态，如 new、ready、running、waiting 或 blocked 等；
  • 进程优先级：进程抢占 CPU 时的优先级；

  资源分配清单：

  • 有关内存地址空间或虚拟地址空间的信息，所打开文件的列表和所使用的 I/O 设备信息。

  CPU 相关信息：

  • CPU 中各个寄存器的值，当进程被切换时，CPU 的状态信息都会被保存在相应的 PCB 中，以便进程重新执行时，能从断点处继续执行。

• PCB是如何组织的

  通常是通过链表的方式进行组织，把具有相同状态的进程链在一起，组成各种队列。比如：

  • 将所有处于就绪状态的进程链在一起，称为就绪队列；
  • 把所有因等待某事件而处于等待状态的进程链在一起就组成各种阻塞队列；
  • 对于运行队列在单核 CPU 系统中则只有一个运行指针了，因为单核 CPU 在某个时间，只能运行一个程序。

• 进程的控制

  01 创建进程

  • 申请一个空白的 PCB，并向 PCB 中填写一些控制和管理进程的信息，比如进程的唯一标识等；
  • 为该进程分配运行时所必需的资源，比如内存资源；
  • 将 PCB 插入到就绪队列，等待被调度运行；

  02 终止进程

  进程可以有 3 种终止方式：正常结束、异常结束以及外界干预（信号 kill 掉）。

  当子进程被终止时，其在父进程处继承的资源应当还给父进程。而当父进程被终止时，该父进程的子进程就变为孤儿进程，会被 1 号进程收养，并由 1 号进程对它们完成状态收集工作。

  终止进程的过程如下：

  • 查找需要终止的进程的 PCB；
  • 如果处于执行状态，则立即终止该进程的执行，然后将 CPU 资源分配给其他进程；
  • 如果其还有子进程，则应将该进程的子进程交给 1 号进程接管；
  • 将该进程所拥有的全部资源都归还给操作系统；
  • 将其从 PCB 所在队列中删除；

  03 阻塞进程

  当进程需要等待某一事件完成时，它可以调用阻塞语句把自己阻塞等待。而一旦被阻塞等待，它只能由另一个进程唤醒。

  阻塞进程的过程如下：

  • 找到将要被阻塞进程标识号对应的 PCB；
  • 如果该进程为运行状态，则保护其现场，将其状态转为阻塞状态，停止运行；
  • 将该 PCB 插入到阻塞队列中去；

  04 唤醒进程

  进程由「运行」转变为「阻塞」状态是由于进程必须等待某一事件的完成，所以处于阻塞状态的进程是绝对不可能叫醒自己的。

  如果某进程正在等待 I/O 事件，需由别的进程发消息给它，则只有当该进程所期待的事件出现时，才由发现者进程用唤醒语句叫醒它。

  唤醒进程的过程如下：

  • 在该事件的阻塞队列中找到相应进程的 PCB；
  • 将其从阻塞队列中移出，并置其状态为就绪状态；
  • 把该 PCB 插入到就绪队列中，等待调度程序调度；

  进程的阻塞和唤醒是一对功能相反的语句，如果某个进程调用了阻塞语句，则必有一个与之对应的唤醒语句。

• CPU上下文切换

  在每个任务运行前，CPU 需要知道任务从哪里加载，又从哪里开始运行。

  操作系统需要事先帮 CPU 设置好 CPU 寄存器和程序计数器，是任务必须依赖的环境，这些环境就叫做 CPU 上下文。

  • CPU 上下文切换就是先把前一个任务的 CPU 上下文（CPU 寄存器和程序计数器）保存起来，然后加载新任务的上下文到这些寄存器和程序计数器，最后再跳转到程序计数器所指的新位置，运行新任务。

  • 系统内核会存储保持下来的上下文信息，当此任务再次被分配给 CPU 运行时，CPU 会重新加载这些上下文，这样就能保证任务原来的状态不受影响，让任务看起来还是连续运行。

• 进程的上下文切换

  进程的切换只能发生在内核态，是由内核管理和调度。

  所以，进程的上下文切换不仅包含了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的资源。

  通常，会把交换的信息保存在进程的 PCB，当要运行另外一个进程的时候，我们需要从这个进程的 PCB 取出上下文，然后恢复到 CPU 中，这使得这个进程可以继续执行。

• 发生进程上下文切换有哪些场景？

  • 时间片调度原则，当某个进程的时间片耗尽了，进程就从运行状态变为就绪状态，系统从就绪队列选择另外一个进程运行；

  • 进程在系统资源不足（比如内存不足）时，要等到资源满足后才可以运行，这个时候进程也会被挂起，并由系统调度其他进程运行；

  • 使用sleep()将自己挂起。

  • 高优先级优先执行，当有优先级更高的进程运行时，为了保证高优先级进程的运行，当前进程会被挂起，由高优先级进程来运行；

  • 发生硬件中断时，CPU 上的进程会被中断挂起，转而执行内核中的中断服务程序；

• 线程

  **线程是进程当中的一条执行流程。**同一个进程内多个线程之间可以共享代码段、数据段、打开的文件等资源，但每个线程各自都有一套独立的寄存器和栈，这样可以确保线程的控制流是相对独立的。

• 线程的优点：

  • 一个进程中可以同时存在多个线程；

  • 各个线程之间可以并发执行；

  • 各个线程之间可以共享地址空间和文件等资源；

• 线程的缺点：

  • 当进程中的一个线程崩溃时，会导致其所属进程的所有线程崩溃（这里是针对 C/C++ 语言，Java语言中的线程奔溃不会造成JVM进程崩溃。)

• 进程与线程的比较

  • 进程是资源（包括内存、打开的文件等）分配的单位，线程是 CPU 调度（资源调度）的基本单位；

  • 进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈；

  • 线程同样具有就绪、阻塞、执行三种基本状态，同样具有状态之间的转换关系；

  • 线程能减少并发执行的时间和空间开销；

    • 线程的创建时间比进程快。创建时，进程需要资源管理信息，线程不会涉及这些资源管理信息，而是共享它们；

    • 线程释放的资源比进程少。

    • 同一个进程内的线程切换比进程切换快，因为线程具有相同的地址空间（虚拟内存共享），这意味着同一个进程的线程都具有同一个页表，那么在切换的时候不需要切换页表。而对于进程之间的切换，切换的时候要把页表给切换掉，而页表的切换过程开销是比较大的；

    • 由于同一进程的各线程间共享内存和文件资源，那么在线程之间数据传递的时候，就不需要经过内核了，这就使得线程之间的数据交互效率更高了；

      所以，不管是时间效率，还是空间效率线程比进程都要高。

• 线程的上下文切换

  线程是调度的基本单位，而进程则是资源拥有的基本单位。所以，所谓操作系统的任务调度，实际上的调度对象是线程，而进程只是给线程提供了虚拟内存、全局变量等资源。

  对于线程和进程，我们可以这么理解：

  • 当进程只有一个线程时，可以认为进程就等于线程；

  • 当进程拥有多个线程时，这些线程会共享相同的虚拟内存和全局变量等资源，这些资源在上下文切换时是不需要修改的；

  另外，线程也有自己的私有数据，比如栈和寄存器等，这些在上下文切换时也是需要保存的。

  所以，线程的上下文切换的是什么这还得看线程是不是属于同一个进程：

  • 当两个线程不是属于同一个进程，则切换的过程就跟进程上下文切换一样；

  • 当两个线程是属于同一个进程，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据；

• 线程的实现

  • 用户线程（User Thread）：在用户空间实现的线程，操作系统不参与，由用户态的线程库来完成线程的管理。

    • 用户线程是基于用户态的线程管理库来实现的，那么线程控制块（Thread Control Block, TCB） 也是在库里面来实现的，对于操作系统而言是看不到这个 TCB 的，它只能看到整个进程的 PCB。

      所以，用户线程的整个线程管理和调度，操作系统是不直接参与的，而是由用户级线程库函数来完成线程的管理，包括线程的创建、终止、同步和调度等。

  • 内核线程（Kernel Thread）：在内核中实现的线程，是由内核管理的线程；

    • 内核线程是由操作系统管理的，线程对应的 TCB 自然是放在操作系统里的，这样线程的创建、终止和管理都是由操作系统负责。

  • 轻量级进程（LightWeight Process）：在内核中来支持用户线程；

    • 轻量级进程（Light-weight process，LWP）是内核支持的用户线程，一个进程可有一个或多个 LWP，每个 LWP 是跟内核线程一对一映射的，也就是 LWP 都是由一个内核线程支持，而且 LWP 是由内核管理并像普通进程一样被调度。

      在大多数系统中，LWP与普通进程的区别也在于它只有一个最小的执行上下文和调度程序所需的统计信息。一般来说，一个进程代表程序的一个实例，而 LWP 代表程序的执行线程，因为一个执行线程不像进程那样需要那么多状态信息。

• 调度

  一旦操作系统把进程切换到运行状态，也就意味着该进程占用着 CPU 在执行，但是当操作系统把进程切换到其他状态时，那就不能在 CPU 中执行了，于是操作系统会选择下一个要运行的进程。

  选择一个进程运行这一功能是在操作系统中完成的，通常称为调度程序（scheduler）。

• 调度时机

  在进程的生命周期中，当进程从一个运行状态到另外一状态变化的时候，其实会触发一次调度。

  另外，如果硬件时钟提供某个频率的周期性中断，那么可以根据如何处理时钟中断 ，把调度算法分为两类：

  • 非抢占式调度算法挑选一个进程，然后让该进程运行直到被阻塞，或者直到该进程退出，才会调用另外一个进程，也就是说不会理时钟中断这个事情。
  • 抢占式调度算法挑选一个进程，然后让该进程只运行某段时间，如果在该时段结束时，该进程仍然在运行时，则会把它挂起，接着调度程序从就绪队列挑选另外一个进程。这种抢占式调度处理，需要在时间间隔的末端发生时钟中断，以便把 CPU 控制返回给调度程序进行调度，也就是常说的时间片机制。

• CPU进行调度的原则

  • 原则一：CPU 利用率：调度程序应确保 CPU 是始终匆忙的状态，这可提高 CPU 的利用率；
  • 原则二：系统吞吐量：吞吐量表示的是单位时间内 CPU 完成进程的数量，长作业的进程会占用较长的 CPU 资源，因此会降低吞吐量，相反，短作业的进程会提升系统吞吐量；调度程序要提高系统吞吐量，要兼顾短任务和长任务运行完成数量。
  • 原则三：周转时间：周转时间是进程运行+阻塞时间+等待时间的总和，一个进程的周转时间越小越好；
  • 原则四：等待时间：这个等待时间不是阻塞状态的时间，而是进程处于就绪队列的时间，等待的时间越长，用户越不满意；
  • 原则五：响应时间：用户提交请求到系统第一次产生响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准。

• 调度算法

  单核 CPU 系统中常见的调度算法。

  • 先来先服务调度算法(First Come First Serve, FCFS)

    顾名思义，先来后到，**每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行。**但是当一个长作业先运行了，那么后面的短作业等待的时间就会很长，不利于短作业。

  • 最短作业优先调度算法

    最短作业优先（Shortest Job First, SJF）调度算法同样也是顾名思义，它会优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量。这显然对长作业不利，很容易造成一种极端现象。

  • 高响应比优先调度算法

    高响应比优先 （Highest Response Ratio Next, HRRN）调度算法主要是权衡了短作业和长作业。每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行。

  • 时间片轮转调度算法

    最古老、最简单、最公平且使用最广的算法就是时间片轮转（*Round Robin, RR*）调度算法。每个进程被分配一个时间段，称为时间片（*Quantum*），即允许该进程在该时间段中运行。

    • 如果时间片用完，进程还在运行，那么将会把此进程从 CPU 释放出来，并把 CPU 分配给另外一个进程；
    • 如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换；

    另外，时间片的长度就是一个很关键的点：

    • 如果时间片设得太短会导致过多的进程上下文切换，降低了 CPU 效率；

    • 如果设得太长又可能引起对短作业进程的响应时间变长。

  • 最高优先级调度算法

    调度程序能从就绪队列中选择最高优先级的进程进行运行，这称为最高优先级（Highest Priority First，HPF）调度算法。

    进程的优先级可以分为，静态优先级和动态优先级：

    • 静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化；
    • 动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级。

    该算法也有两种处理优先级高的方法，非抢占式和抢占式：

    • 非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程。
    • 抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。

  • 多级反馈队列调度算法

    多级反馈队列（Multilevel Feedback Queue）调度算法是「时间片轮转算法」和「最高优先级算法」的综合和发展。

    顾名思义：

    • 「多级」表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。
    • 「反馈」表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列；

    对于短作业可能可以在第一级队列很快被处理完。对于长作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变长了，但是运行时间也变更长了，所以该算法很好的兼顾了长短作业，同时有较好的响应时间。

进程间有哪些通信方式？

由于每个进程的用户空间都是独立的，不能相互访问，这时就需要借助内核空间来实现进程间通信，原因很简单，每个进程都是共享一个内核空间。

• 管道

  Linux 内核提供了不少进程间通信的方式，其中最简单的方式就是管道，管道分为「匿名管道」和「命名管道」。

  $ ps auxf | grep mysql
  

  「|」竖线就是一个管道，它的功能是将前一个命令（ps auxf）的输出，作为后一个命令（grep mysql）的输入，从这功能描述，可以看出管道传输数据是单向的，如果想相互通信，我们需要创建两个管道才行。这种就是匿名管道。

  匿名管道顾名思义，它没有名字标识，匿名管道是特殊文件只存在于内存，没有存在于文件系统中，shell 命令中的「|」竖线就是匿名管道，通信的数据是无格式的流并且大小受限，通信的方式是单向的，数据只能在一个方向上流动，如果要双向通信，需要创建两个管道，再来匿名管道是只能用于存在父子关系的进程间通信，匿名管道的生命周期随着进程创建而建立，随着进程终止而消失。

  命名管道突破了匿名管道只能在亲缘关系进程间的通信限制，因为使用命名管道的前提，需要在文件系统创建一个类型为 p 的设备文件，那么毫无关系的进程就可以通过这个设备文件进行通信。

  另外，不管是匿名管道还是命名管道，进程写入的数据都是缓存在内核中，另一个进程读取数据时候自然也是从内核中获取，同时通信数据都遵循先进先出原则。

  所谓的管道，就是内核里面的一串缓存。从管道的一段写入的数据，实际上是缓存在内核中的，另一端读取，也就是从内核中读取这段数据。另外，管道传输的数据是无格式的流且大小受限。

• 消息队列

  消息队列克服了管道通信的数据是无格式的字节流并且通信效率低的问题，消息队列实际上是保存在内核的「消息链表」，消息队列的消息体可以是用户自定义的数据类型，发送数据时，会被分成一个一个独立的消息体，当然接收数据时，也要与发送方发送的消息体的数据类型保持一致，这样才能保证读取的数据是正确的。消息队列通信的速度不是最及时的，毕竟每次数据的写入和读取都需要经过用户态与内核态之间的拷贝过程。

• 共享内存

  共享内存可以解决消息队列通信中用户态与内核态之间数据拷贝过程带来的开销，它直接分配一个共享空间，每个进程都可以直接访问，就像访问进程自己的空间一样快捷方便，不需要陷入内核态或者系统调用，大大提高了通信的速度，享有最快的进程间通信方式之名。但是便捷高效的共享内存通信，带来新的问题，多进程竞争同个共享资源会造成数据的错乱。

• 信号量

  那么，就需要信号量来保护共享资源，以确保任何时刻只能有一个进程访问共享资源，这种方式就是互斥访问。信号量不仅可以实现访问的互斥性，还可以实现进程间的同步，信号量其实是一个计数器，表示的是资源个数，其值可以通过两个原子操作来控制，分别是 P 操作和 V 操作。

• 信号

  信号是异步通信机制，信号可以在应用进程和内核之间直接交互，内核也可以利用信号来通知用户空间的进程发生了哪些系统事件，对于异常情况下的工作模式，就需要用「信号」的方式来通知进程。

  信号事件的来源主要有硬件来源（如键盘 Cltr+C ）和软件来源（如 kill 命令），一旦有信号发生，**进程有三种方式响应信号 **。

  1. 执行默认操作

     Linux 对每种信号都规定了默认操作，例如， SIGTERM 信号，就是终止进程的意思

  2. 捕捉信号

     我们可以为信号定义一个信号处理函数。当信号发生时，我们就执行相应的信号处理函数。

  3. 忽略信号

     当我们不希望处理某些信号的时候，就可以忽略该信号，不做任何处理。有两个信号是应用进程无法捕捉和忽略的，即 SIGKILL 和 SEGSTOP，它们用于在任何时候中断或结束某一进程。

• Socket

  前面说到的通信机制，都是工作于同一台主机，如果要与不同主机的进程间通信，那么就需要 Socket 通信了。Socket 实际上不仅用于不同的主机进程间通信，还可以用于本地主机进程间通信，可根据创建 Socket 的类型不同，分为三种常见的通信方式，一个是基于 TCP 协议的通信方式，一个是基于 UDP 协议的通信方式，一个是本地进程间通信方式。

线程间通信的方式呢？

同个进程下的线程之间都是共享进程的资源，只要是共享变量都可以做到线程间通信，比如全局变量，所以对于线程间关注的不是通信方式，而是关注多线程竞争共享资源的问题，信号量也同样可以在线程间实现互斥与同步：

• 互斥的方式，可保证任意时刻只有一个线程访问共享资源；
• 同步的方式，可保证线程 A 应在线程 B 之前执行；

多线程冲突了怎么办？

由于多线程执行操作共享变量可能会导致竞争状态，因此我们将此段访问共享变量的代码称为临界区（critical section），它是访问共享资源的代码片段，一定不能给多线程同时执行。

我们希望这段代码是互斥（mutualexclusion）的，也就说保证一个线程在临界区执行时，其他线程应该被阻止进入临界区，说白了，就是这段代码执行过程中，最多只能出现一个线程。

所谓同步，就是并发进程/线程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通信息称为进程/线程同步。

所以我们使用加锁操作和解锁操作可以解决并发线程/进程的互斥问题。任何想进入临界区的线程，必须先执行加锁操作。若加锁操作顺利通过，则线程可进入临界区；在完成对临界资源的访问后再执行解锁操作，以释放该临界资源。

自旋锁

• CPU 体系结构提供的特殊原子操作指令 —— 测试和置位（Test-and-Set）指令。原子操作就是，要么全部执行，要么都不执行，不能出现执行到一半的中间状态。

• 可以用Test-and-Set实现忙等待锁/自旋锁，这是最简单的一种锁，一直自旋，利用 CPU 周期，直到锁可用。在单处理器上，需要抢占式的调度器（即不断通过时钟中断一个线程，运行其他线程）。否则，自旋锁在单 CPU 上无法使用，因为一个自旋的线程永远不会放弃 CPU。

无等待锁

无等待锁顾明思义就是获取不到锁的时候，不用自旋。既然不想自旋，那当没获取到锁的时候，就把当前线程放入到锁的等待队列，然后执行调度程序，把 CPU 让给其他线程执行。

信号量

通常信号量表示资源的数量，对应的变量是一个整型（sem）变量。

另外，还有两个原子操作的系统调用函数来控制信号量的，分别是：

• P 操作：将 sem 减 1，相减后，如果 sem < 0，则进程/线程进入阻塞等待，否则继续，表明 P 操作可能会阻塞；
• V 操作：将 sem 加 1，相加后，如果 sem <= 0，唤醒一个等待中的进程/线程，表明 V 操作不会阻塞；

PV 操作的函数是由操作系统管理和实现的，所以操作系统已经使得执行 PV 函数时是具有原子性的。

生产者-消费者问题

• 生产者在生成数据后，放在一个缓冲区中；
• 消费者从缓冲区取出数据处理；
• 任何时刻，只能有一个生产者或消费者可以访问缓冲区；

对问题分析可以得出：

• 任何时刻只能有一个线程操作缓冲区，说明操作缓冲区是临界代码，需要互斥；

• 缓冲区空时，消费者必须等待生产者生成数据；缓冲区满时，生产者必须等待消费者取出数据。说明生产者和消费者需要同步。

使用三个信号量，就可以实现同步和互斥。

• 互斥信号量 mutex：用于互斥访问缓冲区，初始化值为 1；（保证两个线程互斥）

• 资源信号量 fullBuffers：用于消费者询问缓冲区是否有数据，有数据则读取数据，初始化值为 0（表明缓冲区一开始为空）；

• 资源信号量 emptyBuffers：用于生产者询问缓冲区是否有空位，有空位则生成数据，初始化值为 n （缓冲区大小）；

哲学家就餐问题

• 5 个老大哥哲学家，闲着没事做，围绕着一张圆桌吃面；
• 巧就巧在，这个桌子只有 5 支叉子，每两个哲学家之间放一支叉子；
• 哲学家围在一起先思考，思考中途饿了就会想进餐；
• 奇葩的是，这些哲学家要两支叉子才愿意吃面，也就是需要拿到左右两边的叉子才进餐；
• 吃完后，会把两支叉子放回原处，继续思考；

使用互斥信号量mutex，初始值为1，要么拿到两把叉子或放回两把叉子的过程是互斥的。拿叉子时不能尝试返回叉子。

s[i]信号量，来表示第i个哲学家是否可以进餐。

我们还用一个数组 state 来记录每一位哲学家的三个状态，分别是在进餐状态、思考状态、饥饿状态（正在试图拿叉子）。

那么，一个哲学家只有在两个邻居都没有进餐时，才可以进入进餐状态。

第 i 个哲学家的左邻右舍，则由宏 LEFT 和 RIGHT 定义：比如 i 为 2，则 LEFT 为 1，RIGHT 为 3。

具体代码实现如下：

读者-写者问题

前面的「哲学家进餐问题」对于互斥访问有限的竞争问题（如 I/O 设备）一类的建模过程十分有用。

另外，还有个著名的问题是「读者-写者」，它为数据库访问建立了一个模型。

读者只会读取数据，不会修改数据，而写者即可以读也可以修改数据。

读者-写者的问题描述：

• 「读-读」允许：同一时刻，允许多个读者同时读
• 「读-写」互斥：没有写者时读者才能读，没有读者时写者才能写
• 「写-写」互斥：没有其他写者时，写者才能写

公平策略：

• 优先级相同；

• 写者、读者互斥访问；

• 只能一个写者访问临界区；

• 可以有多个读者同时访问临界资源；

怎么避免死锁？

那么，当两个线程为了保护两个不同的共享资源而使用了两个互斥锁，那么这两个互斥锁应用不当的时候，可能会造成两个线程都在等待对方释放锁，在没有外力的作用下，这些线程会一直相互等待，就没办法继续运行，这种情况就是发生了死锁。

死锁只有同时满足以下四个条件才会发生：

• 互斥条件；

  • 互斥条件是指多个线程不能同时使用同一个资源。

• 持有并等待条件；

  • 当线程 A 已经持有了资源 1，又想申请资源 2，而资源 2 已经被线程 C 持有了，所以线程 A 就会处于等待状态，但是线程 A 在等待资源 2 的同时并不会释放自己已经持有的资源 1。

• 不可剥夺条件；

  • 不可剥夺条件是指，当线程已经持有了资源 ，在自己使用完之前不能被其他线程获取，线程 B 如果也想使用此资源，则只能在线程 A 使用完并释放后才能获取。

• 环路等待条件；

  • 环路等待条件指的是，在死锁发生的时候，两个线程获取资源的顺序构成了环形链。比如，线程 A 已经持有资源 2，而想请求资源 1， 线程 B 已经获取了资源 1，而想请求资源 2，这就形成资源请求等待的环形图。

所以要避免死锁问题，就是要破坏其中一个条件即可，最常见的并且可行的就是使用资源有序分配法，来破坏环路等待条件。

• 就是A线程和B线程获取资源的顺序要一致。两个线程都使用相同的顺序来访问资源。

什么是悲观锁、乐观锁？

• 互斥锁与自旋锁

  最底层的两种锁就是互斥锁和自旋锁，有很多高级的锁都是基于它们实现的。

  当已经有一个线程加锁后，其他线程加锁则就会失败，互斥锁和自旋锁对于加锁失败后的处理方式是不一样的：

  • 互斥锁加锁失败后，线程会释放 CPU ，给其他线程；

    • 互斥锁是一种「独占锁」，比如当线程 A 加锁成功后，此时互斥锁已经被线程 A 独占了，只要线程 A 没有释放手中的锁，线程 B 加锁就会失败，于是就会释放 CPU 让给其他线程，既然线程 B 释放掉了 CPU，自然线程 B 加锁的代码就会被阻塞。

  • 自旋锁加锁失败后，线程会忙等待，直到它拿到锁；

    • 使用自旋锁的时候，当发生多线程竞争锁的情况，加锁失败的线程会「忙等待」，直到它拿到锁。这里的「忙等待」可以用 while 循环等待实现，不过最好是使用 CPU 提供的 PAUSE 指令来实现「忙等待」，因为可以减少循环等待时的耗电量。

      PAUSE指令：用于暂时终止程序的运行。可以提高自选等待循环的性能。

• 自旋锁与互斥锁

  • 互斥锁会存在两次线程上下文切换的成本，如下：

    • 当线程加锁失败时，内核会把线程的状态从「运行」状态设置为「睡眠」状态，然后把 CPU 切换给其他线程运行；
    • 接着，当锁被释放时，之前**「睡眠」状态的线程会变为「就绪」状态**，然后内核会在合适的时间，把 CPU 切换给该线程运行。

    如果锁住的代码执行时间比较短，那可能上下文切换的时间可能比锁住代码执行时间更长。所以，如果你能确定被锁住的代码执行时间很短，就不应该用互斥锁，而应该选用自旋锁，否则使用互斥锁。

  • 自旋锁是通过 CPU 提供的 CAS 函数（Compare And Swap），在「用户态」完成加锁和解锁操作，不会主动产生线程上下文切换，所以相比互斥锁来说，会快一些，开销也小一些。

    自旋锁与互斥锁使用层面比较相似，但实现层面上完全不同：当加锁失败时，互斥锁用「线程切换」来应对，自旋锁则用「忙等待」来应对。

    需要注意，在单核 CPU 上，需要抢占式的调度器（即不断通过时钟中断一个线程，运行其他线程）。否则，自旋锁在单 CPU 上无法使用，因为一个自旋的线程永远不会放弃 CPU。

• 读写锁

  读写锁从字面意思我们也可以知道，它由「读锁」和「写锁」两部分构成，如果只读取共享资源用「读锁」加锁，如果要修改共享资源则用「写锁」加锁。所以，读写锁适用于能明确区分读操作和写操作的场景。

  读写锁的工作原理如下：

  • **读锁是共享锁。**当「写锁」没有被线程持有时，多个线程能够并发地持有读锁，这大大提高了共享资源的访问效率，因为「读锁」是用于读取共享资源的场景，所以多个线程同时持有读锁也不会破坏共享资源的数据。

  • **写锁是独占锁。**一旦「写锁」被线程持有后，读线程的获取读锁的操作会被阻塞，而且其他写线程的获取写锁的操作也会被阻塞。

  读写锁在读多写少的场景，能发挥出优势。因为多个线程可以同时持有读锁。

  另外，根据实现的不同，读写锁可以分为「读优先锁」和「写优先锁」。

  • 「读优先锁」期望的是，读锁能被更多的线程持有，以便提高读线程的并发性。即所有的读锁优先级比写锁高，写锁必须等待读锁释放。
  • 「写优先锁」是期望优先服务写线程。当读线程 A 先持有了读锁，写线程 B 在获取写锁的时候，会被阻塞，并且在阻塞过程中，后续来的读线程 C 获取读锁时会失败，于是读线程 C 将被阻塞在获取读锁的操作，这样只要读线程 A 释放读锁后，写线程 B 就可以成功获取写锁。

  公平读写锁比较简单的一种方式是：用队列把获取锁的线程排队，不管是写线程还是读线程都按照先进先出的原则加锁即可，这样读线程仍然可以并发，也不会出现「饥饿」的现象。

• 悲观锁

  悲观锁做事比较悲观，它认为多线程同时修改共享资源的概率比较高，于是很容易出现冲突，所以访问共享资源前，先要上锁。

  那相反的，如果多线程同时修改共享资源的概率比较低，就可以采用乐观锁。

• 乐观锁

  乐观锁做事比较乐观，它假定冲突的概率很低，它的工作方式是：先修改完共享资源，再验证这段时间内有没有发生冲突，如果没有其他线程在修改资源，那么操作完成，如果发现有其他线程已经修改过这个资源，就放弃本次操作。

  可见，乐观锁的心态是，不管三七二十一，先改了资源再说。另外，你会发现乐观锁全程并没有加锁，所以它也叫无锁编程。

  乐观锁虽然去除了加锁解锁的操作，但是一旦发生冲突，重试的成本非常高，所以只有在冲突概率非常低，且加锁成本非常高的场景时，才考虑使用乐观锁。

不管使用的哪种锁，我们的加锁的代码范围应该尽可能的小，也就是加锁的粒度要小，这样执行速度会比较快。再来，使用上了合适的锁，就会快上加快了。

一个进程最多可以创建多少个线程？

主要和进程的虚拟内存空间大小、系统参数限制最大线程个数有关。

因为创建一个线程，操作系统需要为其分配一个栈空间，如果线程数量越多，所需的栈空间就要越大，那么虚拟内存就会占用的越多。

• 实践：

  我们可以执行 ulimit -a 这条命令，查看进程创建线程时默认分配的栈空间大小。在前面我们知道，在 32 位 Linux 系统里，一个进程的虚拟空间是 4G，内核分走了1G，留给用户用的只有 3G。那么假设创建一个线程需要占用 10M 虚拟内存，总共有 3G 虚拟内存可以使用。于是我们可以算出，最多可以创建差不多 300 个（3G/10M）左右的线程。

  • 下面这三个内核参数的大小，都会影响创建线程的上限：

    • /proc/sys/kernel/threads-max，表示系统支持的最大线程数，默认值是 14553；

    • /proc/sys/kernel/pid_max，表示系统全局的 PID 号数值的限制，每一个进程或线程都有 ID，ID 的值超过这个数，进程或线程就会创建失败，默认值是 32768；

    • /proc/sys/vm/max_map_count，表示限制一个进程可以拥有的VMA(虚拟内存区域)的数量，如果它的值很小，也会导致创建线程失败，默认值是 65530。

• 总结：

  32 位系统，用户态的虚拟空间只有 3G，如果创建线程时分配的栈空间是 10M，那么一个进程最多只能创建 300 个左右的线程。

  64 位系统，用户态的虚拟空间大到有 128T，理论上不会受虚拟内存大小的限制，而会受系统的参数或性能限制。

线程崩溃了，进程也会崩溃吗？

如果线程因为非法访问内存崩溃，进程也会崩溃。

• 因为进程中，每个线程地址空间共享，如果产生非法内存访问，可能会对其他线程产生影响。所以整个线程就会崩溃。

非法访问的情况：对只读内存进行写入、访问进程没有权限访问的地址（比如内核空间）、访问不存在的内存。

操作系统使用信号来让进程崩溃。背后的机制如下：

1. CPU 执行正常的进程指令
2. 调用 kill 系统调用向进程发送信号
3. 进程收到操作系统发的信号，CPU 暂停当前程序运行，并将控制权转交给操作系统
4. 调用 kill 系统调用向进程发送信号（假设为 11，即 SIGSEGV，一般非法访问内存报的都是这个错误）
5. 操作系统根据情况执行相应的信号处理程序（函数），一般执行完信号处理程序逻辑后会让进程退出。

为什么线程崩溃不会导致JVM进程崩溃？

因为 JVM 自定义了自己的信号处理函数，拦截了 SIGSEGV 信号，针对这两者不让它们崩溃。在启动 JVM 的时候，也设置了信号处理函数，收到 SIGSEGV，SIGPIPE 等信号后最终会调用 JVM_handle_linux_signal 这个自定义信号处理函数。恢复了线程的执行，并抛出 StackoverflowError 和 NPE（NullPointExpection），这就是为什么 JVM 不会崩溃且我们能捕获这两个异常的原因。

• SEGV是segmentation violation（段违例）的缩写。

如果 JVM 不对信号做额外的处理，最后会自己退出并产生 crash 文件 hs_err_pid_xxx.log（可以通过 -XX:ErrorFile=/var/log/hs_err.log 这样的方式指定），这个文件记录了虚拟机崩溃的重要原因。

Java并发

Java并发常见面试题（上）

• 进程和线程的关系

  进程是资源分配的基本单位，而一个进程可以有多个线程，线程是资源调度的最小单位。多个线程可以共享进程的堆和方法区。

  从JVM角度来说进程和线程的关系：

  从上图看出：一个进程中可以有多个线程，多个线程共享进程的堆和方法区，但是每个线程有自己的程序计数器、虚拟机栈和本地方法栈。

  进程和线程的最大区别在于，基本上各进程是独立的，各线程却不一定，同一进程的线程极有可能会相互影响。线程开销小，但是不利于资源的管理和保护。

• 程序计数器为什么是私有的？

  程序计数器属于寄存器的一种，在CPU的内部。有以下作用：

  1. 根据程序计数器的内存地址读取命令。
  2. 多线程的情况下，程序计数器记录当前线程的执行位置，当线程被切换回来时，可以知道线程上次运行到哪儿了。

  所以，程序计数器私有主要是为了线程切换之后能恢复到正确的执行位置。

• 虚拟机栈和本地方法栈为什么是私有的？

  • 栈解决程序的运行问题，即程序如何执行，或者说如何处理数据。
  • 堆解决的是数据存储的问题，即数据怎么放，放哪里。

  虚拟机栈： 每个线程运行时所需要的内存，就是虚拟机栈。每个 Java 方法在执行的同时会创建一个栈帧用于存储局部变量表、操作数栈、常量池引用等信息。从方法调用直至执行完成的过程，就对应着一个栈帧在 Java 虚拟机栈中入栈和出栈的过程。

  本地方法栈： 和虚拟机栈所发挥的作用非常相似，区别是： 虚拟机栈为虚拟机执行 Java 方法 （也就是字节码）服务，而本地方法栈则为虚拟机使用到的 Native 方法服务。

  所以，为了保证线程中的局部变量不被别的线程访问，虚拟机栈和本地方法栈是线程私有的。

• 堆和方法区是什么？

  堆和方法区是所有线程共享的资源，堆用于存放新创建的对象，是进程中最大的一块内存。方法区用于存放被加载的类的信息、常量、静态变量等数据。

• 并发与并行的区别？

  并发：单核CPU中，多个任务在同一时间段内执行。

  并行：多核CPU中，多个任务在同一时刻执行。

• 同步和异步的区别？

  同步：发出调用，等待返回。

  异步：发出调用，直接返回。

• 为什么要使用多线程？

  从CPU多核心来说：现在的CPU多为多核CPU，那么就意味着多个线程可以同时执行，使用多线程，可以减少线程上下文切换的开销成本，可以提高CPU核心的利用率。

  **从高并发来说：**多线程并发编程是开发高并发系统的基础，使用多线程可以提高系统的并发性能。

• 多线程带来的问题？

  内存泄漏、死锁、线程不安全等等。

• 说说线程的生命周期和状态？

  Java 线程在运行的生命周期中的指定时刻只可能处于下面 6 种不同状态的其中一个状态：

  • NEW: 初始状态，线程被创建出来但没有被调用 start() 。
  • RUNNABLE: 运行状态，线程被调用了 start()等待运行的状态。
  • BLOCKED ：阻塞状态，需要等待锁释放。
  • WAITING：等待状态，表示该线程需要等待其他线程做出一些特定动作（通知或中断）。
  • TIME_WAITING：超时等待状态，可以在指定的时间后自行返回而不是像 WAITING 那样一直等待。
  • TERMINATED：终止状态，表示该线程已经运行完毕。

  线程在生命周期中并不是固定处于某一个状态而是随着代码的执行在不同状态之间切换。

• 什么是上下文切换？

  线程在执行过程中会有自己的运行条件和状态（也称上下文），比如上文所说到过的程序计数器，栈信息等。当出现如下情况的时候，线程会从占用 CPU 状态中退出。

  • 主动让出 CPU，比如调用了 sleep(), wait() 等。
  • 时间片用完，因为操作系统要防止一个线程或者进程长时间占用 CPU 导致其他线程或者进程饿死。
  • 调用了阻塞类型的系统中断，比如请求 IO，线程被阻塞。
  • 被终止或结束运行

  这其中前三种都会发生线程切换，线程切换意味着需要保存当前线程的上下文，留待线程下次占用 CPU 的时候恢复现场。并加载下一个将要占用 CPU 的线程上下文。这就是所谓的 上下文切换。

  上下文切换是现代操作系统的基本功能，因其每次需要保存信息恢复信息，这将会占用 CPU，内存等系统资源进行处理，也就意味着效率会有一定损耗，如果频繁切换就会造成整体效率低下。

• 什么是线程死锁？如何避免死锁？

  线程死锁描述的是这样一种情况：多个线程同时被阻塞，它们中的一个或者全部都在等待某个资源被释放。由于线程被无限期地阻塞，因此程序不可能正常终止。

  产生死锁的四个必要条件：

  1. 互斥条件：该资源任意一个时刻只由一个线程占用。
  2. 请求与保持条件：一个线程因请求资源而阻塞时，对已获得的资源保持不放。
  3. 不剥夺条件:线程已获得的资源在未使用完之前不能被其他线程强行剥夺，只有自己使用完毕后才释放资源。
  4. 循环等待条件:若干线程之间形成一种头尾相接的循环等待资源关系。

• 如何预防和避免线程死锁？

  如何预防死锁？ 破坏死锁的产生的必要条件即可：

  1. 破坏请求与保持条件 ：一次性申请所有的资源。
  2. 破坏不剥夺条件 ：占用部分资源的线程进一步申请其他资源时，如果申请不到，可以主动释放它占有的资源。
  3. 破坏循环等待条件 ：靠按序申请资源来预防。按某一顺序申请资源，释放资源则反序释放。破坏循环等待条件。

  如何避免死锁？

  避免死锁就是在资源分配时，借助于算法（比如银行家算法）对资源分配进行计算评估，使其进入安全状态。

• sleep()方法和wait()方法对比

  共同点 ：两者都可以暂停线程的执行。

  区别 ：

  • sleep() 方法没有释放锁，而 wait() 方法释放了锁 。
  • wait() 通常被用于线程间交互/通信，sleep()通常被用于暂停执行。
  • wait() 方法被调用后，线程不会自动苏醒，需要别的线程调用同一个对象上的 notify()或者 notifyAll() 方法。sleep()方法执行完成后，线程会自动苏醒，或者也可以使用 wait(long timeout) 超时后线程会自动苏醒。
  • sleep() 是 Thread 类的静态本地方法，wait() 则是 Object 类的本地方法。

• 为什么 wait() 方法不定义在 Thread 中？

  wait() 是让获得对象锁的线程实现等待，会自动释放当前线程占有的对象锁。每个对象（Object）都拥有对象锁，既然要释放当前线程占有的对象锁并让其进入 WAITING 状态，自然是要操作对应的对象（Object）而非当前的线程（Thread）。

  类似的问题：为什么 sleep() 方法定义在 Thread 中？

  因为 sleep() 是让当前线程暂停执行，不涉及到对象类，也不需要获得对象锁。

• 可以直接调用Thread类的run 方法吗？

  不可以。应该调用start()方法， 调用 start() 方法可以启动线程并使线程进入就绪状态，直接执行 run() 方法的话不会以多线程的方式执行。会把 run() 方法当成一个 main 线程下的普通方法去执行，并不会在某个线程中执行它，所以这并不是多线程工作。

  • 因为当我们new 一个 Thread对象创建一个线程。随后调用 start()方法，会启动一个线程并使线程进入了就绪状态，当分配到时间片后就可以开始运行了。 start() 会执行线程的相应准备工作，然后自动执行 run() 方法的内容，这是真正的多线程工作。