EEEN30141 Concurrent Systems
1. Introduction and Overview
The coursework is in three parts that will fit together into the simulation of four-by-one
hundred metres sprint relay race1. The race consists of NO_TEAMS competing teams and
each team has NO_MEMBERS members. NO_TEAMS and NO_MEMBERS are both four.
The three parts of the coursework are as follows:
• Part 1: This is concerned with creating and starting a two dimensional array of
threads, each thread representing a runner, interrogating thread properties, and
using random numbers and time delays to represent each runner’s race time. It
also involves these use of C++ maps.
• Part 2: This involves synchronising threads at the start of the race, at the baton
exchanges and ensuring that there is only one winner – photo-finishes are not
allowed in this simulation!
• Part 3: Integrates the code from parts 1 and 2 into the compete simulation.
Although the coursework should be undertaken in the three parts described above, there is
only one submission of the complete program, or as much of it as you have completed by
the deadline.
1.1 Development Environment
You should use the Microsoft Visual Studio IDE to develop your code. This is available on
the Computer Clusters in Engineering Building A and for download via the instruction on the
unit’s Blackboard pages.
1.2 Contact Sessions
The coursework assignment is an individual piece of work that you should complete
independently in your own time (as specified in the Unit Delivery Plan).
There will be a number of one hour lab sessions attended by staff and GTAs to enable you
ask questions about the assignment and seek advice on your code. There will also be code
surgeries run by the Unit Coordinator. Attendance at these sessions is not compulsory.
The schedule of sessions will be published separately.
1.3 Submission of Coursework
The submission of your coursework should a single .zip file. NO OTHER COMPRESSION
FORMAT THAN .ZIP WILL BE ACCEPTED, and if you upload a file in a different format (such
as .7z, .rar etc) you will receive a mark of ZERO. This uploaded .zip file should contain
1 https://en.wikipedia.org/wiki/4_%C3%97_100_metres_relay.
3
your Visual Studio project, including all the source files and headers. A marker should be
able to access you code by double clicking the .vcxproj file, and then building it.
The upload deadline is 13.00 MONDAY 27th NOVEMBER 2023 (week 10). The standard
Departmental penalties for late submissions apply.
Further details about the upload will be provided later.
2. Overview of Part 1
The objective of this part is to write a C++ program that declares a two dimensional array of
thread objects, each of which executes the function run and represents an athlete
competing in the race. The athlete’s time to complete the race is simply a random number,
which is used to produce a time delay in the run function.
The initial version of run to be developed in Part 1 has the following prototype:
void run(Competitor& c);
Class Competitor will be provided for you to use. It is discussed in Section 3 below. Note that
it requires a small, but non-trivial extension. Objects of class Competitor identify the
athletes in the race.
run should sleep for a random period that is compatible with the time taken to run
100 m by a professional athlete2, and print out the calling thread’s id.
To create an array of threads, you will need to use class thread’s default constructor in
the array declaration. The default constructor is briefly introduced near the end of Lecture 4
(slide Threads, Thread Objects and Move Assignment) and one of the example programs
illustrates one way of using it. A thread must then be assigned to each element of the array.
You are expected to do some Internet research on the exact details of how to accomplish
this, although it is straightforward.
The Lecture 4 slide mentioned above also provides an example of how to find the identifier
given to a thread by the underlying run-time system.
3. class Competitor
This allows the program to specify the name of an athlete and the name of the team to
which they belong. The basic version of this class, which is usable at the start of the
coursework is as follows:
2 The women’s world record for the 100 m sprint is 10.49 s, set by Florence Griffith-Joyner (US). The men’s
record is 9.58 s, set by Usain Bolt (Jamacia).
4
Competitor.h
#pragma once
#include <string>
using namespace std;
class Competitor {
// created in main, never updated, passed to a thread, placed in map
private:
string teamName;
string personName;
public:
Competitor();
Competitor(string tN, string pN);
void setTeam(string tN);
string getTeam();
void setPerson(string pN);
string getPerson();
static Competitor makeNull();
void printCompetitor();
};
Competitor.cpp
#include "Competitor.h"
#include <iostream>
Competitor::Competitor() {}
Competitor::Competitor(string tN, string pN) : teamName(tN), personName(pN) {}
void Competitor::setTeam(string tN) { teamName = tN; }
string Competitor::getTeam() { return teamName; }
void Competitor::setPerson(string pN) { personName = pN; }
string Competitor::getPerson() { return personName; }
Competitor Competitor::makeNull() { return *(new Competitor(" ", " ")); }
void Competitor::printCompetitor() {
std::cout << "Team = " << teamName << " Person = " << personName << std::endl;
}
The class has two data members of type string: teamName and personName, that enable
individual athletes to be specified in terms of their team and name e.g., Jamacia and Bolt.
There is a default constructor and a constructor that allows these data members to be
initialised. set and get functions that are common in data holding classes to modify and
return the values of data members are also included. printCompetitor simply prints the
current values of teamName and personName.
The makeNull member function returns a ‘null Competitor’ object whose data members
are both a single character of white space. It can be useful when writing a class to define
and implement a null object, and this is the case here, as discussed in the Appendix.
When a thread is created it is given a thread id by the underlying run-time system (the code
provided by the compiler that interfaces with the Operating System). Lecture 4 explains how
this id can be found. The id and the corresponding Competitor object should be stored in a
map container (see line 8 in the pseudo code of Section 4) and Appendix A1.2. This enables
a thread to determine which Competitor it represents.
5
4. First Version of the Program
A skeleton of the first version of the program is shown and explained below
1. #include <iostream>
2. #include <string>
3. #include //other .h files
4. // Random number generation – see Appendix 1.1
5. const int NO_TEAMS = 4; // number of teams in the race
6. const int NO_MEMBERS = 4; // number of athletes in the team
7. void run(Competitor& c) {
8. // store thread id and competitor in a map
9. // delay for random period
10. // print message stating which competitor has just ‘finished’
11. }
12. int main() {
13. thread theThreads[NO_TEAMS][NO_MEMBERS];
14. Competitor teamsAndMembers[NO_TEAMS][NO_MEMBERS];
15. // define elements of teamsAndMembers
16. // create threads (elements of theThreads)
17. // join threads
18. }
Notes:
Line 3: You will need to #include other header files to complete this part of the
coursework.
Line 5: Global constant representing the number of teams in the race.
Line 6: Global constant representing the number of athletes in each team.
Line 7: This is the function executed by each of the threads. It must be passed a
Competitor object that defines which team and athlete the thread represents.
Line 8: The thread id and Competitor should be stored in a map container. This supports
a mapping between the system thread id and the identity of the athlete
represented by the thread. It is needed because thread ids are system generated
and so it is difficult to know which thread is running a particular Competitor. If
this information is stored in a map then the identity of the Competitor can be
found from the thread id. See Appendix 1.2.
Line 9: This delay represents the time taken for an athlete to run 100 m. This will be a
random number between the world record time and 12 s.
Line 10: This involves calling the printCompetitor member function for the Competitor
object passed to run.
Line 13: The declaration of the two dimensional array of threads.
Line 14: The declaration of the two dimensional array of Competitors.
Line 15: This will be multiple lines in your code, each line defining a Competitor in term of
their team name and person (family) name.
Line 16: Again, this will be multiple lines within your code that creates the threads.
Line 17: All the threads should be joined. Multiple lines in your code.
6
5. Thread Safety
Besides writing some parts of the ThreadMap class, you should consider whether part or all
of the class needs to be thread-safe. Thread safety ensures that objects of a class can be
used reliably in the presence of multiple threads without suffering from concurrency-related
problems. THIS IS A PART OF THE ASSESSMENT OF THE FINAL PROGRAM.
If you decide that Thread safety is relevant, then you should use appropriate techniques to
ensure it. These must be consistent with good program practice as well as being effective.
6. Advice
You should aim to complete this part of the assignment by the start of
week 7.
7
Appendix: Additional Information
A1.1. Random Numbers
The assignment requires the use of random numbers. The standard C/C++ rand and srand
functions have limitations, and so the Mersenne Twister algorithm is used. This is a
powerful and commonly used technique, which is built into C++ via the class mt19937,
available via random.h.
The Twister algorithm is contained in the wrapper class RandomTwister, shown below.
The uniform_int_distribution template is used which provides a uniform, discrete
probability distribution within a defined range, where the numbers within the range have
the same probability of selection3 . These facilities have been used to build the class
RandomTwister below that is provided in the skeleton code, available on Blackboard.
class RandomTwister {
private:
std::mt19937 rnd; // rnd is an object of class mt19937
std::mutex mu;
public:
RandomTwister() : rnd(std::chrono::high_resolution_clock::now().
time_since_epoch().count()){ }
int randomPeriod(int l, int u) {
std::lock_guard<std::mutex> guard (mu);
std::uniform_int_distribution<int> dis(l, u);
int n = dis(rnd);
return n;
}
};
RandomTwister rt;
rt should be a global variable4.
A1.2. Maps
Object Oriented Programming makes use of the idea of Container Classes – classes that
store many instances of objects of some other class. Buffers and stacks are examples of
Container Classes that you have already encountered, but there are many others, including
sets, lists, trees and graphs.
Different Container Classes efficiently support different access patterns to the data stored in
them, and a key programming skill is choosing a good container for a particular application.
Buffers support FIFO access that is needed in Producer-Consumer problems, Stacks support
LIFO access which is needed in compilers and navigation applications, amongst others.
3 See https://cplusplus.com/reference/random/uniform_int_distribution 4 Global variable should be avoided as they can introduce difficult-to-find errors. However, the state of rt is not
changed – it simply produces random numbers when randomPeriod is called, so cannot cause errors of the
kind that were just mentioned.
8
C++ is supported by the Standard Template Library (STL) which provides a large library of
classes, many of which are Container Classes. The library is based on templates so that the
type of object stored can be customised for a particular application.
In this part of the assignment, you need to use the STL library map class. A map is an
associative container that uses a key to locate a mapped value. In a sense, it provides an
abstraction of an array. In an array, the desired element is specified by an integer index. In
a map the ‘index’ is the key and can be of any type. Each mapped value is associated with
a unique5 key.
An example of a map is shown below6. Each map entry is a pair – the first item (the key) is a
Roman numeral between one and ten. The second item in the pair is the text representing
the same number in decimal. In a program that used this map, both the Roman numeral and
the text decimal number would be strings. The map allows the program to specify the
Roman numeral and to find the corresponding text name.
Roman numeral
(key)
Text decimal number
(mapped value)
i one
ii two
iii three
iv four
v five
vi six
vii seven
viii eight
ix nine
x ten
In the assignment, the key is the system thread id, and the data element associated with
the key is the Competitor. Why is this helpful? Well, a thread can discover its id via the
get_id function from the this_thread namespace (see lecture 4). However, a thread
cannot know the Competitor that it represents. Hence the ‘mapping’ between thread id and
Competitor is stored in a map.
When a thread needs to know which Competitor it represents (e.g., for providing output
that can be understood by users, such as printing the finishing order of the teams), it finds
its id by calling get_id and then requests the map to provide the Competitor that
corresponds to the thread id.
5 If you attempt to insert a pair with a key that is already in the map, then the insertion will fail, but no error is
flagged.
6 Not a very useful one!
9
6.1 Using Maps in this Assignment
In order to use maps in this application it is necessary to use a ‘wrapper class’ – a class that
is based on the STL map, but which provides some extra functionality. This is called
ThreadMap.
Like most classes in the STL, maps have many member functions. However, for this
assignment you will only need to use the following (at most)7:
• begin() – Returns an iterator to the first element in the map
• end() – Returns an iterator to the notional element that follows last element in the
map
• size() – Returns the number of elements in the map
• insert(keyvalue, mapvalue) – Adds a new pair to the map
• find(keyvalue) – Returns an iterator that indicates the map entry containing the
key value. If the key value is not present in the map, find returns an iterator to end()
(see above).
An iterator can be thought of as a pointer which can be moved to point to each map
element in turn. Hence iterators can be used to search for an entry (as with the find
function above), or to ‘visit’ every element e.g., if the contents of the map are to be printed
out.
6.2 Wrapper Class – ThreadMap
Here is the header file for the wrapper class ThreadMap (also included in the Part 1
skeleton program):
1. #include <map>
2. #include "Competitor.h"
3. ...
4. class ThreadMap {
5. private:
6. std::map <std::thread::id, Competitor> threadComp;
7. public:
8. ThreadMap();
9. void insertThreadPair(Competitor c);
10. Competitor getCompetitor();
11. void printMapContents();
12. int ThreadMapSize();
13. };
Line 1: This must be included to enable the creation of a map objects.
Line 2: The map will store Competitor objects, so this is needed.
Line 6: This declares a map called threadComp, whose entries are thread id/Competitor
pairs, as specified by the types within the angle brackets.
Line 8: constructor.
7 See https://thispointer.com/stdmap-tutorial-part-**usage-detail-with-examples/
10
Line 9: This function inserts a thread id/Competitor pair into the map threadComp.
Line 10: This member function returns the Competitor corresponding to the id of the thread
that calls it.
The following is part of ThreadMap.cpp:
1. #include "ThreadMap.h"
2. ThreadMap::ThreadMap() {}; // constructor
3. void ThreadMap::insertThreadPair(Competitor c) {
// create a threadID, Competitor pair using a call to std::make_pair
// store the pair in the map using the map insert member function
}
4. Competitor ThreadMap::getCompetitor() {
5. std::map <std::thread::id, Competitor>::iterator
it = threadComp.find(std::this_thread::get_id());
6. if (it == threadComp.end())
7. return Competitor::makeNull();
8. else
9. return it->second; // the second item in the pair (the Competitor)
10.}
11.void ThreadMap::printMapContents() {
12. std::cout << "MAP CONTENTS:" << std::endl;
13. std::map <std::thread::id, Competitor>::iterator it = threadComp.begin();
// you need to write the rest!
14. cout << "END MAP CONTENTS" << endl;
15.}
16. int ThreadMap::ThreadMapSize() { return threadComp.size(); }
Line 3: Writing this function is part of the assignment.
Line 4: This function searches the map for the Competitor corresponding to the id of the
thread that calls it.
Line 5: This creates an iterator that will be used to search for thread id/Competitor pairs
by calling the find function of class map. If find returns end() (see above) then
the thread id is NOT present in the map and so a ‘null Competitor’ object is
returned8 (lines 6 and 7). If the thread id is found, then the second element of the
pair (the Competitor) is returned. This is what it->second does (line 9).
Line 13. This creates an iterator that is used to move through the map, allowing each
element to be printed out. It is initialised to indicate the first element of the map
(it = threadComp.begin();).
The code to move through the map is part of the assignment. This is very
straightforward, particularly if you recall that it is possible in C/C++ to iterate
through an array using a pointer rather than an array index.
8 This is the reason for including makeNull in class Competitor.
請加QQ：99515681 或郵箱：99515681@qq.com WX：codehelp
