diff --git a/redfish-core/lib/task.hpp b/redfish-core/lib/task.hpp
index 40aaffd..d0f2b07 100644
--- a/redfish-core/lib/task.hpp
+++ b/redfish-core/lib/task.hpp
@@ -138,18 +138,36 @@
 
         if (tasks.size() >= maxTaskCount)
         {
-            const auto& last = tasks.front();
+            const auto last = getTaskToRemove();
 
             // destroy all references
-            last->timer.cancel();
-            last->match.reset();
-            tasks.pop_front();
+            (*last)->timer.cancel();
+            (*last)->match.reset();
+            tasks.erase(last);
         }
 
         return tasks.emplace_back(std::make_shared<MakeSharedHelper>(
             std::move(handler), match, lastTask++));
     }
 
+    /**
+     * @brief Get the first completed/aborted task or oldest running task to
+     * remove
+     */
+    static std::deque<std::shared_ptr<TaskData>>::iterator getTaskToRemove()
+    {
+        static constexpr std::array<std::string_view, 5> activeStates = {
+            "Running", "Pending", "Starting", "Suspended", "Interrupted"};
+
+        auto it =
+            std::find_if(tasks.begin(), tasks.end(), [](const auto& task) {
+                return std::ranges::find(activeStates, task->state) ==
+                       activeStates.end();
+            });
+
+        return (it != tasks.end()) ? it : tasks.begin();
+    }
+
     void populateResp(crow::Response& res, size_t retryAfterSeconds = 30)
     {
         if (!endTime)