?
Solved

Multi-threaded Java Application Help Needed

Posted on 2004-11-22
24
Medium Priority
?
290 Views
Last Modified: 2010-03-31
Hi, I have written the following code which I need to simulate a deadlock in a "ten pin bowling alley" situation, where there are:

8 players
2 lanes
6 balls
2 x size 5 shoes
1 x size 6 shoes
1 x size 7 shoes
2 x size 8 shoes
1 x size 9 shoes
1 x size 10 shoes

If anyone can fix this up for me, it will be worth 475 points for you. Here is what needs to be done:

I have three classes:

1. Deadlock
2. NoDeadlock
3. PlayerThread

If you run Deadlock, it must simulate how the deadlock occurs. If you run NoDeadlock, it must simulate how the "game" can be completed without getting a deadlock. Find below the actual assignment:

== Assignment specifics - my source code will follow ==

Bowling Alley Deadlock
--------------------------

There exists a bowling alley with two lanes in which to bowl.
The computer that does the scoring for each lane is programmed
to allow 4 players per lane.  

There are six balls available for playing that need to be
shared amongst the players.

The bowling alley has one other requirement; you have to wear the
shoes that are provided for you.  The shoesizes available are as
follows:  2 x size 5
        1 x size 6
        1 x size 7
        2 x size 8
        1 x size 9
        1 x size 10

At a given time the following players arrive for an evening of
ten-pin bowling:
      Player 1: shoe-size 8
      Player 2: shoe-size 6
      Player 3: shoe-size 8
      Player 4: shoe-size 6
      Player 5: shoe-size 7
      Player 6: shoe-size 10
      Player 7: shoe-size 9
      Player 8: shoe-size 8

Write a multi-threaded Java application that simulates a deadlock
situation based on the bowling alley information given above.

Adapt your program so that no deadlocks will occur.

=====================================

The code is as follows (lots of comments to indicate what I INTEND to do, but failing to do):

Deadlock.java
==========

public class Deadlock {

    public static void main(String args[]) {

        // Sets the players' names, numbers, preferred shoe sizes and the lanes they will play in.
        // Whether they receive a ball, shoes and a lane will be determined in the PlayerThread class.

        PlayerThread firstPlayer   = new PlayerThread("Michaelangelo", 0, 8, 1);
        firstPlayer.start();

        PlayerThread secondPlayer  = new PlayerThread("Leonardo", 1, 6, 1);
        secondPlayer.start();

        PlayerThread thirdPlayer   = new PlayerThread("Raphael", 2, 8, 1);
        thirdPlayer.start();

        PlayerThread fourthPlayer  = new PlayerThread("Donatello", 3, 6, 1);
        fourthPlayer.start();

        PlayerThread fifthPlayer   = new PlayerThread("Jason", 4, 7, 2);
        fifthPlayer.start();

        PlayerThread sixthPlayer   = new PlayerThread("Freddie", 5, 10, 2);
        sixthPlayer.start();

        PlayerThread seventhPlayer = new PlayerThread("Michael", 6, 9, 2);
        seventhPlayer.start();

        PlayerThread eighthPlayer  = new PlayerThread("Petri", 7, 8, 2);
        eighthPlayer.start();

    }

}

=====================================

public class NoDeadlock {

