12/10/20

1. Threads and processes execute concurrently or in parallel and can **share resources** (like devices, memory, variables, data structures etc)
2. A process/thread can be interrupted at any point in time. The process "state" (including registers) is saved in the **process control block**

The outcome of programs may be unpredictable:

> Sharing data can lead to **inconsistencies**.
>
> The **outcome of execution** may **depend on the order** in which instructions are carried out.

```c
#include <stdio.h>
#include <pthread.h>
int counter = 0;
void * calc(void * number_of_increments) {
	int i;
	for(i = 0; i < *((int*) number_of_increments);i++)
		counter++;
	}
int main() {
	int iterations = 50000000;
	pthread_t tid1,tid2;
	pthread_create(&tid1, NULL, calc, (void *) &iterations);
	pthread_create(&tid2, NULL, calc, (void *) &iterations);
	pthread_join(tid1,NULL);
	pthread_join(tid2,NULL);
	printf("The value of counter is: %d\n", counter);
}
```

This piece of code creates two threads, and points them towards the `calc` function. The `pthread_join(tid1,NULL);`  line is waiting until thread 1 is finished until the code moves on.



Counter++ consists of three separate actions.

1. *read* the value of counter from memory and **store it in a register**
2. *add* one to the value in the register
3. *store* the value of the register **in counter** in memory

The above actions are **not** "atomic". This means they can be interrupted by the timer.

![image](/lectures/osc/assets/p.png)

TCB - *Thread Control Block*

This is what could happen if the threads are not interrupted.

However the thread control block could be out of date by the time the thread starts running again. For example *counter* could be 2 but the thread control block still has the old value of *counter*.



The problem is that simple instructions in c are actually multiple instructions in assembly code. Another example is `print()`

```c	
void print() {
	chin = getchar();
	chout = chin;
	putchar(chout);
}
```

If the two threads are **interleaved** one after the other, there is no issue.

![img](/lectures/osc/assets/q.png)

However if **interleaved** like this they do interact. The global variable used to store the character in thread 1, is overwritten when thread 2 runs. This means 1+1+1 = 2 

## Bounded Buffer

> Consider a **bounded buffer** in which N items can be stored
>
> A **counter** is maintained to count the number of items currently in the buffer. **Increment** when something is added and **decremented** when an item is removed.
>
> Similar **concurrency problems** as with the calculation of sums happen in the bounded buffer which is a consumer problem.

```c	
// producer
while (true) {
	//while buffer is full
	while (counter == BUFFER SIZE); /* do nothing */
	// Produce item
	buffer[in] = new_item;
	in = (in + 1) % BUFFER_SIZE;
	counter++;
}
// consumer
while (true) {
	// wait until items in buffer
	while (counter == 0); /* do nothing */
	// Consume item
	consumed = buffer[out];
	out = (out + 1) % BUFFER_SIZE;
	counter--;
}
```

This is a circular queue, there's a start and end pointer (*in* and *out*). The shared counter is being manipulated from 2 different places which can go wrong.

## Race Conditions

A **race conditions occurs** when multiple threads/processes **access shared data** and the result is dependent on **the order in which the instructions are interleaved**.

### Concurrency within the OS

> **Kernels are pre-emptive** 
> **Multiple processes/threads are running** in the kernel.
> Kernel processes can be **interrupted** at any point.
>
> The kernel maintains **data structures**
>
> 1. These data structures are accessed **concurrently.**
> 2. These can be subject to **concurrency issues.**
>
> The OS must make sure that interactions within the OS do not result in race conditions.
>
> Processes **share resources** including memory, files, processor time, printers etc.
>
> The OS must:
>
> 1. provide **locking mechanisms** to implement **mutual exclusion** and **prevent starvation and deadlocks.**
> 2. Allocate and deallocate these resources safely.

A **critical section** is a set of instructions in which **shared resources** between processes/threads **are changed**.

**Mutual exclusion** must be enforced for **critical sections**.

> Only **one process at a time** should be in the critical section (mutual exclusion)
>
> Processes have to **get "permission"** before entering their critical section 
>
> 1. Request a lock
> 2. Hold the lock
> 3. Release the lock

Any solution to the **critical section problem** must satisfy the following requirements:

1. **Mutual exclusion** - only one process can be in its critical section at any one point in time.
2. **Progress** - any process must be able to enter its critical section at some point in time. (a process/thread has a right to enter its critical section at a point in time). If there is no thread/process in the critical section there is no reason for the currently thread not to be allowed in the **critical section**.
3. **Fairness/bounded waiting** - fairly distributed waiting times/processes cannot be made to wait indefinitely.

These requirements have to be satisfied, independent of the order in which sequences are executed.

### Enforcing Mutual Exclusion

**Approaches** for mutual exclusion can be

1. Software based - Peterson's solution
2. Hardware based - `test_and_set()` `swap_and_comapare()`

Deadlocks have to be prevented as well.

#### Deadlock Example 

A set of processes/threads is *deadlocked* if each process/thread in the set is waiting for an event that only the other process/thread in the set can cause

Each **deadlocked process/thread** is waiting for a resource held by another deadlocked process/thread (which cannot run and hence release the resource) .

* Assume that X and Y are **mutually exclusive resources**.
* Thread A and B need to **acquire both resources** and request them in oppose orders.

![img](assets/r.png)

**Four conditions** must hold for a deadlock to occur

1. **Mutual exclusion** - a resource can be assigned to at most one process at a time.
2. **Hold and wait condition** - a resource can be held while requesting new resources.
3. **No pre-emption** - resources cannot be forcefully taken away from a process
4. **Circular wait** - there is a circular chain of two or more processes,, waiting for a resource held by the other processes.

**No deadlocks** can occur if one of the conditions isn't met.
