diff --git a/runtime/gc/heap.cc b/runtime/gc/heap.cc
index 9755016..532b3ef 100644
--- a/runtime/gc/heap.cc
+++ b/runtime/gc/heap.cc
@@ -2014,10 +2014,14 @@
                static_cast<double>(space_size_before_compaction);
   }
   // Finish GC.
-  reference_processor_->EnqueueClearedReferences(self);
+  // Get the references we need to enqueue.
+  SelfDeletingTask* clear = reference_processor_->CollectClearedReferences(self);
   GrowForUtilization(semi_space_collector_);
   LogGC(kGcCauseHomogeneousSpaceCompact, collector);
   FinishGC(self, collector::kGcTypeFull);
+  // Enqueue any references after losing the GC locks.
+  clear->Run(self);
+  clear->Finalize();
   {
     ScopedObjectAccess soa(self);
     soa.Vm()->UnloadNativeLibraries();
@@ -2545,12 +2549,16 @@
   total_bytes_freed_ever_ += GetCurrentGcIteration()->GetFreedBytes() +
       GetCurrentGcIteration()->GetFreedLargeObjectBytes();
   RequestTrim(self);
-  // Enqueue cleared references.
-  reference_processor_->EnqueueClearedReferences(self);
+  // Collect cleared references.
+  SelfDeletingTask* clear = reference_processor_->CollectClearedReferences(self);
   // Grow the heap so that we know when to perform the next GC.
   GrowForUtilization(collector, bytes_allocated_before_gc);
   LogGC(gc_cause, collector);
   FinishGC(self, gc_type);
+  // Actually enqueue all cleared references. Do this after the GC has officially finished since
+  // otherwise we can deadlock.
+  clear->Run(self);
+  clear->Finalize();
   // Inform DDMS that a GC completed.
   Dbg::GcDidFinish();
 
diff --git a/runtime/gc/reference_processor.cc b/runtime/gc/reference_processor.cc
index b0fc7a6..498013e 100644
--- a/runtime/gc/reference_processor.cc
+++ b/runtime/gc/reference_processor.cc
@@ -31,6 +31,7 @@
 #include "reflection.h"
 #include "scoped_thread_state_change-inl.h"
 #include "task_processor.h"
+#include "thread_pool.h"
 #include "well_known_classes.h"
 
 namespace art {
@@ -289,8 +290,11 @@
   const jobject cleared_references_;
 };
 
-void ReferenceProcessor::EnqueueClearedReferences(Thread* self) {
+SelfDeletingTask* ReferenceProcessor::CollectClearedReferences(Thread* self) {
   Locks::mutator_lock_->AssertNotHeld(self);
+  // By default we don't actually need to do anything. Just return this no-op task to avoid having
+  // to put in ifs.
+  std::unique_ptr<SelfDeletingTask> result(new FunctionTask([](Thread*) {}));
   // When a runtime isn't started there are no reference queues to care about so ignore.
   if (!cleared_references_.IsEmpty()) {
     if (LIKELY(Runtime::Current()->IsStarted())) {
@@ -306,12 +310,12 @@
         Runtime::Current()->GetHeap()->GetTaskProcessor()->AddTask(
             self, new ClearedReferenceTask(cleared_references));
       } else {
-        ClearedReferenceTask task(cleared_references);
-        task.Run(self);
+        result.reset(new ClearedReferenceTask(cleared_references));
       }
     }
     cleared_references_.Clear();
   }
+  return result.release();
 }
 
 void ReferenceProcessor::ClearReferent(ObjPtr<mirror::Reference> ref) {
diff --git a/runtime/gc/reference_processor.h b/runtime/gc/reference_processor.h
index c1c9a3c..54de5cc 100644
--- a/runtime/gc/reference_processor.h
+++ b/runtime/gc/reference_processor.h
@@ -61,7 +61,9 @@
   // Decode the referent, may block if references are being processed.
   ObjPtr<mirror::Object> GetReferent(Thread* self, ObjPtr<mirror::Reference> reference)
       REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Locks::reference_processor_lock_);
-  void EnqueueClearedReferences(Thread* self) REQUIRES(!Locks::mutator_lock_);
+  // Collects the cleared references and returns a task, to be executed after FinishGC, that will
+  // enqueue all of them.
+  SelfDeletingTask* CollectClearedReferences(Thread* self) REQUIRES(!Locks::mutator_lock_);
   void DelayReferenceReferent(ObjPtr<mirror::Class> klass,
                               ObjPtr<mirror::Reference> ref,
                               collector::GarbageCollector* collector)