Extended semaphores systems such as in UNIX System V are a powerful extension of Dijkstra's semaphores. They allow efficient solutions to a number of classic synchronization problems. UNIX semaphore operations appear to be insufficiently well defined, in particular when a semaphore is repeated in an operator. This results in several solutions relying on assumed properties. A new semaphore operator, isem, based on extended semaphore operators is introduced. The operator isem is clearly defined, can be implemented efficiently, and yields simple solutions to many classic synchronization problems. Copyright © 2000 John Wiley & Sons, Ltd.

Abstract Semaphores have been used extensively in programming concurrent tasks. Various extensions have been proposed for problems in which traditional semaphores turned out to be difficult to use. The extended semaphore primitives investigated here are based on the version of semaphores implemented in UNIX System V. Implementation issues are discussed and practical illustrations of their use are provided. In particular, algorithms for a variety of common process scheduling schemes are shown. These solutions are evaluated and the strengths and weaknesses of UNIX semaphores are discussed.

In this paper we study some relationships between the number of vertices, degree and diameter of finite diregular graphs. The three problems considered are N(d,k), K(n,d) and D(n,k); that is, find the maximum possible number of vertices given degree d and diameter k, find the minimum possible diameter given the number of vertices n and degree d, and find the minimum possible degree given the number of vertices n and diameter k respectively. These three problems are related but as far as we know not equivalent. In this paper we restrict our attention to digraphs of degree 2. Using new techniques we improve upon the bounds for N(d,k) and K(n,d) in the case of d = 2. The current state of knowledge of N(2,k) and K(n,2) (n≤100) is given in Tables 1 and 2. The paper concludes with eight open problems in the area.