search

arulbose / rosx

Real time OS Xperiment
GNU General Public License v3.0
5 stars 1 forks source link

Implement efficient algorithm to add and remove task from run queue #24

Open arulbose opened 6 years ago

arulbose commented 6 years ago

Description: In file: kernel/task.c the current implementation of __add_to_ready_q() and __remove_from_ready_q() will scale poorly when the number of thread grows. It has to be re-written with an efficient algorithm with O(log n) scheduling in mind

arulbose commented 6 years ago

Update: Added red-black tree Algo support to be used by rose scheduler which gives the possibility to have O(log(n)) time for searching/adding/deleting of task. The rbtree support source code has been ported from Linux source. The files are available in rose/lib/rbtree.c. The idea is to make rose scheduler configurable to support both Linear(O(n)) search/add/delete(which is already present) and O(log(n)) using rbtree.

Pending task:
To add code for the rose task management code to use functions in rbtree.c.