Модераторы: Daevaorn

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Массив клиентов 
:(
    Опции темы
REZiaMIX
Дата 25.8.2010, 09:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 346
Регистрация: 3.11.2007

Репутация: нет
Всего: 4
Исходя из старой моей темы:
Код

http://forum.vingrad.ru/forum/topic-280440.html

Положение дел:
Есть массив элементов(кол-во от 0 до 20000).
Необходимо организовать потокобезопасные операции с этим массивом:
Код

size_t size();
objectType operator[](size_t indx);
void push_back(objectType obj);
bool erase(size_t indx);


Хочу такой класс:
Код

template <typename objT>
class SafeArray
{
....
};


Какие стратегии применять при синхронизации? Начал писать такой класс на основе std::vector и наткнулся на следующие траблы:
  • При доступе к элементам необходимо блокировать весь вектор
  • При вызове size() необходимо также блокировать весь вектор.
  • Попытка синхронизировать участки массива несколькими крит. секциями обломалась - вызов size() требует блокировки всего вектора.
Требования к классу у меня такие:
  • Хорошая скорость при доступе к случайному элементу
  • Хорошая скорость при вставке элемента в конец(push_back) и удалении элемента(erase)
  • Операции size push_back и erase не должны блокировать весь массив
Подскажите как такое сделать ? Данный класс будет использоваться в сетевом приложении как массив клиентов.

Добавлено через 6 минут и 5 секунд
+ доступ возможен из нескольких потоков


--------------------
user posted image
PM MAIL   Вверх
boostcoder
Дата 25.8.2010, 10:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110
тебе нужно разграничение блокировки. гугли RW-lock.


--------------------
компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW
PM WWW   Вверх
REZiaMIX
Дата 25.8.2010, 10:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 346
Регистрация: 3.11.2007

Репутация: нет
Всего: 4
Цитата(boostcoder @ 25.8.2010,  10:06)
тебе нужно разграничение блокировки. гугли RW-lock.

Почитал, как понял при такой блокировке может быть только 1 writer, или не так?. У меня же врайтеров может быть много.


--------------------
user posted image
PM MAIL   Вверх
boostcoder
Дата 25.8.2010, 10:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110
нет. writer`ов может быть несколько, но для твоего случая это не подходит. посему, один writer и много reader`ов. это лучше чем один reader-writer.


--------------------
компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW
PM WWW   Вверх
REZiaMIX
Дата 25.8.2010, 11:00 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 346
Регистрация: 3.11.2007

Репутация: нет
Всего: 4
Цитата(boostcoder @ 25.8.2010,  10:27)
нет. writer`ов может быть несколько, но для твоего случая это не подходит. посему, один writer и много reader`ов. это лучше чем один reader-writer.

а почему для меня не подходит много врайтеров?


--------------------
user posted image
PM MAIL   Вверх
djamshud
Дата 25.8.2010, 11:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Пердупержденный
***


Профиль
Группа: Завсегдатай
Сообщений: 1655
Регистрация: 23.11.2009

Репутация: 8
Всего: 39
REZiaMIX, используйте список или chain vector, что даже лучше. Пока пишите в одно место, блокируете только модифицируемый вектор (во втором случае) или только нынешний и соседние элементы (в первом). Аналогично с удалением. Доступ к size делайте в один поток для записи и много потоков для чтения.

Случайный доступ к элементам будет медленный, но если оптимизировать алгоритм доступа к элементу, то скорость последовательного будет лишь немного уступать обычному vector-у.

Добавлено через 2 минуты и 26 секунд
chain vector - это нечто вроде списка небольших векторов.


--------------------
'Cuz I never walk away from what I know is right
Alice Cooper - Freedom
PM   Вверх
REZiaMIX
Дата 25.8.2010, 11:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 346
Регистрация: 3.11.2007

Репутация: нет
Всего: 4
Цитата(djamshud @ 25.8.2010,  11:18)
REZiaMIX, используйте список или chain vector, что даже лучше. Пока пишите в одно место, блокируете только модифицируемый вектор (во втором случае) или только нынешний и соседние элементы (в первом). Аналогично с удалением. Доступ к size делайте в один поток для записи и много потоков для чтения.

Случайный доступ к элементам будет медленный, но если оптимизировать алгоритм доступа к элементу, то скорость последовательного будет лишь немного уступать обычному vector-у.

Добавлено @ 11:21
chain vector - это нечто вроде списка небольших векторов.

Сам только что сидел думал, и придумал также)


--------------------
user posted image
PM MAIL   Вверх
REZiaMIX
Дата 27.8.2010, 11:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 346
Регистрация: 3.11.2007

Репутация: нет
Всего: 4
Написал на коленке класс "кусок того самого chain vector". Словил дедлок, помогите найти ошибку в синхронизации.
.h
Код

class SafeItemBase
    {
    protected:
        SafeArrayPart * myParent;
        criticalSection itemLock;
        size_t refCount;
        bool deletePending;
    public:
        void ref();
        bool unref();
        SafeItemBase();
        ~SafeItemBase();
        bool requestDelete();
    };

class SafeArrayPart
    {
    private:
        typedef std::vector<SafeItemBase *> array_t;
        
        array_t itemList;
        criticalSection arrayLock;
    public:
        size_t size();
        size_t push_back(SafeArrayPart * item);
        SafeArrayPart * sget(size_t indx);
        bool sret(SafeArrayPart * item);
        void erase(size_t indx);
        bool eraseByPtr(SafeArrayPart * item);
        SafeArrayPart();
        ~SafeArrayPart();
    };

.cpp
Код

