Due: Wednesday, February 27th at the beginning of class (but not to hand in)

Read: Tanenbaum, Chs. 1 & 2

Solutions.

Problem 0: Review old homeworks.

Problem 1: Suppose we have two implementations of a caching multithreaded web server. Implementation #1 uses user-level threads and can process a cache hit in 15ms of CPU time and a cache miss in 15ms of CPU time plus 35ms during which it must wait for I/O. Implementation #2 uses kernel-level threads and can process cache hits in 25ms of CPU time and cache misses in 40ms of CPU time plus 35ms during which it must wait for I/O.

• Assuming that 75% or requests are for pages in the cache, which implementation can process more requests per unit time?
• What if only 60% of requests are for pages in the cache.

Problem 2: Recall the proposed use of select to avoid having one user-level thread block all others in the same process when it blocks for I/O. User level threads would call select before a potentially blocking I/O call in order to determine if the call would block. Consider the following pseudocode implementation of this idea.

while (!select(cin))
  ; /* do nothing */

int data;
cin >> data;

Problem 3: Draw a diagram showing thr parent/child relationships among the processes created by the following code fragment. Also show which call to fork created each process.

pid = fork() /* call #1 */

if (pid != 0)
  fork()     /* call #2 */

fork()       /* call #3 */

Problem 4: Consider Peterson's solution to the mutual exclusion problem. Explain how this solution satisfies the condition "no process should have to wait forever to enter its critical region". Consier the following attempt to generalize Peterson's solution to three processes. Assume that the processes are numbered 0, 1, and 2. Does this proposal meet all the criteria for solutions to the mutual exclusion problem?

void enter_region(int process)
{
  int other1 = (process + 1) % 3; /* other1 and other 2 are the ids */
  int other2 = (process + 2) % 3; /* of the other two processes     */

  interested[process] = TRUE;
  turn = other1;
  
  while (turn != process && (interested[other1] || interested[other2]))
    ; /* do nothing */
}

void leave_region(int process)
{
  interested[process] = false;
}

Problem 5: Complete the following pseudocode definition of a condition variable assuming that the operating system provides system calls for semaphores.

class ConditionVariable
{
  Semaphore sem = ???
  Semaphore mutex = 1;
  // declare anything else you need

  void wait()
  {

  }

  void signal()
  {

  }

  void broadcast()
  {

  }
}

Problem 6: The HRM702 heart rate monitor has several functions. It has a stopwatch, a clock, and of course a heart rate monitor. Each function is handled by a separate process, and so the HRM702 has some sort of an operating system to manage those processes. Do you think the HRM702 OS provides anything like the following Unix system calls? Explain your answers.

• execvp
• open
• link

Problem 7: Imagine a CPU with the ability to encrypt the return address as it is pushed on the stack by the call instruction and then decrypt it as it is popped from the stack by the ret instruction. With such encryption in place, someone wishing to overwrite the return address with a buffer overflow would need to know the address of the buffer that the malicious code was overflowing as well as the key used to encrypt the return addresses. The encryption is a simple xor with a key that is held in a special register. Should that key be accessible at the user level? Should the OS maintain a separate key for each process? Explain your answers.

Problem 8: Suppose there are several files containing information about several schools. The files are names info_001.txt, info_002.txt, etc. There is a file that records which school corresponds to which file. The file will look like the following.

001:Virginia:
002:Loyola College in Maryland:
003:Boston College:
004:Texas A&M: