Purple Server Overview

Blocking Queue

• If a thread tries to remove an item from an empty queue

• Then it blocks until an item is placed inside

• Uses wait/notify technique

JDK 1.2 Collections

• Set

• List

• Map

• Queue
  • Built on top of LinkedList

Basic Object Model

• Acceptor (thread)

• Clients (set)

• Receiver (thread)

• Incoming (queue)

• Processor (thread)

Basic Object Model (Fig.)

Acceptor Thread

• Listens for incoming connections

• Creates a client object

• Adds it to clients set

Clients Set

• Set of all active clients

• Synchronized methods
  • Only one thread at a time can access

Receiver Thread

• Walks down clients set

• For each client, checks if message is (fully) available

• Reads message and places it on incoming queue

• Uses non-blocking input streams

Receiver Thread: Alternative

• Alternative: one receiver thread per client

• Each receiver thread blocks until input available

• Con:
  • Reach number of threads bottleneck
  • Scheduling not determined - could starve or do in weird order

Incoming Queue

• Queue of messages

• Synchronized methods
  • Only one thread at a time can access

• Blocking queue
  • If a thread tries to get a message from an empty queue, it blocks until another thread adds a message

Processor Thread

• While incoming queue is not empty

• Pops message off incoming queue

• Delivers it

Full Object Model

• Checker (thread)

• Problems (list)

• Auditor (thread)

Full Object Model (Fig.)

Problems List

• List of clients who have problems

• Receiver can add a client to problems list if it gets a socket read error

• Processor can add a client to problems list if it gets a socket write error

• Checker thread periodically disconnects them all

Checker Thread

• Wakes up every N seconds

• Walks list of clients

• Move to problems list
  • If N seconds has passed (“timeout”)
  • If socket has a problem

• Walk problems list and actively close each client

Auditor Thread

• Every N seconds, wakes up

• Collects and prints statistics

Non-Blocking Input Stream

• Needed for receiver to do its job

• If a full message is not available, it does NOT block

• Instead, it returns null

• Tricky to implement
  • Must use available(), mark() and reset() cleverly

Thread Safety Policies

• All data objects synchronized

• All data objects independent

• Therefore no possibility of deadlock in the data objects themselves

Thread Safety Policies

• Thread objects must be very careful to avoid deadlock

• Current model: no multi-object transactions

• Example
  • Checker does clients.remove(c) then problems.add(c)
  • NOT

    synchronized(clients) { synchronized(problems) {
    
    clients.remove(c); problems.add(c);
    }}

  • It's OK if it's interrupted between remove and add

Priority: Why?

• In low-volume server, all threads are normally blocked

• When something needs to happen, it happens

• That's the beauty of threads!

• So priorities are irrelevant
  • If you don’t know what you’re doing, don’t mess with priorities

Priority: Why?

• In high-volume server, many threads always have something to do

• Important to do things in the right order

• Deal with starvation issue

Priorities: General Strategies

• Threads that have more to do get lower priority

• Counterintuitive

• Cut to head of line for short tasks

Priorities: Queuing Strategies

• Most important: keep incoming queue empty

• So we don't get bogged down

• Minimize latency for received messages

Priorities: Decisions

• Don't want to add new messages if we're already busy
  • Therefore processor > receiver

• Don't want to accept new connections if we're already busy
  • Therefore processor > acceptor

• Implication:
  • Receiver and acceptor may starve?
  • No: queue will eventually get cleared

Priorities: Decisions

• Want to be able to accept new connections, even if a currently connected client has something to say
  • Therefore acceptor > receiver

Priorities: Decisions

• Checker's job is brief but important

• Needs to wake up, check all clients, and go back to sleep

• Therefore checker > processor

Priorities: Decisions

• Auditor's job is brief but important

• Need to get accurate statistics -- timing is crucial

• Can't wait around for other threads to finish

• Therefore auditor > checker

Priorities: Conclusion

• Auditor - 10

• Checker - 8

• Processor - 6

• Acceptor - 4

• Receiver - 2

• Goes by twos to accommodate Windows threading model

Processor Thread Behavior

• Processor thread does:

  1. Pop message off incoming queue
  
  2. Deliver it
  3. Loop

• Very independent

Processor Thread Blocking

• Step 1 (pop message) may block

• If queue is empty

• Allows other threads to wake up and fill queue

Processor Thread Blocking

• Step 2 (delivery) may block
  • If network is busy
  • If OS socket buffer is full

• Bad, because queue is still full

• Increases latency (delivery time) for already-queued messages
  • While new messages are arriving, old messages should be delivered instead

Multiple Processor Threads

• Solution: have many processor threads working simultaneously

• If one blocks, another picks up the next message

Multiple Processors (Fig.)

How Many Threads?

1. Constant, tuned per application

2. Dynamic a/k/a thread pooling

Thread Pooling

• Thread pool keeps a certain number of threads alive

• Other threads ask the thread pool to perform a task

• If an existing thread is available, that thread performs the task

• Else a new thread is created, or the task blocks until one is available
  • (depending on policy)

Thread Pooling (Cont.)

• Removes overhead of creating threads

• Allows modular task strategy

Information Flow

• Decoupling threads with buffers is a good idea
  • Maximizes concurrency
  • Smooths out bursty differences in rate

• Can cause problems with information flow
  • Producers outpace Consumers
  • Too many threads

Limiting Flow

• Bounded Buffers
  • Stalls producers if they outpace consumers

• Bounded Thread Pools
  • Prevents thrashing

• Rate-adjustment / back-pressure
  • Consumer asks Producer to slow down

Another Problem

• One message, multiple recipients, one processor thread

• If one recipient is in Finland, it will stall the remaining recipients for that message

Another Problem: Solutions

• Solution 1: one message queue per client; thread pool applied to these delivery queues

• Solution 2: split multi-message into several single-recipient messages
  • Called a Splitter (or Fork or Multicaster)
  • Also possible: Routers, Mergers, Collectors, Combiners, Conduits -- see Lea’s Concurrent Programming in Java

Debugging Techniques

• Make sure to trap all Throwables in your Thread objects run() method
  • Otherwise a stray OutOfMemoryError or NullPointerException will kill your thread and it will look like deadlock

• Good logging procedure is vital
  • I use a global log method that outputs the name of the thread and the time in addition to the message
  • Name your threads at creation time

Thread Dump

• Control-backslash in Solaris

• Control-break in Windows
  • Unfortunately, it scrolls
  • There’s no way to redirect standard error
  • Oops

Bots

• PingBot
  • periodically sends a message to itself, measures the latency

• QuoteBot
  • sends random Zippy quotes to mimic a chat room