350 Intermediate C Programming
question, because the execution of this program is unpredictable. When we executed this
program three different times, the program printed three different values:
value is 1
value is -1
value is 0
How can this be possible? If a thread increments and decrements the value before check-
ing, how can it be possible that the value is anything other than zero? It can be even more
surprising when we see the output that includes:
value is 0
This makes no sense because the program should print the message only if the value is
non-zero, based on the condition at line 12.
i f ((* intptr ) != 0)12
The program prints the value only when *intptr is not zero. However, the program
ends up printing zero. What is wrong with this program? To understand what this means,
we must understand this statement: the operating system may change the lengths of the
time intervals. The operating system gives each thread a short time interval to execute
some code. If the program has multiple threads, then each thread gets some time intervals.
Due to many reasons, the operating system may decide to suspend a thread (or a program)
so that another thread (or another program) can run and make progress. There is no
guarantee when a thread is suspended. The operating system needs to manage all programs
and threads so that no single program or thread can occupy the processor for too long. If
a processor has multiple cores, two or more threads may be executing simultaneously. It
is possible that one thread is executing the machine instructions for line 10, while another
thread is executing the machine instructions for line 12. The microsecond differences in
what hundreds of different programs are doing at different times makes it impossible in
general to predict what any given thread is doing at any given time.
Let us look deeper into how this relates to the program. How specifically does this
make the value of * intptr anything other than zero after the increment and decrement
operations? What happens when the program executes this statement?
(* intptr ) ++;10
Because intptr stores arg’s address, this statement increments the value stored in arg. To
execute this statement, the computer must do the following:
1. Read the value of arg.
2. Increment the value.
3. Write the new value to arg.
Please note that arg’s value is changed only at the last step. During the first and the
second steps, the value is stored in a temporary location (called register) inside the processor.
Threads may share memory space but they do not share registers. The operating system may
suspend a thread anywhere in these three steps. The following diagram shows one possible
interleaving of the execution of two threads. In this diagram, time progresses downwards.
We use - to indicate that a thread is currently suspended. If thread 1 is suspended right
after arg increments, then the value is 1 when thread 2 reads it. As a result, when thread
2 checks the value, it is not zero and it prints the message. Table 21.1 explains why the
program may print the value 1.
If we change the ordering, Table 21.2 shows why it is possible to see the value 0 printed.
In this scenario, thread 2 is suspended after it checks arg’s value and it is one. When
Parallel Programming Using Threads 351
thread 1 thread 2 arg’s value
read arg - 0
increment arg - 0
write arg - 1
- read arg 1
- increment arg 1
- write arg 2
- read arg 2
- decrement arg 2
- write arg 1
- check arg’s value 1
- print arg’s value 1
TABLE 21.1: Interleaving scenario 1.
thread 1 thread 2 arg’s value
read arg - 0
increment arg - 0
write arg - 1
- read arg 1
- increment arg 1
- write arg 2
- read arg 2
- decrement arg 2
- write arg 1
- check arg’s value 1
read arg - 1
decrement arg - 1
write arg - 0
- print arg’s value 0
TABLE 21.2: Interleaving scenario 2.
thread 2 prints the value, it has already been changed to 0. Due to the subtle interleaving
of the threads, it is possible that arg’s value is nonzero when the condition is checked and
is 0 when the value is printed.
Is it possible for the program to print 2? Yes. This is one scenario: Thread 1 increments
and decrements arg and arg is 0 when it is suspended just before the if statement. The
thread enters the if statement, but is suspended before it does any printing. Now thread 2
increments arg and is then suspended. The value is now 1. Thread 3 increments arg and the
thread is then suspended. The value is 2 now. Thread 1 gets another turn on the processor,
and prints the value of arg and it is 2. If the threads always increment before decrementing,
how is it possible to print −1? Consider the scenario in Table 21.3.
How contrived is this example? Do scenarios like this happen when solving real world
problems? It happens almost always.
We can find analogous examples in the real world. For example, when several people try
to purchase tickets for the same flight, the shared variable is the total number of tickets
sold for the flight. If only one seat is available and several people buy the ticket at once,
then the flight is oversold (also called overbooked). How can it be possible to oversell one
flight? Suppose two customers check the flight at almost the same time (reading the shared
variable). The flight still has one seat available and both buy the tickets. Now, the flight
352 Intermediate C Programming
thread 1 thread 2 arg’s value
read arg - 0
increment arg - 0
write arg - 1
read arg - 1
decrement arg - 1
- read arg 1
- increment arg 1
- write arg 2
write arg - 0
- read arg 0
- decrement arg 0
- write arg −1
- check arg’s value −1
- print arg’s value −1
TABLE 21.3: Interleaving scenario 3.
is oversold. Airline companies often do this on purpose because some people buy tickets
but never show up for their flight. It can save money, including the customer, if airlines do
this. Airlines can make reasonable accommodations in the unlikely scenario that everyone
actually checks in for the flight. One common solution is to give a voucher to a volunteer
for taking a later flight.
In some other real world cases, we need a solution that strictly prevents this type of
problem occurring altogether. Consider the following scenario: Two people share a bank
account and the current balance is $900. One day, they go to two ATMs (automatic teller
machine) side-by-side. Each withdraws $100 simultaneously. The two people stand next
to each other and attempt to hit the keys on the ATMs at the same time. The correct
remaining balance should be $700. However, subtle interleaving could make the remaining
balance $800 as illustrated below:
Customer 1 Customer 2 Balance
read balance - $900
- read balance $900
subtract $100 - $900
- subtract $100 $900
write balance - $800
- write balance $800
The bank gives each customer $100 and the remaining balance is $800 so the bank loses
$100. No bank would allow this to happen.
How could the designers of threads allow this to happen? First, it is not a flaw in the
specification of threads. The source of the problem is that there is no simple way to predict
the order in which multiple threads execute their instructions. Thus it allows operating
systems to manage the computer resources more efficiently.
The solution to the problem is to prevent any interleaving of the withdrawal operations.
If two requests come in simultaneously, then one must wait until the other request finishes
in its entirety. The entire withdrawal operation is said to be atomic: it cannot be divided
into parts, i.e., it is irreducible. Threads would not be particularly useful if they did not
support atomic operations, and this is the topic of the next section. Atom comes from the
Greek word atomon which means uncuttable. Such irreducible components of matter have
been hypothesized since at least the beginning of recorded history. Now we know that an
Parallel Programming Using Threads 353
atom can be divided to electrons, neutrons, and protons. Nevertheless, we still use “atomic
operation” to describe a computer operation that cannot be divided.
21.6 Thread Synchronization
The previous section described a problem in multi-threaded programs. The problem
occurs because there is no good way to predict the order in which multiple threads may
read and modify the same shared variable. There is no problem when threads do not share
data. There is no problem when they share read-only data. For the subset sum problem,
the threads share the array but it is read-only. No thread modifies the array and there is no
problem. The problem only occurs when threads are writing to, or reading from and writing
to, the same piece of memory, and the operations are interleaved in specific ways. When
we test the program, the problem will occur sometimes, and frustratingly, will not occur at
other times. This adds a significant challenge to testing threaded programs. The only way
to be sure is to use a clear mind to reason logically about how multi-thread programs work.
Threads can specify which operations must be atomic. An atomic operation is called
a critical section. Critical sections cannot interleave. In the previous example, the critical
section should include the code where the variable is read or written. If the threads takes
turns to increment and decrement the variable atomically, then the value will always remain
zero. Thus, the question becomes how to ensure that the threads take turns executing the
critical section of code. Only one thread can start a critical section at a time, and once
it starts, no other thread can enter the critical section until it finishes. The threads must
be synchronized. Synchronization restricts how threads’ operations may interleave. This is
achieved by using a mutually exclusive lock, also called mutex lock or mutex for short.
Consider an analogy of a library study room with the following rules:
• The room has a lock and only one key.
• Before a student enters the room, the student must obtain the key from the library’s
reception desk.
• Only one student can enter the room. The student must keep the key while inside the
room.
• When the student enters the room, the student must immediately lock the door.
• When the student leaves the room, the door is unlocked and the key is returned to
the library’s reception desk.
• If a student wants to use the study room but does not have the key, the student has
to wait.
A mutex comes with a pair of lock and unlock statements. The code between this pair
of statements is the critical section. A mutex lock is very similar to the lock of the library’s
study room.
• Before a thread enters the critical section, the thread must obtain the key from the
operating system.
• Only one thread can enter the critical section. The thread must lock the door and
keep the key while running the code in the critical section.
• When the thread leaves the critical section, the thread unlocks the door and returns
the key to the operating system.
• If a thread wants to enter the critical section but does not have the key, then the
thread has to wait for the key.
354 Intermediate C Programming
The following example shows how to lock and unlock a mutex in order to create a critical
section of code.
// sync . c1
#in clude < pthread .h >2
#in clude < stdio .h >3
#in clude < stdlib .h >4
#d ef in e NUM B ER_THR EAD 165
typedef s t ru ct6
{7
int * intptr ;8
pthr ead_mu tex_t * mlock ;9
} Thr e adData ;10
11
void * t hreadfunc ( void * arg )12
{13
ThreadD a ta * td = ( ThreadD ata *) arg ;14
int * intptr = td -> intptr ;15
pthr ead_mu tex_t * mlock = td -> mlock ;16
while (1)17
{18
int rtv ;19
rtv = pthr ead_m u tex_ l ock ( mlock ); // lock20
// begi n ning cri t ical section21
i f ( rtv != 0)22
{23
printf (" mutex _ lock fail n") ;24
return NULL ;25
}26
(* intptr ) ++;27
(* intptr ) --;28
i f ((* intptr ) != 0)29
{30
printf (" value is % dn ", * intptr );31
return NULL ;32
}33
// end critic a l section34
rtv = pthr ead_m utex _ unlo ck ( mlock ); // unlock35
i f ( rtv != 0)36
{37
printf (" mut e x_unloc k fail n" );38
return NULL ;39
}40
}41
return NULL ;42
}43
44
int main ( i n t argc , char * argv [])45
{46
pthr ead_mu tex_t mlock ;47
pthr ead_m utex_ init (& mlock , NULL ) ;48
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.