    public static void main(String args[]) {

        // The first four parameters set the players' names, numbers, preferred shoe size and the lane they will play in.
        // The rest of the parameters set whether the players receives a ball, shoes or a lane, as described below.

        // firstPlayer (Michaelangelo, 0) gets a ball, shoes in his preferred size, as well as a lane to play in.
        PlayerThread firstPlayer   = new PlayerThread("Michaelangelo", 0, 8, 1, 1, 1, 1);
        firstPlayer.start();

        // secondPlayer (Leonardo, 1) gets a ball, shoes in his preferred size, but not a lane to play in.
        PlayerThread secondPlayer  = new PlayerThread("Leonardo", 1, 6, 1, 1, 1, 0);
        secondPlayer.start();

        // thirdPlayer (Raphael, 2) gets a ball, shoes in his preferred size, but not a lane to play in.
        PlayerThread thirdPlayer   = new PlayerThread("Raphael", 2, 8, 1, 1, 1, 0);
        thirdPlayer.start();

        // fourthPlayer (Donatello, 3) gets a ball, but no shoes and no lane to play in.
        PlayerThread fourthPlayer  = new PlayerThread("Donatello", 3, 6, 1, 1, 0, 0);
        fourthPlayer.start();

        // fifthPlayer (Jason, 4) gets a ball, shoes in his preferred size, as well as a lane to play in.
        PlayerThread fifthPlayer   = new PlayerThread("Jason", 4, 7, 2, 1, 1, 2);
        fifthPlayer.start();

        // sixthPlayer (Freddie, 5) gets a ball, shoes in his preferred size, but not a lane to play in.
        PlayerThread sixthPlayer   = new PlayerThread("Freddie", 5, 10, 2, 1, 1, 0);
        sixthPlayer.start();

        // seventhPlayer (Michael, 6) doesn't get a ball, gets shoes in his preferred size, but not a lane to play in.
        PlayerThread seventhPlayer = new PlayerThread("Michael", 6, 9, 2, 0, 1 ,0);
        seventhPlayer.start();

        // eighthPlayer (Petri, 7) doesn't get a ball, no shoes, and no lane to play in.
        PlayerThread eighthPlayer  = new PlayerThread("Petri", 7, 8, 2, 0, 0, 0);
        eighthPlayer.start();

    }

}

=====================================

public class PlayerThread extends Thread{

    private String[][] player   = new String[8][6];                 // We have 8 players
    private int[] shoes         = new int[11];                      // We have shoes of 10 different sizes (theoretically).
    private int[] lane          = new int[2];                       // We have two lanes.
    private int whichOne        = -1;                               // Default value for which program was run - NONE.
    private int activeLane      = -1;                               // Default value for the active lane - NONE.
    private int error           = 0;                                // There currently is no error.
    private int round           = 1;                                // The next round to be played...
    private int totalBalls, totalLanes, currentPlayer;

    public PlayerThread (String playerName, int playerNumber, int shoeSize,  int playerLane) {
        shoes[0]                = 0;                                // We have no pairs of shoes with size 0.
        shoes[1]                = 0;                                // We have no pairs of shoes with size 1.
        shoes[2]                = 0;                                // We have no pairs of shoes with size 2.
        shoes[3]                = 0;                                // We have no pairs of shoes with size 3.
        shoes[4]                = 0;                                // We have no pairs of shoes with size 4.
        shoes[5]                = 2;                                // We have no pairs of shoes with size 5.
        shoes[6]                = 1;                                // We have one pair of shoes with size 6.
        shoes[7]                = 1;                                // We have one pair of shoes with size 7.
        shoes[8]                = 2;                                // We have two pairs of shoes with size 8.
        shoes[9]                = 1;                                // We have one pair of shoes with size 9.
        shoes[10]               = 1;                                // We have one pair of shoes with size 10.
        totalBalls              = 6;                                // We have a total of 6 balls.
        totalLanes              = 2;                                // We have a total of 2 lanes.
        currentPlayer           = playerNumber;                     // Indicates the current active player.
        activeLane              = playerLane;                       // The lane that this player will use.
        player[playerNumber][0] = playerName;                       // Player's name.
        player[playerNumber][1] = Integer.toString(shoeSize);       // Player's preferred shoe size.
        player[playerNumber][2] = "0";                              // Player doesn't have a ball yet.
        player[playerNumber][3] = "0";                              // Player doesn't have shoes yet.
        player[playerNumber][4] = "0";                              // Player doesn't have a lane yet.
        player[playerNumber][5] = "0";                              // This player hasn't played yet.
        whichOne                = 1;                                // We have determined that the program that was run was the one
                                                                    // in which a deadlock may or may not occur.
    }
   
