Scheduler-I

A. First Edition

This is just for fun. You know, in DBMS you can find almost everything in OS. Scheduler is one of them. Actually

I want to implement a small simulation of transaction-control algorithm in DBMS which uses time-stamp of 

transactions and database elements. But starting this environment takes me a whole day. 

B.The problem

There is a big common thing between task pool and transaction pool---they can both be implemented as a kind of

special queue. Therefore, I defined a template queue.

Then I plan to write scheduler whose scheduling scheme would most probably round-robin. 

Probably many people would find difficult in understanding the purpose of many functions. Actually almost every

time I try to write some program, it is like an adventure for me in C++. This time, I found I don't need to

stick to the idea of class. Instead, struct and class are basically same thing in defining member functions

except in struct all are all public, and in class all are private, by default.

D.The major functions

E.Further improvement

F.File listing

1. scheduler.h

2. scheduler.cpp

1. main.cpp

file name: scheduler.h

const int MaxTaskCount=10;
const int MaxTransCount=10;
const int MaxElementCount=4;
const int MaxTaskItemCount=200;

enum TaskType
{
	Read, Write, Commit, Abort
};

struct Element
{
	int ID;
	int readStamp;
	int writeStamp;
	bool committed;
	void display();
};	

struct Task
{
	int element;
	TaskType taskType;
	void display();
};

struct Transaction
{
	int timeStamp;
	int count;
	int current;
	Task tasks[MaxTaskCount];
	void moveNext(int& index);
	bool haveNext();
	Task* operator[](int index){return tasks+index;}
	void display();
};


	
template<class T, int MaxListLength>
class Queue
{
protected:
	T list[MaxListLength];
	int count;
	int front, back, current;
public:
	Queue();
	inline int getCount(){return count;}
	bool enqueue(T*& outPtr);
	bool dequeue(T*& outPtr);
	T* next();
	void display();
	T* operator[](int index);
	void remove(int index);
};

struct TaskItem
{
	int transID;
	int taskIndex;
	void display();
};

class TransPool
{
private:
	Queue<Transaction, MaxTransCount> list;
public:
	TransPool();
	void createTrans(int timeStamp);
	Transaction* next();
	void destroyTrans();
	void display(){ list.display();}
};
	
class TaskPool
{
private:
	Queue<TaskItem, MaxTaskItemCount> list;
public:
	void addItem(Transaction* transPtr);
	void update(int transID);//put status on
	void display(){ list.display();}
};

class Scheduler
{
private:
	int timeStamp;
	TransPool transPool;
	TaskPool taskPool;

	void createTrans();
	void tickTimer();
	void execTask();
	void addTask();
	void destroyTrans();
	void showStatus();
public:
	void display();
	void doJob(int step);
	Scheduler();
};

template<class T, int MaxListLength>
void Queue<T, MaxListLength>::display()
{
	for (int i=0; i<count; i++)
	{
		list[(back+i)%MaxListLength].display();
	}
}


template<class T, int MaxListLength>
void Queue<T, MaxListLength>::remove(int index)
{	
	if (index<count)
	{
		for (int i=index; i<count-1; i++)
		{
			this->operator[](i)->operator=(*(this->operator[](i+1)));
			count--;
			if (current==front)
			{
				current=(back+count-1)%MaxListLength;
			}
			//else current doesn't matter
			front=(back+count-1)%MaxListLength;//different module
		}
	}
}


template<class T, int MaxListLength>
T* Queue<T, MaxListLength>::operator [](int index)
{
	if (index<count)
	{
		return list+(back+index)%count;
	}
	else
	{
		return NULL;
	}
}

template<class T, int MaxListLength>
Queue<T, MaxListLength>::Queue()
{
	front=back=current=count=0;
}

template<class T, int MaxListLength>
bool Queue<T, MaxListLength>::enqueue(T*& outPtr)
{
	if (count+1<MaxListLength)
	{
		count++;
		outPtr=list+front;//return first
		front=(front+1)%MaxListLength;		
		return true;
	}
	else
	{
		return false;
	}
}

template<class T, int MaxListLength>
bool Queue<T, MaxListLength>::dequeue(T*& outPtr)
{
	if (count>0)
	{
		count--;
		outPtr=list+back;
		if (current==back)
		{
			back=(back+1)%MaxListLength;
		}
		back=(back+1)%MaxListLength;
		return true;
	}
	else
	{
		return false;
	}
}

template<class T, int MaxListLength>
T* Queue<T, MaxListLength>::next()
{	
	if (count==0)
	{
		return NULL;
	}
	if (current==front)
	{
		current=back;
	}
	return list+current;
}

file name: scheduler.cpp

#include <stdio.h>
#include <stdlib.h>
#include "scheduler.h"

const int ScheduleTaskNumber=3;

char* typeString[]=
{
	"Read", "Write", "Commit", "Abort"
};

Scheduler::Scheduler()
{
	timeStamp=0;
}

void Scheduler::doJob(int step)
{
	for (int i=0; i<step; i++)
	{
		tickTimer();
		switch(rand()%ScheduleTaskNumber)
		{
		case 0:
			transPool.createTrans(timeStamp);
			break;
		case 1:
			addTask();
			break;
		case 2:
			execTask();
			break;
		}
		showStatus();
	}
}

void Scheduler::addTask()
{
	Transaction* ptr;
	if ((ptr=transPool.next())!=NULL)
	{
		taskPool.addItem(ptr);
	}
}

