Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Convert rust_task_thread::running_tasks list to a queue #2028

Closed
brson opened this issue Mar 19, 2012 · 9 comments
Closed

Convert rust_task_thread::running_tasks list to a queue #2028

brson opened this issue Mar 19, 2012 · 9 comments
Assignees
Labels
A-runtime Area: std's runtime and "pre-main" init for handling backtraces, unwinds, stack overflows I-slow Issue: Problems and improvements with respect to performance of generated code.

Comments

@brson
Copy link
Contributor

brson commented Mar 19, 2012

Right now it is a list, and scheduling a task involves using a the rng to pick a task and blocking involves removing it from the middle of the list. It would be more efficient (and probably more fair) as a queue. Sort of depends on #1189 and on #2027 in that it would be nice to get rid of the blocked_tasks list as well.

@jamorton
Copy link
Contributor

If such a queue was implemented would it be acceptable to not use random indices to schedule tasks?

More generally, I'm wondering why tasks are put in random threads and tasks are selected randomly. What's wrong with a simple round robin?

@brson
Copy link
Contributor Author

brson commented Mar 29, 2012

Yes, part of the goal of switching to the queue is to get rid of the random number generator. I want to switch to round robin thread selection and the queue for task selection (which is effectively round robin).

@brson
Copy link
Contributor Author

brson commented Mar 29, 2012

Switching to round robin for thread selection is a trivial change that would be easy to do right now.

@brson
Copy link
Contributor Author

brson commented Apr 2, 2012

@graydon suggested on IRC that using a queue could result in some deadlock situations when contending for external resources like file handles and that enforcing some nondeterminism is necessary.

If we had timeslice accounting and enough preemption points then we would presumably use a priority queue based on which tasks deserve more time, and that would also avoid the problem solved by the rng.

@jamorton
Copy link
Contributor

jamorton commented Apr 2, 2012

I'm just going to start working on a time slice pqueue branch and see how it turns out

@brson
Copy link
Contributor Author

brson commented Apr 2, 2012

Just so you know, the compiler doesn't generate any preemption points yet, so the only time that tasks yield is when they explicitly call yield.

@jamorton
Copy link
Contributor

jamorton commented Apr 2, 2012

oh, well then, maybe not yet.

@graydon
Copy link
Contributor

graydon commented Apr 3, 2012

I talked about this more with some colleagues here and did a bit more background reading, and I'm still most comfortable with the existing PRNG-vector scheme. Reasons are as follows:

  • Basic efficiency: swap-to-end-and-decrement is just fast, but vector is memory-dense, no extra pointers.
  • I think lockless version will work ok if we go there; CAS on a randomly-chosen cell with "try again" when the cell is null. Take a lock only if the vector needs resizing or is at a lifecycle event (scheduler shutdown say).
  • Randomizing schedule means preserving -- in fact, promoting -- the illusion of uniform pseudo-parallelism that's the default assumption when writing concurrent software. That is, a user's only safe bet about the schedule they get from an OS thread scheduler is "random" (as threads might run truly-concurrently, or be time-sliced under unpredictable policy), so if we pick a particular deterministic schedule, we're undermining that assumption, which can have at least two unwanted effects:
    • We might hide races in user code. So code that "breaks" on threads might "work" on tasks (by appearing race-free when it's not).
    • We might change analytic assumptions in user code such as average-vs-worst-case complexity or eventual-success on intentionally racey code. These assumptions might not be "right" in the sense that a fixed schedule is legal behavior from a thread scheduler, but it's very improbable; such assumptions are safe to make about threads. So code that "works" on threads might "break" on tasks (by degrading to worst-case or livelocking or such).

Basically I want our scheduler to behave -- to outside observers with no reason to believe otherwise -- as much like "running in 1:1 mode" as possible. I want users to face no concurrency "surprises" when changing between 1:1 and M:N modes. Our scheduler is only there to compensate for the fact that running 100,000 threads is too expensive on OSX or windows. If a user really wants a more interesting schedule, they should have to request it: make a separate scheduler, inject some set of threads into it, and ask the OS to run those threads in a particular scheduling model. The OS can provide much finer-grained, faster and more-robust scheduling than we can.

@ghost ghost assigned brson Apr 19, 2012
@brson
Copy link
Contributor Author

brson commented May 17, 2012

We're not doing this. Closing.

@brson brson closed this as completed May 17, 2012
celinval added a commit to celinval/rust-dev that referenced this issue Jun 4, 2024
We should probably only use info for stats, major compilation steps, and summary of some operations. This reduces the compiler verbosity quite a bit when user runs Kani with --verbose.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-runtime Area: std's runtime and "pre-main" init for handling backtraces, unwinds, stack overflows I-slow Issue: Problems and improvements with respect to performance of generated code.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants