The Tor Browser / file diff

     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/js/src/tests/js1_8/extensions/lamport.js	Wed Dec 31 06:09:35 2014 +0100
     1.3 @@ -0,0 +1,93 @@
     1.4 +// |reftest| skip
     1.5 +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
     1.6 +/* This Source Code Form is subject to the terms of the Mozilla Public
     1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
     1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
     1.9 +
    1.10 +//-----------------------------------------------------------------------
    1.11 +
    1.12 +var summary = "Lamport Bakery's algorithm for mutual exclusion";
    1.13 +// Adapted from pseudocode in Wikipedia:
    1.14 +// http://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm
    1.15 +
    1.16 +printStatus(summary);
    1.17 +
    1.18 +var N = 15; // Number of threads.
    1.19 +var LOOP_COUNT = 10; // Number of times each thread should loop
    1.20 +
    1.21 +function range(n) {
    1.22 +  for (let i = 0; i < n; i++)
    1.23 +    yield i;
    1.24 +}
    1.25 +
    1.26 +function max(a) {
    1.27 +  let x = Number.NEGATIVE_INFINITY;
    1.28 +  for each (let i in a)
    1.29 +    if (i > x)
    1.30 +      x = i;
    1.31 +  return x;
    1.32 +}
    1.33 +
    1.34 +// the mutex mechanism
    1.35 +var entering = [false for (i in range(N))];
    1.36 +var ticket = [0 for (i in range(N))];
    1.37 +
    1.38 +// the object being protected
    1.39 +var counter = 0;
    1.40 +
    1.41 +function lock(i)
    1.42 +{
    1.43 +  entering[i] = true;
    1.44 +  ticket[i] = 1 + max(ticket);
    1.45 +  entering[i] = false;
    1.46 +
    1.47 +  for (let j = 0; j < N; j++) {
    1.48 +    // If thread j is in the middle of getting a ticket, wait for that to
    1.49 +    // finish.
    1.50 +    while (entering[j])
    1.51 +      ;
    1.52 +
    1.53 +    // Wait until all threads with smaller ticket numbers or with the same
    1.54 +    // ticket number, but with higher priority, finish their work.
    1.55 +    while ((ticket[j] != 0) && ((ticket[j] < ticket[i]) ||
    1.56 +                                ((ticket[j] == ticket[i]) && (i < j))))
    1.57 +      ;
    1.58 +  }
    1.59 +}
    1.60 +
    1.61 +function unlock(i) {
    1.62 +  ticket[i] = 0;
    1.63 +}
    1.64 +
    1.65 +function worker(i) {
    1.66 +  for (let k = 0; k < LOOP_COUNT; k++) {
    1.67 +    lock(i);
    1.68 +
    1.69 +    // The critical section
    1.70 +    let x = counter;
    1.71 +    sleep(0.003);
    1.72 +    counter = x + 1;
    1.73 +
    1.74 +    unlock(i);
    1.75 +  }
    1.76 +  return 'ok';
    1.77 +}
    1.78 +
    1.79 +function makeWorker(id) {
    1.80 +  return function () { return worker(id); };
    1.81 +}
    1.82 +
    1.83 +var expect;
    1.84 +var actual;
    1.85 +
    1.86 +if (typeof scatter == 'undefined' || typeof sleep == 'undefined') {
    1.87 +  print('Test skipped. scatter or sleep not defined.');
    1.88 +  expect = actual = 'Test skipped.';
    1.89 +} else {
    1.90 +  scatter([makeWorker(i) for (i in range(N))]);
    1.91 +
    1.92 +  expect = "counter: " + (N * LOOP_COUNT);
    1.93 +  actual = "counter: " + counter;
    1.94 +}
    1.95 +
    1.96 +reportCompare(expect, actual, summary);