Что быстрее, мелкозернистое или крупнозернистое? - PullRequest
Новая
       105

Что быстрее, мелкозернистое или крупнозернистое?

0 голосов
/ 03 мая 2020

Сейчас я второкурсник, изучающий тему операционной системы. Я хотел бы сравнить мелкозернистую и крупнозернистую реализацию бинарного дерева поиска и использования мьютекса. Блокировка и разблокировка использовались для функции вставки и удаления узла, а время выполнения было напечатано. Я думал, что Fine Grained будет быстрее. Однако, даже если я изменю число, крупнозернистый будет быстрее. Кто-нибудь может объяснить это? Я сделал неправильный код?

Страница результатов

Страница результатов 2 

int lab2_node_insert_fg(lab2_tree *tree, lab2_node *new_node){
if (tree->root == NULL) {
    tree->root = new_node;
    return LAB2_ERROR;
}   
if (search_key(tree,new_node->key)) {
    return LAB2_ERROR;
}   
lab2_node* cur = tree->root;
while (1) {
    if (cur->key < new_node->key) {
        if (cur->right == NULL) {
            pthread_mutex_lock(&lock); // LOCK
            cur->right = new_node;
            pthread_mutex_unlock(&lock); // UNLOCK
            return LAB2_SUCCESS;
        }
        cur = cur->right;
    }
    else {
        if (cur->left == NULL) {
            pthread_mutex_lock(&lock); // LOCK
            cur->left = new_node;
            pthread_mutex_unlock(&lock); // UNLOCK
            return LAB2_SUCCESS;
        }
        cur = cur->left;
    }
}

} 

int lab2_node_insert_cg(lab2_tree *tree, lab2_node *new_node){
pthread_mutex_lock(&lock); // LOCK
if (tree->root == NULL) {
    tree->root = new_node;
    pthread_mutex_unlock(&lock); // UNLOCK
    return LAB2_ERROR;
}   
if (search_key(tree,new_node->key)) {
    pthread_mutex_unlock(&lock); // UNLOCK
    return LAB2_ERROR;
}   
lab2_node* cur = tree->root;
while (1) {
    if (cur->key < new_node->key) {
        if (cur->right == NULL) {
            cur->right = new_node;
            pthread_mutex_unlock(&lock); // UNLOCK
            return LAB2_SUCCESS;
        }
        cur = cur->right;
    }
    else {
        if (cur->left == NULL) {
            cur->left = new_node;
            pthread_mutex_unlock(&lock); // UNLOCK
            return LAB2_SUCCESS;
        }
        cur = cur->left;
    }
}

}

1 Ответ

0 голосов
/ 12 мая 2020

Я предполагаю, что первый фрагмент должен представлять собой детализированную версию, а другой - грубую версию.

В "мелкозернистой" версии отсутствует блокировка для создания root узел. Кроме того, вы удерживаете блокировку для назначения нового узла, вы не делаете этого для условия. Пока вы выполняете итерацию дерева, блокировка узла за раз недостаточна при наличии одновременных удалений. Все это проблемы параллелизма.

Обычно разница между мелкозернистой и крупнозернистой блокировкой - это не «размер» ваших секций блокировки (количество кода, которое вы закрываете блокировкой), это относится к детализации блокировки по отношению к самой структуре данных.

Итак, один из подходов заключается в том, чтобы иметь единую блокировку для всего дерева - грубую блокировку. Другой подход заключается во введении блокировок на более низких уровнях (например, для каждого узла), чтобы устранить конфликт блокировок, если две параллельные операции выполняются на разных узлах дерева. Это похоже на разницу между блокировками таблиц и блокировками на уровне строк в пространстве базы данных.

Один из подходов для детальной версии состоит в том, чтобы иметь блокировку для каждого узла и использовать так называемую ручную передачу ручная блокировка. Для операции вставки вам нужно будет заблокировать текущий узел, пока вы не определите и не заблокируете следующий узел при спуске.

Проведите дополнительное исследование, измените свою реализацию соответствующим образом и повторите тест.

Обычно говоря точнее, мелкозернистая блокировка может привести к более масштабируемой реализации, если шаблон доступа имеет тенденцию поражать различные блокировки. Если это не так в большинстве случаев, то крупнозернистая версия может работать так же хорошо или немного лучше, потому что единственная блокировка может удерживаться на протяжении всей операции, а не требовать получения разных блокировок, при этом большинство из них снова приводит к конфликту блокировок. Как всегда, это зависит от фактического шаблона использования.

...