Midterm Exam

CS354 Fall 2008



Name:________________________________________________________________





Question
 Max.
Current
True/False
 10 pts.
Short Questions 1-5
 15 pts.
Short Questions 6-10
 15 pts.
11,
 5 pts.
12.
 5 pts.
13.
 10 pts.
14.
 15 pts.
15.
 10 pts
16.
 15 pts

Total:




















Part 1. True False Questions

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

____ It is possible to get a deadlock with a single mutex lock.
____ Shared libraries add into the size of an executable file.
____ COFF stands for Compiler Object File Format.
____ The entry point of an executable file is the function main().
____ A process has a stack for every thread it contains.
____ truss lists the function calls that a process makes.
____ Kernel-level threads use preemptive scheduling  to switch among them.
____ Race conditons are more likely to happen in multiprocessor machines.
____ If multiple threads are waiting in a spin_lock call, a call to spin_unlock() will allow the thread that has been waiting the longest to proceed.
____ In POSIX threads, the thread calling fork will create a child process that is a copy of the parent inclluding all the threads in the process.


Part 2. Short questions.

1. (3 pts) Explain the advantages and disadvantages of a cluster compared with a parallel machine.





2. (3 pts.) Explain the differences between kernel and user mode..

 


 

3. (3 pts.) Explain the differences between non-preemptive and preemptive scheduling..


 

4. (3 pts.) If most of the time processes are in wait state, how do you justify getting a faster machine?


 

 

5. (3 pts.) Explain how multi-level feedback-queue scheduling works.





6. (3 pts.) Explain how the size of a quantum is chosen.





7. (3 pts.) Write down the implementation of spinlocks:


int test_and_set(int *v)
{



}

void spinlock(int * lock)
{



}

void spinunlock(int*lock){



}

8. (3 pts.) What are the advantages and disadvantages of using threads vs. using processes?





9. (3 pts.) Explain why atomic sections need to be small in multiprocessor machines?




10. (3 pts.) Give the names of 5 of the data fields contained in the ELF_HEADER and explain what they contain. If you do not remember the names, give approximate names.





11. (5 pts) In the following code,  

T1:
a) mutex_lock(&m3)
b) mutex_lock(&m6);
c) mutex_lock(&m1);
 T2:
d) mutex_lock(&m2)
e)mutex_lock(&m1);
f)mutex_lock(&m4);
 T3:
g)mutex_lock(&m4);
h)mutex_lock(&m3);
i)mutex_lock(&m2);

a) give a sequence of steps using the letters at the left of each statement that will cause the threads to get into a deadlok. (Example: a, d, g ... etc)



b) Draw the graph representation of the deadlock.




c) Rewrite the code to prevent the deadlock.
T1:




 T2:

T3:





12.(5 pts) Assume that the following code for removing an item from a list is called by multiple threads. Write the sequence of events that will cause an item in the list not to be removed after calling the remove() operation.
int MTList::remove(){   ListEntry *tmp;
  a) tmp = _head;
  if(tmp == NULL) {
    return -1;
  }
  b) _head=tmp->_next;
  int val=tmp->_val;
  delete tmp;
  return val;
}
 void MTList::insert(int val){  
  ListEntry *tmp;
  tmp = newListEntry;
  tmp->_val = val;
  c) tmp->_next = _head;
  d) _head = tmp;
}

Time
 Thread 1
Write a), b), c), d) or nothing in each line.
 Thread 2
Write a), b), c), d) or nothing in each line.
 Thread 3
Write a), b), c), d) or nothing in each line.
1


2


3


4


5




Part 3. Programming questions.

 
13. (10 pts.) Implement the function char *strstr(const char *haystack, const char *needle). The  strstr()  function  finds the first occurrence of the substring needle in the string haystack and returns a pointer to the beginning of the substring or NULL if the substring is not found.  The terminating `\0' characters are not compared.
 
char *strstr(const char *haystack, const char *needle)
{













}
















14. (15 pts.) Write a program "grepsort arg1 arg2 arg3" that implements the command "grep arg1 | sort  < arg2 >> arg3". The program should not return until the command finishes. "arg1", "arg2", and "arg3"  are passed as arguments to the program. Example of the usage is "grepsort hello infile outfile". This command will print the entries in file infile that contain the string hello and will append the output sorted to file outfile. Do error checking. Notice that the output is appended to arg3.
int main( int argc, char ** argv)
{





































}

 
 
15. (10 pts) Write a class SynchronizedStack of int values where pop() will block  if the stack is empty and push will block if the stack is full. Write the member variables that you think are necessary. Implement the stack with an array of int's and allocate it dynamically in the constructor.
 

class SynchronizedStack {
  // Add your member variables here
  




public:
  SynchronizedStack( int maxStackSize );
  void push(int val );
  int pop();
};

SynchronizedStack ::SynchronizedStack(int maxStackSize )
{







}

void SynchronizedStack::push(int val)
{









}
  
int SynchronizedStack::pop()
{











}

 
 
16. (15 pts) Write the code of  method waitForTemperature(double low, double high) and readTemperatureThread(). The procedure waitForTemperature(double low, double high) will continue if the currentTemperature() is in the range low <= currentTemperature <= high. Otherwise it will wait until the temperature is in that range.The method readTemperatureThread() reads the temperature once every half a second and wakes up any thread calling waitForTemperature() that has the current temperature in range. Assume that the method currentTemperature() is already impelmented and reads a digital thermometer. Also write the code for the constructor 

// Add any structures you need






class TemperatureAlert {
  // Add any variables you need






  double currentTemperature() {
    // Already implemented
    return temperature from digital thermometer
  }

  void waitForTemperature(double low, double high) {
    // Return immediately if low <= currentTemperature() <= high or
    // Wait until the current temperature is in that range.












  }

  static void readTemperatureThread() {
    while (1) {
      double t = currrentTemperature();
      
      // Wakeup any threads waiting for the right temperature
  










      // Sleep for 1/2 second before next temperature reading
      nanosleep(500*1000*1000);
    }
  }

  TemperatureAlert() {
    // Do any initializations here including starting the thread that calls readTemperaturethread




  }

}