cs343.txt

* What is a multi-exit loop?

A loop that has one or more exit locations occurring within the body of the loop.

* What is a flag variable?

A variable used solely to affect control flow.

* What are flag variables equivalent to?

Goto statements.

* What is static multi-level exit?

Exiting multiple control structures, while the exit points are known at
compile time.

* How can dynamic multi-level exit be used to handle exceptional events?

Since dynamic multi-level exit allows you to return from any statement to
anywhere, you can return to an "exception handler" following an
exceptional event.

* What are the traditional approaches to handling exceptional events?

- Return code: returns value indicating normal or exceptional execution.
- Status flag: set global variable indicating normal or exceptional execution.
- Fix-up routine: routine called for an exceptional event to return
                  a corrective result.

* What are the drawbacks of the traditional approaches to handling exceptional events?

- Checking return code or status flag is optional.
- Return code mixes exceptional and normal values.

* What is a source execution w.r.t exception handling?

The execution raising an exception.

* What is a faulting execution w.r.t exception handling?

The execution changing control flow due to an exception.

* What is the static/dynamic call/return table?

                       call/raise
return/handled|   static        dynamic
----------------------------------------------------
static        |   sequel        termination exception
dynamic       |   routine       virtual routine

* Why is starting a full-coroutine cycle difficult?

Because it requires every coroutine to know at least one other coroutine,
causing a dependency cycle that must be addressed.

# 5 Concurrency

* What is a thread?

An independent sequential execution path through a program.

* What is a process?

A program component that has its own thread and has the same state information
as a coroutine.

* What is a task?

Process that is reduced along some particular dimension. Does "only one thing".

* What is parallel execution?

When 2 or more operations occur at the same time.
Can only occur when multiple processors are present.

* What is concurrent execution?

Any situation in which execution of multiple threads appears to be
performed in parallel.

* What is Amdahl's law?

S_c = 1 / ((1 - P) + P/C)

* What bounds the speedup of concurrent sections?

The critical path of computation.

* What are the three mechanisms required for concurrency?

1. Creation: Can cause another thread to be created.
2. Synchronization: Establish timing relationships among threads.
3. Communication: Transmit data among threads.

* What are the 5 rules of the mutual exclusion game?

1. Only one thread can be in a critical section at a time with respect to a
   particular object. (Safety)
2. Threads may run at arbitrary speed and in arbitrary order, while the
   underlying system guarantees a thread makes progress.
3. If a thread is not in the entry or exit code controlling access to the
   critical section, it may not prevent other threads from entering the
   critical section.
4. In selecting a thread for entry to a critical section, a selection cannot
   be postponed indefinitely (liveness).
5. After a thread starts entry into the critical section, it must eventually
   enter.

* What is livelock?

No one being picked to enter the critical section indefinitely.

* What can cause unfairness?

Threads not being serviced in first-come first-served order.

* What causes barging?

Waiting threads are overtaken by a thread arriving later.

* What are the 5 conditions to get into a dead-lock?

1. There exists more than one shared resource requiring mutual exclusion.
2. A process holds a resource while waiting for access to a resource held
   by another process. (Hold-and-wait)
3. Once a process has gained access to a resource, the runtime system cannot
   get it back. (no preemption)
4. There exists a circular wait of processes on resources.
5. These conditions must occur simultaneously.

* What is a synchronization dead-lock?

Failure in co-operation. A blocked task is never unblocked.

# 7.3 Deadlock prevention

* How does deadlock prevention work?

Eliminate one or more of the conditions required for a deadlock.

* What is synchronization prevention?

Eliminating all synchronization from a program.
Therefore, there is no communication between the threads, and all tasks
run completely independently.

* What is the problem with disallowing hold and wait?

There is poor resource utilization, and some possible starvation.
This is because all resources have to be held from the start of the program,
even if they may not be used!

* Why is there poor resource utilization when disallowing hold and wait?

All resources that the task could use have to be reserved at the same time,
including resources that may never be used.

* Why is starvation possible when disallowing hold and wait?

All resources required by a task may never be available at the same time.

* What is the problem with allowing preemption w.r.t deadlock prevention?

