6. Conclusion
The existence of a a-coloration of a graph is a necessary and sufficient condition for the existence of a solution to the class-teacher timetable problem with unavailability constraints and preassigned meetings. This condition allows existing graph coloring algorithms to be applied to timetable problems.
Acknowledgment: The authors thank the referees for their constructive criticism and helpful suggestions.
Received: July 1973, revised February 1974.
References:
1. Corneil, D.G., and Graham, B. An algorithm for determining the chromatic number of a graph.
2. Csima, J., and Gotlieb, C.C. A computer method for constructing school time-tables.
3. Dempster, M.A.H. On the Gotlieb-Csima time-tabling algorithm.
4. Dempster, M.A.H. Two algorithms for the time-table problem.
5. De Werra, D. Construction of school timetables by flow methods.
6. Formby, J.A. Computer procedure for bounding the chromatic number of a graph.
7. Gotlieb, C.C. The construction of class-teacher time-tables.
8. Lions, J. Matrix reduction using the Hungarian method for the construction of school timetables.
9. Lions, J. A counter-example for Gotlieb's method for the construction of school timetables.
10. Lions, J. A generalization of a method for the construction of class/teacher timetables.
11. Lions, J. The Ontario school scheduling program.
12. Lions, J. Some results concerning the reduction of binary matrices.
13. Neufeld, G.A., and Tartar, J. Generalized graph colorations.
14. Peck, J.E.L., and Williams, M.R. Algorithm 286, exam scheduling.
15. Welsh, D.J.A., and Powell, M.B. An upper bound for the chromatic number of a graph and its application to timetabling problems.
16. Williams, M.R. The coloring of very large graphs.
A New Solution of Dijkstra's Concurrent Programming Problem
Leslie Lamport
A simple solution to the mutual exclusion problem is presented, allowing the system to continue operating despite the failure of any individual component.
Key Words: critical section, concurrent programming, multiprocessing, semaphores.
Introduction:
Knuth, deBruijn, and Eisenberg and McGuire have given solutions to Dijkstra's concurrent programming problem. A simpler solution using semaphores has also been implemented. However, these solutions have a drawback: the failure of a single unit will halt the entire system.
The Algorithm:
Consider N asynchronous computers communicating via shared memory. Each computer runs a cyclic program with two parts: a critical section and a noncritical section. The problem is to write the programs so that the following conditions are satisfied:
1. At most one computer may be in its critical section at any time.
2. Each computer must eventually be able to enter its critical section (unless it halts).
3. Any computer may halt in its noncritical section.
The solution assumes N processors, each containing its own memory unit. A processor may read from any other processor's memory but need only write into its own memory. The algorithm has the property that if a read and a write operation to a single memory location occur simultaneously, then only the write operation must be performed correctly.
A processor may fail at any time, and when it fails, it immediately goes to its noncritical section and halts. The algorithm is a first-come-first-served method, where a processor is guaranteed to enter its critical section before any other processor that later requests service.
The algorithm is based on a bakery-like solution, where each processor chooses its own number, and the holder of the lowest number is the next one served. The common store consists of integer arrays choosling and number, where words choosing (i) and number (i) are in the memory of processor i and are initially zero.
The program for processor i is as follows:
begin integer choosling, number;
... (rest of the program)
The relation "less than" on ordered pairs of integers is defined by (a,b) < (c,d) if a < c, or if a = c and b < d.
