程序代写代做代考 jvm algorithm concurrency gui database Java cache Computer Systems Concurrency & Threads

Computer Systems Concurrency & Threads

A view of an operating System
Slide #2 of 35

What does this imply?
Multiple ‘users’
Working independently The operating system:
Protects memory from interference from other processes Interleaves execution of each process to:
Maximise resource utilisation Responsiveness of each process
Preserves the states of each process so it can resume execution
Slide #3 of 35

Historically …. Computers were expensive:
Maximise utilisation
Now:
Users expect concurrent execution of multiple tasks
Stream music Update software Edit file
Test program Monitor SNS Etc.
Slide #4 of 35

So?
The problem is that these processes do not always work independently:
They can compete for access to resources: Devices, files, data etc. that are local (or remote)
They can co-operate – through messages, shared memory, files etc.
Applications are distributed:
So, potentially, millions of people are reading or updating
information at the same time
SNS, bank accounts, on line shopping ….
Slide #5 of 35

And …
We need to build applications that can interleave multiple independent (but potentially conflicting) tasks:
Consider an app with a GUI:
do we want it to freeze when it is performing some time
consuming task?
What about a database of bank accounts?
Do we want to wait in a queue to perform a transaction? What about programmers’ efficiency & effectiveness?
Do we want them to have to ‘build an OS’ for every app? What about the effectiveness of use of our computing resources?
We want to maximise the efficiency
Slide #6 of 35

This leads us to two things:
How can we manage concurrency?
How can we ensure that our concurrent execution behaves correctly?
How can we do this conveniently? How can we do this efficiently?
To maintain responsiveness
How can we provide programming mechanisms within
a program to allow concurrency? Threads
Slide #7 of 35

Let’s think about a bank transfer
Find Balance Acc1
Subtract transfer
Store new value
Find Balance Acc2
Add transfer
Store new value
Find Balance Acc1
This is unlikely:
• but possible!
• and hard to debug!
Store new value
Find Balance Acc2
Store new value
Subtract Transfer
Subtract Transfer
Slide #8 of 35

Concurrency
 Introduction to Concurrency
 OS Concerns and Process Interaction
 Process Synchronization
 Critical Section Problem
 Requirements for Solutions to CS Problem  Software Solutions
 Hardware Solutions
 High Level OS Support
Slide #9 of 35

Multiple Processes
 Operating System design is concerned with the management of processes and threads
Multiprogramming (Multitasking)  Multiprocessing
Distributed Processing
Slide #10 of 35

Concurrency in Different Contexts
Slide #11 of 35

Concurrency: Key Terms
Slide #12 of 35

Principles of Concurrency
Interleaving and Overlapping
 Can be viewed as examples of concurrent processing  Both present the same problems
Uniprocessor – the relative timing of execution of processes cannot be predicted:
 Depends on activities of other processes The way the OS handles interrupts
 Scheduling policies of the OS
Slide #13 of 35

Difficulties of Concurrency
 Sharing of global resources
 Difficult for the OS to manage the allocation of
resources optimally
 Coordination of ‘parallel’ and asynchronous ‘processes’
Ensuring correct behaviour Debugging of programming errors:
 behaviour can be non-deterministic and, therefore, hard to identify and reproduce
Slide #14 of 35

Operating System Concerns
 Design and management issues raised by the existence of concurrency:
The OS must:
• •
• •
be able to keep track of various processes allocate and de-allocate resources for each active
process
protect the data and physical resources of each process
against interference by other processes
ensure that the processes and outputs are independent of the processing speed
Slide #15 of 35

Process Interaction
Slide #16 of 35

Resource Competition
 Concurrent processes come into conflict when they are competing for use of the same resource
for example: I/O devices, memory, processor time, clock  In the case of competing processes three control
problems must be faced:
 Mutual Exclusion – to ensure correct behaviour  Deadlocks
 Starvation
Slide #17 of 35

Synchronization of Processes – Example
 We expect
When process1 finishes, shared variable x is reduced by 5 When process2 finishes, shared variable x is increased by 2
Slide #18 of 35

Synchronization of Processes – Example
 Context switches may occur at any time
 Process 2 has its result overwritten by process 1  Process 1 operates with outdated information
Slide #19 of 35

