page_title: Edsger W. Dijkstra
section_title: Concurrent computing and programming
hierarchical_section_title: Edsger W. Dijkstra / Pioneering contributions and impact on computing science / Concurrent computing and programming
caption_attribution_description: English: A British lower-quadrant semaphore stop signal with subsidiary arm below. Español: Señal inglesa de parada con semáforo de cuadrante inferior y auxiliar de brazo por debajo. Source: https://www.flickr.com/photos/frield/30608398/ by User: https://www.flickr.com/people/frield/ Uploaded by -=# Amos E Wolfe talk #=- 18:22, 4 July 2006 (UTC)
context_page_description: Edsger Wybe Dijkstra was a Dutch computer scientist, programmer, software engineer, systems scientist, science essayist, and pioneer in computing science. A theoretical physicist by training, he worked as a programmer at the Mathematisch Centrum from 1952 to 1962. A university professor for much of his life, Dijkstra held the Schlumberger Centennial Chair in Computer Sciences at the University of Texas at Austin from 1984 until his retirement in 1999. He was a professor of mathematics at the Eindhoven University of Technology and a research fellow at the Burroughs Corporation. In 1972, he became the first non-American and non-British to win the Turing Award.
  One of the most influential figures of computing science's founding generation, Dijkstra helped shape the new discipline from both an engineering and a theoretical perspective.
context_section_description: In a one-page paper from 1965 Dijkstra introduced the 'mutual exclusion problem' for n processes and discussed a solution to it. It was probably the first published concurrent algorithm. The notion, standard by now, of a 'critical section' was also introduced in this paper. Per Brinch Hansen, a pioneer in the field of concurrent computing, considers Dijkstra's Cooperating Sequential Processes (1965) to be the first classic paper in concurrent programming. As Brinch Hansen notes, 'Dijkstra lays the conceptual foundation for abstract concurrent programming' with that paper.
  In 1968 Dijkstra published his seminal paper 'Cooperating sequential processes', a 70-page essay that originated the field of concurrent programming. He discussed in it the notion of mutual exclusion (mutex) and the criteria a satisfactory solution should satisfy. He also redressed the historical perspective left out of his 1965 paper by including the first known correct solution to the mutual exclusion problem, for two processes, due to Theodorus Dekker. Dijkstra subsequently generalized Dekker's solution to n processes. Further, he proposed the first synchronisation mechanism for concurrent processes, the semaphore with its two operations, P and V. He also identified the 'deadlock problem' (called there 'the problem of the deadly embrace') and proposed an elegant 'Banker's algorithm' that prevents deadlock. The deadlock detection and prevention became perennial research problems in the field of concurrent programming.
  The dining philosophers problem is an example problem often used in concurrent algorithm design to illustrate synchronization issues and techniques for resolving them. It was originally formulated in 1965 by Dijkstra as a student exam exercise, presented in terms of computers competing for access to tape drive peripherals. Soon after, Tony Hoare gave the problem its present formulation. The sleeping barber problem is also attributed to Dijkstra.
  In his book Concurrent Programming: Algorithms, Principles, and Foundations Michel Raynal writes, "Since the early work of E.W. Dijkstra (1965), who introduced the mutual exclusion problem, the concept of a process, the semaphore object, the notion of a weakest precondition, and guarded commands (among many other contributions), synchronization is no longer a catalog of tricks but a domain of computing science with its own concepts, mechanisms, and techniques whose results can be applied in many domains. This means that process synchronization has to be a major topic of any computer science curriculum."
  John W. McCormick et al. (2011) notes, "The notion of the concurrent program as a means for writing parallel programs without regard for the underlying hardware was first introduced by Edsger Dijkstra (1968). Moti Ben-Ari (1982) elegantly summed up Dijkstra's idea in three sentences: ‘Concurrent programming is the name given to programming notation and techniques for expressing potential parallelism and solving the resulting synchronization and communication problems. Implementation of parallelism is a topic in computer systems (hardware and software) that is essentially independent of concurrent programming. Concurrent programming is important because it provides an abstract setting in which to study parallelism without getting bogged down in the implementation details.’"
caption: A semaphore (Dutch: seinpaal, the term used in Dijkstra's original description[76]). In the early 1960s Dijkstra proposed the first synchronisation mechanism for concurrent processes, the semaphore with its two operations, P and V.
exif: {"Image Make": "Canon", "Image Model": "Canon EOS 300D DIGITAL", "Image XResolution": "180", "Image YResolution": "180", "Image ResolutionUnit": "Pixels/Inch", "Image DateTime": "2005:08:02 09:28:02", "Image YCbCrPositioning": "Centered", "Image Tag 0x1001": "3072", "Image Tag 0x1002": "2048", "Image ExifOffset": "248", "Image CustomRendered": "Normal", "Image ExposureMode": "Auto Exposure", "Image WhiteBalance": "Auto", "Image SceneCaptureType": "Standard", "Thumbnail Compression": "JPEG (old-style)", "Thumbnail XResolution": "180", "Thumbnail YResolution": "180", "Thumbnail ResolutionUnit": "Pixels/Inch", "Thumbnail JPEGInterchangeFormat": "2452", "Thumbnail JPEGInterchangeFormatLength": "7176", "EXIF ExposureTime": "1/400", "EXIF FNumber": "13", "EXIF ISOSpeedRatings": "200", "EXIF ExifVersion": "0221", "EXIF DateTimeOriginal": "2005:08:02 09:28:02", "EXIF DateTimeDigitized": "2005:08:02 09:28:02", "EXIF ComponentsConfiguration": "YCbCr", "EXIF CompressedBitsPerPixel": "3", "EXIF ShutterSpeedValue": "141621/16384", "EXIF ApertureValue": "15157/2048", "EXIF ExposureBiasValue": "1/3", "EXIF MaxApertureValue": "4", "EXIF MeteringMode": "Pattern", "EXIF Flash": "Flash did not fire", "EXIF FocalLength": "109", "EXIF FlashPixVersion": "0100", "EXIF ColorSpace": "sRGB", "EXIF ExifImageWidth": "2048", "EXIF ExifImageLength": "3072", "EXIF FocalPlaneXResolution": "409600/119", "EXIF FocalPlaneYResolution": "768000/223", "EXIF FocalPlaneResolutionUnit": "2", "EXIF SensingMethod": "One-chip color area", "EXIF FileSource": "Digital Camera"}