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.

• 75% cache hits: 25ms * 0.75 + 40ms * 0.25 = 28.75ms per request for kernel-level. 15ms * 0.75 + (15ms + 35ms) * 0.25 = 23.75ms per request for user-level threads. User-level threads are faster.
• 60% cache hits: 25ms * 0.60 + 40ms * 0.40 = 31ms per request for user-level versus 15ms * 0.60 + (15ms + 35ms) * 0.40 = 29ms per request for user-level. User-level threads are still faster.

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;

Threads will poll the input device continually without giving up the CPU. This can be fixed by putting a yield call in the loop or by replacing the kernel call select with a similar call to the user-level thread system; that new call would make the select call to the kernel and if input was not available could also do a yield.

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 */

Pardon the ASCII art.

     parent
   /    |   \
  #1   #2   #3
   |    |
  #3   #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". Consider 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;
}

This can make two processes both wait while the third is not trying to enter its critical region:

• P1 calls enter_region but is preempted just before the loop.
• P2 calls enter_region, sets turn to 0, and begins waiting in the loop.
• P0 calls enter_region, sets turn to 1, and begins waiting.
• P1 resumes, and since turn = 1 it enters its critical region.
• P1 leaves its critical region and calls leave_region.
• P0 and P2 are still waiting in the loop since turn = 1 and interested[0] and interested[1] are both true.

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

See if you can find the error in the following attempt at a solution, and then see this paper from Microsoft.

class ConditionVariable
{
  Semaphore sem = 0;
  Semaphore mutex = 1;
  // declare anything else you need
  int waiting = 0;

  void wait()
  {
    mutex.down();
    waiting++;
    mutex.up();
    sem.down();
  }

  void signal()
  {
    mutex.down();
    if (waiting > 0)
    {
        sem.up();
        waiting--;
    }
    mutex.up();
  }

  void broadcast()
  {
    mutex.down();
    while (waiting > 0)
    {
        sem.up();
        waiting--;
    }
    mutex.up();
  }
}

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 Assuming that all three processes are running all the time, there is no need to start new processes, so no need for execvp.
• open If the HRM has some sort of memory, it might save data using established calls for file I/O. On the other hand, if all saved data is stored in structures held by the processes then there is no need for open.
• link This is really most useful on a general system in which the files that will be created are not known at system design time. Even if the HRM702 were to save data as files, the designers would know ahead of time what files could possibly exist, and so wouldn't need 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.

It should be a per-process item. Otherwise, any user on the system could examine a stack dump of a known piece of code to determine what the key is. Knowing that key, a malicious user could contrive a buffer overflow that would write the encrypted address of the buffer over the return address. The hardware would then decrypt the fake return address and execute the code copied to the buffer.

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

#!/bin/bash

SEARCH="${1}:"
FILE=`grep "$SEARCH" index.txt | cut -d':' -f 1`

if [ "$FILE" = "" ]; then
  echo "$1 not found in index"
else
    FILE="info_$FILE.txt"

    if [ -e $FILE ]; then
        cat $FILE
    else
        echo "File $FILE not found"
    fi
fi