disksim_ioqueue.c

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

   schedalg = queue->bigqueue->timeout.sched_alg;
   priority_factor = queue->bigqueue->priority.sched_alg;
   age_factor = queue->bigqueue->to_time;
   if (schedalg == ELEVATOR_LBN) {
      vscan_value = numlbns;
   } else if (schedalg == SSTF_LBN) {
      vscan_value = 0;
   }
   tmp = queue->list->next;
   for (i = 0; i < queue->iobufcnt; i++) {
      if (READY_TO_GO(tmp,queue)) {
	 curr_effpri = tmp->blkno - queue->lastblkno;
	 if (schedalg == CYCLE_LBN) {
	    if (curr_effpri < 0) {
	       curr_effpri += numlbns;
	    }
	 } else if (curr_effpri) {
	    if (curr_effpri < 0) {
	       curr_effpri = -curr_effpri;
	       if (queue->dir == ASC) {
		  curr_effpri += vscan_value;
	       }
	    } else {
	       if (queue->dir == DESC) {
		  curr_effpri += vscan_value;
	       }
	    }
	 }
	 curr_effpri = numlbns - curr_effpri;
	 curr_effpri += (priority_factor * numlbns * ioqueue_get_priority_level(queue->bigqueue, tmp)) / 100;
	 curr_effpri += (age_factor * (int) (simtime - tmp->starttime)) / 1280;
	 if ((ret == NULL) || (curr_effpri > best_effpri)) {
	    ret = tmp;
	    best_effpri = curr_effpri;
	 }
      }
      tmp = tmp->next;
   }
   return(ret);
}


/* Queue contains >= 2 items when called */

static iobuf * ioqueue_get_request_from_lbn_scan_queue (subqueue *queue)
{
   iobuf *temp;
   iobuf *stop;

   temp = queue->list->next;
   stop = temp;
   if (queue->lastblkno > temp->blkno) {
      while ((temp->next != stop) && (queue->lastblkno > temp->next->blkno)) {
         temp = temp->next;
      }
      temp = temp->next;
   }
   stop = temp;
   while ((temp->next != stop) && !READY_TO_GO(temp,queue)) {
      temp = temp->next;
   }
   if ((temp->next == stop) && !READY_TO_GO(temp,queue)) {
      temp = NULL;
   }
   return(temp);
}


/* Queue contains >= 2 items when called */

