Concurrent Work-Stealing Task Scheduler in C

---

This project implements a multithreaded task scheduler in C that distributes work across multiple threads using queues. Each thread processes tasks from its own queue and, when idle, can steal tasks from other threads to balance the workload efficiently. The project demonstrates key concepts in concurrent programming, including thread management with POSIX threads, lock-free and synchronized queue operations, and work-stealing algorithms. Features include configurable number of threads and queue sizes, global or locking and lock-free per-thread queues, and runtime logging for task execution.

Key Components:

• Thread-safe per-thread queues
• Work-stealing mechanism for load balancing
• Countdown tasks executed by threads
• Atomic operations and mutex locks for synchronization
• Configurable runtime parameters (number of threads, queue type, queue length, silent mode, work stealing)
  

📝 Table of Contents

• About
• Installation and Setup
  • Prerequisites
  • Clone the Repository
  • Compile the Project
  • Run the Program
  • Cleanup
• Parameter
  • Queue Types
• Authors
• References

About

The purpose of this project is to explore and implement efficient concurrent programming techniques in C through a multithreaded task scheduler. The system distributes independent tasks across multiple threads using per-thread queues, allowing each thread to process its own tasks in parallel. When a thread completes its assigned tasks, it can steal tasks from other threads’ queues, demonstrating the work-stealing algorithm and improving overall load balancing. This approach provides a practical understanding of synchronization, thread safety, and performance optimization in concurrent systems.

Additionally, the project serves as a hands-on demonstration of key concurrency concepts such as atomic operations, mutex locks, and lock-free data structures. By implementing both thread-local and global queues, configurable thread and queue sizes, and runtime logging, the project highlights the challenges and strategies for efficiently coordinating multiple threads while avoiding common pitfalls like race conditions and deadlocks.

Installation and Setup

These instructions will help you set up the project and run it on your local system for development and testing.

1. Prerequisites

Make sure you have the following installed:

• GCC with C11 support
• Make
• POSIX Thread Library (pthread) support, usually included with GCC
• Standard C libraries (stdio.h, stdlib.h, stdbool.h, unistd.h, time.h, assert.h, string.h)

You can install GCC and related tools on Ubuntu/WSL with:

sudo apt update
sudo apt install build-essential

Verify the installation with:

gcc --version

---

2. Clone the Repository

Clone the repository and navigate into the project directory.

With HTTPS:

git clone https://github.com/SC-2025-26/project-75171-75229.git
cd project-75171-75229

With SSH:

git clone git@github.com:SC-2025-26/project-75171-75229.git
cd project-75171-75229

---

3. Compile the Project

Compile the project using the Makefile:

make

Notes:

• This will automatically compile all .c files and link the POSIX thread library.
• The Makefile includes the -std=c11 flag to ensure support for atomic operations (<stdatomic.h>).
• The executable will be created with the name threadqueues.

---

4. Run the Program

./queuethreads [options]

Example:

./queuethreads -t 4 -q i

• -t : Number of threads (optional, Default = 4)
• -q : Queue type (o= multiple queues with no locking, l = coarse-grained locking, g = global, s = stealable, i = local locking, see queue types) (optional, Default = l)
• -l : Length of queue(s) (optional, Default = 10)
• -w : Disable workstealing (optional, Default = 1)
• -s : Silent mode (optional)

---

5. Cleanup

If you want to remove the compiled binary and object files:

make clean

Parameter

Queue Types

The program implements four different queue types which can be selected by the flag:

• -q : Queue type (o= multiple queues with no locking, l = coarse-grained locking, g = global, s = stealable, i = local locking) (optional, Default = l)

All queues use atomic integers for the head and tail. When all queues are empty the threads terminate. In the following, each queue is described in more detail.

Queues with no synchronization (-q o)

• Each thread has its own queue.
• Each queue is used only by one thread
• Each thread only dequeues from its queue, no work stealing

Coarse-Grained Locking Queues (-q l)

• Each thread has its own queue.
• Each queue uses a single mutex for all operations.
• Every enqueue() and dequeue() locks the mutex and unlocks it after completion.

Global Queue (-q g)

• All threads share one global queue.
• Uses a single mutex for the entire queue.
• Every enqueue() and dequeue() locks and unlocks the mutex.

Lock-Free Queue (-q s)

• Each thread has its own queue.
• Lock-free using full memory barriers (__sync_synchronize()) and atomic compare-and-swap (__sync_bool_compare_and_swap).
• The owning thread dequeues from the head.
• Other threads steal tasks from the tail.

Local / Fine-Grained Locking Queue (-q i)

• Each thread has its own queue.
• Mutex protects only the last element and the tail.
• enqueue() is lock-free for the owning thread.
• The owning thread dequeues from the head without locking, locking only when one element remains.
• Stealing threads dequeue from the tail and lock the mutex. If only one element remains, they leave it for the owner and treat the queue as empty.

Authors

• Hanna Groß (75171)
• Luca Cordisco (75229)