1 // Copyright 2006-2008 the V8 project authors. All rights reserved. 2 // Redistribution and use in source and binary forms, with or without 3 // modification, are permitted provided that the following conditions are 4 // met: 5 // 6 // * Redistributions of source code must retain the above copyright 7 // notice, this list of conditions and the following disclaimer. 8 // * Redistributions in binary form must reproduce the above 9 // copyright notice, this list of conditions and the following 10 // disclaimer in the documentation and/or other materials provided 11 // with the distribution. 12 // * Neither the name of Google Inc. nor the names of its 13 // contributors may be used to endorse or promote products derived 14 // from this software without specific prior written permission. 15 // 16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28 29 // This is a JavaScript implementation of the Richards 30 // benchmark from: 31 // 32 // http://www.cl.cam.ac.uk/~mr10/Bench.html 33 // 34 // The benchmark was originally implemented in BCPL by 35 // Martin Richards. 36 37 38 /** 39 * The Richards benchmark simulates the task dispatcher of an 40 * operating system. 41 **/ 42 function runRichards() { 43 var scheduler = new Scheduler(); 44 scheduler.addIdleTask(ID_IDLE, 0, null, COUNT); 45 46 var queue = new Packet(null, ID_WORKER, KIND_WORK); 47 queue = new Packet(queue, ID_WORKER, KIND_WORK); 48 scheduler.addWorkerTask(ID_WORKER, 1000, queue); 49 50 queue = new Packet(null, ID_DEVICE_A, KIND_DEVICE); 51 queue = new Packet(queue, ID_DEVICE_A, KIND_DEVICE); 52 queue = new Packet(queue, ID_DEVICE_A, KIND_DEVICE); 53 scheduler.addHandlerTask(ID_HANDLER_A, 2000, queue); 54 55 queue = new Packet(null, ID_DEVICE_B, KIND_DEVICE); 56 queue = new Packet(queue, ID_DEVICE_B, KIND_DEVICE); 57 queue = new Packet(queue, ID_DEVICE_B, KIND_DEVICE); 58 scheduler.addHandlerTask(ID_HANDLER_B, 3000, queue); 59 60 scheduler.addDeviceTask(ID_DEVICE_A, 4000, null); 61 62 scheduler.addDeviceTask(ID_DEVICE_B, 5000, null); 63 64 scheduler.schedule(); 65 66 if (scheduler.queueCount != EXPECTED_QUEUE_COUNT || 67 scheduler.holdCount != EXPECTED_HOLD_COUNT) { 68 var msg = 69 "Error during execution: queueCount = " + scheduler.queueCount + 70 ", holdCount = " + scheduler.holdCount + "."; 71 throw new Error(msg); 72 } 73 } 74 75 var COUNT = 1000; 76 77 /** 78 * These two constants specify how many times a packet is queued and 79 * how many times a task is put on hold in a correct run of richards. 80 * They don't have any meaning a such but are characteristic of a 81 * correct run so if the actual queue or hold count is different from 82 * the expected there must be a bug in the implementation. 83 **/ 84 var EXPECTED_QUEUE_COUNT = 2322; 85 var EXPECTED_HOLD_COUNT = 928; 86 87 88 /** 89 * A scheduler can be used to schedule a set of tasks based on their relative 90 * priorities. Scheduling is done by maintaining a list of task control blocks 91 * which holds tasks and the data queue they are processing. 92 * @constructor 93 */ 94 function Scheduler() { 95 this.queueCount = 0; 96 this.holdCount = 0; 97 this.blocks = new Array(NUMBER_OF_IDS); 98 this.list = null; 99 this.currentTcb = null; 100 this.currentId = null; 101 } 102 103 var ID_IDLE = 0; 104 var ID_WORKER = 1; 105 var ID_HANDLER_A = 2; 106 var ID_HANDLER_B = 3; 107 var ID_DEVICE_A = 4; 108 var ID_DEVICE_B = 5; 109 var NUMBER_OF_IDS = 6; 110 111 var KIND_DEVICE = 0; 112 var KIND_WORK = 1; 113 114 /** 115 * Add an idle task to this scheduler. 116 * @param {int} id the identity of the task 117 * @param {int} priority the task's priority 118 * @param {Packet} queue the queue of work to be processed by the task 119 * @param {int} count the number of times to schedule the task 120 */ 121 Scheduler.prototype.addIdleTask = function (id, priority, queue, count) { 122 this.addRunningTask(id, priority, queue, new IdleTask(this, 1, count)); 123 }; 124 125 /** 126 * Add a work task to this scheduler. 127 * @param {int} id the identity of the task 128 * @param {int} priority the task's priority 129 * @param {Packet} queue the queue of work to be processed by the task 130 */ 131 Scheduler.prototype.addWorkerTask = function (id, priority, queue) { 132 this.addTask(id, priority, queue, new WorkerTask(this, ID_HANDLER_A, 0)); 133 }; 134 135 /** 136 * Add a handler task to this scheduler. 137 * @param {int} id the identity of the task 138 * @param {int} priority the task's priority 139 * @param {Packet} queue the queue of work to be processed by the task 140 */ 141 Scheduler.prototype.addHandlerTask = function (id, priority, queue) { 142 this.addTask(id, priority, queue, new HandlerTask(this)); 143 }; 144 145 /** 146 * Add a handler task to this scheduler. 147 * @param {int} id the identity of the task 148 * @param {int} priority the task's priority 149 * @param {Packet} queue the queue of work to be processed by the task 150 */ 151 Scheduler.prototype.addDeviceTask = function (id, priority, queue) { 152 this.addTask(id, priority, queue, new DeviceTask(this)) 153 }; 154 155 /** 156 * Add the specified task and mark it as running. 157 * @param {int} id the identity of the task 158 * @param {int} priority the task's priority 159 * @param {Packet} queue the queue of work to be processed by the task 160 * @param {Task} task the task to add 161 */ 162 Scheduler.prototype.addRunningTask = function (id, priority, queue, task) { 163 this.addTask(id, priority, queue, task); 164 this.currentTcb.setRunning(); 165 }; 166 167 /** 168 * Add the specified task to this scheduler. 169 * @param {int} id the identity of the task 170 * @param {int} priority the task's priority 171 * @param {Packet} queue the queue of work to be processed by the task 172 * @param {Task} task the task to add 173 */ 174 Scheduler.prototype.addTask = function (id, priority, queue, task) { 175 this.currentTcb = new TaskControlBlock(this.list, id, priority, queue, task); 176 this.list = this.currentTcb; 177 this.blocks[id] = this.currentTcb; 178 }; 179 180 /** 181 * Execute the tasks managed by this scheduler. 182 */ 183 Scheduler.prototype.schedule = function () { 184 this.currentTcb = this.list; 185 while (this.currentTcb != null) { 186 if (this.currentTcb.isHeldOrSuspended()) { 187 this.currentTcb = this.currentTcb.link; 188 } else { 189 this.currentId = this.currentTcb.id; 190 this.currentTcb = this.currentTcb.run(); 191 } 192 } 193 }; 194 195 /** 196 * Release a task that is currently blocked and return the next block to run. 197 * @param {int} id the id of the task to suspend 198 */ 199 Scheduler.prototype.release = function (id) { 200 var tcb = this.blocks[id]; 201 if (tcb == null) return tcb; 202 tcb.markAsNotHeld(); 203 if (tcb.priority > this.currentTcb.priority) { 204 return tcb; 205 } else { 206 return this.currentTcb; 207 } 208 }; 209 210 /** 211 * Block the currently executing task and return the next task control block 212 * to run. The blocked task will not be made runnable until it is explicitly 213 * released, even if new work is added to it. 214 */ 215 Scheduler.prototype.holdCurrent = function () { 216 this.holdCount++; 217 this.currentTcb.markAsHeld(); 218 return this.currentTcb.link; 219 }; 220 221 /** 222 * Suspend the currently executing task and return the next task control block 223 * to run. If new work is added to the suspended task it will be made runnable. 224 */ 225 Scheduler.prototype.suspendCurrent = function () { 226 this.currentTcb.markAsSuspended(); 227 return this.currentTcb; 228 }; 229 230 /** 231 * Add the specified packet to the end of the worklist used by the task 232 * associated with the packet and make the task runnable if it is currently 233 * suspended. 234 * @param {Packet} packet the packet to add 235 */ 236 Scheduler.prototype.queue = function (packet) { 237 var t = this.blocks[packet.id]; 238 if (t == null) return t; 239 this.queueCount++; 240 packet.link = null; 241 packet.id = this.currentId; 242 return t.checkPriorityAdd(this.currentTcb, packet); 243 }; 244 245 /** 246 * A task control block manages a task and the queue of work packages associated 247 * with it. 248 * @param {TaskControlBlock} link the preceding block in the linked block list 249 * @param {int} id the id of this block 250 * @param {int} priority the priority of this block 251 * @param {Packet} queue the queue of packages to be processed by the task 252 * @param {Task} task the task 253 * @constructor 254 */ 255 function TaskControlBlock(link, id, priority, queue, task) { 256 this.link = link; 257 this.id = id; 258 this.priority = priority; 259 this.queue = queue; 260 this.task = task; 261 if (queue == null) { 262 this.state = STATE_SUSPENDED; 263 } else { 264 this.state = STATE_SUSPENDED_RUNNABLE; 265 } 266 } 267 268 /** 269 * The task is running and is currently scheduled. 270 */ 271 var STATE_RUNNING = 0; 272 273 /** 274 * The task has packets left to process. 275 */ 276 var STATE_RUNNABLE = 1; 277 278 /** 279 * The task is not currently running. The task is not blocked as such and may 280 * be started by the scheduler. 281 */ 282 var STATE_SUSPENDED = 2; 283 284 /** 285 * The task is blocked and cannot be run until it is explicitly released. 286 */ 287 var STATE_HELD = 4; 288 289 var STATE_SUSPENDED_RUNNABLE = STATE_SUSPENDED | STATE_RUNNABLE; 290 var STATE_NOT_HELD = ~STATE_HELD; 291 292 TaskControlBlock.prototype.setRunning = function () { 293 this.state = STATE_RUNNING; 294 }; 295 296 TaskControlBlock.prototype.markAsNotHeld = function () { 297 this.state = this.state & STATE_NOT_HELD; 298 }; 299 300 TaskControlBlock.prototype.markAsHeld = function () { 301 this.state = this.state | STATE_HELD; 302 }; 303 304 TaskControlBlock.prototype.isHeldOrSuspended = function () { 305 return (this.state & STATE_HELD) != 0 || (this.state == STATE_SUSPENDED); 306 }; 307 308 TaskControlBlock.prototype.markAsSuspended = function () { 309 this.state = this.state | STATE_SUSPENDED; 310 }; 311 312 TaskControlBlock.prototype.markAsRunnable = function () { 313 this.state = this.state | STATE_RUNNABLE; 314 }; 315 316 /** 317 * Runs this task, if it is ready to be run, and returns the next task to run. 318 */ 319 TaskControlBlock.prototype.run = function () { 320 var packet; 321 if (this.state == STATE_SUSPENDED_RUNNABLE) { 322 packet = this.queue; 323 this.queue = packet.link; 324 if (this.queue == null) { 325 this.state = STATE_RUNNING; 326 } else { 327 this.state = STATE_RUNNABLE; 328 } 329 } else { 330 packet = null; 331 } 332 return this.task.run(packet); 333 }; 334 335 /** 336 * Adds a packet to the worklist of this block's task, marks this as runnable if 337 * necessary, and returns the next runnable object to run (the one 338 * with the highest priority). 339 */ 340 TaskControlBlock.prototype.checkPriorityAdd = function (task, packet) { 341 if (this.queue == null) { 342 this.queue = packet; 343 this.markAsRunnable(); 344 if (this.priority > task.priority) return this; 345 } else { 346 this.queue = packet.addTo(this.queue); 347 } 348 return task; 349 }; 350 351 TaskControlBlock.prototype.toString = function () { 352 return "tcb { " + this.task + "@" + this.state + " }"; 353 }; 354 355 /** 356 * An idle task doesn't do any work itself but cycles control between the two 357 * device tasks. 358 * @param {Scheduler} scheduler the scheduler that manages this task 359 * @param {int} v1 a seed value that controls how the device tasks are scheduled 360 * @param {int} count the number of times this task should be scheduled 361 * @constructor 362 */ 363 function IdleTask(scheduler, v1, count) { 364 this.scheduler = scheduler; 365 this.v1 = v1; 366 this.count = count; 367 } 368 369 IdleTask.prototype.run = function (packet) { 370 this.count--; 371 if (this.count == 0) return this.scheduler.holdCurrent(); 372 if ((this.v1 & 1) == 0) { 373 this.v1 = this.v1 >> 1; 374 return this.scheduler.release(ID_DEVICE_A); 375 } else { 376 this.v1 = (this.v1 >> 1) ^ 0xD008; 377 return this.scheduler.release(ID_DEVICE_B); 378 } 379 }; 380 381 IdleTask.prototype.toString = function () { 382 return "IdleTask" 383 }; 384 385 /** 386 * A task that suspends itself after each time it has been run to simulate 387 * waiting for data from an external device. 388 * @param {Scheduler} scheduler the scheduler that manages this task 389 * @constructor 390 */ 391 function DeviceTask(scheduler) { 392 this.scheduler = scheduler; 393 this.v1 = null; 394 } 395 396 DeviceTask.prototype.run = function (packet) { 397 if (packet == null) { 398 if (this.v1 == null) return this.scheduler.suspendCurrent(); 399 var v = this.v1; 400 this.v1 = null; 401 return this.scheduler.queue(v); 402 } else { 403 this.v1 = packet; 404 return this.scheduler.holdCurrent(); 405 } 406 }; 407 408 DeviceTask.prototype.toString = function () { 409 return "DeviceTask"; 410 }; 411 412 /** 413 * A task that manipulates work packets. 414 * @param {Scheduler} scheduler the scheduler that manages this task 415 * @param {int} v1 a seed used to specify how work packets are manipulated 416 * @param {int} v2 another seed used to specify how work packets are manipulated 417 * @constructor 418 */ 419 function WorkerTask(scheduler, v1, v2) { 420 this.scheduler = scheduler; 421 this.v1 = v1; 422 this.v2 = v2; 423 } 424 425 WorkerTask.prototype.run = function (packet) { 426 if (packet == null) { 427 return this.scheduler.suspendCurrent(); 428 } else { 429 if (this.v1 == ID_HANDLER_A) { 430 this.v1 = ID_HANDLER_B; 431 } else { 432 this.v1 = ID_HANDLER_A; 433 } 434 packet.id = this.v1; 435 packet.a1 = 0; 436 for (var i = 0; i < DATA_SIZE; i++) { 437 this.v2++; 438 if (this.v2 > 26) this.v2 = 1; 439 packet.a2[i] = this.v2; 440 } 441 return this.scheduler.queue(packet); 442 } 443 }; 444 445 WorkerTask.prototype.toString = function () { 446 return "WorkerTask"; 447 }; 448 449 /** 450 * A task that manipulates work packets and then suspends itself. 451 * @param {Scheduler} scheduler the scheduler that manages this task 452 * @constructor 453 */ 454 function HandlerTask(scheduler) { 455 this.scheduler = scheduler; 456 this.v1 = null; 457 this.v2 = null; 458 } 459 460 HandlerTask.prototype.run = function (packet) { 461 if (packet != null) { 462 if (packet.kind == KIND_WORK) { 463 this.v1 = packet.addTo(this.v1); 464 } else { 465 this.v2 = packet.addTo(this.v2); 466 } 467 } 468 if (this.v1 != null) { 469 var count = this.v1.a1; 470 var v; 471 if (count < DATA_SIZE) { 472 if (this.v2 != null) { 473 v = this.v2; 474 this.v2 = this.v2.link; 475 v.a1 = this.v1.a2[count]; 476 this.v1.a1 = count + 1; 477 return this.scheduler.queue(v); 478 } 479 } else { 480 v = this.v1; 481 this.v1 = this.v1.link; 482 return this.scheduler.queue(v); 483 } 484 } 485 return this.scheduler.suspendCurrent(); 486 }; 487 488 HandlerTask.prototype.toString = function () { 489 return "HandlerTask"; 490 }; 491 492 /* --- * 493 * P a c k e t 494 * --- */ 495 496 var DATA_SIZE = 4; 497 498 /** 499 * A simple package of data that is manipulated by the tasks. The exact layout 500 * of the payload data carried by a packet is not importaint, and neither is the 501 * nature of the work performed on packets by the tasks. 502 * 503 * Besides carrying data, packets form linked lists and are hence used both as 504 * data and worklists. 505 * @param {Packet} link the tail of the linked list of packets 506 * @param {int} id an ID for this packet 507 * @param {int} kind the type of this packet 508 * @constructor 509 */ 510 function Packet(link, id, kind) { 511 this.link = link; 512 this.id = id; 513 this.kind = kind; 514 this.a1 = 0; 515 this.a2 = new Array(DATA_SIZE); 516 } 517 518 /** 519 * Add this packet to the end of a worklist, and return the worklist. 520 * @param {Packet} queue the worklist to add this packet to 521 */ 522 Packet.prototype.addTo = function (queue) { 523 this.link = null; 524 if (queue == null) return this; 525 var peek, next = queue; 526 while ((peek = next.link) != null) 527 next = peek; 528 next.link = this; 529 return queue; 530 }; 531 532 Packet.prototype.toString = function () { 533 return "Packet"; 534 }; 535 536 for (var i = 0; i < 350; ++i) 537 runRichards(); 538