Transcript virtual machine - Regis University: Academic Web Server for Faculty

CS-430: Operating Systems
Week 8
Dr. Jesús Borrego
Lead Faculty, COS
Regis University
1
scis.regis.edu ● [email protected]
Topics
• Chapter 16 – Virtual Machines
• Chapter 17 – Distributed Systems
• Final project presentation due this week
▫ 20 min. each, 3/hr, 5 minute break between each
▫ Provide presentation file before class
• Final Exam – take home, due Monday, 12/16,
midnight
2
Chapter 16 – Virtual Machines
3
Chapter 16: Virtual Machines
• Overview
• History
• Benefits and Features
• Building Blocks
• Types of Virtual Machines and Their
Implementations
• Virtualization and Operating-System
Components
• Examples
4
Overview
• Fundamental idea – abstract hardware of a single
computer into several different execution
environments
▫ Similar to layered approach
▫ But layer creates virtual system (virtual machine,
or VM) on which operation systems or applications
can run
5
Overview (Cont’d)
• Several components
▫ Host – underlying hardware system
▫ Virtual machine manager (VMM) or
hypervisor – creates and runs virtual machines by
providing interface that is identical to the host
 (Except in the case of paravirtualization)
▫ Guest – process provided with virtual copy of the
host
 Usually an operating system
• Single physical machine can run multiple
operating systems concurrently, each in its own
virtual machine
6
System Models
Non-virtual machine
7
Virtual machine
Implementation of VMMs
• Vary greatly, with options including:
▫ Type 0 hypervisors - Hardware-based solutions
that provide support for virtual machine creation
and management via firmware
 IBM LPARs and Oracle LDOMs are examples
▫ Type 1 hypervisors - Operating-system-like
software built to provide virtualization
 Including VMware ESX, Joyent SmartOS, and Citrix XenServer
8
Implementation of VMMs (Cont’d)
▫ Type 1 hypervisors – Also includes generalpurpose operating systems that provide standard
functions as well as VMM functions
 Including Microsoft Windows Server with HyperV and RedHat Linux with KVM
▫ Type 2 hypervisors - Applications that run on
standard operating systems but provide VMM features
to guest operating systems
 Includeing VMware Workstation and Fusion, Parallels Desktop, and Oracle
VirtualBox
9
Implementation of VMMs (cont.)
• Other variations include:
▫ Paravirtualization - Technique in which the guest operating system is
modified to work in cooperation with the VMM to optimize performance
▫ Programming-environment virtualization - VMMs do not virtualize
real hardware but instead create an optimized virtual system
 Used by Oracle Java and Microsoft.Net
▫ Emulators – Allow applications written for one hardware environment to
run on a very different hardware environment, such as a different type of
CPU
▫ Application containment - Not virtualization at all but rather provides
virtualization-like features by segregating applications from the operating
system, making them more secure, manageable
 Including Oracle Solaris Zones, BSD Jails, and IBM AIX WPARs
• Much variation due to breadth, depth and
importance of virtualization in modern computing
10
History
• First appeared in IBM mainframes in 1972
• Allowed multiple users to share a batch-oriented
system
• Formal definition of virtualization helped move it
beyond IBM
1.A VMM provides an environment for programs that
is essentially identical to the original machine
2.Programs running within that environment show
only minor performance decreases
3.The VMM is in complete control of system resources
11
History (Cont’d)
• In late 1990s Intel CPUs fast enough for
researchers to try virtualizing on general purpose
PCs
▫ Xen and VMware created technologies, still used
today
▫ Virtualization has expanded to many OSes, CPUs,
VMMs
12
Benefits and Features
• Host system protected from VMs, VMs protected
from each other
▫ I.e. A virus less likely to spread
▫ Sharing is provided though via shared file
system volume, network communication
13
Benefits and Features (Cont’d)
• Freeze, suspend, running VM
▫ Then can move or copy somewhere else and resume
▫ Snapshot of a given state, able to restore back to that
state
 Some VMMs allow multiple snapshots per VM
