CPU paging support
The CPU should store, probably within the page tables, a value indicating the last time any given page of memory was accessed. That way the OS can ask the CPU when a page was last accessed to help it with its swapping algorithm. It seems to me that swapping by time since last accessed would be almost as effective as, and a lot simpler than, using some sort of frequency of use algorithm. Without this feature, the OS has no way of knowing when the last time a page of memory in RAM was accessed was.
I don't know what mechanism the OS uses now for knowing what and when to swap, but I know it must be vastly less efficient than this. I would recommend just swapping out and in at the granularity of memory pages. If I remember correctly, conveniently a page is 4 Kb which is the same minimal amount of storage a harddrive can read or write in one command.