四川丹甫制压缩机股份有限公司招.90

Bring

forks

today!Outline

for

Today1Objective:To

continue

talking

about

the

critical

section

proband

get

more

practice

thinking

about

possibleinterleavings.Start

talking

about

synchronization

primitives.Introduce

other

“classic”

concurrency

problemsAdministrative

details:Look

on

the

web

for

TAs’

office

hours

or

checknewsgroup

for

UTAs’

office

hours

for

assignment

1.On

collecting

problem

sets…SemaphoresWell-known

synchronization

abstraction

Defined

as

a

non-negative

integer

with

twoatomic

operationsP(s)

-

[wait

until

s

>

0;

s--]

Reminder:

notation

[

]

=

atomicV(s)

-

[s++] The

atomicity

and

the

waiting

can

beimplemented

by

either

busywaiting

orblocking

solutions.11Semaphore

Usage

Binary

semaphores

can

provide

mutualexclusion

(solution

of

critical

section

problem

Counting

semaphores

can

represent

aresource

with

multiple

instances

(e.g.

solvproducer/consumer

problem)Signaling

events(persistent

events

that

stayrelevant

even

if

nobody

listening

right

now)while

(1){

...other

stuff...critical

section}The

Critical

Section

ProblemP(mutex)1V(mutex)Semaphore:mutex

initially

1Fill

in

the

boxesProducer

/

ConsumerProducer:while(whatever){}Consumer:while(whatever)locally

generate

item

{fill

empty

buffer

with

itemget

item

from

full

bufferuse

item}1Producer

/

ConsumerProducer:while(whatever){}Consumer:while(whatever)get

item

from

full

bufferlocally

generate

item

{fill

empty

buffer

with

itemP(emptybuf);V(emptybuf);use

item1V(fullbuf);}Semaphores:

emptybuf

initially

N;

fullbuf

initiP(fullbuf);1Tweedledum

and

Tweedledee

Separate

threads

executing

their

respectiveprocedures.

The

idea

to

cause

them

toforever

take

turns

exchanging

insults

throughthe

shared

variable

X

in

strict

alternation.

The

Sleep()

andWakeup()routines

operateas

follows:Sleep

blocks

the

calling

thread,Wakeup

unblocks

a

specific

thread

if

that

threadis

blocked,

otherwise

its

behavior

is

unpredictable1The

code

shown

above

exhibits

a

well-knownsynchronization

flaw.

Outline

a

scenario

in

which

thiscode

would

fail,

and

the

outcome

of

that

scenariovoid

Tweedledum()void

Tweedledee(){{while(1)

{while(1)

{Sleep();x

=

Quarrel(x);x

=

Quarrel(x);Wakeup(Tweedledum);Wakeup(Tweedledee);Sleep();}}}}If

dee

goes

first

to

sleep,

the

wakeup

is

lost

(since

dumsleeping

yet).

Both

sleep

forever.Show

how

to

fix

the

problem

by

replacing

the

Sleep

andWakeup

calls

with

semaphore

P

(down)

and

V

(up)operations.void

Tweedledum(){while(1)

{Sleep();x

=

Quarrel(x);Wakeup(Tweedledee);}}void

Tweedledee(){while(1)

{x

=

Quarrel(x);Wakeup(Tweedledum);Sleep();}}P(dum);V(dee);semaphore

dee

=

0;semaphore

dum

=

0;V(dum);P(dee):1Monitor

Abstraction

Associated

ConditionVariables

withoperations

of

Wait

andSignal.enQ

deQ

Encapsulates

shareddata

and

operationswith

mutual

exclusiveentry

queuemonitor_lock

notEmptyuse

of

the

object

(anassociated

lock).initshared

dataconditions11Condition

Variables

We

build

the

monitor

abstraction

out

of

a

lock(for

the

mutual

exclusion)

and

a

set

ofassociated

condition

variables.

Wait

on

condition:

releases

lock

held

bycaller,

caller

goes

to

sleep

on

condition’squeue.When

awakened,

it

must

reacquire

lock.

Signal

condition:

wakes

up

one

waitingthread.

Broadcast:

wakes

up

all

threads

waiting

onthis

condition.1Nachos-style

Synchronizationsynch.h,

ccSemaphoresSemaphore::PSemaphore::VLocks

and

condition

variablesLock::AcquireLock::ReleaseCondition::Wait

(conditionLock)Condition::Signal

(conditionLock)Condition::Broadcast

(conditionLock)Monitor

AbstractionenQ

deQinitshared

dataEnQ:{Lock->Acquire

(

);if

(head

==

null){head

=

item;notEmpty->Signal(Lock)e;n}try

queuemonitor_lock

notEmptyelse

tail->next

=

item;tail

=

item;Lock->Release(

);}conditionsdeQ:{Lock->Acquire

(lock);if

(head

==

null)notEmpty->Wait

(lock);item

=

head;if

(tail

==

head)

tail

=

null;head=item->next;Lock->Release(

);}1Monitor

AbstractionenQ

deQinitshared

dataentry

queuemonitor_locknotEmptyconditionsEnQ:{Lock->Acquire

(

);if

(head

==

null){head

=

item;notEmpty->Signal

(Lock);}1else

tail->next

=

item;tail

=

item;Lock->Release(

);}deQ:{Lock->Acquire

(lock);if

(head

==

null)notEmpty->Wait

(lock);item

=

head;if

(tail

==

head)

tail

=

null;head=item->next;Lock->Release(

);}deQ:{Lock->Acquire

(lock);–

if

(head

==

null)notEmpty->Wait

(lock);–

item

=

head;Monitor

AbstractionenQ

deQinitshared

dataEnQ:{Lock->Acquire

(

);–

if

(head

==

null){head

=

item;notEmpty->Signal

(Lock);}else

tail->next

=

item;

entry

queuemonitor_locktail

=

item;Lock->Release(

);}notEmpty––––if

(tail

==

head)

tail

=

null;head=item->next;Lock->Release(

);}conditions1else

tail->next

=

item;tail

=

item;Lock->Release(

);}deQ:{Lock->Acquire

(lock);if

(head

==

null)notEmpty->Wait

(lock);–

item

=

head;EnQ:{Lock->Acquire

(

);–

if

(head

==

null){head

=

item;notEmpty->Signal(Lock)e;n}try

queuemonitor_lock

notEmptyMonitor

AbstractionenQ

deQinitshared

data––––if

(tail

==

head)

tail

=

null;head=item->next;Lock->Release(

);}conditions1else

tail->next

=

item;tail

=

item;Lock->Release(

);}deQ:{Lock->Acquire

(lock);if

(head

==

null)notEmpty->Wait

(lock);–

item

=

head;EnQ:{Lock->Acquire

(

);–

if

(head

==

null){head

=

item;notEmpty->Signal(Lock)e;n}try

queuemonitor_lock

notEmptyMonitor

AbstractionenQ

deQinitshared

data––––if

(tail

==

head)

tail

=

null;head=item->next;Lock->Release(

);}conditions1else

tail->next

=

item;tail

=

item;Lock->Release(

);}deQ:{Lock->Acquire

(lock);if

(head

==

null)notEmpty->Wait

(lock);–

item

=

head;EnQ:{Lock->Acquire

(

);–

if

(head

==

null){head

=

item;notEmpty->Signal(Lock)e;n}try

queuemonitor_lock

notEmptyMonitor

AbstractionenQ

deQinitshared

data––––if

(tail

==

head)

tail

=

null;head=item->next;Lock->Release(

);}conditions11Classic

ProblemsThere

are

a

number

of

“classic”

problemsthat

represent

a

class

of

synchronizationsituations√Critical

Section

problem√Producer/Consumer

problemReader/Writer

problem5

Dining

Philosophers5

Dining

PhilosophersPhilosopher

0Philosopher

1PhilosopherPhilosopher

3Philosopher

4while(food

available){pick

up

2

adj.

forks;eat;put

down

forks;think

awhile;}21Template

for

Philosopherwhile

(food

available){forks*//*pick

upeat;/*put

down

forks*/think

awhile;}1Naive

Solution/*pick

up/*put

down

forks*/}while

