程序代写代做代考 algorithm database scheme c# data structure Java compiler jvm concurrency x86 distributed system gui CE303 Lecture 2

CE303 Lecture 2

PART I
Introduction

Concurrent Systems
A system is concurrent if some of its activities can occur simultaneously
“at the same time”
execution of activities can overlap
Concurrent systems are everywhere
human body, university, car, …
Concurrency in computing
physical: distributed systems, multi-processor machines, graphics processor, devices (RAM, I/O, sound card), …
logical: multiple apps/threads running “in parallel” on one device
Concurrency may just be virtual, like when using time slicing to run processes concurrently on a single-core machine

3

Processes and threads
Process is an OS entity corresponding to an app instance
A process, in the simplest terms, is an executing program
Each process has its own address space
Each process’s address space is isolated
OS are usually capable of running several processes
Special mechanisms for processes to communicate: sockets, signals, remote method invocation, …

Processes and threads
Thread is an OS entity corresponding to a stream of instructions
One or more threads run in the context of the process
Each thread belongs to exactly one process and uses its address space
Each process has at least one thread (think of the main function)
A thread can execute any part of the process code, including parts currently being executed by another thread.

OS support of parallelism
OS will run all the threads ‘in parallel’
What if there are more threads than CPU cores?
OS uses time slicing to run several threads concurrently on a single core

Switching processes is expensive (because it involves address space switching)
Switching threads is cheaper
Allocation of computing resources (i.e. CPU time) is controlled by process and thread priorities

time

Image Source: http://web.mit.edu/6.031/www/fa17/classes/19-concurrency/
On most systems, time slicing happens unpredictably and non-deterministically, meaning that a thread may be paused or resumed at any time.
6

Operating System Processes
Modern OS like Unix or Windows support multiple processes (“multitasking”)
java MyProg creates a new process
Each process has an independent address space: processes do not share variables
Managed by the operating system
OS ensures processes do not interfere (“isolated”)
need special mechanisms for communication like signals, sockets, remote method invocation
Switching processes is relatively slow
requires a lot of copying and loading

7

(Java) Threads
“Lightweight” concurrent processing
Each thread is an independent flow of control with its own local variables
A process can have many threads
Threads can share some part of the address space
In Java, this means that there may be shared objects that can be accessed from different threads
Java threads are managed by JVM
scheduler activates/ deactivates threads
Each Java program starts with one thread: main()
Switching threads is relatively fast

8

Shared Memory
Each thread has its own context
Stack: local variables, call stack
CPU registers including the program counter pc
Any items on the heap are potentially shared

pc=…

pc=…

pc=…

Not shared:
locals and
registers
Shared:
objects and
static fields

END OF PART I

PART II
Threads in Java

Defining and Running a New Thread in Java
Define a class that implements Runnable
Runnable has only one method: void run()
This method defines what the thread should do, similar to the main() method; the thread terminates when run() exits
Construct an object of this class
Construct a thread from the object
Start thread

Alternatively, use a lambda expression
Alternatively, obtain a Thread object by extending class Thread and override run()
This approach can save some lines of code
Disadvantage: can not inherit from other classes (as you’ve already extended Thread)

12

