BBR

今天花了一个下午学习bbr，真的是太奇妙了这个东西。计算机网络的东西我都忘得差不多了，一边学习一边回顾，也不敢写什么研究心得，主要是看了知乎上李博杰关于bbr的回答，然后看了原文（以下简称，对于一些不太清楚的概念做一些笔记，以便时候回顾。

一些概念

• 加性增，乘性减：简单讲就是说，tcp loss-based拥塞控制传输时，拥塞窗口会已加的形式增大，而一旦遇到包丢失的情况，就会以除二的方式减小窗口。详情可以查看tcp慢启动和指数退避相关内容。

这张图我看了半个小时（学渣！），图的整体意思是说：单位时间内，随着发送数据的增加，到达链路运输能力（实际带宽）前发送速率（数据成功到达receiver的）增加，数据延迟不变；一旦达到链路的运输能力，发送速率不会变化，而数据发送耗时会增加。BBR将数据发送量限制到带宽，从而达到发送速率最大同时耗时最短，而传统的基于丢包的拥塞控制则控制的是数据量为buffer的极限。一点上图中的概念解析：

• inflight:拥塞窗口（？不确定），可以理解为发送的数据量
• loss-based congestion control:基于包丢失的拥塞控制。传统TCP拥塞控制方法，由于链路中存在buffer，buffer容量会比链路大，当buffer缓冲区到达limit时，会产生丢包行为，因此会把‘丢包’这个行为视为拥塞控制信号。因此，在高丢包率的长肥管道（带宽大，延迟高）中，这种机制表现非常差，会不停地进行指数退避。
• RTT：round-trip time，指一个包从sender方到达receiver方耗时
• RTprop:物理延迟。当链路中没有任何排队和其他耗时时，RTprop=RTT
• deliveryRate：发送速率。虽然有rate但并不是说的比率，Delivery Rate = CWND/SRTT，其中CWND = 可发送包的个数 * 包的大小；SRTT 是平滑RTT，动态测量的结果。所以deliveryRate 其实可以解释为每单位时间可以发送的数据量。中有个公式，大意为BtlBw=max(deliveryRatet)，也就是评估瓶颈带宽的方式。
• BtlBw:瓶颈带宽，也就是链路的最大传输能力。
• BDP带宽时延积：（Bandwidth-Delay Product ，BDP）即链路上的最大比特数，也称以比特为单位的链路长度。计算方法：Bandwidth-Delay Product = delay_bandwidth=RTprop_BtlBw
  BBR的方法可以理解为将链路上的比特数控制为BDP的值。
  论文：
  一开始讲了RTprop和BtlBw的回归方程计算。表明BBR需要实时统计deliveryRate和RTT的值来获得RTprop和BtlBw的值。
  然后说了RTprop和BtlBw不能同时测得。

锁

自旋锁 ，自旋锁的其他种类，阻塞锁，可重入锁 ，读写锁 ，互斥锁 ，悲观锁 ，乐观锁 ，公平锁 ，偏向锁， 对象锁，线程锁，锁粗化， 锁消除，轻量级锁，重量级锁， 信号量，独享锁，共享锁，分段锁

不可不说的Java“锁”事

乐观锁 VS 悲观锁

对于同一个数据的并发操作，悲观锁认为自己在使用数据的时候一定有别的线程来修改数据，因此在获取数据的时候会先加锁，确保数据不会被别的线程修改。Java中，synchronized关键字和Lock的实现类都是悲观锁。

而乐观锁认为自己在使用数据时不会有别的线程修改数据，所以不会添加锁，只是在更新数据的时候去判断之前有没有别的线程更新了这个数据。如果这个数据没有被更新，当前线程将自己修改的数据成功写入。如果数据已经被其他线程更新，则根据不同的实现方式执行不同的操作（例如报错或者自动重试）。

1. 乐观锁在Java中是通过使用无锁编程来实现，最常采用的是CAS算法，Java原子类中的递增操作就通过CAS自旋实现的。例如AtomicInteger.incrementAndGet()
2. 版本号机制。一般是在数据表中加上一个数据版本号version字段，表示数据被修改的次数，当数据被修改时，version值会加一。当线程A要更新数据值时，在读取数据的同时也会读取version值，在提交更新时，若刚才读取到的version值为当前数据库中的version值相等时才更新，否则重试更新操作，直到更新成功。

场景：

• 悲观锁适合写操作多的场景，先加锁可以保证写操作时数据正确。
• 乐观锁适合读操作多的场景，不加锁的特点能够使其读操作的性能大幅提升。

CAS虽然很高效，但是它也存在三大问题：

1. ABA问题。CAS需要在操作值的时候检查内存值是否发生变化，没有发生变化才会更新内存值。但是如果内存值原来是A，后来变成了B，然后又变成了A，那么CAS进行检查时会发现值没有发生变化，但是实际上是有变化的。ABA问题的解决思路就是在变量前面添加版本号，每次变量更新的时候都把版本号加一，这样变化过程就从“A－B－A”变成了“1A－2B－3A”。
   • JDK从1.5开始提供了AtomicStampedReference类来解决ABA问题，具体操作封装在compareAndSet()中。compareAndSet()首先检查当前引用和当前标志与预期引用和预期标志是否相等，如果都相等，则以原子方式将引用值和标志的值设置为给定的更新值。
