4. Synchronization

4. Synchronization
	Chapter 3. Threads

Thread Synchronization
Synchronization objects are variables in memory that you access just like data.
The main types of synchronization objects are:
- Mutex Locks
- Condition Variables
- Semaphores
Note: Synchronization is the only way to ensure consistency of shared data.
Synchronization Variables:
The default blocking behavior is to put a thread to sleep.
Each synchronization variable has a sleep queue associated with it:
1. The synchronization primitives put the blocking threads on the synchronization variable's sleep queue
2. They surrenders the executing thread to the scheduler.
3. The scheduler tries to execute another thread.
Blocked threads are awakened when the synchronization variables become available:
1. The synchronization primitives check if threads are waiting for the synchronization variables.
2. The unblocked threads are removed from the synchronization variable's sleep queue.
3. The scheduler places the threads on a run queue corresponding to their priority.
4. The thread are then dispatched to execution in priority order.

Mutual Exclusion Locks

Mutual exclusion locks (mutexes) are used to serialize thread execution, by ensuring that only one thread at a time executes a critical section of code.

A thread acquires the lock.
Executes critical section of code.
Releases lock.

Note: Mutex locks can also preserve code that was written to run serially and thus is not thread safe.

Basic Routines*         Operation 
pthread_mutex_init      Initialize a Mutual Exclusion Lock 
pthread_mutex_lock      Lock a Mutex
pthread_mutex_unlock    Unlock a Mutex
pthread_mutex_destroy   Destroy Mutex State

Producer-Consumer Example:

pthread_mutex_t count_mutex;
int count;

increment_count() {
   pthread_mutex_lock(&count_mutex);
   count = count + 1;
   pthread_mutex_unlock(&count_mutex);
}

int get_count() {
   int c;
   pthread_mutex_lock(&count_mutex);
   c = count;
   mutex_unlock(&count_mutex);
   return (c);
}

* The examples as implemented using the Linux threads library based on the POSIX 1003.c standard.

Condition Variables

Condition variables atomically block threads until a particular condition is true.

With a condition variable, a thread can atomically block until a condition is satisfied:

When the condition is false:
1. A thread acquires the mutex.
2. It blocks on the condition variable.
3. It atomically releases the mutex waiting for the condition to change.
When another thread changes the condition:
1. The associated condition variable is signaled to cause waiting threads to wake up.
2. One of the threads reacquire the mutex, and re-evaluate the condition.
3. It continues critical code execution.
4. It releases the mutex allowing other blocked threads to proceed.

Note: Always test condition variables under the protection of a mutex lock.

Basic Routines            Operation

pthread_cond_init         Initialize a Condition Variable
pthread_cond_wait         Block on a Condition Variable
pthread_cond_signal       Unblock a Specific Thread
pthread_cond_timedwait    Block Until a Specified Event
pthread_cond_broadcast    Unblock All Threads
pthread_cond_destroy      Destroy Condition Variable State

Producer-Consumer Example:

typedef struct {
    char buf[BSIZE];
    int occupied;
    int nextin;
    int nextout;
    pthread_mutex_t mutex;
    pthread_cond_t more;
    pthread_cond_t less;
} buffer_t;

buffer_t buffer;
void producer(buffer_t *b, char item) {
    pthread_mutex_lock(&b->mutex);
    while (b->occupied == BSIZE)
        pthread_cond_wait(&b->less, &b->mutex);
    b->buf[b->nextin] = item;
    nextin++;
    b->nextin %= BSIZE; /* Makes nextin < BSIZE or 0 */
    b->occupied++;
  
    pthread_cond_signal(&b->more);
    pthread_mutex_unlock(&b->mutex);
}
char consumer(buffer_t *b) {
    char item;
    pthread_mutex_lock(&b->mutex);
    while(b->occupied == 0)
        pthread_cond_wait(&b->more, &b->mutex);
    item = b->buf[b->nextout];
    b->nextout++;
    b->nextout %= BSIZE;  /* Makes nextout < BSIZE or 0 */
    b->occupied--;
    
    pthread_cond_signal(&b->less);
    pthread_mutex_unlock(&b->mutex);
    return(item);
}

Semaphores
Semaphores are modeled after the operation of single track railroads: A train must wait a semaphore signal before entering a single track.
In the computer version, a semaphore uses a simple integer:
Producer-Consumer Example:
In the computer version, a semaphore uses a simple integer:
1. A thread waits for permission to proceed (It waits until the semaphore value is positive).
2. Then signals that it has proceeded by subtracting one from the semaphore.
3. It executes some restricted code.
4. When it is finished, the thread adds one to the semaphore's value.
Note: All these semaphore operations take place atomically, they cannot be subdivided into pieces between which other actions on the semaphore can take place.
There are two basic sorts of semaphores:
- Binary semaphores, which never take on values other than zero or one (It is like a mutex).
- Counting semaphores, which can take on arbitrary nonnegative values.
Semaphores are typically used to coordinate access to resources, with the semaphore count initialized to the number of free resources:
- Threads atomically increment the count when resources are added.
- Threads atomically decrement the count when resources are removed.
- Threads block when no resources are available.
```
Basic Routines   Operation
sem_init         Initialize a Semaphore
sem_post         Increment a Semaphore
sem_wait         Block on a Semaphore Count
sem_trywait      Decrement a Semaphore Count
sem_destroy      Destroy the Semaphore State
```
Producer-Consumer Example:
```
typedef struct {
    char buf[BSIZE];
    sem_t occupied;
    sem_t empty;
    int nextin;
    int nextout;
    sem_t pmut;
    sem_t cmut;
} buffer_t;

buffer_t buffer;

sem_init(&buffer.occupied, USYNC_THREAD, 0);
sem_init(&buffer.empty, USYNC_THREAD, BSIZE);
sem_init(&buffer.pmut, USYNC_THREAD, 1);
sem_init(&buffer.cmut, USYNC_THREAD, 1);

buffer.nextin = buffer.nextout = 0;
void producer(buffer_t *b, char item) {
    sem_wait(&b->empty);
    sem_wait(&b->pmut);
    b->buf[b->nextin] = item;
    b->nextin++;
    b->nextin %= BSIZE;
    sem_post(&b->pmut);
    sem_post(&b->occupied);
}
char consumer(buffer_t *b) {
    char item;
    sem_wait(&b->occupied);
    sem_wait(&b->cmut);
    item = b->buf[b->nextout];
    b->nextout++;
    b->nextout %= BSIZE;
    sem_post(&b->cmut);
    sem_post(&b->empty);
    return(item);
}
```


3. Scheduling		Chapter 4. Distribution Programming