1/** 2 * \file 3 * \brief Scheduler system simulator 4 */ 5 6/* 7 * Copyright (c) 2007, 2008, 2009, 2010, ETH Zurich. 8 * All rights reserved. 9 * 10 * This file is distributed under the terms in the attached LICENSE file. 11 * If you do not find this file, copies can be found by writing to: 12 * ETH Zurich D-INFK, Haldeneggsteig 4, CH-8092 Zurich. Attn: Systems Group. 13 */ 14 15#include <stdlib.h> 16#include <stdbool.h> 17#include <assert.h> 18#include <stdio.h> 19#include <stdarg.h> 20#include <stdint.h> 21#include <sys/param.h> 22 23 24/***** Prerequisite definitions copied from Barrelfish headers *****/ 25 26#define trace_event(x,y,z) 27 28#define DISP_NAME_LEN 16 29 30enum task_type { 31 TASK_TYPE_BEST_EFFORT, 32 TASK_TYPE_SOFT_REALTIME, 33 TASK_TYPE_HARD_REALTIME 34}; 35 36enum objtype { 37 ObjType_L1CNode, 38 ObjType_EndPoint 39}; 40 41struct capability { 42 enum objtype type; 43}; 44 45struct cte { 46 struct capability cap; 47}; 48 49typedef uintptr_t dispatcher_handle_t; 50 51struct dispatcher_shared_generic { 52 char name[DISP_NAME_LEN];///< Name of domain, for debugging purposes 53}; 54 55struct dcb { 56 dispatcher_handle_t disp; 57 struct cte cspace; 58 struct cte ep; 59 size_t vspace; 60 struct dcb *next; ///< Next DCB in schedule 61 unsigned long release_time, etime, last_dispatch; 62 unsigned long wcet, period, deadline; 63 unsigned short weight; 64 enum task_type type; 65 66 // Simulator state 67 int id; 68 bool dispatched; 69 unsigned long blocktime; 70 struct dispatcher_shared_generic dsg; 71}; 72 73struct kcb { 74 struct kcb *prev, *next; 75 struct dcb *queue_head, *queue_tail; 76 unsigned int u_hrt, u_srt, w_be, n_be; 77} curr = { 0, 0, 0, 0, 0, 0, 0, 0 }; 78struct kcb *kcb_current = &curr; 79 80 81static void panic(const char *msg, ...) 82{ 83 va_list ap; 84 85 fprintf(stderr, "Scheduler panic: "); 86 va_start(ap, msg); 87 vfprintf(stderr, msg, ap); 88 va_end(ap); 89 fprintf(stderr, "\n"); 90 91 exit(EXIT_FAILURE); 92} 93 94static __attribute__ ((unused)) struct dispatcher_shared_generic * 95get_dispatcher_shared_generic(dispatcher_handle_t handle) 96{ 97 return (struct dispatcher_shared_generic *)handle; 98} 99 100typedef uint64_t systime_t; 101#define systime_now() kernel_now 102static size_t kernel_now = 0; 103static int kernel_timeslice = 80; 104static struct dcb *dcb_current = NULL; 105 106/***** Including scheduler C file *****/ 107 108#include "../../kernel/schedule_rbed.c" 109 110/***** Simulator internal definitions *****/ 111 112#define MAXTASKS 10 113 114static struct dcb *sched, **allptrs; 115 116static void init_dcb(struct dcb *dcb, int id) 117{ 118 dcb->disp = (uintptr_t)&dcb->dsg; 119 dcb->cspace.cap.type = ObjType_L1CNode; 120 dcb->ep.cap.type = ObjType_EndPoint; 121 dcb->vspace = 1; 122 dcb->next = NULL; 123 dcb->release_time = 0; 124 dcb->wcet = 0; 125 dcb->period = 0; 126 dcb->weight = 0; 127 dcb->etime = 0; 128 129 dcb->id = id; 130 snprintf(dcb->dsg.name, DISP_NAME_LEN, "%d", id); 131} 132 133static inline char typechar(enum task_type type) 134{ 135 switch(type) { 136 case TASK_TYPE_HARD_REALTIME: 137 return 'h'; 138 139 case TASK_TYPE_SOFT_REALTIME: 140 return 's'; 141 142 case TASK_TYPE_BEST_EFFORT: 143 return 'b'; 144 145 default: 146 printf("unknown task type!\n"); 147 abort(); 148 break; 149 } 150} 151 152int main(int argc, char **argv) 153{ 154 int tasks = 0, alltasks = MAXTASKS, runtime, quantum = 1; 155 156 if(argc < 3) { 157 printf("Usage: %s <config.cfg> <runtime> [quantum]\n", argv[0]); 158 exit(EXIT_FAILURE); 159 } 160 161 runtime = atoi(argv[2]); 162 if(argc >= 4) { 163 quantum = atoi(argv[3]); 164 } 165 166 sched = malloc(sizeof(struct dcb) * runtime * alltasks); 167 allptrs = calloc(alltasks, sizeof(struct dcb *)); 168 169 FILE *f = fopen(argv[1], "r"); 170 assert(f != NULL); 171 bool readline = true; 172 173 for(kernel_now = 0; kernel_now < runtime; kernel_now++) { 174 unsigned long time, wcet, period, weight, id, blocktime, deadline, rd; 175 char b[512], *r; 176 177 for(;;) { 178 if(readline) { 179 do { 180 r = fgets(b, 512, f); 181 } while(r != NULL && (b[0] == '#' || b[0] == '\n')); 182 183 if(r == NULL) { 184 break; 185 } 186 } else { 187 readline = true; 188 } 189 190 if((rd = sscanf(b, "%lu H %lu %lu %lu %lu", &time, &wcet, &period, &blocktime, &deadline)) >= 4) { 191 if(time != kernel_now) { readline = false; break; } 192 // Create new hard real-time task 193 struct dcb *dcb = malloc(sizeof(struct dcb)); 194 init_dcb(dcb, tasks); 195 dcb->type = TASK_TYPE_HARD_REALTIME; 196 dcb->wcet = wcet; 197 dcb->period = period; 198 dcb->blocktime = blocktime; 199 dcb->release_time = kernel_now; 200 snprintf(dcb->dsg.name, DISP_NAME_LEN, "h %d", tasks); 201 if(rd == 5) { 202 dcb->deadline = deadline; 203 } else { 204 dcb->deadline = period; 205 } 206 make_runnable(dcb); 207 assert(tasks < MAXTASKS); 208 allptrs[tasks++] = dcb; 209 } else if(sscanf(b, "%lu S %lu %lu", &time, &wcet, &period) == 3) { 210 if(time != kernel_now) { readline = false; break; } 211 // Create new soft real-time task 212 struct dcb *dcb = malloc(sizeof(struct dcb)); 213 init_dcb(dcb, tasks); 214 dcb->type = TASK_TYPE_SOFT_REALTIME; 215 dcb->wcet = wcet; 216 dcb->period = period; 217 snprintf(dcb->dsg.name, DISP_NAME_LEN, "s %d", tasks); 218 make_runnable(dcb); 219 assert(tasks < MAXTASKS); 220 allptrs[tasks++] = dcb; 221 } else if(sscanf(b, "%lu B %lu", &time, &weight) == 2) { 222 if(time != kernel_now) { readline = false; break; } 223 // Create new best-effort task 224 struct dcb *dcb = malloc(sizeof(struct dcb)); 225 init_dcb(dcb, tasks); 226 dcb->type = TASK_TYPE_BEST_EFFORT; 227 dcb->weight = weight; 228 snprintf(dcb->dsg.name, DISP_NAME_LEN, "b %d", tasks); 229 make_runnable(dcb); 230 assert(tasks < MAXTASKS); 231 allptrs[tasks++] = dcb; 232 } else if(sscanf(b, "%lu d %lu", &time, &id) == 2) { 233 if(time != kernel_now) { readline = false; break; } 234 // Delete task with given ID 235 assert(id < MAXTASKS); 236 scheduler_remove(allptrs[id]); 237 } else if(sscanf(b, "%lu r %lu", &time, &id) == 2) { 238 if(time != kernel_now) { readline = false; break; } 239 // Re-release task with given ID 240 assert(id < MAXTASKS); 241 if(allptrs[id]->type != TASK_TYPE_BEST_EFFORT) { 242 allptrs[id]->release_time = kernel_now; 243 } 244 make_runnable(allptrs[id]); 245 } else if(sscanf(b, "%lu y %lu", &time, &id) == 2) { 246 if(time != kernel_now) { readline = false; break; } 247 // Yield task with given ID 248 assert(id < MAXTASKS); 249 scheduler_yield(allptrs[id]); 250 } else if(sscanf(b, "%lu c %lu", &time, &id) == 2) { 251 if(time != kernel_now) { readline = false; break; } 252 // Context switch to task with given ID 253 assert(id < MAXTASKS); 254 dcb_current = allptrs[id]; 255 continue; 256 } else { 257 fprintf(stderr, "Invalid line: %s\n", b); 258 abort(); 259 } 260 261 dcb_current = schedule(); 262 } 263 264 for(int i = 0; i < alltasks; i++) { 265 struct dcb *cd = allptrs[i]; 266 if(cd != NULL) { 267 cd->dispatched = false; 268 269#if 0 270 if(cd->type == TASK_TYPE_HARD_REALTIME) { 271 if(cd->etime >= cd->blocktime) { 272 scheduler_remove(cd); 273 } 274 } 275#endif 276 } 277 } 278 279 if(kernel_now % quantum == 0) { 280 dcb_current = schedule(); 281 } 282 283 if(dcb_current != NULL) { 284 dcb_current->dispatched = true; 285 286 /* printf("%4d: dispatching %2d, release time: %4lu, deadline: %4lu, period: %3lu, WCET: %3lu/%3lu\n", kernel_now, dcb_current->id, dcb_current->release_time, dcb_current->deadline, dcb_current->period, dcb_current->etime, dcb_current->wcet); */ 287 } 288 for(int i = 0; i < alltasks; i++) { 289 if(allptrs[i] != NULL) { 290 sched[kernel_now * alltasks + i] = *allptrs[i]; 291 } 292 } 293 } 294 295 fclose(f); 296 297 // Print schedule 298 printf(" "); 299 for(int t = 0; t < runtime; t++) { 300 if(t % 1000 == 0) { 301 printf("%d", (t / 1000) % 10); 302 } else { 303 printf(" "); 304 } 305 } 306 printf("\n"); 307 printf(" "); 308 for(int t = 0; t < runtime; t++) { 309 if(t % 100 == 0) { 310 printf("%d", (t / 100) % 10); 311 } else { 312 printf(" "); 313 } 314 } 315 printf("\n"); 316 printf(" "); 317 for(int t = 0; t < runtime; t++) { 318 if(t % 10 == 0) { 319 printf("%d", (t / 10) % 10); 320 } else { 321 printf(" "); 322 } 323 } 324 printf("\n"); 325 326 printf(" "); 327 for(int t = 0; t < runtime; t++) { 328 printf("%d", t % 10); 329 } 330 printf("\n"); 331 332 for(int i = 0; i < tasks; i++) { 333 struct dcb *ct = allptrs[i]; 334 printf("%c%2d: ", typechar(ct->type), i); 335 for(int t = 0; t < runtime; t++) { 336 struct dcb *s = &sched[t * alltasks + i]; 337 338 if(s->dispatched) { 339 printf("#"); 340 } else { 341 printf(" "); 342 } 343 } 344 printf("\n"); 345 printf(" "); 346 for(int t = 0; t < runtime; t++) { 347 struct dcb *s = &sched[t * alltasks + i]; 348 349 if(s->release_time == t) { 350 printf("r"); 351 } else { 352 printf(" "); 353 } 354 } 355 printf("\n"); 356 } 357 358 free(sched); 359 free(allptrs); 360 return 0; 361} 362