Pthreads, OpenMP, and CPU scheduling methods

Pthreads

The Pthreads library is a POSIX standard API for thread creation and synchronization. So it specifies the behavior of the library but implementation is left to the developers.

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

// This variable is shared between the main and the worker thread.
int sum;

// Function that runs in the separate thread.
void* runner(void *param) {
    int i, upper = atoi(param);
    sum = 0;

    for (i = 0; i < upper; ++i) {
        sum += i;
    }

    // We use the sum variable for simplicity instead of returning a pointer
    // with a return value.
    pthread_exit(NULL);
}

int main(int argc, char* argv[]) {
    // Pointer to thread id;
    pthread_t tid;
    // Thread attributes;
    pthread_attr_t attr;

    // Initializes thread attributes with default values.
    pthread_attr_init(&attr);
    // Creates the thread and runs the runner function with argv[1] as param.
    pthread_create(&tid, &attr, runner, argv[1]);
    // Waits for the thread to call pthread_exit;
    pthread_join(tid, NULL);

    printf("sum = %d\n", sum);

    return 0;
}

Implicit threading (OpenMP)

Explicit thread handling becomes difficult for non-trivial examples. Modern approaches use the compiler to automatically insert code that spawns and waits for threads to complete.

OpenMP uses the #pragma omp parallel compiler directive to automatically parallelize a region of code:

#include <omp.h>
#include <stdio.h>

int main() {
    printf("sequential code\n");

    // Creates as many threads as the system has available by default.
    // There are more directives to customize its behavior.
    #pragma omp parallel
    {
        printf("parallel code\n");
    }

    printf("sequential code\n");

    return 0;
}

CPU scheduling

Maximum CPU utilization is achieved with multiprogramming when:

there are no context switches;
there is no I/O waiting;

Typically, a process cycle consists of a CPU burst followed by an I/O burst. A basic CPU scheduler selects from the processes in the ready queue and allocates a CPU core to one of them.

CPU scheduling decisions take place when a process:

switches from running to waiting state;
switches from running to ready state;
switches from waiting to ready state;
terminates;

Under non-preemptive scheduling, the process retains the CPU until it terminates or voluntarily transitions to the waiting state. Modern operating systems utilize preemptive scheduling, which allows the scheduler to interrupt a running process and switch to another at any time.

Preemptive scheduling can result in race conditions, especially when data is shared among threads or processes.

The dispatcher is the module responsible for managing CPU execution. It handles context switching and kernel-to-user mode transitions. Dispatch latency is defined as the time required for the dispatcher to halt one process and initiate another.

Scheduling algorithms

First-Come, First-Served (FCFS): processes are executed in the order of arrival. This method is vulnerable to the convoy effect, where a slow initial process significantly delays subsequent processes.
Shortest Job First (SJF): executes the process requiring the least execution time first. Determining the exact required time is difficult; however, it can be approximated using an exponential average of historical data.
Shortest Remaining Time First (SRTF): this is the preemptive counterpart to SJF. Upon any arrival in the ready queue, the scheduling decision is re-evaluated based on SJF criteria.
Round Robin: Each process is allocated a small time quantum $q$ . If the process does not complete within this time, it is preempted and appended to the end of the ready queue. The quantum $q$ must be carefully chosen: if too large, it degenerates into FCFS; if too small, the overhead increases significantly.

Priority scheduling

A priority number is associated with each process. The CPU is allocated first to the process with the highest priority.

A potential issue is starvation, where low-priority processes may never execute. This is mitigated by the aging technique, which involves gradually increasing a process’s priority over time.

For processes with the same priority, round-robin can be used.