程序代写代做代考 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