Solved Exercise: 6 POSIX Threads That Identify Themselves in C

Solved OS exam exercise in C: six POSIX threads with their own logical ID, pthread_create, pthread_join and deterministic output, with tests.

Updated on October 27, 2026

Exam Code C Operating systems Exam level Tested code

Exam Code: Solved Exercise: 6 POSIX Threads That Identify Themselves in C

Operating Systems · Midterm examExercise 2 · 2.5 points · 30 min

An experimental mathematics lab wants to split a computation across exactly 6 POSIX threads. Each thread has a logical identifier from 1 to 6, and that is the identifier it must use to identify itself. The system identifier returned by pthread_self() is not acceptable, because it changes on every run.

Each thread receives a natural number n and computes how many steps the Collatz sequence needs to reach 1. One step turns x into x/2 if x is even and into 3x+1 if x is odd. By convention, for n = 1 the number of steps is 0.

Input (on standard input): six integers separated by spaces or newlines. The first belongs to thread 1, the second to thread 2, and so on. Every value must satisfy 1 <= n <= 1000000000. If there are more than six numbers, the extra ones are ignored.

There may be fewer than six integers (including empty input), a token that is not an integer, or a value out of range. In any of those cases the program creates no thread at all and prints a single line: Invalid input.

Output: six lines, ordered by identifier, in the format Thread I: n=N steps=P. Then one line Maximum: thread I with P steps naming the thread with the most steps. In case of a tie, the smaller identifier wins.

The output must be identical on every run, whatever order the scheduler uses to run the threads. The main program must wait for all threads with pthread_join. It is compiled with gcc -std=c17 -O2 -Wall -Wextra -lpthread and must produce no warnings.

Sample input

27 1 6 7 97 871

Expected output

Thread 1: n=27 steps=111
Thread 2: n=1 steps=0
Thread 3: n=6 steps=8
Thread 4: n=7 steps=16
Thread 5: n=97 steps=118
Thread 6: n=871 steps=178
Maximum: thread 6 with 178 steps

Creates the 6 threads with pthread_create, passing each one its own argument that is neither shared nor overwritten: 0.75
Waits for all threads with pthread_join before reading their results: 0.5
Computes the Collatz steps correctly inside the thread, using 64-bit integers for the intermediate values: 0.5
Validates the input and produces deterministic output in the exact format, including the tie-break for the maximum: 0.75

Hints

Hint 1 · What do I pass to each thread as its argument?

pthread_create accepts only a void *. If you pass &i, the loop variable, every thread points to the same memory location, and that location keeps changing while the threads start up. The correct approach is for each thread to have its own structure holding its identifier, its input value and a slot for its result. For instance, an array of 6 structures declared in main.

Hint 2 · Who should print?

If every thread calls printf when it finishes, the order of the lines depends on the scheduler and the output stops being deterministic. There is a simpler alternative than synchronizing the threads with each other: the thread only computes and leaves its result in its structure. The main thread prints afterwards, walking the array in order.

Hint 3 · When is it safe to read the result?

Only after pthread_join has returned for that thread. That return guarantees the thread has finished and that what it wrote to memory is visible to the main thread. Create all six threads first and do all six joins afterwards. If you join inside the same loop that creates the threads, the program works, but the computations end up running one after another.

Solution

Explained solution

The solution separates three phases: read and validate all the input, launch and wait for the threads, and print. All communication between the main thread and the workers goes through an array of Task structures, one per thread. Each thread writes only to its own structure, so there is no shared data to protect with locks.

If you need a refresher on why passing the address of a variable lets another function modify it, see the solved exercise on pass by value and by reference in C. It is exactly the mechanism behind the void * argument of pthread_create.

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

#define NUM_THREADS 6
#define LIMIT 1000000000LL

typedef struct {
    int id;                 /* logical identifier 1..6 */
    unsigned long long n;   /* input value */
    int steps;              /* result written by the thread */
} Task;

static void *work(void *arg)
{
    Task *t = (Task *)arg;
    unsigned long long x = t->n;
    int steps = 0;

    while (x != 1ULL) {
        if (x % 2ULL == 0ULL) {
            x /= 2ULL;
        } else {
            x = 3ULL * x + 1ULL;
        }
        steps++;
    }
    t->steps = steps;   /* writes only to its own structure */
    return NULL;
}

