OrderedLock


1   /*******************************************************************************
2    * Copyright (c) 2003, 2006 IBM Corporation and others.
3    * All rights reserved. This program and the accompanying materials
4    * are made available under the terms of the Eclipse Public License v1.0
5    * which accompanies this distribution, and is available at
6    * http://www.eclipse.org/legal/epl-v10.html
7    * 
8    * Contributors:
9    *     IBM - Initial API and implementation
10   *******************************************************************************/
11  package org.eclipse.core.internal.jobs;
12  
13  import org.eclipse.core.runtime.Assert;
14  import org.eclipse.core.runtime.jobs.ILock;
15  import org.eclipse.core.runtime.jobs.ISchedulingRule;
16  
17  /**
18   * A lock used to control write access to an exclusive resource.
19   * 
20   * The lock avoids circular waiting deadlocks by detecting the deadlocks
21   * and resolving them through the suspension of all locks owned by one 
22   * of the threads involved in the deadlock. This makes it impossible for n such 
23   * locks to deadlock while waiting for each other.  The downside is that this means
24   * that during an interval when a process owns a lock, it can be forced
25   * to give the lock up and wait until all locks it requires become
26   * available.  This removes the feature of exclusive access to the
27   * resource in contention for the duration between acquire() and
28   * release() calls.
29   * 
30   * The lock implementation prevents starvation by granting the
31   * lock in the same order in which acquire() requests arrive. In
32   * this scheme, starvation is only possible if a thread retains
33   * a lock indefinitely.
34   */
35  public class OrderedLock implements ILock, ISchedulingRule {
36  
37      private static final boolean DEBUG = false;
38      /**
39       * Locks are sequentially ordered for debugging purposes.
40       */
41      private static int nextLockNumber = 0;
42      /**
43       * The thread of the operation that currently owns the lock.
44       */
45      private volatile Thread   currentOperationThread;
46      /**
47       * Records the number of successive acquires in the same
48       * thread. The lock is released only when the depth
49       * reaches zero.
50       */
51      private int depth;
52      /**
53       * The manager that implements the deadlock detection and resolution protocol.
54       */
55      private final LockManager manager;
56      private final int number;
57  
58      /**
59       * Queue of semaphores for threads currently waiting
60       * on the lock. This queue is not thread-safe, so access
61       * to this queue must be synchronized on the lock instance.
62       */
63      private final Queue operations = new Queue();
64  
65      /**
66       * Creates a new workspace lock.
67       */
68      OrderedLock(LockManager manager) {
69          this.manager = manager;
70          this.number = nextLockNumber++;
71      }
72  
73      /* (non-Javadoc)
74       * @see Locks.ILock#acquire()
75       */
76      public void acquire() {
77          //spin until the lock is successfully acquired
78          //NOTE: spinning here allows the UI thread to service pending syncExecs
79          //if the UI thread is waiting to acquire a lock.
80          while (true) {
81              try {
82                  if (acquire(Long.MAX_VALUE))
83                      return;
84              } catch (InterruptedException   e) {
85                  //ignore and loop
86              }
87          }
88      }
89  
90      /* (non-Javadoc)
91       * @see Locks.ILock#acquire(long)
92       */
93      public boolean acquire(long delay) throws InterruptedException   {
94          if (Thread.interrupted())
95              throw new InterruptedException  ();
96  
97          boolean success = false;
98          if (delay <= 0)
99              return attempt();
100         Semaphore semaphore = createSemaphore();
101         if (semaphore == null)
102             return true;
103         if (DEBUG)
104             System.out.println("[" + Thread.currentThread() + "] Operation waiting to be executed... " + this); //$NON-NLS-1$ //$NON-NLS-2$
105         success = doAcquire(semaphore, delay);
106         manager.resumeSuspendedLocks(Thread.currentThread());
107         if (DEBUG && success)
108             System.out.println("[" + Thread.currentThread() + "] Operation started... " + this); //$NON-NLS-1$ //$NON-NLS-2$
109         else if (DEBUG)
110             System.out.println("[" + Thread.currentThread() + "] Operation timed out... " + this); //$NON-NLS-1$ //$NON-NLS-2$  
111         return success;
112     }
113 
114     /**
115      * Attempts to acquire the lock.  Returns false if the lock is not available and
116      * true if the lock has been successfully acquired.
117      */
118     private synchronized boolean attempt() {
119         //return true if we already own the lock
120         //also, if nobody is waiting, grant the lock immediately
121         if ((currentOperationThread == Thread.currentThread()) || (currentOperationThread == null && operations.isEmpty())) {
122             depth++;
123             setCurrentOperationThread(Thread.currentThread());
124             return true;
125         }
126         return false;
127     }
128 
129     /* (non-Javadoc)
130      * @see org.eclipse.core.runtime.jobs.ISchedulingRule#contains(org.eclipse.core.runtime.jobs.ISchedulingRule)
131      */
132     public boolean contains(ISchedulingRule rule) {
133         return false;
134     }
135 
136     /**
137      * Returns null if acquired and a Semaphore object otherwise. If a
138      * waiting semaphore already exists for this thread, it will be returned, 
139      * otherwise a new semaphore will be created, enqueued, and returned.
140      */
141     private synchronized Semaphore createSemaphore() {
142         return attempt() ? null : enqueue(new Semaphore(Thread.currentThread()));
143     }
144 
145     /**
146      * Attempts to acquire this lock.  Callers will block  until this lock comes available to 
147      * them, or until the specified delay has elapsed.
148      */
149     private boolean doAcquire(Semaphore semaphore, long delay) throws InterruptedException   {
150         boolean success = false;
151         //notify hook to service pending syncExecs before falling asleep
152         if (manager.aboutToWait(this.currentOperationThread)) {
153             //hook granted immediate access
154             //remove semaphore for the lock request from the queue
155             //do not log in graph because this thread did not really get the lock
156             removeFromQueue(semaphore);
157             depth++;
158             manager.addLockThread(currentOperationThread, this);
159             return true;
160         }
161         //Make sure the semaphore is in the queue before we start waiting
162         //It might have been removed from the queue while servicing syncExecs
163         //This is will return our existing semaphore if it is still in the queue
164         semaphore = createSemaphore();
165         if (semaphore == null)
166             return true;
167         manager.addLockWaitThread(Thread.currentThread(), this);
168         try {
169             success = semaphore.acquire(delay);
170         } catch (InterruptedException   e) {
171             if (DEBUG)
172                 System.out.println("[" + Thread.currentThread() + "] Operation interrupted while waiting... :-|"); //$NON-NLS-1$ //$NON-NLS-2$
173             throw e;
174         }
175         if (success) {
176             depth++;
177             updateCurrentOperation();
178         } else {
179             removeFromQueue(semaphore);
180             manager.removeLockWaitThread(Thread.currentThread(), this);
181         }
182         return success;
183     }
184 
185     /**
186      * Releases this lock from the thread that used to own it.
187      * Grants this lock to the next thread in the queue.  
188      */
189     private synchronized void doRelease() {
190         //notify hook
191         manager.aboutToRelease();
192         depth = 0;
193         Semaphore next = (Semaphore) operations.peek();
194         setCurrentOperationThread(null);
195         if (next != null)
196             next.release();
197     }
198 
199     /**
200      * If there is another semaphore with the same runnable in the
201      * queue, the other is returned and the new one is not added.
202      */
203     private synchronized Semaphore enqueue(Semaphore newSemaphore) {
204         Semaphore semaphore = (Semaphore) operations.get(newSemaphore);
205         if (semaphore == null) {
206             operations.enqueue(newSemaphore);
207             return newSemaphore;
208         }
209         return semaphore;
210     }
211 
212     /**
213      * Suspend this lock by granting the lock to the next lock in the queue.
214      * Return the depth of the suspended lock. 
215      */
216     protected int forceRelease() {
217         int oldDepth = depth;
218         doRelease();
219         return oldDepth;
220     }
221 
222     /* (non-Javadoc)
223      * @see Locks.ILock#getDepth()
224      */
225     public int getDepth() {
226         return depth;
227     }
228 
229     /* (non-Javadoc)
230      * @see org.eclipse.core.runtime.jobs.ISchedulingRule#isConflicting(org.eclipse.core.runtime.jobs.ISchedulingRule)
231      */
232     public boolean isConflicting(ISchedulingRule rule) {
233         return rule == this;
234     }
235 
236     /* (non-Javadoc)
237      * @see Locks.ILock#release()
238      */
239     public void release() {
240         if (depth == 0)
241             return;
242         //only release the lock when the depth reaches zero
243         Assert.isTrue(depth >= 0, "Lock released too many times"); //$NON-NLS-1$
244         if (--depth == 0)
245             doRelease();
246         else
247             manager.removeLockThread(currentOperationThread, this);
248     }
249 
250     /**
251      * Removes a semaphore from the queue of waiting operations.
252      * 
253      * @param semaphore The semaphore to remove
254      */
255     private synchronized void removeFromQueue(Semaphore semaphore) {
256         operations.remove(semaphore);
257     }
258 
259     /**
260      * If newThread is null, release this lock from its previous owner.
261      * If newThread is not null, grant this lock to newThread.
262      */
263     private void setCurrentOperationThread(Thread   newThread) {
264         if ((currentOperationThread != null) && (newThread == null))
265             manager.removeLockThread(currentOperationThread, this);
266         this.currentOperationThread = newThread;
267         if (currentOperationThread != null)
268             manager.addLockThread(currentOperationThread, this);
269     }
270 
271     /**
272      * Forces the lock to be at the given depth.
273      * Used when re-acquiring a suspended lock.
274      */
275     protected void setDepth(int newDepth) {
276         for (int i = depth; i < newDepth; i++) {
277             manager.addLockThread(currentOperationThread, this);
278         }
279         this.depth = newDepth;
280     }
281 
282     /**
283      * For debugging purposes only.
284      */
285     public String   toString() {
286         return "OrderedLock (" + number + ")"; //$NON-NLS-1$ //$NON-NLS-2$
287     }
288 
289     /**
290      * This lock has just been granted to a new thread (the thread waited for it).
291      * Remove the request from the queue and update both the graph and the lock.
292      */
293     private synchronized void updateCurrentOperation() {
294         operations.dequeue();
295         setCurrentOperationThread(Thread.currentThread());
296     }
297 }
298
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags