Использование двоичного семафора для построения счетного семафора

Question

Я изучаю семафоры. В книге есть вопрос без ответа, и мне бы очень хотелось узнать, как решить проблему.

Вопрос в том:

Это счетный семафор, написанный на Algol68:

Down mutex: if mutex = 0 then access is blocked
                            else mutex := mutex -1
Up mutex: mutex := mutex + 1, restart  program
                            which blocked because of mutex.

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

Используйте две двоичные переменные семафора и одну статическую переменную в счетном семафоре.

Answer 1

Этот пример не в правильном синтаксисе для Алгола 68, но очень вероятно, псевдокод стиля Алгол 68. Он явно содержит некоторые комментарии, которые служат для объяснения утверждений, которые вы можете найти в описании алгоритма.

Существует аналогичный пример использования семафоров в Алголе 68, содержащийся в книге Линдси и Ван дер Мейлена " Неформальное введение в Алгол 68 " и в пересмотренном отчете Алгола 68.

Вы не будете писать примитивы вверх и вниз в Алголе 68, поскольку они уже реализованы на предоставленном языке в качестве примитивов. Неделимая атомарная природа операций над семафорами потребовала бы их встраивания. Реализация их самостоятельно сделала бы их неатомарными и бесперебойными, что сделало бы их бесполезными в качестве операционных семафоров! Тем не менее, полезно узнать, что находится внутри такого примитива.

Алгол 68 обеспечивает объявление семафора, используя объявление sema и операции вверх и вниз, как обсуждалось. Он также предоставляет параллельные предложения, в которых они могут работать, которые обозначены символом par, а также запятой , разделитель. (Точка с запятой ; используется для последовательных, непараллельных операций).

Таким образом:

семафор сем; ¢ Объявляет семафор, содержащий целое число ¢
семафор: = уровень 9; ¢ Инициализирует целое число внутри семафора значением 9 ¢
вверх семафор; ¢ целое число внутри семафора увеличивается на единицу ¢
вниз семафор; ¢ целое число внутри семафора уменьшается на единицу ¢
значение типа: = семафор уровня; ¢ извлечь значение целого числа, содержащегося в семафоре ¢

Таким образом, текст, который вы цитировали, неправильно переведен. Следует сказать, что показанные алгоритмы являются описанием того, как функционируют операторы семафора в Алголе 68. Это не часть Алгола 68, а объяснение того, что на самом деле делают операторы вверх и вниз. Вас не просят реализовать их в Алголе 68, но внедрите их на другом языке в качестве примера, чтобы продемонстрировать, как они работают. Алгол 68 уже содержит счетные семафоры. Какой-то другой язык (не Алгол 68) будет содержать двоичные семафоры.

Поскольку алгоритм в описании является довольно явным, его не должно быть сложно кодировать. Если бы вы указали, на каком языке должен быть показан код (содержащий двоичные семафоры), мы могли бы помочь с этим! Вы неправильно перевели и неправильно поняли, что ваша книга просит вас сделать.

---

_{^{Я бы ответил раньше, но забыл проверить тег algol68!}}