NC&IS Introduction to Distributed System Parallelization Synchronization
Introduction to Distributed System Parallelization & Synchronization
Parallelization Idea (2) w1 w2 w3 Spawn worker threads: thread thread thread
Parallelization Idea (2) w1 w2 w3 thread thread thread Spawn worker threads:
Parallelization Idea (3) Workers process data: thread thread thread w1 w2 w3
Parallelization Idea (3) thread thread thread Workers process data: w1 w2 w3
Parallelization Idea (4) thread thread thread w1 w2 w3 Report results results
Parallelization Idea (4) results Report results thread thread thread w1 w2 w3
Process synchronization refers to the coordination of simultaneous threads or processes to complete a task in order to get correct runtime order and avoid unexpected race conditions
Process synchronization refers to the coordination of simultaneous threads or processes to complete a task in order to get correct runtime order and avoid unexpected race conditions
M然
And if you thought I was joking…
What is Wrong With This? Thread 1: Thread 2: void foo(){ void bar(){ X++ y++; y=X; X++ } If the initial state is y =0,x=6,what happens after these threads finish running?
What is Wrong With This? Thread 1: void foo() { x++; y = x; } Thread 2: void bar() { y++; x++; } If the initial state is y = 0, x = 6, what happens after these threads finish running?
Multithreaded Unpredictability Many things that look like "one step"operations actually take several steps under the hood: Thread 1: Thread 2: void foo(){ void bar() eax mem[x]; eax mem[y]; inc eax; inc eax; mem[x]eax; mem[y]eax; ebx mem[x]; eax mem[x]; mem[y]ebx; inc eax; mem[x]eax; When we run a multithreaded program,we don't know what order threads run in,nor do we know when they will interrupt one another
Multithreaded = Unpredictability ◼ When we run a multithreaded program, we don’t know what order threads run in, nor do we know when they will interrupt one another. Thread 1: void foo() { eax = mem[x]; inc eax; mem[x] = eax; ebx = mem[x]; mem[y] = ebx; } Thread 2: void bar() { eax = mem[y]; inc eax; mem[y] = eax; eax = mem[x]; inc eax; mem[x] = eax; } ◼ Many things that look like “one step” operations actually take several steps under the hood:
Multithreaded Unpredictability This applies to more than just integers: Pulling work units from a queue Reporting work back to master unit Telling another thread that it can begin the "next phase”of processing ..All require synchronization!
Multithreaded = Unpredictability This applies to more than just integers: ◼ Pulling work units from a queue ◼ Reporting work back to master unit ◼ Telling another thread that it can begin the “next phase” of processing … All require synchronization!
Synchronization Primitives Lock Semaphore Barriers Thread 1: Thread 2: void foo(){ void bar( sem.lock(); sem.lock(; X++; y++; y=X X++ sem.unlockO; sem.unlockO;
Synchronization Primitives Semaphore Barriers Lock Thread 1: void foo() { sem.lock(); x++; y = x; sem.unlock(); } Thread 2: void bar() { sem.lock(); y++; x++; sem.unlock(); }