Model of consistency and Lock protocols:

A moderately formal model is required in order to make precise statements about the issues of locking and recovery. For the reason that the problems are so complex one must either accept many simplifying assumptions or accept a less formal approach. A negotiation is adopted here. First we will introduce a moderately formal model of transactions locks and recovery that will allow us to discuss the issues of lock management and recovery management. Subsequent to this presentation the implementation issues associated with locking and recovery will be discussed.

Several definition of consistency:

Numerous equivalent definitions of consistency are presented. The first definition is an operational as well as intuitive one it is useful in describing the system behaviour to users. The second definition is a technical one in terms of lock protocols it is useful in explaining the system implementation. The third definition is in requisites of a trace of the system actions it is useful in formally stating and proving consistency properties.

Informal definition of consistency:

An output (write) of a transaction is committed while the transaction abdicates the right to “undo” the write thereby making the new value available to all other transactions (that is commits). Outputs are said to be uncommitted or else dirty if they are not yet committed by the writer. Concurrent execution increases the problem that reading or writing other transactions’ dirty data may yield inconsistent data.

Utilizing this notion of dirty data consistency may perhaps be defined as:

Definition 1: Transaction T observes a consistent state if:

(a) T doesn’t overwrite dirty data of other transactions.
(b) T doesn’t commit any writes until it completes all its writes (that is until the end of transaction (EOT)).
(c) T doesn’t read dirty data from other transactions.
(d) Other transactions don’t dirty any data read by T before T completes.

Clauses (a) as well as (b) insure that there are no lost updates.

Clause (c) isolates a transaction as of the uncommitted data of other transactions. Without this section a transaction might read uncommitted values which are subsequently updated or are undone. If clause (c) is observed no uncommitted values are read.

Clause (a) assures repeatable reads. For illustration without clause (c) a transaction may read two different (committed) values if it reads the same entity twice. This is for the reason that a transaction that updates the entity could begin, update and commit in the interval between the two reads. More elaborate types of anomalies due to concurrency are possible if one updates an entity after reading it or if more than one entity is involved (see example below).

The rules précised have the properties that:

1. If all transactions examined the consistency protocols then any execution of the system is equivalent to some ‘serial’ execution of the transactions (that is it is as though there was no concurrency.)

2. If all transactions examine the consistency protocols then each transaction sees a consistent state.

3. If all transactions examine the consistency protocols then system backup (undoing all in-progress transactions) loses no updates of completed transactions.

4. If all transactions examine the consistency protocols then transaction backup (undoing any inprogress transaction) produces a consistent state.
Assertions 1 as well as 2 are proved in the paper "On the Notions of Consistency as well as Predicate Locks" CACM Vol. 9, No. 71, Nov. 1976. Offering the second two assertions is a good research problem. It necessitates extending the model used for the first two assertions and reviewed here to include recovery notions.

Schedules: Formalize dirty and commited data

The definition of what it signifies for a transaction to see a consistent state was given in terms of dirty data. In order to make the notion of dirty data explicit it is essential to consider the implementation of a transaction in the context of a set of concurrently executing transactions. To do this we initiate the notion of a schedule for a set of transactions. A schedule is able to be thought of as a history or audit trail of the actions performed by the set of transactions. Specified a schedule the notion of a particular entity being dirtied by a particular transaction is made explicit and hence the notion of seeing a consistent state is formalized.

These notions may perhaps then be used to connect the various definitions of consistency and show their equivalence.
The system straight supports objects and actions. Actions are categorized as begin actions, share lock actions, end actions, abort actions, exclusive lock actions, unlock actions, read actions, write actions.

Commit actions as well as abort actions are presumed to unlock any locks held by the transaction but not explicitly unlocked by the transaction. For the reason of the following definitions share lock actions and their corresponding unlock actions are additionally considered to be read actions and exclusive lock actions as well as their corresponding unlock actions are additionally considered to be write actions.

For the reason of this mad, a transaction is any sequence of actions beginning until a begin action as well as ending with a commit or abort action and not containing other begin, commit or else abort actions and, here are two trivial transactions.

Any (sequence preserving) integration of the actions of a set of transactions into a single sequence is called a schedule for the set of transactions.

A schedule is a history of the order in which actions were productively executed (it doesn’t record actions which were undone due to backup (This aspect of the model requires to be generalized to prove assertions 3 and 4 above)). The easiest schedules run all actions of one transaction as well as then all actions of another transaction,... Such one-transaction-at-a-time schedules are describing serial because they have no concurrency among transactions. Obviously a serial schedule has no concurrency-induced inconsistency and no transaction sees dirty data. Lock constrains the set of authorized schedules. Particularly a schedule is legal only if it doesn’t schedule a lock action on an entity for one transaction when that entity is already locked by some other transaction in a conflicting mode.

The following table depicts the compatibility among the simple lock modes.

The subsequent are three example schedules of two transactions. The first schedule is legal and the second is serial and legal and the third schedule isn’t legal since T1 and T2 have conflicting locks on the object A.

The three assortment of schedules (serial and not legal is impossible).

An initial state and a schedule entirely define the system's behaviour. At every step of the schedule one can deduce which entity values have been committed and which are dirty: if locking is utilized updated data is dirty until it is unlocked.

One transaction illustration is said to depend on another if the first takes some of its inputs from the second. The notion of dependency is able to be useful in comparing two schedules of the same set of transactions.

Every schedule S defines a ternary dependency relation on the set TRANSACTIONS X OBJECTS X TRANSACTIONS as follows. Presume that transaction T performs action an on entity e at some step in the schedule, and that transaction T’ performs action a' on entity e at a later step in the schedule. Further presume that T and T' are distinct.

