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
CSc 360: Operating Systems Fall 2019
Programming Assignment 2 P2 MultiThread Scheduling MTS
Spec Out: Oct 4, 2019 Design Due: Oct 18, 2019 Code Due: Nov 1, 2019
1 Introduction
In P1 Simple Shell Interpreter, SSI, you have built a shell environment to interact with the host operating system. Good job! But very soon you find that SSI is missing one of the key features in a real multiprocess or multithread operating system: scheduling, i.e., all processes or threads created by your SSI are still scheduled by the host operating system, not yours! Interested in building a multithread scheduling system for yourself? In this assignment, you will learn how to use the three programming constructs provided by the posix pthread library:
1. threads
2. mutexes
3. condition variables convars
to do so. Your goal is to construct a simulator of an automated control system for the railway track shown in Figure 1 i.e., to emulate the scheduling of multiple threads sharing a common resource in a real operating system.
As shown in Figure 1, there are two stations for high and low priority trains on each side of the main track. At each station, one or more trains are loaded with commodities. Each train in the simulation commences its loading process at a common start time 0 of the simulation program. Some trains take more time to load, some less. After a train is loaded, it patiently awaits permission to cross the main track, subject to the requirements specified in Section 2.2. Most importantly, only one train can be on the main track at any given time. After a train finishes crossing, it magically disappears. You will use threads to simulate the trains approaching the main track from two different directions, and your program will schedule between them to meet the requirements in Section 2.2.
You will use C or C and the Linux workstation in ECS242 or ECS348 or the linux.csc.uvic.ca cluster to implement and test your work.
2 Trains
Each train, which will be simulated by a thread, has the following attributes: 1. Number: an integer uniquely identifying each train.
eastbound highpriority
westbound
eastbound lowpriority
West
East westbound highpriority
eastbound
westbound lowpriority
main track
Figure 1: The railway system under consideration. 1
29
30
31
32
33
34
35 36
37
38
39
40
41
42
43
44 45 46 47
48
49
50
51 52
53
54
55 56 57
58
59
60
2. Direction:
If the direction of a train is Westbound, it starts from the East station and travels to the West station.
If the direction of a train is Eastbound, it starts from the West station and travels to the East station. 3. Priority: The priority of the station from which it departs.
4. Loading Time: The amount of time that it takes to load it with goods before it is ready to depart.
5. Crossing Time: The amount of time that the train takes to cross the main track.
Loading time and crossing time are measured in 10ths of a second. These durations will be simulated by having your threads, which represent trains, usleep for the required amount of time.
2.1 Step 1: Reading the input file
Your program mts will accept one parameter on the command line:
The parameter is the name of the input file containing the definitions of the trains.
2.1.1 Input file format
The input files have a simple format. Each line contains the information about a single train, such that:
1.
2. 3. 4.
The first field specifies the direction of the train. It is one of the following four characters: e,E,w, orW
e or E specify a train headed East EastBound: e represents an eastbound lowpriority train, and E represents an eastbound highpriority train;
w or W specify a train headed West WestBound: w presents a westbound lowpriority train, and W represents a westbound highpriority train.
Immediately following is an integer that indicates the loading time of the train. Immediately following is an integer that indicates the crossing time of the train. A newline n ends the line.
Trains are numbered sequentially from 0 according to their order in the input file. You need to use strtok to handle the line. More efficiently, you can use fscanf
2.1.2 An Example
The following file specifies three trains, two headed East and one headed West.
e 10 6 W67 E 3 10
It implies the following list of trains:
Train No. Priority Direction
0 low East 1.0s 1 high West 0.6s 2 high East 0.3s
Crossing Time 0.6s
0.7s
1.0s
Loading Time
Note: Observe that Train 2 is actually the first to finish the loading process.
2
61
2.2 Step 2: Simulation Rules
The rules enforced by the automated control system are:
1. Only one train is on the main track at any given time.
2. Only loaded trains can cross the main track.
3. If there are multiple loaded trains, the one with the high priority crosses. 4. If two loaded trains have the same priority, then:
62
63
64
65
66
67 68 69
70 71 72
73 74
75
76
77 78 79 80 81 82 83 84 85
86
87 88
89
90
91
92
93
94
95
96 97
98
a
b
c
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.
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.
To avoid starvation, if there are three trains in the same direction traveled through the main track back to back, the trains waiting in the opposite direction get a chance to dispatch one train if any.
2.3
Step 3: Output
For the example, shown in Section 2.1.2, the correct output is:
00:00:00.3 Train2 is ready to go East
00:00:00.3 Train2 is ON the main track going East
00:00:00.6 Train1 is ready to go West
00:00:01.0 Train0 is ready to go East
00:00:01.3 Train2 is OFF the main track after going East
00:00:01.3 Train1 is ON the main track going West
00:00:02.0 Train1 is OFF the main track after going West
00:00:02.0 Train0 is ON the main track going East
00:00:02.6 Train0 is OFF the main track after going East
You must:
1.
2.
3.
print the arrival of each train at its departure point after loading using the format string, prefixed by the simulation time:
Train 2d is ready to go 4s
print the crossing of each train using the format string, prefixed by the simulation time:
Train 2d is ON the main track going 4s
print the arrival of each train at its destination using the format string, prefixed by the simulation time:
Train 2d is OFF the main track after going 4s
where:
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.
3
99
2.4 Manual Pages
Be sure to study the man pages for the various functions to be used in the assignment. For example, the man page for pthread create can be found by typing the command:
man pthread create
At the end of this assignment you should be familiar with the following functions:
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123 124 125
126
127
128
129
130
131 132 133 134
3
1. File access functions:
a atoi b fopen
c feof
d fgets and strtok and more efficiently you can use fscanf
e fclose
2. Thread creation functions:
a pthread create b pthread exit c pthread join
3. Mutex manipulation functions:
a pthread mutex init b pthread mutex lock
c pthread mutex unlock
4. Condition variable manipulation functions:
a pthread cond init b pthread cond wait
c pthread cond broadcast d pthread cond signal
It is absolutely critical that you read the man pages, and attend the tutorials. Your best source of information, as always, is the man pages.
For help with the posix interface in general:
http:www.opengroup.orgonlinepubs007908799
For help with posix threads: http:www.opengroup.orgonlinepubs007908799xshpthread.h.html
A good overview of pthread can be found at: http:computing.llnl.govtutorialspthreads Tutorial Schedule
In order to help you finish this programming assignment on time successfully, the schedule of this assignment has been synchronized with both the lectures and the tutorials. There are four tutorials arranged during the course of this assignment, including the one on pthread. NOTE: Please do attend the tutorials and follow the tutorial schedule closely.
4
Tutorial
p2 spec gothru, pthread, mutex and condition variable calls design reviewhints
feedback on design and pthread programming testing and lastminute help
Date
Oct 81011 Oct 151718 Oct 222425 Oct 2931 Nov 1
Milestones
multithreading programming design and code skeleton done code almost done
final deliverable
135
136 137 138 139 140 141
142
143
144
145
146 147
148
149
150
151
152 153
154
155
156
157 158 159
160
161
162
163 164 165
166
167
168
4 Submission: Deliverable A Design Due: Oct 18, 2019
You will write a design document which answers the following questions. It is recommended that you think through the following questions very carefully before answering them.
Unlike P1, no amount of debugging will help after the basic design has been coded. Therefore, it is very important to ensure that the basic design is correct. Answering the following questions haphazardly will basically ensure that Deliverable B does not work.
So think about the following for a few days and then write down the answers.
1. 2. 3. 4. 5.
6. 7.
8.
How many threads are you going to use? Specify the work that you intend each thread to perform. Do the threads work independently? Or, is there an overall controller thread?
How many mutexes are you going to use? Specify the operation that each mutex will guard.
Will the main thread be idle? If not, what will it be doing?
How are you going to represent stations which are collections of loaded trains ready to depart? That is, what type of data structure will you use?
How are you going to ensure that data structures in your program will not be modified concurrently? How many convars are you going to use? For each convar:
a Describe the condition that the convar will represent. b Which mutex is associated with the convar? Why?
c What operation should be performed once pthread cond wait has been unblocked and reacquired the mutex?
In 15 lines or less, briefly sketch the overall algorithm you will use. You may use sentences such as:
If train is loaded, get station mutex, put into queue, release station mutex.
The marker will not read beyond 15 lines.
Note: Please submit answers to the above on 8.511 paper in 10pt font, single spaced with 1 margins left, right, top, and bottom. 2 pages maximum cover page excluded, on Oct 18 through connex. The design counts for 5.
5 Submission: Deliverable B Code Due: Nov 1, 2019
The code is submitted through connex. The tutorial instructor will give the detailed instruction in the tutorial. 5.1 Submission Requirements
Your submission will be marked by an automated script. The script which is not very smart makes certain assumptions about how you have packaged your assignment submission. We list these assumptions so that your submission can be marked thus, in a timely, convenient, and hasslefree manner.
1. The name of the submission file must be p2.tar.gz
2. p2.tar.gz must contain all your files in a directory named p2
3. Inside the directory p2, there must be a Makefile. Also there shall be a test input file created by you.
5
169 4.
170 5.
Invoking make on it must result in an executable named mts being built, without user intervention.
You may not submit the assignment with a compiled executable andor object .o files; the script will delete
them before invoking make. 172 Note:
171
173 1. 174
175
176 2. 177
178 3. 179
The script will give a time quota of 1 minute for your program to run on a given input. This time quota is given so that nonterminating programs can be killed.
Since your program simulates train crossing delays in 10ths of a second, this should not be an issue, at all.
Follow the output rules specified in the assignment specification, so that the script can tally the output produced by your program against text files containing the correct answer.
The markers will read your C code after the script has run to ensure that the pthread library is used as required.
180 The code counts for 15.
181 6 Plagiarism
182 This assignment is to be done individually. You are encouraged to discuss the design of the solution with your
183 classmates, but each student must implement their own assignment. The markers will submit your code to an
184 automated plagiarism detection service.
185 NOTE: Do not requestgive source code fromto others; do not putuse code atfrom public
186 repositories such as github or so.
6
Reviews
There are no reviews yet.