Imagine you are working for ABC Computers Pvt. Ltd. as a research associate in the R&D department.
The R&D team is involved in developing new innovative products for the company.
As a part of the research for a new product, you are trying to: Run multiprocessors on the system you are designing
Analyze, in terms of the operating system, how the OS manages multiple processors and multiple caches using a virtualization process of the CPU
Explain these in layman’s terms so that your company’s procuring manager, a person with no technical background, can understand and better help you with your resource requirements.
Note: You must be creative and realistic in assuming the new product’s features. Make sure that you mention your assumptions wherever required.
Processor. A processor is a device that performs arithmetic and logical operations on data, usually referred to as a CPU.
Operating System. An operating system is a software that manages the hardware resources of a computer system; it serves in the middle between the user and the hardware.
Cache. A cache is a small amount of memory used to store data frequently accessed by the processor.
Processor Core. A core is a CPU plus a small cache memory in a single chip; the cache is put near the CPU to reduce the time taken to access data.
Memory. Memory is a device that stores data and instructions for the processor to use. It is usually referred to as RAM and is usually shared by all the processors in a system.
A Single Processor System consists of a single processor, a single cache, and a single memory.
The OS manages the processor, cache, and memory, by allocating them to the necessary processes.
When a new process is queued to run (by the user or another process), The OS examines the process and allocates the process, cache, and memory to the process.
The OS shares resources between processes using virtualization:
Every process has its own share of memory, called address space. This address space is isolated from the address space of other processes.
Every process thinks that it is the only process running on the system.
CPU is virtualized by giving each process a time slice to run on the processor. The OS switches between processes after the time slice is over or if the process voluntarily gives up the CPU.
OS needs to keep track of all running processes; it saves the state of the process when it is switched out and restores the state when it is switched in.
The OS runs a scheduler process that decides which process to run next.
There are many different scheduling algorithms, but they all have the same goal: to maximize CPU utilization, reduce waiting and response time, and maximize throughput (number of processes completed per unit time).
Some scheduling algorithms: First Come, First Serve (FCFS), Shortest Job First (SJF), Round Robin (RR), Priority Scheduling, Multi-Level Queue Scheduling, Multi-Level Feedback Queue Scheduling, etc.
A Multiprocessor System consists of multiple processor cores (each with its own cache); and a single memory.
Increasing the number of cores increases the number of processes that can run simultaneously.
This complicates the OS’s job of managing the resources.
There are two ways to manage the resources in a multiprocessor system:
Symmetric Multiprocessing (SMP): In this method, all the cores are identical.
Asymmetric Multiprocessing (AMP): In this method, One core is the master core, and the rest are slave cores. The master core manages the resources and allocates them to the slave cores.
In terms of scheduling, there are also two ways:
Single-Que MultiProcessor Scheduling (SQMS). OS keeps track of all running processes in one queue and schedules them using a single scheduler.
Multi-Queue MultiProcessor Scheduling (MQMS). Each core has its own queue and scheduler.
SQMS is simpler to implement, but it has a few issues:
Cache incoherence: If a process runs on one core and issues an update so that the cache is updated, but the main memory is not. If this process is rescheduled on a different core, the value in the main memory will be outdated.
Cache affinity: A process scheduled on a core will build up a specific cache. The cache will be useless if the process is rescheduled on a different core.
To solve the issues listed above, SQMS has introduced some techniques:
Bus snooping: When a core updates the cache, it sends a message to all other cores to invalidate their cache.
Mutex Lockers: When a process is scheduled on a core, it will issue a lock on its address space. Other cores will not be able to access the address space until the lock is released.
The locks and bus snooping are expensive and slow, preventing SQMS from scaling. So MQMS is preferred over SQMS.
On MQMS, each core has its own queue and scheduler, and the scheduling happens in the following steps:
When a new process is queued to run, the OS adds it to the global queue.
OS Examines all cores and adds the process to the core’s queue if the core is idle.
The process is scheduled only on this core’s queue until it terminates.
MQMS solves cache incoherence since it ties up the process to a specific core, and it increases cache affinity to the maximum, preventing the need for lockers or cache snooping.
MQMS comes with its own issues as well:
Load imbalance: Jobs are rarely equally distributed among cores or consume time. If a core takes up some short jobs, it will finish early and remains idle. While other cores are still busy.
To solve the load imbalance issues, job-stealing is introduced. When a core becomes idle, it consults other cores and steals some jobs from the busy ones.
We saw that multiprocessor systems have huge advantages over single-processor systems. They maximize the throughput, interactivity, and resource utilization; and minimize waiting time and energy consumption.
Users like the traits listed above as if they bought multiple computers in one device.
The OS managing multiprocessors is more complex and requires careful planning and design.
We also introduced the details of multiprocessor system scheduling; and decided that MQMS is the best way to manage multiprocessors.F
Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. (2018). Operating systems: three easy pieces (1.01 ed.). Arpaci-Dusseau Books. Retrieved June 16, 2022, from https://pages.cs.wisc.edu/~remzi/OSTEP/