COMP35112 - More about Locks

class: center, middle
background-image: url(include/title-background.svg)
# COMP35112 Chip Multiprocessors
<br/>
<br/>
# .white[More about Locks]

.white[Pierre Olivier]

???
- Hello everyone
- So we have seen previously that locks are practical to protect critical sections
- However they are not without dangers
- This is what we will cover in this lecture, as well as a few additional info about locks

---
class: center, middle, inverse
# Dangers with Locks

???

- Let's start with a few issues we can get when using locks

---
# Dangers with Locks

???

- One of the common issues with lock is the deadlock
- This is when, due to improper use of locks, your program is stuck waiting
  indefinitely, trying to take a lock it will never acquire
- This is illustrated on the picture
- If you look at the center part
- White truck is stuck because white car can't move
- White car can't move because gray car is stuck
- And gray car is stuck because white truck can't move

---
# Dangers with Locks

```c
typedef struct {
    double balance;
    pthread_mutex_t lock;
} account;

void initialise_account(account *a, double balance) {
    a->balance = balance;
    pthread_mutex_init(&a->lock, NULL);  // return value checks omitted for brevity
}

void transfer(account *from, account *to, double amount) {
    if(from == to) return;  // can't take a standard lock twice, avoid account transfer to self

pthread_mutex_lock(&from->lock);
    pthread_mutex_lock(&to->lock);

if(from->balance >= amount) {
        from->balance -= amount;
        to->balance += amount;
    }

pthread_mutex_unlock(&to->lock);
    pthread_mutex_unlock(&from->lock);
}
```
.codelink[<a href="src/deadlock.c" download>`09-more-about-locks/deadlock.c`</a> <a href="https://github.com/olivierpierre/comp35112-devcontainer" target="_blank" style="text-decoration: none"><img src="include/gh-logo.svg" style="height: 1em" ></a><a href="https://www.programiz.com/online-compiler/3HdPzd4QWLZ0a" target="_blank" style="text-decoration: none"><img src="include/programiz-logo.png" style="height: 1em"></a>]

???
- As soon as your code uses more than one lock it opens the possibility for
deadlocks if the lock/unlock operations are not made in the proper way
- Let's take an example
- We have a data structure representing a bank account, with a balance, and an
  associated lock protecting the balance from concurrent access
- We have a simple init function that sets a starting balance in the account
  and initialises the lock
- We also have a function, transfer, that moves a given amount of money from
  one account to another
- transfer is supposed to be called from multithreaded code. So we use the
  locks relative to each account.
- We first check that from and to aren't the same account, because a standard
  lock can't be taken twice, that'll result in undefined behaviour
- Next we first lock the from account, then lock the to account,
  we perform the transaction is there is enough money,
  then release the locks in order
- Everything seems fine right? let's try it out

---
# Dangers with Locks

.leftcol[
```c
void transfer(account *from, account *to,
        double amount) {
    if(from == to) return;

pthread_mutex_lock(&from->lock);
    pthread_mutex_lock(&to->lock);

if(from->balance >= amount) {
        from->balance -= amount;
        to->balance += amount;
    }

pthread_mutex_unlock(&to->lock);
    pthread_mutex_unlock(&from->lock);
}
```
]

.rightcol[
<div style="text-align:center"><img src="include/deadlock.svg" width=500 /></div>
]

???

- So what happened?
- Here's a scenario that leads to a deadlock
- We have two threads calling the transfer method at the same time
- Thread 1 calls transfer from account a to account b and the other thread
  from b to a
- Let's assume that thread 1 gets a's lock first, then it tries to get b's lock
- But in the meantime thread 2 took b's lock and is now trying to lock a
- No thread can continue and the system is stuck, it's a deadlock

---
# Dangers with Locks

```c
typedef struct {
    int id;              // unique integer id, used to sort accounts
    double balance;
    pthread_mutex_t lock;
} account;

void transfer(account *from, account *to, double amount) {
    if(from == to) return;
    pthread_mutex_t *lock1 = &from->lock, *lock2 = &to->lock;

if(from->id < to->id) {   // always lock the accounts in the same order
        lock1 = &to->lock;
        lock2 = &from->lock;
    }

pthread_mutex_lock(lock1);
    pthread_mutex_lock(lock2);
    if(from->balance >= amount) {
        from->balance -= amount;
        to->balance += amount;
    }
    pthread_mutex_unlock(lock2);
    pthread_mutex_unlock(lock1);
}
```
.codelink[<a href="src/deadlock-fixed.c" download>`09-more-about-locks/deadlock-fixed.c`</a> <a href="https://github.com/olivierpierre/comp35112-devcontainer" target="_blank" style="text-decoration: none"><img src="include/gh-logo.svg" style="height: 1em" ></a><a href="https://www.programiz.com/online-compiler/3EGvhGn1Dk5ND" target="_blank" style="text-decoration: none"><img src="include/programiz-logo.png" style="height: 1em"></a>]

