程序代写代做代考 scheme chain file system Java algorithm Excel AI IOS data structure FTP gui dns concurrency android c++ cache Fortran database compiler assembler distributed system Hive DEPARTMENT OF INFORMATICS

DEPARTMENT OF INFORMATICS

CO2017

Operating Systems, Networks &
Distributed Systems

Slides 2016/2017

Dr. G. Laycock

CO2017 — Operating Systems, Networks and

Distributed Systems

Week1 L1 — Introduction

Dr Gilbert Laycock (gtl1)

2016–01–24

gtl1–R557 W1L1 — Introduction 2016–01–24 1 / 22

Module Organisation Teaching staff

Teaching staff

Convenor: Dr Gilbert Laycock

email: gtl1@le.ac.uk
office: G15

Teaching assistants:

Whole team: co2017-team@mcs.le.ac.uk

gtl1–R557 W1L1 — Introduction 2016–01–24 2 / 22

Module Organisation Background

Background

The module webpage is
https://campus.cs.le.ac.uk/teaching/resources/CO2017/

Make sure you read this webpage regularly. News and additional
material will be posted there as the semester progresses.

It is worth reading the study guide, available on line on the
webpage.

gtl1–R557 W1L1 — Introduction 2016–01–24 3 / 22

Module Organisation Timetable

Timetable

Lectures:

Mon 14:00–15:00 in ATT LT1
Mon 16:00–17:00 in ENG LT2
Tue 17:00–18:00 in LE LT3

Surgery/Problem Class:

Mon 17:00–18:00 in Eng LT2

Computer Class:

Fri 15:00–17:00 in CW301

gtl1–R557 W1L1 — Introduction 2016–01–24 4 / 22

Module Organisation Coursework

Coursework

Interactive shell use and simple shell programming 10%

Java Threads, Scheduling, Deadlocks 15%

Java Sockets 15%

gtl1–R557 W1L1 — Introduction 2016–01–24 5 / 22

Module Organisation Exam

Exam

New exam structure since last year.

“Attempt all questions. Full marks may be obtained only if all
questions are answered.”

gtl1–R557 W1L1 — Introduction 2016–01–24 6 / 22

Module Organisation Module materials

Module materials

Recommended reading:

Andrew S. Tanenbaum, Modern Operating Systems, 3rd ed.,
Prentice Hall, 2014.
Andrew S. Tanenbaum, (David J. Wetherall), Computer Networks,
5th ed., Prentice Hall, 2003/2014.
J. Farley, Java Distributed Computing, O’Reilly, 1997.
M. Boger, Java in Distributed Systems, Wiley, 2001.

Website:
https://campus.cs.le.ac.uk/teaching/resources/CO2017/

gtl1–R557 W1L1 — Introduction 2016–01–24 7 / 22

Module Organisation Syllabus

Operating Systems

Introduction Overview; historical perspective.

Process management Programs and processes; multitasking;
dispatcher; scheduling and scheduling policies;
inter-process communication, in particular joint access to
shared resources; threads; Java thread programming.

Memory management Memory allocation methods; paging; virtual
memory; segmentation; protection and sharing.

File management Concept of file; directory structure; file
management techniques; directory implementation.

gtl1–R557 W1L1 — Introduction 2016–01–24 8 / 22

Module Organisation Syllabus

Networks/Distributed Systems

Introduction Overview; different sorts of networks; layered protocols.

OSI model A short overview, contrast with TCP/IP model

Low Layers Error detection and correction; flow control; channel
allocation; protocols for local area networks; bridges.
Datagrams and virtual circuits; routing; congestion
control; inter-networking; the network layer in the
Internet.

Upper layers Connection management; transport layer in the
Internet; congestion control; socket concept; Java socket
programming. Application example (e-mail, http, . . . ).

gtl1–R557 W1L1 — Introduction 2016–01–24 9 / 22

Operating Systems Introduction

Introduction

Brief history of computers, focusing on OS/network
developments.

The functions and parts of an OS and network.

A few key definitions.

gtl1–R557 W1L1 — Introduction 2016–01–24 10 / 22

Operating Systems Processes and scheduling

Processes and scheduling

How do two or more programs “simultaneously” run on the same
computer?

Scheduling: related definitions.

Principles of fair scheduling.

Scheduling algorithms.

gtl1–R557 W1L1 — Introduction 2016–01–24 11 / 22

Operating Systems Memory management

Memory management

Why is concurrent use of shared memory not safe without special
precautions?

Safe concurrent use of memory. . .

Safe concurrent use of memory without unnecessary delays.

Concurrent protocols under particular hardware assumptions.

Virtual memory: a way to run a program requiring memory
exceeding available RAM.

Paging algorithms.

gtl1–R557 W1L1 — Introduction 2016–01–24 12 / 22

Operating Systems File system and I/O

File system and I/O

Files: role and operations.

Methods of allocation of disc space.

Implementation of directories.

Also

Other system I/O and hardware interaction.

gtl1–R557 W1L1 — Introduction 2016–01–24 13 / 22

Operating Systems Practical issues and programming

Practical issues and programming

Investigating practical behaviour of real OS

Thread programming in Java

Network/distributed client/server programming in Java

gtl1–R557 W1L1 — Introduction 2016–01–24 14 / 22

Overview of Operating Systems Brief history of Operating Systems

History of Operating Systems

Early days, programs were entered via switches. Advances:

Cards/paper tape used, and read in by a loader program
Simple terminals with keyboard ⇒ control console
Punch cards were employed for storage

In the 1950s

Standard subroutines produced and loaded at start-up
Magnetic tapes used for storage, then disks
Assemblers appeared, then FORTRAN and ALGOL

In the late 1950s, batch systems first appeared.

Atlas (designed at Manchester Univ.) was 1st with an OS in mind: interrupts and
virtual memory
The loader program was elaborated to allow batch processing
Control cards ⇒ job control languages

gtl1–R557 W1L1 — Introduction 2016–01–24 15 / 22

Overview of Operating Systems Brief history of Operating Systems

History of Operating Systems (Cont’d)

In the mid/late 1960s, multi-programming followed.

CPU could switch between jobs, allowing processing and I/O
simultaneously
Desire for quick response leads to time-sharing via on-line operations

In the 1980s

graphical user interfaces started to be widely used.
The Internet provides shared access to computing resources, to data/files.

Current trends

Workstations vs mobile devices vs cloud computing; Distributed Systems;
Graphical User Interfaces

Some common OSs

Microsoft OSs, Unix-like OSs, and MacOS; iOS, Android,

gtl1–R557 W1L1 — Introduction 2016–01–24 16 / 22

Overview of Operating Systems System structure

Computer System Structure

A computer system consists of hardware and software.

Software: application software and system software.

Operating System is the most important system software.

gtl1–R557 W1L1 — Introduction 2016–01–24 17 / 22

Overview of Operating Systems Operating system

Operating system

A computer program that mediates between hardware and
application programs.

Consists of many loosely related parts handling

Memory management
I/O management
CPU Scheduling
Communications
Multi-tasking/multi-programming

Principles:

Keep user programs from crashing OS and each other
Allocate resources efficiently and fairly

We will study algorithms run by these parts.

Assumption: single-processor computer (mostly)

gtl1–R557 W1L1 — Introduction 2016–01–24 18 / 22

Overview of Operating Systems Operating system

Networks

A network is two or more computers connected by a physical
medium.

The question we will be studying in the class: how to transfer a
message from one computer to another reliably and efficiently?

Detailed discussion of the subject is offered by advanced
modules “Networking” and “Cryptography and Internet security.”

gtl1–R557 W1L1 — Introduction 2016–01–24 19 / 22

Overview of Operating Systems Operating system

Distributed systems

Distributed system is a program than runs on two or more
computers.

We will implement a simple distributed system based on the
client-server architecture.

Detailed discussion of the subject is offered by the “Distributed
systems” module.

gtl1–R557 W1L1 — Introduction 2016–01–24 20 / 22

Overview of Operating Systems Some key features of OS

Simple Fetch-Execute Cycle

CPU works in a Fetch-Execute cycle

Fetching an instruction from memory
Executing the instruction

If an I/O operation is required, CPU will be suspended

Execute

Start

process

Fetch

instruction

instruction

Process

terminated

gtl1–R557 W1L1 — Introduction 2016–01–24 21 / 22

Overview of Operating Systems Some key features of OS

Kernel Mode vs User Mode

OS needs to protect users from each other for security

If a user had access to all machine instructions, then the user could do
anything an OS can

The solution is for the CPU to have a special operating mode, the
kernel or supervisor mode, which can only be invoked by the OS

In kernel mode, OS can execute certain privileged instructions, e.g,
I/O operation and system data modification, which are not available to
normal program (user mode)

gtl1–R557 W1L1 — Introduction 2016–01–24 22 / 22

CO2017 — Week 1L2 — Processes and

Multi-tasking

Dr Gilbert Laycock (gtl1)

2016–01–26

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 1 / 31

How to implement multi-tasking Why multi-tasking?

Simple Fetch-Execute Cycle

CPU operates in a Fetch-Execute cycle — it just does one thing at a
time

1 Fetch next instruction from memory
2 Execute the instruction

If an I/O operation is required, CPU will wait until I/O is complete

Execute

Start

process

Fetch

instruction

instruction

Process

terminated

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 2 / 31

How to implement multi-tasking Why multi-tasking?

Why do we want more than one process at a time?

For convenience of the user.

A modern OS typically needs to monitor and control all kinds of
background tasks.

For better CPU utilisation.

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 3 / 31

How to implement multi-tasking How to appear to multi-task

How to implement multi-tasking:

There is only a single CPU (or perhaps a handful).

Apparent simultaneous execution of several processes is
achieved by the CPU performing a little bit of each process
then suspending it and moving to the next.

CPU needs a mechanism to determine that a particular process
can be suspended to allow the next one to take over.

Mechanism is interrupts

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 4 / 31

How to implement multi-tasking Interrupts and the CPU cycle

The (interrupted) CPU cycle

N

Handle

interrupt

Process

terminated

Start

process

Fetch

instruction

instruction

Interrupt?

Execute

Y

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 5 / 31

How to implement multi-tasking Interrupts and the CPU cycle

Definition and rôle of interrupts

Interrupts: events that cause the CPU to stop the current
process and switch to the special process for handling the
interrupt.

The Dispatcher performs the operation required by the
interrupt (e.g. sending data to a printer) and then decides
which process is the next to run.

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 6 / 31

How to implement multi-tasking Interrupts and the CPU cycle

Types of Interrupts

Input/Output (I/O): by I/O devices to signal completion, error or other
state change.

Timer: by a clock within the CPU; used to alert the OS at pre-set
intervals for time critical activities.

Hardware Error: by hardware faults.

Program: by error conditions within user programs, e.g, division by
zero

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 7 / 31

How to implement multi-tasking Programs and processes

Programs and processes

A program is code ready to execute on a system.

A process is a program in execution, i.e, a particular
instance of a program together with its data.

There may be several copies of the same program running
simultaneously as different processes.

The OS stores information about each process in a process
control block (PCB) (also called process descriptor).

Multi-tasking: is the simultaneous running of two or more
processes.

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 8 / 31

How to implement multi-tasking Programs and processes

Sharing Code among Processes

Tetris

Alice’s second document

Operating System

Emacs code (shared)

Alice’s first document

Bob’s document

Alice

Bob

Memory

Shared code must not be changed during execution

Each processes requires its own data area

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 9 / 31

How to implement multi-tasking Programs and processes

Process Creation

E.g, Created by a user via a command:

When a user invokes a program, OS creates a PCB to represent the
execution of this process.
OS also allocates resources for the process.
So, a process consists of machine code in memory and a PCB.

Created by another process, called spawning a process:

The process that creates a new process is called the parent while the
created process is the child
The child can also spawn further processes, forming a tree of processes

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 10 / 31

How to implement multi-tasking Programs and processes

Aside about Kernel Mode vs User Mode

OS needs to protect processes from each other for security

If a user’s process had access to all machine instructions, then the
user could do anything the OS can.

The solution is for the CPU to have a special operating mode, kernel or
supervisor mode, which can only be invoked by the OS.

In kernel mode, certain privileged instructions, e.g, interrupt
processing, dispatcher, memory allocation, are possible; normal
processes run in (user mode)

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 11 / 31

How to implement multi-tasking The Dispatcher

The Dispatcher

After an interrupt has been handled, control is passed to the
Dispatcher (or Low Level Scheduler).

1 Is the current process still the most suitable to run? If so, resume
execution; otherwise . . .

2 Save the state of the current process in its PCB
3 Retrieve the state of the most suitable process from its PCB
4 Transfer control to the new process, at the point indicated in the PCB

The action of storing the state of current process and (re-)starting
another process is called a context switch

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 12 / 31

How to implement multi-tasking The Dispatcher

States of processes

The running process is in the RUNNING state; only one RUNNING
process on a processor at a time.

Clock interrupt:

Initiated by a clock within the CPU.
Gives the dispatcher an opportunity to context switch.
A process stopped by clock interrupt goes to READY state.

I/O interrupt:

Initiated by CPU when an I/O instruction occurs in the running
process or by an I/O device signalling completion of an I/O
operation
When a process starts an I/O operation it goes to the BLOCKED
state
When an I/O operation completes for a process, it goes to READY
state

The dispatcher can select a process to run only if it is READY.

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 13 / 31

How to implement multi-tasking The Dispatcher

Diagram of process states

Process entry

READY BLOCKED

RUNNING

Dispatch

Termination

I/O wait

I/O completion

Timeout

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 14 / 31

How to implement multi-tasking The Dispatcher

Summary of the story and what next

A process can be RUNNING (currently running), READY (ready to run)
or BLOCKED (waiting on I/O).

Interrupts are used to stop the currently RUNNING process.

A clock interrupt causes the current process to become READY.

An I/O interrupt causes the current process to become BLOCKED,
upon completion of the I/O it becomes READY

The Dispatcher chooses the next process to run from the queue of
READY processes.

Scheduling: is the policy for choosing among the READY processes?

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 15 / 31

How to implement multi-tasking The Dispatcher

Types of Scheduling policy

Scheduling policy determines:

Which READY process to run next.
How long a process is given to use the CPU.

Non-preemptive scheduling:

A process releases CPU only if it BLOCKS on I/O (or it finishes).
i.e. the process cannot be stopped during regular operation.

Preemptive scheduling:

A process can be stopped at any point by a clock interrupt.

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 16 / 31

How to implement multi-tasking The Dispatcher

Efficiency measures of scheduling policies

There are many possible ways to measure efficiency of
scheduling policies.

We consider the following 3:

Turnaround time.
CPU usage.
Response time.

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 17 / 31

How to implement multi-tasking The Dispatcher

Turnaround time

Turnaround time of a particular process is its duration in real
time, i.e. the difference between the end and the start times.

Turnaround time of a group of processes is the average of their
individual turnaround times.

Example:

We have 3 processes with respective start and end times
(100, 200), (150, 300) and (200, 400).
The individual turnaround times are 100, 150, 200.
The average turnaround time is 150

A good scheduling policy keeps average turnaround time as low
as possible.

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 18 / 31

How to implement multi-tasking The Dispatcher

CPU Usage

If all the processes are blocked waiting for completion of their I/O
operations, the CPU stays idle.

A good scheduling policy minimises the idleness time.

CPU usage: given some amount of time, the percentage of
time during which the CPU is busy.

Clearly, it is good if the scheduling policy maximises CPU usage.

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 19 / 31

How to implement multi-tasking The Dispatcher

Response time

The OS classifies some processes as user commands.

E.g, in Linux, user requests are commands like cp, cd, ls, etc. or
applications.

The response time is average turnaround time of user
requests.

The turnaround time of other processes is ignored.

response time must be minimised in interactive systems.

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 20 / 31

How to implement multi-tasking The Dispatcher

Types of operating systems

Batch systems:

Run a series of programs without human intervention.
Examples: scientific computing, salary calculation in big
companies.
Turnaround time and CPU usage are more important measures
than response time.

Interactive systems:

Designed to continuously communicate with the user.
Examples: Linux, Windows.
Response time is more important measure than the other two.

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 21 / 31

How to implement multi-tasking Scheduling policies

First come first served (FCFS) policy

This policy is non-preemptive.

The first READY process in the queue is started.

The process releases the CPU when it finishes or it BLOCKs on
I/O

When a process gets BLOCKed by an I/O interrupt, it goes to the
end of the READY queue when it is subsequently unblocked.

Suitable for batch systems only.

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 22 / 31

How to implement multi-tasking Scheduling policies

Advantages and disadvantages of the FCFS policy

Advantages:

Easy to implement.
No indefinite waiting (when a process can potentially wait forever
to be run).

Disadvantage: turnaround time of short processes can be much
longer than their actual execution time.

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 23 / 31

How to implement multi-tasking Scheduling policies

Shortest job first (SJF) policy

The policy is non-preemptive.

Requires knowledge about the runtime of programs before
they actually execute.

From the queue of READY processes choose the one whose
(expected) runtime is smallest.

Otherwise, as for FCFS.

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 24 / 31

How to implement multi-tasking Scheduling policies

Advantages and disadvantages of the SJF policy

Advantage: favourable to program with short runtimes.

Disadvantages:

Requires advance knowledge about runtimes.
Indefinite waiting is possible: a long process can wait a long time
if multiple new short processes arrive.
Does not take into account the situation when a long process is
close to completion (i.e. effectively becomes a short process).

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 25 / 31

How to implement multi-tasking Scheduling policies

Shortest remaining time first (SRTF) policy

This is a preemptive policy.

For every process, requires knowledge of the remaining
runtime.

Very similar to SJF.

The differences are:

Chooses process with the shortest remaining time instead
shortest overall time.
When a process with shorter remaining time than the current one
arrives in the READY queue, the current process is preempted.

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 26 / 31

How to implement multi-tasking Scheduling policies

Advantages and disadvantages of the SRTF policy.

Advantage: even more sensitive to the short processes than SJF.

Disadvantages: requires advance knowledge of runtimes;
indefinite waiting is still possible.

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 27 / 31

How to implement multi-tasking Scheduling policies

Round-Robin scheduling policy

This is a preemptive policy used in interactive systems.

Each process in turn gets the CPU for a fixed time quantum
(typically 10–20 ms).

When the quantum finishes: a timeout interrupt occurs and the
process goes to the back of the queue.

If a process blocks on I/O, it goes to the back of the queue.

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 28 / 31

How to implement multi-tasking Scheduling policies

Quantum duration for round-robin

Context switch: is the procedure of replacing the currently
running process by another one. This takes a non-zero amount
of time.

If the quantum is too short (similar to the time taken for a
context switch), the CPU spends a large proportion of its time
just context switching.

If the quantum is too long then the response time may become
unacceptable.

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 29 / 31

How to implement multi-tasking Real world schedulers

Schedulers used in actual OSes

MS-DOS: single process (no scheduling);

Windows 3.1: non-preemptive;

Windows NT (and newer): multi-level feedback queue;

Linux: multi-level feedback queue until 2.6; then the O(1)
scheduler; uses completely fair scheduler (CFQ) since
2.6.23;

MacOS 9: Round-robin, with cooperative non-preemptive threads;

MacOS X: multi-level feedback queue;

Android: CFQ, but with processes grouped into 5 priority levels;
aggressively kills “idle” processes;

iOS (iphone): none until iOS4; cooperative multi-tasking since then.

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 30 / 31

Summary

Summary

What a process is.

What interrupts are.

The Dispatcher implements scheduling policy.

Compared various simple scheduling policies.

gtl1–R570 W1L2 — Multi-tasking 2016–01–26 31 / 31

CO2017 — Week 1L3 — Linux OS and the Linux

user interface

Dr Gilbert Laycock (gtl1)

2016–01–24

gtl1–R557 W1L3 — Linux user interface 2016–01–24 1 / 10

Recap

Recap and Lecture Review

Recap

Overview of OSs:

Managing resources and extending the machine

Two key concepts of OSs:

Processes & interrupt

Multitasking and scheduling algorithms

gtl1–R557 W1L3 — Linux user interface 2016–01–24 2 / 10

Relationship of user interface and the OS

User interface is built on top of an OS

The user’s gateway into the computer.

Enables the user to interact with the computer via the capabilities
provided by the OS.

Human-computer interaction (HCI) is now a hot topic

Inconsistency and lack of forethought in the design of user interface have
made much trouble in many systems.
User-friendliness has become a key factor in computer system design.

gtl1–R557 W1L3 — Linux user interface 2016–01–24 3 / 10

Relationship of user interface and the OS Exploring OS features using linux command line

Tour of linux command line looking at OS features

Status of processes

Memory usage

Filesystem

Devices

gtl1–R557 W1L3 — Linux user interface 2016–01–24 4 / 10

Relationship of user interface and the OS System calls

System Calls

A layer of services/procedures just on top of the hardware an OS
provides for user programs to implement some activities, usually
sensitive or privileged

Different OSs have different set of system calls

An OS has only limited system calls, but may provide additional
subroutines, APIs, between the programmer and system call interface

Invoking a system call is similar to calling a general function. But the
general function code is part of the calling program, while the system
call code is in the OS

gtl1–R557 W1L3 — Linux user interface 2016–01–24 5 / 10

Relationship of user interface and the OS System calls

Example System Calls of UNIX OS

System V UNIX provides about 64 system calls, concerning file, I/O, and
processes.

System Call Description

Process
pid = fork() Create a child process identical to the parent
exit(status) Terminate process execution and return status
File management
read(fd,buf,size) Read data from a file into a buffer
link(fd1,fd2) Create a new entry fd2 pointing to fd1
Miscellaneous
time(&secs) Get the elapsed time since Jan 1, 1970 GMT
stime(secs) Set the system time and date

gtl1–R557 W1L3 — Linux user interface 2016–01–24 6 / 10

Relationship of user interface and the OS Kernel vs User mode

Kernel vs User mode

User Mode
Applications

Standard Libraries

Kernel Mode

system-call interface to the kernel

CPU scheduling file system virtual memory

kernel interface to the hardware

Hardware Physical memory device controllers terminals

gtl1–R557 W1L3 — Linux user interface 2016–01–24 7 / 10

Relationship of user interface and the OS Command line

Command Language

Allow users to interact directly with an OS via a terminal

The main aim is to initiate the execution of programs

They are of most value to operational users

In UNIX and similar systems, they are sufficiently powerful for
application programming

UNIX command language, shell, has the format like

commandname options arguments #comment

e.g., “ls -l” lists all file information in the directory

A series of commands can be assembled in a text file — shell program
or script

gtl1–R557 W1L3 — Linux user interface 2016–01–24 8 / 10

Relationship of user interface and the OS GUI/WIMP interface

Graphical User Interface (GUI)

GUIs are a common, significant feature in modern computing

GUIs are usually layered on top of an existing command based interface, e.g, X
Windows for UNIX and Windows for MS-DOS

Common features of GUI systems

