Calculation of Catalan Numbers in a Multithreading System

Authors

• Ariel Gomez Garcia
• Yoel Polanco

Course

COP 6611 — Operating Systems (Spring 2026)

Description

This program computes Catalan numbers C(0) through C(N) using POSIX threads (Pthreads). It demonstrates two levels of parallelism:

• Level 1: One "manager" thread per Catalan number C(1)..C(N). Each manager waits via condition variables until all prerequisite values are available.
• Level 2: Once dependencies are satisfied, each manager spawns worker threads that compute disjoint chunks of the summation in parallel, then combines partial sums.

OS Concepts Demonstrated

• Multithreading (pthread_create / pthread_join)
• Mutual exclusion (pthread_mutex_lock / pthread_mutex_unlock)
• Condition variables (pthread_cond_wait / pthread_cond_broadcast)
• Shared memory between threads (global arrays)
• Dependency management without busy-waiting
• Parallel reduction (splitting work among sub-threads)

Files Included

File	Description
Catalan.c	Source code
input.txt	Sample input file (single integer N)
output.txt	Sample output generated by the program
README.md	This file
slides.pptx	Presentation slides
report.pdf	Final project report

Compilation

gcc -Wall -Wextra -std=c11 -pthread -o catalan Catalan.c

Usage

./catalan <input_file>

Example

echo "15" > input.txt
./catalan input.txt

Input Format

A text file containing a single non-negative integer N on the first line.

• Recommended range: 0 to 33
• Values above 33 will overflow unsigned long long and produce incorrect results.

Output

• Results are printed to stdout (terminal).
• Results are also saved to output.txt in the current directory.
• The program compares the multithreaded results against a single-threaded baseline for verification and displays a performance comparison.

Platform Tested

• Server: sclogin1 (University of South Florida)
• OS: Linux
• Compiler: GCC with -std=c11 -pthread