Then:

(T, e, T’) is in DEP(S)

if a is a write action as well as a' is a write action
or a is a write action as well as a' is a read action
or a is a read action as well as a’ is a write action

The dependency set of a schedule entirely defines the inputs and outputs each transaction”sees”. If two distinct schedules have the similar dependency set then they provide each transaction with the same inputs and outputs. Therefore we say two schedules are equivalent if they have the same dependency sets.

If a schedule is equal to a serial schedule then that schedule must be consistent since in a serial schedule there are no inconsistencies due to concurrency. Alternatively if a schedule is not equivalent to a serial schedule then it is probable (possible) that a few transaction sees an inconsistent state. Therefore,

Definition 2: A schedule is consistent if it is equal to some serial schedule.

The following argument may perhaps clarify the inconsistency of schedules not equivalent to serial schedules. Describe the relation <<<on the set of transactions by:

T<<<T` 'if for some entity e (T, e, T') is in DEP(S).

Let <<<* be the transitive closure of <<<, then define:
BEFORE(T) = {T' l T'<<<*T }
AFTER(T) = { ~T’ | T <<<*T' }.

The clear interpretation of this is that BEFORE(T) is the set of transactions that contribute inputs to T and each AFTER(T) set is the set of transactions that take their inputs from T

If some transaction is both prior to T and after T in some schedule then no serial schedule could give such results. In these circumstances concurrency has introduced inconsistency. Alternatively if all relevant transactions are either before or after T (but not both) then T will see a consistent state. If every transactions dichotomize others in this way then the relation <<<*will be a partial order as well as the whole schedule will provide consistency.

The above definitions is able to be related as follows:

Assertion:

A schedule is consistent
if and only if (by definition)
the schedule is equal to a serial schedule
if and only if
the relation <<<*is a partial order.

Lock Protocol Definition of Consistency:

Whether an instantiation of a transaction observes a consistent state depends on the actions of other concurrent transactions. All transactions concur to certain lock protocols so that they can all be guaranteed consistency.

Since the lock system permits only legal schedules we want a lock protocol such that every legal schedule is a consistent schedule.

Consistency is able to be procedurally defined by the lock protocol which produces it: A transaction locks its inputs to guarantee their consistency as well as locks its outputs to mark them as dirty (uncommitted).

For this segment locks are dichotomized as share mode locks which allow multiple readers of the same entity and exclusive mode locks which reserve exclusive access to an entity.

The lock protocols sophisticated to these modes is:

Definition 3: Transaction T examines the consistency lock protocol if:

a) T sets an exclusive lock on any data it dirties
b) T sets a share lock on any data it reads.
c) T holds all locks to end of transaction.

These lock protocol definitions is able to be stated more precisely and tersely with the introduction of the following notation. A transaction is well-formed if it forever locks an entity in exclusive (shared or exclusive) mode before writing (reading) it.

A transaction is two-phase if it doesn’t (share or exclusive) lock an entity after unlocking some entity A two-phase transaction has a growing phase during which it acquires locks as well as a shrinking phase during which it releases locks.
The lock consistency protocol is able to be redefined as:

Definition 3: Transaction T examines the consistency lock protocol if it is well formed and two phase.

Definition 3 was excessively restrictive in the sense that consistency does not require that a transaction hold all locks to the EOT (that is the ROT need not be the start of the shrinking phase). Rather the constraint which the transaction be two-phase is sufficient to insure consistency. Alternatively once a transaction unlocks an updated entity it has committed that entity and therefore cannot be undone without cascading backup to any transactions that may have subsequently read the entity. Consequently the shrinking phase is usually deferred to the end of the transaction therefore the transaction is always recoverable and all updates are committed together.

Relationship among Definitions:

These definitions possibly related as follows if T sees a consistent state in S.

Assertion:

(a) If every transaction observes the consistency lock protocol (Definition 3') then any legal schedule is consistent (Definition 2) (that is every transaction sees a consistent state in the sense of Definition 1).

(b) If transaction T violates the consistency lock protocol afterwards it is possible to define another transaction T’ that does observe the consistency lock protocol such that T and T' have a legal schedule S but T doesn’t see a consistent state in S.

This says that if a transaction examines the consistency lock protocol definition of consistency (Definition 3') then it is assured of the definition of consistency based on committed as well as dirty data (Definition 1 or 3).

Except a transaction actually Sets the locks prescribed by consistency one can construct transaction mixes as well as schedules which will cause the transaction to see an inconsistent state. Nevertheless in particular cases such transaction mixes may never take place due to the structure or use of the system. In these cases an apparently insufficient locking may actually provide consistency. For illustration a data base reorganization typically need no locking since it is run as an off-line utility which is never run concurrently with other transactions.

Latest technology based Operating System Online Tutoring Assistance

Tutors, at the www.tutorsglobe.com, take pledge to provide full satisfaction and assurance in Operating System help via online tutoring. Students are getting 100% satisfaction by online tutors across the globe. Here you can get homework help for Operating System, project ideas and tutorials. We provide email based Operating System help. You can join us to ask queries 24x7 with live, experienced and qualified online tutors specialized in Operating System. Through Online Tutoring, you would be able to complete your homework or assignments at your home. Tutors at the TutorsGlobe are committed to provide the best quality online tutoring assistance for Operating System Homework help and assignment help services. They use their experience, as they have solved thousands of the Operating System assignments, which may help you to solve your complex issues of Operating System. TutorsGlobe assure for the best quality compliance to your homework. Compromise with quality is not in our dictionary. If we feel that we are not able to provide the homework help as per the deadline or given instruction by the student, we refund the money of the student without any delay.