What is a Race Condition?
 Occurs when multiple processes or threads read and write shared data items
 The processes “race” to perform their read /write actions
 The final result depends on the order of execution
The “loser” of the race is the process that performs the last update and determines the final value of a shared data item
Slide #20 of 35

Why do Race Conditions Occur?
 Order of Execution: Whenever the state of a shared resource depends on the precise execution order of the processes
 Scheduling: Context switches at arbitrary times during execution
 Outdated Information: Processes / Threads operate with Stale or Dirty copies of memory values in registers / local variables
Other processes may already have changed the original value in the shared memory location
How can we avoid race conditions?
Slide #21 of 35

Critical Section
 Part of the program code that accesses a shared resource
 In order to avoid race conditions, we have to control the concurrent execution of the critical sections
 Strict Serialization i.e. Mutual Exclusion
Slide #22 of 35

Critical Section
 Entry Protocol
Process requests permission for entering a critical
section; May have to wait / suspended until entry is granted Process has to communicate that it entered critical section
 Exit Protocol
Process communicates to other processes that it has left the critical section
Slide #23 of 35

Critical Section / Mutual Exclusion
 Important: A process can finish the execution of it’s critical section, even if it is preempted or interrupted.
Slide #24 of 35

Deadlock and Starvation
 Enforcing mutual exclusion creates two new problems Deadlocks – Processes wait forever for each other to free
resources
Starvation – A Process waits forever to be allowed to enter its critical section
 Implementing mutual exclusion has to account for these problems!
Slide #25 of 35

Requirements for Solutions to the Critical Section Problem
1) Serialization of Access: Only one process at a time is allowed in the critical section for a resource
2) Bounded Waiting (No Starvation):
A process waiting to enter a critical section, must be
guaranteed entry (within some defined limited waiting time)
Scheduling algorithm has to guarantee that process is eventually scheduled and can progress
Slide #26 of 35

Requirements for Solutions to the Critical Section Problem (cont’d)
3) Progress (Liveness, No Deadlock)
A process that halts in its noncritical section must do so without interfering with other processes currently waiting to enter their critical section
Only processes currently waiting to enter their critical section are involved in the selection of the one process that may enter
A process remains inside its critical section for a finite time only
Slide #27 of 35

Solutions to the Critical Section Problem
1) Software Solutions
Shared lock variables
Busy Waiting (Polling / Spinning / Strict Alternation)
2) Hardware Solutions
Disabling Interrupts
Special H/W Instructions (like compare & swap)
3) Higher Level OS Constructs Semaphores, Monitors, Message Passing
Slide #28 of 35

Lock Variables
 Critical sections must be protected by some form of a “lock”, where a lock is:
A shared data item
Processes have to “acquire” such a lock before entering a critical section
Processes have to “release” a lock when exiting critical section
 A lock is also called a Mutex.
Slide #29 of 35

Shared Lock / Mutex
Two State Lock (shared variable)
 True = Critical Section Locked, False = Critical Section Unlocked
Problem: As lock variable is itself a shared resource, race conditions can occur on it!
Slide #30 of 35

Shared Lock – Problem
Solution: Use Atomic Instructions for Shared Lock!
Slide #31 of 35

Busy Waiting (Polling, Spinning)
 A process continuously evaluates whether a lock has become available
 Lock is represented by a data item held in shared memory (IPC via shared memory)
 Process consumes CPU cycles without any progress
 A process busy waiting may prevent another process holding the lock from executing and completing its critical section and from releasing the lock
 Spin locks are used at kernel level (special HW instructions)
Slide #32 of 35

Busy Waiting (Strict Alternation)
 Strict alternation between two processes – a process waits for its turn
 Use a “token” as shared variable – usually process ID  indicates which process is the next to enter critical section, set by
previous process
 Entry to critical section
 Process Pi busy-waits until token == i (its own process ID)
 Exit from critical Section
 Process Pi sets token to next process ID
Slide #33 of 35

Busy Waiting (Strict Alternation)
 Mutual exclusion is guaranteed!
 Liveness / Progression problem
 Both process depend on a change of the “turn” variable
 If one of the processes is held up in its non-critical section, it cannot do that and will block the other process
Slide #34 of 35

