Weekly Notes for Week 13

Due to the university lockdown we will still use Zoom for online teaching and this week also for the tutorials.
In the lecture in week 13 we will discuss Chapter 9 (Main Memory), Chapter 10 (Virtual Memory).
In the lecture on Wednesday I will give an introduction to the 2nd mandatory assignment.

Tutorial Session Week 13

See also the Weekly Notes from Week 11, as there are still important exercises from Chapter 5 to be discussed. In addition prepare the following exercises form Chapter 6:

In Section 6.4, we mentioned that disabling interrupts frequently can affect the system’s clock. Explain why this can occur and how such effects can be minimized.
What is the meaning of the term busy waiting? What other kinds of waiting are there in an operating system? Can busy waiting be avoided altogether? Explain your answer.
Explain why spinlocks are not appropriate for single-processor systems yet are often used in multiprocessor systems.
Show that, if the wait() and signal() semaphore operations are not executed atomically, then mutual exclusion may be violated.
Illustrate how a binary semaphore can be used to implement mutual exclusion among n processes.
Race conditions are possible in many computer systems. Consider a banking system that maintains an account balance with two functions: deposit(amount) and withdraw(amount). These two functions are passed the amount that is to be deposited or withdrawn from the bank account balance. Assume that a husband and wife share a bank account. Concurrently, the husband calls the withdraw() function, and the wife calls deposit(). Describe how a race condition is possible and what might be done to prevent the race condition from occurring.

The pseudocode below illustrates the basic push() and pop() operations of an array-based stack. Assuming that this algorithm could be used in a concurrent environment, answer the following questions:

What data have a race condition?
How could the race condition be fixed?

 push(item) {
     acquire();
     if (top < SIZE) {
         stack[top] = item;
         top++;
     }
     else
         ERROR
             release();
 }
 pop() {
     acquire();
     if (!is empty()) {
         top--;
         item = stack[top];
         release();
         return item;
     }
     else
         ERROR
             release();
 }
 is empty() {
     if (top == 0)
         return true;
     else
         return false;
 }

The following program example can be used to sum the array values of size N elements in parallel on a system containing N computing cores (there is a separate processor for each array element):
```
 for j = 1 to log 2(N) {
     for k = 1 to N {
         if ((k + 1) % pow(2,j) == 0) {
           values[k] += values[k - pow(2,(j-1))]
         }
     }
 }
```
This has the effect of summing the elements in the array as a series of partial sums, as shown in the figure below.

After the code has executed, the sum of all elements in the array is stored in the last array location. Are there any race conditions in the above code example? If so, identify where they occur and illustrate with an example. If not, demonstrate why this algorithm is free from race conditions.
One approach for using compare_and_swap() for implementing a spinlock is as follows:
```
 void lock spinlock(int *lock) {
     while (compare_and_swap(lock, 0, 1) != 0)
         ; /* spin */
 }
```
A suggested alternative approach is to use the “compare and compareand-swap” idiom, which checks the status of the lock before invoking the compare_and_swap() operation. (The rationale behind this approach is to invoke compare_and_swap() only if the lock is currently available.)

This strategy is shown below:
```
 void lock_spinlock(int *lock) {
     while (true) {
         if (*lock == 0) {
             /* lock appears to be available */

             if (!compare_and_swap(lock, 0, 1))
                 break;
         }
     }
 }
```
Does this “compare and compare-and-swap” idiom work appropriately for implementing spinlocks? If so, explain. If not, illustrate how the integrity of the lock is compromised.

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 $P_i$ (i == 0 or 1) in Dekker’s algorithm is shown below. The other process is $P_j$ (j == 1 or 0).

 while (true) {
     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 */
  }

Prove that the algorithm satisfies all three requirements for the critical-section problem.

Consider how to implement a mutex lock using the compare_and_swap() instruction. Assume that the following structure defining the mutex lock is available:
```
 typedef struct {
     int available;
 } lock;
```
The value (available == 0) indicates that the lock is available, and a value of 1 indicates that the lock is unavailable. Using this struct, illustrate how the following functions can be implemented using the compare_and_swap() instruction:
- void acquire(lock *mutex)
- void release(lock *mutex)
Be sure to include any initialization that may be necessary.
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:
- The lock is to be held for a short duration.
- The lock is to be held for a long duration.
- A thread may be put to sleep while holding the lock.
A multithreaded web server wishes to keep track of the number of requests it services (known as hits). Consider the two following strategies to prevent a race condition on the variable hits. The first strategy is to use a basic mutex lock when updating hits:
```
 int hits;
 mutex lock hit lock;
 hit lock.acquire();
 hits++;
 hit lock.release();
```
A second strategy is to use an atomic integer:
```
 atomic t hits;
 atomic inc(&hits);
```
Explain which of these two strategies is more efficient.
Servers can be designed to limit the number of open connections. For example, a server may wish to have only N socket connections at any point in time. As soon as N connections are made, the server will
Describe how the signal() operation associated with monitors differs from the corresponding operation defined for semaphores.