Tech Today

This blog has been moved to:

MacBoyPro.com/blog

Hope to see you there!

SO, today we are talking about the producer-consumer problem, and we are going to solve it utilizing a bounded-buffer and pthreads.

Let’s talk about a producer-consumer relationship for a second, shall we? Basically, the producer produces goods while the consumer consumes the goods and typically does something with them.

In our case our producer will produce an item and place it in a bound-buffer for the consumer. Then the consumer will remove the item from the buffer and print it to the screen.

At this point you may be asking yourself what exactly is a “bound-buffer”? Well a buffer is a container of sorts; a bound-buffer is a container with a limit. We have to be very careful in our case that we don’t over fill the buffer or remove something that isn’t there; in c this will produce a segmentation fault.

The last thing we need to talk about before I explain the problem is semaphores. What, where, when, why and how???

What: A synchronization tool used in concurrent programming

Where: We will use semaphores in any place where we may have concurrency issues. In other words any place where we feel more than one thread will access the data or structure at any given time.

When: To help solve concurrency issues when programming with threads.

Why: Think about how registers work in the operating system for a second. Here is an example of how registers work when you increment a counter-

register1 = counter;

register1 = register1 + 1;

counter = register1;

Now image two threads manipulating this same example but one thread is decrementing -

(T1) register1 = counter;              [register1 = 5]

(T1) register1 = register1 + 1;    [register1 = 6]

(T2) register2 = counter;             [register2 = 5]

(T2) register2 = register2 – 1;     [register2 = 4]

(T1) counter = register1;             [counter = 6]

(T2) counter = register2;            [counter = 4]

WOW, that does look good, does it?! Because both threads were allowed to run without synchronization our counter now has a definitely wrong value. With synchronization the answer should come out to be 5 like it started.

How: We implement a semaphore as an integer value that is only accessible through two atomic operations wait() and signal(). Defined as follows:

/* The wait operation */
wait(S) {
   while(S <= 0); //no-operation
   S--;
}

/* The signal operation */
signal(S) {
   S++;
}

S: Semaphore

The operation wait() tells the system that we are about to enter a critical section and signal() notifies that we have left the critical section and it is now accessible to other threads.

Therefore:

wait(mutex);

//critical section where the work is done

signal(mutex)

//continue on with life

Mutex stands for mutual exclusion. Meaning only one process may execute the section at a time.

Are we starting to get it? Well if not we have an example that demonstrates how semaphores are used in reference to pthreads coming up right after this problem walk-through.

Basically, we are going to have a program that creates an N number of producer and consumer threads. The job of the producer will be to generate a random number and place it in a bound-buffer. The role of the consumer will be to remove items from the bound-buffer and print them to the screen. Sounds simple right? Well, yes and no. Remember the big issue here is concurrency so we will be using semaphores to help prevent any issues that might occur. To double our efforts we will also be using a pthread mutex lock to further guarantee synchronization.

The user will pass in three arguments to start to application: <INT, time for the main method to sleep before termination> <INT, Number of producer threads> <INT, number of consumer threads>

We will then use a function in initialize the data, semaphores, mutex lock, and pthread attributes.

Create the producer threads.

Create the consumer threads.

Put main() to sleep().

Exit the program.

If you are kind of rusty on how pthreads work, I have a previous tutorial that may be some help in understanding them:

Prime numbers using POSIX threads on Linux in [C]

That will give you a clearer picture on how to create a pthread.

Time for the code…

CODE:

/* buffer.h */
typedef int buffer_item;
#define BUFFER_SIZE 5

/* main.c */

#include <stdlib.h>
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include "buffer.h"

#define RAND_DIVISOR 100000000
#define TRUE 1

/* The mutex lock */
pthread_mutex_t mutex;

/* the semaphores */
sem_t full, empty;

/* the buffer */
buffer_item buffer[BUFFER_SIZE];

/* buffer counter */
int counter;

pthread_t tid;       //Thread ID
pthread_attr_t attr; //Set of thread attributes

void *producer(void *param); /* the producer thread */
void *consumer(void *param); /* the consumer thread */

void initializeData() {

   /* Create the mutex lock */
   pthread_mutex_init(&mutex, NULL);

   /* Create the full semaphore and initialize to 0 */
   sem_init(&full, 0, 0);

   /* Create the empty semaphore and initialize to BUFFER_SIZE */
   sem_init(&empty, 0, BUFFER_SIZE);

   /* Get the default attributes */
   pthread_attr_init(&attr);

   /* init buffer */
   counter = 0;
}

