北京大学：《大规模数据处理——云计算 Mass Data Processing Cloud Computing》课程教学资源（PPT课件）并行与分布式系统基础 Introduction to Distributed Systems

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(); }