Shared Variable Models
======================

"The world is a flat global store"

Shared Memory Architectures

	Processors -> Global Memory

Symmetrical Multiprocessing

	Ready Queue -> Processors -> New/Interrupted Processes

Shared Variables
----------------

int stack[]
int sptr = 0
P: loop
	v = produce()
	stack[sptr] = v }
	sptr++		} C1
C: loop
	sptr--
	v = stack[sptr] } C2
	consume v	}

- C1 and C2 critical regions
- Execution must not overlap
- Must be executed atomically

Lock Variable ("Mutex")
-----------------------

- Shared variable
- States "locked" and "unlocked"
- If locked, LOCK() blocks calling process until unlocked

mutex lock = INIT()
P: loop
	v = produce()
	LOCK(lock)
	C1
	UNLOCK(lock)
C: loop
	LOCK(lock)
	C2
	UNLOCK(lock)
	consume(v)

Only one process can have lock => enter critical region!

Semaphores
----------
Dijkstra

- Counter variable s
- s = INIT(n)
- P(s): if s>0 then s=s-1 else block
- V(s): if some process p blocked on s then release p else s:=s-1

Binary semaphore
  lock ~ sem = INIT(1)
n-ary semaphore
  sem = INIT(n)
  at most n processes can enter critical region

Barriers
--------

- Synchronization of n processes
- WAIT blocks until all n processes reach barrier

barrier b = INIT(n)
.
.
.
WAIT(b)

- n pathes synchronized
- used for separating data-parallel phases in SPMD program

Unix
----

- Process creation
- Process synchronization

pid = fork()
if (pid == 0)
  {
    ... child process
    exit(code)
  }
... parent process
wait(&status)


       =0 
fork() --> child
   |        |
   | >0     |
   |        v
   |      wait()
   v       
 wait() <----
   |
   v


fork/join model

Shared memory:
- child inherits state/memory of parent
- modifications by process not visible by other process
- special features for shared memory
  - s = shmalloc(n)
    allocate n bytes of shared memory s
  - allocated memory shared with children

System V IPC
- Interprocess communication
- Shared memory, semaphores, messages

---------------------
Handout Foster, Figure 4-10
A primitive stack monitor implemented in Sequent C
----------------------

Monitors
--------

Locks/semaphores are very low-level tools for process coordination
- lock forgotten => inconsistencies
- too many locks => deadlock

lock l1, l2
stack s1, s2

A: lock(l1)
   v = pop(s1)
   lock(l2)
   push(v, s2)
   unlock(l2)
   unlock(l1)

B: lock(l2)
   v = pop(s2)
   lock(l1)
   push(v, s1)
   unlock(l1)
   unlock(l2)

Monitor = ADT/Module that may be accessed by multiple processes

Monitor Queue

  Element Q[N]
  int front, back;

  Condition nonEmpty, nonFull;

  insert(elem)
	if (front = back) WAIT(nonFull)
	Q[back] = elem;
	back = (back+1) mod N;
	SIGNAL nonEmpty

  remove()
	if ((front+1) mod N = back) WAIT(nonEmpty)
	front = (front+1) % N
	elem = Q[front]
	SIGNAL nonFull
	return(elem)

  init()
	nonEmpty = FALSE
	nonFull = TRUE
	front = back = 0

end Queue

Main
	Queue.init()
	start P
	start Q
	
Process P
	loop
	  v = produce()
	  Queue.insert(v)  

Process Q
	loop
	  v = Queue.remove()
	  consume(v)

Behavior
- Only one process in monitor at a time
  other processes placed in entry queue
- condition variable C
- WAIT(C) places process in condition queue
- SIGNAL(C) places process from condition queue in signalled queue
- After signaller has left monitor
  next process in signalled queue enters monitor
- If no process any more in signalled queue,
  next process in entry queue may enter

"Signal and Continue" type of monitor
- various types of monitors, depending on relative priority of processes 
  - processes in entry queue
  - processes in signalled queue
  - signalling process
- process with highest priority continues in monitor

=> Shared data abstractions

Threads
-------

-------------
See Handout "Alle Fäden in der Hand (Teil 1)"
-------------

More on threads => client/server programming

Summary
-------
Shared variables are an extremely simple communication model
Process coordination typically low-level and error prone
Used for light-weight concurrency (threads)
Popular for programming SMPs and NUMAs