Explore
For Enterprise
Join for Free
Log In

Parcourir
Rechercher
For Enterprise
Connexion
Inscrivez-vous gratuitement

4.3 Linearizability

Loading...

Concurrent Programming in Java

Université de Rice

4.5 (384 notes) | 10K étudiants inscrits

Cours 2 de 3 dans Parallel, Concurrent, and Distributed Programming in Java Spécialisation

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).

Visualiser le programme de cours

Compétences que vous apprendrez

Concurrency (Computer Science), Actor Model, Optimistic Concurrency Control, Java Concurrency

Avis

4.5 (384 notes)

5 stars
251 ratings
4 stars
101 ratings
3 stars
23 ratings
2 stars
4 ratings
1 star
5 ratings

JB

Sep 03, 2017

Short and easy to understand multi-threading with locks, object-based isolation, Actors, Atomic values and optimistic concurrency.

RR

Jul 22, 2018

Hard course, we need more assignments, small chunks. Making assignments for courses like these is not trivial as well.

À 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

Enseigné par

Vivek Sarkar
Professor

Transcription

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.

Coursera

À propos
Direction
Carrières
Catalogue
Certificats
Certificats MasterTrack™
Diplômes
For Enterprise
For Government

Communauté

Étudiants
Partenaires
Développeurs
Testeurs bêta
Traducteurs
Blog
Blog Tech

Plus

Conditions
Confidentialité
Aide
Accessibilité
Presse
Contact
Répertoire
Filiales

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