Distributed Systems

((()))

Chapter 03: Processes

Processes Threads

Outline

▪ Threads
• Introduction to Threads
• Thread Implementation
• Threads in Distributed Systems
▪ Clients
• User Interfaces
• Client-Side Software for Distribution Transparency
▪ Servers
• General Organization
• Out-of-Band Communication
• Servers and State
• Server Clusters
▪ Code Migration
• Approaches to Code Migration
• Migration and Local Resources
• Migration in Heterogeneous Systems

Introduction to threads
Processes Threads

Introduction to threads
Basic idea – process

▪ An operating system uses multitasking to run multiple programs at once, giving

each program its own virtual processor-vCPU (OS will build virtual processor on
top of physical processor).
▪ It keeps track of all running programs using a process table.
▪ Each entry in the process table is a Process Control Block (PCB) that stores a
program's state, such as its CPU registers, memory, and open files.
▪ A process is simply a program that is currently being executed, including its
current variables and state.
▪ The OS ensures processes are isolated so they can’t interfere with each other.
▪ It uses hardware support to share the CPU and other resources transparently
while maintaining this separation.
▪ When a new process is created, the operating system gives it a completely
separate and independent address space in memory.

Introduction to threads
Processes Threads

Introduction to threads
Processor vs process vs thread
Processor: A processor is the physical hardware (or virtual processor is
software component) component of a computer system.
It executes machine-level instructions of programs.
It contains hardware components such as: Registers, Caches,
ALU, Control Unit, etc.
Process: A process is a program in execution.
It is a software abstraction created by the operating system.
A process contains (process context): Program code, data,
memory space, resources (files, handles, etc.), one or more threads.
A process provides the execution environment and resources
for running programs.
Thread: A thread is the smallest unit of execution within a process.

Introduction to threads
Processes Threads

Introduction to threads
Basic idea – Threads

All threads within a process share the same address space.

▪ A thread shares its code and data section with other threads.
• Memory
• Files
• Other process resources
▪ Each thread has its own program counter, stack and register set.
▪ The PC determines which instruction the thread is currently executing.
▪ The register set saves the thread’s state when it is suspended and reloaded
into the machine registers upon

Introduction to threads
Processes Threads

Context switching
Observations
1. Threads share the same address space. Thread context switching can be
done entirely independent of the operating system (i.e. user thread).
2. Process switching is generally (somewhat) more expensive as it involves
getting the OS in the loop, i.e., trapping to the kernel.
3. Creating and destroying threads is much cheaper than doing so for
processes. However more prone to errors, because no support from
OS/HW to protect threads using each other’s memory.

Introduction to threads
Processes Threads

Why use threads

Some simple reasons
• Avoid needless blocking: In a single-threaded process, the entire process
blocks during I/O operations. In a multithreaded process, the operating
system can switch the CPU to another thread while one thread waits for I/O.
• Exploit parallelism: Multithreading allows multiple threads of the same
process to run simultaneously on multiple CPUs or cores. This improves
performance and system utilization.
• Avoid process switching: Creating and switching between processes is
relatively expensive because each process has its own memory space and
resources.

Introduction to threads
Processes Threads

Introduction to threads
Basic idea – Thread Types

Threads are generally classified into two main types based on where they are
implemented and managed: User Threads and Kernel Threads.

▪ User threads: are implemented and managed at the user level rather than by
the operating system kernel.
▪ Kernel threads: are directly supported and managed by the operating system
kernel.

Introduction to threads
Processes Threads

Threads and operating systems

Main issue
Should an OS kernel provide threads, or should they be implemented as
user-level packages?

User-space solution
• All operations can be completely handled within a single process ⇒
implementations can be extremely efficient.
• All services provided by the kernel are done on behalf of the process in
which a thread resides ⇒ if the kernel decides to block a thread, the
entire process will be blocked.
• Threads are used when there are many external events: threads block on
a per-event basis ⇒ if the kernel can’t distinguish threads, how can it
support signaling events to them?

Introduction to threads
Processes Threads

Threads and operating systems

Kernel solution
n the kernel solution, the operating system kernel itself manages threads.
This means the implementation of the thread package is inside the OS
kernel, not in a user library.
• Operations that block a thread are no longer a problem: the kernel
schedules another available thread within the same process.
• All thread operations (such as creating, blocking, scheduling, and
terminating threads) are performed through system calls.
• The problem is (or used to be) the loss of efficiency because each thread
operation requires a trap to the kernel.

Conclusion – but
Try to mix user-level and kernel-level threads into a single concept (this
called lightweight process), however, performance gain has not turned out to
generally outweigh the increased complexity.

Introduction to threads
Processes Threads

Combining user-level and kernel-level threads

Basic idea
Introduce a two-level threading approach: kernel threads that can execute
user-level threads.

Introduction to threads
Processes Threads

User and kernel threads combined

Principle operation
• User thread does system call ⇒ the kernel thread that is executing that
user thread, blocks. The user thread remains bound to the kernel thread.
• The kernel can schedule another kernel thread having a runnable user
thread bound to it. Note: this user thread can switch to any other
runnable user thread currently in user space.
• A user thread calls a blocking user-level operation ⇒ do context switch to
a runnable user thread, (then bound to the same kernel thread).
• When there are no user threads to schedule, a kernel thread may remain
idle, and may even be removed (destroyed) by the kernel.

Introduction to threads
 Processes Threads

Threads and Distributed Systems

Using threads at the client side

Multithreaded web client
Hiding network latencies:
• Web browser scans an incoming HTML page, and finds that more files
need to be fetched.
• Each file is fetched by a separate thread, each doing a (blocking) HTTP
request.
• As files come in, the browser displays them.

Multiple request-response calls to other machines (RPC)

• A client does several calls at the same time, each one by a different
thread. Call server A → wait
Call server B → wait
• It then waits until all results have been returned. Call server C → wait

• Note: if calls are to different servers, we may have a linear speed-up.

Server A → 2 sec Server A → 2 sec
Without threads (Sequential) Server B → 3 sec With threads (Parallel) Server B → 2 sec
Server C → 2 sec Server C → 2 sec
Threads in distributed systems Total = 6 seconds Total = 3 seconds
Processes Threads

Using threads at the server side

Improve performance
• Starting a thread is cheaper than starting a new process.
• Having a single-threaded server can execute only one task at a
time, even if the machine has multiple CPUs or cores.
• As with clients: hide network latency by reacting to next request while
previous one is being replied.

Better structure
• Most servers have high I/O demands (Reading files, Accessing
databases, Communicating over networks). Using simple, well-
understood blocking calls simplifies the structure.
• Multithreaded programs tend to be smaller and easier to understand due
tosystems
Threads in distributed simplified flow of control.
Processes Threads

Using threads at the server side

Better structure
• Most servers have high I/O demands (Reading files, Accessing
databases, Communicating over networks). These operations often
use blocking calls, meaning the program waits until the operation
finishes.
• So, without threads, blocking calls would stop the entire server.
• With threads, if one thread blocks - other threads continue running,
and the server remains responsive.
• Multithreaded programs tend to be smaller and easier to understand due
to simplified flow of control.
Multithreading simplifies the program flow.
Without threads:
Programs must use, event loops, callbacks, state
This makes programs:
machines. This can make code complex and difficult to
•Shorter
maintain.
•Easier to read
With threads
•Easier to maintain
Each thread can execute sequential logic, like a normal
program: receive, process, and end requestes
Threads in distributed systems
Processes Threads

Why multithreading is popular: organization

Dispatcher/worker model

Overview
Model Characteristics
Multithreading Parallelism, blocking system calls
Single-threaded process No parallelism, blocking system calls
Finite-state machine Parallelism, nonblocking system calls

Threads in distributed systems

Processes Virtualization

