Concurrency

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

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

–Competition is usually provided by mutually exclusive access  (approaches are discussed later)    

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

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

Object-Oriented Programming

If you are new to object-oriented programming languages, you will need to know a few basics before you can get started with code. The following Webopedia definitions will help you better understand object-oriented programming:

• Abstraction: The process of picking out (abstracting) common features of objects and procedures.
• Class: A category of objects. The class defines all the common properties of the different objects that belong to it.
• Encapsulation: The process of combining elements to create a new entity. A procedure is a type of encapsulation because it combines a series of computer instructions.
• Information hiding: The process of hiding details of an object or function. Information hiding is a powerful programming technique because it reduces complexity.
• Inheritance: a feature that represents the "is a" relationship between different classes.
• Interface: the languages and codes that the applications use to communicate with each other and with the hardware.
• Messaging: Message passing is a form of communication used in parallel programming and object-oriented programming.
• Object: a self-contained entity that consists of both data and procedures to manipulate the data.
• Polymorphism: A programming language's ability to process objects differently depending on their data type or class.
• Procedure: a section of a program that performs a specific task.

Advantages of Object Oriented Programming

One of the principal advantages of object-oriented programming techniques over procedural programming techniques is that they enable programmers to create modules that do not need to be changed when a new type of object is added. A programmer can simply create a new object that inherits many of its features from existing objects. This makes object-oriented programs easier to modify.

OOPL - Object Oriented Programming Languages

An object-oriented programming language (OOPL) is a high-level programming language based on the object-oriented model. To perform object-oriented programming, one needs an object-oriented programming language.  Many modern programming languages are object-oriented, however some older programming languages, such as Pascal, do offer object-oriented versions. Examples of object-oriented programming languages include Java, C++and Smalltalk.

The First  OOPL

Simula, developed in the 1960s at the Norwegian Computing Center in Oslo, is considered to be the first object-oriented programming language. Despite being first, Smalltalk is considered to be the only true object-oriented programming environment and the one against which all others must be compared. It was first developed for educational use at Xerox Corporation's Palo Alto Research Center in the late 1960s and released in 1972.

Abstract Data Type

Abstract Data type (ADT)

Is a type (or class) for objects whose behavior is defined by a set of value and a set of operations.
The definition of ADT only mentions what operations are to be performed but not how these operations will be implemented. It does not specify how data will be organized in memory and what algorithms will be used for implementing the operations. It is called “abstract” because it gives an implementation independent view. The process of providing only the essentials and hiding the details is known as abstraction.
The user of data type need not know that data type is implemented, for example, we have been using int, float, char data types only with the knowledge with values that can take and operations that can be performed on them without any idea of how these types are implemented. So a user only needs to know what a data type can do but not how it will do it. We can think of ADT as a black box which hides the inner structure and design of the data type. Now we’ll define three ADTs namely List ADT, Stack ADT, Queue ADT.

List ADT

A list contains elements of same type arranged in sequential order and following operations can be performed on the list.
get() – Return an element from the list at any given position.
insert() – Insert an element at any position of the list.
remove() – Remove the first occurrence of any element from a non-empty list.
removeAt() – Remove the element at a specified location from a non-empty list.
replace() – Replace an element at any position by another element.
size() – Return the number of elements in the list.
isEmpty() – Return true if the list is empty, otherwise return false.
isFull() – Return true if the list is full, otherwise return false.

Stack ADT

A Stack contains elements of same type arranged in sequential order. All operations takes place at a single end that is top of the stack and following operations can be performed:
push() – Insert an element at one end of the stack called top.
pop() – Remove and return the element at the top of the stack, if it is not empty.
peek() – Return the element at the top of the stack without removing it, if the stack is not empty.
size() – Return the number of elements in the stack.
isEmpty() – Return true if the stack is empty, otherwise return false.
isFull() – Return true if the stack is full, otherwise return false.

Queue ADT

A Queue contains elements of same type arranged in sequential order. Operations takes place at both ends, insertion is done at end and deletion is done at front. Following operations can be performed:
enqueue() – Insert an element at the end of the queue.
dequeue() – Remove and return the first element of queue, if the queue is not empty.
peek() – Return the element of the queue without removing it, if the queue is not empty.
size() – Return the number of elements in the queue.
isEmpty() – Return true if the queue is empty, otherwise return false.
isFull() – Return true if the queue is full, otherwise return false.

