The elevator algorithm
A. First Edition
This is a small demo program to test the algorithm of elevator algorithm which is used in disk for arm moving.
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.)
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.)
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![]()
![]()
![]()