Back 2 BaseCS : OS : Mutual Exclusion

All way stop.

Whenever we have multiple threads in play, and shared objects between threads, we have a recipe to run into weird things. If you have had an opportunity to work on any kind of multi-threaded web applications, you know that even two consecutive lines of code are not guaranteed to give you the results you might expect!

Imagine this, you only have 8 tickets left for a concert. Every time someone buys a ticket, you need to decrease the number of tickets remaining.

class TicketCounter {
  private int m_curr;
  public TicketCounter(int numTickets) {
    m_curr = numTickets;
}

public int decrementTickets() {

  if(m_curr <= 0) { fail("Sold Out"); return -1;}

  int currentTickets = m_curr;  //what could go wrong?
  m_curr = currentTickets - 1;
  return m_curr;
}

If the concert turns out to be super popular, you might really have a big problem on your hands! Imagine 1000 people all try to buy the tickets at the same time. Think of each person’s request being executed on a thread. All of the threads will read the m_curr variable value to be ‘8’, decrement by 1, and return. You might sell a lot more tickets than you have!

Critical Sections

Some pieces of code are often referred to as ‘critical’ sections. These are sections of code that must be run by one thread at a time. The threads need to exercise a property called — mutual exclusion.

This means, if one thread is executing the critical section of a code, then all other threads are excluded from running it. This is often simply implemented by a ‘lock’. Before entering the critical section, a thread must ‘acquire’ the lock and ‘release’ it after exiting the section.

A relatable example of a ‘critical’ section is a single person restroom in a cafe. You really don’t want two threads (often referred to as ‘persons’ in real world) to execute inside this critical section at the same time. It can lead to very uncomfortable experiences, specially if the restroom faces everyone else (definitely NOT talking from personal experience!). In many such cafes, the cafe owners avoid this situation by having a ‘lock’ on the door of the restroom. The key is often kept on the counter. Any thread (aka person) who can ‘acquire’ the lock’s key, can enter the restroom (still better to check by knocking!). Once done, the key is ‘released’ back to the counter, where another thread can acquire it now!

Thread acquiring a lock. Courtesy: Microsoft AI.

A typical solution to this in the above code looks like below : Now only one thread can enter the critical section in the try{ } block.

class TicketCounter {
  private int m_curr;
  private Lock m_lock;

  public TicketCounter(int numTickets) {
    m_curr = numTickets;
    m_lock = new Lock();
}

public int decrementTickets() {
  m_lock.acquire(); // acquire lock before entering critical section
  try{ //critical section start
    if(m_curr <= 0) { fail("Sold Out"); return -1;} 
  
    int currentTickets = m_curr;  
    m_curr = currentTickets - 1;

    return m_curr; 
  }   //critical section end
  finally { m_lock.release(); } //release lock after exiting
}

Note, it’s important to make sure the same lock object is used by multiple threads for a given critical section. It’s best to avoid using the same object for multiple critical sections, unless you really need to coordinate between multiple critical sections!

Common concerns of locking algorithms

Locking algorithms are often judged by whether they can perform on providing the below characteristics -

1. Mutual exclusion — This is the most basic requirement from any locking algorithm. Execution of critical sections by two threads can not overlap.
2. No deadlocks — The locking algorithms should not deadlock in itself. If multiple threads try to acquire the lock, at least one should succeed. If a thread fails to get a lock, it can assume some other thread has the lock.
3. No starvation — Eventually, all threads trying to acquire lock will succeed. None of the threads should starve that it is effectively locked out. As you can probably feel, this property is highly desirable but nice to have, unlike the first two.
4. Fairness — This property goes beyond the starvation property. This defines a fair sequence in which the threads get to enter the critical section. One such implementation is First-come-First-serve (FCFS), but fairness can be quite subjective.

Lamport’s Bakery Algorithm — A sample lock implementation

The algorithm is named after a bakery’s “take-a-number” system where customers take a number and wait their turn based on the order of their numbers. Similarly, in the Bakery Algorithm, each thread takes a “number” when it wants to enter the critical section, and the thread with the smallest number gets to enter the critical section first.

When a thread wants to enter the critical section, it chooses a number that is greater than any number currently being used by other threads. If two threads try to acquire at the same time, the threadIds are used to resolve the conflict. After entering the ‘doorway’ section of the lock, the threads have their flags raised (i.e. it is waiting to enter).

The thread then waits until all other threads with smaller numbers or with the same number but a smaller ID have finished executing their critical sections. Once it determines, no thread with smaller number has it’s flag raised, it enters the critical section.

To exit, the number can’t just be reset, but rather it’s flag is reset (or lowered). This raises some interesting complications, like what happens when the numbers eventually overflow.

This algorithm is not actually used, but is a good example of how locks can be implemented. It provides mutual exclusion, as only one thread can enter the critical section. As the smallest thread number enters, it is deadlock free and starvation free. Additionally, the FCFS ordering by using increasing numbers provides fairness.

Quick Note: These concerns are applicable in many other scenarios, where shared and constrained resources need to be access by a lot of demanders. Think, distributing gasoline in a hurricane hit area. You need to make sure it is distributed fairly. Think about the ‘All way Stop’, which makes all cars to stop and proceed one-by-one when entering the critical (inter)section. It’s everywhere!

In computers, think scheduling of processes to CPUs, you need to make sure none of the process is starved of CPU time. These concepts are important to keep in mind, when contemplating about various business logic problems you might encounter.

In coming days and months, we will dig deeper into each of the OS components and learn concepts and implementations. If you are interested to learn these and up-level your computer engineering skills, please consider subscribing to this newsletter.

If you loved this piece, please consider leaving a small tip to keep me motivated! Your support means a lot!