Partea intai arata doar principiile

how to think as a concurrent programmer, developing fundamental skills such as

understanding when operations “happen,” considering all possible interleavings, and
identifying impediments to progress.

===================================================================================
===================================================================================
==============
Chapter 1 - Amhdal Law

This book focuses on how to program multiprocessors that communicate via a shared
memory.
Such systems are often called shared-memory multiprocessors or, more recently,
multicores.
Programming challenges arise at all scales of multiprocessor systems—at a very
small scale, processors within a single chip need to coordinate access to a shared
memory location, and on a large scale, processors in a supercomputer need to
coordinate the routing of data.

Multiprocessor programming is challenging because modern computer systems are

inherently asynchronous: activities can be halted or delayed without warning by
interrupts, preemption, cache
misses, failures, and other events. These delays are inherently unpredictable, and
can vary enormously in scale: a cache miss might delay a processor for fewer than
ten
instructions, a page fault for a few million instructions, and operating system
preemption for hundreds of millions of instructions

We approach multiprocessor programming from two complementary directions:

principles and practice.

In the principles part of this book, we focus on computability: !!!!!

figuring out what can be computed in an asynchronous concurrent environment.
We use an idealized model of computation in which multiple concurrent threads
manipulate a set of shared objects.
The sequence of the thread operations on the objects is called the concurrent
program or concurrent algorithm.

Surprisingly, there are easy-to-specify shared objects that cannot be implemented

by any concurrent algorithm

Many of the issues that will land multiprocessor programmers in trouble are
consequences of fundamental limitations of the computational model, so we view the
acquisition of a basic understanding of concurrent shared-memory computability as a
necessary step

The chapters dealing with principles take the reader through a quick tour of
asynchronous computability, attempting to expose various computability issues, and
how they are addressed
through the use of hardware and software mechanisms.
An important step in the understanding of computability is the specification and
verification of what a given program actually does.
This is perhaps best described as program correctness. !!!!!

!!!!! Sequential correctness is mostly concerned with safety properties.

A safety property states that some “bad thing” never happens. For example, a
traffic light never displays green in all directions, even if the power fails.

Naturally, concurrent correctness is also concerned with safety, but the problem is
much, much harder, because safety must be ensured despite the vast number of ways
that the steps of concurrent threads can be interleaved.
Equally important, concurrent correctness encompasses a variety of liveness
properties that have no counterparts in the sequential world.
A liveness property states that a particular good thing will happen. For example, a
red traffic light will eventually turn green

The second part of the book deals with the practice of multiprocessor programming,
and focuses on performance.
Analyzing the performance of multiprocessor algorithms is also different in flavor
from analyzing the performance of sequential programs.
Sequential programming is based on a collection of well-established and well-
understood abstractions

In the multiprocessor context, this abstraction breaks down, at least from a

performance perspective.
To achieve adequate performance, programmers must sometimes “outwit” the underlying
memory system, writing programs that would seem bizarre to someone unfamiliar with
multiprocessor architectures

The practice part of the book presents a progressive collection of shared objects
and programming tools.
Every object and tool is interesting in its own right, and we use each one to
expose the reader to higher-level issues: spin locks illustrate contention, linked
lists illustrate the role of locking in data structure design, and so on.

transactional memory.?????

memory management is an important aspect of programming, especially concurrent

programming - in Java e facut automat dar e curios de citit despre

------------------------------------------------------------
1.1 Shared objects and synchronization

first scenario ... between 1 and 10 inclusive

using a parallel machine that supports ten concurrent threads.
As a first attempt, you might consider giving each thread an equal share of the
input domain

fails to distribute the work evenly for an elementary but important reason:
Equal ranges of inputs do not produce equal amounts of work.
Primes do not occur uniformly; there are more primes between 1 and 109 than between
9 · 109 and 1010.
To make matters worse, the computation time per prime is not the same in all
ranges:
it usually takes longer to test whether a large number is prime than a small
number.
In short, there is no reason to believe that the work will be divided equally among
the threads, and it is not clear even which threads will have the most work.

second scenario:
Balancing the work load using a shared counter. Each thread is given a dynamically
determined number of numbers to test.

A more promising way to split the work among the threads is to assign each thread
one integer at a time. When a thread is finished testing an integer, it asksfor
another.
To this end, we introduce a shared counter, an object that encapsulates an integer
value, and that provides a getAndIncrement() method, which increments the counter’s
value and returns the counter’s prior value.

The heart of the problem is that incrementing the counter’s value requires two
distinct operations on the shared variable: reading the value field into a
temporary variable and writing it back to the Counter object

On an intuitive level, what is going on is that each of you is performing two

distinct steps: looking at (“reading”) the other’s current position, and moving
(“writing”) to one side or the other
-atomicitatea operatiilor nu exista, de asta faileaza

As we discuss in Chapter 5, modern multiprocessor hardware provides special read–

modify–write instructions that allow threads to read, modify, and write a value to
memory in one atomic (that is, indivisible) hardware step.
For the Counter object, we can use such hardware to increment the counter
atomically = atomic

We can also ensure atomic behavior by guaranteeing in software (using only read and
write instructions) that only one thread executes the read-and-write sequence at a
time.
The problem of ensuring that only one thread can execute a particular block of code
at a time, called the mutual exclusion problem, is one of the classic coordination
problems in multiprocessor programming
=== Synchronizare sau Mutual exclusion problem - one of the classic coordonation
problem

you are unlikely ever to find yourself having to design your own mutual exclusion
algorithm (you would probably call on a library)

ubiquitous issues such as mutual exclusion, deadlock, bounded fairness, and

blocking versus nonblocking synchronization.
------------------------------------------------------------
1.2 A fable

Instead of treating coordination problems (such as mutual exclusion) as programming

exercises, we prefer to frame concurrent coordination problems as interpersonal
problems.
In the next few sections, we present a sequence of fables, illustrating some of the
basic problems

1) impartim toata treaba pe thread-uri

approach fails to distribute the work evenly for an elementary but important
reason:
Equal ranges of inputs do not produce equal amounts of work.
To make matters worse, the computation time per prime is not the same in all
ranges:
it usually takes longer to test whether a large number is prime than a small
number.
In short, there is no reason to believe that the work will be divided equally among
the
threads, and it is not clear even which threads will have the most work.

2) Impartim treaba fiecare thread luand- o separat unul cate unul

When a thread is finished testing an integer, it asks
for another. To this end, we introduce a shared counter, an object that
encapsulates
an integer value, and that provides a getAndIncrement() method, which increments
the counter’s value and returns the counter’s prior value - nu e atomica acel
shared counter

Atomic Behaviour --->

1) As we discuss in Chapter 5, modern multiprocessor hardware provides special
read–modify–write instructions that allow threads to read, modify, and write a
value
to memory in one atomic (that is, indivisible) hardware step. For the Counter
object,
we can use such hardware to increment the counter atomically.
2) We can also ensure atomic behavior by guaranteeing in software (using only read
and write instructions) that only one thread executes the read-and-write sequence
at a
time.
The problem of ensuring that only one thread can execute a particular block of code
at a time,
called the mutual exclusion problem, is one of the classic coordination problems in
multiprocessor programming

Exista mai multe probleme de coordonare la nivel de thread-uri

- mutual exclusion problem
2 thread-uri diferite folosesc aceeasi shared variable - method ca sa faca ceva,
asa ca trebe sa se coordoneze sa nu o foloseasca in acelasi timp
they rule out trivial solutions that do not allow either pet into an empty yard,
or that reserve the yard exclusively to one pet or the other
How should they do it? Alice and Bob need to agree on mutually compatible
procedures for deciding what to do. We call such an agreement a coordination
protocol
(or just a protocol, for short)

Alice has a clever idea. She sets up one or more empty beer cans on Bob’s
windowsill (Fig. 1.4), ties a string around each one, and runs the string back to
her house.
Bob does the same. When she wants to send a signal to Bob, she yanks the string to
knock over one of the cans. When Bob notices a can has been knocked over, he resets
the can.
--->
Coordonation protocol: Flag principle protocol

So Alice and Bob try a different approach. Each one sets up a flagpole, easily
visible to the other. When Alice wants to release her cat, she does the following:
1. She raises her flag.
2. When Bob’s flag is lowered, she releases her cat.
3. When her cat comes back, she lowers her flag.
When Bob wants to release his dog, his behavior is a little more complicated:
1. He raises his flag.
2. While Alice’s flag is raised
a. Bob lowers his flag,
b. Bob waits until Alice’s flag is lowered,
c. Bob raises his flag.
3. As soon as his flag is raised and hers is down, he releases his dog.
4. When his dog comes back, he lowers his flag.
This protocol rewards further study as a solution to Alice and Bob’s problem. On
an intuitive level, it works because of the following flag principle: If Alice and
Bob
each
1. raises his or her own flag, and then
2. looks at the other’s flag,
then at least one will see the other’s flag raised (clearly, the last one to look
will
see the other’s flag raised) and will not let his or her pet enter the yard

However,
this observation does not prove that the pets will never be in the yard together.
What
if, for example, Alice lets her cat in and out of the yard several times while Bob
is
looking?
-dar nu e complet ok, ca threads interleavings, nu se intampla instant operatiile

