Single queue vs. multi-queue multiprocessor scheduling

Operating systems have CPUsCentral Processing Units that allow for tasks to be executed. However, these tasks need to be processed in an order that is not conflicting and based on priorities. Moreover, as computational complexities increase, the CPU has to manage more tasks and allocate them to its single CPU. This is where multiprocessors come in use. Multiprocessors are the use of two or more CPUs in a computer system to allow for parallel processes and better performance.

In this Answer, we will discuss two approaches that use multiprocessors to delegate tasks.

The SQMSSingle Queue Multiprocessor Scheduling policy takes a simplistic approach. It dequeues tasks from the global task queue and enqueues them into the CPU queue. This works by picking the "n" best tasks from the global queue based on priority and other policies and assigning them to each CPU where "n" is the total number of CPUs.

The diagram above shows a single CPU system based on the SQMS.

The example above shows a situation where we have three CPUs available. The policy will pick the top three best tasks and assign each to each CPU.

The MQMSMulti-Queue Multiprocessor Scheduling policy consists of multiple scheduling queues, and each queue can contain different scheduling algorithms. One can use the round-robin scheduler, while the other can use the shortest job first scheduler

This policy works by first placing each task dequeued from the global queue into one CPU queue depending on some heuristic like random allotment or based on the remaining capacity of each queue. Then, it is scheduled independently to prevent problems such as information sharing and synchronization.

The diagram above shows an example of tasks A, B, C, and D dequeued, and two CPUs are available. Each CPU is assigned a task based on the capacity heuristic.

Now that we know what each scheduling policy is, we can discuss the differences and limitations of each.

To conclude, we can summarize that the choice between SQMS and MQMS depends on the requirements, as both policies provide a good solution to their respective issues. However, we can generalize that for systems where all tasks are equally important and require a simple structure, SQMS is the suitable option. In contrast, MQMS is suitable when we require better control and optimization for our system where all tasks are unequal.