Synchronization invariants

This page lists synchronization invariants that hold in Chickadee. See also spinlocks.

Run queue invariants

• RQI1. A CPU’s run queue is implemented by members in cpustate and proc:

  1. cpustate::current_, the kernel task currently running on a CPU.
  2. cpustate::runq_, the head of the linked list of tasks waiting to run on a CPU.
  3. proc::runq_links_, the links used to connect cpustate::runq_.
  4. proc::runq_cpu_, the index of the CPU on which a task should run.
  5. cpustate::runq_lock_, a per-CPU spinlock.

• RQI2. A proc* p is on the run queue for CPU c if:

  1. p is part of the linked list headed at c->runq_, or
  2. p is running on CPU c.

  Normally a single proc is either running or scheduled, but a process may be both running and scheduled simultaneously. (So it is possible that p == c->current_ && p->runq_links_.linked().)

• RQI3. A proc may be on at most one CPU’s run queue at a time. This CPU is called its home CPU. proc::runq_cpu_ is the index of the home CPU.

• RQI4. cpustate::current_ holds the currently-running kernel task on a CPU. c->current_ may only be modified by c->schedule(), the cpustate::schedule() function for that same CPU, while it holds c->runq_lock_.

  • RQI4a. Because modifications to c->current_ are limited, a kernel task may safely examine %gs:(8), which holds c->current_ for the CPU currently running that task. (The kernel task is running on CPU c, so c->schedule() is not, guaranteeing that c->current_ will not be written concurrently.) However, kernel tasks must not examine other CPUs’ current_ members without acquiring the relevant runq_lock_s.

• RQI5. cpustate::runq_ and proc::runq_links_ form the linked list of runnable tasks.

  1. RQI5a. To add a new proc* p to CPU c’s run queue, call c->enqueue(p). This checks that p has never been scheduled before. It also sets p->runq_cpu_ = c->cpuindex_, marking c as p’s home CPU.

  2. RQI5b. To reschedule a proc* p on its home CPU’s run queue, call c->reenqueue(p). This checks, among other things, that p->runq_cpu_ == c->cpuindex_.

  3. RQI5c. c->runq_lock_ protects c->runq_ and every runq_links_ associated with that CPU. Both cpustate::enqueue() and cpustate::reenqueue() acquire c->runq_lock_.

• RQI6. In Chickadee handout code, proc::runq_cpu_ never changes after it is initialized by cpustate::enqueue(). proc::unblock() uses proc::runq_cpu_ to find a task’s home CPU; it must reads runq_cpu_ before acquiring any lock (because runq_cpu_ is needed to find the relevant cpustate::runq_lock_ to lock). When an object is accessed from multiple CPUs without locks, the First Law of Synchronization says all such accesses must be reads. Enabling process migration among CPUs would require modifying proc::runq_cpu_, and therefore additional synchronization objects to protect accesses to it.

Suspension invariants

• SUI1. The proc::regs_ and proc::yields_ members are used to store resumption state. At most one of these members can be nonnull at a time. A proc with nonnull regs_ or yields_ is called resumable.

• SUI2. A nonnull proc::regs_ or proc::yields_ must point into the kernel task stack containing the proc (so their address must be on the same memory page as the proc).

• SUI3. The proc::regs_ member may be accessed only in one of the following ways:

  • A running kernel task may modify its proc::regs_ if interrupts are disabled and remain disabled until the next call to cpustate::schedule() via proc::yield_noreturn().

  • After proc::init_user() is called, the new proc has a nonnull proc::regs_ pointer. It is safe to access that member and modify its contents, but only up to the point that the new proc is scheduled by cpustate::enqueue() [RQI5a].

  • The cpustate::schedule() function may access and clear proc::regs_ by calling proc::resume().

• SUI4. The proc::yields_ member may be accessed only in one of the following ways:

  • A running kernel task may modify its proc::yields_ (as proc::yield() does) if interrupts are disabled and remain disabled until the next call to cpustate::schedule() via proc::yield_noreturn().

  • The cpustate::schedule() function may access and clear proc::yields_ by calling proc::resume().

