diff --git a/automotive/vehicle/aidl/impl/utils/common/include/RecurrentTimer.h b/automotive/vehicle/aidl/impl/utils/common/include/RecurrentTimer.h
index 5f0f716..cd2b727 100644
--- a/automotive/vehicle/aidl/impl/utils/common/include/RecurrentTimer.h
+++ b/automotive/vehicle/aidl/impl/utils/common/include/RecurrentTimer.h
@@ -83,8 +83,9 @@
     // each time we might introduce outdated elements to the top. We must make sure the heap is
     // always valid from the top.
     void removeInvalidCallbackLocked() REQUIRES(mLock);
-    // Pops the next closest callback (must be valid) from the heap.
-    std::unique_ptr<CallbackInfo> popNextCallbackLocked() REQUIRES(mLock);
+    // Gets the next calblack to run (must be valid) from the heap, update its nextTime and put
+    // it back to the heap.
+    std::shared_ptr<Callback> getNextCallbackLocked(int64_t now) REQUIRES(mLock);
 };
 
 }  // namespace vehicle
diff --git a/automotive/vehicle/aidl/impl/utils/common/src/RecurrentTimer.cpp b/automotive/vehicle/aidl/impl/utils/common/src/RecurrentTimer.cpp
index 2eca6b7..908564c 100644
--- a/automotive/vehicle/aidl/impl/utils/common/src/RecurrentTimer.cpp
+++ b/automotive/vehicle/aidl/impl/utils/common/src/RecurrentTimer.cpp
@@ -101,68 +101,71 @@
     }
 }
 
-std::unique_ptr<RecurrentTimer::CallbackInfo> RecurrentTimer::popNextCallbackLocked() {
+std::shared_ptr<RecurrentTimer::Callback> RecurrentTimer::getNextCallbackLocked(int64_t now) {
     std::pop_heap(mCallbackQueue.begin(), mCallbackQueue.end(), CallbackInfo::cmp);
-    std::unique_ptr<CallbackInfo> info = std::move(mCallbackQueue[mCallbackQueue.size() - 1]);
-    mCallbackQueue.pop_back();
+    auto& callbackInfo = mCallbackQueue[mCallbackQueue.size() - 1];
+    auto nextCallback = callbackInfo->callback;
+    // intervalCount is the number of interval we have to advance until we pass now.
+    size_t intervalCount = (now - callbackInfo->nextTime) / callbackInfo->interval + 1;
+    callbackInfo->nextTime += intervalCount * callbackInfo->interval;
+    std::push_heap(mCallbackQueue.begin(), mCallbackQueue.end(), CallbackInfo::cmp);
+
     // Make sure the first element is always valid.
     removeInvalidCallbackLocked();
-    return info;
+
+    return nextCallback;
 }
 
 void RecurrentTimer::loop() {
-    std::unique_lock<std::mutex> uniqueLock(mLock);
-
+    std::vector<std::shared_ptr<Callback>> callbacksToRun;
     while (true) {
-        // Wait until the timer exits or we have at least one recurrent callback.
-        mCond.wait(uniqueLock, [this] {
-            ScopedLockAssertion lockAssertion(mLock);
-            return mStopRequested || mCallbackQueue.size() != 0;
-        });
-
-        int64_t interval;
         {
+            std::unique_lock<std::mutex> uniqueLock(mLock);
             ScopedLockAssertion lockAssertion(mLock);
+            // Wait until the timer exits or we have at least one recurrent callback.
+            mCond.wait(uniqueLock, [this] {
+                ScopedLockAssertion lockAssertion(mLock);
+                return mStopRequested || mCallbackQueue.size() != 0;
+            });
+
+            int64_t interval;
             if (mStopRequested) {
                 return;
             }
             // The first element is the nearest next event.
             int64_t nextTime = mCallbackQueue[0]->nextTime;
             int64_t now = uptimeNanos();
+
             if (nextTime > now) {
                 interval = nextTime - now;
             } else {
                 interval = 0;
             }
-        }
 
-        // Wait for the next event or the timer exits.
-        if (mCond.wait_for(uniqueLock, std::chrono::nanoseconds(interval), [this] {
-                ScopedLockAssertion lockAssertion(mLock);
-                return mStopRequested;
-            })) {
-            return;
-        }
+            // Wait for the next event or the timer exits.
+            if (mCond.wait_for(uniqueLock, std::chrono::nanoseconds(interval), [this] {
+                    ScopedLockAssertion lockAssertion(mLock);
+                    return mStopRequested;
+                })) {
+                return;
+            }
 
-        {
-            ScopedLockAssertion lockAssertion(mLock);
-            int64_t now = uptimeNanos();
+            now = uptimeNanos();
+            callbacksToRun.clear();
             while (mCallbackQueue.size() > 0) {
                 int64_t nextTime = mCallbackQueue[0]->nextTime;
                 if (nextTime > now) {
                     break;
                 }
 
-                std::unique_ptr<CallbackInfo> info = popNextCallbackLocked();
-                info->nextTime += info->interval;
-
-                auto callback = info->callback;
-                mCallbackQueue.push_back(std::move(info));
-                std::push_heap(mCallbackQueue.begin(), mCallbackQueue.end(), CallbackInfo::cmp);
-
-                (*callback)();
+                callbacksToRun.push_back(getNextCallbackLocked(now));
             }
         }
+
+        // Do not execute the callback while holding the lock.
+        for (size_t i = 0; i < callbacksToRun.size(); i++) {
+            (*callbacksToRun[i])();
+        }
     }
 }
 
diff --git a/automotive/vehicle/aidl/impl/utils/common/test/RecurrentTimerTest.cpp b/automotive/vehicle/aidl/impl/utils/common/test/RecurrentTimerTest.cpp
index a033a24..141efc1 100644
--- a/automotive/vehicle/aidl/impl/utils/common/test/RecurrentTimerTest.cpp
+++ b/automotive/vehicle/aidl/impl/utils/common/test/RecurrentTimerTest.cpp
@@ -186,6 +186,33 @@
     ASSERT_EQ(countTimerCallbackQueue(&timer), static_cast<size_t>(0));
 }
 
+TEST_F(RecurrentTimerTest, testRegisterCallbackMultipleTimesNoDeadLock) {
+    // We want to avoid the following situation:
+    // Caller holds a lock while calling registerTimerCallback, registerTimerCallback will try
+    // to obtain an internal lock inside timer.
+    // Meanwhile an recurrent action happens with timer holding an internal lock. The action
+    // tries to obtain the lock currently hold by the caller.
+    // The solution is that while calling recurrent actions, timer must not hold the internal lock.
+
+    std::unique_ptr<RecurrentTimer> timer = std::make_unique<RecurrentTimer>();
+    std::mutex lock;
+    for (size_t i = 0; i < 1000; i++) {
+        std::scoped_lock<std::mutex> lockGuard(lock);
+        auto action = std::make_shared<RecurrentTimer::Callback>([&lock] {
+            // While calling this function, the timer must not hold lock in order not to dead
+            // lock.
+            std::scoped_lock<std::mutex> lockGuard(lock);
+        });
+        // 10ms
+        int64_t interval = 10'000'000;
+        timer->registerTimerCallback(interval, action);
+        // Sleep for a little while to let the recurrent actions begin.
+        std::this_thread::sleep_for(std::chrono::milliseconds(1));
+    }
+    // Make sure we stop the timer before we destroy lock.
+    timer.reset();
+}
+
 }  // namespace vehicle
 }  // namespace automotive
 }  // namespace hardware