CSc -Programming Assignment 2 (P2) Multi-Thread Scheduling (MTS) Solution

12

13

14

1. threads

2. mutexes

3. condition variables (convars)

15. to do so. Your goal is to construct a simulator of an automated control system for the railway track shown in Figure 1

15. (i.e., to emulate the scheduling of multiple threads sharing a common resource in a real operating system).

15. As shown in Figure 1, there are two stations (for high and low priority trains) on each side of the main track. At

15. each station, one or more trains are loaded with commodities. Each train in the simulation commences its loading

15. process at a common start time 0 of the simulation program. Some trains take more time to load, some less. After

15. a train is loaded, it patiently awaits permission to cross the main track, subject to the requirements specified in

15. Section 2.2. Most importantly, only one train can be on the main track at any given time. After a train finishes

15. crossing, it magically disappears. You will use threads to simulate the trains approaching the main track from two

15. different directions, and your program will schedule between them to meet the requirements in Section 2.2.

15. You will use C or C++ and the Linux workstation in ECS242 or ECS348 or the linux.csc.uvic.ca cluster to

15. implement and test your work.

15. 2 Trains

15. Each train, which will be simulated by a thread, has the following attributes:

15. 1. Number: an integer uniquely identifying each train.

east−bound	West	East	west−bound
high−priority			high−priority
west−bound			east−bound
		main track
east−bound			west−bound
low−priority			low−priority

Figure 1: The railway system under consideration.

1

29

30

31

32

33

34

2. Direction:

2. • If the direction of a train is Westbound, it starts from the East station and travels to the West station.

2. • If the direction of a train is Eastbound, it starts from the West station and travels to the East station.

2. Priority: The priority of the station from which it departs.

2. Loading Time: The amount of time that it takes to load it (with goods) before it is ready to depart.

2. Crossing Time: The amount of time that the train takes to cross the main track.

35. Loading time and crossing time are measured in 10ths of a second. These durations will be simulated by having

36. your threads, which represent trains, usleep() for the required amount of time.

35. 2.1 Step 1: Reading the input file

35. Your program (mts) will accept one parameter on the command line:

35. • The parameter is the name of the input file containing the definitions of the trains.

35. 2.1.1 Input file format

35. The input files have a simple format. Each line contains the information about a single train, such that:

42

43

44

45

46

47

48

49

50

1. The first field specifies the direction of the train. It is one of the following four characters:

e, E, w, or W

e or E specify a train headed East (East-Bound): e represents an east-bound low-priority train, and E represents an east-bound high-priority train;

w or W specify a train headed West (West-Bound): w presents a west-bound low-priority train, and W represents

a west-bound high-priority train.

2. Immediately following is an integer that indicates the loading time of the train.

2. Immediately following is an integer that indicates the crossing time of the train.

2. A newline (\n) ends the line.

51. Trains are numbered sequentially from 0 according to their order in the input file. You need to use strtok() to

52. handle the line. More efficiently, you can use fscanf()

51. 2.1.2 An Example

51. The following file specifies three trains, two headed East and one headed West.

55

56

57

e 10 6

W 6 7

E310

58. It implies the following list of trains:

60. Note: Observe that Train 2 is actually the first to finish the loading process.

2

67

68

69

70

71

72

1. If they are both traveling in the same direction, the train which finished loading first gets the clearance to cross first. If they finished loading at the same time, the one appeared first in the input file gets the clearance to cross first.

2. If they are traveling in opposite directions, pick the train which will travel in the direction opposite of which the last train to cross the main track traveled. If no trains have crossed the main track yet, the Eastbound train has the priority.

73 2.3 Step 3: Output

74. For the example, shown in Section 2.1.2, the correct output is:

75

76

77

78

79

80

81

82

83

84. You must:

84. 1. print the arrival of each train at its departure point (after loading) using the format string, prefixed by the

84. simulation time:

84. “Train %2d is ready to go %4s”

84. 2. print the crossing of each train using the format string, prefixed by the simulation time:

84. “Train %2d is ON the main track going %4s”

