Thread Creation, Manipulation and Synchronization

Operating Systems Lecture Notes

Lecture 3
Thread Creation, Manipulation and
Synchronization
Martin C. Rinard
We first must postulate a thread creation and manipulation interface. Will use the one in
Nachos:
class Thread {
public:
Thread(char* debugName);
~Thread();
void Fork(void (*func)(int) int arg);
void !ield();
void Finish();
"
The Thread constructor creates a new thread. It allocates a data structure with space for
the TCB.
To actually start the thread running, must tell it what function to start running when it
runs. The Fork method gives it the function and a parameter to the function.
What does Fork do? It first allocates a stac for the thread. It then sets up the TCB so that
when the thread starts running, it will invoe the function and pass it the correct
parameter. It then puts the thread on a run !ueue someplace. Fork then returns, and the
thread that called Fork continues.
"ow does #$ set up TCB so that the thread starts running at the function? %irst, it sets
the stac pointer in the TCB to the stac. Then, it sets the &C in the TCB to 'e the first
instruction in the function. Then, it sets the register in the TCB holding the first parameter
to the parameter. When the thread system restores the state from the TCB, the function
will magically start to run.
The system maintains a !ueue of runna'le threads. Whenever a processor 'ecomes idle,
the thread scheduler gra's a thread off of the run !ueue and runs the thread.
Conceptually, threads e(ecute concurrently. This is the 'est way to reason a'out the
'ehavior of threads. But in practice, the #$ only has a finite num'er of processors, and it
can)t run all of the runna'le threads at once. $o, must multiple( the runna'le threads on
the finite num'er of processors.
*et)s do a few thread e(amples. %irst e(ample: two threads that increment a varia'le.
int a # $;
void sum(int p) {
a%%;
printf(&'d : a # 'd(n& p a);
"
void main() {
Thread *t # ne) Thread(&child&);
t*+Fork(sum ,);
sum($);
"
The two calls to sum run concurrently. What are the possi'le results of the program? To
understand this fully, we must 'rea the sum su'routine up into its primitive components.
sum first reads the value of a into a register. It then increments the register, then stores the
contents of the register 'ac into a. It then reads the values of of the control string, p and
a into the registers that it uses to pass arguments to the printf routine. It then calls
printf, which prints out the data.
The 'est way to understand the instruction se!uence is to loo at the generated assem'ly
language +cleaned up ,ust a 'it-. .ou can have the compiler generate assem'ly code
instead of o',ect code 'y giving it the /$ flag. It will put the generated assem'ly in the
same file name as the .c or .cc file, 'ut with a .s suffi(.
la a 'r$
ld -'r$.'r,
add 'r,,'r,
st 'r,-'r$.

ld -'r$. 'o/ 0 parameters are passed starting )ith 'o$

mov 'o$ 'o,
la 12,3 'o$
call printf
$o when e(ecute concurrently, the result depends on how the instructions interleave.
What are possi'le results?
$ : , $ : ,
, : 4 , : ,

, : 4 , : ,
$ : , $ : ,

, : , $ : 4
$ : 4 , : 4

$ : 4 , : 4
, : , $ : 4
$o the results are nondeterministic / you may get different results when you run the
program more than once. $o, it can 'e very difficult to reproduce 'ugs. Nondeterministic
e(ecution is one of the things that maes writing parallel programs much more difficult
than writing serial programs.
Chances are, the programmer is not happy with all of the possi'le results listed a'ove.
&ro'a'ly wanted the value of a to 'e 0 after 'oth threads finish. To achieve this, must
mae the increment operation atomic. That is, must prevent the interleaving of the
instructions in a way that would interfere with the additions.
Concept of atomic operation. 1n atomic operation is one that e(ecutes without any
interference from other operations / in other words, it e(ecutes as one unit. Typically
'uild comple( atomic operations up out of se!uences of primitive operations. In our case
the primitive operations are the individual machine instructions.
2ore formally, if several atomic operations e(ecute, the final result is guaranteed to 'e
the same as if the operations e(ecuted in some serial order.
In our case a'ove, 'uild an increment operation up out of loads, stores and add machine
instructions. Want the increment operation to 'e atomic.
3se synchroni4ation operations to mae code se!uences atomic. %irst synchroni4ation
a'straction: semaphores. 1 semaphore is, conceptually, a counter that supports two
atomic operations, & and 5. "ere is the $emaphore interface from Nachos:
class 5emaphore {
public:
5emaphore(char* debugName int initial6alue);
~5emaphore();
void 7();
void 6();
"
"ere is what the operations do:
o $emphore+name, count- : creates a semaphore and initiali4es the counter to count.
o &+- : 1tomically waits until the counter is greater than 6, then decrements the
counter and returns.
o 5+- : 1tomically increments the counter.
"ere is how we can use the semaphore to mae the sum e(ample wor:
int a # $;
5emaphore *s;
void sum(int p) {
int t;
s*+7();
a%%;
t # a;
s*+6();
printf(&'d : a # 'd(n& p t);
"
void main() {
Thread *t # ne) Thread(&child&);
s # ne) 5emaphore(&s& ,);
t*+Fork(sum ,);
sum($);
"
We are using semaphores here to implement a mutual e(clusion mechanism. The idea
'ehind mutual e(clusion is that only one thread at a time should 'e allowed to do
something. In this case, only one thread should access a. 3se mutual e(clusion to mae
operations atomic. The code that performs the atomic operation is called a critical section.
$emaphores do much more than mutual e(clusion. They can also 'e used to synchroni4e
producer7consumer programs. The idea is that the producer is generating data and the
consumer is consuming data. $o a 3ni( pipe has a producer and a consumer. .ou can also
thin of a person typing at a ey'oard as a producer and the shell program reading the
characters as a consumer.
"ere is the synchroni4ation pro'lem: mae sure that the consumer does not get ahead of
the producer. But, we would lie the producer to 'e a'le to produce without waiting for
the consumer to consume. Can use semaphores to do this. "ere is how it wors:
5emaphore *s;
void consumer(int dumm8) {
)hile (,) {
s*+7();
consume the ne9t unit of data
"
"
void producer(int dumm8) {
)hile (,) {
produce the ne9t unit of data
s*+6();
"
"
void main() {
s # ne) 5emaphore(&s& $);
Thread *t # ne) Thread(&consumer&);
t*+Fork(consumer ,);
t # ne) Thread(&producer&);
t*+Fork(producer ,);
"
In some sense the semaphore is an a'straction of the collection of data.
In the real world, pragmatics intrude. If we let the producer run forever and never run the
consumer, we have to store all of the produced data somewhere. But no machine has an
infinite amount of storage. $o, we want to let the producer to get ahead of the consumer if
it can, 'ut only a given amount ahead. We need to implement a 'ounded 'uffer which can
hold only N items. If the 'ounded 'uffer is full, the producer must wait 'efore it can put
any more data in.
5emaphore *full;
5emaphore *empt8;
void consumer(int dumm8) {
)hile (,) {
full*+7();
consume the ne9t unit of data
empt8*+6();
"
"
void producer(int dumm8) {
)hile (,) {
empt8*+7();
produce the ne9t unit of data
full*+6();
"
"
void main() {
empt8 # ne) 5emaphore(&empt8& N);
full # ne) 5emaphore(&full& $);
Thread *t # ne) Thread(&consumer&);
t*+Fork(consumer ,);
t # ne) Thread(&producer&);
t*+Fork(producer ,);
"
1n e(ample of where you might use a producer and consumer in an operating system is
the console +a device that reads and writes characters from and to the system console-.
.ou would pro'a'ly use semaphores to mae sure you don)t try to read a character 'efore
it is typed.
$emaphores are one synchroni4ation a'straction. There is another called locs and
condition varia'les.
*ocs are an a'straction specifically for mutual e(clusion only. "ere is the Nachos loc
interface:
class 2ock {
public:
2ock(char* debugName); :: initiali;e lock to be F<==
~2ock(); :: deallocate lock
void >c?uire(); :: these are the onl8 operations on a lock
void <elease(); :: the8 are both *atomic*
"
1 loc can 'e in one of two states: loced and unloced. $emantics of loc operations:
o *oc+name- : creates a loc that starts out in the unloced state.
o 1c!uire+- : 1tomically waits until the loc state is unloced, then sets the loc
state to loced.
o 8elease+- : 1tomically changes the loc state to unloced from loced.
In assignment 9 you will implement locs in Nachos on top of semaphores.
What are re!uirements for a locing implementation?
o #nly one thread can ac!uire loc at a time. +safety-
o If multiple threads try to ac!uire an unloced loc, one of the threads will get it.
+liveness-
o 1ll unlocs complete in finite time. +liveness-
What are desira'le properties for a locing implementation?
o :fficiency: tae up as little resources as possi'le.
o %airness: threads ac!uire loc in the order they as for it. 1re also weaer forms
of fairness.
o $imple to use.
When use locs, typically associate a loc with pieces of data that multiple threads
access. When one thread wants to access a piece of data, it first ac!uires the loc. It then
performs the access, then unlocs the loc. $o, the loc allows threads to perform
complicated atomic operations on each piece of data.
Can you implement un'ounded 'uffer only using locs? There is a pro'lem / if the
consumer wants to consume a piece of data 'efore the producer produces the data, it must
wait. But locs do not allow the consumer to wait until the producer produces the data.
$o, consumer must loop until the data is ready. This is 'ad 'ecause it wastes C&3
resources.
There is another synchroni4ation a'straction called condition varia'les ,ust for this ind
of situation. "ere is the Nachos interface:
class @ondition {
public:
@ondition(char* debugName);
~@ondition();
void Aait(2ock *condition2ock);
void 5ignal(2ock *condition2ock);
void Broadcast(2ock *condition2ock);
"
$emantics of condition varia'le operations:
o Condition+name- : creates a condition varia'le.
o Wait+*oc ;l- : 1tomically releases the loc and waits. When Wait returns the
loc will have 'een reac!uired.
o $ignal+*oc ;l- : :na'les one of the waiting threads to run. When $ignal returns
the loc is still ac!uired.
o Broadcast+*oc ;l- : :na'les all of the waiting threads to run. When Broadcast
returns the loc is still ac!uired.
1ll locs must 'e the same. In assignment 9 you will implement condition varia'les in
Nachos on top of semaphores.
Typically, you associate a loc and a condition varia'le with a data structure. Before the
program performs an operation on the data structure, it ac!uires the loc. If it has to wait
'efore it can perform the operation, it uses the condition varia'le to wait for another
operation to 'ring the data structure into a state where it can perform the operation. In
some cases you need more than one condition varia'le.
*et)s say that we want to implement an un'ounded 'uffer using locs and condition
varia'les. In this case we have 0 consumers.
2ock *l;
@ondition *c;
int avail # $;
void consumer(int dumm8) {
)hile (,) {
l*+>c?uire();
if (avail ## $) {
c*+Aait(l);
"
consume the ne9t unit of data
avail**;
l*+<elease();
"
"
void producer(int dumm8) {
)hile (,) {
l*+>c?uire();
produce the ne9t unit of data
avail%%;
c*+5ignal(l);
l*+<elease();
"
"
void main() {
l # ne) 2ock(&l&);
c # ne) @ondition(&c&);
Thread *t # ne) Thread(&consumer&);
t*+Fork(consumer ,);
Thread *t # ne) Thread(&consumer&);
t*+Fork(consumer 4);
t # ne) Thread(&producer&);
t*+Fork(producer ,);
"
There are two variants of condition varia'les: "oare condition varia'les and 2esa
condition varia'les. %or "oare condition varia'les, when one thread performs a 5ignal,
the very ne(t thread to run is the waiting thread. %or 2esa condition varia'les, there are
no guarantees when the signalled thread will run. #ther threads that ac!uire the loc can
e(ecute 'etween the signaller and the waiter. The e(ample a'ove will wor with "oare
condition varia'les 'ut not with 2esa condition varia'les.
What is the pro'lem with 2esa condition varia'les? Consider the following scenario:
Three threads, thread 9 one producing data, threads 0 and < consuming data.
o Thread 0 calls consumer, and suspends.
o Thread 9 calls producer, and signals thread 0.
o Instead of thread 0 running ne(t, thread < runs ne(t, calls consumer, and
consumes the element. +Note: with "oare monitors, thread 0 would always run
ne(t, so this would not happen.-
o Thread 0 runs, and tries to consume an item that is not there. =epending on the
data structure used to store produced items, may get some ind of illegal access
error.
"ow can we fi( this pro'lem? 8eplace the if with a )hile.
void consumer(int dumm8) {
)hile (,) {
l*+>c?uire();
)hile (avail ## $) {
c*+Aait(l);
"
consume the ne9t unit of data
avail**;
l*+<elease();
"
"
In general, this is a crucial point. 1lways put )hile)s around your condition varia'le
code. If you don)t, you can get really o'scure 'ugs that show up very infre!uently.
In this e(ample, what is the data that the loc and condition varia'le are associated with?
The avail varia'le.
&eople have developed a programming a'straction that automatically associates locs and
condition varia'les with data. This a'straction is called a monitor. 1 monitor is a data
structure plus a set of operations +sort of lie an a'stract data type-. The monitor also has
a loc and, optionally, one or more condition varia'les. $ee notes for *ecture 9>.
The compiler for the monitor language automatically inserts a loc operation at the
'eginning of each routine and an unloc operation at the end of the routine. $o,
programmer does not have to put in the loc operations.
2onitor languages were popular in the middle ?6)s / they are in some sense safer 'ecause
they eliminate one possi'le programming error. But more recent languages have tended
not to support monitors e(plicitly, and e(pose the locing operations to the programmer.
$o the programmer has to insert the loc and unloc operations 'y hand. @ava taes a
middle ground / it supports monitors, 'ut also allows programmers to e(ert finer grain
control over the loced sections 'y supporting synchroni4ed 'locs within methods. But
synchroni4ed 'locs still present a structured model of synchroni4ation, so it is not
possi'le to mismatch the loc ac!uire and release.
*aundromat :(ample: 1 local laudromat has switched to a computeri4ed machine
allocation scheme. There are N machines, num'ered 9 to N. By the front door there are &
allocation stations. When you want to wash your clothes, you go to an allocation station
and put in your coins. The allocation station gives you a num'er, and you use that
machine. There are also & deallocation stations. When your clothes finish, you give the
num'er 'ac to one of the deallocation stations, and someone else can use the machine.
"ere is the alpha release of the machine allocation software:
allocate(int dumm8) {
)hile (,) {
)ait for coins from user
n # get();
give number n to user
"
"
deallocate(int dumm8) {
)hile (,) {
)ait for number n from user
put(i);
"
"
main() {
for (i # $; i C 7; i%%) {
t # ne) Thread(&allocate&);
t*+Fork(allocate $);
t # ne) Thread(&deallocate&);
t*+Fork(deallocate $);
"
"
The ey parts of the scheduling are done in the two routines get and put, which use an
array data structure a to eep trac of which machines are in use and which are free.
int a-N.;
int get() {
for (i # $; i C N; i%%) {
if (a-i. ## $) {
a-i. # ,;
return(i%,);
"
"
"
void put(int i) {
a-i*,. # $;
"
It seems that the alpha software isn)t doing all that well. @ust looing at the software, you
can see that there are several synchroni4ation pro'lems.
The first pro'lem is that sometimes two people are assigned to the same machine. Why
does this happen? We can fi( this with a loc:
int a-N.;
2ock *l;
int get() {
l*+>c?uire();
for (i # $; i C N; i%%) {
if (a-i. ## $) {
a-i. # ,;
l*+<elease();
return(i%,);
"
"
l*+<elease();
"
void put(int i) {
l*+>c?uire();
a-i*,. # $;
l*+<elease();
"
$o now, have fi(ed the multiple assignment pro'lem. But what happens if someone
comes in to the laundry when all of the machines are already taen? What does the
machine return? 2ust fi( it so that the system waits until there is a machine free 'efore it
returns a num'er. The situation calls for condition varia'les.
int a-N.;
2ock *l;
@ondition *c;
int get() {
l*+>c?uire();
)hile (,) {
for (i # $; i C N; i%%) {
if (a-i. ## $) {
a-i. # ,;
l*+<elease();
return(i%,);
"
"
c*+Aait(l);
"
"
void put(int i) {
l*+>c?uire();
a-i*,. # $;
c*+5ignal();
l*+<elease();
"
What data is the loc protecting? The a array.
When would you use a 'roadcast operation? Whenever want to wae up all waiting
threads, not ,ust one. %or an event that happens only once. %or e(ample, a 'unch of
threads may wait until a file is deleted. The thread that actually deleted the file could use
a 'roadcast to wae up all of the threads.
1lso use a 'roadcast for allocation7deallocation of varia'le si4ed units. :(ample:
concurrent malloc7free.
2ock *l;
@ondition *c;
char *malloc(int s) {
l*+>c?uire();
)hile (cannot allocate a chunk of si;e s) {
c*+Aait(l);
"
allocate chunk of si;e s;
l*+<elease();
return pointer to allocated chunk
"
void free(char *m) {
l*+>c?uire();
deallocate m1
c*+Broadcast(l);
l*+<elease();
"
:(ample with malloc7free. Initially start out with 96 'ytes free.
Time &rocess 9 &rocess 0 &rocess <
malloc+96- / succeeds malloc+A- / suspends loc malloc+A- suspends loc
9 gets loc / waits
0 gets loc / waits
< free+96- / 'roadcast
> resume malloc+A- /
succeeds
A resume malloc+A- / succeeds
B malloc+C- / waits
C malloc+<- / waits
? free+A- / 'roadcast
D resume malloc+C- / waits
96 resume malloc+<- / succeeds
What would happen if changed c*+Broadcast(l) to c*+5ignal(l)? 1t step 96, process
< would not wae up, and it would not get the chance to allocate availa'le memory. What
would happen if changed )hile loop to an if?
.ou will 'e ased to implement condition varia'les as part of assignment 9. The
following implementation is INC#88:CT. &lease do not turn this implementation in.
class @ondition {
private:
int )aiting;
5emaphore *sema;
"
void @ondition::Aait(2ock* l)
{
)aiting%%;
l*+<elease();
sema*+7();
l*+>c?uire();
"
void @ondition::5ignal(2ock* l)
{
if ()aiting + $) {
sema*+6();
)aiting**;
"
"
Why is this solution incorrect? Because in some cases the signalling thread may wae up
a waiting thread that called Wait after the signalling thread called $ignal.