Semi-Partitioning Multiprocessor Real-Time Scheduling in Data Stream Management Systems
Subject Areas : electrical and computer engineering
1 -
2 -
Keywords: Workload distribution multiprocessor real-time scheduling partitioning utilization,
Abstract :
In data stream management systems as long as streams of data arrive to the system, stored queries are executed on these data. Regarding high workload, high processing capacity is required, leading to consider multiple processors to cope with it. Partitioning approach, one of the main methods in multiprocessor real-time scheduling, bind each query to one of processors based on its utilization, ratio of estimated execution time to period, and instances of each query which should be completed under defined deadline can only be executed on specified processor. Each query which could not be assigned to any processor can be split based on utilization of processors and spread among them, causing to get closer to optimum result. This system has been examined with real network data, showing lower miss ratio and higher utilization in comparison to simple partitioning approach.
[1] A. Arasu, et al., "STREAM: the stanford stream data manager," in Proc. of ACM SIGMOD Int. Conf. on Management of Data, SIGMOD'03, p. 265, New York, USA, Jun. 2004.
[2] S. Babu and J. Widom, "Continuous queries over data streams," ACM SIGMOD Record, vol. 30, no. 3, pp. 109-120, 2001.
[3] Y. Wei, S. H. Son, and J. A. Stankovic, "RTSTREAM: real-time query processing for data streams," in Proc. 9th IEEE Int. Symp. On Object/Component/Service-Oriented Real-Time Distributed Computing, pp. 141-150, 2006.
[4] S. Sven, L. Thomas, S. Daniel, and L. Wolfgang, "Real-time scheduling for data stream management systems," in Proc. of the 17th Euromicro Conf. on Real-Time Systems, pp. 167-176, 6-8 Jul. 2005.
[5] L. Hennadiy, C. Samarjit, and H. A. James, "Multiprocessor extensions to real-time calculus," in Proc. 30th IEEE Real-Time Systems Symp., RTSS, pp. 410-421, 1-4 Dec. 2009.
[6] P. L. Holman, On the Implementation of Pfair - Scheduled Multiprocessor Systems, Ph. D Thesis, Chapel Hill, 2004.
[7] J. Carpenter, S. Funk, P. Holman, A. Srinivasan, J. Anderson, and S. Baruah, "A categorization of real - time multiprocessor scheduling problems and algorithms," Handbook on Scheduling Algorithms, Methods, and Models, vol. 30, pp. 1-19, 2004.
[8] A. A. Safaei, M. Alemi, M. Haghjoo, and S. Mohammadi, "Hybrid multiprocessor real-time scheduling approach," International Journal of Computer Science Issues, vol. 8, no. 2, pp. 171-178, Mar. 2011.
[9] D. Abadi, et al., "Aurora: a data stream management system," Proc. of ACM SIGMOD Int. Conf. on Management of Data, SIGMOD'03, p. 666, New York, USA, Jun. 2004.
[10] S. Schmidt, H. Berthold, and W. Lehner, "Qstream: deterministic querying of data streams," in Proc. of Int. Conf. on Very Large Data Bases, pp. 1365-1368, 2004.
[11] S. Schmidt, T. Legler, and W. Lehner, "Robust real-time query processing with QStream," in Proc. of the 31st Very Large Data Bases Conf., pp. 1299-1301, Trondheim, Norway, 2005.
[12] X. Li and H. Wang, "Adaptive real-time query scheduling over data streams," in Proc. Int. Conf. on Very Large Databases, PhD Workshop, Sep. 2007.
[13] A. A. Safaei and M. S. Haghjoo, "Parallel processing of continuous queries over data streams," Distributed and Parallel Databases, vol. 28, no. 2-3, pp. 93-118, Dec. 2010.
[14] A. A. Safaei and M. S. Haghjoo, "Dispatching of stream operators in parallel execution of continuous queries," J. of Scheduling, vol. 61, no. 3, pp. 619-641, 2010
[15] م. عالمي، م. حقجو و ع. صفايي، "زمانبندي بيدرنگ چندپردازندهاي در سيستمهاي مديريت جريان داده بيدرنگ،" سومين همايش ملي مهندسي کامپيوتر و فناوري اطلاعات، همدان، 1389.