CODEWITHSUNDEEP
javamultithreading
Daniel
Daniel

Reputation: 7724

How to avoid threads to starve

Suppose I have a hotel with m Rooms.

Guests (Threads) come in and out the whole time.

A Room can have lots of people inside, but only one Room will have people. For example:

How can I implement this somehow the threads will not starve?

For simplicity, suppose that, once the Guest comes inside a room, it sleeps for some seconds and then get out. Here is my (wrong) implementation:

import java.util.ArrayList;
import java.util.Random;

public class Guest extends Thread {
    static Rooms rooms = new Rooms(5);

    int id;

    Guest(int id) {
        this.id = id;
    }

    public void run() {

        rooms.join(this);

        nap();

        rooms.quit(this);
    }

    public void nap() {
        try {
            sleep((new Random().nextInt(4000) + 1000));
        } catch (InterruptedException e) {
        }
    }

    public static void main(String[] args) throws InterruptedException {

        for (int i = 0; i < 20; i++) {

            Thread t = new Guest(i);
            t.start();

            Thread.sleep((long) new Random().nextInt(1500) + 1000);

        }

    }

}

class Rooms {

    Room[] rooms;
    int busy;

    Rooms(int m) {
        busy = -1;
        rooms = new Room[m + 1];
        for (int i = 0; i < m + 1; i++)
            rooms[i] = new Room();
    }

    void join(Guest h) {
        if (busy == -1) {
            busy = (new Random().nextInt(rooms.length));
        }

        rooms[busy].add(h);

        System.out.println("Guest " + h.id + " came inside room " + busy + " with " + rooms[busy].size() + " people");
    }

    void quit(Guest h) {

        if (rooms[busy].size() == 1) {
            setHandler(busy, h);
        } else {
            rooms[busy].remove(h);
            System.out
                    .println("Guest " + h.id + " came out of room " + busy + " with " + rooms[busy].size() + " people");
        }

    }

    synchronized void setHandler(int numQuarto, Guest ultimo) {
        System.out.println("(Last) Guest " + ultimo.id + " came out of room " + busy + " with "
                + rooms[numQuarto].size() + " people");
        rooms[numQuarto].remove(ultimo);
        busy = -1;
    }

}

class Room extends ArrayList<Guest> {
}

Upvotes: 2

Views: 921

Answers (2)

ChiefTwoPencils
ChiefTwoPencils

Reputation: 13930

You can't. Based on what you've given, other mechanisms would need to be implemented which guarantee no starvation can occur. For example,

Guests (Threads) come in and out the whole time.

So, it's possible that n threads come in for Room m possibly the whole time. It's possible, too, that during that time more threads come in wanting another room. However, they cannot access the room until Room m is first emptied (which may never actually happen). This can continue for any number of rooms and threads. This is the case even if...

For simplicity, suppose that, once the Guest comes inside a room, it sleeps for some seconds and then get out.

And that's because...

C can go to Room 1, because the Room C wants is the only Room with people inside;

Which implies that another thread may enter an already occupied room with one or more threads with t time left to sleep. The new thread goes to sleep and won't wake up until after the previous one. While sleeping n more threads may enter the room potentially causing other threads waiting for other rooms to starve.

Upvotes: 1

John Bollinger
John Bollinger

Reputation: 180181

To do this with threads -- which is highly artificial, but I suppose it is an exercise -- you need to learn how to make a Thread wait on a condition, and how to notify one or more Threads that the condition they are waiting for may have been satisfied. Conveniently, every object has methods wait(), notify(), and notifyAll() that serve these purposes.

One important consideration with wait / notify is that you must be careful to wait on and notify the correct object. Generally, that's not the Thread you want to be affected, but rather some shared object that all threads involved rely upon for mutual synchronization. In this particular case, it looks like Guest.rooms would do nicely.

The general idea would be that in Rooms.join(), the current thread tests whether it can immediately take a room. If so, it does, and continues as now. If not, however, it invokes wait() (on the Rooms instance, which at that point is this). Whenever that wait() returns, the thread must again check whether it can immediately take the room it wants; if not, it must wait again.

The other half would be in Rooms.quit(). Whenever a thread running that method is the last one out of the room, it must reset busy to indicate that no room is occupied, and then, importantly, invoke notifyAll() to let all threads waiting at that time know that there's a chance to get a room.

You will find that you need to employ proper synchronization for this. In particular, you can invoke wait() and notifyAll() (and notify()) only while holding the monitor of the target object (it will be released for the duration of the wait, and reacquired before wait() returns). You will also need to ensure that you properly synchronize all manipulation of shared objects, however, in this case mainly the Rooms and its members, without preventing threads from proceeding when otherwise they could. In particular, be aware that threads that sleep() do not for that reason release any monitors they may hold.

The rest is up to you. I've given you rather a lot more of a hint than maybe I should, but it truly is a bit tricky to learn how to use wait / notify properly.

Upvotes: 1

Related Questions