Synchonization

1. Critical Sections & Mutual Exclusion

A critical section is a section of code in which a process (or thread) accesses a shared resource.

Mutual exclusion ensures only a single process can execute a critical section at a time. Processes must request permission to enter a critical section. The requirements are:

• No two processes may be simultaneously inside a critical region.
• No process running outside the critical region may block other processes from entering the critical region.
• No process should have to wait forever to enter its critical region.
• No assumptions are made about the relative speed of the processes.

1.1 Disabling Interrupts

One way to achieve mutual exclusion is to disable interrupts:

1void extract(int acc_no, int sum) {
2  enum intr_level old_level = intr_disable();
3  int b = acc[acc_no];
4  acc[acc_no] = b - sum;
5  intr_set_level(old_level);
6}

This only works on a single-core system. Misbehaving / buggy processes may never release CPU. This is usually only used by kernel code.

1.2 Strict Alternation

Another way to achieve mutual exclusion is to use strict alternation:

1int turn = 0;
2
3void P0() {
4  while (true) {
5    while (turn != 0);
6    critical_section();
7    turn = 1;
8    noncritical_section();
9  }
10}
11
12void P1() {
13  while (true) {
14    while (turn != 1);
15    critical_section();
16    turn = 0;
17    noncritical_section();
18  }
19}

If P0 takes a long time in the noncritical_section() and P1 is ready to run, P1 will busy-wait until P0 finishes. This violates the second requirement of mutual exclusion. Additionally, one of the processes will not be able to execute its loop twice in a row.

Strict alteration requires busy waiting:

• Wastes CPU time.
• Should only be used when the wait is expected to be short (violates the fourth requirement of mutual exclusion).

1.3 Peterson's Algorithm

1int turn = 0;
2int interested[2] = {0, 0};
3
4void enter_critical (int thread) {
5  int other = 1 - thread;
6  interested[thread] = 1;
7  turn = other;
8  while (turn == other && interested[other]);
9}
10
11void leave_critical (int thread) {
12  interested[thread] = 0;
13}
14
15void P0() {
16  enter_critical(0);
17  critical_section();
18  leave_critical(0);
19}
20
21void P1() {
22  enter_critical(1);
23  critical_section();
24  leave_critical(1);
25}

1.4 Spin Locks

Atomic instruction provided by most CPUs called TSL. Automatically sets memory location LOCK to 1 and returns the previous value. This can be used to implement a lock:

1void lock (int L) {
2  while (TSL(L) != 0);
3}
4
5void unlock (int L) {
6  L = 0;
7}

Spin locks are locks that require a busy wait. These waste CPU time, and may run into a priority inversion problem:

• High priority is waiting for IO.
• Low priority acquires lock.
• IO completes, high priority is ready to run.
• Low priority is still holding the lock, so high priority must wait.
• Low priority is not running, so high priority is not running.
• Low priority is not running, so high priority is not running.
• ...

1.5 Lock Granularity

Lock granularity allows specifying the size of the critical section. For example:

1void extract(int acc_no, int sum) {
2  lock(acc[acc_no]);
3  int b = acc[acc_no];
4  acc[acc_no] = b - sum;
5  unlock(acc[acc_no]);
6}

Lock overhead - the cost associated with acquiring and releasing locks. Takes into account:

• Memory space
• Initialization
• Time to acquire and release

Lock contention - measure the number of processes that are waiting for a lock. More contention -> less parallelism.

We need to chose finer lock granurality to reduce contention, but this increases lock overhead. Release a lock as soon as it is not needed:

1void add_account (int acc_no, int balance) {
2  lock(acc);
3  create_account(acc_no, balance);
4  unlock(acc);
5
6  lock(acc[acc_no]);
7  acc[acc_no] = balance;
8  unlock(acc[acc_no]);
9}

1.6 Read / Write Locks

• lock_rd - acquires a lock in read mode.
• lock_wr - acquires a lock in write mode.
• In write mode, the thread has exclusive access.
• In read mode, multiple threads can access the resource.

A race condition occurs when multiple threads or processes read / write shared data and the final result depends on the order of execution.

2 Memory Models

In this course, we assume sequential consistency:

• The operations of each thread appear in program order.
• The operations of all threads are executed in some sequential order atomically.

Other memory models (due to hardware behaviour and compiler optimizations) exist.

1int flag0 = 0, flag1 = 0;
2
3void T1() {
4  flag0 = 1;
5  if (flag1 == 0) critical();
6}
7
8void T2() {
9  flag1 = 1;
10  if (flag0 == 0) critical();
11}

Under sequential consistency, it is impossible for both threads to enter the critical section. However, under weak memory models, it is possible.

3. Semaphores

Semaphores are blocking synchronization methods, where process cooperate by means of signals. They are special variables, accessible via the following atomic operations:

• down(s): receive a signal via semaphore s.
• up(s) : transmit a signal via semaphore s.
• init(s, n): initialize semaphore s with value n.

Semaphores have two private components:

• n : the value of the semaphore.
• queue: a queue of processes waiting for the semaphore.

1typedef struct {
2  int value;
3  struct process *queue;
4} semaphore;
5
6void init(semaphore *s, int n) {
7  s->value = n;
8  init_queue(s->queue);
9}
10
11void down(semaphore *s) {
12  s->value--;
13  if (s->value < 0) {
14    add_to_queue(s->queue, current_process);
15    block();
16  }
17}
18
19void up(semaphore *s) {
20  s->value++;
21  if (s->value <= 0) {
22    pop_from_queue(s->queue, p);
23    unblock(p);
24  }
25}

3.1 Semaphore: Mutual Exclusion

In a binary semaphore, the counter is initialized to 1. This is similar to a lock / mutex.

1semaphore *sema;
2
3void P0() {
4  down(sema);
5  critical_section();
6  up(sema);
7}
8
9void P1() {
10  down(sema);
11  critical_section();
12  up(sema);
13}
14
15void init () {
16  init(sema, 1);
17
18  // Start P0 and P1 in random order
19}

3.2 Semaphore: Ordering

Process P0 must run before P1:

1semaphore *sema;
2
3void P0() {
4  critical_section();
5  up(sema);
6}
7
8void P1() {
9  down(sema);
10  critical_section();
11}
12
13void init () {
14  init(sema, 0);
15  
16  // Start P0 and P1 in random order`
17}

3.3 General Semaphores

The initial value of a semaphore indicates how many processes can access shared data at the same time.

3.4 Producer / Consumer Problem

Producer constraints:

• Items can only be deposited in the buffer if there is space.
• Items can only be deposited in the buffer if mutual exclusion is guaranteed.

Consumer constraints:

• Items can only be fetched from the buffer if it is not empty.
• Items can only be fetched from the buffer if mutual exclusion is guaranteed.

A buffer can hold between and items.

1semaphore *item, *space, *mutex;
2sema_init(item, 0);  // Ensure buffer is not empty
3sema_init(space, N); // Ensure buffer is not full
4sema_init(mutex, 1); // Ensure mutual exclusion
5
6void producer() {
7  while (true) {
8    produce();
9    down(space);
10    down(mutex);
11    deposit();
12    up(mutex);
13    up(item);
14  }
15}
16
17void consumer() {
18  while (true) {
19    down(item);
20    down(mutex);
21    fetch();
22    up(mutex);
23    up(space);
24    consume();
25  }
26}

4. Monitors

A monitor consists of:

• Shared data
• Entry procedures (can be called from outside the monitor)
• Internal procedures (can only be called from within the monitor)
• An (implicit) monitor lock
• One or more condition variables

Processes can only call entry procedures, and cannot directly access internal data. Only one process can be in the monitor at a time.

Condition variables are associated with higher-level conditions (e.g. "space available in buffer"). It contains three operations:

• wait(c) : release the monitor lock and wait for a signal on condition c.
• signal(c): wake up one process waiting on condition c.
• broadcast(c): wake up all processes waiting on condition c.

Signals do not accumulate - if a condition variable is signalled with no one waiting, the signal is lost. Now, the producer / consumer problem can be solved using monitors:

1condition not_empty, not_full;
2int count = 0;
3
4void producer() {
5  while (true) {
6    produce();
7    if (count == N) wait(not_full);
8    deposit();
9    count++;
10    if (count == 1) signal(not_empty);
11  }
12}
13
14void consumer() {
15  while (true) {
16    if (count == 0) wait(not_empty);
17    fetch();
18    count--;
19    signal(not_full);
20    consume();
21  }
22}