???
- So what is the solution to this problem?
- One possible solution is to give each account a unique identifier that can
  be used to establish an ordering relationship between accounts
- And we use this to sort the objects to lock so that, when given 2 accounts,
  all threads will always lock them in the same order, avoiding the deadlock
- In this example we use a simple unique integer id for each account
- In the transfer function we use the id to sort the accounts
- Establishing such an ordering allows us to always take the locks in the same
  order, so when a thread calls transfer from a to b while another calls
  transfer from b to a, both will lock the accounts in the same order and only
  one can obtain both locks at once

---
name:lost-wakeup
# Dangers with Locks
- **Lost wakeup** issue
  - Example with `bounded_buffer` code from last lecture

???
- Another issue with synchronisation is the "lost wakeup"
- It happens when the programmer mistakenly uses conditions
- Let's take an example with the bounded buffer code from last lecture
- Something that can happen is the following scenario

---
template:lost-wakeup
<div style="text-align:center"><img src="include/lost-wakeup-1.svg" width=300 /></div>

???

- Assume we have an empty queue and 4 threads

---
template:lost-wakeup
<div style="text-align:center"><img src="include/lost-wakeup-2.svg" width=300 /></div>

???
- Thread A tries to extract something from the empty queue and waits
- Thread B tries the same, and waits

---
template:lost-wakeup
<div style="text-align:center"><img src="include/lost-wakeup-3.svg" width=300 /></div>

???
- Next thread C deposits something in the empty queue, so it signals a waiting
  thread
- Let's assume it's thread A

---
template:lost-wakeup
<div style="text-align:center"><img src="include/lost-wakeup-4.svg" width=300 /></div>

???
- Let's assume that at the same time thread D also deposits in the queue, which
  is non empty, so there is no need to signal

---
template:lost-wakeup
<div style="text-align:center"><img src="include/lost-wakeup-5.svg" width=300 /></div>

???

- A wakes up, and extracts an element from the queue

---
template:lost-wakeup
<div style="text-align:center"><img src="include/lost-wakeup-6.svg" width=300 /></div>

???
- In the end, B is never awoken, even though the queue is not empty!

---
template:lost-wakeup

- Fix (here) would be to use `pthread_cond_broadcast()` instead of `pthread_cond_signal()`
  - Wake up **all** threads (vs. a single thread) waiting on a condition variable

???

- In this scenario, the fix would be to use the `pthread_cond_broadcast()`
  function when someone deposits in an empty queue, rather than
  `pthread_cond_signal()`
- That would ensure to wakeup all the waiting threads

---
class: center, middle, inverse

# Misc. Information about Locks

???

- Now let's briefly see a few miscellaneous topics regarding locks

---
# Granularity

- How big a chunk of code which depends on obtaining a lock should you write?
  - **Coarse-** vs. **fine-** grained

.leftcol[
```c
/* Coarse-grained locking: */

lock();

/* access a mix of shared and unshared data */

unlock();

```
]

.rightcol[
```c
/* Fine-grained locking: */

lock();
/* access shared data */
unlock();
/* access non-shared data */
lock();
/* access shared data */
unlock();
```
]

???
- The granularity of locking defines how big are the chucks of code that you
  protect with a single lock
- it is an important design choice when developing a parallel program
- Large blocks of code protected by locks generally access a mix of shared and
  non shared data
- We talk about **coarse-grained** locking
- Because locking serialise the protected code it limits parallelism
- On the other hand you can have many lock operations each protecting small
  quantities of code:
- This is **fine-grained** locking
- It increases parallelism
- However it may lead to a high overhead from obtaining and releasing many locks
- The program is also harder to write
- So it really is a trade-off
- For example we could lock a whole array to allow updates to some element(s),
  or we could lock only the individual element(s) being changed

---
# Reentrant Lock

- By default, a thread locking a lock it already holds results in **undefined
  behaviour**

.leftcol[
```c
void transfer(account *from, account *to,
    double amount) {
  /* no check if from == to */

// BUGGY when from == to if lock is
  // not reentrant
  pthread_mutex_lock(from->lock);
  pthread_mutex_lock(to->lock);

if(from->balance >= amount) {
    from->balance -= amount;
    to->balance += amount;
  }
  /* ... */
}
```
]

