Chapter 13: Concurrency Lecture Notes PDF

Chapter 13: Concurrency Lecture # 15 Prof. Nidal F. Shilbayeh Dr. Asim Abdallah Elshiekh  Chapter 13 Topics Introduction Introduction to Subprogram-Level Concurrency Semaphores M...

Chapter 13: Concurrency Lecture # 15 Prof. Nidal F. Shilbayeh Dr. Asim Abdallah Elshiekh  Chapter 13 Topics Introduction Introduction to Subprogram-Level Concurrency Semaphores Monitors Message Passing Chapter 13: Concurrency Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 2  Introduction Concurrency can occur at four levels:  Machine instruction level.  High-level language statement level.  Unit level.  Program level. Chapter 13: Concurrency Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 3  Categories of Concurrency Categories of Concurrency:  Physical concurrency:  More than one processor is available, several program units in the same program is executed concurrently.  Logical concurrency:  Is presented by time-sharing one processor. Chapter 13: Concurrency Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 4  Motivations for Studying Concurrency Many real-world situations involve concurrency. Multiprocessor computers capable of physical concurrency are now widely used. Chapter 13: Concurrency Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 5  Introduction to Subprogram-Level Concurrency A task or process is a program unit that can be in concurrent execution with other program units. Tasks differ from ordinary subprograms in that:  A task may be implicitly started.  When a program unit starts the execution of a task, it is not necessarily suspended.  When a task’s execution is completed, control may not return to the caller. Tasks usually work together. Chapter 13: Concurrency Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 6  Two General Categories of Tasks Heavyweight tasks execute in their own address space. Lightweight tasks all run in the same address space. A task is disjoint if it does not communicate with or affect the execution of any other task in the program in any way. Chapter 13: Concurrency Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 7  Task Synchronization Task Synchronization is a mechanism that controls the order in which tasks execute. Two kinds of synchronization:  Cooperation synchronization.  Competition synchronization. Chapter 13: Concurrency Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 8  Kinds of Synchronization Cooperation:  Task A must wait for task B to complete some specific activity before task A can continue its execution.  e.g., the producer-consumer problem. Competition:  Two or more tasks must use some resource that cannot be simultaneously used.  e.g., a shared counter. Chapter 13: Concurrency Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 9  Need for Competition Synchronization Chapter 13: Concurrency Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 10  Scheduler Providing synchronization requires a mechanism for delaying task execution. Task execution control is maintained by a program called the scheduler, which maps task execution onto available processors. Chapter 13: Concurrency Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 11  Task Execution States New: created but not yet started. Ready: ready to run but not currently running (no available processor). Running. Blocked: has been running, but cannot now continue (usually waiting for some event to occur). Dead: no longer active in any sense. Chapter 13: Concurrency Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 12  Liveness and Deadlock Liveness is a characteristic that a program unit may or may not have. o In sequential code, it means the unit will eventually complete its execution. In a concurrent environment, a task can easily lose its liveness. If all tasks in a concurrent environment lose their liveness, it is called deadlock. Chapter 13: Concurrency Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 13  Design Issues for Concurrency Competition and cooperation synchronization. Controlling task scheduling. How and when tasks start and end execution. How and when are tasks created. Chapter 13: Concurrency Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 14  Methods of Providing Synchronization Semaphores. Monitors. Message Passing. Chapter 13: Concurrency Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 15  Cooperation Synchronization with Semaphores Example: A shared buffer. The buffer is implemented as an ADT with the operations DEPOSIT and FETCH as the only ways to access the buffer. Use two semaphores for cooperation: emptyspots and fullspots. The semaphore counters are used to store the numbers of empty spots and full spots in the buffer. Chapter 13: Concurrency Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 16  Competition Synchronization with Semaphores A semaphore, named access, is used to control access (competition synchronization).  The counter of access will only have the values 0 and 1.  access = 1, indicates that the shared buffer is not currently being accessed, and the task is allowed to access it.  If access = 0, there is a current access taking place, and the task is placed in the queue of the semaphore.  Such a semaphore is called a binary semaphore. Chapter 13: Concurrency Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 17  Monitors Monitors are supported by Ada, Java, and C#. The idea: encapsulate the shared data and its operations to restrict access. A monitor is an abstract data type for shared data. Chapter 13: Concurrency Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 18  Message Passing Message passing is a general model for concurrency. It is a form of communication. In this model, processes can send and receive messages to/from other processes. It can be used for cooperation and competition synchronization. Chapter 13: Concurrency Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 19  Task Termination The execution of a task is completed if control has reached the end of its code body. If a task has created no dependent tasks and is completed, it is terminated. If a task has created dependent tasks and is completed, it is not terminated until all its dependent tasks are terminated. Chapter 13: Concurrency Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 20  Summary Concurrent execution can be at the instruction, statement, or subprogram level. Physical concurrency: when multiple processors are used to execute concurrent units. Logical concurrency: concurrent units are executed on a single processor. Two primary facilities to support subprogram concurrency: competition synchronization and cooperation synchronization. Mechanisms: semaphores, monitors, message passing. Chapter 13: Concurrency Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 21