Tech Today

Archive for the ‘Kernel Development’ 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

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

REQUIRES:

Compiling a [C] program in Linux

POSIX Message passing is supported in Unix, Linux, Mac OS X and many more.

The example shown here was derived in Ubuntu 9.04 using the Jaunty Jackalope Kernel Version: 2.6.28-11.

Okay, so first question what exactly is POSIX Message passing and why should I use it?

Well, POSIX stands for “Portable Operating System Interface for Unix” and it is a collection of standards governed by the IEEE.

Message passing is all about processes being able to communicate and synchronize with one another. Why do process need to communicate with one another? Well sometimes processes hold data that other processes may need. This doesn’t just hold true for process though, think about the World Wide Web. Computers need to be able to communicate with one another all the time, so wouldn’t it be nice to have some kind of mechanism in place that demonstrates that functionality? Yeah, I thought so too.

Well here is an example of processes communication utilizing the POSIX API. Think of it as like a client – server relationship; if that helps…

Overview:

Basically four external process will be communicating with a central process relaying temperature data back and forth. The goal here is to get all the processes to have the same temperature. Once that happens the central process will send a message indicating the system is stable and the processes can print out their final temp and end. Until the system is stable the external and central processes will continue to calculate new temperatures and relay them back and forth. [NOTE]: The four external processes are only aware of the central process, but the central process is aware of all the processes.

This starts by utilizing msgget(); This function will request a message queue ID using the mailbox name provided or create one if not existent previously.

Then use msgsnd(); to relay a message to a particular mailbox and use msgrcv(); the get a message from a mailbox.

First the “server side” code:

#include <sys/ipc.h>
#include <sys/types.h>
#include <sys/msg.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define CENTRAL_MAILBOX 1200    //Central Mailbox number 
#define NUM_PROCESSES 4           //Total number of external processes

struct {
long priority;         //message priority
int temp;             //temperature
int pid;                //process id
int stable;            //boolean for temperature stability
} msgp, cmbox;

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

   //Validate that a temperature was given via the command line
   if(argc != 2) {
      printf("USAGE: Too few arguments --./central.out Temp");
      exit(0);
   }

   printf("\nStarting Server...\n");

   //Set up local variables
   int i,result,length,status;             //counter for loops
   int uid = 0;                               //central process ID
   int initTemp = atoi(argv[1]);        //starting temperature
   int msqid[NUM_PROCESSES];       //mailbox IDs for all processes
   int unstable = 1;          //boolean to denote temp stability
   int tempAry[NUM_PROCESSES];   //array of process temperatures

   //Create the Central Servers Mailbox
   int msqidC = msgget(CENTRAL_MAILBOX, 0600 | IPC_CREAT);

   //Create the mailboxes for the other processes and store their IDs
   for(i = 1; i <= NUM_PROCESSES; i++){
      msqid[(i-1)] = msgget((CENTRAL_MAILBOX + i), 0600 | IPC_CREAT);
   }

   //Initialize the message to be sent
   msgp.priority = 1;
   msgp.pid = uid;
   msgp.temp = initTemp;
   msgp.stable = 1;

   /* The length is essentially the size 
       of the structure minus sizeof(mtype) */
   length = sizeof(msgp) - sizeof(long);

   //While the processes have different temperatures
   while(unstable == 1){
      int sumTemp = 0;        //sum up the temps as we loop
      int stable = 1;            //stability trap

      // Get new messages from the processes
      for(i = 0; i < NUM_PROCESSES; i++){
         result = msgrcv( msqidC, &cmbox, length, 1, 0);

         /* If any of the new temps are different from the old temps
             then we are still unstable. Set the new temp to the
             corresponding process ID in the array */
         if(tempAry[(cmbox.pid - 1)] != cmbox.temp) {
            stable = 0;
            tempAry[(cmbox.pid - 1)] = cmbox.temp;
         }

         //Add up all the temps as we go for the temperature algorithm
         sumTemp += cmbox.temp;
      }

      //When all the processes have the same temp twice:
      // 1) Break the loop
      // 2) Set the messages stable field to stable
      if(stable){
         printf("\Temperature Stabilized: %d\n", msgp.temp);
         unstable = 0;
         msgp.stable = 0;
      }
      else { //Calc a new temp and set the temp field in the message
         int newTemp = (2 * msgp.temp + sumTemp) / 6;
         msgp.temp = newTemp;
      }

      /* Send a new message to all processes 
          to inform of new temp or stability */
      for(i = 0; i < NUM_PROCESSES; i++){
         result = msgsnd( msqid[i], &msgp, length, 0);
      }
   }

   printf("\nShutting down Server...\n");

   //Remove the mailbox
   status = msgctl(msqidC, IPC_RMID, 0);

   //Validate nothing when wrong when trying to remove mailbox
   if(status != 0){
      printf("\nERROR closing mailbox\n");
   }
}