84. 3. print the arrival of each train (at its destination) using the format string, prefixed by the simulation time:

84. “Train %2d is OFF the main track after going %4s”

84. where:

93

94

95

96

• there are only two possible values for direction: “East” and “West”

• trains have integer identifying numbers. The ID number of a train is specified implicitly in the input file. The train specified in the first line of the input file has ID number 0.

• trains have loading and crossing times in the range of [1, 99].

97 2.4 Manual Pages

98 Be sure to study the man pages for the various functions to be used in the assignment. For example, the man page

99 for pthread create can be found by typing the command:

100 $ man pthread create

101 At the end of this assignment you should be familiar with the following functions:

102 1. File access functions:

3

103

104

105

106

107

1. atoi

2. fopen

3. feof

4. fgets and strtok and more efficiently you can use fscanf

5. fclose

108. 2. Thread creation functions:

109

110

111

1. pthread create

2. pthread exit

3. pthread join

112. 3. Mutex manipulation functions:

113

114

115

1. pthread mutex init

2. pthread mutex lock

3. pthread mutex unlock

116. 4. Condition variable manipulation functions:

116. (a) pthread cond init

116. (b) pthread cond wait

116. (c) pthread cond broadcast

116. (d) pthread cond signal

116. It is absolutely critical that you read the man pages, and attend the tutorials.

117. Your best source of information, as always, is the man pages.

116. For help with the POSIX interface (in general):

116. http://www.opengroup.org/onlinepubs/007908799/

116. For help with POSIX threads:

116. http://www.opengroup.org/onlinepubs/007908799/xsh/pthread.h.html

116. A good overview of pthread can be found at: http://computing.llnl.gov/tutorials/pthreads/

116. 3 Tutorial Schedule

116. In order to help you finish this programming assignment on time successfully, the schedule of this assignment has

116. been synchronized with both the lectures and the tutorials. There are four tutorials arranged during the course of

116. this assignment, including the one on pthread. NOTE: Please do attend the tutorials and follow the tutorial

116. schedule closely.

Date		Tutorial	Milestones
Jan 30/31		pthread, mutex and condition variable calls	multi-threading programming
Feb 6/7		P2 spec go-through, design review/hints	design and code skeleton
Feb 13/14		reading break, no tutorials	design finished
Feb 20/21		feedback on design and pthread programming	code done
Feb 27/28		testing and last-minute help	final deliverable

4

148

149

150

151

1. Describe the condition that the convar will represent.

2. Which mutex is associated with the convar? Why?

3. What operation should be performed once pthread cond wait() has been unblocked and re-acquired the mutex?

152. 8. In 15 lines or less, briefly sketch the overall algorithm you will use. You may use sentences such as:

153

154

If train is loaded, get station mutex, put into queue, release station mutex.

The marker will not read beyond 15 lines.

155. Note: Please submit answers to the above on 8.5^′′×11^′′ paper in 10pt font, single spaced with 1” margins left,

155. right, top, and bottom. 2 pages maximum (cover page excluded), on Feb 19 through connex. The design counts for

155. 5%.

155. 5 Bonus Features

155. Only a simple control system simulator with limited scheduling and synchronization features is required in this assign-

155. ment. However, students have the option to propose bonus features to include more scheduling and synchronization

155. functions (e.g., to address scheduling fairness issues).

155. If you want to design and implement a bonus feature, you should contact the course instructor for permission

155. before the due date of Deliverable 1, and clearly indicate the feature in the submission of Deliverable 2. The credit

155. for the correctly implemented bonus feature will not exceed 20% of the full marks for this assignment.

155. 6 Submission: Deliverable 2 (Code Due: March 5, 2018)

155. The code is submitted through connex. The tutorial instructor will give the detailed instruction in the tutorial.

155. 6.1 Submission Requirements

155. Your submission will be marked by an automated script. The script (which is not very smart) makes certain

155. assumptions about how you have packaged your assignment submission. We list these assumptions so that your

155. submission can be marked thus, in a timely, convenient, and hassle-free manner.

155. 1. The name of the submission file must be p2.tar.gz

5