/* Producer Thread */
void *producer(void *param) {
   buffer_item item;

   while(TRUE) {
      /* sleep for a random period of time */
      int rNum = rand() / RAND_DIVISOR;
      sleep(rNum);

      /* generate a random number */
      item = rand();

      /* acquire the empty lock */
      sem_wait(&empty);
      /* acquire the mutex lock */
      pthread_mutex_lock(&mutex);

      if(insert_item(item)) {
         fprintf(stderr, " Producer report error condition\n");
      }
      else {
         printf("producer produced %d\n", item);
      }
      /* release the mutex lock */
      pthread_mutex_unlock(&mutex);
      /* signal full */
      sem_post(&full);
   }
}

/* Consumer Thread */
void *consumer(void *param) {
   buffer_item item;

   while(TRUE) {
      /* sleep for a random period of time */
      int rNum = rand() / RAND_DIVISOR;
      sleep(rNum);

      /* aquire the full lock */
      sem_wait(&full);
      /* aquire the mutex lock */
      pthread_mutex_lock(&mutex);
      if(remove_item(&item)) {
         fprintf(stderr, "Consumer report error condition\n");
      }
      else {
         printf("consumer consumed %d\n", item);
      }
      /* release the mutex lock */
      pthread_mutex_unlock(&mutex);
      /* signal empty */
      sem_post(&empty);
   }
}

/* Add an item to the buffer */
int insert_item(buffer_item item) {
   /* When the buffer is not full add the item
      and increment the counter*/
   if(counter < BUFFER_SIZE) {
      buffer[counter] = item;
      counter++;
      return 0;
   }
   else { /* Error the buffer is full */
      return -1;
   }
}

/* Remove an item from the buffer */
int remove_item(buffer_item *item) {
   /* When the buffer is not empty remove the item
      and decrement the counter */
   if(counter > 0) {
      *item = buffer[(counter-1)];
      counter--;
      return 0;
   }
   else { /* Error buffer empty */
      return -1;
   }
}

int main(int argc, char *argv[]) {
   /* Loop counter */
   int i;

   /* Verify the correct number of arguments were passed in */
   if(argc != 4) {
      fprintf(stderr, "USAGE:./main.out <INT> <INT> <INT>\n");
   }

   int mainSleepTime = atoi(argv[1]); /* Time in seconds for main to sleep */
   int numProd = atoi(argv[2]); /* Number of producer threads */
   int numCons = atoi(argv[3]); /* Number of consumer threads */

   /* Initialize the app */
   initializeData();

   /* Create the producer threads */
   for(i = 0; i < numProd; i++) {
      /* Create the thread */
      pthread_create(&tid,&attr,producer,NULL);
    }

   /* Create the consumer threads */
   for(i = 0; i < numCons; i++) {
      /* Create the thread */
      pthread_create(&tid,&attr,consumer,NULL);
   }

   /* Sleep for the specified amount of time in milliseconds */
   sleep(mainSleepTime);

   /* Exit the program */
   printf("Exit the program\n");
   exit(0);
}

OUTPUT:

lee@isis:~/programming/c/producer-consumer$ ./pc.out 10 10 10
producer produced 35005211
consumer consumed 35005211
producer produced 1726956429
consumer consumed 1726956429
producer produced 278722862
consumer consumed 278722862
producer produced 468703135
producer produced 1801979802
producer produced 635723058
producer produced 1125898167
consumer consumed 1125898167
Exit the program

Here, we have the output for the program. As you can see we told main to quit after 10 seconds and we produced 10 producer and 10 consumer threads.

Ever wonder what the word enum means in [C]? I know most of us don’t spend the majority of our days pondering over its definition but still I thought I would add a simple tutorial to my repertoire depicting its uses.

So basically, enum creates a list of aliases. What are aliases? Well an alias is something that assumes the identity of something else. Think about your favourite spy assuming the alias of a henchmen to infiltrate the enemy base. The spy in this case assumed the identity of someone else. Got it? Great!

When we say:

enum person

You are getting ready to list a bunch of aliases for a person. Like so:

enum person {henchmen, guard, janitor};

Next we declare a variable for our person called spy and now aliases for a spy are a henchmen, guard, or janitor.

person spy;

The spy just isn’t going to use the same alias all the time, he may want to switch one out for another. So to apply an alias to a spy we write:

spy = henchmen;

Now the spy assumes the identity of the henchmen.

If we were to print out the value of the spy to the command line we would see that the value of a spy is 0. Consequently if we were to assign the spy the alias of the guard he we have a value of 1 and finally if he were to assume the janitor alias he would have a value of 2. Now thats kool right?! By not defining an initial value for a henchmen you are saying that you want a henchmen to be equal to zero and every alias after that to be one plus the previous number. If you decide to define the first value like so:

enum person {henchmen=5, guard, janitor};

Then henchmen will be 5, guard 6, and janitor 7.

Okay, now that you understand what enum does lets drive it home with an interactive program written using one. This simple program uses the months of the year defined 1 – 12. The user inputs the number for a month and the program uses aliases to print out which month was inputed.

CODE:

#include <stdio.h>
#include <stdlib.h>

main(int argc, char *argv[]) {
 /*
 * Define a list of aliases
 */
 enum months {Jan=1, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec};

 enum months month;        /* define 'month' variable of type 'months' */

 //Verify an arg was passed in
 if(argc != 2) {
    fprintf(stderr, "USAGE: ./month.out <Integer value>\n");
    exit(1);
 }

 int userInput = atoi(argv[1]);

 //Verify the input is greater then zero
 if(userInput <= 0 && userInput <= 12) {
    fprintf(stderr, "USAGE: %d must be 1 <= N <= 12\n", userInput);
    exit(1);
 }

 /* Using aliases print out a statement
 that corresponds to the month the user choose */
 switch(userInput) {
    case 1:
       month = Jan;
       printf("January is the %dst month in the year.\n", month);
       break;
    case 2:
       month = Feb;
       printf("February is the %dnd month in the year.\n", month);
       break;
    case 3:
       month = Mar;
       printf("March is the %drd month in the year.\n", month);
       break;
    case 4:
       month = Apr;
       printf("April is the %dth month in the year.\n", month);
       break;
    case 5:
       month = May;
       printf("May is the %dth month in the year.\n", month);
       break;
    case 6:
       month = Jun;
       printf("June is the %dth month in the year.\n", month);
       break;
    case 7:
       month = Jul;
       printf("July is the %dth month in the year.\n", month);
       break;
    case 8:
       month = Aug;
       printf("August is the %dth month in the year.\n", month);
       break;
    case 9:
       month = Sep;
       printf("September is the %dth month in the year.\n", month);
       break;
    case 10:
       month = Oct;
       printf("October is the %dth month in the year.\n", month);
       break;
    case 11:
       month = Nov;
       printf("November is the %dth month in the year.\n", month);
       break;
    case 12:
       month = Dec;
       printf("December is the %dth month in the year.\n", month);
       break;
 }
}

Output:
lee@isis:~/programming/c/enum$ ./month.out 1
January is the 1st month in the year.
lee@isis:~/programming/c/enum$ ./month.out 2
February is the 2nd month in the year.

Now, you may be asking yourself why you would want to use enum in the first place? Well enum will make your code more readable and cut down on the amount of code that you would have to write to sequentially initialise all those variables.

This concludes the tutorial on enum. I hope you have enjoyed and happy coding!

So, today I downloaded a torrent that contained a bunch of files that had a file type of: R00, R 01, R02… and I was like ???? I hadn’t seen the .RAR file yet so at this point I had no idea what was going on. It turns out these are a bunch of mini archives that are associated with a RAR archive file. To un-archive  RAR content you will have to download:

Linux:

sudo apt-get install unrar

Windows:

WinRAR

Mac OS X:

UnRarX

As long as the .RNN files are in the same directory as the .RAR file the extractors should be able to pick them up. Happy RARing :)

Today we are doing a little learning in the area of PThreads and Matrix multiplication. First, lets start by learning how to multiply matrices.

We are not going to go really in depth into matrices if you would like to learn more, check out: Tutorial: Matrix Multiplication

Matrix A:  [ 10     15     20 ]

Matrix B:

3
4
1

Rule numero uno:

The length of the rows on matrix A must equal the length of the columns on matrix B.

So if A is a 1 x 3 matrix and B is a 3 x 4 Matrix then C will be a 1 x 4 matrix. See how the 3’s canceled out to give us the dimensions of the resultant matrix?

Rule #2:

What we really wanna do is multiply the rows in A by the columns in B. SO, we just have to keep telling ourselves when we do these problems rows by columns, rows by columns.

