Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

The Performance of Multilevel Feedback Queues

DZone's Guide to

The Performance of Multilevel Feedback Queues

Learn how the multilevel feedback queue works and how it boosts performance by giving preferential treatment to shorter tasks.

· Performance Zone ·
Free Resource

xMatters delivers integration-driven collaboration that relays data between systems, while engaging the right people to proactively resolve issues. Read the Monitoring in a Connected Enterprise whitepaper and learn about 3 tools for resolving incidents quickly.

In this blog, I will discuss the performance characteristics of the Multilevel Feedback queue, which is a scheduling policy that gives preferential treatment to short jobs. This policy is also called multi-level time sharing policy (MLTP). Several OS schedulers use multilevel feedback queues for scheduling jobs and it allows a process to move between queues. One of the main advantages of using this policy is that it can speed up the flow of small tasks. This can result in overall performance improvements when the service time distribution of tasks follow long-tailed distributions (note: long-tailed distributions are explained in detail later in this article).

The following figure illustrates the model:

Model

The basic functionality of the multilevel time sharing scheduling policy considered in this article is as follows.

Each new task that arrives at the system is placed in the lowest queue, where the task is served in a First-Come-First-Serviced (FCFS) manner until it receives a maximum of q1 amount of service (note: q1 represents a time duration).

If the service time of the task is less than or equal to q1, the task departs system (after receiving a maximum of q1 amount of service). Otherwise, the task is placed in Queue 2, where the task is processed in a FCFS manner until it receives, at most, q2 amount of service, and so on.

The task propagates through the system of queues until the total processing time the task has so far received is equal to its service time, at which point it leaves the system.

A task waiting to be served in Queue 1 has the priority of service over tasks that are waiting to be served in Queue 1 + 1, 1 + 2,…,N, where N denotes number of levels. However, a task currently being processed is not preempted upon the arrival of a new task to the system.

Two Variants

In this article, I will consider the following two models:

Multilevel optimal quantum timesharing policy with N levels (N-MLTP-O): The quanta (q1, q2, …, qn) for N-MLTP-O are computed to optimize overall expected waiting time.

Multilevel equal quantum timesharing policy with N levels (N-MLTP-E): The quanta for N-MLTP-E are equal on each level, i.e. , q1 =q2=q3=…=qn.

Long-Tailed Distributions

In his paper, L. E. Schrage derived an expected waiting time for the multilevel time sharing policy under general service time distribution when the task arrivals follow the Poisson process. We used this result in our previous work to study the performance of the multilevel time sharing policy under long-tailed service time distributions. We have specifically considered long-tailed service time distributions since there is evidence that shows service times of certain computing work loads closely follow such distributions. In such distributions:

  1. There is a very high probability that the size of a task being very small (short) and the probability that a size of a task being very large (long) is very small. This results in a service time distribution that has a very high variance.
  2. Although the probability of a very large task appearing is very small, the load imposed on the system by these (very small number of) large tasks can be as high as 50% of the system load.
  3. When service time distribution exhibits very high variance, several small tasks can get behind a very large task. This results in significant performance degradations, particularly if the tasks are processed in a FCFS manner until completion

In particular, we looked at the performance of the multilevel time sharing policy under the Pareto Distribution (one of the commonly appearing long-tailed distributions) and investigated how the variability of service time affected the performance of the multilevel timesharing policy under different system loads. The probability density function of Pareto Distribution is given by

where 2 > α > 0. αrepresents the variability of task service times. The value of α depends on the type of tasks. For example, Unix process CPU requirements have an α value of 1.0. The lower the value of alpha, the higher the variability of service times.

The Behavior of Overall Expected Waiting Time (or Overall Average Waiting Time)

The following figures show the overall expected waiting time and factor of improvement in the expected waiting time in MLTP over FCFS.

In Figure 1:

Y axis: E[W]- Overall expected waiting time (or overall average waiting time) of a task which enters the system (unit: time unit).

X axis: α: Represents the variability of task service times (refer to the previous section). The lower the value of alpha the higher variability of service times.

In Figure 2:

Y axis: The factor of improvement in MLTP over FCFS.

X axis: α: Represents the variability of task service times (refer to the previous section). The lower the value of alpha the higher variability of service times.

The behaviour of overall average expected waiting time

The factor of improvement in MLTP over FCFS

First, let's have a look at the performance of 2-MLTP-O, 2-MLTP-E, and FCFS.

We note from Figure 1, 2-MLTP-O outperforms both 2-MLTP-E and FCFS under all the scenarios considered. For example, under a system load of 0.7, when α = 0.4, 2-MLTP-O outperforms FCFS and 2-MLTP-E by factors of 3 and 2 respectively.

Under the same system load, when α is equal to 1.1, 2-MLTP-O outperforms FCFS and 2-MLTP-E by factors of 2 and 1.5 respectively. We note that the factor of improvement is highly significant when both the system load and the task size variability are high (i.e. low α).

On the other hand, if both the system load and task size variability are low (i.e. high α), then the factor of improvement is not highly significant.

Also, notice that as you increase the number of levels we get an improvement in the performance. For example, under a system load of 0.7, when α is equal to 0.4, 3-MLTP-O performs 1.6 times better than 2-MLTP-O.

The Impact Numbers of Levels

The following figure plots the expected waiting versus number of levels (N) for some selected α values and system loads. Note that in these plots, x and y axes are in log (base10) scale.

In the figure below:

E[W]: Overall expected waiting time (or overall average waiting time) of a task which enters the system (unit: time unit).

N: Number of queues/levels

α: Represents the variability of task service times (refer to the previous section). The lower the value of alpha, the higher variability of service times.

The impact of numbers of levels on E[W]

One of the main observations is when the variability of service times are very high, then we can get significant improvement in the average waiting time by increasing the number of levels.

Conclusion

In this blog, we had a look at the performance of multi-level feedback queue scheduling policy (also called multi-level time sharing policy) with a finite number of queues. We compared the performance of the multilevel time sharing policy with the FCFS under two scenarios: (1) quanta of multilevel time sharing policy computed to optimize the expected waiting time (MLTP-O), and (2) quanta are equal on each level (MLTP-E). We noticed that if the variability of service times are high, we can get significant improvements by using MLTP-O. We noticed that both MLTP-O and MLTP-E outperform FCFS significantly, in particular when the variability of service times are high. If the variability of service times is low, then there are no significant differences in the performance. 

Discovering, responding to, and resolving incidents is a complex endeavor. Read this narrative to learn how you can do it quickly and effectively by connecting AppDynamics, Moogsoft and xMatters to create a monitoring toolchain.

Topics:
low latency ,scheduling ,operating systems ,performance ,queues

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}