Robust/Transactions/dstm2src/manager/KarmaManager.java

   1 /*
   2  * KarmaManager.java
   3  *
   4  * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle, Santa
   5  * Clara, California 95054, U.S.A.  All rights reserved.
   6  *
   7  * Sun Microsystems, Inc. has intellectual property rights relating to
   8  * technology embodied in the product that is described in this
   9  * document.  In particular, and without limitation, these
  10  * intellectual property rights may include one or more of the
  11  * U.S. patents listed at http://www.sun.com/patents and one or more
  12  * additional patents or pending patent applications in the U.S. and
  13  * in other countries.
  14  *
  15  * U.S. Government Rights - Commercial software.
  16  * Government users are subject to the Sun Microsystems, Inc. standard
  17  * license agreement and applicable provisions of the FAR and its
  18  * supplements.  Use is subject to license terms.  Sun, Sun
  19  * Microsystems, the Sun logo and Java are trademarks or registered
  20  * trademarks of Sun Microsystems, Inc. in the U.S. and other
  21  * countries.
  22  *
  23  * This product is covered and controlled by U.S. Export Control laws
  24  * and may be subject to the export or import laws in other countries.
  25  * Nuclear, missile, chemical biological weapons or nuclear maritime
  26  * end uses or end users, whether direct or indirect, are strictly
  27  * prohibited.  Export or reexport to countries subject to
  28  * U.S. embargo or to entities identified on U.S. export exclusion
  29  * lists, including, but not limited to, the denied persons and
  30  * specially designated nationals lists is strictly prohibited.
  31  */
  32
  33 package dstm2.manager;
  34 import dstm2.Transaction;
  35 import dstm2.ContentionManager;
  36
  37 /**
  38  * Uses "karmic debt management" to resolve conflicts.  Roughly, a
  39  * thread gains "karma" for every object it successfully opens, and
  40  * threads with greater karma can abort transactions of other threads.
  41  * A thread's karma is reset every time it successfully commits a
  42  * transaction, but not when it is aborted (hence the name).
  43  *
  44  * When conflict occurs between two transactions, the one with the
  45  * greater accumulated karma wins. If the other transaction holds a
  46  * block, it gets aborted immediately. Otherwise, the "lesser"
  47  * transaction backs off for a fixed interval and up to the square of
  48  * the difference in karma bethere the two.
  49  *
  50  * The key idea behind this policy is that it allows long transactions
  51  * to eventually finish even if mixed with lots of competing shorter
  52  * transactions. This happens because the longer transaction will
  53  * accumulate more and more karma each time it gets aborted, so it
  54  * will eventually reach "critical mass" and be able to bulldoze its
  55  * way through to get its work done.
  56  *
  57  * @author Bill Scherer
  58  **/
  59
  60 public class KarmaManager extends BaseManager {
  61   static final int SLEEP_PERIOD = 1000;
  62
  63   public void resolveConflict(Transaction me, Transaction other) {
  64     ContentionManager otherManager = other.getContentionManager();
  65     for (int attempts = 0; ; attempts++) {
  66       long delta = otherManager.getPriority() - priority;
  67       if (attempts > delta) {
  68         other.abort();
  69       }
  70     }
  71   }
  72
  73   /**
  74    * Reset priority only on commit. On abort, restart with previous priority.
  75    * "Cosmic debt"?. More like cosmic credit.
  76    **/
  77   public void committed() {
  78     setPriority(0);
  79   }
  80
  81   public void openSucceeded() {
  82     setPriority(getPriority() + 1);
  83   }
  84 }