LINUX.ORG.RU

Оцените потокобезопасность кода

 


0

2

Есть вот такой код:

Thread * volatile threadQueue[TASK_SCHEDULER_MAX_PRIORITY + 1];
int threadMaxRunningPriority = 0;
Mutex threadQueueMutex;
Thread * volatile threadResumeQueue;
Mutex threadResumeQueueMutex;

void schedulerInit(void) {
	mutexInit(&threadQueueMutex);
	mutexInit(&threadResumeQueueMutex);
}

inline Thread *schedulerFindNextTask(void) {
	Thread *nextThread = NULL;
	if (mutexTryLock(&threadQueueMutex)) {
		for (; threadMaxRunningPriority >= 0; threadMaxRunningPriority--) {
			if (threadQueue[threadMaxRunningPriority] != NULL) {
				nextThread = threadQueue[threadMaxRunningPriority];
				threadQueue[threadMaxRunningPriority] = nextThread->nextScheduled;
				break;
			}
		}
		mutexUnlock(&threadQueueMutex);
	}
	return nextThread;
}

void schedulerResumeTask(Thread *thread);

void schedulerResumeDelayedTasks(void) {
	if (mutexTryLock(&threadResumeQueueMutex)) {
		while (threadResumeQueue != NULL) {
			Thread *thread = threadResumeQueue;
			if (__sync_bool_compare_and_swap(&threadResumeQueue, thread, thread->nextScheduled)) {
				schedulerResumeTask(thread);
			}
		}
		mutexUnlock(&threadResumeQueueMutex);
	}
}

void schedulerResumeTask(Thread *thread) {
	if (mutexTryLock(&threadQueueMutex)) {
		if (threadQueue[thread->priority] == NULL) {
			thread->nextScheduled = thread;
			thread->prevScheduled = thread;
			threadQueue[thread->priority] = thread;
		} else {
			thread->nextScheduled = threadQueue[thread->priority];
			thread->prevScheduled = thread->nextScheduled->prevScheduled;
			thread->nextScheduled->prevScheduled = thread;
			thread->prevScheduled->nextScheduled = thread;
		}
		if (thread->priority > threadMaxRunningPriority) {
			threadMaxRunningPriority = thread->priority;
		}
		mutexUnlock(&threadQueueMutex);
		schedulerResumeDelayedTasks();
	} else {
		do {
			thread->nextScheduled = threadResumeQueue;
		} while (!__sync_bool_compare_and_swap(&threadResumeQueue, thread->nextScheduled, thread));
	}
}

void schedulerSuspendTask(Thread *thread) {
	mutexLock(&threadQueueMutex);
	if (threadQueue[thread->priority] == thread) {
		threadQueue[thread->priority] = thread->nextScheduled;
		if (threadQueue[thread->priority] == thread) {
			threadQueue[thread->priority] = NULL;
		}
		return;
	}
	thread->nextScheduled->prevScheduled = thread->prevScheduled;
	thread->prevScheduled->nextScheduled = thread->nextScheduled;
	mutexUnlock(&threadQueueMutex);
	schedulerResumeDelayedTasks();
}

Поля структуры Thread nextScheduled и prevScheduled описаны как Thread * volatile.

Условия такие:

1) schedulerFindNextTask может прервать любую функцию, кроме самой себя. Ей допустимо иногда возвращать NULL вместо того, чтобы выполнить свою работу.

2) schedulerResumeTask может прервать любую функцию, в том числе саму себя. Она не имеет права блокироваться.

3) schedulerSuspendTask не может прервать никакую функцию, но два потока могут вызвать эту функцию одновременно. Допустима блокировка выполнения.

Больше никакой код к полям nextScheduled и prevScheduled, а также вышеописанным глобальным переменным не обращается.

1) Достаточно ли проверок и условий в этих функциях, чтобы гарантировать, что структура данных (связанный список) не будет никогда повреждена и не возникнет зависания (schedulerFindNextTask и schedulerResumeTask не имеют права блокироваться ни при каких обстоятельствах).