Virtualization
Virtualization is important: Virtualization is a technique in computer systems where
one system imitates or emulates another system’s interface or environment. This
allows software designed for one platform to run on another platform without
modification.
• Hardware changes faster than software
▪ If software depends directly on specific hardware, every hardware change
may require rewriting the software.
▪ Role of Virtualization: it creates a stable interface between SW and HW.
• Ease of portability and code migration
• Isolation of failing or attacked components
▪ E.g. In a cloud server: VM1 runs a web server VM2 runs a database server
▪ If VM1 crashes or is attacked, VM2 continues working.

Principle: mimicking interfaces

Principle of virtualization
Processes Virtualization

Zooming into VMs: performance

Refining the organization

• Privileged instruction: if and only if executed in user mode, it causes a trap to

the operating system
• Nonpriviliged instruction: the rest

Principle of virtualization
Processes Virtualization

Ways of virtualization

(a) Process VM (b) Native VMM (VM Monitor) (c) Hosted VMM

Differences
(a) Process VM → for running one program (lightweight).
(b) Native VMM → best for high performance and servers.
(c) Hosted VMM → best for ease of use on personal computers..

Principle of virtualization
Processes Virtualization

Ways of virtualization

(a) Process VM (Process Virtual Machine)

• Runs a single application, not a full operating system
• Provides a virtual environment for one program
• Works on top of an existing OS
• Focus: portability and isolation of applications
• Lightweight and fast
Example:
Java Virtual Machine (runs Java programs on any platform)

Principle of virtualization
Processes Virtualization

Ways of virtualization

(b) Native VMM (Bare-Metal Virtual Machine Monitor)

• Runs directly on hardware (no host OS in between)
• Controls hardware and manages multiple virtual machines
• Each VM can run its own OS
• Focus: performance and strong isolation
• Used in servers and data centers
Examples:
• VMware ESXi
• Microsoft Hyper-V
• Xen

Principle of virtualization
Processes Virtualization

Ways of virtualization

(c) Hosted VMM (Hosted Virtual Machine Monitor)

• Runs on top of a host operating system
• Uses the host OS to access hardware
• Easier to install and use, but slower than native VMM
• Focus: convenience and flexibility
Examples:
• VMware Workstation
• Oracle VM VirtualBox

Principle of virtualization
Processes Clients

Client-server interaction - two ways to support client-server interaction

Distinguish application-level and middleware-level solutions

Application-level protocol - For each remote services, the client machine will
have a separate counterpart that can contact the service over the network.
• Example: an agenda running on a user's PDA that needs to synchronize
with a remote, possibly shared agenda.
• Here the middleware layer is typically thin or even absent.
Middleware-level protocol - Provide direct access to remote services by only
offering a convenient user interface.
• The client machine is used only as a terminal with no need for local storage.
• thin-client approach - everything is processed and stored at the server.
• Example: The X Window System (X)
Networked user interfaces
Processes Clients

Example: The X Window system

• The X Window System (X11) is a networked, client-server display protocol used

on Unix-like operating systems to create graphical user interfaces (GUIs).
• It works by separating the application (the Client) from the display hardware
(the Server), allowing applications to run locally or on remote machines while
displaying on the user's screen

Networked user interfaces

Processes Clients

Example: The X Window system

Basic organization: Unlike normal systems, X uses a client-server model

X client and server

The application acts as a client to the X-kernel, the latter running as a server
on the client’s machine.
Networked user interfaces
Processes Clients

The Two Perspectives in X

In x system you as a users are a client to those applications, but application servers
are a client to your machine (terminal).

Perspective 1: You (the User) as Client

• You sit at your terminal (the machine with the screen, keyboard)
• You want to run applications (like a web browser, or text editor)
• Those applications may be running on remote application servers
• From this perspective: YOU are the client using remote applications

Perspective 2: The Technical Client-Server Model of X

• The X server runs on your local machine (the terminal)

• The applications running on remote machines are X clients

• These X clients send display requests to your X server

• From this perspective: The APPLICATION is the client of your machine's X

