Concept of a Thread

A thread is a basic unit of CPU utilization, consisting of a thread ID, a program counter, a register set, and a stack. It shares with other threads belonging to the same process its code section, data section, and other operating-system resources, such as open files and signals.

Differences between Thread and Process

The pthread_create() function is used to create a new thread. It starts execution in the function pointed to by start_routine.

Syntax

c
int pthread_create(pthread_t thread, const pthread_attr_t attr,
void (start_routine) (void ), void arg);

Parameters

1. thread: A pointer to a pthread_t variable where the unique identifier of the newly created thread will be stored.
2. attr: A pointer to pthread_attr_t structure to specify thread attributes (e.g., stack size, scheduling policy). If passed as NULL, default attributes are used.
3. start_routine: A pointer to the C function that the thread will execute once created. This function must accept a void * argument and return a void *.
4. arg: The argument to be passed to the start_routine. If multiple arguments are needed, a pointer to a structure containing the data is passed. If no argument is needed, NULL is passed.

Return Value

On success, it returns 0. On error, it returns a non-zero error number.

pthread_exit()

This function is used to terminate the calling thread.

• Usage: void pthread_exit(void *retval);
• Significance: It ensures that the thread cleans up its own stack and registers but does not close the entire process (unless it is the last thread). It allows the thread to return a value (retval) to the thread that joins it.

pthread_join()

This function is used to wait for the termination of a specific thread.

• Usage: int pthread_join(pthread_t thread, void **retval);
• Significance:
  • Synchronization: It acts as a barrier, suspending the execution of the calling thread until the target thread terminates.
  • Resource Release: In many implementations, a thread's resources are not fully reclaimed until it is joined (similar to wait() for processes to prevent zombies).
  • Return Value Retrieval: It allows the calling thread to retrieve the exit status/value returned by the target thread via pthread_exit.

Definition

A Race Condition is a situation in concurrent programming where the system's behavior or output depends on the uncontrollable sequence or timing of unrelated events (like the scheduling order of threads). It occurs when two or more threads access shared data and try to change it at the same time.

Scenario: The Bank Account Problem

Consider a shared variable balance = 1000.

Thread A (Deposit 500):

1. Read balance (1000)
2. balance = balance + 500
3. Write balance

Thread B (Withdraw 200):

1. Read balance (1000)
2. balance = balance - 200
3. Write balance

Race Condition Execution:

1. Thread A reads 1000.
2. Context switch to Thread B.
3. Thread B reads 1000.
4. Thread B calculates 800 and writes 800.
5. Context switch back to Thread A.
6. Thread A (using its old register value of 1000) calculates 1500 and writes 1500.

Result: The withdrawal of 200 is lost. The final balance is 1500 instead of the correct 1300. This is a race condition.

Critical Section Problem

The Critical Section Problem involves designing a protocol that processes/threads use to cooperate. A Critical Section is a segment of code where a process accesses shared resources (common variables, files, tables). The problem is to ensure that when one process is executing in its critical section, no other process is allowed to execute in its critical section.

Required Conditions

1. Mutual Exclusion: If process is executing in its critical section, then no other processes can be executing in their critical sections.
2. Progress: If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not in their remainder sections can participate in deciding which will enter its critical section next, and this selection cannot be postponed indefinitely.
3. Bounded Waiting: There must be a limit (bound) on the number of times other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted. This prevents starvation.

Mutex Lock

A Mutex (Mutual Exclusion) is a synchronization primitive used to protect shared resources. It acts like a lock: a thread acquires the lock before entering a critical section and releases it upon exiting. If the lock is already held by another thread, the requesting thread blocks until the lock becomes available.

POSIX Usage

1. Initialization: The mutex must be initialized before use.
   c
   pthread_mutex_t lock;
   pthread_mutex_init(&lock, NULL);

2. Locking (Entry Section): Before entering the critical section, the thread attempts to lock the mutex.
   c
   pthread_mutex_lock(&lock);
   // Critical Section (Access shared resource)

3. Unlocking (Exit Section): After finishing, the thread releases the mutex.
   c
   pthread_mutex_unlock(&lock);
   // Remainder Section

4. Destruction: When no longer needed.
   c
   pthread_mutex_destroy(&lock);

This ensures Mutual Exclusion because only the thread holding the lock can execute the code between the lock and unlock calls.

Semaphores

A semaphore is an integer variable accessed only through two standard atomic operations: wait() and signal().

Semaphores are accessed via two atomic operations, historically called (wait) and (signal).

1. Wait Operation (sem_wait or )

The wait() operation decrements the semaphore value. If the value becomes negative, the process executing the wait is blocked.

Definition:

2. Signal Operation (sem_post or )