Preemption is dynamic, and cannot be applied statically.

* How can one prevent a circular wait for resources?

Using an ordered resource policy.

* What is the ordered resource policy?

1. Divide all resources into classes. (R1, R2, R3, ...)
2. Rule: Can only request a resource from class Ri if holding no resources
   from any class Rj, j >= i.

* What is the general principle of banker's algorithm?

Generate a safe sequence of allocations that result in no deadlock.

* What information does the oracle need to know in the banker's algorithm?

1. The number of resources available of each type.
2. The resource allocation needed for each task in the worst case.

* What is the banker's algorithm?

1. Given the state of execution, ask "is there a task that can run to
   completion such that its maximum requirements is less than the available
   resources"?
2. Execute that task to completion, all resources that it held should be
   free now.
3. Repeat until all tasks are finished.

* What is an allocation graph?

Create a graph of processes and resource usage at each moment a resource is
allocated.

* How can you use an allocation graph to check for deadlocks?

If a graph contains no cycles, then no process in the system is deadlocked.
However, if a resource has several instances, cycles are not always deadlocks.

* What can you do with resources with several instances in an allocation graph?

Break them up into multiple nodes.
Now if there is a cycle, we know that the system is deadlocked.

* How can you avoid deadlocks using an allocation graph?

1. Assign resources to tasks such that there is no cycle.
2. Complete the task, reducing the graph.
3. Repeating until all tasks are finished.

# 7.5 Detection and Recovery

* What is the alternative to deadlock prevention?

Let the deadlock happen and recover from it.

* What does deadlock recovery involve?

Preemption of one or more processes in a cycle.

* What in preempting a task for deadlock recovery?

1. The decider of the task must prevent starvation.
2. Preemption victim must be killed and restarted to its last checkpoint state.
3. Even that might not work since the victim may have made changes before the
   preemption.

* What happens when Windows deadlocks?

Blue screen!

# 7.6 Which method to choose?

* What is the only deadlock prevention policy to have practical value?

Ordered resource policy.

# Exam questions

* After raising a nonlocal exception between coroutines in uC++, what are two additional actions that must be performed to make it work?

1. The faulting coroutine must have called _Enable.
2. The source coroutine must resume the faulting coroutine so the nonlocal
   exception can propagate.

* How does Dekker's algorithm work without atomic assignment?

No simultaneous assignments on the three shared variables.

Last will never be assigned at the same time by both you and me, because
the assignment happens only in the critical section, where only one task can
be in at the same time.

Me and you are only written to by one task and read by the other task.

* Given only N bits to construct an N-task software solution for mutual
exclusion, what rule of the mutual-exclusion game is always broken?

Rule 5: Starvation.

This is because you can only set boolean flags, so there is no way to keep
track of who came first!

* For the N-task bakery algorithm, how many bits are used?

NM bits, where N is the number of tasks, and M is the maximum size of the
ticket.

* Does the Bakery algorithm solve all 5 rules of the critical-section game
perfectly?

No, it is only probablistically correct because the ticket number can
overflow.

* Given an atomic compare/assignment instruction, implement an atomic increment routine.

int inc(int& val) {
  while (true) {
    int old = val;
    if (CAssn(val, old, old + 1)) {
      return old;
    }
  }
}

* How can you write a spinning counting semaphore using a binary semaphore?

class cSem {
  private:
    int counter;
    bSem sem;
  public:
    cSem(int initial) : counter(initial) {}
    void P() {
      while (true) {
        sem.P();
        if (counter > 0) {
          counter = counter - 1;
          sem.V();
          return;
        } else {
          sem.V();
        }
      }
    }
    void V() {
      sem.P();
      counter = counter + 1;
      sem.V();
    }
};

* Why, in C++, is A || B and B || A not identical?

The || operator "short-circuits" if the left-hand side is truthy. This means
that the expression on the right-hand side may not be evaluated, and any
side effects that it could cause are not executed.

* What is the key restriction with labelled exits that make them acceptable control transfers?

Labelled exits should not be used to create a loop, and should only be used to
transfer out of control structures.

* What execution context is saved when making a routine call?

