CMSI 6998: Midterm Answers

Control flow mechanisms include sequential, conditional, iterative, nondeterministic, and disruptive. Concurrent is not a control flow. Control flow is what happens within a line of execution. Concurrency is multiple lines of execution.
In Java, a thread needing to wait for several other threads to finish before it can proceed past a certain point should use a CountDownLatch.
Things that are task-like, or active, include Go Goroutines, Java Threads, and Erlang Processes. These all run code. Semaphores and protected objects are passive, data-like objects. Yes, an Ada protected object can have entries, but they are not tasks. The code inside the protected object is not executed as a separate task but rather runs on the same “thread” as the caller.
The ERCW PRAM makes no sense, or is at least of no practical use. Multiple readers are traditionally fine as long as you have a way to ensure that writes are exclusive. Making the reader exclusive is just weird. Might as well just go all out with a CRCW.
Concurrency is more about independence than about anything else.
Concurrency is the general idea of dividing up a computation into independent tasks. Parallelism is the specific implementation of concurrency where those tasks are executed simultaneously on multiple processors, and is but one kind of concurrency (therefore concurrency is not parallelism), the others being asynchronous calls, coroutines, distribution, and shared memory threading. There may be others. If you first look at a system, and identify the tasks that can be executed concurrently, you may then be able to enable parallelism.
Two lines with 15 and 20 instructions have $$ \frac{(15 + 20)!}{15! \cdot 20!} = 3247943160 $$ possible interleavings.
Livelocked processes never get to their critical section, but they keep running and trying to get in. A starved process not only doesn’t get to its critical section, but it might not even get to run at all.
In Java, every object has a monitor, so a chopstick in the Dining Philosophers problem is represented as a plain old object. There’s no need to create a separate object.
Since a signal is a synchronization device that is up or down and carries no intrinsic data, the Go unbuffered channel with an empty struct is perfect: we can use it to signal between goroutines without needing to pass any actual data.
The general term for that which executes a bunch of threads in Java is an executor service. There are many kinds of executor services, one of which is a thread pool, but the general term is that of an executor service.
The analog of a JavaScript promise in Java is a future.
An Ada task must wait to execute until each of its children has activated, and can only terminate when its dependencies have terminated. Since a task has to complete before it terminates, it is also correct to say a task cannot terminate until its children have completed, but that is a much weaker statement. True, but weaker.
Devices for barrier synchronization include barrier objects, countdown latches, and exchangers. Condition synchronization is enabled by condition variables. Devices for resource synchronization, that is, devices designed explicitly for mutual exclusion are: mutexes, locks, semaphores, and software transactional memory.
The main concern of shared memory concurrency is the possibility of race conditions.
We covered several theoretical message passing styles, among them the redezvous, relays, buffers, mailboxes (as well as callbacks and receipts). We also saw that message passing had quite a few communication styles, including balking calls, the others being (async calls, timeouts, and full wait calls).
The Ada selective wait, by definition has exactly three kinds of alternatives: accepts, delay, and terminate. Note that the ”else” part is not an alternative, but part of the larger syntactic structure. Guards are not alternatives either; they guard alternatives.

If you had an atomic testAndSet instruction, you can implement mutual exclusion, if every thread does the following:

loop
  while Test_And_Set (Lock) loop
    null;
  end loop;
  Critical_Section;
  Lock := False;
  Non_Critical_Section;
end loop;

Condition synchronization is necessary then getting a resource lock is not enough, but a critical section must be guarded by whether or not some arbitrary boolean condition holds. The classic example is that you cannot write to a full buffer or read from an empty one. Getting the lock just to find out you can’t proceed would be annoying if you had to give it up and try again later if the condition was false. Condition synchronization helps out here a lot, allowing threads to wait ”inside” the monitor.
The body for:

   protected type Transient_Broadcast_Signal is
      entry Wait;
      procedure Send;
   private
      Signalled: Boolean := False;
   end Transient_Broadcast_Signal;

protected body Transient_Signal is
   entry Wait when Signalled is
   begin
      if Wait'Count = 0 then
         Signalled := False;
      end if;
   end Wait;
   procedure Send is
   begin
      if Wait'Count > 0 then
         Signalled := True;
      end if;
   end Send;
end Transient_Signal;