    public PlayerThread (String playerName, int playerNumber, int shoeSize, int playerLane, int hasBall, int hasShoes, int hasLane) {
        shoes[0]                = 0;                                // We have no pairs of shoes with size 0.
        shoes[1]                = 0;                                // We have no pairs of shoes with size 1.
        shoes[2]                = 0;                                // We have no pairs of shoes with size 2.
        shoes[3]                = 0;                                // We have no pairs of shoes with size 3.
        shoes[4]                = 0;                                // We have no pairs of shoes with size 4.
        shoes[5]                = 2;                                // We have no pairs of shoes with size 5.
        shoes[6]                = 0;                                // We have no free pairs of shoes with size 6.
        shoes[7]                = 0;                                // We have no free pairs of shoes with size 7.
        shoes[8]                = 0;                                // We have no free pairs of shoes with size 8.
        shoes[9]                = 0;                                // We have no free pairs of shoes with size 9.
        shoes[10]               = 0;                                // We have no free pairs of shoes with size 10.
        totalBalls              = 0;                                // We have no free balls.
        totalLanes              = 0;                                // We have no free lanes.
        currentPlayer           = playerNumber;                     // Indicates the current active player.
        activeLane              = playerLane;                       // The lane that this player will use.
        player[playerNumber][0] = playerName;                       // Player's name.
        player[playerNumber][1] = Integer.toString(shoeSize);       // Player's preferred shoe size.
        player[playerNumber][2] = Integer.toString(hasBall);        // Determines whether the player has a ball.
        player[playerNumber][3] = Integer.toString(hasShoes);       // Determines whether the player has shoes.
        player[playerNumber][4] = Integer.toString(hasLane);        // Determines whether the player has a lane.
        player[playerNumber][5] = "0";                              // This player hasn't played yet.
        whichOne                = 0;                                // We have determined that the program that was run was the one
                                                                    // in which a deadlock will never occur.
    }

    private void takeBall (int ball, int aPlayer) {
        if (player[aPlayer][2] != "0") {
            System.out.println ("  " + player[aPlayer][0] + " already has a ball. No need to report at the ball counter.");
            return;
        }
        if (ball == 1) {
            if (totalBalls > 0) {                                   // Ball is available
                totalBalls -= 1;
                player[aPlayer][2] = "1";
                System.out.println ("  " + player[aPlayer][0] + " went to the ball counter and obtained a ball.");
            }
            else {                                                  // Ball is not available
                System.out.println ("  There does not seem to be a ball available for " + player[aPlayer][0] + ".");
            }
        }
    }

    private void takeShoes (int shoe, int aPlayer) {
        if (player[aPlayer][3] != "0") {
            System.out.println ("  " + player[aPlayer][0] + " already has shoes. No need to report at the shoe counter.");
            return;
        }
        if (shoe > -1) {
            if (shoes[shoe] > 0) {                                  // Shoe is available
                shoes[shoe] -= 1;
                player[aPlayer][3] = "1";
                System.out.println ("  " + player[aPlayer][0] + " went to the shoe counter and obtained a pair of shoes with size " + player[aPlayer][2] + ".");
            }
            else {                                                  // Shoe is not available
                System.out.println ("  There does not seem to be a pair of shoes available for " + player[aPlayer][0] + ".");
            }
        }
    }

    private void takeLane (int lane, int aPlayer) {
        if (player[aPlayer][4] != "0") {
            System.out.println ("  " + player[aPlayer][0] + " goes to the track and occupies lane number " + player[aPlayer][4] + ".");
            return;
        }
        if (lane == 1) {
            if (totalLanes > 0) {
                totalLanes -= 1;
                if (aPlayer < 4) player[aPlayer][4] = "1";
                else player[aPlayer][4] = "2";
                System.out.println ("  " + player[aPlayer][0] + " goes to the track and occupies lane number " + player[aPlayer][4] + ".");
            }
            else {
                System.out.println ("  There does not seem to be a lane available for " + player[aPlayer][0] + ".");
            }
        }
    }

