Original code:

int allocate()
{
    P(nfree);
    for (int i=0; i < NMACHINES; i++) 
        if (available[i] == TRUE) {
            available[i] = FALSE;
            return i;
        }
}

void release(int machine)
{
    available[machine] = TRUE;
    V(nfree);
}

Part A

The problem occurs because there is no protection around testing and setting the available variable. So if two requests are executed in lockstep, the test available[0] == TRUE will succeed for both of them, and both will return machine 0 to the caller. To solve this, we can protect the access:

Lock lock;

int allocate() 
{
    P(nfree);
    lock->Acquire();
    for (int i=0; i < NMACHINES; i++)
    if (available[i] == TRUE) {
        available[i] = FALSE;
        lock->Release();
        return i;
    }
}

void release(int machine)
{
    lock->Acquire();
    available[machine] = TRUE;
    lock->Release();
    V(nfree);
}

Notes:

• The lock in release is unnecessary if we have atomic assignment.
• Many people acquired and released the lock inside the for loop; ie.

      for (i = 0; i < NMACHINES; i++) {
          lock->Acquire();
          if (available[i] == TRUE) {
              available[i] = FALSE;
              lock->Release();
              return i;
          }
          lock->Release();
      }
  

  In this case, one ensures that a machine won't become unavailable between being checked and being returned, but it is possible that the contents of the table can change in the middle of verification. It is possible to imagine, for example, that in the middle of the for loop, a slot that's already checked becomes available, and the only other empty slot (not checked yet) becomes taken; in which case the for loop will terminate without finding the empty slot. This won't in fact happen, but proving this is non-trivial.

Part B

The problem occurs because several customers may be allocated a subset of their desired machines, while waiting for more to become available. For example, if there are 4 machines in the laundromat, and customers A and B request 3 each, it's possible that both A and B will be allocated two machines, after which neither A nor B can make progress -- they are deadlocked. There were two basic solutions to this:

Variant 1

Lock lock;

int acquire(int nummachines) 
{
    lock->Acquire();
    for (int i = 0; i < nummachines; i++) 
        P(nfree);

    // allocate available machines
    for (i = 0; i < MACHINES; i++) {
        if (available[i] == TRUE) {
        available[i] = FALSE;
        nummachines--;
        if (!nummachines)
            break;
    }
    }
    
    lock->Release();
    // return allocated machines
}

void release(int machine)
{
    available[machine] = TRUE;
    V(nfree);
}

Variant 2

Lock lock;
Condition machineAvailable;
int numFree;

int acquire(int nummachines) 
{
    lock->Acquire();
    while (numFree < nummachines)
    machineAvailable->wait(&lock);
    
    numFree -= nummachines;
    // allocate machines
    lock->Release();
}

int release(int machine)
{
    lock->Acquire();
    numFree++;
    available[machine] = TRUE;
    machineAvailable->broadcast(&lock);
		lock->Release();
}

The first variant ensures that machines are allocated on a first-come first-serve basis; each customer waits to receive all the requested machines, and then the next customer may try to allocate. The second variant ensures that machines are allocated all at once, but lets waiting people compete for them, regardless of arrival order. This can lead to starvation: if customer A is waiting for 3 machines, and only two are available, other customers requesting one or two machines can delay A indefinitely. On the other hand, the first variant could be considered inefficient, since it prevents the above scenario by not allowing new customers to proceed until A gets his machines, even if there are enough available machines for other customers to proceed.

If your solution allowed starvation to occur, you would have lost some points, unless you explicitly stated that you understand that this occurs.