The current stack of the caller. This includes all statically allocated
variables, and the current execution state (the program counter).

* Does the compiler know where a routine's return statement transfer control to?

No. The return statement transfers control to the routine's first resumer. This
cannot be statically inferred.

The return address is found on the coroutine's stack.

* How can a callback routine be implemented in C++?

A function is passed in as a parameter (routine pointer).

* What is the problem with using longjmp/setjmp in C++ programs?

No destructors are executed while unwinding the stack.

* What are two reasons why derived exception-types are a useful feature to have in an EHM?

1. Allows the faulting execution only worry about categories of exceptions,
   instead of specific ones.
2. Allows new exception, specific exceptions to be declared without needing to
   add new checks.
3. Allows a handler to match multiple exception types.

* What is the difficulty of accessing local variables in an resumption handler?

You don't know exactly where on the stack the local variables are. There is
an arbitrary number of stack frames between the handler and the source.

* Why does a coroutine need its own stack?

So that it can save its execution state in between suspend and resumes.

* What is the difference between a coroutine and a task?

Only one coroutine can be executing instructions at the same time.
Tasks each have their own thread of control.

* What is the difference between the suspend and resume operations of a coroutine?

suspend suspends the current coroutine and resumes the coroutine that last
resumed it.
resume suspends the current coroutine and resumes "this" coroutine.

* Does a program with coroutines, but without tasks, ever need synchronization locks?

No, because only one coroutine can be executing at the same time, and the
program will invoke the coroutines deterministically.

* How can concurrency improve the efficiency of programs executed on a single CPU?

The programs can be waiting on external resources (e.g. file IO). This is case,
it is possible to proceed with the rest of the program instead of blocking it.

* Does a concurrent program on a single CPU system without preemption ever need mutual exclusion?

No, because only one thread is active at a single time and the program can make
deterministic choices on how to invoke them.

* What makes the retract-intent solution better than the declare-intent solution even though they both violate rule 4 (infinite postponement)?

The declare-intent solution will fail when a problematic solution happens once.
(i.e. They both declare intent at the same time.)
The retract-intent solution will only keep failing when its problematic solution
constantly occurs.
(i.e. Both tasks keep declaring and retracting intent at the same time.)

* What is the disadvantage of only providing COBEGIN and COEND operations for concurrency?

Interleaving dependencies cannot be expressed.

For example:

START T1
S1
START T2
S2
WAIT T1
S3
WAIT T2
S4

* What are the problems that result from encapsulating a thread library into the C++ OO model?

When starting the thread in the base-class constructor, it cannot be guaranteed
that all constructors in the inheritance hierarchy are executed before 
invocation of the thread's routine.

When waiting for the thread in the base-class destructor, it cannot be
guaranteed that the thread's routine has finished when executing destructors
in the inheritance hierarchy.

* What is the swap instruction in pseudocode?

void swap(int& a, int& b) {
  int temp = a;
  a = b
  b = temp;
}

* How can the swap instruction be used to solve the N-task mutex problem for rules 1-4?

int lock = 0
void run() {
  int closed = 1;
  while (true) {
    swap(lock, closed);
    if (closed == 0) {
      break;
    }
  }
  /* critical section */
  lock = 0;
}

* What is the primary benefit of using an exit in the middle of a loop?

You can avoid duplicating priming code.

* Why should a loop exit NOT have an else clause?

It is redundant since the loop will only continue if the loop exit condition
was false.

* What does multi-level exits allow the elimination of?

Flag variables.

* How does Sequel provide simple exception handling?

The block's stack is unwound after the end of the block.

* Why does C longjmp execute faster than C++ throw?

Because it doesn't call destructors, so it can be a direct stack transfer.

* What happens when a resumption exception is not handled?

It is rethrown as a termination exception.

* What class of problems does a coroutine handle better than the basic control-flow constructs?

Problems that can be simplified to traversing a DFA or state-machine.

* Why does coroutine main termination resume the start coroutine work for 80% of all coroutines?

For semi-coroutines, the starter is often the only resumer.
For full-coroutines, starters almost always lead to uMain, which can delete
unterminated coroutines.

