Scheduler-II
A. Second 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.
And it is not only for fun, as I found a small problem in the rule of textbook. Even though it seems trivial, but
as a protocol, it will cause deadlock which I consider to be big mistake in sense of protocol!!!
to simulate timestamp first. Then we have first to define what is a transaction. After that you
need to define what is a task.
I changed my idea of "taskitem" which becomes little use now. Since I am aiming to implement Round-
Robin, there is no need for me to record this "TaskItem".
C.The idea of programThere 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.
I implement "abort" by recording previous timestamp and committed status in each "Task" structure.
E.Further improvement
F.File listing
1. scheduler.h
2. scheduler.cpp
1. main.cpp
file name: scheduler.h
#include <stdio.h> const int MaxTaskCount=6; const int MaxTransCount=4; const int MaxElementCount=4; const int MaxTaskItemCount=300; //forward declaration class Scheduler; enum TaskType { Read, Write, Commit, Abort }; //this is database elements struct Element { int ID;//should be same as index int readStamp; int writeStamp; bool committed; void display(); }; //read or write struct Task { int element;//the index of element TaskType taskType; int prevStamp; bool prevCommitted; 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;} Transaction& operator=(Transaction& other); void display(); }; //a universal queue, because I find transpool, and taskpool is //similar in someway, I can let them both inherit from a //common ancester, but template is another choice. template<class T, int MaxListLength> class Queue { friend class Scheduler; protected: T list[MaxListLength]; int count; int front, back, current; public: Queue(); inline int getCount(){return count;} bool enqueue(T*& outPtr);//add at front+1 bool dequeue(T*& outPtr);//remove from back T* next(); void display(); //passing a compare function pointer int search(bool (*compare)(T* left, T* right), T* key); int find(T* item); T* operator[](int index); void remove(int index);//remove the indexed, and shift array }; //it is difficult to remove by returning pointers, instead of index struct TaskItem { Transaction* transID;//should be the pointer, instead of timestamp int taskIndex; void display(); }; bool taskItemCompare(TaskItem* left, TaskItem* right); class TransPool { friend class Scheduler; private: Queue<Transaction, MaxTransCount> list; public: TransPool(); void createTrans(int timeStamp); Transaction* next(); void removeAny(); void destroyTrans(); void display(){ list.display();} }; class TaskPool { friend class Scheduler; private: Queue<TaskItem, MaxTaskItemCount> list; public: TaskItem* getTaskItem(); void addItem(Transaction* transPtr); void removeAny();//this is for debugging void update(int transID);//put status on void display(){ list.display();} TaskItem* next(){return list.next();} }; class Scheduler { private: int timeStamp; Element elements[MaxElementCount]; TransPool transPool; TaskPool taskPool; void delayItem(TaskItem* item); void abortItem(TaskItem* item); void commitItem(TaskItem* item); void doExecTask(TaskItem* item); void removeAny(); 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))= *(this->operator[]((i+1))); } count--; if (current==(back+index)%MaxListLength) { if (index>0) { current=(back+index-1)%MaxListLength; } //current still equal back } front=(back+count)%MaxListLength;//different module } } template<class T, int MaxListLength> int Queue<T, MaxListLength>::find(T* item) { for (int i=0; i<count; i++) { if (list+(back+i)%MaxListLength==item) { return i; } } return -1; } //compare is a function pointer template<class T, int MaxListLength> int Queue<T, MaxListLength>::search(bool (*compare)(T* left, T* right), T* key) { for (int i=0; i<count; i++) { if (compare(list+(back+i)%MaxListLength, key)) { return i; } } return -1; } template<class T, int MaxListLength> T* Queue<T, MaxListLength>::operator [](int index) { if (index<count) { return list+(back+index)%MaxListLength; } 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<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; } //advance until meet front current=(current+1)%MaxListLength; if (current==front) { current=back; } return list+current; }
file name: scheduler.cpp
#include <stdio.h> #include <stdlib.h> #include "scheduler.h" const int ScheduleTaskNumber=4; char* typeString[]= { "Read", "Write", "Commit", "Abort" }; bool taskItemCompare(TaskItem* left, TaskItem* right) { return left->transID==right->transID; } Scheduler::Scheduler() { timeStamp=0; for (int i=0; i<MaxElementCount; i++) { elements[i].ID=i; elements[i].readStamp=elements[i].writeStamp=0; elements[i].committed=true; } } void Scheduler::doJob(int step) { for (int i=0; i<step; i++) { tickTimer(); switch(rand()%ScheduleTaskNumber) { case 0: transPool.createTrans(timeStamp); break; case 2: execTask(); break; case 3: //removeAny(); break; } //showStatus(); } } //for debugging void Scheduler::removeAny() { transPool.removeAny(); } void Scheduler::addTask() { Transaction* ptr; //if transpool is not empty if ((ptr=transPool.next())!=NULL) { //ptr is an input pointer param 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++; if (timeStamp%20==0) { showStatus(); } } void Scheduler::doExecTask(TaskItem* item) { Transaction* tranPtr; Task* taskPtr; Element* elemPtr; tranPtr=item->transID;//the pointer taskPtr=tranPtr->tasks+item->taskIndex; elemPtr=elements+taskPtr->element;//element is array of Element in scheduler printf("\n*************************\nbefore action element %c is:", elemPtr->ID+'A'); elemPtr->display(); switch(taskPtr->taskType) { case Read: //compare the transaction timestamp with write timestamp of element if (tranPtr->timeStamp>=elemPtr->writeStamp) { //two cases, if element is committed if (tranPtr->timeStamp!=elemPtr->writeStamp&&!elemPtr->committed) { //realizable, but have to delay it until it is committed //delayItem(item); printf("transaction %d is delayed when attempted reading element %c\n", tranPtr->timeStamp, elemPtr->ID+'A'); } else { //update read timestamp of element if necessary if (tranPtr->timeStamp>elemPtr->readStamp) { //record previous read stamp taskPtr->prevStamp=elemPtr->readStamp; taskPtr->prevCommitted=elemPtr->committed; elemPtr->readStamp=tranPtr->timeStamp; } printf("transaction %d is successful when attempted reading element %c\n", tranPtr->timeStamp, elemPtr->ID+'A'); //it can be finished, or committed commitItem(item); } } else { //unrealizable, abort abortItem(item); printf("transaction %d is aborted when attempted reading element %c\n", tranPtr->timeStamp, elemPtr->ID+'A'); } break; case Write: //two cases, if timestamp is later than readstamp of element if (tranPtr->timeStamp >= elemPtr->readStamp) { //if no other later transaction has written if (tranPtr->timeStamp >= elemPtr->writeStamp) { //record time stamp and committed status for rollback taskPtr->prevCommitted=elemPtr->committed; taskPtr->prevStamp=elemPtr->writeStamp; elemPtr->writeStamp=tranPtr->timeStamp; elemPtr->committed=false; printf("transaction %d is successful when attempt writing element %c\n", tranPtr->timeStamp, elemPtr->ID+'A'); commitItem(item); } else { if (elemPtr->committed) { printf("transaction %d is ignored when attempt writing element %c\n", tranPtr->timeStamp, elemPtr->ID+'A'); //ignore should be able to be finished taskPtr->prevCommitted=elemPtr->committed; taskPtr->prevStamp=elemPtr->writeStamp; commitItem(item); } else { //delayItem(item); printf("transaction %d is delayed when attempted writing element %c\n", tranPtr->timeStamp, elemPtr->ID+'A'); } } } else { //unrealizable, abort abortItem(item); printf("transaction %d is aborted when attempted writing element %c\n", tranPtr->timeStamp, elemPtr->ID+'A'); } break; default: printf("strange thing is here\n**********************\n"); break; } printf("after action element %c is:", elemPtr->ID+'A'); elemPtr->display(); //it is committed or } void Scheduler::abortItem(TaskItem* item) { Transaction* tranPtr; Task* taskPtr; tranPtr=item->transID; for (int i=tranPtr->current; i>=0; i--) { taskPtr=tranPtr->tasks+i; if (taskPtr->taskType==Read) { elements[taskPtr->element].readStamp=taskPtr->prevStamp; } else { elements[taskPtr->element].writeStamp=taskPtr->prevStamp; } elements[taskPtr->element].committed=taskPtr->prevCommitted; } tranPtr->current=0; } void Scheduler::commitItem(TaskItem* item) { Transaction* tranPtr; int index; tranPtr=item->transID; if (tranPtr->count==item->taskIndex+1) { printf("transaction %d is committed\n", tranPtr->timeStamp); for (int i=0; i<tranPtr->count; i++) { if (tranPtr->tasks[i].taskType==Write) { elements[tranPtr->tasks[i].element].committed=true; } } if ((index=transPool.list.find(tranPtr))!=-1) { transPool.list.remove(index); } } else { tranPtr->current++; } /* while ((index=taskPool.list.search(taskItemCompare, item))!=-1) { taskPool.list.remove(index); } */ //showStatus(); } void Scheduler::execTask() { Transaction* tranPtr; TaskItem item; //if there is transaction if (transPool.list.count>0) { tranPtr=transPool.list.next(); { item.transID=tranPtr; item.taskIndex=tranPtr->current; doExecTask(&item); } } /* TaskItem* item; item=taskPool.next(); if (item!=NULL) { doExecTask(item); } */ //taskPool.display(); //taskPool.removeAny(); //taskPool.display(); } void TaskPool::removeAny() { int index; if (list.getCount()>0) { index=rand()%list.getCount(); printf("remove taskpool of task with index of %d\n", index); list.remove(index); } } //want to remove finished tasks //later..... void TaskPool::update(int transID) { TaskItem* ptr; for (int i=0; i<list.getCount(); i++) { ptr=list.next(); if (ptr!=NULL) { //if (ptr->ti } } } //this is like a scheduler's bookkeeper which records all //tasks to be done void TaskPool::addItem(Transaction* transPtr) { TaskItem* ptr; int index; if (!transPtr->haveNext()) { return; } if (list.enqueue(ptr)) { ptr->transID=transPtr; transPtr->moveNext(index); ptr->taskIndex=index; } } void Element::display() { printf("Element ID=%c; read stamp=%d; write stamp=%d; committed=%c\n", ID+'A', 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", element+'A', typeString[taskType]); printf("Element previous timestamp=%d, previous committed=%c\n", prevStamp, prevCommitted?'T':'F'); } 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; taskindex of %d\n", transID->timeStamp, taskIndex); printf("the task is:"); transID->tasks[taskIndex].display(); } TransPool::TransPool() { } Transaction& Transaction::operator =(Transaction& other) { timeStamp=other.timeStamp; count=other.count; current=other.current; for (int i=0; i<count; i++) { tasks[i]=other.tasks[i];//copy } return *this; } //this is mainly for debugging void TransPool::removeAny() { int index; if (list.getCount()>0) { list.display(); index=rand()%list.getCount(); printf("transpool remove transaction of index of %d\n", index); list.remove(index); list.display(); } } 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->tasks[i].prevCommitted=false; ptr->tasks[i].prevStamp=0; } 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" #include <time.h> #include <stdlib.h> int main() { srand(time(0)); Scheduler S; S.doJob(100); return 0; }
How to run?
1.This is just a startup of environment. So, I just implement the display function for debugging.
*************************
before action element A is:Element ID=A; read stamp=0; write stamp=0;
committed=T
transaction 2 is successful when attempted reading element A
after action element A is:Element ID=A; read stamp=2; write stamp=0; committed=T
*************************
before action element B is:Element ID=B; read stamp=0; write stamp=0;
committed=T
transaction 2 is successful when attempted reading element B
after action element B is:Element ID=B; read stamp=2; write stamp=0; committed=T
*************************
before action element D is:Element ID=D; read stamp=0; write stamp=0;
committed=T
transaction 8 is successful when attempted reading element D
after action element D is:Element ID=D; read stamp=8; write stamp=0; committed=T
time is 20;
*****************************
transaction pool is:
Transaction timestamp=2; count=5; current=2;
Task element=A, type=ReadElement previous timestamp=0, previous committed=T
Task element=B, type=ReadElement previous timestamp=0, previous committed=T
Task element=A, type=ReadElement previous timestamp=0, previous committed=F
Task element=A, type=ReadElement previous timestamp=0, previous committed=F
Task element=A, type=WriteElement previous timestamp=0, previous committed=F
Transaction timestamp=8; count=4; current=1;
Task element=D, type=ReadElement previous timestamp=0, previous committed=T
Task element=C, type=WriteElement previous timestamp=0, previous committed=F
Task element=C, type=ReadElement previous timestamp=0, previous committed=F
Task element=B, type=ReadElement previous timestamp=0, previous committed=F
Transaction timestamp=9; count=1; current=0;
Task element=D, type=ReadElement previous timestamp=0, previous committed=F
Transaction timestamp=13; count=2; current=0;
Task element=B, type=WriteElement previous timestamp=0, previous committed=F
Task element=A, type=WriteElement previous timestamp=0, previous committed=F
*************************
before action element D is:Element ID=D; read stamp=8; write stamp=0;
committed=T
transaction 9 is successful when attempted reading element D
transaction 9 is committed
after action element D is:Element ID=D; read stamp=9; write stamp=0; committed=T
*************************
before action element B is:Element ID=B; read stamp=2; write stamp=0;
committed=T
transaction 13 is successful when attempt writing element B
after action element B is:Element ID=B; read stamp=2; write stamp=13;
committed=F
*************************
before action element C is:Element ID=C; read stamp=0; write stamp=0;
committed=T
transaction 25 is successful when attempted reading element C
after action element C is:Element ID=C; read stamp=25; write stamp=0;
committed=T
*************************
before action element A is:Element ID=A; read stamp=2; write stamp=0;
committed=T
transaction 2 is successful when attempted reading element A
after action element A is:Element ID=A; read stamp=2; write stamp=0; committed=T
*************************
before action element C is:Element ID=C; read stamp=25; write stamp=0;
committed=T
transaction 8 is aborted when attempted writing element C
after action element C is:Element ID=C; read stamp=25; write stamp=0;
committed=F
time is 40;
*****************************
transaction pool is:
Transaction timestamp=2; count=5; current=3;
Task element=A, type=ReadElement previous timestamp=0, previous committed=T
Task element=B, type=ReadElement previous timestamp=0, previous committed=T
Task element=A, type=ReadElement previous timestamp=0, previous committed=F
Task element=A, type=ReadElement previous timestamp=0, previous committed=F
Task element=A, type=WriteElement previous timestamp=0, previous committed=F
Transaction timestamp=8; count=4; current=0;
Task element=D, type=ReadElement previous timestamp=0, previous committed=T
Task element=C, type=WriteElement previous timestamp=0, previous committed=F
Task element=C, type=ReadElement previous timestamp=0, previous committed=F
Task element=B, type=ReadElement previous timestamp=0, previous committed=F
Transaction timestamp=13; count=2; current=1;
Task element=B, type=WriteElement previous timestamp=0, previous committed=T
Task element=A, type=WriteElement previous timestamp=0, previous committed=F
Transaction timestamp=25; count=4; current=1;
Task element=C, type=ReadElement previous timestamp=0, previous committed=T
Task element=A, type=WriteElement previous timestamp=0, previous committed=F
Task element=D, type=ReadElement previous timestamp=0, previous committed=F
Task element=B, type=ReadElement previous timestamp=0, previous committed=F
*************************
before action element A is:Element ID=A; read stamp=2; write stamp=0;
committed=T
transaction 13 is successful when attempt writing element A
transaction 13 is committed
after action element A is:Element ID=A; read stamp=2; write stamp=13;
committed=T
time is 60;
*****************************
transaction pool is:
Transaction timestamp=2; count=5; current=3;
Task element=A, type=ReadElement previous timestamp=0, previous committed=T
Task element=B, type=ReadElement previous timestamp=0, previous committed=T
Task element=A, type=ReadElement previous timestamp=0, previous committed=F
Task element=A, type=ReadElement previous timestamp=0, previous committed=F
Task element=A, type=WriteElement previous timestamp=0, previous committed=F
Transaction timestamp=8; count=4; current=0;
Task element=D, type=ReadElement previous timestamp=0, previous committed=T
Task element=C, type=WriteElement previous timestamp=0, previous committed=F
Task element=C, type=ReadElement previous timestamp=0, previous committed=F
Task element=B, type=ReadElement previous timestamp=0, previous committed=F
Transaction timestamp=25; count=4; current=1;
Task element=C, type=ReadElement previous timestamp=0, previous committed=T
Task element=A, type=WriteElement previous timestamp=0, previous committed=F
Task element=D, type=ReadElement previous timestamp=0, previous committed=F
Task element=B, type=ReadElement previous timestamp=0, previous committed=F
*************************
before action element A is:Element ID=A; read stamp=2; write stamp=13;
committed=T
transaction 25 is successful when attempt writing element A
after action element A is:Element ID=A; read stamp=2; write stamp=25;
committed=F
*************************
before action element A is:Element ID=A; read stamp=2; write stamp=25;
committed=F
transaction 2 is aborted when attempted reading element A
after action element A is:Element ID=A; read stamp=0; write stamp=25;
committed=T
*************************
before action element D is:Element ID=D; read stamp=0; write stamp=0;
committed=T
transaction 8 is successful when attempted reading element D
after action element D is:Element ID=D; read stamp=8; write stamp=0; committed=T
*************************
before action element D is:Element ID=D; read stamp=8; write stamp=0;
committed=T
transaction 25 is successful when attempted reading element D
after action element D is:Element ID=D; read stamp=25; write stamp=0;
committed=T
*************************
before action element C is:Element ID=C; read stamp=25; write stamp=0;
committed=F
transaction 71 is delayed when attempted reading element C
after action element C is:Element ID=C; read stamp=25; write stamp=0;
committed=F
*************************
before action element A is:Element ID=A; read stamp=0; write stamp=25;
committed=T
transaction 2 is aborted when attempted reading element A
after action element A is:Element ID=A; read stamp=0; write stamp=25;
committed=T
time is 80;
*****************************
transaction pool is:
Transaction timestamp=2; count=5; current=0;
Task element=A, type=ReadElement previous timestamp=0, previous committed=T
Task element=B, type=ReadElement previous timestamp=0, previous committed=T
Task element=A, type=ReadElement previous timestamp=0, previous committed=F
Task element=A, type=ReadElement previous timestamp=0, previous committed=F
Task element=A, type=WriteElement previous timestamp=0, previous committed=F
Transaction timestamp=8; count=4; current=1;
Task element=D, type=ReadElement previous timestamp=0, previous committed=T
Task element=C, type=WriteElement previous timestamp=0, previous committed=F
Task element=C, type=ReadElement previous timestamp=0, previous committed=F
Task element=B, type=ReadElement previous timestamp=0, previous committed=F
Transaction timestamp=25; count=4; current=3;
Task element=C, type=ReadElement previous timestamp=0, previous committed=T
Task element=A, type=WriteElement previous timestamp=13, previous committed=T
Task element=D, type=ReadElement previous timestamp=8, previous committed=T
Task element=B, type=ReadElement previous timestamp=0, previous committed=F
Transaction timestamp=71; count=4; current=0;
Task element=C, type=ReadElement previous timestamp=0, previous committed=F
Task element=D, type=WriteElement previous timestamp=0, previous committed=F
Task element=B, type=ReadElement previous timestamp=0, previous committed=F
Task element=D, type=ReadElement previous timestamp=0, previous committed=F
*************************
before action element C is:Element ID=C; read stamp=25; write stamp=0;
committed=F
transaction 8 is aborted when attempted writing element C
after action element C is:Element ID=C; read stamp=25; write stamp=0;
committed=F
*************************
before action element B is:Element ID=B; read stamp=0; write stamp=13;
committed=T
transaction 25 is successful when attempted reading element B
transaction 25 is committed
after action element B is:Element ID=B; read stamp=25; write stamp=13;
committed=T
time is 100;
*****************************
transaction pool is:
Transaction timestamp=2; count=5; current=0;
Task element=A, type=ReadElement previous timestamp=0, previous committed=T
Task element=B, type=ReadElement previous timestamp=0, previous committed=T
Task element=A, type=ReadElement previous timestamp=0, previous committed=F
Task element=A, type=ReadElement previous timestamp=0, previous committed=F
Task element=A, type=WriteElement previous timestamp=0, previous committed=F
Transaction timestamp=8; count=4; current=0;
Task element=D, type=ReadElement previous timestamp=0, previous committed=T
Task element=C, type=WriteElement previous timestamp=0, previous committed=F
Task element=C, type=ReadElement previous timestamp=0, previous committed=F
Task element=B, type=ReadElement previous timestamp=0, previous committed=F
Transaction timestamp=71; count=4; current=0;
Task element=C, type=ReadElement previous timestamp=0, previous committed=F
Task element=D, type=WriteElement previous timestamp=0, previous committed=F
Task element=B, type=ReadElement previous timestamp=0, previous committed=F
Task element=D, type=ReadElement previous timestamp=0, previous committed=F
Transaction timestamp=99; count=1; current=0;
Task element=D, type=WriteElement previous timestamp=0, previous committed=F
*************************
before action element C is:Element ID=C; read stamp=25; write stamp=0;
committed=F
transaction 71 is delayed when attempted reading element C
after action element C is:Element ID=C; read stamp=25; write stamp=0;
committed=F