реализовать мьютекс, чтобы обеспечить ограниченное ожидание

Question

это вопрос интервью, который я встретил, но я не знаю, как на него ответить.

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

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

как бы вы ответили на этот вопрос интервью? какую атомарную операцию я могу использовать для реализации мьютекса и как?

Answer 1

Похоже, есть два варианта «ограниченного ожидания». Кажется, что одно использование представляет собой простое значение, основанное на времени :

Существует ограничение времени ожидания для любого конкретного процесса для входа в критическую секцию.

Другое использование, кажется, имеет значение подсчета потоков :

Процесс, запрашивающий вход в критическую секцию, должен ждать только ограниченного числа других процессов, чтобы войти и выйти из критической секции.

---

К сожалению, я понятия не имею, как на самом деле ответить на вопрос. Кажется, это зависит от примитивов ОС. Возможно, они искали что-то вроде решения Петерсона .

Answer 2

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

повтор
... получить блокировку мьютекса ОС на счетчике
... проверить счетчик, см.> 0.
... ... если больше 0, уменьшить, освободить мьютекс ОС, получен тайм-аут возврата
... снять блокировку мьютекса ОС на счетчике
... проверить, истекло ли время
... ... если тайм-аут, тайм-аут возврата тайм-аута
... поспать некоторое время
конец повтор

Конечно, мьютексы POSIX имеют функцию триблока, которая делает цикл ожидания тривиальным.

Ожидание при занятости - это, конечно, потеря мощности процессора. Возможны более эффективные реализации, например, в POSIX есть условные переменные.