Synchronization invariants

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

Run queue invariants

• A CPU’s run queue is implemented by members in cpustate and proc: cpustate::current_, cpustate::runq_, proc::runq_links_, and proc::runq_cpu_.

• 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().)

• A proc may be on at most one CPU’s run queue at a time.

• cpustate::current_ holds the currently-running kernel task on a CPU.

  1. c->current_ is protected by c->runq_lock_.
  2. c->current_ may only be modified by c->schedule(), the cpustate::schedule() function for that same CPU.
  3. 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 the relevant locks.

• cpustate::runq_ and proc::runq_links_ form the linked list of runnable tasks. These members are protected by c->runq_lock_. cpustate::enqueue() modifies these members after acquiring that lock.

• proc::runq_cpu_ is the index of the CPU on which a proc should be scheduled. It is initialized the first time cpustate::enqueue is called for that proc. In Chickadee handout code, proc::runq_cpu_ never changes after initialization.

  • proc::unblock() uses proc::runq_cpu_ to find a task’s home CPU. It reads runq_cpu_ before acquiring any lock (it in fact uses runq_cpu_ 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

• 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 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).

• The proc::regs_ member can’t be accessed by kernel code, except:

  • A running kernel task may set and modify its own proc::regs_ if interrupts are disabled and remain disabled until the next call to 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.

  • The proc::resume() function may access and clear proc::regs_.

• The proc::yields_ member can’t be accessed by kernel code, except:

  • A running kernel task may set and modify its own proc::yields_ if interrupts are disabled and remain disabled until the next call to proc::yield_noreturn(). (The proc::yield() function does this.)

  • The proc::resume() function may access and clear proc::yields_.

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

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

• The proc::yield_noreturn() function must be called with no spinlocks held and with interrupts disabled.

Scheduling invariants

• The cpustate::schedule() function must be called with no spinlocks held and with interrupts disabled.

• The cpustate::schedule() function must be called from the current CPU’s CPU stack. (The proc::yield_noreturn() function switches to that stack.)

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

  Note that for user threads, 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.

Process state invariants

• proc::pstate_ indicates whether a task is runnable. In the handout code, proc::ps_runnable represents 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.

• Many contexts, including the memviewer and cpustate::schedule(), may examine the proc::pstate_ member for any proc, to see whether that proc is runnable, faulted, or otherwise. This member has type std::atomic<int> to prevent undefined behavior.

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

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

  • A kernel task p may change its own p->pstate_ from proc::ps_runnable to any other value, such as proc::ps_blocked.

  proc::unblock(), which changes from proc::ps_blocked to proc::ps_runnable, uses an atomic compare-and-swap operation. This is because the task itself might be running on another CPU, and changing p->pstate_ to another value, such as proc::ps_faulted. In such cases, the task’s own choice of state should win; proc::unblock() only transitions from blocked to runnable.

  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 until some condition holds. Generally, a call to proc::yield() or proc::yield_noreturn() quickly follows the change of pstate_.

  A task may change its pstate_ while interrupts are enabled, but this requires care. When a task’s state is non-runnable at interrupt time, the proc::exception handler will not return to that task after handling the interrupt; rather, cpustate::schedule will choose another task to run. 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_.

  If you introduce new states, you can introduce new rules for those states. For instance, our handling of exit involves new states, and some state transitions are performed by contexts other than the proc itself.

  Note that a task may be unblocked without knowing which wait queues it is on, if any. (For instance, a process might be interrupted by a signal.) Thus, your wait queue implementation must handle tasks that unblock without being removed from the corresponding wait queue.

• A task may be resumed only if the associated pstate_ is proc::ps_runnable. 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

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

Page table invariants

• 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().