Search code examples
operating-systemschedulingpreemption

Lottery Scheduling - preemptive - How to manipulate the tickets after a process is choosen?


Assume there are 2 processes with tickets A:75 and B:25. Now if lottery results in ticket number = 66, that means we run A. This is okay for non-preemptive kernels because A will run until A is complete and then will not participate in the lottery. But if Kernel is preemptive and A is selected,then wouldn't we need to decrease the tickets A has.


Solution

  • I'm not sure that I understand the concern that you're raising in your question, but I'll try to address your points. I assume that the system has 1 core and that each process has 1 thread.

    Non-preemptive: If 66 is chosen, then A will run until it voluntarily yields to the scheduler. Once the scheduler has control, it will randomly choose another ticket and run the associated process. Thus, A could immediately run again or B could run.

    Preemptive: If 66 is chosen, then A will run until it either voluntarily yields to the scheduler or it is preempted (e.g. by a timer interrupt) and the scheduler is given control. Just like in the non-preemptive version, the scheduler will randomly choose another ticket and run the associated process, so in this case A has a 75/100 = 75% chance of running and B has a 25/100 = 25% chance of running.

    I assume that what you're asking is how do you revoke A's tickets while it is running so that it is not chosen by a scheduler on another core to run at the same time (i.e. how does lottery scheduling work on a multicore system?). When the scheduler chooses a ticket, it can simply mark the process's other tickets as invalid or manipulate the ticket data structure in the appropriate way so that the process cannot be chosen by a scheduler. The process's ticket should be chosen and the other tickets should be marked invalid at the same time (i.e. the two operations should look like one operation that is atomic) and before the scheduler performs a context switch to the process. The tickets should be marked valid again immediately after the scheduler regains control from that process.

    The idea remains the same when processes can have more than 1 thread. It just comes down to the scheduler implementation to determine how to distribute the tickets among the process's threads and which ones to take away when one of the threads is chosen.