In this thesis probabilistic methods are explored for analysis and scheduling of real-time systems, where computation times vary significantly. The aim is to enable sufficient timing-related performance while allowing for economic resource provisioning or other average-case objectives. In one line of research, Hidden Markov Models (HMMs) with continuous emission distributions are used to model execution times of periodic tasks. A framework for identification and validation of such models is presented. Methods are developed for updating model parameters in systems where the execution time behavior changes, and for bounding the deadline miss probability for such periodic tasks in a reservation based server. For scheduling parallel workload with varying computational demand, a mechanism is proposed for sharing a job queue among several reservation based servers. The mechanism guarantees executing jobs a certain amount of computational resource prior to their deadline, by enabling job dismissal in overload situations. Another contribution regards parallel synchronous tasks, and the problem of assigning a suitable number of cores to the task, so that the deadline is met while optimizing towards a goal such as minimizing energy consumption. A suitable core assignment is found using a Multi-Armed Bandit (MAB) formulation of the problem, requiring only limited knowledge of the worst case properties of the task structure. Using derived response time bounds in the MAB formulation reduces the time to convergence and the energy consumption.