elevator

The elevator algorithm

    A. Second Edition

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

    And when I made some change to previous version, I began to doubt the meaning of latency, and what exactly

    mean by word latency? Is it same as response time in process management?

    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
¡¡

    What I concern now is the task generating rate. You see, according to theory of queuing, the waiting time should

    be closely connected with the incoming rate. What I mean is that only if the length of queue is stable, the

    average waiting time is not fixed. Therefore, what we are talking about latency is quite meaningless.

    For example, in my program, the "rate of task" is how much the chance a task would be generated. (No matter

    what track number it is.) If you change the rate, then the average waiting time is not fixed. However, there is

    only a small programming trick from reality. That is, I set an upper limit "MaxTaskNumber" for number of tasks.

    So, you have to adjust it too. Nevertheless, the average waiting time is not fixed.

    However, the result is quite interesting: When the task generating rate is very low, the average waiting time

    is exactly 1/3! I cannot figure why!

    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=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);
    	}
    }

    The result is like following: please note that the average waiting time is: 1/3!

    This is rate of 20, or 1/20 chances to generate a task.

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

    This is rate of 40, or 1/40 chances to generate a task.

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

    This is rate of 80, or 1/80 chances to generate a task.

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

    ¡¡

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

    This is rate of 120, or 1/120 chances to generate a task.

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

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

    ¡¡

    ¡¡

    ¡¡

    ¡¡