VP: a new operation for semaphores

ABSTRACT

A semaphore is a non-negative integer variable on which only operations P and V are allowed. The semaphore construct (with various extensions) is supported by many operating systems and is often used to implement other synchronization constructs. Since the semaphore construct is low-level, a semaphore-based program may contain synchronization errors that are very difficult to detect. In this paper, we propose a new operation VP (s1,s2), where s1 and s2 are distinct or identical semaphores. An execution of VP(s1,s2) by a process T is equivalent to that of "V (s1); P(s2)" except that when T starts the V (s1) operation, T is guaranteed to be the next process to access s2 (i.e., T will execute the P(s2) operation before another process executes a P(s2) or V(s2) operation.) Section 2 shows several examples to illustrate the advantages of the VP operation. Section 3 concludes this paper. In this paper, we assume that the queue for a semaphore is first-in-first-out and that the order of processes blocked in a semaphore queue is the same order in which they executed P operations on the semaphore. We also assume that the scheduling of processes in a concurrent program is fair, i.e., each process ready for execution will eventually be selected as the running process. Programs in this paper use Ada-like syntax.

REFERENCES

• 1: Gregory R. Andrews, Concurrent programming: principles and practice, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1991
• 2: Richard H. Carver , Kuo-Chung Tai, Replay and Testing for Concurrent Programs, IEEE Software, v.8 n.2, p.66-74, March 1991 [doi>10.1109/52.73751]
• 3: [3] Kessels, J. L. W. and Martin, A. J., "Two implementations of the conditional critical region using a split binary semaphore", Information Processing Letters, Vol. 8, No. 2, Feb. 1979, 67-71.
• 4: Abraham Silberschatz , James L. Peterson , Peter B. Galvin, Operating system concepts (3rd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 5: C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [doi>10.1145/355620.361161]
• 6: Kuo-Chung Tai, Definitions and Detection of Deadlock, Livelock, and Starvation in Concurrent Programs, Proceedings of the 1994 International Conference on Parallel Processing, p.69-72, August 15-19, 1994 [doi>10.1109/ICPP.1994.84]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Queueing theory

General Terms:
Design, Management, Performance