elevator

The problem is a simple: what is the average waiting time or latency time for disk arm to move to

required track? In the book, it is said 1/3 of total track number moving time and I am not sure

about the number. By elevator algorithm, the disk arm will just move like an elevator to one

direction until in its front there is no more track to scan or no more task waiting. Then the arm

change direction. So simple, so easy. However, I am puzzled if I need to "buffer" the incoming

tasks in a waiting list. I decide to have because disk has a buffer and can only accept a bunch of

task at one time. (This may not be true. And I will modify this in next edition shortly.)

1. disk.cpp(main)

file name: naughty.cpp

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

const int MaxTrackNumber=40;
const int MaxTaskNumber=40;
const int TotalTaskNumber=1600;
const int RateOfTask=40;
//const int Average=20;


struct Task
{
	int startTime;
	int track;
	int endTime;
};

Task taskPool[TotalTaskNumber];

class Arm;


class Timer
{
	friend class Arm;
private:
	int working[MaxTrackNumber];
	//int waiting[MaxTrackNumber];
	int workingCount;
	//int waitingCount;
	//int lastPeriod;
	//int currPeriod;
	int counter;
	bool possible();
	bool testDir(bool forward, int current);
	int taskIndex;
public:
	void generate();
	Timer();
	int getTime(){return counter;}
	void tick(Arm arm);
	//void reset();
	void taskTest(bool& forward, int& current);
	bool finished(){return taskIndex==TotalTaskNumber;}
};

Timer timer;

class Arm
{
private:
	bool forward;
	int current;
	
public:
	Arm();
	bool step();
	void report();
};


int main()
{
	Arm A;
	srand(time(0));
	timer.tick(A);
	A.report();
	return 0;
}




//timer tick and solve task, generate new task by possibility
void Timer::tick(Arm arm)
{
	while (!arm.step())
	{
		counter++;
		generate();
		/*
		
		*/
		
	}
}

bool Timer::possible()
{
	//currPeriod++;
	//waitingCount/currPeriod
	//return currPeriod-rand()%lastPeriod>=0;
	return rand()%RateOfTask==0;
}

void Timer::generate()
{
	int theTrack;
	if (finished())
	{
		return;
	}
	if (workingCount<MaxTaskNumber)
	{
		if (possible())//generate
		{
			taskPool[taskIndex].startTime=counter;
			theTrack=rand()%MaxTrackNumber;
			while (working[theTrack]!=-1)
			{
				theTrack=rand()%MaxTrackNumber;
			}
			taskPool[taskIndex].track=theTrack;
			taskPool[taskIndex].endTime=-1;//initialize
			working[theTrack]=taskIndex;
			workingCount++;
			taskIndex++;
		}
	}
}

Timer::Timer()
{
	counter=0;
	taskIndex=0;
	//lastPeriod=Average;
	//currPeriod=0;
	workingCount=0;
	for (int i=0; i<MaxTrackNumber; i++)
	{
		working[i]=-1;
	}
}
/*
void Timer::reset()
{
	if (workingCount==0)
	{
		for (int i=0; i<MaxTrackNumber; i++)
		{
			working[i]=waiting[i];
			//waiting[i]=-1;//clear up
		}
		//lastPeriod=currPeriod;
		//currPeriod=0;
		workingCount=0;//=waitingCount;
		//waitingCount=0;//clear up
	}
}
*/

void Timer::taskTest(bool& forward, int& current)
{
	//always to call reset in case working period finished
	//reset();
	//first to determine direction
	if (timer.workingCount==0)
	{
		return;
	}
	if (forward)
	{
		//always assume change direction unless...
		forward=false;
		//unless there is something to explore
		
		for (int i=current+1; i<MaxTrackNumber; i++)
		{
			if (working[i]!=-1)
			{
				forward=true;
				break;
			}
		}			
	}
	else
	{
		//always assume change direction
		forward=true;

		for(int i=current-1; i>=0; i--)
		{
			if (working[i]!=-1)
			{
				//unless we find reason for keep going
				forward=false;
				break;
			}
		}	
	}
	//since we setup direction,let's go
	if (forward)
	{
		current++;
	}
	else
	{
		current--;
	}
	if (working[current]!=-1)
	{
		//if (taskPool[working[curPos]].endTime==-1)
		{
			taskPool[working[current]].endTime=counter;
			workingCount--;
			working[current]=-1;
		}
	}
	//tick(current);
}

bool Arm::step()
{
	//it is timer's responsibility to determine forward
	timer.taskTest(forward, current);
	return timer.workingCount==0&&timer.finished();
	//timer.tick(current);
}
	
Arm::Arm()
{
	current=0;
	forward=true;
	//initialize to have at least one task
	while (timer.workingCount<1)
	{
		timer.generate();
	}
}

void Arm::report()
{
	long total=0;
	if (timer.finished())
	{
		for (int i=0; i<TotalTaskNumber; i++)
		{
			total+=taskPool[i].endTime-taskPool[i].startTime;
		}
		printf("total waiting time is %d\n", total);
		printf("for total number %d tasks, the average waiting time:\n%d", 
			TotalTaskNumber, total/TotalTaskNumber);
		printf("and ratio with number of track is %d/%d=%d\n", total/TotalTaskNumber, 
			MaxTrackNumber,	total/TotalTaskNumber/MaxTrackNumber);
	}
	else
	{
		printf("task proceeding no. %d\n", timer.taskIndex);
	}
}