1清华云计算课件--分布式计算.ppt

1清华云计算课件--分布式计算
Distributed Problems
Indexing the web (Google)
Simulating an Internet-sized network for networrate tasks?
What is the common theme of all of these problems?
21
Parallelization Pitfalls (2)
Each of these problems represents a point at which multiple threads must communicate with one another, or access a shared resource.
Golden rule: Any memory that can be used by multiple threads must have an associated synchronization system!
22
What’s 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?
23
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:
24
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!
25
Synchronization Primitives
A synchronization primitive is a special shared variable that guarantees that it can only be accessed atomically.
Hardware support guarantees that operations on synchronization primitives only ever take one step
26
Semaphores
A semaphore is a flag that can be raised or lowered in one step
Semaphores were flags that railroad engineers would use when entering a shared track
Only one side of the semaphore can ever be red! (Can both be green?)
27
Semaphores
set() and reset() can be thought of as lock() and unlock()
Calls to lock() when the semaphore is already locked