From these definitions, we can clearly see that the definitions do not specify how these ADTs will be represented and how the operations will be carried out. There can be different ways to implement an ADT, for example, the List ADT can be implemented using arrays, or singly linked list or doubly linked list. Similarly, stack ADT and Queue ADT can be implemented using arrays or linked lists.

Subprogram

Fundamentals of Subprograms

•Each subprogram has a single entry point

•The calling program is suspended during execution of the called subprogram

•Control always returns to the caller when the called subprogram’s execution terminates

Local Referencing Environments

•Local variables can be stack-dynamic

     - Advantages

•Support for recursion

•Storage for locals is shared among some subprograms

–Disadvantages

•Allocation/de-allocation, initialization time

•Indirect addressing

•Subprograms cannot be history sensitive

•Local variables can be static

–Advantages and disadvantages are the opposite of those for stack-dynamic local variables

Implementing Parameter-Passing Methods

•In most languages parameter communication takes place thru the run-time stack

•Pass-by-reference are the simplest to implement; only an address is placed in the stack

Design Considerations for Parameter Passing

•Two important considerations

–Efficiency

–One-way or two-way data transfer

•But the above considerations are in conflict

–Good programming suggest limited access to variables, which means one-way whenever possible

–But pass-by-reference is more efficient to pass structures of significant size

Control structures and statements

Repetition Statements

• Repetition statements are called loops, and are used to repeat the same code mulitple times in succession.
• The number of repetitions is based on criteria defined in the loop structure, usually a true/false expression
• The three loop structures in C++ are:
  • while loops
  • do-while loops
  • for loops
• Three types of loops are not actually needed, but having the different forms is convenient

while and do-while loops

• Format of while loop:

  
   while (expression) 
      statement 
  

• Format of do/while loop:

  
   do 
      statement 
   while (expression); 
  

• The expression in these formats is handled the same as in the if/else statements discussed previously (0 means false, anything else means true)
• The "statement" portion is also as in if/else. It can be a single statement or a compund statement (a block { } ).
• We could also write the formats as follows (illustrating more visually what they look like when a compound statement makes up the loop "body"):

   // while loop format
   while (expression) 
   {
      statement1;
      statement2;
      // ...
  
      statementN;
   } 
  
   // do-while loop format
   do
   {
      statement1;
      statement2;
      // ...
  
      statementN;
   } while (expression);
  

• HOW THEY WORK
  • The expression is a test condition that is evaluated to decide whether the loop should repeat or not.
    • true means run the loop body again.
    • false means quit.
  • The while and do/while loops both follow the same basic flowchart -- the only exception is that:
    • In a while loop, the expression is tested first
    • In a do/while loop, the loop "body" is executed first

---

Examples

Both of the following loops add up all of the numbers between 1 and 50.

 // while loop example 
 // loop body runs 50 times, condition checked 51 times 
 int i = 1, sum = 0; 
 while (i <= 50) 
 { 
    sum += i;  // means:  sum = sum + i; 
    i++;   // means:  i = i + 1;
 } 

 cout << "Sum of numbers from 1 through 50 is " << sum; 
  

 // do/while loop example 
 // loop body runs 50 times, condition checked 50 times 
 int i = 1, sum = 0; 
 do 
 { 
    sum += i;  // means:  sum = sum + i; 
    i++;   // means:  i = i + 1;
 } while (i <= 50); 

 cout << "Sum of numbers from 1 through 50 is " << sum; 

---

The for loop

• The for loop is most convenient with counting loops -- i.e. loops that are based on a counting variable, usually a known number of iterations
• Format of for loop:

  
   for (initialCondition; testExpression; iterativeStatement) 
      statement 
  

• Remember that the statement can be a single statement or a compound statement (block), so an alternate way to write the format might be:

  
   for (initialCondition; testExpression; iterativeStatement) 
   {
      statement1;
      statement2;
      // ...
  
      statementN;
   }
  

• How it works
  • The initialCondition runs once, at the start of the loop
  • The testExpression is checked. (This is just like the expression in a while loop). If it's false, quit. If it's true, then:
    • Run the loop body
    • Run the iterativeStatement
    • Go back to the testExpression step and repeat

---

Examples of for loops

