1 Advanced Topics in Software Engineering 1 Introduction  Overview  Motivating Examples  Interleaving Model  Semantics of Correctness  Testing, Debugging, and Verification Advanced Topics in Software Engineering 2 Concurrent Programs  Characterized by a set of cooperative processes or threads that can execute in parallel.  Three types of concurrent programs  multi-threaded programs: multiple threads running in a single process space  distributed programs: multiple processes running in a distributed environment  distributed multi-threaded programs: multiple processes running a distributed environment, and each process consists of multiple threads2 Advanced Topics in Software Engineering 3 Why Concurrency?  Better utilization of resources, which often leads to increased computation efficiency  Provides a natural model for many problem domains that are inherently concurrent  Allows computation to be distributed in a network environment So what is the catch? Advanced Topics in Software Engineering 4 How different?  Three fundamental issues in concurrent programming  nondeterminism  synchronization  communication  Note that synchronization can be considered as a special case of communication.3 Advanced Topics in Software Engineering 5 Nondeterminism  An inherent property of concurrent programs - two executions of the same program with the same input may produce different, and sometimes unpredictable, results.  Caused by one or more of the following factors:  the unpredictable rates of progress of threads  the unpredictable network latency  the explicit use of nondeterministic programming constructs Advanced Topics in Software Engineering 6 Synchronization  Enforces a certain order on tasks that are performed by different threads/processes  Mutual exclusion ensures that critical sections in different threads do not execute at the same time.  Conditional synchronization delays a thread until a given condition is true.  Mutual exclusion is a special case of conditional synchronization.4 Advanced Topics in Software Engineering 7 Communication  Exchange data between threads/processes that are running in parallel  shared variables - a thread writes into a variable that is read by another thread.  message passing - a thread sends a message that is received by another thread. Advanced Topics in Software Engineering 8 Process and Thread In general, a process is a program in execution. A thread is a unit of control within a process. When a program is executed, the operating system creates a process. A process starts with a running thread, called the “main” thread, which executes the “main function” of the program. Other threads can be created by the main thread, and these threads can create other threads.5 Advanced Topics in Software Engineering 9 Process vs. Thread A process has its own stream of instructions and its own logical address space. A thread has its own stream of instructions, but shares the same logic address space with other threads in the same process. This difference has significant implications on how processes and threads communicate. Advanced Topics in Software Engineering 10 Introduction  Overview  Motivating Examples  Interleaving Model  Semantics of Correctness  Testing, Debugging, and Verification6 Advanced Topics in Software Engineering 11 Example 1 Assume that integer x is initially 0. Thread 1 Thread 2 Thread 3 (1) x = 1; (2) x = 2; (3) y = x; What is the final value of y?  (1) (2) (3)  (2) (1) (3)  (3) (2) (1) Advanced Topics in Software Engineering 12 Example 2 Assume that y and z are initially 0. Thread 1 Thread 2 x = y + z y = 1; z = 2; What is the final value of x?7 Advanced Topics in Software Engineering 13 1. (1), (2), (3), (4), (5) 2. (4), (1), (2), (3), (5) 3. (1), (4), (5), (2), (3) 4. (4), (5), (1), (2), (3) Example 2 Thread 1 (1) load r1, y (2) add r1, z (3) store r1, x Thread 2 (4) assign y, 1 (5) assign z, 2 Advanced Topics in Software Engineering 14 Example 3 Assume that the initial value of x is 0. Thread 1 Thread 2 x = x + 1; x = 2; What is the final value of x?8 Advanced Topics in Software Engineering 15 Example 3 Thread 1 (1) load r1, x (2) add r1, 1 (3) store r1, x Thread 2 (4) assign x, 2 1. (1), (2), (3), (4) 2. (4), (1), (2), (3) 3. (1), (2), (4), (3) Advanced Topics in Software Engineering 16 Example 4 Consider a linked list of Nodes, pointed to by variable first, and accessed by methods deposit and withdraw. class Node { public int value; public Node* next; } Node* first; void deposit (int value) { Node p = new Node (); // (1) p.value = value; // (2) p.next = first; // (3) first = p; // (4) } int withdraw () { int value = first -> value; // (5) first = first -> next; // (6) return value; // (7) } Can you find a scenario which produces unexpected results?9 Advanced Topics in Software Engineering 17 Example 4 Suppose that the linked list pointed to by first is not empty and that methods deposit and withdraw are executed concurrently by two threads. In the following possible scenario, the deposited item has been lost. int value = first -> value; (5) in withdraw Node p = new Node (); (1) in deposit p.value = value; (2) in deposit p.next = first; (3) in deposit first = p; (4) in deposit first = first -> next; (6) in withdraw return value; (7) in withdraw Advanced Topics in Software Engineering 18 Introduction  Overview  Motivating Examples  Interleaving Model  Semantics of Correctness  Testing, Debugging, and Verification10 Advanced Topics in Software Engineering 19 They actually take turns ... A multithreaded process consists of a set of threads that execute simultaneously. However, a single CPU can only execute one instruction (from one thread) at a time. In general, each thread receives a time slice of the CPU. Threads that execute simultaneously actually take turns to run. Advanced Topics in