Self-written Mutex for 2+ Threads

Question

I have written the following code, and so far in all my tests it seems as if I have written a working Mutex for my 4 Threads, but I would like to get someone else's opinion on the validity of my solution.

typedef struct Mutex{
    int turn;
    int * waiting;
    int num_processes;
} Mutex;

void enterLock(Mutex * lock, int id){   
    int i;
    for(i = 0; i < lock->num_processes; i++){
        lock->waiting[id] = 1;
        if (i != id && lock->waiting[i])
            i = -1;
        lock->waiting[id] = 0;
    }
    printf("ID %d Entered\n",id);
}

void leaveLock(Mutex * lock, int id){
    printf("ID %d Left\n",id);
    lock->waiting[id] = 0;
}

Answer 1

Broken

If you call enterLock() with id 0 followed by enterLock() with id 1 (on another thread perhaps), both calls will succeed. Since your function doesn't change the state of the mutex, it isn't surprising. Perhaps you meant to leave lock->waiting[id] at 1 instead of 0? Note, even if you did that, it wouldn't be enough to fix the mutex.

Also, what is the turn variable used for?

Spinlock, not mutex

Technically, what you are doing is a spinlock. A real mutex should efficiently wait for its turn instead of spinning in a loop.

Answer 2

Broken for more reasons

Without even looking at the details, I can tell that the mutex is not safe. The compiler is allowed to re-order your instructions which means that your writes and reads may not occur in the order you have written them. The compiler may actually even omit them totally... Not to mention there is no guarantee on memory ordering semantics at all.

Writing threading primitives correctly is VERY difficult, I do not recommend that you try to write your own unless you are very knowledgeable about the pitfalls. (And if you are, then you know you don't want to do this unless absolutely necesscary).