diff --git a/hyracks-control-nc/src/main/java/edu/uci/ics/hyracks/control/nc/Joblet.java b/hyracks-control-nc/src/main/java/edu/uci/ics/hyracks/control/nc/Joblet.java
index e8b282c..8f7bc4a 100644
--- a/hyracks-control-nc/src/main/java/edu/uci/ics/hyracks/control/nc/Joblet.java
+++ b/hyracks-control-nc/src/main/java/edu/uci/ics/hyracks/control/nc/Joblet.java
@@ -179,7 +179,12 @@
     }
 
     public void close() {
-        deallocatableRegistry.close();
+        nodeController.getExecutor().execute(new Runnable() {
+            @Override
+            public void run() {
+                deallocatableRegistry.close();
+            }
+        });
     }
 
     @Override
@@ -257,5 +262,10 @@
         }
         close();
         cleanupPending = false;
+        try {
+            nodeController.getClusterController().notifyJobletCleanup(jobId, nodeController.getId());
+        } catch (Exception e) {
+            e.printStackTrace();
+        }
     }
 }
\ No newline at end of file
diff --git a/hyracks-control-nc/src/main/java/edu/uci/ics/hyracks/control/nc/partitions/PartitionManager.java b/hyracks-control-nc/src/main/java/edu/uci/ics/hyracks/control/nc/partitions/PartitionManager.java
index baa50a1..ce40fe6 100644
--- a/hyracks-control-nc/src/main/java/edu/uci/ics/hyracks/control/nc/partitions/PartitionManager.java
+++ b/hyracks-control-nc/src/main/java/edu/uci/ics/hyracks/control/nc/partitions/PartitionManager.java
@@ -15,6 +15,7 @@
 package edu.uci.ics.hyracks.control.nc.partitions;
 
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.HashMap;
 import java.util.Iterator;
 import java.util.List;
@@ -79,13 +80,13 @@
         return partitionMap.get(pid).get(0);
     }
 
-    public synchronized void unregisterPartitions(JobId jobId) {
+    public synchronized void unregisterPartitions(JobId jobId, Collection<IPartition> unregisteredPartitions) {
         for (Iterator<Map.Entry<PartitionId, List<IPartition>>> i = partitionMap.entrySet().iterator(); i.hasNext();) {
             Map.Entry<PartitionId, List<IPartition>> e = i.next();
             PartitionId pid = e.getKey();
             if (jobId.equals(pid.getJobId())) {
                 for (IPartition p : e.getValue()) {
-                    p.deallocate();
+                    unregisteredPartitions.add(p);
                 }
                 i.remove();
             }
diff --git a/hyracks-control-nc/src/main/java/edu/uci/ics/hyracks/control/nc/work/CleanupJobletWork.java b/hyracks-control-nc/src/main/java/edu/uci/ics/hyracks/control/nc/work/CleanupJobletWork.java
index dce7c13..b75a1fc 100644
--- a/hyracks-control-nc/src/main/java/edu/uci/ics/hyracks/control/nc/work/CleanupJobletWork.java
+++ b/hyracks-control-nc/src/main/java/edu/uci/ics/hyracks/control/nc/work/CleanupJobletWork.java
@@ -14,12 +14,15 @@
  */
 package edu.uci.ics.hyracks.control.nc.work;
 
+import java.util.ArrayList;
+import java.util.List;
 import java.util.Map;
 import java.util.logging.Level;
 import java.util.logging.Logger;
 
 import edu.uci.ics.hyracks.api.job.JobId;
 import edu.uci.ics.hyracks.api.job.JobStatus;
+import edu.uci.ics.hyracks.api.partitions.IPartition;
 import edu.uci.ics.hyracks.control.common.work.SynchronizableWork;
 import edu.uci.ics.hyracks.control.nc.Joblet;
 import edu.uci.ics.hyracks.control.nc.NodeControllerService;
@@ -44,12 +47,20 @@
         if (LOGGER.isLoggable(Level.INFO)) {
             LOGGER.info("Cleaning up after job: " + jobId);
         }
-        ncs.getPartitionManager().unregisterPartitions(jobId);
+        final List<IPartition> unregisteredPartitions = new ArrayList<IPartition>();
+        ncs.getPartitionManager().unregisterPartitions(jobId, unregisteredPartitions);
+        ncs.getExecutor().execute(new Runnable() {
+            @Override
+            public void run() {
+                for (IPartition p : unregisteredPartitions) {
+                    p.deallocate();
+                }
+            }
+        });
         Map<JobId, Joblet> jobletMap = ncs.getJobletMap();
         Joblet joblet = jobletMap.remove(jobId);
         if (joblet != null) {
             joblet.cleanup(status);
         }
-        ncs.getClusterController().notifyJobletCleanup(jobId, ncs.getId());
     }
 }
\ No newline at end of file