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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
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
99
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
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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193 | #include <assert.h>
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#ifdef __APPLE__
#include "pthread_barrier.h"
#endif
// Data shared for al threads
typedef struct
{
// Number of teams given by user, two threads are created for each team
size_t team_count;
// Time in milliseconds that threads wait in stage 1: from start to the partner
unsigned stage_time_1;
// Time in milliseconds that threads wait in stage 2: from partner to the finish
unsigned stage_time_2;
// Counter located at the finish used to know the position each thread reach
size_t position;
// A barrier is used at the start of the race to simulate threads departing at the same time
pthread_barrier_t starting_barrier;
// An array of semaphores, one for each team, to simulate the batons. Initially, runner 2 of
// the team will be waiting for the semaphore. When runner 1 reaches runner 2, runner 1 will
// post to the semaphore
sem_t* baton_semaphores;
// A mutex at the finish of the race allows only one runner at time claiming its position
pthread_mutex_t finish_mutex;
} shared_data_t;
// Private thread data: each thread has its own record
typedef struct
{
// The number of the thread: range [0, team_count[ identifies runners from start to the middle
// while range [team_count, 2*team_count[ identify runners from middle to the finish
size_t thread_id;
// Pointer to the shared data record for all threads
shared_data_t* shared_data;
} private_data_t;
int analyze_arguments(int argc, char* argv[], shared_data_t* shared_data);
void* start_race(void* data);
void* finish_race(void* data);
int main(int argc, char* argv[])
{
// Fill the shared data with the values from the arguments
shared_data_t shared_data;
int error = analyze_arguments(argc, argv, &shared_data);
if ( error ) return error;
// Init synchronization controls in shared data
shared_data.position = 0;
pthread_barrier_init( &shared_data.starting_barrier, NULL, shared_data.team_count );
pthread_mutex_init( &shared_data.finish_mutex, NULL );
// Init the semaphores used as batons, one for each team
shared_data.baton_semaphores = (sem_t*) calloc( shared_data.team_count, sizeof(sem_t) );
if ( shared_data.baton_semaphores == NULL )
return (void)fprintf(stderr, "hello_w: error: could not allocate memory for: %zu semaphores\n", shared_data.team_count), 5;
// Create records to control each thread, two per team
const size_t thread_count = 2 * shared_data.team_count;
pthread_t* threads = (pthread_t*) malloc(thread_count * sizeof(pthread_t));
if ( threads == NULL )
return (void)fprintf(stderr, "hello_w: error: could not allocate memory for: %zu threads\n", thread_count), 6;
// Create a private record, one for each thread (two per team)
private_data_t* private_data = (private_data_t*) calloc(thread_count, sizeof(private_data_t));
// Get a time snapshot to calculate the duration later
struct timespec start_time;
clock_gettime(CLOCK_MONOTONIC, &start_time);
// Create the threads, two for each team
#ifdef INVERTED_TEAM_ORDER
for ( size_t team = shared_data.team_count - 1; team <= shared_data.team_count - 1; --team )
#else
for ( size_t team = 0; team < shared_data.team_count; ++team )
#endif
{
// Create the team's thread that starts the race
private_data[team].thread_id = team;
private_data[team].shared_data = &shared_data;
pthread_create(&threads[team], NULL, start_race, private_data + team);
// Create the partner team's thread that finishes the race
const size_t partner = team + shared_data.team_count;
assert(partner < thread_count);
private_data[partner].thread_id = partner;
private_data[partner].shared_data = &shared_data;
pthread_create(&threads[partner], NULL, finish_race, private_data + partner);
}
// Wait until the race finishes
for ( size_t index = 0; index < thread_count; ++index )
pthread_join(threads[index], NULL);
// Get the finish time as another time snapshot
struct timespec finish_time;
clock_gettime(CLOCK_MONOTONIC, &finish_time);
// Calculate the simulation time
const double seconds = finish_time.tv_sec - start_time.tv_sec
+ (finish_time.tv_nsec - start_time.tv_nsec) * 1e-9;
printf("Simulation time: %.9lfs\n", seconds);
// Release synchronization mechanisms
pthread_mutex_destroy(&shared_data.finish_mutex);
pthread_barrier_destroy( &shared_data.starting_barrier );
// Release heap memory
free(shared_data.baton_semaphores);
free(private_data);
free(threads);
return EXIT_SUCCESS;
}
int analyze_arguments(int argc, char* argv[], shared_data_t* shared_data)
{
// Three paramets are mandatory
if ( argc != 4 )
return (void)fprintf(stderr, "usage: relay_race <teams> <stage_time_1> <stage_time_2>\n"), 1;
// Convert text arguments to the shared integer values
if ( sscanf(argv[1], "%zu", &shared_data->team_count) != 1 || shared_data->team_count == 0 )
return (void)fprintf(stderr, "hello_w: error: invalid team count: %s\n", argv[1]), 2;
if ( sscanf(argv[2], "%u", &shared_data->stage_time_1) != 1 )
return (void)fprintf(stderr, "hello_w: error: invalid stage time 1: %s\n", argv[2]), 3;
if ( sscanf(argv[3], "%u", &shared_data->stage_time_2) != 1 )
return (void)fprintf(stderr, "hello_w: error: invalid stage time 2: %s\n", argv[3]), 4;
return 0;
}
// Threads that depart from the start, execute this function. They goal is to give the baton
// to their partners as fast as they can
void* start_race(void* data)
{
// Get pointers to the private and shared data
private_data_t* private_data = (private_data_t*)data;
shared_data_t* shared_data = private_data->shared_data;
// Wait at the starting line
pthread_barrier_wait( &shared_data->starting_barrier );
// The race started! Traverse the stage 1. It takes time
usleep( 1000 * shared_data->stage_time_1 );
// I reached my partner, give it the baton
const size_t team_id = private_data->thread_id;
sem_post( &shared_data->baton_semaphores[team_id] );
// I finished my race
return NULL;
}
void* finish_race(void* data)
{
// Get pointers to the private and shared data
private_data_t* private_data = (private_data_t*)data;
shared_data_t* shared_data = private_data->shared_data;
// I wait until my partner gives me the baton
size_t team_id = private_data->thread_id - shared_data->team_count;
assert(team_id < shared_data->team_count);
sem_wait( &shared_data->baton_semaphores[team_id] );
// My partner gave me the beaton! Traverse the stage 2. It takes time
usleep( 1000 * shared_data->stage_time_2 );
// I arrived to the finish line! grab my position
pthread_mutex_lock( &shared_data->finish_mutex );
++shared_data->position;
// Only first runners win the race
// if ( shared_data->position <= 3 )
{
// Report the place that my team reached
printf( "Place %zu: team %zu\n", shared_data->position, team_id + 1 );
}
// Leave the finish to allow other teams to traverse it
pthread_mutex_unlock( &shared_data->finish_mutex );
// I finished my race
return NULL;
}
|