DISTRIBUTED SYSTEMS

Lecture 3 – Processes

Pan Hui
pan.hui@helsinki.fi

Huber Flores
huber.flores@helsinki.fi

Helsinki, Finland, 2018.

 2

Recap
• Different architecture styles
• Basic automaton

Helsinki, Finland, 2018.

 3

PROCESSES

Helsinki, Finland, 2018.

 4
Example: Amazon Elastic Compute
Cloud (EC2)
• Large number of preconfigured machine images
(AMI ~ Amazon Machine Image)
– E.g. LAMP (Linux, Apache, MySql, PHP) images
• Launching AMI results in EC2 instance providing different levels of
services for hosting customer’s applications
– CPU: allows customer to select the number and type of cores,
including GPUs
– Memory: how much main memory is allocated to an instance
– Storage: how much local storage is allocated
– Platform: selection between 32-bit and 64-bit architectures
– Networking: how much network capacity is allocated
• Two IP addresses for communication
– Private address for internal communication between EC2 instances
– Public address allowing Internet clients to communicate

Helsinki, Finland, 2018.

 13
Example: Amazon Elastic Compute
Cloud (EC2)
• Used to be market leadere, now down to ~20% market share
– https://news.netcraft.com/archives/category/web-server-survey/
• General organization
– Own runtime environment APR (Apache Portable Runtime) available for
different operating systems makes server platform independent
– Hook ~ placeholder
for functions
• Processed in
predetermined order
– Modules provide
functions processing
HTTP requests
• Highly configurable
• Highly extensible

Helsinki, Finland, 2018.

 14
Client-request redirection using DNS
redirect
• URLs of embedded documents
modified to refer to a virtual ghost
(e.g. CDN server)
– URL contains also unique ID
modified every time embedded
document changes
– URL includes also origin server
• Step 3: DNS name resolution leads
to CDN DNS server
• Step 4: CDN DNS server redirects
client to most suitable replica server
• Step 6: If CDN server does not have
the document, it fetches it from
origin server, caches it locally and
passes it to client
– Replica server has to be able to
contact origin server for which
purpose the origin server is also
included in the URL
Helsinki, Finland, 2018.
 15
IPv6 anycast addressing for distributed
servers
• One-to-many association between network addresses and network
endpoints: each destination address identifies a set of receiver
endpoints, but only one of them is chosen at any given time to
receive information from any given sender, as determined by used
routing protocol.

• Several DNS root name servers are implemented as large numbers

of clusters of machines using anycast. The C, F, I, J, K and M root
name servers exist in multiple locations on different continents,
using anycast announcements to provide a decentralized service.

Helsinki, Finland, 2018.

 16
Sender-initiated mobility vs receiver-
initiated mobility
• Sender-initiated (remote evaluation, mobile
agents)
– Mobility initiated by machine where the code currently resides or is
being executed
– E.g. uploading programs to a computing server
• Receiver-initiated (code-on-demand)
– Mobility initiated by target machine (client), e.g. Java applets
downloaded from a web server
• Receiver-initiated mobility (code moves from
server to client) often simpler to implement
– Server’s resources have to be protected from (malicious) clients
– Server is not typically interested in clients resources

Helsinki, Finland, 2018.

 17

Agenda
• Threads
• Virtualization
• Clients
• Servers
• Code migration
• Modelling

Helsinki, Finland, 2018.

 18

Introduction to threads
• Process ~ a program in execution in a virtual processor
created by the operating system
– Concurrency transparency of multiple processes enforced by OS
• Independent state information
• Independent address spaces
• Interact only via IPC (inter-process communication) mechanism
 Expensive context switch (CPU, memory, address caches)
– A process typically comprises of multiple (parallel) threads
providing finer granularity of control

• Thread (of execution) ~ executes its own piece of code,

independently from other threads
– No high concurrency transparency between multiple threads
• Share state information of a single process
• Share memory and other resources directly
 Cheaper CPU context switch

Helsinki, Finland, 2018.

 19
Thread usage in nondistributed
systems
• Multiple threads allow
– Concurrent execution of different tasks
– Parallel execution on multiprocessor systems
– Efficient context switching in comparison to expensive
context switching as the result of IPC shown below
• Context switch at three points (user mode → kernel mode → user mode)

• Thread switching may be done entirely in user space

 performance inmprovement
Helsinki, Finland, 2018.
 20

Thread implementation
• Two approaches for implementing thread package

– A thread library that is executed entirely in user space

+ Cheap to create/destroy threads
+ Simple switching of thread context
- Invocation of a blocking system call blocks will immediately block the
entire process to which the thread belongs, including all other threads
in the process

– Threads are implemented in OS kernel

