Design an algorithm on red black trees

Completed Posted 7 years ago Paid on delivery
Completed Paid on delivery

Task Scheduler using Red-Black Trees

Red-black trees are very powerful data structures and find numerous applications.

For eg, TreeMap in Java/C++ STL is usually implemented using it. In this project,

you will implement another high profile application - a simplified version of Linux’s

scheduling algorithm - Completely Fair Scheduler(CFS).

Here is the intuition behind the scheduler. The primary objective is to ensure

that each task that is currently active has access to CPU as fairly as possible. So we

associate an unfairness score with each task. The scheduler maintains the list of active

tasks as a red-black tree and the nodes are ordered in descending order of unfairness

hence the task that was treated most unfairly is the left most node. The scheduler

runs a task till it is no longer the most unfairly treated. Please see the references for

additional details. Of course, you have to insert a node for a task when it arrives and

delete it once it is completed.

Input/Output format: Your input will be a single file of the following format.

The first line contains the total number of tasks and the number of time periods to

run the algorithm separated by a space. It is followed by a list of tasks. Each task

will be triple <task id, start time, number of seconds it takes to complete>. For eg

<20, 10, 100>means that task-20 arrives at 10th time unit of simulation and requires

100 seconds in the CPU to complete (not necessarily consecutively).

The output will contain two things:

1. Given some time unit (say time unit 100), the snapshot of the red-black tree including

the tasks, their color and their unfairness values. Do an in-order traversal

so that the tasks are ordered based on their unfairness.

2. The list of tasks that ran during the time period of the simulation. For eg,

suppose the simulation ran for 5 time units <1,2,3,2,2>means that task 1 was

run by the scheduler at the start. Then task-2 ran for 1 time-unit followed by

task-3 and then task-2 ran again for 2 consecutive time periods.

Evaluation:

1. Compare this implementation with that of a heap (you can use a priority queue

from existing library).

2. How fair is the scheduler actually?

3. Does this scheduler maximizes throughput?

References: The algorithm for this scheduler is quite simple once you get the red

black tree working. For further details see:

1. [url removed, login to view]~eschulte/classes/cs587/data/bfs-v-cfs_groves-knockel-schulte.

pdf

2. [url removed, login to view] and the references

therein

3. [url removed, login to view]

C Programming Java Python

Project ID: #10367497

About the project

9 proposals Remote project Active 7 years ago

Awarded to:

coolomar1998

Feel free to contact [login to view URL] is not any issue as well. we can manage each and everything via private messages.

$30 USD in 1 day
(65 Reviews)
5.2

9 freelancers are bidding on average $46 for this job

rajeshpal007

Hello, I can do this. I have been programming in c, c++ and Linux for last 8+ years. I have developed many complex software's involving System Programming, Network Programming , Socket Programming,, Shared Memor More

$50 USD in 3 days
(17 Reviews)
4.6
ZhangDaLong

Dear client, how are you? I am a C++ programmer and mathematician. Please check my "Profile & Work List" and consider hiring me. Looking forward to your response. Thanks.

$100 USD in 1 day
(19 Reviews)
4.3
apmtc11

Hi we are team of developers and we are looking for a chance to make our self best in this. because we know we are the best with new ideas and we can code anything , we are new on freelance and very hungry for work eve More

$25 USD in 1 day
(0 Reviews)
0.0
uuusi

Hello there , can make your project done very efficiently and also can deliver you within your required time frame. Hope to see your message in my inbox. Thanks :)

$20 USD in 1 day
(0 Reviews)
0.0
CodeTurtle

A proposal has not yet been provided

$24 USD in 1 day
(0 Reviews)
0.0