Selectors: High-Level Resource Schedulers

Resource sharing problems can be described in three basically independent modular components. ? The constraints the resource places upon sharing because of physcal limitations and consistency requirements. ? The desired ordering of resource requests to achieve efficiency-either efficiency of resource utilization or efficiency of processes making the requests. ? Modifications to the ordering to prevent starvation of processes waiting for requests which might otherwise never receive service. A high-level nonprocedural language to specify these components of resource sharing problems is described. General deadlock and starvation properties of selectors are proven. Solutions to several classic resource sharing problems are shown to illustrate the expressiveness of this language. Proof techniques for this high-level language are introduced to show how to prove particular selectors are or are not deadlock and starvation free.     

Improving Predictability of Transaction Execution Times in Real-time Databases

We present a design for multi-versionconcurrency control and recovery in a main memory database, anddescribe logical and physical versioning schemes that allowread-only transactions to execute without obtaining data itemlocks or system latches. Our schemes enable a system to providethe guarantee that updaters will never interfere with read-onlytransactions, and read-only transactions will not be delayeddue to data contention. Consequently, transaction executionsbecome more predictable—this partially alleviates a majorproblem in real-time database system (RTDBS) scheduling, namely,significant unpredictability in transaction execution times.As a result, in addition to a transaction's deadline, a moreaccurate estimate of its execution time can also be taken intoaccount, thus facilitating better scheduling decisions. Our contributionsinclude several space saving techniques for the main-memory implementation,including improved methods for logical aging of data items andthe introduction of physical aging for low-level structures.Some of these schemes have been implemented on a widely-usedsoftware platform within Lucent, and the full scheme is implementedin the Dalí main-memory storage manager.