2. 循环时间长开销大。CAS操作如果长时间不成功，会导致其一直自旋，给CPU带来非常大的开销。
3. 只能保证一个共享变量的原子操作。对一个共享变量执行操作时，CAS能够保证原子操作，但是对多个共享变量操作时，CAS是无法保证操作的原子性的。
   • Java从1.5开始JDK提供了AtomicReference类来保证引用对象之间的原子性，可以把多个变量放在一个对象里来进行CAS操作。

自旋锁 VS 适应性自旋锁

阻塞或唤醒一个Java线程需要操作系统切换CPU状态来完成，这种状态转换需要耗费处理器时间。如果同步代码块中的内容过于简单，状态转换消耗的时间有可能比用户代码执行的时间还要长。

在许多场景中，同步资源的锁定时间很短，为了这一小段时间去切换线程，线程挂起和恢复现场的花费可能会让系统得不偿失。如果物理机器有多个处理器，能够让两个或以上的线程同时并行执行，我们就可以让后面那个请求锁的线程不放弃CPU的执行时间，看看持有锁的线程是否很快就会释放锁。

而为了让当前线程“稍等一下”，我们需让当前线程进行自旋，如果在自旋完成后前面锁定同步资源的线程已经释放了锁，那么当前线程就可以不必阻塞而是直接获取同步资源，从而避免切换线程的开销。这就是自旋锁。

自旋锁本身是有缺点的，它不能代替阻塞。自旋等待虽然避免了线程切换的开销，但它要占用处理器时间。如果锁被占用的时间很短，自旋等待的效果就会非常好。反之，如果锁被占用的时间很长，那么自旋的线程只会白浪费处理器资源。所以，自旋等待的时间必须要有一定的限度，如果自旋超过了限定次数（默认是10次，可以使用-XX:PreBlockSpin来更改）没有成功获得锁，就应当挂起线程。

自旋锁的实现原理同样也是CAS，AtomicInteger中调用unsafe进行自增操作的源码中的do-while循环就是一个自旋操作，如果修改数值失败则通过循环来执行自旋，直至修改成功。

自旋锁在JDK1.4.2中引入，使用-XX:+UseSpinning来开启。JDK 6中变为默认开启，并且引入了自适应的自旋锁（适应性自旋锁）。

自适应意味着自旋的时间（次数）不再固定，而是由前一次在同一个锁上的自旋时间及锁的拥有者的状态来决定。如果在同一个锁对象上，自旋等待刚刚成功获得过锁，并且持有锁的线程正在运行中，那么虚拟机就会认为这次自旋也是很有可能再次成功，进而它将允许自旋等待持续相对更长的时间。如果对于某个锁，自旋很少成功获得过，那在以后尝试获取这个锁时将可能省略掉自旋过程，直接阻塞线程，避免浪费处理器资源。

例：

• TicketLock，基于先进先出(FIFO) 队列的自旋锁，保证首先注册的线程有更高级别优先性获取锁。有两个值，一个当前处理队列号，一个等待处理队列号。TicketLock 虽然解决了公平性的问题，但是多处理器系统上，每个进程/线程占用的处理器都在读写同一个变量queueNum ，每次读写操作都必须在多个处理器缓存之间进行缓存同步，这会导致繁重的系统总线和内存的流量，大大降低系统整体的性能。CLHLock和MCSLock是更好的解决方式
• CLHLock，基于隐式链表的自旋锁，线程将会获取上一个线程注册的CLHNode对象，只有当CLHNode.isLocked==false时，自己才获得了锁
• MCSLock，基于显式链表的自旋锁

无锁 VS 偏向锁 VS 轻量级锁 VS 重量级锁

偏向锁通过对比Mark Word解决加锁问题，避免执行CAS操作。而轻量级锁是通过用CAS操作和自旋来解决加锁问题，避免线程阻塞和唤醒而影响性能。重量级锁是将除了拥有锁的线程以外的线程都阻塞。随着锁的竞争，锁可以从偏向锁升级到轻量级锁，再升级的重量级锁（但是锁的升级是单向的，也就是说只能从低到高升级，不会出现锁的降级）

Java并发——关键字synchronized解析

Java锁—偏向锁、轻量级锁、自旋锁、重量级锁

synchronized & Java对象头

synchronized是悲观锁，在操作同步资源之前需要给同步资源先加锁，这把锁就是存在Java对象头里的，而Java对象头又是什么呢？

我们以Hotspot虚拟机为例，Hotspot的对象头主要包括两部分数据：Mark Word（标记字段）、Klass Pointer（类型指针）。

Mark Word：默认存储对象的HashCode，分代年龄和锁标志位信息。这些信息都是与对象自身定义无关的数据，所以Mark Word被设计成一个非固定的数据结构以便在极小的空间内存存储尽量多的数据。它会根据对象的状态复用自己的存储空间，也就是说在运行期间Mark Word里存储的数据会随着锁标志位的变化而变化。

下面给出四种锁状态对应的的Mark Word内容

Klass Point：对象指向它的类元数据的指针，虚拟机通过这个指针来确定这个对象是哪个类的实例。