2) Можно ли доверять встроенной функции GCC __sync_bool_compare_and_swap на платформе ARM Cortex-M3?

3) Возможно ли переписать данный код более оптимально, сохранив безопасность?

★★★★★

Последнее исправление: KivApple (всего исправлений: 5)

Ответ на: комментарий от mashina

Можно конкретные замечания, что в моём стиле кодирования плохого? Если будут объективные замечания, я постараюсь их исправить.

KivApple ★★★★★
() автор топика
Последнее исправление: KivApple (всего исправлений: 1)

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

I-Love-Microsoft ★★★★★
()
Ответ на: комментарий от anonymous

Там, где это будет использоваться, erlang нет.

И что вы все загадки загадываете? Можно конкретные замечания, пусть даже не про потокобезопасность?

KivApple ★★★★★
() автор топика
Ответ на: комментарий от I-Love-Microsoft

Мне кажется, что вышеприведённый код достаточно мал, чтобы можно было оценить его безопасность (если допустить, что библиотечные функции не содержат ошибок) лишь с точки зрения логики.

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

ИМХО в потоках ничего не должно быть кроме сообщений в плане взаимодействий и никакой синхронизации.

Наиболее удачнее всего эта модель реализована в erlang. Ну может быть еще в rust. Кстати можно его подключать в плюсы.

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

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

I-Love-Microsoft ★★★★★
()

Это-ж у вас кусок шедулера самодельного RTOS?

откуда такое обилие volatile`ов и Mutex`ов ? неужели есть более приоритетные вещи которые к тому-же лезут в данные планировщика

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

Ты не на том форуме вопрос задал, здесь 70% виндузятников и 90% нифига не программистов. Так что врядли тебе по делу ответят, но вероятность есть конечно

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

Планировщик (schedulerFindNextTask) может быть прерван высокоприоритетным прерыванием, которое пошлёт сигнал спящему процессу (schedulerResumeTask). Процесс (который захотел разбудить другой процесс или наоборот уснуть сам) может быть прерван любым прерыванием, которое может быть планировщиком (SysTick) или будить кого-то. Запрещать все прерывания на каждый чих мне кажется плохой идеей.

KivApple ★★★★★
() автор топика
Последнее исправление: KivApple (всего исправлений: 2)
Ответ на: комментарий от KivApple

А можно конкретные замечания?

код практически не читаем..какие-уж тут замечания :-)

PS. если встречается что-то типа «thread->platformData.prevScheduled->platformData.nextScheduled» то это верный признак что надо переписывать.

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

Микроконтроллер, для которого я пишу самодельную RTOS

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

I-Love-Microsoft ★★★★★
()
Ответ на: комментарий от MKuznetsov

Претензии только к большой вложенности структур? Иных серьёзных замечаний к читабельности нет?

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

Можно конкретные замечания, что в моём стиле кодирования плохого? Если будут объективные замечания, я постараюсь их исправить.

Да, пожалуйста... Кругом копипаста со специализацией в разных вариантах, например тут

thread->platformData.nextScheduled->platformData.prevScheduled = thread->platformData.prevScheduled;
thread->platformData.prevScheduled->platformData.nextScheduled = thread->platformData.nextScheduled;
копипастишь всюду thread->platformData и, может быть, везде по коду примитивы работы со связанными списками. Кому нужно вчитываться в беспощадные и однообразные простыни текста и отделять примитивы работы со списками от иной логики, тем более везде похожие операции делаются по-разному. Мышиная возьня должна выноситься в отдельные ф-ии чтобы из названия было понятно что это и чтобы не нужно было каждый раз на неё тратить время. Только из-за одной копипасты получаются строки длиной по 100 символов хотя смысловой нагрузки в них практически никакой нет.

