ChibiOS Free Embedded RTOS

Hi
I added another data structure to scheduler(to keep threads in binary tree). But idk how put new thread in tree.
I added lines in code.
chsystypes.h
typedef struct ch_threads_tree threads_tree_t;

chschd.h
struct ch_threads_tree {
thread_t *left;
thread_t *right;
};
struct ch_thread {
threads_tree_t tree;
};
struct ch_ready_list {
threads_tree_t tree;
};
static inline void tree_init(threads_tree_t *thp){
thp->left = NULL;
thp->right = NULL;
}

chthreads.h
thread_t *_thread_init(thread_t *tp, const char *name, tprio_t prio) {
tp->tree.left = NULL;
tp->tree.right = NULL;
};

chschd.c
void _scheduler_init(void) {
tree_init(&ch.rlist.tree);
}
thread_t *chSchReadyI(thread_t *tp) {
thread_t *cp2;
cp2 = (thread_t *)&ch.rlist.tree;
//cp2 contains random data. But in cp there is thread. Where os add first thread to ready queue ?
}

Hi,

Interesting experiment however the worst case of trees is no better than an ordered list, in realtime systems what really matter is the worst case. I doubt it would be a more efficient solution.

Giovanni

I know that ordered list is better solution for that problem, but I'm trying to implement RR with tree (school project)and compare both methods. Now i stuck:
thread_t *chSchReadyI(thread_t *tp) {
thread_t *cp;
thread_t *cp2;

cp2 = (thread_t *)&ch.rlist.tree; //idk why cp2 do not contain threads
cp = (thread_t *)&ch.rlist.queue;//and cp contain threads
}

Hi,

Understood, it will not be that simple, there is a strong assumption for the ready threads to be in a double linked list, see the timeout callback in chSchGoSleepTimeout for example.

Extraction of higher priority thread is another problem, in the list it is always the first element, in the tree it is not and it involves a search.

My suggestion is that you disable everything in chconf.h and restrict your changes to a minimal system.

Giovanni

If i change binary tree to binary heap i will have O(1) for get max and min. Will be this easier to implement ?

Hi,

Algorithm complexity is not related to complexity of changes required

It will be challenging both ways, there is an assumptions for queues deeply in the code.

Main difficulty is that the first two fields of the thread_t structure are assumed to be a queue element and this is required in other places like semaphores, mutextes etc.

I would classify the change as "hard".

Giovanni

Thank you very much for your answers. Is there any easy way to change scheduler algorithm ? I have school project to change scheduler algorithm and compare them.

I thought I already answered: there is no easy way.

Giovanni

Hi,
I thought that if i change priority with deadline, it will be possible to implement EDF ?
I will sort task (in ascending order) by deadline and run them just like in actual RR.
I'm trying to add deadline in data structure.

chschd.h
struct ch_thread{
systime_t dl;
}

struct ch_ready_list{
systime_t dl;
}

But when i inicialize deadline in _scheduler_init it do not inicialize.

_scheduler_init(){
ch.rlist.dl = 50;
}

chSchReadyI(thread_t *tp){
//here i do not get 50 but some random big number.
}

It is possible, it depends on how much effort are you willing to put into it.

Giovanni