Assignment THREAD BASED IMPLEMENTATION

Short answer type questions:-

Ques. 1:
In case of User-Level Thread implementation the schedulable entity is:
a) Program
b) Process
c) Thread
d) (b) & (c) both
Answer:
(b)
(Because kernel is not aware of the threading activity being carried out within the program.)


Ques. 2:
User-Level Threads (ULTs) are implemented by means of ______________ & Kernel-Level Threads are implemented through ____________________.
Answer:
Thread Libraries & System calls


Ques. 3:
Which thread implementation should be preferred in case of a server that spawns a new thread for each incoming request (say for 2000-3000 threads) & why?
User-Level Threads/ Fibers
Kernel-Level Threads/ Threads
Sequential Process Approach
Combined ULT + KLT implementation
Answer:
(a)
(Context switching that includes a blocking system call will be too expensive so in such cases Fibers can be helpful)


Ques. 4:
Mention one such operating system that implements the combined ULT + KLT approach to threading?
Answer:
SOLARIS Operating System


Ques. 5:
The routine used to wake up any threads waiting on a given Condition Variable is:
Event-Clear
Event-Post
Event-Signal
Event-Init
Answer:
(b)


Ques. 6:
To ensure that a post does not happen after the condition checking and before the execution of wait call, _____________________ is made use of.
Answer:
Mutex Variable


Ques. 7:
Name an API for multi-threaded programming standardized by IEEE as part of the POSIX standards?
Answer:
Pthread Library defined under standard POSIX 1003.1c.


Ques. 8:
In JAVA the concept of threads is implemented through:
Integrated in language itself
External APIs & Libraries
Operating System
No multithreaded support in JAVA
Answer:
(b)
(JAVA provides in-built support for multithreading through “java.lang” package & “java.lang.Thread” class)



Ques. 9:
The only method that makes up the entire body of the thread and in which the thread behaviour can be implemented is_____________.
Answer:
The run( ) method.


Ques. 10:
What should be done to prevent a method from causing a RACE CONDITION in a program:
Create only one thread at a time
Precede call to that method with ‘synchronized’ keyword
Precede the method definition with ‘synchronized’ keyword
Synchronization primitives not supported by Java, so can’t be prevented
Answer:
C)
(To make an object enter its lock that is implicitly associated with every object we make use ‘synchronized’ keyword with the method that is likely to result into Race Condition.)


Ques. 11:
List down two basic functions performed by the function pthread_cond_wait (cond, mutex).
Answer:
Put thread in queue of waiting threads
Release the aquired lock


Ques. 12:
Consider the following code segment:
public static void main(String a[])
{
mythread th1=new mythread();
mythread th2=new mythread();
th1.start();
th1.suspend();
th2.start();
System.out.println(" Thread ONE is alive True/False: " +th1.isAlive());
System.out.println(" Thread TWO is alive True/False: " +th2.isAlive());
th1.resume();
try
{
th1.join();
th2.join();
}catch(InterruptedException ie)
{
System.out.println("Exception in threads!!!!");
}
System.out.println(" FINISHED !”);
}
}
What is the purpose of join() call in above code?
Answer:
This will wait for both of the threads to finish (complete execution) and to join it and only after that outputs FINISHED.


Ques. 13:
The join() function in java is equivalent to (serves the purpose of) _________________ primitive in Process Model.
Answer:
barrier() primitive.


Ques. 14:
After making a call to suspend() method on an executing thread, what will the isAlive() method return for the same thread?
True
False
Answer:
a)
(Because the thread is just suspended temporarily, to be resumed later it has not yet completed its execution.)


Ques. 15:
What are the methods available in Java to serve the functionality of Condition Variables?
Answer:
wait() and notify()



Long answer type questions:-

Ques. 1:
Describe different ways of implementing threads, with their merits and demerits. Also mention which method is preferred in which situation?
Answer:
There are two broad categories of thread implementation:
User-Level Threads/ Fibers/ LWPs -- Thread Libraries.
ii) Kernel-level Threads/ Threads -- System Calls.

1. USER-LEVEL THREADS (ULT):
This implementation implements threads as a user-level entity that is unknown to the Operating System. In this level, the kernel is not aware of the existence of threads -- All thread management is done by the application by using a thread library.
Thread switching does not require kernel mode privileges (no mode switch)
Scheduling is application specific
Kernel activity for ULTs: The kernel is not aware of thread activity but it is still managing process activity
Thread/process states: When a thread makes a system call, the whole process will be blocked but for the thread library but that thread is still in the running state. So thread states are independent of process states
Threads are actually handled by a Thread Management Module of the process, which assigns the CPU to one of the available process. When the OS timer interrupts, the control is taken by OS to allot the CPU to another process.

