Robust/Transactions/dstm2src/manager/EruptionManager.java

   1 /*
   2  * EruptionManager.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
  35 import dstm2.ContentionManager;
  36 import dstm2.Transaction;
  37
  38 /**
  39  * Resolves conflicts by increasing pressure on the transactions that
  40  * a blocked transaction is waiting on, eventually causing them to
  41  * erupt through to completion. The way this works is that each time a
  42  * block is successfully opened, the transaction gains one point of
  43  * "momentum". When a transaction finds itself blocked by another of
  44  * higher priority, it adds its momentum (priority) to the other
  45  * transaction and then waits for the other transaction to complete.
  46  * Like the Karma manager, Eruption will only wait around so long
  47  * before clobbering the other transaction and going on anyway; the
  48  * maximum wait is proportional to the square of the difference in
  49  * priorities between the two transactions. Of course, at contention
  50  * time, if the other transaction has a lower priority, we just erupt
  51  * past it.
  52  *
  53  * The reasoning behind this management scheme is that if a particular
  54  * transaction is blocking resources critical to many other
  55  * transactions, it will gain all of their priority in addition to its
  56  * own and thus be much more likely to finish quickly and get out of
  57  * the way of all the others.
  58  *
  59  * Note that while a transaction is blocked, other transactions can
  60  * pile up behind it and increase its priority enough to outweigh the
  61  * transaction it's blocked behind.
  62  *
  63  * @author Bill Scherer
  64  *
  65  **/
  66
  67 public class EruptionManager extends BaseManager {
  68   static final int SLEEP_PERIOD = 1000;
  69
  70   /** Creates a new instance of EruptionManager */
  71   public EruptionManager() {
  72     priority = 0;
  73   }
  74
  75   public void resolveConflict(Transaction me, Transaction other) {
  76     long transferred = 0;
  77     ContentionManager otherManager = other.getContentionManager();
  78     for (int attempts = 0; ; attempts++) {
  79       long otherPriority = otherManager.getPriority();
  80       long delta = otherPriority - priority;
  81       if (delta < 0 || attempts > delta * delta) {
  82         transferred = 0;
  83         other.abort();
  84         return;
  85       }
  86       // Unsafe increment, but too expensive to synchronize.
  87       if (priority > transferred) {
  88         otherManager.setPriority(otherPriority + priority - transferred);
  89         transferred = priority;
  90       }
  91       if (attempts < delta) {
  92         sleep(SLEEP_PERIOD);
  93       }
  94     }
  95   }
  96
  97   public void openSucceeded() {
  98     priority++;
  99   }
 100
 101 }