Operating System

(0) Multiprocessor Scheduling

• Very little has to be done to schedule a multiprocessor system.
• Whenever a CPU needs a process to run, it takes the next task from the ready list.
• The scheduling queue must be accessed in a critical section.
• Busy waiting is usually used.

In computer science, multiprocessor scheduling is an NP-Complete optimization problem. The problem statement is: "Given a set J of jobs where job ji has length li and a number of processors mi, what is the minimum possible time required to schedule all jobs in J on m processors such that none overlap?" The applications of this problem are numerous, but are, as suggested by the name of the problem, most strongly associated with the scheduling of computational tasks in a multiprocessor environment.