need help making this simulation program in java here are di

need help making this simulation program in java: here are directions.

Threads and Synchronization

Whenever we have multiple entities working together to get something done, we have the problem of synchronization between the entities. Processes working together, or threads in one or many processes working together need tools to protect critical sections and to signal one another when important events occur. Java provides thread and synchronization mechanisms which programmers can use to coordinate their activities. The following problem requires that many threads coordinate their activities to assure that the program runs correctly.

A university wants to demonstrate its political correctness by applying the Supreme court’s “Separate but equal is inherently unequal” doctrine to gender as well as race. As such, it has decided that both genders will use the same bathroom facilities (ie. a unisex lounge). However, in order to preserve some tradition, it decrees that when a woman is in the lounge, only other women may enter, and when a man is in the lounge, only other men may enter. Each unisex lounge will have a sign on the outside indicating what state the lounge is in; Empty, Women Present, or Men Present.

Your job is to implement a multi-threaded simulation of this unisex lounge. You may use whatever counters and synchronization mechanisms you need to make sure that your unisex lounge works according to the university decree.

Your implementation must generate some status report whenever anyone enters or leaves the lounge which should include the sex of the person entering or leaving. This status report should include the state of the lounge, the number of men and/or women waiting, and the number and sex of the occupants currently in the lounge.

Once a person (thread) enters the lounge, that person’s stay in the lounge should be determined by a random number. The minimum stay should be 2 seconds, and the maximum stay should be 5 seconds.

Once a person (thread) has left the lounge, use random numbers to determine when that thread will try to gain access again. I suggest that the wait should range from 4 seconds to 10 seconds.

Your program should start 5 male threads and 5 female threads. Each thread should visit the lounge 10 times. Analyze the output to make sure things are working correctly.

Copy all your source code into one text document. Create a zip file of your project. Submit those two files to the appropriate drop box.

Basic Program Structure for USL (UniSex Lounge)

USL Class

            This class really does all the work of synchronizing access to the USL. The first question to ask is what information does the USL need to keep. The USL has a state, which reflects if it is empty, or if there are males or females inside. It also must keep track of the number of occupants which are inside, and the number that are waiting to get inside. There can be males or females inside or waiting.

            The USL must also have a means of blocking a thread which is trying to gain access if the state of the USL does not permit access for this thread at this time. In order to block a thread, the USL can use the wait method which will be used to block threads which must wait until the state of the USL permits access. The USL should keep a counter which indicates how many males or females are blocked waiting to get into the USL.

            Since the USL has multiple member variables which must be read and written by multiple threads, we must synchronize access to these member variables by making the methods of this class synchronized methods.

            The constructor for the USL class must initialize all member variables including all the state and counter variables.

            There should be a maleEnters( ) and a femaleEnters( ) method. These methods check the state to see whether the male or female thread is allowed to enter or must be blocked. Remember, reading and/or writing the member variables must be done inside a critical section which is protected by the synchronized methods. State and/or counter variables must be updated appropriately. If the male or female must wait to enter, the wait method is used to block the thread. When a waiting thread is awakened, it must recheck the state to make sure that it is safe to enter. If the lounge is still in the wrong state, the thread must wait again. Returning from one of these methods indicates that the thread was successful in entering the USL.

            There should also be a femaleExits( ) and a maleExits( ) method. These methods update the counter and state member variables appropriately. If the thread exiting the lounge is the last one out, the state member variable must change, and any waiting threads must be unblocked so that they can attempt to enter again. The notifyAll method can be used to wake up all the threads which are blocked waiting to get into the USL.

            Remember that something in your simulation must output the state and counter info frequently, or whenever any thread enters or exits the USL. The easiest way to do this is to have a display method in the USL class and call it from inside the enter and exit methods.

MaleThread and FemaleThread Classes

These classes contain the code that simulates the actions of a male or female thread entering and exiting the USL. These two classes can either inherit from the Thread class or implement the Runnable interface. The constructor for these two classes should accept a USL object so that all the male and female threads are using the same USL object. The run method of these two classes should contain a loop which executes 10 times. Inside the loop, a thread would sleep for a random amount of time between 4 and 10 seconds, and then call the appropriate entry method on the USL. Once that method returns, the thread has gained access to the USL and should wait for between 2 and 5 seconds before calling the appropriate exit method on the USL object.

