Scheduling is a term mentioned many times in the field of system programming. Here I post some study notes about scheduling approaches used in Distributed Computing system.

Basic Scheduling Approaches review

FIFO

FIFO, or first in first out, utilizes a queue to store the tasks that are waited to be completed based on the order of arrival.

Advantages: Simply priority scheduling using time order, easy to implement.

Disadvantages: Average completion time may be high due to Convoy effect .

STF

STF, or shortest task first, maintains a queue to store the task based on the running time of tasks in increasing order. It is a priority scheduling that uses user-provided priority.

Advantages: Average completion time is the shortest among all approaches.

Disadvantages: Starvation may occurs, meaning that if task with shorter time keeps coming, some longer time tasks will not be solved.

FIFO/STF are preferable for Batch applications.

Round Robin

Round robin also maintains a queue. It uses a quantum (a unit of time) to run portion of task in queue. It will pre-empty the tasks when a quantum expires and save their state for resuming later. After pre-empty, a task will be added to end of queue.

Advantages: Quick responses from system, no starvation.

Disadvantages: sensitive to the length of quantum

Hadoop Scheduling Approaches

Hadoop has two types of tasks: map, reduce. There are two popular types of schedulers in Hadoop: Capacity Scheduler, Fair Scheduler.

Hadoop Capacity Scheduler

This approach has multiple queues. Each queue guarantees some portion of the cluster capacity.

For jobs within same queue, FIFO typically used. Pre-emption is not allowed. Each queue can have limit (lower bound, upper bound) of the portion in cluster that it can guarantee.

Hadoop Fair Scheduler

In this approach, all jobs get equal share of resources. To do this, it divides cluster into pools (typically one per user). Resources are divided equally among pools. Within each pool, any scheduling approach can be used.

To ensure each pool is not perform too badly when there are lots of pools, there is a lower bound of percentage of cluster that pool is guaranteed.

When this minimum share is not met in a pool, it will take resources away from other pools by pre-empty jobs in other pools. It can do so because task can be restart if it is doing idempotent work. To kill, it picks the most-recently-started task to minimize waster work.

Concerns in using FIFO

As we know, FIFO may not be optimal in scheduling. However, it turns out that using STF here is also challenging since it is hard to estimate running time of task. My possible solution for this are；

1. Within a job: calculate by proportional size of task’s input
2. Across jobs: calculate by average of other tasks in that given job(weighted by input size).

Dominant-resource fair scheduling

New concept here!

In a single machine, resources are mostly processor and related. In previous parts, it’s about memory. But actually both need to be scheduled properly in cloud (a task may have multiple properties to be considered for scheduling. such as CPU, memory).

In general, it evaluates each task to see which property intensive (dominant resource) it is to schedule . For example，assume a cloud has total of 18 CPUs, 36 GB RAM.

For job 1, it consumes 2 CPUs, 8 GB RAM. Then $\frac{2}{18}$ < $\frac{8}{36}$ , therefore it is more RAM intensive than CPU-intensive.

For a given job, DRF ensures that the percentage of its dominant resource type that is gets cluster-wide, is the same for all jobs. For example,

Job 1 is RAM intensive with 8/36 percentage. And assume Job 2 consumes 6 CPUs, 2 GB RAM, with 6/18 > 2/36, so it is CPU-intensive. Then, job 1 with $\frac{8}{36}$, job 2 with $\frac{6}{18}$, we make it equal by assigning 3 tasks of job 1, and 2 tasks of job 2, given that $3 *\frac{8}{36}$ = $2 * \frac{6}{18}$ = $\frac{2}{3}$.