/* mp4.c -- disk access time simulator */ /*************************************** * Modified by Douglas Jones to * * a cyclic-scan disk scheduler; * * all changes marked * ***************************************/ /* this simulation uses integer time, * the time unit is the time it takes one sector to spin past the heads */ #include #include /******************************************************************* * simulation support, totally independent of the simulation model * *******************************************************************/ /* NOTE: the event set implementation here is a simple linear priority queue. * this is a good choice only if the queue length stays under 10 to 20 events. * much better algorithms exist (splay trees, skip lists, calendar queues). */ /* events occur at specific instants in time and each event has some kind */ struct event { struct event * next; /* the next event in the pending event set */ int time; /* the time at which this event will occur */ int kind; /* the kind of event this is */ }; struct event * eventset = NULL; /* the pending event set */ struct event * newevent( int t, int k ){ /* initializer */ struct event * new = malloc( sizeof( struct event ) ); new->time = t; new->kind = k; return new; } void schedule( struct event * e ){ /* place an event in the event set */ if (eventset == NULL) { /* trivial enqueue in an empty queue */ e->next = NULL; eventset = e; } else if (e->time < eventset->time) { /* e is new head of queue */ e->next = eventset; eventset = e; } else { /* nontrivial enqueue, sort down into the set */ struct event * pred = eventset; struct event * succ = pred->next; while ((succ != NULL) && (e->time >= succ->time)) { pred = succ; succ = pred->next; } e->next = succ; pred->next = e; } } struct event * getnextevent(){ /* get the next pending event */ struct event * e = eventset; int k; if (e == NULL) return NULL; eventset = e->next; return e; } /******************** * model parameters * ********************/ #define ENDTIME 100000 #define SECTORSPERTRACK 128 #define TRACKSPERCYLINDER 4 #define CYLINDERS 4096 /* the above models a 1 gigabyte drive if sectors are 512 bytes */ /* assume 15,000 RPM, which is 250 RPS, so rotation time is 4 ms; * 4ms/128 = 31.25 ns -- time to read one sector, our time unit. */ #define SEEKSCALE 16 /* scale factor for seek time (t ~= sqrt( SEEKSCALE * cyl's moved)) */ /* typical seek time: 0.5 ms to move one track; * this is 16 time units; worst case is 256 time units or 8 ms. */ #define MEANARRIVALTIME 125 /* average interval from one arrival to the next */ #define SECTORBIAS 5 /* shape of distribution of disk requests * 1 = uniform distribution * 2 = triangular distribution * ... * higher values are successively closer to a normal distribution */ /***************** * model support * *****************/ #define DISKSIZE (SECTORSPERTRACK * TRACKSPERCYLINDER * CYLINDERS) #define SECTOR(a) (a % SECTORSPERTRACK) #define SURFACE(a) ((a / SECTORSPERTRACK) % TRACKSPERCYLINDER) #define CYLINDER(a) ((a / SECTORSPERTRACK) / TRACKSPERCYLINDER) /* types of events */ #define EVENT_END 0 #define EVENT_ARRIVE 1 #define EVENT_READY 2 /******************* * model variables * *******************/ /* current cylinder */ int curcyl = 0; /* note that because the disk rotates at a constant speed, the current sector is (time % SECTORSPERTRACK), and note that there is no need to record the current surface because switching surfaces is a matter of electronic switching */ /* state of disk controller */ #define DISK_IDLE 0 #define DISK_BUSY 1 int disk_state = DISK_IDLE; /***************** * model support * *****************/ /* disk request structure */ struct diskrequest { /* fields to make disk requests queueable */ struct diskrequest * next; /* NULL if at end of list */ /* changed */ struct diskrequest * back; /* NULL if at start of list */ /* changed */ /* actual disk request, sufficient for simulation */ int addr; /* requested disk address */ /* bookkeeping for statistics gathering */ int timein; /* time request enqueued */ }; /************** * disk queue * **************/ /* NOTE: this implements the cyclic scan disk scheduler /+ changed +/ * by maintaining the queue as a list sorted on the addr /+ changed +/ * fields of the requests and dequeueing from a moving /+ changed +/ * cursor that tracks the current head position. /+ changed +/ */ /* To change the queueing discipline, change the queueable * fields in the disk request, change the following declarations, * and change the enqueue and dequeue routines. */ /* changed */ struct diskrequest * head = NULL; /* low end of queue, NULL if empty */ struct diskrequest * current = NULL; /* the moving cursor, NULL if empty */ /* changed */ void enqueue( struct diskrequest * r ){ if (head == NULL) { /* enqueue in empty queue */ /* changed */ r->next = NULL; /* changed */ r->back = NULL; /* changed */ head = r; /* changed */ current = r; /* changed */ } else if (r->addr <= head->addr) { /* new lowest item */ /* changed */ r->next = head; /* changed */ r->back = NULL; /* changed */ head->back = r; /* changed */ head = r; /* changed */ } else { /* sort the new item into the queue */ /* changed */ struct diskrequest * p = head; /* changed */ while ((p->next != NULL) /* changed */ && (r->addr > p->next->addr)){ /* changed */ p = p->next; /* scan through queue */ /* changed */ } /* changed */ r->next = p->next; /* may be NULL if at end */ /* changed */ r->back = p; /* changed */ if (p->next != NULL) p->next->back = r; /* changed */ p->next = r; /* changed */ } } struct diskrequest * dequeue(){ if (head == NULL) { /* dequeue from empty queue */ /* changed */ return NULL; /* changed */ } else { /* the normal case, queue not empty */ /* changed */ struct diskrequest * r = current; /* changed */ current = current->next; /* move cursor */ /* changed */ /* above may make current NULL */ /* changed */ /* changed */ /* snip r out of queue */ /* changed */ if (r->back != NULL) r->back->next = r->next; /* changed */ if (r->next != NULL) r->next->back = r->back; /* changed */ if (r == head) head = r->next; /* changed */ /* above may make head NULL if queue now empty */ /* changed */ /* changed */ /* deal case where highest item dequeued */ /* changed */ if (current == NULL) current = head; /* changed */ /* above makes current NULL if head NULL */ /* changed */ /* changed */ return r; /* changed */ } } /********************* * physical modeling * *********************/ int pickasector(){ /* distribution of disk addresses */ int i; int a = 0; for (i = 0; i < SECTORBIAS; i++) a = a + (random() % DISKSIZE); return a / SECTORBIAS; } int enqdelay(){ /* request arrival time distribution */ int scale = (MEANARRIVALTIME * 34)/ 10; /* approx 1/(1-1/sqrt(2)) */ int d = ((random() % scale) + (random() % scale)) - scale; return abs(d); } int deqdelay( int a, int t ){ /* disk service time computation, given */ /* a = address of next transfer */ /* t = the current time */ int r; /* rotational delay */ int s; /* seek time */ /* first work out quadratic seek time */ s = abs( curcyl - CYLINDER(a) ) * SEEKSCALE; if (s > 1) { int sinit = s; /* original value */ int sold; /* former value */ do { sold = s; s = (s + sinit/s) >> 1; /* Newton's method */ } while (s < sold); } /* second, account for rotational latency */ r = ((t + s) - (SECTOR(a)) + SECTORSPERTRACK) % SECTORSPERTRACK; return r + s; } /******************************** * main program, the simulation * ********************************/ int main(){ int enqueues = 0; /* count total number of items enqueued */ int dequeues = 0; /* count total number of items dequeues */ int queuelen = 0; /* measure queue length */ int waittime = 0; /* total time spent by all enqueued items */ int maxwait = 0; /* worst case waiting time */ int maxqueue = 0; /* worst case queue length */ /* start up the model */ schedule( newevent( ENDTIME, EVENT_END ) ); schedule( newevent( 0, EVENT_ARRIVE ) ); /* run the simulation */ for (;;) { struct event * e = getnextevent(); if (e->kind == EVENT_END) { break; } else switch (e->kind) { case EVENT_ARRIVE: { /* a new disk request arrives */ struct diskrequest * r; /* invent the request */ r = malloc( sizeof( struct diskrequest )); r->addr = pickasector(); r->timein = e->time; enqueue( r ); /* gather statistics */ queuelen++; enqueues++; if (queuelen > maxqueue) maxqueue = queuelen; if (disk_state == DISK_IDLE) { schedule( newevent( e->time, EVENT_READY ) ); } /* make the next request */ e->time = e->time + enqdelay(); schedule( e ); break; } case EVENT_READY: { /* the disk finishes a request */ struct diskrequest * r; r = dequeue(); if (r == NULL) { /* queue was empty */ disk_state = DISK_IDLE; free( e ); } else { disk_state = DISK_BUSY; int mywait = (e->time - r->timein); queuelen--; dequeues++; waittime = waittime + mywait; if (mywait > maxwait) maxwait = mywait; e->time = e->time + deqdelay( r->addr, e->time ); curcyl = CYLINDER( r->addr ); free( r ); schedule( e ); } } } } printf( "in %d time units\n", ENDTIME ); printf( "enqueued %d disk requests\n", enqueues ); printf( "completed %d disk requests\n", dequeues ); printf( "leaving %d requests unfinished\n\n", queuelen ); printf( "average time request is in the queue: %d\n", waittime/dequeues); printf( "worst case waiting time in the queue: %d\n", maxwait); printf( "worst case queue length: %d\n", maxqueue ); }