Process Synchronization
Concurrent programs are executed by multiple
Operating Systems
cooperating processes that share some data
Concurrent access to shared data may result in data
inconsistency
OS must provide mechanisms to synchronize and
coordinate cooperating processes
December 20, 2008 Antônio Augusto Fröhlich ([Link] 42
Producer X Consumer
Producer: Consumer:
Operating Systems
shared int counter; shared int counter;
shared char buf[N]; shared char buf[N];
int main() int main()
{ {
const int n = N; const int n = N;
int in = 0; int out = 0;
while (1) { while (1) {
while (counter == n); while (counter == 0);
buf[in] = produce(); consume (buf[out]);
in = ++in % n; out = ++out % n;
counter++; counter--;
} }
} }
December 20, 2008 Antônio Augusto Fröhlich ([Link] 43
Race Conditions
Producer: Consumer:
Operating Systems
counter++; counter--
load R1,[counter] load R2,[counter]
inc R1 dec R2
store R1,[counter] store R2,[counter]
R1 R2 [counter]
0) P: load R1,[counter] 5 - 5
1) P: inc R1 6 - 5
2) C: load R2,[counter] 6 5 5
3) C: dec R2 6 4 5
4) C: store R2,[counter] 6 4 4
5) P: store R1,[counter] 6 4 6
December 20, 2008 Antônio Augusto Fröhlich ([Link] 44
Critical Sections
Sections of concurrent programs in which shared
Operating Systems
data is manipulated
Conditions for proper execution
● Mutual Exclusion: only a single process executes a critical
section on a time
● Execution progress: a process that is not executing a critical
section cannot prevent others from doing it
● Bounded waiting: a process cannot be deprived from
execution a critical section indefinitely
December 20, 2008 Antônio Augusto Fröhlich ([Link] 45
Synchronization Algorithm I
Process 0 Process 1
Operating Systems
shared int turn; shared int turn;
int main() int main()
{ {
while (1) { while (1) {
while(turn != 0); while(turn != 1);
/* critical */ /* critical */
turn = 1; turn = 0;
/* remainder */ /* remainder */
} }
} }
Misses the progress condition
December 20, 2008 Antônio Augusto Fröhlich ([Link] 46
Synchronization Algorithm II
Process 0 Process 1
Operating Systems
shared int flag[2]; shared int flag[2];
int main() int main()
{ {
while (1) { while (1) {
flag[0] = 1; flag[1] = 1;
while(flag[1]); while(flag[0]);
/* critical */ /* critical */
flag[0] = 0; flag[1] = 0;
/* remainder */ /* remainder */
} }
} }
Misses the bounded waiting condition
December 20, 2008 Antônio Augusto Fröhlich ([Link] 47
Synchronization Algorithm III
(Peterson)
Process 0 Process 1
Operating Systems
shared int turn; shared int turn;
shared int flag[2]; shared int flag[2];
int main() int main()
{ {
while (1) { while (1) {
flag[0] = 1; flag[1] = 1;
turn = 1; turn = 0;
while(flag[1] && while(flag[0] &&
turn); !turn);
/* critical */ /* critical */
flag[0] = 0; flag[1] = 0;
/* remainder */ /* remainder */
} }
} }
December 20, 2008 Antônio Augusto Fröhlich ([Link] 48
Synchronization Hardware
Test and Set Lock (TSL) instruction
Operating Systems
int tsl(int * ptr)
{
int tmp = *ptr;
*ptr = 1;
return tmp;
}
Usage
shared int lock = 0;
int main()
{
while (1) {
while(tsl(lock));
/* critical */
lock = 0;
}
}
December 20, 2008 Antônio Augusto Fröhlich ([Link] 49
Semaphores
Integer variable accessible through atomic operations
Operating Systems
P and V
p(s): while(s <= 0); v(s): s++;
s--;
Usage
shared int mutex;
int main()
{
while(1) {
p(mutex);
/* critical */
v(mutex);
/* remainder */
}
}
December 20, 2008 Antônio Augusto Fröhlich ([Link] 50
Semaphore Implementation
class Semaphore
{
Operating Systems
public:
Semaphore(int i) : s(i) {}
void p();
void v();
private:
int s;
list<Process> l;
};
extern Process * running;
void Semaphore::v() void Semaphore::p()
{ {
if(++s <= 0) if (--s < 0) {
[Link]()->wakeup(); [Link](running);
} running->sleep();
}
}
December 20, 2008 Antônio Augusto Fröhlich ([Link] 51