• SUI5. The proc::resume() function can only be called by cpustate::schedule().

• SUI6. The proc::yield() function must be called with no spinlocks held.

• SUI7. The proc::yield_noreturn() function must be called with no spinlocks held and with interrupts disabled. Furthermore, its proc must be either resumable or non-runnable.

Scheduling invariants

• SCI1. The cpustate::schedule() function must be called on the current CPU’s CPU stack, with no spinlocks held, and with interrupts disabled. (The proc::yield_noreturn() function switches to the CPU stack.)

• SCI2. A task (that is, a proc) can run on at most one CPU at a time.

  For user tasks, the “task” encompasses both privileged and unprivileged modes of execution: it is illegal for CPU 0 to execute a particular thread in unprivileged mode while CPU 1 executes on the corresponding kernel task stack in privileged mode. This is because the unprivileged code could trap at any time, which would cause two CPUs to simultaneously execute the same kernel task.

• SCI3. A CPU should not run in kernel mode with interrupts disabled indefinitely. To prevent yielding processes from blocking out interrupts, proc::yield() may enable interrupts for a single instruction before transferring control to cpustate::schedule().

  Note that proc::yield_noreturn() does not enable interrupts in the same way. This is because proc::yield_noreturn() may be called on a resumable task [SUI7]; and if a resumable task is executing on a CPU, the relevant CPU must have interrupts disabled until cpustate::schedule is called [SUI3, SUI4].

Process state invariants

• PSI1. proc::pstate_ indicates a task’s status. A task with pstate_ == proc::ps_runnable is called runnable; the handout scheduler only resumes runnable tasks. The value proc::ps_blocked is used for tasks that may run in the future, but are currently blocked. You may add other values.

• PSI2. proc::pstate_ has atomic type, so it may be examined at any time without causing undefined behavior. Many contexts, including the memviewer and cpustate::schedule(), examine proc::pstate_.

• PSI3. proc::pstate_ may be changed to and from proc::ps_runnable in the following ways.

  • A kernel task may change its own pstate_ to any value.

  • Any context may change any task’s p->pstate_ from proc::ps_blocked to proc::ps_runnable by calling p->unblock().

  proc::unblock() uses an atomic compare-exchange operation. This is because the task itself might be running on another CPU and in the process of changing p->pstate_ to another value, such as proc::ps_faulted. In such cases, the task’s own choice of state should win.

  A task marks itself as non-runnable (that is, changes p->pstate_ from proc::ps_runnable to proc::ps_blocked, or another value) as it prepares to block. Generally, a call to proc::yield() or proc::yield_noreturn() quickly follows the change of pstate_.

• PSI4. A task may change its pstate_ while interrupts are enabled, but this requires care. If a task is non-runnable when an interrupt occurs, then the task will not be resumed after the interrupt. Thus, a task preparing to block must place itself on a wait queue, or otherwise make itself available for later waking, either (1) while interrupts are disabled, or (2) before changing its pstate_.

• PSI5. You may introduce more states; for instance, our handling of exit involves new states and state transitions. But be careful! A kernel context should change a different task’s state only by calling its proc::unblock(). Other state transitions—for instance, changing another task’s state from proc::ps_runnable to proc::ps_blocked—are very difficult to get right. To manage such transitions, consider introducing other proc member variables (with their own synchronization invariants) that signal a kernel task should change its own state.

• PSI6. Tasks are generally unblocked via wait queues and wait_queue::notify_all(). However, a task may be unblocked directly, even if it is enqueued on some wait queue, by calling p->unblock(). This makes the task runnable without changing its wait queue status. Your wait queue implementation must handle such tasks.

