vendredi 15 janvier 2021

how to implement a new condition variable using other synchronization tools?

i have new synchronization tool (newSem) , and i want to implement a conditional variable using this newSem and mutex , i am stuck and don't know what i am doing wrong ! i added what i tryed this far !

this is the newSem :

typedef struct newSem{
    int value;
} newSem;
// Initialize the newSemto value 0.
void newSem(newSem* h) {
   h->value = 0;
}
// Block until the newSem has value >= bound, then atomically increment its value by delta.
void H(newSem* h, int bound, int delta) {
// This is pseudocode; a real newSem implementation would block, not
// spin, and would ensure that the test and the increment happen in one
// atomic step.
     while (h->value < bound) {
         sched_yield();
     }
     h->value += delta;
}

this is the mutex i implemented (using the newSem) :

typedef struct mutex {
newSem h;
} mutex;

 void mutex_init(mutex* m) {
    
    // Initialize the newSemh ( the value is zero)
    newSem(m->h);
}

// first thread that enters sets the value to -1 , that means other 
// threads will have the value < bound , and will be blocked
void mutex_lock(mutex* m) {
    H(m->h, 0, -1);
}

// value is now set to 1, so other threads can now go in
void mutex_unlock(mutex* m) {
    H(m->h, -1, -1);
}

and this is the conditional variable that i implemented ( what is written in the comments is what i should do exactly ) also we can assume that if there were N threads waiting on the condition variable c then if we call cond_signal(c) N times then this is sufficient in order to wake all the threads

typedef struct condvar {
    mutex m;
    newSem h;
} condvar;

// Initilize the condition variable
void cond_init(condvar* c) {
    newSem(&c->h);
}

// Signal the condition variable
void cond_signal(condvar* c) {
    H(&c->h, INT_MIN, 1);
}


// Block until the condition variable is signaled. The mutex m must be locked by the
// current thread. It is unlocked before the wait begins and re-locked after the wait
// ends. There are no sleep-wakeup race conditions: if thread 1 has m locked and
// executes cond_wait(c,m), no other thread is waiting on c, and thread 2 executes
// mutex_lock(m); cond_signal(c); mutex_unlock(m), then thread 1 will always recieve the
// signal (i.e., wake up).
void cond_wait(condvar* c, mutex* m) {
    mutex_unlock(m);
    H(&c->h, 0, -1);
    mutex_lock(m);
}

what am i missing ? i can't figure how to use newSem and mutex correctly (also why is this synchronization subject is so hard !!!!!!!!!!!!!!!!!!!!!!!!!!)

Aucun commentaire:

Enregistrer un commentaire