How to solve the Santa Claus problem

✍ Scribed by BEN-ARI, MORDECHAI

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 73 KB
• Volume: 10
• Category: Article
• ISSN: 1040-3108
• DOI: 10.1002/(sici)1096-9128(199805)10:6<485::aid-cpe329>3.0.co;2-2

✦ Synopsis

John Trono (1994) published a new exercise in concurrent programming -the Santa Claus problem -and provided a solution based on semaphores. His solution is incorrect because it assumes that a process released from waiting on a semaphore will necessarily be scheduled for execution. We give a simple solution in Ada 95 using higher-order synchronization primitives: protected objects and rendezvous. We then give a solution in Java, although this solution is not as elegant as the Ada 95 solution because the Java synchronization primitives are rather limited. The problem demonstrates that semaphores, designed for low-level mutual exclusion, are not appropriate for solving difficult concurrent programming problems.