Concurrency : Shared memory

Description

.Concurrency 1Shared MemoryJean-Jacques L´evyjeanjacqueslevy.net/dea1.Why concurrency?1. Programs for multi-processors2. Drivers for slow devices3. Human users are concurrent4. Distributed systems with multiple clients5. Reduce lattency6. Increase efficiency, but Amdahl’s lawNS =b⁄N +(1¡b)(S =speedup, b=sequential part, N processors)2.Implicit CommunicationSuppose x is a global variable. At beginning, x=0ConsiderS =[x:=x+1;x:=x+1jjx:=2⁄x]T =[x:=x+1;x:=x+1jj wait(x=1);x:=2⁄x]After S, then x2f2;3;4gAfter T, then x2f3;4gT may be blockedConclusionIn S and T, interaction via x (shared memory)3.AtomicitySuppose x is a global variable. At beginning, x=0ConsiderS =[x:=x+1jjx:=x+1]After S, then x=2.However if[x:=x+1] compiled into [A:=x+1;x:=A]ThenS =[A:=x+1;x:=A]jj[B :=x+1;x:=B]After S, then x2f1;2g.Conclusion1. [x:=x+1] was firstly considered atomic2. Atomicity is important4.Critical section – Mutual exclusionLet P =[¢¢¢;C ;¢¢¢] and P =[¢¢¢;C ;¢¢¢]0 0 1 1C and C are critical sections (ie should not be executed0 1simultaneously).Solution 1 At beginning, turn=0.P0 : ¢¢¢ P1 : ¢¢¢while turn != 0 do while turn != 1 do; ;C ; C ;0 1turn := 1; turn := 0;¢¢¢ ¢¢¢P privileged, unfair.05.Critical section – Mutual exclusionSolution 2 At beginning, a =a =false.0 1P0 : ¢¢¢ P1 : ¢¢¢while a1 do while a0 do; ;a0 := true; a1 := true;C ; C ;0 1a0 := false; a1 := false;¢¢¢ ¢¢¢False.Solution 3 At beginning, a =a =false.0 1P0 : ¢¢¢ ...

Informations

• Publié par: Eftou
• Nombre de lectures: 22
• Langue: English

Extrait

.

Concurrency

Shared

1

Memory

Jean-JacquesLevy

jeanjacqueslevy.net/dea

1

.

.

.

.

.

.

.

.

.

.