void SafeItemBase::ref()
    {
        scopeLock slock(&itemLock);
        ++refCount;
        //printf("[ref]My ref = %i\n",refCount);
    }
    bool SafeItemBase::unref()
    {
        scopeLock slock(&itemLock);
        --refCount;
        //printf("[unref]My ref = %i\n",refCount);
        if (!refCount && deletePending)
        {
            myParent->eraseByPtr(this);
            return true;
        }
        return false;
    }
    SafeItemBase::SafeItemBase()
    {
        refCount = 0;
        deletePending = false;
    }
    SafeItemBase::~SafeItemBase()
    {
        
    }
    bool SafeItemBase::requestDelete()
    {
        scopeLock slock(&itemLock);
        //printf("[requestDelete]My ref = %i\n",refCount);
        if(refCount)
            deletePending = true;
        else
        {
            myParent->eraseByPtr(this);
            return true;
        }
        //printf("delete pending: %i ref count\n",refCount);
        return false;
        
    }

size_t SafeArrayPart::size()
    {
        scopeLock slock(&arrayLock);
        return itemList.size();
    }
    size_t SafeArrayPart::push_back(SafeItemBase * item)
    {
        scopeLock slock(&arrayLock);
        itemList.push_back(item);
        return itemList.size();
    }
    
    SafeItemBase * SafeArrayPart::sget(size_t indx)
    {
        scopeLock slock(&arrayLock);
        if(indx > itemList.size())
        {
            printf("Invalid index: %i\n", indx);
            return itemList[0];
        }
        SafeItemBase * item = itemList[indx];
        item->ref();
        return item;
    }
    bool SafeArrayPart::sret(SafeItemBase * item)
    {
        return item->unref();
    }
    
    void SafeArrayPart::erase(size_t indx)
    {
        scopeLock slock(&arrayLock);
        itemList.erase(itemList.begin() + indx);
    }
    
    bool SafeArrayPart::eraseByPtr(SafeItemBase * item)
    {
        scopeLock slock(&arrayLock);
        array_t::iterator it;
        it = std::find(itemList.begin(),itemList.end(),item);
        if(it == itemList.end())
            return false;

        itemList.erase(it);
        return true;
    }

    SafeArrayPart::SafeArrayPart()
    {
    }
    
    jeSafeArrayPart::~jeSafeArrayPart()
    {
    }





--------------------
user posted image
PM MAIL   Вверх
xvr
Дата 27.8.2010, 11:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 60
Всего: 223
Ошибок не видно. Где возникает дедлок?
PM MAIL   Вверх
REZiaMIX
Дата 27.8.2010, 11:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 346
Регистрация: 3.11.2007

Репутация: нет
Всего: 4
Цитата(xvr @ 27.8.2010,  11:52)
Ошибок не видно. Где возникает дедлок?

Щас начал глубоко разбираться - ошибки есть.
Дедлок при вызове size();


--------------------
user posted image
PM MAIL   Вверх
djamshud
Дата 27.8.2010, 12:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Пердупержденный
***


Профиль
Группа: Завсегдатай
Сообщений: 1655
Регистрация: 23.11.2009

Репутация: 8
Всего: 39
Хз, как у вас организован scopeLock, но предположу, что вызывается size() из уже залоченной области, что и дедлочит программу.

Добавлено через 1 минуту и 3 секунды
Вероятно вы используете мутексы. Тут намного лучше использовать семафоры.


--------------------
'Cuz I never walk away from what I know is right
Alice Cooper - Freedom
PM   Вверх
REZiaMIX
Дата 27.8.2010, 12:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 346
Регистрация: 3.11.2007

Репутация: нет
Всего: 4
Цитата(djamshud @ 27.8.2010,  12:15)
Хз, как у вас организован scopeLock, но предположу, что вызывается size() из уже залоченной области, что и дедлочит программу.

Добавлено @ 12:16
Вероятно вы используете мутексы. Тут намного лучше использовать семафоры.

Это я уже обнаружил, но там еще куча граблей. Уже запутался.
Я эмулирую крит. секции через мьютексы


--------------------
user posted image
PM MAIL   Вверх
REZiaMIX
Дата 27.8.2010, 14:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 346
Регистрация: 3.11.2007

Репутация: нет
Всего: 4
Цитата(djamshud @ 27.8.2010,  12:15)
Хз, как у вас организован scopeLock,

scopeLock:
Код

class scopeLock
{
protected:
    criticalSection * mySection;
public:
    scopeLock(criticalSection * _section)
    {
        mySection = _section;
        mySection->enter();
        //printf("scopelocked\n");
    }
    ~scopeLock()
    {
        mySection->leave();
        //printf("scopeunlocked\n");
    }
};



--------------------
user posted image
PM MAIL   Вверх
REZiaMIX
Дата 27.8.2010, 14:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 346
Регистрация: 3.11.2007

Репутация: нет
Всего: 4
Очень тяжелая для головы задача. Дебажить трудно - в 1ном потоке все нормально, при нескольких ошибки(то дедлок, то наоборот магическим образом получаю доступ к уже заюзанному элементу).
 smile  smile 


--------------------
user posted image
PM MAIL   Вверх
djamshud
Дата 27.8.2010, 15:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Пердупержденный
***


Профиль
Группа: Завсегдатай
Сообщений: 1655
Регистрация: 23.11.2009

Репутация: 8
Всего: 39
Just use semaphore, Luke!

Добавлено через 2 минуты и 9 секунд
Потому что мутексы тут не очень подходят, имхо.

Добавлено через 2 минуты и 51 секунду
Хотя согласен, после однопоточного программирования мозг не сразу переключается в параллелизм.


--------------------
'Cuz I never walk away from what I know is right
Alice Cooper - Freedom
PM   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0642 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.