Loading...

​​Rayon Scheduler Notes 2020.01.22

​​Branch latch-target-thread-2

​​

​​Goals

• ​​when you a thread is blocked on some other task completing, 

• ​​and that task completes,

• ​​wake up just that one thread

• ​​when new work arrives,

• ​​start a proportional number of workers in response

​​

​​Key data structures

• ​​“Counters”

• ​​Jobs/Sleepy counter — a mechanism for detecting when new work is published

• ​​sleepy counter gets incremented when a thread gets “sleepy”

• ​​jobs counter gets “synchronized” with the sleepy counter  when new work is published

• ​​if the two counters are equal, nobody has gotten sleepy since work was published

• ​​but if they are not, when new work is published, they are made equal

• ​​Idle threads — is blocked on some latch and looking for work

• ​​incremented when you are searching for work

• ​​decremented when you find it

• ​​Sleeping threads — is asleep

• ​​incremented when you go to sleep

• ​​decremented by the thread that wakes you 

• ​​Question: uses AtomicU64​, do we care about portability concerns?

• ​​maybe? some architectures we might care about do care

• ​​could plausibly scale back to AtomicU32​ by using fewer bits for the “num threads” match

• ​​requires Rust 1.34 too. but if we scale back to 32-bit for smaller targets anyway, might as well use AtomicUsize​

• ​​
  

• ​​worker sleep states

• ​​mutex per worker

• ​​and a boolean that is set to true when the worker goes to sleep

• ​​set to false when the worker is woken up (by the one who wakes them up)

• ​​latches

• ​​go from UNSET to SET

• ​​UNSET — the event has not hapenned, the owning thread is awake

• ​​SLEEPY — the owning thread is going to sleep (but hasn’t yet)

• ​​SLEEPING — the owning thread is blocked and must be awoken when the latch is set

• ​​SET — the latch has been set, event has happened

• ​​each latch is created by some thread that is waiting for that event

• ​​various kinds of latches, they all wrap a CoreLatch

​​

​​Events and Algorithms

• ​​What happens when a thread goes idle?

• ​​main routine: wait_until​ signals that we are entering the idle state

• ​​join​ — 

• ​​first drains the local deque and then calls wait_until​

• ​​scope​ — 

• ​​calls wait_until​ right away, even if local deque has tasks

• ​​used in firefox, the TSP benchmark

• ​​behavior of wait_until: