程序代写代做代考 concurrency algorithm Java CO2017 — Week2 L1 — Concurrency and Threads
CO2017 — Week2 L1 — Concurrency and Threads
CO2017 — Week2 L1 — Concurrency and Threads
Dr Gilbert Laycock (gtl1)
2017–01–30
gtl1–R895 W2L1 — Concurrency 2017–01–30 1 / 31
Recap
Recap
The structure of Operating Systems
Concept of process: Code + Process Control Block
Scheduling algorithms
Reflections on how user interface interacts with OS
gtl1–R895 W2L1 — Concurrency 2017–01–30 2 / 31
Processes and Threads
Heavyweight processes
A process is an operating system abstraction to represent what is
needed to run a program.
It consists of
Sequential Program Execution Stream (includes state of CPU
registers); plus
Protected resources: memory state, I/O state
NB Strictly sequential — i.e. no concurrency.
gtl1–R895 W2L1 — Concurrency 2017–01–30 3 / 31
Processes and Threads PCB, context switching
PCB, address space, context switch
The current state of the process is held in the PCB (Process
Control Block)
To multiplex several processes we need to allocate CPU time to
processes using suitable scheduling policies.
preemptive: SRT, RR
non-preemptive: FCFS, SJF
Controlled access to non-CPU resources, e.g. memory, I/O.
gtl1–R895 W2L1 — Concurrency 2017–01–30 4 / 31
Processes and Threads Threads
Threads
A thread is an independent sequence of execution within a program
gtl1–R895 W2L1 — Concurrency 2017–01–30 5 / 31
Processes and Threads Threads
Concept of Thread (Cont’d)
A thread is similar to a process
Both have a single sequential flow of control with a start and end
At any time a thread has a single point of execution
A thread has its own execution stack & program counter
Sometimes a thread is called a lightweight process
However, a thread differs from a process
A thread cannot exist on its own. It exists within a process
Usually created and/or controlled by a process
Threads can share a process’s resources, including memory and open
files.
Many languages (Java) support thread programming directly;
gtl1–R895 W2L1 — Concurrency 2017–01–30 6 / 31
Review of sequential programming
What is Sequential Programming?
Traditional activity of constructing a program containing one process
using a (sequential) computer language
The program is supposed to execute on a single processor architecture
gtl1–R895 W2L1 — Concurrency 2017–01–30 7 / 31
Review of sequential programming Single processor architecture
Single Processor Architecture
A CPU is linked to RAM and I/O devices by buses
Both program instructions and data are stored in RAM
The CPU repeatedly executes the cycle of
Fetching, decoding and executing the next instruction
Referenced by the current value of program counter (PC)
Can execute just one instruction at any time
gtl1–R895 W2L1 — Concurrency 2017–01–30 8 / 31
Review of sequential programming Single processor architecture
Program
Program Counter
Runtime Data
Processor
(CPU)
I/O
Devices
(RAM)
Random Access Memory
Bus
gtl1–R895 W2L1 — Concurrency 2017–01–30 9 / 31
Review of sequential programming Execution of a sequential program
Executing a Sequential Program
The execution sequence is the sequence of values of PC
Deterministic: only one possible sequence of execution
A sequential program gives the system strict instructions on the order
of executing the statements in the program.
For example, the program below
P; Q; R;
tells the system to execute the statements in the order
P => Q => R
i.e, P must precede Q and Q must precede R
gtl1–R895 W2L1 — Concurrency 2017–01–30 10 / 31
Review of sequential programming Sequential example
A Simple Example
A simple program consists of three statements
Java Statements
[ P ] x = 1;
[ Q ] y = x+1;
[ R ] x = y+2;
The final values of x and y depend only on the order of executing the
statements
gtl1–R895 W2L1 — Concurrency 2017–01–30 11 / 31
Review of sequential programming The system level view
System Level Execution
Each statement may be compiled into several machine instructions
1 P is treated as a single machine instruction
p: (x = 1) store 1 at the address of x
2 Q (y = x+1 )is broken into 3 machine instructions as follows:
q1: load the value of x into a CPU register
q2: increment the value in this register by 1
q3: store the value in this register at the address of y
3 Similarly, R (x = y+2) is broken into 3 machine instructions
r1: load the value of y into a CPU register
r2: increment the value in this register by 2
r3: store the result at the address of x
gtl1–R895 W2L1 — Concurrency 2017–01–30 12 / 31
Total ordering
Total Ordering
What is meant by P must precede Q?
Q can only begin after P finishes
The execution sequence at the program level
P; Q; R;
implies the execution sequence at the system level
p, q1, q2, q3, r1, r2, r3
So the final result is x = 4; y = 2;
Single threaded computation, no overlap in the execution of the
statements — Total Ordering
gtl1–R895 W2L1 — Concurrency 2017–01–30 13 / 31
Total ordering
Nature of Sequential Programming
Total ordering
Deterministic: same input results in same output
Sequential programming ⇔ Finding a strict sequence of steps to
achieve the desired end
This does not apply for many practical problems
gtl1–R895 W2L1 — Concurrency 2017–01–30 14 / 31
Non-sequential problem solving Calculating factors of a large number
Chinese General Problem
A Chinese princess wanted to marry one of her father’s generals. Each
of them had 1,000,000 soldiers. A general who could win her heart
must be young, handsome, and intelligent enough to:
Find all non-trivial factors of 368,788,194,383 in one month
How would you solve this problem if you were a general with 1,000,000
soldiers under your command?
gtl1–R895 W2L1 — Concurrency 2017–01–30 15 / 31
Non-sequential problem solving Calculating factors of a large number
Clever General Bingxing’s Solution
1 Calculated 607280 = ⌈
√
368788194383 ⌉
2 Gave each number in [2, 607280] to one of his 607,279 soldiers to check
whether it is a factor
3 20 minutes later those soldiers who got 7, 17, 23, 119, 161, 257, 391, 1799,
2737, 4369, 5911, 30583, 41377, 100487, and 524287 reported that their
number were factors
4 Find the remaining factors: 52684027769, 21693423199, 16034269321,
3099060457, 2290609903, 1434973519, 943192313, 204996217, 134741759,
84410207, 62390153, 12058601, 8912879, 3670009, and 703409
5 General Bingxing won the princess’s hand with these factors in 1 hour
NB: 368788194383 = 7× 17× 23× 257× 524287
gtl1–R895 W2L1 — Concurrency 2017–01–30 16 / 31
Non-sequential problem solving Partial ordering of parallel solution
Parallel Computation and Partial Ordering
The operations carried out by Bingxing’s 607,279 soldiers were NOT in
a total order.
They were carried out in parallel
Each individual soldier did his operations in sequence
The operations over the whole computation can be viewed as a partial
order
gtl1–R895 W2L1 — Concurrency 2017–01–30 17 / 31
Concurrent programming
What is Concurrent Programming
Constructing a program containing multiple processes/threads that
execute in parallel
These processes may run on
A multi-processor system
A single processor system
Needs language support, e.g, Java Threads; Posix thread support, etc.
gtl1–R895 W2L1 — Concurrency 2017–01–30 18 / 31
Concurrent programming Benefits of concurrency
Why Concurrent Programming?
Improve efficiency in program execution using multi-CPU hardware
(Chinese General Problem)
Improve CPU utilisation via multi-tasking on a uni-CPU system
(operating systems)
Some applications are inherently non-deterministic and concurrent,
e.g, embedded traffic lights controller
The order of program operations is determined by external events, e.g, a
sensor is triggered by a coming vehicle
Impossible to predict the order of these events, e.g, a car from the north
comes first, and then one from the east, and so on
gtl1–R895 W2L1 — Concurrency 2017–01–30 19 / 31
Concurrent programming Representing concurrency in code
How to Represent Concurrent Program
Use COBEGIN/COEND to bracket the processes
G1; …; Gk; [ calculating p=607297 ]
COBEGIN
S1; [ BEGIN S1.1; …; S1.m END ]
…;
S(p-1); [ BEGIN S(p-1).1; …; S(p-1).n END ]
COEND;
R1; …; Rl; [ reporting to the princess ]
The program ends only if all processes in COBEGIN/COEND terminate
The statements in COBEGIN/COEND may overlap in execution, but we
cannot say they must do so
gtl1–R895 W2L1 — Concurrency 2017–01–30 20 / 31
Concurrent programming Concurrency with multi-processors
Multi-Processor System
A computer with multi-CPUs/cores is a Parallel Computer System
Parallel computation can be implemented on a parallel computer
system
If each task is computed by its own CPU, the computation is called
Maximum Parallel Computation
E.g, if a system has 607279 CPUs, each soldier’s task can be assigned to
its own CPU
Maximum parallelism may not be always possible
gtl1–R895 W2L1 — Concurrency 2017–01–30 21 / 31
Concurrent programming Concurrency with uni-processors
Uni-Processor Multi-Tasking System
A uni-CPU system can support multi-tasking/multi-thread
We can treat each soldier as a process or thread
Each process/thread has its own process counter
The program counter (PC) forks to produce many process/thread
counters, which later re-join
In each CPU cycle, a process is non-deterministically chosen and its
next command is loaded and executed
There may be many different possible paths
This CPU sharing technique is interleaving.
gtl1–R895 W2L1 — Concurrency 2017–01–30 22 / 31
Concurrent programming Interleaving
Example of Interleaving
A concurrent program has two processes p1 and p2:
p1 has three statements A, B, and C; p2 has two S and T
PROCESS p1;
BEGIN A; B; C END;
PROCESS p2;
BEGIN S; T END;
BEGIN
COBEGIN
p1; p2;
COEND
END
gtl1–R895 W2L1 — Concurrency 2017–01–30 23 / 31
Concurrent programming Interleaving
Possible interleavings
1 A ; B ; C ; S ; T
2 A ; B ; S ; C ; T
3 A ; S ; B ; C ; T
4 S ; A ; B ; C ; T
5 A ; B ; S ; T ; C
6 A ; S ; B ; T ; C
7 A ; S ; T ; B ; C
8 S ; T ; A ; B ; C
9 S ; A ; B ; T ; C
10 S ; A ; T ; B ; C
gtl1–R895 W2L1 — Concurrency 2017–01–30 24 / 31
Concurrent programming Interleaving
Back to first example
Each statement may be compiled into several machine instructions
1 P is treated as a single machine instruction
p: (x = 1) store 1 at the address of x
2 Q (y = x+1) is broken into 3 machine instructions as follows:
q1: load the value of x into a CPU register
q2: increment the value in this register by 1
q3: store the value in this register at the address of y
3 Similarly, R (x = y+2) is broken into 3 machine instructions
r1: load the value of y into a CPU register
r2: increment the value in this register by 2
r3: store the result at the address of x
gtl1–R895 W2L1 — Concurrency 2017–01–30 25 / 31
Concurrent programming Interleaving
Possible interleavings
(Assume that variables are automatically initialized to zero.)
Already seen that p; q1 ; q2 ; q3 ; r1 ; r2 ; r3
results in x=4 ; y=2
What about p ; q1 ; r1 ; q2 ; r2 ; q3 ; r3 ?
Result is x=2; y=2
And q1 ; r1 ; q2 ; r2 ; q3 ; r3 ; p
results in x=1 ; y=1
etc.
The results depend on the order of interleaving.
gtl1–R895 W2L1 — Concurrency 2017–01–30 26 / 31
Concurrent programming Interleaving
Complexity of Interleaving
Given a concurrent program with processes p and q
PROCESS p;
BEGIN S1; …; Sm END;
PROCESS q;
BEGIN T1; …; Tn END;
BEGIN
COBEGIN p; q COEND
END.
The number f(m,n) of interleavings is
the combination
Cn+mm = C
n+m
n =
(n+m)!
n!m!
The number f(m,n) grows very fast with m and n
gtl1–R895 W2L1 — Concurrency 2017–01–30 27 / 31
Concurrent programming Interleaving
n : 2 4 6 8 10 · · ·
f(n,n) : 6 70 924 12870 184756 · · ·
gtl1–R895 W2L1 — Concurrency 2017–01–30 28 / 31
Concurrent programming Concurrency critical issues
Issues in Concurrent Programming
The concurrent processes must interact with each other in order
to share resources or exchange data
Synchronisation: when, how, and with what language
abstractions can we synchronise computation to eliminate
unacceptable interleavings, and thus unacceptable outputs?
Distribution: how can we distribute processes among a number
of processors, and how can a process on one processor interact
with another process on a different processor.
gtl1–R895 W2L1 — Concurrency 2017–01–30 29 / 31
Summary
Summary
Processes, threads, context switching
Sequential programming, compared with
Concurrent programming
gtl1–R895 W2L1 — Concurrency 2017–01–30 30 / 31
Summary
Next time
Processes sharing resources
Critical regions, mutual exclusion
Algorithms for solving critical region issues
gtl1–R895 W2L1 — Concurrency 2017–01–30 31 / 31
Processes and Threads
PCB, context switching
Threads
Sequential Programming
Review of sequential programming
Single processor architecture
Execution of a sequential program
Sequential example
The system level view
Total ordering
Concurrency
Non-sequential problem solving
Calculating factors of a large number
Partial ordering of parallel solution
Concurrent programming
Benefits of concurrency
Representing concurrency in code
Concurrency with multi-processors
Concurrency with uni-processors
Interleaving
Concurrency critical issues
Summary
