disksim_ioqueue.c

目前最精确的磁盘模拟器的第3版

/*
 * DiskSim Storage Subsystem Simulation Environment (Version 3.0)
 * Revision Authors: John Bucy, Greg Ganger
 * Contributors: John Griffin, Jiri Schindler, Steve Schlosser
 *
 * Copyright (c) of Carnegie Mellon University, 2001, 2002, 2003.
 *
 * This software is being provided by the copyright holders under the
 * following license. By obtaining, using and/or copying this software,
 * you agree that you have read, understood, and will comply with the
 * following terms and conditions:
 *
 * Permission to reproduce, use, and prepare derivative works of this
 * software is granted provided the copyright and "No Warranty" statements
 * are included with all reproductions and derivative works and associated
 * documentation. This software may also be redistributed without charge
 * provided that the copyright and "No Warranty" statements are included
 * in all redistributions.
 *
 * NO WARRANTY. THIS SOFTWARE IS FURNISHED ON AN "AS IS" BASIS.
 * CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY KIND, EITHER
 * EXPRESSED OR IMPLIED AS TO THE MATTER INCLUDING, BUT NOT LIMITED
 * TO: WARRANTY OF FITNESS FOR PURPOSE OR MERCHANTABILITY, EXCLUSIVITY
 * OF RESULTS OR RESULTS OBTAINED FROM USE OF THIS SOFTWARE. CARNEGIE
 * MELLON UNIVERSITY DOES NOT MAKE ANY WARRANTY OF ANY KIND WITH RESPECT
 * TO FREEDOM FROM PATENT, TRADEMARK, OR COPYRIGHT INFRINGEMENT.
 * COPYRIGHT HOLDERS WILL BEAR NO LIABILITY FOR ANY USE OF THIS SOFTWARE
 * OR DOCUMENTATION.
 *
 */



/*
 * DiskSim Storage Subsystem Simulation Environment (Version 2.0)
 * Revision Authors: Greg Ganger
 * Contributors: Ross Cohen, John Griffin, Steve Schlosser
 *
 * Copyright (c) of Carnegie Mellon University, 1999.
 *
 * Permission to reproduce, use, and prepare derivative works of
 * this software for internal use is granted provided the copyright
 * and "No Warranty" statements are included with all reproductions
 * and derivative works. This software may also be redistributed
 * without charge provided that the copyright and "No Warranty"
 * statements are included in all redistributions.
 *
 * NO WARRANTY. THIS SOFTWARE IS FURNISHED ON AN "AS IS" BASIS.
 * CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY KIND, EITHER
 * EXPRESSED OR IMPLIED AS TO THE MATTER INCLUDING, BUT NOT LIMITED
 * TO: WARRANTY OF FITNESS FOR PURPOSE OR MERCHANTABILITY, EXCLUSIVITY
 * OF RESULTS OR RESULTS OBTAINED FROM USE OF THIS SOFTWARE. CARNEGIE
 * MELLON UNIVERSITY DOES NOT MAKE ANY WARRANTY OF ANY KIND WITH RESPECT
 * TO FREEDOM FROM PATENT, TRADEMARK, OR COPYRIGHT INFRINGEMENT.
 */

