Introducing
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
6
Thank you!
some threads make progress
not necessarily all
progress for continually-enabled calls
method calls
threads
objects
Progress = method call completes
Every thread eventually makes progress
Progress condition is per-method
Progress Soup
every process given an infinite number of steps
classic scheduler for locking ...
A Periodic Table
of Progress
Applications
Conclusions
every thread that acquires a lock eventually releases it
deadlock-free = min fair progress
starvation-free = max fair progress
Why even mention locks?
Some thread eventually acquires each lock
Every thread eventually acquires each lock
clash-freedom
like Einsteinium:
- fills gap
- does not occur in Nature
- no commercial value
min progress for isolating schedules
"Oblivious" fair scheduler: starvation-free spinlocks WHP
"Helping" makes lock-free algorithms wait-free
exponential backoff makes schedulers isolating
Oblivious: does not "persecute" any thread
Timeliness: bounded delays?
Statistical/probabilistic guarantees:
bad executions rare
arbitrary delays, including unbounded ....
classic multicore model
some process makes progress no matter what
every process makes progress, no matter what
Every thread that takes enough steps in isolation makes progress
for all k > 0,
every thread that does not halt
takes at least k steps by itself