* What actions occur in uC++ if a coroutine does not handle an exception?

Raises the non-local exception UnhandledException to the last resumer.

* What is the relationship between a user and a kernel thread?

User threads run on kernel threads.
User threads are scheduled by a library, while kernel threads are scheduled by
the OS.

* What does unbounded overtaking mean?

A low-priority thread can reenter the critical section any number of times
until the high-priority thread declares its intent.

* What is the property of a hardware atomic instruction that allows it to solve mutual exclusion?

Nothing can preempt in the middle of the instruction.

* What rule do hardware atomic instructions violate?

Variable order and speed of execution. (Rule 2)

* How is barging prevented when implementing a mutex lock?

Hold onto the internal lock between releasing and unblocking tasks.

* Can spin locks be used for synchronization and mutual exclusion?

Both.

* Can owner locks be used for synchronization and mutual exclusion?

Only mutual exclusion.

* Can condition locks be used for synchronization and mutual exclusion?

Only synchronization.

* Can barriers be used for synchronization and mutual exclusion?

Only synchronization.

* Can semaphores be used for synchronization and mutual exclusion?

Both.

* Why does modularization cause problems with multi-level exit?

Labels are known only in a routine's scope, so the modules may no longer know
about them.

* When a resumption handler completes, does it perform a static or dynamic return?

Dynamic. Because you don't know where it's going to resume.

* When a termination handler completes, does it perform a static or dynamic return?

Static. Because you know that the statements right after the catch will be
executed.

* What's an advantage of restricting the placement of resume to within a coroutine's members?

The coroutine programmer is able to fully control how the coroutine is resumed.

* What is the advantage of a stackful coroutine vs a stackless one?

A stackful coroutine can modularize code containing a suspend into a helper function.
It can also support recursion.

* What does RW safe mean?

RW-safe means that an algorithm works even if simultaneous writes to the same
location scramble the bits or simulataneous read during a write to the same
location sees the bits flicker.

* What does ABA mean in the ABA problem w.r.t lock-free data structures?

A is removed.
Before A can be removed fully, the thread is preempted and
A then B is removed and A is put back.
When the thread is restarted its view of A is now incorrect.

* Why are condition locks weaker than semaphores?

Condition locks contain no state and cannot remember previous actions performed
on the lock, like a previous signal.

* Why is synchronization more complex for blocking locks than spinning locks?

Blocking locks get only one change to test lock state.
Therefore, you must ensure that the blocking and acquiring is atomic w.r.t to
the releaser.

* When is a loop in a concurrent program a busy-wait and when is it not a busy-wait?

A loop needs a bound or else its a busy wait.

* What can fat atomic instructions eliminate completely?

Busy waiting.

* What is the advantage of using fat atomic instructions?

You can perform a critical section atomically without expensive solutions.

* What is the disadvantage of using fat atomic instructions?

It blocks interrupts during that time.

* Construct a synchronization deadlock with a semaphore.

sem = 0;
sem.P();

* Construct a mutual-exclusion deadlock with a semaphore.

sem = 1;
sem.P();

other task:

sem.P();

# Lock Programming

* How does buffering work?

- Tasks communicate unidirectionally through a queue.
- Producer adds items to the back of the queue.
- Consumer removes items from the front of the queue.

* What is a split binary semaphore?

A collection of semaphores where at most one of the collection has the value 1.

* When are split binary semaphores used?

When different kinds of tasks have to block separately.

* What technique do split binary semaphores use to solve mutual-exclusion problems?

Baton passing.

* What are the rules of baton passing?

- There is exactly one baton.
- Nobody moves in the entry/exit code unless they have the baton.
- Once the baton is released, one cannot read/write variables in the entry/exit.

* Can mutex/condition locks perform baton passing to prevent barging?

Only if the signalled task does not need to re-acquire the lock before continuing.

* What is the readers and writers problem?

- Multiple tasks share a resource. Some read, some write.
- Allow multiple concurrent readers, but serialize writer access.

* How can we use split-binary semaphores to segregate tasks in the readers and writers problem?

Separate tasks into 3 categories:
- Arrivers
- Readers
- Writers

