CS 134

Multicore Scheduling

  • Goat speaking

    Meh. No big deal. We just do everything we did already, except now we have multiple cores accessing our queues. If a core is idle, it just grabs the next job from the highest-priority queue. Done and dusted and we all go home early.

  • Horse speaking

    Hay! We need to be careful. We'll need to make sure that we don't have two cores trying to run the same job at the same time. That would be a disaster. I think we need locks.

Shared-Queue Design

As suggested above, we can adapt a uniprocessor scheduler to a multicore scheduler by having multiple cores access the same queues we used for uniprocessor scheduling.

But we'll have to arbitrate access to the queues.

If we wanted to perform process scheduling on a multicore system, and decided to use a shared-queue design, what kind of locks would we need to use?

Why?

The downside of having shared queues is contention. We'll have to spin while we wait, and even if we don't, sharing memory between cores can be slow as data can usually only be in the cache of one core at a time.

That said, shared queues are a viable option, and are used in some systems, including being an option in the Linux kernel.

  • Duck speaking

    Why not give each core its own set of queues?

  • PinkRobot speaking

    Good idea.

Per-Core Queue Design

Now each core is its own little world with its own scheduler and queues. As such, the most serious issues regarding contention are gone.

  • Dog speaking

    Hurrah! No locks!!

  • PinkRobot speaking

    Hold your horses! It's not quite that simple.

  • Horse speaking

    Hay! I don't need to be held.

  • Hedgehog speaking

    I think I do.   Locks…

Migration

What if one core ends up with all the work and another core is idle? We might want to move a process from one core to another. Thus we need to perform load balancing to ensure that all cores are kept about equally busy.

Load balancing isn't easy though. One issue is that we're back to needing locks again. Because we want to check on how much load other cores have, we want to look at their queues, and we need to lock those queues to do so.

There are two options for moving threads between cores:

  • Pull Migration/Work-Stealing: The idle core asks the busy core for a thread to run.
  • Push Migration/Work-Gifting: The busy core decides to move a thread to the idle core.

Suppose we have three long-running processes and two cores to run them on. Explain why it might be difficult to balance the load.

  • Dog speaking

    Can't we play a game of hot potato, moving the third process back and forth between the two cores?

  • PinkRobot speaking

    Alas, that has some costs.

Cache Affinity

When a process is moved from one core to another, it loses the benefit of the cached data that had been stored on the first core. Losing the cache can cause a significant performance hit.

In fact, losing the cache can be a reason to not migrate a process even when it looks like it would be a good idea. Some schedulers allow a process to specify that it wants to run on a specific core, and the scheduler will try to honor that request.

In OS/161

OS/161 uses a per-core queue design. Each core has its own run queue, and the scheduler runs on each core independently. Periodically, it runs thread_consider_migration to see if a thread should be moved to another core, using a push-migration strategy.

You can find out more by reading about thread.c in the help pages, or by reading thread.c itself.

Can you think of one way in which a push-migration strategy might be better than a pull-migration strategy? (Hint: What does OS/161 do when there are no threads to run on a core?)

(When logged in, completion status appears here.)