1. Quickies

Multiprogramming: Several jobs are in main memory at once; a processor
   is switched to another process when the executing process makes
   an I/O request. This is an attempt to increase CPU utilization by always 
   having something for the CPU to execute.
   Timeshared Operating Systems, in addition to multiprogramming, switch 
   the processor to another process after a certain amount of time. This  
   provides interactive use of the system to a set of users simultaneously.
 
Busy waiting problems:

   Waste of CPU resources
   Priority inversion
   Needs hardware support of atomic instructions


In direct IPC the sender names the receiver
In indirect IPC sender sends the message to a mailbox, and the
receiver picks the message from the mailbox

Save state of currently executing process
Find the next process ready to run
Load the state of this new process


Fork()  :  PT full
open()  :  Descriptor table full
Exec()  :  No effect


Pipe: stream oriented
      does not support message boundaries
      Unidirectional, FIFO
      There can be several senders and several receivers

Port: message oriented
             does support message boundaries
            Unidirectional, FIFO
      Typically several senders but one receiver



If semaphore wait queues are implemented as stacks, starvation
may occur



2.
1.     Child 0 executing     |
       Child 1 executing     | Child 1
       All children created  |
 
       Child 1 executing     | Child 2
       All children created  |
 
       Child 1 executing     | Grand child
       All children created  |
 
       All children created  | Parent
 
 Any permutation of the above sequence is possible.
 

2. main()
 {  int p[2], q[2];
    int buf[10];
     
     pipe(p);
     pipe(q);

     if (fork() == 0)
      {  close(p[1]);
         close(q[0]);
 
        read(p[0],buf,1)

        ......

         write(q[1],msg,1)

       exit();
      }

     if (fork() == 0)
      {  close(p[0]);
         close(p[1]);
         close(q[1]);
 
         read(q[0],msg,1)

       ....
       exit();
      }

         close(p[0]);
         close(q[0]);
         close(q[1]);

write(p[1],msg,1);
}

Semaphore capacity1, capacity2= {N/2, N/2};
Semaphore w.f.boy, w.f.girl, r.l.boy, r.l.girl = {0,0,0,0}
                           
Process Boy()                                                            
{                          		      Process Girl()              
                           		      {                          
                           		                                 
   boyarrive();            		                                 
    down(capacity1);        		         girlarrive();            
                           		          down(capacity2);        
     dance                 		                                 
                           		           dance                 
                           		                                 
                           		                                 
   boyleave();             		                                 
    up(capacity1);          		         girlleave();             
                           		          up(capacity2);          
}                          		                                 
                           		      }                          
boyarrive()                                   girlarrive()                                       
{                   				{                   
   up(w.f.boy)      				   up(w.f.girl)      
   down(w.f.girl)   				   down(w.f.boy)   
}                   				}                   
                    				                    

boyleave()                                            girlleave()         
{                  			      {                  
   up(r.l.boy)     				  up(r.l.girl)     
   down(r.l.girl)  			         down(r.l.boy)
}                                              }


semaphore mutex=1, miss_waiting=0, carn_waiting=0;
int miss_waiting_num=0, carn_waiting_num=0;
 
/*** missionary process ***/
 
down(&mutex);
miss_waiting_num++;
if (miss_waiting_num+carn_waiting_num<3 || miss_waiting_num==1)
        {up(&mutex);
         down(&miss_waiting);
         down(&mutex);
        }
else
if (carn_waiting_num>=1)
        {miss_waiting_num=miss_waiting_num-2;
         carn_waiting_num--;
         up(&miss_waiting);
         up(&carn_waiting);
        }
else    {miss_waiting_num=miss_waiting_num-3;
         up(&miss_waiting);
         up(&miss_waiting);
        }
up(&mutex);
rowboat();
 


/*** cannibal process ***/

down(&mutex);
carn_waiting_num++;
if (miss_waiting_num+carn_waiting_num<3 || 
    (miss_waiting_num==1 && carn_waiting_num==2))
        {up(&mutex);
         down(&carn_waiting);
        }
else
if (miss_waiting_num>=2)
        {miss_waiting_num=miss_waiting_num-2;
         carn_waiting_num--;
         up(&miss_waiting);
         up(&miss_waiting);
         up(&mutex);
        }
else    {carn_waiting_num=carn_waiting_num-3;
         up(&carn_waiting);
         up(&carn_waiting);
         up(&mutex);
         rowboat();
        }