int main(void)
{
    Task tasks[NUM_THREADS];
    pthread_t threads[NUM_THREADS];

    /* Phase 1: read and validate all the input before creating threads */
    for (int i = 0; i < NUM_THREADS; i++) {
        long long v;
        if (scanf("%lld", &v) != 1 || v < 1 || v > LIMIT) {
            printf("Invalid input\n");
            return 0;
        }
        tasks[i].id = i + 1;
        tasks[i].n = (unsigned long long)v;
        tasks[i].steps = -1;
    }

    /* Phase 2: create all threads, each with its own Task */
    for (int i = 0; i < NUM_THREADS; i++) {
        int err = pthread_create(&threads[i], NULL, work, &tasks[i]);
        if (err != 0) {
            fprintf(stderr, "pthread_create failed (code %d)\n", err);
            for (int j = 0; j < i; j++) {
                pthread_join(threads[j], NULL);
            }
            return 1;
        }
    }

    /* Phase 3: wait for all of them */
    for (int i = 0; i < NUM_THREADS; i++) {
        int err = pthread_join(threads[i], NULL);
        if (err != 0) {
            fprintf(stderr, "pthread_join failed (code %d)\n", err);
            return 1;
        }
    }

    /* Phase 4: print in identifier order */
    int best = 0;
    for (int i = 0; i < NUM_THREADS; i++) {
        printf("Thread %d: n=%llu steps=%d\n", tasks[i].id, tasks[i].n, tasks[i].steps);
        if (tasks[i].steps > tasks[best].steps) {
            best = i;
        }
    }
    printf("Maximum: thread %d with %d steps\n", tasks[best].id, tasks[best].steps);
    return 0;
}

The Task structure. It groups what a thread needs to know and what it must return: id (its logical identifier), n (the input) and steps (the result). In main we declare Task tasks[NUM_THREADS]. Each thread receives the address of a different element, &tasks[i], so no thread sees or touches another thread's data.

Validation first. The first loop reads with scanf("%lld", &v) and checks three things: that an integer was read, that v >= 1 and that v <= LIMIT. If anything fails, it prints Invalid input and exits without having created any thread, so there is no half-started thread to wait for. The tests "Empty input" and "Zero value out of range" cover this path. In the second one the third number is 0 and the program rejects the input before reading the rest.

The thread function. work casts the void * to Task * and applies the Collatz rule with an unsigned long long. The type matters: for starting values up to a billion, the intermediate values far exceed the range of a 32-bit int. With 64-bit unsigned there is no overflow in that range. When done, the thread stores the counter in t->steps and returns NULL.

Creation and waiting. The second loop creates the six threads without waiting for any, and the third performs the six pthread_join calls. If pthread_create fails, the threads already created (indices 0 to i-1) are joined before exiting, so no running threads are abandoned. With a single CPU the threads do not run in true parallel, but the program is correct anyway: the design does not depend on how many cores there are.

Why the output is deterministic. No thread prints. The order of the lines is fixed by the last loop in main, which walks tasks from 0 to 5. The values are correct because they are read after the joins, and the return of pthread_join guarantees that the write to t->steps is already visible. The field is initialized to -1 as a sentinel: if someone forgot the join, that value would expose the bug.

The maximum and the tie-break. The variable best starts at 0 and changes only if a thread has strictly more steps. That is why, in a tie, the smaller identifier wins. The test "All equal", with six nines of 19 steps each, checks it: the result is Maximum: thread 1 with 19 steps. In the statement example the maximum is thread 6 (n = 871, 178 steps). In the limits test, thread 3 wins with 837799 and 524 steps, while 536870912 = 229 needs only 29 halvings.

Code and tests on GitLab

Test cases