/*
 * DiskSim Storage Subsystem Simulation Environment
 * Authors: Greg Ganger, Bruce Worthington, Yale Patt
 *
 * Copyright (C) 1993, 1995, 1997 The Regents of the University of Michigan 
 *
 * This software is being provided by the copyright holders under the
 * following license. By obtaining, using and/or copying this software,
 * you agree that you have read, understood, and will comply with the
 * following terms and conditions:
 *
 * Permission to use, copy, modify, distribute, and sell this software
 * and its documentation for any purpose and without fee or royalty is
 * hereby granted, provided that the full text of this NOTICE appears on
 * ALL copies of the software and documentation or portions thereof,
 * including modifications, that you make.
 *
 * THIS SOFTWARE IS PROVIDED "AS IS," AND COPYRIGHT HOLDERS MAKE NO
 * REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED. BY WAY OF EXAMPLE,
 * BUT NOT LIMITATION, COPYRIGHT HOLDERS MAKE NO REPRESENTATIONS OR
 * WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY PARTICULAR PURPOSE OR
 * THAT THE USE OF THE SOFTWARE OR DOCUMENTATION WILL NOT INFRINGE ANY
 * THIRD PARTY PATENTS, COPYRIGHTS, TRADEMARKS OR OTHER RIGHTS. COPYRIGHT
 * HOLDERS WILL BEAR NO LIABILITY FOR ANY USE OF THIS SOFTWARE OR
 * DOCUMENTATION.
 *
 *  This software is provided AS IS, WITHOUT REPRESENTATION FROM THE
 * UNIVERSITY OF MICHIGAN AS TO ITS FITNESS FOR ANY PURPOSE, AND
 * WITHOUT WARRANTY BY THE UNIVERSITY OF MICHIGAN OF ANY KIND, EITHER
 * EXPRESSED OR IMPLIED, INCLUDING WITHOUT LIMITATION THE IMPLIED
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE REGENTS
 * OF THE UNIVERSITY OF MICHIGAN SHALL NOT BE LIABLE FOR ANY DAMAGES,
 * INCLUDING SPECIAL , INDIRECT, INCIDENTAL, OR CONSEQUENTIAL DAMAGES,
 * WITH RESPECT TO ANY CLAIM ARISING OUT OF OR IN CONNECTION WITH THE
 * USE OF OR IN CONNECTION WITH THE USE OF THE SOFTWARE, EVEN IF IT HAS
 * BEEN OR IS HEREAFTER ADVISED OF THE POSSIBILITY OF SUCH DAMAGES
 *
 * The names and trademarks of copyright holders or authors may NOT be
 * used in advertising or publicity pertaining to the software without
 * specific, written prior permission. Title to copyright in this software
 * and any associated documentation will at all times remain with copyright
 * holders.
 */

#include "disksim_global.h"
#include "disksim_ioqueue.h"
#include "disksim_iosim.h"
#include "disksim_stat.h"
#include "disksim_disk.h"
#include "config.h"


#include "modules/disksim_ioqueue_param.h"

#define READY_TO_GO(iobufptr,queue) (((iobufptr)->state == WAITING) && (((queue)->enablement == NULL) || ((*(queue)->enablement)((iobufptr)->iolist))))


/* Request scheduling algorithms */

#define MINSCHED	 1
#define FCFS             1
#define ELEVATOR_LBN     2
#define CYCLE_LBN        3
#define SSTF_LBN         4
#define ELEVATOR_CYL     5
#define CYCLE_CYL        6
#define SSTF_CYL         7
#define SPTF_OPT         8
#define SPCTF_OPT        9
#define SATF_OPT         10
#define WPTF_OPT         11
#define WPCTF_OPT        12
#define WATF_OPT         13
#define ASPTF_OPT        14
#define ASPCTF_OPT       15
#define ASATF_OPT        16
#define VSCAN_LBN        17
#define VSCAN_CYL        18
#define PRI_VSCAN_LBN    19
#define PRI_ASPTF_OPT    20
#define PRI_ASPCTF_OPT   21
#define SDF_APPROX       22
#define SDF_EXACT        23
#define SPTF_ROT_OPT     24
#define SPTF_ROT_WEIGHT  25
#define SPTF_SEEK_WEIGHT 26
#define TSPS             27
#define MAXSCHED         27

/* Sequential Stream Schemes */

#define IOQUEUE_CONCAT_READS		1
#define IOQUEUE_CONCAT_WRITES		2
#define IOQUEUE_CONCAT_BOTH		3
#define IOQUEUE_SEQSTREAM_READS		4
#define IOQUEUE_SEQSTREAM_WRITES	8
#define IOQUEUE_SEQSTREAM_EITHER	16

/* Sub queue identifications */

#define IOQUEUE_BASE		1
#define IOQUEUE_TIMEOUT		2
#define IOQUEUE_PRIORITY	3

/* Buffer states while in ioqueue */

#define WAITING		0
#define PENDING		1

/* Priority schemes */

#define ALLEQUAL	0
#define TWOQUEUE	1

/* Timeout schemes */

#define NOTIMEOUT	0
#define BASETIMEOUT	1
#define HALFTIMEOUT	2

/* Directions of movement for scanning policies */

#define ASC     1
#define DESC    2

/* read-only globals used during readparams phase */
static char *statdesc_accstats		=	"Physical access time";
static char *statdesc_qtimestats	=	"Queue time";
static char *statdesc_outtimestats	=	"Response time";
static char *statdesc_intarrstats	=	"Inter-arrival time";
static char *statdesc_readintarrstats	=	"Read inter-arrival";
static char *statdesc_writeintarrstats	=	"Write inter-arrival";
static char *statdesc_idlestats	=	"Idle period length";
static char *statdesc_infopenalty	=	"Sub-optimal mapping penalty";
static char *statdesc_reqsizestats	=	"Request size";
static char *statdesc_readsizestats	=	"Read request size";
static char *statdesc_writesizestats	=	"Write request size";
static char *statdesc_instqueuelen	=	"Instantaneous queue length";

typedef struct iob {
   double    starttime;
   int       state;
   struct iob *next;
   struct iob *prev;
   int       totalsize;
   int       devno;
   int       blkno;
   int       flags;
   union {
      struct {
 	 int       waittime;
         ioreq_event *concat;
      } pend;
      double time;
   } iob_un;
   ioreq_event *iolist;
   int       reqcnt;
   int       cylinder;
   int       surface;
   int       opid;
} iobuf;

struct ioq;

typedef struct subq {
   struct ioq *	bigqueue;
   int		sched_alg;
   int		surfoverforw;
   int		force_absolute_fcfs;
   int		(**enablement)(ioreq_event *);
   iobuf *	list;
   iobuf *	current;
   int		prior;
   int		dir;
   double	vscan_value;
   int		vscan_cyls;
   u_int	lastblkno;
   int		lastsurface;
   int		lastcylno;
   int		optcylno;
   int		optsurface;
   int		sstfupdown;
   int		sstfupdowncnt;
   int		numreads;
   int		numwrites;
   int		switches;
   int		maxqlen;
   double	lastalt;
   int		listlen;
   int		iobufcnt;
   int		maxlistlen;
   double	runlistlen;
   int		readlen;
   int		maxreadlen;
   double	runreadlen;
   int		maxwritelen;
   int		numcomplete;
   int		reqoutstanding;
   int		numoutstanding;
   int		maxoutstanding;
   double	runoutstanding;
  int          num_sptf_sdf_different;
  int          num_scheduling_decisions;
   statgen	outtimestats;
   statgen	critreadstats;
   statgen	critwritestats;
   statgen	nocritreadstats;
   statgen	nocritwritestats;
   statgen	qtimestats;
   statgen	accstats;
   statgen	instqueuelen;
   statgen	infopenalty;
} subqueue;

typedef struct ioq {
   subqueue	base;
   subqueue	timeout;
   subqueue	priority;
   int		devno;
   void		(**idlework)(void *,int);
   void	*	idleworkparam;
   int		idledelay;
   timer_event *idledetect;
   int		(**concatok)(void *,int,int,int,int);
   void *	concatokparam;
   int		concatmax;
   int		comboverlaps;
   int		seqscheme;
   int 		seqstreamdiff;
   int		to_scheme;
   int		to_time;
   int		pri_scheme;
   int          priority_mix;
   int		cylmaptype;
   double	writedelay;
   double	readdelay;
   int		sectpercyl;
   int		lastsubqueue;
   int		timeouts;
   int		timeoutreads;
   int		halfouts;
   int		halfoutreads;
   double       idlestart;
   double	lastarr;
   double	lastread;
   double	lastwrite;
   double       latency_weight;
   statgen	idlestats;
   statgen	intarrstats;
   statgen	readintarrstats;
   statgen	writeintarrstats;
   statgen	reqsizestats;
   statgen	readsizestats;
   statgen	writesizestats;
   int		maxlistlen;
   int		maxqlen;
   int		maxoutstanding;
   int		maxreadlen;
   int		maxwritelen;
   int		overlapscombed;
   int		readoverlapscombed;
   int		seqblkno;
   int		seqflags;
   int		seqreads;
   int		seqwrites;
   int		printqueuestats;
   int		printcritstats;
   int		printidlestats;
   int		printintarrstats;
   int		printsizestats;
   char        *name;
} ioqueue;