On-screen overlapping windows
Pointing devices, usually a mouse
Various graphical features: buttons, icons, scroll bars
Higher level components: menus, selection lists, dialogue boxes

A GUI system is a desktop metaphor: the screen display represents a working
desk with documents the user can switch

gtl1–R557 W1L3 — Linux user interface 2016–01–24 9 / 10

Summary

Summary

User interface enables the user computer interaction

System calls are the ultimate user interface to computer

Different users may prefer different user interfaces

System calls may be directly used by programmers
Command languages are efficient for operational users
GUIs are most common, esp. for end-users

gtl1–R557 W1L3 — Linux user interface 2016–01–24 10 / 10

CO2017 — Week2 L1 — Concurrency and Threads

Dr Gilbert Laycock (gtl1)

2016–01–31

gtl1–R578 W2L1 — Concurrency 2016–01–31 1 / 28

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–R578 W2L1 — Concurrency 2016–01–31 2 / 28

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)
Protected resources: memory state, I/O state

NB Strictly sequential — i.e. no concurrency.

gtl1–R578 W2L1 — Concurrency 2016–01–31 3 / 28

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–R578 W2L1 — Concurrency 2016–01–31 4 / 28

Processes and Threads Threads

Threads

A thread is an independent sequence of execution within a program

gtl1–R578 W2L1 — Concurrency 2016–01–31 5 / 28

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–R578 W2L1 — Concurrency 2016–01–31 6 / 28

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–R578 W2L1 — Concurrency 2016–01–31 7 / 28

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–R578 W2L1 — Concurrency 2016–01–31 8 / 28

Review of sequential programming Single processor architecture

Program

Program Counter

Runtime Data
Processor

(CPU)

I/O

Devices

(RAM)
Random Access Memory

Bus

gtl1–R578 W2L1 — Concurrency 2016–01–31 9 / 28

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–R578 W2L1 — Concurrency 2016–01–31 10 / 28

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–R578 W2L1 — Concurrency 2016–01–31 11 / 28

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–R578 W2L1 — Concurrency 2016–01–31 12 / 28

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

Single threaded computation, no overlap in the execution of the
statements — Total Ordering

gtl1–R578 W2L1 — Concurrency 2016–01–31 13 / 28

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–R578 W2L1 — Concurrency 2016–01–31 14 / 28

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–R578 W2L1 — Concurrency 2016–01–31 15 / 28

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 with these factors in 1 hour

NB: 368788194383 = 7 × 17 × 23 × 257 × 524287

gtl1–R578 W2L1 — Concurrency 2016–01–31 16 / 28

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–R578 W2L1 — Concurrency 2016–01–31 17 / 28

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 and Socket; Posix thread
support, etc.

gtl1–R578 W2L1 — Concurrency 2016–01–31 18 / 28

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–R578 W2L1 — Concurrency 2016–01–31 19 / 28

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–R578 W2L1 — Concurrency 2016–01–31 20 / 28

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–R578 W2L1 — Concurrency 2016–01–31 21 / 28

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–R578 W2L1 — Concurrency 2016–01–31 22 / 28

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–R578 W2L1 — Concurrency 2016–01–31 23 / 28

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–R578 W2L1 — Concurrency 2016–01–31 24 / 28

Concurrent programming Interleaving

n : 2 4 6 8 10 · · ·
f(n, n) : 6 70 924 12870 184756 · · ·

gtl1–R578 W2L1 — Concurrency 2016–01–31 25 / 28

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–R578 W2L1 — Concurrency 2016–01–31 26 / 28

Summary

Summary

Processes, threads, context switching

Sequential programming, compared with

Concurrent programming

gtl1–R578 W2L1 — Concurrency 2016–01–31 27 / 28

Summary

Next time

Processes sharing resources

Critical regions, mutual exclusion

Algorithms for solving critical region issues

gtl1–R578 W2L1 — Concurrency 2016–01–31 28 / 28

CO2017 — Week 2 — Sharing resources among

concurrent processes

Dr Gilbert Laycock (gtl1)

2016–01–31

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 1 / 28

Recap

Recap

Abstract notion of process (and thread)

Potential to take advantage of concurrent programming:

Fully utilise CPU while some processes are blocked
Fully utilise multi-CPU systems
Some problems easier to solve with parallel reasoning
Some problems inherently non-deterministic

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 2 / 28

Recap

Overview

1 Inter-process communication

2 Critical regions and mutual exclusion
3 Possible solutions

Disabling interrupts
Access in turns; Peterson’s algorithm
Semaphores

4 Note that in this discussion we use process and thread
interchangeably.

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 3 / 28

Shared resources Inter-process Communication

InterProcess Communication

Processes need to communicate, e.g. in a shell pipeline.

But, with concurrent operation, there are issues with

passing messages between processes;
safe sharing of resources;
correct sequencing in the presence of dependencies.

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 4 / 28

Shared resources Example: shared print spool

Hazards of using shared resources

Programs often use shared resources, e.g:

Send/receive data to/from the same device (printer; etc.);
Use the same file or a block of RAM (variable; object attribute;
etc.) to store data.

The role of the OS is to avoid incorrect operation of programs
due to shared resource clashes.

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 5 / 28

Shared resources Example: shared print spool

A shared resource: printer spooler

E.g. we want to ensure that files are printed one after another and
not, say, one page of one file, the next page of a different file.

Printer spool: a place on a disk organised into a number of
consecutive slots

Each process that wants to print a file

detects the first unoccupied slot;
stores the file name in the slot.

The printer manager periodically examines the slots and sends
the files to print.

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 6 / 28

Shared resources Example: shared print spool

Scenario of a clash

Processes P1 and P2 are simultaneously running and both want
to print their files.

Process P1 detects the first unoccupied slot in the spooler
directory (slot 6 say) and then a context switch occurs

Process P2 resumes and detects that slot 6 is free, writes its file
name there and then a context switch occurs.

Process P1 resumes again: it writes its file name to slot 6 (erasing
the record of P2).

P2’s file will never be printed.

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 7 / 28

Shared resources Race conditions

Race conditions

Race conditions are situations when two or more processes are
reading or writing some shared data and the result depends on
the order of execution.

A race condition occurred in the example because of combination
of two circumstances:

Process P1 was interrupted during the use of the shared
resource.
Process P2 used the shared resource while P1 was interrupted.

To prevent the race condition happen, at least one of the
circumstances should be avoided.

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 8 / 28

First approaches to synchronisation

Avoiding race conditions

A critical region is part of the program where shared memory is
accessed. Successful synchronisation requires:

Mutual Exclusion: no two processes should be in their critical
region at the same time.

Progress: no process running outside the critical region may
block other processes.

Bounded wait: each processes should enter its critical region
eventually.

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 9 / 28

First approaches to synchronisation Disabling interrupts

Disabling interrupts: the method

At the hardware level, processors have instructions that
effectively disable all interrupts

A process accessing a shared resource can act as follows
1 Disable all interrupts
2 Access the shared resource
3 Re-enable interrupts

The absence of interrupts ensures that the process is not
interrupted while it accesses the shared resource.

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 10 / 28

First approaches to synchronisation Disabling interrupts

Disabling interrupts: has it helped?

Disabling interrupts achieves mutual exclusion.

But

Disabling interrupts prevents any other processes running
even if it does not need the shared resource.

The strategy is non-preemptive.

So neither progress nor bounded wait is assured.

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 11 / 28

First approaches to synchronisation Access in turns

Access in turns: Overview

A preemptive scheduling policy is needed.

Assume for simplicity that there are only two processes (P0
and P1) running

The resource is associated with a shared variable “turn” that
can take values 0 or 1.

P0 accesses the resources only if turn == 0; P1 accesses it only
if turn == 1.

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 12 / 28

First approaches to synchronisation Access in turns

Access in turns: The algorithm

Algorithm for P0 Algorithm for P1

while(turn == 1) {} ; while(turn == 0) {} ;

Access the resource; Access the resource;

turn = 1; turn = 0;

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 13 / 28

First approaches to synchronisation Access in turns

How does the mechanism work?

Assume turn = 0

If P1 wants to access the resource it will be busy waiting (in the
empty while loop).

When P0 finishes using the resource it assigns turn = 1
enabling P1 to proceed.

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 14 / 28

First approaches to synchronisation Access in turns

Disadvantage: useless busy waiting

If it is not its turn, a process cannot start using the resource
even if the other process is not interested.

So performing the while loop wastes CPU time.

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 15 / 28

First approaches to synchronisation Peterson’s Algorithm

Towards Peterson’s algorithm

Keep track of which processes are interested in accessing the
critical region.

Assume we have only two processes, P0 and P1.

Each process uses a Boolean flag[pid] to express interest in
entering their critical section.

Both flag[0] and flag[1] are initialised to false.

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 16 / 28

First approaches to synchronisation Peterson’s Algorithm

Incorrect attempt

This does not work. Why?
Algorithm for P0 Algorithm for P1

flag[0] = true; flag[1] = true;
while(flag[1]) {} ; while(flag[0]) {} ;
// access resource // access resource
… …

flag[0] = false; flag[1] = false;

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 17 / 28

First approaches to synchronisation Peterson’s Algorithm

Peterson’s algorithm

Keeps track of which processes are interested in accessing the
critical region.

Assume we have only two processes, P0 and P1.

Each process uses a Boolean flag[pid] to express interest in
entering the critical section.

Both flag[0] and flag[1] are initialised to false.

To avoid a deadlock, the process that starts the entry protocol
last is allowed to proceed to the critical section first.

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 18 / 28

First approaches to synchronisation Peterson’s Algorithm

Peterson’s algorithm

flag[0] = false; flag[1] = false;

Algorithm for P0 Algorithm for P1

flag[0] = true; flag[1] = true;
turn = 1; turn = 0;
while(flag[1] && while(flag[0] &&

turn==1) {} ; turn==0) {} ;
// access resource // access resource
… …
flag[0] = false; flag[1] = false;

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 19 / 28

First approaches to synchronisation Busy waiting

Busy waiting in Peterson’s algorithm

The while loop in Peterson’s algorithm performs busy waiting

However, waiting is performed only if the other process is
interested in accessing the resource

Compare with the busy waiting required by the access in turns
method

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 20 / 28

First approaches to synchronisation Busy waiting

Informal Justification of correctness

1 If only P0 wants to access the resource. Then P0 can proceed to
the critical section because flag[1] = false.
And vice versa if only P1 wants the resource.

2 If both processes want to access the resource, then both flag[0]
and flag[1] are true.

3 Suppose that P1 is the last to modify turn, i.e. turn == 0.

4 Then P1 will busy-wait while P0 will enter the critical region.

5 And vice versa if P0 happens to be the last to set turn.

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 21 / 28

First approaches to synchronisation Problems with Peterson’s solution

Problems with Peterson’s Solution

The entry/exit protocols are directly programmed using
busy-waiting

Busy-waiting protocols are difficult to design, understand,
generalise, and analyse

No separation between variables used for synchronisation and
“normal” variables

So, they are often error-prone and inefficient

Modern compilers and processors make it very difficult to make naïve
assumptions about the order statements are executed

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 22 / 28

Semaphores

Motivation for Semaphores

It would be much simpler to write entry/exit protocols using single
statements, e.g.

GETSEMAPHORE;
critical section;
RELEASESEMAPHORE;
non-critical section

We want to encourage the processor to context switch away from a
blocked process to another process (i.e. no busy waiting)

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 23 / 28

Semaphores Example of semaphores

Synchronisation in Railway Traffic

Railway traffic is synchronised as below:

A railway semaphore is used to signal whether the track ahead is clear
or not
As a train proceeds, semaphores are set and cleared
Railway semaphores are mechanisms that ensure mutually exclusive
occupancy of critical sections of track

Semaphores in concurrent programs are similar:

They provide a basic signalling mechanism to implement mutual
exclusion and condition synchronisation

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 24 / 28

Semaphores Definition of semaphore

Definition of Semaphore

Semaphores were introduced by Dijkstra (1968)

A semaphore is an integer variable that takes only non-negative
values (representing the quantity of a resource available)

Only two operations are permitted on a semaphore s:

Wait(s) (or P(s) for Prolaag – to “try to reduce” s):

If s > 0 then decrement s
else block the calling process

Signal(s) (or V(s) for Verhogen – to inscrease s):

If processes are blocked on s then unblock one
else increment s

Semaphores are often implemented efficiently with hardware facilities
and in the kernel of OSs by block-waiting

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 25 / 28

Semaphores Definition of semaphore

Remarks on Semaphores

Wait() and Signal() need to be implemented as synchronized methods

Wait() should wait until the semaphore value becomes > 0

Signal() should release other processes waiting on the semaphore

Wait() and Signal() use block-waiting rather than busy-waiting. A
blocked process uses no CPU time.

If a semaphore only takes 0 or 1, it is called binary; otherwise, called
general (or counting)

Need to ensure that the initial value is ≥ 0 and overflow should not
occur by increment

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 26 / 28

Semaphores Definition of semaphore

Simple semaphore example

Semaphore s = new Semaphore(1);

Algorithm for Process 0 Algorithm for Process 1

Wait(s); Wait(s);
// access resource // access resource
… …
Signal(s); Signal(s);

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 27 / 28

Summary

Summary

Processes (or threads) need to communicate/share resources

Concurrent processes can result in race conditions in access to
critical region

Various (low level) strategies to avoid the problems and achieve

mutual exclusion
progress
bounded wait

Considered: Disable interrupts; access in turns; Peterson’s
method; Semaphores

gtl1–R578 W2L2 — Concurrently shared resources 2016–01–31 28 / 28

CO2017 — Week3L1 — Threads in Java

Dr Gilbert Laycock (gtl1)

2016–02–08

gtl1–R593 W3L1 — Java Threads 2016–02–08 1 / 17

Recap/overview

Recap and Lecture Overview

Recap

The nature of concurrent programming is multiple processes/threads
running in parallel
Processes may share resources
Solutions need to guarantee mutual exclusion, progress, bounded waiting

Overview of this lecture

How can Java support concurrent programming?

Java Thread class, and Runnable interface
Java ThreadGroup class, Executors and ThreadPools
Simple examples

gtl1–R593 W3L1 — Java Threads 2016–02–08 2 / 17

Concurrency in Java

Concurrency in Java

Java Virtual Machine (JVM) allows an application to have multiple
threads running concurrently

the thread concept is supported by

the classes java.lang.Thread and java.lang.ThreadGroup
the interface java.lang.Runnable

Two ways to create a new thread

Extending the Thread class
Implementing the Runnable interface

gtl1–R593 W3L1 — Java Threads 2016–02–08 3 / 17

Concurrency in Java

Two ways to create a thread

Extend Thread class

Implement Runnable class

MyRunnable

+run(): void

Thread

+run(): void

ExampleThread

+run(): void

Runnable

+run(): void
Thread

gtl1–R593 W3L1 — Java Threads 2016–02–08 4 / 17

Concurrency in Java Extend Thread class

Extending Java Thread Class

Declare a subclass of Thread, overriding its run() method

public class ExampleThread extends Thread {
int parameter;
ExampleThread(int para) { parameter = para; }

public void run() {
… // what the thread should do

}
}

Create an instance of the subclass and start executing it

ExampleThread t = new ExampleThread(10);
t.start();

gtl1–R593 W3L1 — Java Threads 2016–02–08 5 / 17

Concurrency in Java Implement Runnable interface

Implementing the Interface Runnable

Java does not permit multiple inheritance

So usually more convenient to implement run() from Java interface
Runnable instead of deriving from Thread

Runnable declares (just) the run() method

public interface Runnable {
public abstract void run();

}

We can extend other classes while implementing Runnable

In fact, the Thread class just implements Runnable

public class Thread
extends Object
implements Runnable

gtl1–R593 W3L1 — Java Threads 2016–02–08 6 / 17

Concurrency in Java Implement Runnable interface

Implementing the Interface Runnable (Cont’d)

First declare a class implementing Runnable

public class MyRunnable extends SomeClass
implements Runnable {

int parameter;
MyRunnable (int para) { parameter = para; }

public void run() {
… // what should the thread do?

}
}

Threads can then be allocated and started by

MyRunnable r = new MyRunnable(10);
Thread t = new Thread(r);
t.start();

gtl1–R593 W3L1 — Java Threads 2016–02–08 7 / 17

Concurrency in Java Thread methods

Methods of Thread Class

Some principal methods of the Thread class

t.start(): Causes thread t to begin execution; (JVM will call run()
concurrently)
t.run(): Call the run method of thread t directly (with no concurrency)
Thread.sleep(ms): Cease the execution of current thread for ms
milliseconds
t.join(): Causes the calling thread to wait (block) for the thread t to
finish

Refer to the Java documents about Thread class and Runnable
interface.

gtl1–R593 W3L1 — Java Threads 2016–02–08 8 / 17

Concurrency in Java Using threads

Outline code using Threads

public class T1 extends Thread {
// attributes and constructor
public void run() { /* thread functionality */ }

}
……
public class Tn extends Thread {
// attributes and constructor
public void run() { /* thread functionality */ }

}
public class MainProgram {
public static void main(String[] args) {

B;
T1 t1 = new T1(); …; Tn tn = new Tn();
t1.start(); …; tn.start();
I;
t1.join(); …; tn.join();
F; }

}

gtl1–R593 W3L1 — Java Threads 2016–02–08 9 / 17

Concurrency in Java Using threads

The Semantics of start()

The execution of B finishes before t1,. . . ,tn as they have not been
started yet;

The effect of t1.start(),. . . ,tn.start() is equivalent to interleaving
the atomic actions of the started threads;

Execution of statement I can interleave with t1,. . . ,tn

Execution of statement F does not begin until all of t1,. . . ,tn have
completed

Execution of main() terminates only if all of the started threads (and
I and F) terminate

If we replace t1.start(),. . . ,tn.start() with t1.run(),. . . ,tn.run(),
the program will become a sequential program

gtl1–R593 W3L1 — Java Threads 2016–02–08 10 / 17

Concurrency in Java Examples

Thread Example

class ExampleThread extends Thread {
int _id;
ExampleThread(int id) { _id = id; }
public void run() {

System.out.println(“This is thread: ” + _id);
}
public static void main(String[] args) {

ExampleThread t1 = new ExampleThread(42);
ExampleThread t2 = new ExampleThread(43);
ExampleThread t3 = new ExampleThread(44);
t1.start();
t2.start();
t3.start();
System.out.println(“All threads have terminated.”);

}
}

gtl1–R593 W3L1 — Java Threads 2016–02–08 11 / 17

Concurrency in Java Examples

Execution Result

A possible result is as follows:

This is thread 42
This is thread 43
All threads have terminated.
This is thread 44

The statements in main() after the start() statements can interleave
with the statements of the started threads.

The result is non-deterministic, and can differ with each run of the
program.

gtl1–R593 W3L1 — Java Threads 2016–02–08 12 / 17

Concurrency in Java Examples

Runnable example

class ExampleRunnable implements Runnable {
int _id;

ExampleRunnable(int id){ _id = id; }
public void run() {

System.out.println(“This is runnable thread: ” + _id);
}
public static void main(String[] args) {

Thread t1 = new Thread(new ExampleRunnable(42));
Thread t2 = new Thread(new ExampleRunnable(43));
Thread t3 = new Thread(new ExampleRunnable(44));
t1.start();
t2.start();
t3.start();
System.out.println(“All threads have terminated.”); }

}

gtl1–R593 W3L1 — Java Threads 2016–02–08 13 / 17

ThreadPoolExecutor Use ThreadPools to group and control threads

ThreadPoolExecutor

In order to control or synchronise the behaviour of threads, a thread
pool can be used

A thread pool represents a set of threads.

A thread can access info about its own thread pool.

Methods of Java ThreadPoolExecutor class include

Factory methods for creating new thread pools, e.g.
ex = (ThreadPoolExecutor)
Executors.newFixedThreadPoolExecutor(5);
int getActiveCount(): Returns the number of active threads in this
thread pool

Add a thread t to a pool ex by calling
Thread t = new Thread(Runnable r);
ex.execute(t);

gtl1–R593 W3L1 — Java Threads 2016–02–08 14 / 17

ThreadPoolExecutor ThreadPool example

ThreadPool Example

public class ThreadPoolMember implements Runnable {
// public class ThreadPoolMember extends Thread {
int _id;
ThreadPoolMember (int id) { _id = id; }

public void run() {
System.out.println(“This is thread: ” + _id);
try Thread.sleep(500); }

catch(InterruptedException e) {};
System.out.println(“This is thread: “+ _id +” again.”);
try { Thread.sleep(500); }

catch(InterruptedException e) {};
System.out.println(“Thread “+ _id +” has terminated.”);

gtl1–R593 W3L1 — Java Threads 2016–02–08 15 / 17

ThreadPoolExecutor ThreadPool example

ThreadPool Example (Cont’d)

public static void main(String[] args) {
ThreadPoolExecutor ex = (ThreadPoolExecutor) Executors.newFixedThreadPool(5);
for (int i=42; i<=44; ++i) { ThreadPoolMember t = new ThreadPoolMember(i); ex.execute(t); } System.out.println(ex.getActiveCount()+" threads."); while (ex.activeCount() > 0) {

try { Thread.sleep(100); } catch(InterruptedException e) {};
}
System.out.println(“All threads have terminated.”);

}
}

Program now outputs “All threads have terminated” only
after all threads actually terminated.

gtl1–R593 W3L1 — Java Threads 2016–02–08 16 / 17

Summary

Summary

Thread in Java can be created via:

Extending Thread class
Implementing Runnable interface

The result of running programs with multiple threads may be
non-deterministic

The Java ThreadPoolExecutor class can be used to collectively
manage the behaviour of threads

(Deprecated ThreadPool interface provides another mechanism to
control groups of threads.)

We have not yet really considered critical sections

gtl1–R593 W3L1 — Java Threads 2016–02–08 17 / 17

CO2017 — Week3L2 — Synchronisation in Java

Dr Gilbert Laycock (gtl1)

2016–02–07

gtl1–R587 W3L2 — Java Synchronisation 2016–02–07 1 / 20

Recap/overview

Recap 1: Critical code

Concurrent processes are interleaved unpredictably

Some code sections are critical, and we want to achieve:
mutual exclusion; progress; bounded waiting

Possible techniques considered: disable interrupts; access in
turns; Peterson’s algorithm; semaphores

gtl1–R587 W3L2 — Java Synchronisation 2016–02–07 2 / 20

Recap/overview

Recap2: Java threads

Any Java program has one special thread that runs main method

We can define an arbitrary number of additional threads.

Defining a new thread requires two things:

Define a new class implementing interface Runnable (or directly
extend the Thread class)
In function main, define one or more instances of the new
Runnable/Thread class.

gtl1–R587 W3L2 — Java Synchronisation 2016–02–07 3 / 20

Recap/overview

Overview

synchronise as basic java feature for programming critical
sections.

Simulate semaphores in Java using synchronise

Producer/consumer example

Implement producer/consumer example using semaphore
simulation

gtl1–R587 W3L2 — Java Synchronisation 2016–02–07 4 / 20

Synchronisation Shared resources

Using a shared resource

Create a Java class representing the shared resource

Pass the same object of this class to each of the involved
threads — a shared resource

Interleaving of threads makes access to the object
unpredictable resulting in contention and race conditions

We need a method of providing mutual exclusion, etc.

gtl1–R587 W3L2 — Java Synchronisation 2016–02–07 5 / 20

Synchronisation Synchronisation

Synchronization

Java has a fundamental mechanism (based on monitors): make
methods synchronized

A class providing a shared resource can have one or more
methods accessing the data declared as synchronized

This ensures that at a given moment of time only one thread can
be executing a synchronized method

All the mechanisms of controlled access to a shared resources
discussed so far can be simulated in Java using synchronisation

gtl1–R587 W3L2 — Java Synchronisation 2016–02–07 6 / 20

Synchronisation Synchronisation

Waiting and notification in Java

The methods described below can be performed in a
synchronized function of a class.

wait() the current thread blocks itself and waits for something
to notify it.

notify() releases one of the waiting threads.

notifyAll() releases all of the waiting threads.

gtl1–R587 W3L2 — Java Synchronisation 2016–02–07 7 / 20

Example 1: Simulate semaphores using synchronized methods

Example: Recall definition of Semaphore

A semaphore is an integer val that takes only non-negative values
(representing the quantity of a resource available)

Only two operations are permitted on a semaphore s:

Wait

If val > 0 then decrement val
else block the calling process

Signal

If there are processes blocked on s then unblock one
else increment val

gtl1–R587 W3L2 — Java Synchronisation 2016–02–07 8 / 20

Example 1: Simulate semaphores using synchronized methods

Java Code for the Semaphore Class

class Semaphore {
private int value;
public Semaphore (int init) { value = init; }

synchronized public void Wait()
throws InterruptedException {

while (value == 0) this.wait();
–value; }

synchronized public void Signal() {
if (value == 0) this.notifyAll();
++value; }

}

gtl1–R587 W3L2 — Java Synchronisation 2016–02–07 9 / 20

Example 1: Simulate semaphores using synchronized methods Simple example of mutual exclusion

Mutual Exclusion with Semaphore

class Thread_i extends Thread {
Semaphore mutex;
public Thread_i(Semaphore s) { mutex = s; }
public void run() {
while (true) {

noncritical_i;
mutex.Wait(); critical_i; mutex.Signal();

}
}

}
public class Controller {

public static void main() {
Semaphore s = new Semaphore(1)
Thread_1 t1 = new Thread_1(s);
……
Thread_n tn = new Thread_n(s);
t1.start(); …; tn.start();

}
}

gtl1–R587 W3L2 — Java Synchronisation 2016–02–07 10 / 20

Example 1: Simulate semaphores using synchronized methods Trace of mutual exclusion

Why Semaphore Ensures Mutual Exclusion?

Consider three processes t1, t2 and t3

s t1 t2 t3
Initially 1 start start start
t1 executes wait() 0 start start start
t2 executes wait() 0 crit blocked start
t3 executes wait() 0 crit blocked blocked
t1 executes signal() 0 noncrit crit blocked
t1 executes wait() 0 blocked crit blocked

…………………….

Once one process enters its critical section, the others must wait

gtl1–R587 W3L2 — Java Synchronisation 2016–02–07 11 / 20

Introducing the producer/consumer problem

The Producer and Consumer Problem

Problem description:

a producer repeatedly produces items and places them into a
buffer;
meanwhile a consumer consumes the items one-by-one by taking
from the buffer.

Requirements:

Assume an implementation of a bounded FIFO buffer with operations
place() and take()
The producer may produce a new item only when the buffer is not full
The consumer may consume an item only when the buffer is not empty
All items produced are eventually consumed

gtl1–R587 W3L2 — Java Synchronisation 2016–02–07 12 / 20

Introducing the producer/consumer problem Solution overview

Behaviour of the FIFO Buffer

Implementation as an array.

We need NextIn and NextOut to locate where to place an item into
and take an item from the buffer

NextIn and NextOut are incremented one by one. When they reach the
end of the buffer we need roll-over to 0.

gtl1–R587 W3L2 — Java Synchronisation 2016–02–07 13 / 20

Introducing the producer/consumer problem Using semphores to control access to the queue

Design of Solution using semaphores

Use a semaphore ItemsReady to record the number of items in the
buffer

The consumer must be blocked on the semaphore ItemsReady when it
is 0, i.e. when the buffer is empty, the consumer cannot proceed.

The initial value of ItemsReady should be 0 (since the queue is empty).

After the producer places an item, it should signal on the semaphore
ItemsReady.

Use a semaphore SpacesLeft to record free spaces in the buffer; its
initial value should be the buffer size.

The producer should be blocked when SpacesLeft is 0.

After the consumer takes an item, it should signal on the semaphore
SpacesLeft.

gtl1–R587 W3L2 — Java Synchronisation 2016–02–07 14 / 20

Introducing the producer/consumer problem Implementation of producer/consumer

The Buffer Class

public class Buffer {
public static final int BUFFSIZE = 5;
private int[] _b = new int[BUFFSIZE];
private int _NextIn, _NextOut;
public Buffer() { _NextIn = 0; _NextOut = 0; }

public void place(int item) {
_b[_NextIn] = item;
_NextIn = (_NextIn + 1)%BUFFSIZE;

}

public int take() {
int value = _b[_NextOut];
_NextOut = (_NextOut + 1)%BUFFSIZE;
return value;

}

gtl1–R587 W3L2 — Java Synchronisation 2016–02–07 15 / 20

Introducing the producer/consumer problem Implementation of producer/consumer

The Buffer Class (Cont’d)

public static void main(String[] args) {
Semaphore MutEx = new Semaphore(1);
Semaphore ItemsReady = new Semaphore(0);
Semaphore SpacesLeft = new Semaphore(BUFFSIZE);

Buffer buff = new Buffer();

Producer p = new Producer(buff, MutEx,
ItemsReady, SpacesLeft);

Consumer c = new Consumer(buff, MutEx,
ItemsReady, SpacesLeft);

p.start(); c.start();
}

}

gtl1–R587 W3L2 — Java Synchronisation 2016–02–07 16 / 20

Introducing the producer/consumer problem Implementation of producer/consumer

The Producer Class