static iobuf * ioqueue_get_request_from_lbn_vscan_queue (subqueue *queue, int value)
{
   iobuf *temp;
   iobuf *head;
   iobuf *top = NULL;
   iobuf *bottom = NULL;
   int diff1, diff2;
   int tmpdir;
   iobuf *bestbottom;

   tmpdir = queue->dir;
   temp = queue->list->next;
   head = queue->list->next;

   while ((temp->next != head) && (queue->lastblkno > temp->next->blkno)) {
      temp = temp->next;
   }
   if (temp->blkno < queue->lastblkno) {
      bottom = temp;
      while ((bottom != head) && !READY_TO_GO(bottom,queue)) {
         bottom = bottom->prev;
      }
      if ((bottom == head) && !READY_TO_GO(bottom,queue)) {
	 bottom = NULL;
      } else {
         bestbottom = bottom;
         while ((bottom != head) && ((bottom->prev->blkno == bestbottom->blkno) || (!(ioqueue_seqstream_head(queue->bigqueue, head, bottom))))) {
	    bottom = bottom->prev;
	    bestbottom = (READY_TO_GO(bottom,queue)) ? bottom : bestbottom;
         }
         bottom = bestbottom;
      }
   }
   if (temp->next != head) {
      if (temp->blkno >= queue->lastblkno) {
	 top = temp;
      } else {
         top = temp->next;
      }
      while ((top->next != head) && !READY_TO_GO(top,queue)) {
         top = top->next;
      }
   }
   if ((top == NULL) || !READY_TO_GO(top,queue) || (!(ioqueue_seqstream_head(queue->bigqueue, head, top)))) {
      temp = bottom;
   } else if ((bottom == NULL) || !READY_TO_GO(bottom,queue)) {
      temp = top;
   } else {
      diff1 = diff(top->blkno, queue->lastblkno);
      diff2 = diff(queue->lastblkno, bottom->blkno);
      if (queue->dir == ASC) {
	 diff2 = (diff2) ? (diff2 + value) : diff2;
      } else {
	 diff1 = (diff1) ? (diff1 + value) : diff1;
      }
      if (diff1 < diff2) {
         temp = top;
      } else if ((diff1 > diff2) || (queue->sstfupdown)) {
         temp = bottom;
      } else {
	 temp = top;
      }
      if (diff1 == diff2) {
	 queue->sstfupdown = (queue->sstfupdown) ? 0 : 1;
	 queue->sstfupdowncnt++;
      }
   }
   if (temp->blkno != queue->lastblkno) {
      queue->dir = (temp->blkno > queue->lastblkno) ? ASC : DESC;
   }
   top = (temp == top) ? bottom : top;
   if ((top) && READY_TO_GO(top,queue)) {
      int cylno1, cylno2;
      int surface1, surface2;

      ioqueue_get_cylinder_mapping(queue->bigqueue, temp, temp->blkno, &cylno1, &surface1, MAP_FULL);
      ioqueue_get_cylinder_mapping(queue->bigqueue, top, top->blkno, &cylno2, &surface2, MAP_FULL);
      diff1 = abs(cylno1 - queue->optcylno);
      diff2 = abs(cylno2 - queue->optcylno);
      if (((tmpdir == ASC) && (temp != bottom)) || ((tmpdir == DESC) && (temp == bottom))) {
	 if (diff2) {
	    diff2 += (int) (queue->vscan_value * (double) device_get_numcyls(temp->iolist->devno));
	 }
      } else if (diff1) {
	 if (diff1) {
	    diff1 += (int) (queue->vscan_value * (double) device_get_numcyls(temp->iolist->devno));
	 }
      }
      if (diff1 > diff2) {
         stat_update(&queue->infopenalty, (double) (diff1 - diff2));
/*
fprintf (outputfile, "diff1 %d, diff2 %d, diffdiff %d\n", diff1, diff2, (diff1 - diff2));
*/
      } else if ((diff1 == diff2) && (diff1 == 0)) {
         if ((queue->optsurface == surface2) && (surface1 != surface2)) {
            stat_update(&queue->infopenalty, (double) 0);
         }
      }
   }
   return(temp);
}


/* Queue contains >= 2 items when called */

/* Returns pointer to "best" request on queue->lastcylno, or first request
   on next available forward cylinder, or head (in priority order). */

static iobuf *ioqueue_identify_request_on_cylinder (subqueue *queue)
{
   iobuf *temp;
   iobuf *head;
   iobuf *cylstop;
   iobuf *surfstop;

   int lastcylno;
   int lastsurface;
   int lastblkno;

   lastcylno = queue->lastcylno;
   lastsurface = queue->lastsurface;
   lastblkno = queue->lastblkno;

   head = queue->list->next;
   temp = head;

   if ((head->cylinder < lastcylno) && (lastcylno <= queue->list->cylinder)) {
      while ((temp->next != head) && (lastcylno > temp->next->cylinder)) {
         temp = temp->next;
      }
      temp = temp->next;
   }

   if (temp->cylinder != lastcylno) {
      return(temp);
   }

   cylstop = temp;      /* first req on cylinder */

   while ((temp->next != head) && (lastcylno == temp->next->cylinder) && (lastsurface > temp->surface)) {
      temp = temp->next;
   }

   if (lastsurface > temp->surface) {
      temp = cylstop;   /* drop out and try from first req on cylinder */

   } else if (!queue->surfoverforw) {
      while ((temp->next != head) && (lastcylno == temp->next->cylinder) && (!READY_TO_GO(temp,queue) || (temp->blkno < lastblkno))) {
         temp = temp->next;
      }
      if (READY_TO_GO(temp,queue) && (temp->blkno >= lastblkno)) {
        return(temp);
      } else {
         temp = cylstop;   /* drop out and try from first req on cylinder */
      }

   } else {    /* surfoverforw */

      surfstop = temp;     /* first req on surface */

      while ((temp->next != head) && (lastcylno == temp->next->cylinder) && (lastsurface == temp->next->surface) && (!READY_TO_GO(temp,queue) || (temp->blkno < lastblkno))) {
         temp = temp->next;
      }
      if (READY_TO_GO(temp,queue) && (temp->blkno >= lastblkno) && (temp->surface == lastsurface)) {
         return(temp);
      }

      temp = surfstop;

      while ((temp->next != head) && (lastcylno == temp->next->cylinder) && !READY_TO_GO(temp,queue)) {
         temp = temp->next;
      }
      if (READY_TO_GO(temp,queue)) {
         return(temp);
      }

      temp = cylstop;   /* drop out and try from first req on cylinder */
   }

   /* drop out recovery point */

   if (!READY_TO_GO(temp,queue)) {
      while (!READY_TO_GO(temp,queue) && (temp->next != head) && (temp->next->cylinder == lastcylno)) {
         temp = temp->next;
      }
      temp = temp->next;
   }
   return(temp);
}