void ioqueue_print_contents (ioqueue *queue)
{
   int i;
   iobuf *tmp;

   tmp = queue->base.list->next;
   fprintf (outputfile, "Contents of base queue: listlen %d\n", queue->base.listlen);
   for (i = 0; i < queue->base.iobufcnt; i++) {
      fprintf(outputfile, "State: %d, blkno: %d\n", tmp->state, tmp->blkno);
      tmp = tmp->next;
   }

   tmp = queue->timeout.list->next;
   fprintf(outputfile, "Contents of timeout queue: listlen %d\n", queue->timeout.listlen);
   for (i = 0; i < queue->timeout.iobufcnt; i++) {
      fprintf(outputfile, "State: %d, blkno: %d\n", tmp->state, tmp->blkno);
      tmp = tmp->next;
   }

   tmp = queue->priority.list->next;
   fprintf(outputfile, "Contents of priority queue: listlen %d\n", queue->priority.listlen);
   for (i = 0; i < queue->priority.iobufcnt; i++) {
      fprintf(outputfile, "State: %d, blkno: %d\n", tmp->state, tmp->blkno);
      tmp = tmp->next;
   }
}


static void ioqueue_print_subqueue_state (subqueue *queue)
{
   int i;
   iobuf *tmp;

   tmp = queue->list->next;
   fprintf(outputfile, "\nContents of subqueue: listlen %d\n", queue->listlen);
   fprintf(outputfile, "Subqueue state: lastblkno %d, lastcylno %d, lastsurface %d, dir %d\n", queue->lastblkno, queue->lastcylno, queue->lastsurface, queue->dir);
   for (i = 0; i < queue->iobufcnt; i++) {
      fprintf(outputfile, "State: %d, blkno: %d, cylno %d, surface %d\n", tmp->state, tmp->blkno, tmp->cylinder, tmp->surface);
      tmp = tmp->next;
   }
}


int ioqueue_get_number_in_queue (ioqueue *queue)
{
   return(queue->base.listlen + queue->timeout.listlen + queue->priority.listlen);
}


int ioqueue_get_number_pending (ioqueue *queue)
{
   int numpend = 0;

   numpend += queue->base.listlen - queue->base.numoutstanding;
   numpend += queue->timeout.listlen - queue->timeout.numoutstanding;
   numpend += queue->priority.listlen - queue->priority.numoutstanding;
   return(numpend);
}


int ioqueue_get_reqoutstanding (ioqueue *queue)
{
   int numout = 0;

   numout += queue->base.reqoutstanding;
   numout += queue->timeout.reqoutstanding;
   numout += queue->priority.reqoutstanding;
   return(numout);
}


int ioqueue_get_number_of_requests (ioqueue *queue)
{
   int numreqs = 0;

   numreqs += queue->base.numcomplete + queue->base.listlen;
   numreqs += queue->timeout.numcomplete + queue->timeout.listlen;
   numreqs += queue->priority.numcomplete + queue->priority.listlen;
   return(numreqs);
}


int ioqueue_get_number_of_requests_initiated (ioqueue *queue)
{
   int numreqs = 0;

   numreqs += queue->base.numcomplete + queue->base.numoutstanding;
   numreqs += queue->timeout.numcomplete + queue->timeout.numoutstanding;
   numreqs += queue->priority.numcomplete + queue->priority.numoutstanding;
   return(numreqs);
}


int ioqueue_get_dist (ioqueue *queue, int blkno)
{
   int lastblkno;

   if (queue->lastsubqueue == IOQUEUE_BASE) {
      lastblkno = queue->base.lastblkno;
   } else if (queue->lastsubqueue == IOQUEUE_TIMEOUT) {
      lastblkno = queue->timeout.lastblkno;
   } else if (queue->lastsubqueue == IOQUEUE_PRIORITY) {
      lastblkno = queue->priority.lastblkno;
   } else {
      fprintf(stderr, "Unknown queue identification at ioqueue_get_dist - %d\n", queue->lastsubqueue);
      exit(1);
   }
   return(abs(blkno - lastblkno));
}


static void 
ioqueue_get_cylinder_mapping(ioqueue *queue, 
			     iobuf *curr, 
			     int blkno, 
			     int *cylptr, 
			     int *surfptr, 
			     int cylmaptype)
{
   cylmaptype = (cylmaptype == -1) ? queue->cylmaptype : cylmaptype;
   switch (cylmaptype) {
      case MAP_NONE:
         *cylptr = 0;