[C] Crossroads simulator: threads, mutex, shared memory, etc...
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
Skia a931452425 Add screenshot 5 years ago
.gitignore Add README.md 5 years ago
88242 iterations.png Add screenshot 5 years ago
Critical.dia Finish the README/Report 5 years ago
Critical.png Finish the README/Report 5 years ago
Makefile Add README.md 5 years ago
README.md Finish the README/Report 5 years ago
Report.pdf Add colors and Report.pdf 5 years ago
crossroad.c Make a better repartition accross the map 5 years ago
crossroad.h Make it more synchronized 5 years ago
main.c Make it more synchronized 5 years ago
map Improve crossroads 5 years ago
map.c Make a better repartition accross the map 5 years ago
map.h Make it more synchronized 5 years ago
print.c Add colors and Report.pdf 5 years ago
print.h Add basic crossroad functions and print a whole crossroad 5 years ago
utils.h Make it more synchronized 5 years ago
v_controller.c Make it more synchronized 5 years ago
v_controller.h Make it more synchronized 5 years ago

README.md


Crossroad simulator

  • Summary
  • Compiling and running
  • Data structures
  • Implementation

Summary

This projet aims to simulate four crossroads disposed in square. The purpose is to manage the vehicle stream to get a “city” working well, without any traffic light. The vehicle are thus interconnected with the road infrastructure, and everything must be synchronized.

The project must be implemented in C without any weird library, and it should make use of threads, shared memory, pipes, mutex (semaphores), etc…

The goal is to learn how to use those system, low-level functions, as asked by the course LO41 in UTBM.

Compiling and launching

Just copy the git repository and run make:

git clone https://git.libskia.so/skia/lo41.git
cd lo41
make

Then launch the program with

./crossroads

Enjoy watching vehicles on the road! :)

Data structures

The project has been made a bit like an object-oriented program, with some kinds of constructors, destructors, and data-structures related functions (a bit like methods).

Everything is made using pointers to avoid duplicating memory.

  • Map: This is the top structure, containing all the others.

  • Road: Basically a matrix of vehicle, plus the start and end crossroad.

  • Crossroad: Four input roads and four output road, plus a buffer of vehicles.

  • Vehicle: Its current road, its speed, its current lane and offset on the road.

  • Fleet: A list of vehicle of the same type. There is one fleet per controller thread.

Critical sections

The most critical sections are the roads: they are the only datas that are used by all the threads. That’s why the map contains an array of mutex to lock each road independently, in order not to fall into an deadlock situation.

Another critical section, which is less critical, is the map itself, but it is locked only during the initialization phase of the threads, and is then not needed anymore until SIGINT is received, when everything needs to be freed.

Figure 1 in annex is a Petri net illustrating how the mutex on a critical section would work with four thread. The four mutex states represent always the same mutex protecting the critical section.

Implementation

There are seven threads, in addition to the first main process:

  • Four for the different crossroads

  • Three for the three different types of vehicle (mainly the speed changes for now)

Once the program is run, it will keep working until receiving a SIGINT (^C) signal. This is of course made using sigaction.

Everything is synchronized around the map structure, instanciated only one time, and the list of roads, containing the vehicles.

The thread routines

All the threads are launch in the main process, and have a function that loops forever until the run variable is set to 0. That happens when the main function catches the SIGINT signal, which calls then the ending function of the program after freeing everything.

The loop is based on a clock using usleep(). The threads don’t need to be synchronized, since mutex are used for critical sections access.

Crossroads

The main function of a crossroad is to pop the stacked vehicles at the end of its input road, store them into its buffer to simulate the time taken to cross it, then put the stored vehicles on the right road, looking at the vehicle’s goal.

Choosing the right path

The goal of a vehicle is implemented as an integer following the next conditions:

  • goal/10 is the id of the last crossroad to be crossed
  • goal%10 is the id of the last road before the exit

There are two cases:

  • The vehicle is on its last crossroad and just needs to be send to the exit.

In that case, the direction is given by the following formula: D=(goal%10)%4 We get something between 0 and 3, and just define when building the map, that UP=1, DOWN=2, LEFT=3, RIGHT=0.

  • The vehicle is not on its last crossroad: we just send it to the less loaded neighbor.

The used map is the following:

               UP: 1
     
               5    1
               |    |
          3 -- 0 -- 1 -- 4
LEFT: 3        |    |      RIGHT: 0
          7 -- 2 -- 3 -- 0
               |    |
               2    6
     
               DOWN: 2

Vehicle controllers

The purpose of those three threads is to manage a fleet of vehicles. Every loop, all the roads are scanned, and the contained vehicles on a given road are stepped forward. Then the next road is scanned, and so on until all the roads have been checked. The whole operation is repeated every clock time.

Main loop

The loop in the main process just perform the displaying of the map.

Printing the map

This has been made easily by allocating a chunk of memory, so basically a big matrix. Then some generic functions have been implemented to write a road, or a crossroad, in the given chunk, at the given coordinates, and for the given direction and orientation.

That way, a crossroad just prints itself and its adjacent roads by computing their coordinates with respect to their length, width, and position.

Finally, printing the map just requires printing the four crossroads at the right place.

Then the whole chunk is displayed in the console output and freed.

Petri net illustrating critical section