Least slack time (LST) or Least Laxity First (LLF)

llf.cpp

struct Task
{
    unsigned id;
    unsigned phase;
    unsigned period;
    unsigned execution_time;
    unsigned deadline;
    unsigned laxity;
    unsigned remaining_time;
    bool     is_done = false;
};

vector<unsigned> llf(vector<Task>& task_set, const unsigned hyper_period)
{
    vector<unsigned> schedule(hyper_period, 0);

    for (size_t frame = 0; frame < hyper_period; ++frame)
    {
        vector<Task> frame_tasks;
        for (auto& task : task_set) // Calculate laxity for all valid tasks
        {
            if (frame < task.phase) // skip
            {
                continue;
            }
            else
            {
                auto real_time = (frame - task.phase) % task.period;
                if (real_time == 0) // Reset at the beginning
                {
                    task.is_done        = false;
                    task.remaining_time = task.execution_time;
                }
                if (task.is_done)
                {
                    continue;
                }
                else
                {
                    task.laxity = task.deadline - real_time - task.remaining_time;
                    frame_tasks.emplace_back(task);
                }
            }
        }

        // Find the minimum laxity
        vector<Task> minimums;
        unsigned     min_laxity = UINT_MAX;
        for (const auto& task : frame_tasks)
        {
            if (task.laxity < min_laxity)
            {
                min_laxity = task.laxity;
                minimums   = { task };
            }
            else if (task.laxity == min_laxity) // Check if multiple tasks have minimum laxity
            {
                minimums.emplace_back(task);
            }
        }

        // Find the task to be scheduled
        if (minimums.size() == 0)             // There are no minimum tasks
        {
            schedule[frame] = 0;              // Nothing to schedule
        }
        else if (minimums.size() == 1)        // We found 1 minimum.
        {
            schedule[frame] = minimums[0].id; // That task will be scheduled.
        }
        else // We found more than 1 minimum.
        {
            bool scheduled = false;
            if (frame > 0)
            {
                auto it = find_if(minimums.begin(), minimums.end(), [&](const Task& task)-> bool {
                    return task.id == schedule[frame - 1];
                });
                if (it != minimums.end())                  // Previous task is among the minimum
                {
                    schedule[frame] = schedule[frame - 1]; // Continue scheduling previous task
                    scheduled       = true;
                }
            }
            if (!scheduled)                       // If previous task is not minimum anymore or this is the first frame
            {
                schedule[frame] = minimums[0].id; // Then pick a random one (here, the first one)
            }
        }
        
        // Reduce remaining time
        auto it = find_if(task_set.begin(), task_set.end(), [&](const Task& task) -> bool {
            return task.id == schedule[frame];
        });
        --it->remaining_time;
        if (it->remaining_time == 0)
        {
            it->is_done = true;
        }
    }

    return schedule;
}