程序代写代做代考 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:CO2017DemosBuffer.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
DemosBuffer.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
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 “
”
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
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
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
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
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
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 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
