Profiling shows about 20 seconds spent between ping() and run(), as evident in the captured profile (YJP 2014 EAP) during a 100 second run.

At first glance, two things jump out: lock should be final and 'starving' should be volatile.

Looking at the logic, I have to wonder if java.util.concurrent.CyclicBarrier wouldn't be more appropriate as opposed to lock:

0) initialize barrier, parties=2
1) run: when starved, set atomically starving to true, barrier.await()
2) ping: check starved, if it's true, barrier.await()
3) run: upon leaving barrier, set starting to false