Do Zak's homework!

[Zakath]

No, I'm not really asking for you to do it FOR me. In fact, I've already done it. However, if you're curious about what sort of stuff a college CS course might make you do, this topic is for you! Here you can see a couple assignments, followed by their solutions.

Introduction
This assignment is intended to introduce you to the process manipulation facilities in the Unix Operating System. You are to implement the program described below.

Command Execution
You are to write a program doit that takes another
command as an argument and executes that command. For instance, executing:

Code Select Expand


% doit cat /etc/motd

would invoke the cat command on the file /etc/motd, which will print the current "message of the day." After execution of the specified command has completed, doit should display statistics that show some of the system resources the command used. In particular, doit should print:

1. the amount of CPU time used (both user and system time) (in milliseconds),
2. the elapsed "wall-clock" time for the command to execute (in milliseconds),
3. the number of times the process was preempted involuntarily (e.g. time slice expired, preemption by higher priority process),
4. the number of times the process gave up the CPU voluntarily (e.g. waiting for a resource),
5. the number of page faults, and
6. the number of page faults that could be satisfied from the kernel's internal cache (e.g. did not require any input/output operations)

Basic Command Shell
Your program should be extended to behave like a shell program if no arguments are given at the command line (it should work as before if arguments are given on the command line). Your program should continually prompt for a command (which may have multiple arguments separated by white space) then execute the command and print the statistics. This work will involve breaking the line of text you read into an argument list. Your program should handle two "built-in" commands, which are handled internally by your shell.

exit - causes your shell to terminate.

cd dir - causes your shell to change the directory to dir.

Your program should also exit if an end-of-file is detected on input. You may assume that a line of input will contain no more than 128 characters or more than 32 distinct arguments.

Note: you may not use the system call system available in Unix to execute the entered command.

[Zakath]

Code Select Expand

//doit.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <sys/time.h>
#include <sys/resource.h>

//runs a specified command
int proccmd( char *const * );
//prints the information stored in the input to stdout
void printresinfo( const struct rusage );

struct rusage oldresinfo;

int main( int argc, char **argv ) {
   oldresinfo.ru_utime.tv_sec = 0;
   oldresinfo.ru_utime.tv_usec = 0;
   oldresinfo.ru_stime.tv_sec = 0;
   oldresinfo.ru_stime.tv_usec = 0;
   oldresinfo.ru_nivcsw = 0;
   oldresinfo.ru_nvcsw = 0;
   oldresinfo.ru_majflt = 0;
   oldresinfo.ru_minflt = 0;
   
   //shell mode
   if ( argc <= 1 ) {
      char inputstring[ 129 ], *arguments[ 32 ];

      //always loop unless eof or exit command issued
      while( 1 ) {
         printf( "==>" );
         //get a line of text from stdin
         if ( fgets( inputstring, 129, stdin ) == NULL )
            break;
         if ( inputstring[0] == '\n' )
            continue;
         size_t len = strlen( inputstring );
         if ( inputstring[ len - 1 ] == '\n' )
            inputstring[ len - 1 ] = '\0';
         //break inputstring into tokens and
         //put pointers to each token into an array
         arguments[ 0 ] = strtok( inputstring, " " );
         for( int i = 1; i < 32; i++ ) {
            arguments[ i ] = strtok( NULL, " " );
            if ( arguments[ i ] == NULL )
               break;
         }
         //exit command
         if ( !strcmp( arguments[0], "exit" ))
            break;
         //cd command
         else if ( !strcmp( arguments[0], "cd" )) {
            if ( chdir( ( arguments[ 1 ] == NULL ) ? getenv( "HOME" ) :
                     arguments[ 1 ] ) < 0 )
               printf( "%s\n", strerror( errno ));
         }
         //other command
         else proccmd( arguments );
      }
   }
   //run once mode
   else {
      if ( proccmd( (argv + 1)) < 0 )
         exit( 1 );
   }

   return 0;
}

int proccmd( char *const *args ) {
   timeval tval1, tval2;
   struct timezone tzone;
   gettimeofday( &tval1, &tzone );
   int pid;
   
   if ( ( pid = fork()) < 0 ) {
      printf( "%s\n", strerror( errno ));
      return 1;
   }
   //child process
   else if ( pid == 0 ) {
      if ( execvp( args[0], args ) < 0 ) {
         printf( "%s\n", strerror( errno ));
         return 1;
      }
   }
   //parent process
   else {
      wait( 0 );
      gettimeofday( &tval2, &tzone );
      tval2.tv_sec -= tval1.tv_sec;
      tval2.tv_usec -= tval1.tv_usec;
      printf( "\nWall-clock time used: %dms\n",
         ( ( tval2.tv_sec * 1000 ) + ( tval2.tv_usec / 1000 )));
      struct rusage newresinfo;
      if ( getrusage( RUSAGE_CHILDREN, &newresinfo ) < 0 ) {
         printf( "%s\n", strerror( errno ));
         return 1;
      }
      //determine exact resource usage for last child process
      //then print it
      else {
         oldresinfo.ru_utime.tv_sec = newresinfo.ru_utime.tv_sec -
            oldresinfo.ru_utime.tv_sec;
         oldresinfo.ru_utime.tv_usec = newresinfo.ru_utime.tv_usec -
            oldresinfo.ru_utime.tv_usec;
         oldresinfo.ru_stime.tv_sec = newresinfo.ru_stime.tv_sec -
            oldresinfo.ru_stime.tv_sec;
         oldresinfo.ru_stime.tv_usec = newresinfo.ru_stime.tv_usec -
            oldresinfo.ru_stime.tv_usec;
         oldresinfo.ru_nivcsw = newresinfo.ru_nivcsw - oldresinfo.ru_nivcsw;
         oldresinfo.ru_nvcsw = newresinfo.ru_nvcsw - oldresinfo.ru_nvcsw;
         oldresinfo.ru_majflt = newresinfo.ru_majflt - oldresinfo.ru_majflt;
         oldresinfo.ru_minflt = newresinfo.ru_minflt - oldresinfo.ru_minflt;
         printresinfo( oldresinfo );
         oldresinfo = newresinfo;
      }
   }
   return 0;
}

void printresinfo( const struct rusage ru ) {
   printf( "User CPU time used: %dms\n",
      ( ( ru.ru_utime.tv_sec * 1000 ) + ( ru.ru_utime.tv_usec / 1000 )));
   printf( "System CPU time used: %dms\n",
      ( ( ru.ru_stime.tv_sec * 1000 ) + ( ru.ru_stime.tv_usec / 1000 )));
   printf( "Involuntary context switches: %d\n", ru.ru_nivcsw );
   printf( "Voluntary context switches: %d\n", ru.ru_nvcsw );
   printf( "Page faults requiring I/O: %d\n", ru.ru_majflt );
   printf( "Page faults reclaimed: %d\n", ru.ru_minflt );
}

[Zakath]

Introduction
The use of threads allows for easy sharing of resources within a process with mechanisms such as mutex locks and semaphores for coordinating the actions of the threads within the process. In this project you will use these facilities to build a message passing mechanism that can be used among a set of threads within the same process. You will use the facilities of the pthreads library for thread and synchronization routines. To exercise these routines you will build a multi-threaded program to add up a range of numbers.

Problem
The basic idea of this assignment is to create a number of threads and to associate with each thread a "mailbox" where a single message for that thread can be stored. Because one thread may be trying to store a message in another's mailbox that already contains a message, you will need to use semaphores in order to control access to each thread's mailbox. The number of threads in your program should be controlled by an argument given on the command line to your program (use atoi() to convert a string to an integer). You should use the constant MAXTHREAD with a value of 10 for the maximum number of threads that can be created.
The parent thread in your program will be known as "thread 0" with threads 1 to the number given on the command line being threads created using the routine pthread_create(). In creating the threads, your program will need to remember the thread id stored in the first argument to pthread_create() for later use.
Associated with each thread is a mailbox. A mailbox contains a message that is defined by the following C/C++ structure:

