C10: Operating systems, concurrency, and safe coordination

A. Prerequisites and observable goals#

Level: Degree core; advanced memory-model work requires further study.

B. The central question: who may access shared state, and when?#

An operating system manages execution, memory mappings, devices, and persistent resources while providing isolation and controlled sharing. A process supplies an execution context and virtual address space. Threads within a process ordinarily share its address space and resources while having their own execution state and call stacks. A separate stack is not a universal privacy barrier: a program can pass a pointer into it to another thread, which reintroduces lifetime and synchronization obligations.

Concurrency means multiple activities have overlapping lifetimes and may interleave. Parallelism means activities execute simultaneously on available hardware. A single-core event loop can be concurrent without executing two instructions simultaneously. A multicore program can execute in parallel and still spend much of its time waiting on a shared lock. More threads do not by themselves create more useful parallel work.

A system call requests an operating-system service through a defined boundary. It can block, fail, or return partial progress. A system call is not necessarily a process switch, and not every library function is a system call. Scheduling decides which runnable threads get execution time, with policies and fairness properties that vary. A mutex does not automatically promise first-in-first-out service or a hard maximum waiting time.

C. Memory and files are resources with observable failure modes#

Demand paging can populate or map memory when accessed. A page fault may be handled normally or report an invalid/prohibited access; it is not synonymous with a crash. File descriptors on POSIX-like systems and handles on Windows identify operating-system resources through platform-specific interfaces. Opening a file can fail; reading can reach end-of-file or return less than requested; writing and later persistence are not identical events.

A filesystem organizes names, metadata, and storage. Buffered writes, atomic namespace changes, and durable persistence are separate properties. A successful application-level write does not universally guarantee survival of immediate power loss under every filesystem and hardware configuration. Backups must be restored and checked, not merely created. C11 uses database backup APIs rather than pretending that copying one file from a live database always captures all its state. [OSTEP][SQL]

Interprocess communication can use pipes, sockets, shared memory, or platform facilities. A byte stream still needs framing. Shared memory still needs synchronization. Asynchronous I/O separates request submission from completion; it does not mean the operation has completed when submission returns. An event loop must avoid blocking work that prevents other completions from being processed. Backpressure prevents producers from creating work faster than consumers can safely retain it.

D. A race is not merely an occasional wrong answer#

Imagine two activities both reading a counter value 0, calculating 1, and storing 1. One increment is lost in this illustrative interleaving. In C++, concurrent conflicting non-atomic accesses without a suitable happens-before relationship constitute a data race and cause undefined behavior; the language does not limit the result to this particular lost-update trace. A program appearing to work during a stress test does not establish that the race is absent.

A mutex protects a shared invariant by allowing only one holder in a critical section. Every relevant access must follow the same protocol. Locking only writes while allowing unsynchronized reads does not generally solve the problem. RAII lock wrappers release the mutex on ordinary scope exit, including exceptions. Keep ownership and lock lifetime visible, and avoid calling unknown or long-running code while holding a lock unless the interface explicitly permits that risk.

An atomic operation provides indivisible access under the language memory model. A relaxed atomic counter is suitable for certain independent counting tasks, but relaxed ordering alone does not publish unrelated non-atomic data. In a simple one-producer/one-consumer publication pattern, the producer writes immutable payload then performs a release store to a flag; a consumer’s acquire load that observes that release establishes visibility of the preceding payload writes. Correctness still depends on the flag’s initial state, no conflicting later payload writes, and adequate object lifetime. volatile is not a replacement for this synchronization. [CPP]

E. Condition variables wait for a predicate, not a remembered notification#

A bounded queue needs producers to wait when full and consumers to wait when empty. A condition variable lets a waiting thread release the mutex and sleep, then reacquire the mutex before continuing. Wakeups can occur without the desired condition being true, and another thread can change the state before the awakened thread gets the lock. Therefore use a predicate loop or predicate overload, not a one-time if followed by an unchecked wait.

The queue’s predicates are “closed or nonempty” for consumers and “closed or not full” for producers. The shared state is protected by one mutex. Closing sets a persistent Boolean state and wakes both groups. New pushes fail after closure; existing items remain available for draining; popping a closed empty queue returns no item. A notification is only a prompt to check the state. The predicate is the durable truth the program reasons about.

Schematic coordination contract. The arrows do not imply simultaneous execution or fairness guarantees.

The owner’s shutdown sequence must stop or join producers, close the queue as appropriate, let consumers drain, and join all users before destroying the queue. Closing does not make it safe to destroy a mutex or condition variable that another thread is still using. The test uses joining threads and verifies exactly-once delivery of generated integer items.

F. Deadlock, ordering, and what tests can establish#

A deadlock can arise when thread A holds lock X and waits for Y while thread B holds Y and waits for X. A global lock order prevents that cycle when all users follow it. Acquiring multiple locks through an appropriate deadlock-avoiding utility is another option. Timeouts can detect lack of progress but do not automatically restore a consistent state. Priority inversion is different: a high-priority thread can wait for a resource held by a low-priority one, possibly delayed by medium-priority work. Real-time systems may need specialized protocols and schedulability analysis.

AddressSanitizer and UndefinedBehaviorSanitizer check selected runtime defects in executed paths; they are not a data-race proof. ThreadSanitizer is a different tool and was not part of the recorded runs. Stress tests, timeouts, invariants, code review, and formal reasoning provide different evidence. The queue’s safety argument comes from exclusive access to its state and well-defined ownership; its tests exercise useful schedules but do not prove fairness or absence of every possible hang in every environment.

G. Independent practice#

F foundation C standard course work T transfer S optional stretch L runnable lab or project. Attempt the complete set before opening its solutions.

H. Complete solutions: C10#

Compare the first step where your work differs. A corrected answer is not yet an independent success.

Open every solution

#pragma once
#include <condition_variable>
#include <cstddef>
#include <deque>
#include <mutex>
#include <optional>
#include <stdexcept>
#include <type_traits>
#include <utility>

// C10.05: close rejects new pushes but permits draining queued values.
// The owner must close and join all users before destroying this object.
template<class T> class BoundedQueue {
    static_assert(std::is_nothrow_move_constructible_v<T>);
    const std::size_t capacity_;
    std::deque<T> queue_;
    std::mutex mutex_;
    std::condition_variable readable_, writable_;
    bool closed_ = false;
public:
    explicit BoundedQueue(std::size_t capacity) : capacity_(capacity) {
        if (!capacity) throw std::invalid_argument("capacity must be positive");
    }
    BoundedQueue(const BoundedQueue&) = delete;
    BoundedQueue& operator=(const BoundedQueue&) = delete;
    bool push(T value) {
        std::unique_lock lock(mutex_);
        writable_.wait(lock, [&] { return closed_ || queue_.size() < capacity_; });
        if (closed_) return false;
        queue_.push_back(std::move(value));
        lock.unlock();
        readable_.notify_one();
        return true;
    }
    std::optional<T> pop() {
        std::unique_lock lock(mutex_);
        readable_.wait(lock, [&] { return closed_ || !queue_.empty(); });
        if (queue_.empty()) return std::nullopt;
        T value = std::move(queue_.front());
        queue_.pop_front();
        lock.unlock();
        writable_.notify_one();
        return value;
    }
    void close() {
        { std::lock_guard lock(mutex_); closed_ = true; }
        readable_.notify_all();
        writable_.notify_all();
    }
};

I. Retention and readiness#

Retrieve C03’s ownership lifetime and C06’s abstract queue contract. Advance when you can write the predicate for every wait, identify the synchronization protecting every shared field, and explain the shutdown sequence without relying on timing luck.