It seems that the alpha software isn't doing all that well.
Just looking at the software, you can see that there are several
synchronization problems.
The first problem is that sometimes two people are assigned
to the same machine. Why does this happen?
We can fix this with a lock:
int a[N];
Lock *l;
int get() {
l->Acquire();
for (i = 0; i < N; i++) {
if (a[i] == 0) {
a[i] = 1;
l->Release();
return(i+1);
}
}
l->Release();
}
void put(int i) {
l->Acquire();
a[i-1] = 0;
l->Release();
}
So now, have fixed the multiple assignment problem. But what
happens if someone comes in to the laundry when all of the
machines are already taken? What does the machine return?
Must fix it so that the system waits until there is a machine
free before it returns a number. The situation calls for
condition variables.
int a[N];
Lock *l;
Condition *c;
int get() {
l->Acquire();
while (1) {
for (i = 0; i < N; i++) {
if (a[i] == 0) {
a[i] = 1;
l->Release();
return(i+1);
}
}
c->Wait(l);
}
}
void put(int i) {
l->Acquire();
a[i-1] = 0;
c->Signal();
l->Release();
}
What data is the lock protecting? The a array.
When would you use a broadcast operation? Whenever want to
wake up all waiting threads, not just one. For an event
that happens only once. For example, a bunch of threads may
wait until a file is deleted.
The thread that actually deleted the file could use a broadcast to wake
up all of the threads.
Also use a broadcast for allocation/deallocation of variable
sized units. Example: concurrent
malloc/free.
Lock *l;
Condition *c;
char *malloc(int s) {
l->Acquire();
while (cannot allocate a chunk of size s) {
c->Wait(l);
}
allocate chunk of size s;
l->Release();
return pointer to allocated chunk
}
void free(char *m) {
l->Acquire();
deallocate m.
c->Broadcast(l);
l->Release();
}
Example with malloc/free. Initially start out with
10 bytes free.
Time
Process 1
Process 2
Process 3
malloc(10) succeeds
malloc(5) suspends lock
malloc(5) suspends lock
1
gets lock - waits
2
gets lock waits
3
free(10) broadcast
4
resume malloc(5) succeeds
5
resume malloc(5) succeeds
6
malloc(7) waits
7
malloc(3) waits
8
free(5) broadcast
9
resume malloc(7) waits
10
resume malloc(3) succeeds
What would happen if changed
c->Broadcast(l) to c->Signal(l)?
At step 10, process 3 would not wake up, and it would
not get the chance to allocate available memory.
What would happen if changed
while loop to an if?
You will be asked to implement condition variables as part
of assignment 1. The following implementation is INCORRECT.
Please do not turn this implementation in.
Why is this solution incorrect? Because in some cases the signalling
thread may wake up a waiting thread that called Wait after the
signalling thread called Signal.
