CPU-Policies 3

Question 1

Multiprocessor scheduling?

Answer 1

how an operating system schedules jobs across multiple CPUs

Question 2

Multicore processor

Answer 2

multiple CPU cores packed onto a single chip. This caused the rise of multiprocessor systems- multiple CPUs on one chip.

Question 3

Background: to understand the new issues that come with multiprocessor scheduling we have to understand the architecture. The difference between single CPU hardware and multi CPU hardware.

Answer 3

The distinction centers around the use of hardware CACHES and how data is shared among multiple processor.

Question 4

hardware caches:

Answer 4

help the processor run programs faster. They are small fast memories that hold copies of popular data that is found in the main memory of the system. CPU -> cache -> memory

Question 5

Main memory:

Answer 5

holds all of the data but access to this larger memory is slower. by keeping frequently accessed data in the cache the system can make the larger slow memory appear to be a fast one. CPU -> cache -> memory

Question 6

Example- how cache and main memory operate with single CPU:

Answer 6

when a program requests data from memory for the first time, it’s slow because the data is in the slow main memory. However, the CPU stores a copy of this data in its fast cache, hoping that the program might need it again. If the program does need the same data later, the CPU checks the cache first. If the data is in the cache, it can be accessed much faster, making the program run faster overall.

Question 7

To work effectively Caches are based on the concept of locality: two kinds:

Answer 7

Temporal locality: repeatedly accessing the same data in a short timeframe.
This means that if you access a piece of data once, you’re likely to access it again in the near future. Caches take advantage of this by storing recently accessed data so that it can be quickly retrieved if needed again soon.

Example:
Editing: editing and re-editing the same document. what was typed or modified can be still accessed they stay in memory for quick retrieval.

Media Streaming: When streaming a video portion of the video ahead of what you’re currently watching is already loaded. you’re likely to continue watching so the data is preloaded to ensure smooth playback.

Spatial Locality: if a program accesses data at a certain memory address, it’s likely to access nearby data as well. Caches benefit from this by storing not only the requested data but also nearby data, anticipating that it might be needed soon.

Example:
editing pics: When applying filters or effects to an image, you often work on neighboring pixels or regions. The software loads and processes nearby pixels together due to their spatial proximity in the image.

Question 8

what happens when you have multiple processors in a single system? cache coherence.

Answer 8

caching becomes more complex leading to cache coherence or data inconsistency.

cache coherence: the challenge of ensuring that all CPUs have a consistent and synchronized view of memory, despite having their own caches.

Imagine two CPUs, A and B, both have a copy of data X in their caches. If CPU A changes X and CPU B still uses the old version, it creates a problem.

Question 9

Solution to cache coherence?

Answer 9

Bus snooping: each CPU’s cache pays attention(snoops) to the memory bus, like listening to a shared communication channel.
When any CPU writes data to memory (let’s say CPU A), all the other caches “snoop” or listen in on the bus to see what’s happening.
If a snooping CPU (like CPU B) hears that CPU A changed some data, it can take appropriate action based on what it hears, such as invalidating its own cache copy or updating it; methods for CPUs to communicate changes in cached data to ensure that all CPUs have a consistent view of memory

invalidating ; when CPU A modifies data in its cache, it sends a message to all the other CPUs (like CPU B) through the shared memory bus.
“I changed this data consider your copies invalid.” CPU B and others then invalidate their cache copies of that data. This ensures that when CPU B needs that data again, it has to fetch the updated version from the main memory because its cache copy is marked as invalid.

Update: when CPU A modifies data in its cache, it shares the new value directly with CPU B and other CPUs, using the memory bus to communicate.
CPU A essentially says, “Hey, I updated this data, and here’s the new value.” CPU B and others then use this new value to update their own cache copies.
This reduces the need to fetch the data again from the main memory because all CPUs are kept up-to-date with the latest value.

Question 10

One Final Issue in building a multiprocessor cache scheduler is: considering Cache Affinity

Answer 10

cache affinity is the idea that a process can benefit from running on the same CPU where it previously executed because of the cached information specific to that CPU. Multiprocessor schedulers can improve performance by considering cache affinity when making scheduling decisions.

Cache affinity is a concept in multiprocessor systems where a process tends to perform better if it runs on the same CPU where it previously executed. This advantage arises because when a process runs on a particular CPU, it builds up a cache of data and translation lookaside buffers (TLBs) specific to that CPU. This cached information can be advantageous for the process’s performance.
In a multiprocessor system, the scheduler should take cache affinity into account when making scheduling decisions. It may be advantageous to schedule a process on the same CPU where it recently executed, as this can lead to better performance due to the presence of cached data and TLBs.

Question 11

Multiprocessor scheduling:
* Single-queue scheduling

Answer 11

Instead of having separate queues for each CPU, SQMS simplifies things by maintaining a single queue for all CPUs to choose tasks from. SQMS tries to achieve fairness and simplicity in multiprocessor scheduling but may not be the most efficient solution for all scenarios due to drawbacks.

Question 12

Multiprocessor scheduling:
* Single-queue scheduling- pros and cons

Answer 12

Pros of SQMS:

Simplicity: it extends a single-processor scheduling policy to handle multiple CPUs with minimal changes. It keeps all tasks in one queue for all CPUs to access.
Example: Imagine you have a scheduling algorithm for a single-CPU system that selects the next task based on priority. In SQMS, you can use the same algorithm for a multiprocessor system, but now you’re picking the top tasks for each CPU from a shared queue.

Cons of SQMS:

Lack of Scalability: SQMS can become less efficient as the number of CPUs in the system increases. This is because synchronization mechanisms like locks are often used to prevent multiple CPUs from accessing the shared queue simultaneously. As more CPUs contend for these locks, performance can degrade. the system spends more time managing locks than performing useful work.
This is a Concurrency issue: multiple CPUs contend for access to a shared queue,

Cache Affinity Issues: involves keeping a process running on the same CPU, so it can take advantage of cached data for better performance. SQMS doesn’t naturally preserve cache affinity because tasks are picked from a shared queue, leading to tasks bouncing between different CPUs.
Example: Consider a scenario where a process frequently accesses data stored in a CPU’s cache. In SQMS, this process may be scheduled on one CPU but then moved to another CPU for its next execution. As a result, it loses the cached data benefits, leading to slower execution times.

“locks” ensure that shared resources are accessed by only one CPU at a time. While they are essential for data consistency, they can introduce performance overhead, especially in systems with many CPUs.

“Overhead” refers to the additional costs or resources consumed by a particular operation or process that are not directly related to its primary function.

Question 13

Multiprocessor scheduling:
* Multi-queue scheduling

Answer 13

(MQMS) is an alternative approach to multiprocessor scheduling that addresses some of the issues found in single-queue schedulers like SQMS.

