In multi-processor systems, several different processors can simultaneously use shared resources of a system, such as, for example, auxiliary devices belonging to the system. Such a situation involves parallel processes on the hardware level. On the software level, in turn, parallelism refers to a program or software, in which processes, which are run in parallel, deal with, for example, a common data structure to be maintained in a shared memory. In this case, the data structure represents a common resource in view of the software processes.
Although the implementation of the present invention is, as such, based on the hardware, its implementations are related, in a wider sense, to the parallelism of processes both on the hardware level and on the software level. The invention can thus be applied, for example, in so-called embedded systems, in which the implementation of a single process involves functions on both the hardware level and the software level in a seamless way.
A situation, in which two or more processes attempt to use the same common resource, is called a contention. Furthermore, a contention situation involves the concept of a critical region. In general, a critical region refers to such a part of the program code which must be run as an unbroken logical unit, i.e. an atomic operation.
The operation of operating systems in a contention situation should be foreseeable; in other words, they should have a way of processing the critical regions contained in the program code in a controlled manner. Operating systems, such as Linux and some Unix versions, which operate in a shared multi-processor environment, apply software kernel locks to secure that only one process at a time has access to a certain critical program code region. Linux applies two types of kernel locks: so-called spin locks and so-called semaphore locks.
The spin locks are simple software locks of one holder, which are actively polled by software until the lock is opened. The spin lock can be formed, for example, by a variable which is stored in a memory and whose status is tested by software. If the polling by a process requiring a resource gives 1 as the value for the variable, then the resource protected by the spin lock in question is already used by another process and the process requiring the resource will continue to poll the lock. When 0 is obtained as the value for the variable in the polling, the resource in question is thus detected to be vacant and the process requiring the resource will set 1 as the value for the variable of the lock and itself as the user of the critical region. When terminating the use of the resource, the process will exit the critical region and write 0 as the value of the variable of the lock again.
A software semaphore lock, in turn, may have several holders; in other words, there may be several “keyholes” in the semaphore lock, and the number of the keyholes is determined when the lock is initialized. Consequently, several processes may have access to the same resource protected by the semaphore lock. If the semaphore controlling the use of a given resource is not vacant, the process requiring the use of the resource will continue to poll the lock until a keyhole of the semaphore lock is released and the process has thus access to the resource protected by the lock. When the lock is busy, it is also possible to place a process requiring the use of the resource protected by the lock in a so-called reservation queue, from which reservation queue the process is woken up by the operating system when the lock is released. The operating system will detect the release of the lock by polling the lock. If the number of holders of the semaphore lock is initialized to one, the operation of the semaphore lock corresponds substantially to the operation of the spin lock.
The implementation of software spin locks and semaphore locks will typically require the use of atomic operations in the critical regions of the program code related to the control of the lock. In other words, the system must be capable of securing that no other process can modify the state of the lock while the first process is first polling the state of the lock and then changing the state of the lock to reserve the resource to its own use. Consequently, all the processors in the system, as well as the bus protocols connecting the processors with a memory, and other interfaces must support the atomic read/write sequence. However, this requirement is not fulfilled in all environments using parallel processes, wherein it restricts significantly the use of software locks in the management of parallel processes.
Furthermore, when software locks are used in multi-processor it is also necessary to determine the way of implementing the lock as well as its location in the (shared) memory space of the system. Moreover, a lock placed in the memory, that is, in practice, a given variable, cannot actively inform the process that the requested resource has been released for use. However, the process requiring the resource or the operating system itself must actively poll the state of the lock/variable in question to obtain this information, wherein the processor performing this task is tied to this task and cannot take care of other possible tasks while waiting for the release of the resource.
As to the prior art relating to software locks, U.S. Pat. No. 6,263,425 also discloses a hardware semaphore circuit, by means of which a semaphore lock can be implemented in a multi-processor environment. The aim of the solution described in this publication is to alleviate the requirements set for processors of the system in relation to atomic read/write sequences when using the semaphore lock.
The solution described in U.S. Pat. No. 6,263,425 is based on the use of a single-bit semaphore comprising, for each processor, a separate port through which the semaphore is used. With the value 0 of the single-bit semaphore, the resource in question is vacant, and correspondingly, the resource is busy with the semaphore value 1. In a contention situation, the operation of this semaphore is based on the fact that when a given process tries to reserve the resource for its use by writing the value 1 for the Set.i bit in the semaphore port, the semaphore circuit will simultaneously set the value of the semaphore preceding the moment of writing as the value for the Test.i bit in the port. In other words, when the process attempting to make a reservation now reads the value of the Test.i bit in the port of the semaphore, the value 1 of the Test.i bit indicates that the resource was busy already before the write attempt, and the locking was unsuccessful. If the value of the Test.i bit is 0, this indicates that the resource was vacant at the moment of writing the Set.i bit, wherein the locking was successful. The solution presented in U.S. Pat. No. 6,263,425 makes it possible to use the semaphore lock also in such an environment, in which the processors or bus solutions as such do not guarantee access to atomic read/write sequences.
USPTO Backgrounds
USPTO Backgrounds