Monitor

Monitor可以理解为一个同步工具或一种同步机制，通常被描述为一个对象。每一个Java对象就有一把看不见的锁，称为内部锁或者Monitor锁。

Monitor是线程私有的数据结构，每一个线程都有一个可用monitor record列表，同时还有一个全局的可用列表。每一个被锁住的对象都会和一个monitor关联，同时monitor中有一个Owner字段存放拥有该锁的线程的唯一标识，表示该锁被这个线程占用。

结构如下：

Owner：初始时为NULL表示当前没有任何线程拥有该monitor record，当线程成功拥有该锁后保存线程唯一标识，当锁被释放时又设置为NULL

EntryQ：关联一个系统互斥锁（semaphore），阻塞所有试图锁住monitor record失败的线程

RcThis：表示blocked或waiting在该monitor record上的所有线程的个数

Nest：用来实现重入锁的计数

HashCode：保存从对象头拷贝过来的HashCode值（可能还包含GC age）

Candidate：用来避免不必要的阻塞或等待线程唤醒，因为每一次只有一个线程能够成功拥有锁，如果每次前一个释放锁的线程唤醒所有正在阻塞或等待的线程，会引起不必要的上下文切换（从阻塞到就绪然后因为竞争锁失败又被阻塞）从而导致性能严重下降。Candidate只有两种可能的值0表示没有需要唤醒的线程1表示要唤醒一个继任线程来竞争锁

这四种锁是指锁的状态，专门针对synchronized的,synchronized通过Monitor来实现线程同步，Monitor是依赖于底层的操作系统的Mutex Lock（互斥锁）来实现的线程同步。

依赖于操作系统Mutex Lock所实现的锁我们称之为“重量级锁”，JDK 6中为了减少获得锁和释放锁带来的性能消耗，引入了“偏向锁”和“轻量级锁”。

所以目前锁一共有4种状态，级别从低到高依次是：无锁、偏向锁、轻量级锁和重量级锁。锁状态只能升级不能降级。

无锁

无锁没有对资源进行锁定，所有的线程都能访问并修改同一个资源，但同时只有一个线程能修改成功。

无锁的特点就是修改操作在循环内进行，线程会不断的尝试修改共享资源。如果没有冲突就修改成功并退出，否则就会继续循环尝试。如果有多个线程修改同一个值，必定会有一个线程能修改成功，而其他修改失败的线程会不断重试直到修改成功。上面我们介绍的CAS原理及应用即是无锁的实现。无锁无法全面代替有锁，但无锁在某些场合下的性能是非常高的。

偏向锁

偏向锁是指一段同步代码一直被一个线程所访问，那么该线程会自动获取锁，降低获取锁的代价。

在大多数情况下，锁总是由同一线程多次获得，不存在多线程竞争，所以出现了偏向锁。其目标就是在只有一个线程执行同步代码块时能够提高性能。

当一个线程访问同步代码块并获取锁时，会在Mark Word里存储锁偏向的线程ID。在线程进入和退出同步块时不再通过CAS操作来加锁和解锁，而是检测Mark Word里是否存储着指向当前线程的偏向锁。引入偏向锁是为了在无多线程竞争的情况下尽量减少不必要的轻量级锁执行路径，因为轻量级锁的获取及释放依赖多次CAS原子指令，而偏向锁只需要在置换ThreadID的时候依赖一次CAS原子指令即可。

偏向锁只有遇到其他线程尝试竞争偏向锁时，持有偏向锁的线程才会释放锁，线程不会主动释放偏向锁。偏向锁的撤销，需要等待全局安全点（在这个时间点上没有字节码正在执行），它会首先暂停拥有偏向锁的线程，判断锁对象是否处于被锁定状态。撤销偏向锁后恢复到无锁（标志位为“01”）或轻量级锁（标志位为“00”）的状态。

偏向锁在JDK 6及以后的JVM里是默认启用的。可以通过JVM参数关闭偏向锁：-XX:-UseBiasedLocking=false，关闭之后程序默认会进入轻量级锁状态。

轻量级锁

是指当锁是偏向锁的时候，被另外的线程所访问，偏向锁就会升级为轻量级锁，其他线程会通过自旋的形式尝试获取锁，不会阻塞，从而提高性能。

在代码进入同步块的时候，如果同步对象锁状态为无锁状态（锁标志位为“01”状态，是否为偏向锁为“0”），虚拟机首先将在当前线程的栈帧中建立一个名为锁记录（Lock Record）的空间，用于存储锁对象目前的Mark Word的拷贝，然后拷贝对象头中的Mark Word复制到锁记录中。

拷贝成功后，虚拟机将使用CAS操作尝试将对象的Mark Word更新为指向Lock Record的指针，并将Lock Record里的owner指针指向对象的Mark Word。

如果这个更新动作成功了，那么这个线程就拥有了该对象的锁，并且对象Mark Word的锁标志位设置为“00”，表示此对象处于轻量级锁定状态。

如果轻量级锁的更新操作失败了，虚拟机首先会检查对象的Mark Word是否指向当前线程的栈帧，如果是就说明当前线程已经拥有了这个对象的锁，那就可以直接进入同步块继续执行，否则说明多个线程竞争锁。

