Multi-threaded Throttled Preemptive Priority Queue

Aug 15, 2023

2 min read

#Data Structure
#C++

In computer science, a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a priority. Items with a higher priority are dequeued before items with a lower priority.

Today, we are looking at a fascinating implementation of a priority queue. Not just any priority queue, but a throttled one with the ability to preempt. This gives developers better control over the queue's behavior, especially in scenarios where they need more advanced queue management features.

Full code can be accessed through this repo.

Key Features

  • Max Size Constraint: The priority queue has a max size. No more items can be pushed if the size reaches this limit.
  • Throttle Rate: A throttle rate determines how often lower priority items are dequeued compared to higher priority ones.
  • Preemption: The priority queue has a mechanism to prevent lower-priority items from being stuck indefinitely. The provided implementation supports two modes: AGING and NEXT_PRIORITY.

Dive into the Code

cpp
template<typename T>
class PriorityQueue {

Here, the PriorityQueue is a templated class, meaning it can store items of any type T.

cpp
public:
    enum class PreemptiveMode {
        AGING,
        NEXT_PRIORITY,
    };

The PreemptiveMode enum helps users specify how they want lower-priority items to be treated. The AGING mode increases the priority of items over time, ensuring they don't remain in the queue indefinitely. The NEXT_PRIORITY mode changes the throttle rate temporarily to dequeue lower-priority items faster.

cpp
PriorityQueue(size_t max_size, int throttle_rate=2, int preemptive_size=50, PreemptiveMode preemptive_mode=PreemptiveMode::AGING);

The constructor allows users to specify the max size, throttle rate, preemption size, and the preemption mode. The provided default values suggest that every second item dequeued will be of the next lower priority, and every 50 items dequeued will trigger the preemption mechanism.

cpp
void push(T item, int priority);

Items are pushed into the queue with a specified priority. Higher numbers indicate lower priorities, with priority 1 being the highest.

cpp
T pop();

Popping items is where the magic happens. The throttle rate and preemptive mechanism kick in to determine which item is dequeued. This method ensures that high-priority items are dequeued first, but lower-priority items aren't left behind.

cpp
bool empty() const;
size_t size() const;
void _display() const;

Utility functions like checking if the queue is empty, fetching its size, and a debug display method are also provided.

Notable Implementation Details

  • Throttling Mechanism: For every throttle_rate items of a particular priority dequeued, the next item dequeued will be of the next lower priority. This mechanism ensures that even if the queue is flooded with high-priority items, lower-priority items will still be processed, albeit at a slower rate.
  • Aging Mechanism: Over time, if lower-priority items aren't dequeued, their priority is increased, ensuring they eventually get processed.
  • Next Priority Mechanism: This temporarily changes the throttle rate to process lower-priority items faster.

Final Thoughts

This PriorityQueue is a versatile tool, especially suitable for scenarios where tasks with varying priorities are processed, and we don't want low-priority tasks to starve or remain unprocessed. Applications might include task scheduling, network packet processing, or any system with a mix of high and low urgency tasks.

Understanding and utilizing such advanced data structures can be a game-changer in building efficient and fair systems.

Reference

[1] https://learn.microsoft.com/en-us/azure/architecture/patterns/priority-queue