Assignment

A2source.java 

/ Source code for semaphore class:

class Semaphore

{

privateint value;

public Semaphore(int value)

{

this.value = value;

}

public Semaphore()

{

this(0);

}

public synchronized void Wait()

{

while (this.value<= 0)

{

try

{

wait();

}

catch(InterruptedException e)

{

System.out.println (“Semaphore::Wait() – caught InterruptedException: ” + e.getMessage() );

e.printStackTrace();

}

}

this.value–;

}

public synchronized void Signal()

{

++this.value;

notify();

}

public synchronized void P()

{

this.Wait();

}

public synchronized void V()

{

this.Signal();

}

}

// Source code for character stack:

 

// Our own exceptions

importCharStackExceptions.*;

classCharStack

{

/*

* Some class constants.

*/

public static final int MIN_SIZE = 7; // Minimum stack size

public static final int MAX_SIZE = 32; // # of letters in the English alphabet + 6

public static final int DEFAULT_SIZE = 10; // Default stack size

/*

* Class variables

*/

private static intiSize = DEFAULT_SIZE;

private static intiTop = 3; // stack[0:9] with four defined values

private static char aCharStack[] = new char[]  {�a�, �b�, �c�, �d�, �$�, �$�,�$�,�$�,�$�,�$�};

// Default constructor

publicCharStack()

{

// Just do nothing

}

// Constructor with supplied size

publicCharStack(intpiSize) throws CharStackInvalidSizeException

{

If (piSize< MIN_SIZE || piSize> MAX_SIZE)

throw new CharStackInvalidSizeException(piSize);

if (piSize != DEFAULT_SIZE)

{

this.aCharStack = new char[piSize];

// Fill in with letters of the alphabet and keep

// 6 free blocks

for(int i = 0; i <piSize – 6; i++)

this.aCharStack[i] = (char)(�a� + i);

for (int i = 1; i <= 6; i++)

this.aCharStack[piSize – i] = �$�;

this.iTop = piSize – 7;

this.iSize = piSize;

}

}

/*

* Picks a value from the top without modifying the stack

*/

public static char pick() throws CharStackEmptyException

{

If (iTop == -1)

throw new CharStackEmptyException();

returnaCharStack[iTop];

}

/*

* Returns arbitrary value from the stack array

*/

public char getAt(intpiPosition) throws CharStackInvalidAceessException

{

if (piPosition< 0 || piPosition>= iSize)

throw new CharStackInvalidAceessException();

returnthis.aCharStack[piPosition];

}

/*

* Standard push operation

*/

public static void push(char pcChar) throws CharStackFullException

{

if (iTop == iSize -1)

throw new CharStackFullException();

aCharStack[++iTop] = pcChar;

}

/*

* Standard pop operation

*/

public static char pop() throws CharStackEmptyException

{

if (iTop == -1)

throw new CharStackEmptyException();

charcChar = aCharStack[iTop];

aCharStack[iTop–] = �$�; // Leave prev. value undefined

returncChar;

}

/* Getters */

publicintgetSize()

{

returnthis.iSize;

}

publicintgetTop()

{

returnthis.iTop;

}

}

// Source code for stack manager:

public class StackManager

