Thread Execution, Scheduling, and Multiprocessing on XNU

Man is born free, and everywhere he is in chains. - Jean-Jacques Rousseau; The Social Contract

Preamble

This post explores how XNU — the kernel behind macOS and iOS — schedules and executes threads across processors. We'll look at preemptive scheduling, the Mach continuation model that allows kernel stacks to be reclaimed, and the hardware topology that underlies multiprocessing: cores, dies, SMT, and the distinction between symmetric and asymmetric multiprocessing.

This post builds on the Mach abstractions covered in Mach Kernel Abstractions and XNU Internals. Familiarity with Mach tasks and threads will be helpful but is not strictly required.

Program Interruption and Preemptive Scheduling

The idea of multiprogramming technique was conceived when it was realized that precious CPU time was being wasted due to historical programming paradigm. Under History of Operating Systems of [MOS] (Specifically Section 1.2.3), we observe that in the early days of computing, people soon came to realization that I/O wait time accounted for majority of total time for a job to its completion. Instead of providing one job to the CPU at a time, there was a need to allow multiple jobs to exist simultaneously. This would ensure that the CPU is as efficient as possible. Since then, various studies have been done to make the CPU as efficient as it can be.

Preemptive Scheduling on XNU

It is the operating system that is responsible for scheduling multiple jobs that are present to be processed. More precisely, the scheduling subsystem (or the scheduler) is responsible for providing CPU time to all threads in the system. In a non-preemptive scheduling approach, a job is executed till its completion, and the next one is selected. In contrast, in a preemptive scheduling approach, the scheduler is responsible for interrupting the current job (and saving its current state if it is not finished) and loading appropriate context for another job in the CPU. Most kernels used in general purpose computers use preemptive schedulers so as to allow multiple jobs to be run.

Preemption is one form of interruption. When there are multiple jobs in a system--as is in most general purpose system--at any given time, preemption is the technique by which the scheduler ensures that those jobs get their fair share of processing time. The frequency at which the kernel will preempt threads, also known as preemption rate, can be fetched using the sysctl(1) utility as:

$ sysctl kern.clockrate
kern.clockrate: { hz = 100, tick = 10000, tickadj = 0, profhz = 100, stathz = 100 }

note

I might use the terms job and thread to imply the same thing. Since a task is not a runnable entity, it cannot be loaded on the processor, but a thread corresponding to a task is loaded on the processor.

Unlike some other system information, the clockrate information is represented as a structure object. The structure definition can be located in sys/time.h as:

/*
 * Getkerninfo clock information structure
 */
struct clockinfo {
	int     hz;             /* clock frequency */
	int     tick;           /* micro-seconds per hz tick */
	int     tickadj;        /* clock skew rate for adjtime() */
	int     stathz;         /* statistics clock frequency */
	int     profhz;         /* profiling clock frequency */
};

Notice that the preemption rate is 100 HZ on my machine. This implies that the timeslice quantum--amount of time a thread receives to use the processor--on my machine is 0.01s (10 ms). The tick value represents the number of microseconds in a scheduler tick. Furthermore, [MOSX_INTERNALS] mentions that hz value can be seen as the frequency of a hardware-independent system clock.

The scheduler on XNU is priority-based. It means that the thread (and task too) structure contains an attribute that represents its priority. Furthermore, direct alteration of priority is not really honoured the way one might expect. A thread does not carry a single priority but four related fields, found in [osfmk/kern/thread.h]: the priority it is currently scheduled at (int16_t sched_pri;), its effective base priority (int16_t base_pri;), the base priority that was actually requested (int16_t req_base_pri;), and a per-thread maximum priority (int16_t max_priority;).

When user space requests an absolute priority through [thread_policy_set], the kernel does not store that number at all. As seen in [osfmk/kern/thread_policy.c], it is converted into a relative importance against the task's priority, and the comment above the conversion is explicit about this:

Reverse engineer and apply the correct importance value from the requested absolute priority value.

TODO: Store the absolute priority value instead

The derived value is then clamped to max_priority, and clamped again every time the priority is recomputed.

What clamping means here

To clamp a value is to force it into a permitted range: if it falls below the minimum, the minimum is used; if it rises above the maximum, the maximum is used; otherwise it passes through unchanged. The kernel expresses this with a pair of nested macros:

adj_priority = priority;
adj_priority = MIN(adj_priority, thread->max_priority);
adj_priority = MAX(adj_priority, MINPRI);

A thread that requests priority 80 while its max_priority is 63 therefore does not fail, and does not receive 80. It silently receives 63.

The reader should also be aware that this maximum is not a constant; as the comment in [thread_recompute_priority] explains, it is 4 or 20 for a task clamped to background or utility, 63 for a user task, and 95 for the kernel task. The same comment notes that thread->importance is user-settable to any integer via THREAD_PRECEDENCE_POLICY, which is precisely why the clamp has to exist.

On top of the clamp, the effective priority is recomputed from several inputs that the thread itself does not control: priority promotion inherited from lock ownership, workload-driven priorities, failsafe demotion for a realtime thread that overran its quantum, and a temporary override that lifts a terminating thread out of a background clamp so that it can exit promptly. A requested priority is therefore better understood as one input among many rather than a setting.

This separation between what was asked for and what takes effect is not specific to priority. Under Effectuating policy changes of Chapter 9 of [OS_INTERNALS], the following remark can be found:

At the thread level, the requested_policy and effective_policy may differ, so they are maintained in two separate fields in the Mach thread structure.

