p-ranav/psched

Priority-based Task Scheduling for Modern C++

psched

psched is a lightweight library that provides a priority-based task scheduler for modern C++.

• The psched scheduler manages an array of concurrent queues, each queue assigned a priority-level
• A task, when scheduled, is enqueued onto one of queues based on the task's priority
• A pool of threads executes ready tasks, starting with the highest priority
• The priority of starving tasks is modulated based on the age of the task

Getting Started

Consider the task set below. There are three periodic tasks: a, b and c.

Task	Period (ms)	Burst Time (ms)	Priority
a	250	130	0 (Lowest)
b	500	390	1
c	1000	560	2 (Highest)

Here, burst time refers to the amount of time required by the task for executing on CPU.

Create a PriorityScheduler

First, let's create a scheduler:

#include <iostream>
#include <psched/priority_scheduler.h>
using namespace psched;

int main() {
  PriorityScheduler<threads<3>, 
                    queues<3, maintain_size<100, discard::oldest_task>>,
                    aging_policy<
                        task_starvation_after<std::chrono::milliseconds, 250>, 
                        increment_priority_by<1>
                    >>
      scheduler;

Create a Task

Create the first task, Task a like below. The task "performs work" for 130ms. The post-completion callback, called when the task has completed, can be used to study the temporal behavior of the task, e.g., waiting time, burst time, and turnaround time.

 Task a(
     // Task action
     [] { std::this_thread::sleep_for(std::chrono::milliseconds(130)); },
 
     // Task post-completion callback
     [](const TaskStats &stats) {
       std::cout << "[Task a] ";
       std::cout << "Waiting time = " << stats.waiting_time() << "ms; ";
       std::cout << "Burst time = " << stats.burst_time() << "ms; ";
       std::cout << "Turnaround time = " << stats.turnaround_time() << "ms\n";
     }
 );

Schedule the task

Now, we can write a simple periodic timer that schedules this task at priority<0>:

  auto timer_a = std::thread([&scheduler, &a]() {
    while (true) {
    
      // Schedule the task
      scheduler.schedule<priority<0>>(a);
      
      // Sleep for 250ms and repeat
      std::this_thread::sleep_for(std::chrono::milliseconds(250));
    }
  });

Schedule more tasks

We can repeat the above code for tasks b and c:

  Task b(
      // Task action
      [] { std::this_thread::sleep_for(std::chrono::milliseconds(390)); },
      // Task post-completion callback
      [](const TaskStats &stats) {
        std::cout << "[Task b] ";
        std::cout << "Waiting time = " << stats.waiting_time() << "ms; ";
        std::cout << "Burst time = " << stats.burst_time() << "ms; ";
        std::cout << "Turnaround time = " << stats.turnaround_time() << "ms\n";
      });

  auto timer_b = std::thread([&scheduler, &b]() {
    while (true) {
      scheduler.schedule<priority<1>>(b);
      std::this_thread::sleep_for(std::chrono::milliseconds(500));
    }
  });

  Task c(
      // Task action
      [] { std::this_thread::sleep_for(std::chrono::milliseconds(560)); },
      // Task post-completion callback
      [](const TaskStats &stats) {
        std::cout << "[Task c] ";
        std::cout << "Waiting time = " << stats.waiting_time() << "ms; ";
        std::cout << "Burst time = " << stats.burst_time() << "ms; ";
        std::cout << "Turnaround time = " << stats.turnaround_time() << "ms\n";
      });

  auto timer_c = std::thread([&scheduler, &c]() {
    while (true) {
      scheduler.schedule<priority<2>>(c);
      std::this_thread::sleep_for(std::chrono::milliseconds(1000));
    }
  });

  timer_a.join();
  timer_b.join();
  timer_c.join();
}

Running this sample may yield the following output:

./multiple_periodic_tasks
[Task a] Waiting time = 0ms; Burst time = 133ms; Turnaround time = 133ms
[Task c] Waiting time = 0ms; Burst time = 563ms; Turnaround time = 563ms
[Task b] Waiting time = 0ms; Burst time = 395ms; Turnaround time = 395ms
[Task a] Waiting time = 60ms; Burst time = 134ms; Turnaround time = 194ms
[Task a] Waiting time = 0ms; Burst time = 131ms; Turnaround time = 131ms
[Task b] Waiting time = 0ms; Burst time = 390ms; Turnaround time = 390ms
[Task a] Waiting time = 3ms; Burst time = 135ms; Turnaround time = 139ms
[Task a] Waiting time = 0ms; Burst time = 132ms; Turnaround time = 132ms
[Task b] Waiting time = 8ms; Burst time = 393ms; Turnaround time = 402ms
[Task c] Waiting time = 0ms; Burst time = 561ms; Turnaround time = 561ms
[Task a] Waiting time = 6ms; Burst time = 133ms; Turnaround time = 139ms
[Task b] Waiting time = [Task a] Waiting time = 0ms; Burst time = 393ms; Turnaround time = 393ms
0ms; Burst time = 133ms; Turnaround time = 133ms
[Task a] Waiting time = 11ms; Burst time = 134ms; Turnaround time = 145ms
[Task a] Waiting time = 0ms; Burst time = 134ms; Turnaround time = 134ms
[Task b] Waiting time = 11ms; Burst time = 394ms; Turnaround time = 405ms
[Task c] Waiting time = 0ms; Burst time = 560ms; Turnaround time = 560ms
[Task a] Waiting time = 7ms; Burst time = 132ms; Turnaround time = 139ms
[Task b] Waiting time = 0ms; Burst time = 390ms; Turnaround time = 390ms
[Task a] Waiting time = 0ms; Burst time = 130ms; Turnaround time = 130ms
[Task a] Waiting time = 17ms; Burst time = 130ms; Turnaround time = 148ms
[Task a] Waiting time = 0ms; Burst time = 131ms; Turnaround time = 131ms
[Task b] Waiting time = 10ms; Burst time = 390ms; Turnaround time = 401ms
[Task c] Waiting time = 0ms; Burst time = 560ms; Turnaround time = 560ms

Building Samples

git clone https://github.com/p-ranav/psched
cd psched
mkdir build && cd build
cmake -DPSCHED_SAMPLES=ON ..
make

Generating Single Header

python3 utils/amalgamate/amalgamate.py -c single_include.json -s .

Contributing

Contributions are welcome, have a look at the CONTRIBUTING.md document for more information.

License

The project is available under the MIT license.

psched's Issues

Lambda capture not used

When I compile with cmake I get include/psched/priority_scheduler.h:83:33: warning: lambda capture 'n' is not used [-Wunused-lambda-capture], but when I import to other projects this warning becomes an error.

Do we need n in the lambda capture?

Full error output:
In file included from psched/samples/multiple_periodic_tasks.cpp:2: psched/include/psched/priority_scheduler.h:83:33: warning: lambda capture 'n' is not used [-Wunused-lambda-capture] threads_.emplace_back([&, n] { run(); });