Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.82/11: Рейтинг темы: голосов - 11, средняя оценка - 4.82
0 / 0 / 0
Регистрация: 04.12.2016
Сообщений: 1
1

Ранний сброс hazard pointer

04.12.2016, 09:07. Показов 1978. Ответов 2
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Вопрос к господам интересующимся lock-free структурами данных. Разбирал методику hazard pointer у Williams-а в его C++ Concurrency in Action, завис на одном моменте, который мне никак не удаётся осознать. Причём автор метода hazard указателей Maged M. Michael в документе "P0233R0" по этой теме делает принципиально так же. Т.е. ошибки в книге быть не может, я даже errata к книге Williams-а проверил, чисто. Всё это говорит о том, что я что-то не понимаю, мне нужна помощь знатоков, т.е. Вас. Итак, вот ссылка на код из книги.

Вот проблемный кусочек:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
        std::atomic<void*>& hp = get_hazard_pointer_for_current_thread();
        node* old_head = head.load();
 
        do {
            node* temp;
            do {    // Keep looping until you know that the head pointer still has the same value you set your hazard pointer to
                temp = old_head;
                hp.store(old_head);
                old_head = head.load();
            } while (old_head != temp);
        } while (old_head && !head.compare_exchange_strong(old_head, old_head->next));
        hp.store(nullptr);  // Once the object is no longer needed, the hazard pointer is cleared
        
        std::shared_ptr<T> res;
        if (old_head) {
            res.swap(old_head->data);
Так вот. hp это сам hazard pointer, он сбрасывается "hp.store(nullptr)", после чего нода, которую он защищал, и на которую указывает old_head может быть удалена (другим потоком), ниже есть код вида "delete old_head;". Но... мы видим что этот указатель совершенно спокойно разыменовывается в объект, из которого совершенно спокойно вытаскивается data.

Вопрос: прав ли я в том, что это может привести в undefined behavior, и если нет (это безопасно), то почему?

Дополнительно: по коду видно, что и ДО обнуления hazard есть проверка на NULL old_head, и ПОСЛЕ, что как бы говорит "да, после old_head может быть изменён", но... всё равно его спокойно разыменовывают.
Вложения
Тип файла: pdf Hazard Pointers, Safe Resource Reclamation for Optimistic Concurrency [p0233r0].pdf (381.5 Кб, 4 просмотров)
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
04.12.2016, 09:07
Ответы с готовыми решениями:

Shared_ptr - stored pointer, owned pointer
Зачем в shared_ptr нужен хранимый указатель, отличный от владеемого? И так в этом средстве,...

Mac OS X Snow Leopard 10.6.6 Hazard
Mac OS X Snow Leopard 10.6.6 Hazard сейчас стоит windows 7 max конфигурация компьютера...

В Сети появился ранний релиз Windows 8
http://lenta.ru/news/2011/04/26/release/

Ранний вывод исхода условия до ввода данных
Здравствуйте. как убрать надпись else echo &quot;sorry, your date is not correct&quot; ; &lt;?php $name =...

2
 Аватар для Martein
700 / 106 / 20
Регистрация: 22.06.2014
Сообщений: 236
04.12.2016, 11:24 2
Trilobit, далее по тексту этой книги написано следующее: "Заявив свои права на владение указателем, а это означает, что никто другой не имеет права удалять объект, нужно проверить не ссылается ли на этот объект указатели опасности других потоков if(outstanding_hazard_pointers_for(old_head))". Ну и если удалять пока нельзя, то поставить в очередь ожидания на удаление reclaim_later(old_head);, т.к. естественно удалять, пока ссылаются на объект указатели опасности из других потоков, нельзя, а если таких ссылок на этот объект нет, то он просто удаляется стандартным способом delete old_head; и больше о нём никто ничего не знает. То есть тут вопрос о владении объектом. Никто ничего удалить не может пока единственным последним владельцем не останется тот поток, для которого outstanding_hazard_pointers_for(old_head) == false. И вот в нём уже происходит реальное физическое удаление оператором delete.
2
Ушел с форума
Эксперт С++
 Аватар для Убежденный
16478 / 7441 / 1187
Регистрация: 02.05.2013
Сообщений: 11,617
Записей в блоге: 1
04.12.2016, 11:32 3
В данном коде, - насколько я понимаю, мы говорим про "Listing 7.6 An implementation of
pop() using hazard pointers", - hazard pointer сбрасывается строго после того, как
node уже удалена из списка. То есть, другие потоки при выходе из блоков do/while
видят уже другое значение old_head.

Мои комментарии к данному коду:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
//
// Lock-free версия list.pop().
//
std::shared_ptr<T> pop()
{
    //
    // Получаем hazard pointer для текущего потока.
    //
    std::atomic<void*>& hp=get_hazard_pointer_for_current_thread();
    
    //
    // Получаем адрес элемента, который находится в голове списка.
    //
    node* old_head=head.load();
    
    //
    // Здесь нужно атомарно сделать две вещи: во-первых, записать указатель
    // на головной элемент списка в hazard pointer, временно защитив его от
    // удаления, а во-вторых, извлечь этот элемент из списка, передвинув
    // указатель head->next на следующий элемент.
    //
    // Внутренний цикл решает первую проблему, внешний - вторую.
    //
    // Защита от удаления элемента с помощью hazard pointer только для
    // того и нужна, чтобы иметь возможность безопасно выполнить
    // compare_exchange_strong(old_head,old_head->next). Другие потоки по
    // окончанию работы проверяют hazard pointers и делают delete объекту
    // только если на него не осталось ссылок (см. ниже)
    //
    
    do
    {
        node* temp;
        do 
        {
            temp=old_head;
            hp.store(old_head); // Временно запрещаем удаление.
            old_head=head.load();
        } while(old_head!=temp);
    }
    while(old_head &&
        !head.compare_exchange_strong(old_head,old_head->next)); // Пытаемся удалить
                           // элемент из списка.
        
    //
    // Если мы попали сюда, значит, мы достигли следующего:
    // 1. old_head удален из списка и head.load() в другом потоке
    // будет возвращать уже другое значение.
    // 2. hazard pointer все еще удерживает элемент от удаления.
    //
    
    //
    // Удерживать элемент дальше нет смысла, т.к. на него ни у кого
    // не осталось ссылок. Поэтому обнуляем hazard pointer.
    //
    hp.store(nullptr);
    
    //
    // Получаем данные из извлеченного элемента списка.
    //
    
    std::shared_ptr<T> res;
    if(old_head)
    {
        res.swap(old_head->data);
        
        //
        // Неочевидный момент.
        // Другой поток в данное время может находиться внутри циклов do/while и
        // выполнять compare_exchange_strong(old_head,old_head->next) с данным
        // указателем, поэтому сразу вызывать delete не безопасно.
        //
        
        if(outstanding_hazard_pointers_for(old_head)) 
        {
            reclaim_later(old_head); 
        }
        else
        {
            delete old_head; 
        }
        delete_nodes_with_no_hazards(); 
    }
    return res;
}
2
04.12.2016, 11:32
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
04.12.2016, 11:32
Помогаю со студенческими работами здесь

Переписать структуру со стандарта c++11 под более ранний
Господа, помогите разобраться. Есть вот такая структура: struct MedianFilter { unsigned k; ...

Ошибка при компиляции: cannot use uintptr(unsafe.Pointer(sslPara) (type uintptr) as type syscall.Pointer in field value
Добрый день. Помогите, пожалуйста, разобраться с проблемой. При попытке скомпилировать проект...

Найти самый ранний год выпуска трека через API Discogs
Здравствуйте. Я новичок в Python (да и в программировании). Решил изучать, что бы можно было...

Определить по дате, сегодняшний это день, вчерашний или более ранний
Всем привет! Ребят, подскажите, пожалуйста! Есть unix time. После конвертирования получаю дату...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Новые блоги и статьи
[Golang] 121. Best Time to Buy and Sell Stock
alhaos 28.01.2025
В этой задаче мы получаем слайс целых чисел, которые означают цену акции в разные моменты времени, и должны вернуть максимально возможную прибыль от купли продажи акции. / / . . .
Проектирование и моделирование
hw_wired 28.01.2025
Введение в моделирование Моделирование представляет собой один из фундаментальных методов научного познания, который позволяет изучать объекты и явления через создание их упрощенных аналогов. В. . .
Алгоритмы и исполнители
hw_wired 28.01.2025
Введение в алгоритмы В современном мире информационных технологий алгоритмы играют основополагающую роль в решении различных задач и автоматизации процессов. Алгоритм представляет собой точную. . .
Хранение информации
hw_wired 28.01.2025
Введение: Роль систем хранения информации в современном мире В современную эпоху цифровых технологий эффективное хранение информации становится одним из ключевых факторов успешного развития любой. . .
Обработка числовой информации
hw_wired 28.01.2025
Введение в обработку числовой информации В современном мире обработка числовой информации стала неотъемлемой частью как профессиональной деятельности, так и повседневной жизни. Электронные таблицы. . .
Мультимедиа
hw_wired 28.01.2025
Введение в мультимедийные технологии В современном мире мультимедийные технологии стали неотъемлемой частью нашей жизни, проникнув во все сферы человеческой деятельности. Термин "мультимедиа". . .
Обработка текстовой информации
hw_wired 28.01.2025
Введение в обработку текстовой информации В современном мире обработка текстовой информации играет фундаментальную роль в различных сферах человеческой деятельности. Текстовые редакторы стали. . .
Обработка графической информации
hw_wired 28.01.2025
Введение в компьютерную графику Компьютерная графика стала неотъемлемой частью современного цифрового мира, пройдя впечатляющий путь развития от простейших черно-белых изображений до сложных. . .
Python в Алгоритмике: Решение задач
hw_wired 28.01.2025
Введение в Python и Алгоритмику В современном мире программирование стало неотъемлемой частью образования и профессионального развития. Python зарекомендовал себя как один из самых популярных и. . .
Компьютер как универсальное устройство для работы с информацией
hw_wired 28.01.2025
Введение в устройство компьютера Компьютер представляет собой универсальное электронное устройство, предназначенное для автоматической обработки информации. В современном мире компьютер стал. . .
Информация и информационные процессы
hw_wired 28.01.2025
Понятие информации и ее виды В современном мире информация является одним из фундаментальных понятий, пронизывающих все сферы человеческой деятельности. Под информацией понимают любые сведения об. . .
Алгоритмика
hw_wired 28.01.2025
Введение: Основы алгоритмики и её роль в информатике В современном мире программирование и алгоритмическое мышление стали неотъемлемой частью образования и профессиональной деятельности. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru