Tech Today

Archive for the ‘C Language’ Category

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.

Advertisements

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!

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

REQUIRES:

Compiling a [C] program in Linux

Today we are going to add a custom “Hello World” system call to Ubuntu 9.04 Linux using the kernel version: 2.6.28-11.

First things first, we need to figure out how to get the source and build a custom kernel. Instructions for how to do this can be found in my previous post:

Compiling a UBUNTU Jaunty Jackalope Kernel

Ok, now that we know how to compile a shiny new custom kernel, we need to create our system call:

/* adding helloworld system call */
#include <linux/linkage.h>

asmlinkage int sys_helloworld() {
   printk(KERN_EMERG "Hello World!\n");
   return 0;
}

Now, I opted to add this to /usr/src/linux/kernel/sys.c. However, you can always create your own file and add it to the kernel’s makefile. If you decide to go down this route you are also going to need to #include <linux/kernel.h> to the code above; the file kernel/sys.c already includes that package.

Lets explain what’s going on here a little shall we?

asmlinkage: thats there to indicate the code is written in ‘C’ as oppose to C++

printk: is used to print out kernel log messages. These messages are stored in /var/log/syslog.

KERN_EMERG: is used for logging emergency messages; these usually happen before a crash. The Kernel has 8 different types of log levels, a few others are- KERN_DEBUG, KERN_ALERT, KERN_ERR

Alright, now that we have our system call we need to let the kernel know its there and can be used.

To do this we will have to modify a few files.

Modify /usr/src/linux/arch/x86/include/asm/unistd_32.h and add:

#define __NR_helloworld         333

to the list of system call numbers. This is the system calls unique identification number.

Modify /usr/src/linux/arch/x86/include/asm/syscalls.h and add:

/* X86_32 only */
/* kernel/sys.c */
asmlinkage int sys_helloworld();

under the “/* X86_32 only */” comment. This registers the system call.

Modify /usr/src/linux/arch/x86/kernel/syscall_table_32.h and add:

.long sys_helloworld           /* 333 */

to the bottom of the list. This also registers the system call.

Alright, now build your new modified kernel..this is going to take a while…

OK, SO 2 hours later…Install the new kernel and reboot.

Now we have to build a little c-program to use that shiny new system call right? *How Exciting!*

#include <sys/syscall.h>
#include <unistd.h>
#include <stdio.h>

#define __NR_helloworld        333    /* or     whatever you set it in unistd.h */

int helloworld() {
   return (int) syscall(__NR_helloworld);
};

main () {
   printf("The return code from the helloworld system call is %d\n", helloworld());
}

Compile it and lets see what happens!

Output [Command Line]:

lee@isis:~$ ./a.out
The return code from the helloworld system call is 0

Output [/var/log/syslog]:

May 14 23:19:02 isis kernel: [48397.527522] Hello World!

Exactly what we expected. Our program returned ‘0’ from the system call execution AND we have the output in the logs. YAY!

[NOTE]: Now, you may have issues with flushing the buffer at this step so you may have to trigger an event on the system like reset your wifi connection to actually see the print out in the log. However, having the newline at the end of the message is supposed to guarantee the flush.

Congratulations you just made your very own system call in your very own custom kernel. Mom would be so proud, if only she knew what a kernel or a system call was!

Enjoy! =)