diff --git a/gdb/gdbthread.h b/gdb/gdbthread.h
index ff7cec2..2c871a2 100644
--- a/gdb/gdbthread.h
+++ b/gdb/gdbthread.h
@@ -285,6 +285,12 @@ struct thread_info
   /* Values that are stored as temporaries on stack while evaluating
      expressions.  */
   value_vec *stack_temporaries;
+
+  /* Step-over chain.  A thread is in the step-over queue if these are
+     non-NULL.  If only a single thread is in the chain, then these
+     fields point to self.  */
+  struct thread_info *step_over_prev;
+  struct thread_info *step_over_next;
 };
 
 /* Create an empty thread list, or empty the existing one.  */
@@ -502,6 +508,23 @@ extern struct value *get_last_thread_stack_temporary (ptid_t);
 
 extern int value_in_thread_stack_temporaries (struct value *, ptid_t);
 
+/* Add TP to the end of its inferior's pending step-over chain.  */
+
+extern void thread_step_over_chain_enqueue (struct thread_info *tp);
+
+/* Remove TP from its inferior's pending step-over chain.  */
+
+extern void thread_step_over_chain_remove (struct thread_info *tp);
+
+/* Return the next thread in the step-over chain starting at TP.  NULL
+   if TP is the last entry in the chain.  */
+
+extern struct thread_info *thread_step_over_chain_next (struct thread_info *tp);
+
+/* Return true if TP is in the step-over chain.  */
+
+extern int thread_is_in_step_over_chain (struct thread_info *tp);
+
 extern struct thread_info *thread_list;
 
 #endif /* GDBTHREAD_H */
diff --git a/gdb/infrun.c b/gdb/infrun.c
index 534ecef..f325a53 100644
--- a/gdb/infrun.c
+++ b/gdb/infrun.c
@@ -1223,6 +1223,15 @@ follow_exec (ptid_t ptid, char *execd_pathname)
      matically get reset there in the new process.).  */
 }
 
+/* The queue of threads that need to do a step-over operation to get
+   past e.g., a breakpoint.  What technique is used to step over the
+   breakpoint/watchpoint does not matter -- all threads end up in the
+   same queue, to maintain rough temporal order of execution, in order
+   to avoid starvation, otherwise, we could e.g., find ourselves
+   constantly stepping the same couple threads past their breakpoints
+   over and over, if the single-step finish fast enough.  */
+struct thread_info *step_over_queue_head;
+
 /* Bit flags indicating what the thread needs to step over.  */
 
 enum step_over_what
@@ -1419,12 +1428,6 @@ step_over_info_valid_p (void)
    displaced step operation on it.  See displaced_step_prepare and
    displaced_step_fixup for details.  */
 
-struct displaced_step_request
-{
-  ptid_t ptid;
-  struct displaced_step_request *next;
-};
-
 /* Per-inferior displaced stepping state.  */
 struct displaced_step_inferior_state
 {
@@ -1434,10 +1437,6 @@ struct displaced_step_inferior_state
   /* The process this displaced step state refers to.  */
   int pid;
 
-  /* A queue of pending displaced stepping requests.  One entry per
-     thread that needs to do a displaced step.  */
-  struct displaced_step_request *step_request_queue;
-
   /* If this is not null_ptid, this is the thread carrying out a
      displaced single-step in process PID.  This thread's state will
      require fixing up once it has completed its step.  */
@@ -1669,6 +1668,9 @@ displaced_step_prepare (ptid_t ptid)
      support displaced stepping.  */
   gdb_assert (gdbarch_displaced_step_copy_insn_p (gdbarch));
 
+  /* Nor if the thread isn't meant to step over a breakpoint.  */
+  gdb_assert (tp->control.trap_expected);
+
   /* Disable range stepping while executing in the scratch pad.  We
      want a single-step even if executing the displaced instruction in
      the scratch buffer lands within the stepping range (e.g., a
@@ -1684,28 +1686,13 @@ displaced_step_prepare (ptid_t ptid)
     {
       /* Already waiting for a displaced step to finish.  Defer this
 	 request and place in queue.  */
-      struct displaced_step_request *req, *new_req;
 
       if (debug_displaced)
 	fprintf_unfiltered (gdb_stdlog,
-			    "displaced: defering step of %s\n",
+			    "displaced: deferring step of %s\n",
 			    target_pid_to_str (ptid));
 
-      new_req = xmalloc (sizeof (*new_req));
-      new_req->ptid = ptid;
-      new_req->next = NULL;
-
-      if (displaced->step_request_queue)
-	{
-	  for (req = displaced->step_request_queue;
-	       req && req->next;
-	       req = req->next)
-	    ;
-	  req->next = new_req;
-	}
-      else
-	displaced->step_request_queue = new_req;
-
+      thread_step_over_chain_enqueue (tp);
       return 0;
     }
   else
@@ -1855,24 +1842,44 @@ displaced_step_fixup (ptid_t event_ptid, enum gdb_signal signal)
   do_cleanups (old_cleanups);
 
   displaced->step_ptid = null_ptid;
+}
 
-  /* Are there any pending displaced stepping requests?  If so, run
-     one now.  Leave the state object around, since we're likely to
-     need it again soon.  */
-  while (displaced->step_request_queue)
+/* Are there any pending step-over requests?  If so, run one now.  */
+
+static void
+start_step_over (void)
+{
+  struct thread_info *tp, *next;
+
+  for (tp = step_over_queue_head; tp != NULL; tp = next)
     {
-      struct displaced_step_request *head;
       ptid_t ptid;
+      struct displaced_step_inferior_state *displaced;
       struct regcache *regcache;
       struct gdbarch *gdbarch;
       CORE_ADDR actual_pc;
       struct address_space *aspace;
+      struct inferior *inf = find_inferior_ptid (tp->ptid);
+
+      next = thread_step_over_chain_next (tp);
 
-      head = displaced->step_request_queue;
-      ptid = head->ptid;
-      displaced->step_request_queue = head->next;
-      xfree (head);
+      displaced = get_displaced_stepping_state (inf->pid);
 
+      /* If this inferior already has a displaced step in process,
+	 don't start a new one.  */
+      if (!ptid_equal (displaced->step_ptid, null_ptid))
+	continue;
+
+      thread_step_over_chain_remove (tp);
+
+      if (step_over_queue_head == NULL)
+	{
+	  if (debug_infrun)
+	    fprintf_unfiltered (gdb_stdlog,
+				"infrun: step-over queue now empty\n");
+	}
+
+      ptid = tp->ptid;
       context_switch (ptid);
 
       regcache = get_thread_regcache (ptid);
@@ -1935,6 +1942,10 @@ displaced_step_fixup (ptid_t event_ptid, enum gdb_signal signal)
 	  /* This request was discarded.  See if there's any other
 	     thread waiting for its turn.  */
 	}
+
+      /* A new displaced stepping sequence started.  Maybe we can
+	 start a displaced step on a thread of other process.
+	 Continue looking.  */
     }
 }
 
@@ -1955,10 +1966,6 @@ infrun_thread_ptid_changed (ptid_t old_ptid, ptid_t new_ptid)
     {
       if (ptid_equal (displaced->step_ptid, old_ptid))
 	displaced->step_ptid = new_ptid;
-
-      for (it = displaced->step_request_queue; it; it = it->next)
-	if (ptid_equal (it->ptid, old_ptid))
-	  it->ptid = new_ptid;
     }
 }
 
@@ -2137,6 +2144,8 @@ resume (enum gdb_signal sig)
 
   tp->stepped_breakpoint = 0;
 
+  gdb_assert (!thread_is_in_step_over_chain (tp));
+
   QUIT;
 
   /* Depends on stepped_breakpoint.  */
@@ -2667,6 +2676,8 @@ proceed (CORE_ADDR addr, enum gdb_signal siggnal)
   /* Fill in with reasonable starting values.  */
   init_thread_stepping_state (tp);
 
