/*      Professor Liang's Quick Guide to Unix Programming in C

	    Part 2: Introduction to Threads and Processes



  You've now learnt that the '&' symbol can be used from the command line
to start processes concurrently.  This document will show you how to create
concurrent processes and threads from within a program.

  In most modern operating systems there exists two classes of
processes: "processes" and "threads".  A process is a running program.
A thread, however, is only part of a running program.  Most of the
programs you wrote in csc15 and 16 resulted only in processes with a
single thread.  In such cases there's no distinction between process
and thread.  However, it is also possible to create a process with
multiple threads.  A conventional program consists of multiple
functions (and classes and objects, etc ...).  A thread is like a
function, except that once called, it begins to run *concurrently*
with the rest of your program!  In other words, consider the program

void f()  { printf("A"); printf("B"); }
int main()
{ f();
  printf("C"); printf("D"); 
  exit(0);
}

  As a conventional program, this will of course print "ABCD".  But if
the function call to f results in a separate "thread of execution", then
the body of f will be executed concurrently with the body of main, and
you may see "ACBD", or "ACDB", or one of several other possibilities 
depending on where the operating system decides to task-switch.  If the
function call to f spins off a separate thread, the above program will have
two threads (one for main and one for f).

  When a new process starts, it gets its own "memory space" - that is,
all data needed by the process are its own, and not shared with other
processes (except through special mechanisms).  In contrast, two
threads that are part of the same process can share data in the same
way that two functions that are part of the same program can share
data.  In this way, a thread is sometimes referred to as a
"lightweight process".  Modern operating system schedulers in fact
operate at the level of threads, and not entire processes.  A thread
is a finer unit of execution than a process, just as a function is a
finer unit of code than an entire program.

  There are system calls one can invoke to create both new threads and
new processes.  I will first explain threads, because it's easier for
them to share data and therefore demonstrate the need for
synchronization mechanisms.  


                             POSIX Threads

  The Portable Operating System Interface standard or "POSIX" defines
a set of system calls a program can use to create multiple threads.
To create a seperate thread of execution, you have to first define a
special "thread function" whose body the thread will execute.  This
function must take a parameter of type (void *) and return something
of the same type.  void* in C is used to mean "pointer to anything"
(it's like the "Object" superclass in Java).  Thus we can pass any
kind of information we want to a thread function, and it can return
any combination of values (though usually it doesn't return values).
A single thread function can spawn several threads by using the
"pthread_create" system call.  Each thread has a thread id of type
"pthread_t."  The exact mechanism for creating a thread function and
initiating a separate thread is best explained through the following
simple example: 

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

void * f(void * x)   // a thread function
{ printf("A");  printf("B"); }

int main()
{ pthread_t threadID;
  pthread_create(&threadID, NULL, f, NULL);

  printf("C");  printf("D");

  pthread_join(threadID,NULL);
  exit(0);
}


  "pthread_create" is like a special way to call functions: instead of
waiting for the function to return before continuing, it immediately
continues to the next instruction as the function called is started
by another thread of execution.  The first argument to pthread_create
is a pointer to a variable identifying the thread, which will be
instantiated by pthread_create (that's why it has to be a pointer).
The second argument is usually NULL.  The third argument is the name
of the thread function (you can pass functions to other functions in
C).  The last argument is a pointer to the data structure that will be
passed to f.  In this example f doesn't use its parameter, so the last
argument is NULL.

  Once the separate thread is created we must assume that the body of
main will be executed concurrently with the separate thread.  However,
it may be the case that main will exit before its "offspring thread"
finishes executing.  In such a case the separate thread will be
killed, since the "main" thread of the process have already
terminated.  To make the main thread wait for the separate thread to
terminte before exiting, we use the "pthread_join" call.  This system
call causes main to suspend until the thread identified by its first
argument has returned.  The second argument to pthread_join is a
pointer to a data structure that will "catch" the void* value returned
by the thread.  In this example, the thread doesn't return anything,
so this argument is NULL.  Consult the appropriate man pages for these
system calls for more information.

  Quiz: what would be the effect of calling pthread_join right after
        pthread_create?

  You must compile this program with "gcc -lpthread" to make sure that the
posix thread library is loaded.  If you run the program you will probably 
always see "CDAB".  That's because the main thread continues to run as the
the separate thread is being created. However, if you put the printfs inside
long loops, you will see that the threads will task-switch at unpredicatable
points.

  The second example creates two threads.  It also passes a pointer to
a shared data structure to the threads as they're created.  Pay
attention to the need for type casting from (void *) to the
appropriate types: 
*/ 

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

struct sharedinfo  // structure containing shared data for threads
{
  int x;  // some data
  int y;  // some more data
};

void * f(void * theinfo)  
{ int i;
  struct sharedinfo * info;
  info = (struct sharedinfo *) theinfo; // type cast from void* to threadinfo*
  for(i=0;i<1000;i++)
      { info->x += 1;  // add one to shared variable
        printf("I am thread F, and I'm changing x to %d\n",info->x);
      }
} //f

void * g(void * theinfo)  
{ int i;
  struct sharedinfo * info;
  info = (struct sharedinfo *) theinfo; // type cast from void* to sharedinfo*
  for(i=0;i<1000;i++)
      { info->x += 1;  // add one to shared variable
        printf("I am thread G, and I'm changing x to %d\n",info->x);
      }
} //g


