it2051229 CS 5343 Thread and Synchronization

The goal of this program is to use thread programming together with synchronization constructs available to simulate a simple multi-player game in the language C.

The game - rules

Each game has a dealer (who is not involved in the game), and N players (we denote them as Player 0, Player 1, ... Player N-1).

The dealer will start generating random numbers between 1-40 and put them into a FIFO queue. The dealer will generate a total of T numbers (which is pre-defined before the start of the game). Every time a number is generated, the dealer will look at the queue, if there is not more than N numbers in the queue, it will insert the number at the end of the queue. Otherwise, it will wait until there are no more than N numbers.

Once there are number(s) in the queue, the players will try to grab the number at the front of the queue. When a player (call him/her player k) grab hold of that number, he/she will rest for a short period of time, and then determine whether he/she will score and whether he/she will need to put the number back to the (end of the) queue: (we denote the number as x)

if x <= N, then the player score x points, and the number is discarded from play
Otherwise, if x % N = k or x % N = (k+1) % N, then the player scores lower bound of 2x/5 points (notice the division integer division). Then the player will insert the number (x - lower bound of 2x/5) back to the end of the queue.
Otherwise, the player does not score, and will insert the number x-2 back to the end of the queue.

The game ends when there is no more number left (either on the queue or in the player's hand). The player with the highest total score wins.

Notice that there is no "player 1's turn", player 2s turn etc (do not impose player orders). Once there is a number in the queue, every player is eligible to try to grab the number. The only exception is that once one gets the number, he/she has to wait till you either discard it or put the required number back on the queue before he can get the next number available. If he/she do it fast enough, he/she can the next number. However, there is no two (or more) players can simultaneously get the same number.

A couple of sample runs of the game is available for you to examine.

Base care

For the base case, you are to implement the game via threads and synchronization constructs.

Main process - dealer

The main process of your program should serve as the dealer. It will take two command line parameters (via argc, argv). The first one is N (number of players) and the second one is T (the number of numbers generated). Your main thread should follow logic similar to described below:

Do all necessary pre-processing
Create all threads
Signal the game to start
Repeat
  If the queue currently has N or fewer numbers
    Generate a new number and add it to the queue
Until T numbers generated
Wait for all threads to finish
Print the final score for each player

Threads - player

Each player should be represented by a thread. The logic of each thread should be as follows

Do all necessary pre-processing
Wait for the game start signal
Repeat
  If the queue is non-empty
    Get the next number (call it x)
    Sleep for 1 + x millseconds (use the function nanosleep())
    Process scoring, and put a number back to the queue if necessary
Until game ends
Exit

One requirement for each thread: once a thread obtained a number, it cannot block other threads from obtaining the next number before it sleeps.

Output

Your program should output what is being output in the sample runs. Namely

Whenever there is a change to the queue (insert/delete), print the whole queue (on a single line) after the change is made
When the dealer push an item onto the queue, print the statement ("Dealer is pushing x to the queue" - where x is the value of the number being pushed). This line should be printed before x is pushed onto the queue.
When a thread push an item onto the queue, print the statement ("Thread t pushing x to the queue" - where x is the value of the number being pushed). This line should be printed before x is pushed onto the queue.
When a thread pop an item off the queue, print the statement ("Thread t pop x from the queue" - where t is the player number and x is the number. It should also print (on the same line), whether the player score, and if the thread needs to push any number back on the queue (and which number to push).

Stage 1

The base part allows one game to be played. In this part you are going to simulate playing multiple games with different players.

In this part you program should read in a name of a file via the command line parameter. Then the program should read that file. The file format is the following:

The first line has three integers, which are N, T, and the total number of players for all the games (we will denote it as p). (N is the number of players for each game)
Then each of the following p lines contains one string, which is the name of a player.

The program now consists of a list of games. The main program, in addition to being the dealer, will have to facilitate multiple games.

In this part, you should consider each thread is a slot for a player to play in the game. The main program will start by assigning players to the slots, and once all the slots are filled, then play a game among them (T is the number of numbers generated per game). At the end of each game, the winner will leave, opening up a slot for the next player to fill in to start a new game.

The main process' logic will now be like this:

Do all necessary pre-processing
Create all threads
Create a list of all players
Assign the first N players to a slot
Repeat
  Play a game (using the logic of base part)
  Print the winner of that game (and the score)
  Replace that player with the next one
Until no more players left in the list

One note: You should not pre-assign players to slots. Also, the player should join the game in the order of players in the file.

The logic of each thread will also need to be adjusted (left to you to figure it out).

Output

In additional to the output for the base case. You need to output two more things:

Whenever a game ends, print the score for each player, and who win the game.
Before the next game starts, print the list of all players for that game.

Sample Output

Number of threads : 4 | Number of objects : 10

Thread 0 started
Thread 1 started
Thread 2 started
The dealer inserted : 13
Thread 3 started

( 13 )

Thread 0 (0, 1) popped x = 13 (1). Matched. Need to push 3/5 * x back on queue

( )

The dealer inserted : 22

( 22 )

Thread 1 (1, 2) popped x = 22 (2). Matched. Need to push 3/5 * x back on queue

( )

The dealer inserted : 33

( 33 )

Thread 3 (3, 0) popped x = 33 (1). Not matched. Need to push x - 2 back on queue

( )

The dealer inserted : 36

( 36 )

Thread 2 (2, 3) popped x = 36 (0). Not matched. Need to push x - 2 back on queue

( )

The dealer inserted : 19

( 19 )

The dealer inserted : 38

( 19 38 )

The dealer inserted : 17

( 19 38 17 )

The dealer inserted : 10

( 19 38 17 10 )

Thread 0 score : 5 total : 5
Thread 0 pushed 8 to back of the queue

( 19 38 17 10 8 )

Thread 0 (0, 1) popped x = 19 (3). Not matched. Need to push x - 2 back on queue

( 38 17 10 8 )

Thread 1 score : 8 total : 8
Thread 1 pushed 14 to back of the queue

( 38 17 10 8 14 )

Thread 1 (1, 2) popped x = 38 (2). Matched. Need to push 3/5 * x back on queue

( 17 10 8 14 )

Thread 3 pushed 31 to back of the queue

( 17 10 8 14 31 )

Thread 3 (3, 0) popped x = 17 (1). Not matched. Need to push x - 2 back on queue

( 10 8 14 31 )

Thread 2 pushed 34 to back of the queue

( 10 8 14 31 34 )

Thread 2 (2, 3) popped x = 10 (2). Matched. Need to push 3/5 * x back on queue

( 8 14 31 34 )

Thread 0 pushed 17 to back of the queue

( 8 14 31 34 17 )

Thread 0 (0, 1) popped x = 8 (0). Matched. Need to push 3/5 * x back on queue

( 14 31 34 17 )

Thread 2 score : 4 total : 4
Thread 2 pushed 6 to back of the queue

( 14 31 34 17 6 )

Thread 1 score : 15 total : 23
Thread 3 pushed 15 to back of the queue

( 14 31 34 17 6 15 )

Thread 2 (2, 3) popped x = 14 (2). Matched. Need to push 3/5 * x back on queue

( 31 34 17 6 15 )

Thread 1 pushed 23 to back of the queue

( 31 34 17 6 15 23 )

Thread 3 (3, 0) popped x = 31 (3). Matched. Need to push 3/5 * x back on queue

( 34 17 6 15 23 )

Thread 1 (1, 2) popped x = 34 (2). Matched. Need to push 3/5 * x back on queue

( 17 6 15 23 )

Thread 0 score : 3 total : 8
Thread 0 pushed 5 to back of the queue

( 17 6 15 23 5 )

Thread 0 (0, 1) popped x = 17 (1). Matched. Need to push 3/5 * x back on queue

( 6 15 23 5 )

Thread 2 score : 5 total : 9
Thread 2 pushed 9 to back of the queue

( 6 15 23 5 9 )

Thread 2 (2, 3) popped x = 6 (2). Matched. Need to push 3/5 * x back on queue

( 15 23 5 9 )

Thread 3 score : 12 total : 12
Thread 3 pushed 19 to back of the queue

( 15 23 5 9 19 )

Thread 3 (3, 0) popped x = 15 (3). Matched. Need to push 3/5 * x back on queue

( 23 5 Thread 1 score : 13 total : 36
9 19 )

Thread 1 pushed 21 to back of the queue

( 23 5 9 19 21 )

Thread 1 (1, 2) popped x = 23 (3). Not matched. Need to push x - 2 back on queue

( 5 9 19 21 )

Thread 0 score : 6 total : 14
Thread 0 pushed 11 to back of the queue

( 5 9 19 21 11 )

Thread 0 (0, 1) popped x = 5 (1). Matched. Need to push 3/5 * x back on queue

( 9 19 21 11 )

Thread 2 score : 2 total : 11
Thread 2 pushed 4 to back of the queue

( 9 19 21 11 4 )

Thread 2 (2, 3) popped x = 9 (1). Not matched. Need to push x - 2 back on queue

( 19 21 11 4 )

Thread 3 score : 6 total : 18
Thread 1 pushed 21 to back of the queue

( 19 21 11 4 21 )

Thread 3 pushed 9 to back of the queue

( 19 21 11 4 21 9 )

Thread 1 (1, 2) popped x = 19 (3). Not matched. Need to push x - 2 back on queue

( 21 11 4 21 9 )

Thread 3 (3, 0) popped x = 21 (1). Not matched. Need to push x - 2 back on queue

( 11 4 21 9 )

Thread 0 score : 2 total : 16
Thread 0 pushed 3 to back of the queue

( 11 4 21 9 3 )

Thread 0 (0, 1) popped x = 11 (3). Not matched. Need to push x - 2 back on queue

( 4 21 9 3 )

Thread 2 pushed 7 to back of the queue

( 4 21 9 3 7 )

Thread 2 (2, 3) popped x = 4 (0). Final bonus for object : no need to push back.

( 21 9 3 7 )

Thread 3 pushed 19 to back of the queue

( 21 9 3 7 19 )

Thread 1 pushed 17 to back of the queue

( 21 9 3 7 19 17 )

Thread 3 (3, 0) popped x = 21 (1). Not matched. Need to push x - 2 back on queue

( 9 3 7 19 17 )

Thread 1 (1, 2) popped x = 9 (1). Matched. Need to push 3/5 * x back on queue

( 3 7 19 17 )

Thread 0 pushed 9 to back of the queue

( 3 7 19 17 9 )

Thread 0 (0, 1) popped x = 3 (3). Final bonus for object : no need to push back.

( 7 19 17 9 )

Thread 2 score : 4 total : 15 (*)
Thread 2 (2, 3) popped x = 7 (3). Matched. Need to push 3/5 * x back on queue

( 19 17 9 )

The dealer inserted : 20

( 19 17 9 20 )

Thread 1 score : 3 total : 39
Thread 1 pushed 6 to back of the queue

( 19 17 9 20 6 )

Thread 1 (1, 2) popped x = 19 (3). Not matched. Need to push x - 2 back on queue

( 17 9 20 6 )

Thread 3 pushed 19 to back of the queue

( 17 9 20 6 19 )

Thread 3 (3, 0) popped x = 17 (1). Not matched. Need to push x - 2 back on queue

( 9 20 6 19 )

Thread 0 score : 3 total : 19 (*)
Thread 0 (0, 1) popped x = 9 (1). Matched. Need to push 3/5 * x back on queue

( 20 6 19 )

The dealer inserted : 6

( 20 6 19 6 )

Thread 2 score : 2 total : 17
Thread 2 pushed 5 to back of the queue

( 20 6 19 6 5 )

Thread 2 (2, 3) popped x = 20 (0). Not matched. Need to push x - 2 back on queue

( 6 19 6 5 )

Thread 1 pushed 17 to back of the queue

( 6 19 6 5 17 )

Thread 1 (1, 2) popped x = 6 (2). Matched. Need to push 3/5 * x back on queue

( 19 6 5 17 )

Thread 3 pushed 15 to back of the queue

( 19 6 5 17 15 )

Thread 3 (3, 0) popped x = 19 (3). Matched. Need to push 3/5 * x back on queue

( 6 5 17 15 )

Thread 0 score : 3 total : 22
Thread 0 pushed 6 to back of the queue

( 6 5 17 15 6 )

Thread 0 (0, 1) popped x = 6 (2). Not matched. Need to push x - 2 back on queue

( 5 17 15 6 )

Thread 2 pushed 18 to back of the queue

( 5 17 15 6 18 )

Thread 2 (2, 3) popped x = 5 (1). Not matched. Need to push x - 2 back on queue

( 17 15 6 18 )

Thread 1 score : 2 total : 41
Thread 1 pushed 4 to back of the queue

( 17 15 6 18 4 )

Thread 1 (1, 2) popped x = 17 (1). Matched. Need to push 3/5 * x back on queue

( 15 6 18 4 )

Thread 3 score : 7 total : 25
Thread 3 pushed 12 to back of the queue

( 15 6 18 4 12 )

Thread 3 (3, 0) popped x = 15 (3). Matched. Need to push 3/5 * x back on queue

( 6 18 4 12 )

Thread 0 pushed 4 to back of the queue

( 6 18 4 12 4 )

Thread 0 (0, 1) popped x = 6 (2). Not matched. Need to push x - 2 back on queue

( 18 4 12 4 )

Thread 2 pushed 3 to back of the queue

( 18 4 12 4 3 )

Thread 2 (2, 3) popped x = 18 (2). Matched. Need to push 3/5 * x back on queue

( 4 12 4 3 )

Thread 1 score : 6 total : 47
Thread 1 pushed 11 to back of the queue

( 4 12 4 3 11 )

Thread 1 (1, 2) popped x = 4 (0). Final bonus for object : no need to push back.

( 12 4 3 11 )

Thread 3 score : 6 total : 31
Thread 3 pushed 9 to back of the queue

( 12 4 3 11 9 )

Thread 3 (3, 0) popped x = 12 (0). Matched. Need to push 3/5 * x back on queue

( 4 3 11 9 )

Thread 0 pushed 4 to back of the queue

( 4 3 11 9 4 )

Thread 0 (0, 1) popped x = 4 (0). Final bonus for object : no need to push back.

( 3 11 9 4 )

Thread 2 score : 7 total : 24
Thread 2 pushed 11 to back of the queue

( 3 11 9 4 11 )

Thread 2 (2, 3) popped x = 3 (3). Final bonus for object : no need to push back.

( 11 9 4 11 )

Thread 1 score : 4 total : 51 (*)
Thread 1 (1, 2) popped x = 11 (3). Not matched. Need to push x - 2 back on queue

( 9 4 11 )

Thread 3 score : 4 total : 35
Thread 3 pushed 8 to back of the queue

( 9 4 11 8 )

Thread 3 (3, 0) popped x = 9 (1). Not matched. Need to push x - 2 back on queue

( 4 11 8 )

Thread 0 score : 4 total : 26 (*)
Thread 0 (0, 1) popped x = 4 (0). Final bonus for object : no need to push back.

( 11 8 )

Thread 2 score : 3 total : 27 (*)
Thread 2 (2, 3) popped x = 11 (3). Matched. Need to push 3/5 * x back on queue

( 8 )

Thread 1 pushed 9 to back of the queue

( 8 9 )

Thread 1 (1, 2) popped x = 8 (0). Not matched. Need to push x - 2 back on queue

( 9 )

Thread 3 pushed 7 to back of the queue

( 9 7 )

Thread 3 (3, 0) popped x = 9 (1). Not matched. Need to push x - 2 back on queue

( 7 )

Thread 0 score : 4 total : 30 (*)
Thread 0 (0, 1) popped x = 7 (3). Not matched. Need to push x - 2 back on queue

( )

Thread 2 score : 4 total : 31
Thread 2 pushed 7 to back of the queue

( 7 )

Thread 2 (2, 3) popped x = 7 (3). Matched. Need to push 3/5 * x back on queue

( )

Thread 1 pushed 6 to back of the queue

( 6 )

Thread 1 (1, 2) popped x = 6 (2). Matched. Need to push 3/5 * x back on queue

( )

Thread 3 pushed 7 to back of the queue

( 7 )

Thread 3 (3, 0) popped x = 7 (3). Matched. Need to push 3/5 * x back on queue

( )

Thread 0 pushed 5 to back of the queue

( 5 )

Thread 0 (0, 1) popped x = 5 (1). Matched. Need to push 3/5 * x back on queue

( )

Thread 2 score : 2 total : 33
Thread 2 pushed 5 to back of the queue

( 5 )

Thread 2 (2, 3) popped x = 5 (1). Not matched. Need to push x - 2 back on queue

( )

Thread 1 score : 2 total : 53
Thread 1 pushed 4 to back of the queue

( 4 )

Thread 1 (1, 2) popped x = 4 (0). Final bonus for object : no need to push back.

( )

Thread 3 score : 2 total : 37
Thread 3 pushed 5 to back of the queue

( 5 )

Thread 3 (3, 0) popped x = 5 (1). Not matched. Need to push x - 2 back on queue

( )

Thread 0 score : 2 total : 32
Thread 0 pushed 3 to back of the queue

( 3 )

Thread 0 (0, 1) popped x = 3 (3). Final bonus for object : no need to push back.

( )

Thread 2 pushed 3 to back of the queue

( 3 )

Thread 2 (2, 3) popped x = 3 (3). Final bonus for object : no need to push back.

( )

Thread 1 score : 4 total : 57 (*)
Thread 3 pushed 3 to back of the queue

( 3 )

Thread 1 (1, 2) popped x = 3 (3). Final bonus for object : no need to push back.

( )

Thread 0 score : 3 total : 35 (*)
Thread 2 score : 3 total : 36 (*)
Thread 1 score : 3 total : 60 (*)
Final score for thread 0 : 35
Final score for thread 1 : 60
Final score for thread 2 : 36
Final score for thread 3 : 37

Academic Honesty!

It is not our intention to break the school's academic policy. Posted solutions are meant to be used as a reference and should not be submitted as is. We are not held liable for any misuse of the solutions. Please see the frequently asked questions page for further questions and inquiries.

Kindly complete the form. Please provide a valid email address and we will get back to you within 24 hours. Payment is through PayPal, Buy me a Coffee or Cryptocurrency. We are a nonprofit organization however we need funds to keep this organization operating and to be able to complete our research and development projects.