程序代写代做代考 Java algorithm CO2017 — Week3L2 — Synchronisation in Java
CO2017 — Week3L2 — Synchronisation in Java
CO2017 — Week3L2 — Synchronisation in Java
Dr Gilbert Laycock (gtl1)
2017–02–05
gtl1–R914 W3L2 — Java Synchronisation 2017–02–05 1 / 16
Recap/overview
Recap 1: Critical code
Concurrent processes are interleaved unpredictably
Some code sections are critical, and we want to achieve: mutual
exclusion; progress; bounded waiting
Possible techniques considered: disable interrupts; access in
turns; Peterson’s algorithm; semaphores
gtl1–R914 W3L2 — Java Synchronisation 2017–02–05 2 / 16
Recap/overview
Recap2: Java threads
Any Java program has one special thread that runs main method
We can define an arbitrary number of additional threads.
Defining a new thread requires two things:
Define a new class implementing interface Runnable (or directly
extend the Thread class)
In function main, define one or more instances of the new
Runnable/Thread class.
gtl1–R914 W3L2 — Java Synchronisation 2017–02–05 3 / 16
Recap/overview
Overview
Semaphores in Java
Mutual exclusion with semaphores
Producer/consumer example
Implement producer/consumer example using semaphores
gtl1–R914 W3L2 — Java Synchronisation 2017–02–05 4 / 16
Recap/overview
Java interface for the Semaphore class
class Semaphore {
private int value;
public Semaphore (int init) { value = init; }
public void Wait()
{
…???…
}
public void Signal() {
…???…
}
}
gtl1–R914 W3L2 — Java Synchronisation 2017–02–05 5 / 16
Recap/overview Simple example of mutual exclusion using a semaphore
Mutual Exclusion with Semaphore
class Thread_i extends Thread {
Semaphore mutex;
public Thread_i(Semaphore s) { mutex = s; }
public void run() {
while (true) {
noncritical_i;
mutex.Wait(); critical_i; mutex.Signal();
}
}
}
public class Controller {
public static void main() {
Semaphore s = new Semaphore(1)
Thread_1 t1 = new Thread_1(s);
……
Thread_n tn = new Thread_n(s);
t1.start(); …; tn.start();
}
}
gtl1–R914 W3L2 — Java Synchronisation 2017–02–05 6 / 16
Recap/overview Trace of mutual exclusion
How Semaphore Ensures Mutual Exclusion?
Consider three processes t1, t2 and t3
s t1 t2 t3
Initially 1 start start start
t1 executes Wait() 0 start start start
t2 executes Wait() 0 crit blocked start
t3 executes Wait() 0 crit blocked blocked
t1 executes Signal() 0 noncrit crit blocked
t1 executes Wait() 0 blocked crit blocked
…………………….
Once one process enters its critical section, the others must wait
gtl1–R914 W3L2 — Java Synchronisation 2017–02–05 7 / 16
Introducing the producer/consumer problem
The Producer and Consumer Problem
Problem description:
a producer repeatedly produces items and places them into a
buffer;
meanwhile a consumer consumes the items one-by-one by taking
from the buffer.
Requirements:
Assume an implementation of a bounded FIFO buffer with operations
place() and take()
The producer may produce a new item only when the buffer is not full
The consumer may consume an item only when the buffer is not empty
All items produced are eventually consumed
gtl1–R914 W3L2 — Java Synchronisation 2017–02–05 8 / 16
Introducing the producer/consumer problem Solution overview
Behaviour of the FIFO Buffer
Implementation as an array.
We need NextIn and NextOut to locate where to place an item into
and take an item from the buffer
NextIn and NextOut are incremented one by one. When they reach the
end of the buffer we need roll-over to 0.
gtl1–R914 W3L2 — Java Synchronisation 2017–02–05 9 / 16
Introducing the producer/consumer problem Using semphores to control access to the queue
Design of Solution using semaphores
Use a semaphore ItemsReady to record the number of items in the
buffer
The consumer must be blocked on the semaphore ItemsReady when it
is 0, i.e. when the buffer is empty, the consumer cannot proceed.
The initial value of ItemsReady should be 0 (since the queue is empty).
After the producer places an item, it should signal on the semaphore
ItemsReady.
Use a semaphore SpacesLeft to record free spaces in the buffer; its
initial value should be the buffer size.
The producer should be blocked when SpacesLeft is 0.
After the consumer takes an item, it should signal on the semaphore
SpacesLeft.
gtl1–R914 W3L2 — Java Synchronisation 2017–02–05 10 / 16
Introducing the producer/consumer problem Implementation of producer/consumer
The Buffer Class
public class Buffer {
public static final int BUFFSIZE = 5;
private int[] _b = new int[BUFFSIZE];
private int _NextIn, _NextOut;
public Buffer() { _NextIn = 0; _NextOut = 0; }
public void place(int item) {
_b[_NextIn] = item;
_NextIn = (_NextIn + 1)%BUFFSIZE;
}
public int take() {
int value = _b[_NextOut];
_NextOut = (_NextOut + 1)%BUFFSIZE;
return value;
}
gtl1–R914 W3L2 — Java Synchronisation 2017–02–05 11 / 16
Introducing the producer/consumer problem Implementation of producer/consumer
The Buffer Class (Cont’d)
public static void main(String[] args) {
Semaphore MutEx = new Semaphore(1);
Semaphore ItemsReady = new Semaphore(0);
Semaphore SpacesLeft = new Semaphore(BUFFSIZE);
Buffer buff = new Buffer();
Producer p = new Producer(buff, MutEx,
ItemsReady, SpacesLeft);
Consumer c = new Consumer(buff, MutEx,
ItemsReady, SpacesLeft);
p.start(); c.start();
}
}
gtl1–R914 W3L2 — Java Synchronisation 2017–02–05 12 / 16
Introducing the producer/consumer problem Implementation of producer/consumer
The Producer Class
class Producer extends Thread {
Buffer _b; Semaphore _mx;
Semaphore _ready; Semaphore _spaces;
public Producer (Buffer buff, Semaphore mutEx,
Semaphore itemsReady,
Semaphore spacesLeft) {
_b = buff; _mx = mutEx;
_ready = itemsReady; _spaces = spacesLeft;
}
public void run() {
for (int i=1; i<=100; ++i) { _spaces.Wait(); // wait for spaces _mx.Wait(); // wait for mutual exclusion _b.place(i); // place an item _mx.Signal(); // release mutual exclusion _ready.Signal();// signal the consumer } } } gtl1–R914 W3L2 — Java Synchronisation 2017–02–05 13 / 16 Introducing the producer/consumer problem Implementation of producer/consumer The Consumer Class class Consumer extends Thread { Buffer _b; Semaphore _mx; Semaphore _ready; Semaphore _spaces; public Consumer (Buffer buff, Semaphore mutEx, Semaphore itemsReady, Semaphore spacesLeft) { _b = buff; _mx = mutEx; _ready = itemsReady; _spaces = spacesLeft; } public void run() { int value; for (int i=1; i <= 100; i++) { _ready.Wait(); // wait for items ready _mx.Wait(); // wait for mutual exclusion value = _b.take(); // take an item _mx.Signal(); // release mutual exclusion _spaces.Signal(); // signal the producer System.out.println(value); } } } gtl1–R914 W3L2 — Java Synchronisation 2017–02–05 14 / 16 Introducing the producer/consumer problem Implementation of producer/consumer Be Careful! What if ready.Wait(); mx.Wait() was swapped to mx.Wait(); ready.Wait() ? Answer: Exchanging the two Wait()s is fatal Consumer executes mx.Wait() and ready.Wait() and is blocked Producer executes spaces.Wait() and mx.Wait() and is blocked Deadlock: A process is said to be deadlocked if it is waiting for an event which will never happen gtl1–R914 W3L2 — Java Synchronisation 2017–02–05 15 / 16 Summary Summary A semaphore is a primitive to synchronise threads. A semaphore has Wait() and Signal() operations to guarantee mutual exclusion of threads relevant to one shared object. Demonstrated the application of semaphores for the Producer and Consumer problem. gtl1–R914 W3L2 — Java Synchronisation 2017–02–05 16 / 16
