Weekly Note 5 - Week 10

23 February 2019

Lecture - Tuesday, March 5th.

16-19 in U82

We will cover chapter 6 and 7 on Synchronization (Tools and Examples).

We will have a small review of the previous lecture, so this time it will be chapter 5, and we might sneak in a Kahoot.

Tutorial session

Thursday March 7th. 8-10 in U143 or Friday March 8th. 8-10 in U30

Preparation:

Make a list of 10-15 keywords for a 10 min. presentation with the topic: "Synchronization"

Prepare at home to discuss:

  1. Race conditions are possible in many computer systems. Consider a banking system with two methods: deposit(amount) and withdraw(amount). These two methods are passed the amount that is to be deposited or withdrawn from a bank account. Assume that a husband and wife share a bank account and that concurrently the husband calls the withdraw() method and the wife calls deposit(). Describe how a race condition is possible and what might be done to prevent the race condition from occurring.

  2. The first known correct software solution to the critical-section problem for two processes was developed by Dekker. The two processes, P 0 and P 1 , share the following variables:

boolean flag[2]; /* initially false */
int turn;

The structure of process Pi (i = 0 or 1) is shown in the Figure below; the other process is Pj, (j = 1 or 0). Prove that the algorithm satisfies all three requirements for the critical-section problem.

do {
    flag[i] = true;
    while (flag[j]) {
        if (turn == j) {
            flag[i] = false;
            while (turn == j) {
                ; /* do nothing */
            }
            flag[i] = true;
        }
    }
    /* critical section */
    turn = j;
    flag[i] = false;
    /* remainder section */
} while (true);

  1. Explain why implementing synchronization primitives by disabling interrupts is not appropriate in a single-processor system if the synchronization primitives are to be used in user-level programs.

  2. Explain why interrupts are not appropriate for implementing synchronization primitives in multiprocessor systems.

  3. The Linux kernel has a policy that a process cannot hold a spinlock while attempting to acquire a semaphore. Explain why this policy is in place.

  4. Describe two kernel data structures in which race conditions are possible. Be sure to include a description of how a race condition can occur.

  5. Assume that a system has multiple processing cores. For each of the following scenarios, describe which is a better locking mechanism-a spinlock or a mutex lock where waiting processes sleep while waiting for the lock to become available:

    1. The lock is to be held for a short duration.

    2. The lock is to be held for a long duration.

    3. The thread may be put to sleep while holding the lock.

  6. Assume a context switch takes T time. Suggest an upper bound (in terms of T ) for holding a spin lock and that if the spin lock is held for any longer duration, a mutex lock (where waiting threads are put to sleep) is a better alternative.

  7. Demonstrate that monitors and semaphores are equivalent insofar as they can be used to implement the same types of synchronization problems.

  8. Discuss the tradeoff between fairness and throughput of operations in the readers-writers problem. Propose a method for solving the readers-writers problem without causing starvation.

  9. How does the signal() operation associated with monitors differ from the corresponding operation defined for semaphores?

In class:

Use the first 30 minutes to work on those exercises:

  1. The first known correct software solution to the critical-section problem for n processes with a lower bound on waiting of n − 1 turns was presented by Eisenberg and McGuire. The processes share the following variables:

enum pstate {idle, want_in, in_cs};
pstate flag[n];
int turn;

All the elements of flag are initially idle; the initial value of turn is immaterial (between 0 and n − 1 ). The structure of process Pi is shown in the Figure below. Prove that the algorithm satisfies all three requirements for the critical-section problem.

do {
  while (true) {
      flag[i] = want in;
      j = turn;
      while (j != i) {
          if (flag[j] != idle) {
          j = turn;
      } else {
          j = (j + 1) % n;
      }
      flag[i] = in cs;
      j = 0;
      while ( (j < n) && (j == i || flag[j] != in cs)) {
          j++;
      }
      if ( (j >= n) && (turn == i || flag[turn] == idle)) {
          break;
      }
  }
  /* critical section */
  j = (turn + 1) % n;
  while (flag[j] == idle) {
      j = (j + 1) % n;
  }
  turn = j;
  flag[i] = idle;
  /* remainder section */
} while (true);

  1. Consider how to implement a mutex lock using an atomic hardware instruction. Assume that the following structure defining the mutex lock is available:

  typedef struct {
      int available;
  } lock;

where ( available == 0 ) indicates the lock is available; a value of 1 indicates the lock is unavailable. Using this struct, illustrate how the following functions may be implemented using the test_and_set() and compare_and_swap() instructions. void acquire(lock *mutex) void release(lock *mutex) Be sure to include any initialization that may be necessary.

  1. Consider the code example for allocating and releasing processes shown in the Figure below.

#define MAX PROCESSES 255
int number of processes = 0;

/* the implementation of fork() calls this function */
int allocate process() {
  int new pid;
  if (number of processes == MAX PROCESSES) {
      return -1;
  } else {
      /* allocate necessary process resources */
      ++number of processes;

      return new pid;
  }
}
/* the implementation of exit() calls this function */
void release process() {
  /* release process resources */
  --number of processes;
}

  1. Identify the race condition(s).

  2. Assume you have a mutex lock named mutex with the operations acquire() and release(). Indicate where the locking needs to be placed to prevent the race condition(s).

  3. Could we replace the integer variable

int number_of_processes = 0

with the atomic integer

atomic_t number_of_processes = 0

to prevent the race condition(s)?

  1. Suppose we replace the wait() and signal() operations of monitors with a single construct await(B), where B is a general Boolean expression that causes the process executing it to wait until B becomes true.

    1. Write a monitor using this scheme to implement the readers-writers problem.

    2. Explain why, in general, this construct cannot be implemented efficiently.

    3. Why is it important for the scheduler to distinguish I/O-bound programs from CPU- bound programs?

  2. Describe how the compare_and_swap() (not described in detail in the lecture) instruction can be used to

    1. provide mutual exclusion

    2. provide mutual exclusion that satisfies the bounded-waiting requirement.

Then spend the remaining time discussing your list of keywords, and the excercises prepared at home and in class.

  • Chapter 6 and 7 in Operating System Concepts, Enhanced eText, 10th Edition

Material (Slides, etc.)