Next the “client side” external processes:

#include <sys/ipc.h>
#include <sys/types.h>
#include <sys/msg.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define CENTRAL_MAILBOX 1200    //Central Mailbox number

struct {
long priority;        //message priority
int temp;            //temperature
int pid;               //process id
int stable;          //boolean for temperature stability
} msgp, cmbox;

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

   /* Validate that a temperature and a Unique 
       process ID was given via the command  */
   if(argc != 3) {
      printf("USAGE: Too few arguments --./central.out Temp UID");
      exit(0);
   }

   //Setup local variables
   int unstable = 1;
   int result, length, status;
   int initTemp = atoi(argv[1]);
   int uid = atoi(argv[2]);

   //Create the Central Servers Mailbox
   int msqidC = msgget(CENTRAL_MAILBOX, 0600 | IPC_CREAT);

   //Create the mailbox for this process and store it's IDs
   int msqid = msgget((CENTRAL_MAILBOX + uid), 0600 | IPC_CREAT);

   //Initialize the message to be sent
   cmbox.priority = 1;
   cmbox.pid = uid;
   cmbox.temp = initTemp;
   cmbox.stable = 1;

   /* The length is essentially the size of 
       the structure minus sizeof(mtype) */
   length = sizeof(msgp) - sizeof(long);

   //While all the processes have different temps
   while(unstable == 1){
      //Send the current temp to the central server
      result = msgsnd( msqidC, &cmbox, length, 0);

      //Wait for a new message from the central server
      result = msgrcv( msqid, &msgp, length, 1, 0);

      //If the new message indicates all the processes have the same temp
      //break the loop and print out the final temperature
      if(msgp.stable == 0) {
         unstable = 0;
         printf("\nProcess %d Temp: %d\n", cmbox.pid, cmbox.temp);
      }
      else { //otherwise calculate the new temp and store it
         int newTemp = (cmbox.temp * 3 + 2 * msgp.temp) / 5;
         cmbox.temp = newTemp;
      }
   }

   //Remove the mailbox
   status = msgctl(msqid, IPC_RMID, 0);

   //Validate nothing when wrong when trying to remove mailbox
   if(status != 0){
      printf("\nERROR closing mailbox\n");
   }
}

START YOUR ENGINES:

Run each process in a separate terminal like so:

./external.out 100 1

./external.out 22 2

./external.out 50 3

./external.out 40 4

./central.out 60

OUTPUT:

lee@isis:~$ ./central.out 60

Starting Server...

Temperature Stabilized: 49

Shutting down Server...

lee@isis:~$ ./external.out 100 1

Process 1 Temp: 49

lee@isis:~$ ./external.out 22 2

Process 2 Temp: 49

lee@isis:~$ ./external.out 50 3

Process 3 Temp: 49

lee@isis:~$ ./external.out 40 4

Process 4 Temp: 49

Congratulations, you have just experienced process communication. Now, where can you take this mechanism from here?

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! =)

current Kernel version: 2.6.28-11

In /usr/src get the source and build tools by typing:

sudo apt-get install linux-source kernel-package fakeroot ncurses-dev

Unpack the source by typing:

sudo bzip2 -d linux-source-2.6.28.tar.bz2
sudo tar xvf linux-source-2.6.28.tar

Make a sym link to the linux source code by typing:

ln -s linux-source-2.6.28 linux

Enter the source directory:

cd linux

Then we are going to make a clean package using the current configuration of the current kernel since it already figured everything out for you.

sudo make-kpkg clean
sudo cp /boot/config-`uname -r` ./.config

Make any changes you want to the kernel here:

sudo make menuconfig

sudo fakeroot make-kpkg --initrd --append-to-version=-lml kernel_image kernel_headers
[NOTE]:–append-to-version” will append a string to the version number; here I am using my initials “lml”. You’re going to want to do this to distinguish your kernel builds apart.

This will give us the header and image output in /usr/src. Issuing these commands will install your new custom kernel:

sudo dpkg -i linux-image-2.6.28.9lml_2.6.28.9lml-10.00.Custom_i386.deb
sudo dpkg -i linux-headers-2.6.28.9lml_2.6.28.9lml-10.00.Custom_i386.deb

As you can see my initials “lml” have been appended in two places.

This also installs the new kernel to grub so next time you boot you will be able to select it.

To edit the grub options:

sudo nano /boot/grub/menu.lst

So, today I am working on understanding how processes communicate in the Linux OS. This code example is written in C and compiled in Ubuntu 9.04 using the Jaunty Jackalope Kernel version 2.6.28-11.

