What is Concurrency Control?
Concurrency Control
We move next to the issue of concurrency control. In this section, we show how certain of the concurrency-control schemes discussed in Chapter 6 can be modified for use in a distributed environment. The transaction manager of a distributed database system manages the execution of those transactions (or subtransactions) that access data stored in a local site.
Each such transaction may be either a local transaction (that is, a transaction that executes only at that site) or part of a global transaction (that is, a transaction that executes at several sites). Each transaction manager is responsible for maintaining a log for recovery purposes and for participating in an appropriate concurrency-control scheme to coordinate the conciirrent execution of the transactions executing at that site. As we shall see, the concurrency schemes described in Chapter 6 need to be modified to accommodate the distribution of transactions.
Locking Protocols
The two-phase locking protocols described in Chapter 6 can be used in a distributed environment. The only change needed is in the way the lock manager is implemented. Here, we present several possible schemes. The first deals with the case where no data replication is allowed. The others apply to the more general case where data can be replicated in several sites. As in Chapter 6, we assume the existence of the shared and exclusive lock modes
Nonreplicated Scheme
If no data are replicated in the system, then the locking schemes described in Section 6.9 can be applied as follows: Each site maintains a local lock manager whose function is to administer the lock and unlock requests for those data items stored in that site.
When a transaction wishes to lock data item Q at site Si, it simply sends a message to the lock manager at site S; requesting a lock (in a particular lock mode). If data item Q is locked in an incompatible mode, then the request is delayed until that request can be granted. Once it has been determined that the lock request can be granted, the lock manager sends a message back to the initiator indicating that the lock request has been granted. 18.4 Concurrency Control 673 This scheme has the advantage of simple implementation. It requires two message transfers for handling lock requests and one message transfer for handling unlock requests. However, deadlock handling is more complex.
Since the lock and unlock requests are no longer made at a single site, the various deadlock-handling algorithms discussed in Chapter 7 must be modified; these modifications are discussed in Section 18.5.
Single-Coordinator Approach
Several concurrency-control schemes can be used in systems that allow data replication. Under the single-coordinator approach, the system maintains a single lock manager that resides in a single chosen site—say, S,\ All lock and unlock requests are made at site S,. When a transaction needs to lock a data item, it sends a lock request to S;. The lock manager determines whether the lock can be granted immediately. If so, it sends a message to that effect to the site at which the lock request was initiated. Otherwise, the request is delayed until it can be granted; and at that time, a message is sent to the site at which the lock request was initiated.
The transaction can read the data item from any one of the sites at which a replica of the data item resides. In the case of a write operation, all the sites where a replica of the data item resides must be involved in the writing. The scheme has the following advantages:
• Simple implementation. This scheme requires two messages for handling lock requests and one message for handling unlock requests.
• Simple deadlock handling. Since all lock and unlock requests are made at one site, the deadlock-handling algorithms discussed in Chapter 7 can be applied directly to this environment. The disadvantages of the scheme include the following:
• Bottleneck. The site S, becomes a bottleneck, since all requests must be processed there.
• Vulnerability. If the site S, fails, the concurrency controller is lost. Either processing must stop or a recovery scheme must be used. A compromise between these advantages and disadvantages can be achieved through a multiple-coordinator approach, in which the lockmanager function is distributed over several sites. Each lock manager administers the lock and unlock requests for a subset of the data items, and the lock managers reside in different sites. This distribution reduces the degree to which the coordinator is a bottleneck, but it complicates deadlock handling, since the lock and unlock requests are not made at a single site.
Majority Protocol
The majority protocol is a modification of the nonreplicated data scheme presented earlier. The system maintains a lock manager at each site. Each manager controls the locks for all the data or replicas of data stored at that site. When a transaction wishes to lock a data item Q that is replicated in n different 674 Chapter 18 Distributed Coordination sites, it must send a lock request to more than one-half of the n sites in which Q is stored.
Each lock manager determines whether the lock can be granted immediately (as far as it is concerned). As before, the response is delayed until the request can be granted. The transaction does not operate on Q until it has successfully obtained a lock on a majority of the replicas of chl8/18. This scheme deals with replicated data in a decentralized manner, thus avoiding the drawbacks of central control. However, it suffers from its own disadvantages:
• Implementation. The majority protocol is more complicated to implement than the previous schemes. It requires 2(n/2 + 1) messages for handling lock requests and (n/2 + 1) messages for handling unlock requests.
• Deadlock handling. Since the lock and unlock requests are not made at one site, the deadlock-handling algorithms must be modified (Section 18.5). In addition, a deadlock can occur even if only one data item is being locked. To illustrate, consider a system with four sites and full replication. Suppose that transactions T\ and" T2 wish to lock data item Q in exclusive mode. Transaction T\ may succeed in locking Q at sites S\ and S3, while transaction T2 may succeed in locking Q at sites Sj and S4. Each then must wait to acquire the third lock, and hence a deadlock has occurred
Biased Protocol
The biased protocol is similar to the majority protocol. The difference is that requests for shared locks are given more favorable treatment than are requests for exclusive locks. The system maintains a lock manager at each site. Each manager manages the locks for all the data items stored at that site. Shared and exclusive locks are handled differently.
• Shared locks. When a transaction needs to lock data item Q, it simply requests a lock on Q from the lock manager at one site containing a replica oichlS/18.
• Exclusive locks. When a transaction needs to lock data item Q, it requests a lock on Q from the lock manager at each site containing a replica of chl8/18. As before, the response to the request is delayed until the request can be granted. The scheme has the advantage of imposing less overhead on read operations than does the majority protocol.
This advantage is especially significant in common cases in which the frequency of reads is much greater than the frequency of writes. However, the additional overhead on writes is a disadvantage. Furthermore, the biased protocol shares the majority protocol's disadvantage of complexity in handling deadlock.
Primary Copy
Yet another alternative is to choose one of the replicas as the primary copyThus, for each data item Q, the primary copy of Q must reside in precisely one site, which we call the primary site ofQ. When a transaction needs to lock a data item Q, it requests a lock at the primary site of chl8/18. As before, the response to the request is delayed until the request can be granted. This scheme enables us to handle concurrency control for replicated data in much the same way as for unreplicated data. Implementation of the method is simple. However, if the primary site of Q fails, Q is inaccessible even though other sites containing a replica may be accessible
Timestamping
The principal idea behind the timestamping scheme discussed in Section 6.9 is that each transaction is given a unique timestamp, which is used to decide the serialization order. Our first task, then, in generalizing the centralized scheme to a distributed scheme is to develop a method for generating unique timestamps. Our previous protocols can then be applied directly to the nonreplicated environment.
Generation of Unique Timestamps
Two primary methods are used to generate unique timestamps; one is centralized, and one is distributed. In the centralized scheme, a single site is chosen for distributing the timestamps. The site can use a logical counter or its own local clock for this purpose. In the distributed scheme, each site generates a local unique timestamp using either a logical counter or the local clock. The global unique timestamp is obtained by concatenation of the local unique timestamp with the site identifier, which must be unique (Figure 18.2).
The order of concatenation is important! We use the site identifier in the least significant position to ensure that the global timestamps generated in one site are not always greater than those generated in another site. Compare this technique for generating unique timestamps with the one we presented in Section 18.1.2 for generating unique names.
We may still have a problem if one site generates local timestamps at a faster rate than do other sites. In such a case, the fast site's logical counter will be larger than those of other sites. Therefore, all timestamps generated by the fast site will be larger than those generated by other sites. A mechanism is needed to ensure that local timestamps are generated fairly across the system. To accomplish the fair generation of timestamps, we define within each site S; a logical clock {LC,), which generates the local timestamp (see Section 18.1.2).
To ensure that the various logical clocks are synchronized, we require that a site S; advance its logical clock whenever a transaction T, with timestamp visits that site and x is greater than the current value of Ld. In this case,?site S, advances its logical clock to the value x + 1. If the system clock is used to generate timestamps, then timestamps are assigned fairly, provided that no site has a system clock that runs fast or slow. Since clocks may not be perfectly accurate, a technique similar to that used for logical clocks must be used to ensure that no clock gets far ahead or far behind another clock.
Timestamp-Ordering Scheme
The basic timestamp scheme introduced in Section 6.9 can be extended in a straightforward manner to a distributed system. As in the centralized case, cascading rollbacks may result if no mechanism is used to prevent a transaction from reading a data item value that is not yet committed. To eliminate cascading rollbacks, we can combine the basic timestamp scheme of Section 6.9 with the 2PC protocol of Section 18.3 to obtain a protocol that ensures serializability with no cascading rollbacks. We leave the development of such an algorithm to you.
The basic timestamp scheme just described suffers from the undesirable property that conflicts between transactions are resolved through rollbacks, rather than through waits. To alleviate this problem, we can buffer the various read and write operations (that is, delay them) until a time when we are assured that these operations can take place without causing aborts. A read(x) operation by T, must be delayed if there exists a transaction Ty that will perform a write(;e) operation but has not yet done so and TS(Ty) < TS(Tj). Similarly, a wr ite(x) operation by T, must be delayed if there exists a transaction T,- that will perform either a read(x) or a write(x) operation and TS(T/) < TS(Ti). Various methods are available for ensuring this property.
One such method, called the conservative timestamp-ordering scheme, requires each site to maintain a read queue and a write queue consisting of all the read and write requests that are to be executed at the site and that must be delayed to preserve the above property. We shall not present the scheme here. Again, we leave the development of the algorithm to you.
Frequently Asked Questions
Recommended Posts:
- Operating System Concepts ( Multi tasking, multi programming, multi-user, Multi-threading )
- Different Types of Operating Systems
- Batch Operating Systems
- Time sharing operating systems
- Distributed Operating Systems
- Network Operating System
- Real Time operating System
- Various Operating system services
- Architectures of Operating System
- Monolithic architecture - operating system
- Layered Architecture of Operating System
- Microkernel Architecture of operating system
- Hybrid Architecture of Operating System
- System Programs and Calls
- Process Management - Process concept