Lets take a look at our example above: [Rows by column] (10 * 3) + (15 * 4) + (20 * 1) = [110] Therefore, matrix C is a 1 x 1 matrix with a resultant of 110.

One more:

Matrix A:

2 4 -1
3 -2 -1

Matrix B:

6 0 3
2 1 -2
0 0 1

Here, we have a 2 x 3 Matrix A and a 3 x 3 Matrix B. This will give us a 2 x 3 Matrix C.

[Rows by columns]

1,1 : (2 * 6) + (4 * 2) + (-1 * 0) = 20

1,2 : (2 * 0) + (4 * 1) + (0 * 1) = 4

1,3 : (2 * 3) + (-4 * -2) + (-1 * 1) = -3

2,1 : (3 * 6) + (-2 * 2) + (-1 * 0) = 14

2,2 : (3 * 0) + (-2 * 1) + (-1 * 0) = -2

2,3 : (3 * 3) + (-2 * -2) + (-1 * 1) = 12

Matrix C:

20 4 -3
14 -2 12

Okay, great, now we understand matrix multiplication. If you are still having issues I recommend visiting the link above, its basically amazing.

Now on to PThreads on linux. For this next code tutorial we are going to be exploring pthreads a little further then last time. This time our goal is to calculate every matrix coordinate with a different thread. In my previous post,

Prime numbers using POSIX threads on Linux in [C], we discussed how to use one thread to calculate a bunch of prime numbers and print them to the command line. This time it gets a little trickier, but not too tricky.

We are first going to define our matrices statically, and then define a structure that will hold row and column information for each thread. Important question alert!! Why do we need a structure to hold row and column information for each thread??? Well, like I said before we need to assign each thread its own coordinate to figure out in the resulting matrix. Remember when we were learning how to multiply matrices earlier? Rows by columns, rows by columns? I practically beat you over the head with it, I’m sure you remember. Well that’s exactly how each thread is going to compute its coordinate, each thread needs a row and a column to multiply. Then we will create two “for” loops, one for rows and an inner one for columns. The inner one will create a new thread and call the join method so the parent will wait for all the threads to complete before it prints out the resulting matrix (the parent can print the resulting matrix because threads share all resources with its parent, remember?).

Time for the code, yay!

CODE:

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

#define M 3
#define K 2
#define N 3
#define NUM_THREADS 10

int A [M][K] = { {1,4}, {2,5}, {3,6} };
int B [K][N] = { {8,7,6}, {5,4,3} };
int C [M][N];

struct v {
   int i; /* row */
   int j; /* column */
};

void *runner(void *param); /* the thread */

int main(int argc, char *argv[]) {

   int i,j, count = 0;
   for(i = 0; i < M; i++) {
      for(j = 0; j < N; j++) {
         //Assign a row and column for each thread
         struct v *data = (struct v *) malloc(sizeof(struct v));
         data->i = i;
         data->j = j;
         /* Now create the thread passing it data as a parameter */
         pthread_t tid;       //Thread ID
         pthread_attr_t attr; //Set of thread attributes
         //Get the default attributes
         pthread_attr_init(&attr);
         //Create the thread
         pthread_create(&tid,&attr,runner,data);
         //Make sure the parent waits for all thread to complete
         pthread_join(tid, NULL);
         count++;
      }
   }

   //Print out the resulting matrix
   for(i = 0; i < M; i++) {
      for(j = 0; j < N; j++) {
         printf("%d ", C[i][j]);
      }
      printf("\n");
   }
}

//The thread will begin control in this function
void *runner(void *param) {
   struct v *data = param; // the structure that holds our data
   int n, sum = 0; //the counter and sum

   //Row multiplied by column
   for(n = 0; n< K; n++){
      sum += A[data->i][n] * B[n][data->j];
   }
   //assign the sum to its coordinate
   C[data->i][data->j] = sum;

   //Exit the thread
   pthread_exit(0);
}

Output:

lee@isis:~/programming/c/matrix$ ./matrix.out

28 23 18

41 34 27

54 45 36

Yay! Look at that it worked! Go figure, haha. If you are still having problems understanding how matrices work maybe you should write this code out by hand and see exactly what its doing and how its traversing the rows and columns.

Quick reminder, in order to compile c programs with the use of pthread in linux you need to add the -lpthread arg to gcc like so:

gcc -lpthread -o matrix.out matrix.c

Prime Numbers

