Coarse-grained synchronization (성긴 동기화)

Coarse-grained linked list (성긴 동기화 리스트)

Source code

class NODE {
public:
    int key;
    NODE *next;

    NODE(int v) {
        key = v;
        next = nullptr;
    }
    NODE() {
        next = nullptr;
    }
};

class CLIST{
private:
    NODE head, tail;
    mutex glock;
public:
    CLIST(){
        head.key = 0x80000000;
        tail.key = 0x7FFFFFFF;
        head.next = &tail;
    }
    void Init(){
        while (head.next != &tail) {
            NODE *temp = head.next;
            head.next = head.next->next;
            delete temp;
        }
    }
    bool Add(int x)
    {
        NODE *pred, *curr;
        pred = &head;
        glock.lock();
        curr = pred->next;
        while (curr->key < x) {
            pred = curr;
            curr = curr->next;
        }

        if (curr->key == x) {
            glock.unlock();
            return false;
        }
        else {
            NODE *node = new NODE(x);
            node->next = curr;
            pred->next = node;
            glock.unlock();
            return true;
        }
    }
    bool Remove(int x)
    {
        NODE *pred, *curr;
        pred = &head;
        glock.lock();
        curr = pred->next;
        while (curr->key < x) {
            pred = curr;
            curr = curr->next;
        }

        if (curr->key == x) {
            pred->next = curr->next;
            delete curr;
            glock.unlock();
            return true;
        }
        else {
            glock.unlock();
            return false;
        }
    }
    bool Contains(int x)
    {
        NODE *pred, *curr;
        pred = &head;
        glock.lock();
        curr = pred->next;
        while (curr->key < x) {
            pred = curr;
            curr = curr->next;
        }

        if (curr->key == x) {
            glock.unlock();
            return true;
        }
        else {
            glock.unlock();
            return false;
        }
    }
};

Execution time of threads

• 1 Threads. 1211msec 
• 2 Threads. 3265msec 
• 4 Threads. 3965msec 
• 8 Threads. 77828msec 
• 16 Threads. 79534msec

Hardware specification

• Intel(R) Core(TM) i5-3570 CPU @ 3.40GHz
• 8.00 GB DDR3