Masters Theses


Ying Zhang

Keywords and Phrases

CRPD analysis; Randomized scheduler; Real-time systems; RWS


"Real-time systems are widely applied to the time-critical fields. In order to guarantee that all tasks can be completed on time, predictability becomes a necessary factor when designing a real-time system. Due to more and more requirements about the performance in the real-time embedded system, the cache memory is introduced to the real-time embedded systems.

However, the cache behavior is difficult to predict since the data will be loaded either on the cache or the memory. In order to taking the unexpected overhead, execution time are often enlarged by a certain (huge) factor. However, this will cause a waste of computation resource. Hence, in this thesis, we first integrate the cache-related preemption delay to the previous global earliest deadline first schedulability analysis in the direct-mapped cache. Moreover, several analyses for tighter G-EDF schedulability tests are conducted based on the refined estimation of the maximal number of preemptions. The experimental study is conducted to demonstrate the performance of the proposed methods.

Furthermore, Under the classic scheduling mechanisms, the execution patterns of tasks on such a system can be easily derived. Therefore, in the second part of the thesis, a novel scheduler, roulette wheel scheduler (RWS), is proposed to randomize the task execution pattern. Unlike traditional schedulers, RWS assigns probabilities to each task at predefined scheduling points, and the choice for execution is randomized, such that the execution pattern is no longer fixed. We apply the concept of schedule entropy to measure the amount of uncertainty introduced by any randomized scheduler, which reflects the unlikelihood of for such attacks to success. Comparing to existing randomized scheduler that gives all eligible tasks equal likelihood at a given time point, the proposed method adjusted such values so that the entropy can be greatly increased"--Abstract, page iii.


Markowsky, George

Committee Member(s)

Nadendla, V. Sriram Siddhardh
Markowsky, Linda


Computer Science

Degree Name

M.S. in Computer Science


Missouri University of Science and Technology

Publication Date

Fall 2018


x, 59 pages

Note about bibliography

Includes bibliographical references (pages 54-58).


© 2018 Ying Zhang, All rights reserved.

Document Type

Thesis - Open Access

File Type




Thesis Number

T 11457

Electronic OCLC #