Implement work stealing in the Rust task scheduler

[brson]

The Rust task scheduler is quite primitive right now. One particular deficiency is that it does not ever migrate tasks between scheduler threads, resulting in threads often being under-utilized. We would like to resolve this using a 'work stealing' algorithm, where threads with no work ask other threads to give them tasks to run. This hacking is low-level, performance-critical and parallel.

See also: 3095, the cilk papers on work stealing

[vib67]

Hi I am interested in this project can i take this up?

[brson]

@vib67 yes!

[vib67]

Thanks. Will start working on it from tomorrow. I will ask for help if stuck anywhere.

[brson]

Great! You may want to check in on IRC, #rust on irc.mozilla.org. There are a lot of people there that can help with general language issues.

[Yoric]

Issue assigned to @vib67 .

[brson]

@vib67 The Rust scheduler is one of the few parts of Rust written in C++, so most, if not all, the code for this project will be in C++, not Rust. Porting the scheduler to Rust is something we want to do in the future though.

Some entry points:

rust_task.h - The definition of a Rust task, which essentially consists of a linked list of stack segments, saved context, some heap bookkeeping, and quite a bit of synchronization code for various purposes.

rust_sched_loop.h - A single scheduler threaad, it executes the function run_single_turn repeatedly until told to exit.

Each loop maintains a list of tasks that it is responsible for. Tasks are scheduled by saving the current registers and loading the registers previously saved inside the task structure (a context switch). Tasks are deschudeled when the task calls yield() by doing a context switch back to the scheduler.

This project is about moving tasks between instances of rust_sched_loop.

rust_scheduler.h - The scheduler itself mostly just starts and stops rust_sched_loop.

libcore/task - The Rust interface to tasks and schedulers, including the public API, the internal task spawning code, and the declaration of the native interface

Once you've got your bearings I suggest outlining your plans on the relevant Rust bug ticket so that those interested might review the design.

[Yoric]

By the way, @vib67 , just to keep track: which university are you from?

[vib67]

Hi, Thanks for sharing the information. I am from Aalto.

[vib67]

Hi I am getting the following problem during the compilation of rust code, Kindly help how to get or build /llvm-mc /rust/code/rust/llvm/i686-unknown-linux-gnu/Release+Asserts/bin/llvm-mc: not found make: *\ [rt/i686-unknown-linux-gnu/arch/i386/_context.o] Error 127

[vib67]

It seems to be the error during the download of the source.some of the directory were not properly fetched.

[brson]

@vib67 Glad you got it sorted out.

[brson]

Closing this as we are working on it now.