Processor threads in a multi-processor system can concurrently lock multiple semaphores by providing a lock command which includes the semaphore value and a semaphore number. Each processor is allocated two or more addressable semaphore stores, each of which include a multi-bit field identifying the requested semaphore and a one bit field identifying the locked status of the requested semaphore. The semaphore number determines which of the allocated semaphore stores are to be used for processing the lock command.