In a large scale computer system, such as a database management system (DBMS), it is important to be able to support a number of different users concurrently. Without such a capability, the system would be little more than a standalone computer. To implement multi-user support, several different processing models have been utilized. One model that has been used is the multi-processing model. In multi-processing, each time a new user requests access to the system, a separate process is started. This process is in essence a separate execution of the software. Once started, the process services all of the requests from the user that spawned it. Under the multi-processing model, each process has its own separate memory space for use in storing and processing data.
Multi-processing is effective for supporting multiple users concurrently; however, it has severe scalability limitations. This is due mainly to two factors. First, spawning and maintaining a process involves a significant amount of overhead. Because of the high cost, only a small number of processes can be maintained at any one time. Second, the same set of data, used by multiple processes, may be stored redundantly; once in each process' memory space. This redundancy can waste a significant amount of system resources.
To overcome some of the limitations of multi-processing, the multi-thread model was developed. According to the multi-thread model, there is only one execution of the software. That is, only one process is spawned. From this one process, multiple threads can be spawned to perform the work necessary to service user requests.
Multi-threading has several advantages over multi-processing. First, because only one process is spawned, overhead is kept to a minimum. It is true that each thread carries with it some overhead cost, but this cost is negligible when compared with the cost of maintaining an entire process. Because multi-threading significantly reduces system overhead, many more users can be supported. Another advantage of multi-threading is that it minimizes the redundant storage of data. Because all of the threads are part of the same process, all of the threads can share the same memory space. This in turn makes it easier to implement a shared cache.
With a shared cache, it is only necessary to store a set of data once. After the data is cached, all of the threads can access it. By reducing redundant storage of data, multi-threading makes more efficient use of system resources.
Implementing a shared cache gives rise to increased efficiencies. However, a shared cache is not without its disadvantages. One of the drawbacks of a shared cache is the possibility of deadlock. To elaborate, in most caching systems, users are allowed to obtain locks on selected entries in the cache. Once a lock is obtained on a cache entry, the entry typically cannot be changed by another user or flushed until the lock is released. In a shared cache, multiple users are accessing and possibly locking various entries in the cache. Because of this, there may be instances in which a first user waits for a lock owned by a second user to be released, while the second user is waiting for a lock owned by the first user to be released. In such an instance, there is deadlock. When deadlock occurs, useful work stops being performed. Because deadlock is an undesirable condition, a need exists for a mechanism for preventing the occurrence of deadlock conditions.