{

// The Stack

private static CharStack stack = new CharStack();

private static final int NUM_ACQREL = 4; // Number of Producer/Consumer threads

private static final int NUM_PROBERS = 1; // Number of threads dumping stack

private static intiThreadSteps = 3; // Number of steps they take

// Semaphore declarations. Insert your code in the following:

//…

//…

// The main()

public static void main(String[] argv)

{

// Some initial stats…

try

{

System.out.println(“Main thread starts executing.”);

System.out.println(“Initial value of top = ” + stack.getTop() + “.”);

System.out.println(“Initial value of stack top = ” + stack.pick() + “.”);

System.out.println(“Main thread will now fork several threads.”);

}

catch(CharStackEmptyException e)

{

System.out.println(“Caught exception: StackCharEmptyException”);

System.out.println(“Message : ” + e.getMessage());

System.out.println(“Stack Trace : “);

e.printStackTrace();

}

/*

* The birth of threads

*/

Consumer ab1 = new Consumer();

Consumer ab2 = new Consumer();

System.out.println (“Two Consumer threads have been created.”);

Producer rb1 = new Producer();

Producer rb2 = new Producer();

System.out.println (“Two Producer threads have been created.”);

CharStackProbercsp = new CharStackProber();

System.out.println (“One CharStackProber thread has been created.”);

/*

* start executing

*/

ab1.start();

rb1.start();

ab2.start();

rb2.start();

csp.start();

/*

* Wait by here for all forked threads to die

*/

try

{

ab1.join();

ab2.join();

rb1.join();

rb2.join();

csp.join();

// Some final stats after all the child threads terminated…

System.out.println(“System terminates normally.”);

System.out.println(“Final value of top = ” + stack.getTop() + “.”);

System.out.println(“Final value of stack top = ” + stack.pick() + “.”);

System.out.println(“Final value of stack top-1 = ” + stack.getAt(stack.getTop() – 1) + “.”);

System.out.println(“Stack access count = ” + stack.getAccessCounter());

}

catch(InterruptedException e)

{

System.out.println(“Caught InterruptedException: ” + e.getMessage());

System.exit(1);

}

catch(Exception e)

{

System.out.println(“Caught exception: ” + e.getClass().getName());

System.out.println(“Message : ” + e.getMessage());

System.out.println(“Stack Trace : “);

e.printStackTrace();

}

} // main()

/*

* Inner Consumer thread class

*/

static class Consumer extends BaseThread

{

private char copy; // A copy of a block returned by pop()

public void run()

{

System.out.println (“Consumer thread [TID=” + this.iTID + “] starts executing.”);

for (int i = 0; i <StackManager.iThreadSteps; i++)  {

// Insert your code in the following:

// …

// …

System.out.println(“Consumer thread [TID=” + this.iTID + “] pops character =” + this.copy);

}

System.out.println (“Consumer thread [TID=” + this.iTID + “] terminates.”);

}

} // class Consumer

/*

* Inner class Producer

*/

static class Producer extends BaseThread

{

private char block; // block to be returned

public void run()

{

System.out.println (“Producer thread [TID=” + this.iTID + “] starts executing.”);

for (int i = 0; i <StackManager.iThreadSteps; i++)  {

// Insert your code in the following:

// …

//…

System.out.println(“Producer thread [TID=” + this.iTID + “] pushes character =” + this.block);

}

System.out.println(“Producer thread [TID=” + this.iTID + “] terminates.”);

}

} // class Producer

/*

* Inner class CharStackProber to dump stack contents

*/

static class CharStackProber extends BaseThread

{

public void run()

{

System.out.println(“CharStackProber thread [TID=” + this.iTID + “] starts executing.”);

for (int i = 0; i < 2 * StackManager.iThreadSteps; i++)

{

// Insert your code in the following. Note that the stack state must be

// printed in the required format.

// …

// …

}

}

} // class CharStackProber

} // class StackManager

classBaseThread extends Thread

{

/*

* Data members

*/

public static intiNextTID = 1; // Preserves value across all instances

protectedintiTID;

publicBaseThread()

{

this.iTID = iNextTID;

iNextTID++;

}

publicBaseThread(intpiTID)

{

this.iTID = piTID;

}

}

// Source code for the user defined exception classes:

packageCharStackExceptions;

public class CharStackEmptyException extends Exception

{

publicCharStackEmptyException()

{

super (“Char Stack is empty.”);

}

}

public class CharStackFullException extends Exception

{

publicCharStackFullException()

{

super (“Char Stack has reached its capacity of CharStack.MAX_SIZE.”);

}

}

public class CharStackInvalidSizeException extends Exception

{

publicCharStackInvalidSizeException()

{

super(“Invalid stack size specified.”);

}

publicCharStackInvalidSizeException (intpiStackSize)

{

super (“Invalid stack size specified: ” + piStackSize);

}

}

public class CharStackInvalidAceessException extends Exception

{

// Fill it up yourself

} 

Solution 

Task1 

public synchronized void Wait() {

this.value–;// TASK 1: 1/ I decremented the semaphore’s value at the

// beginning of the method instead of the end: because

// if it’s done at the end, a lot of threads could be

// waiting and the semaphore value would not be

// reflecting the number of waiting threads–it would

// only reflect the number of threads that acquired an

// authorization (and in fact would never go under

// zero).

if (this.value< 0) { // TASK 1: 2/ I changed while statement to an if

// statement to prevent a process from waiting

// again if more threads are on the waiting list

// (i.e. negative semaphore value). Now, all

// threads that entered this if statement are on

// “the waiting list” and can be picked to run

// if another thread emits a notify() for this

// object.

//

// 3/ I also changed “<= 0” to “< 0”, because 0

// means that it was 1 (i.e. semaphore is free)

// at the beginning of the function–the current

// process just made it 0 with the first

// decrement statement.

try {

wait(); // TASK 1: comment – any thread that reached this point

// is on the waiting list. If the while statement was

// kept it would have resulted in a deadlock–because

// any thread, upon notification, would run back into

// the while loop and wait() again since the semaphore’s

// value is still negative even if it was just

// incremented by the Signal() function.

} catch (InterruptedException e) {

System.out

.println(“Semaphore::Wait() – caught InterruptedException: ”

+ e.getMessage());

e.printStackTrace();

}

}

} 

Task2 

CharStackEmptyException.java

packageCharStackExceptions;