Main Test Program

            This program controls the simulation. The main program must create a USL object to be used by the male and female threads. It must also create 5 MaleThread objects and 5 FemaleThread objects and start all the male and female threads executing.

            It is up to you how to display the output from your simulation. You can use a console window and report status every time a thread enters, starts waiting, stops waiting, or exits the USL object. Or, you can use a simple GUI and use a separate thread to periodically (every 100 msec) update a display that shows in some way the threads that are in the USL or that are waiting to get in and whether they are male or female threads.

Solution

The next step after partitioning the network is to choose a synchronization algorithm, which is the guarantee that the simulation is run in a deterministic and consistent manner. What needs to be ensured is a simple but strict ordering on the dates of the events processed on each node of the network. Thus, the synchronization algorithm task is to define, at each iteration, the maximum date up to which each partition clock (separately) can advance during the iteration, so that the ordering constraint is respected. Two main kinds of synchronization algorithms exist : conservative and optimistic algorithms. Conservative algorithms take the approach that the best thing to do to handle desynchronization is just to avoid it, so that such algorithms strictly enforce the ordering constraint. The downside of this approach is that it can lead to situations where only a few events are processed on each execution unit during each iteration of the algorithm, so that the overhead of the algorithm cannot even be balanced by the speed improvement brought by parallelization. On the opposite, optimistic algorithms assume that the desynchronization points are rare and that the gain of letting the executions units process events at full speed is well worth the cost of interrupting the simulation sometimes and fixing consistency errors. The main problem with the optimistic approach is that it is hard to implement. Three paths can be used to do the recovery : • Ask the users to provide an Undo function matching each event they define, function which will be used to revert all the events that lead to the consistency faults. This approach is definitely not possible since it really intrusive and would require deep rework of the currently existing models codebase. • Write a specific compiler which would produce the Undo functions : this is more than non-trivial and probably really hard to implement. • Frequently take snapshots of the status of the whole network (which mostly means taking snapshot of the whole simulator memory) and restore them if anything goes wrong. This is most likely a very expensive approach time-wise and memory wise (because of the need to backup the whole memory) and finding the right frequency at which snapshots should be taken is a non trivial problem (the cost of taking the snapshots has to be balanced with the cost of the work to redo when the simulation goes wrong). Consequently, we chose to use conservative synchronization algorithms. While working on this project, we have implemented two algorithms : the Chandy-MisraBryant algorithm and a synchronization-barrier-based variant. Algorithm basic shape The basic shape of the simulator execution main loop is the following : while simulation not finished: for each partition P: P.max_date = synchronization_algorithm (P) for each partition P: for each event message M: append M.event to P events queue while P.next_event_date < P.max_date: process (P.next_event) We note here the use for each partition of a queue of incoming event messages, which are messages sent from neighboring partitions when they schedule an event on the current partition (most likely a packet receive event scheduled through a channel). The two iterations on the partitions set can be easily parallelized, for instance by having a global thread-safe shared list of partitions from which each thread picks partition until the list is empty, at which point one of the threads refills it. 2.2.1 Chandy-Misra-Bryant algorithm The Chandy-Misra-Bryant synchronization algorithm ([Chandy and Misra, 1979], [Bryant, 1977]) is a classic, well-known, algorithm which has been studied and used for all kinds of parallel applications. This algorithm is based on the notion of lookahead, which is the minimum transmission delay from one partition to another. At a given iteration, the maximum date up to which the events of a partition can be processed is defined as the maximum date before events created from neighboring partitions may have to be processed. Since the events created from neighboring partitions have to go through a transmission channel, the computation of this maximum date just means computing the minimum of, for each neighboring partition, the neighboring partition clock + the lookahead from the neighboring partition to the current partition. The correctness of the algorithm is quite obvious : since during a given iteration the events which can be processed are those which date is strictly lower than the minimum date of any event that could be scheduled from outside the partition, the simulation is guaranteed to be consistent. The communication between the partitions is made using null-messsages : when a partition has finished processing its events, it sends such a message to the neighboring partition, telling them about the new value of the partition clock. Before computing the new maximum date of a given partition, the synchronization algorithm first processes those messages, updating a 3 local memory of the neighboring clocks, which is then used for the computation. Thus, the synchronization algorithm is : synchronization_algorithm (P): for each stored null-message M: P.neighbor_clock[M.sender] = M.clock max_date = for each partition P2 in P neighborhood: max_date = min (max_date, P.neighbor_clock[P2] + P.lookahead[P2]) return max_date A little trick which is required for this algorithm to work is that each partition clock has to be set to the maximum date at the end of the iteration to be able to solve cases where would be no event in the time frame [clock, max_date[, which may eventually lead the simulation to a state where all the partitions are waiting for a single partition which has no event scheduled until a date relatively far in the future and which clock is frozen because it cannot advance using the events. This algorithm, yet being quite simple, suffers from two design issues. 0-lookahead cycles The first issue arises when an oriented cycle of partitions with 0 lookahead links between them. Since each partition can advance up to the clock of the previous partition in the cycle + 0, and since it is a cycle, all the clocks are bound to remain 0 forever. Obviously, a cycle of partitions with 0 lookahead is not physically feasible, a lookahead of 0 could be used as an approximation in some models where computing the real value or a non-0 approximate would be too expensive. Such situations could probably be broken by some tricky heuristics, that is, by advancing the clocks manually according to the other neighboring clocks and if a tie exists between events (if two events were scheduled for the same date on two partitions of the cycle) decide which event to process first according to an extra parameter, such as the lowest partition identifier, but this would make the algorithm way more complicated and would heavily increase the synchronization overhead (detecting that the problem exists would probably be even more expensive than fixing it). Cost of the null-messages process The second issue is that the time advance of the algorithm is bound to the use of the null-messages. That is, if the maximum lookahead is L, the simulation will only advance of L time-wise at each iteration. Let’s imagine that between the dates 0 and T there is no event for any of the n nodes of the network. To advance to the first event it will take T /L iterations and n T /L null-messages. For 1000 nodes, T = 1s and L = 10ms, this means 100 iterations and 100000 null-messages for no actual simulation work. Even in less specific situations, the fact that advancing the simulation time is expensive when there is no event is a real performance issue which cannot be balanced by the use of multiple cores. 2.2.2 Barrier-based algorithm Both problems of the Chandy-Misra-Bryant algorithm are related to the fact that only the clocks of the partitions are taken into account, and not the actual events waiting to be processed. Thus, a smarter algorithm is to compute a global maximum date based on the next event of each partition and the minimum lookahead from this partition to the neighboring partitions. Note that the meaning of the lookahead is the opposite of its meaning in the Chandy-Misra-Bryant algorithm, where the lookahead was the minimum transmission delay from the neighboring partition to the current one. This algorithm, described in [Fujimoto, 2000], is based on synchronization barriers, which are meeting points which all threads must reach before any of them can continue. The idea is that at each iteration all the threads reach such a barrier, then one or all of them compute the global maximum date as specified above, then they all reach another barrier, then they do the events processing. Here is how an iteration of the algorithm looks, codewise : wait at barrier if thread_id == 0: max_date = for each partition P: max_date = min (max_date, P.next_event_message.date + P.lookahead, P.next_event.date + P.lookahead) wait at barrier for each partition P: for each event message M: append M.event to P events queue while P.next_event_date < max_date: process (P.next_event) This algorithm definitely solves both problems of the Chandy-Misra-Bryant approach : no CPU time is spent on advancing the clock without doing any actual work, and the 0-lookahead cycles problem is solved since the computation of the maximum date ensures that at least the event with the minimum date of the whole simulation will be processed. The correctness of the algorithm is once again quite simple : for each partition, the maximum date is defined as at most the minimum date at which an event may be scheduled on a neighboring node, so it ensures that each partition will not lead to a consistency problem. Thus, the algorithm is correct.