Qfyilyi

I'm a CS student currently learning about concurrent programming so my knowledge on threads is still, uh, tentative.

I'm just a bit stuck at the logic of updating a shared array with threads. I'm creating a program that allows a potentially infinite number of threads to constantly update a boolean array of size 10 to simulate the idea of a seating area where people can go in, sit down for a random amount of time, and then leave. Here is my code:

class Viewer extends Thread{

    private String name;

    private int index;

    volatile boolean seats;





    Viewer(boolean st, String n){

        seats = st;

        name = n;

    }



    public void run() {

        ViewingStand vs = new ViewingStand(seats);

        this.index = vs.findSeat(name, seats);

            try {

                Thread.sleep((long)(Math.random() * 1000));

            } catch (InterruptedException e) {

                // TODO Auto-generated catch block

                e.printStackTrace();

            }

            seats = vs.leaveSeat(name, seats, index);



    }

}



class ViewingStand{

    private volatile boolean area; //the array used by threads

    private int seatNo; //index of whatever area is being taken or left.

    Random rand = new Random();

    boolean found = false;



    public ViewingStand(boolean st){

    this.area = st;

    }



    public int findSeat(String s, boolean seats){

        this.area = seats;

        while(found == false) {

            for(int i=0; i < area.length; i++) {

                if(area[i] == true) {

                    found = true;

                    this.seatNo = i; 

                    area[seatNo] = false;

                    System.out.println(s + " has found a seat.");

                    return this.seatNo;

                }

            }

            System.out.println(s + " has started searching again.");

        }

        return -1; //should never reach this

    }



    public boolean leaveSeat(String s, boolean area, int n){

        this.area = area;

        this.area[n] = false;

        System.out.println(s + " has left their seat.");

        return this.area;

    }

The result of this program is the array initially getting filled with 10 elements (the size of the array I passed from the main program), those threads then leave 'an' array but clearly not the same one I'm passing back and forth between both ViewingStand methods, as every subsequent thread after the 10th gets stuck looking for a seat. Would love some input to point me in the right direction. Thank you!

I'll ignore the concurrency issues at first and go straight for what seems like the logic error you're asking about - leaveSeat is setting this.area[n] = false - which seems to indicate that the seat is taken (your findSeat method assumes a seat is empty if the value is true).

On concurrency issues: You're likely to have issues with your loop checking the seats - it's possible for multiple threads to determine a seat is empty (and go into the if block), and all "claim" the same seat. You should construct one instance of ViewingStand and have it manage access to the seats - using concurrency controls like synchronized or locking to ensure multiple threads don't modify the state of the seats at the same time.

On the concurrency side ...

1. A volatile boolean is unlikely to be thread-safe. The volatile semantics apply to the array reference only, not to the access and updates to the elements of the array.



2. 
   

   You performing a separate read and write on an element of the array. Volatile means that a single read is guaranteed to see the instantaneously correct value; i.e. the value of the last write from any thread. But it doesn't prevent race conditions.

   
   
   

   Your code, a thread performs a read to test if a seat is free followed by a write to reserve it. That sequence is not atomic. Nothing prevents another thread from "grabbing the seat" in between this thread's read and write.

   
   

Unfortunately, the only way to guarantee that your code doesn't have this kind of problem is to perform a formal analysis (i.e. construct a mathematically sound proof) starting from the specified semantics of the Java Memory Model¹. This is difficult. Hence, the normal recommendation is to use the standard building blocks provided by the java.util.concurrent, java.util.concurrent.atomic and java.util.concurrent.locks packages.

^{1 - If you understand the JMM, an informal analysis may be acceptable ...}