## 3 Background
### Multiprocessor Scheduling  
While the preceding subsections detailed various scheduling algorithms in single-core systems, the primary emphasis of this paper is a simulation directed toward scheduling in a multiprocessor environment. By utilizing a single CPU, scheduling is employed to create the illusion that each process in the system has its own CPU. In reality, all processes share a single CPU, and the concepts of context switching and sophisticated scheduling algorithms attempt to conceal this fact. In a multi-CPU system, parallelism is achievable, as two processes can run simultaneously on different cores. In theory, it might sound like a system with four CPUs will exhibit throughput that is four times greater than a system with a single CPU. However, in practice, this is not the case. This occurs because each CPU has its own _caches_ and _translation lookside buffer_ (_TLB_), which is only accessible from its associated CPU. CPUs utilize caches and TLB for enhanced performance by leveraging the principle of locality. This principle states that a CPU will frequently access the same set of memory locations for a specific period, focusing on memory addresses close to each other, such as loops in a program. When a process runs on CPU1 and is switched to CPU2, the cache and TLB must be updated. Moving a process from one CPU to another, known as migration, requires updating the cache and TLB. While the simulation will not specifically focus on cache and TLB issues, it will monitor the frequency of process migrations to provide insights into how often such migrations might occur [3]. Figure 1 depicts a typical multiprocessor architecture, where each CPU has its own cache but the memory is shared.  
There are two usual approaches for multiprocessor scheduling, both of which are explained below.  
* **Single-queue:** when transitioning from a single CPU scheduler to a multi-CPU scheduler, the most basic approach involves sharing a single queue that all processes arrive at. All CPUs use the same scheduling algorithm and fetch jobs accordingly from the queue. While this approach is simple to understand and easy to implement, it has significant drawbacks. The main issue is the need for some form of locking to prevent two CPUs from running the same process. Introducing locking can significantly reduce performance, especially with many CPUs, as each CPU must acquire the lock, find the correct process, and release the lock. This additional overhead is an undesirable property. Another issue with the single-queue approach is cache affinity, as processes might run on a different CPU each time they are scheduled. Figure 2 illustrates how the execution might look using a single-queue setup with four CPUs.  
* **Multi-queue:** an approach that minimizes contention for acquiring locks is using a queue for each CPU in the system. If the number of CPUs is \(n\), there will be  
Figure 1: Example of a simplified multiprocessor architecture with four CPUs and their corresponding caches sharing memory.  
Figure 2: Example of a multiprocessor system with five jobs using a single-queue setup. Adapted from [3].  
queues. When a job arrives in the system, it is typically placed in the queue with the least number of jobs. Each CPU can schedule the jobs in its local queue without worrying about sharing and synchronization. This approach also helps with cache affinity, as jobs do not jump between different CPUs but stay consistent on the same one. However, this approach has drawbacks, particularly in terms of load balancing. For example, if two CPUs have three jobs in total, where CPU one has one job in its queue while CPU two has two jobs in its queue, then the job in CPU one will run more than the two jobs in the queue for CPU two. Another drawback of the multi-queue approach is the need for redistribution if one CPU is idle while the others have multiple jobs in their queues. Figure 3 illustrates how the execution might look with a multi-queue setup with two CPUs.