class Producer extends Thread {
Buffer _b; Semaphore _mx;
Semaphore _ready; Semaphore _spaces;
public Producer (Buffer buff, Semaphore mutEx,

Semaphore itemsReady,
Semaphore spacesLeft) {

_b = buff; _mx = mutEx;
_ready = itemsReady; _spaces = spacesLeft;

}
public void run() {

for (int i=1; i<=100; ++i) { _spaces.Wait(); // wait for spaces _mx.Wait(); // wait for mutual exclusion _b.place(i); // place an item _mx.Signal(); // release mutual exclusion _ready.Signal();// signal the consumer } } } gtl1–R587 W3L2 — Java Synchronisation 2016–02–07 17 / 20 Introducing the producer/consumer problem Implementation of producer/consumer The Consumer Class class Consumer extends Thread { Buffer _b; Semaphore _mx; Semaphore _ready; Semaphore _spaces; public Consumer (Buffer buff, Semaphore mutEx, Semaphore itemsReady, Semaphore spacesLeft) { _b = buff; _mx = mutEx; _ready = itemsReady; _spaces = spacesLeft; } public void run() { int value; for (int i=1; i <= 100; i++) { _ready.Wait(); // wait for items ready _mx.Wait(); // wait for mutual exclusion value = _b.take(); // take an item _mx.Signal(); // release mutual exclusion _spaces.Signal(); // signal the producer System.out.println(value); } } } gtl1–R587 W3L2 — Java Synchronisation 2016–02–07 18 / 20 Introducing the producer/consumer problem Implementation of producer/consumer Be Careful! What if ready.Wait(); mx.Wait() was swapped to mx.Wait(); ready.Wait() ? Answer: Exchanging the two Wait()s is fatal Consumer executes mx.Wait() and ready.Wait() and is blocked Producer executes spaces.Wait() and mx.Wait() and is blocked Deadlock: A process is said to be deadlocked if it is waiting for an event which will never happen gtl1–R587 W3L2 — Java Synchronisation 2016–02–07 19 / 20 Summary Summary A semaphore is a primitive to synchronise threads. A semaphore has Wait() and Signal() operations to guarantee mutual exclusion of threads relevant to one shared object. Demonstrated the application of semaphores for the Producer and Consumer problem. gtl1–R587 W3L2 — Java Synchronisation 2016–02–07 20 / 20 CO2017 — Week3L3 — Monitors Dr Gilbert Laycock (gtl1) 2016–02–08 gtl1–R599 W3L3 — Monitors 2016–02–08 1 / 19 Recap and overview Recap and Lecture Overview Recap Simple techniques: disable interrupts; Peterson’s algorithm, etc. Hard to reason about; need to be re-implemented in each case. Semaphore is simpler and more robust. Overview of this lecture: More detailed critique of semaphores. Introduce monitor as improved concurrency primitive. Apply monitor to the Producer and Consumer problem. gtl1–R599 W3L3 — Monitors 2016–02–08 2 / 19 Semaphores Recap: Semaphores A Semaphore has a non-negative integer value and supports the following two operations: a wait operation Wait(): an atomic operation that waits for semaphore to become positive, then decrements it. a signal operation Signal(): an atomic operation that increments the semaphore, waking up a waiting process, if any. gtl1–R599 W3L3 — Monitors 2016–02–08 3 / 19 Semaphores Mutex and resource constraints Using Semaphores Mutual Exclusion Binary semaphore, we set initial value to 1. mutex.Wait(); critical-section; mutex.Signal(); Scheduling (resource) constraint Use one semaphore for each constraint. Recall Producer and Consumer problem: one semaphore to test if buffer is empty, another to test if buffer is full. gtl1–R599 W3L3 — Monitors 2016–02–08 4 / 19 Semaphores Bounded buffer recap Recap: Semaphore solution to Bounded Buffer Semaphore mx = 0; Semaphore ready = 0; Semaphore spaces = 5; Consumer: ready.Wait(); mx.Wait(); value = b.take(); mx.Signal(); spaces.Signal(); Producer: spaces.Wait(); mx.Wait(); b.place(i); mx.Signal(); ready.Signal(); gtl1–R599 W3L3 — Monitors 2016–02–08 5 / 19 Semaphores Positive features of semaphores Positive aspects of Semaphores Powerful enough to program all kinds of synchronisation and resource management requirements Relatively easy to be implement efficiently A general semaphore can be simulated by binary ones gtl1–R599 W3L3 — Monitors 2016–02–08 6 / 19 Semaphores Negative features of semaphores Negative aspects of Semaphores It is a low level facility and still error-prone, especially when more than one semaphore is in use at a time Missing a Signal() may lead to deadlock Missing a Wait() may lead to a violation of safety requirement, such as mutual exclusion Putting them in wrong order may be dangerous: just swapping Wait()s can lead to deadlock The use of monitors will overcome these problems gtl1–R599 W3L3 — Monitors 2016–02–08 7 / 19 Monitors Concepts Behind Monitor Introduced by Hoare and Hansen (1972). Shown by Hoare to be equivalent to Dijkstra’s semaphores. Two parts to a monitor: lock for enforcing mutual exclusion condition variable(s) for controlling access to resources; AKA guards gtl1–R599 W3L3 — Monitors 2016–02–08 8 / 19 Monitors Concept of Monitor In Object-oriented terms, a monitor is a class with Some attributes (data) (to be shared by processes) Some synchronised methods used to access the data Some variables for condition control (guards) Monitor data can only be accessed via its methods Entry to a monitor by one process excludes entry by any other processes. gtl1–R599 W3L3 — Monitors 2016–02–08 9 / 19 Monitors Mutual exclusion Execution of a Synchronised Method Java associates a lock with every object which transparently inserts code to acquire the lock before executing a synchronised method; and code to release the lock when the method returns. Concurrent threads are blocked until the lock is released Only one thread at a time may hold the lock and thus may be executing the synchronised method Executing synchronised methods of different objects can be concurrent gtl1–R599 W3L3 — Monitors 2016–02–08 10 / 19 Monitors Condition variables Condition Synchronisation Sometimes we need further control to synchronise the order of threads entering the critical section Condition synchronisation is the property that one process wishing to access shared data must be delayed until some condition holds E.g. in the Producer-Consumer problem Producer can place an item into the buffer only when it is not full Consumer can take an item from the buffer only when it is not empty regardless of whether any other thread is trying to use the buffer. gtl1–R599 W3L3 — Monitors 2016–02–08 11 / 19 Monitors Condition Synchronisation in Java Condition Synchronisation in Java Java provides a thread wait queue for each monitor (actually per object). Objects in the class Object have methods public final void notify(): wakes up a single thread that is waiting on this object’s wait set. public final void notifyAll(): wakes up all threads that are waiting on this object’s wait set. public final void wait() throws InterruptedException: waits to be notified by another thread. Implicitly releases lock. gtl1–R599 W3L3 — Monitors 2016–02–08 12 / 19 Monitors Condition Synchronisation in Java Basic pattern of Condition Synchronisation The basic format for condition synchronisation is when (condition) do act or when (not cond) wait In Java, the format is public synchronized void act() throws InterruptedException { while (!cond) wait(); ...... // modify monitor data notifyAll(); } gtl1–R599 W3L3 — Monitors 2016–02–08 13 / 19 Producer/Consumer example revisited Bounded buffer as a monitor Bounded Buffer as a Monitor public class MonitorBuffer { public static final int BUFFSIZE = 5; private int[] _b = new int[BUFFSIZE]; private int _count = 0; private int _nextIn, _nextOut; public MonitorBuffer() { _nextIn=0; _nextOut=0; } public synchronized void place(int item) throws InterruptedException { while (_count >= BUFFSIZE) wait();
_b[_nextIn] = item;
++_count;
_nextIn = (_nextIn +1)%BUFFSIZE;
notifyAll();

}

gtl1–R599 W3L3 — Monitors 2016–02–08 14 / 19

Producer/Consumer example revisited Bounded buffer as a monitor

Bounded Buffer as a Monitor (Cont’d)

public synchronized int take()
throws InterruptedException {

int value;
while (_count == 0) wait();
value = _b[_nextOut];
_nextOut = (_nextOut + 1)%BUFFSIZE;
-_count;
notifyAll();
return value;

}

public static void main(String[] args) {
MonitorBuffer buff=new MonitorBuffer();
Producer p = new Producer(buff);
Consumer c = new Consumer(buff);
p.start(); c.start();

}
}

gtl1–R599 W3L3 — Monitors 2016–02–08 15 / 19

Producer/Consumer example revisited Producer

The Producer Class

class Producer extends Thread {
MonitorBuffer _b;

public Producer(MonitorBuffer mb) { _b = mb; }

public void run() {
for (int i=1; i<=100; i++) { try { _b.place(i); Thread.sleep(500); } catch(InterruptedException e) { } System.out.println("Producer puts " + i +" in the buffer."); } } } gtl1–R599 W3L3 — Monitors 2016–02–08 16 / 19 Producer/Consumer example revisited Consumer The Consumer Class class Consumer extends Thread { MonitorBuffer _b; public Consumer(MonitorBuffer mb) { _b = mb; } public void run() { int value; for (int i=1; i<=100; i++) { try { value = _b.take(); Thread.sleep(1000); } catch(InterruptedException e) { } System.out.println("Consumer takes " + value + " out of the buffer."); } } } gtl1–R599 W3L3 — Monitors 2016–02–08 17 / 19 Producer/Consumer example revisited Analysis Features of this Program Encapsulates the critical code into the monitor Releases the user’s responsibility for coding/ordering Wait() and Signal() operations in the thread class The responsibility for ensuring mutual exclusion is moved to the language compiler Is more efficient and robust than Semaphore gtl1–R599 W3L3 — Monitors 2016–02–08 18 / 19 Summary Summary Semaphore concept has some limitations Monitor is a better choice for condition synchronisation A monitor has a set of data to be shared among threads and synchronised methods to be used by threads Illustrated the application of monitor for the Producer and Consumer problem gtl1–R599 W3L3 — Monitors 2016–02–08 19 / 19 CO2017 — Week 4 L1 — Memory Management Dr Gilbert Laycock (gtl1) 2016–02–07 gtl1–R588 W4L1 — Memory mangement 2016–02–07 1 / 19 Overview Context Operating systems OS overview Processes and scheduling Processes/threads and concurrent programming Memory management File systems Networking ISO OSI 7 layer model (network) Application programming gtl1–R588 W4L1 — Memory mangement 2016–02–07 2 / 19 Overview Lecture Overview 1 Memory management 2 Swapping gtl1–R588 W4L1 — Memory mangement 2016–02–07 3 / 19 Memory Managment Aims of Memory Management To provide memory for processes running concurrently To provide satisfactory performance To protect processes’ memory from each other But to allow sharing of memory where desired To make the addressing of memory transparent gtl1–R588 W4L1 — Memory mangement 2016–02–07 4 / 19 Memory Managment Memory Hierarchy Memory Hierarchy gtl1–R588 W4L1 — Memory mangement 2016–02–07 5 / 19 Memory Managment Memory Hierarchy Memory Hierarchy Registers (in CPU) (10s of bytes) (about 1 CPU cycle to access) Cache levels 1, 2, 3 (near processor) (a few Mb) (many 10s or 100s of Gb/s) “Main” (volatile) RAM and (non-volatile) ROM (outside processor) (multiple Gb) (about 10Gb/s) Non-volatile storage — disk, SSD (100s or 1000s of Gb) (10s or 100s of Mb/s) Off-line storage — tape, DVD, bluray, cloud storage (1Mb/s to 100s Mb/s in ideal conditions) gtl1–R588 W4L1 — Memory mangement 2016–02–07 6 / 19 Memory Managment Memory Hierarchy Memory Latency in human terms Multiply the access times by 1 billion to help get a sense of scale: Registers less than a heartbeat (0.5s) Cache L1 (a heartbeat), L2 (5s) “Main” (volatile) RAM into 100s of seconds (more than a minute) Non-volatile storage — fast SSD seek about 1.7 days; normal HDD about 16.5 weeks Off-line storage — transfer to cloud storage on a different continent about 5 years gtl1–R588 W4L1 — Memory mangement 2016–02–07 7 / 19 Memory Managment What is in “on-line” memory? Memory contents System ROMs (BIOS, device drivers, OS) System code in RAM (OS) System state in RAM (OS) Process memory: Process code Process data Process stack Organised across physical memory in distinct sections gtl1–R588 W4L1 — Memory mangement 2016–02–07 8 / 19 Direct memory model Single process Single process Only one process running and in memory It can address the entire memory space Code is written with absolute addresses When process completes, replace it in memory with a new process (via direct user command, batch control language etc.) gtl1–R588 W4L1 — Memory mangement 2016–02–07 9 / 19 Direct memory model Single process Single Process System Process A OS Free space gtl1–R588 W4L1 — Memory mangement 2016–02–07 10 / 19 Direct memory model Single process Single Process System OS Free space Process B gtl1–R588 W4L1 — Memory mangement 2016–02–07 11 / 19 Direct memory model Multiple processes More than one process in memory Most systems have enough memory for more than one process’s code and data to be stored So, load each process into in consecutive areas Problem: code with absolute addresses will fail Use static relocation to rewrite code as it is loaded; or Use abstract address space for each process with a fixed base address set when process is loaded gtl1–R588 W4L1 — Memory mangement 2016–02–07 12 / 19 Direct memory model Multiple processes Multiple processes in memory Process A OS Process B gtl1–R588 W4L1 — Memory mangement 2016–02–07 13 / 19 Direct memory model Memory addressability Memory Addressability Memory space is limited by the width of the address bus. A 32-bit bus can reference 232 = 4.3Gbytes A 64-bit bus can theoretically reference 264 = 16Exabytes Machine instructions cannot directly access the whole memory space. The solution is to use register(s) to hold a base address The address part of machine instructions is used as an offset from the base address. E.g, code base address: 1,000; instruction: JMP 123; effective address jumped to: 1,000 + 123 = 1,123 gtl1–R588 W4L1 — Memory mangement 2016–02–07 14 / 19 Direct memory model Memory allocation to multiple processes Memory allocation Each process is allocated the memory space it needs Processes are loaded into contiguous memory until it is full When a process terminates, its space is freed This may introduce “holes” — external fragmentation With luck, adjacent fragments can be coalesced A, B & C A & B terminate Coalesced system Operating Process A Process B Process C system Operating Process C system Operating Process C Two Holes Coalesced gtl1–R588 W4L1 — Memory mangement 2016–02–07 15 / 19 Swapping Concepts Swapping Note that with a scheduler, we can multi-process on a system with direct memory access Everying is fine until we want to run more processes than will fit in memory at once Simple solution is to employ swapping Memory full and want to run another process? Pick a process currently in-memory and copy it out to disk Use the newly free space to load another process gtl1–R588 W4L1 — Memory mangement 2016–02–07 16 / 19 Swapping Implementation Swapping implementation Need data structure(s) to record the current state of memory: Where each process’s memory starts and ends (allocated space); where the “holes” are (un-allocated) Could use a bitmap Could use a linked list (or several) Need a strategy to choose where to locate a new process’s memory gtl1–R588 W4L1 — Memory mangement 2016–02–07 17 / 19 Swapping Implementation First fit Look for the first un-allocated space that is big enough Best fit Look through all un-allocated space and choose the one that is the best fit Worst fit Look through all un-allocated space and choose the one that is the largest Need to optimise the data structures for the strategy, but there is always an overhead in maintaining them. gtl1–R588 W4L1 — Memory mangement 2016–02–07 18 / 19 Summary Summary Need to manage memory of a machine Simplest approach is direct memory addressing By using a base address and offset can load multiple processes at the same time Swapping is a strategy for handling over-allocation of memory gtl1–R588 W4L1 — Memory mangement 2016–02–07 19 / 19 CO2017 — Week 4 L2 — Memory Management Dr Gilbert Laycock (gtl1) 2016–02–16 gtl1–R643 W4L2 — Memory mangement 2016–02–16 1 / 24 Overview Context/Overview Direct Memory management Swapping in Direct Memory model Virtual Memory vs direct memory swapping Page table implementation Page replacement algorithms gtl1–R643 W4L2 — Memory mangement 2016–02–16 2 / 24 Memory Management Aims of Memory Management To make the addressing of memory transparent To allow multiple processes to share physical system memory But keep each process’s logical address space separate And to allow sharing of memory where desired With acceptable level of performance gtl1–R643 W4L2 — Memory mangement 2016–02–16 3 / 24 Virtual Memory Concepts Limitations of direct addressing & swapping Modern interactive applications can use 100s of Mb or more Swapping whole process’s memory in/out to disk would take unacceptable amount of time Individual process might require more memory than there is physically available Modern Virtual Memory (VM) and hardware support for paging address these issues gtl1–R643 W4L2 — Memory mangement 2016–02–16 4 / 24 Virtual Memory Concepts Virtual memory The memory “seen” by user space is not real physical memory The OS provides a virtual address space for each process A virtual address is translated to the real address by the Memory Management Unit (MMU). The translation of addresses has to be very fast, therefore the MMU is implemented in hardware. gtl1–R643 W4L2 — Memory mangement 2016–02–16 5 / 24 Virtual Memory Paging Paging Virtual memory is partitioned into chunks of equal size, called pages Page size is much smaller than the total address space needed for a process Virtual memory pages that are in use are stored in RAM (called page frames); the rest of the pages are stored on disc When a process accesses a page that is not in physical memory a page fault occurs. Page fault: an old page frame in RAM needs to be swapped with the new page being accessed. gtl1–R643 W4L2 — Memory mangement 2016–02–16 6 / 24 Virtual Memory Page table Relationship between virtual frames and physical memory 36 X 32 3 28 X 24 4 20 1 5 20 16 X 4 16 12 X 3 12 08 0 2 08 04 2 1 04 00 5 0 00 Then access page 16 36 X 32 X 28 X 24 4 20 1 5 20 16 3 4 16 12 X 3 12 08 0 2 08 04 2 1 04 00 5 0 00 gtl1–R643 W4L2 — Memory mangement 2016–02–16 7 / 24 Virtual Memory Page table Paging-related implementation issues Data structure(s) to support page table Choosing the page size Choosing the page replacement algorithm gtl1–R643 W4L2 — Memory mangement 2016–02–16 8 / 24 Virtual Memory Page table Page table structure Much of this structure is implemented in hardware Example attributes of a page table entry: Present/absent: true if and only if this page is currently in physical memory Page frame number: The physical page frame this page is stored in (if any) Modified: Has the data been modified since it was read from disk (AKA dirty bit)? Referenced: Has the data been referenced (recently)? Protection: Is the data read/write/executable ? gtl1–R643 W4L2 — Memory mangement 2016–02–16 9 / 24 Virtual Memory Page table Optimisations Modern systems have huge amounts of RAM: the page table is itself a large data structure that can be slow to manipulate Modern hardware uses translation lookaside buffers to cache the most commonly used page table entries With large amounts of RAM, may need to have multi-level page tables RISC processors typically have simpler MMUs gtl1–R643 W4L2 — Memory mangement 2016–02–16 10 / 24 Virtual Memory Page table Page size Too large — page swapping will take a long time Too small — page swapping will be repeated often Common page sizes are 4–8K gtl1–R643 W4L2 — Memory mangement 2016–02–16 11 / 24 Virtual Memory Page table Summary 1 Virtual memory Paging Page table implementation gtl1–R643 W4L2 — Memory mangement 2016–02–16 12 / 24 Page replacement algorithms Page replacement algorithm Page replacement happens when a page fault occurs MMU is asked for a page where the present bit is false Need to choose which page to swap out to disk Ideally want to choose the page that will not be needed for the longest possible period If there are several, look for clean (un-modified) pages that will not need to be written to disk Poor page replacement can result in thrashing — the machine spends more time dealing with page faults then real work gtl1–R643 W4L2 — Memory mangement 2016–02–16 13 / 24 Page replacement algorithms Optimal (clairvoyant) page replacement Clairvoyant page replacement algorithm Input needed: for each page frame, the next instruction that will reference this frame Find the page that will next be referenced the furthest in the future and swap it to disk Impossible to implement in a real operating system due to the inherent impossibility of predicting future behaviour gtl1–R643 W4L2 — Memory mangement 2016–02–16 14 / 24 Page replacement algorithms Optimal (clairvoyant) page replacement The optimal algorithm is nevertheless useful Suppose you have a real page replacement algorithm and want to test its performance. This is done by comparing it against the optimal algorithm. Run the same process twice (or more) On the first run, collect the timings of all the page references so that they can be used when analysing the performance of the replacement algorithm gtl1–R643 W4L2 — Memory mangement 2016–02–16 15 / 24 Page replacement algorithms Optimal (clairvoyant) page replacement Page replacement algorithms Not recently used FIFO page replacement Clock page replacement Least recently used (LRU) Working set replacement WSClock page replacement gtl1–R643 W4L2 — Memory mangement 2016–02–16 16 / 24 Page replacement algorithms Not recently used Not Recently Used algorithm Each page frame has a referenced bit false if the frame has not yet been referenced; or true if the frame has been referenced The page to be swapped is selected among those that have not been referenced (0 bit) Eventually all the frames have a 1 bit When this happens, all bits are reset to 0 Obvious disadvantages: crude selection and the need to reset the bits gtl1–R643 W4L2 — Memory mangement 2016–02–16 17 / 24 Page replacement algorithms FIFO page replacement FIFO page replacement Maintain a FIFO queue as pages are added to physical memory When a page fault occurs, simply swap out the page at the head of the queue Simple and efficient to implement But likely to swap out pages that are actively being used Can check if the head page has been referenced; if so, give it a second chance (put it on the back of the queue) (“FIFO with 2nd chance”) gtl1–R643 W4L2 — Memory mangement 2016–02–16 18 / 24 Page replacement algorithms Clock page replacement Clock page replacement Maintain a circular list of all page frames (the clock) Maintain a pointer to one of the pages in the clock (the hand of the clock) On a page fault, start at the hand and look for a page to evict 1 if referenced is false: evict this page 2 if referenced is true: reset referenced and advance the clock hand and try again 3 Advance the clock hand gtl1–R643 W4L2 — Memory mangement 2016–02–16 19 / 24 Page replacement algorithms Least recently used (LRU) Least Recently Used (LRU) algorithm The system maintains a 64 bit counter that is incremented with each CPU instruction. Each page table entry records the counter value when that page is referenced The frame associated with the smallest (oldest) value of the register is the one that is swapped Could be implemented in hardware (but rarely is) gtl1–R643 W4L2 — Memory mangement 2016–02–16 20 / 24 Page replacement algorithms Working set replacement Working set replacement Observe that most processes exhibit locality of reference — concentrate on just a few pages The set currently required is the working set of pages — try to keep the working set in memory For active pages record time of last use When a page fault occurs, consider all the page frames and choose the one based on referenced, dirty and time of last use Working set is not implemented directly, but is a concept that informs other more practical techniques. gtl1–R643 W4L2 — Memory mangement 2016–02–16 21 / 24 Page replacement algorithms WSClock replacement WSClock replacement Maintain circular list of page frames as they are loaded (cf. the clock replacement approach), but include the time of last use Define Tau (τ) as a limit beyond which pages are too old to count as in the working set Instead of searching whole page table, just search the clock for pages that are older than τ . Can be (and is) efficiently implemented in practice. In practice, also consider whether page is dirty (and always schedule a write of dirty pages), and prefer to swap clean pages. gtl1–R643 W4L2 — Memory mangement 2016–02–16 22 / 24 Real-life VM and page replacement Virtual memory in practice Real modern systems combine VM management and page replacement in a general purpose memory allocator that is also used by the file system. Real systems use LRU/clock hybrid approaches, which aim to dynamically capture the working-set and keep it in memory Pre-loading and anticipatory paging allow pages to be loaded before a page fault occurs — based on broad analysis of system usage Many of the same issues occur up and down the memory hierarchy, and in other software systems — e.g. between main memory and processor cache; when populating web server caches. gtl1–R643 W4L2 — Memory mangement 2016–02–16 23 / 24 Summary Summary Virtual memory Paging Page table implementation Page replacement algorithms gtl1–R643 W4L2 — Memory mangement 2016–02–16 24 / 24 CO2017 — Week 5L1 — File systems Dr Gilbert Laycock (gtl1) 2016–02–21 gtl1–R671 W5L1 — File systems 2016–02–21 1 / 37 Overview Context Operating systems OS overview Processes and scheduling Memory management File systems I/O and buffering Networking ISO OSI 7 layer model (network) Application programming gtl1–R671 W5L1 — File systems 2016–02–21 2 / 37 Overview Lecture Overview Objectives of file management system Concepts of file, directory General disk layout Consider file allocation methods Implementing directories gtl1–R671 W5L1 — File systems 2016–02–21 3 / 37 Objectives of the file system Objectives of File System Allow creation and deletion (etc.) of files Allow access to files by symbolic names Allow the sharing of files where required, but protect files against unauthorised access (access control) Perform automatic management of secondary storage, allocating files to physical blocks Protect files against system failure gtl1–R671 W5L1 — File systems 2016–02–21 4 / 37 Files Concept of File A uniform logical view of information storage A named collection of related information Recorded on secondary storage — persistant Allows us to store large volumes of data Allows multiple processes to access the data concurrently gtl1–R671 W5L1 — File systems 2016–02–21 5 / 37 Files File names File Naming File naming conventions are OS specific, but follow common patterns MS-DOS and Windows 3.1: “eight plus three” character filename plus extension Windows 95/NT: up to 255 characters UNIX: typical filename length was 14 but modern versions allows up to 255 characters Restrictions as to the characters that can be used Some OSs distinguish between upper and lower case To MS-DOS, ABC, abc, and AbC are indistinguishable names, while UNIX sees them as different gtl1–R671 W5L1 — File systems 2016–02–21 6 / 37 Files File extension File Extensions Filename has two parts separated by a full stop The part before the full stop is the basename The part after the full stop is the extension MS-DOS: extension is limited to three characters UNIX and Windows 95/NT allow longer extensions Can be used to tell the user or OS what type of data the file contains Historically associates a file with a certain application (cf. MIME type) UNIX: can have multiple extensions on one file, e.g, file.tar.gz gtl1–R671 W5L1 — File systems 2016–02–21 7 / 37 Files File extension MSDOS/Win File Extensions Extension File Content BIN Binary file C C source program file CPP C++ source program file DLL Dynamic link library DOC Microsoft Word file EXE Executable file HLP Help file TXT General text file XLS Microsoft Excel file PDF Portable Document Format file gtl1–R671 W5L1 — File systems 2016–02–21 8 / 37 Files Real file type Actual file type Using file extension to determine file type is fragile (easy to trick) *NIX and MacOSX use a more sophisticated approach file command looks into a file and tries to work out what type it is Uses (amongst other methods) magic number database to identify files from the first “few” bytes of data gtl1–R671 W5L1 — File systems 2016–02–21 9 / 37 Files File Types File Types Most OSs support several types of files Regular: Ordinary files, e.g, program, text and data Directory: “File” containing references to other files Character Special: Not true files but directory entries which refer to character devices, e.g, printer Block Special: Not true files but directory entries which refer to block devices, e.g, disk UNIX supports all of these while Windows supports the first two gtl1–R671 W5L1 — File systems 2016–02–21 10 / 37 Files File attributes File Attributes Each file has a set of attributes associated with it, e.g: Attribute Description Archive flag Bit field: has the file been archived? Creation date/time Date and Time file was created Creator User ID of the person creating the file Hidden flag Bit field : Is the file a hidden file? Last accessed date/time Date and time file was last accessed Owner The ID of the current owner Password Password required to access the file Protection Access rights to the file Read-only Bit field: Is the file read only? Size in bytes How large is the file? System flag Bit field: Is the file a system file? gtl1–R671 W5L1 — File systems 2016–02–21 11 / 37 Files File structure File Structure and Access File structure: A file can be stored as A sequence of bytes. It is up to the program that accesses the file to interpret the byte sequence A sequence of fixed-length structured records A tree of variable length records. Each has a key field to be used for record retrieval File access Sequential access: good for magnetic tapes Random access: good for disks gtl1–R671 W5L1 — File systems 2016–02–21 12 / 37 Directories Directories Most file systems allow files to be grouped together into directories, giving a more logical organisation. Allow operations to be performed on a group of files which have something in common. E.g, copy the files or set one of their attributes Allow different files to have the same filename as long as they are in different directories. Each directory is managed via a special directory file, which contains a file descriptor for each constituent file A file descriptor contains attributes of a file gtl1–R671 W5L1 — File systems 2016–02–21 13 / 37 Directories Directory structure Directory Structure One-level system: one root directory contains all files Two-level system: e.g, giving each user a private directory Hierarchical system: a tree of directories Root directory A A B C Files User directory A A A B B C CC C Root directory User directory User subdirectories C C C C C C B B A A B B C C C B Root directory User file gtl1–R671 W5L1 — File systems 2016–02–21 14 / 37 Directories Path Name Path Name Absolute path name: relative to the root directory “/” in UNIX; or “\” in MS-DOS and Windows /CO2017/Demos/Buffer.java => UNIX
OR

C:\CO2017\Demos\Buffer.java => MS-DOS/Windows

Relative path name: relative to current directory or present
working directory (PWD in UNIX)

If PWD is C:\CO2017, the relative path name would be

Demos\Buffer.java

gtl1–R671 W5L1 — File systems 2016–02–21 15 / 37

Operations

File and Directory Operations

OS provides different services for different users

Interactive facilities for on-line users

Create a file or directory
Delete a file or an empty directory
Copy a file or directory
Rename a file or directory
Display a file or list the content of a directory

Services for programmers via high level languages

Open: make a file ready for processing
Close: make a file unavailable for processing
Read: input data from a file
Write: output data to a file
Seek: select a position in a file for data transfer

gtl1–R671 W5L1 — File systems 2016–02–21 16 / 37

File system layout

File System Layout (MBR)

A disk is divided into partitions/volumes, each holds an independent
file system

Sector 0 is the Master Boot Record (MBR), contains system boot
code and is used to record the partitions (block/sector range, which one
to boot)

Each partition has a boot and a super block, containing info about that
file system

Entire disk

Disk partitionPartition table

Files and directoriesRoot dirI-nodesSuper block Free space mgmtBoot block

MBR

gtl1–R671 W5L1 — File systems 2016–02–21 17 / 37

File system layout Contiguous allocation

Contiguous Allocation

Disks (partitions) are split into blocks of a fixed size, e.g, 1KB, 4K

Files are stored in blocks in a manner dependent on the file-system type

File Descriptor is a data structure for finding the first block of a file

Contiguous allocation assigns contiguous blocks to a file

File A
(4 blocks)

File C
(6 blocks)

File B
(3 blocks)

File D
(5 blocks)

File F
(6 blocks)

File E
(12 blocks)

File G
(3 blocks)

(a)

(File A)

(File C)

File B 5 Free blocks 6 Free blocks

(File E)

(File G)

(b)

gtl1–R671 W5L1 — File systems 2016–02–21 18 / 37

File system layout Contiguous allocation

Contiguous Allocation (Cont’d)

Advantages

Simple to implement: just need to store the first block address and the
length
The performance of such an implementation is good. The read/write
heads have to move very little, if at all
Resilient to disk faults: damage to a single block results in only
localised loss of data
Allows easy random access.

Disadvantages

Need to “guess” the size of the file when it is first created
Fragmentation: as files are deleted, holes appear; can be overcome by
compaction, but this is expensive

gtl1–R671 W5L1 — File systems 2016–02–21 19 / 37

File system layout Linked list allocation

Linked List Allocation

Store a file as a linked list of blocks

Need only to store the first block address in the file descriptor

Each block contains some data and a pointer to the next block.
The final block contains a null pointer

File A

Physical
block

Physical
block

4

0

7 2 10 12

File
block

0

File
block

1

File
block

2

File
block

3

File
block

4

File B

0

6 3 11 14

File
block

0

File
block

1

File
block

2

File
block

3

gtl1–R671 W5L1 — File systems 2016–02–21 20 / 37

File system layout Linked list allocation

Linked List Allocation (Cont’d)

Advantages

Every block can be used
No space is lost due to disk fragmentation, except for internal
fragmentation in the last block
The file size does not have to be known beforehand.

Disadvantages

Random access is very slow
More overhead: space is used in each block by the pointer
Reliability could be a problem—can be alleviated by adding reverse links

gtl1–R671 W5L1 — File systems 2016–02–21 21 / 37

File system layout File allocation table (FAT)

Linked List implemented as File Allocation Table

Store the pointers in a file allocation table (FAT) in memory

The pointer in a file descriptor points to the location in the FAT
representing its first block

Physical
block

File A starts here

File B starts here

Unused block

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

10

11

7

3

2

12

14

-1

-1

gtl1–R671 W5L1 — File systems 2016–02–21 22 / 37

File system layout File allocation table (FAT)

Linked List with File Allocation Table (Cont’d)

Advantages

Does not waste space in each block
Random access is much easier as FAT is in memory

Disadvantages

FAT may be too large to hold in main memory, so has to be held on
secondary storage
May require several disk accesses to read all relevant FAT entries
Damage to FAT can cause serious data loss. (So: store several FAT
copies in different areas of the disk)

gtl1–R671 W5L1 — File systems 2016–02–21 23 / 37

File system layout inodes

inodes in UNIX

Each file has an inode (index?-node) listing all the attributes for the file

The inode also contains a number of direct pointers to disk blocks.
Typically there are 12 direct pointers

In addition, there are three indirect pointers. These pointers point to
further data structures which eventually lead to a disk block address

The first of these pointers is a single level of indirection, the next
pointer is a double indirect pointer and the third is a triple indirect
pointer

gtl1–R671 W5L1 — File systems 2016–02–21 24 / 37

File system layout inodes

inodes in UNIX (Cont’d)

I-node

Attributes

D
is

k
a

d
d
re

s
s
e
s

Single
indirect
block

Double
indirect
block

Triple
indirect
block

Addresses of
data blocks

gtl1–R671 W5L1 — File systems 2016–02–21 25 / 37

File system layout Implementing directories

Implementing Directories

The path name is used to locate a directory entry

A directory entry contains all the information needed

For contiguous and linked list allocations, it contains the first disk
block address
For an inode implementation, it contains the inode number
A directory entry may also contain some attributes of the files (or
a pointer to them)

The directory entry provides a mapping from a filename to the disk
blocks that contain the data

gtl1–R671 W5L1 — File systems 2016–02–21 26 / 37

File system layout Implementing directories

Implementing Directories (Cont’d)

MS-DOS: a directory entry is 32 bytes long

��

Size

Extension Attributes Reserved Date First
block

number

Bytes 8 3 1 10 2

File name

Time

2 2 4

UNIX: a directory entry has an inode no. and filename

All its attributes are stored in the inode
OS maintains a cache of directory and file inodes, so it is generally quick
to locate a particular inode once you know its number

Bytes 2 14

File name

I-node
number

gtl1–R671 W5L1 — File systems 2016–02–21 27 / 37

File system layout Locating a UNIX file

Locating a UNIX File

Given an absolute path name /usr/ast/mbox

The system locates the root directory inode (always inode 2)
Then look up the first path component (usr) in the root directory, to
find its inode number
Use the inode number for /usr, to access its inode data; then locate the
inode number for /usr/ast, etc.
This process is repeated until the actual file is located

For relative path names start from the current working directory

gtl1–R671 W5L1 — File systems 2016–02–21 28 / 37

File system layout Locating a UNIX file

Locating a UNIX File (Cont’d)

Root directory
I-node 6
is for /usr

Block 132
is /usr

directory

I-node 26
is for

/usr/ast

Block 406
is /usr/ast
directory

Looking up
usr yields
i-node 6

I-node 6
says that
/usr is in

block 132

/usr/ast
is i-node

26

/usr/ast/mbox
is i-node

60

I-node 26
says that

/usr/ast is in
block 406

1

1

4

7

14

9

6

8

.

..

bin

dev

lib

etc

usr

tmp

6

1

19

30

51

26

45

dick

erik

jim

ast

bal

26

6

64

92

60

81

17

grants

books

mbox

minix

src

Mode
size

times

132

Mode
size

times

406

gtl1–R671 W5L1 — File systems 2016–02–21 29 / 37

Management and resilience Real world issues

Real world issues

Power failure and other interruptions

Managing multiple physical discs

Small systems: multiple mount points, drives, partitions
But want logical file system to span multiple real drives
Want to deal transparently with physical failures

gtl1–R671 W5L1 — File systems 2016–02–21 30 / 37

Management and resilience Journalling

Journalling file system

A “single” file operation might involve multiple actual writes
to the disk

Potential to leave files and directories in invalid state after a
failure; time consuming repairs are then needed

A journaling file system uses special disk area to make record of
all changes just before they are made

In the event of failure, replay the journal to bring it back into a
consistent state

gtl1–R671 W5L1 — File systems 2016–02–21 31 / 37

Management and resilience Battery Back Up

Battery Back Up

More expensive disk system come with BBU

Small(ish) amount of dedicated cache RAM powered by battery

Disk writes go to cache first

Battery unit has enough power to either finish the write or keep
the data “live” until power is restored.

gtl1–R671 W5L1 — File systems 2016–02–21 32 / 37

Management and resilience Logical Volumes

Drives, mount points

In Windows, multiple drives appear with distinct drive letters:
C:, etc.

Attach a new drive and it gets another letter

Unix style systems present a single uniform file system with a
single root.

Other file systems are mounted at arbitrary points

What if a drive fills up? Or one drive fails?

gtl1–R671 W5L1 — File systems 2016–02–21 33 / 37

Management and resilience Logical Volumes

Logical Volume Manager

Add another layer of abstraction: Logical Volume Manager

Create arbitrary mapping between physical drives (or parts of
drives) and the logical drives seen by the OS

Can resize, extend, replace physical drives without altering the
logical view

Examples are lvm, zfs, btrfs

gtl1–R671 W5L1 — File systems 2016–02–21 34 / 37

Management and resilience RAID

RAID

Redundant Array of Inexpensive Discs (RAID)

Spread file system accross multiple physical discs

Several levels of RAID with different performance
characteristics.

RAID0 Striping of data over multiple drives to improve
performance; no space overhead, so total size s × n

gtl1–R671 W5L1 — File systems 2016–02–21 35 / 37

Management and resilience RAID

RAID

RAID1 Mirroring of data over multiple
drives to improve resilience (and
maybe read speed); total size is s

RAID5

Block-level striping with distrib-
uted parity; can survive failure of
any single drive; one drive space
overhead, total size is (n − 1) × s

gtl1–R671 W5L1 — File systems 2016–02–21 36 / 37

Summary

Summary

File is logical representation of data on 2nd-ary storage

Has various attributes

Directory is a special file that contains other files

Implementation needs to be efficient with space usage and
speed of retrieval

Need to manage complex failure prone systems

gtl1–R671 W5L1 — File systems 2016–02–21 37 / 37

CO2017 — Week 5L2 — Deadlock

Dr Gilbert Laycock (gtl1)

2016–02–21

gtl1–R668 W5L2 — Deadlock 2016–02–21 1 / 31

Overview

Context

Operating systems

OS overview
Processes and scheduling
Memory management
File systems

Networking

ISO OSI 7 layer model
(network) Application programming

gtl1–R668 W5L2 — Deadlock 2016–02–21 2 / 31

Overview

Overview

Definition, examples of deadlocks

Methods of handling deadlocks

Processes and resources

Single resource deadlock detection

Banker’s algorithm

Prevention of deadlocks.

Livelocks and starvation

gtl1–R668 W5L2 — Deadlock 2016–02–21 3 / 31

Definition

Definition of deadlock

Deadlock: a situation when one or more processes get stuck

The simplest such program is just an infinite loop
while(true) {;}

In multi-process systems concern is with deadlocks involving two
or more processes where each process is waiting for an
event caused by another process.

gtl1–R668 W5L2 — Deadlock 2016–02–21 4 / 31

Definition Examples

Examples of deadlocks

A real world example: gridlock/circular traffic jam

A programming example: imagine two programs sharing two
boolean variables var1 and var2

Initially both var1 and var2 are false
while(!var1) {;}
var2 = true;

while(!var2) {;}
var1 = true;

These two threads easily get into a deadlock.

gtl1–R668 W5L2 — Deadlock 2016–02–21 5 / 31

Definition Examples

A more meaningful example: scenario

A program (thread) running alone does not deadlock

But when two programs run together they can deadlock.

E.g. two boolean variables shared between processes; resource1
and resource2 where true indicates the resource is in use.

Initialise both variables to false

gtl1–R668 W5L2 — Deadlock 2016–02–21 6 / 31

Definition Examples

More meaningful example: code

Program1:

while (resource1) wait(); // guard1
resource1 = true; // take resource1
while (resource2) wait(); // guard2
resource2 = true; // take resource2
… // use resource1 and resource2
resource1 = false; resource2 = false

Program2 is the same with resource1 and resource2 reversed

gtl1–R668 W5L2 — Deadlock 2016–02–21 7 / 31

Definition Examples

More meaningful example: analysis

Program1 and Program2 run without deadlocks if they run
sequentially

But, when run concurrently, if Program1 is waiting on
resource2 and Program2 manages to aquire resource2 they
get into a deadlock.

gtl1–R668 W5L2 — Deadlock 2016–02–21 8 / 31

Handling deadlocks

Four ways to handle deadlocks

Ignore

Detect and rectify

Avoid (where possible)

Prevent (in all cases)

gtl1–R668 W5L2 — Deadlock 2016–02–21 9 / 31

Handling deadlocks Deadlock detection

Deadlock detection

OS runs special deadlock detection process(es)

When a deadlock has been detected, action is taken to rectify
the problem

gtl1–R668 W5L2 — Deadlock 2016–02–21 10 / 31

Handling deadlocks Rectify detected deadlock

Ways to rectify detected deadlocks

Preemption: pick a process that is holding a resource resulting in
deadlock; give the resource to a different process.
E.g. if memory is a resource, VM system can swap a
page from one process to another
Drawback: some resources are non-preemptable

Rollback: Check-point all processes periodically. When deadlock
is detected roll back to a previous check point and
proceed with different allocation of resources

Kill processes: might be done manually as the system cannot decide
which process to kill; but can be automated, e.g, Linux
OOM killer.

gtl1–R668 W5L2 — Deadlock 2016–02–21 11 / 31

Handling deadlocks Deadlock avoidance

Deadlock avoidance

Use a scheduling policy that avoids deadlocks

Scheduler considers the resources that a process requires, and
does not allow it to start unless all resources will be available

Requires knowledge about future operations of processes,
which is hard to achieve

gtl1–R668 W5L2 — Deadlock 2016–02–21 12 / 31

Handling deadlocks Deadlock prevention

Deadlock prevention

Design system so that deadlocks cannot in principle occur

This will impose strict requirements on programs running on
the system; e.g. a process cannot start unless all possible
resources are known to be available.

E.g. Program1 and Program2 would be impossible to run
together under a deadlock prevention system

Difference from deadlock avoidance: under avoidance
deadlocks are possible in principle but the system tries to
foresee and avoid them.

gtl1–R668 W5L2 — Deadlock 2016–02–21 13 / 31

Handling deadlocks Real systems

Dealing with deadlocks in real systems

A potential problem has to be explicitly dealt with only if
the cost of letting it happen significantly outweighs the
cost of rectifying it

Deadlocks mostly do little harm to normal users of single
user and small multi-user systems
So consumer systems ignore most potential deadlocks

But for real-time or safety critical systems (medical
equipment, avionics, etc.) or sufficiently large-scale systems
(e.g. banking salary computation) deadlock would be
devastating

gtl1–R668 W5L2 — Deadlock 2016–02–21 14 / 31

Processes and resources

Processes and resources

Considering deadlocks involves two main notions: process and
resource.

Resources are very broadly understood: block of memory,
printer, scanner, file on disk etc.

Processes can hold and release resources as execution
proceeds

Deadlock occurs if there is a set of processes where each
wants to use a resource currently being held by another
process.

gtl1–R668 W5L2 — Deadlock 2016–02–21 15 / 31

Processes and resources Single resource deadlock detection

Detecting a deadlock with a single resource of each

type

Single resource of each type: e.g. one printer, one disc, one
scanner, etc.

Consider state of the processes at a given moment and
determine if there is a deadlock

Needs

The list of processes
The list of resources
The relationship between the given process and the given
resource: holding, requesting, neither of them.

gtl1–R668 W5L2 — Deadlock 2016–02–21 16 / 31

Processes and resources Single resource deadlock detection

The deadlock detection algorithm.

Represent the state of processes and resources with a graph:

Nodes correspond to processes and resources
Edges:

From resource R to process P if P holds R
From process P to resource R if P requests R

The system is in deadlock if and only if the graph has a
directed cycle.

gtl1–R668 W5L2 — Deadlock 2016–02–21 17 / 31

Processes and resources Single resource deadlock detection

Single resource deadlock example

P1

RA RB

P2

gtl1–R668 W5L2 — Deadlock 2016–02–21 18 / 31

Processes and resources Multiple resource deadlock detection

Deadlock detection with multiple resources of each

type

For multiple resource situation, use matrices:

Matrix of resources that exist in the system

Matrix of resources in use

Matrix of available resources

Matrix of processes holding resources

Matrix of processes requesting resources

gtl1–R668 W5L2 — Deadlock 2016–02–21 19 / 31

Processes and resources Multiple resource deadlock detection

Resource matrices

Each matrix is an array with one entry corresponding to each
type of resource.

The existing resource matrix specifies the number of units
of each resource currently in existance in the system

The in use matrix specifies the number of resources of each
type currently being held by processes

The available resources matrix specifies the number of
resources currently not in use: i.e. the “exists” matrix minus
the “in use” one.

gtl1–R668 W5L2 — Deadlock 2016–02–21 20 / 31

Processes and resources Multiple resource deadlock detection

Example of resource matrices

Existing/total
A B C D

4 2 4 3

In use/held
Held A B C D

P1 0 0 3 1
P2 0 1 0 0
P3 4 0 0 1
P4 0 0 0 1

Requested
Req A B C D

P1 2 1 0 1
P2 2 2 0 1
P3 0 1 1 0
P4 3 2 1 2

Available
A B C D

0 1 1 0

gtl1–R668 W5L2 — Deadlock 2016–02–21 21 / 31

Processes and resources Multiple resource deadlock detection

Process matrices

Matrix of processes holding resources is a 2-dimensional
array where each row corresponds to a process and each
column corresponds to a resource

The cell at the intersection of row of process P and resource R
specifies how many units of resource R are currently being held
by process P

Similar matrix of processes requesting resources — the
respective cell is the number of resource R being requested by
process P.

gtl1–R668 W5L2 — Deadlock 2016–02–21 22 / 31

Processes and resources Multiple resource deadlock detection

Comparison of rows and arrays

Let A and B be two one-dimensional arrays. Let us say that A ≤ B
if each entry of A is smaller than or equal to the respective entry
of B

If the process request matrix has no row that is smaller than
or equal to the available resource matrix then the processes
are in deadlock: none of them will ever get a full allocation

Otherwise; no deadlock now — but what about the future?

Assume: a process getting its requested resources will
eventually finish and return all its resources to the system

gtl1–R668 W5L2 — Deadlock 2016–02–21 23 / 31

Banker’s algorithm

The algorithm (Banker’s algorithm)

1 Initially all the processes are unmarked

2 If all the processes are marked, return “NO DEADLOCK”

3 If there is no unmarked process whose row of requested
resources is smaller than or equal to the array of available
resources, return “DEADLOCK”

4 Let P be an unmarked process whose requested resources are
smaller than or equal to the available resources.

5 Add P’s row of held resources to the row of available resources.

6 Mark P.

7 Goto Step 2.

gtl1–R668 W5L2 — Deadlock 2016–02–21 24 / 31

Banker’s algorithm Deadlock avoidance

Deadlock avoidance algorithm

The process request matrix for each process P must hold the
total number of resources R that will be requested in order for P
to complete

The current state is considered safe if there is a scheduling
policy avoiding deadlocks even if each process asks for the
maximum possible number of resource units at once.

gtl1–R668 W5L2 — Deadlock 2016–02–21 25 / 31

Banker’s algorithm Deadlock avoidance

Use Banker’s algorithm for deadlock avoidance

For each resource request, the system analyses the safeness
of the state occurring if the requests were granted

If the resulting state is not safe then the request is either
denied or delayed

gtl1–R668 W5L2 — Deadlock 2016–02–21 26 / 31

Deadlock Prevention

Four conditions for deadlock to occur

Mutual exclusion: Each resource can be held by at most one process

Hold and wait: Processes currently holding resources may request
more resources

No preemption: Resources granted cannot be forcibly taken away
before the process has released them.

Circular wait: There is a circular chain of processes waiting for a
resource held by the next member of the chain.

Consider prevention of Hold and Wait and Circular Chain in order
to prevent deadlock

gtl1–R668 W5L2 — Deadlock 2016–02–21 27 / 31

Deadlock Prevention Eliminate Hold-and-Wait

Elimination of the Hold-and-Wait condition

Each program asks for all the resources it will require at the
beginning of its run.

Usually only possible in batch oriented systems: user requests
are unpredictable in interactive systems

gtl1–R668 W5L2 — Deadlock 2016–02–21 28 / 31

Deadlock Prevention Eliminate Circular Wait

Elimination of the circular wait condition

All the resources are enumerated monotonically

A process can only ask for a resources if the resource number is
greater than the numbers of all the resources already held by
other processes.

gtl1–R668 W5L2 — Deadlock 2016–02–21 29 / 31

Deadlock Prevention Eliminate Circular Wait

Livelocks and starvation

Live lock is just a deadlock where a process performs an infinite
loop without being blocked

Starvation is a situation where a process never gets an
opportunity to run. Occurs due to the poor scheduling policy

gtl1–R668 W5L2 — Deadlock 2016–02–21 30 / 31

Summary

Summary

Deadlock is a state where no processes can proceed because all
the required resources are already in use by other processes

Deadlock is undesirable

Can try to detect and rectify

Can try to avoid or prevent

Banker’s algorithm can be used for avoidance

Prevention requires eliminating one or more of the conditions
for deadlock

gtl1–R668 W5L2 — Deadlock 2016–02–21 31 / 31

CO2017 — Week 6L1 — Devices, Input/Output and

Buffering

Dr Gilbert Laycock (gtl1)

2016–02–22

gtl1–R675 W6L1 — I/O system 2016–02–22 1 / 18

Overview

Context

Operating systems

OS overview
Processes and scheduling
Memory management
File systems
Devices and Input/Output (I/O)

Networking

Introduction
Layered models
(network) Application programming

gtl1–R675 W6L1 — I/O system 2016–02–22 2 / 18

Overview

Overview

Objectives of I/O management system

Structure of I/O system

Buffering techniques

gtl1–R675 W6L1 — I/O system 2016–02–22 3 / 18

Requirements of I/O devices Performance characteristics of I/O devices

Characteristics of I/O Devices

I/O devices vary in a number of ways

Characteristics Examples

Data Rate Disks: 10-150MBytes/sec.

Keyboard: 10-15 bytes/sec

Unit of Transfer Disks: blocks of 512…4096 bytes

Screen: single characters

Permissible operations Disks: read/write/seek

Printer: write/move paper/select font

Error Conditions Disks: read errors

Printer: paper out

gtl1–R675 W6L1 — I/O system 2016–02–22 4 / 18

Requirements of I/O devices Objectives of I/O system

Objectives of I/O System from user POV

Efficiency

I/O devices are much slower than the processor

Desire to use I/O devices efficiently and avoid blocking CPU

Independence and uniformity

I/O devices are quite complex and very diverse

OS user should not have to know the details of I/O devices

I/O system should allow the OS user to treat devices in a uniform way

OS user should deal with virtual devices rather than actual devices

gtl1–R675 W6L1 — I/O system 2016–02–22 5 / 18

Structure of I/O system

Structure of I/O System

I/O system consists of several layers

Application programs

Application’s I/O is written in high level language
Translated to system calls

I/O Control System: deal with I/O related system calls.

Operating System

Device Driver
I/O Control

SystemProgram

Application Device

I/O Bus

Controller

(hardware)

I/O Device

(hardware)

System Calls

gtl1–R675 W6L1 — I/O system 2016–02–22 6 / 18

Structure of I/O system

Structure of I/O System (Cont’d)

Device Driver:

software module in the OS that communicates with a particular
(type of) I/O device
converts logical I/O request into specific commands to the
device

Device controller:

Hardware unit attached to the I/O bus
Provides a hardware interface between computer and I/O
device

Operating System

Device Driver
I/O Control

SystemProgram

Application Device

I/O Bus

Controller

(hardware)

I/O Device

(hardware)

System Calls
gtl1–R675 W6L1 — I/O system 2016–02–22 7 / 18

Structure of I/O system

Structure of I/O System (Cont’d)

Two main kinds of I/O Device

Block device transfers data in groups of characters

Character device transfers data one character a time

Device descriptor

Information that will be used by the I/O controller

device identifier

instructions that operate the device

character translation tables

current status

current user process (if any)

gtl1–R675 W6L1 — I/O system 2016–02–22 8 / 18

Structure of I/O system Repeated data I/O

Repeated Data I/O

A process that does I/O will be repeatedly waiting for the I/O to
complete, e.g, data input from a disk:

1 Process issues system calls to read the first chunk of data into
working RAM

2 The process uses the data

User Process
Disk Drive

Work Area

Operating System

gtl1–R675 W6L1 — I/O system 2016–02–22 9 / 18

Structure of I/O system Repeated data I/O

Repeated Data Input and Output (Cont’d)

Time spent processing (Pi) and transferring (Ti):

T
1

P
1

T
2

P
2

T
3

P
3

This read-processing cycle has several problems:

CPU is idle most of the time, waiting for data transfers to finish
Total time is the sum of Ps and Ts
The disk unit is not running continuously (spins down
between accesses)

gtl1–R675 W6L1 — I/O system 2016–02–22 10 / 18

Buffering

Buffering

Improve efficiency by using buffering

Buffer is an interim memory area — holds data in transit
between process’s working RAM and the device

Two types of buffering
Input buffering
Output buffering

Buffers smooth out peaks in I/O demand

gtl1–R675 W6L1 — I/O system 2016–02–22 11 / 18

Buffering Output Buffering

Output buffering

Output data is transferred to an output buffer

The OS empties the buffer when it is full

The process is blocked only if it tries to output when the buffer
is full and the OS has not finished emptying it

gtl1–R675 W6L1 — I/O system 2016–02–22 12 / 18

Buffering Input buffering

Input buffering

Input data is stored in an input buffer

The process extracts data from this buffer

The OS (re-)fills the buffer when it is empty

The process is blocked only if trying to get data from an
empty buffer waiting for the OS to re-fill it

gtl1–R675 W6L1 — I/O system 2016–02–22 13 / 18

Buffering Single Buffering

Single Buffering

For example, data input with a single buffer

User Process
Disk Drive

Work Area
Buffer

Operating System

Blocks of data are read into the buffer and then moved to the
process’s working memory

Once a block has moved to working memory, its processing can
be in parallel with reading the next block

gtl1–R675 W6L1 — I/O system 2016–02–22 14 / 18

Buffering Single Buffering

Single buffering — timing

Time spent processing (Pi)
time moving buffer to working area (Mi)
time to transfer block to buffer (Ti)

M
3

P
1

T
1

M
1

T
2

T
3

T
4

M
2

P
2

P
3

This has improved the situation, but the process is still blocked
some of the time; and worse, the device is still idle some of the
time

gtl1–R675 W6L1 — I/O system 2016–02–22 15 / 18

Buffering Double Buffering

Double Buffering

Use two buffers: the process writes (or reads) to one, while the OS
empties (or fills) the other from the device

E.g, double buffering for input

Work Area

Buffer A

Buffer B

Operating System Disk DriveUser Process

Buffer A can be emptied into working memory while Buffer B is being
filled by I/O from the device

gtl1–R675 W6L1 — I/O system 2016–02–22 16 / 18

Buffering Double Buffering

Double Buffering (Cont’d)

Timing to process, move and transfer blocks:

P
3

P
2

P
1

TA
1

TB
2

TA
3

TB
4

MA MA
1 2 3

MA

TAi or TBi: transfer block i into buffer A or B from device
MAi or MBi: move block i from buffer A or B to work area
Pi: processing block i in the work area

If the processing time is less than transfer time, data I/O to the device
can be continuous

The idea can be extended to multiple buffering — with enough
buffers, we can always achieve continuous I/O.

gtl1–R675 W6L1 — I/O system 2016–02–22 17 / 18

Summary

Summary

I/O system separates users from the complexity of I/O devices

I/O system consists of: application program, I/O control system, device
driver, device controller, and I/O devices

Input and output buffering can be used to improve efficiency

Can use double or multiple buffering techniques

gtl1–R675 W6L1 — I/O system 2016–02–22 18 / 18

CO2017 — Week 6L2 — Networking: introduction

Dr Gilbert Laycock (gtl1)

2016–02–28

N.B, many figures are from Tanenbaum’s Computer Networks (4th ed)

gtl1–R698 W6L2 — Networking 2016–02–28 1 / 25

Overview

Recap and Lecture Overview

Recap

Operating systems: How can a stand alone computer work?
Process, memory, input-output, and file sub-systems

Overview of this lecture

Introduction to computer networks
Basic concepts: classification, layered structure, protocols, and services

gtl1–R698 W6L2 — Networking 2016–02–28 2 / 25

Introdution

What Is a Computer Network?

A computer network is a collection of interconnected
autonomous computers

Two computers are said to be interconnected if they can exchange
information. They can be connected via a number of media

Computer Network vs Distributed System (DS)
A DS is coherent and transparent; e.g, WWW
A DS is a software system built on top of a network

gtl1–R698 W6L2 — Networking 2016–02–28 3 / 25

Types of network

Network Classification

Two important criteria: transmission technology and scale

According to the transmission technology:
Broadcast networks have a single communication channel shared by all

machines.
Point-to-point networks consist of many connections between pairs of

machines.

gtl1–R698 W6L2 — Networking 2016–02–28 4 / 25

Types of network

Network Classification

Two important criteria: transmission technology and scale

According to the scale:
Personal area networks – PANs
Local area networks – LANs;
Metropolitan area networks – MANs;
Wide area networks – WANs;
Internetworks.

gtl1–R698 W6L2 — Networking 2016–02–28 5 / 25

Types of network

Network Classification by Scale

1 m Square meter

10 m Room

100 m Building

Campus1 km

City10 km

Interprocessor
distance

Processors
located in same

Example

100 km Country

Continent1000 km

Planet

Personal area network

The Internet

Local area network

Metropolitan area network

Wide area network

10,000 km

gtl1–R698 W6L2 — Networking 2016–02–28 6 / 25

Types of network Local Area Networks

Local Area Networks (LANs)

Privately-owned by an organisation

Fairly small (up to a few kilometres in size)

Speeds of 100 Mbps to 10 Gbps and few errors

Commonly broadcast communication with wireless, bus or ring
topologies

Cable Computer

(b)(a)

Computer

gtl1–R698 W6L2 — Networking 2016–02–28 7 / 25

Types of network Metropolitan Area Networks

Metropolitan Area Networks (MANs)

Covers a city or other large area; private or public

E.g. cable based broadband; JANET EMMAN

Internet

Antenna

Junction

box

Head end

gtl1–R698 W6L2 — Networking 2016–02–28 8 / 25

Types of network Wide Area Networks

Wide Area Networks (WANs)

Covers a country or continent

Computers or hosts are connected by a communication subnet or
just called (subnet)

Subnet consists of transmission lines and switching elements (also
called routers)

Subnet Router

Host

LAN

gtl1–R698 W6L2 — Networking 2016–02–28 9 / 25

Types of network Internetworks

Internetworks

Collection of interconnected networks

Connected by gateways, which translate data if necessary

Best known (and biggest) example is the Internet

Differences between subnet, network and internetwork

Subnet = routers + communication lines
Network = subnet + hosts (or cable + hosts for LAN)
Internetwork = different networks + gateways

gtl1–R698 W6L2 — Networking 2016–02–28 10 / 25

Layered Protocols

Layered Protocols

To exchange information, the communicating machines need to agree
on how to communicate.

A protocol is a collection of rules describing how communication is to
proceed, e.g,

The order of messages
How the info is presented within a message

Due to the complexity of computer communications, protocols are
arranged in layers. Different layers handle different aspects of the
communication

gtl1–R698 W6L2 — Networking 2016–02–28 11 / 25

Layered Protocols

Layered Protocols (Cont’d)

Layer 5

Layer 4

Layer 3

Layer 2

Layer 1

Host 1

Layer 4/5 interface

Layer 3/4 interface

Layer 2/3 interface

Layer 1/2 interface

Layer 5 protocol
Layer 5

Layer 4

Layer 3

Layer 2

Layer 1

Host 2

Layer 4 protocol

Layer 3 protocol

Layer 2 protocol

Layer 1 protocol

Physical medium

gtl1–R698 W6L2 — Networking 2016–02–28 12 / 25

Layered Protocols

Layered Protocols (Cont’d)

Each layer provides services to the next layer up. The upper layer
need not know how services are implemented

Layer n on one host carries out a conversation with layer n on another
host

The rules used form the layer n protocol; the two hosts/processes
carrying out this conversation are called peers
The interface between two layers defines which primitive operations and
services the lower layer makes available to its upper layer

gtl1–R698 W6L2 — Networking 2016–02–28 13 / 25

Layered Protocols

The Communicating Philosphers model

I like
rabbits

Location A

3

2

1

3

2

1

Location B

Message Philosopher

Translator

Secretary

Information
for the remote
translator

Information
for the remote
secretary

L: Dutch

Ik vind

konijnen

leuk

Fax #—

L: Dutch

Ik vind

konijnen

leuk

J’aime
bien les

lapins

L: Dutch

Ik vind

konijnen

leuk

Fax #—

L: Dutch

Ik vind

konijnen

leuk

gtl1–R698 W6L2 — Networking 2016–02–28 14 / 25

Layered Protocols Services

Services

A service is a specified set of primitives or operations available to a
user or other entity

Connection-oriented services:

Used for a sequence of messages
Analogous to the telephone system
Example uses: file transfer and remote login

Connectionless services:

Used for single messages, which are self-contained
Analogous to the postal system
Might be unreliable (unacknowledged), reliable (acknowledged), or
request-reply services
Example uses: database queries

gtl1–R698 W6L2 — Networking 2016–02–28 15 / 25

Layered Protocols Services and protocols

Relationship between Services and Protocols

A service is a set of primitives that a layer provides to its upper layer.
It defines what a layer does, but says nothing on how to implement
these operations

A protocol is a set of rules governing the format and meaning of the
info exchanged by peer entities of the same layer. It says how a layer
works inside.

Entities use protocols to implement their service definitions

Layer k

Layer k + 1

Layer k – 1

Protocol

Service provided by layer k

Layer k

Layer k + 1

Layer k – 1

gtl1–R698 W6L2 — Networking 2016–02–28 16 / 25

Layered Protocols Virtual Communication Channel

Virtual Communication

No real data is passed directly between peers (except at the
lowest layer)

The layer n sender entity passes the info to layer n − 1. The layer n
receiver gets info from layer n − 1
Each layer may add a header and/or trailer to the info it sends, which
is stripped off by its peer

H2 H3 H4 M1 T2 H2 H3 M2 T2 H2 H3 H4 M1 T2 H2 H3 M2 T2

H3 H4 M1 H3 M2 H3 H4 M1 H3 M2

H4 M H4 M

M M

Layer 2

protocol
2

Layer 3

protocol

Layer 4 protocol

Layer 5 protocol

3

4

5

1

Layer

Source machine Destination machine

gtl1–R698 W6L2 — Networking 2016–02–28 17 / 25

Layered Protocols The ISO OSI Reference model

The ISO OSI Reference Model

The International Standards Organization (ISO) Open Systems
Interconnection (OSI) reference model defines seven layers

Layer

Presentation

Application

Session

Transport

Network

Data link

Physical

7

6

5

4

3

2

1

Interface

Host A

Name of unit

exchanged

APDU

PPDU

SPDU

TPDU

Packet

Frame

Bit

Presentation

Application

Session

Transport

Network

Data link

Physical

Host B

Network Network

Data link Data link

Physical Physical

Router Router

Internal subnet protocol

Application protocol

Presentation protocol

Transport protocol

Session protocol

Communication subnet boundary

Network layer host-router protocol

Data link layer host-router protocol

Physical layer host-router protocol

gtl1–R698 W6L2 — Networking 2016–02–28 18 / 25

Layered Protocols The ISO OSI Reference model

The ISO OSI Reference Model

Physical layer: responsible for transmitting raw bits over a communication
medium

Data link layer: transforms the raw transmission media into a reliable line
for the network layer; transmit data frames while detecting
and correcting errors

Network layer: routing between non-adjacent nodes within the subnet;
transmits packets of data

Transport layer: accepts data from the session layer, splitting it, and
ensures all the parts arrive correctly at the other end

gtl1–R698 W6L2 — Networking 2016–02–28 19 / 25

Layered Protocols The ISO OSI Reference model

The ISO OSI Reference Model (Cont’d)

Session layer: establish sessions between different machines

Presentation layer: encodes data in a standard way, and translates
between different representations

Application layer: contains common application oriented protocols, e.g,
file transfer protocol, email

gtl1–R698 W6L2 — Networking 2016–02–28 20 / 25

Layered Protocols TCP/IP Reference model

The TCP/IP Reference Model

The model has four layers

It features the Internet Protocol (IP) and Transmission Control
Protocol (TCP)

TCP/IPOSI

Application

Presentation

Session

Transport

Network

Data link

Physical

7

6

5

4

3

2

1

Application

Transport

Internet

Host-to-network

Not present
in the model

gtl1–R698 W6L2 — Networking 2016–02–28 21 / 25

Layered Protocols TCP/IP Reference model

The TCP/IP Reference Model (Cont’d)

Host-to-network layer: (link) logically sits below the internet layer, but not
formally defined; combines data link and physical layers in the
OSI model

Internet layer: responsible for transporting packets over the network; it
uses the Internet Protocol (IP)

Transport layer: allows peer entities to carry on a establish a
communication channel; uses two protocols: TCP
(Transmission Control Protocol) [“reliable”
connection-oriented], and UDP (User Datagram Protocol)
[“unreliable”, connectionless]

Application layer: contains application-oriented protocols, e.g, email
(SMTP, IMAP); World Wide Web (HTTP); . . .

gtl1–R698 W6L2 — Networking 2016–02–28 22 / 25

Layered Protocols TCP/IP Reference model

Layers and protocols

ARPANET

Protocols

Networks

TELNET

TCP UDP Transport

LAN

DNS Application

Layer (OSI names)

Packet
radio

Physical +
data link

SMTP

SATNET

FTP

IP Network

gtl1–R698 W6L2 — Networking 2016–02–28 23 / 25

Layered Protocols Hybrid model

Hybrid 5-layer model

Physical layer: Includes the transmission hardware

Data link layer: Includes software for effective transmission of bits
between computers

Network layer: Where communicating computers are not directly
connected, the network layer establishes a route

Transport layer: High level communication protocols between
computers

Application layer: the software you use with the Internet: web
browsers, emails, search engines, social networking
software, etc.

gtl1–R698 W6L2 — Networking 2016–02–28 24 / 25

Summary

Summary

Definition of computer network

Classification of computer networks

Network software protocols

The OSI and TCP/IP reference models

gtl1–R698 W6L2 — Networking 2016–02–28 25 / 25

CO2017 — Week6 L3 — Physical & data layers

Dr Gilbert Laycock (gtl1)

2016–03–02

gtl1–R716 W6L3 — Lower network layers 2016–03–02 1 / 41

Overview

Context

Operating systems

OS overview
Processes and scheduling
Memory management
File systems
Devices and Input/Output (I/O)

Networking

Introduction & layered model
Low layers
Middle layers
Upper layers (application programming)

gtl1–R716 W6L3 — Lower network layers 2016–03–02 2 / 41

Overview

Overview

1 Network layers

2 The lower layers

3 Frames and delimiters.

4 Error correcting and detecting encoding.

gtl1–R716 W6L3 — Lower network layers 2016–03–02 3 / 41

Layer models of networks

General Layer model

Layer 5

Layer 4

Layer 3

Layer 2

Layer 1

Host 1

Layer 4/5 interface

Layer 3/4 interface

Layer 2/3 interface

Layer 1/2 interface

Layer 5 protocol
Layer 5

Layer 4

Layer 3

Layer 2

Layer 1

Host 2

Layer 4 protocol

Layer 3 protocol

Layer 2 protocol

Layer 1 protocol

Physical medium

gtl1–R716 W6L3 — Lower network layers 2016–03–02 4 / 41

Layer models of networks Services and Protocols

Relationship between Services and Protocols

Service: a set of primitives that a layer provides to the layer
above. Defines what a layer does; but says nothing on
how to implement it

Protocol: a set of rules governing the format and semantics of
the data exchanged by peers at that layer. Describes
how a layer works.

Layer k

Layer k + 1

Layer k – 1

Protocol

Service provided by layer k

Layer k

Layer k + 1

Layer k – 1

gtl1–R716 W6L3 — Lower network layers 2016–03–02 5 / 41

Physical Layer

Physical Layer

Aim is to transmit raw bits reliably between devices
If a 1 bit is transmitted, it must be received as a 1, not a 0

Defines mechanical, electrical, electro-magnetic, etc. and timing
interfaces

How to represent digital data using analogue signal?
What communication media can be used?

Two broad kinds of transmission media
Guided (Wired): coaxial cable and fibre optics
Unguided (Wireless): radio, lasers, micro-waves, infra-red

Transmission media differ in bandwidth, propagation delay, cost
and ease of installation and maintenance

gtl1–R716 W6L3 — Lower network layers 2016–03–02 6 / 41

Physical Layer Example issue: Manchester Encoding

Manchester Encoding

Over most LANs, digital signal is modulated from a Direct Current
(DC) signal

An obvious way: represent a 0 bit by 0V, and a 1 by 5V

But, how can we distinguish a sequence of 0s from no signal?

Or if clock synchronisation is lost, so is the bit pattern.

Bit stream 1 0 0 0 0 1 0 1 1 1 1

Binary encoding

Manchester encoding

Differential

Manchester encoding

Transition here

indicates a 0

Lack of transition here

indicates a 1

(a)

(b)

(c)

gtl1–R716 W6L3 — Lower network layers 2016–03–02 7 / 41

Physical Layer Example issue: Manchester Encoding

Manchester Encoding

Manchester encoding: each bit period has two intervals

0 bit: a low voltage in 1st interval and a high one in 2nd

1 bit: a high voltage in 1st interval and a low one in 2nd

Every bit has a transition in the middle; so no signal, or loss of
clock can always be detected.

But, what if the polarity is reversed? Valid but reversed bit
pattern.

Bit stream 1 0 0 0 0 1 0 1 1 1 1

Binary encoding

Manchester encoding

Differential

Manchester encoding

Transition here

indicates a 0

Lack of transition here

indicates a 1

(a)

(b)

(c)

gtl1–R716 W6L3 — Lower network layers 2016–03–02 8 / 41

Physical Layer Example issue: Manchester Encoding

Differential Manchester encoding

Differential Manchester encoding: Each bit period has a change
of voltage in the middle

0 bit: a change of voltage at the start of the bit period

1 bit: no change of voltage at the start of the bit period

Does not matter if polarity is reversed.

Bit stream 1 0 0 0 0 1 0 1 1 1 1

Binary encoding

Manchester encoding

Differential

Manchester encoding

Transition here

indicates a 0

Lack of transition here

indicates a 1

(a)

(b)

(c)

gtl1–R716 W6L3 — Lower network layers 2016–03–02 9 / 41

Data link layer

Data Link Layer

The central issue is to reliably transmit data over a non-reliable
channel

Reliability means

Avoid loss or corruption of information
Avoid a faster sender swamping a slower receiver with a flood of
bits

Establishing absolute reliability is impossible

Different approaches make particular assumptions about the
conditions affecting reliabilty

gtl1–R716 W6L3 — Lower network layers 2016–03–02 10 / 41

Data link layer Services at the data-link layer

Types of services at the Data Link Layer

Unacknowledged connectionless: a stream of bits is sent without any
any concern for their fate (e.g. original ethernet)

Acknowledged connectionless: sender divides the stream into
frames and requires acknowledgement that each
frame has arrived; re-transmit/error if no ack arrives
within time limit (e.g. WiFi)

Acknowledged connection-oriented: a connection is established
before any frames are sent; frames are sent and must be
received in order.

gtl1–R716 W6L3 — Lower network layers 2016–03–02 11 / 41

Data link layer Fast Sender/Slow Receiver

Fast sender/slow receiver problem

Divide the data into small frames and require acknowledgement
after sending each portion of data

Sender knows that the receiver has received the particular
frames

gtl1–R716 W6L3 — Lower network layers 2016–03–02 12 / 41

Data link layer Framing

Framing

Data is sent in small pieces: frames

Can then receive acknowledgement (ack) after each frame

Applicable to acknowledged connectionless and
connection-oriented services

Acknowledgements help by

avoid overloading (flooding) of a slow receiver;
localising any transmission problems to the most recent frame.

gtl1–R716 W6L3 — Lower network layers 2016–03–02 13 / 41

Data link layer Delimiters and stuffing

Delimiters

The sender needs to specify the beginning and end of frames

Usually done with delimiters

A delimiter is a particular byte preceding and following each
frame

But, what if a delimiter byte occurs within a frame?

Two possible approaches (among others):

Stuffing byte protocol
Stuffing bit protocol

gtl1–R716 W6L3 — Lower network layers 2016–03–02 14 / 41

Data link layer Delimiters and stuffing

Stuffing byte protocol: description.

Two special bytes are needed:

The delimiter itself
The control byte (aka escape)

If the delimiter byte occurs in the frame, put the control byte
before it in the frame

If the control byte itself occurs in the frame, add another
control byte is before it.

gtl1–R716 W6L3 — Lower network layers 2016–03–02 15 / 41

Data link layer Delimiters and stuffing

Stuffing byte protocol: example

Assume that the bytes we want to send are represented by
decimal digits

Also, assume that the delimiter byte is 0 and the control byte is 1

Want to send the frame 21501601.

Actually send 021151011610110.

gtl1–R716 W6L3 — Lower network layers 2016–03–02 16 / 41

Data link layer Delimiters and stuffing

Stuffing bit protocol

The delimiter is ’01111110’ (6 × 1 bits between two 0 bits)
Inside the frame ’0’ is inserted after every occurrence of ’11111’
(5 × 1 bit)
E.g, if the frame is ’00111111 10110001’, actually transmit:
’01111110 00111110 11011000 1 01111110’

Smaller overhead than byte stuffing

gtl1–R716 W6L3 — Lower network layers 2016–03–02 17 / 41

Data link layer Corruption, parity and redundancy

Data Corruption

Data can be corrupted by the physical layer; errors are
introduced

E.g: the sender says ’LONDON’, the receiver reads ’OXFORD’

At the bit level some ’0’s are received as ’1’s and vice versa

Some types of data corruption can be avoided

100% guarantee is impossible to achieve

gtl1–R716 W6L3 — Lower network layers 2016–03–02 18 / 41

Data link layer Corruption, parity and redundancy

Parity encoding: description

In each byte, 7 bits are allocated for the content, one for
verification

The verification bit is called parity bit

If the number of ’1’s in the 7 bits is even, the parity bit should be
’0’, otherwise ’1’ (this is even parity; odd parity is also possible).

gtl1–R716 W6L3 — Lower network layers 2016–03–02 19 / 41

Data link layer Corruption, parity and redundancy

Parity encoding: processing

The sender calculates the correct value of the parity bit and
transmits it

The receiver re-calculates parity and checks if the received
parity bit is the same

If incorrect, the receiver reports an error instead of an ack

Can detect errors in an odd number of bits — in particular single
bit errors

gtl1–R716 W6L3 — Lower network layers 2016–03–02 20 / 41

Data link layer Corruption, parity and redundancy

Parity encoding: example

Suppose that the 7 bits to transmitted are ’0110110’.

There are 4 × 1 bits, so parity is even and the parity bit will be 0.
So transmit ’01101100’.

Suppose that ’01111100’ is received.

Receiver calculates partity on ’0111110’ as odd, so parity would
be 1.

Received parity bit is different to calculated parity bit: error must
have occurred.

gtl1–R716 W6L3 — Lower network layers 2016–03–02 21 / 41

Data link layer Corruption, parity and redundancy

Redundant encoding

Parity encoding is an example of a redundant encoding:

To avoid corruption verification data is added to the real
content

Methods for adding the verification data and restoring the
original content are encoding algorithms

A particular encoding method will be able to detect/correct
specific kinds of error

gtl1–R716 W6L3 — Lower network layers 2016–03–02 22 / 41

Data link layer Corruption, parity and redundancy

Error detecting vs error correcting

Error detecting codes detect particular types of errors without
the ability to correct them

E.g, the parity-bit encoding allows detection of “single bit”
errors

Error correcting codes put right particular types of errors
without needing re-transmission

gtl1–R716 W6L3 — Lower network layers 2016–03–02 23 / 41

Data link layer Corruption, parity and redundancy

Triple modular redundancy

Simple error correcting encoding:

Each ‘0’ is replaced by ‘000’

Each ‘1’ is replaced by ‘111’

Can detect and correct single bit errors.

E.g. if ‘010’ is received then the it will be corrected to ‘000’

gtl1–R716 W6L3 — Lower network layers 2016–03–02 24 / 41

Data link layer Corruption, parity and redundancy

TMR example

Want to transmit ’011’.

Encode and transmit as ’000 111 111’.

Suppose that ’010 011 110’ is received.

Successfully decode as ’011’

gtl1–R716 W6L3 — Lower network layers 2016–03–02 25 / 41

Data link layer Corruption, parity and redundancy

Drawback of triple modular encoding

There is a high overhead to the encoding:

The verification data is twice the size of the original content

So additional traffic is passed through the network

Slowing down communication

gtl1–R716 W6L3 — Lower network layers 2016–03–02 26 / 41

Data link layer Corruption, parity and redundancy

Two-Dimensional Parity

Uses a parity bit for each byte, and an extra parity byte (checksum)
for the complete frame

0101001 1
1101001 0
1011110 1
0001110 1
0110100 1
1011111 0
1111011 0

Can correct one-bit error and detect many multi-bit errors

gtl1–R716 W6L3 — Lower network layers 2016–03–02 27 / 41

Data link layer Corruption, parity and redundancy

Single bit error example

Transmitted

0101001 1
1101001 0
1011110 1
0001110 1
0110100 1
1011111 0

1111011 0

Received and checked

0101001 1 1
1101001 0 0
1011110 1 1
0011110 1 0
0110100 1 1
1011111 0 0

1111011 0 0
1101011 0 1

Single-bit errors can be detected and corrected.

gtl1–R716 W6L3 — Lower network layers 2016–03–02 28 / 41

Data link layer Corruption, parity and redundancy

Double bit error example

Transmitted

0101001 1
1101001 0
1011110 1
0001110 1
0110100 1
1011111 0

1111011 0

Received and checked

0101001 1 1
1101001 0 0
1011110 1 1
0111110 1 1
0110100 1 1
1011111 0 0

1111011 0 0
1001011 0 0

Multi-bit errors can be detected but not corrected.

gtl1–R716 W6L3 — Lower network layers 2016–03–02 29 / 41

Data link layer Hamming code

Hamming code

Developed by Richard Hamming in 1940s to 1950s.

Corrects all single bit errors; can detect up to 3 bit errors.

If n bits are to be transmitted, the code adds at most log(n) + 1
verification bits

This is the theoretical lower limit on the required overhead of
verification bits.

gtl1–R716 W6L3 — Lower network layers 2016–03–02 30 / 41

Data link layer Hamming code

Family of Hamming codes

Hamming codes are classified by number of parity bits in use, which
in turn determines how many data bits can be “covered”:

Parity Total Data Name Rate
2 3 1 Hamming(3,1) (TMR) 1/3
3 7 4 Hamming(7,4) 4/7
4 15 11 Hamming(15,11) 11/15
5 31 26 Hamming(31,26) 26/31
. . .
m 2m − 1 2m − m − 1 Hamming(2m − 1,2m − m − 1)

Based on the observation the m parity bits can cover (express)
2m − 1 bits in total.

gtl1–R716 W6L3 — Lower network layers 2016–03–02 31 / 41

Data link layer Hamming code

Encoding using Hamming(7,4)

There will be 7 bits in total: 4 data bits and 3 parity bits.

The parity bits will be in positions that are powers of 2.
The data bits will be in the remaining positions.
Enter the (4) data bits into the data positions.

Position 1 2 3 4 5 6 7

Parity bits p1 p2 p4

Data bits d1 d2 d3 d4

1110 1 0 1 1

gtl1–R716 W6L3 — Lower network layers 2016–03–02 32 / 41

Data link layer Hamming code

Encoding using Hamming(7,4) cont’d

Next work out the parity bits.

We say that a bit position belongs to group i if the i-th least
significant bit of the binary form of the position is 1

For parity bit n, it covers parity for the data bits in positions that
are members of group n.

Parity bit 1 (20) covers bit positions: 1,3,5,7,9, . . .

Parity bit 2 (21) covers bit positions: 2–3,6–7,10–11,14–15, . . .

Parity bit 4 (22) are of index: 4–7,12–15,20–23, . . .

gtl1–R716 W6L3 — Lower network layers 2016–03–02 33 / 41

Data link layer Hamming code

Encoding using Hamming(7,4) cont’d

p1 covers parity for bits 1, 3, 5, 7
p2 covers parity for bits 2, 3, 6, 7
p4 covers parity for bits 4, 5, 6, 7

Position 1 2 3 4 5 6 7

Parity bits p1 p2 p4

Data bits d1 d2 d3 d4

1110 ? 1 0 1 11110 0 1 0 1 11110 0 ? 1 0 1 11110 0 1 1 0 1 11110 0 1 1 ? 0 1 11110 0 1 1 0 0 1 1

gtl1–R716 W6L3 — Lower network layers 2016–03–02 34 / 41

Data link layer Hamming code

Hamming parity bits

Consider constructing Hamming(15,11) for 157910 = 110001010112

Pos 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Enc p1 p2 d1 p4 d2 d3 d4 p8 d5 d6 d7 d8 d9 d10 d11
p1 X X X X X X X X
p2 X X X X X X X X
p4 X X X X X X X X
p8 X X X X X X X X

157910 – – 1 – 1 0 0 – 0 1 0 1 0 1 1
p1 1 – 1 – 1 – 0 – 0 – 0 – 0 – 1
p2 – 0 1 – – 0 0 – – 1 0 – – 1 1
p4 – – – 0 1 0 0 – – – – 1 0 1 1
p8 – – – – – – – 0 0 1 0 1 0 1 1
f 1 0 1 0 1 0 0 0 0 1 0 1 0 1 1
r 1 0 1 0 0 0 0 0 0 1 0 1 0 1 1

check 0 0 1 1 0 0 0 0 0 1 0 1 0 1 1

If we actually receive string r (error in bit 5), recalculating the parity
bits shows parity errors at 1 & 4, which in turn shows the error was in
bit 5 (4 + 1).

gtl1–R716 W6L3 — Lower network layers 2016–03–02 35 / 41

Data link layer Hamming code

Decoding

The receiver recomputes parity bits

If some of the parity bits are not correct, it indicates that an error
has occurred

The combined positions of the mis-matched parity bits uniquely
identify the location of the incorrect bit in the message

gtl1–R716 W6L3 — Lower network layers 2016–03–02 36 / 41

Data link layer Hamming Distance

Hamming distance

General measures for all encodings.

Code rate: the ratio of transmitted bits to content bits

parity (8,7): 7/8 = 0.875
triple modular (3,1): 1/3 = 0.333
Hamming: (7,4) is 4/7 = 0.571 or (15,11) is
11/15 = 0.733

Hamming distance: number of bits that need to be wrong (flipped)
to get another “valid” code

parity: 2
triple modular: 3
Hamming: min of 3; one extra parity bit gives
distance of 4.

gtl1–R716 W6L3 — Lower network layers 2016–03–02 37 / 41

Sliding Window protocol

Sliding Window Protocol

Sender transmits frames to the receiver. Assume that frames are
sequentially numbered. Receiver sends an ack for the OK
frames.

What happens when the receiver notices an error in a frame
(that cannot be corrected)?

Receiver needs to transmit a nak to the sender indicating an
error was received, and which frame was affected.

How much of the message does the sender need to
re-transmit when it receives a nak?

gtl1–R716 W6L3 — Lower network layers 2016–03–02 38 / 41

Sliding Window protocol

Go back n

Simplest method is for sender to simply go back to the frame
after the last which was acked and start transmitting in
sequence again. Sliding window of size 1.

Alternatively receiver can continue to buffer incoming frames
after sending a nak; the sender only needs to re-send the naked
frames and can then resume the sequence where it left off.
Sliding window of size n, where it can buffer that many frames.

gtl1–R716 W6L3 — Lower network layers 2016–03–02 39 / 41

Sliding Window protocol

0 1

0 1 2 3 4 5 6 7 8E D D D D D D

2 3 4 5 6 7 8 2 3 4 5 6 7 8 9

Timeout interval

Error Frames discarded by data link layer

A
c
k
0

A
c
k
1

Time

(a)

(b)

0 1

0 1 9 10 11 12 13 14E

2 3 4 5 2 6 7 8 9 10 11 12 13 14 15

8

Error Frames buffered by data link layer

A
c
k
0

A
c
k
1

N
a
k

2

4 5 23 6

A
c
k
1

A
c
k
1

A
c
k
5

A
c
k
6

7

A
c
k
7

A
c
k
8

A
c
k
9

A
c
k
1

1
A

c
k
1

2
A

c
k
1

3

A
c
k
1

0

A
c
k
2

A
c
k
3

A
c
k
4

A
c
k
5

A
c
k
6

A
c
k
7

gtl1–R716 W6L3 — Lower network layers 2016–03–02 40 / 41

Summary

Summary

Physical layer concerned with transmission of signals along
wires/through the air

Data layer concerned with splitting data into frames and
encoding it to send through potentially lossy physical layer

Considered error detection/correction methods for transmitted
data

gtl1–R716 W6L3 — Lower network layers 2016–03–02 41 / 41

CO2017 — Week 7L1 — Network Layer: Routing

Algorithms

Dr Gilbert Laycock (gtl1)

2016–03–13

gtl1–R756 W7L3 — Network Layer 2016–03–13 1 / 22

Overview

Context

Operating systems

Networking

Introduction
Layered models

Physical & Data link layer
Network Layer
Transport Layer, Application layer

Application programming

gtl1–R756 W7L3 — Network Layer 2016–03–13 2 / 22

Overview

Recap and Lecture Overview

Main functions of the network layer

Routing algorithms

gtl1–R756 W7L3 — Network Layer 2016–03–13 3 / 22

Network Layer

Introduction to the Network Layer

Aim: get packets from source to destination (End-to-End)

Need to find best path over the subnet — routing

Router stores the subnet topology by routing table

Provide services to the transport layer

Connectionless or connection-oriented

A E F
Process P2

Packet

LAN

Router Carrier’s equipment

Process P1

B

H1 H2

D

C

1

gtl1–R756 W7L3 — Network Layer 2016–03–13 4 / 22

Network Layer Connectionless services

Connectionless Services

Packets, called datagrams, are routed independently

Transport layer responsible for error and flow control

Each entry in routing table: (destination, outgoing line)

E.g. network layer in the Internet

A E F
Process P2

LAN

Router

1

Carrier’s equipment

Process P1

B

H1 H2

D

C

Packet

3

4

2

A –

B B

initially

C C

D B

E C

F C

Dest.

A –

B B

later

A’s table

C C

D B

E B

F B

A A

B A

C’s table

C –

D D

E E

F E

A C

B D

E’s table

C C

D D

E –

F F

Line

gtl1–R756 W7L3 — Network Layer 2016–03–13 5 / 22

Network Layer Connection-oriented services

Connection-Oriented Services

Must set up a connection, called virtual circuit (VC)

Router allocates a unique VC identifier when it sets up a VC

For a particular connection packets are routed over the same VC

Each subsequent packet will include VC ID number

Routing table records where to forward packets for each VC

E F
Process P2

LAN

Router

1

Carrier’s equipment

Process P1

Process
P3

B

H1

H3

H2

D

C

3

4
2

H1 1

H3 1

C 1

C 2

A’s table

A 1

A 2

E 1

E 2

C’s table

C 1

C 2

F 1

F 2

E’s table

A

In Out

gtl1–R756 W7L3 — Network Layer 2016–03–13 6 / 22

Routing Flooding

Routing by Flooding

Forward each incoming packet on every outgoing line

Need a method to end the process at some point. Two possibilities

Each packet has a hop counter

Decremented each time it is forwarded
Packet is discarded when the counter reaches zero

OR:
Each router remembers packets they have seen and only forward new
ones

Flooding is not very practical, except when:

Robustness in case of large network failures is a desirable feature
Good for broadcasting to a significant proportion of the hosts

gtl1–R756 W7L3 — Network Layer 2016–03–13 7 / 22

Routing Shortest Path

Shortest Path Routing

Represent network by graph: router as node and connection line as
edge, labelled with its length/cost

����

��

����

��
��
��
��

��
�����
�����
�����
�����
�����
�����

�����
�����
�����
�����
�����
�����

��
��
��
��
��
��
��
��
��
��

��
��
��
��
��
��
��
��
��
��

�����
�����
�����

�����
�����
�����

����
����
����
����
����

����
����
����
����
����

�����
�����
�����
�����

��
��
��
��
��
��

��
��
��
��
��
��

5

8

4

3

3

4

0

1

2
4

3

Path Cost
0–1–3–4 11
0–1–2–4 13
0–2–4 12

0–2–1–3–4 18

There are several paths from 0 to 4.

The path 0–1–3–4 is shortest/cheapest.

gtl1–R756 W7L3 — Network Layer 2016–03–13 8 / 22

Routing Dijkstra’s algorithm

Dijkstra’s Algorithm

Calculates shortest paths from a node to all nodes

Distance between linked node i and j is dist[i][j]; for nodes not
directly connected, it is ∞
Each node is given a status: permanent or temporary

If a node is permanent, best path already found
Otherwise, might find a better path

gtl1–R756 W7L3 — Network Layer 2016–03–13 9 / 22

Routing Dijkstra’s algorithm

Each node is labelled with a length and a predecessor

final static int permanent = 1;
final static int temporary = 2;
int[N][N] dist;
int[N] status; // permanent or temporary
int[N] length;
int[N] predecessor;

gtl1–R756 W7L3 — Network Layer 2016–03–13 10 / 22

Routing Dijkstra’s algorithm

Dijkstra’s Algorithm (Pseudo-code)

int j; length[0] = 0; status[0] = permanent;
for (j=1; j length[2], this means that path
0 → 1 → 2 is not a better path than path 0 → 2. So, no change with N2
For N3, length[1] + dist[1][3] = 5 + 3 = 8 < length[3] = ∞. A better path is found for N3 for a path is better than no path (whose length is ∞). So update length[3] = 8 and predecessor[3] = 1 Step 2: Pick N2 from T (same reason as in Step 1) as the working node, j = 2. Update status[2] = permanent and T = {3, 4}. Check N2’s adjacent nodes in T (N4). For N4, length[2] + dist[2][4] = 8 + 4 = 12 < length[4]. A better path is found for N4. So update length[4] = 12 and predecessor[4] = 2 gtl1–R756 W7L3 — Network Layer 2016–03–13 14 / 22 Routing Dijkstra’s algorithm Detailed Solving Steps, cont’d Step 3: Pick N3 from T as the working node, j = 3. Update status[3] = permanent and T = {4}. Check N4, length[3] + dist[3][4] = 8 + 3 = 11 < length[4] = 12, this means a better path is found for N4. So update length[4] = 11 and predecessor[4] = 3 Step 4: Pick N4 from T, j = 4. Update status[4] = permanent and T = {}. Stop for T is now empty. All nodes have been permanent and the shortest path has been found Path: Starting at the N4, and following the predecessor fields backward until N0 is reached: N4 predecessor[4]=3 =⇒ N3 predecessor[3]=1 =⇒ N1 predecessor[1]=0 =⇒ N0 Finally the shortest path from node 0 to node 4 is 0 → 1 → 3 → 4 with a total length of 11. gtl1–R756 W7L3 — Network Layer 2016–03–13 15 / 22 Routing Dijkstra’s algorithm Distance Array for the Example Graph 0 1 2 3 4 0 0 5 8 ∞ ∞ 1 5 0 4 3 ∞ 2 8 4 0 ∞ 4 3 ∞ 3 ∞ 0 3 4 ∞ ∞ 4 3 0 gtl1–R756 W7L3 — Network Layer 2016–03–13 16 / 22 Routing Dijkstra’s algorithm Dijkstra’s Algorithm: Example Node status length predecessor j = 0 0 permanent 0 - 1 temporary 5 0 2 temporary 8 0 3 temporary ∞ 0 4 temporary ∞ 0 j = 1 0 permanent 0 - 1 permanent 5 0 2 temporary 8 0 3 temporary 8 1 4 temporary ∞ 0 j = 2 0 permanent 0 - 1 permanent 5 0 2 permanent 8 0 3 temporary 8 1 4 temporary 12 2 gtl1–R756 W7L3 — Network Layer 2016–03–13 17 / 22 Routing Dijkstra’s algorithm Dijkstra’s Algorithm: Example Node status length predecessor j = 3 0 permanent 0 - 1 permanent 5 0 2 permanent 8 0 3 permanent 8 1 4 temporary 11 3 j = 4 0 permanent 0 - 1 permanent 5 0 2 permanent 8 0 3 permanent 8 1 4 permanent 11 3 Best path from 0 to 4 is 0–1–3–4 gtl1–R756 W7L3 — Network Layer 2016–03–13 18 / 22 Routing Dynamic routing Dynamic Routing Algorithms Network conditions may change =⇒ dynamic routing Each router can measure the “distance” (e.g. queue length, delay) to its neighbours Routers exchange info with neighbours, so that info propagates through the network Router then does routing using up-to-date info gtl1–R756 W7L3 — Network Layer 2016–03–13 19 / 22 Routing Hierarchical routing Hierarchical Routing Previous algorithms require router to know the whole subnet: Router memory, CPU time, and bandwidth Better technique: hierarchical routing Routers are divided into regions Each router knows the routers in its region Routers know nothing about other regions, but know how to get packets to somewhere in other regions Multi-level hierarchies are possible gtl1–R756 W7L3 — Network Layer 2016–03–13 20 / 22 Routing Hierarchical routing Hierarchical Routing (Cont’d) Region 1 Region 2 Region 3 Region 5Region 4 1B 1A 1C 2A 2B 2C 5B 5C 5A 5E 5D 2D 4A 4B 4C 3A 3B 1B 1 1C 1 1B 2 1B 3 1B 3 1B 4 1C 3 1C 2 1C 3 1C 4 1C 4 1C 4 1C 5 1B 5 1C 6 1C 5 – –1A 1C 2A 2B 2C 2D 3A 3B 4A 4B 4C 5A 5B 5C 5D 5E 1B Line HopsDest. Full table for 1A 1A 1C 2 3 4 5 1B Line HopsDest. Hierarchical table for 1A 1B 1 1C 1 1B 2 1C 2 1C 3 1C 4 – – (a) (b) (c) gtl1–R756 W7L3 — Network Layer 2016–03–13 21 / 22 Summary Summary The network layer aims to pass packets from source to destination over the whole network Routing algorithms are used to find the best path for packets Static routing: flooding and Dijkstra’s algorithm Dynamic routing: deal with network condition changes Hierarchical routing: used for better efficiency gtl1–R756 W7L3 — Network Layer 2016–03–13 22 / 22 CO2017 — Week 7 — The Network and Transport layer in the Internet Dr Gilbert Laycock (gtl1) 2016–03–13 gtl1–R756 W7L2 — Network & Transport layer 2016–03–13 1 / 17 Overview Context Operating systems Networking Introduction Layered models Physical & Data link layer Network Layer, Transport Layer Application Layer Application programming gtl1–R756 W7L2 — Network & Transport layer 2016–03–13 2 / 17 Overview Recap and Lecture Overview Recap The network layer passes packets over the network using routing algorithms The network layer uses several strategies to avoid congestion control Multi-protocol routers deal with inter-networking Overview of this lecture The Internet Protocol (IP) Routing in the Internet gtl1–R756 W7L2 — Network & Transport layer 2016–03–13 3 / 17 Network layer in the internet Network Layer in the Internet The Internet is a collection of autonomous systems (ASes) Major backbones connect regional networks, which connect LANs Leased lines to Asia A U.S. backbone Leased transatlantic line Regional network A IP Ethernet LAN C D SNA network Tunnel IP token ring LAN A European backbone IP router National network Host B IP Ethernet LAN 1 2 gtl1–R756 W7L2 — Network & Transport layer 2016–03–13 4 / 17 Network layer in the internet Datagrams Communication in the Internet The Internet uses the Internet Protocol (IP) It aims to deliver datagrams from source to destination on a “best effort” base — delivery is not guaranteed Transport layer takes data streams (from the application layer), and breaks them into datagrams, typically 1500 bytes, but could be up to 64Kb Network layer transmits the datagrams across the Internet A datagram might be fragmented, if an intermediate network has a smaller packet size Each datagram is reassembled at the destination, and passed to the transport layer, which reassembles them into a data stream for the application gtl1–R756 W7L2 — Network & Transport layer 2016–03–13 5 / 17 Network layer in the internet Datagram format IP Datagram Format IP datagram = IP header + data IPv4 header = 20-byte fixed + optional part (<= 40 bytes) IHL IP header length in units of 32-bit words Type of service field (expedited/assured; congestion notification) Total length of the datagram in bytes (including data) Identification of the datagram (all fragments have the same ID) Fragment information for reassembling fragmented datagram Time to live hop counter Protocol TCP/UDP (etc.) Checksum of just the header Source/destination addresses Optional Mostly ignored by modern equipment gtl1–R756 W7L2 — Network & Transport layer 2016–03–13 6 / 17 Network layer in the internet Datagram format IPv4 Header Version IHL Type of service Total length Identification Time to live Protocol Fragment offset Header checksum Source address Destination address Options (0 or more words) D F M F 32 Bits gtl1–R756 W7L2 — Network & Transport layer 2016–03–13 7 / 17 Network layer in the internet IP Addresses IPv4 Addresses Each host and router has a 32 bit IP address IPv4 address = network number + host number Written in dotted decimal notation, e.g. 143.210.72.91 Each byte written as a decimal number in [0, 255] Five classes of networks: Class A 128 networks with 16 million hosts each Class B 16384 networks with 64K hosts each Class C 2 million networks with 254 hosts each Class D multicast addresses Class E reserved for future use Each network may split into subnets gtl1–R756 W7L2 — Network & Transport layer 2016–03–13 8 / 17 Network layer in the internet IP Addresses Special addresses Certain values for the fields are special: All 0s represents this host; A network field of all 0s represents this network; All 1s means broadcast on the local network; A host field of all 1s means broadcast on a different network; A host field of 127 means a test loopback packet. 127.0.0.1 is loopback to this host (localhost) 10.x.x.x. 192.168.x.x are strictly local and non-routable gtl1–R756 W7L2 — Network & Transport layer 2016–03–13 9 / 17 Network layer in the internet IP Addresses IP Address Format 32 Bits Range of host addresses 1.0.0.0 to 127.255.255.255 128.0.0.0 to 191.255.255.255 192.0.0.0 to 223.255.255.255 224.0.0.0 to 239.255.255.255 240.0.0.0 to 255.255.255.255 Class 0 Network Host 10 Network Host 110 Network Host 1110 Multicast address 1111 Reserved for future use A B C D E gtl1–R756 W7L2 — Network & Transport layer 2016–03–13 10 / 17 Routing in the internet Routing in the Internet Within an Autonomous System (AS), routing is done by an interior gateway routing protocol Between different ASes, routing is done by an exterior gateway routing protocol gtl1–R756 W7L2 — Network & Transport layer 2016–03–13 11 / 17 Routing in the internet Interior Gateway Routing Protocol Interior Gateway Routing Protocol Open Shortest Path First (OSPF): recommended protocol Each AS is split into areas Each backbone area is connected to all other areas Each router holds information about links in its own area. It can therefore calculate the shortest path to any other router in its area For inter-area communications, three steps are used: Go across the source area to the backbone Go across the backbone to the destination area Go across the destination area to the destination gtl1–R756 W7L2 — Network & Transport layer 2016–03–13 12 / 17 Routing in the internet Interior Gateway Routing Protocol Autonomous Systems and Areas AS 1 AS 2 AS 3 AS 4 Internal router Backbone Backbone router Area Area border router AS boundary router BGP protocol connects the ASes gtl1–R756 W7L2 — Network & Transport layer 2016–03–13 13 / 17 Routing in the internet Exterior Gateway Routing Protocol Exterior Gateway Routing Protocol Each AS has a boundary router, linked with boundary routers in other ASes They are responsible for routing between ASes, using Border Gateway Protocol (BGP) BGPs are complicated by policy considerations, e.g, Telephone companies might only carry traffic for customers Might have commercial reasons to de-prioritise competing services BGP routers exchange info about the routes they use Each router then decide where to send packets, selecting the shortest path within its policy constraints gtl1–R756 W7L2 — Network & Transport layer 2016–03–13 14 / 17 IPv6 Internet Protocol Version 6 — IPv6 IPv4 suffers from a number of shortcomings, which version 6 (IPv6) seeks to fix: Uses 16 byte addresses Provides better security Pays more attention to different types of service, e.g. real-time data Supports mobile agents better Simplifies header for routers to process packets faster gtl1–R756 W7L2 — Network & Transport layer 2016–03–13 15 / 17 IPv6 IPv6 Header 32 Bits Version Traffic class Flow label Payload length Next header Hop limit Source address (16 bytes) Destination address (16 bytes) gtl1–R756 W7L2 — Network & Transport layer 2016–03–13 16 / 17 Summary Summary The Internet uses IP to pass datagrams IPv4 and IPv6 header IP address = network number + host number Routing in the Internet is based on autonomous systems The interior gateway routing protocol (OSPF): intra-AS routing The exterior gateway routing protocol (BGP): inter-AS routing gtl1–R756 W7L2 — Network & Transport layer 2016–03–13 17 / 17 CO2017 — Week 8L1 — Transport Layer Dr Gilbert Laycock (gtl1) 2016–03–15 gtl1–R762 W8L1 — Transport Layer 2016–03–15 1 / 17 Overview Context Operating systems Networking Introduction Layered models Physical & Data link layer Network Layer Transport Layer, Application Layer Client-Server programming gtl1–R762 W8L1 — Transport Layer 2016–03–15 2 / 17 Overview Recap and Lecture Overview Recap: The network layer Passes packets over the network using routing algorithms Takes care of congestion control Uses the IP protocol in the Internet Overview of this lecture Main functions of the transport layer Transport layer services Transport addressing gtl1–R762 W8L1 — Transport Layer 2016–03–15 3 / 17 Aims Introduction to the Transport Layer Aims to provide efficient, reliable, cost-effective services to processes in the application layer Services: connectionless or connection-oriented Functions: sequencing, error and congestion control Application/transport interface Transport/network interface Application (or session) layer Transport entity Transport address Network address Network layer Application (or session) layer Transport entity Network layer TPDU Transport protocol Host 1 Host 2 gtl1–R762 W8L1 — Transport Layer 2016–03–15 4 / 17 Aims Protocol headers Nesting of Protocol Headers Transport layer entities exchange info in the unit of Transport Protocol Data Unit (TPDU) Nesting of TPDus, packets and frames: Frame header Packet header TPDU header TPDU payload Frame payload Packet payload gtl1–R762 W8L1 — Transport Layer 2016–03–15 5 / 17 Aims Comparison with Network Layer Transport Layer cf. Network Layer Similarities: Both do connectionless or connection-oriented services For connection-oriented services: connection establishment, data transfer and release Addressing and flow control gtl1–R762 W8L1 — Transport Layer 2016–03–15 6 / 17 Aims Comparison with Network Layer Transport Layer cf. Network Layer Differences: Network layer may be unreliable: routers may crash, and packets may be discarded to reduce congestion. Transport layer provides a reliable service Transport layer entities run entirely on end nodes, i.e. user machines, network layer entities mostly run on routers Transport layer primitives are intended for programs and programmers, must be convenient to use gtl1–R762 W8L1 — Transport Layer 2016–03–15 7 / 17 Aims Example Transport Layer Primitives Transport Service Primitives Various service primitives, e.g, Berkley sockets gtl1–R762 W8L1 — Transport Layer 2016–03–15 8 / 17 Aims Comparison with Data-Link Layer Transport Layer cf. Data Link Layer Similar protocols: sequencing, error and flow control (e.g. sliding window protocol) However, in the transport layer: Addressing is more of an issue Connection establishment is harder More storage space (buffering) in the subnet ⇒ more variation in delay Routers have to deal with more traffic, so flow and congestion control become bigger issues Router Router Physical communication channel Host (a) (b) Subnet gtl1–R762 W8L1 — Transport Layer 2016–03–15 9 / 17 Making and releasing connections Transport Layer Addressing Transport service corresponds to a Transport Service Access Point (TSAP) Transport address = TSAP + Network SAP (NSAP) A service address can be obtained from a name server New services must be registered with the name server Application process Application layer Transport connection TSAP 1522 TSAP 1208 NSAP NSAP Transport layer Network layer Data link layer Physical layer Server 1 Host 1 Host 2 Server 2 TSAP1836 gtl1–R762 W8L1 — Transport Layer 2016–03–15 10 / 17 Making and releasing connections Transport Layer Address in the Internet Internet TCP addresses: IP address + local port Some ports (with number below 1024) are reserved for specific applications gtl1–R762 W8L1 — Transport Layer 2016–03–15 11 / 17 Making and releasing connections Example of transport layer connection Transport Connection Scenario A time server example 1 A time server process (Server A) on host 2 attaches itself to TSAP 1522 using LISTEN 2 An application (client) process on host 1 issues a CONNECT request specifying TSAP 1208 as the source, and TSAP 1522 on host 2 as the destination 3 The application (client) process on host 1 sends a request for the time 4 The time server responds with the current time 5 The transport connection is then released gtl1–R762 W8L1 — Transport Layer 2016–03–15 12 / 17 Making and releasing connections Making a connection Establishing a Connection Hosts carry out a three-way handshake procedure 1 Host 1 sends a connection request (CR) with its initial sequence number 2 Host 2 sends an acknowledgement (ACK) with Host 1’s number, plus its own sequence number 3 Host 1 sends its first data with both sequence numbers If an old TPDU (datagram) arrives, the sequence number will be out of date and ignored Both sides can try to establish a connection simultaneously gtl1–R762 W8L1 — Transport Layer 2016–03–15 13 / 17 Making and releasing connections Making a connection Three-Way Handshake Protocol T im e DATA (seq = x, ACK = y) AC K (s eq = y , AC K = x) CR (seq = x) Host 1 Host 2 REJECT (ACK = y) DATA (seq = x, ACK = z) AC K ( se q = y, AC K = x) CR (seq = x) Host 1 Host 2 REJECT (ACK = y) AC K ( seq = y , AC K = x) CR (seq = x) Host 1 Host 2 Old duplicate Old duplicate Old duplicate (a) (b) (c) (a) Normal, (b) Duplicate CR, and (c) duplicate CR and ACK gtl1–R762 W8L1 — Transport Layer 2016–03–15 14 / 17 Making and releasing connections Releasing a connection Releasing a Connection Neither side can release a connection until both have stopped sending data Suppose host 1 wants to stop first: 1 Host 1 sends a disconnect request (DR) and starts a timer 2 Host 2 acknowledges by sending its own DR and also starts a timer 3 Host 1 sends an acknowledgement (ACK), and the connection is released What happens if some parts of the sequence get lost? If no acknowledgement is received for a DR (either direction), the host will timeout and resend its DR. If a host times out enough times, just drop the connection gtl1–R762 W8L1 — Transport Layer 2016–03–15 15 / 17 Making and releasing connections Releasing a connection Releasing a Connection—Four Scenarios DR ACK ACK Host 1 Host 2 DR DR Send DR + start timer Send DR + start timer Send ACK Release connection (Timeout) release connection (Timeout) release connection (N Timeouts) release connection ( Timeout) send DR + start timer Release connection DR DR Host 1 Host 2 DR Send DR + start timer Send DR & start timer Send DR & start timer Send DR & start timer Send ACK Release connection Release connection DR ACK Host 1 Host 2 DR Send DR + start timer Send DR + start timer Send ACK Release connection Lost Lost ( Timeout) send DR + start timer DR Host 1 Host 2 Send DR + start timer Lost Lost (a) (b) (c) (d) gtl1–R762 W8L1 — Transport Layer 2016–03–15 16 / 17 Summary Summary The transport layer provides efficient, reliable, cost-effective services to processes in the application layer Transport layer address: TSAP + NSAP Connection establishing and releasing requires a strict protocol gtl1–R762 W8L1 — Transport Layer 2016–03–15 17 / 17 CO2017 — Week 8L2 — Client/Server structure; Java Structures Dr Gilbert Laycock (gtl1) 2016–03–08 gtl1–R738 W8L2 — Client/Server 2016–03–08 1 / 33 Overview Context Operating systems Networking Introduction Layered models Physical & Data link layer Network Layer Transport Layer, Application Layer Client-Server programming (using the transport/application layers) gtl1–R738 W8L2 — Client/Server 2016–03–08 2 / 33 Overview Recap and Lecture Overview Recap Discussed how to do concurrent programming Concurrent programming with threads running on a single computer Java supports concurrent programming; synchronized, wait, notify, etc. Overview of this lecture Introduction to distributed programming Client-Server paradigm Java Sockets gtl1–R738 W8L2 — Client/Server 2016–03–08 3 / 33 Client-Server paradigm Concurrency and Distribution Threads provide concurrency within a program on a computer Threads are not a mechanism for distribution, e.g, it is not possible to spontaneously create a thread on a different computer However, concurrency is critical in distributed systems E.g, in client-server systems multiple threads may run concurrently on both the client and server sides gtl1–R738 W8L2 — Client/Server 2016–03–08 4 / 33 Client-Server paradigm Simple Client-Server System RequestsServices 1 ServerClient * A number of clients request service from a server Server may not be running on the same host as client — remote server Server: a program providing a service for other programs, e.g, expensive calculations or database access Server receives a request from a client and processes it Server sends the service result back to the client gtl1–R738 W8L2 — Client/Server 2016–03–08 5 / 33 Client-Server paradigm Server side Outline for Server side code public class Server { public static void main (String[] args) { while (true) { System.out.println("Waiting for a connection..."); // code to wait and then accept // a client connection goes here Connection client = .... System.out.println("Dealing with a client"); // code to deal with the connection goes here System.out.println("Finished with client"); cl.close(); } } } N.B, the Connection class is not a real Java class. gtl1–R738 W8L2 — Client/Server 2016–03–08 6 / 33 Client-Server paradigm Server side Servers and Handlers Server is required to serve many clients Need an architecture in which the server does not simply process individual requests sequentially Instead, server should be continuously available and able to handle several requests at a time Threads are employed to achieve this goal Server does not process the request on its own It delegates each request to another Handler class, which performs the real service Hence, the server needs only a short time to accept a task, pass it on, and then is directly available again gtl1–R738 W8L2 — Client/Server 2016–03–08 7 / 33 Client-Server paradigm Server side Client-Server System with Handler Calls 1 IsHandledBy Handler 1 1 1..* Client Server1 RequestsServices * gtl1–R738 W8L2 — Client/Server 2016–03–08 8 / 33 Client-Server paradigm Server side Interactions Between Clients, Server & Handlers remoteCall() returnService() localPassOn() h1:handler localPassOn() c1:Client h2:handler:Serverc2:Client remoteCall() returnService() gtl1–R738 W8L2 — Client/Server 2016–03–08 9 / 33 Client-Server paradigm Outline code for Server and Handler Outline Code for Server public class Server { public static void main(String[] args) { while (true) { System.out.println("Waiting for a connection"); // code to wait and then accept // a client connection goes here Connection cl = ....; // create a new thread to handle request Handler h = new Handler(cl); h.start(); } } } gtl1–R738 W8L2 — Client/Server 2016–03–08 10 / 33 Client-Server paradigm Outline code for Server and Handler Outline Code for Handler class Handler extends Thread { private Connection cl; public Handler(Connection c) { cl = c; // other contstructor tasks } public void run() { System.out.println("Doing some work... "); // work involves interaction with client connection cl ... System.out.println("... done."); cl.close(); } } gtl1–R738 W8L2 — Client/Server 2016–03–08 11 / 33 Client-Server paradigm Client side On the Client Side Concurrency may be required on the client side too With normal synchronous method calls, a client must wait until the called process has completed the task assigned to it, and is blocked for all of this time Sometimes the client is supposed to continue its task while the request is being processed. In these cases, asynchronous method calls should be used with concurrency gtl1–R738 W8L2 — Client/Server 2016–03–08 12 / 33 Client-Server paradigm Client side Outline Code for simple synchronous client public class Client { public static void main(String[] args) { // make connection to server Connection s = .... // 1st message to server ... // wait for 1st response from server ... // etc, more interaction with server ... // interaction complete; the end s.close(); } } gtl1–R738 W8L2 — Client/Server 2016–03–08 13 / 33 Client-Server paradigm Client side Model for the Client Side Client makes a call via a caller thread. The caller thread executes a method call synchronously and runs concurrently with the client thread The client does not wait, instead it can do other things Two possible mechanisms to get the service result Polling: Client continuously asks the caller whether the result has arrived. If not yet, it may do other things and then check again. However, if the result has arrived, it can read and utilise it Callback: After making a call, the client continues to do other tasks. The caller calls a method of the client when it receives the result. gtl1–R738 W8L2 — Client/Server 2016–03–08 14 / 33 Client-Server paradigm Client side Class Diagram of the Whole Model Handler ServerClient Caller Calls 1 * 1 1 1 RequestsServices IsHandledBy Calls 1 1 1..* gtl1–R738 W8L2 — Client/Server 2016–03–08 15 / 33 Client-Server paradigm Client side Interaction for the Model with Callback c1:Client :Server:Caller remoteCall() localCall() localPassOn() returnResult() callback() h1:Handler gtl1–R738 W8L2 — Client/Server 2016–03–08 16 / 33 Client-Server paradigm Client side Outline Code for Client using polling public class Client { private int answer; public static void main(String[] args) { Client client = new Client(); Caller c1 = new Caller(client); c1.start(); while (c1.returned()==false) { // polling System.out.println("Do some other work..."); // other work that does not require response from server } // deal with response from server System.out.println("Received result by polling caller."); System.out.println(answer); } } gtl1–R738 W8L2 — Client/Server 2016–03–08 17 / 33 Client-Server paradigm Client side Outline Code for Caller (used with polling) class Caller extends Thread { private Client client; private boolean returned = false; public Caller(Client cl) { client = cl;} public void run() { Connection s = ... ; // make call to server // wait for response from server ... // change state of client data structure based on response client.answer=10; s.close(); returned = true; } public boolean returned() { return returned; } } gtl1–R738 W8L2 — Client/Server 2016–03–08 18 / 33 Client-Server paradigm Client side Outline Code for Client using callback public class Client { private int answer; public void callback(int a) { System.out.println("Received result by callback from a caller."); answer = a; System.out.println(answer); } public static void main(String[] args) { Client client = new Client(); Caller c2 = new Caller(client); c2.start(); System.out.println("Do lots of other work"); } } gtl1–R738 W8L2 — Client/Server 2016–03–08 19 / 33 Client-Server paradigm Client side Outline Code for Caller using callback class Caller extends Thread { private Client client; public Caller(Client cl) { client = cl;} public void run() { Connection s = ...; // make connection to server // wait for response from server ... // use the response from the server answer = 10; s.close(); client.callback(answer); // callback to client } } gtl1–R738 W8L2 — Client/Server 2016–03–08 20 / 33 Sockets Concept of Socket The basic prerequisite for distributed programming is to transfer data between computers Each computer in a TCP/IP network has a IP address To address exact processes on a computer, we need port numbers, which are managed by operating systems and allocated to processes A socket is an endpoint of a communication connection between two computers and is identified by an IP address and a port number A connection over a TCP/IP network is represented by a pair of sockets From the programmer’s viewpoint, a socket represents the mechanism to transfer data between computers gtl1–R738 W8L2 — Client/Server 2016–03–08 21 / 33 Sockets Java Sockets Java Sockets (client side view) Java Sockets serve as communication channels between computers A class called Socket is contained in the java.net package - used for the client side The constructor of Socket takes two parameters: IP address of the server host and port number of the server socket For this to work, on the server side, a socket must already be set up and listening for the connection request gtl1–R738 W8L2 — Client/Server 2016–03–08 22 / 33 Sockets Java Sockets Java Sockets (server side view) To set up a user-defined server socket, we need a ServerSocket instance, also provided in java.net The server can listen for incoming connection requests by invoking accept(); which will return with a new Socket for the new connection Commonly a server is set to endlessly listen for connections the accept() method blocks until a new connection request arrives int port = 1234; ServerSocket server = new ServerSocket(port); while (true) { System.out.println("Waiting for client..."); Socket client = server.accept(); // deal with connection from client } gtl1–R738 W8L2 — Client/Server 2016–03–08 23 / 33 Sockets Java Sockets Back to the client side: creating a connection After a ServerSocket is set up on the server, a client can address it to establish a connection Socket server = new Socket("serverDNS", 1234); System.out.println("Connection to " + server.getInetAddress() ); Or InetAddress addr = InetAddress.getByName("serverDNS"); Socket server = new Socket(addr, 1234); System.out.println("Connection to " + server.getInetAddress() ); gtl1–R738 W8L2 — Client/Server 2016–03–08 24 / 33 Sockets Java Sockets Streams To exchange data over sockets, Java uses streams Streams are an abstraction for arbitrary data sequences, whether from or to a socket, the console, the file system, or a storage medium The java.io package has InputStream and OutputStream classes for input and output respectively. They are abstract classes, which cannot be instantiated directly but only via their children All other streams are derived from these two classes They handle data as bytes with read() and write() to read and write bytes (generally in arrays) gtl1–R738 W8L2 — Client/Server 2016–03–08 25 / 33 Sockets Time Server A Time Server Example A time server runs on a host and transmits the current time to clients when they request it A server program, TimeServer, creates a ServerSocket with a port number and then waits for incoming requests via the accept() method When a request arrives, a socket (a connection with the client) is created. The current time is converted into a string, and transferred via the socket using an OutputStreamWriter A client connects with the TimeServer by creating a socket with the server’s IP address and port number. It reads a String from a BufferedReader and displays it. gtl1–R738 W8L2 — Client/Server 2016–03–08 26 / 33 Sockets Time Server TimeServer import java.net.*; import java.io.*; import java.util.*; // Date class public class TimeServer { public static void main (String[] args) throws IOException { int port = 1234; ServerSocket server = new ServerSocket(port); while(true) { System.out.println("Waiting for client..."); Socket client = server.accept(); System.out.println("Client from "+ client.getInetAddress() + " connected."); Writer out = new OutputStreamWriter(client.getOutputStream()); Date date = new Date(); out.write(String.format("%s%n",date)); out.flush(); // sends out over OutputStream } } } gtl1–R738 W8L2 — Client/Server 2016–03–08 27 / 33 Sockets Time Server TimeClient import java.net.*; import java.io.*; public class TimeClient { public static void main(String[] args) throws IOException { Socket server = new Socket("serverDNSAddress",1234); // InetAddress addr // = InetAddress.getByName("serverDNSAddress"); // Socket server = new Socket(addr, 1234); System.out.println("Connected to " + server.getInetAddress()); BufferedReader in = new BufferedReader( new (InputStreamReader(server.getInputStream(), "UTF-8"))); String date = in.readLine(); System.out.println("Server said: " + date); } } gtl1–R738 W8L2 — Client/Server 2016–03–08 28 / 33 Sockets Time Server Behaviour of The Program Assume the host of TimeServer is called "sun", and the Client is on "lin": sun> java timeServer
sun| waiting for client….

lin> java TimeClient
lin| Connected to 134.100.11.1 // something like this

sun| Client from 134.100.11.2 // something like this
sun| Waiting for client…

lin| Server said: Thur Feb 21 10:00:00 GMT 2002

gtl1–R738 W8L2 — Client/Server 2016–03–08 29 / 33

Sockets Filters

Streams and Filters

Beyond the exchange of byte-based data, filters are used to
derive other streams

For transmitting simple types as int, long, String,
DataOutputStream provides a write method for each of these
types: writeInt(), writeLong() and writeChar()

For transmitting Strings, usually the UTF-8 format is used, which
transfers the characters in Unicode, for which writeUTF()
method is available

Similarly, DataInputStream exists with methods readInt(),
readLong(), readChar(), readUTF()

These methods convert different types into byte sequences for
simple streams, and vice versa

gtl1–R738 W8L2 — Client/Server 2016–03–08 30 / 33

Sockets Buffered Streams

Buffered Streams

For efficiency, a data transfer should not be triggered for every
individual byte, but the data should be stored in a buffer and be
transmitted when a suitable quantity has been collected

A Java buffered filter class BufferedOutputStream provides this
functionality, which by default holds an intermediate memory of
512 bytes

It triggers the transmission of data only when the buffer is full or
its flush() method is called

A corresponding filter BufferedInputStream is also available

There are other filter classes too

gtl1–R738 W8L2 — Client/Server 2016–03–08 31 / 33

Sockets Buffered Streams

Common usage

It is common to be sending simple text messages back and
forward in a protocol

BufferedReader rdr =
new BufferedReader(
new InputStreamReader(server.getInputStream(),

“UTF-8”));
Writer out =

new OutputStreamWriter(server.getOutputStream());

End each line with “\r\n”

After writing data which requires a response, call out.flush()

You can use rdr.readline() to read data one “line” at a time.

gtl1–R738 W8L2 — Client/Server 2016–03–08 32 / 33

Summary

Summary

The Client-Server paradigm sets up distributed parts of the
system

Client and Server communicate over a Socket using specific ports

Server waits for connections on its port

Client initiates connection with server

Server sets up a Socket pair to communicate with the client in
Streams

Client can use polling or callbacks to react to data from server

Use Filters and BufferedStreams for more complex data types

Need to define a protocol to describe the interchange of data
between client and server

gtl1–R738 W8L2 — Client/Server 2016–03–08 33 / 33

CO2017 — Week 9L1 — Application Layer

Dr Gilbert Laycock (gtl1)

2016–04–25

gtl1–R820 W9L1 — Application Layer 2016–04–25 1 / 19

Overview

Context

Operating systems

Networking

Introduction
Layered models

Physical & Data link layer
Network Layer
Transport Layer
Application Layer

Client-Server programming

gtl1–R820 W9L1 — Application Layer 2016–04–25 2 / 19

Overview

Recap and Lecture Overview

Recap: The transport layer
Transport layer addresses: IP address plus port
client-server architecture
sockets
TCP, UDP

Overview of this lecture
Some specific application layer protocols
DNS
email (SMTP)
HTTP

gtl1–R820 W9L1 — Application Layer 2016–04–25 3 / 19

Domain Name System (DNS)

Domain Name System

Transport layer refers to hosts by IP address.

But people would rather use symbolic names such as
www.cs.le.ac.uk, known as Domain Name System (DNS)
addresses.

The DNS name space is a hierarchical scheme, administered by
domain registrars

Generic US based com, edu, org, etc.
International representing countries, e.g. uk, aus, jp. Countries

have their own internal divisions, and system of
registrars.

gtl1–R820 W9L1 — Application Layer 2016–04–25 4 / 19

Domain Name System (DNS)

Generic Countries

int com edu gov mil org net jp us nl . . .

ac co oce vuieeesun

eng nec

csl

yale

engcs

ai linda

robot

acm

jack jill keio

cs

pc24

flits fluit

cs

Zones in the DNS system

gtl1–R820 W9L1 — Application Layer 2016–04–25 5 / 19

Domain Name System (DNS)

DNS and IP addresses

DNS name servers manage a database relating DNS addresses to
IP addresses

Name server is authoratative regarding local addresses

For remote addresses a name server will query other name
servers

Addresses obtained from remote DNS servers can be cached,
but with an expiry date/time so the information will be kept up to
date

gtl1–R820 W9L1 — Application Layer 2016–04–25 6 / 19

Domain Name System (DNS)

Originator
VU CS

name server
Yale

name server
Yale CS

name server
Edu

name server

cs.vu.nl edu-server.net yale.edu cs.yale.eduflits.cs.vu.nl

1

8

2

7

3

6

4

5

How a resolver looks up a remote name in eight steps.

gtl1–R820 W9L1 — Application Layer 2016–04–25 7 / 19

e-mail

Electronic mail

There are several subsystems of e-mail systems:

The user agent (MUA) which allows users to read and send e-mail,
normally giving a user-friendly interface;

The message transfer agent (MTA) which is responsible for
transferring e-mail between hosts.

gtl1–R820 W9L1 — Application Layer 2016–04–25 8 / 19

e-mail

Message formats

Each e-mail address has two parts:

Header Containing addressing information, and meta-data
regarding the message.

Body The message content.

MUA displays only “interesting” parts of the header, but all of the
body.

MTA largely ignores the body.

gtl1–R820 W9L1 — Application Layer 2016–04–25 9 / 19

e-mail

Common mail headers:

To: the e-mail address(es) of the primary recipient(s);

Cc: the e-mail address(es) of secondary recipient(s);

Bcc: e-mail address(es) for blind carbon copies;

From: name and e-mail address of person who created the message;

Sender: e-mail address of person who sent the e-mail;

Received: line added by each transfer agent along the route;

Return-path: to identify a path back to the sender;

Date: the date and time the mesasge was sent;

Reply-To: e-mail address for replies;

Message-Id: unique message identifier;

Subject: summary of the message.

gtl1–R820 W9L1 — Application Layer 2016–04–25 10 / 19

e-mail

Message transfer agents (MTAs)

Mail application establishes a transport layer connection to a
socket on the remote server.

Port 25 is used for un-encrypted Simple Mail Transfer
Protocol SMTP connections.

Simple textual protocol with messages passed back and forth
between client and server:

Messages from client to server mostly in English words;
Messages from server to client mostly numeric.

Protocol defines the order and meaning of these messages.

gtl1–R820 W9L1 — Application Layer 2016–04–25 11 / 19

e-mail

Example SMTP session

S → C : 220 (server ready)
C → S : HELO (hello)
S → C : 250 (ok)
C → S : MAIL FROM: ⟨alice@abc.com⟩
S → C : 250 (ok)
C → S : RCPT TO: ⟨bob@xyz.com⟩
S → C : 250 (ok)
C → S : DATA (I’m ready to send)
S → C : 354 (send the mail)
C → S : From: alice@abc.com (header)

To: bob@xyz.com
Subject: Hello

(blank line between header and body)
Hello Bob! (message body)
. (end of message)

S → C : 250 (ok)
C → S : QUIT (goodbye)
S → C : 221 (goodbye)

gtl1–R820 W9L1 — Application Layer 2016–04–25 12 / 19

e-mail

E-mail gateways

Not all networks use the same format for e-mail messages, that is,
they don’t all use SMTP: e.g. POP, IMAP and variants

Different networks using different e-mail protocols can be connected
together by e-mail gateways, which translate messages from one
format to another.

Internet User
agent

Message
transfer

agent

MailboxPermanent
connection

Sending
host

(a) Receiving
host

SMTP

Internet User
agent

Message
transfer

agent

MailboxSending
host

(b) ISP’s
machine

User’s
PC

SMTP POP3
POP3
server

Dial-up
connection

Transferring email using an application layer email gateway.

gtl1–R820 W9L1 — Application Layer 2016–04–25 13 / 19

WWW and http

HyperText Markup Language (HTML)

Most Web documents are written in HTML. There are two main
features of HTML:

Markup commands are commands that control how the text will
appear on screen; e.g. “hello” will result in
“hello” (in bold font).

Hyperlinks e.g. CS will
produce the text “CS”; clicking on it will load the Web
page http://www.cs.le.ac.uk/.

gtl1–R820 W9L1 — Application Layer 2016–04–25 14 / 19

WWW and http

Uniform Resource Locators (URLs)

Web documents are referred to by a Uniform Resource
Locator

First part of the URL is the name of the protocol typically http

Next comes the address of the host where the resource can be
found, e.g. www.cs.le.ac.uk; may include extra details such as
username and password

Finally is the path on the host of the resource; e.g. a filename

gtl1–R820 W9L1 — Application Layer 2016–04–25 15 / 19

WWW and http

Example URLs

Name Used for Example

http Hypertext http://www.cs.vu.nl/∼ast/
ftp FTP ftp://ftp.cs.vu.nl/pub/README

file Local file file:///usr/suzanne/prog.c

news News group news:comp.os.minix

mailto Sending email mailto:kim@acm.org

ssh Secure remote login ssh:user@www.w3.org

gtl1–R820 W9L1 — Application Layer 2016–04–25 16 / 19

WWW and http

HyperText Transfer Protocol (HTTP)

To access a web resource on a remote server:

Client establishes a transport layer application (e.g. TCP) to port
80 on server

An HTTP daemon (web server) should be listening

Client and server conduct an HTTP exchange
Client commands include:

GET request to read a page;
HEAD request to read a page’s header;

PUT request to upload a page (include authorization)

Server responses include:

status line (numeric code), e.g. 200 (ok), 400 (bad request), 404
(not found)
data response (the requested page)

gtl1–R820 W9L1 — Application Layer 2016–04–25 17 / 19

WWW and http

More on HTTP

HTTP is a request-response protocol

client sends a request;
server sends a corresponding response

HTTP is stateless — the server does not need to keep any
record of the status of a connection once the response is sent

Use application level techniques on the server to manage session
state — cookies, hidden form elements, etc.

HTTP v1.1 and newer allow for persistent connections so that

multiple request/response pairs can be combined;
pipe-lining means data can be streamed in a response.

gtl1–R820 W9L1 — Application Layer 2016–04–25 18 / 19

Summary

Summary

DNS system

email (SMTP) MTP

HTTP for www.

gtl1–R820 W9L1 — Application Layer 2016–04–25 19 / 19