server
Networked user interfaces
Processes Clients

Improving X
Practical observations
• Applications control the display using specific commands provided
by the X system.
• These commands are sent over a network and executed by the X
server (kernel) on the display machine.

Issue
• Applications frequently send requests to the X server and wait for responses
before continuing. This creates synchronous communication, which slows
down performance.
• The problem becomes worse over wide-area networks with high latency.

Solution
• Redesign or optimize the X protocol. Like use techniques that reduce
bandwidth, such as compressing X messages.

• Bandwidth usage can be reduced by up to 1000×.

Networked user interfaces
Processes Clients

Client-side software
Role of client-side software in achieving distribution transparency
• Access transparency: client-side stubs for RPCs
• Location/migration transparency: let client-side software keep track of
actual location
• Replication transparency: multiple invocations handled by client stub:

• Failure transparency: can often be placed only at client (we’re trying to

mask server and communication failures).

Client-side software for distribution transparency

Processes Servers

Servers: General organization

Basic model
A process implementing a specific service on behalf of a collection of clients. It waits
for an incoming request from a client and subsequently ensures that the request is
taken care of, after which it waits for the next incoming request.

Two basic types

• Iterative server: Server handles the request before attending a next
request. (Single-threaded servers are an example of iterative server)
• Handles one request at a time - Accept request – process – move to next
• Concurrent server: Uses a dispatcher, which picks up an incoming
request that is then passed on to a separate thread/process. E.g. fork a
new process or use multithreaded approach.

Observation
Concurrent servers are the most commonly used in practice: they can easily
handle multiple requests, notably in the presence of blocking operations, e.g. disks
General design issues
Processes Servers

Contacting a server - Where do clients contact a server?

Clients send requests to an end point, also called a port, at the machine where
the server is running.
1. Well-Known End Points: Each server listens to a specific end point
• Some services use globally assigned end points (port numbers)
• These are standardized so clients already know where to connect.
• These ports are assigned by the Internet Assigned Numbers Authority

ftp-data 20 File Transfer [Default Data]

ftp 21 File Transfer [Control]
telnet 23 Telnet
smtp 25 Simple Mail Transfer
www 80 Web (HTTP)

Key Idea:
• Client only needs the server’s IP address
• The port number is already known: Examples: servers that handle Internet
FTP requests always listen to TCP port 21.
General design issues
Processes Servers

Contacting a server - Where do clients contact a server?

2. Dynamically Assigned End Points: Many services that do not require a
pre-assigned end point.
• Some servers get a temporary port from the OS
• Example: Local Development server using a dynamically assigned port
React: npm run dev, default to 3000, but if it's busy, try 3001…

How clients find dynamically assigned endpoints.

A. End-Point Table + Daemon B. Super-Server with Request Handoff

These servers maybe stateful or stateless, called State of the Server:

Stateless Server: Stateful Server:
• Treats each request independently • Keeps track of client state (history)
• Does NOT store any client information across requests
General design issues
Processes Servers

Servers and state

Stateless servers
Never keep accurate information about the status of a client after having
handled a request:
• Don’t record whether a file has been opened (simply close it again after
access)
• Don’t keep track of your clients
• Example: A web server responding to HTTP requests After responding, it
forgets the client

Consequences
• Clients and servers are independent, No issues if connection is lost
• Server reboot does not lose client state, and vice versal.
• State inconsistencies due to client or server crashes are reduced
• Possible loss of performance because, e.g., a server cannot anticipate client
behavior (think of prefetching file blocks).
• Send full file names every time and re-authenticate each request.

General design issues

Processes Servers

Servers and state

Stateful servers
Keeps track of the status of its clients:
• Record that a file has been opened, so that prefetching can be done
• Knows which data a client has cached, and allows clients to keep local
copies of shared data.
• Example: File server maintaining a table of (client, file) pairs.

Observation
The performance of stateful servers can be extremely high, provided clients
are allowed to keep local copies. Less data sent per request and easier
interaction (client doesn’t repeat info).

