Wednesday, November 19, 2014 3:30 pm
-
3:30 pm
EST (GMT -05:00)
David
R.
Cheriton
School
of
Computer
Science
University
of
Waterloo
3:30pm,
Wednesday,
November
19
DC
1302
Abstract:
Software
solutions
for
mutual
exclusion
developed
over
a
30-year
period,
starting
with
complex
ad-hoc
algorithms
and
progressing
to
simpler
formal
ones.
While
it
is
easy
to
dismiss
software
solutions
for
mutual
exclusion,
as
this
family
of
algorithms
is
antiquated
and
most
platforms
support
atomic
hardware
instructions,
there
is
still
a
need
for
these
algorithms
in
threaded,
embedded
systems
running
on
low-cost
processors
lacking
atomic
instructions;
e.g.,
low-cost
devices
like
basic
cell
phones,
cameras,
printers,
music
players,
toys, and
even
singing
greeting
cards.
While
N-thread
solutions
are
usually
short
(10-25
lines
of
code),
each
is
ingenious
with
exceptionally
subtle
aspects,
often
making
it
difficult
to
prove
correctness
or
construct
an
implementation.
The
talk
presents
a
survey
of
existing
algorithms,
with
explanations
of
the
intuition
behind
the
algorithms
and
how
they
work. In
the
existing
algorithms,
several
errors
were
found
and
corrections
made,
as
well
as
a
few
small
improvements;
two
new
high-performance
algorithms
were
developed.
Finally,
high
and
low
contention
experiments
were
performed
to
compare
the
algorithms
and
contrast
them
with
three
common
locks
based
on
hardware
atomic
instructions.
The
results
show
our
two
new
algorithms
are
highly
competitive
with
an equivalent
hardware
lock
(Mellor-Crummey
and
Scott)
over
a
range
of
1--32 processors
on
both
AMD
and
SPARC
processors. Hence,
threading
is
a
viable
alternative
to
event-driven
programming
for
complex
embedded
systems
without
atomic
instructions.