public class CharStackEmptyException extends Exception {

publicCharStackEmptyException() {

super(“Char Stack is empty.”);

}

} 

CharStackFullException.java

packageCharStackExceptions;

public class CharStackFullException extends Exception {

publicCharStackFullException() {

super(“Char Stack has reached its capacity of CharStack.MAX_SIZE.”);

}

}

 CharStackInvalidAceessException.java

packageCharStackExceptions;

public class CharStackInvalidAceessException extends Exception{

} 

CharStackInvalidSizeException.java

packageCharStackExceptions;

public class CharStackInvalidSizeException extends Exception {

publicCharStackInvalidSizeException() {

super(“Invalid stack size specified.”);

}

publicCharStackInvalidSizeException(intpiStackSize) {

super(“Invalid stack size specified: ” + piStackSize);

}

} 

BaseThread.java 

package Task2;

classBaseThread extends Thread {

/*

* Data members

*/

public static intiNextTID = 1; // Preserves value across all instances

protectedintiTID;

publicBaseThread() {

this.iTID = iNextTID;

iNextTID++;

}

publicBaseThread(intpiTID) {

this.iTID = piTID;

}

} 

CharStack.java 

package Task2;

//Our own exceptions

importCharStackExceptions.CharStackEmptyException;

importCharStackExceptions.CharStackFullException;

importCharStackExceptions.CharStackInvalidAceessException;

importCharStackExceptions.CharStackInvalidSizeException;

importCharStackExceptions.*;

classCharStack {

/*

* Some class constants.

*/

public static final int MIN_SIZE = 7; // Minimum stack size

public static final int MAX_SIZE = 32; // # of letters in the English

// alphabet + 6

public static final int DEFAULT_SIZE = 10; // Default stack size

/*

* Class variables

*/

private static intiSize = DEFAULT_SIZE;

private static intiTop = 3; // stack[0:9] with four defined values

private static char aCharStack[] = new char[] { ‘a’, ‘b’, ‘c’, ‘d’, ‘$’, ‘$’, ‘$’, ‘$’, ‘$’, ‘$’ };

// Default constructor

publicCharStack() {

// Just do nothing

}

// Constructor with supplied size

publicCharStack(intpiSize) throws CharStackInvalidSizeException {

if (piSize< MIN_SIZE || piSize> MAX_SIZE)

throw new CharStackInvalidSizeException(piSize);

if (piSize != DEFAULT_SIZE) {

this.aCharStack = new char[piSize];

// Fill in with letters of the alphabet and keep

// 6 free blocks

for (int i = 0; i <piSize – 6; i++)

this.aCharStack[i] = (char) (‘a’ + i);

for (int i = 1; i <= 6; i++)

this.aCharStack[piSize – i] = ‘$’;

this.iTop = piSize – 7;

this.iSize = piSize;

}

}

/*

* Picks a value from the top without modifying the stack

*/

public static char pick() throws CharStackEmptyException {

if (iTop == -1)

throw new CharStackEmptyException();

returnaCharStack[iTop];

}

/*

* Returns arbitrary value from the stack array

*/

public char getAt(intpiPosition) throws CharStackInvalidAceessException {

if (piPosition< 0 || piPosition>= iSize)

throw new CharStackInvalidAceessException();

returnthis.aCharStack[piPosition];

}

/*

* Standard push operation

*/

public static void push(char pcChar) throws CharStackFullException {

if (iTop == iSize – 1)

throw new CharStackFullException();

aCharStack[++iTop] = pcChar;

}

/*

* Standard pop operation

*/

public static char pop() throws CharStackEmptyException {

if (iTop == -1)

throw new CharStackEmptyException();

charcChar = aCharStack[iTop];

aCharStack[iTop–] = ‘$’; // Leave prev. value undefined

returncChar;

}

/* Getters */

publicintgetSize() {

returnthis.iSize;

}

publicintgetTop() {

returnthis.iTop;

}

} 

Semaphore.java 

package Task2;

class Semaphore {

privateint value;

public Semaphore(int value) {

this.value = value;

}

public Semaphore() {

this(0);

}

public synchronized void Wait() {

this.value–;// TASK 1: 1/ I decremented the semaphore’s value at the

// beginning of the method instead of the end: because

// if it’s done at the end, a lot of threads could be

// waiting and the semaphore value would not be

// reflecting the number of waiting threads–it would

// only reflect the number of threads that acquired an

// authorization (and in fact would never go under

// zero).

if (this.value< 0) { // TASK 1: 2/ I changed while statement to an if

// statement to prevent a process from waiting

// again if more threads are on the waiting list

// (i.e. negative semaphore value). Now, all

// threads that entered this if statement are on

// “the waiting list” and can be picked to run

// if another thread emits a notify() for this

// object.

//

// 3/ I also changed “<= 0” to “< 0”, because 0

// means that it was 1 (i.e. semaphore is free)

// at the beginning of the function–the current

// process just made it 0 with the first

// decrement statement.

try {

wait(); // TASK 1: comment – any thread that reached this point

// is on the waiting list. If the while statement was

// kept it would have resulted in a deadlock–because

// any thread, upon notification, would run back into

// the while loop and wait() again since the semaphore’s

// value is still negative even if it was just

// incremented by the Signal() function.

} catch (InterruptedException e) {

System.out.println(“Semaphore::Wait() – caught InterruptedException: ” + e.getMessage());

e.printStackTrace();

}

}

}

public synchronized void Signal() {

++this.value;

notify();

}

public synchronized void P() {

this.Wait();

}

public synchronized void V() {

this.Signal();

}

} 

