CSCI305.github.io

CSCI 305 Homework 6

Due Date: April 27, 2018 @ Beginning of Class

Name:                                                                                        

Cost Models

1. For each of the following, give a formula for computing the address to use for the array reference. Assume that the array A is allocated as single block at address base, and let size be the size of an individual array element. (2 points)

• The element A[i], where 0 ≤ i ≤ n

A[i] -> base + i*size
  
  
• The element A[i][j][k], where 0 ≤ i ≤ m, 0 ≤ j < n, and 0 ≤ k < p, and where the array is allocated in column-major order.
  
  A[i][j][k] -> base + (i * p * size) + (j * (m + 1) * p * size) + (k * size)
  

Concurrency

(1) What are the three possible levels of concurrency in programs? (3 points)

• Machine instruction level
• High-level language statement level
• Unit level
  

(2) Describe the logical architecture of an MIMD computer. (3 points)

• MIMD - Multiple Instruction Multiple Data
  • Machine with multiple processors each capable of executing their own instructurion stream.
  • Memory
    • Distributed - Each processor has its own memory
    • Shared - Single memory shared between the processors
      

(3) Define the following terms: (3 points)

• synchronization:
  A mechanism that controls the order in which tasks execute.
  
• deadlock:
  A condition that occurs when two tasks gain control of shared resources and are each awaiting the other to reliquish control of their resource. This condition causes the loss of liveness for both tasks and guarantees that the program will never complete execution correctly.
  
• race condition:
  When two or more tasks are racing to use a shared resource and the behavior of the program is dependent on which task arrives first.
  

(4) What is the best action a system can take when deadlock is detected? (2 points)
Resource preemption: resources allocated to various processes may be successively preempted and allocated to other processes until the deadlock is broken.

(5) How are explicit locks supported in Java? (2 points)
Explicit locks are provided in Java via the Lock interface and its realizations. These provide the methods lock() and unlock(). Specifically one can use either of the ReentrantLock or ReentrantReadWriteLock. Once a lock has been instantiated, calling lock() on that locks the resource until unlock() is called.