This code specifically prints out the Fibonacci sequence.

The parent process creates and attaches a shared memory segment, forks a child process (remember the child process shares the resources of the parent) , waits for the child to finish, prints out the contents of the shared memory, and finally detaches and removes the shared memory segment.

The child process runs through the Fibonacci algorithm, inserts the resultant into the next available space in shared memory and prints out the resultant to standard output.

This example accepts input from the command line with basic error checking. You know, make sure two args have been provided, they are between the min and max limits of the program; the BASICS.

CODE:

#include <sys/shm.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define MAX_SEQUENCE 10 // Max values to store in shared memory
#define MIN_SEQUENCE 2  // Min value the user can enter

//shared memory:
// 1) holds an array of numbers
// 2) holds how many numbers are in the array
typedef struct {
int fib_seq[MAX_SEQUENCE];
int sequence_size;
} shared_data;

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

pid_t pid;    //process ID
int segment_id; //Shared Memory ID
shared_data *mem; //Shared Memory Pointer

//check to validate atleast two arguments
if(argc != 2) {
printf(“USAGE ERROR: [0-9]\n”);
exit(0);
}

//validate the input is not larger then the MAX
if(atoi(argv[1]) > MAX_SEQUENCE) {
printf(“Max Input Size: %d\n”, MAX_SEQUENCE);
exit(0);
}

//validate the input is not smaller then the MIN
if(atoi(argv[1]) < MIN_SEQUENCE) {
printf(“Min Input Size: %d\n”, MIN_SEQUENCE);
exit(0);
}

// 1) create a new shared memory location ‘IPC_PRIVATE’
// 2) the size of our shared memory structure ‘sizeof(shared_data)’
// 3) Set Modes S_IRUSR and S_IWUSR so the owner can read and write to the shared memory ‘S_IRUSR|S_IWUSR’
segment_id = shmget(IPC_PRIVATE, sizeof(shared_data), S_IRUSR|S_IWUSR);

//attach the shared memory and get the pointer to the beginning location in memory
mem = (shared_data *) shmat(segment_id,NULL,0);

//set the size of the sequence to the argument that was passed in via command line
mem->sequence_size = atoi(argv[1]);

// fork a child process
pid = fork();

if(pid < 0) { /* error occured */
fprintf(stderr, “Fork Failed\n”);
return 1;
}
else if(pid == 0) { /* child process */
int counter = 0;
printf(“Child Fibonacci Sequence: “);

while(counter < mem->sequence_size) {
if(counter == 0){
//FIB of zero is always zero
mem->fib_seq[counter] = 0;
}
else if(counter == 1){
//FIB of one is always one
mem->fib_seq[counter] = 1;
}
else {
//The Fibonacci Sequence formula ‘R = fib(n-1) + fib(n-2)’
//The first two numbers in the sequence are always 0 and 1.
//To get a value in the sequence you will want to take the previous
//two numbers and add them together. For example:
// b + a = c
// [fib(d-1) = c] + [fib(d-2) = b] = R
// fib(0) = 0
// fib(1) = 1
// fib(2): 1 + 0 = 1
// fib(3): 1 + 1 = 2
// fib(4): 2 + 1 = 3
// fib(5): 3 + 2 = 5
// The next Fibonacci number in the sequence will be ‘8’
mem->fib_seq[counter] = mem->fib_seq[counter – 1] + mem->fib_seq[counter – 2];
}
printf(“%d “, mem->fib_seq[(counter)]);
counter++;
}
}
else { /* parent process */

/* parent will wait for the child process to complete */
wait(NULL);

//Print out shared memory
int count = 0;
printf(“\nParent Fibonacci Sequence: “);
while(count < mem->sequence_size){
printf(“%d “, mem->fib_seq[count]);
count++;
}

//detach shared memory
shmdt(mem);
//remove shared memory segment
shmctl(segment_id,IPC_RMID,NULL);
printf(“\nComplete\n”);
}

return 0;
}

output:


lee@isis:~$ ./a.out 0
Min Input Size: 2
lee@isis:~$ ./a.out 1
Min Input Size: 2
lee@isis:~$ ./a.out 2
Child Fibonacci Sequence: 0 1
Parent Fibonacci Sequence: 0 1
Complete
lee@isis:~$ ./a.out 3
Child Fibonacci Sequence: 0 1 1
Parent Fibonacci Sequence: 0 1 1
Complete
lee@isis:~$ ./a.out 4
Child Fibonacci Sequence: 0 1 1 2
Parent Fibonacci Sequence: 0 1 1 2
Complete
lee@isis:~$ ./a.out 5
Child Fibonacci Sequence: 0 1 1 2 3
Parent Fibonacci Sequence: 0 1 1 2 3
Complete