The signal() operation increments the semaphore value. If there are processes blocked waiting on this semaphore, one of them is woken up.

Definition:

Comparison

1. Ownership:

   • Mutex: Has a concept of ownership. The thread that locks the mutex must be the one to unlock it.
   • Semaphore: No ownership. One thread can wait (decrement) and another thread can signal (increment). This makes semaphores suitable for signaling between threads.

2. Nature:

   • Mutex: Strictly a locking mechanism for mutual exclusion.
   • Semaphore: A signaling mechanism (Counting semaphores handle resource counting).

Selection Criteria

• Choose Mutex: When you strictly need Mutual Exclusion for a critical section (e.g., modifying a shared variable). It is generally faster and lighter than a semaphore for this specific purpose.
• Choose Semaphore:
  1. When you need to synchronize the execution order of different threads (e.g., Thread A must finish before Thread B starts - Thread A signals, Thread B waits).
  2. When managing a pool of identical resources (Counting Semaphore).
  3. When solving Producer-Consumer problems (handling full/empty slots).

The Producer-Consumer problem involves a fixed-size buffer. Producers add items, Consumers remove them. We must ensure Producers don't add to a full buffer and Consumers don't remove from an empty one, while maintaining mutual exclusion on the buffer indices.

Semaphores Required

1. mutex: A binary semaphore (init 1) for mutual exclusion on buffer access.
2. empty: A counting semaphore (init , where is buffer size) tracking empty slots.
3. full: A counting semaphore (init 0) tracking filled slots.

Producer Logic

c
do {
// produce an item in next_produced

wait(empty); // Wait for an empty slot
wait(mutex); // Lock buffer access

// add next_produced to buffer

signal(mutex); // Unlock buffer
signal(full);  // Increment count of full slots

} while (true);

Consumer Logic

c
do {
wait(full); // Wait for a filled slot
wait(mutex); // Lock buffer access

// remove an item from buffer to next_consumed

signal(mutex); // Unlock buffer
signal(empty); // Increment count of empty slots

// consume the item in next_consumed

} while (true);

The sem_init() function initializes an unnamed semaphore.

Syntax

c
int sem_init(sem_t *sem, int pshared, unsigned int value);

Arguments

1. sem: A pointer to the sem_t structure to be initialized.
2. pshared: An integer indicating whether the semaphore is shared between threads of a process or between processes.
   • If pshared == 0: The semaphore is shared between threads of the calling process.
   • If pshared != 0: The semaphore is shared between processes (requires shared memory).
3. value: The initial value to set the semaphore to.
   • For a binary semaphore/mutex equivalent, this is usually 1.
   • For a resource counter, this is the number of resources N.

Deadlock Definition

Deadlock is a state where a set of threads are blocked because each thread is holding a resource and waiting to acquire another resource held by some other thread in the same set. No thread can proceed.

Scenario with Mutex Locks

Suppose there are two threads () and two mutex locks ().

Thread 1 Execution:
c
pthread_mutex_lock(&M_A); // Acquires A
// Context Switch happens here
pthread_mutex_lock(&M_B); // Waits for B

Thread 2 Execution:
c
pthread_mutex_lock(&M_B); // Acquires B
pthread_mutex_lock(&M_A); // Waits for A

The Deadlock:

1. holds .
2. holds .
3. requests and blocks (because has it).
4. requests and blocks (because has it).

Neither thread can release the lock they hold because they are stuck waiting for the other. This circular dependency creates a deadlock.

Arguments are passed as the fourth parameter in pthread_create, which is of type void *. If a single variable is needed, its address is cast to void *. If multiple arguments are needed, a structure is defined.

Code Snippet (Using a Structure)

c

include <pthread.h>

include <stdio.h>

// Define a structure for arguments
struct thread_args {
int id;
int value;
};

