Concurrent Programming Class Notes

Lecture Notes for Concurrent Programming

19 June 2003 - Using Critical Sections

Outline

Protecting Shared State
Partitioning Shared State
General Rules
Constructor-Destructor Behavior
Higher-Level Abstractions
Conditional Synchronization

Protecting Shared State

Given some shared state protected by atomic execution.

All access should be performed inside the same critical section.

int x

co
   < x = . . . >
 
   < x = . . . >
||
   < x = . . . >
oc

int x
peterson cs

co
   cs.enter1()
     x = . . .
 
     x = . . . 
   cs.exit1()
||
   cs.enter2()
     x = . . .
   cs.exit2()
oc

Partitioning Shared State

Critical sections cut down on concurrency.
More critical sections mean more concurrency.

Partition shared state into separate critical sections.

All references to shared state within the same partition.

int x, y

co
   < x = no y >
 
   < y = no x >
||
   < y = no x >

   < x = no y >
oc

int x, y
bakery xcs(2), ycs(2)

co
   xcs.enter(1)
     x = no y
   xcs.exit(1)
 
   ycs.enter(1)
     y = no x
   ycs.exit(1)
||
   ycs.enter(2)
     y = no x
   ycs.exit(2)

   xcs.enter(2)
     x = no y
   xcs.exit(2)
oc

General Rules

Minimize execution within critical sections.
- Never block within a critical section.
Properly match a critical section's entry and exit.
```
cs.entry(i)

// whatever

if B
  cs.exit(i)
```
Protect all shared state with critical sections.
- Tough under maintenance.
Be careful nesting critical sections.
- In fact, don't nest critical sections.

The Constructor-Destructor Idiom

In C++, use the constructor-destructor idiom.

class stanley
  const critical_section & cs
  const unsigned tid

  stanley(critical_section & cs
        unsigned tid) 
    : cs(cs), tid(tid)
    cs.enter(tid)

 ~stanley() 
    cs.exit(tid)

void f(critical_section & cs)
  { const stanley s(cs, tid)
    // whatever
  }

This idiom properly and always matches entry and exit.
- Even when exceptions happen in the critical section.
This idiom doesn't work for Java.
- Finializers are not as well behaved.
- The Java synchronized construct does provide similar behavior.

Higher-Level Abstractions

Consider packaging a critical section and data together.
```
class database

  const unsigned n
  Bakery cs(n)
  vector db

  void write(unsigned tid, data d)
    cs.enter(tid)
      db = d
    cs.exit(tid)
```
- Global data are pushed to the smallest enclosing scope.
- Critical section use is correct and unconditionally enforced.
Be cautious with this technique.
- Document it throughly.
- It can easily lead to nested critical sections and deadlock.

Conditional Synchronization

Conditional synchronization delays execution until a condition is true.
- < await B ; S >

Wait until B is true, then do S, all atomically.

cs-enter()
  while (not B) skip
  S
cs-exit()

Under atomic execution, B can never change.
- All access to B occur in the same critical section.
```
while (not B) skip
cs-enter()
  S
cs-exit()
```
B can be interfered with.

Implementing Conditional Synchronization

If B is false, step out and let another computation in.

cs-enter()
  while (not B) 
    cs-exit()
    cs-enter()
  S
cs-exit()

Delay the spinning computation to defer to waiters.
```
cs-enter()
  while (not B) 
    cs-exit()
    random_delay()
    cs-enter()
  S
cs-exit()
```
- This is an important optimization for hardware supported sharing.

Points to Remember

Every shared-state access has to be protected.
- Unprotected access to shared state causes nasty errors.
Partition shared-state into separate critical sections.
- Increase potential concurrency.
Explicit critical section access is easy to get wrong.
- Extravagant critical section access should make you nervous.
Exploit the constructor-destructor idiom when you can.
- Sorry Java programmers.
Try packaging critical sections and data together.
- But document well and watch out for nesting.
Critical sections can implement conditional synchronization.

This page last modified on 1 July 2003.