synchronized( this ){
.... // do the task
this.notify();
}
synchronized( task )
{
task.start();
try {
task.wait();
}
catch( InterruptedException e ){
... // do something if interrupted
}
}
Producer and Consumer Problem :
public void add( int num ){ ==> Prob.1 Busy Waiting , Prob.2 No Access Control
while( true ){
....
}
}
public synchronized void add( int num ){ ==> Prob.1 Busy Waiting
while( true ){
if( index < buffer.length ){
buffer[index++] = num;
return;
}
}
}
public synchronized void add( int num ){
while( index == buffer.length -1 ){
try
{
wait();
}
catch (InterrruptedException e)
{
}
}
buffer[index++] = num;
notifyAll();
}
Busy Waiting:
Thread task = new TheTask(); // Prob1. Busy Waiting
task.start();
; // do nothing
}
Thread task = new TheTask(); // Prob. None
synchronized( task )
{
task.start();
try {
task.wait();
}
catch( InterruptedException e ){
... // do something if interrupted
}
}
.....
class TheTask extends Thread {
public void run(){
synchronized( this ){
.... // do the task
this.notify();
}
}
}
1. Graphical user interface that perform lengthy I/O operations, caches
2. AJAX - web server response are processed asynchronously, and hence the JavaScript that runs to process the response possibly accesses data used by other parts of the application.
Thread
1. A fundamental unit of execution within an application
2. An application has at lease one thread.
3. Each thread has its own stack and runs independently from the application's other threads.
4. share resources such as file handles or memory
5. native or kernel-level thread: OS manages the thread
6. Preemptive threading: OS can suspend a thread's execution at any point in order to let another thread run.
7. Context switch: swapping one thread out and another
https://docs.google.com/document/d/1znFkZsnuWj0CI5yjNsiZGjQkReMBAKBg5566J4G3H-s/edit
Thread VS Process
1. thread: inside a process, within a program where CPU is fetching and executing instructions, make the progress of a process(program), a flow of control or line of execution
2. process: a program
System Threads versus User Threads
1. System threads: created and managed by the system
2. User threads: created and managed by the application to do the tasks that cannot or hsould not be done by the main thread
2. Event Thread: waits for and delivers events (such as mouse clicks and key presses) . to avoid blocking, applications creating threads to handle time-consuming operations, especially those involving network access.
Monitors(simpler) and Semaphores
Monitors
1. Thread synchronization: monitors and semaphores
2. Monitors: a set of routines that are protected by a Mutual Exclusion Lock.
3. Only one thread at a time acquiring the lock can execute within the monitor
4. Suspended thread : waiting thread
5. Wake up thread
Semaphores
1.A lock
2. Other is blocked until the owning thread releases the lock
3. mutual exclusion or mutex semaphore
4. Counting semaphores: let maximum of n threads access a resource at any given time
5. Event semaphores: notify one or all waiting threads that a even has occurred, but they all owrk in much the same way.
6. Cost: extra time is required to acquire the necessary lock
DeadLocks
1. shared resource
2. circular wait
3. No preemption
4.
1. Solution:forcefully terminate one of the thread
2. Best solution is deadlock avoidance
synchronized void someMethod(){
.... // the code to protect
}
is exactly equivalent to:
void someMethod(){
synchronized( this ){
.... // the code to protect
}
}
// A single central computer that controls multiple automated teller mahcines (ATMs) in different locations.
public class Account
{
int userNubmer;
String userLastNAMe;
String userFirstName;
double userBalance;
public Synchronized boolean deposit( double amount )
{
double newBalance;
if ( amount < 0.0)
return false;
else
{
newBalance = userBalance + amount;
userBalance = newBlaance;
return true;
}
}
public Synchronized boolean withdraw( double amount )
{
double newBalance;
if ( amount < 0.0)
return false;
else
{
newBalance = userBalance - amount;
userBalance = newBlaance;
return true;
}
}
}
public class Account {
int userNumber;
String userLastName;
String userFirstName;
double userBalance;
public boolean deposit( double amount ){
double newBalance;
if( amount < 0.0 ){
return false; /* Can’t add negative amt */
} else {
synchronized( this ){
newBalance = userBalance + amount;
userBalance = newBalance;
}
return true;
}
}
public boolean withdraw( double amount ){
double newBalance;
synchronized( this ){
if( amount < userBalance ){
return false; /* Insufficient funds */
} else {
newBalance = userBalance – amount;
userBalance = newBalance;
return true;
}
}
}
}
// Busy Waiting
// Consider a thread that spawns another thread to complete a task
// First thread cannot be a event thread (GUI thread)
// Queue pseudo-events for processing by the event thread, which is what second thread would do when it finished its task
// Solution: Busy waiting is avoided using a monitor or a semaphore
// Lock object can do wait and notify
Thread task = new TheTask();
task.start();
while ( task.isAlive() )
{
// do nothing
}
// Solution: Busy waiting is avoided using a monitor or a semaphore
// Lock object can do wait and notify
// wait in the main function and notify in each task object's run mehtod
// === simplified
Thread task = new TheTask();
synchronized ( task )
{
task.start();
try{
task.wait()
}
catch(){
// so somehting if interrupted
}
}
......
class TheTask extedns Thread
{
public void run()
{
synchronized(this)
{
// do the task
this.notify();
}
}
}
// === Not simplified
Object theLock = new Object();
Synchronized ( theLock )
{
Thread task = new TheTask( theLock );
task.start(); // Call task's run()
try{
theLock.wait();
}
catch ( InterruptedException e )
{
// do something if interrupted
}
}
......
class TheTask extends Thread
{
private Object theLock;
public TheTask( Object theLock )
this.theLock = theLock;
public void run()
{
synchronized( theLock )
{
// do the task
theLock.notify()
}
}
}
// Producer and consumer
// Fixed-size buffer and an index to access the buffer
public class IntBuffer
{
private int index;// current available
private int[] buffer = new int[8];
public synchronized void add(int num)
{
while (true)
{
if (index < buffer.length)
{
buffer[index++] = num;
return; // only happen once
}
}
}
public synchronized int remove()
{
while(true)
{
if (index > 0 )
{
return buffer[--index];
}
}
}
}
public class Producer extends Thread
{
private IntBuffer buffer;
public Producer(IntBuffer buffer){
this.buffer = buffer
}
public void run(){
Random r = new Random();
while(true){
int num = r.nextInt();
buffer.add( num );
System.out.println( "Produced" + num );
}
}
}
public class Consumer extends Thread
{
private IntBuffer buffer;
public Consumer(IntBuffer buffer)
{
this.buffer = buffer;
}
public void run(){
while(true){
int num = buffer.remove();
System.out.println("Consumed" + num);
}
}
}
public static void main (String[] )
{
IntBuffer b= new IntBuffer();
Producer p = new Producer(b);
Consumer c = new Consumer(b);
p.start();
c.start();
}
// Problem 1: busy waiting, while(true)
// Problem 2: no access control to share resource
// Solution : add Synchronized keyword to the add() and remove()
// Problem :the producer suspends itself when the buffer is full and waits for a slot to open up,
// While the consumer suspends itseft if the buffer is empty and waits for a new vlaue ot arive
public class IntBuffer
{
..index
.. buffer
.. synchonized void add..
{
// Do the task
while (index == buffer.length-1)
{
try{
wait();
}
catch ( InterruptedException e){
}
}
buffer[index +1] = num;
// Notify
notifyAll();
}
.... synchonized int remove....
{
while (index == 0)
{
try{
wait();
}
catch ( InterruptedException e){
}
}
int ret = buffer[--index];
notifyAll();
return ret;
}
}
// The dining Pholosophers
// Only one fork to eat
Problem 1: This application deadlocks when all philosophers have simultaneously picked up their left fork: Because no right fork is available to any philosopher, no philosopher can eat
Solution1: One solution is to add a timeout to the waiting: If a philosopher is not able to eat within a predetermined amount of time after acquiring the first fork, then the philosopher drops the fork and tries again.
Problem2: The flaw with this solution is that it’s possible for one or more philosophers to starve because they never acquire both forks. This is referred to as livelock.
Solution2:The best solution requires a very simple change to the application. Instead of having all the philosophers pick up the left fork first, have one of the philosophers pick up the right fork first:
public class DiningPholisphers
{
// Field
// Each “fork” is just an object we synchronize on
private Object[] forks;
private Philosophers[] philosophers;
// Constructor
// prepare the forks and philosophers
private DiningPholosophers( int num )
{
forks = new Object[num];
philosophers = new Philosopher[ num];
for (int i = 0 ; i < num ; i ++ )
{
forks[i] = new Object();
int fork1 = i;
int fork2 = (i+1)%num;
philosophers[i] = new Philosopher(fork1, fork2, (i+1)%num ); //
// ‘A’ B’ C’ D’ E’ (5+1)%5 = 1 ⇒ E’s right fork == fork1 = A’s left fork
// This one change to the fork pickup order is enough to break the deadlock and ensure that forks are always available to enable hungry philosophers to eat.
// Ori : 0,1 ; 1,2 ; 2,3; 3,4 ; 4,0;
// New : 1,0; 1,2 ; 2, 3; 3,4 ;4, 0
int fork1 = i;
int fork2 = (i+1)%num;
if (i == 0)
philosophers[0] = new Philosophers(0, fork2, fork1);
else
philosophers[i] = nwe Philosopher(i, fork1, fork2);
}
}
// Main funtion
public void startEating() throws InterrupedException
{
for (int i = 0; i < philosophers.length;i++)
philosophers[i].start();
// suspend the main thread until the first philosopher stops eating, which will never happen -- this keeps the simulation running indefinitely
philosophers[0].join();
}
public static void main (Stirng[] args)
{
try
{
DiningPhilosophers d = new DiningPhilosohers(5);
d.startEating();
}
catch (InterruptedException e)
{
}
}
}
// Each philosophers run in its own thread
private class Philosophers extends Thread
{
// Field
private itn id;
private int fork1;
private int fork2;
// Constructor
Philosopoher(int id , int fork1, int fork2)
{
this.id = id;
this.fork1 = fork1;
this.fork2 = fork2;
}
public void run()
{
status (“Ready to eat using forks” + fork1 + “ and “+ fork2);
pause(); // pause to let others get ready
while (true)
{
status(“Picking up fork ” + fork1);
Synchronized ( forks[fork1] )
{
status (“ Picking up fork” + fork2);
synchronized ( fork[fork2])
{
status(“Eating”);
}
}
}
}
private void pause()
{
try{
sleep(200);
}
catch (InterruptedException e)
{
// do nothing
}
}
private void status (String msg)
{
System.out.println(“Pholisopher ” +id + “;” + msg);
}
}
No comments:
Post a Comment