Project 6

Overview

In this project you will implement a FIFO queue as a monitor that can be used to solve the bounded buffer problem. Your queue will have a fixed capacity and will block calling threads when it is full or empty. Bounded buffers are extremely common in Operating Systems. When you write code in Java, Python, C#, etc. it may seem like you have infinite memory. However, infinite memory is just an abstraction that the OS provides, in reality you are limited by the physical hardware the OS is running on. This data structure could be used to build higher level abstractions like a thread pool.

Learning Outcomes

• 1.4 Apply computer science theory and software development fundamentals to produce computing-based solutions.
• 1.5 Use simple shell scripts and system tools to analyze process behavior
• 3.3 Identify the sources of deadlocks, race conditions, memory stomps and data loss
• 3.4 Apply concurrent programming techniques such as threads, event loops, and inter-process communication

Grading Rubric

Make sure and review the class grading rubric so you know how your project will be graded.

Task 1 - Setup

Follow the steps below to get your repository all setup and ready to use. The steps below show you how to use and setup GitHub codespaces. You are not required to use codespaces, all the steps below can be completed in the CS Lab or on your personal machine if you prefer.

Fork the starter repository

1. Fork the starter repository into your personal GitHub account: https://github.com/shanep/makefile-project-starter

2. In the new fork name the repository cs452-p6

Start a new Codespace

We will use GitHub Codespaces to do most of our coding. Codespaces is just VSCode in the cloud. This makes it really easy to setup a developer environment and code from any computer that has a browser and internet connection!

1. If you are asked to install recommended extensions click "install". You may not be asked to install extensions if you are already syncing your account.

You now should have a new repository (forked from the starter template) that is ready to use.

Task 2 - Prepare your repository

The starter repository is a bare bones template that you will need to update with the starter code below.

src/lab.h

#ifndef LAB_H
#define LAB_H
#include <stdlib.h>
#include <stdbool.h>

#ifdef __cplusplus
extern "C"
{
#endif

    /**
     * @brief opaque type definition for a queue
     */
    typedef struct queue *queue_t;

    /**
     * @brief Initialize a new queue
     *
     * @param capacity the maximum capacity of the queue
     * @return A fully initialized queue
     */
    queue_t queue_init(int capacity);

    /**
     * @brief Frees all memory and related data signals all waiting threads.
     *
     * @param q a queue to free
     */
    void queue_destroy(queue_t q);

    /**
     * @brief Adds an element to the back of the queue
     *
     * @param q the queue
     * @param data the data to add
     */
    void enqueue(queue_t q, void *data);

    /**
     * @brief Removes the first element in the queue.
     *
     * @param q the queue
     */
    void *dequeue(queue_t q);

    /**
     * @brief Set the shutdown flag in the queue so all threads can
     * complete and exit properly
     *
     * @param q The queue
     */
   void queue_shutdown(queue_t q);

    /**
     * @brief Returns true is the queue is empty
     *
     * @param q the queue
     */
    bool is_empty(queue_t q);

    /**
     * @brief
     *
     * @param q The queue
     */
    bool is_shutdown(queue_t q);

#ifdef __cplusplus
} // extern "C"
#endif

#endif

app/main.c

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <stdbool.h>
#include <time.h>
#include <sys/time.h> /* for gettimeofday system call */
#include "../src/lab.h"

#define UNUSED(x) (void)x
#define MAX_C 8           /* Maximum number of consumer threads */
#define MAX_P 8           /* Maximum number of producer threads */
#define MAX_SLEEP 1000000 /* maximum time a thread can sleep in nanoseconds*/

static bool delay = false;

double getMilliSeconds()
{
     struct timeval now;
     gettimeofday(&now, (struct timezone *)0);
     return (double)now.tv_sec * 1000.0 + now.tv_usec / 1000.0;
}

