1. Goals for this week

  • Understanding global variables in C.

  • Practice with signals and signal handler functions.

  • Introduction to circular arrays and practice implementing a fixed-size queue in C.

2. Starting Point Code

Start by creating a week11 directory in your weeklylab subdirectory and copying over some files:

$ cd ~/cs31/weeklylab
$ mkdir week11
$ cd week11
$ pwd
/home/you/cs31/weeklylab/week11
$ cp ~kwebb/public/cs31/week11/* ./
$ ls
circqueue.c  globalvars.c  Makefile  signals.c

3. Global Variables

Open the globalvars.c in an editor and look through it to see how to declare and use a global variable.

Using Global Variables

In general, you should avoid using global variables. Instead, always design functions to take as parameters the values they need; if a function needs a value, pass it in, and if a caller needs a value from the function return it (or pass in pass-by-pointer style parameters through which the function can modify the caller’s argument values). This makes your code more generic than using globals, and it avoids allocation of space for the entire run of your program when it is not needed.

In the shell lab, we’ll allow you to use global variables to implement a circular queue of the command history, but you should not use them for any other purposes.

4. Signals and Signal Handlers

Let’s look at the program signals.c. This program has some examples of registering a signal handler function on a signal, and of some examples of ways in which you can send signals to processes (for example, alarm can be used to send a SIGALRM to one’s self).

We will try running this and use the kill command to send the process signals:

ps                # get the process' pid, let's say its 345

kill -CONT 345    # sends a SIGCONT signal to process 345
kill -18   345    # or -18 is another way to specify the SIGCONT signal

kill -INT 345    # sends a SIGINT signal to process 345
kill -2   345    # or -2 is another way to specify SIGINT signal

Let’s try running the program and see what it is doing.

The man page for signal lists the signals on this system and describes the signal system call in more detail.

You can also try changing some of the handler code to see what happens. Try changing the SIGINT handler to not call exit, and to print out some other message. Then see what happens when you type (assume 345 is the pid):

kill -INT 345

To kill the process now, you need to send it a SIGKILL signal:

kill -9 345

5. Circular Arrays in C

A queue is a data structure whose values are ordered in FIFO order (first-in-first-out). New items are added to the end of the queue and removed from the beginning of the queue (FIFO semantics for adding and removing).

You are going to implement a fixed-size overwriting queue as a fixed-size circular array of int values. This is an overwriting version of a fixed-size queue, where each time a new value is added to a full array, it replaces (or overwrites) the oldest value in the queue. This type of data structure is useful for keeping a list of the N most recent values. As a new value is added, the previous first value (the oldest) is removed to make room for a new last (newest) value.

As values are added and removed, you’ll need to keep track of two important state variables:

  • queue_next: which index to use for storing the next item that gets added

  • queue_size: the number of items currently in the queue

Initially, both variables will be 0. That is, queue is empty, and you’ll want to write the first item into index 0. As you add items to the queue, you’ll need to update the queue_next index to refer to the next location and the queue_size until you reach a pre-defined maximum size.

While the size of the queue is less than the maximum size (while there is free space in the queue), you’ll simply add items into the next free slot. Eventually, the queue will fill up (queue_size will equal the pre-defined max), and you’ll need to begin overwriting old values. When that happens, as your queue_next index reaches the end of its range, it should roll over back to 0 again.

This is a circular array implementation of a queue because the first and last bucket indices cycle around the array indexes. In a 5-element array, the indices would cycle as follows: 0, 1, 2, 3, 4, 0, 1, …​, 4, 0, 1, …​.

For example, for a circular queue of int values of size 5:

initially empty
   0    1    2    3    4
--------------------------     the next index to write is 0
|    |    |    |    |    |     the size of the queue is 0
--------------------------


after adding values: 3, 6, 17: the next index to write is 3
                               the size of the queue is 3
   0    1    2    3    4
--------------------------     the first value in the queue is in bucket 0
|  3 |  6 | 17 |    |    |     the last value in the queue is in bucket 2
--------------------------


after adding values: 10, 8:    the next index to write is 0 (it has rolled over)
                               the size of the queue is 5
   0    1    2    3    4
--------------------------     the first value in the queue is in bucket 0
|  3 |  6 | 17 | 10 |  8 |
--------------------------     the last value in the queue is in bucket 4


after adding the value 7:      the next index to write is 1
                               the size of the queue is 5 (it will remain 5)
   0    1    2    3    4
--------------------------     the first value in the queue is in bucket 1
|  7 |  6 | 17 | 10 |  8 |
--------------------------     the last value in the queue is in bucket 0


after adding the value 9:      the next index to write is 2

   0    1    2    3    4
--------------------------     the first value in the queue is in bucket 2
|  7 |  9 | 17 | 10 |  8 |
--------------------------     the last value in the queue is in bucket 1

printing out the queue from first (oldest) to last (newest) value is:  17  10  8  7  9

In circqueue.c is the starting point of a circular queue implementation. You are going to implement and test two functions:

void add_queue(int value): add a new value to the queue (and update queue state)
                           the value added should replace the first item
                           in the queue when the array is full
void print_queue(): print out the values in the queue from first to last

This code uses global variables for the queue (implemented as an array of ints) and for other state associated with the queue (and feel free to add more state variables if you need them).

This example is also not an obvious need for a global variable, but if this code was being used to implement a single queue library, then declaring the queue and its state as a global might be necessary. For now, I just want you to get some practice with global variables.

Remember, you should always avoid using global variables in your program, and only do so when explicitly allowed in this class.

6. Implementing a shell

Proceed to Lab 8. This is the second part of the two-week lab. In this part of the lab, you will be writing a shell, which will require to implement a circular queue and a signal handler.

7. Handy References