StackManager.java 

package Task2;

importCharStackExceptions.CharStackEmptyException;

importCharStackExceptions.CharStackFullException;

importCharStackExceptions.CharStackInvalidAceessException;

importCharStackExceptions.*;

// Source code for stack manager:

public class StackManager {

// The Stack

private static CharStack stack = new CharStack();

private static final int NUM_ACQREL = 4; // Number of Producer/Consumer

// threads

private static final int NUM_PROBERS = 1; // Number of threads dumping stack

private static intiThreadSteps = 3; // Number of steps they take

// Semaphore declarations. Insert your code in the following:

// …

// …

// TASK 2:

private static Semaphore semaphore = new Semaphore(1);// 1 because only one

// thread can access

// the stack at a

// time

// The main()

public static void main(String[] argv) {

// Some initial stats…

try {

System.out.println(“Main thread starts executing.”);

System.out.println(“Initial value of top = ” + stack.getTop() + “.”);

System.out.println(“Initial value of stack top = ” + stack.pick() + “.”);

System.out.println(“Main thread will now fork several threads.”);

} catch (CharStackEmptyException e) {

System.out.println(“Caught exception: StackCharEmptyException”);

System.out.println(“Message : ” + e.getMessage());

System.out.println(“Stack Trace : “);

e.printStackTrace();

}

/*

* The birth of threads

*/

Consumer ab1 = new Consumer();

Consumer ab2 = new Consumer();

System.out.println(“Two Consumer threads have been created.”);

Producer rb1 = new Producer();

Producer rb2 = new Producer();

System.out.println(“Two Producer threads have been created.”);

CharStackProbercsp = new CharStackProber();

System.out.println(“One CharStackProber thread has been created.”);

/*

* start executing

*/

ab1.start();

rb1.start();

ab2.start();

rb2.start();

csp.start();

/*

* Wait by here for all forked threads to die

*/

try {

ab1.join();

ab2.join();

rb1.join();

rb2.join();

csp.join();

// Some final stats after all the child threads terminated…

System.out.println(“System terminates normally.”);

System.out.println(“Final value of top = ” + stack.getTop() + “.”);

System.out.println(“Final value of stack top = ” + stack.pick() + “.”);

System.out.println(“Final value of stack top-1 = ” + stack.getAt(stack.getTop() – 1) + “.”);

// System.out.println(“Stack access count = ”

// + stack.getAccessCounter());

} catch (InterruptedException e) {

System.out.println(“Caught InterruptedException: ” + e.getMessage());

System.exit(1);

} catch (Exception e) {

System.out.println(“Caught exception: ” + e.getClass().getName());

System.out.println(“Message : ” + e.getMessage());

System.out.println(“Stack Trace : “);

e.printStackTrace();

}

} // main()

/*

* Inner Consumer thread class

*/

static class Consumer extends BaseThread {

private char copy; // A copy of a block returned by pop()

public void run() {

System.out.println(“Consumer thread [TID=” + this.iTID + “] starts executing.”);

for (int i = 0; i <StackManager.iThreadSteps; i++) {

// Insert your code in the following:

// …

// …

try {

semaphore.Wait(); // enter critical section:

this.copy = CharStack.pop(); // pop top of stack

} catch (CharStackEmptyExceptionfe) {

// fe.printStackTrace();

i–; // redo this iteration next time since it was “missed”

} catch (Exception e) {

e.printStackTrace();

i–; // redo this iteration next time since it was “missed”

} finally {

semaphore.Signal(); // end of critical section

System.out.println(“Consumer thread [TID=” + this.iTID + “] pops character =” + this.copy);

}

}

System.out.println(“Consumer thread [TID=” + this.iTID + “] terminates.”);

}

} // class Consumer

/*

* Inner class Producer

*/

static class Producer extends BaseThread {

private char block; // block to be returned

public void run() {

System.out.println(“Producer thread [TID=” + this.iTID + “] starts executing.”);

for (int i = 0; i <StackManager.iThreadSteps; i++) {

// Insert your code in the following:

// …

// …

try {

semaphore.Wait(); // enter critical section:

char top = CharStack.pick(); // read the top char in stack:

this.block = (char) (top + 1); // get the next character in

// the (ascii) alphabet.

CharStack.push(this.block); // push it onto the stack

} catch (CharStackEmptyExceptionee) {

this.block = ‘a’; // if the stack is empty at pick() then

// the char ‘a’ must be written

try {

CharStack.push(this.block); // push it onto the stack

} catch (CharStackFullException e) {

i–; // redo this iteration next time since it was

// “missed”

}

} catch (CharStackFullException e) {

i–; // redo this iteration next time since it was “missed”

} catch (Exception e) {

e.printStackTrace();

} finally {

semaphore.Signal(); // end of critical section

System.out.println(“Producer thread [TID=” + this.iTID + “] pushes character =” + this.block);

}

}

System.out.println(“Producer thread [TID=” + this.iTID + “] terminates.”);

}

} // class Producer

/*

* Inner class CharStackProber to dump stack contents

*/

static class CharStackProber extends BaseThread {

public void run() {

System.out.println(“CharStackProber thread [TID=” + this.iTID + “] starts executing.”);

for (int i = 0; i < 2 * StackManager.iThreadSteps; i++) {

// Insert your code in the following. Note that the stack state

// must be

// printed in the required format.

// …

// …

try {

semaphore.Wait(); // enter the critical section:

System.out.println(“Stack S = ([” + stack.getAt(0) + “],[” + stack.getAt(1) + “],[” + stack.getAt(2)

+ “],[” + stack.getAt(3) + “],[” + stack.getAt(4) + “],[” + stack.getAt(5) + “],[”

+ stack.getAt(6) + “],[” + stack.getAt(7) + “],[” + stack.getAt(8) + “],[” + stack.getAt(9)

+ “])”);

} catch (CharStackInvalidAceessException e) {

e.printStackTrace();

} finally {

semaphore.Signal(); // end of critical section

}

// TASK 2: IMPORTANT NOTE – as it stands now the CharStackProber

// csp thread’s 6 loop iterations could execute at any time in

// the threads order of execution (and often they execute last,

// all 6 of them). That

// seems to me to be a problem: we would like to probe between

// every–but it’s not

// written in the question and the code that we have to take

// care of this. A more meaningful architecture would have been

// to trigger the stack probing routine not within its own

// thread but rather as a part of the Producer and Consumer

// threads (called from within them). But again such a

// modification is not requested in the question, and by chance

// probing occasionally executes between other threads in some

// sample runs.

}

}

} // class CharStackProber

} // class StackManager 