Есть в коде куча переменных с префиксом thread, но нет переменных с другим префиксом - нахрена на ровном месте удлиняешь название сущностей? Читабельность от этого значительно снижается, а с ней и снижается вероятность поиска ошибок. Продолжая тему, совершенно бесcмысленно называть переменную threadMaxRunningPriority так длинно. Если есть проблема с коллизией имён где всё это добро помещается, то нужно помещять их в объекты (структуры) с короткими ёмкими названиями. Если очень хочется уточнить за чем переменная нужна, то сделай это коментом к объявлению переменной (полю структуры), а не придумывая дебильные километровые названия.

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

Удалил из сообщения platformData. Теперь имена стали короче, а логика осталась прежней.

Си не умеет к классы и namespace. Конечно, я могу запихнуть данные планировщика в какую-нибудь структуру, но какая разница между scheduler.maxRunningPriority и threadMaxRunningPriority? Называть переменные односложно, так что потеряется их смысл, я не хочу. Я не из тех программистов, у которых куча переменных i, j, k, m, n и т. д., а потом какая-то чёрная магия. Однобуквенные имена я использую только в for.

Копипасты работы со спискам нет. Добавление в двусвязанный список осуществляется только в schedulerResumeTask, а удаление только в schedulerSuspendTask. Также в schedulerResumeTask осуществляется добавление в односвязанный список threadResumeQueue, а удаление в schedulerResumeDelayedTasks. В каждом случае свой алгоритм (очевидно, что работа с двусвязаным и односвязаным списком отличается, также как отличаются операции добавления и удаления).

KivApple ★★★★★
() автор топика
Последнее исправление: KivApple (всего исправлений: 2)
Ответ на: комментарий от KivApple

может быть прерван высокоприоритетным прерыванием, которое пошлёт сигнал спящему процессу

Запрещать все прерывания на каждый чих мне кажется плохой идеей.

а не надо запрещать - достаточно одного atomic флага типа «shedulerInAction» чтобы объехать вложенный вызов планировщика, а сигналы от прерываний класть в простые очереди. Или придумать другой способ :-)

решение в лоб - объявлять массив из volatile очередей и обкладывать каждый чих мутексами не самое лучшее.

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

Ну вот этот atomic флаг у меня и есть mutex. Какие-то дополнительные действия выполняются лишь если мы пытаемся залочить mutex бессрочно или с таймаутом. Если мы делаем tryLockMutex, то это банальный __sync_bool_compare_and_swap(&(mutex->flag), false, true). Оверхед разве что на вызов функции. Зато я получаю необходимую логику в schedulerSuspendTask, которая таки имеет право блокироваться и ждать.

KivApple ★★★★★
() автор топика
Последнее исправление: KivApple (всего исправлений: 1)
Ответ на: комментарий от MKuznetsov

Есть, конечно, мысль попытаться переписать всё вообще без блокировок с помощью __sync_bool_compare_and_swap.

Но хотелось бы услышать ответ насчёт надёжности данной конструкции на ARM Cortex-M3 (на x86 есть специальная инструкция cmpxchg).

KivApple ★★★★★
() автор топика
Последнее исправление: KivApple (всего исправлений: 1)

Thread * volatile.

Не знаю, как там в этих ваших сях, а в плюсах, когда используешь блокировки (mutex), volatile не нужен. Внутри блокировки должна быть необходимая синхронизация памяти при захвате и при освобождении. Ну, а если писать очередь без блокировок, то нужно использовать atomic (только тогда не в виде связанного списка, а по другому, чтобы избежать управления памятью, с которой и связаны все сложности lockfree алгоритмов)...

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

Тогда я утраиваю свои слова и настойчиво рекомендую сделать юнит-тесты.

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

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

__sync_bool_compare_and_swap(&(mutex->flag), false, true). Оверхед разве что на вызов функции.

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

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

Даже сутки работы теста могут такого не выявить

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

I-Love-Microsoft ★★★★★
()
Ответ на: комментарий от I-Love-Microsoft

По мне так модульный тесты для конкурентных/параллельных алгоритмов полезны, потому что позволяют проверить, что алгоритм действительно работает. Нагрузочные тесты позволяют убедиться, что в 99% случаев алгоритм работает как надо. Но гарантировать отсутствие условий гонки при особо редком стечении обстоятельств не сможет...