So, first lets talk a little about prime numbers. What makes a number prime? Well a prime number is prime when it is only divisible by one and itself. Take for example the number 3, 3 can only be divided by one and three and have a remainder of zero. If you try to divide by two then you will get a remainder of one. Therefore 3 is a prime number. Lets take another example the number 4, 4 is not a prime number because when you divide it by 2 you get a remainder of zero. Our definition states that a number can only have a remainder of zero when divided by one and itself, the number 4 clearly breaks this rule when divided by 2. 5 on the other hand can’t be divided by anything but one and itself so it’s prime. Get the hang of it yet?

So now that we understand what prime numbers are lets try and make a simple sudo code algorithm that depicts this behaviour. Lets say someone comes up to you on the street and asks you to list every prime number that comes before what ever number (we are going to call this the “upper limit”) they ask you.

FOR every number X that comes before our upper limit

FOR every number Y that comes before X

IF X MOD Y doesn’t equal zero

THEN this number must be prime

ELSE X must be divisible by some Y so it is NOT a prime number

[REMEMBER] Mod or Modulus (%) division is remainder division. EX 1: 3 %(MOD) 1 = 0; Because when you divide 3 by 1, 1 goes into 3, 3 times. This gives us a remainder of zero. EX 2: 5 % 3 = 2; Because 3 goes into 5 once, so 2 is left over as the remainder.

Modulus division is really going to help us with this prime number problem.

POSIX Threads

Okay, so you got the prime number thing down, you understand it (or will shortly ;) ). Now it is time to talk about POSIX threads in linux. They kind of work like java threads in the sense that java has the run method it calls after you use the start function. Well, POSIX threads in linux have a create method that accepts a function as one of its parameters, this function is not called directly but rather the creation process calls it for you.

How do you create a thread?

Lets take a look at the code example below:

CODE:

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

void *runner(void *param); /* the thread */

int main(int argc, char *argv[]) {

   //Verify two args were passed in
   if(argc < 2) {
      fprintf(stderr, "USAGE: ./prime.out <Integer value>\n");
      exit(1);
   }

   //verify the input is greater then or equal to two
   if(atoi(argv[1]) < 2) {
      fprintf(stderr, "USAGE: %d must be >= 2\n", atoi(argv[1]));
      exit(1);
   }

   pthread_t tid;       //Thread ID
   pthread_attr_t attr; //Set of thread attributes

   printf("Prime Numbers: ");

   //Get the default attributes
   pthread_attr_init(&attr);
   //Create the thread
   pthread_create(&tid,&attr,runner,argv[1]);
   //Wait for the thread to exit
   pthread_join(tid,NULL);
   printf("\nComplete\n");
}

//The thread will begin control in this function
void *runner(void *param) {
   int i,j,upper = atoi(param);
   /* Check to see if a number is prime */
   for(i = 2; i < upper; i++) {
   int trap = 0;
      /* Check each number for divisibility */
      for(j = 2; j < i; j++) {
         int result = i % j;
         /* If any of the numbers divide cleanly
             then this number is not prime. So
             stop checking. */
         if(result == 0) {
            trap = 1;
            break;
         }
      }
      //No numbers divided cleanly so this number must be prime
      if(trap == 0) {
         printf("[%d] ", i);
      }
   }
   //Exit the thread
   pthread_exit(0);
}

OUTPUT:

lee@isis:~$ ./prime.out 100
Prime Numbers: [2] [3] [5] [7] [11] [13] [17] [19] [23] [29] [31] [37] [41] [43] [47] [53] [59] [61] [67] [71] [73] [79] [83] [89] [97]

As you can see we made use of the POSIX pthread API. We set default attributes on the thread then created it. When we created it we passed in the thread ID, attributes, the function we need to call as the thread, and finaly the params. In this case we passed in the users input because it was already a pointer so it was easily passed with out casting.

In our prime number algorithm we don’t check 1 or the number itself to see if it divides cleanly, mainly because we already know it will so really there is no point in checking; it would also make our algorithim more complex for no reason and thats never a good thing.

Happy coding, hope this helped in some way. :)

[NOTE]: Compiling pthreads using gcc requires a command line option. EX. :gcc -lpthread -o prime.out prime.c

To compile a [C] program in linux

on the command line simply type:

gcc -o foo.out foo.c

Where:

gcc is the compiler

-o is an option that tells it to use the next string as the file name

foo.c is the file you are trying to compile

Happy Compiling :)

Follow

Get every new post delivered to your Inbox.