(food

available){forPk(sf*o/rk[left(me)]);P(fork[right(me)]);eat;V(fork[left(me)]);V(fork[right(me)]);think

awhile;1Does

this

work?Simplest

Example

of

DeadlockThread

0InterleavingThread

1P(R1)P(R1)P(R2)P(R2)P(R2)P(R1)V(R1)P(R1)

waitsV(R2)V(R2)P(R2)

waitsV(R1)R1

and

R2

initially

1

(binary

semaphore)11Conditions

for

DeadlockMutually

exclusive

use

of

resourcesBinary

semaphores

R1

and

R2Circular

waiting

Thread

0

waits

for

Thread

1

to

V(R2)

andThread

1

waits

for

Thread

0

to

V(R1)Hold

and

waitHolding

either

R1

or

R2

while

waiting

on

otherNo

pre-emption

Neither

R1

nor

R2

are

removed

from

their

respective

holdingThreads.1Philosophy

101(or

why

5DP

is

interesting)

How

to

eat

with

your

Fellows

withoutcausing

Deadlock.Circular

arguments

(the

circular

wait

conditionNot

giving

up

on

firmly

held

things

(nopreemption)Infinite

patience

with

Half-baked

schemes (hold

some

&

wait

for

more)

Why

Starvation

exists

and

what

we

cando

about

it.1Dealing

with

DeadlockIt

can

be

prevented

by

breaking

one

ofthe

prerequisite

conditions:Mutually

exclusive

use

of

resou