Кстати, а как нужно «генерировать наихудшие условия работы» в тесте? Обычно их пишут так, что тест гоняется в цикле, в результате 100% данных и кода лежат в кеше первого уровня, а это совсем не тот режим, в котором работает реальное приложение... :-)

anonymous
()
Ответ на: комментарий от anonymous
Thread * volatile threadQueue[TASK_SCHEDULER_MAX_PRIORITY + 1];
volatile int threadMaxRunningPriority = 0;

void schedulerInit(void) {
	
}

inline Thread *schedulerFindNextTask(void) {
	Thread *nextThread = NULL;
	do {
		for (; threadMaxRunningPriority >= 0; threadMaxRunningPriority--) {
			if (threadQueue[threadMaxRunningPriority] != NULL) {
				nextThread = threadQueue[threadMaxRunningPriority];
				break;
			}
		}
	} while (nextThread && (!__sync_bool_compare_and_swap(&threadQueue[nextThread->priority], nextThread, nextThread->platformData.nextScheduled)));
	return nextThread;
}

void schedulerResumeTask(Thread *thread) {
	while (true) {
		if (threadQueue[thread->priority] == NULL) {
			thread->platformData.nextScheduled = thread;
			if (__sync_bool_compare_and_swap(&threadQueue[thread->priority], NULL, thread)) {
				break;
			}
		} else {
			thread->platformData.nextScheduled = threadQueue[thread->priority]->platformData.nextScheduled;
			if (__sync_bool_compare_and_swap(&(threadQueue[thread->priority]->platformData.nextScheduled),
					thread->platformData.nextScheduled, thread)) {
				break;
			}
		}
	}
	int maxPriority, newMaxPriority;
	do {
		maxPriority = threadMaxRunningPriority;
		newMaxPriority = (thread->priority > maxPriority) ? thread->priority : maxPriority;
	} while (!__sync_bool_compare_and_swap(&threadMaxRunningPriority, maxPriority, newMaxPriority));
}

void schedulerSuspendTask(Thread *thread) {
	while (true) {
		if (thread->platformData.nextScheduled == thread) {
			if (__sync_bool_compare_and_swap(&threadQueue[thread->priority], thread, NULL)) break;
		} else {
			/// ???
		}
	}
}

Туплю как сделать lock-free удаление задачи из списка.

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

Есть, конечно, мысль попытаться переписать всё вообще

вообще всё начинается (и реализуется) с вопросов:

1. как отрабатываются прерывания. Разделяется отработка на две фазы или всё идёт в одну кучу.

2. Как часто будет секс с таймером. Как будешь нарезать кванты и отрабатывать таймеры.

3. «где живёт и работает шедулер» :-) известных мест его обитания всего два: в прологе+эпилоге прерываний и как отдельный(хоть и специфичный) тред.

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

Допилил. Это корректный lock-free код?

Thread * volatile threadQueue[TASK_SCHEDULER_MAX_PRIORITY + 1];
volatile int threadMaxRunningPriority = 0;

inline Thread *schedulerFindNextTask(void) {
	Thread *nextThread = NULL;
	do {
		for (; threadMaxRunningPriority >= 0; threadMaxRunningPriority--) {
			if (threadQueue[threadMaxRunningPriority] != NULL) {
				nextThread = threadQueue[threadMaxRunningPriority];
				break;
			}
		}
	} while (nextThread && (!__sync_bool_compare_and_swap(&threadQueue[nextThread->priority], nextThread, nextThread->nextScheduled)));
	return nextThread;
}

void schedulerResumeTask(Thread *thread) {
	while (true) {
		if (threadQueue[thread->priority] == NULL) {
			thread->nextScheduled = thread;
			if (__sync_bool_compare_and_swap(&threadQueue[thread->priority], NULL, thread)) {
				break;
			}
		} else {
			thread->nextScheduled = threadQueue[thread->priority]->nextScheduled;
			if (__sync_bool_compare_and_swap(&(threadQueue[thread->priority]->nextScheduled),
					thread->nextScheduled, thread)) {
				break;
			}
		}
	}
	int maxPriority, newMaxPriority;
	do {
		maxPriority = threadMaxRunningPriority;
		newMaxPriority = (thread->priority > maxPriority) ? thread->priority : maxPriority;
	} while (!__sync_bool_compare_and_swap(&threadMaxRunningPriority, maxPriority, newMaxPriority));
}