+  gdb_assert (!thread_is_in_step_over_chain (tp));
+
   if (addr == (CORE_ADDR) -1)
     {
       if (pc == stop_pc
@@ -2972,35 +2983,17 @@ infrun_thread_stop_requested_callback (struct thread_info *info, void *arg)
 static void
 infrun_thread_stop_requested (ptid_t ptid)
 {
-  struct displaced_step_inferior_state *displaced;
-
-  /* PTID was requested to stop.  Remove it from the displaced
-     stepping queue, so we don't try to resume it automatically.  */
-
-  for (displaced = displaced_step_inferior_states;
-       displaced;
-       displaced = displaced->next)
-    {
-      struct displaced_step_request *it, **prev_next_p;
-
-      it = displaced->step_request_queue;
-      prev_next_p = &displaced->step_request_queue;
-      while (it)
-	{
-	  if (ptid_match (it->ptid, ptid))
-	    {
-	      *prev_next_p = it->next;
-	      it->next = NULL;
-	      xfree (it);
-	    }
-	  else
-	    {
-	      prev_next_p = &it->next;
-	    }
+  struct thread_info *tp;
 
-	  it = *prev_next_p;
-	}
-    }
+  /* PTID was requested to stop.  Remove matching threads from the
+     step-over queue, so we don't try to resume them
+     automatically.  */
+  ALL_NON_EXITED_THREADS (tp)
+    if (ptid_match (tp->ptid, ptid))
+      {
+	if (thread_is_in_step_over_chain (tp))
+	  thread_step_over_chain_remove (tp);
+      }
 
   iterate_over_threads (infrun_thread_stop_requested_callback, &ptid);
 }
@@ -4051,6 +4044,9 @@ Cannot fill $_exitsignal with the correct signal number.\n"));
 	       that this operation also cleans up the child process for vfork,
 	       because their pages are shared.  */
 	    displaced_step_fixup (ecs->ptid, GDB_SIGNAL_TRAP);
+	    /* Start a new step-over in another thread if there's one
+	       that needs it.  */
+	    start_step_over ();
 
 	    if (ecs->ws.kind == TARGET_WAITKIND_FORKED)
 	      {
@@ -4283,6 +4279,7 @@ handle_signal_stop (struct execution_control_state *ecs)
      the PC, so do it here, before we set stop_pc.)  */
   displaced_step_fixup (ecs->ptid,
 			ecs->event_thread->suspend.stop_signal);
+  start_step_over ();
 
   /* If we either finished a single-step or hit a breakpoint, but
      the user wanted this thread to be stopped, pretend we got a
diff --git a/gdb/infrun.h b/gdb/infrun.h
index 1f09e41..bfce810 100644
--- a/gdb/infrun.h
+++ b/gdb/infrun.h
@@ -196,4 +196,8 @@ extern void signal_catch_update (const unsigned int *);
    systems.  Use of symbolic signal names is strongly encouraged.  */
 enum gdb_signal gdb_signal_from_command (int num);
 
+/* The global queue of threads that need to do a step-over operation
+   to get past e.g., a breakpoint.  */
+extern struct thread_info *step_over_queue_head;
+
 #endif /* INFRUN_H */
diff --git a/gdb/thread.c b/gdb/thread.c
index 46b5947..28e5ef8 100644
--- a/gdb/thread.c
+++ b/gdb/thread.c
@@ -307,6 +307,86 @@ add_thread (ptid_t ptid)
   return add_thread_with_info (ptid, NULL);
 }
 
+/* Add TP to the end of the step-over chain LIST_P.  */
+
+static void
+step_over_chain_enqueue (struct thread_info **list_p, struct thread_info *tp)
+{
+  gdb_assert (tp->step_over_next == NULL);
+  gdb_assert (tp->step_over_prev == NULL);
+
+  if (*list_p == NULL)
+    {
+      *list_p = tp;
+      tp->step_over_prev = tp->step_over_next = tp;
+    }
+  else
+    {
+      struct thread_info *head = *list_p;
+      struct thread_info *tail = head->step_over_prev;
+
+      tp->step_over_prev = tail;
+      tp->step_over_next = head;
+      head->step_over_prev = tp;
+      tail->step_over_next = tp;
+    }
+}
+
+/* Remove TP from step-over chain LIST_P.  */
+
+static void
+step_over_chain_remove (struct thread_info **list_p, struct thread_info *tp)
+{
+  gdb_assert (tp->step_over_next != NULL);
+  gdb_assert (tp->step_over_prev != NULL);
+
+  if (*list_p == tp)
+    {
+      if (tp == tp->step_over_next)
+	*list_p = NULL;
+      else
+	*list_p = tp->step_over_next;
+    }
+
+  tp->step_over_prev->step_over_next = tp->step_over_next;
+  tp->step_over_next->step_over_prev = tp->step_over_prev;
+  tp->step_over_prev = tp->step_over_next = NULL;
+}
+
+/* See gdbthread.h.  */
+
+struct thread_info *
+thread_step_over_chain_next (struct thread_info *tp)
+{
+  struct thread_info *next = tp->step_over_next;
+
+  return (next == step_over_queue_head ? NULL : next);
+}
+
+/* See gdbthread.h.  */
+
+int
+thread_is_in_step_over_chain (struct thread_info *tp)
+{
+  return (tp->step_over_next != NULL);
+}
+
+/* See gdbthread.h.  */
+
+void
+thread_step_over_chain_enqueue (struct thread_info *tp)
+{
+  step_over_chain_enqueue (&step_over_queue_head, tp);
+}
+
+/* See gdbthread.h.  */
+
+void
+thread_step_over_chain_remove (struct thread_info *tp)
+{
+  step_over_chain_remove (&step_over_queue_head, tp);
+}
+
 /* Delete thread PTID.  If SILENT, don't notify the observer of this
    exit.  */
 static void
@@ -323,6 +403,10 @@ delete_thread_1 (ptid_t ptid, int silent)
   if (!tp)
     return;
 
+  /* Dead threads don't need to step-over.  Remove from queue.  */
+  if (tp->step_over_next != NULL)
+    thread_step_over_chain_remove (tp);
+
   /* If this is the current thread, or there's code out there that
      relies on it existing (refcount > 0) we can't delete yet.  Mark
      it as exited, and notify it.  */