• Recall this while loop example, which adds the numbers from 1 to 50:

   int i = 1, sum = 0; 
   while (i <= 50) 
   { 
      sum += i; 
      i++; 
   } 
  
   cout << "Sum of numbers from 1 through 50 is " << sum; 
  

  Here's a for loop that does the same job:

   // for loop example 
   // loop body runs 50 times, condition checked 51 times 
   int i, sum = 0; 
   for (i = 1; i <= 50; i++) 
   { 
      sum += i; 
   } 
  
   cout << "Sum of numbers from 1 through 50 is " << sum; 
  

• This loop prints out the word "Hello" 10 times:

    for (int i = 0; i < 10; i++)
      cout << "Hello\n";
  

  So does this one

    for (int i = 1; i <= 10; i++)
      cout << "Hello\n";
  

• A few common types of algorithms using for-loops:
  • A counting algorithm
  • A summing algorithm -- Adding up something with a loop
  • A product algorithm -- Multiplying things with a loop
• Examples using nested loops:
  • Simple nested loop example
  • Prints out a rectangle
  • Prints out a triangle

---

Special notes about for loops:

1. It should be noted that if the control variable is declared inside the for header, it only has scope through the for loop's execution. Once the loop is finished, the variable is out of scope:

       for (int counter = 0; counter < 10; counter++) 
       {
          // loop body    
       } 
   
       cout << counter; // illegal.  counter out of scope
   

   This can be avoided by declaring the control variable before the loop itself.

       int counter;    // declaration of control variable 
   
       for (counter = 0; counter < 10; counter++) 
       {
          // loop body    
       } 
   
       cout << counter; // OK.  counter is in scope
   

2. For loops also do not have to count one-by-one, or even upward. Examples:

       for (i = 100; i > 0; i--)
   
       for (c = 3; c <= 30; c+=4)
   

   The first example gives a loop header that starts counting at 100 and decrements its control variable, counting down to 1 (and quitting when i reaches 0).  The second example shows a loop that begins counting at 3 and counts by 4's (the second value of c will be 7, etc).

---

Special statements: break and continue

• These statements can be used to alter the flow of control in loops, although they are not specifically needed. (Any loop can be made to exit by writing an appropriate test expression).
• break: This causes immediate exit from any loop (as well as from switch blocks)
  • An example of break
• continue: When used in a loop, this statement causes the current loop iteration to end, but the loop then moves on to the next step.
  • In a while or do-while loop, the rest of the loop body is skipped, and execution moves on to the test condition
  • In a for loop, the rest of the loop body is skipped, and execution moves on to the iterative statement

Expression dan Assignment Statements

1. Expression

Expression adalah hal – hal mendasar dalam proses perhitungan di dalam bahasa pemrograman. Expression adalah susunan yang terdiri dari operand dan operator. Sedangkan Assignment statement adalah statement yang terdiri dari asiignment operator (=) yang berfungsi untuk menetapkan/menstore nilai dari hasil sebuah expression pada sebuah variabel. Penulisan code sederhananya dapat ditulis :

variabel = expression;

contohnya :

int a = b * 2 + 1;

Untuk dapat lebih memahami expression evaluation maka kita harus lebih dahulu mengenal dan memahami urutan dari operator dan operand evaluation.

1. Arithmetic Expression

Arithmetic Expression terdiri dari operator, operand, parentheses, dan function call.

Operator adalah simbol untuk memproses nilai/beberapa nilai yang akan menghasilkan suatu nilai yang baru. Arithmetic operator sendiri dibagi menjadi tiga, yaitu :

• Unary operator, operator yang hanya mempunyai 1 operand
• Binary operator, operator yang memiliki 2 operand
• Ternary operator, operator yang memiliki 3 operand

Unary Arithmetic Operators dalam Java

Unary Plus ( +A ) : mengindikasikan sebuah variabel/nilai adalah positif (tidak digunakan juga berarti sama)

Contoh : +num, +num / 5, num1 * +num2

Unary Minus ( – A ) : menindikasikan bahwa sebuah variabel/nilai bernilai negatif

Contoh : -num,  -num / 5, num1 * -num2

Pre-increment Operator: menambah nilai operator secara langsung tanpa harus menunggu eksekusi berikutnya. Contoh syntax  ++<variable-name>