void schedulerSuspendTask(Thread *thread) {
	while (true) {
		Thread *prev = threadQueue[thread->priority];
		while (prev->nextScheduled != thread) {
			prev = prev->nextScheduled;
		}
		if (__sync_bool_compare_and_swap(&(prev->nextScheduled), thread, thread->next)) {
			if (__sync_bool_compare_and_swap(&(threadQueue[thread->priority]), thread, thread->next)) {
				__sync_bool_compare_and_swap(&(threadQueue[thread->priority]), thread, NULL);
			}
			break;
		}
	}
}
KivApple ★★★★★
() автор топика
Ответ на: комментарий от KivApple

Туплю как сделать lock-free удаление задачи из списка.

lockfree для связанного списка без управления памятью не делается. Даже стек без сборщика мусора не написать. Можно только стек, в двумя операциями push и popAll. К тому же параллельные алгоритмы довольно сложная штука. Вряд ли кто-то тут станет вникать в него достаточно детально. Я когда делал свой шуделер для плюсовых корутин, сделал комбинацию стека без pop (popless stack) и ограниченной по количеству ячеек очереди (bounded queue). То и другое можно сделать без сборщика мусора. Добавление задач в очередь идет в стек, а при извлечении из очереди сначала идет обращение в ограниченной очереди, если там ничего не осталось, то берется весь накопившийся стек и слегка размазывается по ограниченной очереди (по одной задаче в каждую ячейку, кроме последней, в нее весь оставшийся стек). Задачи, которые ставятся в очередь сделаны intrusive, чтобы не было выделений памяти под список. Такой алгоритм реализуется как lockfree, даже если одновременно несколько потоков «размазывают» данные в ограниченную очередь. Но там не будет FIFO очереди (что даже полезно для разогретости кешей), потому что, когда идет получение задач и образуется обращение к стеку, то по сути задачи вытаскиваются в обратном порядке. Т.е. в пределах пачки задач, которые попали в стек они оттуда достаются в порядке LIFO, а сами пачки в порядке FIFO.

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

Нет, некорректный. Связанный список без сборщика мусора не реализовать. Ошибка будет тут:

nextThread = threadQueue[threadMaxRunningPriority];
После этой строчки код прервется, затем другой поток прочитает то же значение nextThread, запустит его на выполнение, выполнит, удалит память на которую указывает nextThread, а после этого проснется первый поток и выполнит разыменование nextThread
nextThread->nextScheduled

anonymous
()

Код - лютое нечитаемое говнище, потому что:

  • верблюжийРегистрИменХуевоЧитается
  • имена переменных пиздец какие длинные. Не слушай мудаков, вещающих про «самодокументирующийся код». Строки длиннее 100 символов читаются очень хуево. При твоем подходе к именованию и за две сотни выпрыгнуть не проблема
  • в schedulerSuspendTask нет отпускания мьютекса перед return
  • уже есть pthread_spinlock_t, зачем изобретать свои костыли для меня загадка
anonymous
()
Ответ на: комментарий от anonymous

Завершение процесса - очень редкая ситуация для микроконтроллера. Ради такого дела можно и прерывания позапрещать. Подразумевается, что память не освобождается. Могут только создаваться новые элементы очереди и добавляться с помощью schedulerResumeTask, а также добавляться-удаляться в очередь-из очереди существующие.

Я тут исправил ряд косяков. Теперь всё выглядит так:

Thread * volatile threadQueue[TASK_SCHEDULER_MAX_PRIORITY + 1];
volatile int threadMaxRunningPriority = 0;