Code Select Expand


struct msg {
   int iFrom;   /* who sent the message (0 .. number-of-threads) */
   int type;   /* its type */
   int value1;   /* first value */
   int value2;   /* second value */
};

Notice that the identifiers used in messages are in the range 0 to the number of threads.
We will call this the "mailbox id" of a thread to distinguish it from the thread id returned by pthread_create(). The type of the message can either be RANGE or ALLDONE as defined below.

Code Select Expand


#define RANGE 1
#define ALLDONE 2

Because each thread has one mailbox associated with it, you should define an array of mailboxes (of length MAXTHREAD+1) to store one message for each potential thread. Because mailboxes must be shared by all threads this array must be defined as a global variable. Alternately, you can dynamically allocate only enough space for the number of threads given on the command line.
Similarly, semaphores should be created to control access to each mailbox. These semaphores should be created using the routine sem_init() that is available by linking with the "rt" library in
Unix/Linux. These semaphores should also be created by the main thread before it creates the other threads. All creation of semaphores for the mailboxes should be done in the routine InitMailbox(), which you need to write.
To handle access to each thread's mailbox you must write two procedures: SendMsg() and RecvMsg(). These procedures have the following interfaces

Code Select Expand


SendMsg(int iTo, struct msg *pMsg)   // msg as ptr, C/C++
SendMsg(int iTo, struct msg &Msg)   // msg as reference, C++
/* iTo - mailbox to send to */
/* pMsg/Msg - message to be sent */

RecvMsg(int iFrom, struct msg *pMsg)   // msg as ptr, C/C++
RecvMsg(int iFrom, struct msg &Msg)   // msg as reference, C++
/* iFrom - mailbox to receive from */
/* pMsg/Msg - message structure to fill in with received message */

The index of a thread is simply its number so the index of the parent thread is zero, the first created thread is one, etc. Each thread must have its own index. The SendMsg() routine should block if another message is already in the recipient's mailbox. Similarly, the RecvMsg() routine should block if no message is available in the mailbox.

Test program
After setting up the mailboxes and creating the threads your program will need to exercise these routines. As a simple test, you will use multiple threads to add up the numbers between one and an integer given on the command line. Once a thread is created, it should wait for a message of type RANGE from the parent thread (mailbox id 0) by calling RecvMsg() with its mailbox id as the first argument. When it receives such a message, the child thread should add the numbers between value1 and value2 and return the result to the parent thread with a message of type ALLDONE. The routine pthread_exit() can be used to terminate a thread before the end of the code if need be.
Once the parent thread has received ALLDONE responses from all created threads, it should print the summary total of all response and wait for each created thread to complete using pthread_join().
Once each thread has completed the parent should clean up semaphores it has created and terminate.
The solution to the project should be called addem with a sample invocation shown below.

Code Select Expand


addem 10 100
The total for 1 to 100 using 10 threads is 5050.

Routines
In summary, the routines you must write with the given interface:
InitMailbox() - return 0 on success, -1 on failure. Initializes semaphores.
CleanupMailbox() - return 0 on success, -1 on failure. Cleans up all semaphores. Should be called whenever the parent thread exits.
SendMsg(iTo, Msg) - sends the message to the destination mailbox.
RecvMsg(iFrom, Msg) - receives a message from the source mailbox.

[Zakath]

Code Select Expand

//addem.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>

#define NO_MESSAGE 0
#define RANGE 1
#define ALLDONE 2
#define MAXTHREAD 10

//msg structure - used with mailboxes
typedef struct msg {
   int nFrom;
   int nType;
   int nValue1;
   int nValue2;
} *lpmsg;
typedef sem_t *lpsem;

//Mailbox array
lpmsg lpMailbox;
//Mailbox control semaphore array
lpsem lpMailboxSem;

int InitMailbox();
int CleanupMailbox();

void SendMsg( int, lpmsg );
void RecvMsg( int, lpmsg );

void *AddEm( void * );

