CSCE 313 Lecture 9

« previous | Tuesday, February 14, 2012 | next »

Happy Feast of St. Valentine's Day!

Synchronization

The most difficult part of this class!

Critical Section Problem: Example 1

// shared variables
char in;
char out;

void echo() {
    input(in, keyboard);
    out = in;
    output(out, display);
}

Two processes with interleaved execution and race condition.

	Process 1	Process 2
1	input(in, keyboard))	/
2	out = in	/
3	/	input(in, keyboard)
4	/	out = in
5	/	output(out, display)
6	output(out, display)	/

Critical Section Problem: Example 2

Producer-consumer with bounded, shared memory, buffer of size $n$

int in, out;
Item buffer[n];
int counter;

Producer:

void deposit(Item* next) {
    // wait for buffer to have empty space
    while (counter == n) no_op;
    buffer[in] = next;
    in = (in+1) % n;
    counter++;
}

Consumer:

Item* remove() {
    // wait for item to be put into buffer
    while (counter == 0) no_op;
    next = buffer[out];
    out = (out+1) % n;
    counter--;
    return next;
}

Interleaved Execution:

Producer	Consumer
counter++	counter--
reg[1] = counter	/
reg[1] = reg[1] + 1	/
/	reg[2] = counter
/	reg[2] = reg[2] - 1
counter = reg[1]	/
/	counter = reg[2]

We need to make sure that only one process can manipulate the value of counter at a time. This is synchronization

Critical Sections

A section of code where a shared variable is being accessed/updated.

Criteria for a good solution:

1. Mutual Exclusion: Only one process is allowed to enter critical section at a time.
2. Progress: A process that finishes a critical section should allow other processes to access it again.
3. Bounded Waiting: If a progress requests to enter a critical section, it should not be forced to wait indefinitely.

Software-Based Solutions

Solving race conditions between two processes

Wrong

while (turn != curr_pid) no_op;
critical_section();
turn = other_pid

Does not satisfy progress or bound waiting criteria

Wrong

while (flag[other_pid]) no_op;
flag[curr_pid] = TRUE;
critical_section();
flag[curr_pid] = FALSE;

Does not satisfy mutual exclusion: both processes could pass the while loop at the same time before setting variables.

Wrong

flag[curr_pid] = TRUE;
while (flag[other_pid]) no_op;
critical_section();
flag[curr_pid] = FALSE;

Does not satisfy bound waiting criteria: both flags can be set at the same time.

Correct

Combine turn and flag:

flag[curr_pid] = TRUE;
while (flag[other_pid] && turn == other_pid) no_op;
critical_section();
flag[curr_pid] = FALSE;

Hardware Solutions

• Disallow Interrupts, but that affects latency and multiple processors
• Atomic operations: operations that must be performed in a single step