Multiprocessor Scheduling

Multiprocessor Scheduling

1. Time Sharing

   • Scheduling independent threads
   • We have a set of lists for threads at different priorities. Then we have n CPUs. Once a CPU is ready to pick a thread, it locks the scheduling queues and selects the highest-priority thread. 
   • Disadvantages: 1- The potential contention for the scheduling data structure as the number of CPUs grows. 2- The usual overhead in doing a context switch when a thread blocks for I/O. 

2. Space Sharing

   • When threads are related to one another in some way.
   • Assume an entire group of related threads is created at once. At the time it is created, the scheduler checks to see if there are as many free CPUs as there are threads.  If there are, each thread is given its own dedicated CPU and they all start. If there are not enough CPUs, none of the threads are started until enough CPUs are available. Each thread holds onto its CPU until it terminates, at which time the CPU is put back into the pool of available CPUs. If a thread blocks on I/O, it continues to hold the CPU, which is simply idle until the thread wakes up. 

3. Gang Scheduling

   • 1- Groups of related threads are scheduled as a unit. 2-All  members of a gang run at once on different timeshared CPUs. 3-All gang members start and end their slices together.
   • The trick that makes gang scheduling work is that all CPUs are scheduled synchronously. Doing this means that time is divided into discrete quanta.  At the start of each new quantum, all the CPUs are rescheduled, with a new thread being started on each one. At the start of the next quantum, another scheduling event happens. In between, no scheduling is done. If a thread blocks, its CPU stays idle until the end of the quantum.
   • The idea of gang scheduling is to have all the threads of a process run together, at the same time, on different CPUs, so that if one of them sends a request to another one, it will get the message almost immediately and be able to reply almost immediately.