Advantages:
à Thread switching does not involve the kernel -- no mode switching
à Scheduling can be application specific -- choose the best algorithm.
à ULTs can run on any OS -- Only needs a thread library

Disadvantages:
à Most system calls are blocking and the kernel blocks processes -- So all threads within the process will be blocked
à The kernel can only assign processes to processors -- Two threads within the same process cannot run simultaneously on two processors

2. KERNEL-LEVEL THREADS (KLT):
In this level, All thread management is done by kernel. No thread library but an API (system calls) to the kernel thread facility exists. The kernel maintains context information for the process and the threads both, Switching between threads require the kernel.
Scheduling is performed on a thread basis.

Advantages:
à The kernel can simultaneously schedule many threads of the same process on many processors.
à Blocking due to the system calls is also done on a thread level.

Disadvantages:
à Thread switching within the same process involves the kernel, e.g if we have two threads per process and switching between these threads is required quite often after short intervals then kernel has to participate in this switching resulting in a significant slow down of the whole system.

3. COMBINED ULT/KLT APPROACHES:
Sometimes a combined approach for both of the implementations is followed. Solaris is an example of an OS that combines both ULT and KLT.
Under User Space:
à Thread creation.
à Bulk of scheduling and synchronization of threads.
The programmer may adjust the number of KLTs
Process includes the user's address space, stack, and process control block
User-level threads (threads library) invisible to the OS are the interface for application parallelism
Kernel threads the unit that can be dispatched on a processor
Lightweight processes (LWP) each LWP supports one or more ULTs and maps to exactly one KLT .

Suitability:-
Consider the following pseudo code:
main()
{
status=0;
pthread_create(….,proc1,….);
while(status!=0)
…….
}
proc1()
{
…..
v1=1;
…..
}
à The newly created thread is expected to change the value of v1, which the parent thread is waiting for. But in some implementations this may lead the system to hang. If the system follows ULT implementation, then the main thread is apparently doing some serious work and does not yield control to the new thread. Therefore the second thread never gets a chance to run, in order to change the value of v1, which is what main is waiting for. If system followed KLT instead then the problem outlined above cannot occur.
à A case where fibers/ULTs still can be helpful is when the limits of the OS in terms of number of threads per process are reached (for example 2000-3000 threads). In this case context-switching, which includes a system call, is too expensive and fibers can help.
This situation may happen, for example, in a server that spawns a new thread for each incoming request.
•

Ques. 2:
What primitives are available in POSIX Pthread Library for implementing Condition Variables? Explain with an example.
Answer:
Sometimes, there is a need to detect the occurrence of certain events and behave accordingly.
For example: We may want thread T1 to execute certain steps only after some other computation is over by other thread T2. So, T1 is supposed to wait for T2 until it finishes.
For such situations, Pthread library uses the notion of Condition Variables.
A condition variable has two parts:
1. Condition
2. Semaphore
The condition variable mechanism allows threads to suspend execution and relinquish the processor until some condition is true. A condition variable must always be associated with a mutex to avoid a race condition created by one thread preparing to wait and another thread which may signal the condition before the first thread actually waits on it resulting in a deadlock. The thread will be perpetually waiting for a signal that is never sent. Any mutex can be used, there is no explicit link between the mutex and the condition variable.

A condition variable supports four basic operations:
Event-init: It is for initialization of condition variables
ii) Event-wait: It is called when a thread has to wait for the condition to be true.
iii) Event-clear: Used to flag the condition as true.
Event-Post: Used to flag the condition as false. It should also wake up any threads waiting on the variable by calling event-wait.

PRIMITIVES AVAILABLE FOR USING CONDITION VARIABLES ARE:

pthread_cond_init (cond, NULL)
To initialize the condition variable.
cond is a variable of type pthread_cond_t.

pthread_cond_wait (cond, mutex)
Called when a thread has to wait for a condition to become true.
The thread should check for the condition required and only if it is false executes this. Once it is false the event-post routine wakes up all the threads waiting on the variable/condition.
In order to ensure that post does not happen after the condition checking and before the execution of this wait call, a mutex variable is made use of. All operations on condition variable should be done only under this mutex lock.

