Systems and methods are described for managing provisioning of runtimes to execution environments within an on-demand code execution system. Different runtimes can include various software enabling execution of user-submitted code within the on-demand code execution system, potentially written in different programming languages. Each runtime can implement a pull-based request handler, such that when the runtime is provisioned within an execution environment, the runtime requests execution instructions from a management system on the on-demand code execution system. The management system can maintain a queue of execution instructions for each runtime, and can use a depth of each queue to manage the provisioning of environments with runtimes.