The processor-process marriage
Ola amigos! I’m back with an interesting anecdote from the operating systems world — about our dear old processors, processes and their fragile courtship.
We know that meet-cute between processors and processes is triggered by the scheduler, but just like any romantic relationship, there are several factors that determine the success of this alliance. If everything goes well, there are some reasons why a process might prefer to be scheduled on the same processor, repetitively. For instance, in choosing their significant other, a process might consider
- A processor that is faster than the rest — Time is money, and processes are smart enough to realize this.
- A processor has certain resources that other processors don’t — custom specs are chick magnets and we know it.
- A processor has certain valuable information that other processors don’t — cache affinity is simply marriage material.
Wow, this is beginning to sound more like many real relationships than I initially envisioned it to be!
Given these considerations, scheduling of processes in multiprocessor architecture becomes challenging indeed. This paper explores the importance of using cache affinity in matching processes to processors; a.k.a the courtship.
A note on cache affinity
When a process runs on a processor, it caches a lot of the data that it operates on, onto the processor’s cache. This ensures fast execution by avoiding those pesky memory stalls. Studies in the paper show that running a process on a processor with a “warm” cache (data preloaded) provides almost a 69% increase in performance, compared to that of a “cold” cache.
However, as the processor runs different processes, it populates the caches with data from those processes. Hence, rescheduling the process on the same processor may not be that effective, if there have been many intervening processes in between.
All in all, the matchmaking is a lot more knotty than what it appears to be.
Algorithms for matchmaking
Here are some common algorithms used for the matchmaking.
First come first serve — the good old arranged marriage
This algorithm completely ignores cache affinity and simply schedules processes onto processors that become available in every time slice. The scheduler decides the match depending on the order in which the processes arrive; thus making matchmaking short and sweet, but not always the most performant.
Fixed Processor — the rebel love marriage
This algorithm relies on cache affinity so much, that a process is always scheduled on the same processor, to benefit from the cached data from the previous runs. Each processor maintains a local queue of processes which are served in the first come, first serve manner. Adamant processes execute only on their cache-affined processors, making scheduler’s lives’ difficult.
Last Processor — the casual dating
In this algorithm, the processor is matched with a process in the ready queue, that last ran on the same processor. If no such process is found, then any process from the ready queue is picked up for execution. Thus, processes and processors engage in a casual relationship, for as long as it is meant to be.
Minimum Intervening — the algorithmic matchmaking
This algorithm goes a step forward in taking process’ needs into consideration by not only scheduling them on processors where they last ran, but also taking into account the number of stranger processes that ran in the interval . Of course, this requires maintaining information on each process’ affinity, but you have to agree that is indeed the tinder of process scheduling!
Hope you enjoyed this story about how processes and processors find their matches! I will be back soon, with another interesting story from the operating systems world; till then, happy coding in a parallel world! 😀