/*Track the total items produced and consumed*/
static struct
{
     unsigned int num;
     pthread_mutex_t lock;
} numproduced = {0, PTHREAD_MUTEX_INITIALIZER},
  numconsumed = {0, PTHREAD_MUTEX_INITIALIZER};

/*Shared queue that producers and consumers will access*/
static queue_t pc_queue;

/**
 * Produces items at a random interval. Exits once it has produced
 * the correct number of items.
 */
static void *producer(void *args)
{

     int num = *((int *)args);
     //pthread_t tid = pthread_self();
     unsigned int seedp = 0;
     struct timespec s = {0, 0};
     int *itm = NULL;

     // fprintf(stderr, "Producer thread: %ld - producing %d items\n", tid, num);
     for (int i = 0; i < num; i++)
     {
          if (delay)
          {
               /*simulate producing the item*/
               s.tv_nsec = (rand_r(&seedp) % MAX_SLEEP);
               nanosleep(&s, NULL);
          }

          itm = (int *)malloc(sizeof(int));
          *itm = i;
          // Put the item into the queue
          enqueue(pc_queue, itm);

          // Update counters for testing purposes
          pthread_mutex_lock(&numproduced.lock);
          numproduced.num++;
          pthread_mutex_unlock(&numproduced.lock);
     }
     // fprintf(stderr, "Producer thread: %ld - Done producing!\n", tid);
     pthread_exit(NULL);
}

/**
 * Consumes items.
 */
static void *consumer(void *args)
{
     UNUSED(args);
     //pthread_t tid = pthread_self();
     unsigned int seedp = 0;
     struct timespec s = {0, 0};
     int *itm = NULL;
     // fprintf(stderr, "Consumer thread: %ld\n", tid);

     while (true)
     {
          if (delay)
          {
               /*simulate producing the item*/
               s.tv_nsec = (rand_r(&seedp) % MAX_SLEEP);
               nanosleep(&s, NULL);
          }

          itm = (int *)dequeue(pc_queue);
          if (itm)
          {
               free(itm);
               itm = NULL;
               // Update counters for testing purposes
               pthread_mutex_lock(&numconsumed.lock);
               numconsumed.num++;
               pthread_mutex_unlock(&numconsumed.lock);
          }
          else
          {
               // If the queue is implemented correctly we should not
               // get a NULL item during normal operation. It is possible to
               // get a NULL item AFTER shutdown has been called which is fine
               // because we are just cleaning up all the items.
               if (!is_shutdown(pc_queue))
               {
                    fprintf(stderr, "ERROR: Got a null item when queue was not shutdown!\n");
               }
               break;
          }
     }
     // fprintf(stderr, "Consumer Thread: %ld - Done consuming!\n", tid);
     pthread_exit(NULL);
}

static void usage(char *n)
{
     fprintf(stderr, "Usage: %s [-c num consumer] [-p num producer] [-i num items] [-s queue size] <-d introduce delay>\n", n);
     fprintf(stderr, "-d will introduce a random delay between consumer and producer");
     exit(EXIT_FAILURE);
}