• PSI7. Only runnable tasks may be resumed. A task that is not runnable must not be resumed. (The proc::resume() method resumes a task by loading either its yieldstate or its regstate. After proc::resume(), either the kernel task starts running on its kernel task stack, or the corresponding user context starts running on its stack. proc::resume() is called in exactly one place in the kernel, namely cpustate::schedule().)

  • A task that is actively running may have a pstate_ other than proc::ps_runnable. This happens, for example, when a process takes a page fault, or as a kernel task decides whether or not to block. However, cpustate::schedule() must not resume any task whose pstate_ does not equal proc::ps_runnable.

  Here’s why the handout code obeys this invariant.

  1. While cpustate::schedule() chooses a task to resume, it holds its runq_lock_. This protects tasks in its run queue from being removed from its queue or rescheduled on other CPUs.

  2. cpustate::schedule() chooses a task with p->pstate_ == proc::ps_runnable. Since this task is on the current CPU’s run queue, which is locked, we know the task is not currently running on any other CPU. It is not running on this CPU either (because cpustate::schedule() is running). Therefore, p is not running anywhere. Only p itself can change p->pstate_ from proc::ps_runnable, so we know p->pstate_ will remain proc::ps_runnable until the runq_lock_ is released.

  3. cpustate::schedule() releases its runq_lock_ before resuming the chosen process. However, it sets cpustate::current_ to the chosen process before releasing the lock. This prevents any other CPU from running p, and ensures that p->pstate_ will not change until after p is resumed.

Process table invariants

• PTABLEI1. Read or write access to the process table ptable requires the ptable_lock spinlock.

Page table invariants

• PGI1. You may free a process’s page table pages only if (1) the process is not present in ptable, or (2) the process’s page table lock is locked for writing (forcing proc::lock_pagetable_read() to spin).

  Note that in our handout code, proc::lock_pagetable_read() does nothing. We provide it as a hook for you to complete, in case you want to implement finer-grained page table management.

Buffer cache invariants (Pset 4)

The buffer cache, bufcache, comprises a set of slots. The bufcache has a lock, lock_. Each slot has type bcslot, and contains a state state_, a lock lock_, a disk block number bn_, a reference count ref_, a write owner write_owner_ (initially nullptr), and a pointer to the cached data buf_. These data structures have nontrivial synchronization invariants because disks are slow, making fine-grained synchronization important for performance. As always, you can change these invariants, but understand the current invariants first.

• The bcslot::ref_ and bcslot::state_ members are atomic and can be read without locks.

• Changing a bcslot::state_ member requires the slot’s bcslot::lock_.

• Allocating a slot requires both the global buffer cache lock, bufcache::lock_, and the relevant slot’s lock_.

  • Thus, if a task holds bufcache::lock_, it can be sure that no other task will cause a slot to transition from ref_ == 0 to ref_ > 0.

• Dereferencing a slot (--slot->ref_) can happen at any time and requires no locks.

• Loaded slots have read-only bcslot::bn_ and bcslot::buf_ members. If a slot is referenced, its bn_ and buf_ can be read without locking.

  • Once a slot has been allocated, its bn_ does not change.

  • Once a slot is loaded, its buf_ does not change.

  • All nonempty slots have distinct bn_s.

  • All loaded slots have distinct, nonnull buf_s, because each block is cached in different memory.

  • Allocating or freeing a slot may change its bn_ and buf_. These operations require the slot’s lock_, and require that ref_ == 0.

• bufcache::lock_ precedes all bcslot::lock_s in the lock order. For example, the bufcache::load function initially acquires the bufcache::lock_, then acquires a slot’s bcslot::lock_ and releases the global bufcache::lock_.

• The bufcache::load function, which is the only way to obtain a new slot reference, yields until the relevant slot is fully loaded. Thus, if a kernel task holds a slot reference, that slot has buf_ != nullptr and state_ == s_clean or s_dirty.

• The contents of a bcslot::buf_ are protected by write_owner_, which is a mutual-exclusion lock implemented by bcslot::lock_buffer() and bcslot::unlock_buffer().