diff --git a/services/surfaceflinger/LocklessQueue.h b/services/surfaceflinger/LocklessQueue.h
new file mode 100644
index 0000000..6b63360
--- /dev/null
+++ b/services/surfaceflinger/LocklessQueue.h
@@ -0,0 +1,82 @@
+/*
+ * Copyright 2022 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+#include <atomic>
+#include <optional>
+
+template <typename T>
+// Single consumer multi producer stack. We can understand the two operations independently to see
+// why they are without race condition.
+//
+// push is responsible for maintaining a linked list stored in mPush, and called from multiple
+// threads without lock. We can see that if two threads never observe the same value from
+// mPush.load, it just functions as a normal linked list. In the case where two threads observe the
+// same value, one of them has to execute the compare_exchange first. The one that doesn't execute
+// the compare exchange first, will receive false from compare_exchange. previousHead is updated (by
+// compare_exchange) to the most recent value of mPush, and we try again. It's relatively clear to
+// see that the process can repeat with an arbitrary number of threads.
+//
+// Pop is much simpler. If mPop is empty (as it begins) it atomically exchanges
+// the entire push list with null. This is safe, since the only other reader (push)
+// of mPush will retry if it changes in between it's read and atomic compare. We
+// then store the list and pop one element.
+//
+// If we already had something in the pop list we just pop directly.
+class LocklessQueue {
+public:
+    class Entry {
+    public:
+        T mValue;
+        std::atomic<Entry*> mNext;
+        Entry(T value) : mValue(value) {}
+    };
+    std::atomic<Entry*> mPush = nullptr;
+    std::atomic<Entry*> mPop = nullptr;
+    bool isEmpty() { return (mPush.load() == nullptr) && (mPop.load() == nullptr); }
+
+    void push(T value) {
+        Entry* entry = new Entry(value);
+        Entry* previousHead = mPush.load(/*std::memory_order_relaxed*/);
+        do {
+            entry->mNext = previousHead;
+        } while (!mPush.compare_exchange_weak(previousHead, entry)); /*std::memory_order_release*/
+    }
+    std::optional<T> pop() {
+        Entry* popped = mPop.load(/*std::memory_order_acquire*/);
+        if (popped) {
+            // Single consumer so this is fine
+            mPop.store(popped->mNext /* , std::memory_order_release */);
+            auto value = popped->mValue;
+            delete popped;
+            return std::move(value);
+        } else {
+            Entry* grabbedList = mPush.exchange(nullptr /* , std::memory_order_acquire */);
+            if (!grabbedList) return std::nullopt;
+            // Reverse the list
+            while (grabbedList->mNext) {
+                Entry* next = grabbedList->mNext;
+                grabbedList->mNext = popped;
+                popped = grabbedList;
+                grabbedList = next;
+            }
+            mPop.store(popped /* , std::memory_order_release */);
+            auto value = grabbedList->mValue;
+            delete grabbedList;
+            return std::move(value);
+        }
+    }
+};
diff --git a/services/surfaceflinger/SurfaceFlinger.cpp b/services/surfaceflinger/SurfaceFlinger.cpp
index 9ef8e7b..ce54f50 100644
--- a/services/surfaceflinger/SurfaceFlinger.cpp
+++ b/services/surfaceflinger/SurfaceFlinger.cpp
@@ -3753,6 +3753,8 @@
 
             transactions.emplace_back(std::move(transaction));
             transactionQueue.pop();
+            mPendingTransactionCount--;
+            ATRACE_INT("TransactionQueue", mPendingTransactionCount.load());
         }
 
         if (transactionQueue.empty()) {
@@ -3776,8 +3778,6 @@
     {
         Mutex::Autolock _l(mStateLock);
         {
-            Mutex::Autolock _l(mQueueLock);
-
             int lastTransactionsPendingBarrier = 0;
             int transactionsPendingBarrier = 0;
             // First collect transactions from the pending transaction queues.
@@ -3790,8 +3790,12 @@
             // Second, collect transactions from the transaction queue.
             // Here as well we are not allowing unsignaled buffers for the same
             // reason as above.
-            while (!mTransactionQueue.empty()) {
-                auto& transaction = mTransactionQueue.front();
+            while (!mLocklessTransactionQueue.isEmpty()) {
+                auto maybeTransaction = mLocklessTransactionQueue.pop();
+                if (!maybeTransaction.has_value()) {
+                    break;
+                }
+                auto transaction = maybeTransaction.value();
                 const bool pendingTransactions =
                         mPendingTransactionQueues.find(transaction.applyToken) !=
                         mPendingTransactionQueues.end();
@@ -3829,9 +3833,9 @@
                         }
                     });
                     transactions.emplace_back(std::move(transaction));
+                    mPendingTransactionCount--;
+                    ATRACE_INT("TransactionQueue", mPendingTransactionCount.load());
                 }
-                mTransactionQueue.pop_front();
-                ATRACE_INT("TransactionQueue", mTransactionQueue.size());
             }
 
             // Transactions with a buffer pending on a barrier may be on a different applyToken
