Is Work Stealing always the most appropriate user-level thread scheduling algorithm?

Posted by Il-Bhima on Stack Overflow See other posts from Stack Overflow or by Il-Bhima
Published on 2010-04-05T08:03:03Z Indexed on 2010/04/05 8:13 UTC
Read the original article Hit count: 317

Filed under:

scheduling

|

algorithm

|

load-balancing

|

multithreading

|

work-stealing

I've been investigating different scheduling algorithms for a thread pool I am implementing. Due to the nature of the problem I am solving I can assume that the tasks being run in parallel are independent and do not spawn any new tasks. The tasks can be of varying sizes.

I went immediately for the most popular scheduling algorithm "work stealing" using lock-free deques for the local job queues, and I am relatively happy with this approach. However I'm wondering whether there are any common cases where work-stealing is not the best approach.

For this particular problem I have a good estimate of the size of each individual task. Work-stealing does not make use of this information and I'm wondering if there is any scheduler which will give better load-balancing than work-stealing with this information (obviously with the same efficiency).

NB. This question ties up with a previous question.

© Stack Overflow or respective owner

Related posts about scheduling

Thread scheduling Round Robin / scheduling dispatch

as seen on Stack Overflow - Search for 'Stack Overflow'
#include <pthread.h> #include <stdio.h> #include <stdlib.h> #include <semaphore.h> #define NUM_THREADS 4 #define COUNT_LIMIT 13 int done = 0; int count = 0; int quantum = 2; int thread_ids[4] = {0,1,2,3}; int thread_runtime[4] = {0,5,4,7}; pthread_mutex_t… >>> More
How do tight timelines and scheduling pressure affect TCO and delivery time?

as seen on Programmers - Search for 'Programmers'
A friend's father, who is a software engineering manager, said, emphatically, "The number one cause of scheduling overruns is scheduling pressure." Where does the research stand? Is a moderate amount of scheduling pressure invigorating, or is the manager I mentioned right or wrong, or is it a matter… >>> More
Linux kernel scheduling

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I wish to know how Old Linux scheduling algorithm SJF (shortest job first) calculates the process runtime ? >>> More
Stopping by the Store

as seen on Oracle Blogs - Search for 'Oracle Blogs'
Registrants Get Online Savings on Oracle Products Have you heard about the Oracle Store? It's the one-stop online shop for buying Oracle software and support at significant savings. Better yet, when you register for Oracle OpenWorld 2010 by April 30, you can get an additional 10% off your next purchase… >>> More
SQL University: Parallelism Week - Introduction

as seen on SQL Blog - Search for 'SQL Blog'
Welcome to Parallelism Week at SQL University . My name is Adam Machanic, and I'm your professor. Imagine having 8 brains, or 16, or 32. Imagine being able to break up complex thoughts and distribute them across your many brains, so that you could solve problems faster. Now quit imagining that, because… >>> More

Related posts about algorithm

Jpeg Algorithm vs BMP Algorithm?

as seen on Super User - Search for 'Super User'
I'm just wonder, what the differences are between creating a BMP file algorithm and JPG file algorithm ? If you know the others images' format algorithm, please post them. Thanks. >>> More
word disambiguation algorithm (Lesk algorithm)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hii.. Can anybody help me to find an algorithm in Java code to find synonyms of a search word based on the context and I want to implement the algorithm with WordNet database. For example, "I am running a Java program". From the context, I want to find the synonyms for the word "running", but the… >>> More
Search algorithm (with a sort algorithm already implemented)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, Im doing a Java application and Im facing some doubts in which concerns performance. I have a PriorityQueue which guarantees me the element removed is the one with greater priority. That PriorityQueue has instances of class Event (which implements Comparable interface). Each Event is associated… >>> More
Is there any algorithm for finding LINES by PIXEL COLORS on picture?

as seen on Stack Overflow - Search for 'Stack Overflow'
So I have Image like this I want to get something like this (I hevent drawn all lines I want but I hope you can get my idea) I need algorithm for finding all straight lines on it by just reading colors of pixels. No hard math, no Haar, no Hough. Some algorithm which would be based on points… >>> More
collsion issues with quadtree [on hold]

as seen on Game Development - Search for 'Game Development'
So i implemented a Quad tree in Java for my 2D game and everything works fine except for when i run my collision detection algorithm, which checks if a object has hit another object and which side it hit.My problem is 80% of the time the collision algorithm works but sometimes the objects just go… >>> More