Sunday, September 11, 2011

First Theoretical Presentation

This entry is for the first theoretical presentation.
The content of the entry is an explication to solve the problem unbounded-buffer, and a the unity test for the implement of lock using semaphore, for the project we are working with nachOS 3.4 and C++.


The next code is an example of how to solve the problem unbounded buffer using three locks, one lock for producers, the second lock for consumers and the last one for protecting the access to products.




int maxProducts;
int products;
Lock *consumerLock;
Lock *producerLock;
Lock *changeProductsState;

consumer(){
    bool hasConsumerLock = false;
    while(1){
        if(!hasConsumerLock){
            consumerLock->Acquire();
            hasConsumerLock = true;
        }
        if(products > 0){
            changeProductsState->Acquire();
            products--;
            changeProductsState->Release();
            consumerLock->Release()
            hasConsumerLock = false;
        }
    }
}
producer(){
    bool hasProducerLock = false;
    while(1){
        if(!hasProducerLock){
            producerLock->Acquire();
            hasProducerLock = true;
        }
        if(products < maxProducts){
            changeProductsState->Acquire();
            products--;
            changeProductsState->Release();
            producerLock->Release()
            hasProducerLock = false;
        }
    }
}



Here are some unity test used to test the implementation of the Lock using Semaphore.


Fairness

Lock *l;

Fairness(){
    while(1){
        l->Acquire();
 #some critical computation goes here
 l->Release();
 print "threadName adquired the lock"
    }
}

Liveness

Lock *l;

Liviness(){
    while(1){
 print "threadName ask for the lock";
 l->Adquire();
        print "threadName acquired the lock";
 l->Release();
        print "threadName released the lock";
    } 
}

Safety
In this code we make a deadlock occur on purpose. Because two threads can not has the same lock at the same time. Eventually a deadlock it'll occur.

Lock *l2;
Lock *l3;

Rutine1(){
    while(1){
       l2->Acquire();
       l3->Acquire();
       #some critical computation goes here
       l3->Release();
       l2->Release();
    }
}

Rutine2(){
    while(1){
       l3->Acquire();
       l2->Acquire();
       #some critical computation goes here
       l2->Release();
       l3->Release();
    }
}



Don't forget comment.

Jose/Jorge/Richi

7 comments:

  1. Very good men, I like your explant of the problem, I was doing the same implementation using 3 locks is more efficient, but now i don't implement the problem in nachos I'm wanna to try tu use your explant in the test.

    ReplyDelete
  2. Hi!
    Now, I understand your explanation about implementing more of a lock. It seems an efficient solution, just an observation, your solution applies to a limited buffer, so, in the producer function, I think the second condition to check if the buffer has reached its maximum capacity is irrelevant to this case.

    ReplyDelete
  3. I have a question.
    Suppose I am a consumer, At what time I stop of using the CPU?.
    First, I enter in the consumer code and "hasConsumerLock" is false, then I enter in the first condition, I take the lock and now "hasProducerLock" is true.
    The following condition don't apply because the producer hasn't added data to the buffer. So, what next? I loop infinitly until there is something in the buffer? When the producer have time to add data to the buffer? What about my friends? While I don't enter in the critical section (consuming data), they can't enter in the first and second condition, because I never release the first consumer lock and hasConsumerLock never get back to false.
    :S... I'm confused

    ReplyDelete
  4. Abraham.
    Thank's if there's something we can help you well here we are.

    Juan Carlos.
    Yes you're right the second condition is not necessary because we suppose to implement an unbounded buffer, but we decided to implement a bounded buffer (hope has the same value) =)..

    ReplyDelete
  5. +2 presentation in English
    +1 PC (dicen que es unbounded pero implementan bounded)
    +3 three UTs for locks
    -1 font size illegible in slides
    +1 diapositivas en inglés
    => 6 puntos

    ReplyDelete
  6. Juan Carlos.
    Ok I understand the question, I did´t put the Yield() in the psuedocode, my mistake but the currentThread->Yield(), it´s supposed to be just before returning to the while, in the code thats implemented.

    It´s like this:

    while(1){
    if(){
    #some code
    }
    if(){
    #other code
    }
    currentThread->Yield(); #missed line in the code
    }

    ReplyDelete