OS Support for Building

Distributed Applications:
Multithreaded
Programming using Java
Threads
Rajkumar Buyya
Grid Computing and Distributed Systems (GRIDS)
Laboratory
Dept. of Computer Science and Software Engineering
University of Melbourne, Australia
http://www.gridbus.org/~raj or http://www.buyya.com
1

Outline

Introduction
Thread Applications
Defining Threads
Java Threads and States
Architecture of Multithreaded servers
Threads Synchronization
Thread Concurrency Models
Summary
2

Introduction

We discuss how Middleware is supported

by the Operating System (OS) facilities
at the nodes of a distributed system.
The OS facilitates:

Encapsulation and protection of resources

inside servers;
It supports invocation of mechanisms
required to access those resources including
concurrent access/processing.

Middleware and Network

Operating System (NOS)

Many DOS (Distributed OS) have been investigated,

but there are none in general/wide use. But NOS are
in wide use for various reasons both technical and
non-technical.

Users have much invested in their application software;

they will not adopt to new OS that will not run their
applications.
The 2nd reason against the adoption of DOS is that users
tend to prefer to have a degree of autonomy of their
machines, even in a closely knit organisation.

A combination of middleware and NOSs provides an

acceptance balance between the requirement of
autonomy and network transparency.

NOS allows users to run their favorite word processor.

Middleware enables users to take advantage of services
that become available in their distributed system.
4

Operating system layers and

Middleware
Applications, services
Middleware

OS: kernel,
libraries &
servers

OS1
Processes, threads,
communication, ...

OS2
Processes, threads,
communication, ...

Computer &
network hardware

Computer &
network hardware

Node 1

Platform

Node 2

Unix and Windows are two examples of Network Operating Systems have a
networking capability built into them and so can be used to access remote
resources using basic services such as rlogin, telnet.

Core OS components and

functionality
Process manager

Communication
manager

Thread manager

Memory manager
Supervisor

A single threaded program

class ABC
{
.
public void main(..)
{

..
}

begin

body
end

}
7

A Multithreaded Program
Main Thread

start

Thread A

start

Thread B

start

Thread C

Threads may switch or exchange data/results

Single and Multithreaded

Processes
threads are light-weight processes within a process
Single-threaded Process

Multiplethreaded
Threads of Process
Execution

Multiple instruction stream

Single instruction stream Common
Address Space
9

Multi-Processing (clusters &

grids) and Multi-Threaded
Computing
Threaded Libraries, Multi-threaded I/O
Application
Application

Application

Application

CPU
CPU
CPU
Better Response Times in
Multiple Application
Environments

CPU

CPU

CPU

Higher Throughput for

Parallelizeable Applications
10

Web/Internet Applications:
Serving Many Users
Simultaneously
PC client

Internet
Server
Local Area Network

PDA
11

Multithreaded Server: For Serving

Multiple Clients Concurrently

Server Process

Client 1
Process

Server
Threads

Internet

Client 2
Process

12

Modern Applications need Threads (ex1):

Editing and Printing documents in
background.
Printing
Printing Thread
Thread

Editing
Editing
Thread
Thread

13

Multithreaded/Parallel File
Copy
reader()
reader()
{{
-- -- -- -- -- -- -- -- --lock(buff[i]);
lock(buff[i]);
read(src,buff[i]);
read(src,buff[i]);
unlock(buff[i]);
unlock(buff[i]);
-- -- -- -- -- -- -- -- --}}

buff[0]
buff[0]
buff[1]
buff[1]

writer()
writer()
{{
-- -- -- -- -- -- -- -- -- -lock(buff[i]);
lock(buff[i]);
write(src,buff[i]);
write(src,buff[i]);
unlock(buff[i]);
unlock(buff[i]);
-- -- -- -- -- -- -- -- -- -}}

Cooperative
Cooperative Parallel
Parallel
Synchronized
Synchronized Threads
Threads

14

Levels of Parallelism
Sockets/
PVM/MPI

Threads

Compilers
CPU

Task
Taski-l
i-l

func1
func1( () )
{{
....
....
....
....
}}

aa( (00) )=..

=..
bb( (00) )=..
=..

++

Task
Taskii

func2
func2( () )
{{
....
....
....
....
}}

aa( (11)=..
)=..
bb( (11)=..
)=..

xx

Task
Taski+1
i+1

func3
func3( () )
{{
....
....
....
....
}}

