整体架构
DAGScheduler：负责分析用户提交的应用，并根据计算任务的依赖关系建立DAG，且将DAG划分为不同的Stage，每个Stage可并发执行一组task。注：DAG在不同的资源管理框架实现是一样的。
TaskScheduler：DAGScheduler将划分完成的Task提交到TaskScheduler，TaskScheduler通过Cluster Manager在集群中的某个Worker的Executor上启动任务，实现类TaskSchedulerImpl。
Scheduler的实现概述
1）org.apache.spark.scheduler.DAGScheduler
2）org.apache.spark.scheduler.SchedulerBackend
3）org.apache.spark.scheduler.TaskScheduler
SchedulerBackend是一个trait，作用是分配当前可用的资源，即为Task分配计算资源（Executor），并在分配的Executor上启动Task。
TaskScheduler也是一个trait，它的作用是从DAGScheduler接收不同的Stage的任务，并且向集群提交这些任务（并为执行特别慢的任务启动备份任务）。TaskScheduler是实现多种任务调度器的基础，而org.apache.spark.scheduler.TaskSchedulerImpl是唯一实现。TaskSchedulerImpl在以下几种场景下调用org.apache.spark.scheduler.SchedulerBackend#reviveOffers：
1）有新任务提交时
2）有任务执行失败时
3）计算节点（即Executor）不可用时
4）某些任务执行过慢而需要重新分配资源时
每个SchedulerBackend都会对应个唯一的TaskScheduler
DAGScheduler
DAGScheduler将应用的DAG划分成不同的Stage，每个Stage由并发执行的一组Task构成，Task的执行逻辑完全相同，只是作用于不同数据。
DAGScheduler的创建
TaskScheduler和DAGScheduler在SparkContext创建时创建。
TaskScheduler通过org.apache.spark.SparkContext#createTaskScheduler创建。
// Create and start the scheduler
val(sched,ts) = SparkContext.createTaskScheduler(this,master)
DAGScheduler通过直接调用其构造函数创建，同时DAGScheduler保存了TaskScheduler的引用，因此需要在TaskScheduler创建后创建
def this(sc: SparkContext) = this(sc,sc.taskScheduler)
MapOutputTrackerMaster：运行在Driver管理Shuffle Map Task输出，下游的Task通过MapOutputTrackerMaster获取Shuffle输出的位置信息。
BlockManagerMaster：也是运行在Driver端，管理整个Job的Block信息。
DAGScheduler除了初始化用于保存集群状态信息的数据结构，还会创建一个Actor，用于处理各种信息。
Job提交
以RDD的action count为例：
1）org.apache.spark.rdd.RDD#count
2）org.apache.spark.SparkContext#runJob
3）org.apache.spark.scheduler.DAGScheduler#runJob
submitJob首先为Job生成一个Job ID，并且生成一个JobWaiter的实例监听Job的执行情况
Job由多个Task组成，只有所有Task都成功完成，Job才标记为成功。若失败，则通过jobFailed方法处理。
4）org.apache.spark.scheduler.DAGScheduler#submitJob
5）org.apache.spark.util.EventLoop#post
当eventProcessLoop对象投递了JobSubmitted事件之后，对象内的eventThread线程实例对事件进行处理，不断从事件队列中取出事件，调用onReceive函数处理事件，当匹配到JobSubmitted事件后，调用DAGScheduler的handleJobSubmitted函数并传入jobid、rdd等参数来处理Job。
DAGScheduler::submitJob会创建JobSummitted的event发送给内嵌类eventProcessActor（在源码1.4中，submitJob函数中，使用DAGSchedulerEventProcessLoop类进行事件的处理）
6）org.apache.spark.scheduler.DAGScheduler#handleJobSubmitted
Stage的划分
1、划分依据
宽依赖：需要Shuffle，Spark根据宽依赖将Job划分不同的Stage
窄依赖：RDD的每个Partition依赖固定数量的parent RDD的Partition，可以通过一个Task并行处理这些相互独立的Partition
2、划分过程
Stage的划分是从最后一个RDD开始，RDD会从SparkContext的runJob开始，通过以下调用栈对Stage划分：
1）org.apache.spark.SparkContext#runJob
2）org.apache.spark.scheduler.DAGScheduler#runJob
3）org.apache.spark.scheduler.DAGScheduler#submitJob
4）org.apache.spark.util.EventLoop#post
5）org.apache.spark.scheduler.DAGScheduler#handleJobSubmitted
handleJobSubmitted开始Stage的划分
newResultStage首先会获取当前Stage的Parent Stages，然后创建当前的Stage。
调用getParentStages，把父Stage创建出来，然后根据它们创建当前Stage。
getParentStages是划分Stage的核心实现，每遇到一个ShuffleDependency就会生一个parent Stage。
376：存储parent stage
377：存储已经被访问的RDD
380：存储需要被处理的RDD，Stack中的RDD都需要被处理
381：广度优先遍历RDD生成的依赖树
386：逐个处理当前RDD依赖的parent RDD
389：在依赖是ShuffleDependency时生成新的stage
391：不是ShuffleDependency，则属于同一个stage
396：以输入的rdd作为第一个需要处理的RDD，然后从该RDD开始，顺序处理其parent rdd
397：如果stack非空，则一直处理
398：每次visit如果遇到了ShuffleDependency，那么就会形成一个stage，否则这些RDD属于同一个stage
280~281：根据suffleId是否存在
282：如果创建则直接返回
285：注册该stage的Shuffle依赖，如果Stage的Parent Stage是否已经生成，没有则生成它们
289：生成当前RDD的Stage
354~355：Stage已经被计算过则从newShuffleMapStage中获取计算结果
359：计算结果复制到stage中
366：向mapOutputTracker注册该Stage
ShuffleMapTask的计算结果通过Driver端的mapOutputTracker，其他Task可以从中获取结果。mapOutputTracker.registerShuffle实现了这些元数据的占位，ShuffleMapTask通过registerMapOutputs保存这些计算结果（数据位置、大小等元数据）。
任务生成
handleJobSubmitted调用handleJobSubmitted提交Stage。所有parent Stage都计算完成，才能提交。
submitMissingTasks(stage,jobId.get)：如果所有parent stage已经完成，则提交stage所包含的task
submitStage(parent)：有parent stage未完成，则递归提交
abortStage：无效stage，直接停止
org.apache.spark.scheduler.DAGScheduler#submitMissingTasks完成DAGScheduler最后的工作，向TaskScheduler提交Task。
1、获取需要计算的Partition：最后的Stage判断RusultTask是否已经结束
2、对于其他Stage，对应的Task是ShuffleMapTask
DAGScheduler完成任务提交后，在判断哪些Partition需要计算，就会为Partition生成Task，然后封装成TaskSet，提交至TaskScheduler。等待TaskScheduler最终向集群提交这些Task，监听这些Task的状态。
