CS354 Spring 2004

Final Exam


Name: ____________________________________________









Question
 Max
 Grade
T/F
20pts
1-7
 30 pts
8.
 10 pts.
9.
 10 pts.
10.
 15pts.
11.
 15pts.
Total:
 100pts.























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

____ Most of the time processes are in the  waiting state.
____ ELF is an executable file format used in early versions of Windows.
____ The backing-store of the Text segment is swap space.
____ The stack of one thread could potentially be modified by another thread.
____ Double frees are a serious problem in short lived programs.

____ A page size has to be a power of 2.
____ Memory leaks are a serious problem in longed lived programs.
____ mutex locks should be unlocked in the opposite order they were locked to prevent deadlocks.
____ The file offset pased to mmap should be a multiple of a page size.
____ Free of Non-Heap objects can be tolerated by the allocator in lab7.

____ FIFO is a good page replacement policy because it predicts the future using past events.
____ BEST FIT is more space efficient than FIRST FIT.
____ Copy on write is used during fork().
____ An object returned by malloc could have an address like 0x100287.
____ A v-node may be used by multiple processes.

____ There is one page table for each processor in the computer.
____ i-nodes are fined tuned for medium and large files for scalability.
____ cond_signal could wake up more than one thread.
____ The same page in physical memory could have two different VM addresses in two different processes.
____ mmaped memory that is modified is immediately updated in the mapped file.
 

Part 2. Short Questions

1. (4 pts) Explain how the OS during copy-on-write detects that a page is modified..
 
 
 
 
 
 
 
 
 
 

2. (4 pts) Explain the differences between a symbolic and ahard link.
 
 
 
 
 
 
 
 
 

3. (4 pts) Explain how the algorithm that uses both the modified and access bit works.
 
 
 
 
 
 
 
 

4. (4 pts) Explain in what conditions a duplicate free will not be detected by the allocator explained in lab7.






5. (4 pts) Explain what will happen if the allocator explained in lab7 is used with the following code:

char * p;
p = (char *) malloc( 40 );
p = p + 5;
free(p);





6. (5 pts) Write the fields of an i-node and mention what each field is used for.















7. (5 pts) Add the necessary code to the insert() and removeFirst() functions to make them synchronized.  removeFirst() will have to wait if the list is empty. insert() will have to wait  if there are already 20 elements in the list. Use condition variables. Add also the variables you need.

struct List {
  int val;
  int next;
};

struct List * head = NULL;

// More variables


void insert( int val )
{


  List tmp = new List;

  tmp->val = val;

  tmp->next = head;

  head = tmp;

}

Struct List * removeFirst()
{

  List tmp = head;


  head = tmp->next;

}

Part 3 Long Questions. 

 
8. (10 pts) IMPORTANT: Use condition variables in this problem. Complete the class MReadNWriteLock that is a generalization of the  read/write locks but that limits the number of readers to M and the number of writers to N. This kind of  locks allows at most M readers or N writers but not both. For example, if at least one thread is holding the lock in write mode, reader threads will have to wait but not writer threads. If at least one thread is holding the lock in read mode, writer threads will have to wait. It is possible to have up to M reader threads. If thread M+1 tries to read, it will block until another reader thread unlocks the lock. It is possible to have up to N writer threads. If thread N+1 tries to write, it will block until another writer thread unlocks the lock.

class MReadNWriteLock {
  /* Add other fields here */
 
 
 
 
 
public:
  MReadNWriteLock( int m );
  readLock();
  writeLock();
  readUnlock();
  writeUnlock();
};

MReadNWriteLock ::MReadNWriteLock ( int m )
{
 
 
 
 
 
 
 
 

}

void
MReadNWriteLock ::readLock()
{
 
 
 
 
 
 
 

}

void
MReadNWriteLock ::writeLock()
{
 
 
 
 
 
 
 

}

void
MReadNWriteLock ::readUnlock()
{
 
 
 
 
 
 
 

}

void
MReadNWriteLock ::writeUnlock()
{
 
 
 
 
 
 
 
 

}


 


 

9. (10 pts.) The following program implements the equivalent command "sort file | grep pattern > out" where file, pattern and out are passed as arguments to the program. Assuming the program is named :myprog:, then the command "myprog myfile aaa outfile" will run the the equivalent command "sort myfile aaa > outfile".  Call  perror() and call exit(1) if there is an error, otherwise exit(0) if success.

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



















}

 
 
10. (15 pts) From lab7 write the method int Allocator::objectSize( void * ptr ) that returns the size of the object pointed by ptr or 0 if there is an error. If you need helper functions also include them in your implementation.

int
Allocator::objectSize( void * ptr ) {


















}
 

 
 
11. (15 pts) IMPORTANT: Use condition variables in this problem. Complete the class WaitStack  where void popWait(int val) will wait until val is on the top of the stack and then it wil pop the value. The function void push(int val) will push a value into the stack and it will wait if the stack is full. At most one popWait call will return for each entry in the stack.
class WaitStack {
  /* Add other fields here */
 
 
 
 
 

public:
  WaitStack( int MaxStack );
  void popWait(int val);
  void push( int val );
};

WaitStack::WaitStack ( int MaxStack )
{
 
 
 
 
 
 
 
 

}

void
WaitStack::popWait(int val);
{
 
 
 
 
 
 
 

}

void
WaitStack::push( int val );
{
 
 
 
 
 
 
 

}