若当前只有一个等待线程，则该线程通过自旋进行等待。但是当自旋超过一定的次数，或者一个线程在持有锁，一个在自旋，又有第三个来访时，轻量级锁升级为重量级锁。

重量级锁

轻量级锁自旋

升级为重量级锁时，锁标志的状态值变为“10”，此时Mark Word中存储的是指向重量级锁的指针，此时等待锁的线程都会进入阻塞状态。

锁的转换

公平锁 VS 非公平锁

公平锁是指多个线程按照申请锁的顺序来获取锁，线程直接进入队列中排队，队列中的第一个线程才能获得锁。公平锁的优点是等待锁的线程不会饿死。缺点是整体吞吐效率相对非公平锁要低，等待队列中除第一个线程以外的所有线程都会阻塞，CPU唤醒阻塞线程的开销比非公平锁大。

非公平锁是多个线程加锁时直接尝试获取锁，获取不到才会到等待队列的队尾等待。但如果此时锁刚好可用，那么这个线程可以无需阻塞直接获取到锁，所以非公平锁有可能出现后申请锁的线程先获取锁的场景。非公平锁的优点是可以减少唤起线程的开销，整体的吞吐效率高，因为线程有几率不阻塞直接获得锁，CPU不必唤醒所有线程。缺点是处于等待队列中的线程可能会饿死，或者等很久才会获得锁。

可重入锁 VS 非可重入锁

可重入锁又名递归锁，是指在同一个线程在外层方法获取锁的时候，再进入该线程的内层方法会自动获取锁（前提锁对象得是同一个对象或者class），不会因为之前已经获取过还没释放而阻塞。Java中ReentrantLock和synchronized都是可重入锁，可重入锁的一个优点是可一定程度避免死锁。

独享锁 VS 共享锁

独享锁也叫排他锁，是指该锁一次只能被一个线程所持有。如果线程T对数据A加上排它锁后，则其他线程不能再对A加任何类型的锁。获得排它锁的线程即能读数据又能修改数据。JDK中的synchronized和JUC中Lock的实现类就是互斥锁。

共享锁是指该锁可被多个线程所持有。如果线程T对数据A加上共享锁后，则其他线程只能对A再加共享锁，不能加排它锁。获得共享锁的线程只能读数据，不能修改数据。

独享锁与共享锁也是通过AQS来实现的，通过实现不同的方法，来实现独享或者共享。

锁粗化/锁消除

锁消除：

锁消除是指虚拟机即时编译器在运行时，对一些代码上要求同步，但是被检测到不可能存在共享数据竞争的锁进行消除。锁消除的主要判定依据来源于逃逸分析的数据支持，如果判断在一段代码中，堆上的所有数据都不会逃逸出去从而被其他线程访问到，那就可以把它们当做栈上数据对待，认为它们是线程私有的，同步加锁自然就无须进行。

锁粗化：

如果一系列的连续操作都对同一个对象反复加锁和解锁，甚至加锁操作是出现在循环体中的，那即使没有线程竞争，频繁地进行互斥同步操作也会导致不必要的性能损耗。如果虚拟机探测到有这样一串零碎的操作都对同一个对象加锁，将会把加锁同步的范围扩展（粗化）到整个操作序列的外部

1
2
3
4
5
6
7
8
9
10
11

package com.paddx.test.string;

public class StringBufferTest {
    StringBuffer stringBuffer = new StringBuffer();

    public void append(){
        stringBuffer.append("a");
        stringBuffer.append("b");
        stringBuffer.append("c");
    }
}

这里每次调用stringBuffer.append方法都需要加锁和解锁，如果虚拟机检测到有一系列连串的对同一个对象加锁和解锁操作，就会将其合并成一次范围更大的加锁和解锁操作，即在第一次append方法时进行加锁，最后一次append方法结束后进行解锁。

Yarn

背景

hadoop1.0中架构：

问题：

• 由于大量的数据处理Job提交给Job Tracker，且Job Tracker需要协调的Data Node可能有数千台，Job Tracker极易成为整个系统的性能、可用的瓶颈。
• 无法有效地调配资源，导致资源分配不均。如以下例子，假设有3台Data Node（DN），每个DN的内存为4GB。用户提交了6个Job，每个Job需要1GB内存进行处理，且数据均在DN2上。由于DN2只有4GB内存，所以Job1-4在DN2上运行，Job5和6则在排队等待。但是，此时DN1和3均在闲置的状态下，而未能有效的被利用。

模块

ResourceManager

负责对各个NodeManager 上的资源进行统一管理和调度。包含两个组件：

• Scheduler：调度器根据容量、队列等限制条件（如每个队列分配一定的资源，最多执行一定数量的作业等），将系统中的资源分配给各个正在运行的应用程序
• Applications Manager：应用程序管理器负责管理整个系统中所有应用程序，包括应用程序提交、与调度器协商资源以启动ApplicationMaster、监控ApplicationMaster运行状态并在失败时重新启动它等

NodeManager

NM 是每个节点上的资源和任务管理器。

• 定时地向RM 汇报本节点上的资源使用情况和各个Container 的运行状态
• 接收并处理来自AM 的Container启动/ 停止等各种请求

ApplicationMaster

用户提交的每个应用程序均包含一个AM，主要功能包括：

• 与RM 调度器协商以获取资源（用 Container 表示）
• 将得到的任务进一步分配给内部的任务
• 与 NM 通信以启动 / 停止任务
• 监控所有任务运行状态，并在任务运行失败时重新为任务申请资源以重启任务

Container

Container 是YARN 中的资源抽象， 它封装了某个节点上的多维度资源， 如内存、CPU、磁盘、网络等，当AM 向RM 申请资源时，RM 为AM 返回的资源便是用Container表示的

工作流程

1. 用户向YARN 中提交应用程序， 其中包括ApplicationMaster 程序、启动ApplicationMaster 的命令、用户程序等。
2. ResourceManager 为该应用程序分配第一个Container，并与对应的Node-Manager 通信，要求它在这个Container中启动应用程序的ApplicationMaster。
3. ApplicationMaster 首先向ResourceManager 注册，这样用户可以直接通过ResourceManage 查看应用程序的运行状态，然后它将为各个任务申请资源，并监控它的运行状态，直到运行结束，即重复步骤4~7。
4. ApplicationMaster 采用轮询的方式通过RPC 协议向ResourceManager 申请和领取资源。
5. 一旦ApplicationMaster 申请到资源后，便与对应的NodeManager 通信，要求它启动任务。
6. NodeManager 为任务设置好运行环境（包括环境变量、JAR 包、二进制程序等）后，将任务启动命令写到一个脚本中，并通过运行该脚本启动任务。
7. 各个任务通过某个RPC 协议向ApplicationMaster 汇报自己的状态和进度，以让ApplicationMaster 随时掌握各个任务的运行状态，从而可以在任务失败时重新启动任务。在应用程序运行过程中，用户可随时通过RPC向ApplicationMaster 查询应用程序的当前运行状态。
8. 应用程序运行完成后，ApplicationMaster 向ResourceManager 注销并关闭自己。

资源调度算法

FIFO

FIFO 调度算法用于最早的 Hadoop 系统中，Hadoop 面向的是单用户提交的大规模数据处理作业。在 FIFO 调度算法中只有一个用户，所有作业按照优先级提交至具有不同优先级的队列中，然后由调度器（Scheduler）先按照作业提交的时间顺序选择待执行的作业。FIFO 的队列设置了 5 个优先等级，分别为：Very Low、Low、Normal、High 及 Very High。每个等级对应一个队列，按照队列的优先级从高到低选取队列，在同级队列中，按照提交作业的时间先后顺序提取并执行。其调度大体流程如图所示。

Capacity 调度算法

• 队列中单个任务使用的资源不会超过队列的容量。
• 如果队列满，且集群有空闲的资源，调度器可以把资源分配给此队列（可配置），弹性队列。
• 正常情况下，容量调度器不会抢占容器，因此如果一个队列随着使用，资源不够时，只能等待其他队列释放资源。
• 容量调度器也可以执行work-preserving preemption，RM会请求应用返回容器。

Capacity 调度算法是由 Yahoo！开发的多用户调度策略，它以队列为单位划分资源，每个队列可设定一定比例的资源最低保证和使用上限，同时每个用户也可设定一定的资源使用上限以防止资源滥用。而当一个队列的资源有剩余时，可暂时将剩余资源共享给其他队列。Capacity Scheduler 支持多个队列，每个队列可分配一定的资源量，队列中资源的调度策略可以为 FIFO 或 DRF (Dominant Resource Fairness)，多用户下，为防止同一个用户提交的作业独占队列的所有资源，Capacity Scheduler 对每个用户可提交的作业可分配的资源量进行了限制。

应用程序提交后，ResourceManager 会向 CapacityScheduler 发送一个事件，CapacityScheduler 收到后，将为应用程序创建一个对象跟踪和维护其运行时的信息，同时，将它提交到对应的叶子队列中，队列会对应用程序进行合法性检查。通过检查，应用程序才算提交成功。提交成功后，它的ApplicationMaster会为它申请资源，CapacityScheduler收到资源申请后，暂时将这些请求存放到一个数据结构中，以等待为其分配合适的资源。

NodeManager 发送的心跳信息有两类需要 CapacityScheduler 处理：一类是最新启动的 Container；另一类是运行完成的 Container。CapacityScheduler 将回收它使用的资源进行再分配。CapacityScheduler 采用三级资源分配策略(即将双层调度机制中的第一层分为选择队列与选择应用程序两级)，当一个节点上有空闲资源时，它会依次选择队列、应用程序和 Container (请求)使用该资源，接下来介绍三级资源分配策略。

第一级：选择队列。CapacityScheduler 采用基于优先级的深度优先遍历算法选择队列：从根队列开始，按照资源使用率由小到大遍历子队列。如果子队列是叶子队列，则按照第二、三级的方法在队列中选择一个 Container，否则以该队列为根队列，重复以上过程，直到找到合适的 Container 并退出。

第二级：选择应用程序。选中一个叶子队列后，CapacityScheduler 按照ApplicationID 对叶子队列中的应用程序进行排序，依次遍历排序后的应用程序，找到合适的 Container。