@@ -3892,8 +3896,7 @@
 }
 
 bool SurfaceFlinger::transactionFlushNeeded() {
-    Mutex::Autolock _l(mQueueLock);
-    return !mPendingTransactionQueues.empty() || !mTransactionQueue.empty();
+    return !mPendingTransactionQueues.empty() || !mLocklessTransactionQueue.isEmpty();
 }
 
 bool SurfaceFlinger::frameIsEarly(nsecs_t expectedPresentTime, int64_t vsyncId) const {
@@ -4060,17 +4063,15 @@
 
 void SurfaceFlinger::queueTransaction(TransactionState& state) {
     state.queueTime = systemTime();
-
-    Mutex::Autolock lock(mQueueLock);
-
     // Generate a CountDownLatch pending state if this is a synchronous transaction.
     if (state.flags & eSynchronous) {
         state.transactionCommittedSignal =
                 std::make_shared<CountDownLatch>(CountDownLatch::eSyncTransaction);
     }
 
-    mTransactionQueue.emplace_back(state);
-    ATRACE_INT("TransactionQueue", mTransactionQueue.size());
+    mLocklessTransactionQueue.push(state);
+    mPendingTransactionCount++;
+    ATRACE_INT("TransactionQueue", mPendingTransactionCount.load());
 
     const auto schedule = [](uint32_t flags) {
         if (flags & eEarlyWakeupEnd) return TransactionSchedule::EarlyEnd;
diff --git a/services/surfaceflinger/SurfaceFlinger.h b/services/surfaceflinger/SurfaceFlinger.h
index 7d23c3c..1e4fae7 100644
--- a/services/surfaceflinger/SurfaceFlinger.h
+++ b/services/surfaceflinger/SurfaceFlinger.h
@@ -65,6 +65,7 @@
 #include "FlagManager.h"
 #include "FrameTracker.h"
 #include "LayerVector.h"
+#include "LocklessQueue.h"
 #include "Scheduler/RefreshRateConfigs.h"
 #include "Scheduler/RefreshRateStats.h"
 #include "Scheduler/Scheduler.h"
@@ -762,13 +763,13 @@
             std::vector<TransactionState>& transactions,
             std::unordered_map<sp<IBinder>, uint64_t, SpHash<IBinder>>& bufferLayersReadyToPresent,
             std::unordered_set<sp<IBinder>, SpHash<IBinder>>& applyTokensWithUnsignaledTransactions,
-            bool tryApplyUnsignaled) REQUIRES(mStateLock, mQueueLock);
+            bool tryApplyUnsignaled) REQUIRES(mStateLock);
 
     int flushUnsignaledPendingTransactionQueues(
             std::vector<TransactionState>& transactions,
             std::unordered_map<sp<IBinder>, uint64_t, SpHash<IBinder>>& bufferLayersReadyToPresent,
             std::unordered_set<sp<IBinder>, SpHash<IBinder>>& applyTokensWithUnsignaledTransactions)
-            REQUIRES(mStateLock, mQueueLock);
+            REQUIRES(mStateLock);
 
     uint32_t setClientStateLocked(const FrameTimelineInfo&, ComposerState&,
                                   int64_t desiredPresentTime, bool isAutoTimestamp,
@@ -1098,7 +1099,7 @@
     status_t CheckTransactCodeCredentials(uint32_t code);
 
     // Add transaction to the Transaction Queue
-    void queueTransaction(TransactionState& state) EXCLUDES(mQueueLock);
+    void queueTransaction(TransactionState& state);
     void waitForSynchronousTransaction(const CountDownLatch& transactionCommittedSignal);
     void signalSynchronousTransactions(const uint32_t flag);
 
@@ -1262,11 +1263,11 @@
     uint32_t mTexturePoolSize = 0;
     std::vector<uint32_t> mTexturePool;
 
-    mutable Mutex mQueueLock;
     Condition mTransactionQueueCV;
     std::unordered_map<sp<IBinder>, std::queue<TransactionState>, IListenerHash>
-            mPendingTransactionQueues GUARDED_BY(mQueueLock);
-    std::deque<TransactionState> mTransactionQueue GUARDED_BY(mQueueLock);
+            mPendingTransactionQueues;
+    LocklessQueue<TransactionState> mLocklessTransactionQueue;
+    std::atomic<size_t> mPendingTransactionCount = 0;
     /*
      * Feature prototyping
      */
diff --git a/services/surfaceflinger/fuzzer/surfaceflinger_fuzzers_utils.h b/services/surfaceflinger/fuzzer/surfaceflinger_fuzzers_utils.h
index 3338da0..de04592 100644
--- a/services/surfaceflinger/fuzzer/surfaceflinger_fuzzers_utils.h
+++ b/services/surfaceflinger/fuzzer/surfaceflinger_fuzzers_utils.h
@@ -727,7 +727,7 @@
         return mFlinger->setPowerModeInternal(display, mode);
     }
 
-    auto &getTransactionQueue() { return mFlinger->mTransactionQueue; }
+    auto &getTransactionQueue() { return mFlinger->mLocklessTransactionQueue; }
     auto &getPendingTransactionQueue() { return mFlinger->mPendingTransactionQueues; }
 
     auto setTransactionState(
diff --git a/services/surfaceflinger/tests/unittests/TestableSurfaceFlinger.h b/services/surfaceflinger/tests/unittests/TestableSurfaceFlinger.h
index 60285f9..eae5f82 100644
--- a/services/surfaceflinger/tests/unittests/TestableSurfaceFlinger.h
+++ b/services/surfaceflinger/tests/unittests/TestableSurfaceFlinger.h
@@ -421,7 +421,7 @@
         return mFlinger->SurfaceFlinger::getDisplayNativePrimaries(displayToken, primaries);
     }
 
-    auto& getTransactionQueue() { return mFlinger->mTransactionQueue; }
+    auto& getTransactionQueue() { return mFlinger->mLocklessTransactionQueue; }
     auto& getPendingTransactionQueue() { return mFlinger->mPendingTransactionQueues; }
     auto& getTransactionCommittedSignals() { return mFlinger->mTransactionCommittedSignals; }
 
diff --git a/services/surfaceflinger/tests/unittests/TransactionApplicationTest.cpp b/services/surfaceflinger/tests/unittests/TransactionApplicationTest.cpp
index 84f1170..b2da34e 100644
--- a/services/surfaceflinger/tests/unittests/TransactionApplicationTest.cpp
+++ b/services/surfaceflinger/tests/unittests/TransactionApplicationTest.cpp
@@ -117,7 +117,7 @@
     }
 
     void NotPlacedOnTransactionQueue(uint32_t flags) {
-        ASSERT_EQ(0u, mFlinger.getTransactionQueue().size());
+        ASSERT_TRUE(mFlinger.getTransactionQueue().isEmpty());
         EXPECT_CALL(*mFlinger.scheduler(), scheduleFrame()).Times(1);
         TransactionInfo transaction;
         setupSingle(transaction, flags,
@@ -140,12 +140,12 @@
             EXPECT_LE(returnedTime, applicationTime + mFlinger.getAnimationTransactionTimeout());
         }
         // Each transaction should have been placed on the transaction queue
-        auto transactionQueue = mFlinger.getTransactionQueue();
-        EXPECT_EQ(1u, transactionQueue.size());
+        auto& transactionQueue = mFlinger.getTransactionQueue();
+        EXPECT_FALSE(transactionQueue.isEmpty());
     }
 
     void PlaceOnTransactionQueue(uint32_t flags) {
-        ASSERT_EQ(0u, mFlinger.getTransactionQueue().size());
+        ASSERT_TRUE(mFlinger.getTransactionQueue().isEmpty());
         EXPECT_CALL(*mFlinger.scheduler(), scheduleFrame()).Times(1);
 
         // first check will see desired present time has not passed,
@@ -171,12 +171,12 @@
                       applicationSentTime + mFlinger.getAnimationTransactionTimeout());
         }
         // This transaction should have been placed on the transaction queue
