Kĩ thuật lập trình - Chapter 17: Concurrent programming

Programming Languages2nd editionTucker and NoonanChapter 17Concurrent ProgrammingTwo roads diverged in a yellow wood,And sorry I could not travel both ... Robert Frost, The Road Not TakenContents17.1 Concurrency Concepts17.2 Synchronization Strategies17.3 Synchronization in Java17.4 Interprocess Communication 17.5 Concurrency in Other LanguagesConcurrency occurs at many levelsMore realisticCan be more efficientCarries unique, fundamental complexitiesTraditionally studied in the context of operating systems Example: client-server application such as web browsing17.1 Concurrency ConceptsExample: web browser rendering a pagePage is a shared resourceThread for each image loadThread for text renderingCannot all write to page simultaneouslyThread for user input; e.g., Stop buttonMultiprogramming: several programs loaded into memory and executed in an interleaved mannerScheduler: switches from one program or thread to anotherTime-sharing: allow multiple users to communicate with a computer simultaneouslyProcess: an execution context, including registers, activation stack, next instruction to be executed, etc.Defn: A concurrent program is a program designed to have two or more execution contexts. Such a program is said to be multithreaded, since more than one execution context can be active simultaneously.Parallel program: 2 or more threads simultaneously active.Distributed program: designed so that different pieces are on computers connected by a network.Concurrency: a program with multiple, active threads.Single threaded: all earlier programs.States of a thread:Created: but not yet ready to runRunnable: ready to run; awaiting a processorRunning: executingBlocked: waiting on some resourceTerminated: stoppedStates of a ThreadFigure 17.1Inter-thread communication needs to occur:Thread requires exclusive access to some resourceThread needs to exchange data with another threadCan communicate via:Shared variablesMessage passingParametersA race condition occurs when the resulting value of a variable depends on the execution order of two or more threads.Ex: c = c + 1Machine level:load cadd 1store cIf c initially 0:With 2 threads, can get 1 or 2With n threads, can get 1, 2, ..., nA deadlock occurs when a thread is waiting for an event that will never happen.Necessary conditions for a deadlock to exist:Threads claim exclusive access to resources.Threads hold some resources while waiting for others.Resources may not be removed from waiting threads (preemption).A circular chain of threads exists in which each thread holds a resource needed by the next thread in the chain.SemaphoresA semaphore is an integer variable and an associated thread queue.Operations:P(s) -- if s > 0 then s-- else enqueue threadV(s) -- if a thread is enqueued then dequeue it else s++Binary semaphoreCounting semaphoreprogram SimpleProducerConsumer;var buffer : string; full : semaphore = 0; empty : semaphore = 1;...begin cobegin Producer; Consumer; coend;end.procedure Producer;var tmp : stringbegin while (true) do begin produce(tmp); P(empty); { begin critical section } buffer := tmp; V(full); { end critical section } end;end;procedure Consumer;var tmp : stringbegin while (true) do begin P(full); { begin critical section } tmp := buffer; V(empty); { end critical section } consume(tmp); end;end;program ProducerConsumer;const size = 5;var buffer : array[1..size] of string; inn : integer = 0; out : integer = 0; lock : semaphore = 1; nonfull : semaphore = size; nonempty : semaphore = 0;...procedure Producer;var tmp : stringbegin while (true) do begin produce(tmp); P(nonfull); P(lock); { begin critical section } inn := inn mod size + 1; buffer[inn] := tmp; V(lock); { end critical section } V(nonempty); end;end;procedure Consumer;var tmp : stringbegin while (true) do begin P(nonempty); P(lock); { begin critical section } out = out mod size + 1; tmp := buffer[out]; V(lock); { end critical section } V(nonfull); consume(tmp); end;end;MonitorsEncapsulates a shared resource together with access functions.Locking is automatic.Condition -- thread queuesignalwaitmonitor Buffer;const size = 5;var buffer : array[1..size] of string; in : integer = 0; out : integer = 0; count : integer = 0; nonfull : condition; nonempty : condition;procedure put(s : string);begin if (count = size) then wait(nonfull); in := in mod size + 1; buffer[in] := tmp; count := count + 1; signal(nonempty);end;function get : string;var tmp : stringbegin if (count = 0) then wait(nonempty); out = out mod size + 1; tmp := buffer[out]; count := count - 1; signal(nonfull); get := tmp;end;States of a Java ThreadFigure 17.6Example: Bouncing BallsState of a ball in motion:Location: x, y coordinatesDirection and velocity: dx, dySize in pixelsColor (fun!)Ball methods:Constructormove: one step (delta)paintpublic class Ball { Color color = Color.red; int x; int y; int diameter = 10; int dx = 3; int dy = 6;public Ball (int ix, int iy) { super( ); x = ix; y = iy; color = new Color(x % 256, y % 256, (x+y) % 256); dx = x % 10 + 1; dy = y % 10 + 1;} public void move () { if (x = BouncingBalls.width) dx = - dx; if (y = BouncingBalls.height) dy = - dy; x += dx; y += dy;} public void paint (Graphics g) { g.setColor(color); g.fillOval(x, y, diameter, diameter); }public class BouncingBalls extends JPanel { public final static int width = 500; public final static int height = 400; private Ball ball = new Ball(128, 127); private Vector list = new Vector();public BouncingBalls ( ) { setPreferredSize(new Dimension(width, height)); list.add(ball); addMouseListener(new MouseHandler()); BallThread bt = new BallThread(); bt.start( ); } private class MouseHandler extends MouseAdapter { public void mousePressed(MouseEvent e) { Ball b = new Ball(e.getX(), e.getY()); list.add(b); } // mousePressed } // MouseHandler private class BallThread extends Thread { public boolean cont; public void run( ) { cont = true; while (cont) { for (Ball b : list) { b.move(); } repaint( ); try { Thread.sleep(50); } catch (InterruptedException exc) { } }}} public synchronized void paintChildren(Graphics g) { for (Ball b : list) { b.paint(g); } } public static void main(String[] args) { JFrame frame = new JFrame("Bouncing Balls"); frame.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE); frame.getContentPane().add(new BouncingBalls( )); frame.setLocation(50, 50); frame.pack(); frame.setVisible(true);}Buffer ClassFigure 17.13Producer ClassFigure 17.14Consumer ClassFigure 17.15Bounded Buffer ClassFigure 17.16Sieve of EratosthenesFigure 17.18Test Drive for Sieve of EratosthenesFigure 17.18