aa( (22)=..
)=..
bb( (22)=..
)=..

Load
Load

Code-Granularity
Code-Granularity
Code
CodeItem
Item
Large
Largegrain
grain
(task
(tasklevel)
level)
Program
Program
Medium
Mediumgrain
grain
(control
(controllevel)
level)
Function
Function(thread)
(thread)
Fine
Finegrain
grain
(data
(datalevel)
level)
Loop
Loop(Compiler)
(Compiler)
Very
Veryfine
finegrain
grain
(multiple
(multipleissue)
issue)
With
Withhardware
hardware

15

Multithreading Multiprocessors
Process
Process Parallelism
Parallelism
CPU

P1
P1
P2
P2

CPU

P3
P3

CPU

tim
tim
ee

No
No of
of execution
execution process
process more
more the
the
number
number of
of CPUs
CPUs

16

Multithreading on Uniprocessor

Concurrency Vs Parallelism
Process
ProcessConcurrency
Concurrency
P1
P1
P2
P2

CPU

P3
P3

tim
tim
ee

Number
Number of
of Simultaneous
Simultaneous execution
execution units
units >
>
number
number of
of CPUs
CPUs

17

What are Threads?

A piece of code that run in concurrent with

other threads.
Each thread is a statically ordered
sequence of instructions.
Threads are being extensively used express
concurrency on both single and
multiprocessors machines.
Programming a task having multiple
threads of control Multithreading or
Multithreaded Programming.
18

Java Threads

Java has built in thread support for

Multithreading
Synchronization
Thread Scheduling
Inter-Thread Communication:

currentThread
start setPriority
yield run getPriority
sleep stop suspend
resume

Java Garbage Collector is a low-priority

thread.
19

Threading Mechanisms...

Create a class that extends the Thread

class
Create a class that implements the
Runnable interface

20

1st method: Extending

Thread class

Threads are implemented as objects that

contains a method called run()
class MyThread extends Thread
{
public void run()
{
// thread body of execution
}
}

Create a thread:
MyThread thr1 = new MyThread();
Start Execution of threads:
thr1.start();
Create and Execute:
new MyThread().start();

21

An example
class MyThread extends Thread { // the thread
public void run() {
System.out.println(" this thread is running ... ");
}
} // end class MyThread
class ThreadEx1 {
// a program that utilizes the thread
public static void main(String [] args ) {
MyThread t = new MyThread();
MyThread t2 = new MyThread();
// due to extending the Thread class (above)
// I can call start(), and this will call
// run(). start() is a method in class Thread.
t2.start();
t.start();
} // end main()
}
// end class ThreadEx1

22

Next Lecture

More about threads programming

Using interfaces
Multiple threads in a program

23

2nd method: Threads by

implementing Runnable interface
class MyThread extends ABC implements Runnable
{
.....
public void run()
{
// thread body of execution
}
}
Creating Object:
MyThread myObject = new MyThread();
Creating Thread Object:
Thread thr1 = new Thread( myObject );
Start Execution:
thr1.start();

24

An example
class MyThread implements Runnable {
public void run() {
System.out.println(" this thread is running ... ");
}
} // end class MyThread
class ThreadEx2 {
public static void main(String [] args ) {
Thread t = new Thread(new MyThread());
// due to implementing the Runnable interface
// I can call start(), and this will call run().
t.start();
} // end main()
}
// end class ThreadEx2
25

Life Cycle of Thread

new
start()

wait()
sleep()
suspend()
blocked

runnable
stop()

dead

non-runnable
notify()
slept
resume()
unblocked
26

A Program with Three Java

Threads

Write a program that creates 3

threads

27

Three threads example

class A extends Thread

{
public void run()
{
for(int i=1;i<=5;i++)
{
System.out.println("\t From ThreadA: i= "+i);
}
System.out.println("Exit from A");
}
}
class B extends Thread
{
public void run()
{
for(int j=1;j<=5;j++)
{
System.out.println("\t From ThreadB: j= "+j);
}
System.out.println("Exit from B");
}
}

28

class C extends Thread