Hardware Solutions – Disabling Interrupts
 In uniprocessor systems, concurrent processes cannot be overlapped, they can only be interleaved.
 Disabling interrupts guarantees mutual exclusion!
 However, the efficiency of execution could be noticeably
degraded.
 This approach will not work in a multiprocessor architecture
Slide #35 of 35

Special H/W Instructions
Applicable to any number of processes on either uniprocessor or multiprocessors sharing main memory
 Simple and easy to verify
 Can be used to support multiple critical sections  Busy-waiting is employed
 Starvation and Deadlocks are possible!
Slide #36 of 35

Abstractions
Usually, we build upon abstractions:
The system implements mechanisms correctly and efficiently and we use these:
Database systems
Java
There are other solutions to these problems that may be more efficient – in some circumstances
Slide #37 of 35

Summary
 What is concurrency and what are OS and Process concerns w.r.t to concurrency.
 We have been introduced to the notion of process synchronization, its need and the critical section problem.
 We have seen requirements for solutions to the CS problem i.e. mutual exclusion, progress & bounded waiting time.
Slide #38 of 35

Threads
 What is a thread?
 Parallelism vs. Concurrency
 Multicore and Multi-threading
 Multi-threading Models
 Java Threads
 Limitations of Threads
 Threading Issues
 Thread Interference & Memory Consistency  Synchronized Methods and Statements
Slide #39 of 55

From Processes to Threads
Process model assumed a process was an executing program with a single thread of control
 All modern OS’s provide features enabling a process to contain multiple threads of control
 Multi-threading is the ability of an OS to support multiple, concurrent paths of execution within a single process.
Slide #40 of 55

What is a Thread?
A thread is part of a process Contains:
 Thread ID (TID)
 Program Counter (PC)  Register Set
 Stack
 All threads in the same process, share:  Code section
 Data section:
 Objects
 Open files
 Network connections  Etc.
Slide #41 of 55

What is a Thread?
 If a process has multiple threads of control, it can perform more than one task at a time!
Slide #42 of 55

Why Threads?
Most applications are multi-threaded  Application:
Process with several threads of control
Web browser:
Threads for each tab
Threads for each extension/helper Utility threads
Java Program: main thread + service threads  + GUI threads
Server Processes
Slide #43 of 55

Multi-threaded Server Architecture
 Threads have a critical role in systems which provide services:
Servers: web servers, database servers ….
 When a server receives a message, that request is serviced using a separate thread:
Slide #44 of 55

Benefits of Threads
 Responsiveness: user interaction in a GUI can be responded to by a separate thread from one running a computationally intense algorithm.
 Resource Sharing: Variables & objects can be shared. This is especially important for things like network or DB connections.
Economy: “Light-Weight Processes” due to smaller memory footprint than using multiple processes & efficiency of switching between threads.
 Scalability: Easier to make use of parallel processing in a multi- threaded processor
 Reduce programming complexity: Problems often are better broken down into independent parallel tasks, rather than having to build complex mechanisms to interleave their execution.
Slide #45 of 55

Multicore Programming
 Multiple processing elements on a single chip
 Multi-threaded programming:
Allows efficient use of the multiple processing elements and improved parallelism
Slide #46 of 55

Concurrency
 On a single Processing element, concurrency means that the execution of threads will be interleaved over time.
Only one thread at a time is actually running
Slide #47 of 55

Parallelism
Slide #48 of 55

Parallelism vs Concurrency
 A system is parallel if it can perform more than one task simultaneously
 A concurrent system supports more than one task by allowing all the tasks to make progress.
 It is possible to have concurrency without parallelism
This is incredible! I can do so much more! There must be a catch …
Slide #49 of 55

Multicore systems and Multithreading
 Performance of software on Multicore systems Amdahl’s law states that:
 (1-f) : Inherently serial code
 f : parallelizable code with no scheduling overhead
Slide #50 of 55

Multicore and Multithreading (cont’d)
 Amdahl’s law makes the multicore organizations look attractive!  But even a small amount of serial code has noticeable impact on
the overall performance
Example:
10% serial, 90% parallel, 8 CPUs→~4.7x speedup
 There are overheads to parallelism: Memory access
Cache load
Etc.
Slide #51 of 55

Multicore and Multi-threading (cont’d)
Slide #52 of 55

