Midterm Exam

CS354 Spring 2007



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)

____ A shared library used by a program increases the size of  the executable file.
____ The loader is also called runtime-linker.
____ Most of the CPU bursts finish before a quantum expires.
____ Poling is also called Asynchronous Processing.
____ There is only one stack in a process.
____ The Interrupt vector can be modified in user mode.
____ In preemptive scheduling a context switching happens only when the process goes to waiting state or yields the CPU.
____ It is possible to create a deadlock with a single mutex_lock.
____ Interrupt handlers run in kernel mode.
____ A semaphore initialized with 0 can be used to instead of a mutex.

Part 2. Short questions.

1. (3 pts) Explain the difference between kernel and user mode.





2. (3 pts.) Enumerate the steps of servicing an interrupt.

 


 

3. (3 pts.) Explain how Multi-Level Feedback-Queue Scheduling works.




 

4. (3 pts.) Explain what the "truss" command is used for.


 

 

5. (3 pts.) Explain the differences between I/O bound and CPU  bound processes.





6. (3 pts.) Enumerate the memory sections of a program and explain what they store.





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 a multiprocessor machines?





10. (3 pts.) Explain the differences between user-level threads and kernel threads..




11. (5 pts) Given the following code for remove() of a linked list without mutexes, give a sequence of steps by two threads calling remove() executing c) and d) that will cause the same element to be returned twice by remove():

int MTList::remove(){
<>  ListEntry *tmp;
  c) tmp = _head;
  if(tmp == NULL) {
    return -1;
  }
  d) _head=tmp->_next;
  int val=tmp->_val;
  delete tmp;
  return val;
}

Time
 Thread 1
Write  c) or d)
Thread 2
Write   c) or d)
1

2

3

4

5

<>
12. (5 pts) Assume that there are three threads T1, T2, and T3 that use mutexes. 
<>


 Time
 Thread 1
Write  a) b) c) etc
 Thread 2
Write  d) e) f) etc 		 Thread 3
Write  g) h) etc
 
T1() 
{
  a)mutex_lock(&m3);
  b)mutex_lock(&m1);
  c)mutex_lock(&m2);

  ...

  mutex_unlock(&m2);
  mutex_unlock(&m1);
  mutex_unlock(&m3);
}
T2() 
{
  d)mutex_lock(&m2);
  e)mutex_lock(&m3);
  f)mutex_lock(&m4);

  ...

  mutex_unlock(&m4);
  mutex_unlock(&m3);
  mutex_unlock(&m2);
}

T3() 
{
  g)mutex_lock(&m1);
  h)mutex_lock(&m2);

  ...

  mutex_unlock(&m1);
  mutex_unlock(&m2);
}
 1


2


3


4


5


6


7


8
 



Graph:






<>
<>

Part 3. Programming questions.

 
13. (10 pts.) Implement the function char * wildcardToRegExp(const char * wildcard); that transforms a wildcard to a regular expression. 
char *wildcardToRegExp(const char * wildcard)
{
















}
      












14. (15 pts.) Write a program "lssort arg1 arg2" that implements the command "ls -laR arg1 | sort > arg2". The program should not return until the command finishes. "arg1" and "arg2" are passed as arguments to the program. Example of the usage is "lssort /etc outfile". This command will list the /etc directory, sort it and store the output in outfile. Do error checking.
int main( int argc, char ** argv)
{





































}

 
 
15. (10 pts) Write a class WaitForAlert that allows threads to wait for an alert until an alert is produced. Alerts have names of type (char *). A thread calling waitForAlert(alertName) will wait until another thread calling signalAlert(alertName) with the same alertName is called. For example, multiple threads can call waitForAlert("aaaa") and all these threads will block until  another thread calls signalAlert("aaaa"). If signalAlert(alertName) is called and no threads are waiting for this alertName, the signalAlert() call will be ignored. Hint: Build a linked list with nodes containing the names of the alerts that threads are waiting for and a semaphore that wait on.
 

class WaitForAlert {
  // Add your member variables here




public:
  WaitForAlert();
  void waitForAlert(const char * alertName);
  void signalAlert(const chat *alertName);
};

WaitForAlert::WaitForAlert()
{







}

void WaitForAlert::waitForAlert(const char * alertName)
{









}
  
void WaitForAlert::signalAlert(const chat *alertName)
{











}

 
 
16. (15 pts) Write a class RWLockWithoutStarvation that will behave like a read-write lock except  that once a writter attempts to write,  new readers will not be allowed to enter the read section until the writer has been allowed to enter the write section and calls WriteUnlock(). Make sure that your solution does not have starvation of readers or writers.
 

class RWLockWithoutStarvation {
  // Add your member variables here




public:
  RWLockWithoutStarvation ();
  void ReadLock();
  void ReadUnlock();
  void writeLock();
  void writeUnlock();
};

RWLockWithoutStarvation::RWLockWithoutStarvation()
{







}

void RWLockWithoutStarvation::ReadLock()
{








}
  
void RWLockWithoutStarvation::ReadUnlock()
{







}

void RWLockWithoutStarvation::WriteLock()
{







}
  
void RWLockWithoutStarvation::WriteUnlock()
{








}