Midterm Exam

CS354 Spring 2003

Name:

Part 1. True False Questions

Answer True/False (T/F) (1 point each)

____ The call to putenv() in your shell can be called by a child process.
____ spinlocks have less overhead than mutex-locks as long as the critical section is small.
____ The check for permissions in the open() system call could be done in user space.
____ If foo() calls xoo() and foo() has a local variable v1 and xoo() has a local variable v2, then &v1 > &v2
____ A call to fork() will show in the truss output.
____ execvp() will return a value of 0 if successful.
____ The counter of a semaphore could be negative at some point in the execution of a program..
____ Calling fork() modifies the reference counter of the open file objects.
____ A parent and a child process may communicate using a pipe created by the child process.
____ The size in bytes of a variable of type (char *) is 4 bytes and the size of a variable of type (char **) is 8 bytes.
____ User-level threads use non-preemptive scheduling.
____ ELF means Executable Level Format.
____ SMP stands for Simultaneous Multi Processing.
____ A call to strcat(a,b) will allocate space with a number of bytes equal to the lenght of string "a" plus the lenght of string "b" plus 1.
____ A process that has "n" POSIX threads, where one of them calls fork() will have only one thread in the child process.
____ The number of processes in ready state in mentor cannot exceed 8.
____ a[i] is equivalent to *(&a[0] + i)
____ The input/output redirection to files can be done by the child.
____ It is possible to disable interrupts in user space.
____ BSS stores uninitialized global variables
 

Part 2. Short questions.

1. (3 pts) Mention the advantages and disadvantages of clusters compared to multiprocessor machines.
 
 
 
 
 

2. (3 pts.) Mention in what circumstances the user time of a process may exceed the real time.
 
 
 
 
 
 

3. (3 pts.) Write the factors used to determine the length of a quantum.
 
 
 
 
 

4. (3 pts.) Give the reasons why system calls are implemented using software interrutps.
 
 
 
 
 
 

5. (3 pts.) What are the advantages and disadvantages of preemptive vs. non-preemptive scheduling.
 
 
 
 

Part 3. Programming questions.

 
 
6. (10 pts.) Implement the code for the following function 

       char *strstr(const char *haystack, const char *needle) 

The strstr() function finds the first occurrence of the substring needle in the string haystack.  The terminating `\0' characters  are  not  com­pared. The  strstr()  function  returns  a pointer to the beginning of the sub­string, or NULL if the substring is not found. 

 
char *strstr(const char *haystack, const char *needle)
{
      
      
      
      
      
      
      
      
      
      
      
      
      
      



      
      
      
      
      
      
      
}
      









 

 

 



7. (10 pts.) Write the implementation of the procedure getenv()
that returns the value of an environment variable or NULL if that variable
does not exist. 







extern char ** environ;
     
char * getenv( char * var_val ) {

       
       
       
       
       
       
       
       















}
      









 

 



8. (10 pts.) The add() method adds a number to a linked list
of integers. This add method does not have mutexes. Thread T1 calls add(5)
and thread T2 calls add(7) at the same time. Give a sequence of instructions
(use the labels a, b, c, d) that can cause the node with the "7" value 
to be lost. 







struct Node {
  int _val;
  Node * _next;
};     
       
class IntList {
  Node * _head;

  IntList() {
    _head = NULL;
  }

  void add( int val ) {

    a) Node * n = new Node()

    b) n->_val = val;
  
    c) n->next = _head;

    d) _head = n;

  }
}

    
t --------------------------------> 

T1 ->  

T2 -> 










 

 


 



9. (5 pts) Write a synchronized bounded buffer  class
with a circular buffer where the writer thread that calls add(int val)
will block if the buffer is full. The reader thread calling remove() will
block if the bounded buffer is empty. The constructor BoundedBuffer(int
max) allocates space for _buffer with max size elements and it also initializes
semaphores. Add also the semaphores and mutexes that are necessary.







class BoundedBuffer {



  int * _buffer;
  int _max;
  int _head;
  int _tail;

  // More variables or semaphores if necessary






  BoundedBuffer( int max ) {

















  }

  void add( int val ) {
     // Block if buffer is full




















  }

  int remove() {
      // Block if buffer is empty




















  }











 


 



10. (10 pts.) Write a function redirectOutput(args, outfile)
that will execute the program in args[0] in a separate process and
it will redirect the output to the file named outfile. args is an
array of arguments where args[0] is the program to run and the last
aregument is a NULL pointer. You will have to implement the procedure in
two ways: 1. Do the reedirection in the parent. and 2. Do the redirection
in the child.The procedure will return 0 if success or different than 0
otherwise.







int redirectOutput(char ** args, char * outfile)
{
  // Do the redirection in the parent
























}

int redirectOutput(char ** args, char * outfile)
{
  // Do the redirection in the child


















}











 


 



11. Implement the procedure int runpipe( char ** args1, char
** args2) that runs the programs in args1 and args2 in different children
processes where the output of args1 goes to the input of args2 using a
pipe. args1 and args2 are arrays of arguments where the last argument is
NULL. The element args1[0] and args2[0] are the names of the programs to
execute. runpipe() will return 0 if success or different than 0 otherwise.







int runpipe( char ** args1, char ** args2)
{






































}








 

 




12. (10 pts.) Implement a name table class using an array of TableEntry
struct's. The constructor NameTable(max) will allocate space for a table
with n entries. The function add(var,val) will block until there is space
in the table, then it will search for an entry in the table that is unused
( _var and _val are NULL) and it will add the var and val strings
in that entry. Duplicated values are allowed.

The function lookup(var) will lookup the string var in the table
and it will return the corresponding value. If the variable does not exist,
lookup() will wait until that variable is added with the add() function.
Add the semaphores and mutexes that are necessary and the code that implements
the behavior described.		







struct TableEntry {

  char * _var;

  char * _val;

  // Other variables here









};



class NameTable {

  // Max length of table

  int _max;   



  // Array of TableEntry entries        

  TableEntry * _table;

  

  // Other variables here

 

 

 



 

public:

  NameTable(int max) {

    

    

    

    

    

    





  }

  

  void add(char *var, char *val) {

    





















  }

  

  char * lookup(char * var) { 

    

















  }

  

  

};