1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/v8/richards.js Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,539 @@
1.4 +// Copyright 2006-2008 the V8 project authors. All rights reserved.
1.5 +// Redistribution and use in source and binary forms, with or without
1.6 +// modification, are permitted provided that the following conditions are
1.7 +// met:
1.8 +//
1.9 +// * Redistributions of source code must retain the above copyright
1.10 +// notice, this list of conditions and the following disclaimer.
1.11 +// * Redistributions in binary form must reproduce the above
1.12 +// copyright notice, this list of conditions and the following
1.13 +// disclaimer in the documentation and/or other materials provided
1.14 +// with the distribution.
1.15 +// * Neither the name of Google Inc. nor the names of its
1.16 +// contributors may be used to endorse or promote products derived
1.17 +// from this software without specific prior written permission.
1.18 +//
1.19 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1.20 +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1.21 +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1.22 +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1.23 +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1.24 +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1.25 +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1.26 +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1.27 +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1.28 +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1.29 +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.30 +
1.31 +
1.32 +// This is a JavaScript implementation of the Richards
1.33 +// benchmark from:
1.34 +//
1.35 +// http://www.cl.cam.ac.uk/~mr10/Bench.html
1.36 +//
1.37 +// The benchmark was originally implemented in BCPL by
1.38 +// Martin Richards.
1.39 +
1.40 +
1.41 +var Richards = new BenchmarkSuite('Richards', 35302, [
1.42 + new Benchmark("Richards", runRichards)
1.43 +]);
1.44 +
1.45 +
1.46 +/**
1.47 + * The Richards benchmark simulates the task dispatcher of an
1.48 + * operating system.
1.49 + **/
1.50 +function runRichards() {
1.51 + var scheduler = new Scheduler();
1.52 + scheduler.addIdleTask(ID_IDLE, 0, null, COUNT);
1.53 +
1.54 + var queue = new Packet(null, ID_WORKER, KIND_WORK);
1.55 + queue = new Packet(queue, ID_WORKER, KIND_WORK);
1.56 + scheduler.addWorkerTask(ID_WORKER, 1000, queue);
1.57 +
1.58 + queue = new Packet(null, ID_DEVICE_A, KIND_DEVICE);
1.59 + queue = new Packet(queue, ID_DEVICE_A, KIND_DEVICE);
1.60 + queue = new Packet(queue, ID_DEVICE_A, KIND_DEVICE);
1.61 + scheduler.addHandlerTask(ID_HANDLER_A, 2000, queue);
1.62 +
1.63 + queue = new Packet(null, ID_DEVICE_B, KIND_DEVICE);
1.64 + queue = new Packet(queue, ID_DEVICE_B, KIND_DEVICE);
1.65 + queue = new Packet(queue, ID_DEVICE_B, KIND_DEVICE);
1.66 + scheduler.addHandlerTask(ID_HANDLER_B, 3000, queue);
1.67 +
1.68 + scheduler.addDeviceTask(ID_DEVICE_A, 4000, null);
1.69 +
1.70 + scheduler.addDeviceTask(ID_DEVICE_B, 5000, null);
1.71 +
1.72 + scheduler.schedule();
1.73 +
1.74 + if (scheduler.queueCount != EXPECTED_QUEUE_COUNT ||
1.75 + scheduler.holdCount != EXPECTED_HOLD_COUNT) {
1.76 + var msg =
1.77 + "Error during execution: queueCount = " + scheduler.queueCount +
1.78 + ", holdCount = " + scheduler.holdCount + ".";
1.79 + throw new Error(msg);
1.80 + }
1.81 +}
1.82 +
1.83 +var COUNT = 1000;
1.84 +
1.85 +/**
1.86 + * These two constants specify how many times a packet is queued and
1.87 + * how many times a task is put on hold in a correct run of richards.
1.88 + * They don't have any meaning a such but are characteristic of a
1.89 + * correct run so if the actual queue or hold count is different from
1.90 + * the expected there must be a bug in the implementation.
1.91 + **/
1.92 +var EXPECTED_QUEUE_COUNT = 2322;
1.93 +var EXPECTED_HOLD_COUNT = 928;
1.94 +
1.95 +
1.96 +/**
1.97 + * A scheduler can be used to schedule a set of tasks based on their relative
1.98 + * priorities. Scheduling is done by maintaining a list of task control blocks
1.99 + * which holds tasks and the data queue they are processing.
1.100 + * @constructor
1.101 + */
1.102 +function Scheduler() {
1.103 + this.queueCount = 0;
1.104 + this.holdCount = 0;
1.105 + this.blocks = new Array(NUMBER_OF_IDS);
1.106 + this.list = null;
1.107 + this.currentTcb = null;
1.108 + this.currentId = null;
1.109 +}
1.110 +
1.111 +var ID_IDLE = 0;
1.112 +var ID_WORKER = 1;
1.113 +var ID_HANDLER_A = 2;
1.114 +var ID_HANDLER_B = 3;
1.115 +var ID_DEVICE_A = 4;
1.116 +var ID_DEVICE_B = 5;
1.117 +var NUMBER_OF_IDS = 6;
1.118 +
1.119 +var KIND_DEVICE = 0;
1.120 +var KIND_WORK = 1;
1.121 +
1.122 +/**
1.123 + * Add an idle task to this scheduler.
1.124 + * @param {int} id the identity of the task
1.125 + * @param {int} priority the task's priority
1.126 + * @param {Packet} queue the queue of work to be processed by the task
1.127 + * @param {int} count the number of times to schedule the task
1.128 + */
1.129 +Scheduler.prototype.addIdleTask = function (id, priority, queue, count) {
1.130 + this.addRunningTask(id, priority, queue, new IdleTask(this, 1, count));
1.131 +};
1.132 +
1.133 +/**
1.134 + * Add a work task to this scheduler.
1.135 + * @param {int} id the identity of the task
1.136 + * @param {int} priority the task's priority
1.137 + * @param {Packet} queue the queue of work to be processed by the task
1.138 + */
1.139 +Scheduler.prototype.addWorkerTask = function (id, priority, queue) {
1.140 + this.addTask(id, priority, queue, new WorkerTask(this, ID_HANDLER_A, 0));
1.141 +};
1.142 +
1.143 +/**
1.144 + * Add a handler task to this scheduler.
1.145 + * @param {int} id the identity of the task
1.146 + * @param {int} priority the task's priority
1.147 + * @param {Packet} queue the queue of work to be processed by the task
1.148 + */
1.149 +Scheduler.prototype.addHandlerTask = function (id, priority, queue) {
1.150 + this.addTask(id, priority, queue, new HandlerTask(this));
1.151 +};
1.152 +
1.153 +/**
1.154 + * Add a handler task to this scheduler.
1.155 + * @param {int} id the identity of the task
1.156 + * @param {int} priority the task's priority
1.157 + * @param {Packet} queue the queue of work to be processed by the task
1.158 + */
1.159 +Scheduler.prototype.addDeviceTask = function (id, priority, queue) {
1.160 + this.addTask(id, priority, queue, new DeviceTask(this))
1.161 +};
1.162 +
1.163 +/**
1.164 + * Add the specified task and mark it as running.
1.165 + * @param {int} id the identity of the task
1.166 + * @param {int} priority the task's priority
1.167 + * @param {Packet} queue the queue of work to be processed by the task
1.168 + * @param {Task} task the task to add
1.169 + */
1.170 +Scheduler.prototype.addRunningTask = function (id, priority, queue, task) {
1.171 + this.addTask(id, priority, queue, task);
1.172 + this.currentTcb.setRunning();
1.173 +};
1.174 +
1.175 +/**
1.176 + * Add the specified task to this scheduler.
1.177 + * @param {int} id the identity of the task
1.178 + * @param {int} priority the task's priority
1.179 + * @param {Packet} queue the queue of work to be processed by the task
1.180 + * @param {Task} task the task to add
1.181 + */
1.182 +Scheduler.prototype.addTask = function (id, priority, queue, task) {
1.183 + this.currentTcb = new TaskControlBlock(this.list, id, priority, queue, task);
1.184 + this.list = this.currentTcb;
1.185 + this.blocks[id] = this.currentTcb;
1.186 +};
1.187 +
1.188 +/**
1.189 + * Execute the tasks managed by this scheduler.
1.190 + */
1.191 +Scheduler.prototype.schedule = function () {
1.192 + this.currentTcb = this.list;
1.193 + while (this.currentTcb != null) {
1.194 + if (this.currentTcb.isHeldOrSuspended()) {
1.195 + this.currentTcb = this.currentTcb.link;
1.196 + } else {
1.197 + this.currentId = this.currentTcb.id;
1.198 + this.currentTcb = this.currentTcb.run();
1.199 + }
1.200 + }
1.201 +};
1.202 +
1.203 +/**
1.204 + * Release a task that is currently blocked and return the next block to run.
1.205 + * @param {int} id the id of the task to suspend
1.206 + */
1.207 +Scheduler.prototype.release = function (id) {
1.208 + var tcb = this.blocks[id];
1.209 + if (tcb == null) return tcb;
1.210 + tcb.markAsNotHeld();
1.211 + if (tcb.priority > this.currentTcb.priority) {
1.212 + return tcb;
1.213 + } else {
1.214 + return this.currentTcb;
1.215 + }
1.216 +};
1.217 +
1.218 +/**
1.219 + * Block the currently executing task and return the next task control block
1.220 + * to run. The blocked task will not be made runnable until it is explicitly
1.221 + * released, even if new work is added to it.
1.222 + */
1.223 +Scheduler.prototype.holdCurrent = function () {
1.224 + this.holdCount++;
1.225 + this.currentTcb.markAsHeld();
1.226 + return this.currentTcb.link;
1.227 +};
1.228 +
1.229 +/**
1.230 + * Suspend the currently executing task and return the next task control block
1.231 + * to run. If new work is added to the suspended task it will be made runnable.
1.232 + */
1.233 +Scheduler.prototype.suspendCurrent = function () {
1.234 + this.currentTcb.markAsSuspended();
1.235 + return this.currentTcb;
1.236 +};
1.237 +
1.238 +/**
1.239 + * Add the specified packet to the end of the worklist used by the task
1.240 + * associated with the packet and make the task runnable if it is currently
1.241 + * suspended.
1.242 + * @param {Packet} packet the packet to add
1.243 + */
1.244 +Scheduler.prototype.queue = function (packet) {
1.245 + var t = this.blocks[packet.id];
1.246 + if (t == null) return t;
1.247 + this.queueCount++;
1.248 + packet.link = null;
1.249 + packet.id = this.currentId;
1.250 + return t.checkPriorityAdd(this.currentTcb, packet);
1.251 +};
1.252 +
1.253 +/**
1.254 + * A task control block manages a task and the queue of work packages associated
1.255 + * with it.
1.256 + * @param {TaskControlBlock} link the preceding block in the linked block list
1.257 + * @param {int} id the id of this block
1.258 + * @param {int} priority the priority of this block
1.259 + * @param {Packet} queue the queue of packages to be processed by the task
1.260 + * @param {Task} task the task
1.261 + * @constructor
1.262 + */
1.263 +function TaskControlBlock(link, id, priority, queue, task) {
1.264 + this.link = link;
1.265 + this.id = id;
1.266 + this.priority = priority;
1.267 + this.queue = queue;
1.268 + this.task = task;
1.269 + if (queue == null) {
1.270 + this.state = STATE_SUSPENDED;
1.271 + } else {
1.272 + this.state = STATE_SUSPENDED_RUNNABLE;
1.273 + }
1.274 +}
1.275 +
1.276 +/**
1.277 + * The task is running and is currently scheduled.
1.278 + */
1.279 +var STATE_RUNNING = 0;
1.280 +
1.281 +/**
1.282 + * The task has packets left to process.
1.283 + */
1.284 +var STATE_RUNNABLE = 1;
1.285 +
1.286 +/**
1.287 + * The task is not currently running. The task is not blocked as such and may
1.288 +* be started by the scheduler.
1.289 + */
1.290 +var STATE_SUSPENDED = 2;
1.291 +
1.292 +/**
1.293 + * The task is blocked and cannot be run until it is explicitly released.
1.294 + */
1.295 +var STATE_HELD = 4;
1.296 +
1.297 +var STATE_SUSPENDED_RUNNABLE = STATE_SUSPENDED | STATE_RUNNABLE;
1.298 +var STATE_NOT_HELD = ~STATE_HELD;
1.299 +
1.300 +TaskControlBlock.prototype.setRunning = function () {
1.301 + this.state = STATE_RUNNING;
1.302 +};
1.303 +
1.304 +TaskControlBlock.prototype.markAsNotHeld = function () {
1.305 + this.state = this.state & STATE_NOT_HELD;
1.306 +};
1.307 +
1.308 +TaskControlBlock.prototype.markAsHeld = function () {
1.309 + this.state = this.state | STATE_HELD;
1.310 +};
1.311 +
1.312 +TaskControlBlock.prototype.isHeldOrSuspended = function () {
1.313 + return (this.state & STATE_HELD) != 0 || (this.state == STATE_SUSPENDED);
1.314 +};
1.315 +
1.316 +TaskControlBlock.prototype.markAsSuspended = function () {
1.317 + this.state = this.state | STATE_SUSPENDED;
1.318 +};
1.319 +
1.320 +TaskControlBlock.prototype.markAsRunnable = function () {
1.321 + this.state = this.state | STATE_RUNNABLE;
1.322 +};
1.323 +
1.324 +/**
1.325 + * Runs this task, if it is ready to be run, and returns the next task to run.
1.326 + */
1.327 +TaskControlBlock.prototype.run = function () {
1.328 + var packet;
1.329 + if (this.state == STATE_SUSPENDED_RUNNABLE) {
1.330 + packet = this.queue;
1.331 + this.queue = packet.link;
1.332 + if (this.queue == null) {
1.333 + this.state = STATE_RUNNING;
1.334 + } else {
1.335 + this.state = STATE_RUNNABLE;
1.336 + }
1.337 + } else {
1.338 + packet = null;
1.339 + }
1.340 + return this.task.run(packet);
1.341 +};
1.342 +
1.343 +/**
1.344 + * Adds a packet to the worklist of this block's task, marks this as runnable if
1.345 + * necessary, and returns the next runnable object to run (the one
1.346 + * with the highest priority).
1.347 + */
1.348 +TaskControlBlock.prototype.checkPriorityAdd = function (task, packet) {
1.349 + if (this.queue == null) {
1.350 + this.queue = packet;
1.351 + this.markAsRunnable();
1.352 + if (this.priority > task.priority) return this;
1.353 + } else {
1.354 + this.queue = packet.addTo(this.queue);
1.355 + }
1.356 + return task;
1.357 +};
1.358 +
1.359 +TaskControlBlock.prototype.toString = function () {
1.360 + return "tcb { " + this.task + "@" + this.state + " }";
1.361 +};
1.362 +
1.363 +/**
1.364 + * An idle task doesn't do any work itself but cycles control between the two
1.365 + * device tasks.
1.366 + * @param {Scheduler} scheduler the scheduler that manages this task
1.367 + * @param {int} v1 a seed value that controls how the device tasks are scheduled
1.368 + * @param {int} count the number of times this task should be scheduled
1.369 + * @constructor
1.370 + */
1.371 +function IdleTask(scheduler, v1, count) {
1.372 + this.scheduler = scheduler;
1.373 + this.v1 = v1;
1.374 + this.count = count;
1.375 +}
1.376 +
1.377 +IdleTask.prototype.run = function (packet) {
1.378 + this.count--;
1.379 + if (this.count == 0) return this.scheduler.holdCurrent();
1.380 + if ((this.v1 & 1) == 0) {
1.381 + this.v1 = this.v1 >> 1;
1.382 + return this.scheduler.release(ID_DEVICE_A);
1.383 + } else {
1.384 + this.v1 = (this.v1 >> 1) ^ 0xD008;
1.385 + return this.scheduler.release(ID_DEVICE_B);
1.386 + }
1.387 +};
1.388 +
1.389 +IdleTask.prototype.toString = function () {
1.390 + return "IdleTask"
1.391 +};
1.392 +
1.393 +/**
1.394 + * A task that suspends itself after each time it has been run to simulate
1.395 + * waiting for data from an external device.
1.396 + * @param {Scheduler} scheduler the scheduler that manages this task
1.397 + * @constructor
1.398 + */
1.399 +function DeviceTask(scheduler) {
1.400 + this.scheduler = scheduler;
1.401 + this.v1 = null;
1.402 +}
1.403 +
1.404 +DeviceTask.prototype.run = function (packet) {
1.405 + if (packet == null) {
1.406 + if (this.v1 == null) return this.scheduler.suspendCurrent();
1.407 + var v = this.v1;
1.408 + this.v1 = null;
1.409 + return this.scheduler.queue(v);
1.410 + } else {
1.411 + this.v1 = packet;
1.412 + return this.scheduler.holdCurrent();
1.413 + }
1.414 +};
1.415 +
1.416 +DeviceTask.prototype.toString = function () {
1.417 + return "DeviceTask";
1.418 +};
1.419 +
1.420 +/**
1.421 + * A task that manipulates work packets.
1.422 + * @param {Scheduler} scheduler the scheduler that manages this task
1.423 + * @param {int} v1 a seed used to specify how work packets are manipulated
1.424 + * @param {int} v2 another seed used to specify how work packets are manipulated
1.425 + * @constructor
1.426 + */
1.427 +function WorkerTask(scheduler, v1, v2) {
1.428 + this.scheduler = scheduler;
1.429 + this.v1 = v1;
1.430 + this.v2 = v2;
1.431 +}
1.432 +
1.433 +WorkerTask.prototype.run = function (packet) {
1.434 + if (packet == null) {
1.435 + return this.scheduler.suspendCurrent();
1.436 + } else {
1.437 + if (this.v1 == ID_HANDLER_A) {
1.438 + this.v1 = ID_HANDLER_B;
1.439 + } else {
1.440 + this.v1 = ID_HANDLER_A;
1.441 + }
1.442 + packet.id = this.v1;
1.443 + packet.a1 = 0;
1.444 + for (var i = 0; i < DATA_SIZE; i++) {
1.445 + this.v2++;
1.446 + if (this.v2 > 26) this.v2 = 1;
1.447 + packet.a2[i] = this.v2;
1.448 + }
1.449 + return this.scheduler.queue(packet);
1.450 + }
1.451 +};
1.452 +
1.453 +WorkerTask.prototype.toString = function () {
1.454 + return "WorkerTask";
1.455 +};
1.456 +
1.457 +/**
1.458 + * A task that manipulates work packets and then suspends itself.
1.459 + * @param {Scheduler} scheduler the scheduler that manages this task
1.460 + * @constructor
1.461 + */
1.462 +function HandlerTask(scheduler) {
1.463 + this.scheduler = scheduler;
1.464 + this.v1 = null;
1.465 + this.v2 = null;
1.466 +}
1.467 +
1.468 +HandlerTask.prototype.run = function (packet) {
1.469 + if (packet != null) {
1.470 + if (packet.kind == KIND_WORK) {
1.471 + this.v1 = packet.addTo(this.v1);
1.472 + } else {
1.473 + this.v2 = packet.addTo(this.v2);
1.474 + }
1.475 + }
1.476 + if (this.v1 != null) {
1.477 + var count = this.v1.a1;
1.478 + var v;
1.479 + if (count < DATA_SIZE) {
1.480 + if (this.v2 != null) {
1.481 + v = this.v2;
1.482 + this.v2 = this.v2.link;
1.483 + v.a1 = this.v1.a2[count];
1.484 + this.v1.a1 = count + 1;
1.485 + return this.scheduler.queue(v);
1.486 + }
1.487 + } else {
1.488 + v = this.v1;
1.489 + this.v1 = this.v1.link;
1.490 + return this.scheduler.queue(v);
1.491 + }
1.492 + }
1.493 + return this.scheduler.suspendCurrent();
1.494 +};
1.495 +
1.496 +HandlerTask.prototype.toString = function () {
1.497 + return "HandlerTask";
1.498 +};
1.499 +
1.500 +/* --- *
1.501 + * P a c k e t
1.502 + * --- */
1.503 +
1.504 +var DATA_SIZE = 4;
1.505 +
1.506 +/**
1.507 + * A simple package of data that is manipulated by the tasks. The exact layout
1.508 + * of the payload data carried by a packet is not importaint, and neither is the
1.509 + * nature of the work performed on packets by the tasks.
1.510 + *
1.511 + * Besides carrying data, packets form linked lists and are hence used both as
1.512 + * data and worklists.
1.513 + * @param {Packet} link the tail of the linked list of packets
1.514 + * @param {int} id an ID for this packet
1.515 + * @param {int} kind the type of this packet
1.516 + * @constructor
1.517 + */
1.518 +function Packet(link, id, kind) {
1.519 + this.link = link;
1.520 + this.id = id;
1.521 + this.kind = kind;
1.522 + this.a1 = 0;
1.523 + this.a2 = new Array(DATA_SIZE);
1.524 +}
1.525 +
1.526 +/**
1.527 + * Add this packet to the end of a worklist, and return the worklist.
1.528 + * @param {Packet} queue the worklist to add this packet to
1.529 + */
1.530 +Packet.prototype.addTo = function (queue) {
1.531 + this.link = null;
1.532 + if (queue == null) return this;
1.533 + var peek, next = queue;
1.534 + while ((peek = next.link) != null)
1.535 + next = peek;
1.536 + next.link = this;
1.537 + return queue;
1.538 +};
1.539 +
1.540 +Packet.prototype.toString = function () {
1.541 + return "Packet";
1.542 +};
