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.

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 $𝑞$ . If the process does not complete within this time, it is preempted and appended to the end of the ready queue. The quantum $𝑞$ 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.