int main(int argc, char *argv[])
{
     int nump = 1;       /*total number of producers*/
     int numc = 1;       /*total number of consumers*/
     int numitems = 10;  /*total number of items to produce per thread*/
     int queue_size = 5; /*The default size of the queue*/
     int c;

     pthread_t producers[MAX_P];
     pthread_t consumers[MAX_C];

     while ((c = getopt(argc, argv, "c:p:i:s:dh")) != -1)
          switch (c)
          {
          case 'c':
               numc = atoi(optarg);
               break;
          case 'p':
               nump = atoi(optarg);
               ;
               break;
          case 'i':
               numitems = atoi(optarg);
               break;
          case 's':
               queue_size = atoi(optarg);
               break;
          case 'd':
               delay = true;
               break;
          case 'h':
               usage(argv[0]);
               break;
          default: /* ? */
               usage(argv[0]);
          }
     if (numc > MAX_C)
          numc = MAX_C;
     if (nump > MAX_P)
          nump = MAX_P;

     int per_thread = numitems / nump;
     fprintf(stderr, "Simulating %d producers %d consumers with %d items per thread and a queue size of %d\n", nump, numc, per_thread, queue_size);
     // Start our timing
     double end = 0;
     double start = getMilliSeconds();

     // Initialize the queue for usage
     pc_queue = queue_init(queue_size);
     /*Create the producer threads*/
     for (int i = 0; i < nump; i++)
     {
          pthread_create(&producers[i], NULL, producer, (void *)&per_thread);
     }

     fprintf(stderr, "Creating %d consumer threads\n", numc);
     /*Create the consumer threads*/
     for (int i = 0; i < numc; i++)
     {
          pthread_create(&consumers[i], NULL, consumer, (void *)NULL);
     }

     /*Wait for all the the producer threads to finish*/
     for (int i = 0; i < nump; i++)
     {
          pthread_join(producers[i], NULL);
     }

     // Once all the producers are finished we set a flag so the consumer thread can finish up
     // Once shutdown is called your queue should drain all remaining items and be read for
     // destruction!
     queue_shutdown(pc_queue);

     /*Wait for all the the consumer threads to finish*/
     for (int i = 0; i < numc; i++)
     {
          pthread_join(consumers[i], NULL);
     }

     if (numproduced.num != numconsumed.num)
     {
          fprintf(stderr, "ERROR! produced != consumed\n");
          abort();
     }
     fprintf(stderr, "Queue is empty:%s\n", is_empty(pc_queue) ? "true" : "false");
     fprintf(stderr, "Total produced:%d\n", numproduced.num);
     fprintf(stderr, "Total consumed:%d\n", numconsumed.num);

     // Free up all the stuff we allocated
     queue_destroy(pc_queue);

     // End our timing
     end = getMilliSeconds();
     // Print timing to standard out to graph
     fprintf(stdout, " %f %d \n", end - start, numproduced.num);

     return 0;
}

tests/test-lab.c

#include "harness/unity.h"
#include "../src/lab.h"

// NOTE: Due to the multi-threaded nature of this project. Unit testing for this
// project is limited. I have provided you with a command line tester in
// the file app/main.cp. Be aware that the examples below do not test the
// multi-threaded nature of the queue. You will need to use the command line
// tester to test the multi-threaded nature of your queue. Passing these tests
// does not mean your queue is correct. It just means that it can add and remove
// elements from the queue below the blocking threshold.


void setUp(void) {
  // set stuff up here
}

void tearDown(void) {
  // clean stuff up here
}




void test_create_destroy(void)
{
    queue_t q = queue_init(10);
    TEST_ASSERT_TRUE(q != NULL);
    queue_destroy(q);
}

void test_queue_dequeue(void)
{
    queue_t q = queue_init(10);
    TEST_ASSERT_TRUE(q != NULL);
    int data = 1;
    enqueue(q, &data);
    TEST_ASSERT_TRUE(dequeue(q) == &data);
    queue_destroy(q);
}

void test_queue_dequeue_multiple(void)
{
    queue_t q = queue_init(10);
    TEST_ASSERT_TRUE(q != NULL);
    int data = 1;
    int data2 = 2;
    int data3 = 3;
    enqueue(q, &data);
    enqueue(q, &data2);
    enqueue(q, &data3);
    TEST_ASSERT_TRUE(dequeue(q) == &data);
    TEST_ASSERT_TRUE(dequeue(q) == &data2);
    TEST_ASSERT_TRUE(dequeue(q) == &data3);
    queue_destroy(q);
}

