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 ?
}
RR Scheduler
- Giovanni
- Site Admin
- Posts: 14455
- Joined: Wed May 27, 2009 8:48 am
- Location: Salerno, Italy
- Has thanked: 1076 times
- Been thanked: 922 times
- Contact:
Re: RR Scheduler
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
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
Re: RR Scheduler
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
}
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
}
- Giovanni
- Site Admin
- Posts: 14455
- Joined: Wed May 27, 2009 8:48 am
- Location: Salerno, Italy
- Has thanked: 1076 times
- Been thanked: 922 times
- Contact:
Re: RR Scheduler
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
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
Re: RR Scheduler
If i change binary tree to binary heap i will have O(1) for get max and min. Will be this easier to implement ?
- Giovanni
- Site Admin
- Posts: 14455
- Joined: Wed May 27, 2009 8:48 am
- Location: Salerno, Italy
- Has thanked: 1076 times
- Been thanked: 922 times
- Contact:
Re: RR Scheduler
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
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
Re: RR Scheduler
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.
- Giovanni
- Site Admin
- Posts: 14455
- Joined: Wed May 27, 2009 8:48 am
- Location: Salerno, Italy
- Has thanked: 1076 times
- Been thanked: 922 times
- Contact:
Re: RR Scheduler
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.
}
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.
}
- Giovanni
- Site Admin
- Posts: 14455
- Joined: Wed May 27, 2009 8:48 am
- Location: Salerno, Italy
- Has thanked: 1076 times
- Been thanked: 922 times
- Contact:
Re: RR Scheduler
It is possible, it depends on how much effort are you willing to put into it.
Giovanni
Giovanni
Who is online
Users browsing this forum: No registered users and 9 guests