Programming Language Concept

Just another Binusian blog site

Session 10 : Concurrency

December16

Introduction

  • Concurrency can occur at four levels:

–Machine instruction level

–High-level language statement level

–Unit level

–Program level

  • Because there are no language issues in instruction- and program-level concurrency, they are not addressed here

Introduction to Subprogram-Level Concurrency

  • A task or process or thread 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

Semaphores

  • Dijkstra – 1965
  • A semaphore is a data structure consisting of a counter and a queue for storing task descriptors

–A task descriptor is a data structure that stores all of the relevant information about the execution state of the task

  • Semaphores can be used to implement guards on the code that accesses shared data structures
  • Semaphores have only two operations, wait and release (originally called P and V by Dijkstra)
  • Semaphores can be used to provide both competition and cooperation synchronization

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
  • DEPOSIT must first check emptyspots to see if there is room in the buffer
  • If there is room, the counter of emptyspots is decremented and the value is inserted
  • If there is no room, the caller is stored in the queue of emptyspots
  • When DEPOSIT is finished, it must increment the counter of fullspots
  • FETCH must first check fullspots to see if there is a value–If there is a full spot, the counter of fullspots is decremented and the value is removed

    –If there are no values in the buffer, the caller must be placed in the queue of fullspots

    –When FETCH is finished, it increments the counter of emptyspots

  • The operations of FETCH and DEPOSIT on the semaphores are accomplished through two semaphore operations named wait and release

Monitors

  • Ada, Java, C#
  • The idea: encapsulate the shared data and its operations to restrict access
  • A monitor is an abstract data type for shared data

Message Passing

  • Message passing is a general model for concurrency

–It can model both semaphores and monitors

–It is not just for competition synchronization

  • Central idea: task communication is like seeing a doctor–most of the time she waits for you or you wait for her, but when you are both ready, you get together, or rendezvous

Message Passing: Server/Actor Tasks

  • A task that has accept clauses, but no other code is called a server task (the example above is a server task)
  • A task without accept clauses is called an actor task

–An actor task can send messages to other tasks

–Note: A sender must know the entry name of the receiver, but not vice versa (asymmetric)

Message Passing Priorities

  • The priority of any task can be set with the pragma Priority

pragma Priority (static expression);

  • The priority of a task applies to it only when it is in the task ready queue

Email will not be published

Website example

Your Comment: