CS372: Homework 6

Problem 1:

Show that the following algorithm is a correct solution to the critical section problem for two processes (satisfies the 3 conditions discussed in the text). The solution for process P_i (i = 0 or 1) with P_j(j = 1 or 0) is shown below:
flag[2];
int turn = 0;

flag[i] = 1;
while (flag[j])
{
    if (turn == j)
    {
        flag[i] = 0;
        while(turn == j)
            ;
        flag[i] = 1;
    }
}

/* enter C.S. */
/* exit C.S. */
turn = j;
flag[i] = 0;

This algorithm is called Dekker's solution.

Problem 2:

John Hacker is a hardware designer who came up with a great idea for a hardware instruction that he claims can help in solving the critical section problem. It is called atomic counters. An atomic counter is a variable in memory that can be sampled and incremented in one atomic operation. Also, it can be reset to 0. That is, the two opreations allowed on the shared variable a are:

j = a++; // execute in one atomic operation
a = 0;

Either come up with a solution to the C.S. problem using this facility or show that it cannot help.

Problem 3

A common technique to achieve mutual exclusion in a uniprocessor kernel is to disable interrupts before getting inside a critical
section and enable them after exiting a critical section. Explain why this technique works.

Problem 4:

Following is an implementation of a stack data structure for a multithreaded application. Identify the bugs, if any, and correct them.

#include "Exception.h"
#include "Semaphore.h"
#include <iostream.h>

const MaxStackSize = 100;

class Stack            // throws an exception object when popping an empty stack, and when pushing into a full stack
{
private:
    int s[MaxStackSize];
    int stackp;                        // stack pointer
    Exception * e;                  // For error handling
    Semaphore * sem;           // For mutual exclusion
public:
    Stack();
    ~Stack()        {};
    int Pop(void);
    void Push(int item);
};

Stack::Stack()
{
    stackp = MaxStackSize;
    e = new Exception();
    sem = new Semaphore(1);
}

int Stack::Pop(void)
{
    P(sem)
    if(stackp == MaxStackSize)
        {
            e->SetErrorMsg("Popping empty stack");
            e->SetErrorLocation("Stack::Pop()");
            throw(e);
        }
    V(sem);
    return s[stackp++];
}

void Stack::Push(int item)
{
    P(sem)
    if(stackp == 0)
        {
            e->SetErrorMsg("Pushing to a full stack");
            e->SetErrorLocation("Stack::Push()");
            throw(e);
        }
    s[--stackp] = item;
    V(sem);
}