Task3 

Grep_1.txt

Stack S = ([a],[b],

[c]

,[$],[$],[$],[$],[$],[$],[$])

Stack S = ([a],[b],

[c]

,[d],[$],[$],[$],[$],[$],[$])

Stack S = ([a],[b],

[c]

,[d],[$],[$],[$],[$],[$],[$])

Stack S = ([a],[b],

[c]

,[d],[$],[$],[$],[$],[$],[$])

Stack S = ([a],[b],

[c]

,[d],[$],[$],[$],[$],[$],[$])

Stack S = ([a],[b],

[c]

,[d],[$],[$],[$],[$],[$],[$])

Grep_2.txt

Stack S = ([a],[b],

[c]

,[d],[$],[$],[$],[$],[$],[$])

Stack S = ([a],[b],

[c]

,[d],[$],[$],[$],[$],[$],[$])

Stack S = ([a],[b],

[c]

,[d],[$],[$],[$],[$],[$],[$])

Stack S = ([a],[b],

[c]

,[d],[$],[$],[$],[$],[$],[$])

Stack S = ([a],[b],

[c]

,[d],[$],[$],[$],[$],[$],[$])

Stack S = ([a],[b],

[c]

,[d],[$],[$],[$],[$],[$],[$]) 

Grep_3.txt 

Stack S = ([a],[b],

[c]

,[d],[$],[$],[$],[$],[$],[$])

Stack S = ([a],[b],

[c]

,[d],[$],[$],[$],[$],[$],[$])

Stack S = ([a],[b],

[c]

,[d],[e],[$],[$],[$],[$],[$])

Stack S = ([a],[b],

[c]

,[d],[e],[$],[$],[$],[$],[$])

Stack S = ([a],[b],

[c]

,[d],[e],[$],[$],[$],[$],[$])

Stack S = ([a],[b],

[c]

,[d],[$],[$],[$],[$],[$],[$])

Task4

CharStackEmptyException.java

package CharStackExceptions_Task4;

public class CharStackEmptyException extends Exception {

publicCharStackEmptyException() {

super(“Char Stack is empty.”);

}

} 

CharStackFullException.java

package CharStackExceptions_Task4;

