implement work-steal schedule

[dovahcrow]

this is a meta issue

[dovahcrow]

ref: http://supertech.csail.mit.edu/papers/steal.pdf

[zonyitoo]

Simple implementation of BusyLeaves

#![feature(std_misc)]

extern crate coroutine;

use std::thread;
use std::rt::util::default_sched_threads;

use coroutine::mpmc_bounded_queue::Queue;
use coroutine::coroutine::{Coroutine, State};

fn main() {
    const MAX_MESSAGES_NUM: usize = 1000;
    let n_threads = default_sched_threads();

    let queue = Queue::with_capacity(n_threads * MAX_MESSAGES_NUM);

    let coro = Coroutine::spawn(move || {
        let mut count = 0;
        loop {
            println!("Counting {} in {:?}", count, thread::current());
            count += 1;

            Coroutine::sched();
        }
    });

    queue.push(coro);

    let mut threads = Vec::with_capacity(n_threads);
    for thread_id in 0..n_threads {
        let queue = queue.clone();
        let t = thread::Builder::new().name(format!("Thread {}", thread_id)).spawn(move || {
            loop {
                match queue.pop() {
                    Some(coro) => {
                        coro.resume().unwrap();

                        match coro.state() {
                            State::Suspended => {
                                queue.push(coro);
                            },
                            _ => {}
                        }
                    },
                    None => {}
                }
            }
        }).unwrap();

        threads.push(t);
    }

    for t in threads.into_iter() {
        t.join().unwrap();
    }
}

[zonyitoo]

Here comes the problem: what would happen if a Handle was added into the queue more than once? I think I should reconsider the design of APIs.

[zonyitoo]

In https://github.com/maciekgajewski/coroutines, Scheduler is a Singleton.

When the Scheduler was constructed, it will creates Processors, which actually are native threads with work queues.

When spawning a Coroutine, a Unique handler to the Coroutine may be created. Then the handler will be pushed into a queue owned by Scheduler, which means that the Scheduler owns all Coroutines.

When a Coroutine is ready, Scheduler::schedule may be called with a weak ref to the Coroutine, which actually adds it to a Processor's work queue or a global ready queue inside the Scheduler.

When a Processor is starving, it will ask the Scheduler for more work. Scheduler may tried to get some Coroutines from the global queue. If there is nothing left, let him wait.

When a Coroutine dies, it will tell its parent who spawns it (the Scheduler) to delete itself. All weak ref to the Coroutine will be invalid.

[zonyitoo]

maciekgajewski/corotines does not provide any mechanisms to ensure only one handler to a coroutine can be added into the ready list.

[zonyitoo]

In the original version of libgreen, they implement the work-stealing scheduler heavily rely on many lock-free queues.

Every Scheduler has its own work queue, which is a lock-free queue. This queue is a special type of mpmc queue but it provides multiple Stealers and one Worker. The Scheduler gets work from the queue with pop operation on the Worker, which has less overhead than getting data from Stealer. The other Schedulers have one copy of the Stealer. When the Scheduler is starving, it will call steal on every Stealers it records. If one of them succeed, it runs the coroutine immediately.

Scheduler is in thread local storage.

There are communication channels (mpsc queues) between Schedulers. They could send messages to other Schedulers.

spawn operation is nothing more than add the created coroutine to the Scheduler in current thread.