In a system for supporting a multi-user environment, it is needed to designate and manage shared data in an appropriate size in a critical section for maintaining consistency, and improving the concurrence, of the shared data. A critical section is a shared data area in which only one user request can be executed at a time. The performance of the overall system depends significantly on how the users' simultaneous accessing to the critical section is synchronized. In other words, the performance of the overall system depends largely on how the critical section is implemented.
Implementation of the critical section must satisfy three conditions, i.e., a mutual exclusion, progress and a bounded waiting. The mutual exclusion condition requires control of user requests trying to simultaneously enter the critical section in order to allow only one user request to enter it at a time. The progress condition requires that any one user trying to enter the critical section must be allowed to enter it if the others do not use it. The bounded waiting condition requires that the user trying to enter the critical section must be allowed to enter it after the lapse of a predetermined period of time instead of endless waiting until the required condition is satisfied, even though it is not yet satisfied. Satisfaction of the three conditions above ensures the maintenance of integrity for the shared data and the effective concurrence control of multiple users.
Examples of methods for synchronizing user requests desiring to enter a critical section include use of a semaphore provided by an operating system and implementation of a latch. The latch is the data structure encapsulated by a shared variable, i.e., mutual exclusion variable (hereinafter, referred to as "mutex") for scheduling user requests trying to enter the critical section. The semaphore provided by the operating system is a very expensive resource not only because of the limit on the number of semaphores but also because of the accompanied system call even though it is capable of controlling the users' simultaneous accesses to the critical section through the use of P and V operations and can be implemented simply. Such method for supporting the critical section using the semaphore does not provide very good performance for a system using the same. On the other hand, the method for supporting the critical section through implementation of a latch can support the multi-user environment at a lesser cost than the semaphore method using the system call does.
However, the existing latch has a problem in that the time required to hold the mutex is increased in proportion to the size of critical section. This is because the user continues to hold the mutex during entering and executing of the critical section, since the latch is implemented under the concept regarding the mutual exclusion variable, mutex, itself as the latch. Another problem is in that the latch structure and the method for the same cannot satisfy all the three conditions mentioned above and, in the alternative, the structure and method would become very complicated in order to satisfy all three conditions.