next up previous contents
Next: Concluding Remarks Up: Related Work Previous: Hardware Support

Operating System Support

Allemany and Felten [1] reduce useless concurrency   with OS support to provide the same functionality that we support in hardware using cache-based advisory locking. The method is a variation on the technique of Bershad discussed in Section 6.1. They propose incrementing a counter of active threads on entrance to a critical section, and decrementing on exit. The OS decrements the counter while an active thread is switched out. Processes must wait until the count of active threads is below some threshold (1, in our case) before being allowed to proceed. Delayed processes do not excessively delay other processes because the count is decremented by the OS.

These techniques appear valuable for systems without hardware support for advisory locking and in fact their approach works better than ours under high contention. However, hardware advisory locking and conditional load are more resilient to processor failure and have lower overhead in the low-contention case. As with hardware versus software DCAS, the hardware implementation is simple and fast; further measurements are required to determine if it is compellingly so.

In other work, Israeli and Rappaport [15] implement n-way atomic Compare and Swap and n-way LL/SC for P processors out of single CAS. However, this approach is primarily of theoretical interest because it requires a large amount of space (at least P bits for every word in the shared memory), requires words to be P bits wide, takes to execute, and only interlocks against other multi-word atomic instructions. Anderson and Moir [2] improve upon this, requiring only realistic sized words, time, but still requiring a prohibitively large amount of space.

Finally, Software Transactional Memory [19] is an attempt to implement Transactional Memory in software, depending only on LL/ SC . Unfortunately, their implementation will not work correctly on existing implementations of LL/ SC because their code ( AcquireOwnerships) depends on the ability to interleave two outstanding LL/SC's simultaneously, which is not supported. The LLP/ SCP instructions we proposed would enable their techniques to be used to provide software transactional memory for multiple, independently chosen, words of memory. However, the space and computational overhead in their implementation is excessive for general usegif. Moreover, the STM operations are only atomic with respect to other STM operations, and not to general reads and writes.



next up previous contents
Next: Concluding Remarks Up: Related Work Previous: Hardware Support



Michael Greenwald
Thu Sep 19 12:18:20 PDT 1996