並行計算

Concurrent computing — Grokipedia Fact-checked by Grok 3 months ago Concurrent computing Ara Eve Leo Sal 1x Concurrent computing is a paradigm in computer science where multiple computations execute during overlapping time periods, rather than sequentially one after another, enabling systems to handle several tasks simultaneously. [1] This approach involves defining actions or processes that may occur in parallel, often through multiple sequential programs running as independent execution units. [2] In modern computing, concurrent computing is essential due to the prevalence of multi-core processors, distributed systems, and user demands for responsive applications such as web servers, graphical user interfaces, and mobile apps. [1] It improves resource utilization, system throughput, and fault tolerance by allowing tasks to progress independently, particularly in environments with multiple users or networked components. [2] Key models for implementing concurrent computing include shared memory , where processes interact by reading and writing to common data structures, often protected by synchronization mechanisms like mutual exclusion to prevent conflicts; and message passing , where processes communicate via explicit messages over channels, supporting both synchronous and asynchronous interactions. [1] [2] These models underpin languages and systems like Java threads for shared memory or distributed protocols in networked applications. [1] However, concurrent computing introduces significant challenges, including race conditions where the outcome depends on unpredictable timing of events, deadlocks from circular resource dependencies, and difficulties in testing due to nondeterministic behavior. [1] [2] Addressing these requires careful design of synchronization primitives and verification techniques to ensure correctness and reliability. [2] Overview Definition and Fundamentals Concurrent computing refers to the paradigm in which multiple computational entities, such as processes or threads, execute over overlapping time periods to accomplish a shared objective, often requiring coordination to manage interactions and shared resources. This approach enables systems to handle multiple activities simultaneously, leveraging the capabilities of modern hardware like multi-core processors, though the actual execution may involve interleaving rather than strict simultaneity. Seminal work in the field emphasizes that concurrent programs consist of cooperating entities—such as processors, processes, agents, or sensors—that perform local computations and synchronize to avoid conflicts. [3] [4] Key terminology in concurrent computing includes processes , threads , and tasks . A process is defined as a program in execution, possessing its own independent address space and resources, allowing it to operate autonomously within an operating system. Threads, in contrast, are lightweight subunits of execution within a process, sharing the same memory space and resources, which facilitates efficient communication but introduces challenges in managing shared data access. A task represents a more abstract unit of work , encapsulating a sequence of operations that can be scheduled and executed independently, often serving as a building block for higher-level concurrency models. These concepts build on prerequisites from sequential programming, where instructions execute in a linear order, and operating systems, which provide mechanisms for resource allocation and scheduling. [5] [6] [7] A critical distinction exists between concurrency and parallelism. Concurrency focuses on the structure and management of multiple tasks whose executions overlap in time, enabling responsive and efficient systems even on single-processor hardware through interleaving. Parallelism, however, specifically entails the simultaneous execution of those tasks on multiple processing elements, exploiting hardware capabilities for performance gains. This separation highlights that while concurrency provides the framework for handling multiple activities, parallelism realizes true simultaneity when supported by the underlying architecture . [6] [8] Benefits and Motivations Concurrent computing offers significant performance gains by enabling the overlap of CPU-bound and I/O-bound tasks, thereby increasing overall throughput and reducing idle time in systems. For instance, while one task awaits input/output operations, the processor can execute another computation , preventing resource underutilization and achieving higher efficiency in single-processor environments. [9] This approach is particularly effective in environments where tasks have varying demands, allowing for seamless interleaving that boosts system speed without requiring additional hardware. [10] A key motivation for adopting concurrent computing is enhanced responsiveness, especially in interactive applications such as user interfaces, where background computations do not block foreground activities. By managing multiple threads or processes, systems maintain fluidity, ensuring users experience minimal delays even during intensive operations. [11] Furthermore, concurrency supports scalability in server environments by distributing workloads across resources, enabling the handling of increased user loads or data volumes without proportional performance degradation. [12] Resource efficiency is another compelling benefit, as concurrent programming better exploits multi-core processors and distributed systems, allowing parallel execution of independent tasks to maximize hardware utilization. This leads to improved energy efficiency and cost savings in large-scale deployments, such as data centers. [13] Certain concurrent languages, such as Concurrent Pascal, have demonstrated reduced programming effort for specific implementations compared to low-level languages, though concurrent programming generally introduces additional challenges in design and verification. [14] Concurrency Models Process and Thread Models In the process model of concurrent computing, each process operates within its own independent virtual address space , providing strong isolation between concurrent executions. This separation ensures that one process cannot directly access the memory of another, thereby enhancing fault tolerance and security, as a crash or malicious behavior in one process is contained without affecting others. However, communication between processes requires explicit inter-process communication (IPC) mechanisms, such as pipes for unidirectional data streams or shared memory regions for bidirectional access, which introduce overhead due to the need for kernel mediation and potential data copying. [15] The thread model, in contrast, allows multiple threads to execute concurrently within a single process , sharing the same address space and resources like code, data, and open files. This design facilitates efficient data sharing through direct memory access , reducing communication latency compared to IPC, and enables low-overhead creation and switching since threads maintain separate execution contexts (e.g., stacks and registers) but share the process's core structures. While this promotes scalability in resource utilization, it necessitates careful synchronization to prevent race conditions and data corruption from concurrent modifications. [16] Comparing the two models reveals significant trade-offs in performance and scalability. Process creation, such as via the fork() system call in Unix-like systems, involves duplicating the entire address space, leading to high overhead—often orders of magnitude greater than thread creation, where only lightweight thread control blocks are allocated. Context switching between processes requires flushing translation lookaside buffers (TLBs) and reloading address spaces, incurring latencies of tens to hundreds of microseconds, whereas thread switches within a process avoid these costs, typically completing in microseconds or less. For instance, early benchmarks on systems like DYNIX showed thread creation to be about 500 times cheaper than process creation. Scalability in both models is limited by inherent sequential portions of workloads, as described by Amdahl's law, which quantifies parallel speedup. The law derives from assuming a program fraction f f f executes serially while the remainder 1 − f 1-f 1 − f parallelizes across p p p processors; the maximum speedup S S S is then S = 1 f + 1 − f p S = \frac{1}{f + \frac{1-f}{p}} S = f + p 1 − f ​ 1 ​ , obtained by normalizing execution time such that serial time is f f f and parallel time per processor is 1 − f p \frac{1-f}{p} p 1 − f ​ . As p p p increases, S S S approaches 1 f \frac{1}{f} f 1 ​ , highlighting diminishing returns if f > 0 f > 0 f > 0 . [17] [18] [19] Representative implementations include the POSIX threads (pthreads) API for the thread model, standardized by IEEE as part of POSIX.1c, which provides functions like pthread_create() to spawn threads sharing the process address space. For processes, the fork() call in POSIX -compliant Unix-like systems creates a child process as a near-exact duplicate of the parent, enabling independent execution while inheriting resources until explicitly modified. These models contrast with message-passing approaches, where entities communicate without shared state. [20] [17] Message-Passing and Actor Models In the message-passing model, concurrent entities such as processes or nodes communicate by explicitly sending and receiving messages containing data or commands, without relying on shared mutable state. This approach isolates components, preventing direct access to each other's memory and thereby avoiding race conditions inherent in shared-memory systems. [21] Message passing can be synchronous, where the sender blocks until the receiver acknowledges receipt and processes the message, ensuring strict ordering and synchronization between sender and receiver. [2