scheduler (sched_4bsd) questions
Peter Holm
peter at holm.cc
Thu Sep 30 13:38:31 PDT 2004
On Thu, Sep 30, 2004 at 10:17:54AM -0400, John Baldwin wrote:
> On Wednesday 29 September 2004 06:14 pm, Stephan Uphoff wrote:
> > On Wed, 2004-09-29 at 16:52, John Baldwin wrote:
> > > > > OK - here is a crude patch to fix some problems with mutex priority
> > > > > inheritance. My theory is that the clock thread gets stuck waiting on
> > > > > GIANT.
> > > > >
> > > > > During release/acquisition of a contested sleep mutex there are a few
> > > > > windows where a task can be preempted when actions (waking up blocked
> > > > > threads, ownership of the mutex, ..) need to be atomic as far as
> > > > > scheduling is concerned. Otherwise priority inheritance may fail. The
> > > > > patch uses critical_enter/critical_exit to protect these regions
> > > > > against preemption.
> > > > >
> > > > > It would be great if could run this in addition to the other patches.
> > >
> > > turnstile_claim() doesn't make any threads runnable and thus can't
> > > preempt. The other place is supposed to preempt, and it should be ok to
> > > do so. Note that since the turnstile chain lock is held, that includes a
> > > nested critical section and any preemption will be deferred until the
> > > turnstile lock is released via turnstile_release which happens in the
> > > middle of
> > > turnstile_unpend() after it has finished building a list of all the
> > > threads to be made runnable so that the turnstile object can be re-used
> > > safely. I don't think this patch will make much of a difference (if
> > > any). Can you provide a description of a case where you think the
> > > priority inheritance can fail if turnstile_unpend() doesn't run in a
> > > nested critical section?
> >
> > This is a bit of a mind bender.
> > I hope you have some aspirins close by ;-)
> >
> > Thread A holds a mutex x contested by Thread B and has priority pri(A).
> > Thread B holds a mutex y.
> > There is a thread C with priority pri(C) with pri(C) < pri(A).
> >
> > Thread A is in the process of releasing x.
> > It removes thread B from the turnstile and holds a pointer to B in a
> > private list.
> > Thread A sets the owner of the turnstile to NULL and releases all spin
> > locks. ( mtx_unlock_spin(&tc->tc_lock); line 148)
> > This means interrupts are now enabled.
> >
> > An interrupt occurs (or is already pending) and the interrupt handler
> > puts the associated interrupt thread I on the run queue.
> > This causes a preemption from A to I.
> > The interrupt thread I tries to acquire mutex y owned by B and blocks.
> > I donates its priority to B - but inheritance stops at B.
> > The next thread with the best priority is C and the cpu switches to C.
> > However B needs A to run to make it to the run-queue.
> >
> > If y is GIANT and I is the clock thread C could run forever in userspace
> > without being interrupted.
>
> Fair enough. The right place to fix this is in turnstile_unpend() though I
> think. I have had these patches that try to "clump" setrunqueue's before
> preempting lying around (but not thoroughly tested yet) that might fix this
> as well but in the turnstile code itself:
>
> --- //depot/projects/smpng/sys/kern/kern_thread.c 2004/09/22 15:31:15
> +++ //depot/user/jhb/preemption/kern/kern_thread.c 2004/09/22 16:59:47
> @@ -954,6 +954,7 @@
> p->p_suspcount++;
> TD_SET_SUSPENDED(td);
> TAILQ_INSERT_TAIL(&p->p_suspended, td, td_runq);
> +#if 0
> /*
> * Hack: If we are suspending but are on the sleep queue
> * then we are in msleep or the cv equivalent. We
> @@ -962,6 +963,7 @@
> */
> if (TD_ON_SLEEPQ(td))
> TD_SET_SLEEPING(td);
> +#endif
> }
>
> void
> @@ -988,9 +990,11 @@
> mtx_assert(&sched_lock, MA_OWNED);
> PROC_LOCK_ASSERT(p, MA_OWNED);
> if (!P_SHOULDSTOP(p)) {
> + critical_enter();
> while ((td = TAILQ_FIRST(&p->p_suspended))) {
> thread_unsuspend_one(td);
> }
> + critical_exit();
> } else if ((P_SHOULDSTOP(p) == P_STOPPED_SINGLE) &&
> (p->p_numthreads == p->p_suspcount)) {
> /*
> @@ -1025,9 +1029,11 @@
> * to continue however as this is a bad place to stop.
> */
> if ((p->p_numthreads != 1) && (!P_SHOULDSTOP(p))) {
> - while (( td = TAILQ_FIRST(&p->p_suspended))) {
> + critical_enter();
> + while ((td = TAILQ_FIRST(&p->p_suspended))) {
> thread_unsuspend_one(td);
> }
> + critical_exit();
> }
> mtx_unlock_spin(&sched_lock);
> }
> --- //depot/projects/smpng/sys/kern/subr_sleepqueue.c 2004/08/20 17:10:02
> +++ //depot/user/jhb/preemption/kern/subr_sleepqueue.c 2004/09/10 21:36:10
> @@ -400,9 +400,10 @@
> * just return.
> */
> if (td->td_sleepqueue != NULL) {
> - MPASS(!TD_ON_SLEEPQ(td));
> mtx_unlock_spin(&sc->sc_lock);
> mtx_lock_spin(&sched_lock);
> + MPASS(!TD_ON_SLEEPQ(td));
> + MPASS(!TD_IS_SLEEPING(td));
> return;
> }
>
> @@ -709,11 +710,13 @@
> sleepq_release(wchan);
>
> /* Resume all the threads on the temporary list. */
> + critical_enter();
> while (!TAILQ_EMPTY(&list)) {
> td = TAILQ_FIRST(&list);
> TAILQ_REMOVE(&list, td, td_slpq);
> sleepq_resume_thread(td, pri);
> }
> + critical_exit();
> }
>
> /*
> --- //depot/projects/smpng/sys/kern/subr_turnstile.c 2004/09/03 14:14:21
> +++ //depot/user/jhb/preemption/kern/subr_turnstile.c 2004/09/10 21:36:10
> @@ -727,6 +726,7 @@
> * in turnstile_wait(). Set a flag to force it to try to acquire
> * the lock again instead of blocking.
> */
> + critical_enter();
> while (!TAILQ_EMPTY(&pending_threads)) {
> td = TAILQ_FIRST(&pending_threads);
> TAILQ_REMOVE(&pending_threads, td, td_lockq);
> @@ -742,6 +742,7 @@
> MPASS(TD_IS_RUNNING(td) || TD_ON_RUNQ(td));
> }
> }
> + critical_exit();
> mtx_unlock_spin(&sched_lock);
> }
>
> --- //depot/projects/smpng/sys/vm/vm_glue.c 2004/09/22 15:31:15
> +++ //depot/user/jhb/preemption/vm/vm_glue.c 2004/09/22 16:59:47
> @@ -753,6 +753,7 @@
> vm_thread_swapin(td);
>
> PROC_LOCK(p);
> + critical_enter();
> mtx_lock_spin(&sched_lock);
> p->p_sflag &= ~PS_SWAPPINGIN;
> p->p_sflag |= PS_INMEM;
> @@ -767,6 +768,7 @@
>
> /* Allow other threads to swap p out now. */
> --p->p_lock;
> + critical_exit();
> }
> #endif /* NO_SWAPPING */
> }
>
>
> I.e., you could just move the critical_enter() in subr_turnstile.c earlier so
> it is before the mtx_unlock_spin() of the turnstile chain lock.
>
> --
> John Baldwin <jhb at FreeBSD.org> <>< http://www.FreeBSD.org/~jhb/
> "Power Users Use the Power to Serve" = http://www.FreeBSD.org
This patch did not seem to make the freeze problem go away.
--
Peter Holm
More information about the freebsd-arch
mailing list