With the emergence of large wired and wireless sensor networks, many real-time applications need to operate on continuous unbounded data streams. At the same time, many of these systems have inherent timing constraints. Providing deadline guarantees for queries over dynamic data streams is a challenging problem due to bursty data stream arrival rates and time-varying stream contents. In this paper, we propose a predictionbased Quality-of-Service (QoS) management scheme for periodic queries over dynamic data streams. Our QoS management scheme features novel query workload estimators, which predict the query workload using execution time profiling and input data sampling, and adjusts the query QoS levels based on online query execution time prediction. We implement our QoS management algorithm on a real-time data stream query system prototype called RTStream. Our experimental evaluation of the scheme shows that our query workload estimator performs very well even with workload fluctuations and our QoS management scheme yields better overall system utility than the existing approaches for QoS management.