public class CharStackFullException extends Exception {

publicCharStackFullException() {

super(“Char Stack has reached its capacity of CharStack.MAX_SIZE.”);

}

} 

CharStackInvalidAceessException.java

package CharStackExceptions_Task4;

public class CharStackInvalidAceessException extends Exception {

} 

CharStackInvalidSizeException.java

package CharStackExceptions_Task4;

public class CharStackInvalidSizeException extends Exception {

publicCharStackInvalidSizeException() {

super(“Invalid stack size specified.”);

}

publicCharStackInvalidSizeException(intpiStackSize) {

super(“Invalid stack size specified: ” + piStackSize);

}

} 

BaseThread.java 

package Task4;

classBaseThread extends Thread {

/*

* Data members

*/

public static intiNextTID = 1; // Preserves value across all instances

protectedintiTID;

publicBaseThread() {

this.iTID = iNextTID;

iNextTID++;

}

publicBaseThread(intpiTID) {

this.iTID = piTID;

}

} 

CharStack.java 

package Task4;

import CharStackExceptions_Task4.*;

classCharStack {

/*

* Some class constants.

*/

public static final int MIN_SIZE = 7; // Minimum stack size

public static final int MAX_SIZE = 32; // # of letters in the English

// alphabet + 6

public static final int DEFAULT_SIZE = 10; // Default stack size

/*

* Class variables

*/

private static intiSize = DEFAULT_SIZE;

private static intiTop = 3; // stack[0:9] with four defined values

private static char aCharStack[] = new char[] { ‘a’, ‘b’, ‘c’, ‘d’, ‘$’, ‘$’, ‘$’, ‘$’, ‘$’, ‘$’ };

// Default constructor

publicCharStack() {

// Just do nothing

}

// Constructor with supplied size

publicCharStack(intpiSize) throws CharStackInvalidSizeException {

if (piSize< MIN_SIZE || piSize> MAX_SIZE)

throw new CharStackInvalidSizeException(piSize);

if (piSize != DEFAULT_SIZE) {

this.aCharStack = new char[piSize];

// Fill in with letters of the alphabet and keep

// 6 free blocks

for (int i = 0; i <piSize – 6; i++)

this.aCharStack[i] = (char) (‘a’ + i);

for (int i = 1; i <= 6; i++)

this.aCharStack[piSize – i] = ‘$’;

this.iTop = piSize – 7;

this.iSize = piSize;

}

}

/*

* Picks a value from the top without modifying the stack

*/

public static char pick() throws CharStackEmptyException {

if (iTop == -1)

throw new CharStackEmptyException();

returnaCharStack[iTop];

}

/*

* Returns arbitrary value from the stack array

*/

public char getAt(intpiPosition) throws CharStackInvalidAceessException {

if (piPosition< 0 || piPosition>= iSize)

throw new CharStackInvalidAceessException();

returnthis.aCharStack[piPosition];

}

/*

* Standard push operation

*/

public static void push(char pcChar) throws CharStackFullException {

if (iTop == iSize – 1)

throw new CharStackFullException();

aCharStack[++iTop] = pcChar;

}

/*

* Standard pop operation

*/

public static char pop() throws CharStackEmptyException {

if (iTop == -1)

throw new CharStackEmptyException();

charcChar = aCharStack[iTop];

aCharStack[iTop–] = ‘$’; // Leave prev. value undefined

returncChar;

}

/* Getters */

publicintgetSize() {

returnthis.iSize;

}

publicintgetTop() {

returnthis.iTop;

}

} 

Cycle_Semaphore.java 

package Task4;

public class Cycle_Semaphore extends Semaphore {

privateintnum_of_threads_in_cycle;

publicCycle_Semaphore(int i, int j) {

super(i);

num_of_threads_in_cycle = j;

}

public synchronized void Wait() { // the original semaphore Wait() function that never goes under zero.

while (this.value<= 0) {

try {

wait();

} catch (InterruptedException e) {

System.out.println(“Semaphore::Wait() – caught InterruptedException: ” + e.getMessage());

e.printStackTrace();

}

}

this.value–;

}

public synchronized void Signal() {

++this.value;

notify();

}

public synchronized booleanDoneCycle() {

// if both threads in the group ran then

// it’s time to signal to the other group of threads.

returnthis.value == 0;

}

public synchronized void Reset() {

this.value = num_of_threads_in_cycle;

notify();

}

} 

Semaphore.java 

package Task4;

class Semaphore {

protectedint value; // changed to protected for the child class Jupimg_Semaphore.java

public Semaphore(int value) {

this.value = value;

}

public Semaphore() {

this(0);

}

public synchronized void Wait() {

this.value–;// TASK 1: 1/ I decremented the semaphore’s value at the

// beginning of the method instead of the end: because

// if it’s done at the end, a lot of threads could be

// waiting and the semaphore value would not be

// reflecting the number of waiting threads–it would

// only reflect the number of threads that acquired an

// authorization (and in fact would never go under

// zero).

if (this.value< 0) { // TASK 1: 2/ I changed while statement to an if

// statement to prevent a process from waiting

// again if more threads are on the waiting list

// (i.e. negative semaphore value). Now, all

// threads that entered this if statement are on

// “the waiting list” and can be picked to run

// if another thread emits a notify() for this

// object.

//

// 3/ I also changed “<= 0” to “< 0”, because 0

// means that it was 1 (i.e. semaphore is free)

// at the beginning of the function–the current

// process just made it 0 with the first

// decrement statement.

try {

wait(); // TASK 1: comment – any thread that reached this point

// is on the waiting list. If the while statement was

// kept it would have resulted in a deadlock–because

// any thread, upon notification, would run back into

// the while loop and wait() again since the semaphore’s

// value is still negative even if it was just

// incremented by the Signal() function.

} catch (InterruptedException e) {

System.out.println(“Semaphore::Wait() – caught InterruptedException: ” + e.getMessage());

e.printStackTrace();

}

}

}

public synchronized void Signal() {

++this.value;

notify();

}

public synchronized void P() {

this.Wait();

}

public synchronized void V() {

this.Signal();

}

} 

StackManager2.java 

package Task4;

import CharStackExceptions_Task4.*;

public class StackManager2 {

// The Stack

private static CharStack stack = new CharStack();

private static final int NUM_ACQREL = 4; // Number of Producer/Consumer

// threads

private static final int NUM_PROBERS = 1; // Number of threads dumping stack

private static intiThreadSteps = 3; // Number of steps they take

// Semaphore declarations. Insert your code in the following:

// …

// …

// TASK 2:

private static Semaphore semaphore = new Semaphore(1);// 1 because only

// one

// thread can access

// the stack at a

// time

// TASK 4:

// start with producers’ lock available. –> Two producers can run at a time

private static Semaphore producer_semaphore = new Cycle_Semaphore(2, 2);

private static intcounter_of_running_PRODUCER_threads = 0;

// start with consumers blocked

private static Semaphore consumer_semaphore = new Cycle_Semaphore(0, 2);

private static intcounter_of_running_CONSUMER_threads = 0;

// The main()

public static void main(String[] argv) {

// Some initial stats…

try {

System.out.println(“Main thread starts executing.”);

System.out.println(“Initial value of top = ” + stack.getTop() + “.”);

System.out.println(“Initial value of stack top = ” + stack.pick() + “.”);

System.out.println(“Main thread will now fork several threads.”);

} catch (CharStackEmptyException e) {

System.out.println(“Caught exception: StackCharEmptyException”);

System.out.println(“Message : ” + e.getMessage());

System.out.println(“Stack Trace : “);

e.printStackTrace();

}

/*

* The birth of threads

*/

Consumer ab1 = new Consumer();

Consumer ab2 = new Consumer();

System.out.println(“Two Consumer threads have been created.”);

Producer rb1 = new Producer();

Producer rb2 = new Producer();

System.out.println(“Two Producer threads have been created.”);

CharStackProbercsp = new CharStackProber();

System.out.println(“One CharStackProber thread has been created.”);

/*

* start executing

*/

ab1.start();

rb1.start();

ab2.start();

rb2.start();

csp.start();

/*

* Wait by here for all forked threads to die

*/

try {

ab1.join();

ab2.join();

rb1.join();

rb2.join();

csp.join();

// Some final stats after all the child threads terminated…

System.out.println(“System terminates normally.”);

System.out.println(“Final value of top = ” + stack.getTop() + “.”);

System.out.println(“Final value of stack top = ” + stack.pick() + “.”);

System.out.println(“Final value of stack top-1 = ” + stack.getAt(stack.getTop() – 1) + “.”);

// System.out.println(“Stack access count = ”

// + stack.getAccessCounter());

} catch (InterruptedException e) {

System.out.println(“Caught InterruptedException: ” + e.getMessage());

System.exit(1);

} catch (Exception e) {

System.out.println(“Caught exception: ” + e.getClass().getName());

System.out.println(“Message : ” + e.getMessage());

System.out.println(“Stack Trace : “);

e.printStackTrace();

}

} // main()

/*

* Inner Consumer thread class

*/

static class Consumer extends BaseThread {

private char copy; // A copy of a block returned by pop()

public void run() {

System.out.println(“Consumer thread [TID=” + this.iTID + “] starts executing.”);

try {

// each thread grabs a lock until completion of all 6 loops: (2

// are allowed to run at any time)

consumer_semaphore.Wait();

counter_of_running_PRODUCER_threads = 0; // are now not running anymore

counter_of_running_CONSUMER_threads++; // count consumer threads

// in

// order to know when we are

// done this round

for (int i = 0; i < StackManager2.iThreadSteps; i++) {

// Insert your code in the following:

// …

// …

try {

semaphore.Wait(); // enter critical section:

this.copy = CharStack.pop(); // pop top of stack

System.out.println(“Consumer thread [TID=” + this.iTID + “] pops character =” + this.copy);

} catch (CharStackEmptyExceptionfe) {

// fe.printStackTrace();

// i–; // redo this iteration next time (after a

// Signal()

// and Wait()) since it was

// “missed”

System.out.println(“11”);

} catch (Exception e) {

e.printStackTrace();

// i–; // redo this iteration next time since it was

// “missed”

System.out.println(“12”);

} finally {

semaphore.Signal(); // end of critical section

}

}

} catch (Exception e) {

} finally {

// at the end of the 6 consumer loops, increment the mutex

// producer_semaphore only if the 2 consumer threads ran:

if (counter_of_running_CONSUMER_threads>= 2) {

producer_semaphore.Signal();

producer_semaphore.Signal();

}

System.out.println(“Consumer thread [TID=” + this.iTID + “] terminates.”);

}

}

} // class Consumer

/*

* Inner class Producer

*/

static class Producer extends BaseThread {

private char block; // block to be returned

public void run() {

System.out.println(“Producer thread [TID=” + this.iTID + “] starts executing.”);

try {

// each thread grabs a lock until its completion of all 6 loops:

// (2 are allowed to run at any time)

producer_semaphore.Wait();

counter_of_running_CONSUMER_threads = 0; // not the running group anymore

counter_of_running_PRODUCER_threads++; // count consumer threads

// in

// order to know when we

// are

// done this round

for (int i = 0; i < StackManager2.iThreadSteps; i++) {

// Insert your code in the following:

// …

// …

try {

semaphore.Wait(); // enter critical section:

char top = CharStack.pick(); // read the top char in

// stack:

this.block = (char) (top + 1); // get the next character

// in

// the (ascii) alphabet.

CharStack.push(this.block); // push it onto the stack

System.out.println(“Producer thread [TID=” + this.iTID + “] pushes character =” + this.block);

} catch (CharStackEmptyExceptionee) {

this.block = ‘a’; // if the stack is empty at pick()

// then

// the char ‘a’ must be written

System.out.println(“3”);

try {

CharStack.push(this.block); // push it onto the

// stack

} catch (CharStackFullException e) {

// i–; // redo this iteration next time (after a

// Signal() and Wait()) since it was

// “missed”

System.out.println(“1”);

}

} catch (CharStackFullException e) {

// i–; // redo this iteration next time since it was

// “missed”

System.out.println(“2”);

} catch (Exception e) {

e.printStackTrace();

} finally {

semaphore.Signal(); // end of critical section

}

}

} catch (Exception e) {

} finally {

// at the end of 6 loops of the producer, increment the

// consumer_semaphore twice only if the 2 producer

// threads ran:

if (counter_of_running_PRODUCER_threads>= 2) {

consumer_semaphore.Signal();

consumer_semaphore.Signal();

}

System.out.println(“Producer thread [TID=” + this.iTID + “] terminates.”);

}

}

} // class Producer

/*

* Inner class CharStackProber to dump stack contents

*/

static class CharStackProber extends BaseThread {

public void run() {

System.out.println(“CharStackProber thread [TID=” + this.iTID + “] starts executing.”);

for (int i = 0; i < 2 * StackManager2.iThreadSteps; i++) {

// Insert your code in the following. Note that the stack state

// must be

// printed in the required format.

// …

// …

try {

semaphore.Wait(); // enter the critical section:

System.out.println(“Stack S = ([” + stack.getAt(0) + “],[” + stack.getAt(1) + “],[” + stack.getAt(2)

+ “],[” + stack.getAt(3) + “],[” + stack.getAt(4) + “],[” + stack.getAt(5) + “],[”

+ stack.getAt(6) + “],[” + stack.getAt(7) + “],[” + stack.getAt(8) + “],[” + stack.getAt(9)

+ “])”);

} catch (CharStackInvalidAceessException e) {

e.printStackTrace();

} finally {

semaphore.Signal(); // end of critical section

}

// TASK 2: IMPORTANT NOTE – as it stands now the CharStackProber

// csp thread’s 6 loop iterations could execute at any time in

// the threads order of execution (and often they execute last,

// all 6 of them). That

// seems to me to be a problem: we would like to probe between

// every–but it’s not

// written in the question and the code that we have to take

// care of this. A more meaningful architecture would have been

// to trigger the stack probing routine not within its own

// thread but rather as a part of the Producer and Consumer

// threads (called from within them). But again such a

// modification is not requested in the question, and by chance

// probing occasionally executes between other threads in some

// sample runs.

}

}

} // class CharStackProber

} // class StackManager