代写program、代做Java编程语言
Project 5: A Concurrent MBTA Simulator
1/7
Due No Due Date Points 100
Test case due 11:59pm ET on Wed, Nov 29
Project due 11:59pm ET on Mon, Dec 11
Code Skeleton
Here is the code skeleton: p5.zip (files/?wrap=1)
(files/download?download_frd=1)
You may only modify MBTA.java , Sim.java , Verify.java ; the replayAndCheck methods of BoardEvent ,
DeboardEvent , and MoveEvent ; the make methods of Train , Station , and Passenger ; and add new
classes. You may not modify any other .java files in the code skeleton or any other methods of the
three Event classes.
Introduction
Object-oriented programming was pioneered by the Simula (https://en.wikipedia.org/wiki/Simula)
programming language, which was designed for doing simulations. Object-orientation is useful for many
different kinds of programming, but for this project you will go back to basics and implement a simulation
using Java. More specifically, you will implement a multi-threaded simulation of the T. In your simulation,
passengers will ride trains between stations, boarding and deboarding (getting on and off) to complete
their journey. Your simulation will generate a log showing the movements of passengers and trains, for
example:
$ ./sim sample.json
Passenger Alice boards red at Davis
Passenger Bob boards green at Park
Train green moves from Park to Government Center
Train red moves from Davis to Harvard
Train red moves from Harvard to Kendall
Train green moves from Government Center to North Station
Train green moves from North Station to Lechmere
Train green moves from Lechmere to East Sommerville
Passenger Alice deboards red at Kendall
Train green moves from East Sommerville to Tufts
Passenger Bob deboards green at Tufts
Your simulation will be multi-threaded, with a thread for each passenger and each train. That means if
you run the simulation multiple times, you may get different results depending on the scheduler! To make
Project 5: A Concurrent MBTA Simulator Project 5: A Concurrent MBTA Simulator
2/7
testing and debugging easier, you will also build a verifier that checks that the simulation result is
sensible, e.g., passengers can only deboard trains at the stations the trains are at, trains must move
along their lines in sequence, etc.
Building and Running the Code
This project uses JSON. For convenience working with JSON, we have included Gson
(https://github.com/google/gson) , a library for working with JSON in Java. Since we're doing that, we've
also thrown in JUnit for testing. To keep things simple, rather than provide a full-fledged build system,
we've instead provided several scripts:
./build - run javac *.java with Gson and JUnit in classpath
./sim config_filename - run java Sim config_filename with Gson in classpath
./verify config_filename log_filename - run java Verify config_filename log_filename with Gson in
classpath
./test test_classname - run java org.junit.runner.JUnitCore test_classname with Gson and Junit in
classpath
You may alternatively add the appropriate jar files to your CLASSPATH and not use these scripts. To see
what to add to your CLASSPATH, look inside of the scripts ( build , sim , etc), which are just text files
containing shell code. If you are using an IDE, you'll need to figure out how to modify the CLASSPATH in
the IDE.
Part 1: Simulation Con??guration
The input to the simulation describes the initial configuration: the set of train lines and the set of
passenger journeys. For this project, that input will be specified in JSON
(https://en.wikipedia.org/wiki/JSON) . For example, here is sample.json , a sample configuration included
with the project:
{
"lines": {
"red": [ "Davis", "Harvard", "Kendall", "Park", "Downtown Crossing",
"South Station", "Broadway", "Andrew", "JFK" ],
"orange": [ "Ruggles", "Back Bay", "Tufts Medical Center", "Chinatown",
"Downtown Crossing", "State", "North Station", "Sullivan" ],
"green": [ "Tufts", "East Sommerville", "Lechmere", "North Station",
"Government Center", "Park", "Boylston", "Arlington", "Copley" ],
"blue": [ "Bowdoin", "State", "Aquarium",
"Maverick", "Airport" ]
},
"trips": {
"Bob": [ "Park", "Tufts" ],
"Alice": [ "Davis", "Kendall" ],
"Carol": [ "Maverick", "State", "Downtown Crossing", "Park", "Tufts" ]
}
} Project 5: A Concurrent MBTA Simulator
3/7
The top-level is a JSON object (JSON terminology for a map) with keys lines and trips . The key
lines maps to another JSON object, which maps train names (there is only one train per line in this
simulation) to a list of station names. The key trips maps passenger names to a list of station names.
The rules for the simulation will be described fully below.
For the first part of the project, you will work with the classes Train , Station , and Passenger , instances
of which represent the corresponding entities, and class MBTA , which represents the state of the
simulation.
First, taking a brief trip back to the land of design patterns, implement the following methods:
Train.make(String name) , Station.make(String name) , and Passenger.make(String name) . These
factory methods should return instances of the corresponding classes, where if one of these
methods is called multiple times with the same name, it must always return the same object.
For example, Train.make("red") == Train.make("red") (note the physical equality test). Thus, you'll
need to implement some kind of caching. You have a few choices about exactly how to design the
caching; we'll leave those choices to you, and we'll only test for functionality.
Second, implement the following methods (you will need to add fields to MBTA , plus another class, as
described below):
MBTA#addLine(String name, List stations) - Add a new train line to the simulation, where
name is the name of the line and stations is an ordered list of stations on the line. This method will
be handy for writing test cases.
MBTA#addJourney(String name, List stations) - Add a new passenger journey to the
simulation, where name is the name of the passenger and stations is an ordered list of stations the
passenger wants to visit. This method will be handy for writing test cases.
MBTA#reset() - Reset the MBTA state so it contains no lines and no journeys. Again, this method will
be handy for writing tests.
MBTA#loadConfig(String filename) - Load a JSON simulation configuration (as specified above),
adding the lines and journeys listed in the JSON file. Let's discuss how to do this next. This will take a
lot of words, but you won't actually have to write much code.
To load the JSON configuration file, you will definitely want to use the class Gson
(https://www.javadoc.io/doc/com.google.code.gson/gson/latest/com.google.gson/com/google/gson/Gson.htm
, specifically one of the fromJson methods. You can use any of them that work, but here's our
suggestion. The Gson library's key feature is that it can take any Java object and turn it into a JSON
string, and vice-versa. For example, consider the following code (included in the code skeleton):
public class C {
public List l;
public Map m;
public static void main(String[] args) {
Gson gson = new Gson();
C c = new C();
c.l = List.of("a", "b", "c"); Project 5: A Concurrent MBTA Simulator
4/7
c.m = Map.of("k1", "v1", "k2", "v2");
String s = gson.toJson(c);
System.out.println(s);
C c2 = gson.fromJson(s, C.class);
System.out.println(c2.l);
System.out.println(c2.m);
}
}
This code first creates an instance of C and then converts it to a JSON string. The first print statement
produces:
{"l":["a","b","c"],"m":{"k2":"v2","k1":"v1"}}
Then, the code uses one form of fromJson to take that string and produce a C from it. Notice that the
JSON parser needs to know what kind of object to produce, so we pass the type of the object, in this
case C.class , to fromJson . The last two lines print out the fields of c2 to show they are correct.
To implement MBTA#loadConfig , look at the JSON type for simulation configurations and then create a
new class that, when turned into JSON, will look exactly like the configuration format. You can
experiment with this by using toJson to look at how your new class is encoded. Once you have the right
class, all you need to do is call fromJson and, magically, you'll be able to turn an on-disk JSON file into
an in-memory representation! Once you have the in-memory representation, you can then traverse it and
call addLine and addJourney as appropriate to set up the simulation.
If you want to see a worked-out example of this, you can look in classes Log and LogJson , which
include code to turn simulation logs (discussed below) to and from JSON. Note that process is more
complicated than what you'll need to do for configurations. So the code you have to write will be much
simpler than the code for logs.
Part 2: Verifying Simulation Output
The next part of the project is to write a verifier that, given the initial configuration and a log of a
simulation, ensures that the log follows all the simulation rules. We've already built the basic logging
infrastructure for you. The class Log stores a List , where an Event is one of the following three
classes:
MoveEvent(Train t, Station s1, Station s2) - Train t moves from s1 to s2
BoardEvent(Passenger p, Train t, Station s) - Passenger p boards t at s
DeboardEvent(Passenger p, Train t, Station s) - Passenger p deboards t at s
Your job is to implement:
MoveEvent#replayAndCheck(MBTA mbta) , BoardEvent#replayAndCheck(MBTA mbta) , and
DeboardEvent#replayAndCheck(MBTA mbta) - Check that the change indicated by the event is valid. If
not, raise an exception (any exception). If it is valid, modify mbta so that the change indicated by the Project 5: A Concurrent MBTA Simulator
5/7
event is incorporated into it. For example, if train green is at Tufts and the event is
MoveEvent(green, Tufts, East Sommerville) , then the event is valid (no exception raised), and after
the method returns, green will now be at East Sommerville .
MBTA#checkStart() and MBTA#checkEnd() - Check that the simulation is in the correct initial and final
states, respectively, and raise an exception (any exception) if not.
We've already written the following code in class Verify to use these methods to verify a log against a
configured MBTA :
public static void verify(MBTA mbta, Log log) {
mbta.checkStart();
for (Event e : log.events()) {
e.replayAndCheck(mbta);
}
mbta.checkEnd();
}
The simulation is initially configured with a set of lines (e.g., Red, Green, Blue, Orange), each of which
has an ordered list of stations (e.g., Davis, Porter, Harvard, Central, Kendall). Stations are identified by
names, and if the same station name is on two lines, that's considered just one station. You can assume
all lines, stations, and passengers are named uniquely within their respective groups (but not necessarily
across groups, e.g., a passenger could have the same name as a train). There is exactly one train on
each line, whose name is the same as the line. The initial configuration also includes a set of
passengers, each of whom has a journey they want to take (e.g., Alice wants to go from Kendall to
Davis).
Here are the rules your verifier needs to check:
1. At the start of the simulation,
a. Each train starts at the first station in the line's ordered list of stations.
b. Each passenger starts at the initial station of their journey.
2. Trains move along their line until they reach the end, at which point they change direction and
follow the line in reverse until they reach the beginning of the line, then go forward on the line, etc.
Trains never skip stations.
3. At most one train can be at a station at a time. Trains may not be in-between stations; they must
wait to leave their current station until the station they are moving to is available. Trains and
stations can hold an unbounded number of passengers. You can assume the initial configuration
does not place two trains at the same station.
4. A passenger can only board a train that is at the same station as the passenger; they can only
deboard a train at the station it is currently at.
5. A passenger exits from a train only if they have arrived at the next station on their journey. You can
assume that passenger journeys include all the necessary stops to change lines, e.g., if a
passenger wants to go from Maverick to Tufts , they journey will probably be Maverick , State ,
Downtown Crossing , Park , Tufts . Project 5: A Concurrent MBTA Simulator
6/7
6. The simulation ends when all passengers have arrived at their final stops. It is an error for the
simulation to end early. It is fine if trains run a bit past the point where all passengers have finished
their journeys.
7. You can assume all specified passenger journeys are possible on the given set of lines. You don't
need to check if the journeys themselves are sensible.
Here are a few tips about how your verifier will be graded:
You should store the simulation state in MBTA and not elsewhere. The autograder assumes that it can
create multiple instances of MBTA and they will not interfere with each other.
MBTA#reset will not be called between runs testing the verifier.
The autograder may call MBTA#addLine etc directly to set up the simulation rather than using a
configuration file.
Part 3: The Simulation
Finally, you must implement the simulation. More specifically, implement
Sim#run_sim(MBTA mbta, Log log) - runs the simulation starting with the already configured mbta ,
logging events using log .
and
In design.txt , briefly explain how your simulation uses threads and locks. The purpose is to give the
TAs a quick overview of your code so that they can easily check that you followed the rules below. It
is not necessary to write a lot of text.
Your simulation must obey the rules checked by the verifier, plus the following rules:
Your simulation must use the following methods to log events as trains and passengers move:
a. log.train_moves(Train t, Station s1, Station s2) when train t leaves station s1 and enters
station s2 .
b. log.passenger_boards(Passenger p, Train t, Station s) when passenger p boards train t at
station s .
c. log.passenger_deboards(Passenger p, Train t, Station s) when passenger p exits train t at
station s .
There methods will both store the event in the log and print the event to the console (and flush the
output after doing so). The second part will be useful if your simulation deadlocks.
Use multiple threads in the simulation. More specifically, each passenger and each train should have
a corresponding thread. You may use additional threads as well, but no fewer.
When a train moves to a new station, it should stay at that new station (i.e., not attempt to move) for
10 milliseconds (call Thread.sleep ). The train thread should not hold a lock while the train is
waiting at the station! Project 5: A Concurrent MBTA Simulator
7/7
Do not use a single global lock. You should aim to let passengers and trains move as
independently as possible, though of course there will be some mutual exclusion to ensure there are
no data races. You may assume that the simulation configuration does not itself cause deadlocks (for
example, a cycle in the station map such that trains are all waiting for each other to move before they
can move).
Avoid data races. Your code should not have any.
Do not use busy waiting or spinning. You will want to use await/signalAll , wait/notifyAll , or
classes from java.util.concurrent
(https://docs.oracle.com/en/java/javase/20/docs/api/java.base/java/util/concurrent/packagesummary.html)
instead. For example, you can have passengers that are at a station await for a train
to arrive, and when the train arrives, it can signalAll < those waiting for the train. Training can also
await for a station to become available, and when a train leaves it can signalALl to indicate the
station is now available.
It is possible that a passenger might miss their train, even if it arrives at their station, or might miss
their stop. In these cases the passenger remains at the station or on the train, respectively.
You maybe use ReentrantLock and/or the synchronized keyword and/or data structures from
java.util.concurrent .
In class Sim , we've already written a useful main method for you that uses loadConfig (part 1) to set up
the initial conditions; calls run_sim (part 3); writes the resulting log file to disk as log.json ; and then
runs verify (part 2) on the result to check that all the rules are followed. You can run this main method
from the command line using the command ./sim config_filename . If you want to run the verifier
separately on the saved log.json , you can run the command ./verify config_filename log.json . Note
that log.json gets overwritten each time you run the simulation, so be sure to save a copy somewhere
else if you need it.
Part 4: Test Cases
We've given you a script ./test test_classname you can use to run JUnit tests in the given class (and
we've given you a class Tests with a trivial test inside it). For this project, you must write at least one
test case for Part 2 (the verifier), only, and share it on the class web forum. You can use the
methods in MBTA and Log to create an initial configuration (without using JSON, even) and sample log,
and then directly call Verify#verify to check that the verifier passes (returns normally) or throws an
exception, depending on the test.