Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Push Method Scheduler

IP.com Disclosure Number: IPCOM000012042D
Original Publication Date: 2003-Apr-03
Included in the Prior Art Database: 2003-Apr-03
Document File: 2 page(s) / 42K

Publishing Venue

IBM

Abstract

The purpose of this article is to address the issue of CPU scheduling to increase probability of threads being able to run in shorter amounts of time by using a push method for kernel scheduling rather than a pull method for multiple CPU, multiple run queue thread scheduling. Current schedulers are pull based. Threads are stolen when CPUs go idle, or based on criteria of load on a CPU. Rather than waiting for a CPU to steal some thread from another CPU, if a CPU is ready to give a thread away, then it will push it to another CPU that is less loaded than the current CPU where the thread resides. By pushing threads, better load balancing can be achieved in conjunction to increasing the probability of time to execution.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 73% of the total text.

Page 1 of 2

Push Method Scheduler

Current schedulers are pull based. Threads are stolen when CPUs go idle, or based on criteria of load on a CPU. Rather than waiting for a CPU to steal some thread from another CPU, if a CPU is ready to give a thread away, then it will push it to another CPU that is less loaded than the current CPU where the thread resides. By pushing threads, better load balancing can be achieved in conjunction to increasing the probability of time to execution.

With multiple CPU machines, there are multiple run queues based on priority of threads. Each CPU's priority location queue can have a various number of threads on each.

example: CPU 0 priority 60: thread1 thread2 thread3 thread9 thread10 thread11 priority 61:
...

priority 80: thread4 thread5 thread6 thread12 thread13


...

priority 255:

CPU1 priority 60: thread7 priority 61:
...

priority 80: thread8
...

priority 255:

If CPU1 priority 60 run queue has a small amount of threads, then allowing CPU0 to push some of its threads to CPU1 will increase the probability that those threads will run quicker.

Key advantages:

On multiple CPU machines with a large amount of runnable threads, CPU balancing is achieved With pushing threads, the probability of threads completing quicker increases, thus allowing applications a better probability for response and throughput

Current CPU scheduling methods are pull based when CPUs go idle or are loaded. With busy systems, where the CPUs have large number of threads running, a...