/* Queue contains >= 2 items when called */

static iobuf * ioqueue_get_request_from_cyl_scan_queue (subqueue *queue)
{
   iobuf *temp;
   iobuf *stop;

   temp = queue->list->next;
   if (queue->lastcylno >= temp->cylinder) {
      temp = ioqueue_identify_request_on_cylinder(queue);
   }
   stop = temp;
   while (!READY_TO_GO(temp,queue) && (temp->next != stop)) {
      temp = temp->next;
   }
   if ((temp->next == stop) && !READY_TO_GO(temp,queue)) {
      temp = NULL;
   }
   return(temp);
}


/* Queue contains >= 2 items when called */

static iobuf * ioqueue_get_request_from_cyl_vscan_queue (subqueue *queue, int value)
{
   iobuf *temp;
   iobuf *head;
   iobuf *top = NULL;
   iobuf *bottom = NULL;
   iobuf *bottom2 = NULL;
   iobuf *bestone;
   int diff1, diff2, diff3;
   int tmpdir;
   int cylno1, cylno2, cylno3;
   int surface1, surface2, surface3;

   tmpdir = queue->dir;
   temp = queue->list->next;
   head = queue->list->next;

   bestone = ioqueue_identify_request_on_cylinder(queue);
   if (!READY_TO_GO(bestone,queue) || (bestone->cylinder != queue->lastcylno)) {
      bestone = NULL;
   }
   while ((temp->next != head) && (queue->lastblkno > temp->next->blkno)) {
      temp = temp->next;
   }
   if (temp->blkno < queue->lastblkno) {
      bottom = temp;
      while ((bottom != head) && !READY_TO_GO(bottom,queue)) {
         bottom = bottom->prev;
      }
      bottom2 = temp;
      if (READY_TO_GO(bottom,queue) && (!bestone)) {
         while ((bottom != head) && (bottom->prev->cylinder == bottom->cylinder)) {
	    bottom = bottom->prev;
         }
         while ((bottom != temp) && !READY_TO_GO(bottom,queue)) {
	    bottom = bottom->next;
         }
      }
   }
   if (temp->next != head) {
      top = (temp->blkno >= queue->lastblkno) ? temp : temp->next;
      while ((top->next != head) && !READY_TO_GO(top,queue)) {
         top = top->next;
      }
   }
   if (!bestone) {
      if ((top == NULL) || !READY_TO_GO(top,queue)) {
         temp = bottom;
      } else if ((bottom == NULL) || !READY_TO_GO(bottom,queue)) {
         temp = top;
      } else {
         diff1 = diff(top->cylinder, queue->lastcylno);
         diff2 = diff(queue->lastcylno, bottom->cylinder);
         if (queue->dir == ASC) {
	    diff2 += value;
         } else {
	    diff1 += value;
         }
         if (diff1 < diff2) {
	    temp = top;
         } else if ((diff1 > diff2) || (queue->sstfupdown)) {
            temp = bottom;
         } else {
	    temp = top;
         }
         if (diff1 == diff2) {
	    queue->sstfupdown = (queue->sstfupdown) ? 0 : 1;
	    queue->sstfupdowncnt++;
         }
      }
   } else {
      temp = bestone;
   }
   if (temp->cylinder != queue->lastcylno) {
      queue->dir = (temp->cylinder > queue->lastcylno) ? ASC : DESC;
   }
   ioqueue_get_cylinder_mapping(queue->bigqueue, temp, temp->blkno, &cylno1, &surface1, MAP_FULL);
   diff1 = abs(cylno1 - queue->optcylno);
   if ((top == NULL) || !READY_TO_GO(top,queue)) {
      top = temp;
   }
   ioqueue_get_cylinder_mapping(queue->bigqueue, top, top->blkno, &cylno2, &surface2, MAP_FULL);
   diff2 = abs(cylno2 - queue->optcylno);
   if ((bottom2 == NULL) || !READY_TO_GO(bottom2,queue)) {
      bottom2 = temp;
   }
   ioqueue_get_cylinder_mapping(queue->bigqueue, bottom2, bottom2->blkno, &cylno3, &surface3, MAP_FULL);
   diff3 = abs(cylno3 - queue->optcylno);
   if (tmpdir == ASC) {
      diff3 = (diff3) ? (diff3 + value) : diff3;
      diff1 = (temp->cylinder < queue->lastcylno) ? (diff1 + value) : diff1;
   } else {
      diff2 = (diff2) ? (diff2 + value) : diff2;
      diff1 = (temp->cylinder > queue->lastcylno) ? (diff1 + value) : diff1;
   }
   if ((diff3 < diff2) || ((!diff3) && (surface3 == queue->optsurface))) {
      surface2 = surface3;
      diff2 = diff3;
   }
   if (diff1 > diff2) {
      stat_update(&queue->infopenalty, (double) (diff1 - diff2));
/*
fprintf (outputfile, "diff1 %d, diff2 %d, diffdiff %d, value %d\n", diff1, diff2, (diff1 - diff2), value);
*/
   } else if ((diff1 == diff2) && (diff1 == 0)) {
      if ((queue->optsurface == surface2) && (surface1 != surface2)) {
         stat_update(&queue->infopenalty, (double) 0);
      }
   }
   return(temp);
}


