LINUX.ORG.RU

Царям Си. Задача на синхронизацию.

 ,


1

3

Есть два типа объектов: A и B.

Объекты A выступают в качестве weak pointer. Объект типа A может указывать на объект типа B, а может никуда не указывать (NULL).

Объекты типа B хранят своё название (строка) и произвольные данные и имеют два состояния: не готов или готов. Если объект в состоянии готов, данные можно читать. Если объект в состоянии не готов, данные еще не вычислены.
Каждый объект типа B также хранит список объектов типа A, которые на него ссылаются.

Вся совокупность объектов B образует кэш. Имеется менеджер кэша, который хранит список всех объектов B. В произвольный момент времени менеджер кэша может удалить произвольное число объектов B, если сочтёт, что их «слишком много». Все объекты A, которые содержали указатель на удаленный объект, начинают содержать NULL.

Имеются сервисные потоки, которые подготавливают данные для объектов B и управляют кэшем.
Имеются потоки-клиенты, которые в стеке хранят _указатели_ на объекты A. (Один объект A может быть доступен нескольким потокам.)

Возможны следующие операции:

Для клиентских потоков:

void schedule_A(A *a, char * key);
Если объект B с ключём key имеется в кэше, ссылка на него будет помещена в A.
Если объекта нет в кэше, он будет создан, и ссылка на него будет помещена в A.
Объект B может быть в любом состоянии и изменить состояние с не готов на готов в любой момент времени.

data_t deref_A(A *a);
Если объект A не ссылается ни на один объект B, возвращает специальное значение NONE.
Если объект A ссылается на объект B, и данные в объекте B готовы, возвращает данные.
Если объект A ссылается на объект B, но данные в объекте B не готовы, текущий поток засыпает, пока не произойдёт одно из двух событий:
* Данные станут готовы. (Возвращает данные.)
* Объект A перестаёт ссылаться на какой-либо объект B (начинает ссылаться на NULL). (Возвращает NONE.)

Для сервисных потоков:

B * acquire_by_key_B(char * key);
Ищет объект в кэше и захватывает мьютекст на доступ к нему. (В общем случае возможны разные варианты функций выборки: acquire_oldest_B, acquire_oldest_not_ready_B и т.п.)

void validate_B(B *b);
Отмечает объект как готовый.

void drop_B(B *b);
Отмечает объект как удалённый.

void release_B(B * b);
Освобождает мьютекс на доступ к объекту.
Если объект отмечен как готовый, все клиентские потоки, которые ждали готовности объекта внутри функции deref_A(), просыпаются и возвращают значение.
Если объект отмечен как удалённый, все клиентские потоки, которые ждали готовности объекта внутри функции deref_A(), просыпаются и возвращают NONE, а занятая объектом память освобождается.
Если объект отмечен и как готовый, и как удалённый, флаг удаленный имеет приоритет. (Т.е. клиенты получают NONE.)

Задача:

Придумать алгоритм для указаного выше API, не содержащий race condition. В функциях deref_A(), validate_B(), drop_B() и release_B() алгоритм должен работать с per-object блокировками. То есть, если потоки оперируют непересекающимися наборами объектов, они не должны тормозить друг друга на точках синхронизации. (За исключением логики освобождения памяти внутри release_B(), где возможен глобальный мьютекс на куче.)

Deleted

Из всего мусора понял, что у автора проблема с архитектурой.

anonymous ()
Ответ на: комментарий от crowbar

Банальщина же.

Ну расскажи тогда, а то я не могу сообразить.

Чтобы избежать взаимоблокировки, нам нужен предсказуемый порядок захвата мьютексов.

У клиентского потока есть только указатель на A. Когда клиентский поток вызывает deref_A(a), то порядок мьютексов будет:

lock(a->mutex);
if (a->b) {
   lock(a->b->mutex);
   // проверяем b...
}
// ....

А из сервисного потока порядок захвата будет обратный. У него есть только указатель на B.

Deleted ()

Звучит как тестовое задание. Коли так, то, будь добр, делай его сам.

Hater ★★ ()
Ответ на: комментарий от Hater

Звучит как тестовое задание. Коли так, то, будь добр, делай его сам.

Нет. Возникла такая задача в pet project. Вернее, это её довольно упрощенная формализация.

Deleted ()

Я за собой заметил, что, когда встают замысловатые проблемы синхронизации, истинное решение проблемы — пересмотр архитектуры. Так как мне лень читать все, да и не Царь вовсе, я не могу оценить насколько твои проблемы замысловаты. Но все же попробуй взглянуть на задачу критично и придумать кэш по-проще.

staseg ★★★★★ ()
Ответ на: комментарий от Deleted

А из сервисного потока порядок захвата будет обратный

Почему обратный, если у него только указатель на B? deref ведь перед ожиданием освобождает мьютекс? Если нет, то нужно освобождать и ждать сигнала от сервисного потока (в java через wait/notify, не знаю что там в pthread есть).

crowbar ()
Ответ на: комментарий от crowbar

ведь перед ожиданием освобождает мьютекс?

Блорировка будет раньше.

Перед тем, как хотя бы прочитать указатель на очередь ожидания (или на кондвар, семафор, не суть, чем у нас оно будет реализовано), поток 1 должен захватить два мьютекса:

Раз - захватываем мютекст a->mutex.
Читаем указатель a->b.
Два - захватываем мьютекст a->b->mutex.
Читаем a->b->queue и встаём в очередь (освобождая оба мьютекса).

Если в это время сервисный поток 2 выполняет удаление объекта, происходит следующее. Он уже держит мюьтекс b->mutex. Он пытается прочитать список ссылающихся объектов A и сделать для каждого присвоение a->b = NULL. Для этого он должен для каждого A захватить мюьтекс. Имеет место deadlock: поток 1 держит a->mutex и ждёт b->mutex, а поток 2 держит b->mutex и ждёт a->mutex.

Deleted ()

Придумать алгоритм для указаного выше API, не содержащий race condition

лучше придумай API, чтобы алгоритмы не имели таких проблем

MyTrooName ★★★★★ ()
Ответ на: комментарий от MyTrooName

лучше придумай API, чтобы алгоритмы не имели таких проблем

Задача от этого сама себя не решит. Тут задача первична, а не API.

Deleted ()
Ответ на: комментарий от Deleted

Он пытается прочитать список ссылающихся объектов A и сделать для каждого присвоение a->b = NULL

Читаем список, освобождаем мьютекс b->mutex, захватываем a->mutex, делаем присвоение.

crowbar ()
Ответ на: комментарий от crowbar

Читаем список, освобождаем мьютекс b->mutex, захватываем a->mutex, делаем присвоение.

Race condition. Как только мы отпустили b->mutex, клиентский поток может выполнить удаление объекта a.

Deleted ()

Видимо нужен lock-free контейнер для объектов В. Об этом уже много написано

four_str_sam ()

Re: Царям Си

Я знал, что у царя шизофрения.

Pavval ★★★★★ ()
Ответ на: комментарий от staseg

Я за собой заметил, что, когда встают замысловатые проблемы синхронизации, истинное решение проблемы — пересмотр архитектуры.

Именно. Если сложно удержать решение в голове, то поддерживать и изменять код потом будет сложно - высока вероятность внесения рейсов, дедлоков и т.п.

Pavval ★★★★★ ()

Подышал свежим воздухом, вроде дошло.

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

deref_A() пытается захватить оба объекта в цикле. Если данные не готовы, ставит себя в очередь, снимает локи и ждёт.

acquire_B() атомарно достаёт объект из списка кэша, таким образом, на объект B может быть ссылаться не более одного сервисного потока (остальные его просто не увидят в кэше).

release_B() при чистке указателей пытается захватить объекты в цикле, пока не получится. Затем отправляет уведомления потокам в очереди и возвращает объект в список кэша (если объект не удалён).

Такой вот псевдокод набросал:

Клиентская функция:

data_t deref_A(A *a)
{
	volatile B * b;

again:
	LOCK(a->slock);

	b = a->b;
	if (!b) {
		UNLOCK(a->slock);
		return NONE;
	}

	if (!TRY_LOCK(b->slock)) {
		UNLOCK(a->slock);
		goto again;
	}

	if (b->state == VALID) {
		data_t data = b->data;
		UNLOCK(b->slock);
		UNLOCK(a->slock);
		return data;
	}

	queue_push(b->wait_queue, my_fd());
	UNLOCK(b->slock);
	UNLOCK(a->slock);
	wait_fd(my_fd());
	goto again;
}

Сервисные функции:

B * acquire_чего_то_там_B(бла бла) {
	MUTEX_LOCK(cache_mutex);
	B * b = find_matching(бла);
	if (!b)
		goto end;

	LOCK(b->slock);
	remove_from_cache_list(b);
	UNLOCK(b->slock);

end:
	MUTEX_UNLOCK(cache_mutex);
	return b;
}

void validate_B(B *b) {
	if (b->new_state != STATE_DROPPED)
		b->new_state = STATE_VALID;
}

void drop_B(B *b) {
	b->new_state = STATE_DROPPED;
}

void release_B(B *b) {

	if (b->new_state == STATE_DROPPED) {
again_1:
		LOCK(b->slock);

		while (!queue_empty(b->ref_queue)) {
			A * a = queue_get_head(b->ref_queue);
			if (!TRY_LOCK(a->slock)) {
				UNLOCK(b->slock);
				goto again_1;
			}
			a->b = NULL;
			queue_pop_head(b->ref_queue);
			UNLOCK(a->slock);
		}

		while (!queue_empty(b->wait_queue)) {
			sendmsg_fd(queue_pop_head(b->ref_queue));
		}

		deref_B(b);

		UNLOCK(b->slock);

		return;

	}


	LOCK(b->slock);
	if (b->new_state == STATE_VALID) {
		b->state = b->new_state;

		while (!queue_empty(b->wait_queue)) {
			sendmsg_fd(queue_pop_head(b->ref_queue));
		}

	}
	UNLOCK(b->slock);

	MUTEX_LOCK(cache_mutex);
	LOCK(b->slock);
	put_to_cache_list(b);
	UNLOCK(b->slock);
	MUTEX_UNLOCK(cache_mutex);

}

Deleted ()
Ответ на: Re: Царям Си от Pavval

Я знал, что у царя шизофрения.

Ни одного царя в треде так и не появилось. :(

Deleted ()
Ответ на: комментарий от Pavval

Оппа. А подробнее?)

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

anonymous ()
Ответ на: комментарий от Deleted

