Technologies are described herein for regulating memory bandwidth usage in virtual machines via CPU scheduling. A virtual machine monitor (“VMM”) executing on a host computer detects excessive memory bandwidth usage by programs executing in a virtual machine on a processor of the host computer. The VMM may detect excessive memory bandwidth usage by monitoring cache-misses occurring in the processor, for example. Upon detecting excessive memory bandwidth usage, the VMM penalizes the virtual machine currently executing on the processor through the CPU-scheduling algorithm utilized to allocate processor time among the virtual machines.