Disadvantages: Can become inconsistent if failures occur

General design issues

Processes Servers

Out-of-band communication – how to handle urgent requests?

Issue
▪ When a server is already handling a request, it may need to respond to
urgent or high-priority messages.
▪ Is it possible to interrupt a server once it has accepted (or is in the process of
accepting) a service request?

Solution 1: Use a separate port for urgent data

• Server has a separate thread/process for urgent messages
• Urgent message comes in ⇒ The current (normal) request may be paused or
put on hold.
• Requirement: we require OS supports priority-based scheduling
• Advantage: Clear separation between normal and urgent communication
• Limitation: Requires extra resources (threads/processes, ports)

Solution 2: Use facilities of the transport layer

• Example: TCP allows for urgent (out-of-band) messages in same connection
• Urgent messages can be caught using OS signaling techniques

General design issues

TCP Urgent Pointer
Processes Servers

Server Clusters - Three different tiers Server

Common organization
• A server cluster is a collection of machines connected through a network,
where each machine runs one or more servers.
• A server cluster is logically organized into three tiers

Crucial element
The first tier is generally responsible for passing requests to an appropriate
server: request dispatching
Server clusters
Processes Servers

Server Clusters - Three different tiers Server

Google as an Example
First Tier: Google Front Ends
• (GFEs) are the entry points for all Google services
(Search, Gmail, YouTube, etc.).
• They act as the logical switch: terminate SSL,
perform load balancing, like GFEs use global load
balancing to send users to the nearest data center
and to avoid overloaded servers.

Second Tier: Application Servers

• Behind the GFEs, requests are forwarded to
application servers running on Google’s cluster
management system.
• These servers handle the core logic.
Third Tier: Distributed Storage Systems
• Google’s storage layer is composed of highly scalable, distributed systems:
• Google File System (GFS) – distributed file system.
• Bigtable – high-performance NoSQL database used for search indexes, Gmail,
etc.

Server clusters
Processes Servers

Request Handling
Observation
Having the first tier handle all communication from/to the cluster may lead to a
bottleneck. Dispatching Server

Application
Servers (many)

In a traditional three-tier setup, the first tier typically acts as a reverse proxy:
• It accepts client connections, terminates the TCP connection, then opens a
new connection to a backend server.
• Every request and every response passes through the dispatcher.

Server clusters
Processes Servers

Request Handling
A solution: TCP handoff (connection handoff or direct server return)
• When the switch receives a TCP connection request, it identifies the best
server for handling that request, and forwards the request packet to that server.
• The server, will send an acknowledgment back to the requesting client, but
inserting the switch's IP address as the source field of the header of the IP
packet carrying the TCP segment.
• Note that this spoofing (the creation of TCP/IP packets using another IP
address) is necessary for the client to continue executing the TCP protocol: it is
expecting an answer back from the switch, not from some arbitrary server it is
has never heard of before.

Server clusters
Processes Code migration

Code migration
Three Segments of a Process
• Code segment – contains the actual program instructions.
• Resource segment – references to external resources the process needs
(e.g., files, printers, devices, other processes).
• Execution segment – the current execution state: private data, stack,
program counter (i.e., the runtime context)..

Why Code Migration?

• What if the operation we want (e.g., moving data) isn’t offered remotely?
• Instead of moving large amounts of data over the network, we can move the
code to where the data resides. This is the core idea behind code migration.

Reasons for migrating code

Processes Code migration

Benefits of Code Migration

Motivation Explanation
Move computation from overloaded nodes to
Load balancing
underutilized ones.

Reduced Move code to the data instead of transferring large data

communication sets over the network (e.g., MapReduce).

Execute critical tasks near the client to minimize response

Latency improvement
time.

Run code on a machine that has special hardware or

Resource access
required data (e.g., database stored procedures).

Fault tolerance Relocate code away from failing or unreliable nodes.

Update or deploy new services without stopping the entire

