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