As the respones imply, the question was really "what is a fair priority algo for this?" Which is a more fickle question. Google can give you more answers than you care for.

If the machines can handle all the requests, but you just want to have the paid requests have the quickest turn around times, then almost anything will work. If you don't have enough CPU for everyone, almost nothing will be satisfying.

I'd go with a decorated list of (priority, request) items. Set the priority of paid requests to half of free requests (lower is better). Before you pop the top request subtract one from all the priorities and re-sort the list. Unless you have a billion items this will be so cheap in CPU time that fancier solutions aren't neccessary.

-jack