CST334 - Week 5

Week 5 Reflection

    In this week, I learned a great deal about concurrency, threads, and best practices on how to keep threads managed efficiently. A thread is seen as a process that can share the same address space as another thread, and access the same data, rather than needing to occupy a different address space. Multi-threading is handling multiple threads in the same address space using thread control blocks (TCBs) to store thread states. For multi-threaded processes, each thread has its own stack, called the thread-local storage. 

    In the aside, four key terms are highlighted: 

• critical section: Code that accesses a shared resource, like a data structure or variable. 
• race condition (aka data race): If multiple threads enter the critical section at the same time, a race condition occurs. These threads could be executed in any order, leading to the program becoming indeterminate.
• indeterminate program: A program with one or more race conditions that creates outcomes that are not deterministic, like what we previously handled in class.
• mutual exclusion: A property of code that only allows one thread to be accessing the critical section at a time, preventing race conditions.

    To manage threads efficiently, lock variables are put in place to prevent multiple threads from entering the critical section at the same time. Locks are "unlocked" when available/free, or "locked" when acquired/held. Locks can be coarse-grained, which locks an entire critical section (lower concurrency), or fine-grained, which makes use of different locks for different data/data structures (higher concurrency). For locks, we look for correctness (mutual exclusion), fairness (do waiting threads ever starve?), and performance (costs of using a lock).

    The test-and-set (aka atomic exchange) instruction stores a value from a pointer, then stores a new value in that pointer, then returns the old value. This is also thought of as the mechanism for a spin lock, which makes use of a while loop and a test-and-set setup. For spin locks they are correct, but unfair and wasteful in single-CPU scenarios, but decently efficient in multiple-CPU setups where the number of threads is about the same as the number of CPUs.

    The compare-and-swap (compare-and-exchange) instruction tests if a value pointed to is equal to an expected value - if so, it updates the value with the expected value, if not, it does nothing. The instruction returns the pointed value to determine whether the compare-and-swap succeeded.

    The load-linked and store-conditional instructions work together to create a lock. The load-linked (LL) instruction uses a passed-in value and returns it in a register. A store-conditional (SC) instruction updates only if the address has not been updated yet (returning 1). If so, it does nothing, returning 0.

    The fetch-and-add instruction stores an old value much like test-and-set, increments the pointer's value, and then returns the unchanged old value. 

    Ticket locks create a ticket system, where a lock is given a turn (lock->turn), and eventually gives each thread a turn in the critical section. This ensures fairness for locks, and prevents threads from starving.

    To prevent threads from spinning indefinitely, we can implement a yield instead of a spin to allow a different thread to enter the critical section. In other words, move a thread from running to ready, aka descheduling itself. This can still lead to endless yielding, causing other threads to be starved (unfair).

     A two-phase lock can mitigate some of these issues by first trying to spin to acquire the lock (first phase) then if unsuccessful, the caller sleeps and only wakes up once the lock becomes free in the future.

    I actually had an easier time understanding how threads work! I play a few factory automation video games like Satisfactory, Factorio, and Shapez and the concepts they work on is very similar to threads (unsurprising, since after a certain building point they are simulating a motherboard-like structure).

Isopod Update: I had to redo the red pak chongs' terrarium because the number of dwarf whites in it were far outnumbering the original colony. They are a pain to deal with, and unfortunately my troglodillo sp. terrarium also has this same problem. I'll have to redo their enclosure at some point too.