Posting an event
pthread_cond_broadcast(cond)
Wakes up all threads waiting on the given condition variable.

pthread_cond_signal(cond)
If there are more than one thread waiting then a random one is chosen and woken-up.Else only the thread associated with the condition is woken.

EXAMPLE: The program given below describes the use of condition variables as well as mutex variables.
main()
{
pthread_t thread1, thread2;
int count=0;
pthread_create( &thread1, NULL, &functionCount1, NULL);
pthread_create( &thread2, NULL, &functionCount2, NULL);
exit(0);
}
void *functionCount1()
{
for(;;)
{
pthread_mutex_lock( &condition_mutex );
while( count >= 3 && count <= 6 )
{
pthread_cond_wait( &condition_cond, &condition_mutex );
}
pthread_mutex_unlock( &condition_mutex );

pthread_mutex_lock( &count_mutex );
count++;
printf("Counter value functionCount1: %d\n",count);
pthread_mutex_unlock( &count_mutex );
if(count >= 10) return(NULL);
}
}
void *functionCount2()
{
for(;;)
{
pthread_mutex_lock( &condition_mutex );
if( count <> 6 )
{
pthread_cond_signal( &condition_cond );
}
pthread_mutex_unlock( &condition_mutex );
pthread_mutex_lock( &count_mutex );
count++;
printf("Counter value functionCount2: %d\n",count);
pthread_mutex_unlock( &count_mutex );
if(count >= 10) return(NULL);
}
}

Output: Compile: cc -lpthread cond1.c
Run: ./a.out
Results:
Counter value functionCount1: 1
Counter value functionCount1: 2
Counter value functionCount1: 3
Counter value functionCount2: 4
Counter value functionCount2: 5
Counter value functionCount2: 6
Counter value functionCount2: 7
Counter value functionCount1: 8
Counter value functionCount1: 9
Counter value functionCount1: 10
Counter value functionCount2: 11



Ques. 3:
Write down the steps for creating threads in JAVA?
OR
What are the alternative methods of creating threads in JAVA? Explain.
Answer:
A unique property of Java is its support for multithreading. That is, java enables us to use multiple flows of control in developing programs.
Each flow of control may be thought of as a separate tiny program (or module) known as a thread that runs in parallel to others. A program that contains multiple flows of control is known as multithreaded program.
A new thread can be created in two ways:
By creating a thread class
By converting a class to a thread
The approach to be used depends on what the class that we are creating requires. If it requires to extend another class, then we have to implement the Runnable interface (as Java does not support more than one superclasses so multiple inheritance is achieved through interfaces in Java).


I) METHOD #1: EXTENDING THE THREAD CLASS
For both the methods we need to extend the class java.lang.Thread which gives us access to all the thread methods directly. The steps involved are:

Step 1: Declare the class as extending the Thread class.

class MyThread extends Thread
{ - - - - - - - - -
- - - - - - - - -
}
This creates a new thread of type ‘MyThread’

Step 2: Implement the run ( ) method that is responsible for executing the sequence of code that the thread will execute.
The run ( ) method has been inherited by the class MyThread. We need to override this method in order to implement the code to be executed by our thread. When we start the new thread, Java calls the thread’s run ( ) method, so it is the run ( ) where all the action takes place.

public void run( )
{
- - - - - - - - - - -
- - - - - - - - - (Statements for implementing thread)
- - - - - - - - - - -
}

Step 3: Create a thread object and call the start ( ) method to initiate the thread execution. To actually create and run the instance of our thread class we must write the following:

MyThread th1 = new MyThread ( );
// This will put the thread th1 in a newborn state.
th1.start( );
// Thread th1 is now put into Runnable state


à Now the Java runtime will schedule the thread to run by invoking its run ( ) method implicitly. Now, the thread is said to be in the running state.
à The start ( ) method returns back to the main thread immediately after invoking the run ( ) method, thus allowing the main thread to start some another thread.

II) METHOD #2: IMPLEMENTING THE ‘Runnable’ INTERFACE
To create threads in those situations where the class needs to have more than one super classes we must use the practice of implementing the ‘Runnable’ interface. It involves the following steps:

Step 1: Declare the class as implementing the Runnable interface.
class mythread implements Runnable
{
…………
…………
}

Step 2: Implement the run ( ) method. It is important to understand that run ( ) can call other methods, use other classes, and declare variables just like the main thread can.

