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 require
merits 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. / Graduation date: 1999
| Identifer | oai:union.ndltd.org:ORGSU/oai:ir.library.oregonstate.edu:1957/33531 |
| Date | 29 January 1999 |
| Creators | Lai, Chih |
| Contributors | Rudd, Walter G. |
| Source Sets | Oregon State University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis/Dissertation |
Page generated in 0.0014 seconds