Home| Contact Us| New Journals| Browse Journals| Journal Prices| For Authors|

Print ISSN: 2230 – 8776
Online ISSN:


  About JISM
  DLINE Portal Home
Home
Aims & Scope
Editorial Board
Current Issue
Next Issue
Previous Issue
Sample Issue
Upcoming Conferences
Self-archiving policy
Alert Services
Be a Reviewer
Publisher
Paper Submission
Subscription
Contact us
 
  How To Order
  Order Online
Price Information
Request for Complimentary
Print Copy
 
  For Authors
  Guidelines for Contributors
Online Submission
Call for Papers
Author Rights
 
 
RELATED JOURNALS
Journal of Digital Information Management (JDIM)
Journal of Multimedia Processing and Technologies (JMPT)
International Journal of Web Application (IJWA)

 

 
Journal of Information & Systems Management (JISM)

Scheduling Algorithm for the Efficient Management of Memory and Cache
Will Lunniss, Robert I. Davis and Sebastian Altmeyer
Department of Computer Science University of York, York, UK., Department of Computer Science University of York, York, UK
Abstract: In real-time multitasking systems, the scheduling algorithm is one of the most critical factors in meeting response time requirements while maximizing system resources. There are two popular scheduling algorithms: fixed priority (FP), which has been studied in detail before. Still, we haven’t compared them in the context of cache-related pre-emption (CRPD) delays. Memory and cache are divided into several blocks with instructions and stored data. When a task is pre-empted, cache blocks from that task can evict blocks from the preempted task. When the task is restarted, if it has to load those evicted blocks again, CRPD is introduced, which affects the task schedulability.
Keywords: Pre-Emption Delays, Scheduling Algorithms, Memory And Cache
DOI:https://doi.org/10.6025/jism/2024/14/1/8-33
Full_Text   PDF 1.85 MB   Download:   7  times
References:

[1] Altmeyer, Sebastian., Burguière, Claire. (2009). A new notion of useful cache block to improve the bounds of cache-related preemption delay. In 21st Euromicro Conference on Real-Time Systems, ECRTS 2009, Dublin, Ireland, July 1–3, 2009 (pp. 109–118). IEEE Computer Society. doi:10.1109/ECRTS.2009.21.
[2] Altmeyer, Sebastian, Davis, Robert I., Maiza, Claire. (2011). Cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems. In Proceedings of the 32nd IEEE Real-Time Systems Symposium, RTSS 2011, Vienna, Austria, November 29 – December 2, 2011 (pp. 261–271). IEEE Computer Society. doi:10.1109/RTSS.2011.31.
[3] Altmeyer, Sebastian, Davis, Robert I., Maiza, Claire. (2012). Improved cache related preemption delay aware response time analysis for fixed priority preemptive systems. Real-Time Systems, 48(5), 499–526. doi:10.1007/s11241-012-9152-2.
[4] Altmeyer, Sebastian, Maiza, Claire., Reineke, Jan. (2010). Resilience analysis: tightening the CRPD bound for set-associative caches. In Proceedings of the ACM SIGPLAN/SIGBED 2010 Conference on Languages, Compilers, and Tools for Embedded Systems, LCTES 2010, Stockholm, Sweden, April 13–15, 2010 (pp. 153–162). ACM. doi:10.1145/1755888.1755911.
[5] Audsley, Neil C., Burns, Alan, Richardson, Mike F., Tindell, Ken, & Wellings, Andrew J. (1993). Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal, 8(5), 284–292. URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=238595&isnumber=6134.
[6] Baruah, Sanjoy K., Mok, Aloysius K., Rosier, Louis E. (1990). Preemptively scheduling hardreal-time sporadic tasks on one processor. In Proceedings of the Real-Time Systems Symposium – 1990, Lake Buena Vista, Florida, USA, December 1990 (pp. 182–190). IEEE Computer Society. doi:10.1109/REAL.1990.128746.
[7] Baruah, Sanjoy K., Rosier, Louis E., Howell, Rodney R. (1990). Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor. Real-Time Systems, 2(4), 301–324. doi:10.1007/BF01995675.
[8] Bastoni, Andrea, Brandenburg, Björn B., Anderson, James H. (2010). Cache-related preemption and migration delays: Empirical approximation and impact on schedulability. In Proceedings of the 6th International Workshop on Operating Systems Platforms for Embedded Real-Time Applications, OSPERT 2010 (pp. 33–44). URL: http://www.mpi-sws.org/~bbb/papers/ pdf/ospert10.pdf.
[9] Bini, Enrico, & Buttazzo, Giorgio C. (2005). Measuring the performance of schedulability tests. Real-Time Systems, 30(1-2), 129–154. doi:10.1007/s11241-005-0507-9.
[10] Brandenburg, Björn B., Leontyev, Hennadiy, Anderson, James H. (2009). Accounting for interrupts in multiprocessor real-time systems. In 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2009, Beijing, China, 24–26 August 2009 (pp. 273–283). IEEE Computer Society. doi:10.1109/RTCSA.2009.37.
[11] Burguière, Claire, Reineke, Jan, Altmeyer, Sebastian. (2009). Cache-related preemption delay computation for set-associative caches - pitfalls and solutions. In 9th International Workshop on Worst-Case Execution Time Analysis, WCET 2009, Dublin, Ireland, July 1–3, 2009 (Vol. 10 of OASICS, pp. 1–11). Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik. doi:10.4230/ OASIcs.WCET.2009.2285.
[12] Busquets-Mataix, José V., Serrano, Juan José, Ors, Rafael, Gil, Pedro J., Wellings, Andy J. (1996). Adding instruction cache effect to schedulability analysis of preemptive real-time systems. In 2nd IEEE Real-Time Technology and Applications Symposium, RTAS 1996, June 10–12, 1996, Boston, MA, USA (p. 204). IEEE Computer Society. doi:10.1109/RTTAS.1996.509537.,
[13] Buttazzo, Giorgio C. (2005). Rate monotonic vs. EDF: judgment day. Real-Time Systems 29(1), 5–26. doi:10.1023/B:TIME.0000048932.30002.d9.
[14] Davis, Robert I., Zabos, A., Burns, Alan. (2008). Efficient exact schedulability tests for fixed priority real-time systems. IEEE Transactions on Computers, 57(9), 1261–1276. doi:10.1109/TC.2008.66.
[15] Dertouzos, Michael L. (1974). Control robotics: The procedural control of physical processes. In IFIP Congress (pp. 807–813).
[16] George, Laurent, Rivierre, Nicolas., Spuri, Marco. (1996). Preemptive and non-preemptive real-time uniprocessor scheduling. Technical report, INRIA. URL: http://hal.inria.fr/inria00073732.
[17] Ju, Lei, Chakraborty, Samarjit., Roychoudhury, Abhik. (2007). Accounting for cache-related preemption delay in dynamic priority schedulability analysis. In 2007 Design, Automation and Test in Europe Conference and Exposition, DATE 2007, April 16–20, 2007, Nice, France (pp. 1623– 1628). ACM. URL: http://dl.acm.org/citation.cfm?id=1266366.1266723.
[18] Lee, Chang-Gun, Hahn, Joosun, Seo, Yang-Min, Min, Sang Lyul, Ha, Rhan, Hong, Seongsoo, Park, Chang Yun, Lee, Minsuk., Kim, Chong-Sang. (1998). Analysis of cache-related preemption delay in fixed-priority preemptive scheduling. IEEE Trans. Computers, 47(6), 700–713. doi:10.1109/ 12.689649.
[19] Leung, Joseph Y.-T., Merrill, M. L. (1980). A note on preemptive scheduling of periodic, real-time tasks. Information Processing Letters, 11(3), 115–118. doi:10.1016/0020- 0190(80)90123-4.
[20] Liu, C. L., Layland, James W. (1973). Scheduling algorithms for multiprogramming in a hard-realtime environment. Journal of the ACM, 20(1), 46–61. doi:10.1145/321738.321743.
[21] Lunniss, Will, Altmeyer, Sebastian.,Davis, Robert I. (2012). Optimising task layout to increase schedulability via reduced cache related preemption delays. In 20th International Conference on Real-Time and Network Systems, RTNS 2012, Pont a Mousson, France – November 08–09, 2012 (pp. 161–170). ACM. doi:10.1145/2392987.2393008.
[22] Lunniss, Will, Altmeyer, Sebastian, Maiza, Claire., Davis, Robert I. (2013). Integrating cache related preemption delay analysis into EDF scheduling. In 19th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2013, Philadelphia, PA, USA, April 9–11, 2013 (pp. 75–84). IEEE Computer Society. doi:10.1109/RTAS.2013.6531081.
[23] Ripoll, Ismael, Crespo, Alfons., Mok, Aloysius K. (1996). Improvement in feasibility testing for realtime tasks. Real-Time Systems, 11(1), 19–39. doi:10.1007/BF00365519.
[24] Spuri, Marco. (1996). Analysis of deadline scheduled realtime systems. Technical report, INRIA. URL: http://hal.inria.fr/inria-00073920.
[25] Staschulat, Jan, Schliecker, Simon., Ernst, Rolf. (2005). Scheduling analysis of real-time systems with precise modeling of cache related preemption delay. In 17th Euromicro Conference on Real-Time Systems, ECRTS 2005, 6–8 July 2005, Palma de Mallorca, Spain (pp. 41–48). IEEE Computer Society. doi:10.1109/ECRTS.2005.26.
[26] Tan, Yudong., Mooney III, Vincent John. (2007). Timing analysis for preemptive multitasking realtime systems with caches. ACM Transactions on Embedded Computing Systems (TECS), 6(1). doi:10.1145/1210268.1210275.
[27] Zhang, Fengxiang., Burns, Alan. (2009). Schedulability analysis for real-time systems with EDF scheduling. IEEE Transactions on Computers, 58(9), 1250–1258. doi:10.1109/ TC.2009.58.


Home | Aim & Scope | Editorial Board | Author Guidelines | Publisher | Subscription | Previous Issue | Contact Us |Upcoming Conferences|Sample Issues|Library Recommendation Form|

 

Copyright © 2011 dline.info