RU/2: ودزصح. ïآفإخةإ ذدجطعد×ءشإجإت ة زءعزءآدشقةثد× OS/2 (eCS). : Multithreading (X)

From	:	???
To	:	All
Subj	:	Multithreading (X)

Example 3: Race Conditions - When two threads have the access to the same memory space

The first basic problem of multithreading can be illustrated with these fragments of
two simple tasks of the following program. These two tasks where each can increments
the same global location:

long counter;

void thread2(void *x)

{
long i;
long tmp;

for (i= 0; i < 1000000; i++) {

tmp= counter;
tmp++;
counter= tmp;
}
}

void thread3(void *x)

{
long i;
long tmp;

for (i= 0; i < 2000000; i++) {

tmp= counter;
tmp++;
counter= tmp;
}
}

These two tasks work in this example:

/*ررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررر*
*ر Example 3 ر*
*çررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررر÷*
*ر ر*
*ر This program demonstrates the basic problem of concurrency. ر*
*ر Two threads concurrently modify a global location, and a mistake ر*
*ر ensues. ر*
*ر ر*
*ر Each of the two threads increments a global location a ر*
*ر set number of times. If the two threads ran serially, the value ر*
*ر of the counter would be the sum of the two increments at the ر*
*ر end of execution. However, because a thread can be rescheduled ر*
*ر in the midst of updating the counter, some updates get lost. ر*
*ر ر*
*ررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررر*/

#include <stdio.h>
#include <process.h>

#define INCL_DOSPROCESS
#define STACK_SIZE 0x8000
#include <os2.h>

/*
* Function declarations for the threads.
*/
void thread2(void *);
void thread3(void *);

/*
* Declare our global counter variable. This is the location which
* the two threads will be fighting over.
*/
long counter;

/*ررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررر*
*ر Main() ر*
*ررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررر*/
void main()
{
TID thread2Tid;
TID thread3Tid;

counter= 0;
printf("Program starts:\n");
printf(" counter= %d\n", counter);
printf(" [Threads start..."); fflush(stdout);

/*
* Start the threads:
*/
thread2Tid= _beginthread(
thread2, /* Address of function */
NULL, /* Don't really give stack */
STACK_SIZE, /* Size of stack needed */
(PVOID) 0); /* Message to thread */

thread3Tid= _beginthread(
thread3, /* Address of function */
NULL, /* Don't really give stack */
STACK_SIZE, /* Size of stack needed */
(PVOID) 0); /* Message to thread */

/*
* Wait for both threads to complete.
*/
DosWaitThread(&thread2Tid, DCWW_WAIT);
DosWaitThread(&thread3Tid, DCWW_WAIT);

/*
* Now that they're done, let's see what the counter reads.
* If we had called the functions in serial, we would expect the
* result to be 3000000. We will find that it is less, because
* some updates have been lost.
*/
printf("end]\n");
printf(" counter= %d\n", counter);

}

/*ررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررر*
*ر thread2() ر*
*çررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررر÷*
*ر ر*
*ر thread2 increments the global location "counter" 1000000 ر*
*ر times. ر*
*ر ر*
*ررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررر*/

void thread2(void *foo)

{
long i;
long tmp;

for (i= 0; i < 1000000; i++) {
tmp= counter;
tmp++;
counter= tmp;
}
}

/*ررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررر*
*ر thread3() ر*
*çررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررر÷*
*ر ر*
*ر thread3 increments the global location "counter" 2000000 ر*
*ر times. ر*
*ر ر*
*ررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررررر*/

void thread3(void *foo)

{
long i;
long tmp;

for (i= 0; i < 2000000; i++) {
tmp= counter;
tmp++;
counter= tmp;
}
}

If these routines run serially, the counter will be greater than by 3,000,000 after both
routines have run. One might expect the same behavior when they are two different
threads, but we would be surprised.

If one tries to run this program, one will find that the number varies each time that it
runs. What is the reason? Remember that with preemptive multitasking, a process (or
in this case a thread) can be interrupted at any point to run another thread(see and
read again: m019498.html).

Remember: thread #1 within a program is the thread of the main routine

Suppose thread 2 is interrupted after the statement

tmp= counter;

and thread 3 is run for a while, after which thread 2 is resumed. One might have the
following interleaving of instructions:

thread 2 .................................thread 3

tmp= counter;
....................................................tmp= counter;
....................................................tmp++;
....................................................counter= tmp;
..................................................................................
....................................................counter= tmp;
tmp++;
counter= tmp;

Thread 2 gets the value of counter into a local(!) variable, then thread 3 takes over,
incrementing 'counter'. When thread 2 resumes, however, it still has an old value of
'counter' saved in 'tmp', and it is this old value that it increments and stores.

Thus, all of the increments that thread 3 did are lost. This type of 'bug' is called a
'timing bug' or a 'race condition', indicating, that the bug appears only under certain timing
conditions. Such bugs can be extraordinarily difficult to find. Because they often are
intermittent, they are difficult to debug.

Further, even when a timing bug is reproducible, using a debugger might alter the timing
of the program sufficiently that the bug no longer occurs.

What this example has shown is that the sequence:

tmp= counter;
tmp++;
counter= tmp;

is not atomic. An 'atomic operation' is one that runs from start to finish without anything
else happening. Atomicity is relative to how we define "anything else happening". In
absolute terms, the only things that are truly atomic are the quantum state transitions
of fundamental particles; however, this assumes a rather broad definition of "anything
else happening".

It is generally useful to limit the scope to the CPU that we are running on. In this context,
most instructions are atomic. On some hardware, though, there are even some instructions
of sufficient complexity that they can be interuppted in the middle by a hardware
interrupt or a page fault. If we replace our three line sequence by the equivalent:

counter= counter + 1;

the program can be to work as expected. This is because the code is optimized into one
atomic instruction that increments 'counter'. This optimization depends on the compiler,
so it might or might not translate into one instruction. A sufficiently brilliant compiler
might even be able to optimize the three line sequence into one line, recognizing that the
'tmp' local variable is extraneous.

In the next example 4 we will see a solution of this problem with defined 'critical
sections'.

Thu 15 Jan 2004 14:18

Mozilla/4.61 [en] (OS/2; U)

Multithreading (X) (???, 15.01.04 14:18)

َذةسدث سددآفإخةت \| îءذةسءشط خد×دإ \| ïش×إشةشط خء سددآفإخةإ \| ندحدت	ًدةسث:
ًزإؤظؤصفإإ سددآفإخةإ \| َجإؤصہفإإ سددآفإخةإ