Most of the existing real-time processing systems over data streams focus on minimizing average tuple latency while less attention has been paid to deadline of each individual tuple. This paper presents a real-time adaptive batch task scheduling (ATS) mechanism to support the strict deadline requirements of mission-critical applications over time-varying and bursting data streams. The ATS strategy aims at maximizing task throughput and minimizing deadline miss ratio by minimizing both scheduling overheads and deadline miss overheads. The paper proposes a concept of the optimal scheduling unit—batch granularity, and designs a closed-loop feedback control mechanism to adaptively select the dynamic optimal batch size in a non-predictable data stream environment. The theoretical analyses and experimental results show the efficiency and effectiveness of the ATS batching technique.