семафоры...

[yigal_s]

Что-то я не вполне понимаю документацию линукса:

sem_post() increments (unlocks) the semaphore pointed to by sem. If the semaphore's value consequently becomes greater than zero, then another process or thread blocked in a sem_wait(3) call will be woken up and proceed to lock the semaphore.

sem_wait() decrements (locks) the semaphore pointed to by sem. If the semaphore's value is greater than zero, then the decrement proceeds, and the function returns, immediately. If the semaphore currently has the value zero, then the call blocks until either it becomes possible to perform the decrement (i.e., the semaphore value rises above zero), or a signal handler interrupts the call.

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

Даже хуже, можно засигналить семафор, который кто-то ждет, тут же самому сделать на нём sem_wait и проглотить этот сигнал. А тот, кто ждет - так и не дождется.

Вообще говоря, интересно, какие неявные допущения мы делаем, когда использует семафоры или критические секции, т.е. будет ли наш код работать лишь при определенном уровне faireness, либо же при любом, в том числе и самом минимальном, т.н. weak faireness, примером которого и является данный спек. Относительно некоторых простейших алгоритмов этот вопрос прост и на него можно ответить сразу, разумеется, но в целом я не уверен, что всегда отдаю себе в этом отчет.

Можно даже проще поставить вопрос: существует ли алгоритм общего вида (а не специально злостно написанный), который будет работать на fair mutex/semaphore и не рабоать на unfair? Да даже если и злостно написанный. Хммм... что-то у меня в этой области слепое пятно.

Comments

[juan-gandhi.livejournal.com]

А вот это очередная тема, по которой я хотел бы потоптаться сапогами (только в джаве соответственно). Я понимаю, году в 69-м Дийкстра всё это впаривал, это было свежо и правильно. В 2011 расчитывать на счётчики и экспонировать обе стороны семафора всякому желающему - совершенно некошерно. Я полагаю всё это совершенно неправильным, по нынешним понятиям.

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

Короче, всё неправильно в современном привычном подходе.

[yigal_s]

экспонировать только одну сторону семафора - это примерно как экспонировать только одну сторону мютекса )))


Я не очень осведомлён о той истории, но вроде народ довольно быстро тогда допёр, что кондвары и прочие "мониторы" лучше семафоров. Вроде, там и Дейкстра руку приложил, хотя может я что-то путаю.

Я не знаю, "правильно" это или "неправильно". К сожалению, как правильно программировать мультитред - пока неясно, хотя, конечно, хочется прокричать Transaction Memory/Actors rules, но всё-таки очень многое с этим неясно пока.

В этом контексте семафоры дают неплохую разминку мозгам.

[spamsink.livejournal.com]

"Даже хуже" не будет, т.к., надо понимать, another process or thread [already] blocked in a sem_wait(3) call will be woken up.

[yigal_s]

woken up... and proceed to lock the semaphore :-)

[spamsink.livejournal.com]

При правильной реализации это действие атомарное.

[yigal_s]

что есть "правильная реализация"?

Есть спек, по спеку это действие не атомарное, да оно и не обязано быть атомарным.

Просто есть разные вариации семафоров - от обеспечивающих жесткую очередность до вот таких. Причем, судя по документации, на linux они именно что "вот такие".

Что, конечно, не мешает реализовать их с более строгим fairness на практике.

[spamsink.livejournal.com]

По определению семафора оно атомарное. Если спек это не оговаривает, то это или подразумевается, или - если и реализация не делает P атомарным - то козлы писали.

[yigal_s]

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

Т.е. управление счетчиком тут, конечно, атомарное, но атомарности wake up and gain the semaphore не наблюдается.

[spamsink.livejournal.com]

Атомарности wake up and gain the semaphore и не нужно - достаточно очередности входа и выхода в/из sem_wait(), какую порядочный scheduler и должен обеспечивать для процессов с одинаковыми приоритетами.

[yigal_s]

неважно как это называть, главное, что ЭТОГО нет в спеке.

[spamsink.livejournal.com]

В спеке sim_*() этого и не должно быть. Это quality of implementation операционной системы.

[yigal_s]

Почему же обязательно не должно? Степень fairness семафора вполне может быть частью спека.