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