/* mp4.c -- disk access time simulator */
/* By Douglas W. Jones, using one-way circular-scan scheduling */

/* The one-way circular scan only worries about cylinder number,
 * ignoring track number in cylinder and sector number in track.
 * The impact is huge, compared to simple FIFO scheduling:
 * with the queue load simulated here,
 * the average time a request is in the queue is reduced from 3572 to 351.
 * the worst-case waiting time is reduced from 6926 to 1529,
 * and the worst-case queue length is reduced from 34 to 8.

/* this simulation uses integer time,
 * the time unit is the time it takes one sector to spin past the heads
 */

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

/******************** 
 * model parameters * 
 ********************/

#define ENDTIME 100000
#define NEVER   (ENDTIME + 1)

#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   175
	/* average interval from one arrival to the next */	/*** bug ***/

/***************** 
 * model support * 
 *****************/

#define DISKSIZE    (SECTORSPERTRACK * TRACKSPERCYLINDER * CYLINDERS)
#define SECTOR(a)   (a % SECTORSPERTRACK)
#define SURFACE(a)  ((a / SECTORSPERTRACK) % TRACKSPERCYLINDER)
#define CYLINDER(a) ((a / SECTORSPERTRACK) / TRACKSPERCYLINDER)

/*******************
 * model variables *
 *******************/

int time = -1;       /* current time */
int nextenq = 0;     /* time of next enqueue */
int nextdeq = NEVER; /* time of next dequeue */
	/* note, the above sets things up so that the model will
	 * begin with an enqueue, and no dequeue is pending
	 */

int curcyl = 0;      /* current cylinder */

/***************** 
 * model support * 
 *****************/

/* disk request structure */
struct diskrequest {
	/* fields to make disk requests queueable */
	struct diskrequest * next; /* sufficient for FIFO */

	/* actual disk request, sufficient for simulation */
	int addr; /* requested disk address */

	/* bookkeeping for statistics gathering */
	int timein; /* time request enqueued */
};

/**************
 * disk queue * 
 **************/

/* NOTE: this is an circular scan algorithm implemented using an array
 * of simple FIFO queue, one per disk cylinder, using the queueable
 * fields in the diskrequest struct.  In addition, there is one queue
 * for the requests being worked on in the current cylinder, so that
 * it is impossible for repeated enqueues in that cylinder to starve
 * requests for other cylinders.
 */
/* To change the queueing discipline, change the queueable
 * fields in the disk request, change the following declarations,
 * and change the enqueue and dequeue routines.
 */

struct requestqueue {
	struct diskrequest * head;
	struct diskrequest * tail;
};

/* one queue per cylinder */
struct requestqueue queues[CYLINDERS];

/* plus one queue for the current cylinder */
struct requestqueue thisqueue;

/* keep track of the cylinder currently being served */
int deqcyl = -1; /* an illegal initial value used to force initialization */

void initqueues(){ /* initialize the queue data structures */
	int i; /* for loop index */
	thisqueue.head = NULL;
	thisqueue.tail = NULL;
	for (i = 0; i < CYLINDERS; i++) {
		queues[i].head = NULL;
		queues[i].tail = NULL;
	}
	deqcyl = 0;
}

void enqueue( struct diskrequest * r ){
	struct requestqueue * q;
	if (deqcyl == -1) initqueues();
	
	/* pick the correct queue to enqueue on */
	q = &queues[ CYLINDER( r->addr ) ];

	/* do the enqueue */
	r->next = NULL;
	if (q->head == NULL) { /* implies tail == undefined */
		q->head = r;
	} else {
		q->tail->next = r;
	}
	q->tail = r;
}

struct diskrequest * dequeue(){
	struct diskrequest * r;

	/* check if an elevator scan is needed */
	if (thisqueue.head == NULL) {
		int start = deqcyl;
		for (;;) { /* scan looking for work */
			deqcyl = deqcyl + 1;
			if (deqcyl >= CYLINDERS) deqcyl = 0;
			if (deqcyl == start) break;
			if (queues[deqcyl].head != NULL) break;
		}
		thisqueue.head = queues[deqcyl].head;
		thisqueue.tail = queues[deqcyl].tail;
		queues[deqcyl].head = NULL;
		queues[deqcyl].tail = NULL;
	}

	/* now dequeue from the current working queue */
	if (thisqueue.head == NULL) return NULL;
	r = thisqueue.head;
	thisqueue.head = r->next;
	return r;
}

/*********************
 * physical modeling * 
 *********************/

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 ){
	/* disk service time distribution, given */
	/*  a = address of next transfer */
	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 = ((time + s) - (SECTOR(a)) + SECTORSPERTRACK) % SECTORSPERTRACK;

	return r + s;
}

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 */
	while (time < ENDTIME) {
		if (nextenq < nextdeq) { /* enqueue a new disk request */
			struct diskrequest * r;
			time = nextenq;

			r = malloc( sizeof( struct diskrequest ));
			r->addr = random() % DISKSIZE;
			r->timein = time;
			enqueue( r );
			queuelen++;
			enqueues++;
			if (queuelen > maxqueue) maxqueue = queuelen;
			if (nextdeq == NEVER) nextdeq = time;
			nextenq = time + enqdelay();
		} else { /* dequeue a disk request */
			struct diskrequest * r;
			time = nextdeq;

			r = dequeue();
			if (r == NULL) { /* queue was empty */
				nextdeq = NEVER;
			} else {
				int mywait = (time - r->timein);
				queuelen--;
				dequeues++;
				waittime = waittime + mywait;
				if (mywait > maxwait) maxwait = mywait;
				nextdeq = time + deqdelay( r->addr );
				curcyl = CYLINDER( r->addr );	/*** bug ***/
				free( r );
			}
		}
	}
	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 );
}