diff --git a/lib/bb/runqueue.py b/lib/bb/runqueue.py
index ef95eb46b..522288d63 100644
--- a/lib/bb/runqueue.py
+++ b/lib/bb/runqueue.py
@@ -237,7 +237,7 @@ class RunQueueScheduler(object):
             pressure_state = (exceeds_cpu_pressure, exceeds_io_pressure, exceeds_memory_pressure)
             pressure_values = (round(cpu_pressure,1), self.rq.max_cpu_pressure, round(io_pressure,1), self.rq.max_io_pressure, round(memory_pressure,1), self.rq.max_memory_pressure)
             if self.pressure_state is not None and pressure_state != self.pressure_state:
-                psi_logger.verbose("Pressure status changed to CPU: %s, IO: %s, Mem: %s (CPU: %s/%s, IO: %s/%s, Mem: %s/%s) - using %s/%s bitbake threads" % (pressure_state + pressure_values + (len(self.rq.runq_running.difference(self.rq.runq_complete)), self.rq.number_tasks)))
+                psi_logger.verbose("Pressure status changed to CPU: %s, IO: %s, Mem: %s (CPU: %s/%s, IO: %s/%s, Mem: %s/%s) - using %s/%s bitbake threads" % (pressure_state + pressure_values + (len(self.rq.runq_running_not_complete), self.rq.number_tasks)))
                 bb.event.fire(PSIEvent(pressure_state, pressure_values), self.rq.cfgData)
             self.pressure_state = pressure_state
             return (exceeds_cpu_pressure or exceeds_io_pressure or exceeds_memory_pressure)
@@ -248,7 +248,7 @@ class RunQueueScheduler(object):
             if loadfactor > self.rq.max_loadfactor:
                 limit = True
             if self.loadfactor_limit is not None and limit != self.loadfactor_limit:
-                bb.note("Load average limiting set to %s as load average: %s - using %s/%s bitbake threads" % (limit, loadfactor, len(self.rq.runq_running.difference(self.rq.runq_complete)), self.rq.number_tasks))
+                bb.note("Load average limiting set to %s as load average: %s - using %s/%s bitbake threads" % (limit, loadfactor, len(self.rq.runq_running_not_complete), self.rq.number_tasks))
             self.loadfactor_limit = limit
             return limit
         return False
@@ -259,9 +259,11 @@ class RunQueueScheduler(object):
         """
         # Once tasks are running we don't need to worry about them again
         self.buildable.difference_update(self.rq.runq_running)
-        buildable = set(self.buildable)
-        buildable.difference_update(self.rq.holdoff_tasks)
-        buildable.intersection_update(self.rq.tasks_covered | self.rq.tasks_notcovered)
+        holdoff = self.rq.holdoff_tasks
+        covered = self.rq.tasks_covered
+        notcovered = self.rq.tasks_notcovered
+        buildable = {t for t in self.buildable
+                     if t not in holdoff and (t in covered or t in notcovered)}
         if not buildable:
             return None
 
@@ -273,7 +275,7 @@ class RunQueueScheduler(object):
 
         # Filter out tasks that have a max number of threads that have been exceeded
         skip_buildable = {}
-        for running in self.rq.runq_running.difference(self.rq.runq_complete):
+        for running in self.rq.runq_running_not_complete:
             rtaskname = taskname_from_tid(running)
             if rtaskname not in self.skip_maxthread:
                 self.skip_maxthread[rtaskname] = self.rq.cfgData.getVarFlag(rtaskname, "number_threads")
@@ -1883,6 +1885,8 @@ class RunQueueExecute:
         self.runq_buildable = set()
         self.runq_running = set()
         self.runq_complete = set()
+        # runq_running - runq_complete, kept up to date for the scheduler
+        self.runq_running_not_complete = set()
         self.runq_tasksrun = set()
 
         self.build_stamps = {}
@@ -2082,6 +2086,10 @@ class RunQueueExecute:
         self.runq_buildable.add(task)
         self.sched.newbuildable(task)
 
+    def runq_running_add(self, task):
+        self.runq_running.add(task)
+        self.runq_running_not_complete.add(task)
+
     def task_completeoutright(self, task):
         """
         Mark a task as completed
@@ -2089,6 +2097,7 @@ class RunQueueExecute:
         completed dependencies as buildable
         """
         self.runq_complete.add(task)
+        self.runq_running_not_complete.discard(task)
         for revdep in self.rqdata.runtaskentries[task].revdeps:
             if revdep in self.runq_running:
                 continue
@@ -2152,7 +2161,7 @@ class RunQueueExecute:
             self.rq.state = RunQueueState.CLEAN_UP
 
     def task_skip(self, task, reason):
-        self.runq_running.add(task)
+        self.runq_running_add(task)
         self.setbuildable(task)
         bb.event.fire(runQueueTaskSkipped(task, self.stats, self.rq, reason), self.cfgData)
         self.task_completeoutright(task)
@@ -2381,7 +2390,7 @@ class RunQueueExecute:
                 startevent = runQueueTaskStarted(task, self.stats, self.rq,
                                                  noexec=True)
                 bb.event.fire(startevent, self.cfgData)
-                self.runq_running.add(task)
+                self.runq_running_add(task)
                 self.stats.taskActive()
                 if not (self.cooker.configuration.dry_run or self.rqdata.setscene_enforce):
                     bb.build.make_stamp_mcfn(taskname, taskfn)
@@ -2426,7 +2435,7 @@ class RunQueueExecute:
                 self.rq.worker[mc].process.stdin.flush()
 
             self.build_stamps[task] = bb.parse.siggen.stampfile_mcfn(taskname, taskfn, extrainfo=False)
-            self.runq_running.add(task)
+            self.runq_running_add(task)
             self.stats.taskActive()
             if self.can_start_task():
                 return True