.rightcol[
```c
int main(int argc, char **argv) {
  account account1;
  pthread_t t1;

initialize_account(&account1, 1, INIT_MONEY);

/* transfer from account1 to account1 */
  worker w1 = {&account1, &account1,
    ITERATIONS};

pthread_create(&t1, NULL, thread_fn,
    (void *)&w1);
  pthread_join(t1, NULL);

return 0;
}
```
.codelink[<a href="src/non-reentrant.c" download>`09-more-about-locks/non-reentrant.c`</a> <a href="https://github.com/olivierpierre/comp35112-devcontainer" target="_blank" style="text-decoration: none"><img src="include/gh-logo.svg" style="height: 1em" ></a><a href="https://www.programiz.com/online-compiler/1ABe5BFVksWBh" target="_blank" style="text-decoration: none"><img src="include/programiz-logo.png" style="height: 1em"></a>]
]

???

- We can also talk about a special type of locks, reentrant locks
- To understand let's first see what happens when a thread tries to take a
  standard lock twice in a nested fashion
- Let's assume the transfer function does not check if to and from are the
  same account
- Assuming the thread calls transfer with the same account by pointed by the
  from and to parameters
- It will then take the account's lock once, then attempt to take it a second
  time while already holding it
- On a standard lock this results in undefined behaviour, it's a bug
- We can try it out

---
# Reentrant Lock

- A **reentrant** lock can be taken by a thread that already holds it
  - Avoid a thread deadlocking with itself

```c
// Version of the bank account program that allows self transfers
// (return value checks omitted for brevity)

void initialize_account(account *a, int id, double balance) {
    a->id = id;
    a->balance = balance;

/* Declare the lock as reentrant */
    pthread_mutexattr_t attr;
    pthread_mutexattr_init(&attr);
    pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE);
    pthread_mutex_init(&a->lock, &attr);
}
```
.codelink[<a href="src/reentrant.c" download>`09-more-about-locks/reentrant.c`</a> <a href="https://github.com/olivierpierre/comp35112-devcontainer" target="_blank" style="text-decoration: none"><img src="include/gh-logo.svg" style="height: 1em" ></a><a href="https://www.programiz.com/online-compiler/8ZzBtzGCRcAZe" target="_blank" style="text-decoration: none"><img src="include/programiz-logo.png" style="height: 1em"></a>]

???

- A reentrant lock can be taken several time by the same thread
- We can specify that a mutex is reentrant by using the second parameter of the
  pthread_mutex_init function
- It takes a pointer to a data structure of type pthread_mutexattr_t,
  that allows to set various attributes to a created mutex
- It is initialised with pthread_mutexattr_init, and we indicate the fact that
  we want to set the reentrant attribute with pthread_mutexattr_settype
- If we try the corresponding code, even when transfer is called with the
  to and from parameters pointing to the same account, there is no
  problems because the lock is reentrant

---
# Other Lock Types

- **Semaphores**
  - Mutexes that can be hold by multiple threads
  - Useful to coordinate access to a fixed number of resources
- **Spinlocks**
  - Threads attempting to hold an unavailable lock will **busy-wait**
      - As opposed to going to sleep for mutexes
      - Monopolises CPU, lower wakeup latency
- **Read-write locks**
  - Allows concurrent reads and exclusive writes

For more information see the multithreaded programming guide:
https://bit.ly/3FGt3k2

???

- So in addition to the mutex, pthread gives you access to other lock types
- While the mutex can only be held by a single thread, even if it is reentrant,
  a semaphore is a lock that can be held by several threads at once
- It is useful for example to arbitrate access to a set of resources that are
  in limited number
- Further we have the spinlock
- Contrary to a mutex that, when it cannot take a lock, has the operating
  system put the calling thread to sleep, the spinlock uses busy waiting
- It spins, it means it monopolises the CPU in a loop until it can take the
  lock
- It wastes CPU cycles but gives a better wakeup latency versus compared to the
  mutex
- And finally we have read-write locks, they allow concurrent reads, but
  serialise write operations

---
# Summary

- Locks come with their own issues
  - **Concurrency issues are hard to debug, it's important to get your
synchronisation strategy right from the beginning**
- Lock granularity and reentrancy
- Other lock types: semaphores, spinlocks, read-write locks

Next lecture: hardware support for synchronisation

???
- And that's it!
- To briefly summarise, locks are important to protect
  critical sections, however they have some specific issues that it is
  important to keep in mind
- When implementing your locking strategy, you have to think about all the
  possible scenarios to avoid things like deadlocks
- It is not easy, however concurrency issues are generally very hard to debug
  and it is important to get your locking strategy right from the start
- In the next lecture, we'll see what are the low-level hardware mechanisms
  that make locking possible