Both fields are present in [osfmk/kern/thread.h], and they are not merely an analogy to the priority fields; the two mechanisms are wired together. [thread_recompute_priority] reads the effective policy directly, consulting thread->effective_policy.thep_promote_above_task and thread->effective_policy.thep_terminated when deciding whether a thread is permitted to exceed its max_priority. The req_base_pri and base_pri pair seen earlier is the same design applied one level down, to priority rather than policy.

Run Queues in the Mach Scheduler

On Mach, a data structure which is non-trivial to the scheduling subsystem is a run queue. Its definition in [osfmk/kern/sched.h] is compact:

struct run_queue {
	int                     highq;                          /* highest runnable queue */
	bitmap_t                bitmap[BITMAP_LEN(NRQS)];       /* run queue bitmap array */
	int                     count;                          /* # of threads total */
	int                     urgency;                        /* level of preemption urgency */
	circle_queue_head_t     queues[NRQS];           /* one for each priority */

	struct runq_stats       runq_stats;
};

The important part is queues[NRQS]: rather than one list of runnable threads, there is a separate queue per priority level. Selecting the next thread to run is then a matter of finding the highest non-empty queue and taking its head, instead of scanning every runnable thread. The highq field caches the index of that highest runnable queue, and bitmap records which levels are currently occupied, so the search is a bit-scan over a small bitmap.

NRQS is itself defined in terms of the realtime base priority (see [osfmk/kern/sched.h]), giving 96 non-realtime levels; realtime threads are counted separately as NRTQS:

#define NRQS                    (BASEPRI_REALTIME)      /* Non-realtime levels for runqs */
#define NRTQS                   (MAXPRI - BASEPRI_REALTIME) /* Realtime levels for runqs */

The same header lays out the priority bands these levels are divided into:

Priority	Band
97	BASEPRI_RTQUEUES (realtime run queues)
95	MAXPRI_KERNEL (kernel maximum)
80	MINPRI_KERNEL
63	MAXPRI_USER (user task maximum)
47	BASEPRI_FOREGROUND
31	BASEPRI_DEFAULT (default base for threads)
20	BASEPRI_UTILITY
4	MAXPRI_THROTTLE
0	MINPRI / DEPRESSPRI

note

The queues array is a circle_queue_head_t, a circular queue. This matters for fairness within a single priority level: threads at the same priority are taken round-robin rather than one of them being able to starve the others.

Thread Continuation Model in Mach

Every thread that enters the kernel needs somewhere to keep its working state: local variables, saved registers, and the chain of callers that led it there. That somewhere is the kernel stack, and on XNU it is not small. The symbol KERNEL_STACK_SIZE, defined in [osfmk/mach/arm/vm_param.h], sets it:

#if KASAN
/* Increase the stack sizes to account for the redzones that get added to every
 * stack object. */
# define KERNEL_STACK_SIZE      (4*4*4096)
#elif DEBUG
/**
 * Increase the stack size to account for less efficient use of stack space when
 * compiling with -O0.
 */
# define KERNEL_STACK_SIZE      (2*4*4096)
#else
/*
 * KERNEL_STACK_MULTIPLIER can be defined externally to get a larger
 * kernel stack size. For example, adding "-DKERNEL_STACK_MULTIPLIER=2"
 * helps avoid kernel stack overflows when compiling with "-O0".
 */
#ifndef KERNEL_STACK_MULTIPLIER
#define KERNEL_STACK_MULTIPLIER (1)
#endif /* KERNEL_STACK_MULTIPLIER */
# define KERNEL_STACK_SIZE      (4*4096*KERNEL_STACK_MULTIPLIER)
#endif /* XNU_KERNEL_PRIVATE */

A release kernel therefore gives every thread at least 16 KB, and debug configurations more. That memory is wired: it cannot be paged out, because the kernel may need to touch it precisely at moments when taking a page fault is not an option. A system carrying a few thousand threads thus spends tens of megabytes of unpageable memory on kernel stacks alone.

What makes this wasteful is that most threads, most of the time, are blocked. A blocked thread is doing no work at all. It is holding 16 KB of wired memory for one purpose: to remember where it was. The continuation model is Mach's answer to that, and it is discussed in 7.2.6 of [MOSX_INTERNALS].

What a kernel stack is, and what "freeing" one means

A kernel stack is an ordinary range of kernel virtual memory, allocated with a guard page on either side. [osfmk/kern/stack.c] requests two pages beyond the stack size and then steps past the lower one:

/*
 * Request guard pages on either side of the stack.  Ask
 * kernel_memory_allocate() for two extra pages to account
 * for these.
 */

kernel_memory_allocate(kernel_map, &stack,
    kernel_stack_size + ptoa(2), stack_addr_mask,
    flags, VM_KERN_MEMORY_STACK);

/*
 * The stack address that comes back is the address of the lower
 * guard page.  Skip past it to get the actual stack base address.
 */

stack += PAGE_SIZE;

Those guard pages are why a kernel stack overflow faults at a recognisable address instead of quietly corrupting whatever happens to sit next to it.

Attaching a stack to a thread is stack_alloc, which passes the result to the machine-dependent layer:

void
stack_alloc(
	thread_t        thread)
{
	assert(thread->kernel_stack == 0);
	machine_stack_attach(thread, stack_alloc_internal());
}

The part that matters for this section is what stack_free does not do: it does not hand the memory back to the VM subsystem. [osfmk/kern/stack.c] pushes the stack onto a per-processor cache, falling back to a global free list once that cache is full:

cache = PERCPU_GET(stack_cache);
if (cache->count < STACK_CACHE_SIZE) {
	stack_next(stack) = cache->free;
	cache->free = stack;
	cache->count++;
} else {
	stack_lock();
	stack_next(stack) = stack_free_list;
	stack_free_list = stack;

Releasing a stack is therefore a list push, and acquiring one a list pop. This is what makes the whole arrangement worth the trouble: if every block and wakeup cost a full kernel map allocation, giving the stack back would buy very little.

The Process Model and the Interrupt Model

When a thread blocks, something has to record how it is to be resumed. There are two ways of doing this, and they differ in what they treat as the system of record.

In the process model, the kernel stack is the record. The thread's position in the code, its local variables, and its chain of callers are all on the stack already, so blocking means leaving that stack untouched and switching away from it; resuming means switching back to it. Every thread needs a stack of its own for this to work, which makes the stack a per-thread resource.

In the interrupt model, the kernel stack is a per-processor resource instead. There is one stack per processor, used by whichever thread happens to be running on it. A thread cannot leave its state on a stack it does not own, so it must write down what it needs somewhere else before blocking.

[Draves 91] describes the design that results, under Restructuring With Continuations (Section 1.4):

We have restructured the Mach kernel so that a thread can use either the process model or the interrupt model when blocking. When a thread blocks using the process model, its current execution state is recorded on the stack. The blocked thread is resumed with a context-switch. When a thread blocks using the interrupt model, it records the execution context in which it should be resumed in an auxiliary data structure, called a continuation.

Before Mach 3 was introduced, the kernel was limited to the process model. The process model has the advantage that it can be easily programmed, yet it did come with its drawbacks. The obvious one: it consumes more space, since each thread allocates a stack in the kernel address space (per-thread resource). Another one discussed is that optimization techniques to reduce the latency of transferring control from one thread to another were found to be difficult, as the kernel stack reflects the state of the blocked thread at the machine level. Furthermore, [Draves 91]--under Some Inadequate Solutions (Section 1.3)--also mentions that the interrupt model was inappropriate for the Mach kernel. This is why continuation is considered the appropriate middle-ground between these two execution models.

What a Continuation Is

A continuation is a function pointer held in the thread structure, recording the address at which the thread is to resume the next time it is dispatched. It takes over from the kernel stack as the record of where the thread had reached: rather than preserving the entire call state where it stands, the thread preserves a single entry point and discards the rest.

The trade is therefore not free. When a thread blocks with a continuation, its stack may be released, and everything that lived on it is gone: every local variable, every saved register, the whole chain of callers. The thread does not resume in the middle of the function that blocked. It resumes at the top of the function the continuation names, running on a freshly assigned stack. Anything that must survive the block has to live somewhere other than the stack--a global, a static, a field in the thread structure, or the single void * parameter a continuation is permitted to carry.

An analogy, if it helps

Consider two ways of pausing a book: keeping a finger on the page, or closing the book after writing the page number down.

The finger preserves everything. You resume mid-sentence, with the sentence still in your head, but one hand is occupied for the whole time you are away. Writing the number down frees the hand and lets the book go back on the shelf, at the cost of your place in the sentence and whatever you had been holding in mind while reading.

The kernel stack is the finger; the continuation is the page number. A thread blocking with a continuation takes the second arrangement: it gives up the fine detail of where it was, in exchange for not having to hold anything while it waits.

The signature is declared in [osfmk/kern/kern_types.h]. A continuation returns nothing and takes two arguments:

typedef void (*thread_continue_t)(void *, wait_result_t);
#define THREAD_CONTINUE_NULL    ((thread_continue_t) NULL)

The second argument is worth noting, because it is how a resumed thread learns why it woke up. The same header defines the possible values: THREAD_AWAKENED for a normal wakeup, THREAD_TIMED_OUT if a timeout expired, THREAD_INTERRUPTED if the wait was aborted, and THREAD_RESTART if the operation is to be started over. A thread that resumes on a fresh stack has lost its local variables, but it is at least told the outcome of the wait it just finished.

struct thread itself holds the pieces, in [osfmk/kern/thread.h]:

thread_continue_t       continuation;   /* continue here next dispatch */
void                   *parameter;      /* continuation parameter */
...
vm_offset_t             kernel_stack;   /* current kernel stack */
vm_offset_t             reserved_stack; /* reserved kernel stack */

Those four fields are very nearly the whole mechanism: where to resume, what to pass when resuming, which stack the thread currently owns, and one held in reserve.

Blocking With a Continuation

XNU offers two entry points for blocking, both defined in [osfmk/kern/sched_prim.c]:

wait_result_t
thread_block(
	thread_continue_t       continuation)
{
	return thread_block_reason(continuation, NULL, AST_NONE);
}

wait_result_t
thread_block_parameter(
	thread_continue_t       continuation,
	void                            *parameter)
{
	return thread_block_reason(continuation, parameter, AST_NONE);
}

Both forward to [thread_block_reason], which does the actual work. thread_block_parameter is the one to use when the continuation needs an argument; the value supplied is stored in the thread's parameter field and loaded into the appropriate register before the continuation is called.

The choice between the two execution models is not a build option or a per-thread setting. It is made at each individual blocking call, by what is passed as the continuation:

• thread_block(THREAD_CONTINUE_NULL) blocks without a continuation. The thread keeps its kernel stack, and on wakeup execution carries on at the statement following the call, exactly as any ordinary blocking call behaves. This is the process model.
• thread_block(some_function) blocks with a continuation. The thread's stack may be released while it waits, and on wakeup some_function is entered from the top on a new stack. Execution never returns to the statement following the call. This is the interrupt model.

The second form is what makes the stack reclaimable, and it is also what makes continuation-style code look unusual: a function that blocks with a continuation never finishes normally.

note

It might be helpful to assume we're working on some low level task and not the typical BSD process. Doing so allows us to view instructions without added complexity such as system call transition from user-land to kernel-land, or other hardware/software exceptions. Although they too use the idea of continuation, let's look at a simpler example.

Converting the Kernel to Use Continuations (Section 2.2) of [Draves 91] describes the pattern this leads to in practice:

For threads that run only in the kernel, there is no "return-to-user-level" continuation. In practice, most of our kernel threads execute an infinite loop, blocking until an event occurs, doing some work, and then blocking again. For these threads, we define the continuation to be a function containing the body of the loop. The last statement in the function blocks with a continuation that is the function itself, thereby achieving the infinite loop via tail-recursion.

A thread of this kind only ever deals with one stack, the kernel stack, which keeps the illustration simple. Take a kernel thread whose job is to drain a queue of work items: it sleeps until something is enqueued, handles what it finds, and sleeps again. The event it waits on is just an address both sides agree to treat as a token--the queue itself will do--and whoever enqueues work wakes the thread with thread_wakeup(&work_queue).

In the process model:

void
worker_thread(void)
{
  int drained = 0;              /* safe: the stack is kept across the block */

  for (;;) {
    assert_wait(&work_queue, THREAD_INTERRUPTIBLE);

    if (thread_block(THREAD_CONTINUE_NULL) != THREAD_AWAKENED) {
      continue;                 /* interrupted or timed out, not signalled */
    }

    drained += drain(&work_queue);
  }
}

An ordinary loop, with thread_block returning into the middle of it. The local drained survives because the stack holding it is never released. The same thing in the interrupt model:

static int work_drained;        /* must not live on the stack */

static void
worker_continue(void *param, wait_result_t wres)
{
  if (wres == THREAD_AWAKENED) {
    work_drained += drain(&work_queue);
  }

  assert_wait(&work_queue, THREAD_INTERRUPTIBLE);
  thread_block_parameter(worker_continue, param);
  /*NOTREACHED*/
}

No loop keyword appears, yet this loops: the final statement blocks with the function itself as the continuation, so each wakeup re-enters it from the top. This is the tail-recursion the paper refers to, and it accumulates no frames. It needs no separate entry point either, since kernel_thread_start takes a thread_continue_t as a thread's starting address.

Three things had to change. The counter became a static, since a local would read zero on every wakeup. The event is re-asserted before each block. And param is carried through thread_block_parameter rather than kept in a variable.

The second parameter deserves a word, since its purpose is easy to miss. Either model has to tell the thread why it woke, and the answer usually decides what happens next. In the process model it is the return value of thread_block--thread_block_reason ends with return self->wait_result;. In the interrupt model there is no frame left to return into, so the same value is handed over as an argument. Identical information, different route.

XNU's semaphore implementation makes the choice between the two routes unusually visible, since it supports both. In [semaphore_wait_internal] the decision is a single branch:

	/*
	 * Now, we can block.  If the caller supplied a continuation
	 * pointer of his own for after the block, block with the
	 * appropriate semaphore continuation.  This will gather the
	 * semaphore results, release references on the semaphore(s),
	 * and then call the caller's continuation.
	 */
	if (caller_cont) {
		self->sth_continuation = caller_cont;
		self->sth_waitsemaphore = wait_semaphore;
		self->sth_signalsemaphore = signal_semaphore;

		thread_handoff_parameter(handoff_thread, semaphore_wait_continue,
		    NULL, handoff_option);
	} else {
		wait_result = thread_handoff_deallocate(handoff_thread, handoff_option);
	}

	assert(self->handoff_thread == THREAD_NULL);
	return semaphore_convert_wait_result(wait_result);

The if branch is the interrupt model. Notice what it does first: it copies the caller's continuation and both semaphore references into the thread structure, because the stack those values currently sit on is about to be released. Those are exactly the sth_ fields that [semaphore_wait_continue] reads back out when the thread resumes. Control does not return from thread_handoff_parameter, so the return at the bottom is never reached on this path.

The else branch is the process model. The thread keeps its stack, wait_result is assigned from the blocking call, and execution falls through to the return.

Both paths end at the same place, [semaphore_convert_wait_result], which turns the wait result into the status the caller receives:

wait_result_t	becomes
THREAD_AWAKENED	KERN_SUCCESS
THREAD_TIMED_OUT	KERN_OPERATION_TIMED_OUT
THREAD_INTERRUPTED	KERN_ABORTED
THREAD_RESTART	KERN_TERMINATED

One mapping, reached either by return value or by argument. [semaphore_wait]--described in its own comment as the "traditional (non-continuation) interface"--passes SEMAPHORE_CONT_NULL and so always takes the else path.

Where the Stack Is Reclaimed

All of the above only pays off if the stack is handed back, so it is worth seeing where that happens. The path from a blocking call to the release runs as follows:

        +---------------------------------------------+
        | thread_block(continuation)                  |
        +---------------------------------------------+
                               |
                               v
        +---------------------------------------------+
        | thread_block_reason()                       |
        |   self->continuation = continuation;        | <-- resume point is recorded
        |   self->parameter    = parameter;           |
        +---------------------------------------------+
                               |
                               v
        +---------------------------------------------+
        | do {                                        |
        |   thread_lock(self);                        |
        |   thread_select(...);                       | <-- picks the next thread
        |   thread_unlock(self);                      |
        | } while (!thread_invoke(...));              |
        +---------------------------------------------+
                               |
                               v
        +---------------------------------------------+
        | thread_invoke()                             |
        |   context switch; the new thread is now     |
        |   running on the processor                  |
        +---------------------------------------------+
                               |
                               v
        +---------------------------------------------+
        | thread_dispatch(old, new)                   |
        |   if (old->continuation != NULL &&          |
        |       old->kernel_stack != 0)               |
        |     stack_free(old);                        | <-- the 16 KB is handed back
        +---------------------------------------------+

The release itself is performed by [thread_dispatch], which runs as part of switching away from a thread:

/*
 *	If blocked at a continuation, discard
 *	the stack.
 */
if (thread->continuation != NULL && thread->kernel_stack != 0) {
	stack_free(thread);
}

The test is exactly the condition described earlier: a non-NULL continuation means the thread recorded where to resume, so the stack holding its old position is no longer needed and stack_free reclaims it. Had the thread blocked with THREAD_CONTINUE_NULL, continuation would be NULL, the test would fail, and the stack would be kept.

The reader should also be aware that thread_block_reason forces a reschedule; a thread that blocks does not merely mark itself unrunnable, but gives up the processor immediately. Within that function we find the following loop:

do {
  thread_lock(self);
  new_thread = thread_select(self, processor, &reason);
  thread_unlock(self);
} while (!thread_invoke(self, new_thread, reason));

A replacement thread is selected, and thread_invoke switches to it. That is the path by which thread_dispatch is reached, and the reason the stack_free above refers to the thread being switched away from; its documentation states that the first argument is "the old thread that we have switched away from". The stack the blocking thread was using is therefore released on its way out, and can be handed to whichever thread runs next.

The thread_lock and thread_unlock calls guarding the selection are examined separately in Spinlocks and Thread Locking in XNU.

Processor Topology and Multiprocessing

CPU Topology: Cores, Dies, Sockets, and Packages

The term core has various meaning depending on the context. The word has older uses than the processor one; section 3.9 of [APUE] notes:

The term incore means in main memory. Back in the day, a computer's main memory was built out of ferrite core. This is where the phrase "core dump" comes from: the main memory image of a program is stored in a file on disk for diagnosis.

In regards to processors, a core refers to an individual processing unit within a computing system. On a uniprocessor system, there exists only one core which is responsible for processing the instructions. Parallel computing is not possible but concurrency strategies can be applied on such systems. In contrast, a multiprocessor system is one where multiple cores are present and various strategies can be used to achieve true parallelism. Core count is the convention used here, though it is not the only one in circulation.

Why uniprocessor and multiprocessor are ambiguous terms

Strictly, the term counts whole processors. Wikipedia: Multiprocessing opens with:

Multiprocessing (MP) is the use of two or more central processing units (CPUs) within one computer system.

This was unambiguous when it was coined, because a machine's chip count, processor count, and instruction-stream count were all the same number. Two processors meant two chips on a board, each executing one instruction at a time.

Two developments separated those counts. Multi-core packaging put several independent cores inside one microprocessor, so a machine holding a single chip could still execute several instruction streams at once. SMT then gave an individual core more than one schedulable context, though the contexts share that core's execution units; the technique was first researched by IBM in 1968 for the ACS-360 project and reached mainstream desktops with the 3.06 GHz Pentium 4 in 2002 (see Wikipedia: Simultaneous multithreading). A single-core package with SMT enabled is therefore a uniprocessor by chip count, while the operating system sees two processors to schedule on.

The same article concedes the result:

Many variants of this basic theme exist, and the definition of multiprocessing can vary with context, mostly as a function of how a processor is defined (multi-core processors (multiple cores) on one die, multiple dies in one chip carrier (package), multiple packages in one computer case (system unit), etc.).

Those are the levels the rest of this section walks through. XNU avoids the ambiguity by reporting both counts instead of one: hw.physicalcpu counts cores and hw.logicalcpu counts schedulable contexts, declared alongside their _max variants in [bsd/kern/kern_mib.c], with the ARM64 comments in [bsd/dev/arm64/sysctl.c] spelling out the mapping. Both are readable from a shell:

sysctl hw.physicalcpu hw.logicalcpu

The two agree on hardware without SMT, and hw.logicalcpu is the larger where SMT is present and enabled. It is the second number the scheduler cares about, which is why the figures later in this section label the thread level with flat CPU n numbering -- under SMT a core and a schedulable CPU are no longer the same thing.

A multi-core processor is a single microprocessor with two or more independent processing units, or cores. On the other hand, a multi-CPU system has two or more separate microprocessors, each occupying its own socket on the motherboard.

Hence, a multiprocessor system can be built either way: multiple physical CPU chips (a multi-CPU system), or a single chip with multiple cores (a multi-core system). The two are not exclusive -- a machine can have several sockets, each holding a multi-core chip.

When working in a multiprocessing environment, it is wise to define some terminologies to avoid ambiguity. There are still some edge cases that depart from the norm but generally speaking, a system contains one motherboard. Such motherboard includes one or more CPU Sockets (some other components being memory slots, non-volatile memory for system's firmware, and other vendor-specific motherboard specifications). Analogous to sockets being an endpoint in network programming, a CPU socket allows placement of a microprocessor, thereby providing connection with the Printed Circuit Board (PCB); the motherboard. The benefit of a CPU socket is to allow such connection without soldering. Do note that the microprocessor inserted in the CPU socket is sometimes referred to as CPU Package. Such CPU package contains one or more Die. A die is a block of semiconducting material on which a given functional circuit is fabricated, and it can host many types of circuits. As Wikipedia: Die (integrated circuit) states:

One common use case of an integrated circuit die is in the form of a central processing unit (CPU).

and it is up to the vendor to fabricate the die as per the specification. Core, which is an independent processing unit within a die, contains various internal units such as Arithmetic Logic Units (ALUs), Floating Point Units (FPUs), control logic and the like. One or more cores can be present in a die. A package may be built from a single die or from several. The figures below are drawn from an educational viewpoint rather than to industry specification.

The first case is the monolithic one, where a single die carries every core in the package:

System
|
+-- Motherboard
    |
    +-- Socket 0  (holds CPU Package "Processor 0")
        |
        +-- Die 0
            +-- Core 0
            |   +-- Thread 0 ....... CPU 0
            +-- Core 1
                +-- Thread 0 ....... CPU 1

The second splits the package across two dies, one carrying a performance core with SMT enabled and the other a single efficiency core without it:

System
|
+-- Motherboard
    |
    +-- Socket 0  (holds CPU Package "Processor 0")
        |
        +-- Die 0   performance core, SMT enabled
        |   +-- Core 0
        |       +-- Thread 0 ....... CPU 0
        |       +-- Thread 1 ....... CPU 1
        |
        +-- Die 1   efficiency core, no SMT
            +-- Core 0
                +-- Thread 0 ....... CPU 2

Thread here represents an execution context, and it is the level the operating system actually schedules on; the CPU n labels are the flat numbering by which it refers to them. Notice that the SMT core in the second figure presents two of them while every other core presents one. That ratio is what tools report as threads per core, and it is the subject of Simultaneous Multithreading and Hyper-Threading below.

Monolithic and chiplet designs

A monolithic processor places every functional block--cores, cache, memory controller, I/O--on one die. A chiplet design splits those blocks across several smaller dies, connected inside a single package over the package substrate or a silicon interposer.

Smaller dies are cheaper to produce, since a manufacturing defect spoils less silicon. Dies in one package also need not share a manufacturing process, so cores can use the newest node while blocks that gain little from it stay on an older and cheaper one. The trade-off is that communication between dies is slower and draws more power than wiring within a single die. Wikipedia: Chiplet covers this in more detail.

AMD's Zen processors (separate compute and I/O dies) and Intel's tile-based designs are the common examples, as is Apple's Ultra line, which joins two dies with a dedicated interconnect.

note

Neither topology above is drawn from a real product, and both omit a great deal: cache hierarchy, memory controllers, interconnects, and much else. They are meant only to fix the vocabulary--socket, package, die, core, thread--in a reader's mind.

Simultaneous Multithreading and Hyper-Threading

Before briefly describing about Simultaneous MultiThreading (SMT) and Intel's implemention of it; also known as Hyper-Threading Technology (HTT), let's first understand some basic concepts. A scalar processor is a class of computer processor which is able to process only one data item at a time. Based on Flynn's taxonomy, a scalar processor is classified as a Single Instruction, Single Data (SISD) processor. Another class of computer processor exists which operates on multiple data through a single instruction. Such processors--which are also known as Single Instruction, Multiple Data (SIMD)--are classified as vector processors.

The superscalar processor, which can be thought of as a mixture of scalar and vector processors, has instructions which operate on one data item, but such a processor contains multiple execution units which allow execution of more than one instruction during a clock cycle. An execution unit (E-unit or EU) is a part of a processing unit that performs the operations and calculations forwarded from the instruction unit (I-unit or IU). The sequence to process an instruction can be as simple as one mentioned below (classic RISC pipeline):

• Instruction Fetch (IF): Retrieve the instruction from memory.
• Instruction Decode (ID): Decode instruction to know the instruction class, opcodes, operands of the instruction.
• Execute (E): Execute the instruction.
• Memory Access (MA): Read or write back to main memory (for some instructions).
• Write Back (WB): Save the result back to register.

IU is responsible for handling the IF and ID steps of the pipeline, whereas EU is responsible for the rest of the pipeline steps. It should be noted that superscalar and pipeline are two different performance improvement techniques. Wikipedia: Superscalar processor contains the following paragraph:

The former (superscalar) executes multiple instructions in parallel by using multiple execution units, whereas the latter (pipeline) executes multiple instructions in the same execution unit in parallel by dividing the execution unit into different phases.

One might wonder how a single execution unit can execute multiple instructions in parallel. It is possible by virtue of many internal units within a single execution unit. Some of the internal units commonly found are (see Wikipedia: Central processing unit (Instruction-level parallelism)): load-store units, arithmetic-logic units, floating-point units, and address-generation units.

SMT is a technique used for improving the overall efficiency of superscalar CPUs with hardware multithreading. Two major implementations of multithreading are possible: SMT and temporal multithreading. The major difference: temporal multithreading limits a pipeline to one thread's instructions at a time. On SMT-based superscalar CPUs, instructions from more than one thread can be executed in any given pipeline stage at a time.

HTT is Intel's proprietary SMT implementation used to improve parallelization of computations performed on x86 microprocessors. For each processor core that is physically present, the operating system addresses two virtual (logical) cores and shares the workload between them when possible. Doing so allows concurrent scheduling of two processes per core.

Symmetric vs Asymmetric Multiprocessing

There are two popular strategies for a multiprocessing system: Symmetric Multi-Processing (SMP) and Asymmetric Multi-Processing (AMP or ASMP). On an SMP-based system, all cores are treated equally. Figure 2, which is an excerpt from Wikipedia: Symmetric multiprocessing, shows a high-level overview of a symmetric multiprocessor system. Typically, cores on an SMP-based system share components such as global memory (main memory), disks, I/O devices, and interrupt system. Notice that each processor has an associated cache, which is present to speed up the main memory data access and to also reduce the traffic on system bus.

Given that multiple processors share the same main memory, access to the main memory must be in serial order; serialization must take place. To mitigate such performance bottlenecks, newer memory designs such as NUMA are proposed, which allow each processor to contain its own dedicated memory bank. On NUMA-based architecture, access to local memory (e.g. a portion of the main memory) is significantly faster as compared to traditional SMP where the entire main memory is shared. It does come with its own drawback, though. In particular, access to non-local (or remote; portion of main memory which is not assigned to the processor) memory is expensive.

Figure 2: Symmetric Multiprocessor System

On the other hand, AMP-based systems do not treat all cores as the same. For example, a system could contain multiple cores but only one core is present to execute the instructions while other cores are present to handle I/O operations. Figure 3 (excerpt from Wikipedia: Asymmetric multiprocessing) shows a high-level architecture view of Asymmetric multiprocessing.

From the computing environment standpoint (see [INTEL_HVHCE]), SMP corresponds loosely to Homogeneous Computing, wherein all processing units are of the same type and have similar capabilities, and AMP to Heterogeneous Computing. Such a computing environment involves a system that comprises different processing units such as Central Processing Units (CPUs), Graphics Processing Units (GPUs), Field-Programmable Gate Arrays (FPGAs), or specialized accelerators.

Figure 3: Asymmetric Multiprocessor System

The correspondence is only loose, however, because the two describe independent things. Symmetric against asymmetric is a statement about how the processors relate to the operating system: whether a single OS image treats them as interchangeable peers, or assigns them fixed and unequal roles. Homogeneous against heterogeneous is a statement about whether the processing units are the same kind of unit at all. A system may sit in any of the four combinations:

	Homogeneous units	Heterogeneous units
Symmetric	Conventional multi-core CPU; identical cores, any thread anywhere	Performance and efficiency cores in one package, scheduled by one OS image
Asymmetric	Identical cores given unequal duties, such as one executing instructions while others handle I/O	Embedded SoC pairing an application processor with a DSP running its own firmware

The top-right cell is the one worth noting, since it is the machine most readers are using. A package with performance and efficiency cores is heterogeneous in composition, yet macOS schedules across all of those cores from a single OS image, which is symmetric multiprocessing. Recall from Mach Kernel Abstractions and XNU Internals that XNU exposes just the one processor set, pset0; the asymmetry of the cores is a property of the hardware rather than a division the scheduler is built around.

Spinlocks and Thread Locking in XNU

The thread_block_reason excerpt in Where the Stack Is Reclaimed opens with a call to thread_lock, which is worth following up on its own account. The primitives it rests on guard most of the kernel's data structures, and part of their behaviour only makes sense with the uniprocessor and multiprocessor distinction of the previous section in hand.

The functions thread_lock and thread_unlock are essentially macros that expand to functions (a function is a closed subroutine, whereas a macro is an open subroutine). These are defined as parameterized macros in [osfmk/kern/thread.h] as:

#define thread_lock(th)                 simple_lock(&(th)->sched_lock, &thread_lck_grp)
#define thread_unlock(th)               simple_unlock(&(th)->sched_lock)

Mach uses simple locks to protect most of the kernel data structures. There are three flavors of spinlocks: hw_lock (hw_lock_t [osfmk/kern/lock_types.h]), usimple (usimple_lock_t (i386) [osfmk/i386/simple_lock.h] and usimple_lock_t (arm) [osfmk/arm/simple_lock.h]), and simple (lck_spin_t (i386) [osfmk/i386/locks.h] and lck_spin_t (arm) [osfmk/arm/locks.h]). Only the last one is exported to loadable kernel extensions. Below is an excerpt from [MOSX_INTERNALS] (Section 9.18.2.1) that describes the spinlock behavior in uniprocessor and multiprocessor systems:

Moreover, the use of a spinlock is different on a multiprocessor system compared with a uniprocessor system. On the former, a thread could busy-wait on one processor while the holder of a spinlock uses the protected resources on another processor. On a uniprocessor, a tight loop--if not preempted--will spin forever, since the holder of the lock will never get a chance to run and free the task!

One of the reason for the implementation of usimple lock was to support true spin lock mechanism on uniprocessor system. On Spinlocks subsection of Synchronization Primitives Chapter, we notice that traditional simple locks--while disabling preemption--do not spin on uniprocessor systems. [MOSX_INTERNALS] mentions that simple lock "disappears" on a uniprocessor system. Furthermore, once a usimple lock is acquired, preemption is disabled, and is again re-enabled once the lock is released.

Architecture-dependent expansion of simple_lock

It also appears that simple_lock too is a macro... and it's architecture dependent. In ARM variant, the macro simple_lock is defined in [osfmk/arm/simple_lock.h] and we see that the macro conditionally expands based on whether or not the symbol LCK_GRP_USE_ARG is defined (and is not 0):

#define simple_lock_init(l, t)   arm_usimple_lock_init(l,t)

#if LCK_GRP_USE_ARG
#define simple_lock(l, grp)                  lck_spin_lock_grp(l, grp)
...
#else
#define simple_lock(l, grp)                  lck_spin_lock(l)
...
#endif /* LCK_GRP_USE_ARG */

#define simple_unlock(l)                lck_spin_unlock(l)

And the general macro can be found in [osfmk/kern/simple_lock.h] when the macro simple_lock_init is not defined:

/*
 * If we got to here and we still don't have simple_lock_init
 * defined, then we must either be outside the osfmk component,
 * running on a true SMP, or need debug.
 */
#if !defined(simple_lock_init)
#define simple_lock_init(l, t)               usimple_lock_init(l,t)
#define simple_lock(l, grp)                  usimple_lock(l, grp)
#define simple_unlock(l)                     usimple_unlock(l)
...
#endif /* !defined(simple_lock_init) */

The definition of usimple_lock (for i386) is defined in [osfmk/i386/locks_i386.c], and so is usimple_unlock defined in [osfmk/i386/locks_i386.c].

I should also mention that [osfmk/i386/locks_i386.c] also defines the functions: lck_spin_lock_grp and lck_spin_lock, but they internally call the function usimple_lock.

For the ARM variant, the function is defined in [osfmk/arm/locks_arm.c]. We see that it internally calls a function lck_spin_verify that is defined in the same file as:

#if DEVELOPMENT || DEBUG
...
static inline void
lck_spin_verify(lck_spin_t *lck)
{
    if (lck->type != LCK_SPIN_TYPE ||
        lck->lck_spin_data == LCK_SPIN_TAG_DESTROYED) {
        __lck_spin_invalid_panic(lck);
    }
}
#else /* DEVELOPMENT || DEBUG */
#define lck_spin_verify(lck)          ((void) 0)
#endif  /* DEVELOPMENT || DEBUG */

Whichever macro the architecture selects, the chain ends in the same place: a spinlock acquisition that disables preemption for as long as the lock is held. That is precisely the property the scheduler needs. In thread_block_reason, thread_lock and thread_unlock bracket the call to thread_select, and a thread reading and modifying scheduling state cannot afford to be preempted partway through.

Scheduling in Application Software

Writing application software becomes a hurdle when the system provides more than one processing unit. Even though it allows the execution of various threads in parallel, orchestrating them with historical languages such as C introduces challenges to the developer working on multicore platforms. Linux provides a system call for a program which allows the calling thread to determine the CPU it is intended to run: sched_setaffinity(2). The DESCRIPTION section of the manual states the functionality of the system call:

For example, by dedicating one CPU to a particular thread (i.e., setting the affinity mask of that thread to specify a single CPU, and setting the affinity mask of all other threads to exclude that CPU), it is possible to ensure maximum execution speed for that thread.

In this context, a CPU is briefly described in the EXAMPLES section:

We first employ lscpu(1) to determine that this (x86) system has two cores, each with two CPUs:

$ lscpu | egrep -i 'core.*:|socket';
Thread(s) per core:    2
Core(s) per socket:    2
Socket(s):             1

sched_setaffinity(2) EXAMPLES overview

The EXAMPLES section also lists a program which uses this system call. This simple program does the following:

1. Parses the arguments provided to the program. Three additional arguments are expected: parent-CPU, child-CPU, and number of loops.
2. Another process is created via fork(2).
3. Both parent and child processes appropriately sets their CPU affinity using sched_setaffinity(2).
4. Both parent and child processes calls getppid(2) for number-of-loops times.
5. Parent waits for the child to exit.

The test program is executed under time(1) utility. It uses the structure of times(2) system call; tms:

struct tms {
  clock_t tms_utime;  /* user time */
  clock_t tms_stime;  /* system time */
  clock_t tms_cutime; /* user time of children */
  clock_t tms_cstime; /* system time of children */
};

The time(1) utility--as per the manual--gives timing statistics in the form:

These statistics consist of (i) the elapsed real time between invocation and termination, (ii) the user CPU time (the sum of the tms_utime and tms_cutime values in a struct tms as returned by times(2)), and (iii) the system CPU time (the sum of the tms_stime and tms_cstime values in a struct tms as returned by times(2)).

Three cases are considered: both processes running on the same CPU; both processes running on different CPUs on the same core; and both processes running on different CPUs on different cores. The result is provided as follows:

$ time -p ./a.out 0 0 100000000;
real 14.75
user 3.02
sys 11.73
$ time -p ./a.out 0 1 100000000;
real 11.52
user 3.98
sys 19.06
$ time -p ./a.out 0 3 100000000;
real 7.89
user 3.29
sys 12.07

The elapsed real time between invocation and termination (real) is lowest on the last case--expected as different threads on different cores are being used. User time is reasonably low since the program is mostly calling the getppid(2) system call. Lastly, it also mentions the factors that affect the statistics:

the amount of real and CPU time consumed when running the program will depend on intra-core caching effects and whether the processes are using the same CPU.

Manually controlling threads is a relatively complex task. Further complexity is introduced when an attempt is made to write a program which utilizes different CPUs.

Apple was aware of this and introduced a new approach to programming in a multiprocessing environment: Grand Central Dispatch (GCD). This approach differs from the traditional procedural programming paradigm and introduces concepts such as Blocks which can be queued for execution. A comprehensive tutorial on GCD can be found on [swiftlang.github: Using Grand Central Dispatch on macOS].

References

[APUE] Stevens, W.R., & Rago. S.A. (2013). Advanced Programming in Unix Environment.

[MOS] Tanenbaum, A.S., & Bos H. (2014). Modern Operating Systems.

[MOSX_INTERNALS] Singh, A (2007). Mac OS X Internals: A Systems Approach.

[OS_INTERNALS] Levin, J (2016, 2017, 2019) MacOS and iOS Internals Trilogy. https://www.newosxbook.com/index.php

[INTEL_HVHCE] https://www.intel.com/content/www/us/en/docs/sycl/introduction/latest/01-homogeneous-vs-heterogeneous.html

[XNU_GIT] https://github.com/apple-oss-distributions/xnu

[Draves 91] http://staff.ustc.edu.cn/~bjhua/courses/ats/2014/ref/draves91continuations.pdf

Source references in this post are against XNU commit f6217f8 (xnu-12377.1.9).