CSCI 4061: Exam 2 Review Problems

A printer is a shared resource in that there is usually only one attached to a computing system that many users/processes can access.

Consider managing the printer using a "daemon" (background process). Programs that want to print do not so directly but instead contact the daemon to request data be printed. The printer daemon must get data from client processes, feed it to the printer, notify the client process of the completion of the printing, and then pick up the next request if any.

Describe a simple protocol that could accomplish this by specifying the following:

• What mechanism will you use to allow the printer daemon process to communicate with a client?
• How will client processes communicate data to the daemon? Keep in mind that print files have a variety of types and sizes
• How will the daemon process notify client processes of the completion of the print job or errors that occurred?
• Keep in mind that the printer daemon is a system process started when the computer boots.

As an alternative to the above daemon approach to managing a printer, consider a protocol that DOES NOT involve a manager. In this setting, the printer is usable directly by any process. However, processes that print must obey a protocol you will design to avoid problems. The printer is associated with a known special file /dev/printer. When data is written to this file, it is sent directly to the printer. However, if multiple processes write data simultaneously, the printing results are likely to become corrupted.

Design a protocol that would allow the shared printer resource to be managed without a manager process.

• What mechanism would you use for processes want to print to coordinate using the /dev/printer file?
• Is it possible in your scheme to guarantee fairness: processes that are ready to print early actually get to print earlier than later print attempts?

Give an outline of C code for Process A and Process B which would (roughly) implement the above protocol. Below

// PROCESS A
int pipeX[2];  
int pipeY[2];
int receive;  // put data "received" from Process B in this integer

// assume both pipes opened appropriately 

// A1: Process A writes its PID to Pipe X

// A2: Process A sleeps waiting for a signal

// A3: Process A wakes up from a signal 

// A4: Process A reads an integer from Pipe Y

// PROCESS B
int pipeX[2];  
int pipeY[2];
int send = 42;  // integer to "send" to Process A

// assume both pipes opened appropriately 

// B1: Process B reads a PID from Pipe X

// B2: Process B writes an integer to Pipe Y

// B3: Process B signals Process A to wake up and continue

A naive implementation of the basic protocol outlined is likely to contain flaws. For example, if Process A merely calls

sleep(0);

to await a signal, it may result in Process A never waking up.

Describe a sequence of events using the steps A1, A2,.. B1, B2 that could give rise to the this situation. Also describe how one might fix this with a slightly more complex sleeping/waiting behavior and signals handling.

Outline the similarities and differences between Processes and Threads. Describe some details of the assumptions that each makes about what memory is shared versus private. Describe the tradeoffs associated with using one versus the others on issues such as system tools, security, and efficiency.

Recall the Pi calculation program discussed in class. One version of this program spawned multiple threads to run the following worker function.

int total_hits = 0;
int points_per_thread = -1;

void *compute_pi(void *arg){
  long thread_id = (long) arg;
  unsigned int rstate = 123456789 * thread_id;
  for (int i = 0; i < points_per_thread; i++) { 
    double x = ((double) rand_r(&rstate)) / ((double) RAND_MAX);
    double y = ((double) rand_r(&rstate)) / ((double) RAND_MAX);
    if (x*x + y*y <= 1.0){
      total_hits++;
    }
  } 
  return NULL;
}

1. Why was it necessary to use the rand_r() function rather than the standard rand() function to generate random numbers?
2. Do all the worker threads generate identical random sequences of numbers or are they different? Explain your reasoning.
3. It was determined in discussion that this version always underestimates the value of Pi. Explain why and how one might fix this while also maintaining the efficiency of using multiple threads to get speedup.