考虑缓存预热时间的多核实时调度算法和分析
|
摘要
由于功耗和散热的问题,处理器的设计正往多核方向发展。多核处理器不仅应用在一般的计算机系统中,而且正不断的应用到嵌入式系统中。这样的系统往往也是实时系统。在实时系统中,计算的正确性不仅依赖于结果的正确性而且依赖于结果产生时间的正确性。
多核处理器带给实时系统的不仅是高效的处理能力而且还有复杂的任务调度。在单处理器系统中,计算任务最坏情况执行时间(WCET)时,一般认为任务的缓冲行都在缓存中,通过静态分析用缓存延迟得到。然而在多核处理器系统中,有的核上的缓存并没有任务的缓冲行。当任务运行在这样的核上时,会增大任务的WCET,增大的这部分时间称为缓存预热时间。解决缓存预热时间对多核实时调度产生的影响是一个重要的问题。
可调度性分析是研究实时调度的重要手段,主要有两种方法:模拟和利用率的边界测试。模拟的方法尽管实现简单,但它只检测了系统运行的有限路径,所以得到的可调度任务集数目并不可靠。利用率边界测试往往只能推导出充分条件,由此获得的可调度任务集数目较为悲观。由于这些原因,研究者提出使用模型检测的方法,对多处理器调度算法进行可调度性分析。但他们都没有考虑缓存预热时间对可调度性分析的影响。针对这一问题,本论文基于模型检测,提出一种考虑了缓存预热时间的可调度性分析的方法,并以静态优先级调度算法单调速率(RM)为例,说明了这种方法的有效性。
在采用多核RM算法的调度系统中,缓存预热时间会导致一些任务集错失截止时间。为了降低缓存预热时间带来的不可预测性,研究者提出新的硬件架构Push Block,预先将任务的缓冲行迁移到目的核缓存中。当任务在目的核上运行时,就不会产生缓存预热时间。然而,现有的调度算法并不支持这种架构。针对这个问题,本论文以静态优先级调度算法RM为基础,结合这种新架构所提供的功能,给出了三种策略,提出了一个新的静态优先级调度算法,提高了系统实时性,减少了错失截止时间的任务集。
在静态优先级调度中,系统运行时,任务优先级是固定的。这可能导致一个高优先级任务长时间占有CPU,而低优先级的任务必须等待。因此,产生了动态优先级调度。在系统运行时,它可以改变任务的优先级,增强了对环境的调整能力。不幸的是缓存预热时间仍然会导致采用了动态优先级调度算法的系统错失截止时间。另外,目前的多核动态优先级调度算法并没有建立在新架构Push Block上,无法利用预迁移机制提高算法的性能。针对这些问题,本论文以经典的动态优先级调度算法最短截止时间优先(EDF)为基础,提出了适应缓存预热时间的动态优先级调度算法。通过实验,展示了新算法良好的性能。综上所述,本论文研究中所做出的主要贡献体现在以下三个方面:
1)针对以往的可调度性分析没有考虑缓存预热时间的问题,提出了基于模型检测,考虑缓存预热时间的可调度性分析方法,并以RM算法为例,验证了方法的有效性。
2)针对缓存预热时间导致经典的静态优先级调度算法RM实时性降低的问题,给出了降低缓存预热时间的三种策略,提出了适应缓存预热时间的静态优先级调度算法WM-RM,既保留了RM算法的良好性能,同时提高了适应缓存预热时间的能力。
3)针对缓存预热时间导致经典的动态优先级调度算法EDF实时性降低的问题,提出了适应缓存预热时间的动态优先级调度算法WM-EDF,与EDF算法相比增强了算法的实时性。
As the power consumption and thermal dissipation problems, researchers propose Chip Multiple Processor. Now multicore processors are not only used into general purpose computing systems, and are constantly applied into embedded systems, which are usually real-time systems. In these systems, the correctness of computation depends not only on correctness of results but also the time when the results are generated.
Multicore processor brings real-time systems the efficient process ability and the complex task scheduling. In the single processor system, a general assumption is that the cache lines of a task are all in the cache. We can get its worst case execution time(WCET) with static analysis by cache hit delay. However, in the multicore processor system, there are some cores on which the caches don’t have any lines of the task. Once a task runs on these cores, its WCET will dilate due to cache warm-up overhead. It is an important problem for solving the impacts of cache warm-up overhead in multicore real-time scheduling.
Schedulability analysis is an important means for real-time scheduling research. There are mainly two methods for schedulability analysis: simulation and utilization bound test. Simulation is easy to implement, but it only tests finite running paths of a system. So the result of scheduable tasksets is not reliable. Bound utilization test often gets sufficient conditions and the result is pessimistic. For the disadvantages of the two methods, model checking is utilized by some researchers for schedulability analysis. However, they don’t focus on the impact of cache warm-up overhead to schedulability analysis. For this problem, based on model checking this thesis proposes a schedulability analysis method considering cache warm-up overhead and illustrates the efficiency of this method with a classical scheduling algorithm named rate monotonic(RM).
For the impact of cache warm-up overhead, there are some tasksets missing their deadlines under multicore RM algorithm. To reduce the unpredictability brought by cache warm-up overhead, some researchers propose the new hardware architecture Push Block, proactively migrating the cache lines of a task to the cache of the target core. When the task runs on the core which already has the cache lines of the task, there is no time wasting in warming up the cache of the core. However, current scheduling algorithms don’t support this architecture. For this problem, this paper is constructed on the static priority scheduling algorithm RM. Using the function provided by the new architecture, we presents three strategies and proposes a new static priority scheduling algorithm, which improves system timeliness and reduces the number of tasksets missing deadlines.
In static priority scheduling, the priority of a task is fixed during the system running. This may result in a high-priority task holds a CPU for a long time and low-priority tasks have to wait. Therefore, the dynamic priority scheduling is proposed. It can change priorities of tasks in system running and improve the adjust ability to variable environments. Unfortunately, cache warm-up overhead still causes the system with the dynamic scheduling algorithm missing deadline. In addition, the current multicore dynamic scheduling algorithms don’t use the new architecture named Push Block and can’t improve the performance with this mechanism. For these problems, this thesis proposes a new dynamic scheduling algorithm based on the classical dynamic scheduling algorithm called earliest deadline first(EDF) and presents good performance through experiments.
In summary, the main innovative contributions of this thesis include the three aspects,
1) For the previous schedulability analyses don’t consider cache warm-up overhead, we propose an exact schedulability analysis method based on model checking and illustrates the efficiency with RM algorithm.
2) For cache warm-up overhead results in the timeliness of the classical static priority scheduling algorithm RM reduces, we present three strategies and propose a new algorithm named WM-RM, which retains the performance of RM and improves the ability for adapting to cache warm-up overhead.
3) For cache warm-up overhead results in the timeliness of the classical dynamic priority scheduling algorithm EDF reduces, we propose a new algorithm called WM-EDF, which improves the timeliness of a system comparing to EDF.
多核处理器带给实时系统的不仅是高效的处理能力而且还有复杂的任务调度。在单处理器系统中,计算任务最坏情况执行时间(WCET)时,一般认为任务的缓冲行都在缓存中,通过静态分析用缓存延迟得到。然而在多核处理器系统中,有的核上的缓存并没有任务的缓冲行。当任务运行在这样的核上时,会增大任务的WCET,增大的这部分时间称为缓存预热时间。解决缓存预热时间对多核实时调度产生的影响是一个重要的问题。
可调度性分析是研究实时调度的重要手段,主要有两种方法:模拟和利用率的边界测试。模拟的方法尽管实现简单,但它只检测了系统运行的有限路径,所以得到的可调度任务集数目并不可靠。利用率边界测试往往只能推导出充分条件,由此获得的可调度任务集数目较为悲观。由于这些原因,研究者提出使用模型检测的方法,对多处理器调度算法进行可调度性分析。但他们都没有考虑缓存预热时间对可调度性分析的影响。针对这一问题,本论文基于模型检测,提出一种考虑了缓存预热时间的可调度性分析的方法,并以静态优先级调度算法单调速率(RM)为例,说明了这种方法的有效性。
在采用多核RM算法的调度系统中,缓存预热时间会导致一些任务集错失截止时间。为了降低缓存预热时间带来的不可预测性,研究者提出新的硬件架构Push Block,预先将任务的缓冲行迁移到目的核缓存中。当任务在目的核上运行时,就不会产生缓存预热时间。然而,现有的调度算法并不支持这种架构。针对这个问题,本论文以静态优先级调度算法RM为基础,结合这种新架构所提供的功能,给出了三种策略,提出了一个新的静态优先级调度算法,提高了系统实时性,减少了错失截止时间的任务集。
在静态优先级调度中,系统运行时,任务优先级是固定的。这可能导致一个高优先级任务长时间占有CPU,而低优先级的任务必须等待。因此,产生了动态优先级调度。在系统运行时,它可以改变任务的优先级,增强了对环境的调整能力。不幸的是缓存预热时间仍然会导致采用了动态优先级调度算法的系统错失截止时间。另外,目前的多核动态优先级调度算法并没有建立在新架构Push Block上,无法利用预迁移机制提高算法的性能。针对这些问题,本论文以经典的动态优先级调度算法最短截止时间优先(EDF)为基础,提出了适应缓存预热时间的动态优先级调度算法。通过实验,展示了新算法良好的性能。综上所述,本论文研究中所做出的主要贡献体现在以下三个方面:
1)针对以往的可调度性分析没有考虑缓存预热时间的问题,提出了基于模型检测,考虑缓存预热时间的可调度性分析方法,并以RM算法为例,验证了方法的有效性。
2)针对缓存预热时间导致经典的静态优先级调度算法RM实时性降低的问题,给出了降低缓存预热时间的三种策略,提出了适应缓存预热时间的静态优先级调度算法WM-RM,既保留了RM算法的良好性能,同时提高了适应缓存预热时间的能力。
3)针对缓存预热时间导致经典的动态优先级调度算法EDF实时性降低的问题,提出了适应缓存预热时间的动态优先级调度算法WM-EDF,与EDF算法相比增强了算法的实时性。
As the power consumption and thermal dissipation problems, researchers propose Chip Multiple Processor. Now multicore processors are not only used into general purpose computing systems, and are constantly applied into embedded systems, which are usually real-time systems. In these systems, the correctness of computation depends not only on correctness of results but also the time when the results are generated.
Multicore processor brings real-time systems the efficient process ability and the complex task scheduling. In the single processor system, a general assumption is that the cache lines of a task are all in the cache. We can get its worst case execution time(WCET) with static analysis by cache hit delay. However, in the multicore processor system, there are some cores on which the caches don’t have any lines of the task. Once a task runs on these cores, its WCET will dilate due to cache warm-up overhead. It is an important problem for solving the impacts of cache warm-up overhead in multicore real-time scheduling.
Schedulability analysis is an important means for real-time scheduling research. There are mainly two methods for schedulability analysis: simulation and utilization bound test. Simulation is easy to implement, but it only tests finite running paths of a system. So the result of scheduable tasksets is not reliable. Bound utilization test often gets sufficient conditions and the result is pessimistic. For the disadvantages of the two methods, model checking is utilized by some researchers for schedulability analysis. However, they don’t focus on the impact of cache warm-up overhead to schedulability analysis. For this problem, based on model checking this thesis proposes a schedulability analysis method considering cache warm-up overhead and illustrates the efficiency of this method with a classical scheduling algorithm named rate monotonic(RM).
For the impact of cache warm-up overhead, there are some tasksets missing their deadlines under multicore RM algorithm. To reduce the unpredictability brought by cache warm-up overhead, some researchers propose the new hardware architecture Push Block, proactively migrating the cache lines of a task to the cache of the target core. When the task runs on the core which already has the cache lines of the task, there is no time wasting in warming up the cache of the core. However, current scheduling algorithms don’t support this architecture. For this problem, this paper is constructed on the static priority scheduling algorithm RM. Using the function provided by the new architecture, we presents three strategies and proposes a new static priority scheduling algorithm, which improves system timeliness and reduces the number of tasksets missing deadlines.
In static priority scheduling, the priority of a task is fixed during the system running. This may result in a high-priority task holds a CPU for a long time and low-priority tasks have to wait. Therefore, the dynamic priority scheduling is proposed. It can change priorities of tasks in system running and improve the adjust ability to variable environments. Unfortunately, cache warm-up overhead still causes the system with the dynamic scheduling algorithm missing deadline. In addition, the current multicore dynamic scheduling algorithms don’t use the new architecture named Push Block and can’t improve the performance with this mechanism. For these problems, this thesis proposes a new dynamic scheduling algorithm based on the classical dynamic scheduling algorithm called earliest deadline first(EDF) and presents good performance through experiments.
In summary, the main innovative contributions of this thesis include the three aspects,
1) For the previous schedulability analyses don’t consider cache warm-up overhead, we propose an exact schedulability analysis method based on model checking and illustrates the efficiency with RM algorithm.
2) For cache warm-up overhead results in the timeliness of the classical static priority scheduling algorithm RM reduces, we present three strategies and propose a new algorithm named WM-RM, which retains the performance of RM and improves the ability for adapting to cache warm-up overhead.
3) For cache warm-up overhead results in the timeliness of the classical dynamic priority scheduling algorithm EDF reduces, we propose a new algorithm called WM-EDF, which improves the timeliness of a system comparing to EDF.
引文
[1] C. L. Liu and James W. Layland, Scheduling algorithms for multiprogramming in a hard-real-time environment, Journal of the ACM, v.20 n.1, p.46-61, Jan. 1973, New York, NY, USA.
[2] Michael R.Garey and David S. Johnson, Computers and intractability: a guide to the theory of NP-Completeness, 1979, W.H. Freeman & Co. New York, NY, USA.
[3] Rhan Ha and Liu J W S, Validating timing constraints in multiprocessor and distributed real-time systems, In Proceedings of the 14th IEEE International Conference on Distributed Computing Systems, p.162-171, Jun. 1994, Poznan, Poland.
[4] John P. Lehoczky, Lui Sha and Y. Ding, The rate monotonic scheduling algorithm: exact characterization and average case behavior, In Proceedings of the 10th IEEE Real-Time Systems Symposium, p.166-171, Dec. 1989, Santa Monica, CA, USA.
[5] Paul K. Harter, Response times in level structured systems, ACM Transactions on Compugter Systems, v.5, n.3, p.232-248, Aug. 1987, New York, NY, USA.
[6] J. Y. T. Leung and J. Whitehead, On the complexity of fixed-priority scheduling of periodic real-time tasks, Performance Evaluation, v.2, n.4, p.237-250, 1982.
[7] J. P. Lehoczky, Fixed priority scheduling of periodic tasks sets with arbitrary deadlines, In Proceedings of the 11th IEEE Real-Time Systems Symposium, p.201-209, Dec. 1990, Lake Buena Vista, FL, USA.
[8] K. W. Tindell, A. Burns and A. J. Wellings, An extendible approach for analysing fixed priority hard real-time tasks, Real-Time Systems, v.6, n.2, p.133-15, March 1994, Kluwer Academic Publishers Norwell, MA, USA.
[9] Ken Tindell and John Clark, Holistic schedulability analysis for distributed hard real-time systems, Microprocessing and Microprogramming - Parallel processing in embedded real-time systems, v.40, n.2-3, pp. 117-134, April 1994, Elsevier Science Publishers B. V. Amsterdam, The Netherlands, The Netherlands.
[10] N. C. Audsley, R. I. Davis, and A. Burns, Mechanisms for enhancing the flexibility and utility of hard real-time systems, In Proceddings of the 15th IEEE Real-Time Systems Symposium, p.12-21, Dec. 1994, San Juan.
[11] Michael L. Dertouzos, Control robotics: the procedural control of physical processes, In Proceedings of IFIP Congress, p.807-813, 1974.
[12] A. K Mok, Fundamental design problems of distributed systems for the hard real-time environment, Ph.D. thesis, 1983, Massachusetts Institute of Technology Cambridge, MA, USA.
[13] S. K. Baruah, N. K. Cohen, C. G. Plaxton and D. A. Varvel, Proportionate progress: a notion of fairness in resource allocation, Algorithmica, v.15, no. 6, p.600-625, June 1996.
[14] S. K. Baruah, J. E. Gehrke and C. G. Plaxton, Fast scheduling of periodic tasks on multiple resources, In Proc. of the 9th Intl. Parallel Processing Symposium, p.280- 288, April 1995, Santa Barbara, CA, USA.
[15] J. H. Anderson and A. Srinivasan, Early-release fair scheduling, In Proc. of the 12th Euromicro Conference on Real-Time Systems, p.35-43, Jun. 2000, Stockholm, Sweden.
[16] J. H. Anderson and A. Srinivasan, Pfair scheduling: beyond periodic task systems, In Proc. of 17th Intl. Conf. Real-Time Computing Systems and Applications, Dec. 2000, Cheju Island, South Korea.
[17] J. H. Anderson and A. Srinivasan, Mixed Pfair/ERfair scheduling of asynchronous periodic task, In Proc. of 13th Euromicro Conference on Real-Time Systems, p.76-85, Jun. 2001, Delft, Netherlands.
[18] B. Andersson, S. Baruah and J. Jonsson, Static-priority scheduling on multiprocessors, In Proc. of the 22nd IEEE Real-Time Systems Symposium, p.193–202, Dec. 2001, London, UK.
[19] S. K. Baruah and J. Goossens, Rate-Monotonic scheduling on uniform multiprocessors, IEEE Trans. on Computers v.52, n.7, p.966–970, Jul. 2003, IEEE Computer Society Washington, DC, USA.
[20] Theodore P. Baker, An analysis of fixed-priority schedulability on a multiprocessor, Real-Time Systems, v.32, n.1-2, p.49–71, Feb. 2006, Kluwer Academic Publisher Norwell, MA, USA.
[21] Marko Bertogna, Michele Cirinei and Giuseppe Lipari, Schedulability analysis of global scheduling algorithms on multiprocessor platforms, In IEEE Trans. on Parallel and Distributed Systems, v.20, n.4, p.553-566, 2009, IEEE Press Piscataway, NJ, USA.
[22] Jo?l Goossens, Shelby Funk, and Sanjoy Baruah, Priority-driven scheduling of periodic task systems on multiprocessors, Real-Time Systems, v.25, n.2-3, p.187–205, Sep.-Oct. 2003, Kluwer Academic Publisher Norwell, MA, USA.
[23] Theodore P. Baker, Multiprocessor EDF and deadline monotonic schedulability analysis, In Proceedings of the 24th IEEE International Real-Time Systems Symposium, p.120–129, Dec. 2003, Cancun, Mexico.
[24] Theodore P. Baker, An analysis of EDF schedulability on a multiprocessor, IEEE Trans. On Parallel Distributed Systems, v.16, n.8, p.760–768, Aug. 2005, IEEE Press Piscataway, NJ, USA.
[25] M. Bertogna, M. Cirinei and G. Lipari, Improved schedulability analysis of edf on multiprocessor platforms, In Proceedings of the 17th Euromicro Conference on Real-Time Systems , p.209–218, July 2005, Palma de Mallorca, Balearic Islands, Spain.
[26] Alexandra Fedorova, M. Seltzer, C. Small and D. Nussbaum, Throughput-oriented scheduling on chip multithreading systems, Technical Report TR-17-04, Division of Engineering and Applied Sciences, Harvard University, 2004.
[27] David Tam, Reza Azimi and Michael Stumm, Thread clustering: sharing-aware scheduling on SMP-CMP-SMT multiprocessors, ACM SIGOPS Operating Systems Review, v.41 n.3, June 2007, New York, NY, USA.
[28] Vivy Suhendra, C. Raghavan and T. Mitra, Integrated scratchpad memory optimization and task scheduling for mpsoc architectures, In Proceedings of the International Conference on Compilers, architecture and synthesis for embedded systems, 2006, New York, NY, USA.
[29] Haakon Dybdahl and Per Stenstrom, An adaptive shared/private NUCA cache partitioning scheme for chip multiprocessors, In Proceedings of the IEEE 13th International Symposium on High-Performance Computer Architecture, p.2-12, Feb. 2007, Scottsdale, AZ.
[30] C. Liu, Anand Sivasubramaniam and M. Kandemir, Organizing the last line of defense before hitting the memory wall for CMPs, In Proceedings of the 10th International Symposium on High-Performance Computer Architecture, p.176-185, Feb. 2004, Madrid, Spain.
[31] Shimin Chen, P. B. Gibbons, M. Kozuch, V. Liaskovitis, A. Ailamaki, G. E. Blelloch, B. Falsafi, L. Fix, N. Hardavellas, T. C. Mowry and C. Wilkerson, Scheduling Threads for Constructive Cache Sharing on CMPs, In Proceedings of the 19th ACM Symposium on Parallel Algorithms and Architectures, p.105–115, June 2007, San Diego, CA, USA.
[32] Cho S and Jin L. Managing distributed shared l2 caches through os-level page allocation, In Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.455–468, Dec. 2006, Orlando, Florida, USA.
[33] Mohan Rajagopalan, Brian T. Lewis and Todd A. Anderson, Thread scheduling for multic-core platforms, In Proceedings of the 11th workshop on Hot topics in operating systems, May 2007, San Diego, CA, USA.
[34] Silas Boyd-Wickizer, Robert Morris and M. Frans Kaashoek, Reinventing scheduling for multicore systems, In Proceedings of the 12th workshop on Hot topics in operating systems, p.21-26, May 2009, Switzerland.
[35] Seonqbeom Kim, Dhruba Chandra and Yan Solihin, Fair cache sharing and partitioning on a chip multiprocessor architecture, In Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.111-122, Sep.-Oct. 2004, Raleigh, NC, USA.
[36] A. Fedorova, M. Seltzer and M. Smith, Cache-fair scheduling for chip multiprocessors, Technical Report TR-17-06, Division of Engineering and Applied Sciences, Harvard University, 2006.
[37] Ravi Iyer, CQoS: a Framework for Enabling QoS in Shared Caches of CMP Platforms, In Proceedings of the 18th International Conference on Supercomputing, p.257-266, 2004, Saint Malo, France.
[38] Jichuan Chang and Gurindar S. Sohi, Cooperative cache partitioning for chip multicprcessors, In Proceedings of the 21st International Conference on Supercomputing, p.242-252, 2007, Washington, USA.
[39] Jichuan Chang. and Gurinadar S. Sohi, Cooperative Caching for Chip Multiprocessors, In Proceedings of the 33th Annual International Symposium on Computer Architecture, p.264-276, June 2006, Wisconsin, USA.
[40] Thomas Y. Yeh and Glenn Reinman, Fast and fair:data-stream quality of service, In Proceedings of the International Conference on Compilers, architecture, and synthesis for embedded systems, p.237-248, Sep. 2005, San Francisco, California, USA.
[41] Tong Li, Dan Baumberger, David A. Koufaty and Scott Hahn, Efficient operating system scheduling for performance-asymmetric multi-core architectures, In Proceedings of the conference on supercomputing, p.1-11, Nov. 2007, Reno, NC, USA.
[42] J. H. Anderson, J. M. Calandrino and U. C. Devi, Real-time scheduling on multicore platforms, In Proceedings of 12th IEEE Real-Time and Embedded Technology and Applications Symposium, California, p.179–190, April 2006, San Jose, California, USA.
[43] James H. Anderson and John M. Calandrino, Parallel real-time task scheduling on multicore platforms, In Proceedings of 27th Real-Time Systems Symposium, p.89-100, Dec. 2006, Rio de Janeiro.
[44] John M. Calandrino and James H. Anderson, Cache-aware real-time scheduling on multicore platforms: Heuristics and a case study, In Proceedings of the 20th Euromicro Conference on Real-Time Systems, p.299-308, July 2008, Prague, Czech Republic.
[45] Jun Yan and Wei Zhang, WCET analysis for multi-core processors with shared l2 instruction caches, In Proceedings of the 14th Real-Time and Embedded Technology and Applications Symposium, p.80-89, 2008, St. Louis, Missouri, USA.
[46] Vivy Suhendra and Tulika Mitra, Exploring locking and partitioning for predictable shared caches on multi-cores, In Proceedings of the 45th Design Automation Conference, p.300-303, June 2008, Anaheim, CA, USA.
[47] Nan Guan, Martin Stigge, Wang Yi and Ge Yu, Cache-aware scheduling and analysis for multi-cores, In Proceedings of the 7th International Conference on Embedded software, p.245-254, Sep.-Oct. 2009, Salzburg, Austria.
[48] David Choffnes, Mark Astley and Michael J. Ward, Migration policies for multicore fair-share scheduling, ACM SIGOPS Operating Systems Review, v.42 n.1, p. 92-93, Jan. 2008, New York, NY, USA.
[49] Acquaviva A, Alimonda A, Carta S and Pittau M. Assessing task migration impact on embedded soft real-time streaming multimedia applications, EURASIP Journal on Embedded Systems–Operating System Support for Embedded Real-Time Applications, v.2, 2008, Hindawi Publishing Corp. New York, NY, USA.
[50] Kedar M. Katre, Harini Ramaprasad, A. Sarkar and F. Mueller, Policies for migration of real-time tasks in embedded multi-core systems, In Proceedings of Real-Time Systems Symposium, p.17-20, Dec. 2009, Washington, D.C., USA.
[51] Abhik Sarkar, F. Mueller, Harini Ramaprasad and S. Mohan, Push-assisted migration of real-time tasks in multi-core processors, In Proceedings of the SIGPLAN/SIGBED Conference on Languages, compilers, and tools for embedded systems, p.80-89, June 2009, Dublin, Ireland.
[52] Guan N, Gu Z H, Deng Q, et al. Exact schedulability analysis for static-priority global multiprocessor scheduling using model-checking. Proceedings of 5th IFIP Workshop on Software Technologies for Embedded and Ubiquitous Systems, Greece: Springer,pp.263–272, 2007.
[53] Nan Guan, Zonghua Gu, Mingsong Lv, Qingxu Deng and Ge Yu, Schedulability analysis of global Fixed-Priority or EDF multiprocessor scheduling, In Proceedings of 11th IEEE Symposium on Object Oriented Real-Time Distributed Computing, p.556-560, May 2008, Orlando, Flordia, USA.
[54] The UPPAAL Model-Checker, http://www.uppaal.com
[55] Cindy Eisner and Doron Peled, Comparing symbolic and explicit model checking of a software system, In Proceedings of the 9th International SPIN Workshop on Model Checking of Software, p.230-239, April 2002, Grenoble, France.
[56] H. Lin and W. Zhang, Model checking: Theories, techniques and applications. Chinese Journal of Electronics, 30(12A):1907?1912, 2002 (in Chinese with English abstract).
[57] G. J. Holzmann, Design and validation of computer protocols, 1991, Prentice Hall.
[58] Rajeev Alur and David L. Dill, A theory of timed automata, Theoretical Computer Science, v.126 n.2, p.183–235, April 1994, Elsevier Science Publishers Ltd. Essex, UK.
[59] T. A. Henzinger, The theory of hybrid automata, In Proceedings of the 11th Annual IEEE Symposium on Logic in Computer Science, p.278-293, July 1996, New Brunswick, New Jersey.
[60] Amir Pnueli, The temporal logic of programs, In Proceedings of the 18th Annual Symposium on Foundations of Computer Science, p. 46-57, Oct.-Nov. 1977.
[61] R. Alur, C. Courcoubetis, and D. Dill, Model-checking for real-time systems, In Proceedings of the 5th IEEE Symposium on Logic in Computer Science, p.414–425, June 1990, Philadelphia, PA, USA.
[62] Kenneth L. McMillan, Symbolic model checking, 1993, Kluwer Academic Publishers.
[63] Libor Waszniowski and Z. Hanzálek, Formal verification of multitasking applications based on timed automata model, Real-Time System, v.38 n.1, p.39-65, 2008, Kluwer Academic Publishers Norwell, MA, USA.
[64] Libor Waszniowski and Z. Hanzálek, Over-approximate model of multitasking application based on timed automata using only one clock, In Proceedings of the 19th Int. Parallel and Distributed Processing Symposium, p.128-135, April 2005, Denver, Colorado, USA.
[65] Zonghua Gu, Solving Real-Time Scheduling problems with model-checking, In Proceedings of International Conference on Embedded Software and Systems, p.186-197, Dec. 2005, Xi’an, China.
[66] James C. Corbett, Timing analysis of Ada tasking programs, IEEE Trans. on Software Engineering, v.22 n.7, p.461–483, July 1996, IEEE Press Piscataway, NJ, USA.
[67] Thorsten Gerdsmeier and Cardell-oliver Rachel, Analysis of scheduling behaviour using generic timed automata, Electronic Notes in Theoretical Computer Science, v.42, p.143-157, Jan. 2001.
[68] Kristina Lundqvist and Lars Asplund, A Ravenscar-compliant runtime kernel for safety-critical systems, Real-Time Systems, v.24 n.1, p.29-54, Jan. 2003, Kluwer Academic Publishers Norwell, MA, USA.
[69] Brian Dobbing and George Romanski, The Ravenscar tasking profile-experience reporting, In Proceedings of the 9th International workshop on Real-Time Ada, p.28-32, Mar. 1999, Wakulla Springs Lodge, Florida, USA.
[70] John Penix, Willem Visser, Eric Engstrom, A. Larson amd N. Weininger, Verification of time partitioning in the DEOS scheduler kernel, In Proceedings of the 22nd International Conference on Software Engineering, p.488–497, June 2000, Ireland.
[71] D. Cofer and M. Rangarajan, Formal verification of overhead accounting in an avionics RTOS, In Proceedings of the 23rd IEEE Real Time Systems Symposium, p.181-190, Dec. 2002, Austin, Texas, USA.
[72] C. Norstr?m, A. Wall and Wang Yi, Timed automata as task models for event driven systems. In Proceedings of the 6th International Conference on Real-Time Computing Systems and Applications, p.182-189, Dec. 1999, Hong Kong, China.
[73] E. Fersman, P. Pettersson and Wang Yi, Timed automata with asynchronous processes: schedulability and decidability, In Proceedings of the 8th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, p.67–82, April 2002, Grenoble, France.
[74] E. Fersman, P. Pettersson and Wang Yi, Schedulability analysis using two clocks, In Proceedings of the 9th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, p.224–239, April 2003, Warsaw, Poland.
[75] P. Krcál and Wang Yi, Decidable and undecidable problems in schedulability analysis using timed automata, In Proceedings of the 10th Int. Conference on Tools and Algorithms for the Construction and Analysis of Systems, p.236-250, Mar.-Apr. 2004, Barcelona, Spain.
[76] T. Amnell, E. Fersman, L. Mokrushin, P. Pettersson and W. Yi, Times-A tool for modeling and implementation of embedded systems, In Proceedings of the 8th Int. Conference on Tools and Algorithms for the Construction and Analysis of Systems, p. 460-464, April 2002, Grenoble, France..
[77] J. Krákora and Z. Hanzálek, Timed automata approach to CAN verification, In Proceedings of the 11th IFAC Symposium on Information Control Problems in Manufacturing, p.8-14, April 2004, Brazil.
[78] J. Krákora, L. Waszniowski, P. Pí?a and Z. Hanzálek, Timed automata approach to real time distributed system verification, In Proceedings of the 5th IEEE International workshop on Factory Communication Systems, p. 407–410, Sep. 2004.
[79] Nan Guan, Shuaihong Gao, Qingxu Deng, Ge Yu, Zonghua Gu, Exact schedulability analysis for static-priority global multiprocessor scheduling using model-checking, In Proceedings of the 5th IFIP WG10.2 Int. Conference on Software technologies for embedded and ubiquitous systems, p.263–272, May 2007, Santorini Island, Greece.
[80] Nan Guan, Z. Gu, M. Lv, Q. Deng and G. Yu, Schedulability analysis of global fixed-priority or EDF multiprocessor scheduling, In Proceedings of the 11th IEEE Symposium on Object Oriented Real-Time Distributed Computing, p.556-560, May 2008, Orlando, Florida.
[81] P. Krcal, M. Stigge and Wang Yi, Multi-processor schedulability analysis of preemptive real-time tasks with variable execution times, In Proceedings of the 5th International Conference on Formal Modeling and Analysis of Timed Systems, p.274–289, Oct. 2007, Szlzburg, Austria.
[82] B. Andersson, S. K. Baruah, and J. Jonsson, Static-priority scheduling on multiprocessors, In Proceedings of the 22nd IEEE Real-Time Systems Symposium, p.193–202, Dec. 2001, London, UK.
[83] M. Bertogna, M. Cirinei, and G. Lipari, Schedulability analysis of global scheduling algorithms on multiprocessor platforms, IEEE Trans. on Parallel and Distribute Systems, v.20 n.4, p.553-566, April 2009, IEEE Press Piscataway, NJ, USA.
[2] Michael R.Garey and David S. Johnson, Computers and intractability: a guide to the theory of NP-Completeness, 1979, W.H. Freeman & Co. New York, NY, USA.
[3] Rhan Ha and Liu J W S, Validating timing constraints in multiprocessor and distributed real-time systems, In Proceedings of the 14th IEEE International Conference on Distributed Computing Systems, p.162-171, Jun. 1994, Poznan, Poland.
[4] John P. Lehoczky, Lui Sha and Y. Ding, The rate monotonic scheduling algorithm: exact characterization and average case behavior, In Proceedings of the 10th IEEE Real-Time Systems Symposium, p.166-171, Dec. 1989, Santa Monica, CA, USA.
[5] Paul K. Harter, Response times in level structured systems, ACM Transactions on Compugter Systems, v.5, n.3, p.232-248, Aug. 1987, New York, NY, USA.
[6] J. Y. T. Leung and J. Whitehead, On the complexity of fixed-priority scheduling of periodic real-time tasks, Performance Evaluation, v.2, n.4, p.237-250, 1982.
[7] J. P. Lehoczky, Fixed priority scheduling of periodic tasks sets with arbitrary deadlines, In Proceedings of the 11th IEEE Real-Time Systems Symposium, p.201-209, Dec. 1990, Lake Buena Vista, FL, USA.
[8] K. W. Tindell, A. Burns and A. J. Wellings, An extendible approach for analysing fixed priority hard real-time tasks, Real-Time Systems, v.6, n.2, p.133-15, March 1994, Kluwer Academic Publishers Norwell, MA, USA.
[9] Ken Tindell and John Clark, Holistic schedulability analysis for distributed hard real-time systems, Microprocessing and Microprogramming - Parallel processing in embedded real-time systems, v.40, n.2-3, pp. 117-134, April 1994, Elsevier Science Publishers B. V. Amsterdam, The Netherlands, The Netherlands.
[10] N. C. Audsley, R. I. Davis, and A. Burns, Mechanisms for enhancing the flexibility and utility of hard real-time systems, In Proceddings of the 15th IEEE Real-Time Systems Symposium, p.12-21, Dec. 1994, San Juan.
[11] Michael L. Dertouzos, Control robotics: the procedural control of physical processes, In Proceedings of IFIP Congress, p.807-813, 1974.
[12] A. K Mok, Fundamental design problems of distributed systems for the hard real-time environment, Ph.D. thesis, 1983, Massachusetts Institute of Technology Cambridge, MA, USA.
[13] S. K. Baruah, N. K. Cohen, C. G. Plaxton and D. A. Varvel, Proportionate progress: a notion of fairness in resource allocation, Algorithmica, v.15, no. 6, p.600-625, June 1996.
[14] S. K. Baruah, J. E. Gehrke and C. G. Plaxton, Fast scheduling of periodic tasks on multiple resources, In Proc. of the 9th Intl. Parallel Processing Symposium, p.280- 288, April 1995, Santa Barbara, CA, USA.
[15] J. H. Anderson and A. Srinivasan, Early-release fair scheduling, In Proc. of the 12th Euromicro Conference on Real-Time Systems, p.35-43, Jun. 2000, Stockholm, Sweden.
[16] J. H. Anderson and A. Srinivasan, Pfair scheduling: beyond periodic task systems, In Proc. of 17th Intl. Conf. Real-Time Computing Systems and Applications, Dec. 2000, Cheju Island, South Korea.
[17] J. H. Anderson and A. Srinivasan, Mixed Pfair/ERfair scheduling of asynchronous periodic task, In Proc. of 13th Euromicro Conference on Real-Time Systems, p.76-85, Jun. 2001, Delft, Netherlands.
[18] B. Andersson, S. Baruah and J. Jonsson, Static-priority scheduling on multiprocessors, In Proc. of the 22nd IEEE Real-Time Systems Symposium, p.193–202, Dec. 2001, London, UK.
[19] S. K. Baruah and J. Goossens, Rate-Monotonic scheduling on uniform multiprocessors, IEEE Trans. on Computers v.52, n.7, p.966–970, Jul. 2003, IEEE Computer Society Washington, DC, USA.
[20] Theodore P. Baker, An analysis of fixed-priority schedulability on a multiprocessor, Real-Time Systems, v.32, n.1-2, p.49–71, Feb. 2006, Kluwer Academic Publisher Norwell, MA, USA.
[21] Marko Bertogna, Michele Cirinei and Giuseppe Lipari, Schedulability analysis of global scheduling algorithms on multiprocessor platforms, In IEEE Trans. on Parallel and Distributed Systems, v.20, n.4, p.553-566, 2009, IEEE Press Piscataway, NJ, USA.
[22] Jo?l Goossens, Shelby Funk, and Sanjoy Baruah, Priority-driven scheduling of periodic task systems on multiprocessors, Real-Time Systems, v.25, n.2-3, p.187–205, Sep.-Oct. 2003, Kluwer Academic Publisher Norwell, MA, USA.
[23] Theodore P. Baker, Multiprocessor EDF and deadline monotonic schedulability analysis, In Proceedings of the 24th IEEE International Real-Time Systems Symposium, p.120–129, Dec. 2003, Cancun, Mexico.
[24] Theodore P. Baker, An analysis of EDF schedulability on a multiprocessor, IEEE Trans. On Parallel Distributed Systems, v.16, n.8, p.760–768, Aug. 2005, IEEE Press Piscataway, NJ, USA.
[25] M. Bertogna, M. Cirinei and G. Lipari, Improved schedulability analysis of edf on multiprocessor platforms, In Proceedings of the 17th Euromicro Conference on Real-Time Systems , p.209–218, July 2005, Palma de Mallorca, Balearic Islands, Spain.
[26] Alexandra Fedorova, M. Seltzer, C. Small and D. Nussbaum, Throughput-oriented scheduling on chip multithreading systems, Technical Report TR-17-04, Division of Engineering and Applied Sciences, Harvard University, 2004.
[27] David Tam, Reza Azimi and Michael Stumm, Thread clustering: sharing-aware scheduling on SMP-CMP-SMT multiprocessors, ACM SIGOPS Operating Systems Review, v.41 n.3, June 2007, New York, NY, USA.
[28] Vivy Suhendra, C. Raghavan and T. Mitra, Integrated scratchpad memory optimization and task scheduling for mpsoc architectures, In Proceedings of the International Conference on Compilers, architecture and synthesis for embedded systems, 2006, New York, NY, USA.
[29] Haakon Dybdahl and Per Stenstrom, An adaptive shared/private NUCA cache partitioning scheme for chip multiprocessors, In Proceedings of the IEEE 13th International Symposium on High-Performance Computer Architecture, p.2-12, Feb. 2007, Scottsdale, AZ.
[30] C. Liu, Anand Sivasubramaniam and M. Kandemir, Organizing the last line of defense before hitting the memory wall for CMPs, In Proceedings of the 10th International Symposium on High-Performance Computer Architecture, p.176-185, Feb. 2004, Madrid, Spain.
[31] Shimin Chen, P. B. Gibbons, M. Kozuch, V. Liaskovitis, A. Ailamaki, G. E. Blelloch, B. Falsafi, L. Fix, N. Hardavellas, T. C. Mowry and C. Wilkerson, Scheduling Threads for Constructive Cache Sharing on CMPs, In Proceedings of the 19th ACM Symposium on Parallel Algorithms and Architectures, p.105–115, June 2007, San Diego, CA, USA.
[32] Cho S and Jin L. Managing distributed shared l2 caches through os-level page allocation, In Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.455–468, Dec. 2006, Orlando, Florida, USA.
[33] Mohan Rajagopalan, Brian T. Lewis and Todd A. Anderson, Thread scheduling for multic-core platforms, In Proceedings of the 11th workshop on Hot topics in operating systems, May 2007, San Diego, CA, USA.
[34] Silas Boyd-Wickizer, Robert Morris and M. Frans Kaashoek, Reinventing scheduling for multicore systems, In Proceedings of the 12th workshop on Hot topics in operating systems, p.21-26, May 2009, Switzerland.
[35] Seonqbeom Kim, Dhruba Chandra and Yan Solihin, Fair cache sharing and partitioning on a chip multiprocessor architecture, In Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.111-122, Sep.-Oct. 2004, Raleigh, NC, USA.
[36] A. Fedorova, M. Seltzer and M. Smith, Cache-fair scheduling for chip multiprocessors, Technical Report TR-17-06, Division of Engineering and Applied Sciences, Harvard University, 2006.
[37] Ravi Iyer, CQoS: a Framework for Enabling QoS in Shared Caches of CMP Platforms, In Proceedings of the 18th International Conference on Supercomputing, p.257-266, 2004, Saint Malo, France.
[38] Jichuan Chang and Gurindar S. Sohi, Cooperative cache partitioning for chip multicprcessors, In Proceedings of the 21st International Conference on Supercomputing, p.242-252, 2007, Washington, USA.
[39] Jichuan Chang. and Gurinadar S. Sohi, Cooperative Caching for Chip Multiprocessors, In Proceedings of the 33th Annual International Symposium on Computer Architecture, p.264-276, June 2006, Wisconsin, USA.
[40] Thomas Y. Yeh and Glenn Reinman, Fast and fair:data-stream quality of service, In Proceedings of the International Conference on Compilers, architecture, and synthesis for embedded systems, p.237-248, Sep. 2005, San Francisco, California, USA.
[41] Tong Li, Dan Baumberger, David A. Koufaty and Scott Hahn, Efficient operating system scheduling for performance-asymmetric multi-core architectures, In Proceedings of the conference on supercomputing, p.1-11, Nov. 2007, Reno, NC, USA.
[42] J. H. Anderson, J. M. Calandrino and U. C. Devi, Real-time scheduling on multicore platforms, In Proceedings of 12th IEEE Real-Time and Embedded Technology and Applications Symposium, California, p.179–190, April 2006, San Jose, California, USA.
[43] James H. Anderson and John M. Calandrino, Parallel real-time task scheduling on multicore platforms, In Proceedings of 27th Real-Time Systems Symposium, p.89-100, Dec. 2006, Rio de Janeiro.
[44] John M. Calandrino and James H. Anderson, Cache-aware real-time scheduling on multicore platforms: Heuristics and a case study, In Proceedings of the 20th Euromicro Conference on Real-Time Systems, p.299-308, July 2008, Prague, Czech Republic.
[45] Jun Yan and Wei Zhang, WCET analysis for multi-core processors with shared l2 instruction caches, In Proceedings of the 14th Real-Time and Embedded Technology and Applications Symposium, p.80-89, 2008, St. Louis, Missouri, USA.
[46] Vivy Suhendra and Tulika Mitra, Exploring locking and partitioning for predictable shared caches on multi-cores, In Proceedings of the 45th Design Automation Conference, p.300-303, June 2008, Anaheim, CA, USA.
[47] Nan Guan, Martin Stigge, Wang Yi and Ge Yu, Cache-aware scheduling and analysis for multi-cores, In Proceedings of the 7th International Conference on Embedded software, p.245-254, Sep.-Oct. 2009, Salzburg, Austria.
[48] David Choffnes, Mark Astley and Michael J. Ward, Migration policies for multicore fair-share scheduling, ACM SIGOPS Operating Systems Review, v.42 n.1, p. 92-93, Jan. 2008, New York, NY, USA.
[49] Acquaviva A, Alimonda A, Carta S and Pittau M. Assessing task migration impact on embedded soft real-time streaming multimedia applications, EURASIP Journal on Embedded Systems–Operating System Support for Embedded Real-Time Applications, v.2, 2008, Hindawi Publishing Corp. New York, NY, USA.
[50] Kedar M. Katre, Harini Ramaprasad, A. Sarkar and F. Mueller, Policies for migration of real-time tasks in embedded multi-core systems, In Proceedings of Real-Time Systems Symposium, p.17-20, Dec. 2009, Washington, D.C., USA.
[51] Abhik Sarkar, F. Mueller, Harini Ramaprasad and S. Mohan, Push-assisted migration of real-time tasks in multi-core processors, In Proceedings of the SIGPLAN/SIGBED Conference on Languages, compilers, and tools for embedded systems, p.80-89, June 2009, Dublin, Ireland.
[52] Guan N, Gu Z H, Deng Q, et al. Exact schedulability analysis for static-priority global multiprocessor scheduling using model-checking. Proceedings of 5th IFIP Workshop on Software Technologies for Embedded and Ubiquitous Systems, Greece: Springer,pp.263–272, 2007.
[53] Nan Guan, Zonghua Gu, Mingsong Lv, Qingxu Deng and Ge Yu, Schedulability analysis of global Fixed-Priority or EDF multiprocessor scheduling, In Proceedings of 11th IEEE Symposium on Object Oriented Real-Time Distributed Computing, p.556-560, May 2008, Orlando, Flordia, USA.
[54] The UPPAAL Model-Checker, http://www.uppaal.com
[55] Cindy Eisner and Doron Peled, Comparing symbolic and explicit model checking of a software system, In Proceedings of the 9th International SPIN Workshop on Model Checking of Software, p.230-239, April 2002, Grenoble, France.
[56] H. Lin and W. Zhang, Model checking: Theories, techniques and applications. Chinese Journal of Electronics, 30(12A):1907?1912, 2002 (in Chinese with English abstract).
[57] G. J. Holzmann, Design and validation of computer protocols, 1991, Prentice Hall.
[58] Rajeev Alur and David L. Dill, A theory of timed automata, Theoretical Computer Science, v.126 n.2, p.183–235, April 1994, Elsevier Science Publishers Ltd. Essex, UK.
[59] T. A. Henzinger, The theory of hybrid automata, In Proceedings of the 11th Annual IEEE Symposium on Logic in Computer Science, p.278-293, July 1996, New Brunswick, New Jersey.
[60] Amir Pnueli, The temporal logic of programs, In Proceedings of the 18th Annual Symposium on Foundations of Computer Science, p. 46-57, Oct.-Nov. 1977.
[61] R. Alur, C. Courcoubetis, and D. Dill, Model-checking for real-time systems, In Proceedings of the 5th IEEE Symposium on Logic in Computer Science, p.414–425, June 1990, Philadelphia, PA, USA.
[62] Kenneth L. McMillan, Symbolic model checking, 1993, Kluwer Academic Publishers.
[63] Libor Waszniowski and Z. Hanzálek, Formal verification of multitasking applications based on timed automata model, Real-Time System, v.38 n.1, p.39-65, 2008, Kluwer Academic Publishers Norwell, MA, USA.
[64] Libor Waszniowski and Z. Hanzálek, Over-approximate model of multitasking application based on timed automata using only one clock, In Proceedings of the 19th Int. Parallel and Distributed Processing Symposium, p.128-135, April 2005, Denver, Colorado, USA.
[65] Zonghua Gu, Solving Real-Time Scheduling problems with model-checking, In Proceedings of International Conference on Embedded Software and Systems, p.186-197, Dec. 2005, Xi’an, China.
[66] James C. Corbett, Timing analysis of Ada tasking programs, IEEE Trans. on Software Engineering, v.22 n.7, p.461–483, July 1996, IEEE Press Piscataway, NJ, USA.
[67] Thorsten Gerdsmeier and Cardell-oliver Rachel, Analysis of scheduling behaviour using generic timed automata, Electronic Notes in Theoretical Computer Science, v.42, p.143-157, Jan. 2001.
[68] Kristina Lundqvist and Lars Asplund, A Ravenscar-compliant runtime kernel for safety-critical systems, Real-Time Systems, v.24 n.1, p.29-54, Jan. 2003, Kluwer Academic Publishers Norwell, MA, USA.
[69] Brian Dobbing and George Romanski, The Ravenscar tasking profile-experience reporting, In Proceedings of the 9th International workshop on Real-Time Ada, p.28-32, Mar. 1999, Wakulla Springs Lodge, Florida, USA.
[70] John Penix, Willem Visser, Eric Engstrom, A. Larson amd N. Weininger, Verification of time partitioning in the DEOS scheduler kernel, In Proceedings of the 22nd International Conference on Software Engineering, p.488–497, June 2000, Ireland.
[71] D. Cofer and M. Rangarajan, Formal verification of overhead accounting in an avionics RTOS, In Proceedings of the 23rd IEEE Real Time Systems Symposium, p.181-190, Dec. 2002, Austin, Texas, USA.
[72] C. Norstr?m, A. Wall and Wang Yi, Timed automata as task models for event driven systems. In Proceedings of the 6th International Conference on Real-Time Computing Systems and Applications, p.182-189, Dec. 1999, Hong Kong, China.
[73] E. Fersman, P. Pettersson and Wang Yi, Timed automata with asynchronous processes: schedulability and decidability, In Proceedings of the 8th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, p.67–82, April 2002, Grenoble, France.
[74] E. Fersman, P. Pettersson and Wang Yi, Schedulability analysis using two clocks, In Proceedings of the 9th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, p.224–239, April 2003, Warsaw, Poland.
[75] P. Krcál and Wang Yi, Decidable and undecidable problems in schedulability analysis using timed automata, In Proceedings of the 10th Int. Conference on Tools and Algorithms for the Construction and Analysis of Systems, p.236-250, Mar.-Apr. 2004, Barcelona, Spain.
[76] T. Amnell, E. Fersman, L. Mokrushin, P. Pettersson and W. Yi, Times-A tool for modeling and implementation of embedded systems, In Proceedings of the 8th Int. Conference on Tools and Algorithms for the Construction and Analysis of Systems, p. 460-464, April 2002, Grenoble, France..
[77] J. Krákora and Z. Hanzálek, Timed automata approach to CAN verification, In Proceedings of the 11th IFAC Symposium on Information Control Problems in Manufacturing, p.8-14, April 2004, Brazil.
[78] J. Krákora, L. Waszniowski, P. Pí?a and Z. Hanzálek, Timed automata approach to real time distributed system verification, In Proceedings of the 5th IEEE International workshop on Factory Communication Systems, p. 407–410, Sep. 2004.
[79] Nan Guan, Shuaihong Gao, Qingxu Deng, Ge Yu, Zonghua Gu, Exact schedulability analysis for static-priority global multiprocessor scheduling using model-checking, In Proceedings of the 5th IFIP WG10.2 Int. Conference on Software technologies for embedded and ubiquitous systems, p.263–272, May 2007, Santorini Island, Greece.
[80] Nan Guan, Z. Gu, M. Lv, Q. Deng and G. Yu, Schedulability analysis of global fixed-priority or EDF multiprocessor scheduling, In Proceedings of the 11th IEEE Symposium on Object Oriented Real-Time Distributed Computing, p.556-560, May 2008, Orlando, Florida.
[81] P. Krcal, M. Stigge and Wang Yi, Multi-processor schedulability analysis of preemptive real-time tasks with variable execution times, In Proceedings of the 5th International Conference on Formal Modeling and Analysis of Timed Systems, p.274–289, Oct. 2007, Szlzburg, Austria.
[82] B. Andersson, S. K. Baruah, and J. Jonsson, Static-priority scheduling on multiprocessors, In Proceedings of the 22nd IEEE Real-Time Systems Symposium, p.193–202, Dec. 2001, London, UK.
[83] M. Bertogna, M. Cirinei, and G. Lipari, Schedulability analysis of global scheduling algorithms on multiprocessor platforms, IEEE Trans. on Parallel and Distribute Systems, v.20 n.4, p.553-566, April 2009, IEEE Press Piscataway, NJ, USA.