In this paper, we present Pythia, deadline-aware admission control for systems that execute jobs from multiple big data (batch) frameworks using shared resources. Pythia adds support for deadline-driven workloads in resource-constrained cloud settings, for use by resource negotiators such as Apache Mesos or YARN. Pythia uses histories of job statistics to estimate the minimum number of CPUs to allocate to a job in order for it to meet its deadline. Pythia admits jobs when these resources are available. Any job not admitted "fails fast" and wastes no resources. We implement a Pythia prototype and empirically evaluate it using production YARN traces under different resource constraints and deadline assignments. Our results show that Pythia is able to meet significantly more deadlines than fair share approaches and wastes fewer cloud resources in resource-limited scenarios, for the workloads, cluster sizes, and deadline assignments that we consider.