• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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
38var 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 **/
47function 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
80var 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 **/
89var EXPECTED_QUEUE_COUNT = 2322;
90var 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 */
99function 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
108var ID_IDLE       = 0;
109var ID_WORKER     = 1;
110var ID_HANDLER_A  = 2;
111var ID_HANDLER_B  = 3;
112var ID_DEVICE_A   = 4;
113var ID_DEVICE_B   = 5;
114var NUMBER_OF_IDS = 6;
115
116var KIND_DEVICE   = 0;
117var 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 */
126Scheduler.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 */
136Scheduler.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 */
146Scheduler.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 */
156Scheduler.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 */
167Scheduler.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 */
179Scheduler.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 */
188Scheduler.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 */
204Scheduler.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 */
220Scheduler.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 */
230Scheduler.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 */
241Scheduler.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 */
260function 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 */
276var STATE_RUNNING = 0;
277
278/**
279 * The task has packets left to process.
280 */
281var 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 */
287var STATE_SUSPENDED = 2;
288
289/**
290 * The task is blocked and cannot be run until it is explicitly released.
291 */
292var STATE_HELD = 4;
293
294var STATE_SUSPENDED_RUNNABLE = STATE_SUSPENDED | STATE_RUNNABLE;
295var STATE_NOT_HELD = ~STATE_HELD;
296
297TaskControlBlock.prototype.setRunning = function () {
298  this.state = STATE_RUNNING;
299};
300
301TaskControlBlock.prototype.markAsNotHeld = function () {
302  this.state = this.state & STATE_NOT_HELD;
303};
304
305TaskControlBlock.prototype.markAsHeld = function () {
306  this.state = this.state | STATE_HELD;
307};
308
309TaskControlBlock.prototype.isHeldOrSuspended = function () {
310  return (this.state & STATE_HELD) != 0 || (this.state == STATE_SUSPENDED);
311};
312
313TaskControlBlock.prototype.markAsSuspended = function () {
314  this.state = this.state | STATE_SUSPENDED;
315};
316
317TaskControlBlock.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 */
324TaskControlBlock.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 */
345TaskControlBlock.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
356TaskControlBlock.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 */
368function IdleTask(scheduler, v1, count) {
369  this.scheduler = scheduler;
370  this.v1 = v1;
371  this.count = count;
372}
373
374IdleTask.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
386IdleTask.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 */
396function DeviceTask(scheduler) {
397  this.scheduler = scheduler;
398  this.v1 = null;
399}
400
401DeviceTask.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
413DeviceTask.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 */
424function WorkerTask(scheduler, v1, v2) {
425  this.scheduler = scheduler;
426  this.v1 = v1;
427  this.v2 = v2;
428}
429
430WorkerTask.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
450WorkerTask.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 */
459function HandlerTask(scheduler) {
460  this.scheduler = scheduler;
461  this.v1 = null;
462  this.v2 = null;
463}
464
465HandlerTask.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
493HandlerTask.prototype.toString = function () {
494  return "HandlerTask";
495};
496
497/* --- *
498 * P a c k e t
499 * --- */
500
501var 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 */
515function 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 */
527Packet.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
537Packet.prototype.toString = function () {
538  return "Packet";
539};
540