Loading presentation...

Present Remotely

Send the link below via email or IM


Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.



"On the Nature of Progress"

Maurice Herlihy

on 19 February 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Progress

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