    private void hasResources (int aPlayer) {
        if (player[aPlayer][0] != null) {
            // int turn = aPlayer + 1;
            // System.out.println ("This is round number " + round + ", turn number " + turn + ".");
            // System.out.println ("------------------------------------------------------------------------------------------------");
            System.out.println ("This is round number " + round + ". The total unallocated resources available before round " + round + " started were: {");
            System.out.println ("  Lanes: " + totalLanes);
            System.out.println ("  Balls: " + totalBalls);
            System.out.println ("  Shoes: " + shoes[5] + " * size 5, " + shoes[6] + " * size 6, " + shoes[7] + " * size 7, " + shoes[8] + " * size 8, " + shoes[9] + " * size 9 and " + shoes[10] + " * size 10.");
            System.out.println ("}");
            System.out.println ("Resource status for " + player[aPlayer][0] + ": {");
            takeBall (1, aPlayer);
            takeShoes (Integer.parseInt(player[aPlayer][1]), aPlayer);
            takeLane (1, aPlayer);
            System.out.println("}");
            if (player[aPlayer][2] == "0" || player[aPlayer][3] == "0" || player[aPlayer][4] == "0") {
                System.out.println (player[aPlayer][0] + " skips this round and goes for a snack.");
            }
            if (player[aPlayer][2] == "1" && player[aPlayer][3] == "1" && player[aPlayer][4] != "0") {
                System.out.println (player[aPlayer][0] + " plays this round then returns his shoes, ball and clears the lane.");
                returnResources(1, Integer.parseInt(player[aPlayer][1]), Integer.parseInt(player[aPlayer][4]), aPlayer);
            }
            System.out.println ("================================================================================================");
        }
    }

    private void returnResources (int ball, int shoe, int lane, int aPlayer) {
        if (ball == 1) {                                            // We have specified that one ball was returned.
            if (totalBalls < 6) {                                   // We actually determined that at least one ball is in use.
                totalBalls += 1;
                player[aPlayer][2] = "0";
            }
        }
        if (shoe > -1) {                                            // We have specified that a pair of shoes of size 'shoe' were returned.
            shoes[shoe] += 1;                                       // No (short) way to check here whether we have a shoe to return, so
            player[aPlayer][3] = "0";                               // be really careful with specifying shoe parameters above.
        }
        if (lane == 1) {                                            // We have specified that a lane was released.
            if (totalLanes < 2) {                                   // We actually determined that at least one lane is in use.
                totalLanes += 1;
                player[aPlayer][4] = "0";
            }
        }
    }

    // I suspect my problem comes with the notify() and wait() sequences and a general misconception I may have about threads. I am totally clueless here.
    public synchronized void run() {
        if (whichOne == 0) {                                        // Players gets specifically assigned resources. No deadlock occurs.
            while (round <= 4) {
                try {
                    if (player[currentPlayer][5] == "1") {
                        wait();
                    }
                    if (player[currentPlayer][5] == "0") {
                        player[currentPlayer][5] = "1";
                        hasResources(currentPlayer);
                        wait();
                        notify();
                    }
                    round += 1;
                }
                catch (InterruptedException exception) {
                    exception.printStackTrace();
                }
            }
        }
        else {                                                      // Players gets randomly assigned resources. A deadlock may occur.
            boolean isDeadlocked = false;
            int numGames         = 1;
            while (isDeadlocked == false || numGames < 5000) {      // Players keep playing until a deadlock occurs, or until 5000 bowls.
                numGames += 1;
                // TODO...!
            }
        }
    }
}
0
Comment
Question by:FolkLore
  • 11
  • 10
  • 2
  • +1
24 Comments
 
LVL 35

Expert Comment

by:girionis
ID: 12643222
That sounds terribly like an assignment. We cannot do it for you. If you have any specific questions ask but solving whole assignment is against EE rules and experts' principles.
0
 

Author Comment

by:FolkLore
ID: 12643257
Ok, I can live with that, but my main problems are:

1. For some reason my while loop never gets completed. It runs through only once. I think that it has to do with my implementation of threads.
2. I tried resume() stop() suspend() wait() etc. on the threads, but I have those wrong.

I think that if you look at my code you will see that I am actually very close to making it work for the NoDeadlock part. The Deadlock part will be easy once I have one part solved.

So, let me rephrase: I do not want it COMPLETED, but I want to be put on the right track ;) Better?

Regards

FolkLore
0
 
LVL 35

Expert Comment

by:girionis
ID: 12643335
> 1. For some reason my while loop never gets completed. It runs through
> only once. I think that it has to do with my implementation of threads.

Which while loop are you talking about? The one in the if or in the else statement?
0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 

Author Comment

