Skip site navigation (1)Skip section navigation (2)

FreeBSD Man Pages

Man Page or Keyword Search:
Man Architecture
Apropos Keyword Search (all sections) Output format
home | help
KSE(2)                    FreeBSD System Calls Manual                   KSE(2)

     kse - kernel support for user threads

     Standard C Library (libc, -lc)

     #include <sys/types.h>
     #include <sys/kse.h>

     kse_create(struct kse_mailbox *mbx, int newgroup);



     kse_wakeup(struct kse_mailbox *mbx);

     kse_thr_interrupt(struct kse_thr_mailbox *tmbx);

     These functions implement kernel support for multi-threaded processes.

     Traditionally, user threading has been implemented in one of two ways:
     either all threads are managed in user space and the kernel is unaware of
     any threading (also known as ``N to 1''), or else separate processes
     sharing a common memory space are created for each thread (also known as
     ``N to N'').  These approaches have advantages and disadvantages:

     User threading                    Kernel threading
     + Lightweight                     - Heavyweight
     + User controls scheduling        - Kernel controls scheduling
     - Syscalls must be wrapped        + No syscall wrapping required
     - Cannot utilize multiple CPUs    + Can utilize multiple CPUs

     The KSE system is a hybrid approach that achieves the advantages of both
     the user and kernel threading approaches.  The underlying philosophy of
     the KSE system is to give kernel support for user threading without
     taking away any of the user threading library's ability to make
     scheduling decisions.  A kernel-to-user upcall mechanism is used to pass
     control to the user threading library whenever a scheduling decision
     needs to be made.  Arbitrarily many user threads are multiplexed onto a
     fixed number of virtual CPUs supplied by the kernel.  This can be thought
     of as an ``N to M'' threading scheme.

     Some general implications of this approach include:

     +o   The user process can run multiple threads simultaneously on multi-
         processor machines.  The kernel grants the process virtual CPUs to
         schedule as it wishes; these may run concurrently on real CPUs.

     +o   All operations that block in the kernel become asynchronous, allowing
         the user process to schedule another thread when any thread blocks.

     +o   Multiple thread schedulers within the same process are possible, and
         they may operate independently of each other.

     KSE allows a user process to have multiple threads of execution in
     existence at the same time, some of which may be blocked in the kernel
     while others may be executing or blocked in user space.  A kernel
     scheduling entity (KSE) is a ``virtual CPU'' granted to the process for
     the purpose of executing threads.  A thread that is currently executing
     is always associated with exactly one KSE, whether executing in user
     space or in the kernel.  The KSE is said to be assigned to the thread.

     The KSE becomes unassigned, and the associated thread is suspended, when
     the KSE has an associated mailbox (see below) and any of the following

     +o   The thread invokes a blocking system call.

     +o   The thread makes any other demand of the kernel that cannot be
         immediately satisfied, e.g., touches a page of memory that needs to
         be fetched from disk, causing a page fault.

     +o   Another thread that was previously blocked in the kernel completes
         its work in the kernel (or is interrupted) and becomes ready to
         return to user space.

     +o   A signal is delivered to the process, and this KSE is chosen to
         deliver it.

     In other words, as soon as there is a scheduling decision to be made, the
     KSE becomes unassigned, because the kernel does not presume to know how
     the process' other runnable threads should be scheduled.  Unassigned KSEs
     always return to user space as soon as possible via the upcall mechanism
     (described below), allowing the user process to decide how that KSE
     should be utilized next.  KSEs always complete as much work as possible
     in the kernel before becoming unassigned.

     A KSE group is a collection of KSEs that are scheduled uniformly and
     which share access to the same pool of threads, which are associated with
     the KSE group.  A KSE group is the smallest entity to which a kernel
     scheduling priority may be assigned.  For the purposes of process
     scheduling and accounting, each KSE group counts the same as a
     traditional unthreaded process.  Individual KSEs within a KSE group are
     effectively indistinguishable, and any KSE in a KSE group may be assigned
     by the kernel to any runnable thread associated with that KSE group.  In
     practice, the kernel attempts to preserve the affinity between threads
     and actual CPUs to optimize cache behavior, but this is invisible to the
     user process.

     Each KSE has a unique KSE mailbox supplied by the user process.  A
     mailbox consists of a control structure containing a pointer to an upcall
     function and a user stack.  The KSE invokes this function whenever it
     becomes unassigned.  The kernel updates this structure with information
     about threads that have become runnable and signals that have been
     delivered before each upcall.  Upcalls may be temporarily blocked by the
     user thread scheduling code during critical sections.

     Each user thread has a unique thread mailbox as well.  Threads are
     referred to using pointers to these mailboxes when communicating between
     the kernel and the user thread scheduler.  Each KSE's mailbox contains a
     pointer to the mailbox of the user thread that the KSE is currently
     executing.  This pointer is saved when the thread blocks in the kernel.

     Whenever a thread blocked in the kernel is ready to return to user space,
     it is added to the KSE group's list of completed threads.  This list is
     presented to the user code at the next upcall as a linked list of thread

     There is a kernel-imposed limit on the number of threads in a KSE group
     that may be simultaneously blocked in the kernel (this number is not
     currently visible to the user).  When this limit is reached, upcalls are
     blocked and no work is performed for the KSE group until one of the
     threads completes (or a signal is received).

   Managing KSEs
     To become multi-threaded, a process must first invoke kse_create().
     kse_create() creates a new KSE (except for the very first invocation; see
     below).  The KSE will be associated with the mailbox pointed to by mbx.
     If newgroup is non-zero, a new KSE group is also created containing the
     KSE.  Otherwise, the new KSE is added to the current KSE group.  Newly
     created KSEs are initially unassigned; therefore, they will upcall

     Each process initially has a single KSE in a single KSE group executing a
     single user thread.  Since the KSE does not have an associated mailbox,
     it must remain assigned to the thread and does not perform any upcalls.
     The result is the traditional, unthreaded mode of operation.  Therefore,
     as a special case, the first call to kse_create() by this initial thread
     with newgroup equal to zero does not create a new KSE; instead, it simply
     associates the current KSE with the supplied KSE mailbox, and no
     immediate upcall results.  However, the upcall will be invoked the next
     time the thread blocks.

     The kernel does not allow more KSEs to exist in a KSE group than the
     number of physical CPUs in the system (this number is available as the
     sysctl(3) variable hw.ncpu).  Having more KSEs than CPUs would not add
     any value to the user process, as the additional KSEs would just compete
     with each other for access to the real CPUs.  Since the extra KSEs would
     always be side-lined, the result to the application would be exactly the
     same as having fewer KSEs.  There may however be arbitrarily many user
     threads, and it is up to the user thread scheduler to handle mapping the
     application's user threads onto the available KSEs.

     kse_exit() causes the KSE assigned to the currently running thread to be
     destroyed.  If this KSE is the last one in the KSE group, there must be
     no remaining threads associated with the KSE group blocked in the kernel.
     This function does not return.

     As a special case, if the last remaining KSE in the last remaining KSE
     group invokes this function, then the KSE is not destroyed; instead, the
     KSE just looses the association with its mailbox and kse_exit() returns
     normally.  This returns the process to its original, unthreaded state.

     kse_release() is used to ``park'' the KSE assigned to the currently
     running thread when it is not needed, e.g., when there are more available
     KSEs than runnable user threads.  The KSE remains unassigned but does not
     upcall until there is a new reason to do so, e.g., a previously blocked
     thread becomes runnable.  If successful, kse_release() does not return.

     kse_wakeup() is the opposite of kse_release().  It causes the KSE
     associated with the mailbox pointed to by mbx to be woken up, causing it
     to upcall.  If the KSE has already woken up for another reason, this
     function has no effect.  The mbx may be NULL to specify ``any KSE in the
     current KSE group''.

     kse_thr_interrupt() is used to interrupt a currently blocked thread.  The
     thread must either be blocked in the kernel or assigned to a KSE (i.e.,
     executing).  The thread is then marked as interrupted.  As soon as the
     thread invokes an interruptible system call (or immediately for threads
     already blocked in one), the thread will be made runnable again, even
     though the kernel operation may not have completed.  The effect on the
     interrupted system call is the same as if it had been interrupted by a
     signal; typically this means an error is returned with errno set to

     When a process has at least one KSE with an associated mailbox, then
     signals are no longer delivered on the process stack.  Instead, signals
     are delivered via upcalls.  Multiple signals may be delivered with one

     If there are multiple KSE groups in the process, which KSE group is
     chosen to deliver the signal is indeterminate.  However, once a signal
     has been delivered to a specific KSE group, that KSE group then takes
     ownership of signal delivery and all subsequent signals are delivered via
     that KSE group.  When this KSE group is destroyed, a new KSE group is
     chosen as needed.

   KSE Mailboxes
     Each KSE has a unique mailbox for user-kernel communication:

     /* Upcall function type */
     typedef void    kse_func_t(struct kse_mailbox *);

     /* KSE mailbox */
     struct kse_mailbox {
             int                     km_version;     /* Mailbox version */
             struct kse_thr_mailbox  *km_curthread;  /* Current thread */
             struct kse_thr_mailbox  *km_completed;  /* Completed threads */
             sigset_t                km_sigscaught;  /* Caught signals */
             unsigned int            km_flags;       /* KSE flags */
             kse_func_t              *km_func;       /* UTS function */
             stack_t                 km_stack;       /* UTS context */
             void                    *km_udata;      /* For use by the UTS */
             struct timespec         km_timeofday;   /* Time of upcall */

     km_version describes the version of this structure and must be equal to
     KSE_VER_0.  km_udata is an opaque pointer ignored by the kernel.

     km_func points to the KSE's upcall function; it will be invoked using
     km_stack, which must remain valid for the lifetime of the KSE.

     km_curthread always points to the thread that is currently assigned to
     this KSE if any, or NULL otherwise.  This field is modified by both the
     kernel and the user process as follows.

     When km_curthread is not NULL, it is assumed to be pointing at the
     mailbox for the currently executing thread, and the KSE may be
     unassigned, e.g., if the thread blocks in the kernel.  The kernel will
     then save the contents of km_curthread with the blocked thread, set
     km_curthread to NULL, and upcall to invoke km_func().

     When km_curthread is NULL, the kernel will never perform any upcalls with
     this KSE; in other words, the KSE remains assigned to the thread even if
     it blocks.  km_curthread must be NULL while the KSE is executing critical
     user thread scheduler code that would be disrupted by an intervening
     upcall; in particular, while km_func() itself is executing.

     Before invoking km_func() in any upcall, the kernel always sets
     km_curthread to NULL.  Once the user thread scheduler has chosen a new
     thread to run, it should point km_curthread at the thread's mailbox, re-
     enabling upcalls, and then resume the thread.  Note: modification of
     km_curthread by the user thread scheduler must be atomic to avoid the
     race condition where the kernel saves a partially modified value.

     km_completed points to a linked list of user threads that have completed
     their work in the kernel since the last upcall.  The user thread
     scheduler should put these threads back into its own runnable queue.
     Each thread in a KSE group that completes is guaranteed to be linked into
     exactly one KSE's km_completed list; which KSE in the group, however, is
     indeterminate.  Furthermore, the thread will appear in only one upcall.

     km_sigscaught contains the list of signals caught by this process since
     the previous upcall to any KSE in the process.  As long as there exists
     one or more KSEs with an associated mailbox in the user process, signals
     are delivered this way rather than the traditional way.

     km_timeofday is set by the kernel to the current system time before
     performing each upcall.

     km_flags may contain any of the following bits OR'ed together:

             (No flags are defined yet.)

   Thread Mailboxes
     Each user thread must have associated with it a unique struct

     /* Thread mailbox */
     struct kse_thr_mailbox {
             ucontext_t              tm_context;     /* User thread context */
             unsigned int            tm_flags;       /* Thread flags */
             struct kse_thr_mailbox  *tm_next;       /* Next thread in list */
             void                    *tm_udata;      /* For use by the UTS */
             unsigned int            tm_uticks;      /* User time counter */
             unsigned int            tm_sticks;      /* Kernel time counter */

     tm_udata is an opaque pointer ignored by the kernel.

     tm_context stores the context for the thread when the thread is blocked
     in user space.  This field is updated by the kernel before a completed
     thread is returned to the user thread scheduler via km_completed.

     tm_next links the km_completed threads together when returned by the
     kernel with an upcall.  The end of the list is marked with a NULL

     tm_uticks and tm_sticks are time counters for user mode and kernel mode
     execution, respectively.  These counters count ticks of the statistics
     clock (see clocks(7)).  While any thread is actively executing in the
     kernel, the corresponding tm_sticks counter is incremented.  While any
     KSE is executing in user space and that KSE's km_curthread pointer is not
     equal to NULL, the corresponding tm_uticks counter is incremented.

     tm_flags may contain any of the following bits OR'ed together:

             (No flags are defined yet.)

     kse_create(), kse_wakeup, and kse_thr_interrupt() return zero if
     successful.  kse_exit() and kse_release() do not return if successful.

     All of these functions return a non-zero error code in case of an error.

     Note: error codes are returned directly rather than via errno.

     kse_create() will fail if:

     [ENXIO]            There are already as many KSEs in the KSE group as
                        hardware processors.

     [EAGAIN]           The system-imposed limit on the total number of KSE
                        groups under execution would be exceeded.  The limit
                        is given by the sysctl(3) MIB variable KERN_MAXPROC.
                        (The limit is actually ten less than this except for
                        the super user.)

     [EAGAIN]           The user is not the super user, and the system-imposed
                        limit on the total number of KSE groups under
                        execution by a single user would be exceeded.  The
                        limit is given by the sysctl(3) MIB variable

     [EAGAIN]           The user is not the super user, and the soft resource
                        limit corresponding to the resource parameter
                        RLIMIT_NPROC would be exceeded (see getrlimit(2)).

     [EFAULT]           mbx points to an address which is not a valid part of
                        the process address space.

     kse_exit() will fail if:

     [EDEADLK]          The current KSE is the last in its KSE group and there
                        are still one or more threads associated with the KSE
                        group blocked in the kernel.

     [ESRCH]            The current KSE has no associated mailbox, i.e., the
                        process is operating in traditional, unthreaded mode
                        (in this case use exit(2) to exit the process).

     kse_release() will fail if:

     [ESRCH]            The current KSE has no associated mailbox, i.e., the
                        process is operating is traditional, unthreaded mode.

     kse_wakeup() will fail if:

     [ESRCH]            mbx is not NULL and the mailbox pointed to by mbx is
                        not associated with any KSE in the process.

     [ESRCH]            mbx is NULL and the current KSE has no associated
                        mailbox, i.e., the process is operating in
                        traditional, unthreaded mode.

     kse_thr_interrupt() will fail if:

     [ESRCH]            The thread corresponding to tmbx is neither currently
                        assigned to any KSE in the process nor blocked in the

     rfork(2), pthread(3), ucontext(3)

     Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska, and Henry M.
     Levy, "Scheduler activations: effective kernel support for the user-level
     management of parallelism", ACM Press, ACM Transactions on Computer
     Systems, Issue 1, Volume 10, pp. 53-79, February 1992.

     The KSE function calls first appeared in FreeBSD 5.0.

     KSE was originally implemented by Julian Elischer <>,
     with additional contributions by Jonathan Mini <>, Daniel
     Eischen <>, and David Xu <>.

     This manual page was written by Archie Cobbs <>.

     The KSE code is currently under development.

FreeBSD 11.0-PRERELEASE       September 10, 2002       FreeBSD 11.0-PRERELEASE


Want to link to this manual page? Use this URL:

home | help