public class Greeter implements Runnable {
private String greeting;
private static final int REPETITIONS = 8;
private static final int DELAY = 100;
public Greeter(String aGreeting) { greeting = aGreeting; }

public void run() {
try {
for (int i = 1; i <= REPETITIONS; i++) { System.out.println(i + ": " + greeting); Thread.sleep(DELAY); } } catch (InterruptedException exception) {} } public static void main(String[] args) { … } Concurrent Greeter Threads (Java, slide 1) 13 Concurrent Greeter Threads (Java, slide 2) public static void main(String[] args) { Runnable r1 = new Greeter("Hello, World!"); Runnable r2 = new Greeter("Goodbye, World!"); Thread t1 = new Thread(r1); Thread t2 = new Thread(r2); t1.start(); t2.start(); } Thread.start() returns immediately after launching the thread – it does not wait for it to finish. Question: What would happen if main called r1.run() and r2.run() instead of starting new threads? 14 Greeter Threads: Two Sample Program Runs Run 1 1: Hello! 1: Goodbye! 2: Hello! 2: Goodbye! 3: Hello! 3: Goodbye! 4: Hello! 4: Goodbye! 5: Hello! 5: Goodbye! 6: Hello! 6: Goodbye! 7: Hello! 7: Goodbye! 8: Goodbye! 8: Hello! Run 2 1: Hello! 1: Goodbye! 2: Hello! 2: Goodbye! 3: Goodbye! 3: Hello! 4: Hello! 4: Goodbye! 5: Goodbye! 5: Hello! 6: Hello! 6: Goodbye! 7: Goodbye! 7: Hello! 8: Hello! 8: Goodbye! 15 Thread state diagram New Runnable Dead Blocked Started Finished or terminated Suspended, entered sleeping, acquiring lock, waiting for another thread Resumed, sleeping finished, acquired lock, another thread finished Java and C# define more states, e.g., they have variations of the Blocked state 16 Thread states Each thread has a state Once created, a thread needs to be started Thread runs until its main method exits or it is terminated When a thread runs, it switches between the runnable and blocked states Runnable means actually running the code (utilising CPU) Blocked means waiting for something In real life, a typical thread spends most of the time in the blocked state Waiting for user input Waiting for I/O Waiting to acquire some shared resource Sleeping Etc. 17 Thread scheduling JVM and .NET Framework include thread schedulers – usually only wrappers for the functionality of the operating system Scheduler de-activates a thread if run() exits the thread calls yield() – voluntarily give up CPU resource the thread is blocked (waits for something) OS decides to switch to another thread (time slicing) Scheduler looks only at the runnable threads prefers threads with higher priority, also aging schemes Scheduler is likely to activate a blocked thread immediately after it being unblocked – better than using timers and check periodically some variable’s state Blocked thread consumes very little computational resources 18 It is the resposibility of the OS (or the JVM in Java) to switch the context based on underlying operating system and memory model. We can write code to control the scheduling of the threads More info about scheduling: https://www.tutorialandexample.com/thread-scheduler-in-java/ Terminating threads Thread terminates when run() exits If you want to tell a thread to terminate, you can inform it by calling Thread.interrupt() this will set a boolean field in the Thread data structure A thread should check regularly if it is meant to stop call isInterrupt() or perform sleep or wait, and catch InterruptedException You can also use shared variable(s) to communicate that a thread should stop Method isAlive() returns true if a thread has been started but it has not terminated yet Threads are not re-startable 19 Typical Structure: Runnable with Loop public class MyRunnable implements Runnable { public void run() { try { while (…) { doWork(); Thread.sleep(…); } } catch (InterruptedException e) { … } } } 20 END OF PART II PART III Synchronisation Concurrency: Interleaving Consider threads t1, t2 with run() methods consisting of two statements each: t1: public void run() {a; b} t2: public void run() {c; d} Assume execution of individual statements is “atomic” and “mutually exclusive” Can a be executed before c? Can a be executed after d? Execution of t1 and t2 is “interleaved” All you know is “a before b” and “c before d” even that could be wrong due to compiler optimisations 23 public class CounterThread extends Thread { static int TOTAL = 0; static int REPETITIONS = 1000; public CounterThread() { this.start(); } public static void inc() { TOTAL++; } @Override public void run() { for (int i = 0; i < REPETITIONS; i++) inc(); } public static void main(String[] args) throws Exception{ Thread t1 = new CounterThread(); System.out.println("Total = " + TOTAL); } } CounterThread (Java, slide 1) What is the TOTAL value going to be when we print it? 24 CounterThread It’s not necessarily 1000!!! The main method is also running on one thread This is the default main thread in Java created by the JVM When our thread t1 is inside the loop counting the values between 0 and 1000, the main thread does not wait Thus it prints the value of TOTAL at that instance public static void main(String[] args) throws Exception { Thread t1 = new CounterThread(); t1.join(); System.out.println("Total = " + TOTAL); } } CounterThread (Java, slide 2) The TOTAL now would be 1000, as expected! 26 Thread Method join() t.join() waits for thread t to terminate before proceeding t.join(maxTime) waits at most for maxTime (in ms) This is useful when a parent thread creates one or more child threads to do some work Parent thread waits for answers before proceeding Also useful if you want to calculate how long it took until a started thread has finished In our example, it is needed in CounterThread.main() to ensure that it prints the total after the t1 thread has finished 27 public static void main(String[] args) throws Exception { Thread t1 = new CounterThread(); Thread t2 = new CounterThread(); t1.join(); t2.join(); System.out.println("Total = " + TOTAL); } } CounterThread (Java, slide 3) What is the TOTAL value going to be when we print it? 28 Results from Running CounterThread Run 1: total = 2000 Run 2: total = 2000 Run 3: total = 1743 Run 4: total = 2000 Run 5: total = 1209 29 Thread Interleaving – CounterThread Thread t1.inc() Thread t2.inc() total++ total++ fetch total return fetch total return total 0 0 1 1 1 1 30 Race Conditions in Threads When two or more concurrent threads access a common variable – potential trouble! problem caused by interleaved reading and writing of shared objects, reading on its own is ok sometimes called race conditions as result depends on who gets access first Missing atomicity of statements a thread can yield control half-way through updating a shared object, leaving it in an inconsistent state Leads to very bad kind of programming errors program works “nearly always” Java solution: synchronisation and locks 31 Synchronised Methods and Locks Java offers synchronized methods “mutual exclusion” for critical code public synchronized void myMethod (…) {…} Each Java object has a built-in “monitor lock” when a synchronised method is started, it needs to obtain the lock of the object to which it is applied this stops more than one synchronized method to be applied to this object at the same time. A static synchronized method locks the class object Java also has an interface Lock and several implementing classes including ReentrantLock explicit lock()/unlock() methods good for coding more sophisticated locking behaviour 32 Visualizing Locks Object = phone booth Thread = person Locked object = closed booth Blocked threads = people waiting for booth to open Monitor/lock = ensures at most one person is in the booth at any time 33 Source: [Horstmann OOP&D] Synchronized CounterThread Change inc() declaration to: public static synchronized void inc() { … } Now the value of total is always the same as the overall number of invocations of method inc(): Run 1: total = 2000 Run 2: total = 2000 Run 3: total = 2000 34 CounterThread: Which Object is Locked? Method inc() is static. This means that the lock is on the CounterThread.class object There is only one of these in the JVM so at most one thread can carry out method inc() at any point in time Warning: if method inc() was not static, the program above would synchronise on instances of class CounterThread This would mean, there would be two locks, one for thread t1 and one for thread t2 Thus there would be no contention for the locks, and no protection against concurrent modification of total For more information, see: http://tutorials.jenkov.com/java-concurrency/synchronized.html 35 There can of course be cases that we don’t want to synchronize a static method. E.g., imagine we only have a single object instance, and we want to parallelize a method of this class. Then it does not need to be static. CounterThread Synchronized Thread t1.inc() Thread t2.inc() total++ total++ fetch total return fetch total return total 0 0 1 1 2 2 36 Block Synchronization Can also synchronise a block of code by associating it explicitly with an object that gets locked / unlocked Suppose we have two bank account objects use synchronisation to avoid interference when transferring money from one account to another synchronized (account1) { synchronized (account2) { account1.transfer( -amount ); account2.transfer( amount ); } } 37 To synchronize a single variable, we can use AtomicReference, see the example with AtomicInteger a few slides later. Remarks about synchronized CounterThread is correct after adding synchronized We have made method inc() “atomic”, so two calls of this method can no longer overlap But: the code is a LOT slower than the incorrect, unsynchronised version, up to a factor ~100 during testing Only use synchronisation when necessary When you do need it, be sure to use it! 38 Threads in C# C# API for handling threads is mainly similar to that in Java C# neatly uses delegates to create threads – functionality unavailable in Java When creating a thread, you specify which method it will run C# supports synchronized blocks (it uses keyword lock instead) C# does not have synchronized methods Greeter in C# (slide 1) public class Greeter { private readonly String greeting; private static readonly int repetitions = 8; private static readonly int delay = 100; public Greeter(string greeting) { this.greeting = greeting; } public void Run() { for (int i = 1; i <= repetitions; i++) { Console.WriteLine(i + ": " + greeting); Thread.Sleep(delay); } } } Greeter in C# (slide 2) class Program { static void Main(string[] args) { Greeter g1 = new Greeter("Hello, World!"); Greeter g2 = new Greeter("Goodbuy, World!"); Thread t1 = new Thread(g1.Run); Thread t2 = new Thread(g2.Run); t1.Start(); t2.Start(); t1.Join(); t2.Join(); } } CounterThread in C# (slide 1) class Program { static void Main(string[] args) { var t1 = new Thread(Run); var t2 = new Thread(Run); t1.Start(); t2.Start(); t1.Join(); t2.Join(); Console.WriteLine(total); } … CounterThread in C# (slide 2) … static int total = 0; const int repetitions = 1000; private static object sync = new object(); public static void Inc() { lock (sync) total++; } public static void Run() { for (int i = 0; i < repetitions; i++) Inc(); } } More efficient synchronisation: AtomicInteger (Java) The object stores a single integer Provides synchronised functionality with integers int getAndIncrement() equivalent to value++ int addAndGet(int delta) equivalent to value += delta int getAndSet(int newValue) sets the value and returns the old value All operations are thread safe Much faster then using synchronized methods / blocks Where possible, exploits platform-specific instructions Most CPUs (e.g. x86 since 80486) support this on the hardware level Interlocked (C#) Interlocked class gives access to the same functionality, i.e. enables efficient atomic operations with integers As C# has call-by-reference, you don’t need to create special objects – you use static methods of class Interlocked: public static void Inc() { Interlocked.Increment(ref total); } If you were not using call-by-reference, then we’d have the relevant variable sitting outside the method, and then we’d need to lock it in a different way, such as creating an object and lock it, like we did in Java. 45 END OF PART III PART IV Deadlocks Dining Philosophers 48 Deadlock (“Starvation”) Dining philosophers example: philosophers sit at a round table eat spaghetti with two forks assume a philosopher first picks up fork to the right, then picks up fork to the left, then eats, then drops forks what if everyone picks up fork to their right immediately? Deadlock situation can arise whenever you have at least two threads and two locks (think of only 2 philosophers and 2 forks): Thread (Philosopher) 1 acquires lock on object (fork) A Thread (Philosopher) 2 acquires lock on object (fork) B Thread (Philosopher) 1 waits for lock on object (fork) B Thread (Philosopher) 2 waits for lock on object (fork) A Deadlock avoidance programs need to ensure deadlocks are impossible 49 Coarse-grained Concurrency Res. 1 Res. 2 Res. 3 Res. n Uses a single lock for an entire set of resource objects (indicated by the "orange border" in the image) When one thread has acquired the lock, it stops all others threads from accessing any of the objects in the set No danger of deadlock Potentially inefficient as it may cause unnecessary blocking of threads 50 Fine-grained Concurrency A separate lock for each resource A thread acquires locks for those objects involved in the current transaction. Potentially more efficient than a more coarse-grained strategy less blocking of threads actual gain depends on various factors such as processor cores, etc. Danger of deadlock if threads need to acquire (and return) multiple locks for a transaction Res. 1 Res. 2 Res. 3 Res. n 51 Coarse-Grained Dining Philosophers Implementing a coarse-grained solution for the dining philosophers is straightforward The synchronisation is done on the entire set of forks So at most one philosopher can access the forks This prevents deadlock But it makes for slow eating If we interpret the philosophers as processors and eating as “doing work”, then at most one processor is actually working at any point in time 52 public abstract class Philosopher implements Runnable { static class Fork { int holder; Fork(int holder) { this.holder = holder; } } final static int COUNT = 5; final static Fork[] forks = new Fork[COUNT]; static { for (int i = 0; i < COUNT; i++) forks[i] = new Fork(-1); } int id; Philosopher(int id) { this.id = id; } public abstract void run(); public void takeFork(int i) {…} public void dropFork(int i) {…} public void eat() {…} } 53 public class PhilosopherCoarse extends Philosopher { public PhilosopherCoarse(int id) { super(id); } @Override public void run() { int fst = id; int snd = (id + 1) % COUNT; synchronized (forks) { takeFork(fst); takeFork(snd); eat(); dropFork(snd); dropFork(fst); } } } 54 Program Output: PhilosopherCoarse Philosopher 0 takes fork 0 Philosopher 0 takes fork 1 Philosopher 0 is eating... Philosopher 0 drops fork 1 Philosopher 0 drops fork 0 Philosopher 9 takes fork 9 Philosopher 9 takes fork 0 Philosopher 9 is eating... Philosopher 9 drops fork 0 Philosopher 9 drops fork 9 Philosopher 7 takes fork 7 ... duration = 5053 ms Fine-grained Dinging Philosophers Lock only the forks needed by each philosopher the synchronisation ensures that no two philosophers can pick up one fork at the same time BUT: need to be careful about how we request the locks Otherwise, could end up in a state of deadlock Simple deadlock-avoidance strategy: restrict order of requests: first philosopher takes right fork first, then left fork; all other philosophers take left fork first, then right fork Other deadlock-avoidance strategies are possible 56 public class PhilosopherFine extends Philosopher { public PhilosopherFine(int id) { super(id); } @Override public void run() { // Deadlock prevention int fst = (id == 0 ? id : (id + 1) % COUNT); int snd = (id == 0 ? 1 : id); synchronized (forks[fst]) { takeFork(fst); synchronized (forks[snd]) { takeFork(snd); eat(); dropFork(snd); } dropFork(fst); } } } 57 Program Output: PhilosopherFine Philosopher 0 takes fork 0 Philosopher 2 takes fork 3 Philosopher 1 takes fork 2 Philosopher 0 takes fork 1 Philosopher 3 takes fork 4 Philosopher 0 is eating... Philosopher 5 takes fork 6 Philosopher 5 takes fork 5 Philosopher 5 is eating... Philosopher 6 takes fork 7 Philosopher 7 takes fork 8 Philosopher 8 takes fork 9 ... duration = 2543 ms END OF PART IV PART V More advanced synchronisation Synchronisation primitives Synchronized/lock sections have very limited functionality There exist multiple synchronisation primitives (tools) including Mutex allows at most one thread at a time to access some resource Semaphore allows at most n threads at a time to access some resource Barrier synchronises several threads; a thread will wait until all other threads complete some task 61 Cyclic Barriers CyclicBarrier in Java (Barrier in C#) allows a fixed number of threads to wait for each other at some common barrier point CyclicBarrier.await() blocks until that has happened Called “cyclic” because the barrier can be re-used after waiting threads have been released Cyclic barrier can be set up with a barrier action that is executed once per barrier point, after the last thread in the party arrives, but before any threads are released. Java example: CyclicBarrierDemo 62 public class CyclicBarrierDemo { final static int COUNT = 3; final static int REPEATS = 3; final static CyclicBarrier cb = new CyclicBarrier(COUNT, () -> System.out.println(“All done”));
static class Task implements Runnable {
int id;
Task(int id) { this.id = id; }
public void run() {
for (int i = 0; i < REPEATS; i++) { System.out.println("Thread " + id + " done"); try { cb.await(); } catch (Exception e) {} } } } public static void main(String[] args) { for (int i = 0; i < COUNT; i++) new Thread(new Task(i)).start(); } } COUNT refers to the number of threads REPEATS to the number of iterations 63 CyclicBarrierDemo Output Thread 0 done Thread 2 done Thread 1 done All done Thread 1 done Thread 2 done Thread 0 done All done Thread 2 done Thread 0 done Thread 1 done All done Concurrency in GUI GUI libraries usually do not support concurrency The entire GUI is supposed to operate from a single thread Events such as user interactions, system updates and timers are added to a queue and then processed one by one Trying to access GUI from another thread will cause problems Having a lengthy operation in a GUI application will lead to GUI freezing Concurrency in GUI – solutions Do the long operation in another thread; use special function to update the GUI once the operation is finished C#: Control.Invoke() Java: EventQueue.invokeLater() (A variation of the previous approach) Use a special class for lengthy operations C#: BackgroundWorker Java: SwingWorker Multi-Threaded Servers (“Concurrency”) Many applications have to deal with “real world” concurrency Like multiple users who may issue task requests concurrently and non-deterministically Threads can help to code such server applications Run a separate thread for each concurrent interaction Servers are often built on top of a standardised multi-threaded environment such as a servlet container like Tomcat Server threads may be blocked a lot of the time, because they are waiting for the next request During waiting times, they do not actually use up CPU time Often requires some access control for shared resources Such as a database 67 Parallel Programming (“Parallelism”) Parallel programming tries to divide a computation-intensive task into sub-tasks and execute these at the same time Can be coded for multi-core or distributed machines Parallelisation requires a careful breakdown into sub-tasks and allocation over different cores / processors / machines Try to reduce idle (waiting) times Not every algorithm can be efficiently parallelised Communication and memory access are often the bottlenecks Simply increasing the number of CPUs does not necessarily improve the performance In fact, overheads may even worsen the performance 68 Summary Java and C# fully support multi-threaded programming Synchronised methods, synchronised blocks (Java) and locks (C#) can be used to control access to shared objects Choice of synchronisation (locking) strategy coarse-grained concurrency is simpler, less danger of deadlock, potentially poorer performance fine-grained concurrency is more complex, needs more care to avoid deadlocks, potentially better performance Barriers and semaphores can help to coordinate the progress of different threads GUI: use special classes to execute background tasks Multi-threaded servers versus parallel programming 69 END OF LECTURE