Post-increment Operator: menambah Nilai operand yang tersimpan pada memori yang akan berubah pada eksekusi berikutnya. Contoh syntax  <variable-name>++

Pre-decrement Operator: mengurangi nilai operand secara langsung tanpa harus menunggu eksekusi berikutnya. Contoh syntax – -<variable-name>

Post-decrement Operator: mengurangi Nilai operand yang tersimpan pada memori yang akan berubah pada eksekusi berikutnya. Contoh syntax  <variable-name> – –

Binary Arithmetic Operators dalam Java

Arithmetic Operation digunakan untuk melakukan operasi matematika, seperti penambahan, pengurangan, pembagian, dan modulus (sisa pembagian), namun bisa juga digunakan untuk menggabungkan string

Simbol	Nama Operator	Contoh
+	Penjumlahan	a = b + c
–	Pengurangan	a = b – c
*	Perkalian	a = b * c
/	Pembagian	a = b / c
%	Modulus	a = b % c
+	Penggabungan String	a = “Hello “ + “World”

Tabel V.A.1.1: Operator dalam Java

Ternary Operators dalam Java

Dipakai dalam conditional statements dengan sintaks (Condition) ? (kondisi jika true) : (kondisi jika false)

Contoh :          int score; char status;

status = (score >= 70)? ‘P’ : ‘F’ ;      // P =>pass, F =>failed

2. Aturan Presedence dan Associativity dalam Operator

Presedence adalah aturan urutan eksekusi operator berdasarkan tingkat prioritasnya, dimana operator yang memiliki tingkat presedence paling tinggi akan dieksekusi lebih dulu. Sedangkan Assosiative adalah aturan urutan eksekusi operator berdasarkan lokasinya pada suatu expression (dari kiri/kanan), dimana Assosiative ini dipakai dalam operator dengan tingkat presedence yang sama. Berikut adalah tabel urutan presedence dan assosiative:

Tabel V.A.2.1: Presedence dan Assosiative

3. Operand Evaluation Order

Operand Evaluation Order adalah aturan urutan pengambilan nilai suatu operand dari memory. Dalam Java, operand evaluation ordernya dari kiri ke kanan dalam suatu expression.

4. Overloaded Operator

Overloaded Operator adalah operator yang digunakan untuk lebih dari satu tujuan. Dalam Java tidak diperbolehkan menggunakan user-defined overloaded.

5. Type Convertion

Type Convertion adalah cara merubah suatu tipe data ke tipe data lain, dapat terbagi menjadi 2 jenis yaitu narrowing convertion (merubah tipe data sehingga nilai yang terambil tidak mencakup seluruh nilai tipe data awal contohnya dari double ke float) dan widening convertion (konversi yang dapat mencakup setidaknya sama dengan nilai tipe data awal contohnya int ke float). Sedangkan jika berdasarkan cara konversinya juga terbagi 2 yaitu secara implisit (terkonversi secara otomatis, biasa terjadi dalam mix mode yaitu ketika ada 2 tipe data berlainan dalam suatu expression) dan eksplisit (dikonversi oleh programmer dengan coding atau biasa disebut casting).

Dalam Java, konversi secara implisit hanya terjadi ketika mix mode assignmentnya berjenis widening. Berikut adalah contohnya.

Gambar V.A.5.1: Contoh Widening Convertion

Sedangkan untuk narrowing conversion dalam Java harus menggunakan konversi secara eksplisit, berikut contoh cara konversi secara eksplisit dalam Java:

Gambar V.A.5.2: Contoh Narrowing Convertion

6. Boolean Expressions

Bahasa pemrograman Java memiliki tipe data boolean, yaitu tipe data yang memiliki nilai true atau false.

7. Relational Expressions

Expression yang membandingkan dua nilai operand dimana hasilnya adalah tipe data boolean (true atau false). Berikut adalah relational (equality) operator dan contoh programnya dalam Java :

==      Equal to!=      Not equal to>       Greater than>=      Greater than or equal to<       Less than<=      Less than or equal to

Gambar V.A.7.1: Contoh Relational Expressions

8. Conditional Expressions

Expression yang membandingkan dua boolean expression dimana hasilnya nanti adalah sebuah boolean juga. Berikut contoh conditional operator dan contoh code dalam Java

Gambar V.A.8.1: Contoh Conditional Operator

9. Comparison Operator Instanceof