int nThreads;

int main( int argc, char **argv ) {
   //Make sure there are enough params for the function to work
   if ( argc < 3 ) {
      printf( "Not enough parameters!\n" );
      return 0;
   }
   //Get end value
   int nEnd = atoi( argv[ 2 ] ), nSum = 0;
   //Figure out how many threads are needed
   nThreads = MAXTHREAD;
   nThreads = atoi( argv[ 1 ] );
   if ( nThreads > MAXTHREAD || nThreads < 1 )
      nThreads = MAXTHREAD;
   if ( !InitMailbox() ) {
      //Create and start new threads
      pthread_t *lpThreads = new pthread_t[ nThreads ];
      for ( int i = 0; i < nThreads; i++ ) {
         pthread_create( &(lpThreads[ i ]), NULL, AddEm, (void *)(i + 1) );
      }
      msg Msg;
      Msg.nFrom = 0;
      Msg.nType = RANGE;
      Msg.nValue1 = 1;
      //Get each thread the RANGE message it needs
      for ( int i = 1; i <= nThreads; i++ ) {
         Msg.nValue2 = i * ( nEnd / nThreads );
         if ( i == nThreads )
            Msg.nValue2 = nEnd;
         SendMsg( i, &Msg );
         Msg.nValue1 = Msg.nValue2 + 1;
      }
      //Wait for all threads to send ALLDONE messages
      for ( int i = 1; i <= nThreads; i++ ) {
         while ( Msg.nType != ALLDONE )
            RecvMsg( 0, &Msg );
         nSum += Msg.nValue1;
         Msg.nType = NO_MESSAGE;
      }
      //Ensure that all other threads have finished
      for ( int i = 0; i < nThreads; i++ ) {
         pthread_join( lpThreads[ i ], NULL );
      }
      //Print total and finalize program
      printf( "The total for 1 to %d using %d threads is %d.\n", nEnd, nThreads, nSum );
      delete [] lpThreads;
      CleanupMailbox();
   }
   return 0;
}

//Create and initialize necessary arrays for mailbox functions
int InitMailbox() {
   lpMailbox = new msg[ nThreads + 1 ];
   lpMailboxSem = new sem_t[ nThreads + 1 ];
   for ( int i = 0; i <= nThreads; i++ ) {
      lpMailbox[ i ].nType = NO_MESSAGE;
      if ( sem_init( &(lpMailboxSem[ i ]), 0, 1 ) < 0 ) {
         for( int j = 0; j < i; j++ )
            sem_destroy( &(lpMailboxSem[ j ]) );
         return -1;
      }
   }
   return 0;
}

//Destroy mailbox arrays
int CleanupMailbox() {
   for ( int i = 0; i <= nThreads; i++ ) {
      if ( sem_destroy( &(lpMailboxSem[ i ] )) < 0 )
         delete [] lpMailbox;
         delete [] lpMailboxSem;
         return -1;
   }
   delete [] lpMailbox;
   delete [] lpMailboxSem;
   return 0;
}

//Send message to target mailbox
void SendMsg( int nTo, lpmsg lpMsg ) {
   //Ensure that the mailbox is empty
   while ( 1 ) {
      //Lock the semaphore
      sem_wait( &(lpMailboxSem[ nTo ]) );
      if ( lpMailbox[ nTo ].nType != NO_MESSAGE ) {
         //Release the semaphore so another thread can potentially retrieve the message
         sem_post( &(lpMailboxSem[ nTo ]) );
      }
      else break;
   }
   lpMailbox[ nTo ].nFrom = lpMsg->nFrom;
   lpMailbox[ nTo ].nType = lpMsg->nType;
   lpMailbox[ nTo ].nValue1 = lpMsg->nValue1;
   lpMailbox[ nTo ].nValue2 = lpMsg->nValue2;
   //Release the semaphore
   sem_post( &(lpMailboxSem[ nTo ]) );
}