* What is a shadow queue?

A queue that stores additional information about tasks blocked in a semaphore.

# 7 Concurrent Errors

* What is a race condition?

When there is missing synchronization or mutual exclusion.
At least two threads race along assuming that it exists.

* What is a live-lock?

When at least two threads are stuck waiting for another to go first.

* What is a property of live-locks?

There always exits some mechanism to break ties on simultaneous arrival that
deals effectively with the live-lock.

* What is starvation?

A selection algorithm ignores one or more tasks so they are never executed.

* What is a deadlock?

When one or more tasks are waiting for an event that will never occur.

* What is starvation?

When a task tries to acquire a lock, but never does.

# Indirect communication

* What is the idea of "critical regions" w.r.t concurrency APIs?

- Declare which variables are to be shared.
- Access to shared variables are restricted to within a REGION statement.
- Mutual exclusion within that statement.

* What are some problems of the "critical regions" idea of concurrency?

- Nesting these critical regions can cause a deadlock.
- Simultaneous reads are impossible.

* What are conditional critical regions?

Introduce a condition that must be true as well as having mutual exclusion
before you can enter the critical region.

* What is a monitor?

An abstract data type that combines shared data with serialization of its
modification.

* What is a mutex member?

A member function that does not begin execution if there is another active
mutex member.

* What are the two types of synchronization scheduling?

External and internal.

* What is external scheduling? How does one do it in uC++?

Tasks are scheduled outside the monitor. _Accept statement.

* What is internal scheduling? How does one do it in uC++?

Tasks are scheduled inside the monitor. uCondition variables.

* What is the advantage of external scheduling over internal scheduling?

External scheduling is easier to specify and explain over internal scheduling.

* When is external scheduling unusable?

- Scheduling depends on member parameter values.
- Scheduling must block in the monitor, but cannot guarantee that the next call
fulfils cooperation.

* What is the nested monitor problem?

Acquire monitor X, call to monitor Y, wait on condition in Y.

Now monitor Y's mutex is released, but monitor X's mutex is not.

* When does explicit scheduling occur?

- An accept statement blocks the active task on the acceptor stack and makes
a task ready from the specified mutex member queue.
- A signal moves a task from the specified condition to the signalled stack.

* When does implicit scheduling occur?

When a task waits in or exits from a mutex member and a new task is selected.

* What are the possible orderings of relative priority between task queues in a monitor?

Calling queue has to be lowest priority (or equal or lower), anything else is fine.

* What is a disadvantage of implicit (automatic) signal monitors?

Poor performance.

* What is a coroutine monitor?

A coroutine with implicit mutual exclusion on calls to specified member routines.

* What is a Java monitor?

- A monitor with a single implicit condition variable.
- Internal scheduling is no-priority nonblocking.
- Barging can occur.

# Direct communication

* What is a task?

A class with a distinguished member (main) that has its own execution state.

* How is a task similar to a monitor?

Tasks provide mutual exclusion and synchronization so only one thread is active
in that object.

* What does _Else do in uC++?

It is executed if there is no caller waiting on one of the functions specified
in the previous _Accept statements.

* What happens after a task's destructor is called?

The task behaves like a monitor.

* How can an internal buffer increase concurrency?

One can process and put multiple results into the buffer concurrently, rather
than running the process inside the mutex member itself.

* What are some issues with the internal buffer method to increase concurrency?

- Unless the average time for production and consumption is almost equal, the
  buffer is either always full or empty.
- Since tasks are monitor-like, no calls can occur while the server is working.

* What is a worker task?

An additional (private) task that is used to offload the work to another thread.

* What is an administrator?

A server managing multiple clients and worker tasks.
Does little real work, just manages.

* Why does the administrator not make calls to other tasks?

Because those calls may block the administrator, but we want the administrator
to always keep accepting calls.

* How does an administrator work?

Maintains a list of work to pass to worker tasks.

* What are some typical worker types?

- Timer
- Notifier
- Simple worker
- Complex worker
- Courier

* What is a timer worker?

A task that prompts the administrator at specified time intervals.

* What is a notifier worker?

A task that performs a potentially blocking wait for an external event.