第三级：选择 Container。选中一个应用程序后，先满足优先级高的Container。同一优先级，先满足本地化的 Container，依次选择节点本地化、机架本地化和非本地化的 Container。

Fair 调度算法

• 每个队列有权重元素，用于fair share的计算。
• 默认队列和动态创建的队列，权重为1（默认队列的可配置）。
• 调度器会使用最小资源数量来进行资源分配进行优先排序。如果两个队列的资源都低于fair share额度，那么远低于最小资源数量的队列，会被有限分配资源。

Fair Scheduler 是 Facebook 开发的多用户调度器，同 Capacity Scheduler 相似，都以队列为单位划分资源，且每个队列可设定一定比例的资源最低保证和使用上限。Facebook 设计 Fair Scheduler 算法的初衷是让 Hadoop 平台可以更高效的处理不同类型的作业，最大化的保证了系统中各作业能够分配到的系统资源 。如果当前集群中只有一个作业，则该作业会独占整个集群中全部系统资源。当有新的作业被提交至系统时，一些任务会在完成后将资源分配给新提交的作业，Fair Scheduler 会尽量保证各作业间可以获得基本相同的系统资源，从而保证短作业具有较短的响应时间。

与CapacityScheduler不同的是，FairScheduler 提供了更多样化的调度策略，调度策略在队列间和队列内部可单独设置。当前有三种策略可选，分别是先来先服务(FIFO)、公平调度(Fair)和主资源公平调度(Dominant ResourceFairness，DRF)。

1. 先来先服务：按优先级高低调度，优先级相同，则按提交时间先后顺序调度；提交时间相同，则按名称大小调度。
2. 公平调度：按内存资源使用比率大小调度。
3. 主资源公平调度：按主资源公平调度算法进行调度，所需份额最大的资源称为主资源，把最大最小公平算法应用于主资源上，将多维资源调度问题转化为单资源调度问题。

DRF算法伪代码：

1
2
3
4
5
6
7
8
9
10
11
12

R = <r1, ··· , rm> //m种资源对应容量
C = <c1, ··· , cm> //已经使用资源量，初始为0
si (i = 1…n) //用户i的主资源所需份额，初始为0
Ui = <ui,1, ··· , ui,m> (i = 1…n) //分配给用户i的资源量，初始为0
挑选出所需主资源si最小的用户i；
Di ← 用户i下一个任务所需的资源量
if C + Di <= R then
C = C + Di //更新C
Ui = Ui + Di //更新U
else
return //资源已经用完
end if

饥饿和抢占

FairShare的计算会被用于判断饥饿以及是否进行抢占。在计算FairShare时，有两种：

• Steady FairShare，按照配置文件中所有queue的weight，计算出的。
• Instantaneous FairShare，，按照配置文件中所有queue的weight，仅对包含活动应用程序的queue计算出的。
  在配置yarn.scheduler.fair.preemption和yarn.scheduler.fair.preemption.cluster-utilization-threshold后，抢占会启用。

饥饿有两种：

1. FairShare Starvation
   要注意的是，在同一个队列里面，如果存在多个应用程序，它们会平均的分摊Instantaneous FairShare。因此可能存在队列整体不是饥饿状态，但是每个应用程序是。
   判定条件为：
   1. 未获得所要求的资源。
   2. 应用程序资源使用低于Instantaneous FairShare。
   3. 应用程序的资源使用低于fairSharePreemptionThreshold，并持续fairSharePreemptionTimeout。
2. MinShare Starvation
   判定条件为：
   1. 未获得所要求的资源。
   2. 应用程序资源使用低于MinShare。
   3. 应用程序的资源使用低于MinShare，并持续MinSharePreemptionTimeout。

决定需要进行抢占的时候，可能在多个队列中都有可抢占的container，决定container是否可以被抢占，需要满足：

1. 所在队列是可抢占的。
2. 杀死container以后不会导致应用程序的资源低于Instantaneous FairShare。

启用抢占并不能保证队列或应用程序能够获得所有的Instantaneous FairShare。只能最终保证脱离饥饿的状态，即获得fairSharePreemptionThreshold份额的资源。

FairShare Starvation、MinShare Starvation以及抢占的关系如下：

数据仓库

分层

原文

中断的定义与种类

Linux中的中断异常机制：

中断（interrupt）被定义为一个事件，该事件改变处理器执行的指令顺序，这样的事件与CPU芯片内外部硬件电路产生的电信号相对应。中断通常分为同步（synchronous）中断和异步（asynchronous）中断。

• 同步中断指的是当指令执行时由CPU控制单元产生的，之所以称为同步，是因为只有在一条指令终止执行后CPU才会发出中断。
• 异步中断是由其他硬件设备依照CPU时钟信号随机产生的。

在Intel处理器中，把同步中断和异步中断分别称为异常（exception）和中断（interrupt）。我们这里也采用这种分类。我们也使用中断信号来统称中断和异常。

中断是由间隔定时器和I/O设备产生的，例如，用户的一次按键会引起一个中断，虽然用户没有感觉，但是按键这个过程到下一次按键之间的间隔对于计算机指令时间来说是非常长的。

