×

On the design and implementation of a shared memory dispatcher for partially clairvoyant schedulers. (English) Zbl 1154.68348

Summary: With the onset of distributed computing in hard real-time applications, the problem of assigning to, scheduling in, and executing jobs on processors, has received a lot of attention. Usually, real-time systems are embedded in closed loop reactive environments with uncertain behaviors and such systems take varying times to respond to such stimuli. One of the fundamental features of such systems is the presence of complex timing constraints between pairs of jobs. A secondary feature is the non-constant nature of the execution times of jobs. Real-time operating systems such as MARUTI can measure the interval within which the execution time varies.
Partially clairvoyant scheduling was introduced in (Saksena, Parametric Scheduling in Hard Real-Time Systems. PhD thesis, University of Maryland, College Park, June 1994) to schedule jobs with varying execution times and non-trivial timing constraints. The schedulability of the job set is determined offline and a set of dispatch functions are produced from the given set of constraints if the job set is schedulable. The dispatch functions bind the start time of a job \(J\) to an interval that depends on the start and execution times of jobs sequenced before \(J\). The online dispatcher of the system reads these dispatch functions and computes the interval within which a job can start without violating the constraints imposed on the system. In certain situations, the dispatcher fails to dispatch a job as the time to compute the dispatch functions associated with a job is greater than the interval within which the job needs to be dispatched.
This phenomenon is called Loss of Dispatchability. In this paper, we propose and implement a partially clairvoyant dispatching algorithm on a shared memory cluster with Concurrent Read Exclusive Write architecture and contrast it with the sequential approach. For a preset number of processors, our approach has \(O(1)\) dispatch complexity while using a total of \(O(n^{2})\) space, while the sequential approach requires \(\Omega(n)\) time. The detailed implementation profile obtained clearly demonstrates the superiority of the multiprocessor approach to dispatching. We also address the issue of scalability of the dispatcher for increasing number of processors and show that job sets of different sizes require different number of processors. Finally, we demonstrate the effect of execution time on the dispatchability of schedules.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aydin, H., Melhem, R., Mossé, D., Mejía-Alvarez, P.: Dynamic and aggressive scheduling techniques for power-aware real-time systems. In: The 22nd IEEE Real-Time Systems Symposium (RTSS ’01), pp 95–105. IEEE, Washington, Brussels, Tokyo (December 2001)
[2] Abdelzaher, T.F., Shin, K.G., Bhatti, N.: Performance guarantees for Web server end-systems: a control-theoretical approach. IEEE Trans. Parallel Distri. Syst. 13(1), 80–96 (2002) · Zbl 05106443 · doi:10.1109/71.980028
[3] Choi, S., Agrawala, A.K.: Dynamic dispatching of cyclic real-time tasks with relative timing constraints. Real-Time Systems 19(1), 5–40 (2000) · doi:10.1023/A:1008133505376
[4] Chodrow, S.E., Jahanian, F., Donner, M.: Run-time monitoring of real-time systems. In: R. Werner (ed.) Proceedings of the Real-Time Systems Symposium–1991, pp. 74–83. IEEE Computer Society Press, San Antonio, Texas, USA (December 1991)
[5] Gerber, R., Pugh, W., Saksena, M.: Parametric dispatching of hard real-time tasks. IEEE Trans. Comput. 44(3), 471–479 (1995) · Zbl 1062.68543 · doi:10.1109/12.372041
[6] Guo, X.: An optimal strategy for sellers in an online auction. ACM Trans. Internet Technol. (TOIT) 2(1), 1–13 (2002) · Zbl 05458142 · doi:10.1145/503334.503335
[7] Hull, D.L., Feng, W., Liu, J.W.-S.: Enhancing the performance and dependability of real-time systems. In: Proceedings of International Computer Performance and Dependability Symposium (IPDS’95), pp. 174–182. IEEE Computer Society (April 1995)
[8] Ja’Ja’, J.: An introduction to parallel algorithms (contents). SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory) 23 (1992)
[9] Konana, P., Mok, A.K., Lee, C.-G., Woo, H., Liu, G.: Implementation and performance evaluation of a real-time E-brokerage system. In: Proceedings of the 21st Symposium on Real-Time Systems (RSS-00), p 13. IEEE Computer Society, Los Alamitos, CA, (November 27–30, 2000)
[10] Kweon, S.-K., Shin, K.G.: Statistical real-time communication over ethernet for manufacturing automation systems. IEEE Trans. Parallel and Distri. Comput. 14(3), 322–335 (2003) · Zbl 05106784 · doi:10.1109/TPDS.2003.1189588
[11] Li, K., Hudak, P.: Memory coherence in shared virtual memory systems. ACM Trans. Comput. Syst. 7(4), 321–359 (1989) · doi:10.1145/75104.75105
[12] Liu, C.L., Layland, J.W.: Scheduling algorithms for multiprogramming in hard real-time environment. J. ACM, 20 (1973) · Zbl 0265.68013
[13] Levi, S.T., Tripathi, S.K., Carson, S.D., Agrawala, A.K.: The \({{\mathtt Maruti}}\) hard real-time operating system. ACM Special Interest Group Operat. Syst. 23(3), 90–106 (1989)
[14] Mosse, D., Agrawala, A.K., Tripathi, S.K.: Maruti a hard real-time operating system. In: Second IEEE Workshop on Experimental Distributed Systems, pp. 29–34. IEEE (1990)
[15] Marti, P., Fuertes, J.M., Fohler, G., Ramamritham, K.: Improving quality-of-control using flexible timing constraints: metric and scheduling issues. In: Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS’02), pp. 91–100. IEEE Computer Society Press (2002)
[16] Mok, A.K., Lee, C.-G., Woo, H., Konana, P.: The monitoring of timing constraints on time intervals. In: Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS’02), pp. 191–200. IEEE Computer Society Press (2002)
[17] Rybski, P.E., Gini, M., Hougen, D.F., Stoeter, S.A., Papanikolopoulos, N.: A distributed surveillance task using miniature robots. In: Gini, M., Ishida, T., Castelfranchi, C., Lewis J.W., (eds.) Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS’02), pp. 1393–1394. ACM Press (July 2002) · Zbl 1017.68865
[18] Saksena, M.: Parametric Scheduling in Hard Real-Time Systems. PhD thesis, University of Maryland, College Park (June 1994)
[19] Schiebe, M., Pferrer, S. (eds.): Real-Time Systems Engineering and Applications, vol. 1. Kluwer Academic Publishers (1992) · Zbl 0781.68020
[20] Sha, L., Rajkumar, R., Lehoczky, J.P.: Priority inheritance protocols: an approach to real-time synchronization. IEEE Trans. Comput. 39(9), 1175–1185 (1990) · doi:10.1109/12.57058
[21] Stankovic, J.A., Spuri, M., Ramamritham, K., Buttazzo G.C. (eds.): Deadline Scheduling for Real-Time Systems. Kluwer Academic Publishers (1998) · Zbl 0931.68136
[22] Subramani, K.: Duality in the Parametric Polytope and its Applications to a Scheduling Problem. PhD thesis, University of Maryland, College Park (August 2000)
[23] Subramani, K.: An analysis of zero-clairvoyant scheduling. In: Katoen, J.-P., Stevens, P. (eds.) Proceedings of the 8th International Conference on Tools and Algorithms for the construction of Systems (TACAS), vol. 2280 of Lecture Notes in Computer Science, pp. 98–112. Springer-Verlag (April 2002) · Zbl 1043.68512
[24] Subramani, K.: A specification framework for real-time scheduling. In: Grosky, W.I., Plasil, F. (eds.) Proceedings of the 29th Annual Conference on Current Trends in Theory and Practice of Informatics (SOFSEM), vol. 2540 of Lecture Notes in Computer Science, pp. 195–207. Springer-Verlag (November 2002)
[25] Subramani, K.: An analysis of partially clairvoyant scheduling. J. Math. Model. Algorithms 2(2), 97–119 (2003) · Zbl 1033.90044 · doi:10.1023/A:1024930227883
[26] Subramani, K.: A comprehensive framework for specifying clairvoyance, constraints and periodicty in real-time scheduling. Comput. J. 48(3), 259–272 (2005) · Zbl 05001533 · doi:10.1093/comjnl/bxh082
[27] Tsigas, P., Zhang, Y.: Non-blocking data sharing in multiprocessor real-time systems. In: Proceedings of the Sixth International Conference on Real-Time Computing Systems and Applications, p. 247. IEEE Computer Society (1999)
[28] Tsigas, P., Zhang, Y.: A simple, fast and scalable non-blocking concurrent FIFO queue for shared memory multiprocessor systems. In: Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 134–143. SIGACT/SIGARCH and EATCS, Crete Island, Greece (July 3–6, 2001)
[29] Tsigas, P., Zhang, Y.: Integrating non-blocking synchronisation in parallel applications: performance advantages and methodologies. In: Proceedings of the 3rd International Workshop on Software and Performance (WOSP-02), pp. 55–67. ACM Press, New York (July 24–26, 2002)
[30] Yang, S.X., Guangfeng, Y., Meng, M.: Real-time collision-free path planning and tracking control of a nonholonomic mobile robot using a biologically inspired approach. In: Proceedings of Computational Intelligence in Robotics and Automation, pp. 113–118. IEEE Computer Society (2001)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.