* What is a simple worker?

A task that does work and returns the result to the administrator.

* What is a complex worker?

A task that does work and interacts directly with client of the work.

* What is a courier worker?

A task that performs a potentially blocking call on behalf of the administrator.

* How can clients increase concurrency with servers?

Perform server calls asynchronously.

* Does uC++ provide asynchronous calls out of the box?

No.

* How do tickets work w.r.t asynchronous calls?

- Tickets are matched with results and given to the client.
- Clients retrieve their result by passing the ticket to the server.

* What is a disadvantage of using tickets for managing asynchronous calls?

Protocols are error-prone because the caller may not obey the protocol.

* How do call-back routines work w.r.t asynchronous calls?

- A routine is passed to the server on the initial call.
- Routine is called when the result is ready.

* What is the advantage of using call-back routines for managing asynchronous calls?

The server does not need to store any results, it can drop it off immediately.

* What are futures?

A future provides asynchronous communcation but without an explicit protocol.

* What is the difference between Future_ESM and Future_ISM?

Future_ESM must be explicitly deleted.
Future_ISM has garbage collection.

* What is the _Select clause w.r.t futures?

The _Select statement waits for one or more heterogeneous futures based on the
logical clause passed inside it.

The selector is blocked until future.available() is true.

* What is the difference between future() and _Select(future)?

future() gets the value, which also means that it can throw an exception.

* What is something important to consider when you have e.g. _Select(f1 || f2)?

When the statement finishes, you don't know which future is available so you
have to check.

# 10 Optimization

* Why is optimization useful or necessary?

To conserve resources and for good performance.

* What are the 3 general forms of optimization?

1. Reordering.
2. Eliding.
3. Replication.

* What is reordering w.r.t optimization?

Data and code are reordered to increase performance in certain contexts.

* What is eliding w.r.t optimization?

Removal of unnecessary data, data accesses, and computation.

* What is replication w.r.t optimization?

Processors, memory, data, code are duplicated because of limitations in
processing or communication.

* How can the compile/hardware optimize sequential programs?

- Reorder disjoint operations.
- Elide unnecessary operations.
- Execute in parallel if multiple functional-minutes.

* How are caches loaded?

In cache lines of 32/64/128 bytes.

* Why is the necessary to eagerly move reads up the memory hierarchy?

So that the next read will be cached.

* Why is it advantageous to lazily move writes down the memory hierarchy?

Because writing is expensive so we don't want to block on it very often.

* What is cache coherence?

A hardware protocol for ensuring update of duplicate data.

* What are the advantages and drawbacks of eager cache consistency?

+ Data changes appear instantaneously.
- Slow and expensive.

* What are the advantages and drawbacks of lazy cache consistency?

+ Faster
- Concurrent programs can read stale data.

* What is cache thrashing?

When threads continuously read/write the same memory locations, causing the
excessive cache updates.

* What is false sharing?

Since cache lines can contain multiple variables, cache thrashing can through
different variables.

* How can sequential optimizations cause problems for concurrent programs?

Concurrent sections accessing shared variables can become corrupted by
sequential optimizations.

* How can reordering optimizations cause problems for concurrent programs?

- Flag variable reads might be done in a different order than intended.
- Locks can have their function calls be reordered.

* How can eliding optimizations cause problems for concurrent programs?

- Flag variables can be copied to a register, and thus never being updated.
- "Meaningless" sleep statements may be removed causing delays to be skipped.

* How can replication optimizations cause problems for concurrent programs?

- Modern processors execute multiple instructions in parallel.
- Sometimes the order of instructions matters however.
- e.g. A variable cannot be visible before being initialized.

* What are the sources of all optimization problems?

Races on shared variables.

* How can you prevent optimization problems?

Protect all shared data with locks.

* What is a race free program?

No variables in the program has races.

* Is a race free program free of all races?

No. There can still be races internal to locks.

* What are the two approaches lock programmers can take to eliminate races in locks?

1. Ad hoc
2. Formal

* What is the ad hoc approach to dealing with races as a lock programmer?

Augment all data races with pragmas to restrict compiler and hardware
optimizations.

