We describe a new operating system scheduling algorithm that improves performance isolation on chip multiprocessors (CMP). Poor performance isolation is the phenomenon where an application’s performance is determined by the behaviour of its co-runners, i.e., other applications simultaneously running with it. This performance dependency is caused by unfair, co-runner-dependent allocation of shared caches on CMPs; co-runner-dependent cache allocation causes co-runner-dependent performance. Poor performance isolation interferes with the operating system’s control over priority enforcement, complicates per-CPU-hour billing and hinders QoS provisioning. Previous solutions required modifications to the hardware, and thus had limited flexibility and long time-to-market. We present a new software solution. Our cache-fair scheduling algorithm reduces the dependency of an application’s performance on its co-runners by ensuring that the application always runs as quickly as it would under fair cache allocation, regardless of how the cache is actually allocated. If the application executes fewer instructions per cycle (IPC) than it would under fair cache allocation, the scheduler increases that thread’s CPU timeslice. This way, even if the thread’s IPC is lower than it would be under fair cache allocation, its overall performance does not suffer because it is allowed to use the CPU longer. We demonstrate, using our implementation of the algorithm in Solaris 10, that this algorithm significantly improves performance isolation for workloads such as SPEC CPU, SPEC JBB and TPC-C.