void test_queue_dequeue_shutdown(void)
{
    queue_t q = queue_init(10);
    TEST_ASSERT_TRUE(q != NULL);
    int data = 1;
    int data2 = 2;
    int data3 = 3;
    enqueue(q, &data);
    enqueue(q, &data2);
    enqueue(q, &data3);
    TEST_ASSERT_TRUE(dequeue(q) == &data);
    TEST_ASSERT_TRUE(dequeue(q) == &data2);
    queue_shutdown(q);
    TEST_ASSERT_TRUE(dequeue(q) == &data3);
    TEST_ASSERT_TRUE(is_shutdown(q));
    TEST_ASSERT_TRUE(is_empty(q));
    queue_destroy(q);
}

int main(void) {
  UNITY_BEGIN();
  RUN_TEST(test_create_destroy);
  RUN_TEST(test_queue_dequeue);
  RUN_TEST(test_queue_dequeue_multiple);
  RUN_TEST(test_queue_dequeue_shutdown);
  return UNITY_END();
}

Once you have updated all the starter code lets make your first commit so everything is saved. Open up a terminal and lets make a commit!

git add --all
git commit -m "Added in starter code"

Task 3 - Implement the header file

Implement all the functions defined in lab.h in lab.c.

• pthread tutorial
• Intro to Threads
• Condition Variables
• Threads API

Final Task - Submit your code

Now that you have completed all the tasks the only thing left to do is to submit your code as a patch so you can receive a grade for all your hard work.

Turn on Two Factor

Turn on Two factor authentication for your Boise State provided email account

DANGER

Do NOT skip this step. Boise State University uses Gmail as their email provider and Gmail requires you to use two factor authentication in order to generate an app password.

You need to use your Boise State University issued email account to send the email and you must have two factor authentication turned on.

Generate an app password

INFO

If you are working in GitHub codespaces you will need to setup SMTP for EACH project. This is because each codespace is tied to a specific repository and the settings are not shared. However, if you are working on your own personal machine or in the CS Lab then you will only have to setup SMTP once!

In order to use git send-email you will need to generate an app password. Navigate to https://security.google.com/settings/security/apppasswords and generate a new app password. Make sure and copy the password before you close the window because you will not be able to see it again.

I can't generate a password

If you get the error shown below it typically means that you have not enabled two factor authentication. Follow these steps to resolve the issue:

1. Go back and ensure you have two factor authentication enabled.
2. Log out of your Gmail account
3. Log back into your Gmail account and make sure you did have to use two factor authentication
4. If the steps above fail then open an incognito tab and go back to the first step
5. If you still have issues reboot your machine and go back to the first step

Setup SMTP

1. Open up a terminal in codespaces

2. In the terminal type git config --global --edit and modify the file with the info listed below. You will need to change the info listed below to match your own name, email and App Password that you generated in the previous step.

[User]
	name =  YOUR NAME
	email = YOURNAME@u.boisestate.edu
[sendemail]
	smtpserver = smtp.gmail.com
	smtpuser = YOURNAME@u.boisestate.edu
	smtpPass = xxxx xxxx xxxx xxxx
	smtpencryption = ssl
	smtpserverport = 465

Congrats you should be all setup to send code patch's over email. Now lets create a patch!

Create a patch file

We are now going to do what is called a squash merge and then create a patch file with all our changes in one commit.

1. First lets fetch the upstream branch. This is the branch that you originally forked from at the start of the project

git fetch upstream

2. Checkout a new branch named submit from the upstream/master branch.

git checkout upstream/master -b submit

3. Now we will do a squash merge all the commits we did onto our new submit branch.

git merge --squash master

4. Now commit those new changes to your submit branch

git commit -m "Submit project"

5. Push your submit branch to GitHub

git push -u origin

6. Open up a web browser and navigate to your repository on GitHub and confirm that your submit branch is correctly pushed. Open up the files and make sure that everything looks good before going to the next step.

Install Libraries

If you are working on codespaces you will need to install the required dependencies before you attempt to email out your patch file.

make install-deps

Email Patch File

First make sure you are still on the submit branch that you created. If you type git branch you should see a star next to the submit branch that indicates you are currently on the submit branch.

$ git branch
  master