{
public void run()
{
for(int k=1;k<=5;k++)
{
System.out.println("\t From ThreadC: k= "+k);
}
System.out.println("Exit from C");

class ThreadTest
{
public static void main(String args[])
{
new A().start();
new B().start();
new C().start();
}
}

29

Run 1
[raj@mundroo] threads [1:76] java ThreadTest
From ThreadA: i= 1
From ThreadA: i= 2
From ThreadA: i= 3
From ThreadA: i= 4
From ThreadA: i= 5
Exit from A
From ThreadC: k= 1
From ThreadC: k= 2
From ThreadC: k= 3
From ThreadC: k= 4
From ThreadC: k= 5
Exit from C
From ThreadB: j= 1
From ThreadB: j= 2
From ThreadB: j= 3
From ThreadB: j= 4
From ThreadB: j= 5
Exit from B

30

Run2
[raj@mundroo] threads [1:77] java ThreadTest
From ThreadA: i= 1
From ThreadA: i= 2
From ThreadA: i= 3
From ThreadA: i= 4
From ThreadA: i= 5
From ThreadC: k= 1
From ThreadC: k= 2
From ThreadC: k= 3
From ThreadC: k= 4
From ThreadC: k= 5
Exit from C
From ThreadB: j= 1
From ThreadB: j= 2
From ThreadB: j= 3
From ThreadB: j= 4
From ThreadB: j= 5
Exit from B
Exit from A

31

Partitioning: Process
Parallelism

int add (int a, int b, int & result)

// function stuf
int sub(int a, int b, int & result)
// function stuf
Processor

IS1

pthread
pthreadt1,
t1,t2;
t2;
pthread-create(&t1,
pthread-create(&t1,add,
add,a,b,
a,b,&&r1);
r1);
pthread-create(&t2,
pthread-create(&t2,sub,
sub,c,d,
c,d,&&r2);
r2);
pthread-par
pthread-par(2,
(2,t1,
t1,t2);
t2);

add
add
Processor

IS2

sub
sub

Data
aa
bb
r1
r1
cc
dd
r2
r2

MISD and MIMD Processing

32

Partitioning: Data Parallelism

sort( int *array, int count)

//......
//......

pthread-t,
pthread-t,thread1,
thread1,thread2;
thread2;

pthread-create(&
pthread-create(&thread1,
thread1,sort,
sort,array,
array,N/2);
N/2);
pthread-create(&
pthread-create(&thread2,
thread2,sort,
sort,array,
array,N/2);
N/2);
pthread-par(2,
thread1,
thread2);
pthread-par(2, thread1, thread2);

Data
Processor

Sort
Sort
IS
Processor

Sort
Sort

SIMD Processing

do

dn/2
dn2/+1

dn
33

Multithreaded Server

Multithreaded Server
Client
Process

Server Process
Server
Threads

Client Process

User Mode
Kernel Mode
Message Passing
Facility

34

Architecture for Multithread

Servers

Multithreading enables servers to maximize

their throughput, measured as the number
of requests processed per second.
Threads may need to treat requests with
varying priorities:

A corporate server could prioritize request

processing according to class of customers.

Architectures:

Worker pool
Thread-per-request
Thread-per-connection
Thread-per-object
35

Client and server with threads

Thread 2 makes
requests to server
Thread 1
generates
results

Input-output

Receipt &
queuing

T1
Requests
N threads
Client
Server

In worker-pool architecture, the server creates a fixed pool of worker

threads to process requests.
The module receipt and queuing receives requests from
sockets/ports and places them on a shared request queue for retrieval
by the workers.

36

Alternative server threading

architectures
workers
I/O

a. Thread-per-request

remote
objects

per-connection threads
remote
objects

b. Thread-per-connection

per-object threads
I/O

remote
objects

c. Thread-per-object

37

Assignment 1: Multithreaded Dictionary

Server Demonstrate the use Sockets
and Threads

A Client Program
What is the Meaning of (Love)?

Love

Multithreaded
Dictionary Server
A deep, tender, inefable feeling of (try, dictionary.com)
afection and solicitude toward a
person
Solicitude
care or concern, as for
the well-being of
A Client Program
another
What is the Meaning of (Love)?

A Client
Program in C

A Client
Program in C++

38

Next Lecture

Thread Synchronisation
Thread Priorities

39

Accessing Shared Resources

Applications Access to Shared Resources

need to be coordinated.

Printer (two person jobs cannot be printed at

the same time)
Simultaneous operations on your bank
account.
Can the following operations be done at the
same time on the same account?

Deposit()
Withdraw()
Enquire()
40

Online Bank: Serving Many

Customers and Operations
PC client

Internet Bank
Server
Local Area Network

Bank
Database

PDA
41

Shared Resources

If one thread tries to read the data and

other thread tries to update the same
date, it leads to inconsistent state.
This can be prevented by synchronising
access to the data.
Use Synchronized method:

public synchronized void update()

{

}
42

the driver: 3rd Threads

sharing the same object
class InternetBankingSystem {
public static void main(String [] args ) {
Account accountObject = new Account ();
Thread t1 = new Thread(new MyThread(accountObject));
Thread t2 = new Thread(new YourThread(accountObject));
Thread t3 = new Thread(new HerThread(accountObject));

t1.start();
t2.start();
t3.start();
// DO some other operation
} // end main()
}
43

Shared account object

between 3 threads
class MyThread implements Runnable {
Account account;
public MyThread (Account s) { account = s;}
public void run() { account.deposit(); }
} // end class MyThread
class YourThread implements Runnable {
Account account;
public YourThread (Account s) { account = s;}
public void run() { account.withdraw(); }
} // end class YourThread
class HerThread implements Runnable {
Account account;
public HerThread (Account s) { account = s; }
public void run() {account.enquire(); }
} // end class HerThread

accoun
t
(shared
object)

44

Monitor (shared object access):

serializes operation on shared
object
class Account { // the 'monitor'
int balance;
// if 'synchronized' is removed, the outcome is unpredictable
public synchronized void deposit( ) {
// METHOD BODY : balance += deposit_amount;
}
public synchronized void withdraw( ) {
// METHOD BODY: balance -= deposit_amount;
}
public synchronized void enquire( ) {
// METHOD BODY: display balance.
}

}
45

Thread Priority

In Java, each thread is assigned priority,

which afects the order in which it is
scheduled for running. The threads so far
had same default priority
(NORM_PRIORITY) and they are served
using FCFS policy.

Java allows users to change priority:

ThreadName.setPriority(intNumber)

MIN_PRIORITY = 1
NORM_PRIORITY=5
MAX_PRIORITY=10

46

Thread Priority Example

class A extends Thread
{
public void run()
{
System.out.println("Thread A started");
for(int i=1;i<=4;i++)
{
System.out.println("\t From ThreadA: i= "+i);
}
System.out.println("Exit from A");
}
}
class B extends Thread
{
public void run()
{
System.out.println("Thread B started");
for(int j=1;j<=4;j++)
{
System.out.println("\t From ThreadB: j= "+j);
}
System.out.println("Exit from B");
}
}

47

Thread Priority Example

class C extends Thread
{
public void run()
{
System.out.println("Thread C started");
for(int k=1;k<=4;k++)
{
System.out.println("\t From ThreadC: k= "+k);
}
System.out.println("Exit from C");
}
}
class ThreadPriority
{
public static void main(String args[])
{
A threadA=new A();
B threadB=new B();
C threadC=new C();
threadC.setPriority(Thread.MAX_PRIORITY);
threadB.setPriority(threadA.getPriority()+1);
threadA.setPriority(Thread.MIN_PRIORITY);
System.out.println("Started Thread A");
threadA.start();
System.out.println("Started Thread B");
threadB.start();
System.out.println("Started Thread C");
threadC.start();
System.out.println("End of main thread");
}
}

48

Thread Programming
Thread concurrency/operation
models
models

The master/worker model

The peer model
A thread pipeline

49

The master/worker model

Program

Resources

Workers
taskX
taskX

Files
Databases

Master
Input (Stream)

main
main( () )

taskY
taskY

Disks
taskZ
taskZ

Special
Devices

50

Example

main() /* the master */

{
forever {
get a request;
switch( request )
case X: pthread_create(....,taskX);
case Y: pthread_create(....,taskY);
....
}
}
taskX() /* worker */
{
perform the task, sync if accessing shared resources
}
taskY() /* worker */
{
perform the task, sync if accessing shared resources
}
....
--Above runtime overhead of creating thread can be solved by thread pool
* the master thread creates all worker thread at program initialization
and each worker thread suspends itself immediately for a wakeup call
from the master

51

The peer model

Program

Input
Input

Resources

Workers
taskX
taskX

Files
Databases

taskY
taskY

Disks
taskZ
taskZ

Special
Devices

52

Example

main()
{
pthread_create(....,thread1...taskX);
pthread_create(....,thread2...taskY);
....
signal all workers to start
wait for all workers to finish
do any cleanup
}
}
taskX() /* worker */
{
wait for start
perform the task, sync if accessing shared resources
}
taskY() /* worker */
{
wait for start
perform the task, sync if accessing shared resources
}

53

thread pipeline
A thread Apipeline
Program

Filter Threads
Stage
Stage11

Stage
Stage22

Stage
Stage33

Input (Stream)

Resources

Files

Files

Files

Databases

Databases

Databases

Disks

Special Devices

Disks

Special Devices

Disks

Special Devices

54

Example
main()
{
pthread_create(....,stage1);
pthread_create(....,stage2);
....
wait for all pipeline threads to finish
do any cleanup
}
stage1() {
get next input for the program
do stage 1 processing of the input
pass result to next thread in pipeline
}
stage2(){
get input from previous thread in pipeline
do stage 2 processing of the input
pass result to next thread in pipeline
}
stageN()
{
get input from previous thread in pipeline
do stage N processing of the input
pass result to program output.
}

55

Java thread constructor and

management methods
Thread(ThreadGroupgroup,Runnabletarget,Stringname)
CreatesanewthreadintheSUSPENDEDstate,whichwillbelongtogroupand
beidentifiedasname;thethreadwillexecutetherun()methodoftarget.
setPriority(intnewPriority),getPriority()
Setandreturnthethreadspriority.
run()
Athreadexecutestherun()methodofitstargetobject,ifithasone,andotherwise
itsownrun()method(ThreadimplementsRunnable).
start()
ChangethestateofthethreadfromSUSPENDEDtoRUNNABLE.
sleep(intmillisecs)
CausethethreadtoentertheSUSPENDEDstateforthespecifiedtime.
yield()
EntertheREADYstateandinvokethescheduler.
destroy()
Destroythethread.
56

Java thread synchronization

calls
thread.join(intmillisecs)
Blocksthecallingthreadforuptothespecifiedtimeuntilthreadhasterminated.
thread.interrupt()
Interruptsthread:causesittoreturnfromablockingmethodcallsuchassleep().
object.wait(longmillisecs,intnanosecs)
Blocksthecallingthreaduntilacallmadetonotify()ornotifyAll()onobject
wakesthethread,orthethreadisinterrupted,orthespecifiedtimehaselapsed.
object.notify(),object.notifyAll()
Wakes,respectively,oneorallofanythreadsthathavecalledwait()onobject.

57

Scheduler activations
Process
A

P added
SA preempted

Process
B
Process

SA unblocked
SA blocked

Kernel

Virtual processors
A. Assignment of virtual processors
to processes

Kernel

P idle
P needed

B. Events between user-level scheduler & kernel

Key: P = processor; SA = scheduler activation

58

Invocations between address

spaces
(a) System call

Control transfer via

trap instruction

Thread

Control transfer via

privileged instructions
User

Kernel
Protection domain
boundary

(b) RPC/RMI (within one computer)

Thread 1

User 1

Thread 2

Kernel

User 2

(c) RPC/RMI (between computers)

Network

Thread 1

Thread 2

User 1

User 2
Kernel 1

Kernel 2

59

RPC delay against parameter

size
RPC delay

Requested data
size (bytes)
0

1000

2000
Packet
size

60

A lightweight remote
procedure call
Client

Server

A stack

A
4. Execute procedure
and copy results

1. Copy args

User

stub

stub

Kernel
2. Trap to Kernel

3. Upcall

5. Return (trap)

61

Times for serialized and

concurrent invocations
Serialised invocations

process args
marshal
Send

Receive
unmarshal
process results
process args
marshal
Send

Concurrent invocations

process args
marshal
Send
transmission
process args
marshal
Send
Receive
unmarshal
execute request
marshal
Send
Receive
unmarshal
process results

Receive
unmarshal
execute request
marshal
Send
Receive
unmarshal
execute request
marshal
Send

Receive
unmarshal
process results
Receive
unmarshal
execute request
marshal
Send

time

Receive
unmarshal
process results
Client

Server

Client

Server

62

Summary

Operating system provides various types of facilities to

support middleware for distributed system:

Multithreading enables servers to maximize their throughput,

measured as the number of requests processed per second.
Threads support treating of requests with varying priorities.
Various types of architectures can be used in current
processing:

encapsulation, protection, and concurrent access and

management of node resources.

Worker pool
Thread-per-request
Thread-per-connection
Thread-per-object

Threads need to be synchronized when accessing and

manipulating shared resources.
New OS designs provide flexibility in terms of separating
mechanisms from policies.
63