inline Thread *schedulerFindNextTask(void) {
	Thread *nextThread = NULL;
	do {
		int maxRunningPriority = threadMaxRunningPriority;
		while (maxRunningPriority >= 0) {
			nextThread = threadQueue[maxRunningPriority];
			if (nextThread != NULL) {
				break;
			}
			int newMaxPriority = maxRunningPriority - 1;
			__sync_bool_compare_and_swap(&threadMaxRunningPriority, maxRunningPriority, newMaxPriority);
			maxRunningPriority = threadMaxRunningPriority;
		}
	} while (nextThread && (!__sync_bool_compare_and_swap(&threadQueue[nextThread->priority], nextThread, nextThread->nextScheduled)));
	return nextThread;
}

void schedulerResumeTask(Thread *thread) {
	if (!__sync_bool_compare_and_swap(&(thread->running), false, true)) return;
	while (true) {
		if (threadQueue[thread->priority] == NULL) {
			thread->nextScheduled = thread;
			if (__sync_bool_compare_and_swap(&threadQueue[thread->priority], NULL, thread)) {
				break;
			}
		} else {
			thread->nextScheduled = threadQueue[thread->priority]->nextScheduled;
			if (__sync_bool_compare_and_swap(&(threadQueue[thread->priority]->nextScheduled),
					thread->nextScheduled, thread)) {
				break;
			}
		}
	}
	int maxPriority, newMaxPriority;
	do {
		maxPriority = threadMaxRunningPriority;
		newMaxPriority = (thread->priority > maxPriority) ? thread->priority : maxPriority;
	} while (!__sync_bool_compare_and_swap(&threadMaxRunningPriority, maxPriority, newMaxPriority));
}

void schedulerSuspendTask(Thread *thread) {
	if (!__sync_bool_compare_and_swap(&(thread->running), true, false)) return;
	while (true) {
		Thread *prev = threadQueue[thread->priority];
		if (prev == NULL) break;
		while (prev->nextScheduled != thread) {
			prev = prev->nextScheduled;
		}
		if (__sync_bool_compare_and_swap(&(prev->nextScheduled), thread, thread->nextScheduled)) {
			if (__sync_bool_compare_and_swap(&(threadQueue[thread->priority]), thread, thread->nextScheduled)) {
				__sync_bool_compare_and_swap(&(threadQueue[thread->priority]), thread, NULL);
			}
			break;
		}
	}
}

Спасибо большое за подсказки.

KivApple ★★★★★
() автор топика
Последнее исправление: KivApple (всего исправлений: 1)
Ответ на: комментарий от I-Love-Microsoft

Для начала решил прогнать следующий тест.

Вставил весь этот код в обычную сишную программу. Создаю сотню Thread-ов. По 10 каждого приоритета от 0 до 9.

Затем создаю настоящий линуксовые треды. 4 штуки. Они берут рандомный Thread и если он спит будят его, если не спит - усыпляют.

Главный линуксовый поток после всей инициализации начинает в бесконечном цикле вызывать schedulerGetNextThread. Если он возвращает NULL, то пишем «FAILED» и выходим из программы. Запускаю всё это хозяйство под GDB и жду.

Отловил пару ошибок, которые приводили к SegFault. Сейчас уже минут 10 работает и не падает (там триллионы операций уже наверное произошли, на МК такой активности не будет никогда).

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

Нормальное тестирование?

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

Я не из тех программистов, у которых куча переменных i, j, k, m, n и т. д., а потом какая-то чёрная магия. Однобуквенные имена я использую только в for.

Никто ещё об этом никогда не писал, все по какой-то странной причине обходят эту тему в беседах... Но сейчас я постараюсь перешагнуть через предрассудки и озвучить страшную тайну: кроме идиотских названий длиной в половину терминала и однобуквенных переменных есть ещё имена из 2, 3, 4 и даже из 5 и 6 символов.

какая разница между scheduler.maxRunningPriority и threadMaxRunningPriority?

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

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

Смотрю я на код уже существующих RTOS и вижу, что они именно то и делают, что обкладывают каждый чих блокировками.

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