//Retrieve message from target mailbox
void RecvMsg( int nFrom, lpmsg lpMsg ) {
   //If there is no message, wait until there is
   while ( 1 ) {
      //Lock the semaphore
      sem_wait( &(lpMailboxSem[ nFrom ]) );
      if ( lpMailbox[ nFrom ].nType == NO_MESSAGE )
         //Release the semaphore so another thread can potentially send a message
         sem_post( &(lpMailboxSem[ nFrom ]) );
      else break;
   }
   lpMsg->nFrom = lpMailbox[ nFrom ].nFrom;
   lpMsg->nType = lpMailbox[ nFrom ].nType;
   lpMsg->nValue1 = lpMailbox[ nFrom ].nValue1;
   lpMsg->nValue2 = lpMailbox[ nFrom ].nValue2;
   lpMailbox[ nFrom ].nType = NO_MESSAGE;
   //Release the semaphore
   sem_post( &(lpMailboxSem[ nFrom ]) );
}

//Routine for adding numbers between target vars
//Multithread-design dependent
void *AddEm( void *arg ) {
   int nStart = 1, nEnd = 100, nSum = 0, nThreadID = (int)arg;
   msg Msg;
   Msg.nType = NO_MESSAGE;
   //Get the RANGE message needed to start processing
   while ( Msg.nType != RANGE )
      RecvMsg( nThreadID, &Msg );
   nStart = Msg.nValue1;
   nEnd = Msg.nValue2;

   //Calculate the sum
   for ( int i = nStart; i <= nEnd; i++ ) {
      nSum += i;
   }

   Msg.nFrom = nThreadID;
   Msg.nType = ALLDONE;
   Msg.nValue1 = nSum;
   Msg.nValue2 = 0;
   //Send the sum back to the main thread
   SendMsg( 0, &Msg );

   return 0;
}

[Eibro]

Code Select Expand

int CleanupMailbox() {
  for ( int i = 0; i <= nThreads; i++ ) {
     if ( sem_destroy( &(lpMailboxSem[ i ] )) < 0 )
        delete [] lpMailbox;
        delete [] lpMailboxSem;
        return -1;
  }
  delete [] lpMailbox;
  delete [] lpMailboxSem;
  return 0;
}Curious, the indenting here makes it seem as if you want delete [] lpMailbox; delete [] lpMailboxSem; return -1; within the if statement. Is this the case?

[Zakath]

Ooh...you're right. Mistake there on my part. Oops. Since I was running this via console-based SSH and it seemed to be executing fine, I never caught it. Odd...Unix doesn't appear to have problems calling delete [] on array that points to no allocated data, I guess.

[Banana fanna fo fanna]

Zakath, this thread kicks ass. Keep it going

[Eibro]

Ooh...you're right. Mistake there on my part. Oops. Since I was running this via console-based SSH and it seemed to be executing fine, I never caught it. Odd...Unix doesn't appear to have problems calling delete [] on array that points to no allocated data, I guess.

You had better have lost points for that

[Zakath]

Nope, actually I didn't. :\

Here is your score:

Comments: Addit (15/15)
    I0: Everything looks good!

Yes st0rm, I certainly intend to keep this going. I'm out of applicable assignments for the time being. I was doing more theoretical work this term...

[K]

If you want to look at my current assignment, feel free.

Instructions:
http://www.cs.colorado.edu/~hal/CS3104/h3.ps (PostScript)
Provided files:
http://www.darkvariant.com/dubbs/csci/

Note: for some reason my professor likes to use the old depreciated headers.  I always change it so I don't get 30 warnings.  You should too.

Edit: I haven't done this one yet, so the files aren't complete.  It's due on friday though, so when (if?) I get it done I'll post the completed assignment.    

BTW, does anyone besides me really dislike my professor's style?
He puts spacing here between the array and the indexer, which is kind of weird:

Code Select Expand

Given_x [i] = i;
Given_y [i] = i;
and not here between the insertion operator and the arguments:

Code Select Expand

cout <<"Sweep Alg:"<<"\t"<<answer_2<<endl;

Not to mention I like my braces on their own lines, but that's just a preference.