Fixed queue so conflicting jobs cannot overtake
diff --git a/bundles/org.eclipse.core.runtime/src/org/eclipse/core/internal/jobs/InternalJob.java b/bundles/org.eclipse.core.runtime/src/org/eclipse/core/internal/jobs/InternalJob.java index 12bf311..c456cb5 100644 --- a/bundles/org.eclipse.core.runtime/src/org/eclipse/core/internal/jobs/InternalJob.java +++ b/bundles/org.eclipse.core.runtime/src/org/eclipse/core/internal/jobs/InternalJob.java
@@ -18,7 +18,7 @@ /** * Internal implementation class for jobs. */ -public abstract class InternalJob extends ListEntry implements Comparable { +public abstract class InternalJob implements Comparable { private static final JobManager manager = JobManager.getInstance(); private static int nextJobNumber = 0; @@ -34,10 +34,12 @@ */ private long startTime; private int state = Job.NONE; + private InternalJob next; + private InternalJob previous; /* (non-Javadoc) - * @see Job#addJobListener(IJobListener) + * @see Job#addJobListener(IJobChangeListener) */ - protected void addJobListener(IJobListener listener) { + protected void addJobChangeListener(IJobChangeListener listener) { if (listeners == null) listeners = Collections.synchronizedList(new ArrayList(2)); listeners.add(listener); @@ -81,10 +83,18 @@ void internalSetPriority(int newPriority) { this.priority = newPriority; } - /* (non-Javadoc) - * @see Job#removeJobListener(IJobListener) + /** + * Returns true if this job conflicts with the given job, and false otherwise. */ - protected void removeJobListener(IJobListener listener) { + boolean isConflicting(InternalJob otherJob) { + ISchedulingRule myRule = schedulingRule; + ISchedulingRule otherRule = otherJob.getRule(); + return myRule != null && otherRule != null && myRule.isConflicting(otherRule); + } + /* (non-Javadoc) + * @see Job#removeJobListener(IJobChangeListener) + */ + protected void removeJobChangeListener(IJobChangeListener listener) { if (listeners != null) listeners.remove(listener); if (listeners.isEmpty()) @@ -120,4 +130,44 @@ protected void wakeUp() { manager.wakeUp(this); } + /** + * Adds an entry at the end of the list of which this item is the head. + */ + final void addLast(InternalJob entry) { + if (previous == null) { + previous = entry; + entry.previous = null; + } else + previous.addLast(entry); + } + /** + * Returns the next entry (ahead of this one) in the list, or null if there is no next entry + */ + final InternalJob next() { + return next; + } + /** + * Returns the previous entry (behind this one) in the list, or null if there is no previous entry + */ + final InternalJob previous() { + return previous; + } + final void setNext(InternalJob entry) { + this.next = entry; + } + final void setPrevious(InternalJob entry) { + this.previous = entry; + } + /** + * Removes this entry from any list it belongs to. Returns the receiver. + */ + final InternalJob remove() { + if (next != null) + next.setPrevious(previous); + if (previous != null) + previous.setNext(next); + next = null; + previous = null; + return this; + } } \ No newline at end of file
diff --git a/bundles/org.eclipse.core.runtime/src/org/eclipse/core/internal/jobs/JobListeners.java b/bundles/org.eclipse.core.runtime/src/org/eclipse/core/internal/jobs/JobListeners.java index d807e06..a803a82 100644 --- a/bundles/org.eclipse.core.runtime/src/org/eclipse/core/internal/jobs/JobListeners.java +++ b/bundles/org.eclipse.core.runtime/src/org/eclipse/core/internal/jobs/JobListeners.java
@@ -12,44 +12,44 @@ import java.util.*; import org.eclipse.core.runtime.IStatus; -import org.eclipse.core.runtime.jobs.IJobListener; +import org.eclipse.core.runtime.jobs.IJobChangeListener; import org.eclipse.core.runtime.jobs.Job; /** * Responsible for notifying all job listeners about job lifecycle events. Uses a * specialized iterator to ensure the complex iteration logic is contained in one place. */ -public class JobListeners implements IJobListener { +public class JobListeners implements IJobChangeListener { interface IListenerDoit { - public void notify(IJobListener listener, Job job, IStatus result); + public void notify(IJobChangeListener listener, Job job, IStatus result); } private final IListenerDoit aboutToRun = new IListenerDoit() { - public void notify(IJobListener listener, Job job, IStatus result) { + public void notify(IJobChangeListener listener, Job job, IStatus result) { listener.aboutToRun(job); } }; private final IListenerDoit awake = new IListenerDoit() { - public void notify(IJobListener listener, Job job, IStatus result) { + public void notify(IJobChangeListener listener, Job job, IStatus result) { listener.awake(job); } }; private final IListenerDoit done = new IListenerDoit() { - public void notify(IJobListener listener, Job job, IStatus result) { + public void notify(IJobChangeListener listener, Job job, IStatus result) { listener.done(job, result); } }; private final IListenerDoit running = new IListenerDoit() { - public void notify(IJobListener listener, Job job, IStatus result) { + public void notify(IJobChangeListener listener, Job job, IStatus result) { listener.running(job); } }; private final IListenerDoit scheduled = new IListenerDoit() { - public void notify(IJobListener listener, Job job, IStatus result) { + public void notify(IJobChangeListener listener, Job job, IStatus result) { listener.scheduled(job); } }; private final IListenerDoit sleeping = new IListenerDoit() { - public void notify(IJobListener listener, Job job, IStatus result) { + public void notify(IJobChangeListener listener, Job job, IStatus result) { listener.sleeping(job); } }; @@ -67,7 +67,7 @@ int size = global.size(); for (int i = 0; i < size; i++) { //note: tolerate concurrent modification - IJobListener listener = (IJobListener) global.get(i); + IJobChangeListener listener = (IJobChangeListener) global.get(i); if (listener != null) doit.notify(listener, job, result); } @@ -77,16 +77,16 @@ size = local.size(); for (int i = 0; i < size; i++) { //note: tolerate concurrent modification - IJobListener listener = (IJobListener) global.get(i); + IJobChangeListener listener = (IJobChangeListener) global.get(i); if (listener != null) doit.notify(listener, job, result); } } } - public void add(IJobListener listener) { + public void add(IJobChangeListener listener) { global.add(listener); } - public void remove(IJobListener listener) { + public void remove(IJobChangeListener listener) { global.remove(listener); } public void aboutToRun(Job job) {
diff --git a/bundles/org.eclipse.core.runtime/src/org/eclipse/core/internal/jobs/JobManager.java b/bundles/org.eclipse.core.runtime/src/org/eclipse/core/internal/jobs/JobManager.java index 9b01aab..5a4d6af 100644 --- a/bundles/org.eclipse.core.runtime/src/org/eclipse/core/internal/jobs/JobManager.java +++ b/bundles/org.eclipse.core.runtime/src/org/eclipse/core/internal/jobs/JobManager.java
@@ -57,21 +57,21 @@ /** * Jobs that are currently running. */ - private final HashSet running = new HashSet(10); + private final HashSet running; /** * Jobs that are sleeping. Some sleeping jobs are scheduled to wake * up at a given start time, while others will sleep indefinitely until woken. */ - private final PriorityQueue sleeping = new PriorityQueue(); + private final JobQueue sleeping; /** * jobs that are waiting to be run */ - private final PriorityQueue waiting = new PriorityQueue(); + private final JobQueue waiting; public static synchronized JobManager getInstance() { if (instance == null) { - instance = new JobManager(); + new JobManager(); } return instance; } @@ -81,15 +81,19 @@ instance = null; } private JobManager() { + instance = this; synchronized (lock) { alive = true; + waiting = new JobQueue(); + sleeping = new JobQueue(); + running = new HashSet(10); pool = new WorkerPool(this); } } /* (non-Javadoc) - * @see org.eclipse.core.runtime.jobs.IJobManager#addJobListener(org.eclipse.core.runtime.jobs.IJobListener) + * @see org.eclipse.core.runtime.jobs.IJobManager#addJobListener(org.eclipse.core.runtime.jobs.IJobChangeListener) */ - public void addJobListener(IJobListener listener) { + public void addJobChangeListener(IJobChangeListener listener) { jobListeners.add(listener); } /** @@ -195,7 +199,7 @@ */ protected void endJob(Job job, IStatus result) { InternalJob internalJob = (InternalJob)job; - ListEntry blocked = null; + InternalJob blocked = null; synchronized (lock) { //if the job is finishing asynchronously, there is nothing more to do for now if (result == Job.ASYNC_FINISH) { @@ -205,15 +209,15 @@ internalJob.setState(Job.NONE); internalJob.setMonitor(null); running.remove(job); - blocked = job.next(); - job.setNext(null); + blocked = internalJob.previous(); + internalJob.setPrevious(null); } //add any blocked jobs back to the wait queue while (blocked != null) { - ListEntry next = blocked.next(); + InternalJob previous = blocked.previous(); waiting.enqueue(blocked); - pool.jobQueued((InternalJob)blocked); - blocked = next; + pool.jobQueued(blocked); + blocked = previous; } //notify listeners outside sync block jobListeners.done(job, result); @@ -223,21 +227,19 @@ * @see org.eclipse.core.runtime.jobs.IJobManager#find(java.lang.String) */ public Job[] find(String family) { - ArrayList members = select(family); + List members = select(family); return (Job[]) members.toArray(new Job[members.size()]); } /** * Returns a running job whose scheduling rule conflicts with the scheduling rule * of the given waiting job. Returns null if there are no conflicting jobs. */ - private Job findBlockingJob(Job waiting) { - ISchedulingRule waitingRule = waiting.getRule(); - if (waitingRule == null) + private InternalJob findBlockingJob(InternalJob waiting) { + if (waiting.getRule() == null) return null; for (Iterator it = running.iterator(); it.hasNext();) { Job job = (Job) it.next(); - ISchedulingRule testRule = job.getRule(); - if (testRule != null && testRule.isConflicting(waitingRule)) + if (waiting.isConflicting(job)) return job; } return null; @@ -266,26 +268,25 @@ job = (InternalJob)sleeping.peek(); } //process the wait queue until we find a job whose rules are satisfied. - Job next = (Job)waiting.dequeue(); - while (next != null) { - Job blocker = findBlockingJob(next); + InternalJob next; + while ((next = waiting.dequeue()) != null) { + InternalJob blocker = findBlockingJob(next); if (blocker == null) break; //queue this job after the job that's blocking it blocker.addLast(next); - next = (Job)waiting.dequeue(); } //the job to run must be in the running list before we exit //the sync block, otherwise two jobs with conflicting rules could start at once if (next != null) running.add(next); - return next; + return (Job)next; } } /* (non-Javadoc) - * @see org.eclipse.core.runtime.jobs.IJobManager#removeJobListener(org.eclipse.core.runtime.jobs.IJobListener) + * @see org.eclipse.core.runtime.jobs.IJobManager#removeJobListener(org.eclipse.core.runtime.jobs.IJobChangeListener) */ - public void removeJobListener(IJobListener listener) { + public void removeJobChangeListener(IJobChangeListener listener) { jobListeners.remove(listener); } /* (non-Javadoc) @@ -313,18 +314,21 @@ /** * Adds all family members in the list of jobs to the collection */ - private void select(ArrayList members, String family, Job job) { - while (job != null) { + private void select(List members, String family, Job firstJob) { + if (firstJob == null) + return; + Job job = firstJob; + do { if (job.belongsTo(family)) members.add(job); - job = (Job)job.next(); - } + job = (Job)((InternalJob)job).previous(); + } while (job != null && job != firstJob); } /** * Returns a list of all jobs known to the job manager that belong to the given family. */ - private ArrayList select(String family) { - ArrayList members = new ArrayList(); + private List select(String family) { + List members = new ArrayList(); synchronized (lock) { for (Iterator it = running.iterator(); it.hasNext();) { select(members, family, (Job)it.next()); @@ -444,6 +448,12 @@ * @see org.eclipse.core.runtime.jobs.IJobManager#wait(org.eclipse.core.runtime.jobs.Job, org.eclipse.core.runtime.IProgressMonitor) */ public void wait(Job job, IProgressMonitor monitor) { + synchronized (lock) { + //compute set of all jobs that must run before this one + //add a listener that removes jobs from the blocking set when they finish + + } + //wait until listener notifies this thread. } /* (non-Javadoc) * @see IJobManager#wait(String, IProgressMonitor)
diff --git a/bundles/org.eclipse.core.runtime/src/org/eclipse/core/internal/jobs/JobQueue.java b/bundles/org.eclipse.core.runtime/src/org/eclipse/core/internal/jobs/JobQueue.java new file mode 100644 index 0000000..97ca2c4 --- /dev/null +++ b/bundles/org.eclipse.core.runtime/src/org/eclipse/core/internal/jobs/JobQueue.java
@@ -0,0 +1,111 @@ +/********************************************************************** + * Copyright (c) 2003 IBM Corporation and others. All rights reserved. This + * program and the accompanying materials are made available under the terms of + * the Common Public License v1.0 which accompanies this distribution, and is + * available at http://www.eclipse.org/legal/cpl-v10.html + * + * Contributors: + * IBM - Initial API and implementation + **********************************************************************/ +package org.eclipse.core.internal.jobs; + +/** + * A linked list based priority queue. + * Either the elements in the queue must implement Comparable, or a Comparator + * must be provided. + */ +public class JobQueue { + /** + * The dummy entry sits between the head and the tail of the queue. + * dummy.previous() is the head, and dummy.next() is the tail. + */ + private final InternalJob dummy; + + /** + * Create a new job queue. + */ + public JobQueue() { + //compareTo on dummy is never called + dummy = new InternalJob() {}; + dummy.setNext(dummy); + dummy.setPrevious(dummy); + } + /** + * remove all elements + */ + public void clear() { + dummy.setNext(dummy); + dummy.setPrevious(dummy); + } + /** + * Returns true if the given element is in the queue, and false otherwise. + * + * NOTE: Containment is based on identity, not equality. + */ + public boolean contains(Object object) { + InternalJob entry = dummy.next(); + while (entry != dummy && entry != object) + entry = entry.next(); + return entry == object; + } + /** + * Return and remove the element with highest priority, or + * null if empty. + */ + public InternalJob dequeue() { + InternalJob toRemove = dummy.previous(); + if (toRemove == dummy) + return null; + return toRemove.remove(); + } + /** + * Adds an entire list of entries to the queue + */ + public void enqueueAll(InternalJob newEntry) { + while (newEntry != null) { + InternalJob previous = newEntry.previous(); + enqueue(newEntry); + newEntry = previous; + } + } + /** + * Adds an item to the queue + */ + public void enqueue(InternalJob newEntry) { + InternalJob tail = dummy.next(); + //overtake lower priority jobs that are not conflicting + while (tail != dummy && tail.compareTo(newEntry) < 0 && !newEntry.isConflicting(tail)) + tail = tail.next(); + //new entry is smaller than tail + newEntry.setNext(tail); + newEntry.setPrevious(tail.previous()); + tail.previous().setNext(newEntry); + tail.setPrevious(newEntry); + } + /** + * Removes the given element from the queue. + */ + public void remove(InternalJob toRemove) { + toRemove.remove(); + //previous of toRemove might now bubble up + } + /** + * The given object has changed priority. Reshuffle the heap until it is valid. + */ + public void resort(InternalJob entry) { + remove(entry); + enqueue(entry); + } + /** + * Returns true if the queue is empty, and false otherwise. + */ + public boolean isEmpty() { + return dummy.next() == dummy; + } + /** + * Return greatest element without removing it, or null if empty + */ + public Object peek() { + return dummy.next() == dummy ? null : dummy.next(); + } +} \ No newline at end of file
diff --git a/bundles/org.eclipse.core.runtime/src/org/eclipse/core/internal/jobs/ListEntry.java b/bundles/org.eclipse.core.runtime/src/org/eclipse/core/internal/jobs/ListEntry.java deleted file mode 100644 index 9ef7c3e..0000000 --- a/bundles/org.eclipse.core.runtime/src/org/eclipse/core/internal/jobs/ListEntry.java +++ /dev/null
@@ -1,43 +0,0 @@ -/********************************************************************** - * Copyright (c) 2003 IBM Corporation and others. All rights reserved. This - * program and the accompanying materials are made available under the terms of - * the Common Public License v1.0 which accompanies this distribution, and is - * available at http://www.eclipse.org/legal/cpl-v10.html - * - * Contributors: - * IBM - Initial API and implementation - **********************************************************************/ -package org.eclipse.core.internal.jobs; - -/** - * An item in a linked list - */ -public class ListEntry { - private ListEntry next; - /** - * Adds an entry at the end of the list of which this item is the head. - */ - protected final void addLast(ListEntry entry) { - if (next == null) { - next = entry; - entry.next = null; - } else - next.addLast(entry); - } - /** - * Adds an entry immediately after this one in the list. - */ - protected final void insertNext(ListEntry entry) { - entry.next = this.next; - this.next = entry; - } - /** - * Returns the next entry in the list, or null if there is no next entry - */ - protected final ListEntry next() { - return next; - } - protected final void setNext(ListEntry entry) { - this.next = entry; - } -} \ No newline at end of file
diff --git a/bundles/org.eclipse.core.runtime/src/org/eclipse/core/internal/jobs/PriorityQueue.java b/bundles/org.eclipse.core.runtime/src/org/eclipse/core/internal/jobs/PriorityQueue.java deleted file mode 100644 index da02239..0000000 --- a/bundles/org.eclipse.core.runtime/src/org/eclipse/core/internal/jobs/PriorityQueue.java +++ /dev/null
@@ -1,154 +0,0 @@ -/********************************************************************** - * Copyright (c) 2003 IBM Corporation and others. All rights reserved. This - * program and the accompanying materials are made available under the terms of - * the Common Public License v1.0 which accompanies this distribution, and is - * available at http://www.eclipse.org/legal/cpl-v10.html - * - * Contributors: - * IBM - Initial API and implementation - **********************************************************************/ -package org.eclipse.core.internal.jobs; - -import java.util.Comparator; - -/** - * A linked list based priority queue. - * Either the elements in the queue must implement Comparable, or a Comparator - * must be provided. - */ -public class PriorityQueue { - private final Comparator comparator; - // the head of the queue - private ListEntry head = null; - - /** - * Create a new queue. Using this constructor assumes the - * objects in the queue implement the <code>java.lang.Comparable</code> - * interface - */ - public PriorityQueue() { - this(null); - } - /** - * Create a queue with the given comparator - */ - public PriorityQueue(Comparator comparator) { - this.comparator = comparator; - } - /** - * remove all elements - */ - public void clear() { - head = null; - } - /** - * perform element comparisons - */ - protected int compare(Object a, Object b) { - if (comparator == null) - return ((Comparable) a).compareTo(b); - else - return comparator.compare(a, b); - } - /** - * Returns true if the given element is in the queue, and false otherwise. - * - * NOTE: Containment is based on identity, not equality. - */ - public boolean contains(Object object) { - ListEntry entry = head; - while (entry != null && entry != object) - entry = entry.next(); - return entry != null; - } - /** - * Return and remove the element with highest priority, or - * null if empty. - */ - public ListEntry dequeue() { - if (head == null) - return null; - ListEntry max = head; - head = head.next(); - max.setNext(null); - return max; - } - /** - * Adds an entire list of entries to the queue - */ - public void enqueueAll(ListEntry newEntry) { - while (newEntry != null) { - ListEntry next = newEntry.next(); - enqueue(newEntry); - newEntry = next; - } - } - /** - * Adds an item to the queue - */ - public void enqueue(ListEntry newEntry) { - if (head == null) { - head = newEntry; - newEntry.setNext(null); - return; - } - if (compare(head, newEntry) > 0) { - newEntry.setNext(head); - head = newEntry; - return; - } - ListEntry greater = head; - ListEntry next = greater.next(); - while (next != null && (compare(next, newEntry) <= 0)) { - greater = next; - next = greater.next(); - } - //insert the new entry between greater and next - greater.insertNext(newEntry); - } - /** - * Removes the given element from the heap. Returns true if the element was - * removed, and false otherwise. - */ - public boolean remove(ListEntry toRemove) { - if (head == null) - return false; - if (toRemove == head) { - head = head.next(); - toRemove.setNext(null); - return true; - } - ListEntry previous = head; - ListEntry next = previous.next(); - while (next != null && next != toRemove) { - previous = next; - next = next.next(); - } - if (next != null) { - previous.setNext(next.next()); - toRemove.setNext(null); - return true; - } - return false; - } - /** - * The given object has changed priority. Reshuffle the heap until it is valid. - */ - public void resort(ListEntry entry) { - if (remove(entry)) - enqueue(entry); - - } - /** - * Returns true if the queue is empty, and false otherwise. - */ - public boolean isEmpty() { - return head == null; - } - /** - * Return greatest element without removing it, or null if empty - */ - public Object peek() { - return head; - } -} \ No newline at end of file