Multicore and Multi-threading (cont’d)
Slide #53 of 55

Parallel Programming Challenges
 Pressure placed on system designers and application programmers to better use multiple cores
 System designers must write scheduling algorithms that use multiple processing core to allow parallel execution
 Challenge to modify existing programs
 Challenge to design new programs that are multithreaded
Slide #54 of 55

Parallel Programming Challenges (cont’d)
 Identifying tasks: which areas of an application can be divided into separate, concurrent (and ideally independent) tasks?
 Balance: how do we balance the tasks on the multiple cores to achieve maximum efficiency?
 Data splitting: how can data sets be split for processing in parallel?
 Data dependency: Certain tasks will rely on data from another. In this case, how do we synchronise the access to this data?
 Testing and debugging: Due to complexities of concurrent and parallel execution (multiple pathways etc.), how do we debug such an application?
Slide #55 of 55

Multithreading Models
 Threads may either be at the user or kernel thread level
 User threads managed above kernel
 Kernel threads are managed directly by the OS
 Three types of relationships between user and kernel threads are possible.
 Many-to-One  One-to-One
 Many-to-Many
Slide #56 of 55

Many-to-One Model
 Maps many user-level threads to one kernel thread
 Thread management done by the thread library, in user space. Therefore, efficient!
 But, entire process will block if a thread makes a blocking system call
 Only one thread can access kernel at a time – lacks parallelism on multicore systems
 Not many systems use this due to inability to take advantage of multiple cores
Slide #57 of 55

One-to-One Model
 Maps each user thread to a kernel thread
 Overcomes blocking issue – so more concurrent Allows for parallelism
 But, for each user thread, there has to be a kernel thread
Slide #58 of 55

Many-to-Many Model
 A software developer can create as many user threads as necessary i.e. a Thread Pool.
Corresponding kernel threads can run in parallel on a multiprocessor
 If a thread blocks, kernel can schedule another for execution
Slide #59 of 55

How can we use Threads?
Through use of a thread library
 POSIX Pthreads (user/kernel level)
 Windows (kernel)
 Java Threads (on top of Windows/Pthreads)
API for creating and managing threads
Slide #60 of 55

Java Threads
 Fundamental model of program execution in a Java program
 Java API provides a rich feature set for the creation and management of threads
All programs consist of at least a single thread of control – main()
 Java threads available on any system that contains a JVM
Slide #61 of 55

Warning!
 This section does NOT expect you to be able to program using threads in JAVA:
It is just to give a flavour of what you can do! Java threads will be covered in semester 2
Slide #62 of 35

Creating a Thread in Java (Method # 1)
 Create a new class derived from the Thread class and over-rides its run() method
public class MyThread extends Thread{ public void run(){
// Code below overrides run()
System.out.println(“My first thread”); }
Slide #63 of 55

Test for MyThread
 Here is an example for testing MyThread
public class TestMyThread {
public static void main(String[] args) {
} }
MyThread t = new MyThread();
t.start(); }
The above code currently doesn’t do a lot!
In case you are interested:
Modify the run and main methods to do something useful.
Slide #64 of 55

Creating a Thread in Java (Method # 2)
 Implement the Runnable interface, which is defined as:
public interface Runnable{ public abstract void run();
}
 When a class implements Runnable, it must define a run() method
 It’s this code, in the run() method, that runs as a separate thread
Slide #65 of 55

Implementing Runnable (Method # 2)
public class HelloRunnable implements Runnable{ // implement run method here
public void run(){
} }
System.out.println(“Thread by implementing Runnable”);
Slide #66 of 55

Testing Runnable (Method # 2)
public class TestHelloRunnable{
public static void main(String[] args){
} }
HelloRunnable ht = new HelloRunnable(); Thread t = new Thread(ht);
t.start();
Slide #67 of 55

Which way of Creating Threads is Better ?
 Implementing the Runnable interface is preferred over extending Thread class
Java does not support multiple inheritance!
But multiple inheritance can almost be achieved in java by
using interfaces
e.g. class A extends B implements Runnable {}
Slide #68 of 55

Pausing Execution with Sleep
 Thread.sleep() causes the current thread to suspend execution for a specified period
 This is an efficient way of making processor time available to other threads of an application
 It takes an argument that denotes the time (in milliseconds) that you would like a thread to pause for.
Slide #69 of 55

Stopping a Thread
 The only safe way to stop a thread is for it to stop itself  A thread t1 can interrupt the running of a thread t2 by
invoking its interrupt method
 This sets a flag indicating that the thread should be
terminated right away. For more details:
https://docs.oracle.com/javase/7/docs/api/java/lang/Thread.html#interrupt()
Slide #70 of 55

Some Interesting Statistics
 64-bit Mac OS X 10.9, Java 1.7.0_45 – JVM dies after #2031 threads have been created
 64-bit Ubuntu Linux, Java 1.7.0_45 – JVM dies after #31893 threads have been created
 64-bit Windows 7, Java 1.7.0_45 – due to a different thread model used by the OS, this error seems not to be thrown on this particular platform. On thread #250,000 the process was still alive, even though the swap file had grown to 10GB and the application was facing extreme performance issues.
More at:
https://plumbr.eu/outofmemoryerror/unable-to-create-new-native- thread
Slide #71 of 55

Inter-thread Communication
• Threads communicate by sharing data: • Efficient!
• We now have the same problems that we discussed earlier!
• Solution?
• Synchronize!
Slide #72 of 55

An Example
class Counter { private int c = 0;
public void increment() { c++;
}
public void decrement() { c–;
}
public int value() { return c;
} }
Slide #73 of 55

Why is there a problem?
 Functions seem simple and atomic
 But, to increment, there are three steps Retrieve the current value of integer
Add 1 to this value
Store the incremented value back to the variable
Slide #74 of 55

Thread Interference
 If multiple threads all reference the same object: thread interference can occur
 Happens when two functions, operating on the same data, interleave
 Unpredictable
 Difficult to debug
Slide #75 of 55

Memory Consistency
 Memory consistency errors occur when different threads have inconsistent views of the same data
Happens-before relationship
Guarantee that memory writes by one statement are visible
to another
 To create a happens-before relationship, we can:
 synchronize
 Synchronization in Java Synchronized methods Synchronized statements
Slide #76 of 55

Synchronized Methods
Add the synchronized keyword to a method declaration
public synchronized void increment(){ c++;
}
Slide #77 of 55

Synchronized Methods – Effects
 Two invocations of a synchronized method on the same object cannot interleave
All other threads are blocked until first thread is done
 When a synchronized method exits, it automatically establishes a happens-before relationship with any subsequent invocation of a synchronized method on the same object
Slide #78 of 55

Locks
 Synchronization built around the notion of intrinsic locks
 Enforce exclusive access
 Establish happen-before relationships
 Thread needs to acquire lock before it can do anything
Slide #79 of 55

Synchronized Statements
Alternatively, synchronized statements must specify the object that provides the lock.
public void addName(String name) { synchronized(this) {
lastName = name;
nameCount++; }
nameList.add(name); }
Slide #80 of 55

Object Locks
 Used where execution can be interleaved
For example, where two different variables are being
updated.
 private Object lock = new Object();
object created purely to act as a lock in a synchronized statement.
 Use with care – ensure it is absolutely safe to all access to fields to interleave
Slide #81 of 55

Object Locks – Example
public class ObjectsAsLocksExample { private long c1 = 0;
private long c2 = 0;
private Object lock1 = new Object(); private Object lock2 = new Object(); public void inc1() {
synchronized(lock1) { c1++;
} }
public void inc2() { synchronized(lock2) {
c2++; }
} }
Slide #82 of 55

Summary
In this part, we have introduced:
The concept of threads and multithreading.
The differences between parallelism and concurrency
 The Amdahl’s law for performance on multicore
 Multithreading Models and Java Threads
Threading Issues including thread interference & memory consistency
 The use of synchronized methods and statements to address the threading issues.
Slide #83 of 55

References / Links
 Chapter # 4: Threads, Operating System Concepts (9th edition) by Silberschatz, Galvin & Gagne
 Chapter # 4: Threads, Operating System Internals and Design Principles (7th edition) by William Stallings
https://docs.oracle.com/javase/tutorial/essential/concurr ency/locksync.html
http://tutorials.jenkov.com/java-concurrency/creating- and-starting-threads.html
Slide #84 of 55