In MQMS, the scheduling framework consists of multiple scheduling queues, typically one queue per CPU. Each queue follows a specific scheduling discipline, such as round-robin. When a job enters the system, it is placed on one of these scheduling queues, usually based on a heuristic or policy ((e.g., random, or picking one with fewer jobs than others)

Then it is scheduled essentially independently, thus avoiding
the concurrency issue found in the single-queue approach
each CPU or processing core can make its own scheduling decisions based on the tasks available in its respective queue.

Question 14

Multiprocessor scheduling:
* Multi-queue scheduling: pros and cons:

Answer 14

Pros of MQMS:

Scalability: MQMS can be inherently more scalable than single-queue approaches like SQMS. As the number of CPUs increases, so does the number of queues, reducing contention for locks and caches.

Cache Affinity: MQMS naturally provides cache affinity because jobs tend to stay on the same CPU. This means that jobs can take advantage of cached data, improving performance.

Cons of MQMS:

Load Imbalance: Achieving load balance(even work load) in MQMS can be challenging, especially when jobs have varying execution times. Continuous migration may be required to maintain balance.

Migration: To achieve load balance, MQMS employs a technique known as migration, where jobs are moved or “migrated” between CPUs as needed to balance the load.

Complexity: Implementing migration mechanisms and load balancing strategies adds complexity to the scheduler.

Overhead: Techniques like work stealing, used to achieve load balance, can introduce overhead if not implemented carefully, potentially impacting system performance.

Load Balancing: One of the primary objectives of MQMS is load balancing. It aims to distribute the workload evenly across CPUs to maximize resource utilization.

Work stealing: It allows CPUs to share and balance their workloads by periodically stealing tasks from other CPUs with fuller queues, ensuring that all CPUs contribute to the overall system’s efficiency.

Question 15

Which of the following statements are true regarding cache for CPU?
Each cache holds copies of data from the memory that are frequently accessed by its corresponding CPU.

Both single-processor and multi-processor designs suffer from the cache coherence problem.

Spatial locality refers to if a program accesses a data item at address x it is likely to access data items near x as well.

Temporal locality refers to when a piece of data is accessed, it is likely to be accessed again in the near future.

A multiprocessor scheduler should consider cache affinity when making its scheduling decisions, perhaps preferring to keep a process on the same CPU if at all possible.

Answer 15

Each cache holds copies of data from the memory that are frequently accessed by its corresponding CPU.

Spatial locality refers to if a program accesses a data item at address x it is likely to access data items near x as well.

Temporal locality refers to when a piece of data is accessed, it is likely to be accessed again in the near future.

A multiprocessor scheduler should consider cache affinity when making its scheduling decisions, perhaps preferring to keep a process on the same CPU if at all possible.

Both single-processor and multi-processor designs suffer from the cache coherence problem. False: its specific to multi-processor designs where multiple CPUs share access to a common memory system and have their own caches. Single-processor designs do not face these cache coherence challenges because they involve only one CPU and its local memory.

Single-Processor Designs:

In a single-processor system, there is only one CPU (central processing unit) that accesses the system’s memory. In such a setup, there is no need to deal with cache coherence issues because there is no sharing of data or resources among multiple processors. The single CPU operates on its own, and any caching used is typically designed to enhance the performance of that single CPU, without the complexities of cache coherence protocols.

Multi-Processor Designs:

Cache coherence problems become relevant when multiple CPUs or processing cores share access to a common memory system in a multiprocessor or multi-processor design. In these systems, each CPU often has its own cache, and when one CPU modifies a data item in its cache, ensuring that all other CPUs see the correct and up-to-date value becomes a challenge. This is where cache coherence protocols, such as MESI (Modified, Exclusive, Shared, Invalid), MOESI (Modified, Owner, Exclusive, Shared, Invalid), or other variations, are used to maintain data consistency among caches.

Question 16

Which of the following statements are true regarding single-queue scheduling for multiprocessor?

Simple single-queue scheduling design suffers from cache affinity.

Simple single-queue scheduling design suffers from lack of scalability.

Single-queue scheduling does not require much work to take an existing policy and adapt it to work on more than one CPU.

Single-queue allows concurrent access of the single queue without locking.

Answer 16

Which of the following statements are true regarding single-queue scheduling for multiprocessor?
Simple single-queue scheduling design suffers from cache affinity.

Simple single-queue scheduling design suffers from lack of scalability.

Single-queue scheduling does not require much work to take an existing policy and adapt it to work on more than one CPU. ( SQMS takes an existing single-processor scheduling policy and can adapt it to work on multiple CPUs with relatively minimal changes. Since SQMS uses a single scheduling queue shared by all CPUs, it often doesn’t require a complete redesign of the scheduling policy.)

Single-queue allows concurrent access of the single queue without locking. False: This statement is false. Single-queue scheduling typically requires locking mechanisms to ensure that only one CPU accesses the shared queue at a time. Without locking, concurrent access to the single queue can lead to data corruption, scheduling conflicts, and other synchronization problems.

Question 17

Which of the following statements are true regarding multi-queue scheduling for multiprocessor?
Migration of some processes can mitigate load imbalancing for multi-queue scheduling.
Simple multi-queue scheduling suffers from load imbalancing.
Multi-queue design is scalable.
Multi-queue design suffers from cache affinity.
Different queues can use different scheduling policies.

Answer 17

Which of the following statements are true regarding multi-queue scheduling for multiprocessor?
Migration of some processes can mitigate load imbalancing for multi-queue scheduling.
Simple multi-queue scheduling suffers from load imbalancing.
Multi-queue design is scalable.
Different queues can use different scheduling policies.

Multi-queue design suffers from cache affinity. False: Multi-queue scheduling, when properly implemented, does not inherently suffer from cache affinity issues. In fact, multi-queue designs can be designed to preserve cache affinity to some extent. Cache affinity problems are more commonly associated with single-queue scheduling, where jobs may migrate between CPUs and lose access to cached data. Multi-queue designs often keep jobs on the same CPU, preserving cache locality.

Question 18

Which of the following statements are true for the xv6 scheduler?
It is multi-processor scheduler.
It maintains one global queue across all CPUs.
It is multi-queue scheduler.
Each CPU runs a Round-Robin scheduling algorithm.

Answer 18

It is a multi-processor scheduler.

True: xv6 is a multiprocessor operating system, and its scheduler is designed to work on systems with multiple CPUs or processing cores. Therefore, statement 1 is correct.

It maintains one global queue across all CPUs.

True: xv6 follows a simple and efficient scheduling approach where it maintains a single run queue shared among all CPUs in the system. This global run queue holds the runnable processes, and each CPU selects the next process to run from this shared queue. Therefore, statement 2 is correct.

It is a multi-queue scheduler.

False: xv6’s scheduler is not a multi-queue scheduler. Instead, it uses a single global run queue shared among all CPUs. In a multi-queue scheduler, there would be separate scheduling queues or run queues for different categories or priorities of processes, which is not the case in xv6.

Each CPU runs a Round-Robin scheduling algorithm.

True: In xv6, each CPU employs a round-robin scheduling algorithm to select the next process to run from the shared global run queue. This simple round-robin approach helps provide fairness in process execution among the CPUs. Therefore, statement 4 is correct.

Question 19

Which of the following function call causes the processor to directly resume the execution of scheduler()?
swtch(&proc->context, cpu->scheduler)
swtch(&cpu->scheduler, proc->context)
yield()
sched()
trap(struct trapframe *tf)

Answer 19

swtch(&proc->context, cpu->scheduler) is used to switch from a process’s context to the scheduler’s context. This typically occurs when a process is yielding the CPU, and the scheduler needs to select the next process to run.

yield() is a system call or function used by a process to voluntarily yield the CPU, allowing the scheduler to run and select another process to execute. It doesn’t directly resume the execution of scheduler(); rather, it triggers a context switch.

sched() is a function often called within the context of a process to indicate that the process should be put back into the scheduling queue so that the scheduler can decide when to run it. It doesn’t directly resume the execution of scheduler().

trap(struct trapframe *tf) is a function called in response to a trap or exception. It handles various events, including system calls, page faults, and interrupts. It doesn’t directly resume the execution of scheduler().

In contrast, swtch(&cpu->scheduler, proc->context) is typically used when a process has finished its execution time quantum or is waiting for an event (e.g., I/O completion). This call switches from the process’s context to the scheduler’s context, allowing the scheduler to make decisions about which process to run next. In essence, it directly leads to the execution of the scheduler() code, where the scheduler determines the next process to execute on the CPU.