Ни одного царя в треде так и не появилось. :(

Когда он появится, ты будешь скучать по тем светлым временам, когда его не было, и будешь сожалеть о том, что его звали.

Pavval ★★★★★ ()
Ответ на: комментарий от Deleted

Подышал свежим воздухом, вроде дошло.

Можно же не хранить в B списки ссылающихся на него объектов A. Достаточно хранить количество таких ссылок. И не удалять объект B до тех пор, пока на него есть ссылки из A. Даже если B изымается из кэша.

С объектом B связан mutex и condition, у B есть состояние и счетчик ссылок из объектов A.

void schedule_A(A *a, char * key);

Захватываешь mutex кэша. Ищешь или создаешь B. Захватываешь его mutex, инкрементируешь счетчик ссылок. Освобождаешь mutex B, освобождаешь mutex кэша.

data_t deref_A(A *a);

В A должна быть ссылка на B, полученная внутри schedule_A. Захватываешь mutex B. Проверяешь состояние B. Если B помечен как удаленный, то декрементируешь количество ссылок. Если счетчик ссылок обнулился, то освобождаешь mutex B, удаляешь B. Если не обнулился, то просто освобождаешь mutex B.

Если B не удален:

- если данные готовы, то освобождаешь mutex B, возвращаешь data_t;

- иначе засыпаешь на condition B. После пробуждение возвращаешься к проверке состояния B.

B * acquire_by_key_B(char * key);

Вроде ничего сложного, все делается под захваченным сначала mutex кэша.

void validate_B(B *b);

Захватываешь mutex B, помечаешь как готовый, взводишь condition B, освобождаешь mutex B.

void drop_B(B *b);

Захватываешь mutex кэша. Захватываешь mutex B. Вычеркиваешь B из кэша. Выставляешь состояние «удален». Если есть ссылки, то взводишь condition B (в режиме notify_all), освобождаешь mutex B (объект будет удален из объектов A). Если ссылок нет, то просто освобождаешь mutex B, удаляешь B. Перед выходом из drop_B освобождаешь mutex кэша.

Тут получается, что либо mutex B захватывается из под уже захваченного mutex кэша. Либо же захват mutex кэша вообще не нужен.

В принципе, можно счетчики ссылок на B делать атомарными, а вместо mutex B/condition B использовать какой-то велосипед на спинлоках. Но имело бы смысл сначала сделать простой вариант на mutex/condition и провести замеры. Если производительности не будет хватать, то искать дальше.

PS. Алгоритм предложен сходу, так что косяки в нем наверняка есть. Но и постановка задачи довольно размытая и странная.

eao197 ★★★★★ ()
Ответ на: комментарий от eao197

Можно же не хранить в B списки ссылающихся на него объектов A. Достаточно хранить количество таких ссылок. И не удалять объект B до тех пор, пока на него есть ссылки из A. Даже если B изымается из кэша.

Да, с этим условием всё проще. Но в полной версии задачи, с которой я тут вожусь, как раз это нельзя. Подсистема, стоящая за объектами B, должна иметь возможность в произвольный момент времени (читай: при нехватке ресурсов) потребовать пометить все ссылки на отбираемый объект как битые.

Если использовать отложенное освобождение ресурсов, — клиент может вообще никогда не вызвать deref_A() и не освободить ресурсы.

Deleted ()
Ответ на: комментарий от Deleted

Если использовать отложенное освобождение ресурсов, — клиент может вообще никогда не вызвать deref_A() и не освободить ресурсы.

А кто тогда будет удалять объекты A?

eao197 ★★★★★ ()
Ответ на: комментарий от eao197

Если использовать отложенное освобождение ресурсов, — клиент может вообще никогда не вызвать deref_A() и не освободить ресурсы.

А кто тогда будет удалять объекты A?

Я к тому, что объекты A кто-то же должен удалять. Соответственно, объект B можно разбить на две части: proxy (в которой будет состояние, счетчик ссылок, mutex и condition, указатель на data) и data. Объекты A будут ссылаться на B_proxy, откуда будет ссылка на B_data.

Когда объект B не нужен, в B_proxy ссылка на B_data зануляется. Сам B_data уничтожается. А оставшийся B_proxy будет жить столько же, сколько и ссылающиеся на него объекты A.

eao197 ★★★★★ ()
Ответ на: комментарий от eao197

А кто тогда будет удалять объекты A?

В общем случае они все удаляются при смерти клиента.

Но пока клиент жив, их может вообще никто не удалить. Клиент может зависнуть в бесконечном цикле, уснуть навечно в select() и т.п. Клиент — недоверенная сторона. Поэтому ресурсы отбираются у него принудительно.

Объекты A — дешевые по расходу памяти (по сути это просто 32-битные индексы), а B — дорогие.

Deleted ()
Ответ на: комментарий от eao197

Когда объект B не нужен, в B_proxy ссылка на B_data зануляется.

Да, ввести дополнительные уровень индиректности я обдумывал. Но идея с активным ожиданием на быстрых спинлоках мне пока нравится больше.

Deleted ()
Ответ на: комментарий от Deleted

В общем случае они все удаляются при смерти клиента.

Но пока клиент жив, их может вообще никто не удалить. Клиент может зависнуть в бесконечном цикле, уснуть навечно в select() и т.п. Клиент — недоверенная сторона. Поэтому ресурсы отбираются у него принудительно.

Стоп, причем здесь клиенты?

Объекты A и B уже у тебя существуют внутри одного процесса, правильно? В разных нитях, каждая из которых может завершиться не предупредив другую.

Следовательно, если у B будет список указателей на объекты A, ты должен как-то гарантировать, что объекты A будут оставаться живыми, а указатели на них валидными, до тех пор пока есть объекты B.

Ну или расписывай именно постановку задачи более подробно, чтобы такие детали были известны заранее.

eao197 ★★★★★ ()
Ответ на: комментарий от eao197

Следовательно, если у B будет список указателей на объекты A, ты должен как-то гарантировать, что объекты A будут оставаться живыми, а указатели на них валидными, до тех пор пока есть объекты B.

Да, механизм удаления объектов A — под контролем нашего кода. А вот политика их удаления — нет. Мы не знаем, сколько указателей на A есть в клиентском потоке, и когда именно он решит, что пора освободить данные. Поэтому отбирать A мы у него не можем, чтобы он не остался с некорректными указателями. А изменять данные внутри A (ссылку на B) — можем.

Deleted ()
Ответ на: комментарий от Deleted

Да, механизм удаления объектов A — под контролем нашего кода. А вот политика их удаления — нет.

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

eao197 ★★★★★ ()
Ответ на: комментарий от eao197

Если клиент получил объект A, то рано или поздно он должен вызвать вашу функцию для уничтожения A?

Либо он вызывает эту функцию сам, либо объект будет удалён автоматически при подчистке ресурсов после смерти клиента.

Если он этого не сделал, то это некорректная работа и такой сценарий не рассматривается?

Корректная, рассматривается.

Ладно, я опишу ситуацию. Я тут на коленке проектирую менеджер страничной памяти. Объекты типа A — это записи к таблице страниц, содержащие индексы физических фреймов. Объекты типа B — это дескприторы физических фреймов. В них лежит вся информация, необходимая для менеджмента фрейма.

Индекс физического фрейма одновременно является и индексом дескриптора, между ними однозначное соответствие.

«Указатели на A» — это на самом деле любые указатели в юзерспейсе, которые указывают на дарес на странице номер A.

Операция schedule_A() — это выделение физического фрейма и постановка его в очередь загрузки данных с блочного устройства.

deref_A() — это упрощеное изложение одной из функции обработчика страничного исключения, ожидающей готовности данных.

drop_B() — принудительное изъятие физического фрейма при выгрузке данных своп или по внутренним причинам системы.

Операция «освободить A» — это сискол munmap().

Deleted ()
Ответ на: комментарий от Deleted

s/записи к таблице страниц/записи в таблице страниц/

Deleted ()
Ответ на: комментарий от Deleted

Я тут на коленке проектирую менеджер страничной памяти

И все это должно работать в ядре?

eao197 ★★★★★ ()
Ответ на: комментарий от Deleted

Да.

Тогда я пас, не копенгаген совершенно.

Однако, задачу в теме нужно было сразу именно так и описывать. Меньше левого фидбэка было бы.

eao197 ★★★★★ ()
Ответ на: комментарий от eao197

Однако, задачу в теме нужно было сразу именно так и описывать. Меньше левого фидбэка было бы.

Да ладно, единственный полезный фидбек — от тебя. :)