by:FolkLore
ID: 12643363
I am talking about the one in the IF (round <= 4). For some reason that never gets executed. That whole process runs only once, and I think it has to do with my low knowledge with multi-threading :)
0
 
LVL 35

Expert Comment

by:girionis
ID: 12643436
It should be executed. It depends on which constructor of the PlayerThread you are calling. If you are calling the first one it will never get executed because the "whichOne" variable will never be 0. If you call the second constructor it will be zero and thus it should be executed. Which one are you trying to run, the Deadlock or the "NoDeadlock"?
0
 

Author Comment

by:FolkLore
ID: 12643471
As I said in my code, I am running the NoDeadlock class, which calls the second constructor, which results in the round <= 4 while loop that should be executed. If you run the code (should compile and all) you and run NoDeadlock, you will see what happens.
0
 

Author Comment

by:FolkLore
ID: 12643491
Maybe I should explain what I need done with the NoDeadlock code:

1. All players gets assigned the resources they need (where possible).
2. In NoDeadlock class, player 1 has a ball, shoes and lane 1.
3. In NoDeadlock class, player 5 has a ball, shoes and lane 2.
4. All other players don't have enough resources to play.
5. Player 1 and player 5 must go through the first round, release their resources.
6. After the first round, there will be 2 more pairs of shoes, 2 more balls and both lanes available.
7. Now it must start again, but player 1 and player 5 must not contend to play this round, because they already played.
8. Now there will be enough resources for at least 2 more players to play.
9. My logic never gets met past step #6. The resources gets released, but the loop doesn't get executed.

FolkLore
0
 
LVL 35

Expert Comment

by:girionis
ID: 12643602
> As I said in my code, I am running the NoDeadlock class, which calls
> the second constructor, which results in the round <= 4 while loop that
> should be executed. If you run the code (should compile and all) you
> and run NoDeadlock, you will see what happens.

I just tried it and it runs fine. It enters the loop if I use the NoDeadlock class.
0
 

Author Comment

by:FolkLore
ID: 12643647
But the loop runs only once. Not four times. Look at the value for the variable "round".

It never goes past round 1. Since there are 8 players and two lanes, I assume there will be 4 rounds, therefore it must go through 4 times, but it goes only once. Why is that? s it my implementation of the threads that is bogus?

FolkLore
0
 
LVL 35

Expert Comment

by:girionis
ID: 12643829
> It never goes past round 1. Since there are 8 players and two lanes,
> I assume there will be 4 rounds, therefore it must go through 4 times,
> but it goes only once. Why is that?

That's probably because each thread waits and is never notified about changes. So when all threads are created and reach the wait() method then all will wait until they are notified about changes and start again. But the notify() code is just afetr the wait() and will never be reached. You will need to move the notify() somewhere else and call it upon a condition. This condition should occur when the first player has finished and there are shoes available.
0
 
LVL 35

Expert Comment

by:girionis
ID: 12643839
This

> round += 1;

is actually *never* reached because each thread waits forever.
0
 
LVL 21

Expert Comment

by:MogalManic
ID: 12643942
If I may offer design a suggestion?  You are putting too much responsiblity on the PlayerThread object.   I would seperate the Players from the Resources (shoes, lanes, ...).  One player only has one set of shoes, and one lane.  The run method should be something like this

public void Run()
{
    GetShoes();
    GetLane();
    PlayGame();
}

The resources should be available to the player or the player would have to wait for the resource to be available.   A deadlock would occur if two different players allocated resources in different orders
P1:
    GetShoes()
    GetLane();
    PlayGame();

P2
    GetLane();
    GetShoes();
    PlayGame();
Player 1 would have shoes but wait for a lane
while player 2 would have a lane but wait for shoes.
0
 

Author Comment

by:FolkLore
ID: 12643943
So, if the thread has played out successfully, it must terminate, but if I use stop() or suspend() instead of wait when a thread has finished, I get a warning when I compile.

Ok... so... if you look at the hasResources method, you'll see that a player just acquires resources if he doesn't have sufficient resources to play, and it also does most of the output. My logic then tells me that:

1. I start all 8 threads.
2. If a player can play, his thread must stop(), suspend() or wait()
3. If a player can't play, his thread must NOT wait() nor stop() nor suspend(), it must just notify()?

But trying to do anything else than stopping or notifying gives a warning during compile.

I would really appreciate if you can just order the lines correctly for me as it should be in the loop, or would that constitute doing the assignment?

FolkLore
0
 
LVL 35

Expert Comment

by:girionis
ID: 12643986
How many players can play at a time? I suggest you start all threads, have the first players play and the rest wait, and when the first players finish then have them notify the rest, so they can also play. The players that finish can simply exit the run() method and the thread will die. No need to worry about them after they are done playing.
0
 

Author Comment

by:FolkLore
ID: 12644132
I have two lanes, so two players can play at a time. In my setup, player 1 and player 5 plays. How do they exit the run? Is there a keyword like exit() or something? I know about suspend() or stop() but when trying to use them, I get a warning about that method being deprecated.
0
 
LVL 13

Accepted Solution

by:
Webstorm earned 1200 total points
ID: 12648327
Hi FolkLore,

The main problem is the wait() & notify() method should be called on a shared object.

Replace :
public synchronized void run() {

By :
public void run() {

Create a new static Object (to share it for all Player classes instances) :

private static Object queue_waiting_to_play=new Object();

and call wait() when the player should wait (no available resources)
    synchronized(queue_waiting_to_play)
    {queue_waiting_to_play.wait();}

and call notify() when a player release the resource (has finish to play)
    synchronized(queue_waiting_to_play)
    {queue_waiting_to_play.notify();}

0
 
LVL 35

Assisted Solution

by:girionis
girionis earned 700 total points
ID: 12652228
>  I have two lanes, so two players can play at a time. In my setup, player 1 and player 5 plays. How do they exit the run?

The run will exit on its own (the run() method will finish running and the thread will exit). The only thing you have to make sure in order to avoid deadlock is to give resources to the players one by one. The commonest solution is to make sure that whoever gets the first pair of shoes will also get a lane to run, without shoes there should be no lane available. So do not allocate lanes to the players unless they already have a pair of shoes with them.

Webstorm is also right, you need to wait on a shared object (a pair of shoes). You will wait while there is no pair of shoes left and when the first player or second (or even both of them) is done running and there is a pair of shoes available you notify the rest of the players.
0
 

Author Comment

by:FolkLore
ID: 12652496
Thanks to both of you! I will check through your comments tonight and try to figure it out. I am still learning programming in various languages, so most of your comment is Greek to me, but I'll figure out what you mean tonight. We have a study group meeting tonight and we will discuss your comments and see what we can implement. This assignment must be in on Thursday, so I will award the points (split) to you folks then, should these hints help us.

Regards,

FolkLore
0
 
LVL 35

Expert Comment

by:girionis
ID: 12652521
If you have any more questions do not hesitate to ask :)
0
 

Author Comment

by:FolkLore
ID: 12680424
Thanks for all your help - I finally managed to implement Webstorm's method, although girionis helped a lot in getting me to understand the stuff - I will therefore allocate the points fairly.

Kobus
0
 
LVL 13

Expert Comment

by:Webstorm
ID: 12680459
:-)
0
 
LVL 35

Expert Comment

by:girionis
ID: 12680490
:)
0
 

Author Comment

by:FolkLore
ID: 12680508
By the way - with your help, my assignment got a final mark of 100% ;) Well done! Heh :)
0
 
LVL 35

Expert Comment

by:girionis
ID: 12680551
Hehe nice to hear that :)
0

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

After being asked a question last year, I went into one of my moods where I did some research and code just for the fun and learning of it all.  Subsequently, from this journey, I put together this article on "Range Searching Using Visual Basic.NET …
For beginner Java programmers or at least those new to the Eclipse IDE, the following tutorial will show some (four) ways in which you can import your Java projects to your Eclipse workbench. Introduction While learning Java can be done with…
Viewers will learn about arithmetic and Boolean expressions in Java and the logical operators used to create Boolean expressions. We will cover the symbols used for arithmetic expressions and define each logical operator and how to use them in Boole…
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.
Suggested Courses
Course of the Month13 days, 8 hours left to enroll

750 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question