EDF scheduler seems to be misfunctioning...

[alexpaschoaletto]

TL:DR

the Earliest Deadline First (EDF) scheduler does not seem to be updating the execution order as expected. A thread that starts with earliest deadline and gradually becomes the latest remains the first to execute nonetheless.

Expected - thread 2 executes before 1 because 2 has earliest deadline than 1.

Observed - thread 2 executes before 1 even having later deadline than 1.

Note that the start time of thread 1 is also AFTER thread 2 has finished.
It does not preempt thread 2.

Context

Let's suppose we have a simple demo code where two equal user threads execute periodically. Each thread has the values of relative deadline, ID and WCET defined in a struct:

edf_t task1 = {
    .id = 1,
    .rel_deadline_msec = 50,
    .wcet_msec = 5
};

edf_t task2 = {
    .id = 2,
    .rel_deadline_msec = 10,
    .wcet_msec = 1
};

As it can be seen, thread 2 has a much lower relative deadline, All the threads do after initial setup is increment a counter, busy wait for a specified amount of time, and print some metadata of their execution:

void thread_function(void *task_props, void *a2, void *a3){
    ...
    edf_t *task = (edf_t *) task_props;
    task->thread = k_current_get();
    k_msgq_init(&task->queue, buffer, sizeof(char), 10);
    printk("[ %d ] ready.\n", task->id);

    for(;;){
        k_msgq_get(&task->queue, &message, K_FOREVER);
        start = k_cycle_get_64();
        counter++;
        deadline = task->thread->base.prio_deadline;
        k_busy_wait(MSEC_TO_USEC(task->wcet_msec));
        end = k_cycle_get_64();

        print(task, counter, start, end, deadline);
    }
}

The threads are activated by a master timer, which periodically sends a message to each thread and therefore unlocks its cycle.
The trigger also updates the absolute deadlines of each thread right after activating them.

void trigger(edf_t *task){
    const char t = 1;
    int deadline = MSEC_TO_CYC(task->rel_deadline_msec);
    k_msgq_put(&task->queue, &t, K_NO_WAIT);
    k_thread_deadline_set(task->thread, deadline);
}

void trigger_all(struct k_timer *timer){
    printk("\n");
    trigger(&task1);
    trigger(&task2);
    grow(&task2, 10);        // just adds +10ms to the task deadline and wcet
}

So both threads are triggered at almost exactly the same time. Finally, at each activation, thread 2 gains +10ms of relative deadline and therefore gradually loses its priority to the eyes of the EDF. If it starts with 10ms, then 20ms, then 30ms... until it becomes greater than thread 1's deadline of 50ms. Right?

Yes. But that does not seem to be reflected on the execution order. Here's the actual log observed (click to enlarge):

Values in hardware cycles.
Thread 2 deadline's surpasses thread 1 on the 5th iteration, but thread 1 continues being the second to run even after that. Is there anything I'm missing here, or is the EDF scheduler actually failing to run as expected?

[alexpaschoaletto]

The full code if anyone wishes to try out:

#include <zephyr/kernel.h>

/*
	Remember that for "pure" EDF results, all
	user threads must have the same static priority.
	That happens because EDF will be a tie-breaker
	among two or more ready tasks of the same static
	priority. An arbitrary positive number is chosen here.
*/

#define EDF_PRIORITY            5
#define INACTIVE                -1
#define MSEC_TO_CYC(msec)       ((msec * CONFIG_SYS_CLOCK_HW_CYCLES_PER_SEC) / MSEC_PER_SEC)
#define MSEC_TO_USEC(msec)      (msec * 1000)

typedef struct {
    int id;
    int32_t rel_deadline_msec;
    int32_t period_msec;
    uint32_t wcet_msec;
    k_tid_t thread;
    struct k_msgq queue;
    struct k_timer timer;
} edf_t;


edf_t task1 = {
	.id = 1,
	.rel_deadline_msec = 50,
	.wcet_msec = 5
};


edf_t task2 = {
	.id = 2,
	.rel_deadline_msec = 10,
	.wcet_msec = 1
};


void grow(edf_t *task, int32_t amount_msec){
	task->wcet_msec += amount_msec;
	task->rel_deadline_msec += amount_msec;
}


void trigger(edf_t *task){
	const char t = 1;
	int deadline = MSEC_TO_CYC(task->rel_deadline_msec);
	k_msgq_put(&task->queue, &t, K_NO_WAIT);
	k_thread_deadline_set(task->thread, deadline);
}


void trigger_all(struct k_timer *timer){
	printk("\n");
	trigger(&task1);
	trigger(&task2);
	grow(&task2, 10);
}


void thread_function(void *task_props, void *a2, void *a3){
	char buffer[10];
	char message;
	int counter = 0;
	uint32_t deadline = 0;
	uint64_t start = 0;
	uint64_t end = 0;

	edf_t *task = (edf_t *) task_props;
	task->thread = k_current_get();

	k_msgq_init(&task->queue, buffer, sizeof(char), 10);
	printk("[ %d ] ready.\n", task->id);

	for(;;){
		/*
			The periodic thread has no period, ironically.
			What makes it periodic is that it has a timer
			associated with it that regularly sends new
			messages to the thread queue (e.g. every two
			seconds).
		*/
		k_msgq_get(&task->queue, &message, K_FOREVER);
		start = k_cycle_get_64();
		counter++;
		deadline = task->thread->base.prio_deadline;
		k_busy_wait(MSEC_TO_USEC(task->wcet_msec));
		end = k_cycle_get_64();
		printk("[ %d ] %d \tstart %llu\t end %llu\t dead %u\n", task->id, counter, start, end, deadline);
	}
}


K_THREAD_DEFINE(
	task1_thread, 2048,
	thread_function,
	&task1, NULL, NULL,
	EDF_PRIORITY, 0, INACTIVE
);


K_THREAD_DEFINE(
	task2_thread, 2048,
	thread_function,
	&task2, NULL, NULL,
	EDF_PRIORITY, 0, INACTIVE
);


K_TIMER_DEFINE(master_timer, trigger_all, NULL);

int main(void){
    k_sleep(K_SECONDS(1));
    printk("\nexecuting on: %s\n\n", CONFIG_BOARD_TARGET);

	k_thread_start(task1_thread);
	k_thread_start(task2_thread);

	k_timer_start(&master_timer, K_SECONDS(1), K_SECONDS(2));
	return 0;
}