Homework 2 Solutions

22C:116, Spring 1997

Problem 1

   #include 

   void main() {
     int pid_CFI, pid_E;
     int cfiFinished=0;


     write(1,"A",1);		/* in ABDHJ */
     if((pid_CFI = fork()) == 0) {	/* in CFI */
       printf("C\n");
       if(fork() == 0) {		/* in G */
         write(1,"G",1);
         exit(0);
       } else {			/* in CFI */
         write(1,"F",1);
         wait((void *)0);
         write(1,"I",1);
         exit(0);
       }
     } else {			/* in ABDHJ */
       write(1,"B",1);
       if((pid_E = fork()) == 0) {	/* in E */
         write(1,"E",1);
         exit(0);
       } else {			/* in ABDHJ */
         write(1,"D",1);
         pid = wait((void *)0);
         if(pid == pid_CFI) {
           cfiFinished = 1;
           wait((void *)0);
         }
         write(1,"H",1);
         if(!cfiFinished)
           wait((void *)0);
         write(1,"J",1);
         exit(0);
       }
     }
   }

   This Solution is fixed from that distributed previously.
   
Problem 2

   Data Structures:

   struct item {
	   int data;
	   struct item * next;
   }

   struct queue {
	   item * head;
	   item * tail;
   }

   Semaphores:
   
   int FreeBuffS = BuffSize;	  /* available space in the bounded buffer */
   int BuffS = 1;		  /* MUTEX access to the buffer */
   int QueS[#Queues]=[1 1...1];	  /* MUTEX access to each queue */
   int FullQS[#Queues]=[0 0...0]; /* number of items in each queue */
   
   Variables

   queue FreeLocations, Queue[#queues];

   Enqueue(ithQue,data){

	P(FreeBuffS);	/* wait for free buffer space */
	P(BuffS);	/* wait for MUTEX for queue of free locations */
	take_first_free_location;	/* allocate memory */
	put_data_in_that_location;
	S(BuffS);	

	P(QueS[ithQue]);	/* wait for i-th queue */
	add_new_item_at_tail;
	S(QueS[ithQue]);	/* release the queue lock */
	S(FullQS[ithQue]);	/* increment the count of items in the queue */
   }

   Dequeue(ithQue){

	P(FullQS[ithQue]);	/* wait until the queue is not empty */
	P(QueS[ithQue]);	/* gain exclusive access to the queue */
	take_item_from_head;	
	extract_data;
	S(QueS[ithQue]);	/* release queue lock */

	P(BuffS); 	/* wait for exclusive access for the buffer */	
	add_location_to_free_list;
	S(BuffS);	/* release lock to buffer */
	S(FreeBuffS);	/* increment thr number of free locations */
   }


Problem 3

   The answer is : no, there cannot be achieved a working mutual exclusion
   mechanism with no busy waiting using only sleep and wakeup. Because a
   wakeup doesn't have any effect on an awake process(it is simply lost)
   and because the processes are interuptable (a context switch can ocurr
   at any time) there always exists a scenario that brakes one of the
   mutual exclusion's conditions. Most frequently both (or all) processes
   go to sleep forever. The progammer can not fight a weakness like:
   sometimes weakup calls are lost without any other tool (hard or soft).


Problem 4

   A priority queue implemented with a (maximum) binary heap is very
   efficient.  We want to be able to pick the maximum quickly and this
   is done in logarithmic time (counting for the maintenance of the
   heap,too). The can be stored using an array( no need for pointers).
   The insertion also takes logarthmic time in the worst case.

   In a large scale shared memory multiprocessor system mutualy exclusive
   access to the queue must be provided. This is not difficult but it
   slows down the performance of the system, paralellism being affected.