Shared Memory

Due before midnight on Monday, January 4.

Each team members should create a directory named shm in their repository and include a file named shm.c that includes your program.  Please include the names of the members of the team in a comment at the beginning of the file.

Program Description

Use the code I gave you in class on Friday to create a single program that allows the users that run it to repeatedly read and write to a shared region of memory.  When this program is used by multiple users in multiple terminals it acts like a chat app.

When the program begins, ask the user for a user name.  Preface each message that the user enters with the user name so that the messages from multiple users can be distinguished from one another.

 

Signals

Due prior to midnight on Wednesday, February 4

Please create a directory in your repository named signals for your work.

This assignment will provide you experience using the following system function.

  • signal()
  • kill()
  • fork()
  • execl()
  • wait()

Program Description

Below are descriptions of two executables. The first, named player, is a program that will act as autonomous agent in a game environment. The second, named game_engine, will create child processes that each run the player program. Please write each program in c and include a make file named Makefile. All files should also include the following:

  • Your name and the date at the beginning of each source code file
  • Proper style, including proper variable names and indentation

player.c

The player program should have a global variable named health_level that holds an integral value between 0 and 5, initially 3. The program should have two signal handlers. One named decrease_health and one named increase_health.

The decrease_health method should decrease the value of health_level by 1. After decrementing the value, the program should print to the screen “HEALTH: XX”, where XX is the value of health_level. If the value of health_level reaches 0, the current process should print to standard out “Player killed: PID” where PID is the pid of the current process. The process should then terminate.

The increase_health method should increase the value of health_level by 1 if the current value of health_level is less than 5. After incrementing the value, the program should print to the screen “HEALTH: XX”, where XX is the value of health_level.

The program should register decrease_health as a signal handler for SIGUSR1 and register increase_health as a signal handler for SIGUSR2.

The program should run in a loop until terminated. While in the loop, the program should pause until a signal is received. After processing the signal, the program should continue in the loop.

Testing the Player

On the AWS Linux instance, the numeric values for each signals can be found in /usr/include/asm/signal.h (verify this).  There SIGUSR1 has a value of 10 and SIGUSR2 has a value of 12. You can test your player executable independently of the game engine by starting an instance of the player on the command line and then, using a different terminal window, finding the pid of the player process and issuing a kill signal to it.

Terminal Window 1

$ ./player                     // start up a player

Terminal Window 2

$ ps ax | grep your_user_name  // find the pid of your player process

$ kill -10 player_pid          // send your player process SIGUSR1
$ kill -12 player_pid          // send your player process SIGUSR2

game_engine.c

This program should run a loop and at the top of the loop display the following menu to the user:

  1. Spawn player
  2. Injure player
  3. Heal player
  4. List players
  5. Quit

When the user presses 1, the program should create a child process and run the player executable within it using an exec function.

When the user presses 2, the program should display a list of the engine’s child pids and prompt the user to enter a pid. The program should then send a SIGUSR1 signal to the child with the entered pid.

When the user presses 3, the program should display a list of the engine’s child pids and prompt the user to enter a pid. The program should then send a SIGUSR2 signal to the child with the entered pid.

When the user presses 4, the program should print out a list of the engine’s child pids.

When the user presses 5, the program kills all child processes, prints to the screen “GAME OVER”, and then terminates.

Updating the List of Players When a Player Terminates

When the process’ state has changed (e.g. a player process has terminated) a SIGCHLD signal is sent to the parent process.  In order for the game engine to recognize when a player has terminated the game engine should register a signal handler for the SIGCHLD signal.  In that handler call the wait() function to get the pid of the terminated child process.

#include <sys/types.h>
#include <sys/wait.h>
pid_t wait(int *wstatus);

Note that you can pass 0 (NULL) to wait() if you don’t care about the status, which is probably the case in your program.

With the pid of the terminated player process known, you can update your list of active players.

Matrix Cover

Program Specifications

Create a program consisting of a single source code file named array_cover.c and submit it in a directory named cover.  Please be mindful of the spelling and case of the source code file name and directory name specified above as I will be testing your code using a script.

Your source code file must contain:

  • A comment at the beginning of the file that states your name and the date it was last modified
  • Proper style, including proper variable names and indentation

Your program must accept 3 command line arguments in the order that follows:

  1. an integer k specifying the dimensions of a k x k matrix
  2. an integer i in the interval [0 , k x k)
  3. an integer specifying and id

The program should allocate on the heap a single dimensional array of integers of length k x k and free it before terminating.

After allocating the array, your program should initialize all of the integers to 0 using memset and set the integer at index i to the value id.

After initializing the array the program should print the contents of the array as a k x k matrix to the console using a function named print_matrix.

In the remainder of this program description we will view the array as a k x k matrix and refer to it as such.

The program should set all of the elements in the matrix to the value id while satisfying the following constraints:

  • If the program changes the value of a matrix element, the program must print to the console the contents of the matrix before changing the value of another element in the matrix.
  • You may only change the value of a matrix element if one of the cells adjacent (including those on the diagonal) to the element about to be changed has the value id.

Grading Rubric

