Each thread can be thought of as a binary value that is either 0 (or 1) if the thread is not in the critical section and 1 (or 0) if it is. An n-thread computation can then be represented by an n-bit binary number, where bit i represents the value associated with the ith thread. For example, the all-zeros binary number represents the state in which no thread is in the critical section, and the all-ones binary number represents the state in which all threads are in the critical section (not a happy state to be in).
An n-bit binary number can represent 2n possible numbers, and the associated state machine would have the same number of states.
This page last modified on 12 August 2003.