void myThreadFun(void arg) {
// Cast back to struct pointer
struct thread_args my_data = (struct thread_args )arg;
printf("ID: %d, Value: %d
", my_data->id, my_data->value);
return NULL;
}

int main() {
pthread_t tid;
struct thread_args args;
args.id = 1;
args.value = 100;

// Pass address of struct cast to void*
pthread_create(&tid, NULL, myThreadFun, (void *)&args);

pthread_join(tid, NULL);
return 0;

}

Both functions interact with a mutex object, but they behave differently when the mutex is already locked by another thread.

pthread_mutex_lock()

• Behavior: It is a blocking call.
• If the mutex is available, it locks it and returns immediately.
• If the mutex is already locked, the calling thread is suspended (put to sleep) until the mutex becomes available.

pthread_mutex_trylock()

• Behavior: It is a non-blocking call.
• If the mutex is available, it locks it and returns 0.
• If the mutex is already locked, it does not block. Instead, it returns immediately with an error code (usually EBUSY).

Use Case for trylock

Used when a thread wants to do alternative work if the resource is busy, rather than waiting idle, preventing potential deadlocks or improving responsiveness.

Condition Variables (pthread_cond_t)

A condition variable is a synchronization primitive that allows threads to suspend execution and relinquish the processor until some condition is true. They allow threads to synchronize based on the actual value of data.

Why used with Mutexes?

Condition variables are always associated with a mutex lock to avoid race conditions on the condition being checked.

The Pattern:

1. Wait (pthread_cond_wait):
   • A thread acquires a mutex.
   • It checks a condition (e.g., buffer_count > 0).
   • If the condition is false, it calls pthread_cond_wait(&cond, &mutex).
   • Crucially, this function atomically releases the mutex and blocks the thread. This allows other threads to acquire the mutex to change the condition.
   • When signaled, it re-acquires the mutex before returning.
2. Signal (pthread_cond_signal):
   • Another thread acquires the mutex, changes the state (e.g., adds to buffer), and signals the condition variable to wake up waiting threads.

Busy Waiting

Busy waiting (or spinning) occurs when a process/thread repeatedly checks a condition in a loop (e.g., while(locked);) to see if it can proceed.

• Disadvantage: It wastes CPU cycles that could be used by other processes. This is inefficient in multiprogramming systems.

How Synchronization Primitives Avoid It

Modern implementations of Mutexes and Semaphores use a Block/Sleep and Wakeup mechanism instead of busy waiting.

1. Block: When a thread attempts to acquire a locked mutex or wait on a zero-valued semaphore, the OS kernel moves the thread from the Running state to the Waiting state.
2. Context Switch: The CPU is yielded to another process.
3. Wakeup: When the mutex is unlocked or the semaphore is signaled, the OS kernel moves the waiting thread from the Waiting state to the Ready queue.

This ensures the CPU is not idle checking a variable, thus solving the inefficiency of busy waiting.

The Problem

Multiple threads (readers and writers) access a shared database.

• Readers: Only read the data (multiple readers can read simultaneously).
• Writers: Read and write data (writers require exclusive access).

Constraints

1. If a Writer is active, no other Writer or Reader can be active.
2. If a Reader is active, other Readers can join, but no Writer can enter.

Challenges (Variations)

1. First Readers-Writers Problem (Reader Preference):
   • Logic: No reader is kept waiting unless a writer has already obtained permission to use the shared object.
   • Issue: Starvation of Writers. If new readers keep arriving, the writer may never get a chance to write.
2. Second Readers-Writers Problem (Writer Preference):
   • Logic: Once a writer is ready, it performs the write as soon as possible. No new readers may start reading if a writer is waiting.
   • Issue: Starvation of Readers.

Function

pthread_self() is a function in the POSIX thread library that returns the Thread ID of the calling thread.

Syntax: pthread_t pthread_self(void);

Utility

1. Identification: It allows a thread to know its own identity. This is useful for logging or debugging purposes to trace which thread is performing an action.
2. Comparison: It is used with pthread_equal(tid1, tid2) to check if two thread IDs correspond to the same thread.
3. Detaching: A thread might use it to detach itself using pthread_detach(pthread_self()), ensuring its resources are released immediately upon termination without being joined.

c

include <stdio.h>

include <semaphore.h>

include <pthread.h>

int main() {
sem_t mySem;

// 1. Initialize Semaphore
// pshared = 0 (thread shared), value = 1 (binary)
if (sem_init(&mySem, 0, 1) != 0) {
    perror("Semaphore init failed");
    return 1;
}

printf("Semaphore initialized.

");

// 2. Wait (P operation)
// Decrements value. If value was 1, it proceeds. If 0, it blocks.
sem_wait(&mySem);

printf("Entered Critical Section.

");
// ... Critical Section Operations ...

// Signal (V operation) to release
sem_post(&mySem);
printf("Exited Critical Section.

");

// 3. Destroy Semaphore
sem_destroy(&mySem);

return 0;

}

1. Responsiveness: In an interactive application, multithreading allows a program to continue running even if part of it is blocked or is performing a lengthy operation (e.g., a GUI remains responsive while a background thread downloads a file).
2. Resource Sharing: Threads share the memory and resources of the process they belong to by default. This avoids the overhead of setting up shared memory or message passing used in inter-process communication.
3. Economy: Allocating memory and resources for process creation is costly. Because threads share resources, it is more economical to create and context-switch threads.
4. Scalability (Utilization of MP Architectures): On multiprocessor or multicore architectures, multithreading can greatly increase parallelism. Different threads can run on different cores simultaneously, speeding up computation.