[PDF] Improving your Multilevel Feedback Queue with Wait Time Variance

View - Download Improving your Multilevel Feedback Queue with Wait Time Variance

Previous PDF

Next PDF

Improving your Multilevel Feedback Queue with Wait Time

Variance

Nathan Davis

Pennsylvania State University, Department of Electrical and Computer Science Pennsylvania State University, Department of Biomedical Engineering

Who needs to these instructions?

These instructions are intended for a programmer who has worked on an operating system or a process scheduler before. However, anyone familiar with standard C++, shell programming, and object oriented programming should be able to follow these instructions. Additionally, familiarity with summation notation will help. This tutorial follows the structure: create the required mathematical constructs, create schedulers, link the math to the schedulers.

Getting Started ~ <30 minutes

1. Make sure you have the following programs:

2. Download the sample scheduler with Git by running this command in your favorite shell.

git clone https://github.com/mchaker/cmpsc473p1/tree/NatesCreateProcess

Program a Rolling Wait Time Variance

Calculator ~ 1 hour

Wait time variance is the most important single

statistic of a schedulers performance. But calculating variance requires data from every process every time the process is scheduled. Infinite samples are impractical or impossible for a scheduler. So, you need a program to calculate a rolling wait time variance. You can create your own or use the provided program: ͞RollingVariance.hpp͟. Either way to continue using the tutorial, acquire or make a rolling variance program with the following public interface and formula. // a constructor

RollingVariance()

//access the computed variance double getVariance(); // add data to the rolling variance window and compute variance void updateVariance(int waiting_cycles);

C++ compiler C++ debugger Git

//compute wait time variance with the current window void updateVariance(); //Are there enough samples for the variance to have any meaning bool enoughSamples(); Create a Multidimensional Wait Time Variance Kernel (MDWTVK) ~ ͳ୦୭୳୰

1. Understand the multidimensional kernel

In statistics, a kernel is a probability distribution of a given result against one variable. This variable is called a dimension. This dimension is mapped onto a probability of a certain result. Equation 2 is the formula for calculating one dimension of a kernel. To combine dimensions, choose orthogonal (independent) variables and map them onto the probability of a result (wait time variance is the result). Do not worry about visualizing these many dimensions.

2. Apply Multidimensional Kernels to

Processes and Wait Time Variance

2.1 Pick Your Dimensions

Choose any information which can be retrieved from a process control block or via static analysis of the processes object code. For example, take the processes number of CPU registers from the process control block and the number of branches from the object code. When choosing dimensions, pick at least one fewer dimensions than the number of scheduling algorithms.

2.2 Program an Interface to your

MDWTVK

There is no provided interface to a

MDWTVK because the dimensions are

operating system specific and the number of dimensions depends on the number of scheduling algorithms. Fill in the functions of the following interfaces. These will be the glue between the scheduling algorithms and their processes. After you implement the interface you should be able to produce the graph such as the one shown in figure 1. h = smoothing factor (choose about 0.3) n = total number of samples //creates a kernel object with dimensional values of datatype overload all comparison //and arithmetic operators for datatype. For more than 1 dimension, datatype should be //a multidimensional container

KDE ();

//adds a value mapping process dimension to wait time variance result //this function should calculate the wait time variance for the added value void addValue(datatype sample); //gets the value and wait time variance of the minimum value in the kernel using the //KdeMin struct struct KdeMin {

RollingVariance var;

int dimensionAddress;

KdeMin getMin();

//resizes the number of values in the dimension by the percentage. This should //recalculate the wait time variance for the new values of the dimension void resizeDimension(double percent, uint8_t dimension); //plots the kernel for visual inspection void plot(); Create a Multilevel Feedback Queue ~ ʹ୦୭୳୰ୱ

1. Program Multiple Scheduling Algorithms

You can create as many scheduling algorithms as you want. However, the more you program the more effort you will need to put into your MDWTVK (via increasing the number of dimensions). A scheduling algorithm picks processes from a list and chooses which one will execute on the CPU. There are many

necessary considerations and desired outcomes. For the purpose of this tutorial, create two scheduling

algorithms: A first come first server scheduler which runs processes in the order they are created and a

shortest remaining time first scheduler which runs the shortest processes first. You can create these

schedulers on your own using the described interface or use the provided ͞scheduler.h" as an abstract

go(). //create a scheduler with the given policies using the given number of CPUs

Scheduler(enum Policy, int cpuCount);

//Begin running the scheduler void go() //Add a thread to the scheduler void createThread(Process process)

2. Link the schedulers using a feedback queue

A feedback queue allows movement of processes between multiple schedulers. When a criterion is

met, a process switches queues. Often this criterion is execution time, but picking optimal wait time

variance is a superior criterion. Implement the following interface to link the processes schedulers via an

abstract criterion (make this criterion wait time variance when you call the constructor). //Create a feeback queue using criterionType as the selector for choosing queues criterionType //must follow the implement the functions, getMin(), addValue(), and resizeDimension() from //the MDWTVK interface FeedbackQueue (enum Policies[], int cpuCount); //Call at a regular interval to move threads between queues by finding the kde with minimum //wait time variance at the processes dimensions void updateQueues(); //Adds a process to the default queue pushStartQueue(Process);

3. Piecing it Together

All the required interfaces are complete. Your scheduler can now be controlled by the wait time variance. You should be able to create a process using CreateThread and using a debugger, view the process move through different queues until it has finished executing.

Appendix

External Documentation

Git: http://rogerdudler.github.io/git-guide/

C++ Compilers and Debuggers

MinGW (Windows only): http://www.mingw.org/wiki

GCC (pretty much anything else): https://gcc.gnu.org/wiki Gdb: https://www.gnu.org/software/gdb/documentation/ Terms Object Code: http://stackoverflow.com/questions/466790/assembly-code-vs-machine-code-vs-object- code Process Control Block: https://en.wikipedia.org/wiki/Process_control_block

Schedulers (and info on the following):

First Come First Serve

Shortest Remaining Time First

Feedback Queue

Preemption

Kernel Density Estimate: https://en.wikipedia.org/wiki/Kernel_density_estimation Orthogonal: http://mathworld.wolfram.com/Orthogonal.htmlquotesdbs_dbs17.pdfusesText_23

[PDF] multilevel inverter block diagram

[PDF] multilevel inverter ppt

[PDF] multilevel inverter project report

[PDF] multilevel inverter switching pattern

[PDF] multilevel inverter thesis

[PDF] multilevel inverters syllabus

[PDF] multilevel queue scheduling

[PDF] multimedia powerpoint presentation examples

[PDF] multimedia presentation software examples

[PDF] multimedia presentations

[PDF] multinational company profile pdf

[PDF] multiple business names under one abn

[PDF] multiple choice questions about alcohol

[PDF] multiple choice questions in english language teaching

[PDF] multiple choice questions in probability and statistics with answers pdf