Abstract
Serializability is unnecessarily strict for real-time systems because most transactions in such systems occur periodically and changes among data values over a few consecutive periods are often insignificant. Hence, data values produced within a short interval can be treated as if they are “similar” and interchangeable. This notion of similarity allows higher concurrency than serializability, and the increased concurrency may help more transactions to meet their deadlines. The similarity stack protocol (SSP) proposed in [25, 26] utilizes the concept of similarity. The rules of SSP are constructed based on prior knowledge of worst-case execution time (WCET) and data requirements of transactions. As a result, SSP rules need to be re-constructed each time a real-time application is changed. Moreover, if WCET and data requirements of transactions are over-estimated, the benefits provided by similarity can be quickly overshadowed, causing feasible schedules to be rejected. The advantages of similarity and the drawbacks of SSP motivate us to design other similarity-based protocols that can better utilize similarity without relying on any prior information. Since optimistic approaches usually do not require prior information of transactions, we explore the ideas of integrating optimistic approaches with similarity in this thesis. We develop three different protocols based on either the forward-validation or backward-validation mechanisms. We then compare implementation overheads, number of transaction restarts, length of transaction blocking time, and predictabilities of these protocols. One important characteristic of our design is that, when similarity is not applicable, our protocols can still accept serializable histories. We also study how to extend our protocols to handle aperiodic transactions and data freshness in this thesis. Finally, a set of simulation experiments is conducted to compare the deadline miss rates between SSP and one of our protocol.