S4CH/completely-fair-scheduler

CFS is an implementation of a well-studied, classic scheduling algorithm called weighted fair queuing and I implemented it in rust

Completely Fair Scheduler

You can get idea about the CFS on Wikipedia

Implementation and Usage

• This implementation of CFS is inspired by the Linux kernel but with differences in specifics of its functioning. The scheduler requires properties such as weight, maximum allocated CPU time, CPU burst length, and I/O burst length to be determined for each task before it runs. In the actual scheduler, these properties are determined by the kernel at the birth of the task.

• In this implementation, tasks are born in a separate thread and fed into the ready queue through a born queue The born queue is a priority-based queue, where the priority is set according to the task's birth time, so that the tasks are continuously added to the ready queue in order of their creation.

• The running of the scheduler takes place in a separate thread, which waits for the next systick, a tick of the internal (virtual) clock. When the tick is received, the running event pops the highest priority task from the ready queue and lets it run on the CPU. After the task finishes its CPU burst, it is placed in the idle queue, which is a simple FIFO queue. The task then runs one iteration of its I/O burst before being put back into the ready queue or placed at the back of the idle queue.

• To run the scheduler, you can generate a sequence of random tasks using python3 by running python3 generate_tasks.py. This will write the necessary task characteristics to a tasks.txt file, which is then read by the main function in the Rust program to generate the born tasks. To run the Rust program, execute cargo run if you have cargo installed.

Credits

The real credit goes to Jackson Isenberg