Chapter 13

Concept of Programming Languages by Robert W. Sebesta Answer

Review Questions

1. What are the three possible levels of concurrency in programs ?

Instruction level, Statement level, and Unit level

2. Describe the logical architecture of an SIMD computer.

In an SIMD computer, each processor has its own local memory. One processor controls the operation of the other processors. Because all of the processors, except the controller, execute the same instruction at the same time, no synchronization is required in the software.

3. Describe the logical architecture of an MIMD computer.

Each processor in an MIMD computer executes its own instruction stream. MIMD computers can appear in two distinct configurations: distributed and shared memory systems. The distributed MIMD machines, in which each processor has its own memory, can be either built in a single chassis or distributed, perhaps over a large area. The shared-memory MIMD machines obviously must provide some means of synchronization to
prevent memory access clashes.

4. What level of program concurrency is best supported by SIMD computers ?

Instruction concurrency level

5. What level of program concurrency is best supported by MIMD computers ?

Unit concurrency level.

6. Describe the logical architecture of a vector processor.

Vector processor have groups of registers that store the operands of a vector operation in which
the same instruction is executed on the whole group of operands simultaneously.

7. What is the difference between physical and logical concurrency ?

Physical concurrency is when it is assumed that if more than one processor is available, several program units from the same program literally execute simultaneously. Logical concurrency is assuming multiple processors can execute simultaneously while the actual execution is taking place in a single processor.

8. What is the work of a scheduler ?

Managing the share of processors among tasks.

9. Give some examples of languages which can be used for synchronization.

Ada 95, Java, C#, F#, Python and Ruby

10. When is a task in a blocked state ?

When its execution is interrupted by one of several different events

12. What is a heavyweight task ? What is a lightweight task?

Heavyweight task is a task that executes in its own address space. Lightweight tasks are tasks run in the same address space.

14. What kind of tasks do not require any kind of synchronization ?

Tasks that are not depending on the outcome or output from other tasks.

17. In the context of language support for concurrency, what is a guard ?

Linguistic device that allows the guarded code to be executed only when a specified condition is true.

Problem Set

1. Explain clearly why a race condition can create problems for a system .

A race condition allows different outputs to come out of the synchronization, as stated in the book, for example task A which increments an integer and task B that multiplies an integer with 2.
Say we have integer A with value of 3. If both tasks are run in race condition, its value could be either 7 (when B runs and finishes before A starts) or 8 (vice versa) or, either 4 or 6 (if they started at the same time, 4 when A finishes later and 6 when B finishes the last. ). Without proper synchronization on timing, the output can vary. Thus this makes the program unreliable.

2. What are the different ways to handle deadlock ?

One of the ways is to design algorithm where tasks that can cause deadlock to not to run together. Or, to allow them to execute at the same time but with an exception if a deadlock happens, the program will either reset its status to the time when deadlock has not occurred or to break forcefully from the loop and continues execution.

3. Busy waiting is a method whereby a task waits for a given event by continuously checking for that event to occur. What is the main problem with this approach ?

A continuous check might mean a deadlock for a task, where it does something that does not has a direct impact on the program unless the specified event happens. It does consume extra processor capability. A better way to do this might be executing the same task when an event occurs, instead of running it first and make it waiting and continuously wasting CPU capability.