Dynamic deployment
system.

Reasons for migrating code

Processes Code migration

Paradigms (Models) for code mobility

Weak Mobility

Strong Mobility

Models for code migration

Processes Code migration

Strong and weak mobility

Weak mobility: Move only code and (some)data segment (and
reboot execution)
• Only code (and possibly initial data) is moved; execution starts fresh at the
destination.
• Example: Java applets.

Strong mobility: Move component, including execution state

• Code plus the entire execution state (stack, program counter, etc.) is moved;
• Execution resumes exactly where it left off.
• This includes migration (moving the object) and cloning (creating a copy with
the same state).

Initiation
• Sender-initiated: The source node decides to push the code.
• Receiver-initiated: The destination node pulls the code.

Models for code migration

Processes Code migration

Migration and Local Resource

• So far, we have only accounted for migration of the code and execution segments.
• A process uses local resources that may or may not be available at the target site.
• Either references need to be updated, or resources need to be moved.
• Resources might not be as easy to move around as code and variables.
• Example: A huge database might in theory be moved across the network, but in
practice it will not.

Two issues:
• How does the resource segment refer to resources? Process-to-resource binding
• How does the resource relate with the hosting machine?, how easy it is to move
the resource? Resource-to-machine binding
• Because, when code migrates, the system must decide what to do with each
resource reference.
• The combination of how the code refers to the resource (binding type) and how
movable the resource is (machine binding) determines the best strategy—for
example, move the resource, copy it, keep it accessible remotely.
Models for code migration
Processes Code migration

Migration and Local Resource

Process-to-Resource Binding defines how a process refers to a resource:

• By identifier – uses a unique name (e.g., URL).
→ Must bind to the exact same resource after migration.
• By value – relies on the resource’s content, not its identity (e.g., standard library).
→ Can bind to an equivalent resource.
• By type – only needs a resource that provides a certain service (e.g., printer).
→ Can rebind to any local resource of the same type.
Resource-to-Machine Binding categorizes by how easily they can be moved:
• Unattached – easily moved (e.g., data files, cache).
• Fastened – movable but at high cost (e.g., local databases, entire websites).
• Fixed – bound to a specific machine, cannot move (e.g., special hardware).

Models for code migration

Processes Code migration

Actions for Handling Resources During Migration

Actions to be taken with respect to the references to local resources when migrating
code to another machine. Resource-to-Machine Binding
Process Binding Unattached Fastened Fixed
GR, MVGR preferred
Process-to-Resource Binding

MV, GRMV preferred GR (MV infeasible)

(avoid costly move); MV
(cheap, preserves Must use remote access
By Identifier if migration is
identity); GR if remote since resource cannot
permanent or remote
access is efficient. move.
access is slow.
CP (best), MV, GR GR, CPGR preferred; CP GR, CP GR preferred; CP
By Value Copying is simplest and if resource is static and possible if value can be
cheapest. copy is acceptable. read and duplicated.
RB (best), MV, GR, CP RB, GR, CP Rebind RB (best), GR Use local
By Type Rebind to a local preferred; fallback to equivalent; otherwise
equivalent resource. GR or CP if needed. access remotely.
MV (Move): Move the resource to the new machine
GR (Global Reference): Access the resource remotely
Legend
CP (Copy): Copy the resource’s value
RB (Rebind): Bind to a different local resource of the same type
Models for code migration
Processes Code migration

Migration in heterogeneous systems

Main problem
• The target machine may not be suitable to execute the migrated code.
▪ A different instruction set architecture (x86 vs. ARM).
▪ A different operating system (Linux vs. Windows).
• The definition of process/thread/processor context is highly dependent on local
hardware, operating system and runtime system

Only solution:
Make use of an abstract machine that is implemented on different platforms
• Interpreted languages running on a virtual machine
▪ E.g., Java/JVM, scripting languages
• Virtual machine monitors allowing migration of complete OS + apps.

Migration in heterogeneous systems

End of Chapter 3