Process Syncronization

Cooperative vs Independent

• Cooperative processes share state
• The actions of cooperative processes depends on the actions of the others
• But all the processes are independent and isolated

Producer-consumer problem

• It is a recurring problem in computing.
• It is necessary to synchronize the consumer process and the production process in order to
  • Avoid consumption if there is nothing to consume
  • Avoid overproduction, in case there is no space in the buffer.

Producer code

do {
    ...
    produce_a_new_element(thing) 
    ...
    while (counter == MAX_PLACES) do_nothing(); 
    buffer[producer_pointer] = thing;
    producer_pointer = (producer_pointer + 1) % MAX_ELEMENT; 
    counter = counter + 1;
} while (TRUE);
 

Consumer code

do
{
    while (counter == 0) do_nothing();
    thing = buffer[consumer_pointer];
    consumer_pointer = (consumer_pointer + 1) % MAX_ELEMENT; 
    counter = counter - 1;
    
    ...
    use_produced_element(thing)
    ...
} while (TRUE);

Race conditions

Why there are race conditions?

• They happend because of the different relative speed between two processes when operating on shared data.
• Depending on that speed we obtain different results (not deterministic)
• The increase or decrease operation is not atomic

• We need parts of the code to be executed exclusively: critical sections

Critical section

• Code section in which shared variables are updated
• The mutual exclusion is a mechanism that ensures that only one process accesses a critical section exclusively.

Critical section requirements

• Mutual exclusion must be ensured
• Progress must be ensured
• Limited waiting time must be guaranteed

How to provide critical sections

• Control variables
• Specific machine instructions (test_and_set, swap)
• Operating system primitives (semaphores)
• Solutions provided by third parties (language, external services, etc.)

Control variables (first try)

• We assume that load and store machine operations are atomic
• Two threads \(T_i\) y \(T_j\) share the turn variable

do {
    while (turn != i) do_nothing(); 
    // CRITICAL SECTION
    turn = j;
    ....
} while (TRUE);

• mutual exclusion
• progress
• finite wait

Control variables (second try)

flag[i] = false
flag[j] = false

flag variable signals the intention of a process i to enter the critical section

 
do {
    while (flag[j]) do_nothing();
    flag[i] = true;
    // CRITICAL SECTION
    flag[i] = FALSE;
    ...
} while (true);

• mutual exclusion
• progress
• finite wait

Control variables (third try)

flag[i] = false
flag[j] = false

flag variable signals the intention of a process i to enter the critical section

do {
    flag[i] = true;
    while (flag[j]) do_nothing();
    // CRITICAL SECTION
    flag[i] = FALSE;
    ...
} while (true);

• mutual exclusion
• progress
• finite wait

Control variables (The Dekker's Algorithm)

flag[i] = false
flag[j] = false
turno = i

do {
    flag[i] = true;
    turn = j;
    while (flag[j] && (turn == j)) do_nothing();
    // CRITICAL SECTION
    flag[i] = false;
    resto de la sección 
} while (true);

• mutual exclusion
• progress
• finite wait

How does test_and_set work?

test_and_set(&memory)

pseudocode in C

int test_and_set (int *memory_position) { 
    int aux;
    aux = *dest; 
    *dest = TRUE; 
    return (aux);
}

do {
    while (test_and_set (&lock)) do_nothing();
    // CRITICAL SECTION
    lock = false;
    ...
} while (TRUE);

Critical sections with test_and_set

• mutual exclusion
• progress
• finite wait
• easy to extend to many processes
• require shared memory
• uses busy wait

Semaphores

• They are objects managed by the kernel
• It is a special type of variable that allows two operations
  • P(S) Wait until the semaphore is positive, and then decrease it.
  • V(S) Increase the semaphore by one.
• Both operations P and V are atomic

The producer-consumer problem with semaphores

• The consumer waits if there is nothing to consume
• The producer waits if there is no room left in the buffer
• All the operations have to be done in mutual exclusion

smf_full <- 0 ; Counts the number of elements in the buffer
smf_empty <- N; Counts the number of free positions in the buffer
mutex <- 1; to provide mutual exclusion

Producer code

data = produce()
P(sem_empty)
P(mutex)
push(data)
V(mutex)
V(sem_full)

Consumer code

P(sem_full)
P(mutex)
data = pop()
V(mutex)
V(sem_empty)

Some open questions?

• Does the order of operations P and V matter?
• What if there were two producers or two consumers?
• If one participant had to wait, would it be a busy wait?
• What are the implications in CPU schedulling?

Semaphore implementation

• P and V are software constructions
• Both of them involve and rely on the kernel to:
  • Avoid race conditions mutual exclusion
  • Avoid busy-waiting synchronization and state of a process

typedef struct {
	int counter;
	queue q;
}

Implementation guidelines: P(sem)

P (Semaphore sem) {
	CLI; //Disable interrupts
	if (sem.counter >0) {
		sem.counter --;
		STI; //Enable interrupts
		return;
	}
	sem.q.add(calling_process);
	set_to_sleep(calling_process);
	call_scheduler();
}

Implementation guidelines: V(sem)

V (Semaphore sem) {
	CLI; //Disable interrupts
	if (is_empty(sem.q) {
		sem.counter ++;
	} else {
		sem.q.pop(calling_process);
		wake_up(calling_process);
	}
	STI; //Enable interrupts
	call_scheduler(); // Depending on the scheduling policy
}

Synchronization examples

• The producer and consumers problem.
• The sleeping barber problem.
• The Readers–writers problem.
• The dining philosophers problem.