Потокобезопасный кэш

[brankovic]

А для мьютекса замер?

[Igors]

А для мьютекса замер?

Если имеется ввиду реализация на pthread_cond_wait (как в Qt) - то незачем терять время на ее проверку

[brankovic]

Имеется ввиду QMutex, который контролирует доступ к кэшу. И времени для замены спинлока на мьютекс нужно немного. Но если незачем то тогда ладно.

[Igors]

Вот уж и не знаю как быть: вижу что это никому не интересно и не хочу навязываться. Но я обещал отписаться когда сделаю, поэтому вот псевдокод

Код

C++ (Qt)
struct CPageHead {
 CPageData * AcquireRead( void );
 void * ReleaseRead( void )  { mMutex.unlock(); }
 
 CPageData * mData;
 atomic <UInt32> mAccessCount;
 spin_rw_mutex mMutex;
 
 static atomic <UInt32> mAccessTotal;
 static spin_mutex mLoadMutex;
};
 
CPageData * CPageHead::AcquireRead( void )
{
 mMutex.lock_read();    
 
// здесь mData может быть загружена или нет, но не может быть выгружена
 
  if (!mData) {                                                     // не загружена
   spin_mutex::scoped_lock theLock(mLoadMutex);    // берем лок
   if (!mData) {                         // др. нитка успела подгрузить?
//    UInt32_64 * dummy = (UInt32_64 *) &mMutex;  // неверно! (предыдущий вариант)
       atomic <UInt32_64> * dummy = (atomic <UInt32_64> *) &mMutex;  
       *dummy += WRITE_PENDING;             // блокируем доступ по чтению во время LoadPage           
       LoadPage();                      // грузим апельсины бочками
       *dummy -= WRITE_PENDING;     // mData готово, можно читать
    }
  }
 
// обновляем статистику
  mAccessCount = ++mAccessTotal;
  return mData;
}
 

LoadPage сводится к нахождению кандидата на вытеснение, захвату его "по записи", сбросу его на диск и перелинковке списка. Ищу линейным поиском по списку, беру первый элемент для которого выполняется условие mAccessCount < mAccessTotal / 4. Прикидывал более оптимальный поиск но ничего путного не придумал.

[brankovic]

Вот уж и не знаю как быть: вижу что это никому не интересно и не хочу навязываться. Но я обещал отписаться когда сделаю, поэтому вот псевдокод

Отнюдь, как время будет почитаю с интересом. Хорошо, что отписались -- обещания надо выполнять

[Waryable]

Вот уж и не знаю как быть: вижу что это никому не интересно и не хочу навязываться. Но я обещал отписаться когда сделаю, поэтому вот псевдокод

Отнють. Очень интересно. Но мне для нормального прочтения этого псевдокода надо подтянуть свои знания. Как смогу, так и оценю. 

[brankovic]

   *dumy |= WRITE_PENDING;                              // коряво но без этого не обойтись
    LoadPage();                                                   // грузим апельсины бочками
    *dumy &= ~WRITE_PENDING;

Igors, нельзя ли кратко пояснить магию WRITE_PENDING? Почему не mMutes.write_lock ()?

[Igors]

   *dumy |= WRITE_PENDING;                              // коряво но без этого не обойтись
    LoadPage();                                                   // грузим апельсины бочками
    *dumy &= ~WRITE_PENDING;

Igors, нельзя ли кратко пояснить магию WRITE_PENDING? Почему не mMutes.write_lock ()?

Для LoadPage нам нужно захватить страницу "по записи" (т.е. exclusive) но mMutes.write_lock здесь ведет к deadlock - ведь мы уже захватили ее "по чтению" (shared)

[brankovic]

Кажется понял: если бы у spin_rw_mutex была операция upgrade_read_lock_to_write_lock (), то её вызов потенциально может привести к дэдлоку (поправьте, если неверно).

Под *dumy |= WRITE_PENDING подразумевается атомарная операция, правильно я понимаю? Потому что иначе не будет работать.

Кода про вытеснение страницы вообще нет, а он тут важен. Собственно от его реализации зависит, насколько верен этот код.

Как осуществляется поиск "самой старой страницы" при вытеснении, перебором по всем страницам?

[Igors]

Кажется понял: если бы у spin_rw_mutex была операция upgrade_read_lock_to_write_lock (), то её вызов потенциально может привести к дэдлоку (поправьте, если неверно).

В принципе верно. Как только LoadPage поставит ненулевое mData, др. нитка может ее "подхватить" (и рухнуть).

Под *dumy |= WRITE_PENDING подразумевается атомарная операция, правильно я понимаю? Потому что иначе не будет работать.

Необязательно. Пока LoadPage страницу не загрузила - мы защищены

