Concepts of Programming Languages Assignment - Chapter 13

Review Questions

1. What are the three possible levels of concurrency in programs?
Concurrency in software execution can occur at four different levels: instruction level (executing two or more machine instructions simultaneously), statement level (executing two or more high-level language statements simultaneously), unit level (executing two or more subprogram units simultaneously), and program level (executing two or more programs simultaneously).

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. Perhaps the most widely used
SIMD machines are a category of machines called vector processors. They 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. Originally, the kinds of programs that could most benefit from this architecture were in scientific computation, an area of computing that is often the target of multiprocessor machines. However, SIMD processors are now used for a variety of application areas, among them graphics and video processing. Until recently, most supercomputers were vector processors.

3. Describe the logical architecture of an MIMD computer.
Computers that have multiple processors that operate independently but whose operations can be synchronized are called Multiple-Instruction Multiple- Data (MIMD) computers. 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. Even distributed MIMD machines require synchronization to operate together on single programs. MIMD computers, which are more general than SIMD computers, support unit-level concurrency. The primary focus of this chapter is on language design for shared memory MIMD computers, which are often called multiprocessors.

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

5. What level of program concurrency is best supported by SIMD computers?
Unit-level concurrency

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. Originally, the kinds of programs that could most benefit from this architecture were in scientific computation, an area of computing that is often the target of multiprocessor machines.

7. What is the difference between physical and logical concurrency?
There are two distinct categories of concurrent unit control. The most natural category of concurrency is that in which, assuming that more than one processor is available, several program units from the same program literally execute simultaneously. This is physical concurrency. A slight relaxation of this concept of concurrency allows the programmer and the application software to assume that there are multiple processors providing actual concurrency, when in fact the actual execution of programs is taking place in interleaved fashion on a single processor. This is logical concurrency.

8. what is the work of a scheduler?
A run-time system program called a scheduler manages the sharing of processors among the tasks.

34. What does the Java sleep method do?
The sleep method has a single parameter, which is the integer number of milliseconds that the caller of sleep wants the thread to be blocked. After the specified number of milliseconds has passed, the thread will be put in the task-ready queue. Because there is no way to know how long a thread will be in the task-ready queue before it runs, the parameter to sleep is the minimum amount of time the thread will not be in execution. The sleep method can throw an InterruptedException, which must be handled in the method that calls sleep.

35. what does the Java yield method do?
The yield method, which takes no parameters, is a request from the running thread to surrender the processor voluntarily. The thread is put immediately in the task-ready queue, making it ready to run. The scheduler then chooses the highest-priority thread from the task-ready queue. If there are no other ready threads with priority higher than the one that just yielded the processor, it may also be the next thread to get the processor.

36. what does the Java join method do?
The join method is used to force a method to delay its execution until the run method of another thread has completed its execution. join is used when the processing of a method cannot continue until the work of the other thread is complete.

37. What does the Java interrupt method do?
The interrupt method is one way to communicate to a thread that it should stop. This method does not stop the thread; rather, it sends the thread a message that actually just sets a bit in the thread object, which can be checked by the thread. The bit is checked with the predicate method, isInterrupted. This is not a complete solution, because the thread one is attempting to interrupt may be sleeping or waiting at the time the interrupt method is called, which means that it will not be checking to see if it has been interrupted. For these situations, the interrupt method also throws an exception, InterruptedException, which also causes the thread to awaken (from sleeping or waiting). So, a thread can periodically check to see whether it has been interrupted and if so, whether it can terminate. The thread cannot miss the interrupt, because if it was asleep or waiting when the interrupt occurred, it
will be awakened by the interrupt.

42. What kind of Java object is a monitor?
In Java, a monitor can be implemented in a class designed as an abstract data type, with the shared data being the type. Accesses to objects of the class are controlled by adding the synchronized modifier to the access methods.

47. How are explicit locks supported in Java?
Java 5.0 introduced explicit locks as an alternative to synchronized method and blocks, which provide implicit locks. The Lock interface declares the lock, unlock, and tryLock methods. The predefined ReentrantLock class implements the Lock interface. To lock a block of code, the following idiom can be used:
Lock lock = new ReentrantLock();
. . .
Lock.lock();
try {
// The code that accesses the shared data
} finally {
Lock.unlock();
}

48. What kinds of methods can run in a C# thread?
Rather than just methods named run, as in Java, any C# method can run in its own thread.

55. What is Concurrent ML?
Concurrent ML (CML) is an extension to ML that includes a form of threads and a form of synchronous message passing to support concurrency. The language is completely described in Reppy (1999).

59. Who developed the monitor concept?
The monitor concept is developed and its implementation in Concurrent Pascal is described by Brinch Hansen (1977)

Problem Set

1 . Explain why a race condition can create problems for  a system.
a race condition creates problem because when a race condition happens two or more tasks are racing to use the shared resource and the behavior of the program depends on which task arrives first (and wins the race).

2. What are the different ways to handle deadlock?
When deadlock occurs, assuming that only two program units are causing the deadlock, one of the involved program units should be gracefully terminated, thereby allowed the other to continue.

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?
The main problem with busy waiting is that machine cycles are wasted in the process.

4. In the producer-consumer example of Section 13.3, suppose that we incorrectly replaced the release(access) in the consumer process with wait(access). What woud be the result of this error on execution of the system?
Deadlock would occur if the release(access) were replaced by a wait(access) in the consumer process, because instead of relinquishing access control, the consumer would wait for control that it already had.