This kind of argument by contradiction shows up over and over again, and it is
worth spending some time understanding why this claim is true. It is important to
note that we never assumed that “raising my flag” or “looking at your flag” happens
instantaneously, nor did we make any assumptions about how long such activities
take. All we care about is when these activities start or end.

-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
-----------------------------
1.2.1 Properties of a mutual exclusion protocol

To show that the flag protocol is a correct solution to Alice and Bob’s problem, we
must understand what properties a solution requires, and then show that the
protocol meets them

safety property:
We already proved that the pets are excluded from being in the yard at the same
time, a property we call mutual exclusion.

liveness property:
If only one pet wants to enter the yard, then it eventually succeeds. In addition,
if both pets want to enter the yard, then eventually at least one of them succeeds
We consider this deadlock-freedom property to be essentia = deadlock-free

We claim that Alice and Bob’s protocol is deadlock-free.

Suppose both pets want to use the yard. Alice and Bob both raise their flags. Bob
eventually notices that Alice’s flag is raised, and defers to her by lowering his
flag, allowing Alice’s cat into
the yard.

safety property:
starvation-freedom (sometimes called lockoutfreedom): If a pet wants to enter the
yard, will it eventually succeed? Here, Alice and Bob’s protocol performs poorly.
Whenever Alice and Bob are in conflict, Bob defers to Alice

waiting - de ce? pentru ca daca un thread arunca vreo exceptie si se intampla ceva,
nu reuaseste sa seteze flag-ul inapoi, preventing the other thread to function -
thread starvation
The question of waiting is important as an example of fault-tolerance.

The mutual exclusion problem, by its very essence, requires waiting:

No mutual exclusion protocol, no matter how clever, can avoid it.
Nevertheless, we will see that many other coordination problems can be solved
without waiting, sometimes in unexpected ways.

-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
-----------------------------
1.2.2 The moral

Exista 2 tipuri de comunicare ce se intampla in sisteme asincrone

- comunicare transienta - in care ambele parti trebuie sa fie prezente in acelasi
timp
- comunicare persistenta - in care lasam un mesaj undeva iar celalalt il va lua de
acolo intr-un timp diferite

Mutual exclusion requires persistent communication

The can-and-string protocol might seem somewhat contrived, but it corresponds
accurately to a common communication protocol in concurrent systems: interrupts.
In modern operating systems, one common way for one thread to get the attention
of another is to send it an interrupt. More precisely, thread A interrupts thread B
by
setting a bit at a location periodically checked by B. Sooner or later, B notices
the
bit has been set and reacts. After reacting, B typically resets the bit (A cannot
reset
the bit). Even though interrupts cannot solve the mutual exclusion problem, they
can
still be very useful. For example, interrupt communication is the basis of the Java
language’s wait() and notifyAll() calls.

On a more positive note, the fable shows that mutual exclusion between two
threads can be solved (however imperfectly) using only two one-bit variables, each
of which can be written by one thread and read by the other.

-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
-----------------------------
1.3 The producer–consumer problem

Update:
Inca am de rulat teste la USOB, imi va mai lua 3-4 ore dimineata.
CDC-3665 il testez dimineata intre teste

Eu ies in cateva minute, daca vreti ceva sa spuneti, o puteti face

-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
-----------------------------
1.5 The harsh realities of parallelization

The formula
we need is called Amdahl’s law. It captures the notion that the extent to which we
can
speed up any complex job (not just painting) is limited by how much of the job must
be executed sequentially

-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
-----------------------------
1.6 Parallel programming
===================================================================================
===================================================================================
==============
mutual exclusion problem (Chapter 2).
This chapter is essential for understanding why concurrent programming is a
challenge. It covers basic concepts such as fairness and deadlock

We then ask what it means for a concurrent program to be correct (Chapter 3).
We consider several alternative conditions and the circumstances under which one
might want to use each one

We examine the properties of shared memory essential to concurrent computation

(Chapter 4)

kinds of synchronization primitives needed to implement highly concurrent data

structures (Chapters 5 and 6).

!!!
second part of the book describes the practice of concurrent programming

The
chapter also provides an impossibility proof. This proof teaches us the limitations
of solutions to mutual exclusion that work by reading and writing shared memory,
which helps to motivate the real-world mutual exclusion algorithms that appear in
later chapters. This chapter is one of the few that contains proofs of algorithms.

Mutual exclusion is perhaps the most prevalent form of coordination in

multiprocessor programming. This chapter covers classical mutual exclusion
algorithms that
work by reading and writing shared memory

-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
---------------
2.1 Time and events