Кода про вытеснение страницы вообще нет, а он тут важен. Собственно от его реализации зависит, насколько верен этот код.

Как осуществляется поиск "самой старой страницы" при вытеснении, перебором по всем страницам?

Там нiчого особливого. Поиск линейным проходом по списку, выбирается первая страница у которой

mAccessCount <= mAccessTotal / 4;

Она захватывается "по записи". Загружаемая перемещается в голову списка (как обычно в LRU). Во время выгрузки/подгрузки чтение др. страниц не блокируется (чем я весьма доволен).

[brankovic]

Под *dumy |= WRITE_PENDING подразумевается атомарная операция, правильно я понимаю? Потому что иначе не будет работать.

Необязательно. Пока LoadPage страницу не загрузила - мы защищены

Я конечно понимаю, что это псевдокод, но всё-таки тут неясный момент. spinlock_mutex это обёртка вокруг atomic_int? В таком случае операция |= попортит всю атомарность. Можно в общих чертах схему работы spinlock_mutex?

[Igors]

Я конечно понимаю, что это псевдокод, но всё-таки тут неясный момент. spinlock_mutex это обёртка вокруг atomic_int? В таком случае операция |= попортит всю атомарность. Можно в общих чертах схему работы spinlock_mutex?

Это read/write locker . Член данных один (4/8 байт в 32/64). Флаги

бит 0 - WRITE (locker захвачен exclusive - "по записи")
бит 1 - PENDING (блокирует новый захват по чтению, хотя еще могут быть читающие)
биты 2..32(64) - число читающих

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

[brankovic]

бит 0 - WRITE (locker захвачен exclusive - "по записи")
бит 1 - PENDING (блокирует новый захват по чтению, хотя еще могут быть читающие)
биты 2..32(64) - число читающих

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

Попробую набросать сценарий, вы меня поправьте если что. Пусть имеется 2 треда, А и Б, и пусть события происходят в таком порядке:

1. тред А захватил mMutex на чтение, mMutex == {false, false, 1}
2. тред А проверил, что mData == NULL, выполнил mLoadMutex.lock (), ещё раз проверил mData (всё ещё NULL)
3. тред А собирается сделать mMutex.pending = true и для этого читает mMutex в регистр AR, теперь AR == {false, false, 1}
4. тред А засыпает
5. тред Б захватывает mMutex на чтение, теперь mMutex == {false, false, 2}
6. тред Б засыпает
7. тред А просыпается и делает AR.pending = true, теперь AR == {false, true, 1}, mMutex == {false, false, 2}
8. тред А записывает AR в mMutex, теперь mMutex == {false, true, 1}
9. тред А загружает страницу и снимает write_pending, mMutex == {false, false, 1}
10. тред А отпускает mLoadMutex, и выходит из aquire_read, делает свою полезную работу и вызывает release_read, теперь mMutex == {false, false, 0}

Состояние после пункта 10 таково: мьютекс mMutex не захвачен ни на чтение ни на запись, но Б считает, что захватил мьютекс. Когда Б проснётся, он станет работать со страницей не имея рид-лока. Насколько я понимаю, это вовсе не то, чего хотелось. Правильно я рассуждаю?

[Igors]

Попробую набросать сценарий, вы меня поправьте если что. Пусть имеется 2 треда, А и Б, и пусть событий происходят в таком порядке:

Нечего поправлять, Вы правы, прямая ошибка и, мне кажется это можно показать даже проще

Код

C++ (Qt)
*dummy |= WRITE_PENDING;
 

Это НЕ атомарно и выполняется так

- содержимое *dummy принимается на регистр
- выполняется OR на регистре
- содержимое регистра записывается по адресу dummy

Заметим что объявление volatile (так кстати и было) в данном случае ничего не меняет. Ошибка в том что пока выполняется OR на регистре, ОС может забрать у нитки управление на любое время, в течение которого др. нитка может обновить dummy. Когда  управление вернулось и регистр пишется в память, эти изменения будут утеряны. В общем, классические грабли.

Исправил, спасибо

[brankovic]

В общем, классические грабли.

Собственно такие ошибки сразу видно, нельзя мешать атомарный доступ с обычным. Но это так, придирки, гораздо интереснее вот что: зачем вообще нужно WRITE_PENDING? Почему нельзя так:

Код

C++ (Qt)
Data *acquire ()
{
   m_mutex.lock_read ();
 
   if (!m_data)
   {
      scoped_lock sl (m_load_mutex);
      if (!m_data)
      {
         Data *tmp = LoadPage (); //first load
         m_data = tmp;           //tmp is ready, assign m_data to it
      }
   }
 
   return m_data;
}