▫ Clone by creating copy and running both original
and copy
• Great for OS research, better system development
efficiency
• Run multiple, different OSes on a single machine
▫ Consolidation, app dev, …
14
Benefits and Features (cont.)
• Templating – create an OS + application VM,
provide it to customers, use it to create multiple
instances of that combination
• Live migration – move a running VM from
one host to another!
▫ No interruption of user access
• All those features taken together -> cloud
computing
▫ Using APIs, programs tell cloud infrastructure
(servers, networking, storage) to create new
guests, VMs, virtual desktops
15
Building Blocks
• Generally difficult to provide an exact
duplicate of underlying machine
• Especially if only dual-mode operation available
on CPU
• But getting easier over time as CPU features and
support for VMM improves
• Most VMMs implement virtual CPU (VCPU)
to represent state of CPU per guest as guest
believes it to be
• When guest context switched onto CPU by VMM,
information from VCPU loaded and stored
• Several techniques, as described in next slides
16
Building Block – Trap and Emulate
• Dual mode CPU means guest executes in
user mode
▫ Kernel runs in kernel mode
▫ Not safe to let guest kernel run in kernel
mode too
▫ So VM needs two modes – virtual user mode
and virtual kernel mode
 Both of which run in real user mode
▫ Actions in guest that usually cause switch to
kernel mode must cause switch to virtual
kernel mode
17
Trap-and-Emulate (cont.)
• How does switch from virtual user mode to
virtual kernel mode occur?
▫ Attempting a privileged instruction in user mode
causes an error -> trap
▫ VMM gains control, analyzes error, executes
operation as attempted by guest
▫ Returns control to guest in user mode
▫ Known as trap-and-emulate
▫ Most virtualization products use this at least in
part
18
Trap-and-Emulate (cont.)
• User mode code in guest runs at same speed as if
not a guest
• But kernel mode privilege mode code runs
slower due to trap-and-emulate
▫ Especially a problem when multiple guests
running, each needing trap-and-emulate
• CPUs adding hardware support, mode CPU
modes to improve virtualization performance
19
Trap-and-Emulate Virtualization Implementation
20
Building Block – Binary Translation
• Some CPUs don’t have clean separation between
privileged and nonprivileged instructions
▫ Earlier Intel x86 CPUs are among them
 Earliest Intel CPU designed for a calculator
▫ Backward compatibility means difficult to
improve
▫ Consider Intel x86 popf instruction
 Loads CPU flags register from contents of the stack
 If CPU in privileged mode -> all flags replaced
 If CPU in user mode -> on some flags replaced
 No trap is generated
21
Binary Translation (cont.)
Other similar problem instructions we will call
special instructions
Caused trap-and-emulate method considered
impossible until 1998
Binary translation solves the problem
Basics are simple, but implementation very complex
22
Binary Translation (cont.)
1. If guest VCPU is in user mode, guest can run
instructions natively
2. If guest VCPU in kernel mode (guest believes it is in
kernel mode)
1. VMM examines every instruction guest is about to
execute by reading a few instructions ahead of
program counter
2. Non-special-instructions run natively
3. Special instructions translated into new set of
instructions that perform equivalent task (for
example changing the flags in the VCPU)
23
Binary Translation (cont.)
Implemented by translation of code within VMM
Code reads native instructions dynamically from
guest, on demand, generates native binary code
that executes in place of original code
Performance of this method would be poor
without optimizations
Products like VMware use caching
Translate once, and when guest executes code containing special
instruction cached translation used instead of translating again
Testing showed booting Windows XP as guest caused 950,000
translations, at 3 microseconds each, or 3 second (5 %) slowdown
over native
24
Binary Translation Virtualization Implementation
25
Nested Page Tables
• Memory management another general challenge to VMM
implementations
• How can VMM keep page-table state for both guests believing they
control the page tables and VMM that does control the tables?
• Common method (for trap-and-emulate and binary translation) is
nested page tables (NPTs)
▫ Each guest maintains page tables to translate virtual to physical
addresses
▫ VMM maintains per guest NPTs to represent guest’s page-table
state
 Just as VCPU stores guest CPU state
▫ When guest on CPU -> VMM makes that guest’s NPTs the active
system page tables
▫ Guest tries to change page table -> VMM makes equivalent
change to NPTs and its own page tables
▫ Can cause many more TLB misses -> much slower performance
26
Nested Page Tables
27
Types of Virtual Machines and Implementations
Many variations as well as HW details
Assume VMMs take advantage of HW features
HW features can simplify implementation, improve
performance
Whatever the type, a VM has a lifecycle
Created by VMM
Resources assigned to it (number of cores, amount
of memory, networking details, storage details)
In type 0 hypervisor, resources usually dedicated
Other types dedicate or share resources, or a mix
When no longer needed, VM can be deleted, freeing
resouces
28
Types of Virtual Machines and Implementations (Cont’d)
Steps simpler, faster than with a physical machine
install
Can lead to virtual machine sprawl with lots of
VMs, history and state difficult to track
29
Types of VMs – Type 0 Hypervisor
• Old idea, under many names by HW
manufacturers
▫
▫
▫
▫
▫
30
“partitions”, “domains”
A HW feature implemented by firmware
OS need to nothing special, VMM is in firmware
Smaller feature set than other types
Each guest has dedicated HW
Types of VMs – Type 0 Hypervisor
• I/O a challenge as difficult to have enough
devices, controllers to dedicate to each guest
• Sometimes VMM implements a control
partition running daemons that other guests
communicate with for shared I/O
• Can provide virtualization-within-virtualization
(guest itself can be a VMM with guests
▫ Other types have difficulty doing this
31
Type 0 Hypervisor
32
Types of VMs – Type 1 Hypervisor
• Commonly found in company datacenters
▫ In a sense becoming “datacenter operating systems”
 Datacenter managers control and manage OSes in new,
sophisticated ways by controlling the Type 1 hypervisor
 Consolidation of multiple OSes and apps onto less HW
 Move guests between systems to balance performance
 Snapshots and cloning
• Special purpose operating systems that run natively on HW
▫ Rather than providing system call interface, create run and
manage guest OSes
▫ Can run on Type 0 hypervisors but not on other Type 1s
▫ Run in kernel mode
▫ Guests generally don’t know they are running in a VM
▫ Implement device drivers for host HW because no other
component can
▫ Also provide other traditional OS services like CPU and memory
management
33
Types of VMs – Type 1 Hypervisor (cont.)
Another variation is a general purpose OS
that also provides VMM functionality
RedHat Enterprise Linux with KVM,
Windows with Hyper-V, Oracle Solaris
Perform normal duties as well as VMM
duties
Typically less feature rich than dedicated
Type 1 hypervisors
In many ways, treat guests OSes as just
another process
Albeit with special handling when guest
tries to execute special instructions
34
Types of VMs – Type 2 Hypervisor
• Less interesting from an OS perspective
▫ Very little OS involvement in virtualization
▫ VMM is simply another process, run and managed
by host
 Even the host doesn’t know they are a VMM running
guests
▫ Tend to have poorer overall performance because
can’t take advantage of some HW features
▫ But also a benefit because require no changes to
host OS
 Student could have Type 2 hypervisor on native host,
run multiple guests, all on standard host OS such as
Windows, Linux, MacOS
35
Types of VMs – Paravirtualization
• Does not fit the definition of virtualization – VMM
not presenting an exact duplication of underlying
hardware
▫ But still useful!
▫ VMM provides services that guest must be modified
to use
▫ Leads to increased performance
▫ Less needed as hardware support for VMs grows
36
Types of VMs – Paravirtualization (Cont’d)
• Xen, leader in paravirtualized space, adds several
techniques
▫ For example, clean and simple device abstractions
 Efficient I/O
 Good communication between guest and VMM about
device I/O
 Each device has circular buffer shared by guest and
VMM via shared memory
37
Xen I/O via Shared Circular Buffer
38
Types of VMs – Paravirtualization (cont.)
Memory management does not include nested
page tables
Each guest has own read-only tables
Guest uses hypercall (call to hypervisor) when
page-table changes needed
Paravirtualization allowed virtualization of
older x86 CPUs (and others) without binary
translation
Guest had to be modified to use run on
paravirtualized VMM
But on modern CPUs Xen no longer requires
guest modification -> no longer
39 paravirtualization
Types of VMs – Programming Environment Virtualization
Also not-really-virtualization but using same
techniques, providing similar features
Programming language is designed to run within
custom-built virtualized environment
For example Oracle Java has many features that
depend on running in Java Virtual Machine
(JVM)
40
Types of VMs – Programming Environment Virtualization
In this case virtualization is defined as providing
APIs that define a set of features made available
to a language and programs written in that
language to provide an improved execution
environment
JVM compiled to run on many systems
(including some smart phones even)
Programs written in Java run in the JVM no
matter the underlying system
Similar to interpreted languages
41
Types of VMs – Emulation
• Another (older) way for running one operating system on a different operating
system
▫ Virtualization requires underlying CPU to be same as guest was compiled for
▫ Emulation allows guest to run on different CPU
• Necessary to translate all guest instructions from guest CPU to native CPU
▫ Emulation, not virtualization
• Useful when host system has one architecture, guest compiled for other
architecture
▫ Company replacing outdated servers with new servers containing different
CPU architecture, but still want to run old applications
• Performance challenge – order of magnitude slower than native code
▫ New machines faster than older machines so can reduce slowdown
• Very popular – especially in gaming where old consoles emulated on new
42
Types of VMs – Application Containment
• Some goals of virtualization are segregation of
apps, performance and resource management,
easy start, stop, move, and management of them
• Can do those things without full-fledged
virtualization
▫ If applications compiled for the host operating
system, don’t need full virtualization to meet these
goals
43
Types of VMs – Application Containment (Cont’d)
• Oracle containers / zones for example create
virtual layer between OS and apps
▫ Only one kernel running – host OS
▫ OS and devices are virtualized, providing resources
within zone with impression that they are only
processes on system
▫ Each zone has its own applications; networking
stack, addresses, and ports; user accounts, etc
▫ CPU and memory resources divided between zones
 Zone can have its own scheduler to use those resources
44
Solaris 10 with Two Zones
45
Virtualization and Operating-System Components
• Now look at operating system aspects of
virtualization
▫ CPU scheduling, memory management,
I/O, storage, and unique VM migration
feature
How do VMMs schedule CPU use when
guests believe they have dedicated CPUs?
How can memory management work when
many guests require large amounts of
memory?
46
OS Component – CPU Scheduling
• Even single-CPU systems act like
multiprocessor ones when virtualized
One or more virtual CPUs per guest
• Generally VMM has one or more physical
CPUs and number of threads to run on them
▫ Guests configured with certain number of
VCPUs
Can be adjusted throughout life of VM
47
OS Component – CPU Scheduling (cont.)
• Cycle stealing by VMM and
oversubscription of CPUs means guests
don’t get CPU cycles they expect
▫ Consider timesharing scheduler in a
guest trying to schedule 100ms time
slices -> each may take 100ms, 1 second,
or longer
 Poor response times for users of guest
 Time-of-day clocks incorrect
▫ Some VMMs provide application to run
in each guest to fix time-of-day and
provide other integration features
48
OS Component – Memory Management
• Also suffers from oversubscription -> requires extra
management efficiency from VMM
• For example, VMware ESX guests have a configured amount of
physical memory, then ESX uses 3 methods of memory
management
1. Double-paging, in which the guest page table indicates a
page is in a physical frame but the VMM moves some of
those pages to backing store
2. Install a pseudo-device driver in each guest (it looks like
a device driver to the guest kernel but really just adds
kernel-mode code to the guest)
 Balloon memory manager communicates with VMM
and is told to allocate or deallocate memory to decrease
or increase physical memory use of guest, causing guest
OS to free or have more memory available
3. Deduplication by VMM determining if same page loaded
more than once, memory mapping the same page into
multiple guests
49
OS Component – I/O
• Easier for VMMs to integrate with guests
because I/O has lots of variation
▫ Already somewhat segregated / flexible via device drivers
▫ VMM can provide new devices and device drivers
• But overall I/O is complicated for VMMs
▫ Many short paths for I/O in standard OSes for improved performance
▫ Less hypervisor needs to do for I/O for guests, the better
▫ Possibilities include direct device access, DMA pass-through, direct
interrupt delivery
 Again, HW support needed for these
• Networking also complex as VMM and
guests all need network access
▫ VMM can bridge guest to network (allowing direct access)
▫ And / or provide network address translation (NAT)
 NAT address local to machine on which guest is running, VMM provides
address translation to guest to hide its address
50
OS Component – Storage
Management
• Both boot disk and general data access need
be provided by VMM
• Need to support potentially dozens of guests
per VMM (so standard disk partitioning not
sufficient)
• Type 1 – storage guest root disks and config
information within file system provided by
VMM as a disk image
51
OS Component – Storage
Management (Cont’d)
• Type 2 – store as files in file system provided
by host OS
• Duplicate file -> create new guest
• Move file to another system -> move guest
• Physical-to-virtual (P-to-V) convert
native disk blocks into VMM format
• Virtual-to-physical (V-to-P) convert from
virtual format to native or disk format
• VMM also needs to provide access to network
attached storage (just networking) and other
disk images, disk partitions, disks, etc
52
OS Component – Live Migration
• Taking advantage of VMM features leads to new functionality not
found on general operating systems such as live migration
• Running guest can be moved between systems, without interrupting
user access to the guest or its apps
• Very useful for resource management, maintenance downtime
windows, etc
1. The source VMM establishes a connection with the target VMM
2. The target creates a new guest by creating a new VCPU, etc
3. The source sends all read-only guest memory pages to the target
4. The source sends all read-write pages to the target, marking them
as clean
5. The source repeats step 4, as during that step some pages were
probably modified by the guest and are now dirty
6. When cycle of steps 4 and 5 becomes very short, source VMM
freezes guest, sends VCPU’s final state, sends other state details,
sends final dirty pages, and tells target to start running the guest
 Once target acknowledges that guest running, source terminates
guest
53
Live Migration of Guest Between Servers
54
Examples - VMware
• VMware Workstation runs on x86, provides VMM for
guests
• Runs as application on other native, installed host
operating system -> Type 2
• Lots of guests possible, including Windows, Linux, etc all
runnable concurrently (as resources allow)
• Virtualization layer abstracts underlying HW, providing
guest with is own virtual CPUs, memory, disk drives,
network interfaces, etc
• Physical disks can be provided to guests, or virtual
physical disks (just files within host file system)
55
VMware Workstation Architecture
56
Examples – Java Virtual Machine
Example of programming-environment
virtualization
Very popular language / application environment
invented by Sun Microsystems in 1995
Write once, run anywhere
Includes language specification (Java), API library,
Java virtual machine (JVM)
Java objects specified by class construct, Java
program is one or more objects
57
Examples – Java Virtual Machine
(Cont’d)
Each Java object compiled into architecture-neutral
bytecode output (.class) which JVM class
loader loads
JVM compiled per architecture, reads bytecode and
executes
Includes garbage collection to reclaim memory
no longer in use
Made faster by just-in-time (JIT) compiler that
turns bytecodes into native code and caches them
58
The Java Virtual Machine
59
Chapter 17 – Distributed Systems
60
Overview
Distributed system is collection of loosely coupled
processors interconnected by a communications network
Processors variously called nodes, computers,
machines, hosts
Site is location of the processor
Generally a server has a resource a client node at a
different site wants to use
61
Reasons for Distributed Systems
• Reasons for distributed systems
▫ Resource sharing
 Sharing and printing files at remote sites
 Processing information in a distributed database
 Using remote specialized hardware devices
▫ Computation speedup – load sharing or job
migration
▫ Reliability – detect and recover from site failure,
function transfer, reintegrate failed site
62
Reasons for Distributed Systems (Cont’d)
▫ Communication – message passing
 All higher-level functions of a standalone system can
be expanded to encompass a distributed system
▫ Computers can be downsized, more flexibility,
better user interfaces and easier maintenance by
moving from large system to multiple smaller
systems performing distributed computing
63
Types of Distributed Operating Systems
• Network Operating Systems
• Distributed Operating Systems
64
Network-Operating Systems
• Users are aware of multiplicity of machines
• Access to resources of various machines is done
explicitly by:
▫ Remote logging into the appropriate remote
machine (telnet, ssh)
▫ Remote Desktop (Microsoft Windows)
▫ Transferring data from remote machines to local
machines, via the File Transfer Protocol (FTP)
mechanism
• Users must change paradigms – establish a
session, give network-based commands
▫ More difficult for users
65
Distributed-Operating Systems
• Users not aware of multiplicity of machines
▫ Access to remote resources similar to access to local
resources
• Data Migration – transfer data by transferring
entire file, or transferring only those portions of
the file necessary for the immediate task
• Computation Migration – transfer the
computation, rather than the data, across the
system
▫ Via remote procedure calls (RPCs)
▫ or via messaging system
66
Distributed-Operating Systems (Cont.)
• Process Migration – execute an entire
process, or parts of it, at different sites
▫ Load balancing – distribute processes across
network to even the workload
▫ Computation speedup – subprocesses can run
concurrently on different sites
▫ Hardware preference – process execution may
require specialized processor
▫ Software preference – required software may
be available at only a particular site
▫ Data access – run process remotely, rather than
transfer all data locally
• Consider the World Wide Web
67
Network Structure
• Local-Area Network (LAN) – designed to
cover small geographical area
▫ Multiple topologies like star or ring
▫ Speeds from 1Mb per second (Appletalk, bluetooth)
to 40 Gbps for fastest Ethernet over twisted pair
copper or optical fibre
▫ Consists of multiple computers (mainframes
through mobile devices), peripherals (printers,
storage arrays), routers (specialized network
communication processors) providing access to
other networks
68
Network Structure (Cont’d)
▫ Ethernet most common way to construct LANs
 Multiaccess bus-based
 Defined by standard IEEE 802.3
▫ Wireless spectrum (WiFi) increasingly used for
networking
 I.e. IEEE 802.11g standard implemented at 54 Mbps
69
Local-area Network
70
Network Types (Cont.)
• Wide-Area Network (WAN) – links
geographically separated sites
▫ Point-to-point connections over long-haul lines
(often leased from a phone company)
 Implemented via connection processors known as
routers
▫ Internet WAN enables hosts world wide to
communicate
 Hosts differ in all dimensions but WAN allows
communications
71
Network Types (Cont.)
▫ Speeds
 T1 link is 1.544 Megabits per second
 T3 is 28 x T1s = 45 Mbps
 OC-12 is 622 Mbps
▫ WANs and LANs interconnect, similar to cell phone
network:
 Cell phones use radio waves to cell towers
 Towers connect to other towers and hubs
72
Communication Processors in a Wide-Area Network
73
Communication Structure
The design of a communication network must address four basic
issues:
• Naming and name resolution - How do
two processes locate each other to
communicate?
• Routing strategies - How are messages sent
through the network?
• Connection strategies - How do two
processes send a sequence of messages?
• Contention - The network is a shared
resource, so how do we resolve conflicting
demands for its use?
74
Naming and Name Resolution
• Name systems in the network
• Address messages with the
process-id
• Identify processes on remote
systems by
<host-name, identifier> pair
• Domain name system (DNS) –
specifies the naming structure of
the hosts, as well as name to
address resolution (Internet)
75
Routing Strategies
• Fixed routing - A path from A to B is specified
in advance; path changes only if a hardware
failure disables it
▫ Since the shortest path is usually chosen,
communication costs are minimized
▫ Fixed routing cannot adapt to load changes
▫ Ensures that messages will be delivered in the
order in which they were sent
76
Routing Strategies (Cont’d)
• Virtual routing- A path from A to B is fixed for
the duration of one session. Different sessions
involving messages from A to B may have
different paths
▫ Partial remedy to adapting to load changes
▫ Ensures that messages will be delivered in the
order in which they were sent
77
Routing Strategies (Cont.)
• Dynamic routing - The path used to
send a message form site A to site B is
chosen only when a message is sent
▫ Usually a site sends a message to another
site on the link least used at that particular
time
▫ Adapts to load changes by avoiding
routing messages on heavily used path
▫ Messages may arrive out of order
 This problem can be remedied by appending
a sequence number to each message
▫ Most complex to set up
78
Routing Strategies (Cont.)
• Tradeoffs mean all methods are used
▫ UNIX provides ability to mix fixed and
dynamic
▫ Hosts may have fixed routes and
gateways connecting networks together
may have dynamic routes
79
Routing Strategies (Cont.)
• Router is communications processor
responsible for routing messages
• Must have at least 2 network connections
• Maybe special purpose or just function running
on host
• Checks its tables to determine where
destination host is, where to send messages
▫ Static routing – table only changed manually
▫ Dynamic routing – table changed via routing
protocol
80
Routing Strategies (Cont.)
• Routing managed by intelligent software more
intelligently than routing protocols
▫ OpenFlow is device-independent, allowing
developers to introduce network efficiencies by
decoupling data-routing decisions from underlying
network devices
• Messages vary in length – simplified design
breaks them into packets (or frames, or
datagrams)
• Connectionless message is just one packet
▫ Otherwise need a connection to get a multi-packet
message from source to destination
81
Connection Strategies
• Circuit switching - A permanent physical link
is established for the duration of the
communication (i.e., telephone system)
• Message switching - A temporary link is
established for the duration of one message
transfer (i.e., post-office mailing system)
82
Connection Strategies (Cont’d)
• Packet switching - Messages of variable length
are divided into fixed-length packets which are
sent to the destination
▫ Each packet may take a different path through the
network
▫ The packets must be reassembled into messages as
they arrive
• Circuit switching requires setup time, but incurs
less overhead for shipping each message, and may
waste network bandwidth
▫ Message and packet switching require less setup
time, but incur more overhead per message
83
Communication Protocol
The communication network is partitioned into the following multiple layers:
• Layer 1: Physical layer – handles the
mechanical and electrical details of the physical
transmission of a bit stream
• Layer 2: Data-link layer – handles the
frames, or fixed-length parts of packets,
including any error detection and recovery that
occurred in the physical layer
84
Communication Protocol (Cont’d)
• Layer 3: Network layer – provides
connections and routes packets in the
communication network, including handling the
address of outgoing packets, decoding the
address of incoming packets, and maintaining
routing information for proper response to
changing load levels
85
Communication Protocol (Cont.)
• Layer 4: Transport layer – responsible
for low-level network access and for message
transfer between clients, including
partitioning messages into packets,
maintaining packet order, controlling flow,
and generating physical addresses
• Layer 5: Session layer – implements
sessions, or process-to-process
communications protocols
86
Communication Protocol (Cont.)
• Layer 6: Presentation layer –
resolves the differences in formats
among the various sites in the network,
including character conversions, and
half duplex/full duplex (echoing)
• Layer 7: Application layer –
interacts directly with the users, deals
with file transfer, remote-login protocols
and electronic mail, as well as schemas
for distributed databases
87
Communication Via ISO Network Model
88
The ISO Protocol Layer
89
The ISO Network Message
90
The TCP/IP Protocol Layers
91
Example: TCP/IP
• The transmission of a network packet between
hosts on an Ethernet network
• Every host has a unique IP address and a
corresponding Ethernet Media Access Control (MAC)
address
• Communication requires both addresses
• Domain Name Service (DNS)
IP addresses
92
can be used to acquire
Example: TCP/IP (Cont’d)
• Address Resolution Protocol (ARP)
is used to map
MAC addresses to IP addresses
▫ Broadcast
to all other systems on the Ethernet
network
• If the hosts are on the same network, ARP can be
used
▫ If the hosts are on different networks, the sending
host will send the packet to a router which routes
the packet to the destination network
93
An Ethernet Packet
94
Distributed File System
• Distributed file system (DFS) – a
distributed implementation of the classical
time-sharing model of a file system, where
multiple users share files and storage resources
• A DFS manages set of dispersed storage devices
• Overall storage space managed by a DFS is
composed of different, remotely located, smaller
storage spaces
• There is usually a correspondence between
constituent storage spaces and sets of files
• Challenges include:
▫ Naming and Transparency
95 ▫ Remote File Access
DFS Structure
• Service – software entity running on one or
more machines and providing a particular type
of function to a priori unknown clients
• Server – service software running on a single
machine
• Client – process that can invoke a service using
a set of operations that forms its client interface
• A client interface for a file service is formed by a
set of primitive file operations (create, delete,
read, write)
96
Naming and Transparency
• Naming – mapping between logical and
physical objects
• Multilevel mapping – abstraction of a file that
hides the details of how and where on the disk
the file is actually stored
• A transparent DFS hides the location where in
the network the file is stored
• For a file being replicated in several sites, the
mapping returns a set of the locations of this
file’s replicas; both the existence of multiple
copies and their location are hidden
97
Naming Structures
• Location transparency – file
name does not reveal the file’s
physical storage location
• Location independence – file
name does not need to be changed
when the file’s physical storage
location changes
98
Naming Schemes — Three Main Approaches
• Files named by combination of their host name
and local name; guarantees a unique system-wide
name
• Attach remote directories to local directories,
giving the appearance of a coherent directory tree;
only previously mounted remote directories can
be accessed transparently
99
Naming Schemes — Three Main Approaches
(Cont’d)
• Total integration of the component file systems
▫ A single global name structure spans all the files in
the system
▫ If a server is unavailable, some arbitrary set of
directories on different machines also becomes
unavailable
• In practice most DFSs use static, locationtransparent mapping for user-level names
▫ Some support file migration
▫ Hadoop supports file migration but without
following POSIX standards
100
Remote File Access
• Remote-service mechanism is one transfer
approach
• Reduce network traffic by retaining recently
accessed disk blocks in a cache, so that repeated
accesses to the same information can be handled
locally
101
Remote File Access (Cont’d)
▫ If needed data not already cached, a copy of data is
brought from the server to the user
▫ Accesses are performed on the cached copy
▫ Files identified with one master copy residing at the
server machine, but copies of (parts of) the file are
scattered in different caches
▫ Cache-consistency problem – keeping the
cached copies consistent with the master file
 Could be called network virtual memory
102
Cache Location – Disk vs. Main Memory
• Advantages of disk caches
▫ More reliable
▫ Cached data kept on disk are still there during recovery
and don’t need to be fetched again
• Advantages of main-memory caches:
▫
▫
▫
▫
103
Permit workstations to be diskless
Data can be accessed more quickly
Performance speedup in bigger memories
Server caches (used to speed up disk I/O) are in main
memory regardless of where user caches are located;
using main-memory caches on the user machine permits
a single caching mechanism for servers and users
Cache Update Policy
• Write-through – write data through to disk as
soon as they are placed on any cache
▫ Reliable, but poor performance
• Delayed-write (write-back) – modifications
written to the cache and then written through to
the server later
▫
Write accesses complete quickly; some data may be overwritten before they are
written back, and so need never be written at all
▫ Poor reliability; unwritten data will be lost whenever a user machine crashes
▫ Variation – scan cache at regular intervals and flush blocks that have been
modified since the last scan
▫ Variation – write-on-close, writes data back to the server when the file is closed
 Best for files that are open for long periods and frequently modified
104
Consistency
• Is locally cached copy of the data
consistent with the master copy?
• Client-initiated approach
▫ Client initiates a validity check
▫ Server checks whether the local data are
consistent with the master copy
• Server-initiated approach
▫ Server records, for each client, the (parts
of) files it caches
▫ When server detects a potential
inconsistency, it must react
105
Oral Presentations
106
Questions!
• Email to
[email protected]
107