* What are the advantages and disadvantages of the ad hoc approach to dealing with races?

+ Optimal
- Not portable

* What is the formal approach to dealing with races as a lock programmer?

Language has a memory model and mechanisms to define races in programs.

* What are the advantages and disadvantages of the formal approach to dealing with races?

+ Portable
- Not optimal

* What utilities does C++ have to deal with data races?

The volatile qualifier, which forces variable updates to occur quickly.
The atomic qualifier, which prevents eliding and disjoint reordering.

# 11 Other approaches

* What is a lock free data structure?

A data structure where operations that are critical sections can be performed
without a lock.

* What does "wait free" mean?

Operations also guarantees progress.

* How can compare and assign be used to implement a lock-free stack?

void Stack::push( Node &n ) {
  for ( ;; ) {
    n.next = top;
    if ( CAA( top, n.next, &n ) ) break;
  }
}

Node *Stack::pop() {
  Node *t;
  for ( ;; ) {
    t = top;
    if ( t == NULL ) break;
    // busy wait
    // copy current top // empty list ?
    if ( CAA( top, t, t->next ) ) break; // attempt to update top nod
  }
  return t;
}

* What is the ABA problem w.r.t lock free stack?

top -> x -> y -> z

1. pop() called, x is read and y is chosen as the next top of the stack.
2. Preemption!
3. x and y are both popped, x is pushed back.

top -> x -> z

4. Unpreemption!
5. Compare and assign sees that x is still at the top.

top -> y -> ???

Stack is now corrupted.

* What is a hardware fix for the ABA problem?

Use a double-wide compare and assign instruction.
Pass in both the pointer and a ticket number.
The ticket number would change (and fail the comparison) if the stack has been
modified.

* What do the LL and SC instruction do in MIPS?

LL: Loads a value from memory to a register, and sets a hardware reservation
on the memory location.

SC: Stores a new value back to the memory location. This store is conditional
and only occurs if no interrupt, exception or write has occurred at the 
LL reservation.

* What happens when the SC instruction fails?

The value at the memory location it tried to write at is set to 0.

* What does the language "Ada 95" offer for concurrency?

- The "when" clause, which is external scheduling similar to the _Accept statement.
- No internal scheduling.
- Instead, the "requeue" statement allows one to make a blocking call to
  another mutex member of the object.

* What does SR and concurrent C++ offer for concurrency?

- External scheduling with an accept statement.
- In addition, it has "when" and "by" clauses to let the accept statement run
  depending on a variable or condition.

* What is the equivalent of Task in Java?

Thread class.

* Why does Java need the start function to start its threads?

Since there can be inheritance, there is no way to start the thread in the
constructor.

* What does Go offer for concurrency?

- Non-object-oriented, light-weight threads called goroutines.
- Started with the go statement.
- No direct communication with goroutines.
- Channels (bounded buffers) are used to communicate.

* What does C++11 offer for concurrency?

- There is a thread object.
- Any callable entity can be started by a thread.
- Parameters passed in via the variadic template feature.

- There are also mutex and condition locks.
- Scheduling no-priority nonblocking. Which means that barging is possible.

- There are also futures and atomic types and operations.

* When do C++11 thread's start?

At the point of declaration.

* What do you have to be careful about when using C++11 threads?

Dangling pointers to local variables.

* What is an error in C++11's threading model?

Deallocating the thread object before calling join() or detach().

* What is the actor concurrency model?

- An administrator accepts messages that a group of workers will process.
- Communication is done through an untyped queue of messages.

* What does Linda offer for concurrency?

- There is a tuple space that is known to all threads.
- Threads communicate by adding, reading, and removing tuples from the space.
- read( ... ) reads a tuple that matches the parameters. Blocking call.
- in( ... ) is like read( ... ) but removes the tuple.
- out( ... ) writes a tuple to the space.

* What does OpenMP offer for concurrency?

- Uses pragma statements to do concurrency.
- There are fork/join statements to create parallel threads.
- Offers COFOR COEND features via #pragma omp parallel for

* What is an Executor in Java?

A server with one or more worker tasks.
You can submit() work to the executor.