另一方面，异常是由程序的错误产生的，或者由内核必须处理的异常条件产生的。第一种情况下，内核通过发送一个每个Unix程序员都熟悉的信号来处理异常，第二种情况下，内核执行恢复异常需要的所有步骤，例如缺页异常。

中断信号提供了一种特殊的方式，使处理器转而去运行正常的控制流之外的代码。当一个中断信号到达时，CPU必须停止它当前正在做的事情，保留上下文，并切换产生中断后的一个空间。

虽然进程切换和中断都会导致内核保存上下文并且切换到另一空间，但中断处理程序和进程切换有一个明显的差异，由中断或异常处理程序执行的代码不是一个进程，更确切的说，它是一个内核执行路径，代表中断发生时正在运行的进程执行。作为一个内核控制路径，中断处理程序要比一个进程更轻量。

中断处理是由内核执行的最敏感的任务之一，因此它必须满足下面的约束：

当内核正打算去完成一些别的事情时，中断会随时到来。因此，内核的目标就是让中断尽可能快的处理完，尽其所能把更多的处理向后推迟。例如一个数据块已经到达了网线，当硬件中断内核时，内核只简单的标志数据到来了，让处理器恢复到它以前的运行状态，其余的处理稍后再进行。因此，内核响应中断后需要进行的操作氛围两部分，关键而紧急的部分内核立即执行，其他的推迟的部分内核随后会执行。

因为中断随时到来，所以内核可能正在处理其中一个中断的时候，另一个中断又会到来，应该尽可能多的允许这样的情况发生，因为这能维持更多的I/O设备处于忙状态，提高I/O设备的吞吐量。因此中断处理程序必须便写成使相应的内核控制路径能以嵌套的方式执行。当最后一个内核控制路径终止时，内核必须能恢复被中断执行的进程。

尽管内核在处理前一个中断时可以接受一个新的中断，但在内核代码中还是存在一些临界区，在临界区中，中断必须被禁止。必须尽可能的限制这样的临界区，因为根据以前的要求，内核，尤其时中断处理程序，应该在大部分时间内以开中断的方式运行。

Intel文档把中断和异常分为以下几类：

中断：

• 可屏蔽中断，I/O设备发出的所有中断请求（IRQ）都产生可屏蔽中断，一个屏蔽的中断只要还是屏蔽的，控制单元就可以忽略它。
• 非屏蔽中断，有一些危险的事件才能引起非屏蔽中断，例如硬件故障，非屏蔽中断总是由CPU辨认。

异常：

当CPU执行指令时探测到一个异常，会产生一个处理器探测异常（processor-detected exception），可以进一步区分，这取决于CPU控制单元产生异常时保存在内核堆栈eip寄存器的值。

• 故障（fault），通常可以纠正，一旦纠正，程序就可以重新开始，保存在eip寄存器中的值是引起故障的指令地址。
• 陷阱（trap）在陷阱指令执行后立即报告，内核把控制权烦给程序后就可以继续它的执行而不失连续性。保存在eip中的值是一个随后要执行的指令地址。陷阱的主要作用是为了调试程序。
• 异常中止（abort），发生一个严重的错误，控制单元出了问题，不能在eip寄存器中保存引起异常的指令所在的确切位置。异常中止用于报告严重的错误，例如硬件故障或系统表中无效的值或者不一致的值。这种异常会强制中止进程。
• 编程异常（programmed exception），在编程者发出的请求时发送，是由int或int3指令触发的。

每个中断和异常是由0～255之间的一个数来标识的，Intel把这个8位无符号整数叫做一个向量（vector）。非屏蔽中断的向量和异常的向量是固定的，而可屏蔽中断的向量是可以通过对中断控制器的编程来改变。

在X86中，分为实模式和保护模式，实模式通常是CPU启动到BIOS再到操作系统启动前的这段时间，操作启动初始化完成进入到保护模式。在不同模式下中断的处理机制同步，在这里只简单探讨一下保护模式下的中断机制。

中断的初始化

Intel X86位处理器有256个硬中断号，用一个8位的无符号整数表示，被叫做一个向量（vector）。

中断描述符表（Interrupt Descriptor Table，IDT）是一个系统表，它与每一个中断或异常向量相联系，每一个向量在表中有相应地中断或异常处理程序地入口地址，内核在允许中断发生前，必须适当地初始化IDT。

在IDT中可以存储以下三种Gate Descriptor（门描述符）：用于描述和控制Interrupt Service Routine（每个中断对应的回调函数）的访问，它们分别是：

• Interrupt Gate Descriptor（中断门描述符），包含段选择符和中断或异常处理程序地段内偏移量，当控制权转移到一个适当地段时，处理器清IF标志，从而关闭将来会发生的可屏蔽中断。
• Trap Gate Descriptor（陷井门描述符），和中断门类似，只是控制权传递到一个适当地段处理器不修改IF标志。
• Task Gate Descriptor（任务门描述符），Linux中未使用该类型，当中断信号发生时，必须取代当前进程地那个进程地TSS选择符存放在任务门中。

IDT表中地每一项Gate Descriptor由8个字节组成，因此，最多需要256x8=2048字节来存放IDT（64位时扩展到16个字节）。因为需要增加权限控制等因素，在IDT中并不直接关联到Interrupt Service Routine。

