семафоры...

[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 расчитывать на счётчики и экспонировать обе стороны семафора всякому желающему - совершенно некошерно. Я полагаю всё это совершенно неправильным, по нынешним понятиям.

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

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

[spamsink.livejournal.com]

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