N processes and M types of processes - enter and exit cs

Question

i was asked to write: enter function and exit function for the following case:

there are N processes and M types of processes (N>>M) tere is a critical section in which all processes with the same type can enter. for example: if type A is in cs, type B cannot enter cs. but all processes with type A can enter.

i can use only mutex and "type" which is the type of the process. deadlock is not allowed.

do you think this is ok?

shared: this.type = -1;
mutex m, m1=1;

enter{
    down(m)
    if (this.type == process.type) up(m1)
    down(m1)
    this.type= process.type
    up(m)
}
exit {
    this.type = -1
    up(m1)
}

thanks! (by the way, this is not HW... i have an exam and im solvig tests from previous years)

Answer 1

I'd say no, the current method is not okay.

Specifically, say a type 0 comes in, and gets through enter. type 1 then comes through before type 0 exited. It hits the mutex, finds that the process type is wrong and locks on m1. Type 0 then comes through, unlocks m, resets process type, and the lock on m1 is still in effect.

In addition, if you have 2 processes of type 0 enter, the first one to exit will cause the running process type to be reset while processes are still in the critical section.

I'm making an assumption that 'up' is akin to unlock, and 'down' is akin to lock; it sounds like a set of methods intended for a semaphore though. I'm also making an assumption that there are only two mutexes for the system (m and m1); as the markup isn't perfectly clear about that.

EDIT: The suggestion you offered would come out to something like this:

shared: this.type = -1;
mutex m, m1=1;
count=0;

enter{
    down(m)
    if (this.type == process.type) up(m1)
    down(m1)
    this.type= process.type
    count++;
    up(m)
}
exit {
    count--;
    if(count==0) this.type = -1
    up(m1)
}

This still has the problem that exit isn't thread safe on state modifications; and that when a new Process is woken/starts executing, its brethren are not woken.

I'm not entirely certain that there is a safe way to do this without Condition variables; unless there is more information about the problem available. (ie is this in the context of a 'Monitor', where method executions are already threadsafe)

Answer 2

i think about what you say and indeed i can see the problem - 10X!

what about adding a counter? when the first process of the same type enter if the counter==0 type==process.type (initialize the type)

in exit: counter-- and i will cheack if (count==1) type=-1.

better??