+ More efficient scheduling
- Expensive creation/deletion/synchronization of threads
– Carried out by kernel requiring a system call
- Expensive switching of thread context

Helsinki, Finland, 2018.

 21

Thread implementation
• Lightweight process (LWP) ~ hybrid form of user-level and kernel-
level threads
– LWP runs in context of single (heavy-weight) process
• There can be several LWPs per process
– User-level thread package is implemented entirely in user space
• Shared by multiple LWPs, each LWP can run its own user-level thread

– In a multithreaded application each thread is implicitly assigned to a

LWP (assignment is hidden from the programmer)
Helsinki, Finland, 2018.
 22

Thread implementation
• LWP operation
– LWP is created with a system call and given its own stack
– LWP executes scheduling routine provide by the thread
package to search for a runnable thread from a shared
thread table
– Upon finding a runnable thread LWP switches context (in
user space) to that thread
– When a thread makes a blocking system call
• Execution changes from user mode to kernel mode, and continues in the context of
current LWP
• If current LWP cannot continue, OS switches context to another LWP (and back to user
mode)
– Mutually exclusive access control to shared resources (e.g.
thread table) with mutexes implemented in user space

Helsinki, Finland, 2018.

 23

Thread implementation
• Pros / cons of using LWPs with user-level thread package
+ Creating/destroying/synchronizing threads is relatively cheap
(no kernel involvement)
+ Blocking system call will not suspend entire process (assuming
process has enough LWPs)
+ LWPs are transparent to applications
+ Transparent multiprocessing by executing different LWPs on
different CPUs
- Creating/destroying LWPs is as expensive as with kernel-level
threads, though it needs to be done only occasionally
• Similar alternative: scheduler activations
– Upon a thread blocking on system call, kernel makes an upcall
to thread package, calling scheduler to select next runnable
thread, likewise when a thread is unblocked
– Saves management of LWPs by the kernel
– Violates the principle of layered design
Helsinki, Finland, 2018.
 24

Threads in distributed systems

• Threads provide convenient means of allowing blocking
system calls without blocking the entire process
 facilitates communication in form of multiple
simultaneous logical connections in distributed systems

• Multithreaded clients such as web browsers

– Goal is to conceal long interprocess message propagation times
in wide-area networks
– Separate threads for displaying and fetching data
– Client handles parallel streams of incoming data by allocating
separate threads for establishing multiple connections to fetch
parts of data (e.g. one for base HTML and other for images)
– Particularly effective if client is dealing with a replicated server

Helsinki, Finland, 2018.

 25

Threads in distributed systems

• Multithreaded servers
– Multithreaded server organized in dispatcher/worker model
– Dispatcher thread reads an incoming request and hands it to
idle (i.e. blocked) worker thread
– If a worker thread is suspended due to a blocking system call,
another thread is selected to be executed

– Goal: efficient parallel computing on multiprocessor systems

Helsinki, Finland, 2018.
 26

Threads in distributed systems

• Other approaches to construct a server
– Single-threaded process
• No parallelism
• Blocking system calls
– Finite-state machine
• Parallelism
• Nonblocking system calls

• Benefits of threads in distributed systems

– Allow retaining the idea of sequential processing that make
blocking system calls and still achieve parallelism
– Blocking system calls make programming easier
– Parallelism improves performance

Helsinki, Finland, 2018.

 27

Virtualization
• Resource virtualization
– E.g. multithreading on a single CPU for creating an illusion of
parallelism (simultaneous execution)
• Role of virtualization in distributed systems
– Support porting of legacy interfaces to new platforms
– Reduce diversity of platforms and machines by letting each application
run on its own virtual machine

(a) General organization between a program, interface and system

(b) General organization of virtualizing system A on top of system B
Helsinki, Finland, 2018.
 28

Architectures of virtual machines

• Interfaces at four different levels
1. An interface between the hardware and software
consisting of machine instructions that can be invoked by
any program.
2. An interface between the hardware and software,
consisting of machine instructions that can be invoked
only by privileged programs, such as an operating system.
3. An interface consisting of system calls as offered by an
operating system.
4. An interface consisting of library calls generally forming
what is known as an application programming interface
(API). In many cases, the aforementioned system calls are
hidden by an API.

Helsinki, Finland, 2018.

 29

Architectures of virtual machines

The essence of virtualization is to

mimic the behavior of these
interfaces

Helsinki, Finland, 2018.

 30

Architectures of virtual machines

• Virtualization in two different ways
– Process virtual machine
• Virtualization for a single process
• Runtime system with abstract instruction
set for executing applications
– Interpretation (Java Runtime Environment)
– Emulation (Windows apps on Unix)
• Multiple instances of (application, runtime)
combinations on same platform
– Virtual machine monitor (VMM)
• Layer offering a complete instruction
set as an interface
• Multiple instances of (application,
operating system) combinations on
same platform
• E.g. VMware

Helsinki, Finland, 2018.

 31

Clients
• Two approaches for networked user interfaces

– Application-specific protocol
• Handles synchronization with
remote service

– Thin-client network computing

• Application-independent protocol
offers a convenient user interface
• E.g. WWW

Helsinki, Finland, 2018.

 32

Clients
• Example: The X Window system
– X kernel
• Contains all terminal-specific device drivers, HW dependent
• Offers relatively low-level interface (as a library called Xlib) for controlling screen and
capturing events from keyboard and mouse
– X protocol
• Application-level communication protocol for an instance of Xlib to exchange data and
events with X kernel
– Window manager
• Dictates the ”look and feel” of the display

Helsinki, Finland, 2018.

 33

General design issues of servers

• Iterative vs concurrent
– Iterative
• Server itself handles the request and returns a response to the
requesting client if necessary

– Concurrent
• Passes the request to a separate thread or another process, and waits
for next incoming request (e.g. multithreaded server),
or
• Forks a new process for each new incoming request

• Thread/process handling the request is responsible for returning a

response to the requesting client

Helsinki, Finland, 2018.

 34

General design issues of servers

• Stateless vs stateful
– Stateless: does not maintain state information of its clients and
can change its own state without having to inform any client
• E.g. web server is stateless
– Clients’ state information is stored and passed with cookies
– Web server maintains state information of its clients (for logging
purposes), but losing it would not disturb the service
• Soft state maintained by server for limited time
• Simplicity of implementation

– Stateful: maintains persistent information of its clients

• E.g. a file server allowing a client to keep a local copy
• Pro: performance improvements in some applications
• Con: recovery from crashes increases complexity

Helsinki, Finland, 2018.

 35

General design issues of servers

• In-band vs out-of-band signaling with the server
– Out-of-band: data and signaling in different connections
(e.g. FTP)
– In-band: data and signaling in same connection (e.g. TCP
urgent data)

Helsinki, Finland, 2018.

 36

General design issues of servers

• Client-to-server binding with end points (ports)
– How do clients know the end point of a service?

1. Endpoints (ports) assigned to well-known services

• E.g. FTP TCP port 21, HTTP TCP port 80
• Client only needs to find network address of the machine where server is running (e.g. using DNS)

2. Special daemon keeps track of

current end points of each service
implemented by a colocated server
• Daemon itself listens to a well-known endpoint

3. Superserver listens to end points

associated with specific services
and creates server processes for
incoming requests
• E.g. inetd in UNIX

Helsinki, Finland, 2018.

 37

Server clusters
• General organization of three-tiered server cluster
– Switch (front end) provides a single access point to realize
access transparency (hides the internal organization of the
server cluster from clients)

Helsinki, Finland, 2018.

 38

Server clusters
• TCP handoff performed by transport layer switch
– Switch accepts incoming TCP connection requests
– Switch identifies the best server for handling the
request and forwards the request packet to that
server
– The server replies to the client, inserting the switch’s
IP address (IP spoofing) as the source IP address in the
reply
– Load balancing (round robin, content-aware request
distribution)

Helsinki, Finland, 2018.

 39

Server clusters

Helsinki, Finland, 2018.

 40

Code migration
• Goal: passing programs (sometimes even while they are
being executed), not just data

• Motivation
– Performance improvement
• Load distribution
• Parallel execution
– Flexibility via dynamic
configuration of clients

• Challenges
The principle of dynamically configuring a
– Security: can you trust
client to communicate with a server. The
the migrating code?
client first fetches the necessary software,
and then invokes the server.
Helsinki, Finland, 2018.
 41

Helsinki, Finland, 2018.

 42

Models for code migration

• Code segment ~ set of intructions making up the
program that is being executed

• Resource segment ~ references to external resources

needed by the process (files, other processes etc.)

• Execution segment ~ stores current execution state of a

process (private data, stack, program counter)

(Terminology from framework of Fuggetta et al. (1998))

Helsinki, Finland, 2018.

 43

Models for code migration

• Weak mobility vs strong mobility
– Weak
• Only code segment and initialization data is transferred
• Transferred program is always started from predefined starting position
• Target machine has to be able to execute the (portable) code
• Simple to implement
• Execution by target process (e.g. Java applets in web) or as a separate process
(e.g. helper applications in web)
– Strong
• Execution segment is moved/cloned to another machine
• Much harder to implement
• Process migration (moving a process)
– Running process is stopped and moved to another machine,
where it resume execution
• (Remote) cloning
– Exact copy of the original process is cloned and run parallel on a
different machine
Helsinki, Finland, 2018.
 44

