Operating System代写：ECS60 Railway Network

发表于   |   分类于

Introduction

代写一个铁道网络系统的小程序，练习操作系统相关的库函数用法。

You are to write an efficient program that will determine the best route for a train to pick-up and deliver railroad cars on a large railway network. You may add any classes and/or code you wish to train.cpp and train.h. You will find CPUTimer.h, TrainRunner.cpp, TrainRunner.h, a barebones train.h, a barebones train.cpp, a barebones Makefile, my executable called train.out, CreateRoute.cpp, and CreateRoute.out which creates the station files.

Further specifications

  1. The program should terminate once all cars are delivered to their destinations.
  2. The program takes a station file as its only parameter. The names of the files have the format.
  3. The problem files contain a list of stations, in ID order, with their adjacent stations, and distances to them. The list of stations is followed by a list of cars, in ID order, with their origin station ID, and destination station ID. main.cpp takes care of reading the file.
  4. There is one train which can hold up to 50 cars, and starts at station 0.
    4.1. The train can move from one station to an adjacent station in exactly one simulated time unit for every mile of distance between them.
    4.2. Picking up and delivering cars do not take any time.
  5. Your program’s solution will be stored in an array of Operations.
    5.1. It is up to your Train class to maintain simulated time.
    5.2. For train movement an entry will be [time] ‘M’ [station_ID]. The [time] is the simulated time of arrival at the specified station. Train movement entries must be listed before any other activity at the same time.
    5.3. For car pick-up an entry will be [time] ‘P’ [car_ID]
    5.4. For car delivery an entry will be [time] ‘D’ [car_ID]
  6. checkOperations() analyzes your operations and checks it for any mistakes.
    6.1. Among the errors checked:
    6.1.1. Movement between non-adjacent stations.
    6.1.2. Time of movement between adjacent stations is not correct.
    6.1.3. Pick-up of a car at a station that is not its origin.
    6.1.4. Delivery of a car at a station that is not its destination, or delivery of a car that is not on the train.
    6.1.5. Train having more than 50 cars.
  7. Grading is based on total simulated time, and actual CPU time.
    7.1. TrainRunner.cpp, TrainRunner.h, and CPUTimer.h will be copied into your directory.
    7.2. Though numOperations is printed, it is just for information purposes, and is not graded.
    7.3. The programs will be tested with three files with 20000 stations, and 8000 cars, and the results totaled.
    7.4. Programs must be compiled without any optimization options. You may not use any precompiled code, including the STL and assembly. Other than Weiss files, you must have written all of the code you submit.
    7.5. If there are ANY error messages, then the program will receive zero.
    7.6. CPU Time score = min(30, 25 * Sean’s CPU Time / Your CPU Time)
    7.7. Simulated Time score = min(30, 25 * Sean’s Simulated Time / Your Simulated Time)
  8. Suggestions
    8.1. Since the stations array is deleted before you get the actual cars, you will need to copy it in some way. If you just want to copy it, memcpy() is very fast.
    8.2. Start early, and get something working without errors.
    8.3. Don’t fuss about speed or simulate time until you have something working. Too many students fail to have a correct program by the deadline because they spend too much time tweaking early on. You will learn a lot just getting it running. Then you can use this knowledge to improve your code.
    8.4. To debug, add if-statements that are only true during the state in which you are interested.
    8.5. Leave lots of time for testing and debugging. Test with all of the available files.
    8.6. Here is a sample handin command: handin cs60 p5 Makefile authors.csv *.cpp *.h

Example

$ CreateRoute.out
stations (5 -): 5
cars: 3
seed: 1

$ cat st-5-3-1.txt
5 3
0 4 3 397 2 2039 4 731 1 2635
1 3 2 1436 0 2635 3 3032
2 4 1 1436 0 2039 3 2436 4 2770
3 4 4 334 0 397 2 2436 1 3032
4 3 3 334 0 731 2 2770
0 2 0
1 4 3
2 1 0

$ train.out st-5-3-1.txt
CPU Time: 0.00029 Simulated time: 7572 numOperations: 11

$ train.out st-20000-8000-5.txt
CPU Time: 0.649742 Simulated time: 4371992 numOperations: 206655

Sample Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Operation {
public:
  int time;
  char operation; // 'M', 'P', or 'D'
  short ID; // CarID or StationID
  Operation(int t = 0, char o = 'M', short ID = 0) : time(t), operation(o), ID(ID) {}
}; // class Operation

class Station {
public:
  int adjacent[10];
  int distances[10];
  int adjCount;
  Station():adjCount(0){}
};

class Car {
public:
  int origin;
  int destination;
  Car(int orig = -1, int dest = -1) : origin(orig), destination(dest) {}
}; // class Car

int main(int argc, char* argv[]) {
  CPUTimer ct;
  Station *stations, *stations2;
  Car *cars, *cars2;
  Operation *operations = new Operation[1000000];
  int numCars, numStations, numOperations;
  readFile(argv[1], &stations, &stations2, &cars, &cars2, &numStations, &numCars);
  ct.reset();
  Train *train = new Train(stations, numStations, numCars);
  delete [] stations;
  train->run(cars, operations, &numOperations);
  double time = ct.cur_CPUTime();
  int simulatedTime = checkOperations(operations, numOperations, cars2, stations2, numCars, numStations);
  cout << "CPU Time: " << time << " Simulated time: " << simulatedTime << " numOperations: " << numOperations << endl;
  return 0;
} // main()