Channels ▼

zz_unused_Marianne Kolbasuk zz_unused_McGee

Dr. Dobb's Bloggers

Don't Worry, When it's Your Turn We'll Let You Know...

January 18, 2011

Everybody's telling us, don't worry about that, just let the tool do its work. So we try not to worry, just turn the code over to the tool, take a deep breath and relax. You'll see, the tool takes care of most of the multithreading troubles for you. Maybe we've just spent too much time dancin' to the nitty gritty. But we always have so many questions that at the last moment, right before we're baptized, we pull the plug on the tool until all questions are answered to our satisfaction.For example, if our application is decomposed into a set of processes or threads that may run in parallel, are all the processes or threads created equal? You know, is there something about Process A that makes it more important than Process B? Is there some reason ThreadA might legitimately deserve more processor time than ThreadB? Or are the processes and threads one big happy homogeneous family?

See, here's the problem we run into. The applications we've been developing these days always decompose into many more processes or threads than the number of CPUs or cores available. For example, our application starts immediately with 80 threads that can execute in parallel. Let's say the hardware only has 8 cores, with maybe 8 hardware threads each (sounds like our T1). That's 64 potential threads in parallel. Even if our application was given all the available hardware threads, we still have 16 threads waiting their turn. Herein lies the rub, what if all of our threads or processes are not created equal? What if some should get more processor time than others? How does the operating system decide which of our 80 threads should get CPUs or cores first?, or how long they should stay on the CPU in a timesharing scenario?

Most Posix compatible operating systems will have process and thread schedulers that support three policies SCHED_RR, SCHED_FIFO, SCHED_OTHER, or round robin, first in first out, and other respectively. So when I have more threads than there are cores, or CPUs, the threads have to wait their turn. The scheduling policy determines who's next in line. Under one policy it's whoever is at the front of the line. Under another policy, it's whichever thread is the most important. Under another policy, the next thread is more or less randomly chosen. Well, if you have a SIMD parallelism scheme in place, maybe a randomly chosen thread works. But what if you have a MIMD where not all processes are created equal, and not all data is created equal. And there are many boss processes and many worker processes, what does the 'one-size-fits-all-tool' do in that situation? What is the default scheduling process for the operating system? How does it know that certain processes or threads requires more CPU time than others? From a programming perspective I can set the scheduling policy in place that I need. I can dynamically set that policy during run time if I need to depending on my application. We have operating system calls like sched_setscheduler, and sched_getscheduler that lets us set the policy that is to be enforced at any given time. What does the 'one-size-fits-all-tool' do with scheduling policies, system wide contention scopes, process contention scopes, default scheduling policies etc. Since there is more than one scheme, the tool has to chose one for you. On the other hand, if the tool leaves the dirty low-level details up to you, then what good is the tool. We have to look at this issue a little deeper. Should we design the concurrency in such a way that it simply doesn't matter who's turn it is to get the processor? Is it possible to design all applications with this kind of 'don't ask, don't tell' policy? Should there be SCHED_RR, and SCHED_FIFO policies? Well, without SCHED_RR, and SCHED_FIFO, many of our AI programs would be DOA. We do need to know when it's our turn ...

Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.