Я думаю, что для задачи в общем виде «weak pointers на кэш ограниченного размера» решения те же самые, это абсолютно та же задача. Поэтому предметная область (кернелспейс или юзерспейс) не релевантна для решения.

Deleted ()
Ответ на: комментарий от Deleted

Я думаю, что для задачи в общем виде «weak pointers на кэш ограниченного размера» решения те же самые, это абсолютно та же задача.

Ну вот не уверен в этом. Из такой постановки задачи я не понимаю, откуда вообще берутся A и B. Может, если бы я был в курсе того, как устроены менеджеры памяти и какие там отношения между виртуальными и физическими адресами, было бы проще. А так есть у меня ощущение, что ты изложил какое-то странное приближение к реальной задаче, и вместо A и B на самом деле нужно что-то еще или что-то другое.

eao197 ★★★★★ ()

смотрю, здесь уже гуру многопоточности eao197 отметился...

тс, определись для начала: ты кеш фиксированного размере делаешь или менеджер памяти. если первое, сделай его частью прокси, если второе — перестань лохматить бабушку и повесь свой обработчик page-fault-а.

anonymous ()
Ответ на: комментарий от anonymous

тс, определись для начала: ты кеш фиксированного размере делаешь или менеджер памяти.

Внезапно: физическая память — это и есть кэш фиксированного размера.