Case	Input	Expected output	Actual output	Result
Statement example	`27 1 6 7 97 871`	`Thread 1: n=27 steps=111 Thread 2: n=1 steps=0 Thread 3: n=6 steps=8 Thread 4: n=7 steps=16 Thread 5: n=97 steps=118 Thread 6: n=871 steps=178 Maximum: thread 6 with 178 steps`	`Thread 1: n=27 steps=111 Thread 2: n=1 steps=0 Thread 3: n=6 steps=8 Thread 4: n=7 steps=16 Thread 5: n=97 steps=118 Thread 6: n=871 steps=178 Maximum: thread 6 with 178 steps`	OK
All equal (tie-break)	`9 9 9 9 9 9`	`Thread 1: n=9 steps=19 Thread 2: n=9 steps=19 Thread 3: n=9 steps=19 Thread 4: n=9 steps=19 Thread 5: n=9 steps=19 Thread 6: n=9 steps=19 Maximum: thread 1 with 19 steps`	`Thread 1: n=9 steps=19 Thread 2: n=9 steps=19 Thread 3: n=9 steps=19 Thread 4: n=9 steps=19 Thread 5: n=9 steps=19 Thread 6: n=9 steps=19 Maximum: thread 1 with 19 steps`	OK
Large values and limits	`1 536870912 837799 77031 6171 1024`	`Thread 1: n=1 steps=0 Thread 2: n=536870912 steps=29 Thread 3: n=837799 steps=524 Thread 4: n=77031 steps=350 Thread 5: n=6171 steps=261 Thread 6: n=1024 steps=10 Maximum: thread 3 with 524 steps`	`Thread 1: n=1 steps=0 Thread 2: n=536870912 steps=29 Thread 3: n=837799 steps=524 Thread 4: n=77031 steps=350 Thread 5: n=6171 steps=261 Thread 6: n=1024 steps=10 Maximum: thread 3 with 524 steps`	OK
Input spread over several lines	`2 3 4 5 6 7`	`Thread 1: n=2 steps=1 Thread 2: n=3 steps=7 Thread 3: n=4 steps=2 Thread 4: n=5 steps=5 Thread 5: n=6 steps=8 Thread 6: n=7 steps=16 Maximum: thread 6 with 16 steps`	`Thread 1: n=2 steps=1 Thread 2: n=3 steps=7 Thread 3: n=4 steps=2 Thread 4: n=5 steps=5 Thread 5: n=6 steps=8 Thread 6: n=7 steps=16 Maximum: thread 6 with 16 steps`	OK
Empty input	(empty)	`Invalid input`	`Invalid input`	OK
Zero value out of range	`5 3 0 2 4 8`	`Invalid input`	`Invalid input`	OK

Actual outputs: code compiled with gcc 14.4.0 (C17) and run in an isolated container on 27 October 2026.

Complexity

Let L(n) be the number of Collatz steps of n. The total work is the sum of the six values L(n) plus a constant cost for creating and joining six threads. No closed-form bound for L(n) is known in general. In the range of the statement (up to 109) the step counts stay below about a thousand (the largest is 986), so the time is negligible next to the cost of creating the threads.

Memory is constant: two arrays of six elements (tasks and threads) plus the stack of each thread, which the system reserves. Since the number of threads is fixed, the extra space is O(1) with respect to the data. With several cores the real time tends toward that of the slowest thread. With a single one, as in the grading environment, the six computations add up.

Common mistakes

Passing &i (the loop variable) as the argument of pthread_create. By the time the thread reads it, i may already have changed, and two threads may end up with the same identifier or with one equal to 6.
Identifying threads with pthread_self() and printing it with %d after casting to int. pthread_t is an opaque type, the conversion is not portable and the value changes on every run, so the output never matches the expected one.
Using a global counter that each thread increments with counter += 1 to number itself. That is a race condition: the increment is not atomic and the number each thread obtains depends on the scheduler.
Printing from inside the thread with no turn-taking mechanism. The lines come out in a different order on each run, even if on the student's laptop they "always come out right".
Reading tasks[i].steps without having called pthread_join on that thread first, or ending main without waiting for the threads. Returning from main terminates the whole process and pending threads die with it.
Computing the Collatz sequence with int. With large inputs, 3x+1 overflows, which is undefined behavior, and the loop may never terminate.

Variants

Each thread prints its own line, in identifier order

If the professor requires the thread itself to write its line, the threads must be synchronized. Use a global variable turn protected by a pthread_mutex_t and a condition variable. Each thread computes without holding the lock, then locks the mutex and waits with pthread_cond_wait in a while (turn != t->id) loop. When its turn comes, it prints, increments turn and calls pthread_cond_broadcast to wake the others. broadcast is used rather than signal because only one of the waiters is the next one. The computation stays concurrent: only the printing is ordered. The output is the same as in the main solution.

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

#define NUM_THREADS 6
#define LIMIT 1000000000LL

typedef struct {
    int id;
    unsigned long long n;
    int steps;
} Task;

static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t changed = PTHREAD_COND_INITIALIZER;
static int turn = 1;

static void *work(void *arg)
{
    Task *t = (Task *)arg;
    unsigned long long x = t->n;
    int steps = 0;

    while (x != 1ULL) {
        x = (x % 2ULL == 0ULL) ? x / 2ULL : 3ULL * x + 1ULL;
        steps++;
    }
    t->steps = steps;

    pthread_mutex_lock(&lock);
    while (turn != t->id) {
        pthread_cond_wait(&changed, &lock);
    }
    printf("Thread %d: n=%llu steps=%d\n", t->id, t->n, t->steps);
    turn++;
    pthread_cond_broadcast(&changed);
    pthread_mutex_unlock(&lock);
    return NULL;
}

int main(void)
{
    Task tasks[NUM_THREADS];
    pthread_t threads[NUM_THREADS];

    for (int i = 0; i < NUM_THREADS; i++) {
        long long v;
        if (scanf("%lld", &v) != 1 || v < 1 || v > LIMIT) {
            printf("Invalid input\n");
            return 0;
        }
        tasks[i].id = i + 1;
        tasks[i].n = (unsigned long long)v;
        tasks[i].steps = -1;
    }

    int created = 0;
    for (int i = 0; i < NUM_THREADS; i++) {
        if (pthread_create(&threads[i], NULL, work, &tasks[i]) != 0) {
            fprintf(stderr, "pthread_create failed\n");
            break;
        }
        created++;
    }
    if (created < NUM_THREADS) {
        /* release waiters whose turn will never come */
        pthread_mutex_lock(&lock);
        turn = NUM_THREADS + 100;
        pthread_mutex_unlock(&lock);
        for (int i = 0; i < created; i++) {
            pthread_cancel(threads[i]);
            pthread_join(threads[i], NULL);
        }
        return 1;
    }

    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_join(threads[i], NULL);
    }

    int best = 0;
    for (int i = 1; i < NUM_THREADS; i++) {
        if (tasks[i].steps > tasks[best].steps) {
            best = i;
        }
    }
    printf("Maximum: thread %d with %d steps\n", tasks[best].id, tasks[best].steps);
    return 0;
}

Each thread returns its result through pthread_join

Instead of writing into the structure, the thread can return its result as its return value. To avoid dubious conversions between integers and pointers, the clean way is to allocate an int with malloc inside the thread and return its address. main collects it with pthread_join(threads[i], &ret), copies the value and calls free(ret). Never return the address of a local variable of the thread, because its stack no longer exists once the thread ends.

What the professor will ask

“If instead of &tasks[i] I pass &i to pthread_create and then in the thread I write int id = *(int *)arg + 1, why does it sometimes work in the lab and still earn zero on that part of the exam?”

Because it is a race condition. All six threads receive the same address, that of i, and read its contents at a moment decided by the scheduler. If a thread starts right away, it reads the correct value. If it is slow, the loop has already incremented i, and two threads may get the same identifier, or one may read 6 after the loop ends. That it works on your machine only shows that in that run the scheduler was favorable, not that the program is correct. Moreover, if i is declared inside the for, it ceases to exist when the loop exits and the thread reads invalid memory. Correctness requires that each thread has its own argument and that the argument lives as long as the thread uses it.

On the syllabus

Creating and managing threads is part of the Operating Systems syllabus at several universities. The program for Sistemas Operativos at the Universidad Tecnológica Nacional (FRBA, Argentina) lists scheduling and threads within processes, as well as communication and synchronization between processes. The Computer Engineering course summary of the Pontificia Universidad Católica del Perú lists processes and threads and inter-process communication within its Operating Systems course.

In Chile, the program of IIC2333 Operating Systems and Networks at the Pontificia Universidad Católica de Chile covers processes, their scheduling, and synchronization and communication between them. For its part, CC3301 at the Universidad de Chile works on systems programming over the Linux API with heavyweight processes (fork/exec/pipes), which is the natural context in which POSIX threads appear next.

Article generated with AI.larebelion