using binary semaphore to build counting semaphore

Question

I'm studying semaphores. In the book there's a question without an answer, and I would really like to know how to solve the problem.

The question is:

This is a counting semaphore written in 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.

By using a binary semaphore write a up,down primitive which is built on top of a counting semaphore (like the example).

Use two binary semaphore variables and one static variable in the counting semaphore.

Answer 1

This example is not in the correct syntax for Algol 68, but is very likely Algol 68 style pseudo-code. It clearly contains some comments which are there to explain the statements as you might find in an algorithm description.

There is a similar example of using semaphores in Algol 68 contained in the book "An Informal Introduction to Algol 68" by Lindsey and Van der Meulen and in the Algol 68 Revised Report.

You would not write the up and down primitive in Algol 68 as they are already implemented in the provided language as primitives. The indivisible atomic nature of operations on semaphores would require them be built in. To implement them yourself would render them non-atomic and uninterruptible making them useless as operational semaphores! It is, however, instructional to learn what is inside such a primitive.

Algol 68 provides a declaration of a semaphore using the sema declaration and the operations up and down as discussed. It also provides parallel clauses in which they can operate which are indicated by the par symbol and also by the comma , separator. (The semicolon ; being used for sequential, non-parallel operations).

Thus:

sem semaphore;                       ¢ Declares semaphore containing an integer ¢
semaphore := level 9;               ¢ Initialises the integer inside the semaphore to the value of 9 ¢
up semaphore;                          ¢ the integer inside the semaphore is incremented by one ¢
down semaphore;                     ¢ the integer inside the semaphore is decremented by one ¢
int value := level semaphore;   ¢ extract the value of the integer contained within the semaphore ¢

So, the text you have quoted, is incorrectly translated. It should say that the algorithms shown are the descriptions of how the semaphore operators in Algol 68 function. It is not a piece of Algol 68 but an explanation of what the operators up and down actually do. You are not asked to implement them in Algol 68, but implement them in some other language as an example to demonstrate how they work. Algol 68 already contains counting semaphores. Some other language (not Algol 68) would contain the binary semaphores.

As the algorithm in the description is quite explicit, it should not be difficult to code. If you had indicated what language the code should be shown in (that contained the binary semaphores) we could have helped with that! You have mistranslated and misunderstood what your book is asking you to do.

---

_{^{I would have answered earlier but forgot to check the algol68 tag!}}