CS413: Fall 1997 Midterm Exam

Take your time and read each question carefully. Some have
multiple parts. Be sure to answer each part. 
Also, be sure to put your name on each exam page.


1. Fill in the blanks in the following short statements. (20 pts)

(a) A program runs in [ protected ] mode when it executes protected instructions.
(b) [ save registers ] and [ restore registers ] are the first and last 
    things that are executed during an interrupt service.
(c) [ non-preemptive ] scheduling switches from one process to another only when
    the running process terminates or blocks. In contrast [ preemptive ] scheduling
    uses a clock interrupt to switch from one process to another after a time slice.
(d) These are four of the contents of the PCB: [ PC, registers ], 
    [ memory management information ], [ accounting information ], and 
    [ I/O status ].
(e) Most of the tasks in a computer are [ I/O ] bound.
(f) Predicted SJF uses [ past behavior ] to estimate the length of the next 
    processing burst.
(g) [ starvation ] is a condition that happens when a process waits for something
    that may never happen.

2. Consider the following C functions and data declarations: (20 pts)

struct S {
   int data;
   S * last;
} ListElement;

struct ListElement * list;

  sema_t  sem = 1;        /* solution  */     

void
Enq( ListElement * newElement )
{
     p(sem);          /* solution */  

     newElement->next = list;   /* STATEMENT 1 */


     list = newElement;         /* STATEMENT 2 */
     v(sem) ;        /* solution */   

}

ListElement *
Deq()
{
     ListElement * returnValue;
      p(sem) ;       /* solution */          
     returnValue = list;        /* STATEMENT 3 */


     list = list->next;         /* STATEMENT 4 */
      v(sem)        /* solution */              

     return( returnValue );
}

Answer the questions on the following page by assuming that
an invocation of Enq() and a simultaneous invocation of Deq() are
concurrently executing on two processors in a multiprocessor. 

(a)  List all the possible execution orders in time of the 4 statements
     labeled. 

          1  3  4  2
          1  3  2  4
          3  4  1  2 
          3  1  2  4 
          3  1  4  2


(b)  Pick one of these execution orders which will cause the code to not behave
     as obviously intended (e.g., the list gets corrupted) and describe the actual
     outcome.


     we pick the order    1  3  4  2
     after the execution, the returnValue in dequeue points to an entry in the 
     middle of the list.


(c) Using a single shared semaphore, fix the example to work as intended.
    (remember to Initialize you semaphore). Show your changes directly on the code
    on the last page.

      see the above program.  


3. Assume that two or more processes communicate with each other
using  enqueue  and  dequeue (described below) on
a circular queue. Complete these procedures using semaphores.
Make sure that a processes calling  enqueue will block if the queue
is full, and a process calling  dequeue will block if the queue is
empty. Also make sure that no races can happen. Don't forget the
semaphore initializations. (20 pts)

     

const int MAXQUEUE = 10;
int queue[ MAXQUEUE ];
int tail;
int head;

/* Other declarations and initializations here */


    sema_t semfull = 10;
    sema_t semempty = 0 ;
    mutex_t  mutex = 1;



void enqueue( int a )
{
   
    p(semfull);
    p(mutex);


    queue[ tail] = a;
    tail = (tail + 1)%MAXQUEUE;


    v(mutex);
    v(semempty);


}

int dequeue()
{


    p(semempty);
    p(mutex); 
   

    tmp = queue[ head ];
    head = (head + 1)% MAXQUEUE;


    v(mutex);
    v(semfull);

}


4.  Complete the following procedures. sendBroadcast sends a message to N 
    processes that will call  receiveBroadcast. sendBroadcast and  receiveBroadcast
    will block until the message has been delivered to the N processes.
    Don't forget to initialize the semaphores. (20 pts)

const int N = 5;
int theMessage;

/* Other declarations and initializations here */


   sema_t semMessageSent = 0;
   sema_t semAllReceived = 0;
   mutex_t mutex = 1;
   int num;


void sendBroadcast( int msg )
{
		
    theMessage = msg;


    for (int i = 0; i < N; i++){
     v(semMessageSent);
    }
    p(semAllreceived);


}


int receiveBroadcast()
{


    p(semMessageSent);   

    int tmp = theMessage;


    p(mutex);
    num++;
    if (num == N){
     for (int i = 0; i < N+1 ; i++){
       v(semAllRecieved);
     }
   }
   v(mutex);
   p(semAllreceived);



    return tmp;
}


5. Write a procedure redirectStdoutStderr that will redirect
both standard output and standard error to a single specified file.
Do not include code for error checking. (10 pts)


void redirectStdinStderr( char* fileName )
{
    /* Redirect standard output and standard error to fileName */


     int f = open(filename, O_RDWR);
     dup2(f, 1);
     dup2(f, 2);

     
}


6.  Write a procedure redirectOutputToGrep that will redirect
the current  standard output to a child process executing
 grep pattern  using a pipe. Do not include code for error checking. (10 pts)


void redirectOutputToGrep( char * pattern )
{
    /* Redirect standard output to a child executing  */
    /* 'grep pattern' using a pipe */


   int fd[2];
   
   pipe(fd);
   
   int pid = fork();
   if (pid == 0) {
    dup2(fd[0], 0);
    close(fd[0);
    close(fd[1]);
    exec("grep", pattern, 0);
   }

   dup2(fd[1],1);
   close(fd[0]);
   close(fd[1]);
}