4.3 Linearizability

Loading...

En provenance du cours de Rice University

Concurrent Programming in Java

340 notes

Rice University

Concurrent Programming in Java

340 notes

Cours 2 sur 3 dans Specialization Parallel, Concurrent, and Distributed Programming in Java

This course teaches learners (industry professionals and students) the fundamental concepts of concurrent programming in the context of Java 8. Concurrent programming enables developers to efficiently and correctly mediate the use of shared resources in parallel programs. By the end of this course, you will learn how to use basic concurrency constructs in Java such as threads, locks, critical sections, atomic variables, isolation, actors, optimistic concurrency and concurrent collections, as well as their theoretical foundations (e.g., progress guarantees, deadlock, livelock, starvation, linearizability). Why take this course? • It is important for you to be aware of the theoretical foundations of concurrency to avoid common but subtle programming errors. • Java 8 has modernized many of the concurrency constructs since the early days of threads and locks. • During the course, you will have online access to the instructor and mentors to get individualized answers to your questions posted on the forums. • Each of the four modules in the course includes an assigned mini-project that will provide you with the necessary hands-on experience to use the concepts learned in the course on your own, after the course ends. The desired learning outcomes of this course are as follows: • Concurrency theory: progress guarantees, deadlock, livelock, starvation, linearizability • Use of threads and structured/unstructured locks in Java • Atomic variables and isolation • Optimistic concurrency and concurrent collections in Java (e.g., concurrent queues, concurrent hashmaps) • Actor model in Java Mastery of these concepts will enable you to immediately apply them in the context of concurrent Java programs, and will also help you master other concurrent programming system that you may encounter in the future (e.g., POSIX threads, .NET threads).

À partir de la leçon

Concurrent Data Structures

In this module, we will study Concurrent Data Structures, which form an essential software layer in all multithreaded programming systems. First, we will learn about Optimistic Concurrency, an important multithreaded pattern in which two threads can "optimistically" make progress on their assigned work without worrying about mutual conflicts, and only checking for conflicts before "committing" the results of their work. We will then study the widely-used Concurrent Queue data structure. Even though the APIs for using concurrent queues are very simple, their implementations using the Optimistic Concurrency model can be complex and error-prone. To that end, we will also learn the formal notion of Linearizability to better understand correctness requirements for concurrent data structures. We will then study Concurrent Hash Maps, another widely-used concurrent data structure. Finally, we discuss a concurrent algorithm for finding a Minimum Spanning Tree of an undirected graph, an algorithm that relies on the use of Concurrent Data Structures under the covers.

4.1 Optimistic Concurrency6:42

4.2 Concurrent Queue5:11

4.3 Linearizability6:04

4.4 Concurrent Hash Map5:08

4.5 Concurrent Minimum Spanning Tree Algorithm7:29

Rencontrer les enseignants

Vivek Sarkar
Professor
Department of Computer Science

We will now study a very important property of concurrent objects, and

that is called linearizability.

So a concurrent object is really an object that you may have in a sequential program

that has been made what is called "thread safe", where it is safe for

multiple threads to operate on it.

So it could be an atomic integer, a concurrent queue, a concurrent hash map.

It has some set of operations, op1, op2, op3.

And the question is, what return values are permissible

when multiple threads make these calls in parallel?

Given that we know what is correct from a sequential execution.

So to understand this,

let's use an example where time goes in the vertical dimension and

let's say we have two threads, T1, T2, operating on a concurrent queue.

And T1 performs an operation, ENQ(x).

And T2 performs another operation in time,

overlapping in time that's ENQ(y).

And then it performs a DEQ operation.

Now the question is, what value should DEQ return?

Well, you may say it should return x because the ENQ(x) started in parallel.

But it could be, depending on how these operations are implemented,

for example with optimistic concurrency and the retry loop.

It is possible that the ENQ(x) only really took effect over here and

the ENQ(y) took effect earlier.

So it's also permissible for DEQ to return y.

The way we reason about this is that we talk about

a linearization of the operations.

And we consider the time for

each operation in the concurrent object, which is like a method.

The start, when it's invoked, and the return, that time interval.

And we allow ourselves the liberty of picking any point in that time

where the operation could have taken effect.

So in this case, we assume that ENQ(y) took effect at this point in time.

And then ENQ(x) took effect soon after.

And if this was a sequential program, there'd be absolutely no doubt that

DEQ should return Y because Y was enqueued before X.

However, it's possible that another implementation had the opposite order and

in the sense that ENQ(X) took effect earlier and then ENQ(Y).

And in that scenario you would have ENQ(x)

being performed earlier, ENQ(y) being performed later.

And in that case DEQ should return X.

So which is correct?

Well both are correct.

And if you've ever wanted to practice law, here is your chance.

Because the way to look at it is, the concurrent objects are your clients and

you, as trying to evaluate its concurrency, are their lawyer.

And you follow the rule of innocent until proven guilty.

You try to find at least one case that can get your client of the hook.

So if you have one friend who implemented concurrent queues and in this scenario,

the implementation had DEQ returning Y.

You can make the case that yes that could be correct because the ENQ(Y) could

happened before the ENQ(X).

If you had another client that said, well in my implementation, DEQ returns x.

Well you could say that could also be true because we can imagine a scenario,

given the overlapping time intervals, where ENQ(x) took effect before ENQ(y).

However, if you had the third client that said, well in my implementation,

the call to DEQ returned empty to say that the queue is empty.

Now you're going to really have a hard time and in fact you won't be able to

help that client, because given the scenario you know that

at least one element must have been enqueued in the queue before the DEQ occurred.

And that's because the DEQ occurs on thread 2 after at least ENQ of Y

is performed.

So while the DEQ could return x or y,

they would be normal and plausible linearizations.

There is no possible linearization of this execution where DEQ was

empty because that would require the DEQ to take effect before both of the ENQ's.

So now you get the idea that if you have semantics for

the correct sequential execution of an object, you can extend that,

using linearizability to define the semantics of concurrent execution.

And the way you do that, is you say an execution is linearizable, if you can

find some mapping in time for instance where the operations took effect.

And the semantics of that linearization is consistent with sequential execution.

And the goal for everyone who implements concurrent data structures,

is to make sure that all executions of the data structure are linearizable.

And implementers use whatever techniques they can, locks,

isolated, actors, optimistic concurrency,

to ensure correctness while giving the maximum performance.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play