Can someone explain what "assuming lock acquisition is implemented in O(1) manner" means? Are there (reasonable) cases where it wouldn't be?
Also, the "serialization" in the second bullet is referring to the communication between processors, right?
I guess there could be lock implementations whose complexity depends on the number of waiting threads, although I can't think of any.
@temmie, I think the latency of acquiring the lock is mentioned in this class in previous slides. The latency depends on the implementation of the lock, for example, if you use test and test and set, then the latency will be longer than simply using test and set, since another read operation is needed to acquire the lock. For implementation of using the delaying method, I think the latency would be even longer.