Path: utzoo!utgpu!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!mailrus!ames!pasteur!agate!saturn!fouts@lemming.
From: fouts@lemming. (Marty Fouts)
Newsgroups: comp.os.research
Subject: Re: Question on thread/process scheduler interaction
Message-ID: <5475@saturn.ucsc.edu>
Date: 15 Nov 88 16:59:41 GMT
Sender: usenet@saturn.ucsc.edu
Organization: NASA Ames Research Center, Moffet Field, CA
Lines: 62
Approved: comp-os-research@jupiter.ucsc.edu


In article <5460@saturn.ucsc.edu> edler@cmcl2.nyu.edu (Jan Edler) writes:

   This topic is a few weeks old, but we had a some kind of news problem here
   delayed my posting this.

   In article <5296@saturn.ucsc.edu> fouts@lemming. (Marty Fouts) writes:
   >N tasks (threads) are started on top of M processes on a
   >multiprocessor with P processors (N >= M >= P > 1).
   ...
   >One task enters the critical region in one process.  While there, a
   >second task running on a different process spinlocks on the semaphore.
   ...
   >The process level scheduler preempts the process running the task in
   >the critical region leaving the second process at the spinlock.  The
   >worst case is when the process is preempted by a third process
   >belonging to the same job which also reaches the spinlock.

   Our solution to this problem is a mechanism called "temporary nonpreemption".
   A process informs the kernel of temporary conditions that make preemption
   unadvisable.  The scheduler in the kernel honors this advice, up to a limit
   to prevent abuse.  This solves the problem as long as the maximum time in
   the critical secion is less than the limit the scheduler is willing to honor.

   The implementation is very efficient.

   [More complete description of implementation deleted.]

The system I am investigating has this feature, along with an
additional "advantage":  When a process which is running a task is
about to be preempted by the os level scheduler it saves state, so
that the next process of the group which gets scheduled can pick up
the state and continue execution.  This is done as a means of avoiding
fixing the relationship of a task to a process.

The disadvantage in the current implementation is an addition
"feature" of the implementation:  Each time a process picks up the
work of a task which has been dropped because some other process has
been preempted by the OS, it picks it up at a synchronization point
which may (and generally does) lead to work being duplicated.  At the
language level in this implementation, the synchronization point
corresponds to the entry point of a subroutine.

For a suitably pathologic program (IE, the one I'm interested in
implementing) the behavior of this system exactly mimics the behavior
of the naive system I described in my original posting:  A process
enters the critical region of a task and informs the operating system
that it should not be preempted.  It then takes longer than the OS is
willing to allow to perform the critical region work (the pathology)
so that the process is forced out anyway.

Oh well, I guess it is time to restructure the problem to require less
work in the critical region.  One good thing is that my measurements
seem to confirm the claim for efficency.  Even on a very pathologic
case this system is much more efficent than the naive approach.

--
+-+-+-+     I don't know who I am, why should you?     +-+-+-+
   |        fouts@lemming.nas.nasa.gov                    |
   |        ...!ames!orville!fouts                        |
   |        Never attribute to malice what can be         |
+-+-+-+     explained by incompetence.                 +-+-+-+