Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1282998 > unrolled thread

[PATCH 4/4] sched: Document Program-Order guarantees

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  [PATCH 4/4] sched: Document Program-Order guarantees Peter Zijlstra <peterz@infradead.org> - 2015-12-03 13:50 +0100
    Re: [PATCH 4/4] sched: Document Program-Order guarantees Boqun Feng <boqun.feng@gmail.com> - 2015-12-03 14:20 +0100
      Re: [PATCH 4/4] sched: Document Program-Order guarantees Peter Zijlstra <peterz@infradead.org> - 2015-12-03 14:30 +0100

#1282998 — [PATCH 4/4] sched: Document Program-Order guarantees

These are some notes on the scheduler locking and how it provides
program order guarantees on SMP systems.

Cc: Michal Hocko <mhocko@kernel.org>
Cc: David Howells <dhowells@redhat.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Will Deacon <will.deacon@arm.com>
Cc: Oleg Nesterov <oleg@redhat.com>
Cc: Boqun Feng <boqun.feng@gmail.com>
Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
Cc: Jonathan Corbet <corbet@lwn.net>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 kernel/sched/core.c |   91 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 91 insertions(+)

--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -1916,6 +1916,97 @@ static void ttwu_queue(struct task_struc
 	raw_spin_unlock(&rq->lock);
 }
 
+/*
+ * Notes on Program-Order guarantees on SMP systems.
+ *
+ *  MIGRATION
+ *
+ * The basic program-order guarantee on SMP systems is that when a task [t]
+ * migrates, all its activity on its old cpu [c0] happens-before any subsequent
+ * execution on its new cpu [c1].
+ *
+ * For migration (of runnable tasks) this is provided by the following means:
+ *
+ *  A) UNLOCK of the rq(c0)->lock scheduling out task t
+ *  B) migration for t is required to synchronize *both* rq(c0)->lock and
+ *     rq(c1)->lock (if not at the same time, then in that order).
+ *  C) LOCK of the rq(c1)->lock scheduling in task
+ *
+ * Transitivity guarantees that B happens after A and C after B.
+ * Note: we only require RCpc transitivity.
+ * Note: the cpu doing B need not be c0 or c1
+ *
+ * Example:
+ *
+ *   CPU0            CPU1            CPU2
+ *
+ *   LOCK rq(0)->lock
+ *   sched-out X
+ *   sched-in Y
+ *   UNLOCK rq(0)->lock
+ *
+ *                                   LOCK rq(0)->lock // orders against CPU0
+ *                                   dequeue X
+ *                                   UNLOCK rq(0)->lock
+ *
+ *                                   LOCK rq(1)->lock
+ *                                   enqueue X
+ *                                   UNLOCK rq(1)->lock
+ *
+ *                   LOCK rq(1)->lock // orders against CPU2
+ *                   sched-out Z
+ *                   sched-in X
+ *                   UNLOCK rq(1)->lock
+ *
+ *
+ *  BLOCKING -- aka. SLEEP + WAKEUP
+ *
+ * For blocking we (obviously) need to provide the same guarantee as for
+ * migration. However the means are completely different as there is no lock
+ * chain to provide order. Instead we do:
+ *
+ *   1) smp_store_release(X->on_cpu, 0)
+ *   2) smp_cond_acquire(!X->on_cpu)
+ *
+ * Example:
+ *
+ *   CPU0 (schedule)  CPU1 (try_to_wake_up) CPU2 (schedule)
+ *
+ *   LOCK rq(0)->lock LOCK X->pi_lock
+ *   dequeue X
+ *   sched-out X
+ *   smp_store_release(X->on_cpu, 0);
+ *
+ *                    smp_cond_acquire(!X->on_cpu);
+ *                    X->state = WAKING
+ *                    set_task_cpu(X,2)
+ *
+ *                    LOCK rq(2)->lock
+ *                    enqueue X
+ *                    X->state = RUNNING
+ *                    UNLOCK rq(2)->lock
+ *
+ *                                          LOCK rq(2)->lock // orders against CPU1
+ *                                          sched-out Z
+ *                                          sched-in X
+ *                                          UNLOCK rq(1)->lock
+ *
+ *                    UNLOCK X->pi_lock
+ *   UNLOCK rq(0)->lock
+ *
+ *
+ * However; for wakeups there is a second guarantee we must provide, namely we
+ * must observe the state that lead to our wakeup. That is, not only must our
+ * task observe its own prior state, it must also observe the stores prior to
+ * its wakeup.
+ *
+ * This means that any means of doing remote wakeups must order the CPU doing
+ * the wakeup against the CPU the task is going to end up running on. This,
+ * however, is already required for the regular Program-Order guarantee above,
+ * since the waking CPU is the one issueing the ACQUIRE (smp_cond_acquire).
+ *
+ */
+
 /**
  * try_to_wake_up - wake up a thread
  * @p: the thread to be awakened


--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [next] | [standalone]

#1283040

[Multipart message — attachments visible in raw view] — view raw

On Thu, Dec 03, 2015 at 01:40:14PM +0100, Peter Zijlstra wrote:
[snip]
> + *
> + *   CPU0 (schedule)  CPU1 (try_to_wake_up) CPU2 (schedule)
> + *
> + *   LOCK rq(0)->lock LOCK X->pi_lock
> + *   dequeue X
> + *   sched-out X
> + *   smp_store_release(X->on_cpu, 0);
> + *
> + *                    smp_cond_acquire(!X->on_cpu);
> + *                    X->state = WAKING
> + *                    set_task_cpu(X,2)
> + *
> + *                    LOCK rq(2)->lock
> + *                    enqueue X
> + *                    X->state = RUNNING
> + *                    UNLOCK rq(2)->lock
> + *
> + *                                          LOCK rq(2)->lock // orders against CPU1
> + *                                          sched-out Z
> + *                                          sched-in X
> + *                                          UNLOCK rq(1)->lock
						^^^^^^^^^^^^^^^

This is a typo, right? Should be "UNLOCK rq(2)->lock".

Regards,
Boqun

> + *
> + *                    UNLOCK X->pi_lock
> + *   UNLOCK rq(0)->lock
> + *
> + *

[toc] | [prev] | [next] | [standalone]

#1283043

On Thu, Dec 03, 2015 at 09:16:48PM +0800, Boqun Feng wrote:
> On Thu, Dec 03, 2015 at 01:40:14PM +0100, Peter Zijlstra wrote:
> [snip]
> > + *
> > + *   CPU0 (schedule)  CPU1 (try_to_wake_up) CPU2 (schedule)
> > + *
> > + *   LOCK rq(0)->lock LOCK X->pi_lock
> > + *   dequeue X
> > + *   sched-out X
> > + *   smp_store_release(X->on_cpu, 0);
> > + *
> > + *                    smp_cond_acquire(!X->on_cpu);
> > + *                    X->state = WAKING
> > + *                    set_task_cpu(X,2)
> > + *
> > + *                    LOCK rq(2)->lock
> > + *                    enqueue X
> > + *                    X->state = RUNNING
> > + *                    UNLOCK rq(2)->lock
> > + *
> > + *                                          LOCK rq(2)->lock // orders against CPU1
> > + *                                          sched-out Z
> > + *                                          sched-in X
> > + *                                          UNLOCK rq(1)->lock
> 						^^^^^^^^^^^^^^^
> 
> This is a typo, right? Should be "UNLOCK rq(2)->lock".

Duh, yes. Fixed.

Thanks.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web