IDTR是一个CPU寄存器，用以存储IDT的基地址与段大小，用以快速访问。机器指令LLDT和SLDT是分别用来设置和保存LDTR寄存器的值。

在内核初始化的时候，会为每一个中断向量注册一个对应的回调函数（Interrupt Service Routine），初始化IDT与IDTR寄存器：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

// init/main.c
asmlinkage void __init start_kernel(void)
{
    ...
    setup_arch(&command_line); // 初始化架构相关的，其中包含一些与架构相关的中断，
                               // Page Fault相关的中断就在其内部注册
    ...
    trap_init();    // 初始化异常处理
    ...
    init_IRQ();     // 初始化外部中断
    ...
    init_timers();  // 初始化定时器模块，同时，会注册定时器的软中断处理函数
    ...
    softirq_init(); // 初始化软中断
}

// 在setup_arch中会调用early_trap_pf_init/early_trap_init，其中会注册
// Page Fault异常对应的中断函数page_fault
/* Set of traps needed for early debugging. */
void __init early_trap_init(void)
{
    set_intr_gate_ist(X86_TRAP_DB, &debug, DEBUG_STACK);
    /* int3 can be called from all */
    set_system_intr_gate_ist(X86_TRAP_BP, &int3, DEBUG_STACK);
#ifdef CONFIG_X86_32
    set_intr_gate(X86_TRAP_PF, &page_fault);
#endif
    load_idt(&idt_descr);
}

void __init early_trap_pf_init(void)
{
#ifdef CONFIG_X86_64
    set_intr_gate(X86_TRAP_PF, &page_fault);
#endif
}

更加详细的流程可以参考下面几张图。

在初始化完成后，每个中断向量都会有一个对应的回调函数（Interrupt Service Routine），不同的中断向量对应不同的软件逻辑，如果系统不关心，则置为ignore_int：

上面表格中的这些对应函数，都只是由汇编实现的跳转函数，他们的实现在arch/x86/kernel/entry_64.S，基本上都是处理一下必要的上下文，然后跳转到相关的C实现的函数do_xxx中。

中断和异常的硬件处理

中断触发

假定内核已经被初始化，因此，CPU在保护模式下运行，Linux只有在刚刚启动的时候是在实模式，之后便进入保护模式。

在执行了一条指令之后，cs和eip这对寄存器包含下一条将要执行的指令的逻辑地址，在处理了那条指令之后，控制单元会检查在运行前一条指令时是否已经发生了一个中断异或异常。如果发生了一个中断或者异常，那么控制单元执行下列操作：

1. 确定与中断或异常的关联向量i。
2. 读由IDTR寄存器指向的IDT表中的第i项门描述符。
3. 从GDTR寄存器获得GDT的基地址，并在GDT中查找，以读取IDT表项中的选择符所标识的段描述符，这个描述符指定中断或异常处理程序所在的段的基地址。
4. 确定中断是由授权的中断发生源发出的。(Why？因为INT指令允许用户态的进程产生中断信号，其向量值可以为0到255的任一值，为了避免用户通过INT指令产生非法中断，在初始化的时候，将向量值为80H的门描述符（系统调用使用该门）的DPL设为3，将其他需要避免访问的门描述符的DPL值设为0，这样在做权限检查的时候就可以检查出来非法的情况。)
5. 检查是否发生了特权等级变化。如果是由用户态陷入了内核态，控制单元必须开始使用与新的特权级相关的堆栈 5.1. 读TR寄存器，访问运行进程的TSS段。（why？因为任何进程从用户态陷入内核态都必须从TSS获得内核堆栈指针。) 5.2. 用与新特权级相关的栈段和栈指针装载ss和esp寄存器。这些值可以在进程的TSS段中找到。 5.3. 在新的栈（内核栈）中保存用户态的ss和esp，这些值指明了用户态相关栈的逻辑地址。
6. 如果故障已经发生，用引起异常的指令地址装载cs和eip寄存器，从而使这条指令能够再次被执行。
7. 在栈中保存eflags、cs以及eip的内容。
8. 如果异常产生了一个硬件出错码，则保存在栈中。
9. 装载cs和eip寄存器，其值分别是IDT表中的第i项门描述符的段选择符和偏移量，这些值给出了中断或者异常处理程序的第一条指令的逻辑地址（开始执行中断回调函数）。

中断返回

中断或异常被处理完毕后，相应的处理程序必须产生一条iret指令，把控制权转交给被中断的进程，这样控制单元就会产生以下操作：

1. 用保存在栈中的值装载cs、eip或eflags寄存器，如果一个硬件出错码曾被押入栈中，并且在eip内容上面，那么执行iret指令必须先弹出这个硬件出错码。
2. 检查处理程序的CPL是否等于cs中的最低两位的值，如果是，说明在同一特权级，iret中止执行，否则转入下一步。
3. 从栈中装载ss和esp寄存器，返回到与旧特权级相关的栈。
4. 检查ds、es、fs以及gs段寄存器的内容，如果其中一个寄存器包含的选择符是个段描述符，并且其DPL值小于CPL，那么就清除相应的段寄存器。