This happens when the system is swapping and most processes are swapped out. Then in theory each context switch would need to swap in some pages first.

Not having given this much thought, I think some solutions could be: (a) Favor processes that are already swapped and keep them swapped in a bit longer before swapping in other processes. I.e. trade fairness for higher throughput. (b) Kill the worst offenders, EarlyOOM, etc, comes to mind. (c) Simply do not swap :)

I realize it's not a solution... But on my systems I simply have swapping disabled.