General Requirements

These instructions require you use Java. All code should be well-commented, in a professional style, with ap- propriate variables names, indenting, etc. Your code must be clear and readable. Marks will be very generously deducted for bad style or lack of clarity.

There must be no data races. This means all shared variable access must be properly protected by synchro- nization:  any memory location that is written by one thread and read or written by another should only be accessed within a synchronized block (protected by the same lock), or marked as volatile. At the same time, avoid unnecessary use of synchronization or use of volatile. Unless otherwise specified, your programs should aim to be efficient, and exhibit high parallelism, maximizing the ability of threads to execute concurrently. Please stick closely to the described input and output formats.

Your assignment submission must include a separate text file, declaration.txt stating “This assignment solution represents my own efforts, and was designed and written entirely by me”. Assignments without this declaration, or for which this assertion is found to be untrue are not accepted. In the latter case it will also be referred to the academic integrity office.

Questions

1. In the Tetris video game different shapes (“tetrominoes”) descend within an n × 10 grid. Your task here   20 is to build a multi-threaded simulation inspired by that core behaviour. Every k > 2 time-units (assume       a logical, discrete time), a new, random tetromino is instantiated at the top of the grid.  Every time       step all tetrominoes attempt to shift down by one (or more, see below) grid cell(s). Between downward       movements a tetromino may also shift left or right by a grid cell, or rotate clockwise or counter-clockwise       by 90O . The set of tetrominoes in their starting orientation and their rotation points is shown below.

Figure 1: Tetrominoes.  The “X” indicates the rotation point.  Note that rotating the square has no practical effect.

Every tetromino should be controlled by a different thread, which is responsible for advancing the tetro- mino downward, as well as for performing any transformations of the tetromino (a discrete rotation (c- wise or cc-wise) or shift (left or right)). The decision to do a transformation is based on a random value (p% of the time), while the choice between the 4 possible transformations is uniform.  If the selected transformation would put the tetromino outside of the grid it is not performed.

Downward movement happens each time-step after any transformation.  A thread chooses a random integer in [1,d] (reduced if it would take it below the bottom row of the grid) and attempts to move it down that many steps (note that in the case of moving more than 1 unit down it must pass through each grid cell between). Once any cell of a tetromino reaches the bottom row of the grid the tetromino should be removed in the next time step.

Tetrominoes should move/transform in a discrete, atomic fashion relative to other tetrominoes and must

never overlap.  To enforce this, associate a lock with each grid cell.  In order to move or transform a tetromino a thread must thus acquire all locks associated with its current position, as well as its intended position (and in the case of moving down more than one unit, including any intermediate positions the tetromino would occupy), and only perform the movement or translation if it would not overlap, partially or fully, with another tetromino. The grid cell locks must be acquired individually and enforce blocking behaviour: an attempt to acquire a lock must prevent the thread from all other actions until it is actually acquired. All tetrominoes should eventually reach the bottom of the grid (and then disappear).

After each thread has done its work for the time unit, and before any work is done for the next time unit, the board-state should be printed out in ASCII on the console, using single character symbols to distinguish individual tetrominoes:

# # # # # # # # # # # # #

a

a

a

a    cc

cc

bb

bb

#

#

#

#

#

#

#

#

#

#

#

#

#

############

Your program should be called q1.java, and take arguments:

java  q1  n  k  p  d  m

Where n > 10 is the grid height, k > 2 is the periodicity of introducing new tetrominoes, 0.0 s p s 1.0 is the probability of doing a transformation prior to moving down, d > 1 is the maximum downward movement step size, and m  >  1 is the total number of tetrominoes that should be created.  Once all tetrominoes have reached the bottom and disappeared the simulation should end.

Your program should not deadlock, and all tetrominoes should eventually reach the bottom. In a separate file, provide a brief and high-level textual textual description of how you are ensuring that is true.

2. In most of the class examples we have assumed threads have unique numerical ids. If this is not the case   10

then unique ids within a reasonably compact range can be created algorithmically. For this you will need to look at Exercise 2.9 and 2.10 within the text (2nd edition), or Exercise 16 and 17 (1st revised edition).

The textbook shows code for a simple Bouncer, which can be assembled into a renaming network. This allows you to renumber threads ids to within a bounded range for a given number of threads.

Develop a simulation program that constructs exactly one such renaming network, but which can be used repeatedly to rename (renumber) threads. Call your program q2; it takes two arguments:

java  q2  p  n

Create p > 1 threads, your renaming network, and an integer array A. Each thread should have an integer id value, initialized to -1. The array A should be of a fixed size, and as small as you can make it while still holding any id value that may be assigned by your renaming network.

Then perform n  >  1 rounds of renaming, each round giving each thread a new id according to the renaming network. As soon as a thread knows its new id in a round, it (atomically) increments the count at A[id], sleeps for a random time from 0 to 10ms, and then tries to re-enter the network for the next round.

You may only construct one splitter network, and exactly p threads. In this question you may only use volatile data and the java.util.concurrent.atomic. * classes, as well as basic Thread methods, such as start,  join,  sleep,  currentThread,  yield, and ThreadLocal data if convenient. Do not use other forms of synchronization provided by Java.

Your design should guarantee that every round every thread receives a unique id value. Verify this after every thread has completed n renaming rounds, by (sequentially) checking that every value in the A array is no more than n and the entire array sums to pn.

In a separate file, provide a brief and high-level textual textual description of your parallelization strategy.

What to hand in

Submit your declaration and assignment files to MyCourses. Note that clock accuracy varies, and late assign- ments will not be accepted without a medical note: do not wait until the last minute. Assignments must be submitted on the due date before midnight.

Where possible hand in only source code files containing code you write. Do not submit compiled binaries or .class files. For any written answer questions, submit either an ASCII text document or a .pdf file. Avoid .doc or .docx files. Images (plots or scans) are acceptable in all common graphic file formats.