Part 0. Write your name

Name:

____ Mutex-locks are needed only on multi-threaded programs.
____ During starvation a thread waits for a resource or mutex lock that will never be available.
____ Mutex locks are only needed in multiprocessor machines.
____ It is possible to have a deadlock with only one mutex.
____ The text section of a program is memory mapped Read Write and Executable.
____ The instruction cond_wait unlocks a mutex lock.
____ Most of the time processes are in ready state,
____ Semaphores may have a negative count after calling sema_post().
____ ELF stands for Extended Link Format.
____ cond_post will always wake up a thread waiting on cond_wait.

____ Non-accessed pages are prefered for replacement instead of modified pages.
____ A valid page size in a 64 bit machine could be 8000 Bytes.
____ sizeof(int *) is 4 bytes and sizeof(char *) is 1 byte.
____ LRU works because a page that has been accessed recently is likely to be accessed in the short future.
____ Inverting the order of the mutex_lock and sema_wait calls in the bounded buffer problem leads to starvation.
____ There are at most two ready processes in a dual processor computer.
____ The page-table register is updated every time there is a context switch from one thread to another.
____ Semaphores initialized with 1 may be used as mutex_locks.
____ All pages in physical memory that are replaced are written back to the disk.
____ In a correct program, it is possible to have more free calls than allocate calls.

____ In the SPARC architecture all addresses of integer variables are multiple of 4 bytes.
____ An object returned by malloc could have an address like 0x100284
____ A memory leak is more serious than a premature free.
____ Modern computers use non-preemptive scheduling.
____ A page fault is an interrupt.
____ Threads in the same process share the same stack.
____ Most processes in a system are in ready state.
____ The second chance algorithm is an implementation of LRU using modified bits.
____ By default, pthread_create will create a thread that has preemptive scheduling.
____ When a process updates memory that has been memory mapped from a file, the OS updates the file in disk immediately.
 

Part 2. Short Questions

2. (4 pts) Explain how fork() benefits from using Virtual Memory.
 
 
 
 
 
 
 
 
 

3. (4 pts) Explain how the context switch among threads is different than the context switch among processes.
 
 
 
 
 
 
 
 

4. (4 pts) Explain how could you make your malloc implementation that uses boundary tags tolerant to freeing previously freed objects?

5. (4 pts) Describe how you could make your malloc implementation tolerant to premature frees. If it is not possible mention why.
 
 
 
 
 
 
 
 

6. (5 pts) The following three threads have access to six databases. Each database has its own mutex lock.
a) Could the following threads enter in a deadlock? If that is the case draw the graph that shows the loop that represents this deadlock.
b) If the threads cannot enter into a deadlock, give an alteration of the the mutex_lock call sequence that may lead to a deadlock and draw a graph with the loop that represents this deadlock.

thread1()
{
    while (1) {
      mutex_lock( &mutex_dbD);
      mutex_lock( &mutex_dbE);
      mutex_lock( &mutex_dbB);

      // Access dbD, dbE, dbB

      mutex_unlock( &mutex_dbD);
      mutex_unlock( &mutex_dbE);
      mutex_unlock( &mutex_dbB);
    }
}

thread2()
{
    while (1) {
      mutex_lock( &mutex_dbC);
      mutex_lock( &mutex_dbF);
      mutex_lock( &mutex_dbD);

      // Access dbC, dbF, dbD

      mutex_unlock( &mutex_dbC);
      mutex_unlock( &mutex_dbF);
      mutex_unlock( &mutex_dbD);
    }
}

thread3()
{
    while (1) {
      mutex_lock( &mutex_dbA);
      mutex_lock( &mutex_dbB);
      mutex_lock( &mutex_dbC);

      // Access dbA, dbB, dbC

      mutex_unlock( &mutex_dbA);
      mutex_unlock( &mutex_dbB);
      mutex_unlock( &mutex_dbC);
    }
}

struct List {
  int val;
  int next;
};

struct List * head = NULL;

void insert( int val )
{
  (1)List tmp = new List;

  (2)tmp->val = val;

  (3)tmp->next = head;

  (4)head = tmp;
}

Struct List * removeFirst()
{
  (5) List tmp = head;

  (6) head = tmp->next;
}

Part 3 Long Questions. (10 points each)

9. From your malloc implementation write the code for malloc() implementing only the bestfit part with no boundary tags Assume that the free list is sorted by address. Add comments to your code.
 

10. IMPORTANT:Use condition variables and mutex locks for synchronization in this problem.  Implement the methods sendMessage(int msg ) and receiveMsgN(int n, int *msgArray) . sendMsg sends one message and receiveNMsg() receives n of these messages. sendMessage(int msg) sends a message to a thread calling receiveNMsg() . sendMessage() will wait until there is another thread calling receiveNMsg(), and then sendMessage() will send the message. receiveNMsg( int n, int *msgArray) will wait if there is already  a receiveNMsg() going on, then, receiveNMsg() will wait until n sendMessage() calls are made. Each of the n messages is stored in the aray msgArray passed as parameter to receiveNMsg(). The messages sent are integer values.
 

11. Write the procedure execToBuffer(char ** args, char * buffer, int max ) that executes the command described in args in a child process and writes the output of the command to a a buffer up to max-1 characters. See the main procedure to see how execToBuffer is used. execToBuffer() will return 0 on success or different than 0 if it failed. If success, buffer will be a NULL terminated string.