Archive for the ‘Multithreading’ Category

Music for Debugging: The Duet of Threads

Tuesday, September 1st, 2009

When listening for the first time to all Bach Cantatas from Complete Works, I found Aria Duetto “Wir danken, wir preisen” (”We thank you, we praise”) from BWV 134 (#4) very stimulating to think about multithreading while debugging or analyzing memory dumps and confirmed my feelings during second listening to all Cantatas.

Bach Edition: Complete Works (155 CD Box Set)

Buy from Amazon

Whom do we thank and praise then? Of course, the creator of the correct and maintainable multithreaded code.

- Dmitry Vostokov @ DumpAnalysis.org -

Practical Foundations Series

Saturday, June 20th, 2009

Following the success of Windows Debugging: Practical Foundations the following title will be published this summer:

Windows Device Drivers: Practical Foundations (ISBN: 978-0955832840)

Table of contents will be posted later.

Other planned titles:

X64 Windows Debugging: Practical Foundations (ISBN: 978-1906717568) 

Windows Multithreading: Practical Foundations (ISBN: 978-1906717742)

 Like Windows Debugging book, these forthcoming titles are based on my seminars. 

- Dmitry Vostokov @ DumpAnalysis.org -

Graphical Notation for Memory Dumps (Part 1)

Saturday, May 23rd, 2009

Inspired by Penrose tensor notation encountered in The Road to Reality book and Feynman diagrams I’d like to introduce Visual Dump Objects (VDO) graphical notation to depict and communicate memory dump analysis patterns, their combinations and analysis results. Let’s look at some basic visual objects (shown in handwriting).

1. A thread:

   or   

2. A function:

3. A module:

4. A thread running through functions, modules or both (stack trace). Optional arrowhead can indicate stack trace direction:

  or    or  

Threads running through modules depict collapsed stack traces.

5. A blocked thread:

An example of 3 threads blocked by another thread (an arrowhead can disambiguate the direction of the waiting chain):

6. A spiking thread (colors are encouraged in VDO notation):

   or   

7. Space boundary between user land and kernel land:

 

Here is an example of the thread spiking in kernel space:

or with modules from stack trace:

More notation to come very soon.

- Dmitry Vostokov @ DumpAnalysis.org -

Programming Language Pragmatics (3rd Edition)

Friday, May 8th, 2009

As soon as I wrote my review of the 2nd edition I found out that the 3rd edition was recently published and immediately bought it. I intend to read it from cover to cover again and publish my notes and comments in my reading notebook on Software Generalist blog. The new edition is also bundled with a companion CD.

Programming Language Pragmatics, Third Edition

Buy from Amazon

Hope in one of subsequent editions the author includes my Riemann Programming Language :-)

- Dmitry Vostokov @ DumpAnalysis.org -

Dining Chicken

Wednesday, April 29th, 2009

To illustrate preemptive multitasking orchestrated by a central processor I use a Russian toy that reminds me of the dining philosophers problem that usually opens any textbook on concurrency:

Here is the video (you need to download and install Xvid MP4 codec if your computer doesn’t play it):

Download DiningChicken.avi (1.2 Mb)

- Dmitry Vostokov @ DumpAnalysis.org -

Race conditions on a uniprocessor machine

Saturday, April 14th, 2007

It is a known fact that hidden race conditions in code are manifested more frequently on a multiprocessor machine than on a uniprocessor machine. I was trying to create an example to illustrate this and wrote the following code which was motivated by the similar kernel level code and the discussion on Russian Software Development Network forum:

volatile bool b;
void thread_true(void *)
{
 while(true)
 {
  b = true;
 }
}
void thread_false(void *)
{
 while(true)
 {
  b = false;
 }
}
int _tmain(int argc, _TCHAR* argv[])
{
 _beginthread(thread_true, 0, NULL);
 _beginthread(thread_false, 0, NULL);
 while(true)
 {
  assert (b == false || b == true);
 }
 return 0;
}

The program has three threads. Two of them are trying to set the same boolean variable b to different values and the main thread checks that its value is either true or false. The assertion should fail in the following scenario: the first thread (thread_true) sets b variable to true value so the first comparison in assertion fails and we expect the second comparison to succeed but the main thread is preempted by the second thread (thread_false) that sets that value to false and therefore the second comparison fails too. We get an assertion dialog in debug build showing that boolean variable b is neither true nor false!

I compiled and ran that program and it wasn’t failing for hours on my uniprocessor laptop. On a multiprocessor machine it was failing in a couple of minutes. If we look at assertion assembly language code we would see that it is very short so statistically speaking the chances that our main thread is preempted in the middle of the assertion are very low. This is because on a uniprocessor machine two threads are running not in parallel but until their quantum is expired. So we should make the assertion code longer to exceed the quantum. To simulate this I added a call to SwitchToThread API. When the assertion code yields execution to another thread then perhaps that thread would be thread_false and as soon as it is preempted by main thread again we get the assertion failure:

volatile bool b;
bool SlowOp()
{
 SwitchToThread();
 return false;
}
void thread_true(void *)
{
 while(true)
 {
  b = true;
 }
}
void thread_false(void *)
{
 while(true)
 {
  b = false;
 }
}
int _tmain(int argc, _TCHAR* argv[])
{
 _beginthread(thread_true, 0, NULL);
 _beginthread(thread_false, 0, NULL);
 while(true)
 {
  assert (b == false || SlowOp() || b == true);
 }
 return 0;
}

I compiled and ran the program again and I couldn’t see any failure for a long time. It looks like thread_false is always running before the main thread and when the main thread is running then due to short-circuit operator || evaluation rule we don’t have a chance to execute SlowOp(). Then I added a fourth thread called thread_true_2 to make the number of threads setting b variable to true value as twice as many as the number of threads setting b variable to false value (2 to 1) so we could have more chances to set b variable to true value before executing the assertion:

volatile bool b;
bool SlowOp()
{
 SwitchToThread();
 return false;
}
void thread_true(void *)
{
 while(true)
 {
  b = true;
 }
}
void thread_true_2(void *)
{
 while(true)
 {
  b = true;
 }
}
void thread_false(void *)
{
 while(true)
 {
  b = false;
 }
}
int _tmain(int argc, _TCHAR* argv[])
{
 _beginthread(thread_true, 0, NULL);
 _beginthread(thread_false, 0, NULL);
 _beginthread(thread_true_2, 0, NULL);
 while(true)
 {
  assert (b == false || SlowOp() || b == true);
 }
 return 0;
}

Now when I ran the new program I got the assertion failure in a couple of minutes! It is hard to make race conditions manifest themselves on a uniprocessor machine.

- Dmitry Vostokov -