Migration and local resources

• Process-to-resource bindings
– Binding by identifier (strongest): process requires referenced
resource
• E.g. URL, FTP server, local endpoint (port)
– Binding by value: process requires value of resource
• E.g. standard libraries
– Binding by type (weakest): process requires resource of specific
type
• E.g. local devices (monitor, printer)

• Resource-to-machine bindings
– Unattached resource: can be easily moved between machines
• E.g. files associated only with the program being migrated
– Fastened resource: can be moved only with high cost
• E.g. local databases, complete web sites
– Fixed resource: cannot be moved
• E.g. local devices and local communication end points (ports)
Helsinki, Finland, 2018.
 45

MODELLING

Helsinki, Finland, 2018.

 46

Extended state machines

• States
• Events
– Call event
– Signal event
– Change event
– Time event
• Transitions and guard conditions
• Transitions effects
Helsinki, Finland, 2018.
 47

State
• A state is an abstraction of values an links of an
object
– A given object has a finite number of possible states
– It can only be in one state at a time
– At a given moment, various objects can exist each one
with its one state

Helsinki, Finland, 2018.

 48

Events
• An event is the specification of some
occurrence that may potentially trigger effects
by an object
• Kinds of events
– Call event
– Signal event
• Reliable channel
– Change event
– Time event

Helsinki, Finland, 2018.

 49

Call events
• A call event represents the reception of a
request to invoke a specific operation
– A call event is distinct from the call action that
caused it

Helsinki, Finland, 2018.

 50

Signal event
• A signal is an explicit one-way transmission of
information from one object to another
– Reliable channel
– A signal event is asynchronous
– A call event is a two-way synchronous
communication

Helsinki, Finland, 2018.

 51

Change events
• A change event is an event that is caused by
the satisfaction of a boolean expression

Helsinki, Finland, 2018.

 52

Time event
• A time event is an event that is caused by the
occurrence of an absolute time or the elapse
of a time interval

Helsinki, Finland, 2018.

 53

Transitions and guard conditions

• A transition is the change from one state to another
– E.g. A phone line transitions from “Ringing” state to
“Connected” when somebody picks the phone up
• A boolean expression can be used to add constraints in the
firing of a transition
– Interesting when more than one transition can be selected at a
given time

Helsinki, Finland, 2018.

 54

Transition effects and do-activities

• A transition effect can be an assignment or the
call to an operation

Helsinki, Finland, 2018.

 55

More about transitions guards

Helsinki, Finland, 2018.

 56

More about transitions guards

Helsinki, Finland, 2018.

 57

Hands-on session
• SVM (Python)
• Acronym of Statechart Virtual Machine
– Developed by Thomas Huining Feng
• A simulator Statecharts
– Standalone animation of statecharts
– SVM provides bindings for several programming
languages
• Web page
– http://msdl.cs.mcgill.ca/people/tfeng/uml/svm.html
Helsinki, Finland, 2018.
 58

Hands-on session
• Statechart: Visual vs textual

Helsinki, Finland, 2018.

 59

Hands-on session
• Download the tools and demo
– http://huberflores.com/lectures/handsonsession-
lecture3.zip

Helsinki, Finland, 2018.

 60

Running SVM
• Configure the environment variables
(Windows)
– PATH=%PATH%;C:\Software\Python25;C:\Software\svm-0.3beta3-src
– set PYTHONPATH=.;C:\Software\svm-0.3beta3-src

• Configure the environment variables (UNIX)

– export PATH=$PATH:/usr/home/user/svm-0.3beta3-src
– export PYTHONPATH=.:/usr/home/user/svm-0.3beta3-src

Helsinki, Finland, 2018.

 61

Syntax summary

Helsinki, Finland, 2018.

 62

Hello world … Python & Tkinter

Helsinki, Finland, 2018.

 63

Hello world … Python & Tkinter

Helsinki, Finland, 2018.

 64

Hello world … Python & Tkinter

Helsinki, Finland, 2018.

 65

Binding the GUI to SVM

Helsinki, Finland, 2018.

 66

Exercise
• Play with the lighbulb example (provided)

Helsinki, Finland, 2018.

 67

Your tasks
• For next lecture session:
– Read Chapter 4 Communication (From Van Steen)
– Get acquiantance with the tools
– Extend the lighbulb example to support ‘flashing“
• Quiz in the practical session
• First task: Texas Watch
– Description in course web page
– Thursday 15, 2018, midnight
– Each hour late is 10% less points
• After 6 hours, value of the task is 50%

Helsinki, Finland, 2018.

 68

QUESTIONS 

Helsinki, Finland, 2018.