-        auto transactionQueue = mFlinger.getTransactionQueue();
-        EXPECT_EQ(1u, transactionQueue.size());
+        auto& transactionQueue = mFlinger.getTransactionQueue();
+        EXPECT_FALSE(transactionQueue.isEmpty());
     }
 
     void BlockedByPriorTransaction(uint32_t flags) {
-        ASSERT_EQ(0u, mFlinger.getTransactionQueue().size());
+        ASSERT_TRUE(mFlinger.getTransactionQueue().isEmpty());
         nsecs_t time = systemTime();
         EXPECT_CALL(*mFlinger.scheduler(), scheduleFrame()).Times(2);
 
@@ -239,8 +239,8 @@
     int mTransactionNumber = 0;
 };
 
-TEST_F(TransactionApplicationTest, Flush_RemovesFromQueue) {
-    ASSERT_EQ(0u, mFlinger.getTransactionQueue().size());
+TEST_F(TransactionApplicationTest, AddToPendingQueue) {
+    ASSERT_TRUE(mFlinger.getTransactionQueue().isEmpty());
     EXPECT_CALL(*mFlinger.scheduler(), scheduleFrame()).Times(1);
 
     TransactionInfo transactionA; // transaction to go on pending queue
@@ -253,10 +253,27 @@
                                  mHasListenerCallbacks, mCallbacks, transactionA.id);
 
     auto& transactionQueue = mFlinger.getTransactionQueue();
-    ASSERT_EQ(1u, transactionQueue.size());
+    ASSERT_FALSE(transactionQueue.isEmpty());
 
-    auto& transactionState = transactionQueue.front();
+    auto transactionState = transactionQueue.pop().value();
     checkEqual(transactionA, transactionState);
+}
+
+TEST_F(TransactionApplicationTest, Flush_RemovesFromQueue) {
+    ASSERT_TRUE(mFlinger.getTransactionQueue().isEmpty());
+    EXPECT_CALL(*mFlinger.scheduler(), scheduleFrame()).Times(1);
+
+    TransactionInfo transactionA; // transaction to go on pending queue
+    setupSingle(transactionA, /*flags*/ 0, /*desiredPresentTime*/ s2ns(1), false,
+                FrameTimelineInfo{});
+    mFlinger.setTransactionState(transactionA.frameTimelineInfo, transactionA.states,
+                                 transactionA.displays, transactionA.flags, transactionA.applyToken,
+                                 transactionA.inputWindowCommands, transactionA.desiredPresentTime,
+                                 transactionA.isAutoTimestamp, transactionA.uncacheBuffer,
+                                 mHasListenerCallbacks, mCallbacks, transactionA.id);
+
+    auto& transactionQueue = mFlinger.getTransactionQueue();
+    ASSERT_FALSE(transactionQueue.isEmpty());
 
     // because flushing uses the cached expected present time, we send an empty
     // transaction here (sending a null applyToken to fake it as from a
@@ -272,7 +289,7 @@
     // passed
     mFlinger.flushTransactionQueues();
 
-    EXPECT_EQ(0u, transactionQueue.size());
+    EXPECT_TRUE(mFlinger.getTransactionQueue().isEmpty());
 }
 
 TEST_F(TransactionApplicationTest, NotPlacedOnTransactionQueue_Synchronous) {
@@ -306,7 +323,9 @@
     void TearDown() override {
         // Clear all transaction queues to release all transactions we sent
         // in the tests. Otherwise, gmock complains about memory leaks.
-        mFlinger.getTransactionQueue().clear();
+        while (!mFlinger.getTransactionQueue().isEmpty()) {
+            mFlinger.getTransactionQueue().pop();
+        }
         mFlinger.getPendingTransactionQueue().clear();
         mFlinger.getTransactionCommittedSignals().clear();
         mFlinger.commitTransactionsLocked(eTransactionMask);
@@ -358,7 +377,7 @@
     void setTransactionStates(const std::vector<TransactionInfo>& transactions,
                               size_t expectedTransactionsApplied,
                               size_t expectedTransactionsPending) {
-        EXPECT_EQ(0u, mFlinger.getTransactionQueue().size());
+        EXPECT_TRUE(mFlinger.getTransactionQueue().isEmpty());
         EXPECT_EQ(0u, mFlinger.getPendingTransactionQueue().size());
 
         for (const auto& transaction : transactions) {
@@ -370,7 +389,7 @@
                                          mHasListenerCallbacks, mCallbacks, transaction.id);
         }
         mFlinger.flushTransactionQueues();
-        EXPECT_EQ(0u, mFlinger.getTransactionQueue().size());
+        EXPECT_TRUE(mFlinger.getTransactionQueue().isEmpty());
         EXPECT_EQ(expectedTransactionsPending, mFlinger.getPendingTransactionQueue().size());
         EXPECT_EQ(expectedTransactionsApplied, mFlinger.getTransactionCommittedSignals().size());
     }