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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Перед тем, как хотя бы прочитать указатель на очередь ожидания (или на кондвар, семафор, не суть, чем у нас оно будет реализовано), поток 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.

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

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

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

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

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

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

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

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

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

Алексей?!

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

Алексей?!

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

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

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

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

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

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);

}

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

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

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

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

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

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

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

Можно же не хранить в 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. Алгоритм предложен сходу, так что косяки в нем наверняка есть. Но и постановка задачи довольно размытая и странная.

gen_fsm

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

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

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

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

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

Если использовать отложенное освобождение ресурсов, — клиент может вообще никогда не вызвать 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Да.

Да.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вот так поток сознания!

Вот и цари!

пофантазировать уже нельзя? :)

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

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

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

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

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

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

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

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

сомневаюсь

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

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

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

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