Completely Fair Scheduler
The Completely Fair Scheduler (CFS) is a process scheduler which was merged into the 2.6.23 (October 2007) release of the Linux kernel and is the default scheduler. It handles CPU resource allocation for executing processes, and aims to maximize overall CPU utilization while also maximizing interactive performance. Con Kolivas's work with scheduling, most significantly his implementation of "fair scheduling" named Rotating Staircase Deadline, inspired Ingo Molnรกr to develop his CFS, as a replacement for the earlier O(1) scheduler, crediting Kolivas in his announcement. In contrast to the previous O(1) scheduler used in older Linux 2.6 kernels, the CFS scheduler implementation is not based on run queues. Instead, a red–black tree implements a "timeline" of future task execution. Additionally, the scheduler uses nanosecond granularity accounting, the atomic units by which an individual process' share of the CPU was allocated (thus making redundant the previous notion of time slices). This precise knowledge also means that no specific heuristics are required to determine the interactivity of a process, for example. Like the old O(1) scheduler, CFS uses a concept called "sleeper fairness", which considers sleeping or waiting tasks equivalent to those on the run queue. This means that interactive tasks which spend most of their time waiting for user input or other events get a comparable share of CPU time when they need it.
Why does the Linux Completely Fair Scheduler use a red-black tree instead of the simpler array with queues?
1) The main advantage of Red-Black trees is that a single top-down pass may be used in both insertions and deletions.
2) Red–black trees offer worst-case guarantees for insertion time, deletion time, and search time.
3) Every path from root to leaf has same length. Every node has at most 2 children. If the maximum leaf nodes is reached, new items cause a shifting/rotation of the root to restore the path length.
4) If, say 16 was inserted, it would be placed as the right child of 7, same height as 2. Then if 18 was inserted, it would go on the right child of 16 and a reordering would take place to maintain the height. 16 would move up to where 19 is and 19 would move down to the left child of 25. So 16 would have 7 on the left and 18 on the right and the height (and search time) would be the same for all leaves.
5) The space needed for a the tree is O(n).
6) Search is in O(logn) time.
7) Insert is in O(logn) time.
8) Delete is in O(logn) time.
9) In parallel processing situations, the tree structure is easily (well easier than a stack) spliced off and on to separate threads or processor queues.
10) A new item is always inserted as a leaf in the tree. The tree itself will always be of log2n height so access to the node is fast and insertion and deletion required much less work. The tree needs much less reordering than and array would, and inserting a new leaf does not upset the rest of the tree until a reordering cycle is performed.
Description of the program:
There are set of processes and they don’t run/execute yet. CPU should give same power to all of these processes. When adding all of these processes to the RBT run time is zero. At the beginning user have to input some keys and two digit strings. Then run/execute the left most child of the RBT. It runs only time that comes when CPU power divided by the number of processes. Now delete this node from the RBT. Then add the time that runs until now to the vrun time.
And this moment process will start to run. It copying the string that given earlier to another string, letter by letter. In this process it copy first letter of the string. In next time it copy second letter. Like that it copy complete string to another string. Then it prints output on the screen when one letter has copied. It prints complete string when process completed.
After the adding vrun time to the earlier processed node it insert to the RBT again. Before the insertion it has to confirm whether the new vrun time is less than to the total runtime. If new vrun time greater than or equal to the total run time it means the process is already completed. Then it won’t insert to the tree again. After that this node insert in to the RBT. It is insert to the right side of the RBT. After the insertion left most child of the RBT has changed. Then again have to count the time that one process run.
And again run/execute the left most child of the new RBT. Again do the previous work steps. After all completed the program will terminate.
Assumptions:
1) At the beginning all vrun times of the processes are equal to zero.
2) In this program user act as the CPU and user give inputs to process time, number of nodes.
3) CPU power, total run time declared as a predefined variable.
The sample code is written in C++.
#include<iostream>
#include<string>
#include<sstream>
#include <bits/stdc++.h>
using namespace std;
struct node//create a struct to store data of rbt
{
int key;
node *parent;
node *left_child;
node *right_child;
char colour;
string name1;
string name2;
};
class tree//create a class
{
private:
node *root;
node *q;
public :
tree(){//default constructor
root=NULL;//set root as null
q=NULL;//set q as null
}
void insert();//insert data to the rbt
void insertion_fixing(node *);//fix the problems in balancing when insert
void left_rotate(node *);//do the left rotate
void right_rotate(node *);//do the right rotate
void delete_node();//delete a node from rbt
node* replacement(node *);//replace a node for another node
void deletion_fixing(node *);//fix the problems in balancing when delete
void display(node *);//display a node
void display_tree();//display the tree
int vrun_time();//get v run time
};
int tree::vrun_time(){//function to get v run time
int total_runtime=7;
int newvruntime=0;
int CPU_Power=2;
newvruntime=CPU_Power/2;
return newvruntime;
}
void tree::insert()//function to insert data to the rbt
{
int a;//initialize a veriable
vrun_time();
cout<<"Enter The Process To Be Inserted: "<<endl;//take user input
cin>>a;
node *p,*q;
node *temp=new node;//dynamic memory allocation
temp->key=a;//set the value of a to the key of temp
cout<<"Enter The Name of The Process To Be Inserted(Two Digit): "<<endl;
cin>>temp->name1;
temp->left_child=NULL;//set left child of temp to null
temp->right_child=NULL;//set right child of temp to null
temp->colour='r';//set colour of temp to red
p=root;
q=NULL;
if(root==NULL)//if root is null
{
root=temp;//set temp as the root
temp->parent=NULL;//set temp's parent as null
}
else
{
while(p!=NULL)
{
q=p;
if(p->key<temp->key){//if p's key is less than temp's key
p=p->right_child;//set p as p's right child
}else{
p=p->left_child;//else set p as p's left child
}
}
temp->parent=q;
if(q->key<temp->key){//if q's key is less than temp's key
q->right_child=temp;//set q's right child as temp
}else{
q->left_child=temp;//else q's left child as temp
}
}
insertion_fixing(temp);//call the function fix the problems in balancing when insert
}
void tree::insertion_fixing(node *temp){//insertion fixing function
if(root==temp)//if temp is the root node
{
temp->colour='b';//set temp's colour to black
return;
}
if (temp->parent != NULL && temp->parent->parent != NULL){
while (temp != NULL && temp->parent != NULL && temp->parent->parent != NULL && !temp->parent->colour == 'b'){// as long as color is not black
if(temp->parent == temp->parent->parent->left_child){
node *y = temp->parent->parent->right_child;
if (y!= NULL && y->colour == 'r'){
temp->parent->colour = 'b';
y->colour = 'b';
temp->parent->parent->colour = 'r';
temp = temp->parent->parent;
}else if (temp == temp->parent->right_child){
temp = temp->parent;
left_rotate(temp);
}
temp->parent->colour = 'b';
temp->parent->parent->colour = 'r';
right_rotate(temp->parent->parent);
}
else{
node *y = temp->parent->parent->left_child; // left instead of right
if (y != NULL && y->colour == 'r'){ // is red
temp->parent->colour = 'b'; // color = black
y->colour = 'b'; // color = black
temp->parent->parent->colour = 'r'; // color = red
temp = temp->parent->parent;
}
else{
if (temp == temp->parent->left_child){ // left instead of right
temp = temp->parent;
right_rotate(temp);
}
temp->parent->colour = 'b'; // color is black
temp->parent->parent->colour = 'r'; // color is red
left_rotate(temp->parent->parent);
}
}
}
}
}
void tree::delete_node()//function to delete a node from rbt
{
if(root==NULL)//if root is null
{
cout<<"Tree is Empty"<<endl;//print tree is empty
return;
}
int a;//initialize a int variable
cout<<"Enter The Value of The Node(left most child) To Be Deleted: "<<endl;//get user input to delete the node
cin>>a;
node *p;
p=root;//set p as the root
node *g=NULL;
node *q=NULL;
int flag=0;//initialize a int flag variable
while(p!=NULL&&flag==0)//loop
{
if(p->key==a){//if p's key equal to a value
flag=1;}//set flag as 1
if(flag==0)//if flag is 0
{
if(p->key<a){//if p's key less than a
p=p->right_child;//set p as p's right child
}else{
p=p->left_child;//set p as p's left child
}
}
}
if(flag==0)//if flag is 0
{
cout<<"Can't Find The Key"<<endl;//print the message
return;
}
else
{
cout<<"Key Deleted Successfully: "<<p->key<<endl;//delete the paticular node
cout<<"Colour: ";
if(p->colour=='b'){//if p's colour is black
cout<<"Black"<<endl;//print black
}
else{
cout<<"Red"<<endl;//print red
}
if(p->parent!=NULL){//if p's parent is not equal to null
cout<<"Parent: "<<p->parent->key<<endl;
}
else{
cout<<"There is no parent of the node"<<endl;
}
if(p->right_child!=NULL){
cout<<"Right Child: "<<p->right_child->key<<endl;
}
else{
cout<<"There is no right child of the node/(NIL Node)"<<endl;
}
if(p->left_child!=NULL){
cout<<"Left Child: "<<p->left_child->key<<endl;
cout<<" "<<endl;
}
else{
cout<<"There is no left child of the node/(NIL Node)"<<endl;
}
cout<<"Node Deleted Successfully"<<endl;
if(p->left_child==NULL||p->right_child==NULL){
g=p;
}
else{
g=replacement(p);//call the function replacement
}
if(g->left_child!=NULL){
q=g->left_child;//set q as g's left child
}
else
{
if(g->right_child!=NULL){
q=g->right_child;//set q as g's right child
}
else{
q=NULL;//set q as null
}
}
if(q!=NULL){
q->parent=g->parent;//set q's parent as g's parent
}
if(g->parent==NULL&&q!= NULL){
root=q;//set root as q
}
else
{
if(g==g->parent->left_child){
g->parent->left_child=q;//set g's parent's left child as q
}
else{
g->parent->right_child=q;//set g's parent's right child as q
}
}
if(g!=p)
{
p->colour=g->colour;//set p's colour as g's colour
p->key=g->key;//set p's key as g's key
}
if(g->colour=='b'&& q != NULL){
deletion_fixing(q);//call the function fix the problems in balancing when delete
}
}
int b;
char array[2];
b=vrun_time();
int total_runtime=7;
if(total_runtime>b+a){
cout<<" Insert : "<<b+a<<" to The Tree "<<endl;
strcpy(array, p->parent->name1.c_str());
p->parent->name2=array[(b+a)-5];
cout<<" Copied Name from Name1: "<<p->parent->name2<<endl;
}
else{
cout<<"Process is Completed Successfully"<<endl;
}
}
void tree::deletion_fixing(node *p)//function to fix the problems in balancing when delet
{
node *e;//create node called e
while(p!=root&&p->colour=='b')
{
if(p->parent->left_child==p)
{
e=p->parent->right_child;//set e as p's parent's right child
if(e->colour=='r')
{
e->colour='b';//set e's colour as black
p->parent->colour='r';//set p's parent's colour as red
left_rotate(p->parent);//call left rotate function
e=p->parent->right_child;//set e as p's parent's right child
}
if(e->right_child->colour=='b'&&e->left_child->colour=='b')
{
e->colour='r';//set e's colour as red
p=p->parent;
}
else
{
if(e->right_child->colour=='b')
{
e->left_child->colour=='b';//set e's left child's colour as black
e->colour='r';
right_rotate(e);//call right rotate function
e=p->parent->right_child;
}
e->colour=p->parent->colour;
p->parent->colour='b';
e->right_child->colour='b';
left_rotate(p->parent);//call left rotate funtion
p=root;
}
}
else
{
e=p->parent->left_child;//set e as p's parent's left child
if(e->colour=='r')
{
e->colour='b';//set e's colour as black
p->parent->colour='r';
right_rotate(p->parent);//call right rotate function
e=p->parent->left_child;
}
if(e->left_child->colour=='b'&&e->right_child->colour=='b')
{
e->colour='r';//e's colour as red
p=p->parent;
}
else
{
if(e->left_child->colour=='b')
{
e->right_child->colour='b';//set e's right child's colour as black
e->colour='r';
left_rotate(e);//call left rotate function
e=p->parent->left_child;
}
e->colour=p->parent->colour;//set e's colour as p's parent's colour
p->parent->colour='b';
e->left_child->colour='b';
right_rotate(p->parent);//call right rotate function
p=root;//set p as root
}
}
p->colour='b';//set p's colour as black
root->colour='b';//set root's colour as black
}
}
void tree::left_rotate(node *p)//left rotate function
{
if(p->right_child==NULL){
return ;
}
else
{
node *g=p->right_child;
if(g->left_child!=NULL)
{
p->right_child=g->left_child;
g->left_child->parent=p;
}
else{
p->right_child=NULL;
}
if(p->parent!=NULL){
g->parent=p->parent;
}
if(p->parent==NULL){
root=g;
}
else
{
if(p==p->parent->left_child){
p->parent->left_child=g;
}
else{
p->parent->right_child=g;
}
}
g->left_child=p;
p->parent=g;
}
}
void tree::right_rotate(node *p)//right rotate function
{
if(p->left_child==NULL){
return ;
}
else
{
node *g=p->left_child;
if(g->right_child!=NULL)
{
p->left_child=g->right_child;
g->right_child->parent=p;
}
else{
p->left_child=NULL;
}
if(p->parent!=NULL){
g->parent=p->parent;
}
if(p->parent==NULL){
root=g;
}
else
{
if(p==p->parent->left_child){
p->parent->left_child=g;
}
else{
p->parent->right_child=g;
}
}
g->right_child=p;
p->parent=g;
}
}
node* tree::replacement(node *p)//replace a node for another node funtion
{
node *g=NULL;
if(p->left_child!=NULL)
{
g=p->left_child;
while(g->right_child!=NULL){
g=g->right_child;
}
}
else
{
g=p->right_child;
while(g->left_child!=NULL){
g=g->left_child;
}
}
return g;
}
void tree::display(node *p)//display node funtion
{
if(root==NULL)
{
cout<<"Empty Tree"<<endl;
return ;
}
if(p!=NULL)
{
cout<<"Key: "<<p->key<<endl;
cout<<"Colour: ";
if(p->colour=='b'){
cout<<"Black"<<endl;
}
else{
cout<<"Red"<<endl;
}
if(p->parent!=NULL){
cout<<"Parent: "<<p->parent->key<<endl;
}
else{
cout<<"There is no parent of this node/(This is the root node)"<<endl;
}
if(p->right_child!=NULL){
cout<<"Right Child: "<<p->right_child->key<<endl;
}
else{
cout<<"There is no right child of this node/(NIL Node)"<<endl;
}
if(p->left_child!=NULL){
cout<<"Left Child: "<<p->left_child->key<<endl;
cout<<" "<<endl;
}
else{
cout<<"There is no left child of this node/(NIL Node)"<<endl;
cout<<endl;
}
if(p->left_child)
{
cout<<"Left Child: "<<endl;
display(p->left_child);
}
if(p->right_child)
{
cout<<"Right Child: "<<endl;
display(p->right_child);
}
}
}
void tree::display_tree()//function to display the rbt
{
display(root);
}
int main()
{
int a;
tree object;//create a object for the tree class
while(1){
cout<<"***COMPLETELY FAIR SCHEDULER IMPLIMENTATION USING RED BLACK TREE***"<<endl;//get user inputs
cout<<" "<<endl;
cout<<"1) Insert processes in to the tree"<<endl;
cout<<"2) Delete a process(left most child) from the tree"<<endl;
cout<<"3) Display the processes of the tree"<<endl;
cout<<"4) Exit"<<endl ;
cout<<" "<<endl;
cout<<"Enter Your Choice: "<<endl;
cin>>a;
switch(a)
{
case 1 : object.insert();
break;
case 2 : object.delete_node();
break;
case 3 : object.display_tree();
break;
case 4 : exit(1);
break;
default : cout<<"Invalid Choice"<<endl;
}
}
return 0;
}
Comments
Post a Comment