زمانبندی خود سازگار برای هماهنگ سازی معاملات در محیط های پویا قابل تنظیم

In a database system, the scheduler has the goal of synchronizing operations belonging to several concurrent transactions. The scheduler implements a concurrency control protocol, which may have either conservative or aggressive behavior. Existing database systems have schedulers with static behavior. This paper presents a self-adaptable scheduler, called Intelligent Transaction Scheduler (ITS), which has the ability of dynamically changing its behavior to adapt itself to the characteristics of the computing environment, without any human interference by using an expert system based on fuzzy logic. ITS can implement different correctness criteria, such as classical (syntactic) serializability and semantic serializability.

Users interact with database systems by means of application programs. A transaction is an abstraction that represents a sequence of database operations resulting from the execution of an application program [28]. A database system should synchronize the execution of concurrent transactions to guarantee database consistency. The component in the database system responsible for synchronizing the operations of concurrent transactions is the scheduler. The scheduler synchronizes operations belonging to different transactions by means of a concurrency control protocol. Concurrency control protocols may present aggressive or conservative behavior [28]. An aggressive concurrency control protocol tends to avoid delaying operations, and tries to schedule them immediately. However, such a strategy may lead to a situation in which there is no possibility of yielding a correct execution of all active transactions. In this case, operations of one or more transactions should be rejected. A conservative protocol, on the other hand, tends to delay operations in order to synchronize them correctly. Additionally, aggressive concurrency protocols can be categorized in two sub-classes: pessimistic and optimistic. A scheduler implementing a pessimistic protocol decides to accept or reject the operation as soon as it receives the operation. On the other hand, a scheduler using an optimistic protocol immediately schedules the operation. After a given period of time, the scheduler verifies the correctness of the schedule it has already produced. If the schedule is correct, the scheduler continues synchronizing operations. Otherwise, the scheduler must abort some transactions. The concept of serializability [18] has been used since the 1970s by concurrency control protocols as a correctness criterion to ensure database consistency. The Two Phase Locking Protocol (2PL) is the most widely used conservative protocol based on serializability. Among the protocols with aggressive behavior that use a pessimistic approach, the Timestamp Ordering (TO), and the Serialization Graph Testing (SGT), are noteworthy. A scheduler implementing an aggressive concurrency control protocol is called an aggressive scheduler, whereas a scheduler implementing a conservative concurrency control protocol is called a conservative scheduler. A Mobile Ad hoc NETwork (MANET) [16] is a wireless dynamic network, in which nodes can join or leave the network dynamically. Some database applications that use MANET technology are: industrial and commercial applications involving cooperative mobile data exchange [16]; military networks [21] and [26]; vehicular ad hoc networks [9]; city services, such as the taxi company system presented in [12]. MANETs allow users carrying portable devices to access database services regardless of their physical location or movement patterns. Thus, a dynamic collection of autonomous mobile databases, called mobile database community (MDBC) [3], can be formed, where the mobile databases reside in nodes (Mobile Units – MU) of a MANET. Since new participants may join an MDBC or a participant may transiently disconnect from the MDBC (due to communication disruptions or to save power), an MDBC is characterized as a dynamically configurable environment. Observe that the concept of MDBC models a dynamically configurable multidatabase [6] whose members (local databases) can move across different locations. As already mentioned, mobile units may join and leave an MDBC at anytime. In such a dynamic environment, the use of a fixed concurrency protocol (e.g., using only strict 2PL) to generate correct schedules may not be the most efficient strategy at given moments over a period of time. This is because a scheduler with static behavior is not able to capture modifications in the context it is being executed. As shown in Section 4, the arrival of a new mobile unit in an MDBC drastically modifies the scenario in which transactions are being executed. For example, consider that the new mobile unit submits transactions with several write operations and a scheduler implementing a conservative protocol (e.g., strict 2PL) is being used. In such a scenario, the conflicting operation rate may increase (see Section 4), which may induce low throughput rates (low degree of parallelism). This paper presents the Intelligent Transaction Scheduler (ITS), characterized by having a hybrid behavior (conservative or aggressive). The gist of this approach is to provide a scheduler that can automatically identify and react to the modifications in the computational environment in which it is inserted, by adapting its behavior (from aggressive to conservative and vice versa), without human interference. In other words, ITS is context-aware. It is shown in Section 4 that ITS achieves a reasonable throughput, while generating correct global schedules in dynamically configurable environments. Furthermore, the ITS can be adjusted to use correctness criteria other than classical serializability, since that criterion is very restrictive for controlling concurrency in dynamically configurable environments, such as an MDBC. Therefore, we claim that an adaptive scheduler is quite appropriate for controlling concurrency in dynamically configurable environments, whose configuration (topology) may change dynamically. It is worthwhile to note that although the ITS has been developed for use in dynamically configurable environments, it can also be used to synchronize operations of concurrent transactions in any other distributed environment with static topology as well. The remainder of this paper is organized as follows: Section 2 presents the architecture of the proposed scheduler (ITS); Section 3 presents the theoretical support which proves the correctness of ITS’ self-adaptability (i.e., ITS produces correct schedules); Section 4 describes aspects of ITS’ implementation, its use in MDBCs and an analysis of the obtained results; Section 5 describes some of the existing related proposals in the literature; and finally, Section 6 concludes this paper.

This paper presented the ITS – a scheduler that adapts its behavior dynamically and automatically (without human interference) according to the computing environment characteristics (e.g., aborted transaction rate, conflicting operation rate and lock waiting rate). Therefore, the ITS is a self-adaptable scheduler that reacts to changes in computing environments. Such a feature is critical for a scheduler running in dynamically configurable environments, whose topology changes dynamically. The ITS was developed to synchronize transactions by using syntactical serializability and semantic serializability as correctness criteria. The ITS always produces correct schedules, and the formal proofs of the correctness are presented in Section 3. In order to evaluate the viability of the ITS using serializability, two protocols, 2PL (conservative behavior) and TO (aggressive behavior), were implemented in the core of ITS. In order to evaluate the ITS using semantic serializability, two protocols were implemented, SeL (conservative) and SeTO (aggressive). However, it is important to note that the ITS may be used with any protocol based on serializability or semantic serializability. The ITS was compared to schedulers with fixed behavior (aggressive or conservative). The tests presented in Section 4 simulated the use of the ITS for synchronizing transactions in an MDBC — a dynamically configurable environment. The analysis of the simulation results shows that the ITS (with hybrid behavior) is quite efficient for controlling concurrency in dynamic environments, such as an MDBC, since it is able to find a good compromise between the abort rate and lock waiting rate compared to schedulers implementing static behavior, i.e., fixed concurrency control protocols. The results obtained demonstrate the viability of employing the ITS in a dynamic environment, such as an MDBC. Nonetheless, others functions are being investigated, such as: implementation of the ITS with correctness criteria other than serializability and serializability semantic; distributed processing of the ITS, which is an important feature in a distributed environment; and an Analyzer (ES) specification for mobile environments, including the following variables: number of mobile units, disconnect rate and available rate.