/* Queue contains >= 2 items when called */

static iobuf *ioqueue_get_request_from_opt_sptf_queue (subqueue *queue, int checkcache, int ageweight, int posonly)
{
   int i;
   iobuf *temp;
   iobuf *best = NULL;
   ioreq_event *test;
   double mintime = 100000.0;
   double readdelay;
   double writedelay;
   double delay;
   double weight;
   double temp_delay;
   ioreq_event *tmp;

   double age = 0.0;



   ASSERT((ageweight >= 0) && (ageweight <= 3));
   readdelay = queue->bigqueue->readdelay;
   writedelay = queue->bigqueue->writedelay;
   weight = (double) queue->bigqueue->to_time;
   test = (ioreq_event *) getfromextraq();
   temp = queue->list->next;

   //fprintf(outputfile, "get_request_from_sptf::  listlen = %d\n", queue->listlen);

   for (i=0; i<queue->listlen; i++) {

      if (READY_TO_GO(temp,queue) && (ioqueue_seqstream_head(queue->bigqueue, queue->list->next, temp))) {
	 test->blkno = temp->blkno;
	 test->bcount = temp->totalsize;
         test->devno = temp->iolist->devno;
         test->flags = temp->flags;
	 delay = (temp->flags & READ) ? readdelay : writedelay;
	 test->time = simtime + delay;
	 if (ageweight) {
	    tmp = temp->iolist;
	    age = tmp->time;
	    while (tmp) {
	       if (tmp->time < age) {
		  age = tmp->time;
	       }
	       tmp = tmp->next;
	    }
	    age = simtime - age;
	 }
	 if ((ageweight == 2) || 
	     ((ageweight == 3) && 
	      (test->flags & (TIME_CRITICAL | TIME_LIMITED)))) {
	    delay -= age * weight * (double) 0.001;
         }