To assess your program, I will run your program with various inputs. I will change the dimensions of the matrix, the index where you’ll initially put your id, and I’ll change the value of the id.  Below is the grading rubric which I will use to assign you a grade.

100  Satisfies the program requirements and passes all of the test cases
 80  Satisfies the program requirements but fails at least 1 test case
 60  Satisfies the program requirements but fails all tests
  0  Does not satisfy the program requirements

Gladiator

Due prior to midnight on Thursday, February 21

You are a gladiator. Well … actually you are tasked with writing a gladiator program. In class on Monday, February 18, your gladiator program will compete against your classmates’ gladiator programs in a bracketed competition to determine the greatest gladiator of all.

Your Submission

You gladiator program must reside in a single c source code file. You must use your BC username as the name of the file. For example, mine would be rmcgregor.c. The program must be compilable using the following shell command, where username is replaced with your BC username and executable_name is a name of your choosing.

$gcc username.c –o executable_name

I reiterate, all of your source code must reside in a single source code file that has the same name as your BC username and your code must be compilable using the above command.  Note: this prohibits you from linking in additional object files.

When your program is compiled for the competition it will be compiled using the command above. You must provide a file named README that has a single word in it – the name you want your executable to be given when it is compiled. It must be a valid executable name. The executable name will be displayed on the screen when your gladiator competes.

Your source code file must contain the following:

  • Your name and the date at the beginning of the file
  • Proper style, including proper variable names and indentation
  • Proper and adequate comments

Please upload to GitHub your single source code file and your README file in the folder named gladiator.

Program Arguments

Your program must accept 3 integer arguments in the following order:

  1. an integer specifying a semaphore id
  2. an integer specifying your player’s id
  3. an integer specifying the length of one of the side of the game field

The Arena

Your gladiator will be run against another student’s gladiator in a program that I have written which I’ve called colosseum.

The colosseum program is responsible for setting up the game field and forking two child process in which your gladiator and your opponent’s gladiator will be run.

Before starting the competitors, the colosseum allocates an array of semaphores whose length is a perfect square (4, 9, 16, 25, 36, …). Since the length is a perfect square, the array can be viewed as a 2D array. Each of the semaphores is initialized to 0.

The figure below illustrates an array of semaphores viewed as a 2D array (with side length 8), where each dot represents a semaphore with a value of 0.

One of the gladiators, at random, will be assigned the player id 1 and a random semaphore will be set to the value 1 indicating that the gladiator currently owns that location. The other gladiator will be assigned the player id 2 and a different random semaphore will be set to the value 2 indicating that gladiator 2 currently owns the location. This is illustrated in the figure below.

Once the order of the gladiators (player 1 vs. player 2) and the semaphores (initial locations) are chosen, the colosseum will run each of the gladiators in its own process.

Winning the Game

As mentioned above, each gladiator executable will be passed 3 integers: a semaphore id, a player id, and the side length of the game field.

Since each gladiator has the semaphore id (semid) for the game field and also knows the size of the game field, it can manipulate the game field by changing the values of the semaphores. The goal for each gladiator is to cover the game field with its player id – but there are rules.

A gladiator owns a semaphore if the semaphore’s value is equal to the player’s id. A gladiator can change the value in a semaphore to its player id, even if it is currently owned by its opponent, so long as the semaphore that is to be changed is adjacent to a semaphore that they own prior to changing the value.

For example, in the figure below, gladiator 2 can change the value of all of the semaphores that are circled.

If a gladiator realizes that they no longer own any semaphores they must submit by printing message to standard out indicating that they submit and then terminate.

The contest will continue until a gladiator submits or 2 minutes has expired, whichever comes first. If time expires with no victor, the contest will be considered a draw.

Testing Your Gladiators

I have provided you a program named colosseum.c for you to test your gladiator on. A similar program will be used during the competition. In addition, I have provided a skeleton gladiator program, named gladiator.c, that you may use as a starting point for writing your gladiator program.

These programs are in a directory named gladiator in our shared GitHub repository.

Along with the colosseum.c and gladiator.c source code is a make file. The make file will compile both programs and name the colosseum executable colosseum and name the gladiator executable gladiator.

To compile both programs, run make on the command line.

$make

To run the colosseum program with the skeleton gladiator program, type the command given below on the command line.

$./colosseum gladiator gladiator

After setting up the arena and starting the gladiator programs, the colosseum will display the arena every 0.5 seconds.

To terminate the colosseum program, press CTRL + c.

Don’t Forget

Prior to submitting you code, you must name your gladiator source code file to reflect your username and your program must be able to compile using only the command below.

$gcc username.c –o executable_name

Closing Comments

The goal of this assignment is to learn how to use semaphores – not to win the contest. It is hoped, however, that the gaming environment will inspire you to think creatively to come up with an algorithm that covers the playing field in a strategic way.

Grading Rubric

Criteria Grade
When run against the stationary gladiator on a 10 x 10 board, the program covers the board 100
When run against the stationary gladiator, the program runs and covers 80% or more of the board 80
When run against the stationary gladiator, the program runs and covers 60% of the board 60
Files are missing or the program does not compile 0