Oriental Institute of Science and Technology, Bhopal
RGPV/CSE-6 Sem/Code:6002/Subject: Principle of Programming Language/eNotes:Unit-4
Computer Science & Engg Dept Page 1
UNIT-IV
o Introductions to data abstraction, Abstract Data types: Abstractions and
encapsulation
o Static and Stack-Based Storage management. heap based storage management.
Garbage Collection.
o object oriented programming in small talk, C++, Java, C#, PHP, Perl (See PPTs).
o Concurrency: Subprogram level concurrency, semaphores, monitors, massage
passing, Java threads, C# threads.
Abstractions and encapsulation
• Abstraction: focus on what the object does instead of how it does it.
o In General words, Abstraction is Just Hiding the complex things
behind a particular Procedure to make the procedure look simple.
o Example:
▪ Monitor ON/OFF: The user doesn't need to know much about all
the chips functioning that happens when Monitor is switched ON or
OFF..All he needs to know is On Function ON-Monitor is On and on
function OFF-Monitor is off.
▪ Better Look for a car--Everyone Knows that There's a special Gear
machine Which changes the gear, nobody bother to know what all
functionality undergoes for a gear to change. So, that's abstraction
(avoiding unwanted implementations to prevent Complexity).
o So, if a developer provides a good abstraction, users will not be tempted to
peek at the object's internal mechanisms.
• Encapsulation: means hiding the internal details or mechanics of how an
object does something.
o In general words, Encapsulation is restricting a user to follow a
particular procedure to access control of a particular process. It
Just provides safety and ensures system robustness.
o Example:
▪ We can consider The HR in a company as a person that works on
the principle of Encapsulation.i.e. we cannot talk to other
departments directly we need to communicate through them through
HR. This ensures security and better maintenance of company's
records.
Oriental Institute of Science and Technology, Bhopal
RGPV/CSE-6 Sem/Code:6002/Subject: Principle of Programming Language/eNotes:Unit-4
Computer Science & Engg Dept Page 2
Everything has many properties and behaviours so take whatever
object you want TV, Mobile, Car, Human or anything.
Abstraction:
1. Process of picking the essence of an object you really need
2. In other words, pick the properties you need from the object Example:
a. TV - Sound, Visuals, Power Input, Channels Input.
b. Mobile - Button/Touch screen, power button, volume button, sim port.
c. Car - Steering, Break, Clutch, Accelerator, Key Hole.
d. Human - Voice, Body, Eye Sight, Hearing, Emotions.
Encapsulation:
1. Process of hiding the details of an object you don't need
2. In other words, hide the properties and operations you don't need from the object but
are required for the object to work properly Example:
a. TV - Internal and connections of Speaker, Display, Power distribution b/w
components, Channel mechanism.
b. Mobile - How the input is parsed and processed, How pressing a button on/off or
changes volumes, how sim will connect to service providers.
c. Car - How turning steering turns the car, How break slow or stops the car, How clutch
works, How accelerator increases speed, How key hole switch on/of the car.
d. Human - How voice is produced, What's inside the body, How eye sight works, How
hearing works, How emotions generate and effect us.
ABSTRACT everything you need
and
ENCAPSULATE everything you don't need
Oriental Institute of Science and Technology, Bhopal
RGPV/CSE-6 Sem/Code:6002/Subject: Principle of Programming Language/eNotes:Unit-4
Computer Science & Engg Dept Page 3
An abstraction is a view or representation of an entity that includes only the most significant
attributes. There are two kinds of abstraction i.e. process abstraction and data abstraction.
Process Abstraction-
• All subprograms are process abstraction because they provide a way for a program to
specify that some process is to be done, without providing the details of how it is done.
▪ Ex SortInt ( List, ListLen);
• This call is an abstraction of actual sorting process whose algorithm is not specified.
This call is independent of the algorithm implemented in the called subprogram.
Data Abstraction-
• An abstract data type is an enclosure that includes only the data representation of one
specific data type and the subprograms that provide the operations for that type.
• Ex- C++, Java made it easier for programmer to use ADTs, each ADTs correspond to a
class and the operations on the ADT’s are public methods.
• The user of the ADT only needs to know about the method interfaces not the actual
implementation.
Benefits-
1. Code is easier to understand.
2. Implementation of the ATDs can be changed without requiring changes to the
program that uses ADTs. ADTs support abstraction, encapsulation and information
hiding.
Common Examples of ADTs-
1. Built in types: Boolean, integer, real.
2. User defined: stack, queue, tree list, class, and structure.
Data abstraction refers to the data that can be used without taking into account how the data
are stored.
An ADT is defined as
• Data type that holds some kind of data.
• An ADT has built in operations that can be performed on it or by it.
• Users of an ADT don’t need to have any detail information about the internal
representation of data storage or implementation of the operations.
Oriental Institute of Science and Technology, Bhopal
RGPV/CSE-6 Sem/Code:6002/Subject: Principle of Programming Language/eNotes:Unit-4
Computer Science & Engg Dept Page 4
Floating Point as an ADT
• A floating type provides a set of arithmetic operations for manipulating objects of that
type. The actual format of the data value in floating point memory cell is hidden from
the user and the only operations available are those provided by the language. The
user is not allowed to create new operations on data of the type.
• Implementations may use different representations for particular data types. Ex- IEEE
754 standard floating point.
User Defined ADT-
• ADTs are often called User Defined Data Type because they allow programmers to
define new types that resemble primitive data types.
• Just like primitive data types Integer with operations +, -,*, / an ADT has a type domain
whose representation is unknown to clients and a set of operations defined on the
domain.
• A user DT provides the same characteristics provided by built in abstract type.
• A type definition that allows program units to declare variables of the type but hides
the representation of these variables.
• A set of operations for manipulating objects of the type.
For Example
#include <iostream.h>
class Add
{
private: int x,y,r;
public:
int Addition(int x, int y)
{ r= x+y; return r; }
void Show( )
{ cout << "The sum is::" << r << "\n";}
};
void main()
{
Add s;
s.Addition(10, 4);
s.Show();
}
Internal representation of any object of Add class is
hidden outside the class. --> Encapsulation
Implementation of methods Addition, Show are hidden. -
-> Abstraction.
Oriental Institute of Science and Technology, Bhopal
RGPV/CSE-6 Sem/Code:6002/Subject: Principle of Programming Language/eNotes:Unit-4
Computer Science & Engg Dept Page 5
Static and Stack-Based Storage management. heap based storage management
Storage Management
• The fundamental purpose of any program is to manipulate data and its
storage in the computer memory.
• Two memory management techniques are used for this purpose. They
are:
o Static storage management
o Dynamic storage management
Static Allocation (fixed in size)
• Create data structures that are “fixed” and don’t need to grow or shrink.
• Done at compile time.
• Global variables: variables declared “ahead of time,” such as fixed arrays.
• Lifetime: entire runtime of program
• Advantage: efficient execution time.
• Disadvantage?
o In case more static data space is declared than needed, there is
waste of space.
o In case less static space is declared than needed, then it becomes
impossible to expand this fixed size during run time.
Dynamic Allocation (change in size)
• Increase and decrease the size of our data structures to accommodate
changing needs.
• Done at run time.
• Data structures can grow and shrink to fit changing data requirements.
• Allocate (create) additional storage whenever we need.
• de-allocate (free/delete) dynamic space whenever we not need.
• Advantage: we can always have exactly the amount of space required - no
more, no less.
• Disadvantage
o As the memory is allocated during runtime, it requires more time.
o Memory needs to be freed by the user when done. This is important
as it is more likely to turn into bugs that are difficult to find.
Oriental Institute of Science and Technology, Bhopal
RGPV/CSE-6 Sem/Code:6002/Subject: Principle of Programming Language/eNotes:Unit-4
Computer Science & Engg Dept Page 6
Two general approaches to dynamic storage allocation:
• Stack allocation:
➢ restricted, but simple and efficient.
➢ Used to allocate local variables in C/C++, Ada, Algol, or Pascal.
➢ Grown and shrunk on procedure calls and returns.
➢ Register allocation works best for stack-allocated objects
➢ Allocation during translation that remains fixed throughout
execution.
• Heap allocation:
➢ more general, but less efficient, more difficult to implement.
➢ Used to allocate dynamic objects.
➢ Heap objects are accessed with pointers.
➢ Never allocated to registers.
•
Oriental Institute of Science and Technology, Bhopal
RGPV/CSE-6 Sem/Code:6002/Subject: Principle of Programming Language/eNotes:Unit-4
Computer Science & Engg Dept Page 7
•
Oriental Institute of Science and Technology, Bhopal
RGPV/CSE-6 Sem/Code:6002/Subject: Principle of Programming Language/eNotes:Unit-4
Computer Science & Engg Dept Page 8
Garbage collection
Garbage collection is an automatic memory management feature in many
modern programming languages, such as Java and languages in the .NET
framework. Languages that use garbage collection are often interpreted or run
within a virtual machine like the JVM. In each case, the environment that runs
the code is also responsible for garbage collection.
In older programming languages, such as C and C++, allocating and freeing
memory is done manually by the programmer. Memory for any data that can't
be stored within a primitive data type, including objects, buffers and strings, is
usually reserved on the heap. When the program no longer needs the data, the
programmer frees that chunk of data with an API call. Because this process is
manually controlled, human error can introduce bugs in the code. Memory leaks
occur when the programmer forgets to free up memory after the program no
longer needs it. Other times, a programmer may try to access a chunk of
memory that has already been freed, leading to dangling pointers that can cause
serious bugs or even crashes.
Programs with an automatic garbage collector (GC) try to eliminate these bugs
by automatically detecting when a piece of data is no longer needed. A GC has
two goals: any unused memory should be freed, and no memory should be freed
unless the program will not use it anymore. Although some languages allow
memory to be manually freed as well, many do not.
Benefits-
Garbage collection frees the programmer from manually dealing with memory
allocation and deallocation. As a result certain categories of bugs are eliminated.
i. Dangling pointer bugs which occur when a piece of memory is freed while
there are still pointers to it and one of these pointers is then used.
ii. Double free bugs which occur when the program attempts to free a region
of memory that is already free.
iii. Certain kinds of memory leaks in which a program fails to free memory
occupied by objects that will not be used again, leading overtime to
memory exhaustion.
Oriental Institute of Science and Technology, Bhopal
RGPV/CSE-6 Sem/Code:6002/Subject: Principle of Programming Language/eNotes:Unit-4
Computer Science & Engg Dept Page 9
Semaphores
Semaphore is a synchronization tool.
semaphore is a value that indicates the status of common resources.
A semaphore, in its most basic form, is a protected integer variable that can
facilitate and restrict access to shared resources in a multi-processing
environment.
The two most common kinds of semaphores are counting semaphores and
binary semaphores.
Counting semaphores represent multiple resources, while binary semaphores,
as the name implies, represents two possible states (generally 0 or 1; locked or
unlocked). Semaphores were invented by the late Edsger Dijkstra.
Semaphores can be looked at as a representation of a limited number of
resources, like seating capacity at a restaurant.
If a restaurant has a capacity of 50 people and nobody is there, the semaphore
would be initialized to 50. As each person arrives at the restaurant, they cause
the seating capacity to decrease, so the semaphore in turn is decremented.
When the maximum capacity is reached, the semaphore will be at zero, and
nobody else will be able to enter the restaurant. Instead the hopeful restaurant
goers must wait until someone is done with the resource, or in this analogy,
done eating. When a patron leaves, the semaphore is incremented and the
resource becomes available again.
A semaphore can only be accessed using the following operations: wait() and
signal(). wait() is called when a process wants access to a resource. This would
be equivalent to the arriving customer trying to get an open table.
If there is an open table, or the semaphore is greater than zero, then he can take
that resource and sit at the table. If there is no open table and the semaphore is
zero, that process must wait until it becomes available. signal() is called when a
process is done using a resource, or when the patron is finished with his meal.
The following is an implementation of this counting semaphore (where the
value can be greater than 1):
Oriental Institute of Science and Technology, Bhopal
RGPV/CSE-6 Sem/Code:6002/Subject: Principle of Programming Language/eNotes:Unit-4
Computer Science & Engg Dept Page 10
wait(Semaphore s){
while (s==0); /* wait until s>0 */
s=s-1;
}
signal(Semaphore s){
s=s+1;
}
Init(Semaphore s , Int v){
s=v;
}
Oriental Institute of Science and Technology, Bhopal
RGPV/CSE-6 Sem/Code:6002/Subject: Principle of Programming Language/eNotes:Unit-4
Computer Science & Engg Dept Page 11
If there is only one count of a resource, a binary semaphore is used which can
only have the values of 0 or 1. They are often used as mutex locks. Here is an
implementation of mutual-exclusion using binary semaphores:
do
{
Wait;
// critical section
Signal;
// remainder section
} while (1);
In the Producer-Consumer problem, semaphores are used for two purposes:
• mutual exclusion and
• Synchronization.
In the following example there are three semaphores. Full, used for counting
the number of slots that are full; empty, used for counting the number of slots
that are empty; and mutex, used to enforce mutual exclusion.
BufferSize = 3;
semaphore mutex = 1; // Controls access to critical section
semaphore empty = BufferSize; // counts number of empty buffer slots
semaphore full = 0; // counts number of full buffer slots
Producer()
{
int widget;
while (TRUE) { // loop forever
make_new(widget); // create a new widget to put in the buffer
down(&empty); // decrement the empty semaphore
down(&mutex); // enter critical section
put_item(widget); // put widget in buffer
up(&mutex); // leave critical section
up(&full); // increment the full semaphore
}
}
Oriental Institute of Science and Technology, Bhopal
RGPV/CSE-6 Sem/Code:6002/Subject: Principle of Programming Language/eNotes:Unit-4
Computer Science & Engg Dept Page 12
Consumer() {
int widget;
while (TRUE) { // loop forever
down(&full); // decrement the full semaphore
down(&mutex); // enter critical section
remove_item(widget); // take a widget from the buffer
up(&mutex); // leave critical section
up(&empty); // increment the empty semaphore
consume_item(widget); // consume the item
}
}
Oriental Institute of Science and Technology, Bhopal
RGPV/CSE-6 Sem/Code:6002/Subject: Principle of Programming Language/eNotes:Unit-4
Computer Science & Engg Dept Page 13
Monitors
A monitor has four components as shown below: initialization, private data,
monitor procedures, and monitor entry queue. The initialization component
contains the code that is used exactly once when the monitor is created, the
private data section contains all private data, including private procedures that
can only be used within the monitor. Thus, these private items are not visible
from outside of the monitor. The monitor procedures are procedures that can
be called from outside of the monitor. The monitor entry queue contains all
threads that called monitor procedures but have not been granted permissions.
Mutual Exclusion is automatically provided by the monitor implementation. If a process calls
monitor methods, but another process is already executing inside the monitor, the calling
thread must wait outside the monitor.
Oriental Institute of Science and Technology, Bhopal
RGPV/CSE-6 Sem/Code:6002/Subject: Principle of Programming Language/eNotes:Unit-4
Computer Science & Engg Dept Page 14
Synchronous Message Passing
Move data between processes
• Sender: when data is ready, send it to the receiver process
• Receiver: when the data has arrived and when the receive process is
ready to take the data, move the data to the destination data structure
Synchronization
• Sender: signal the receiver process that a particular event happens
• Receiver: block until the event has happened.
Asynchronous Message Passing
If a process sends a message and continue executing without waiting for the
message to be received then the communication is termed asynchronous.
• Send operations are non blocking.
• A sending process can get arbitrarily for ahead of a receiving process.
• Message delivery is not guaranteed if failures can occur.
• Since channels can contain an unbounded number of messages, messages
have to be buffered.
• The sending process has no ways of knowing if the message was ever
received unless the receiving process sends a reply.
• It is hard to detect when failures have occurred.
• Buffer space is finite- if too many messages are sent either the program
will crash; the buffer will overflow with loss of messages or send operation
will block.
