Midterm Exam

CS354 Spring 2005



Name:________________________________________________________________





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

Total:




















Part 1. True False Questions

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

____ The threads in a process share the same stack.
____  The maximum number of processes in running state is determined at configuration time.
____ A short quantum will benefit CPU-intensive applications
____ Most of the CPU time is spent in user mode.
____ The function strcpy(a,b) will allocate strlen(b)+1 bytes and copy the string from b to a.
____ In pthreads, fork() will only create one thread in the child process.
____ The arguments in a system call could be checked in user mode instead of kernel mode before the system call is performed.
____ It is necessary more than one mutex_lock to create a deadlock.
____ It is possible to modify the interrupt vector in user space.
____ Shared libraries run in user mode

Part 2. Short questions.

1. (3 pts) Explaing "aging" in process scheduling.





2. (3 pts.) Explain how the quantum length can affect the priority of a processes in modern operating systems and how this is going to improve the execution of the applications.

 


 

3. (3 pts.) a) Write the code for spinlock/unlock? b) What problems we may encounter if we remove the thread_yield() instruction?




 

4. (3 pts.) Enumerate the checks that the kernel does during the system call open(filename, mode)


 

 

5. (3 pts.) What are the steps for processing an interrupt.





6. (3 pts.) Explain why it is a good idea to choose a quantum that is longer than the average CPU burst.





7. (3 pts.) Mark the "C" expressions that are quivalent to a[i]. The type of a[i] is  <type of a[0]>

Expression Equivalent to a[i]. Yes or Not
a + i   
a + i * sizeof( <type of a[0]>)  
&a + i  
*(a + i)  
*(a[0] + i)  
*(&a[0] + i)  
*(&a[i])  
&a[i]  
*(<type of a[0]> *) ((char *) &a[0] + i )  
*(<type of a[0]> *) ((char *)&a[0] + i * sizeof(a[0]))  


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





9. (3 pts.) What is the problem of having long critical sections?





10. (3 pts.) Explain step by step the life cycle of a program from editing to running.






Part 3. Programming questions.

 
 
11. (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.  The terminating `\0' characters are not compared.
 
char *strstr(const char *haystack, const char *needle)
{











}
      






12. (10 pts.) Implement the class Array3D of type double that creates a 3D array of 3 dimensions m x n x r as indicated in the constructor. Also implement the function getElementAt and setElementAt that gets and sets the element at this location. Base your implementation in the array of pointers to rows that we covered in class.
class Array3D {

// Add any variables you need


public:
  Array3D( int m, int n, int r);

  double getElementAt( int m, int n, int r);
  void setElementAt( int m, int n, int r);
};

Array3D::Array3D( int m, int n, int r)
{



}

double
Array3D::getElementAt( int i, int j, int k)

{



}

void
Array3D::setElementAt( int i, int j, int k, double val)
{


}
 
 
15. (10 pts) Assume that there are n threads t0, t1, t2... tn-1 where the ith thread needs to lock two mutexes mutexi and mutex(i+1)%1 to do an operation as shown in the code below. Assuming that n=6,  
a) Using a time diagram (like the ones we use in class that shows multiple threads) show the sequence of events that can lead to a deadlock.
b) Represent this deadlock in a graph.
c) Modify the code below so the deadlock can be prevented. 






 

int n = 4;

thread_function(int i) 
{
    while(1) {
       mutex_lock(&mutex[i])
       mutex_lock(&mutex[(i+1)%n);
       
       // Access resource

       mutex_lock(&mutex[i])
       mutex_lock(&mutex[(i+1)%n);
    }
} 






 
15. (10 pts) Assume that there are n threads t0, t1, t2... tn-1 where the ith thread needs to lock two mutexes mutexi and mutex(i+1)%1 to do an operation as shown in the code below. Assuming that n=6,  
a) Using a time diagram (like the ones we use in class that shows multiple threads) show the sequence of events that can lead to a deadlock.
b) Represent this deadlock in a graph.
c) Modify the code below so the deadlock can be prevented. 




 

int n = 4;

thread_function(int i) 
{
    while(1) {
       mutex_lock(&mutex[i])
       mutex_lock(&mutex[(i+1)%n);
       
       // Access resource

       mutex_lock(&mutex[i])
       mutex_lock(&mutex[(i+1)%n);
    }
} 




15. (10 pts) Assume that there are n threads t0, t1, t2... tn-1 where the ith thread needs to lock two mutexes mutexi and mutex(i+1)%1 to do an operation as shown in the code below. Assuming that n=6,  
a) Using a time diagram (like the ones we use in class that shows multiple threads) show the sequence of events that can lead to a deadlock.
b) Represent this deadlock in a graph.
c) Write a second version of thread_function where the deadlock is prevented. 


 

int n = 4;

thread_function(int i) 
{
    while(1) {
       mutex_lock(&mutex[i])
       mutex_lock(&mutex[(i+1)%n);
       
       // Do operation

       mutex_lock(&mutex[i])
       mutex_lock(&mutex[(i+1)%n);
    }
} 



13. (15 pts.) Write a program "lssort" that implements the command "ls -laR dir | sort > out". The program should not return until the command finishes. "dir" and"out" are passed as the first and second argument into the program. For example, to use lssort to list the directory /etc and send the output to ls.out you will type type "lssort /etc ls.out". Do error checking.
 

int main( int argc, char ** argv) 
{





































}

   
 
14. (15 pts.) Write a class AlertTable  that implements two methods: void insert(key, data) andchar * remove(key). The method insert(key,data)  will add the pair (key,data) to the table and will wakeup any thread calling remove(key) that is waiting for that specific key. The method remove(key) will check if there is an entry already with that key in the table and it will remove it if it is found. Otherwise, it will wait until that entry is inserted. remove(key) will return the data that corresponds to that key. If two remove(key) calls wait simultaneously for the same key, the oldest one will wakeup after the first insert call for that key and the newest one will wakeup after a subsequent insertcall with the same key. Implement the table as a list, array, hash table or in any way you want. There is no limit in the size of the table. The type of the key is char *. 

struct AlerTableEntry {
   char * key;
   void * data;
   // Other fields

};


class AlertTable {
  // Declare alert table and other fields




public:
  AlertTable();
  void insert(char * key, void * data);
  void * remove(char * key);
};

Alerttable::AlertTable()
{
  // Write ay initializations.



}

void
AlertTableEntry::insert(char * key, void *data)
{







}

char *
AlertTableEntry::Remove(char * key)
{








t}

 
 
15. (10 pts) Assume that there are n threads t0, t1, t2... tn-1 where the ith thread needs to lock two mutexes mutexi and mutex(i+1)%1 to do an operation as shown in the code below. Assuming that n=6,  
a) Using a time diagram (like the ones we use in class that shows multiple threads) show the sequence of events that can lead to a deadlock.
b) Represent this deadlock in a graph.
c) Write a second version of thread_function where the deadlock is prevented. 

 

int n = 4;

thread_function(int i) 
{
    while(1) {
       mutex_lock(&mutex[i])
       mutex_lock(&mutex[(i+1)%n);
       
       // Do operation

       mutex_lock(&mutex[i])
       mutex_lock(&mutex[(i+1)%n);
    }
}