19.8. Histories and serialization graphs

A history is a data structure which represents a concurrent execution of a set of transactions. The directed graphs of Figures 19.7, 19.8 and 19.9 are simple examples: they show the operations within the transactions, and the order of invocation of conflicting pairs of operations by different transactions. Note that the order of invocation of all conflicting pairs of operations on all objects must be shown in the history. Figure 19.10 gives a representation of a history in which the details of the objects and operations involved are not shown.

Figure 19.10. An example of a serializable history of three transactions.

A serializable history represents a serializable execution of the transactions. That is, ...

Get Operating Systems: Concurrent and Distributed Software Design now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.