笔记 OSC_Concurrency2

2017-01-09

Concurrency 2

Overview

Software approaches: Peterson’s solution Hardware approaches:
Disabling interrupts:
- test_and_set()
- compare_and_swap()
Higher level approaches include mutexes and semaphores
Peterson’s Solution
Peterson’s solution is a software based solution which worked well for older machines
Two shared variables are used:
- turn: indicates which process is next to enter its critical section
- boolean flag[2]: indicates that a process is ready to enter its critical section

It is restricted[限制] to two processes that execute in strict alternation[严格的交替]

do {
	flag[j] = true; // j wants to enter critical section turn = i; // allow i to access first
	while (flag[i] && turn == i);
	// whilst i wants to access critical section
	// and its i’s turn, apply busy waiting 
	
	// CRITICAL SECTION
	
	flag[j] = false;
	// remainder section
} while (...);

Peterson’s solution satisfies all requirements for mutual exclusion
Mutual exclusion requirement: the variable turn can have at most one value at a time
- while(flag[i] && turn == i)or while(flag[j] && turn == j) is true and at most one process can enter its critical section (mutual exclusion)

Disabling Interrupts

Disable interrupts whilst executing a critical section and prevent interruption (i.e., interrupts from timers, I/O devices, etc.)
- Think of the counter++ example
  = counter;
  1
  2
  register = register + 1
  counter = register;
Disabling interrupts “may” be appropriate on a single CPU machine
This is inefficient on modern multi-core/multi processor machines
- Disabling interrupts on all cores/CPUs takes time and causes delays
- CPU capacity[能力] is lost on other cores

Atomic Instructions

Implement test_and_set() and swap_and_compare() instructions as a set of atomic (UN-interruptible) instructions
- Reading and setting the variable(s) is done as one “complete” set of instructions
- If test_and_set() or compare_and_swap() are called simultaneously, they will be executed sequentially
They are used in in combination with global lock variables, assumed to be true if the lock is in use

test_and_set()

Test and set must be atomic/UN-interruptable

// Test and set method
boolean test_and_set(boolean * lock) { 
	boolean rv = *lock;
	*lock = true;
	return rv;
}
// Example of using test and set method
do {
	// WHILE the lock is in use, apply busy waiting
	while (test_and_set(&lock)); 
	// Lock was false, now true
	// CRITICAL SECTION
	...
	lock = false;
	...
	// remainder section
} while (...)

compare_and_swap()

// Compare and swap method
int compare_and_swap(int *lock, int expected, int new_value) { 
	int temp = *lock;
	if(*lock == expected)
	*lock = new_value; return temp;
}
// Example using compare and swap method
do {
	// While the lock is in use (i.e. == 1), apply busy waiting
	while (compare_and_swap(&lock, 0, 1) != 0); 
	// Lock was false, now true
	// CRITICAL SECTION
	...
	lock = 0;
	...
	// remainder section
} while (...);

Disadvantages:

test_and_set()and compare_and_swap() are hardware instructions and (usually) not directly accessible to the user
Busy waiting is used
Starvation is possible
Deadlock is possible

The OS uses the hardware instructions to implement higher level mechanisms/instructions for mutual exclusion, i.e. mutexes and semaphores

##Summary

Peterson’s solution (software)
Hardware instructions: interrupt disabling, (test_and_set, compare_and_swap)