A. First Edition

This is a small demo program to test the algorithm of elevator algorithm which is used in disk for arm moving.

B.The problem

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.)

　

C.The idea of program

　

There is a class called Arm and it has a class object Timer which can tick whenever Arm moves one step. In the

ticking of Timer, it calculates a possibility to generate new tasks in a "waiting" list. The waiting list will

be copied into a "working" list if the tasks in "working" list runs out. The rate of generating new tasks is

a bit of tricky. I presumed the waiting queue is a stable queue such that the rate of leaving tasks is same as

the rate of incoming tasks. So, I record the period of last searching time and possibility of generating a new

task will depend on how...(My God! it is wrong and I will change this in next edition.)

D.The major functions

E.Further improvement

It is a small game and no one would bother to treat them seriously, I presume.

F.File listing

1. disk.cpp(main)

file name: naughty.cpp

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

const int MaxTrackNumber=40;
const int MaxTaskNumber=30;
const int TotalTaskNumber=1600;
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(int curPos);
	void reset();
	void taskTest(bool& forward, int& current);
	bool finished(){return taskIndex==TotalTaskNumber;}
};



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


int main()
{
	Arm A;
	srand(time(0));
	while (!A.step())
	{
		//A.report();
	}
	A.report();
	return 0;
}




//timer tick and solve task, generate new task by possibility
void Timer::tick(int curPos)
{
	counter++;
	generate();
	if (working[curPos]!=-1)
	{
		//if (taskPool[working[curPos]].endTime==-1)
		{
			taskPool[working[curPos]].endTime=counter;
			workingCount--;
			working[curPos]=-1;
		}
	}
}

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

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

Timer::Timer()
{
	counter=0;
	taskIndex=0;
	lastPeriod=Average;
	currPeriod=0;
	waitingCount=workingCount=0;
	for (int i=0; i<MaxTrackNumber; i++)
	{
		working[i]=waiting[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=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 (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--;
	}
	tick(current);
}

bool Arm::step()
{
	//it is timer's responsibility to determine forward
	timer.taskTest(forward, current);
	return timer.workingCount==0&&timer.finished()&&timer.waitingCount==0;
	//timer.tick(current);
}
	
Arm::Arm()
{
	current=0;
	forward=true;
	//initialize to have at least one task
	while (timer.waitingCount<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);
	}
}

The result is like following: And it is not correct!  

total waiting time is 56532
for total number 1600 tasks, the average waiting time:
35and ratio with number of track is 35/40=0
Press any key to continue