1 /* $NetBSD: rf_cvscan.h,v 1.4 2002/09/21 00:37:14 oster Exp $ */ 2 /* 3 * Copyright (c) 1995 Carnegie-Mellon University. 4 * All rights reserved. 5 * 6 * Author: Mark Holland 7 * 8 * Permission to use, copy, modify and distribute this software and 9 * its documentation is hereby granted, provided that both the copyright 10 * notice and this permission notice appear in all copies of the 11 * software, derivative works or modified versions, and any portions 12 * thereof, and that both notices appear in supporting documentation. 13 * 14 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" 15 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND 16 * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. 17 * 18 * Carnegie Mellon requests users of this software to return to 19 * 20 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU 21 * School of Computer Science 22 * Carnegie Mellon University 23 * Pittsburgh PA 15213-3890 24 * 25 * any improvements or extensions that they make and grant Carnegie the 26 * rights to redistribute these changes. 27 */ 28 29 /* 30 ** Disk scheduling by CVSCAN( N, r ) 31 ** 32 ** Given a set of requests, partition them into one set on each 33 ** side of the current arm position. The trick is to pick which 34 ** side you are going to service next; once a side is picked you will 35 ** service the closest request. 36 ** Let there be n1 requests on one side and n2 requests on the other 37 ** side. If one of n1 or n2 is zero, select the other side. 38 ** If both n1 and n2 are nonzero, select a "range" for examination 39 ** that is N' = min( n1, n2, N ). Average the distance from the 40 ** current position to the nearest N' requests on each side giving 41 ** d1 and d2. 42 ** Suppose the last decision was to move toward set 2, then the 43 ** current direction is toward set 2, and you will only switch to set 44 ** 1 if d1+R < d2 where R is r*(total number of cylinders), r in [0,1]. 45 ** 46 ** I extend this by applying only to the set of requests that all 47 ** share the same, highest priority level. 48 */ 49 50 #ifndef _RF__RF_CVSCAN_H_ 51 #define _RF__RF_CVSCAN_H_ 52 53 #include "rf_diskqueue.h" 54 55 typedef enum RF_CvscanArmDir_e { 56 rf_cvscan_LEFT, 57 rf_cvscan_RIGHT 58 } RF_CvscanArmDir_t; 59 60 typedef struct RF_CvscanHeader_s { 61 long range_for_avg; /* CVSCAN param N */ 62 long change_penalty; /* CVSCAN param R */ 63 RF_CvscanArmDir_t direction; 64 RF_SectorNum_t cur_block; 65 int nxt_priority; 66 RF_DiskQueueData_t *left; 67 int left_cnt; 68 RF_DiskQueueData_t *right; 69 int right_cnt; 70 RF_DiskQueueData_t *burner; 71 } RF_CvscanHeader_t; 72 73 void * 74 rf_CvscanCreate(RF_SectorCount_t sect_per_disk, 75 RF_AllocListElem_t * cl_list, RF_ShutdownList_t ** listp); 76 void rf_CvscanEnqueue(void *qptr, RF_DiskQueueData_t * req, int priority); 77 RF_DiskQueueData_t *rf_CvscanDequeue(void *qptr); 78 RF_DiskQueueData_t *rf_CvscanPeek(void *qptr); 79 int 80 rf_CvscanPromote(void *qptr, RF_StripeNum_t parityStripeID, 81 RF_ReconUnitNum_t which_ru); 82 83 #endif /* !_RF__RF_CVSCAN_H_ */ 84