3. Concurrency

Independent and Cooperating Threads

• Independent thread: one that can't affect or be affected by the rest of the universe.
  • Its state isn't shared in any way by any other thread.
  • Deterministic: input state alone determines results.
  • Reproducible.
  • Can stop and continue with no impact on behavior (only time varies).
• For independent threads, the scheduling order doesn't matter
• Cooperating threads: those that share state.
  • Behavior is nondeterministic: depends on relative execution sequence and cannot be predicted in advance.
  • Behavior may be irreproducible.
• Example: one thread writes "ABC" to a console window, another writes "CBA" concurrently.
• Why permit threads to cooperate?
• Basic assumption for cooperating threads is that the order of some operations is irrelevant; certain operations are independent of certain other operations. Examples:
  • Thread 1: A = 1; Thread 2: B = 2;
  • Thread 1: A = B + 1; Thread 2: B = 2 * B;

 

Atomic Operations

• Before we can say ANYTHING about cooperating threads, we must know that some operation is atomic: it either happens in its entirety without interruption, or not at all. Cannot be interrupted in the middle.
  • Single-word references and assignments are atomic in almost all systems. A=B will always read a clean value for B and set a clean value for A (but not necessarily true for arrays or records).
  • If you don't have an atomic operation, you can't make one. Fortunately, hardware designers give us atomic ops.
  • If you have any atomic operation, you can use it to generate higher-level constructs and make parallel programs work correctly. This is the approach we'll take in this class.

 

The "Too Much Milk" Problem

• The basic problem:

	Person A	Person B
3:00	Look in fridge: no milk
3:05	Leave for store
3:10	Arrive at store	Look in fridge: no milk
3:15	Leave store	Leave home
3:20	Arrive home, put milk away	Arrive at store
3:25		Leave store
3:30		Arrive home: too much milk!

• What is the correct behavior?
• More definitions:
  • Synchronization: using atomic operations to ensure correct operation of cooperating threads
  • Critical section: a section of code, or collection of operations, in which only one thread may be executing at a given time. E.g. shopping.
  • Mutual exclusion: mechanisms used to create critical sections.
• Typically, multual exclusion achived with a locking mechanism: prevent others from doing something. For example, before shopping, leave a note on the refrigerator: don't shop, if there is a note.
• First attempt at computerized milk buying (assume atomic reads and writes):

if (milk == 0) {
  if (note == 0) {
    note = 1;
    buy_milk();
    note = 0;
  }
}

• Second attempt: change meaning of note. A buys if no note, B buys if there is a note.

## For thread A
if (note == 0) {
  if (milk == 0) {
    buy_milk();
  }
  note = 1;
}

// For thread B
if (note == 1) {
  if (milk == 0) {
    buy_milk();
  }
  note = 0;
}

• Third attempt: use separate notes for A and B.

// For thread A
noteA = 1;
if (noteB == 0) {
  if (milk == 0) {
    buy_milk();
  }
}
noteA = 0;

// For thread B
noteB = 1;
if (noteA == 0) {
  if (milk == 0) {
    buy_milk();
  }
}
noteB = 0;

• Fourth attempt: just need a way to decide who will buy mmilk when both leave notes (somebody has to hang around to make sure that the job gets done):

// For thread B
noteB = 1;
while (noteA == 1) {
  // do nothing;
}
if (milk == 0) {
  buy_milk();
}
noteB = 0;

 

• This solution works but has two disadvantages:
  • Asymmetric (and complex) code.
  • While B is waiting it is consuming rexources (busy-waiting).
• For a symmetric solution without busy-waiting, see Peterson's Algorithm

 

Summary

 

- Independent thread: 자기를 제외한 나머지로부터 영향받거나 주지 않는 thread, 결과가 정해져있고(deterministic), 복제  가능하며(reproducible), 동작에 영향을 미치지 않고 멈췄다가 다시 시작할 수 있다. 따라서 scheduling order이 그리 중요하지 않다.

- Cooperating thread: state를 공유하는 thread, 결과가 정해져있지 않고(nondeterministic), 복제 불가능하다(irreproducible).

- Cooperating thread를 이야기하기 전 atomic operation(중간에 아무런 방해도 받지 않는 operation을 의미)이 있다는 것을 먼저 알아야 한다. (single-word reference, assignment 같은 것들)

- Synchronization: cooperating thread들의 올바른 작업을 보장하기 위해 atomic operation을 사용하는 것

- Critical section: code의 일부분이나 operation의 모음, 한 thread만 주어진 시간에 실행되어야 한다.

- Mutual exclusion: critical section을 생성하기 위해 사용되는 mechanism (보통 locking mechanism)