×

Cautious transaction schedulers with admission control. (English) Zbl 0568.68077

We propose a new class of schedulers, called cautious schedulers, that grant an input request if it will not necessitate any rollback in the future. In particular, we investigate cautious WRW-schedulers that output schedules in class WRW only. Class WRW consists of all schedules that are serializable, while preserving the write-read and read-write conflict, and is the largest polynomially recognizable subclass of serializable schedules currently known. It is shown, in this paper however, that cautious WRW-scheduling is, in general, NP-complete. Therefore, we introduce a special type (type 1R) of transaction, which consists of no more than one read step (an indivisible set of read operations) followed by multiple write steps. It is shown that cautious WRW-scheduling can be performed efficiently if all transactions are of type 1R and if admission control can be exercised. Admission control rejects a transaction unless its first request is immediately grantable.

MSC:

68P20 Information storage and retrieval of data
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
Full Text: DOI