Concept of Programming Language Chapter 13

Assignment from Mr.Tri Djoko Wahjono

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

11. Give three characteristics of thread that distinguish them from subprograms
– A task may be implicitly started, whereas a subprogram must be explicitly called.
– When a program unit invokes a task, in some cases it need not wait for the task to complete execution before continuing its own.
– When execution of task is completed, control may or may not return to the unit that started that execution

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.

13. Define task ,synchronization, competition and cooperation synchronization, liveness ,race condition and deadlock.
– Task : unit of a program, similar to a subprogram that can be in concurrent execution with other units of same program
Synchronization : a mechanism that controls the order in which task execute.
Competition Synchronization : Synchronization between two task when both require a single resource that can’t be used together.
Cooperation Synchronization : Synchronization in which a task must wait for other task to finish before it can begin or continue its execution
Liveness : condition if some event, like program completion is supposed to occur, it will occur eventually. That is, progress is actually made.
Race Condition : When two or more tasks are racing to use the shared resource and the behavior of the program depends on which task arrives first.
Deadlock : a condition when a program is trapped inside an endless loop due to error between task synchronization.

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.

15. Describe the five different states a task can be.
– New = A task is in the new state when it has been created but yet to start its execution
– Ready = A task that is ready to run but is not currently running. Either it has not been run yet or it had run previously but got blocked.
– Running = A task that is currently being executed.
– Blocked = a task that has been running ,but the execution was interrupted by an event.
– Dead = A task that is no longer active in any sense, either when the execution is completed or killed by the program

16. What is task descriptor ?
– A data structure that stores all of the relevant information about the execution state of a task.

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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s