CSE 451 Midterm Solutions

Problem 1. Scheduler Synchronization Brain Twisters

Part 1.

    // Main scheduler loop
    scheduler()
    {
          minithread_t t;
          minithread_t self = minithread_self();

          for(;;) {
               disable_interrupts();
               t = (minithread_t) dequeue(ready_queue);
               if(t) context_switch(&self->sp, &t->sp);
               enable_interrupts();
          }
    }

    // Queue manipulator
    void *dequeue(queue_t q)
    {
          queue_element_t h;
          void *a = NULL;
          h = q->head;
          if (h)  {
                a = h->elem;
                q->head = h->next;
                free(h);
          }
          return a;
    }

Part 2.

    // Main scheduler loop
    scheduler()
    {
          minithread_t t;
          minithread_t self = minithread_self();

          for(;;) {
               disable_interrupts();
               t = (minithread_t) dequeue(ready_queue);
               if(t) context_switch(&self->sp, &t->sp);
               enable_interrupts();
          }
    }

    // Queue manipulator
    void *dequeue(queue_t q)
    {
          queue_element_t h;
          void *a = NULL;
          // disable_interrupts();
          h = q->head;
          if (h)  {
                a = h->elem;
                q->head = h->next;
                free(h);
          }
          // enable_interrupts();
          return a;
    }

Part 3.

    // Main scheduler loop
    scheduler()
    {
          minithread_t t;
          minithread_t self = minithread_self();
          // tas_lock_t tas;

          for(;;) {
               // while (atomic_test_and_set(&tas) == 1)
               //       ;
               disable_interrupts();
               t = (minithread_t) dequeue(ready_queue);
               // atomic_clear(&tas);
               if(t) context_switch(&self->sp, &t->sp);
               enable_interrupts();
          }
    }

Problem 2. Monitors

  struct JavaMonitor {
      int*  x;
  }

  MonitorLock(struct JavaMonitor *m)
  {
      while (atomic_test_and_set (m->x))
         ;
  }

Because s/he used a spinlock, which is very inefficient.

(2) Assuming a working implementation of semaphores, show the code and data structures required by these monitor facilities (in other words, show how to define monitors strictly in terms of semaphores). Also, please indicate here whether you are implementing Mesa or Hoare semantics and justify by describing the behavior of your monitor.

MY MONITOR IS A: __Mesa____ (Hoare? Mesa?) BECAUSE:__It's easier to program___

// define any data structures you may need here
struct JavaMonitor {
    semaphore_t s;
};

struct JavaCondition {
     int nwaiters;
    semaphore_t c;
};

// Show the implementation of MonitorLock here.

MonitorLock(struct JavaMonitor *m)
{
     P(m->s);
}

// Show the implementation of MonitorUnlock here.

MonitorUnlock(struct JavaMonitor *m)
{
     V(m->s);
}

// Show the implementation of Condition Signal here
ConditionSignal(struct JavaCondition *s)
{
     if(c->nwaiters) { // only signal if there's a waiter
        V(c->s);
        c->nwaiters--;
    }
}

// Show the implementation of Condition Wait here
ConditionWait(struct JavaCondition *c, struct JavaMonitor *m)
{
    c->nwaiters++;
    V(m->s);  // release monitor lock
    P(c->s);  // await semaphore
    P(m->s);  // acquire monitor lock
}

Problem 3. Processes and Virtual Memory

Part 1: How is the child's memory initialized with respect to the parent's?

It is an exact copy.

Part 2: How can virtual memory be used to optimize the implementation of fork()?

Copy the page tables instead of the pages.

Part 3: Considering how so often a fork() is followed by an exec(), describe an inherent inefficiency in Unix's fork()/exec() model of process creation.

It's a waste to copy the parent's address space if we're just going to overlay it with exec anyway.

Part 4: Suggest an optimization to fork()/exec() which addresses this inefficiency.

Combine them into one system call.

Part 5: Why do we need to give a (procedure, arg) pair to minithread_fork() but we don't need to specify anything to UNIX fork()?

In fork(), the child process inherits the parent's context, including stack. In minithread_fork, the new thread has a new stack and needs something to initialize it.

Part 6: Assuming pages are 4096 bytes each, how many page table entries are required to map a contiguous 16 megabyte virtual address space?

2^24/2^12 = 2^12 = 4096

Part 7: How much of the address space could be mapped by a TLB having 16 entries?

2^12 * 2^4 = 2^16 = 64K

Part 8: Without increasing the number of entries in the TLB, how could we increase the TLB's coverage?

Increase the page size.

Part 9: Name one technique for reducing contention for TLB slots between user programs and the kernel?

Problem 4. 25 points

AcquireReadLock
    P(lock);
    if ((AW+WW) == 0) {
         /* No writers */
         V(OkToRead);
         AR++;
    } else WR++;
    V(lock);
    P(OkToRead);

    /* READ DATA */

ReleaseReadLock
    P(lock);
    AR--;
    if (AR == 0 && WW > 0) {
        /* awake writers first */
        V(OkToWrite);
        AW++; WW--;
    }
    V(lock);

AcquireWriteLock
    P(lock);
    if (AW + AR + WW == 0) {
        V(OkToWrite);
        AW++;
        if(WR) NumWriters++;
    } else WW++;
    V(lock);
    P(OkToWrite);

    /* WRITE DATA */

ReleaseWriteLock
    P(lock);
    AW--;
    if (WW > 0) {
        V(OkToWrite);
        AW++; WW--;
    } else while (WR > 0  && ((NumWriters < N) || (WR == 0))) {
        V(OkToRead);
        AR++; WR--;
        NumWriters = 0;
    }
    V(lock);

Writers exclude writers and readers. Readers exclude writers. Writers take priority over readers.

Question 2: A downside of this approach is that an excessive influx of writers can cause reader starvation. Specifically, readers might wait indefinitely as writers proceed through.

Consider a new policy for which no reader ever needs to wait for more than N writers to go before it. Writers still must run exclusively, and readers may run concurrently with other readers.

In place above, modify the code to implement this new policy.

See above.