* submit

WARNING

You MUST test your patch by emailing it to yourself first! You will go through all the steps below with your own email. After you have sent the email to yourself and tested it you can then email your submission to the class mailing list!

Finally we can create our patch to email out!

git send-email --to youremail@u.boisestate.edu HEAD^

You should see results similar to what is show below.

$ git send-email --to youremail@u.boisestate.edu HEAD^
/tmp/T/NWEw4f1sIj/0001-Submit-project-2.patch

From: youremail@u.boisestate.edu
To:  youremail@u.boisestate.edu
Subject: [PATCH] Submit project
Date: Thu,  7 Dec 2023 20:31:55 -0700
Message-Id: <20231208033155.83099-1-shanepanter@boisestate.edu>
X-Mailer: git-send-email 2.39.3 (Apple Git-145)
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit

The Cc list above has been expanded by additional
addresses found in the patch commit message. By default
send-email prompts before sending whenever this occurs.
This behavior is controlled by the sendemail.confirm
configuration setting.

For additional information, run 'git send-email --help'.
To retain the current behavior, but squelch this message,
run 'git config --global sendemail.confirm auto'.

Send this email? ([y]es|[n]o|[e]dit|[q]uit|[a]ll): y
OK. Log says:
Server: smtp.gmail.com
MAIL FROM:  youremail@u.boisestate.edu
RCPT TO:  youremail@u.boisestate.edu
RCPT TO:  youremail@u.boisestate.edu
From: youremail@u.boisestate.edu
To:  youremail@u.boisestate.edu
Subject: [PATCH] Submit project 2
Date: Thu,  7 Dec 2023 20:31:55 -0700
Message-Id: <20231208033155.83099-1-shanepanter@boisestate.edu>
X-Mailer: git-send-email 2.39.3 (Apple Git-145)
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit

Result: 250

You should now be able to check your email and see your patch. Be aware that sometimes email delivery is slightly delayed so you may have to wait a few minutes for it to show up. Make sure and check your spam folder if you don't see any mail.

Test your patch

You can now get your patch from Gmail and test it to make sure that everything works and your patch was correct.

1. Checkout a new branch named test-patch from the upstream/master branch

git checkout upstream/master -b test-patch

2. Push your new test-patch branch to your repo instead of the upstream

 git push -u origin

3. Get the patch file from Gmail

4. Copy the email to your clip board

5. Create a new file and paste the contents that you just copied and save it in the root folder in a file named my-patch.txt.

6. Make sure you saved the file correctly. It should show up in the file explorer as shown below.

7. Now apply that patch to your new test-patch branch

git am my-patch.txt

8. Commit your patch

git commit -m "Testing my email patch"

9. Push your test patch branch to your Github Account

git push

10. After you have successfully applied the patch you can delete the file my-patch.txt. Don't commit the file my-patch.txt it is just a temporary file that you don't want to save.

11. Finally open up the browser again and make sure you have 3 branches master, submit, and test-patch. The submit and test-patch branches should be identical. Each should have exactly 1 commit from you with all your changes.

Submit your Patch for grading

Assuming you have successfully completed all the steps above with your own email and everything looked good you can now submit your patch for grading.

DANGER

Do not use the class mailing list to test your patch. You should only send an email to email is in the syllabus after you have tested the process with your own email. Spamming the mailing list with excessive patches will result in a lower grade.

When you submit to the mailing list you will automatically be cc'd on the email so you will have a copy in your own email as proof that you completed the assignment.

You are allowed to submit up to 3 times without penalty.

Open a terminal and submit your patch.

git checkout submit
git send-email --to email is in the syllabus HEAD^

Assuming all went well you are now complete! You have created a patch file from a squash merge, emailed it and tested the resulting patch. You are well on your way to becoming an advanced git user!

Submitting

You do not need to submit anything to canvas for this assignment. Your email is your submission, your grade will be updated after the due date (and late window) have passed.