A multi-threaded process terminates under two conditions:

1. One of the threads call the “exit()” system call terminating the process. When the process, which is the container for all threads, terminates, all threads terminate with it.
2. All threads inside the process terminate by calling pthread_exit(). When the last thread of a process terminates, the OS terminates the process because there is nothing else to run. Remember, thread is the unit of scheduling, not the process.

Concurrency is the ability of a system to handle multiple tasks or threads, often by interleaving their execution via a pre-emptive scheduling algorithm such as RR so that each task has the impression that they are the only one running in the system and all tasks making progress. Parallelism is the ability of the system to run multiple tasks or thread simultaneously, which requires multiple CPUs or cores, where different cores can run different tasks/threads in parallel.

To maximize throughput, i.e., the number of jobs completed per unit of time, we must use Shortest Job First (SJF) scheduling algorithm, which we know minimizes the waiting time. SJF makes sure that processes with short burst times get scheduled and finish quickly leading to higher throughput.

The reason new processes are placed at the end of the ready queue in RR scheduling is to prevent starvation and to give every process a chance to run. Assume that CPU is running P1 and P2 is in the ready queue. If there is a flurry of new incoming processes P3, P4, P5 …, and the OS always places these new processes at the beginning of the ready queue, then these new processes will be scheduled first before P2 has a chance to get the CPU leading to starvation for P2. But by placing the new incoming processes at the end of the ready queue, RR makes sure that all processes get a fair chance to get scheduled and use the CPU.

Thread function: Executed by each worker thread

void search(int tid) {
    int size = N / 4;
    int startIdx = tid * size;
    int endIdx = startIdx + size;
 
    int count = 0;
    for (int i = startIdx; i < endIdx; i++) {
        if (A[i] == key)
            count++;
    }
 
    localCount[tid] = count;
}

Main function: Executed by the main thread

 
int main() {
    int tids[4];
 
    for (int i = 0; i < 4; i++)
        tids[i] = CreateThread(search, i);
 
    for (int i = 0; i < 4; i++)
        JoinThread(tids[i]);
 
    int count = 0;
    for (int i = 0; i < 4; i++) {
        count += localCount[i];
    }
 
    if (count == 0)
        printf("Key does not exist in the array");
    else
        printf("Key exists %d times\n", count);
 
    return 0;
}

A critical section is the part of the code where a shared resource (a variable, a buffer, a data structure, etc.) is being accessed and modified. Mutual exclusion is to make sure that in a multi-threaded code, there is only one thread inside the critical section. To achieve mutual exclusion in a critical section, we use a mutex lock as follows:

pthread_mutex_t mutex;
 
pthread_mutex_lock(&mutex); // Grab the lock
 
// <Critical Section>
 
pthread_mutex_unlock(&mutex); // Release the lock

A spinlock is one where the thread that is trying to enter the critical section must spin in a while loop trying to grab the lock, which is owned by another thread that is already inside the critical section. In a single CPU system, the thread spinning on the lock will simply waste CPU cycles until the scheduler takes the CPU away from it and schedules the thread that is inside the critical section, which then makes progress and leaves the critical section so that the spinning thread can get re-scheduled and finally enter the critical section. In a multi CPU system, spinlocks are used because they may prevent a context switch as follows: Assume that the thread inside the critical section is about to leave the critical section when the second thread arrives and starts spinning on the lock. Because we have two CPUs, one thread will be running in CPU 1 and the other will be running in CPU2. The thread inside the critical section running say in CPU 1 leaves the critical section very quickly and releases the lock. At that point, the second thread running in CPU 2 and waiting to grab the lock can immediately enter the critical section. Thus, we saved one context switch.

The purpose of a mutex lock is to achieve mutual exclusion in a critical section. The thread that grabs the mutex lock owns this lock and only the owner can release it by unlocking the mutex lock. This also allows recursive locking, where the owner of the lock can potentially lock the mutex multiple times and unlock it the same number of times to release it. The purpose of a binary semaphore is signaling between different threads and there is no ownership of a binary semaphore. It is manipulated by two operations (wait/post, P/V), which are used to atomically decrement the value of the semaphore or to atomically increment the value of the semaphore. Semaphores are used for thread coordination and notification but should NOT be used to achieve mutual exclusion in a critical section.

Consider two threads T1 and T2 with T1 having higher priority than T2. Assume that T2 runs first and enters the critical section grabbing the lock. While T2 is running inside the critical section, T1 arrives (is added to the ready queue). Because T1 has higher priority and the scheduler employs a pre-emptive priority scheduling algorithm, the scheduler preempts T2 and schedules T1. Now T1 tries to enter the critical section but gets blocked on the lock protecting the critical section because T2 is inside the CS. So, T2 gets scheduled again, finishes its job inside the CS and leaves the CS releasing the lock. After T2 releases the lock, T1 is moved back to the ready queue and gets scheduled and enters the CS. As you can see, although T2 has a lower priority than T1, it continues running because it holds the lock and will continue using the CPU until it reaches the end of the CS and releases the lock. This is called “bounded priority inversion” problem, and this is caused by locking. To prevent this problem, you need to avoid locks and achieve mutual exclusion using lock-free mechanisms, which are quite difficult to implement.