void Scheduler::showStatus()
{
	printf("time is %d;\n*****************************\n", timeStamp);
	printf("transaction pool is:\n");
	transPool.display();
	printf("task pool is:\n");
	taskPool.display();
}

void Scheduler::display()
{
	showStatus();
}



void Scheduler::tickTimer()
{
	timeStamp++;
}

void Scheduler::execTask()
{
	taskPool.display();
}

void TaskPool::update(int transID)
{
	TaskItem* ptr;
	for (int i=0; i<list.getCount(); i++)
	{
		ptr=list.next();
		if (ptr!=NULL)
		{
			//if (ptr->ti
		}
	}
}

void TaskPool::addItem(Transaction* transPtr)
{
	TaskItem* ptr;
	int index;
	if (!transPtr->haveNext())
	{
		return;
	}
	if (list.enqueue(ptr))
	{
		ptr->transID=transPtr->timeStamp;
		transPtr->moveNext(index);
		ptr->taskIndex=index;
	}
}

void Element::display()
{
	printf("Element ID=%d; read stamp=%d; write stamp=%d; committed=%c\n",
		ID, readStamp, writeStamp, committed?'T':'F');
}

bool Transaction::haveNext()
{
	return current+1<count;
}

void Transaction::moveNext(int& index)
{
	index=current;
	current++;
}



void Task::display()
{
	printf("Task element=%c, type=%s\n", element+'A', typeString[taskType]);
}

void Transaction::display()
{
	printf("Transaction timestamp=%d; count=%d; current=%d;\n", timeStamp,
		count, current);
	for (int i=0; i<count; i++)
	{
		tasks[i].display();
	}
}

void TaskItem::display()
{
	printf("Task item: transaction time stamp=%d; task index=%d\n", transID, taskIndex);
}

TransPool::TransPool()
{

}

void TransPool::createTrans(int timeStamp)
{
	Transaction* ptr;
	if (list.enqueue(ptr))
	{
		ptr->timeStamp=	timeStamp;
		ptr->count=rand()%MaxTaskCount+1;
		for (int i=0; i<ptr->count; i++)
		{
			ptr->tasks[i].taskType=rand()%2==0?Read:Write;
			ptr->tasks[i].element=rand()%MaxElementCount;			
		}
		ptr->current=0;	
		
	}
	//else do nothing
}


void TransPool::destroyTrans()
{
	Transaction* ptr;
	if (list.dequeue(ptr))
	{
		printf("transaction with timestamp of %d destroyed\n", ptr->timeStamp);
	}
}

Transaction* TransPool::next()
{
	return list.next();
}

file name: main.cpp

#include "scheduler.h"



int main()
{
	Scheduler S;
	S.doJob(10);
	return 0;
}

How to run?

1.This is just a startup of environment. So, I just implement the display function for debugging.

time is 1;
*****************************
transaction pool is:
task pool is:
time is 2;
*****************************
transaction pool is:
task pool is:
time is 3;
*****************************
transaction pool is:
task pool is:
time is 4;
*****************************
transaction pool is:
task pool is:
time is 5;
*****************************
transaction pool is:
task pool is:
time is 6;
*****************************
transaction pool is:
task pool is:
time is 7;
*****************************
transaction pool is:
Transaction timestamp=7; count=9; current=0;
Task element=A, type=Read
Task element=B, type=Write
Task element=D, type=Write
Task element=D, type=Write
Task element=C, type=Write
Task element=A, type=Write
Task element=A, type=Write
Task element=B, type=Read
Task element=C, type=Read
task pool is:
time is 8;
*****************************
transaction pool is:
Transaction timestamp=7; count=9; current=0;
Task element=A, type=Read
Task element=B, type=Write
Task element=D, type=Write
Task element=D, type=Write
Task element=C, type=Write
Task element=A, type=Write
Task element=A, type=Write
Task element=B, type=Read
Task element=C, type=Read
Transaction timestamp=8; count=7; current=0;
Task element=D, type=Read
Task element=C, type=Write
Task element=C, type=Write
Task element=A, type=Write
Task element=D, type=Write
Task element=C, type=Write
Task element=D, type=Write
task pool is:
time is 9;
*****************************
transaction pool is:
Transaction timestamp=7; count=9; current=0;
Task element=A, type=Read
Task element=B, type=Write
Task element=D, type=Write
Task element=D, type=Write
Task element=C, type=Write
Task element=A, type=Write
Task element=A, type=Write
Task element=B, type=Read
Task element=C, type=Read
Transaction timestamp=8; count=7; current=0;
Task element=D, type=Read
Task element=C, type=Write
Task element=C, type=Write
Task element=A, type=Write
Task element=D, type=Write
Task element=C, type=Write
Task element=D, type=Write
task pool is:
time is 10;
*****************************
transaction pool is:
Transaction timestamp=7; count=9; current=0;
Task element=A, type=Read
Task element=B, type=Write
Task element=D, type=Write
Task element=D, type=Write
Task element=C, type=Write
Task element=A, type=Write
Task element=A, type=Write
Task element=B, type=Read
Task element=C, type=Read
Transaction timestamp=8; count=7; current=0;
Task element=D, type=Read
Task element=C, type=Write
Task element=C, type=Write
Task element=A, type=Write
Task element=D, type=Write
Task element=C, type=Write
Task element=D, type=Write
Transaction timestamp=10; count=4; current=0;
Task element=B, type=Read
Task element=B, type=Write
Task element=D, type=Read
Task element=C, type=Read
task pool is:
Press any key to continue