CSIE,NTUT,Taiwan1
Server Software Design
Algorithms and Issues
Chuan-Ming Liu
Computer Science and Information Engineering
Spring 2004,NTUT
TAIWAN
CSIE,NTUT,Taiwan2
Conceptual Server Algorithm
Simple Server Algorithm
1,Create a socket
2,Bind the socket to the port
3,Enter an infinite loop
Accept request
Process request
Reply request
Not enough in practice generally
CSIE,NTUT,Taiwan3
Conceptual Server Algorithm
Consider file transfer
First client needs a 200 MB file
Second client needs a 20 byte file
If the server processes them in FIFO fashion
The second client will wait an unreasonable
amount of time for a small transfer
Server usually handles more than one
request at a time
CSIE,NTUT,Taiwan4
Concurrent v.s,Iterative
Iterative server,one request at a time
Concurrent server,multiple requests at
one time
Note,the concurrency is conceptual
and generally will use one thread for
one request
Concurrent server refers to whether the
server permits multiple requests to
proceed concurrently,not whether the
underlying implementation uses
multiple and concurrent threads
CSIE,NTUT,Taiwan5
Concurrent v.s,Iterative
Concurrent servers are difficult to
design and build
Why concurrency?
Long delay caused by iterative servers
Performance bottleneck resulted from
iterative servers effects many clients
CSIE,NTUT,Taiwan6
Connection Access or Not
Two major transport protocols:
TCP (Transmission Control Protocol)
UDP (User Datagram Protocol)
TCP is connection-oriented and UDP is
connectionless
The corresponding servers are
Connection-oriented servers
Connectionless serves
CSIE,NTUT,Taiwan7
TCP Semantics
Point-to-point communication
Reliable connection establishment
Reliable Delivery
Flow controlled transfer
Full-duplex transfer
Stream paradigm
CSIE,NTUT,Taiwan8
UPD Semantics
Many-to-many communication
Unreliable Service
Lack of flow control
Message paradigm
CSIE,NTUT,Taiwan9
TCP or UDP?
Because the semantics of TCP and
UDP differ sharply,a designer cannot
choose between connection-oriented
and connectionless transport protocols
without considering the semantics
required by the application protocol
Depends on the applications,not the
types
CSIE,NTUT,Taiwan10
Connection-Oriented Servers
Easier to program since TCP provide
all the reliability
Drawbacks:
Need a separate socket for each
connection
Cares about the socket allocation and
resource consuming
Resource limitation problem – due to the
clients crash often
CSIE,NTUT,Taiwan11
Connectionless Servers
Access multiple hosts from a single socket
No problem of resource depletion
No reliable delivery
Need to take care of the reliability
Usually,clients take care of retransmitting
request
Server may retransmit as well
Achieving reliability can be difficult
Timeout
retransmission
CSIE,NTUT,Taiwan12
Connectionless Servers
TCP does not allow multicast or
broadcast
Multicast and broadcast services
require UDP
Any server that accepts or responds to
multicast and broadcast communication
must be connectionless
CSIE,NTUT,Taiwan13
Stateful or Stateless
The issue of stateless arises from a
need to ensure reliability
For a service using connectionless
transport,like UDP,the application
protocols need to ensure the reliability
CSIE,NTUT,Taiwan14
Stateless Servers
Consider a connectionless server that
allows clients to read information from
files
Clients need to specify
Filename
Position in the file
Amount to read
Straightforward method is to handle each
request independently
CSIE,NTUT,Taiwan15
Optimizing Stateless Servers
Observe that
The overhead to open and close files is high
Data read may be few
Sequentially read files
Using buffers to assist reading files
This may be similar to the stateful servers
Hashing table is used
The IP address and the port number form the
index
CSIE,NTUT,Taiwan16
Optimizing Stateless Servers
Filename,Y
Offset 1024
Buffer pointer:
Filename,X
Offset,512
Buffer pointer,Buffer for file XStarting at byte 512
Buffer for file Y
Starting at byte 1024
Hash(ip,port)
CSIE,NTUT,Taiwan17
Optimizing Stateless Servers
Improvement can be achieved when all the
assumptions meet
Problem arises when the client programs fails
Consider the situation that the client crashes
Buffer will be full
Adjustment can be done by least recently
used (LRU) rule for maintaining the hash
table
Thrashing occurs
CSIE,NTUT,Taiwan18
Optimizing Stateless Servers
A programmer must be extremely
careful when optimizing a stateless
server because managing small
amounts of state information can
consume resources if clients crash and
reboot frequently or if the underlying
network duplicates or delay messages
CSIE,NTUT,Taiwan19
Types of Servers
Iterative
Connectionless
Iterative
Connection-oriented
Concurrent
Connectionless
Concurrent
Connection-oriented
CSIE,NTUT,Taiwan20
Iterative or Concurrent
Request processing time:
total time the server takes to handle a
request
Observed response time:
total delay from sending a request to
receiving the response
Server has a queue of requests to
handle
CSIE,NTUT,Taiwan21
Iterative or Concurrent
If N is the average length of the request
queue,then
observed response time?(2/N+1) * request
processing time
observed response time increases in
proportion to N and N should be
reasonable small,say N=5
When N is small,an iterative server is ok;
otherwise,a concurrent serve is preferred
CSIE,NTUT,Taiwan22
Iterative or Concurrent
Alternatively,the overall load can be
considered
Suppose a server is designed to handle K clients
Each client sends R requests per second
Total number of requests is RK
The server’s processing time should be less than
1/KR second per request
If the server can handle at the required rate,
iterative way is ok; otherwise,concurrent
method is selected
CSIE,NTUT,Taiwan23
Iterative Server Algorithms
Easy to design,program,debug,and
modify.
Working best with simple services
accessed by a connectionless access
protocol
CSIE,NTUT,Taiwan24
Connection-oriented
1,Create a socket and bind to the well-known
address for the service being offered
2,Place the socket in passive mode and make it
ready for use by a server
3,Accept the next connection request from the
socket,and obtain a new socket for the
connection
4,Repeatedly read,process,and reply a request
5,When a particular connection is done,close
the connection and go back to step 3
CSIE,NTUT,Taiwan25
Binding a Well-known Address
Like clients,servers use procedure
getportbyname( ) to map a service name
into a well-known port number
bind( ) system call can specify a connection
int bind(int sockfd,struct sockaddr
*my_addr,socklen_t addrlen);
Bind needs IP address,but it is difficult to
select the IP address
CSIE,NTUT,Taiwan26
bind()
BIND(2) Linux Programmer滻 Manual BIND(2)
NAME
bind - bind a name to a socket
SYNOPSIS
#include <sys/types.h>
#include <sys/socket.h>
int bind(int sockfd,struct sockaddr *my_addr,socklen_t addrlen);
CSIE,NTUT,Taiwan27
INADDR_ANY
Using a special constant,INARRD_ANY,
provided by the socket interface to help
binding IP address
INADDR_ANY
specifies a wildcard address that matches any
of the host’s IP address
Has a single server on a multi-homes host
accept incoming communication addressed to
any of the host’s IP address
CSIE,NTUT,Taiwan28
Connection-oriented
1,Create a socket and bind to the well-known
address for the service being offered
2,Place the socket in passive mode and make it
ready for use by a server
3,Accept the next connection request from the
socket,and obtain a new socket for the
connection
4,Repeatedly read,process,and reply a request
5,When a particular connection is done,close
the connection and go back to step 3
CSIE,NTUT,Taiwan29
Passive socket
Using listen( ) system call to place a
socket in passive mode
listen( ) also takes an argument that
specifies the length of an internal
request queue for the socket
CSIE,NTUT,Taiwan30
listen()
LISTEN(2) Linux Programmer滻 Manual LISTEN(2)
NAME
listen - listen for connections on a socket
SYNOPSIS
#include <sys/socket.h>
int listen(int s,int backlog);
DESCRIPTION
To accept connections,a socket is first created with socket(2),a
willingness to accept incoming connections and a queue limit for incoming
connections are specified with listen,and then the connections are
accepted with accept(2),The listen call applies only to sockets of
type SOCK_STREAM or SOCK_SEQPACKET.
CSIE,NTUT,Taiwan31
Connection-oriented
1,Create a socket and bind to the well-known
address for the service being offered
2,Place the socket in passive mode and make it
ready for use by a server
3,Accept the next connection request from the
socket,and obtain a new socket for the
connection
4,Repeatedly read,process,and reply a request
5,When a particular connection is done,close
the connection and go back to step 3
CSIE,NTUT,Taiwan32
Accept Connections
Using accept( ) system call to obtain
the next incoming connection request
After connection,a server uses read
(recv) to receive requests and write
(send) to send replies
When the server finishes with the
connection,it calls close( ) to release
the socket
CSIE,NTUT,Taiwan33
Connectionless
1,Create a socket and bind to the well-known
address for the service being offered
2,Repeatedly read,process,and reply a request
CSIE,NTUT,Taiwan34
Reply Address
Socket interface provides two ways to
specify a remote endpoint
One is for the clients (we have discussed)
Connectionless servers uses sendto( )
socket call
sendto( )
specifies a datagram and an address
int sendto (int s,const void *msg,size_t len,int flags,
const struct sockaddr *to,socklen_t tolen);
How to
get this?
CSIE,NTUT,Taiwan35
sendto( )
SEND(2) Linux Programmer滻 Manual SEND(2)
NAME
send,sendto,sendmsg - send a message from a socket
SYNOPSIS
#include <sys/types.h>
#include <sys/socket.h>
int send(int s,const void *msg,size_t len,int flags);
int sendto(int s,const void *msg,size_t len,int flags,const struct
sockaddr *to,socklen_t tolen);
int sendmsg(int s,const struct msghdr *msg,int flags);
CSIE,NTUT,Taiwan36
The recvfrom( ) call
Two arguments specify two buffers
One buffer for arriving datagram
The other buffer for the sender’s address
Recvfrom( )
int recvfrom(int s,void *buf,size_t len,int flags,
struct sockaddr *from,socklen_t *fromlen);
CSIE,NTUT,Taiwan37
recvfrom( )
RECV(2) Linux Programmer滻 Manual RECV(2)
NAME
recv,recvfrom,recvmsg - receive a message from a socket
SYNOPSIS
#include <sys/types.h>
#include <sys/socket.h>
int recv(int s,void *buf,size_t len,int flags);
int recvfrom(int s,void *buf,size_t len,int flags,struct sockaddr
*from,socklen_t *fromlen);
int recvmsg(int s,struct msghdr *msg,int flags);
CSIE,NTUT,Taiwan38
Concurrent Server Algorithms
Master and slaves
Most concurrent servers use multiple threads
A single thread,known as master,executes
initially
Master thread opens a socket at some port and
waits for the next request
A slave (possibly in a process) is created by
the master to handle each request
The master never communicates with client
It is possible to achieve concurrency by a
thread
CSIE,NTUT,Taiwan39
Connectionless Servers
Master 1,Create a socket,bind the
address,and leave the socket
unconnected
Master 2,Repeatedly call recvfrom to
receive the next request and create a
new slave thread to handle the request
CSIE,NTUT,Taiwan40
Connectionless Servers
Slave 1,Begin with a specific request
from the Master as well as access to
the socket
Slave 2,Form a reply and send it back to
the client using sendto
Slave 3,Exit
CSIE,NTUT,Taiwan41
Connectionless Servers
Because process or thread creation is
expensive,few connectionless servers
have concurrent implementation
CSIE,NTUT,Taiwan42
Connection-oriented
Servers
Connection-oriented servers
implement concurrency among
connections rather than among
individual requests
CSIE,NTUT,Taiwan43
Connection-oriented Servers
Master 1,Create a socket,bind the address,
and leave the socket unconnected
Master 2,Place the socket in passive mode
and make it ready for use by a server
Master 3,Repeatedly call accept to receive
the next request and create a new slave
thread or process to handle the request
CSIE,NTUT,Taiwan44
Connectionless Servers
Slave 1,Begin with a connection passed
from the Master (i.e,a socket for the
connection)
Slave 2,Interact with the client using the
connection
Slave 3,Close the connection and exit
CSIE,NTUT,Taiwan45
Concurrency
Implementation
Master
Process
Slave
Processes
Slave
ThreadsMasterThread
CSIE,NTUT,Taiwan46
Concurrency by One Thread
The creation of thread and process is
expensive
Many applications need to share
information among connections
Apparent concurrency with a single thread
X window
CSIE,NTUT,Taiwan47
Concurrency by One Thread
It is possible to share memory between
threads,but if the request load does not
exceed the server’s capacity to handle
them,one single thread is still ok
To achieve this,using select ( ) call for
asynchronous I/O
One key point is that a socket is treated as
an I/O device
CSIE,NTUT,Taiwan48
Concurrency by One Thread
1,Create a socket and bind the address,Add
socket to the list of I/O’s
2,Use select to wait for I/O on existing sockets
3,If the original socket is ready,use accept to
obtain the next connection and add the new
socket to the list of I/O’s
4,If some socket other than the original is
ready,use recv (read) and send (write) to
communicate
5,Continue with step 2
CSIE,NTUT,Taiwan49
When to Use Each Server Type
Iterative v.s,Concurrent
Real v.s,Apparent concurrency
Connection-oriented v.s,
Connectionless
CSIE,NTUT,Taiwan50
Server Types
Iterative,connectionless server
Most common for connectionless servers
Iterative,connection-oriented server
Less common servers
Concurrent,connectionless server
Uncommon type
Concurrent,connection-oriented server
Most general type
Multi-process,multi-thread,or single thread
CSIE,NTUT,Taiwan51
Server Deadlock
What is deadlock?
A condition in which a program or set of
programs can not proceed because they
are blocked waiting for an event that will
never happen
In case of server,deadlock means that the
server ceases to answer requests
CSIE,NTUT,Taiwan52
Server Deadlock
client server
An iterative connection-oriented server
Connected but no send
Call recv
to receive Server is blocked
CSIE,NTUT,Taiwan53
Server Deadlock
client server
An iterative connection-oriented server
Connected and send
Never reads
response
Flow control
interferes
Buffer full
Server blocks
CSIE,NTUT,Taiwan54
Server Deadlock
Deadlock arises because a calling
program blocks when the OS can not
satisfy a system call
Call to send (write) will block the caller
if no buffer space for sending data
Call to recv (read) will block the caller
until TCP receives data
Any server using only one thread can be
subject to deadlock