Synchronization Notes | EduRev

: Synchronization Notes | EduRev

 Page 1


5/3/2011 
1 
Synchronization 
Coherency protocols guarantee that a reading processor (thread) sees the 
most current update to shared data. 
 
Often we want to follow program behaviors that are on a higher plane than 
an individual access 
Coherency protocols do not regulate access to shared data: 
• Do not ensure that only one thread does a series of accesses to 
shared data or a shared hardware or software resource at a time 
    Critical sections order thread access to shared data 
• Do not force threads to start executing particular sections of code 
together 
    Barriers force threads to start executing particular sections of code 
together 
Spring 2011 1 CSE 471 - Synchronization 
Critical Sections: Motivating Example 
 
 
 
 
 
 
 
 
 
 
 
 
 
Spring 2011 2 CSE 471 - Synchronization 
Thread 0 
       
      ld r4,0(r1) 
   blt r4,r2,label 
   sub r4,r2,r4 
   st r4,0(r1) 
   call give_cash 
Thread 1 
 
 
  ld r4,0(r1) 
  blt r4,r2,label 
  sub r4,r2,r4 
  st r4,0(r1) 
  call give_cash 
   
400 
Time 
400 
500 
Acct 
Page 2


5/3/2011 
1 
Synchronization 
Coherency protocols guarantee that a reading processor (thread) sees the 
most current update to shared data. 
 
Often we want to follow program behaviors that are on a higher plane than 
an individual access 
Coherency protocols do not regulate access to shared data: 
• Do not ensure that only one thread does a series of accesses to 
shared data or a shared hardware or software resource at a time 
    Critical sections order thread access to shared data 
• Do not force threads to start executing particular sections of code 
together 
    Barriers force threads to start executing particular sections of code 
together 
Spring 2011 1 CSE 471 - Synchronization 
Critical Sections: Motivating Example 
 
 
 
 
 
 
 
 
 
 
 
 
 
Spring 2011 2 CSE 471 - Synchronization 
Thread 0 
       
      ld r4,0(r1) 
   blt r4,r2,label 
   sub r4,r2,r4 
   st r4,0(r1) 
   call give_cash 
Thread 1 
 
 
  ld r4,0(r1) 
  blt r4,r2,label 
  sub r4,r2,r4 
  st r4,0(r1) 
  call give_cash 
   
400 
Time 
400 
500 
Acct 
5/3/2011 
2 
Critical Sections 
A critical section 
• a sequence of code that only one thread can execute at a time 
• provides mutual exclusion  
• a thread has exclusive access to the code & the data that it 
accesses 
• guarantees that only one thread can update the data at a time 
• to execute a critical section, a thread  
• acquires a lock that guards it 
• executes its code 
• releases the lock 
 
The effect is to synchronize or order the access of threads with respect to 
their accessing shared data 
 
Spring 2011 3 CSE 471 - Synchronization 
Critical Sections: Correct Example 
 
 
 
 
 
 
 
 
 
 
 
 
 
Spring 2011 4 CSE 471 - Synchronization 
Thread 0 
 
   
   ld r4,0(r1) 
   blt r4,r2,label 
   sub r4,r2,r4 
   st r4,0(r1) 
   call release (lock) 
   call give_cash 
 
 
 
 
 
    
Thread 1 
 
 
 
    
    
 
 
   ld r4,0(r1) 
   blt r4,r2,6 
   sub r4,r2,r4 
   st r4,0(r1) 
   call release 
   call give_cash 
  
400 
Time 
300 
500 
Mem 
Page 3


5/3/2011 
1 
Synchronization 
Coherency protocols guarantee that a reading processor (thread) sees the 
most current update to shared data. 
 
Often we want to follow program behaviors that are on a higher plane than 
an individual access 
Coherency protocols do not regulate access to shared data: 
• Do not ensure that only one thread does a series of accesses to 
shared data or a shared hardware or software resource at a time 
    Critical sections order thread access to shared data 
• Do not force threads to start executing particular sections of code 
together 
    Barriers force threads to start executing particular sections of code 
together 
Spring 2011 1 CSE 471 - Synchronization 
Critical Sections: Motivating Example 
 
 
 
 
 
 
 
 
 
 
 
 
 
Spring 2011 2 CSE 471 - Synchronization 
Thread 0 
       
      ld r4,0(r1) 
   blt r4,r2,label 
   sub r4,r2,r4 
   st r4,0(r1) 
   call give_cash 
Thread 1 
 
 
  ld r4,0(r1) 
  blt r4,r2,label 
  sub r4,r2,r4 
  st r4,0(r1) 
  call give_cash 
   
400 
Time 
400 
500 
Acct 
5/3/2011 
2 
Critical Sections 
A critical section 
• a sequence of code that only one thread can execute at a time 
• provides mutual exclusion  
• a thread has exclusive access to the code & the data that it 
accesses 
• guarantees that only one thread can update the data at a time 
• to execute a critical section, a thread  
• acquires a lock that guards it 
• executes its code 
• releases the lock 
 
The effect is to synchronize or order the access of threads with respect to 
their accessing shared data 
 
Spring 2011 3 CSE 471 - Synchronization 
Critical Sections: Correct Example 
 
 
 
 
 
 
 
 
 
 
 
 
 
Spring 2011 4 CSE 471 - Synchronization 
Thread 0 
 
   
   ld r4,0(r1) 
   blt r4,r2,label 
   sub r4,r2,r4 
   st r4,0(r1) 
   call release (lock) 
   call give_cash 
 
 
 
 
 
    
Thread 1 
 
 
 
    
    
 
 
   ld r4,0(r1) 
   blt r4,r2,6 
   sub r4,r2,r4 
   st r4,0(r1) 
   call release 
   call give_cash 
  
400 
Time 
300 
500 
Mem 
5/3/2011 
3 
Barriers 
Barrier synchronization 
• a barrier: point in a program which all threads must reach before 
any thread can cross 
• threads reach the barrier & then wait until all other threads 
arrive 
• all threads are released at once & begin executing code 
beyond the barrier 
• example implementation of a barrier: 
• set a lock-protected counter to the number of threads 
• each thread decrements the counter 
• when the counter value becomes 0, all threads have crossed 
the barrier 
• code that implements the counter must be a critical section 
• useful for: 
• programs that execute in (semantic) phases 
• synchronizing after a parallel loop 
 
Spring 2011 5 CSE 471 - Synchronization 
Locking 
Locking facilitates access to a critical section & shared data. 
 
Locking protocol: 
• synchronization variable or lock 
• 0: lock is available 
• 1: lock is unavailable because another thread holds it 
• a thread obtains the lock before it can enter a critical section or 
access shared data 
• sets the lock to 1 
• thread releases the lock before it leaves the critical section or after 
its last access to shared data 
• clears the lock 
 
Spring 2011 6 CSE 471 - Synchronization 
Page 4


5/3/2011 
1 
Synchronization 
Coherency protocols guarantee that a reading processor (thread) sees the 
most current update to shared data. 
 
Often we want to follow program behaviors that are on a higher plane than 
an individual access 
Coherency protocols do not regulate access to shared data: 
• Do not ensure that only one thread does a series of accesses to 
shared data or a shared hardware or software resource at a time 
    Critical sections order thread access to shared data 
• Do not force threads to start executing particular sections of code 
together 
    Barriers force threads to start executing particular sections of code 
together 
Spring 2011 1 CSE 471 - Synchronization 
Critical Sections: Motivating Example 
 
 
 
 
 
 
 
 
 
 
 
 
 
Spring 2011 2 CSE 471 - Synchronization 
Thread 0 
       
      ld r4,0(r1) 
   blt r4,r2,label 
   sub r4,r2,r4 
   st r4,0(r1) 
   call give_cash 
Thread 1 
 
 
  ld r4,0(r1) 
  blt r4,r2,label 
  sub r4,r2,r4 
  st r4,0(r1) 
  call give_cash 
   
400 
Time 
400 
500 
Acct 
5/3/2011 
2 
Critical Sections 
A critical section 
• a sequence of code that only one thread can execute at a time 
• provides mutual exclusion  
• a thread has exclusive access to the code & the data that it 
accesses 
• guarantees that only one thread can update the data at a time 
• to execute a critical section, a thread  
• acquires a lock that guards it 
• executes its code 
• releases the lock 
 
The effect is to synchronize or order the access of threads with respect to 
their accessing shared data 
 
Spring 2011 3 CSE 471 - Synchronization 
Critical Sections: Correct Example 
 
 
 
 
 
 
 
 
 
 
 
 
 
Spring 2011 4 CSE 471 - Synchronization 
Thread 0 
 
   
   ld r4,0(r1) 
   blt r4,r2,label 
   sub r4,r2,r4 
   st r4,0(r1) 
   call release (lock) 
   call give_cash 
 
 
 
 
 
    
Thread 1 
 
 
 
    
    
 
 
   ld r4,0(r1) 
   blt r4,r2,6 
   sub r4,r2,r4 
   st r4,0(r1) 
   call release 
   call give_cash 
  
400 
Time 
300 
500 
Mem 
5/3/2011 
3 
Barriers 
Barrier synchronization 
• a barrier: point in a program which all threads must reach before 
any thread can cross 
• threads reach the barrier & then wait until all other threads 
arrive 
• all threads are released at once & begin executing code 
beyond the barrier 
• example implementation of a barrier: 
• set a lock-protected counter to the number of threads 
• each thread decrements the counter 
• when the counter value becomes 0, all threads have crossed 
the barrier 
• code that implements the counter must be a critical section 
• useful for: 
• programs that execute in (semantic) phases 
• synchronizing after a parallel loop 
 
Spring 2011 5 CSE 471 - Synchronization 
Locking 
Locking facilitates access to a critical section & shared data. 
 
Locking protocol: 
• synchronization variable or lock 
• 0: lock is available 
• 1: lock is unavailable because another thread holds it 
• a thread obtains the lock before it can enter a critical section or 
access shared data 
• sets the lock to 1 
• thread releases the lock before it leaves the critical section or after 
its last access to shared data 
• clears the lock 
 
Spring 2011 6 CSE 471 - Synchronization 
5/3/2011 
4 
Acquiring a Lock 
Atomic exchange instruction: swap a value in memory & a value in a 
register as one operation 
• set the register to 1 
• swap the register value & the lock value in memory 
• new register value determines whether got the lock 
  
AcquireLock: 
 li R3, #1   /* create lock value 
 swap  R3, 0(R4)  /* exchange register & lock 
 bnez  R3, AcquireLock /* have to try again */ 
 
• also known as atomic read-modify-write a location in memory 
 
Other examples 
• test & set: tests the value in a memory location & sets it to 1 
• fetch & increment/decrement: returns the value of a memory 
location +/- 1 
Spring 2011 7 CSE 471 - Synchronization 
Releasing a Lock 
Store a 0 in the lock 
 
Spring 2011 8 CSE 471 - Synchronization 
Page 5


5/3/2011 
1 
Synchronization 
Coherency protocols guarantee that a reading processor (thread) sees the 
most current update to shared data. 
 
Often we want to follow program behaviors that are on a higher plane than 
an individual access 
Coherency protocols do not regulate access to shared data: 
• Do not ensure that only one thread does a series of accesses to 
shared data or a shared hardware or software resource at a time 
    Critical sections order thread access to shared data 
• Do not force threads to start executing particular sections of code 
together 
    Barriers force threads to start executing particular sections of code 
together 
Spring 2011 1 CSE 471 - Synchronization 
Critical Sections: Motivating Example 
 
 
 
 
 
 
 
 
 
 
 
 
 
Spring 2011 2 CSE 471 - Synchronization 
Thread 0 
       
      ld r4,0(r1) 
   blt r4,r2,label 
   sub r4,r2,r4 
   st r4,0(r1) 
   call give_cash 
Thread 1 
 
 
  ld r4,0(r1) 
  blt r4,r2,label 
  sub r4,r2,r4 
  st r4,0(r1) 
  call give_cash 
   
400 
Time 
400 
500 
Acct 
5/3/2011 
2 
Critical Sections 
A critical section 
• a sequence of code that only one thread can execute at a time 
• provides mutual exclusion  
• a thread has exclusive access to the code & the data that it 
accesses 
• guarantees that only one thread can update the data at a time 
• to execute a critical section, a thread  
• acquires a lock that guards it 
• executes its code 
• releases the lock 
 
The effect is to synchronize or order the access of threads with respect to 
their accessing shared data 
 
Spring 2011 3 CSE 471 - Synchronization 
Critical Sections: Correct Example 
 
 
 
 
 
 
 
 
 
 
 
 
 
Spring 2011 4 CSE 471 - Synchronization 
Thread 0 
 
   
   ld r4,0(r1) 
   blt r4,r2,label 
   sub r4,r2,r4 
   st r4,0(r1) 
   call release (lock) 
   call give_cash 
 
 
 
 
 
    
Thread 1 
 
 
 
    
    
 
 
   ld r4,0(r1) 
   blt r4,r2,6 
   sub r4,r2,r4 
   st r4,0(r1) 
   call release 
   call give_cash 
  
400 
Time 
300 
500 
Mem 
5/3/2011 
3 
Barriers 
Barrier synchronization 
• a barrier: point in a program which all threads must reach before 
any thread can cross 
• threads reach the barrier & then wait until all other threads 
arrive 
• all threads are released at once & begin executing code 
beyond the barrier 
• example implementation of a barrier: 
• set a lock-protected counter to the number of threads 
• each thread decrements the counter 
• when the counter value becomes 0, all threads have crossed 
the barrier 
• code that implements the counter must be a critical section 
• useful for: 
• programs that execute in (semantic) phases 
• synchronizing after a parallel loop 
 
Spring 2011 5 CSE 471 - Synchronization 
Locking 
Locking facilitates access to a critical section & shared data. 
 
Locking protocol: 
• synchronization variable or lock 
• 0: lock is available 
• 1: lock is unavailable because another thread holds it 
• a thread obtains the lock before it can enter a critical section or 
access shared data 
• sets the lock to 1 
• thread releases the lock before it leaves the critical section or after 
its last access to shared data 
• clears the lock 
 
Spring 2011 6 CSE 471 - Synchronization 
5/3/2011 
4 
Acquiring a Lock 
Atomic exchange instruction: swap a value in memory & a value in a 
register as one operation 
• set the register to 1 
• swap the register value & the lock value in memory 
• new register value determines whether got the lock 
  
AcquireLock: 
 li R3, #1   /* create lock value 
 swap  R3, 0(R4)  /* exchange register & lock 
 bnez  R3, AcquireLock /* have to try again */ 
 
• also known as atomic read-modify-write a location in memory 
 
Other examples 
• test & set: tests the value in a memory location & sets it to 1 
• fetch & increment/decrement: returns the value of a memory 
location +/- 1 
Spring 2011 7 CSE 471 - Synchronization 
Releasing a Lock 
Store a 0 in the lock 
 
Spring 2011 8 CSE 471 - Synchronization 
5/3/2011 
5 
Load-linked & Store Conditional 
Performance problem with atomic read-modify-write:  
• 2 memory operations in one 
• must hold the bus until both operations complete 
 
Pair of instructions appears atomic 
• avoids need for uninterruptible memory read & write pair 
• load-locked & store-conditional 
• load-locked returns the original (lock) value in memory 
• if the contents of lock memory has not changed when the store-
conditional is executed, the processor still has the lock 
• store-conditional returns a 1 if successful 
  
GetLk: li R3, #1  /* create lock value 
   ll R2, 0(R1) /* read lock variable 
   ... 
   sc R3, 0(R1) /* try to lock it 
   beqz R3, GetLk /* cleared if sc failed 
   ... (critical section) 
Spring 2011 9 CSE 471 - Synchronization 
Load-linked & Store Conditional 
Implemented with special processor registers:  lock-flag register & lock-
address register 
• load-locked sets lock-address register to lock’s memory address & 
lock-flag register to 1 
• store-conditional returns lock-flag register value 
• if still 1, then processor has the lock 
• if 0, then processor no longer has the lock & has to try again 
• lock-flag register is cleared if the lock is written by another 
processor 
• lock-flag register cleared if context switch or interrupt 
Spring 2011 10 CSE 471 - Synchronization 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!