Step 3: After creating the class, next we will instantiate an object of type Thread from within that ‘runnable’ class as the target of the thread. For this very purpose the Thread class defines several constructors. One such simple constructor that can be used is:

Thread(Runnable threadOb, String threadname);


Object of the class Name given to the
that implemented new thread(optional)
Runnable interface

Thread th = mythread ( this, “demo Thread”);

Step 4: Call the thread’s start ( ) method that executes a call to the run ( ) method to run the thread.
th.start ( );











Ques. 4:
What is meant by mutual exclusion? What are the primitives available in JAVA and Pthread library for synchronizing access to shared variables and resources?
Answer:
One of the major issues in thread programming is controlling access to shared resources. Mutual exclusion is used to prevent data inconsistencies due to race conditions. A race condition often occurs when two or more threads need to perform operations on the same memory area, but the results of computations depends on the order in which these operations are performed.
Mutual exclusion primitives are used for serializing shared resources. Anytime a global resource is accessed by more than one thread the resource should have some kind of lock associated with it. One can apply a lock to protect a segment of memory ("critical region") from other threads.

Mutual Exclusion In JAVA:
Locking management is well integrated into JAVA language. Conceptually, we can view Java’s synchronization system as associating a lock with every object created. In other words, methods can be declared as ‘synchronized’.
With every object an implicit monitor is associated with. To make an object enter its monitor that is implicitly associated with every object we make use ‘synchronized’ keyword with the method that is likely to result into Race Condition.
(Race Condition is the condition where nothing exists to stop all the threads in the program from calling the same method, on the same object, at the same time.)
All other threads even ‘synchronized threads’ can’t enter or call that thread. To exit monitor and relinquish control of object, owner of monitor simply returns from synchronized method.
Example:
The concept explained above can better be depicted through an example code:

class Callme
{
void call(String msg)
{
System.out.print("[ " +msg);
System.out.println(" ]");
}
}
class caller implements Runnable
{
String msg;
Callme cme;
Thread t;
public caller(Callme c, String s)
{
cme=c;
msg=s;
t = new Thread(this);
/* Create a new thread. 'this' refers to the object of the class that implemented the RUNNABLE interface. In this case it can be any of th1, th2, th3 or th4.
*/
t.start();
}
public void run()
{
cme.call(msg);
} }
class mutual
{
public static void main(String a[])
{
Callme cme1 = new Callme();
caller th1 = new caller ( cme1, "Example");
caller th2 = new caller ( cme1, "Of");
caller th3 = new caller ( cme1, "Mutual");
caller th4 = new caller ( cme1, "Exclusion");
}
}

Output:
[Example][of Mutual]Exclusion][
or
[Example[[of Mutual [Exclusion]]]]
or
Any sort of distorted or overlapped output.

The problem with the above program is that all of the four threads are calling the same method call() at same time, so that’s why we are not able to get the desired output. There is a need to synchronize access to this method which can be simply done as follows:
synchronized void call(String msg)
Now, the desired output will be:
[Example]
[of]
[Mutual]
[Exclusion]



Mutual Exclusion In POSIX:
The threads library provides three synchronization mechanisms:
mutexes - Mutual exclusion lock: Block access to variables by other threads. This enforces exclusive access by a thread to a variable or set of variables.
joins - Make a thread wait till others are complete (terminated).
condition variables - data type pthread_cond_t.

Example:
One such example code that depicts the use of both mutex variables and joins that can be implemented in a program to achieve mutual exclusion features is as follows:

int counter = 0;
main()
{
int rc1, rc2;
pthread_t thread1, thread2;
/* Create independent threads each of which will execute functionC */
if( (rc1=pthread_create( &thread1, NULL, &functionC, NULL)) )
{
printf("Thread creation failed: %d\n", rc1);
}
if( (rc2=pthread_create( &thread2, NULL, &functionC, NULL)) )
{
printf("Thread creation failed: %d\n", rc2);
}
/* Wait till threads are complete before main continues. */
pthread_join( thread1, NULL);
pthread_join( thread2, NULL);
}
void *functionC()
{
pthread_mutex_lock( &mutex1 );
counter++;
printf("Counter value: %d\n",counter);
pthread_mutex_unlock( &mutex1 );
}

OUTPUT:
Compile: cc -lpthread mutex1.c
Run: ./a.out
Results:
Counter value: 1
Counter value: 2

Content Credit: Prabhjot Kaur