int main()
{ pthread_t tid1, tid2;
  struct sharedinfo myinfo;
  myinfo.x = 0;
  myinfo.y = 1;

  pthread_create(&tid1, NULL, f, &myinfo);
  pthread_create(&tid2, NULL, g, &myinfo);

  pthread_join(tid1,NULL);
  pthread_join(tid2,NULL);
  exit(0);
}
/*

  It is also possible to spawn the two threads from a single thread function
(just as a conventional function can be called multiple times).  Note that
the "i" variable of the two threads are not shared simply because they're
local variables.  However, the variable x inside the struct sharedinfo is
shared (through the pointer to the struct passed through pthread_create).
Both threads will therefore try to modify the x variable concurrently.  This
will create a need for a "critical section" and appropriate synchronization
mechanisms.  

  The pthread library provides a very basic synchronization mechanism
called mutex (the type name is pthread_mutex_t).  A mutex is a flag
that can be "tested and set" in one locked step.  Think of it as a
kind of boolean variable.  If a process wants to enter a critical
section, it checks the value of the mutex variable.  If it's true,
then in *one locked step* it sets it to false and enters its critical
section.  If the mutex variable is false, the thread is suspended.
Specifically, the thread is put into a queue of threads that are
waiting for the variable to become true.  When a process leaves its
critical section, it sets the mutex variable to true (it "unlocks"
it).  At this time, one of the processes on the queue will "acquire"
the mutex and begin to run in its critical section.  One important
point to be emphasized is that the mutex itself must be a piece of
*shared* data between the threads.

  Do the following on your own to use a mutex variable to prevent the 
  two threads from changing the shared variable x simultaneously:

  a. in the declaration of struct sharedinfo, add a new variable:
        pthread_mutex_t mutex;

  b. in main, before the calls to create the two threads, initialize
     the mutex with:
        pthread_mutex_init(&myinfo.mutex,NULL);
  
  c. in both thread functions, surrond the critical sections with:
        pthread_mutex_lock(&info->mutex);
        // critical section that changes x goes here
        pthread_mutex_unlock(&info->mutex);

 
  pthread_mutex_lock will in one locked step test the value of the
mutex variable, block if necessary, and if the mutex is available,
acquire it and enter its critical section.  The corresponding
pthread_mutex_unlock releases the mutex.  Note carefully the use of
pointers.  The value passed to all the pthread_mutex functions MUST be
a pointer to a mutex variable.  In particular, note that in the thread
functions it's not enough that "info" is already a pointer.
"info->mutex" accesses the mutex itself, but to convert it into a
pointer, we have to put the additional '&' in front of the expression.

With the mutexes we can also implement more sophisticated
synchronization mechanisms such as semaphores and monitors.  But
that's a story for another day.



                               Fork

  To complete this document I will briefly introduce how to spawn a new
process from a program.

  In Unix, all processes are created by a parent process, except for
the initial scheduler process.  Each process has a process id of type
"pid_t".  A process creates another process using the "fork" system
call.  fork() creates an identical copy of the process that called it,
and immediately begins to run the "child process" concurrently.  The
operating system makes a copy of the process control block.  Among the
items copied to the child process is the program counter (pointer to
the next instruction in the program's code to execute).  This means
that the child will start executing at the point of the fork.  Since
fork creates an entirely new process, no variable between the
processes can be shared without special (and messy) mechanisms - even
if the variables are global.  The only thing that distinguishes a
child process from the parent (the process that called fork) is the
"process id" that is returned by the call to fork().  Zero is always
returned to the child process whereas the parent process will get the
process id of the child process as assigned by the operating system.
Here's an example to clarify all this:


#include<stdio.h>
#include<unistd.h>
#include<sys/types.h>
#include<sys/wait.h>      

int x;  // global variable, but will it be shared? (no)

int main()
{
  pid_t prid;  // process id (returned by fork)
  x = 3;        

  prid = fork();  // fork child process
  // prid == 0 if you're child process, otherwise prid== pid of child

  if (prid == 0) 
    {  x++;
       printf("I'm the child, x==%d\n",x);   
    }
  else  
    {  x++;
       printf("I'm parent, x==%d, and my child has process id %d\n",x,prid);
    }
 
  exit(0);
} 

  When you run the program you will see that both parent and the
forked child process will print 4 as the value of x.  That's because,
in contrast to threads, each process has its own copy of x, even
though x is "global".  The two processes only share the program's
source code.  The child process will execute the first branch of the
if statement and the parent process will execute the else branch.  It
is also possible to have the child process run another program
entirely using the "execv" system call.  One process can wait for
another to finish using the "waitpid" system call.  I will not go into
detail concerning these utilities here, but you can consult the man
pages.

  The problem with spawning multiple processes as opposed to threads
is that it is much more difficult for processes to shared information.
Threads are much easier for the purpose of understanding the necessary
mechanisms for synchronizing concurrent programming in general.  We
will therefore use threads as opposed to processes to understand the
concepts of chapter 7 of the dinosaur book.  In the future, I hope to
cover some interprocess communication (IPC) in Unix.  Communication
between processes is done through sockets, much as sockets are used in
network programs.  In fact, in Unix the same basic mechanism for
implementing client-server applications over the Internet is also used
for processes on the same system to communicate and share information.

*/