Starting from:
$29.99
Assignment 2: Multi-Thread Scheduling (MTS)
Programming Assignment 2 (P2) Multi-Thread Scheduling (MTS)
1 Introduction
In P1 (Simple Shell Interpreter, SSI), you have built a shell environment to interact with the host operating system.7 Good job! But very soon you find that SSI is missing one of the key features in a real multi-process or multi-thread8 operating system: scheduling, i.e., all processes or threads created by your SSI are still scheduled by the host operating9 system, not yours! Interested in building a multi-thread scheduling system for yourself? In this assignment, you will10 learn how to use the three programming constructs provided by the posix pthread library:11
1. threads12
2. mutexes13
3. condition variables (convars)14
to do so. Your goal is to construct a simulator of an automated control system for the railway track shown in Figure 115 (i.e., to emulate the scheduling of multiple threads sharing a common resource in a real operating system).16 As shown in Figure 1, there are two stations (for high and low priority trains) on each side of the main track. At17 each station, one or more trains are loaded with commodities. Each train in the simulation commences its loading18 process at a common start time 0 of the simulation program. Some trains take more time to load, some less. After19 a train is loaded, it patiently awaits permission to cross the main track, subject to the requirements specified in20 Section 2.2. Most importantly, only one train can be on the main track at any given time. After a train finishes21 crossing, it magically disappears. You will use threads to simulate the trains approaching the main track from two22 different directions, and your program will schedule between them to meet the requirements in Section 2.2.23 You will use C or C++ and the Linux workstation in ECS242 or ECS348 or the linux.csc.uvic.ca cluster to24 implement and test your work.25
2 Trains26
Each train, which will be simulated by a thread, has the following attributes:27
1. Number: an integer uniquely identifying each train.28
West Easteast−bound high−priority
low−priority east−bound
east−bound
main track
west−bound high−priority
west−bound low−priority
west−bound
Figure 1: The railway system under consideration.
1
2. Direction:29
• If the direction of a train is Westbound, it starts from the East station and travels to the West station.30 • If the direction of a train is Eastbound, it starts from the West station and travels to the East station.31
3. Priority: The priority of the station from which it departs.32
4. Loading Time: The amount of time that it takes to load it (with goods) before it is ready to depart.33
5. Crossing Time: The amount of time that the train takes to cross the main track.34
Loading time and crossing time are measured in 10ths of a second. These durations will be simulated by having35 your threads, which represent trains, usleep() for the required amount of time.36
2.1 Step 1: Reading the input file37
Your program (mts) will accept one parameter on the command line:38
• The parameter is the name of the input file containing the definitions of the trains.39
2.1.1 Input file format40
The input files have a simple format. Each line contains the information about a single train, such that:41
1. The first field specifies the direction of the train. It is one of the following four characters:42
e, E, w, or W43
e or E specify a train headed East (East-Bound): e represents an east-bound low-priority train, and E represents44 an east-bound high-priority train;45 w or W specify a train headed West (West-Bound): w presents a west-bound low-priority train, and W represents46 a west-bound high-priority train.47
2. Immediately following is an integer that indicates the loading time of the train.48
3. Immediately following is an integer that indicates the crossing time of the train.49
4. A newline (\n) ends the line.50
Trains are numbered sequentially from 0 according to their order in the input file. You need to use strtok() to51 handle the line. More efficiently, you can use fscanf()52
2.1.2 An Example53
The following file specifies three trains, two headed East and one headed West.54
e 10 655 W 6 756 E 3 1057
It implies the following list of trains:58
Train No. Priority Direction Loading Time Crossing Time 0 low East 1.0s 0.6s 1 high West 0.6s 0.7s 2 high East 0.3s 1.0s
59
Note: Observe that Train 2 is actually the first to finish the loading process.60
2
2.2 Step 2: Simulation Rules61
The rules enforced by the automated control system are:62
1. Only one train is on the main track at any given time.63
2. Only loaded trains can cross the main track.64
3. If there are multiple loaded trains, the one with the high priority crosses.65
4. If two loaded trains have the same priority, then:66
(a) If they are both traveling in the same direction, the train which finished loading first gets the clearance67 to cross first. If they finished loading at the same time, the one appeared first in the input file gets the68 clearance to cross first.69 (b) If they are traveling in opposite directions, pick the train which will travel in the direction opposite of70 which the last train to cross the main track traveled. If no trains have crossed the main track yet, the71 Eastbound train has the priority.72
2.3 Step 3: Output73
For the example, shown in Section 2.1.2, the correct output is:74
00:00:00.3 Train 2 is ready to go East75 00:00:00.3 Train 2 is ON the main track going East76 00:00:00.6 Train 1 is ready to go West77 00:00:01.0 Train 0 is ready to go East78 00:00:01.3 Train 2 is OFF the main track after going East79 00:00:01.3 Train 1 is ON the main track going West80 00:00:02.0 Train 1 is OFF the main track after going West81 00:00:02.0 Train 0 is ON the main track going East82 00:00:02.6 Train 0 is OFF the main track after going East83
You must:84
1. print the arrival of each train at its departure point (after loading) using the format string, prefixed by the85 simulation time:86
"Train %2d is ready to go %4s"87
2. print the crossing of each train using the format string, prefixed by the simulation time:88
"Train %2d is ON the main track going %4s"89
3. print the arrival of each train (at its destination) using the format string, prefixed by the simulation time:90
"Train %2d is OFF the main track after going %4s"91
where:92
• there are only two possible values for direction: "East" and "West"93
• trains have integer identifying numbers. The ID number of a train is specified implicitly in the input file. The94 train specified in the first line of the input file has ID number 0.95
• trains have loading and crossing times in the range of [1, 99].96
2.4 Manual Pages97
Be sure to study the man pages for the various functions to be used in the assignment. For example, the man page98 for pthread create can be found by typing the command:99
$ man pthread create100
At the end of this assignment you should be familiar with the following functions:101
1. File access functions:102
3
(a) atoi103 (b) fopen104 (c) feof105 (d) fgets and strtok and more efficiently you can use fscanf106 (e) fclose107
2. Thread creation functions:108
(a) pthread create109 (b) pthread exit110 (c) pthread join111
3. Mutex manipulation functions:112
(a) pthread mutex init113 (b) pthread mutex lock114 (c) pthread mutex unlock115
4. Condition variable manipulation functions:116
(a) pthread cond init117 (b) pthread cond wait118 (c) pthread cond broadcast119 (d) pthread cond signal120
It is absolutely critical that you read the man pages, and attend the tutorials.121 Your best source of information, as always, is the man pages.122 For help with the posix interface (in general):123
http://www.opengroup.org/onlinepubs/007908799/124
For help with posix threads:125
http://www.opengroup.org/onlinepubs/007908799/xsh/pthread.h.html126
A good overview of pthread can be found at: http://computing.llnl.gov/tutorials/pthreads/127
3 Tutorial Schedule128
In order to help you finish this programming assignment on time successfully, the schedule of this assignment has129 been synchronized with both the lectures and the tutorials. There are four tutorials arranged during the course of130 this assignment, including the one on pthread. NOTE: Please do attend the tutorials and follow the tutorial131 schedule closely.132
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
4 Submission: Deliverable 1 (Design Due: Feb 19, 2018)133
You will write a design document which answers the following questions. It is recommended that you think through134 the following questions very carefully before answering them.135 Unlike P1, no amount of debugging will help after the basic design has been coded. Therefore, it is very important136 to ensure that the basic design is correct. Answering the following questions haphazardly will basically ensure that137 Deliverable 2 does not work.138 So think about the following for a few days and then write down the answers.139
1. How many threads are you going to use? Specify the work that you intend each thread to perform.140
2. Do the threads work independently? Or, is there an overall “controller” thread?141
3. How many mutexes are you going to use? Specify the operation that each mutex will guard.142
4. Will the main thread be idle? If not, what will it be doing?143
5. How are you going to represent stations (which are collections of loaded trains ready to depart)? That is, what144 type of data structure will you use?145
6. How are you going to ensure that data structures in your program will not be modified concurrently?146
7. How many convars are you going to use? For each convar:147
(a) Describe the condition that the convar will represent.148 (b) Which mutex is associated with the convar? Why?149 (c) What operation should be performed once pthread cond wait() has been unblocked and re-acquired the150 mutex?151
8. In 15 lines or less, briefly sketch the overall algorithm you will use. You may use sentences such as:152
If train is loaded, get station mutex, put into queue, release station mutex.153
The marker will not read beyond 15 lines.154
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 for156 5%.157
5 Bonus Features158
Only a simple control system simulator with limited scheduling and synchronization features is required in this assign-159 ment. However, students have the option to propose bonus features to include more scheduling and synchronization160 functions (e.g., to address scheduling fairness issues).161 If you want to design and implement a bonus feature, you should contact the course instructor for permission162 before the due date of Deliverable 1, and clearly indicate the feature in the submission of Deliverable 2. The credit163 for the correctly implemented bonus feature will not exceed 20% of the full marks for this assignment.164
6 Submission: Deliverable 2 (Code Due: March 5, 2018)165
The code is submitted through connex. The tutorial instructor will give the detailed instruction in the tutorial.166
6.1 Submission Requirements167
Your submission will be marked by an automated script. The script (which is not very smart) makes certain168 assumptions about how you have packaged your assignment submission. We list these assumptions so that your169 submission can be marked thus, in a timely, convenient, and hassle-free manner.170
1. The name of the submission file must be p2.tar.gz171
5
2. p2.tar.gz must contain all your files in a directory named p2172
3. Inside the directory p2, there must be a Makefile. Also there shall be a test input file created by you.173
4. Invoking make on it must result in an executable named mts being built, without user intervention.174
5. You may not submit the assignment with a compiled executable and/or object (.o) files; the script will delete175 them before invoking make.176
Note:177
1. The script will give a time quota of 1 minute for your program to run on a given input. This time quota is178 given so that non-terminating programs can be killed.179 Since your program simulates train crossing delays in 10ths of a second, this should not be an issue, at all.180
2. Follow the output rules specified in the assignment specification, so that the script can tally the output produced181 by your program against text files containing the correct answer.182
3. The markers will read your C code after the script has run to ensure that the pthread library is used as183 required.184
The code counts for 15%.
1 Introduction
In P1 (Simple Shell Interpreter, SSI), you have built a shell environment to interact with the host operating system.7 Good job! But very soon you find that SSI is missing one of the key features in a real multi-process or multi-thread8 operating system: scheduling, i.e., all processes or threads created by your SSI are still scheduled by the host operating9 system, not yours! Interested in building a multi-thread scheduling system for yourself? In this assignment, you will10 learn how to use the three programming constructs provided by the posix pthread library:11
1. threads12
2. mutexes13
3. condition variables (convars)14
to do so. Your goal is to construct a simulator of an automated control system for the railway track shown in Figure 115 (i.e., to emulate the scheduling of multiple threads sharing a common resource in a real operating system).16 As shown in Figure 1, there are two stations (for high and low priority trains) on each side of the main track. At17 each station, one or more trains are loaded with commodities. Each train in the simulation commences its loading18 process at a common start time 0 of the simulation program. Some trains take more time to load, some less. After19 a train is loaded, it patiently awaits permission to cross the main track, subject to the requirements specified in20 Section 2.2. Most importantly, only one train can be on the main track at any given time. After a train finishes21 crossing, it magically disappears. You will use threads to simulate the trains approaching the main track from two22 different directions, and your program will schedule between them to meet the requirements in Section 2.2.23 You will use C or C++ and the Linux workstation in ECS242 or ECS348 or the linux.csc.uvic.ca cluster to24 implement and test your work.25
2 Trains26
Each train, which will be simulated by a thread, has the following attributes:27
1. Number: an integer uniquely identifying each train.28
West Easteast−bound high−priority
low−priority east−bound
east−bound
main track
west−bound high−priority
west−bound low−priority
west−bound
Figure 1: The railway system under consideration.
1
2. Direction:29
• If the direction of a train is Westbound, it starts from the East station and travels to the West station.30 • If the direction of a train is Eastbound, it starts from the West station and travels to the East station.31
3. Priority: The priority of the station from which it departs.32
4. Loading Time: The amount of time that it takes to load it (with goods) before it is ready to depart.33
5. Crossing Time: The amount of time that the train takes to cross the main track.34
Loading time and crossing time are measured in 10ths of a second. These durations will be simulated by having35 your threads, which represent trains, usleep() for the required amount of time.36
2.1 Step 1: Reading the input file37
Your program (mts) will accept one parameter on the command line:38
• The parameter is the name of the input file containing the definitions of the trains.39
2.1.1 Input file format40
The input files have a simple format. Each line contains the information about a single train, such that:41
1. The first field specifies the direction of the train. It is one of the following four characters:42
e, E, w, or W43
e or E specify a train headed East (East-Bound): e represents an east-bound low-priority train, and E represents44 an east-bound high-priority train;45 w or W specify a train headed West (West-Bound): w presents a west-bound low-priority train, and W represents46 a west-bound high-priority train.47
2. Immediately following is an integer that indicates the loading time of the train.48
3. Immediately following is an integer that indicates the crossing time of the train.49
4. A newline (\n) ends the line.50
Trains are numbered sequentially from 0 according to their order in the input file. You need to use strtok() to51 handle the line. More efficiently, you can use fscanf()52
2.1.2 An Example53
The following file specifies three trains, two headed East and one headed West.54
e 10 655 W 6 756 E 3 1057
It implies the following list of trains:58
Train No. Priority Direction Loading Time Crossing Time 0 low East 1.0s 0.6s 1 high West 0.6s 0.7s 2 high East 0.3s 1.0s
59
Note: Observe that Train 2 is actually the first to finish the loading process.60
2
2.2 Step 2: Simulation Rules61
The rules enforced by the automated control system are:62
1. Only one train is on the main track at any given time.63
2. Only loaded trains can cross the main track.64
3. If there are multiple loaded trains, the one with the high priority crosses.65
4. If two loaded trains have the same priority, then:66
(a) If they are both traveling in the same direction, the train which finished loading first gets the clearance67 to cross first. If they finished loading at the same time, the one appeared first in the input file gets the68 clearance to cross first.69 (b) If they are traveling in opposite directions, pick the train which will travel in the direction opposite of70 which the last train to cross the main track traveled. If no trains have crossed the main track yet, the71 Eastbound train has the priority.72
2.3 Step 3: Output73
For the example, shown in Section 2.1.2, the correct output is:74
00:00:00.3 Train 2 is ready to go East75 00:00:00.3 Train 2 is ON the main track going East76 00:00:00.6 Train 1 is ready to go West77 00:00:01.0 Train 0 is ready to go East78 00:00:01.3 Train 2 is OFF the main track after going East79 00:00:01.3 Train 1 is ON the main track going West80 00:00:02.0 Train 1 is OFF the main track after going West81 00:00:02.0 Train 0 is ON the main track going East82 00:00:02.6 Train 0 is OFF the main track after going East83
You must:84
1. print the arrival of each train at its departure point (after loading) using the format string, prefixed by the85 simulation time:86
"Train %2d is ready to go %4s"87
2. print the crossing of each train using the format string, prefixed by the simulation time:88
"Train %2d is ON the main track going %4s"89
3. print the arrival of each train (at its destination) using the format string, prefixed by the simulation time:90
"Train %2d is OFF the main track after going %4s"91
where:92
• there are only two possible values for direction: "East" and "West"93
• trains have integer identifying numbers. The ID number of a train is specified implicitly in the input file. The94 train specified in the first line of the input file has ID number 0.95
• trains have loading and crossing times in the range of [1, 99].96
2.4 Manual Pages97
Be sure to study the man pages for the various functions to be used in the assignment. For example, the man page98 for pthread create can be found by typing the command:99
$ man pthread create100
At the end of this assignment you should be familiar with the following functions:101
1. File access functions:102
3
(a) atoi103 (b) fopen104 (c) feof105 (d) fgets and strtok and more efficiently you can use fscanf106 (e) fclose107
2. Thread creation functions:108
(a) pthread create109 (b) pthread exit110 (c) pthread join111
3. Mutex manipulation functions:112
(a) pthread mutex init113 (b) pthread mutex lock114 (c) pthread mutex unlock115
4. Condition variable manipulation functions:116
(a) pthread cond init117 (b) pthread cond wait118 (c) pthread cond broadcast119 (d) pthread cond signal120
It is absolutely critical that you read the man pages, and attend the tutorials.121 Your best source of information, as always, is the man pages.122 For help with the posix interface (in general):123
http://www.opengroup.org/onlinepubs/007908799/124
For help with posix threads:125
http://www.opengroup.org/onlinepubs/007908799/xsh/pthread.h.html126
A good overview of pthread can be found at: http://computing.llnl.gov/tutorials/pthreads/127
3 Tutorial Schedule128
In order to help you finish this programming assignment on time successfully, the schedule of this assignment has129 been synchronized with both the lectures and the tutorials. There are four tutorials arranged during the course of130 this assignment, including the one on pthread. NOTE: Please do attend the tutorials and follow the tutorial131 schedule closely.132
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
4 Submission: Deliverable 1 (Design Due: Feb 19, 2018)133
You will write a design document which answers the following questions. It is recommended that you think through134 the following questions very carefully before answering them.135 Unlike P1, no amount of debugging will help after the basic design has been coded. Therefore, it is very important136 to ensure that the basic design is correct. Answering the following questions haphazardly will basically ensure that137 Deliverable 2 does not work.138 So think about the following for a few days and then write down the answers.139
1. How many threads are you going to use? Specify the work that you intend each thread to perform.140
2. Do the threads work independently? Or, is there an overall “controller” thread?141
3. How many mutexes are you going to use? Specify the operation that each mutex will guard.142
4. Will the main thread be idle? If not, what will it be doing?143
5. How are you going to represent stations (which are collections of loaded trains ready to depart)? That is, what144 type of data structure will you use?145
6. How are you going to ensure that data structures in your program will not be modified concurrently?146
7. How many convars are you going to use? For each convar:147
(a) Describe the condition that the convar will represent.148 (b) Which mutex is associated with the convar? Why?149 (c) What operation should be performed once pthread cond wait() has been unblocked and re-acquired the150 mutex?151
8. In 15 lines or less, briefly sketch the overall algorithm you will use. You may use sentences such as:152
If train is loaded, get station mutex, put into queue, release station mutex.153
The marker will not read beyond 15 lines.154
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 for156 5%.157
5 Bonus Features158
Only a simple control system simulator with limited scheduling and synchronization features is required in this assign-159 ment. However, students have the option to propose bonus features to include more scheduling and synchronization160 functions (e.g., to address scheduling fairness issues).161 If you want to design and implement a bonus feature, you should contact the course instructor for permission162 before the due date of Deliverable 1, and clearly indicate the feature in the submission of Deliverable 2. The credit163 for the correctly implemented bonus feature will not exceed 20% of the full marks for this assignment.164
6 Submission: Deliverable 2 (Code Due: March 5, 2018)165
The code is submitted through connex. The tutorial instructor will give the detailed instruction in the tutorial.166
6.1 Submission Requirements167
Your submission will be marked by an automated script. The script (which is not very smart) makes certain168 assumptions about how you have packaged your assignment submission. We list these assumptions so that your169 submission can be marked thus, in a timely, convenient, and hassle-free manner.170
1. The name of the submission file must be p2.tar.gz171
5
2. p2.tar.gz must contain all your files in a directory named p2172
3. Inside the directory p2, there must be a Makefile. Also there shall be a test input file created by you.173
4. Invoking make on it must result in an executable named mts being built, without user intervention.174
5. You may not submit the assignment with a compiled executable and/or object (.o) files; the script will delete175 them before invoking make.176
Note:177
1. The script will give a time quota of 1 minute for your program to run on a given input. This time quota is178 given so that non-terminating programs can be killed.179 Since your program simulates train crossing delays in 10ths of a second, this should not be an issue, at all.180
2. Follow the output rules specified in the assignment specification, so that the script can tally the output produced181 by your program against text files containing the correct answer.182
3. The markers will read your C code after the script has run to ensure that the pthread library is used as183 required.184
The code counts for 15%.
1 file (113.5KB)