Смотрю я на код уже существующих RTOS и вижу, что они именно то и делают, что обкладывают каждый чих блокировками.

просто писал RTOS - про мутексы и их подобия в ядрышке даже и ненамекалось :-) цель ядра: как можно быстрее разрулить прерывания и в правильную сторону отдать управление. Поэтому всё это топтание по куче очередей, их защита мутексами, заумное планирование - оно всё ненужное и выдуманное для больших/универсальных/медленных ОС. Дисциплин (очередей в вашем случае) более чем достаточно трёх на самом деле.

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

Копание в очередях без блокировок - инстант фейл. Копание во внутренностях потока без блокировок - инстант фейл (как ты гарантируешь, что там не копается еще какой-нибудь поток?).

Это относится и к первому куску кода, и ко второму.

shkolnick-kun ★★★★★
()
Ответ на: комментарий от MKuznetsov

Правильно, в большинстве случаев достаточно запретить перывания XD

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

Что касается очередей - я согласен, что можно сделать по mutex'у - отдельный на запись и отдельный на чтение (кольцевой буфер позволяет одновременно читать и писать). Это, кстати, обычно к локам приводить не будет, потому что обычно только кто-то один пишет в очередь и только кто-то один читает. При создании-удалении процессов вообще можно прерывания запрещать, потому что это достаточно редкая операция для МК.

Но вот планировщик (самая часто вызываемая часть ОС) lock-free, ИМХО, сделать можно. Я уже почти написал, но туплю как реализовать lock-free удаление из однонаправленного связанного списка (это по сути suspend задачи). У меня на некоторых тестах всё виснет. Но lock-free алгоритм для однонаправленного списка точно в природе существует.

KivApple ★★★★★
() автор топика
Последнее исправление: KivApple (всего исправлений: 2)
Ответ на: комментарий от KivApple

уменьш вложеность

инвертируй в некоторых местах условия для перестановки веток.

основную ветку старайся поднимать в основной поток -(для этого из неосновных веток можно и досрочный выход из функции)

вообще код понятней когда основное тело предвараяется фильтрацией на предусловие(и обработкой если фильтр тормозит состояние)

qulinxao ★★☆
()
Ответ на: комментарий от qulinxao
#define CAS(var, oldValue, newValue) __sync_bool_compare_and_swap(&(var), oldValue, newValue)

typedef struct Item Item;
struct Item {
	Item * volatile next;
	...
};

Item * volatile head = NULL;

void addToList(Item *item) {
	while (true) {
		item->next = listHead;
		if (item->next == NULL) {
			item->next = item;
			if (CAS(listHead, NULL, item)) {
				break;
			}
		} else {
			if (CAS(listHead, item->next, item)) {
				break;
			}
		}
	}
}

void removeFromList(Item *item) {
	while (true) {
		Item *prev = listHead;
		while (prev->next != item) {
			prev = prev->next;
		}
		if (CAS(prev->next, item, item->next)) {
				if (CAS(head, item, item->next)) {
					CAS(head, item, NULL);
				}
				break;
			}
		}
	}
}

Переписал код более-менее абстрактно, чтобы конкретизировать вопрос. Меня сейчас интересует в первую очередь корректность реализации этих двух функций (без учёта вопроса освобождения памяти после удаления элемента - будем считать, что я могу гарантировать, что элемент никто не добавит перед его уничтожением).

А вот полный код - http://pastebin.com/UqsFYGbV

Так лучше?

KivApple ★★★★★
() автор топика
Последнее исправление: KivApple (всего исправлений: 1)
Ответ на: комментарий от KivApple

Во внутреннем цикле в removeFromList время выполнения O(n), результат непиемлемое WCET.

Уж лучше блокировки и\или запрет прерываний, чем это.

shkolnick-kun ★★★★★
()
Ответ на: комментарий от KivApple

Зачем тебе вообще lockfree планировщик?

Lockfree не значит хорошо на самом деле.

Та же операция CAS вполне себе «блокирующая».

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