Java memiliki instanceof operator membandingkan suatu objek dengan suatu tipe yang spesifik. Ini dapat dipakai untuk menegtahui/mengetes apakah suatu objek adalah instance dari class, instance dari subclass, atau instance dari class yang mengimplementasikan bagian dari interface. Berikut contoh program menggunakan comparison operator.

Gambar V.A.9.1: Contoh Comparison Instanceof

1. Assignment Statements

Assigment statements dalam Java menggunakan symbol sama dengan (=) untuk memasukan nilai hasil expression pada suatu variabel.

Syntax secara umum : <target variabel><assignment operator><expression>

1. Compound Assignment Operator

Operator yang melakukan proses perhitungan dan memasukan nilai hasilnya sekaligus secara bersamaan. Semua binary arithmetic operator dalam Java memiliki fungsi yang sama dengan compound assignment operator, berikut adalah tabelnya.

Expression	Compound Assignment Operator
a = a + b;	a += b;
a = a – b;	a -= b;
a = a * b;	a *= b;
a = a / b;	a /= b;
a = a % b;	a %= b;

Data Types I

Primitive data Types

•Almost all programming languages provide a set of primitive data types

•Primitive data types: Those not defined in terms of other data types

•Some primitive data types are merely reflections of the hardware

•Others require only a little non-hardware support for their implementation

Data types :

•Integer

•Floating Point

•Complex

•Decimal

•Boolean

•Character

Character String Implementation

•Static length: compile-time descriptor

•Limited dynamic length: may need a run-time descriptor for length (but not in C and C++)

•Dynamic length: need run-time descriptor; allocation/deallocation is the biggest implementation

problem

User-Defined Ordinal Types

•An ordinal type is one in which the range of possible values can be easily associated with the set of positive integers

•Examples of primitive ordinal types in Java

–integer

–char

–boolean

Enumerated Type

•Aid to readability, e.g., no need to code a color as a number

•Aid to reliability, e.g., compiler can check:

–operations (don’t allow colors to be added)

–No enumeration variable can be assigned a value outside its defined range

–Ada, C#, and Java 5.0 provide better support for enumeration than C++ because enumeration type variables in these languages are not coerced into integer types

Subrange Type

•An ordered contiguous subsequence of an ordinal type

–Example: 12..18 is a subrange of integer type

•Ada’s design

type Days is (mon, tue, wed, thu, fri, sat, sun);

subtype Weekdays is Days range mon..fri;

subtype Index is Integer range 1..100;

Day1: Days;

Day2: Weekday;

Day2 := Day1;

Array Types

•An array is a homogeneous aggregate of data elements in which an individual element is identified by its position in the aggregate, relative to the first element.

•Indexing (or subscripting) is a mapping from indices to elements

   array_name (index_value_list) ®  an element

•Index Syntax

–Fortran and Ada use parentheses

•Ada explicitly uses parentheses to show uniformity between array references and function calls because both are mappings

–Most other languages use brackets

•FORTRAN, C: integer only

•Ada: integer or enumeration (includes Boolean and char)

•Java: integer types only

•Index range checking

  - C, C++, Perl, and Fortran do not specify

        range checking

    - Java, ML, C# specify range checking

    - In Ada, the default is to require range

        checking, but it can be turned off

Array Initialization

•Some language allow initialization at the time of storage allocation

–C, C++, Java, C# example

int list [] = {4, 5, 7, 83}

–Character strings in C and C++

char name [] = ″freddie″;

–Arrays of strings in C and C++

char *names [] = {″Bob″, ″Jake″, ″Joe″];

–Java initialization of String objects

String[] names = {″Bob″, ″Jake″, ″Joe″};

Pointers in C and C++

•Extremely flexible but must be used with care

•Pointers can point at any variable regardless of when or where it was allocated

•Used for dynamic storage management and addressing

•Pointer arithmetic is possible

•Explicit dereferencing and address-of operators

•Domain type need not be fixed (void *)

   void *  can point to any type and can be type

      checked (cannot be de-referenced)

float stuff[100];

float *p;

p = stuff;

*(p+5) is equivalent to stuff[5] and  p[5]

*(p+i) is equivalent to stuff[i] and  p[i]

Reference

•Robert W. Sebesta - Concept of Programming Languages (Tenth Edition), Chapter 6