если первое, сделай его частью прокси, если второе — перестань лохматить бабушку и повесь свой обработчик page-fault-а.

В обработчике page-fault-а и сидел потенциальный race condition, о котором я писал. Или ты думаешь, обратчики исключений работают через МАГИЮ?

Deleted ()
Ответ на: комментарий от Deleted

1. нет не кеш. из кеша копии отдают, а не ссылки.

2. ты хочешь сделать реентрабельный обработчик? упоролся?

anonymous ()
Ответ на: комментарий от anonymous

2. ты хочешь сделать реентрабельный обработчик? упоролся?

При чем тут реентрабельность? У тебя более одного процессора в железке. Пока ты одним процессором лочишь структуры со стороны обработчика PF, чтобы проверить статус фрейма (готов/не готов), другой процессор может лочить их со стороны дисковой подсистемы для проведения операций IO, а третий — со стороны балансировщика, решающего, какую страницу выгрузить следующей.

Более того, в одном процессе может быть произвольное число потоков, которые обрабатываются произвольным числом процессоров и вызывают исключения. В том числе, в пределах одной страницы. Несколько обработчиков PF может исполняться параллельно.

Deleted ()
Ответ на: комментарий от Deleted

При чем тут реентрабельность?

Несколько обработчиков PF может исполняться параллельно.

ясно. иди учи уроки.

anonymous ()
Ответ на: комментарий от anonymous

реентрабельный

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

ясно. иди учи уроки.

Иди-ка ты их сам поучи.

Deleted ()
Ответ на: комментарий от Deleted

у тебя есть менеджер кэша, следовательно все операции с объектами должны осуществляться через него, объекты кэша представляют собой структуры с данными и текущими статусами, на этом с объектами всё, менеджер имеет доступ к кэшу через набор методов которые работают через мьютекс/конд и предоставляют следующее апи: создать объект. добавить данные в объект, перезаписать данные в объект и тд. Так же в случае невозможности выполнения действий в данный момент( например попытка записи при текущем статусе:чтение) запрос добавляется в очередь которая также находится в менеджере и управляется менеджером. В твоей логике я вижу проблему в том что у тебя есть менеджер а управляют кэшем какие-то сервисные потоки, такие потоки должны либо быть инкапсулированы в менеджер либо работать на уровне клиентов, но работать в привилегированном режиме( иметь возможность изменять данные в кэше) Если это тестовое задание то делай сам

Onito ()
Ответ на: комментарий от Deleted

В винде возможна ситуация, когда PF происходит внутри PF при попытке доступа к page table.

это ты расскажешь своим одноклассникам... во-первых, на винфаке, во-вторых, после того как разберёшься какой адрес таблицы хранится в pde.

anonymous ()

Как устроена аппаратная трансляция адресов на IA-32 я разобрался еще в то время, когда ты под стол пешком ходил.

после того как разберёшься какой адрес таблицы хранится в pde.

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

За винду утверждать не буду, исходников её никто не видел. За что купил, за то и продаю.

Но то, что ты, дебилушка, не понимаешь, что необходимость держать giant lock можно свести к минимуму и использовать частичные блокировки — факт. Так что иди учи уроки и не позорься.

Deleted ()
Ответ на: комментарий от Deleted

Как устроена аппаратная трансляция адресов на IA-32 я разобрался

сомневаюсь

За винду утверждать не буду

это уже второй твой фейл (после реентрабельности)

необходимость держать giant lock

ты слышал от меня предложение использовать giant lock?

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.