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

FreeBSD Manual Pages


home | help
KSE(2)			    BSD	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	shar-
     ing 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 tak-
     ing 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	exis-
     tence 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	asso-
     ciated 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	imme-
	 diately 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 re-
	 turn to user space.

     +o	 A signal is delivered to the process, and this	KSE is chosen to de-
	 liver 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 sched-
     uling and accounting, each	KSE group counts the same as a traditional un-
     threaded process.	Individual KSEs	within a KSE group are effectively in-
     distinguishable, 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	mail-
     box consists of a control structure containing a pointer to an upcall
     function and a user stack.	 The KSE invokes this function whenever	it be-
     comes unassigned.	The kernel updates this	structure with information
     about threads that	have become runnable and signals that have been	deliv-
     ered 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	re-
     ferred 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 exe-
     cuting.  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 cur-
     rently 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	imme-

     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 immedi-
     ate 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 num-
     ber 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 up-
     call 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 associ-
     ated with the mailbox pointed to by mbx to	be woken up, causing it	to up-
     call.  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 sig-
     nals are no longer	delivered on the process stack.	 Instead, signals are
     delivered via upcalls.  Multiple signals may be delivered with one	up-

     If	there are multiple KSE groups in the process, which KSE	group is cho-
     sen to deliver the	signal is indeterminate.  However, once	a signal has
     been delivered to a specific KSE group, that KSE group then takes owner-
     ship 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	mail-
     box 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 up-
     call; 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 sched-
     uler should put these threads back	into its own runnable queue.  Each
     thread in a KSE group that	completes is guaranteed	to be linked into ex-
     actly 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 per-
     forming 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 ker-
     nel with an upcall.  The end of the list is marked	with a NULL pointer.

     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 success-
     ful.  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 execu-
			tion 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 tradi-
			tional,	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.

BSD			      September	10, 2002			   BSD


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

home | help