Two Heap Scheduling Algorithm

• Make two heaps of processes, an active heap and a passive heap.
• The top of the active heap is the process with the greatest excess of quanta (highest ratio of share received to share desired); the top of the passive heap is the process with the greatest deficit of quanta (lowest ratio of share received to share desired).
• Repeat this continuously:
  • Remove the top process of the passive heap. This is the new process.
  • Roll out the top process of the active heap and move it to the passive heap.
  • If there's room, roll in the new process. If not, keep rolling out the top processes of the active heap until there's room; then roll it in.
  • Add the new process to the active heap.
  • If there's room, remove the top process from the passive heap, roll it in, and add it to the active heap. Repeat until there is no longer enough room.
• While all the processes are being rolled in and out, use the time to give each process in the active heap its share of quanta. When each has received its share, loop up to the top of the active heap and begin again.
• To keep track of which process should next receive a quanta, keep an array linking to all active processes. When a process is added or removed from the active heap, add or remove it from the array, but do not alter the array's order.

Back to My Project