Модель кассира

В этой классической модели объекты появляются случайным образом и обслуживаются за случайное время ограниченным количеством серверов. Моделирование позволяет определить идеальное количество серверов. Продолжительность обслуживания в следующей модели зависит от клиента и определяется случайным образом. Вдобавок мы не знаем, сколько новых клиентов будет прибывать за каждый период времени, поэтому эта величина тоже определяется случайным образом.

//: concurrency/BankTellerSimulation.java

// Пример использования очередей и многопоточного программирования..

// {Args: 5}

import java.util.concurrent.*;

import java.util.*;

// Объекты, доступные только для чтения, не требуют синхронизации:

class Customer {

private final int serviceTime;

public Customer(int tm) { serviceTime = tm; }

public int getServiceTime() { return serviceTime; }

public String toString() {

return "[" + serviceTime + "]";

}

}

// Очередь клиентов умеет выводить информацию о своем состоянии:

class CustomerLine extends ArrayBlockingQueue<Customer> {

public CustomerLine(int maxLineSize) {

super(maxLineSize);

}

public String toString() {

if(this.size() == 0)

return "[Empty]";

StringBuilder result = new StringBuilder();

for(Customer customer : this)

result.append(customer);

return result.toString();

}

}

// Случайное добавление клиентов в очередь:

class CustomerGenerator implements Runnable {

private CustomerLine customers;

private static Random rand = new Random(47);

public CustomerGenerator(CustomerLine cq) {

customers = cq;

}

public void run() {

try {

while(!Thread.interrupted()) {

TimeUnit.MILLISECONDS.sleep(rand.nextInt(300));

customers.put(new Customer(rand.nextInt(1000)));

}

} catch(InterruptedException e) {

System.out.println("CustomerGenerator interrupted");

}

System.out.println("CustomerGenerator terminating");

}

}

class Teller implements Runnable, Comparable<Teller> {

private static int counter = 0;

private final int id = counter++;

// Счетчик клиентов, обслуженных за текущую смену:

private int customersServed = 0;

private CustomerLine customers;

private boolean servingCustomerLine = true;

public Teller(CustomerLine cq) { customers = cq; }

public void run() {

try {

while(!Thread.interrupted()) {

Customer customer = customers.take();

TimeUnit.MILLISECONDS.sleep(

customer.getServiceTime());

synchronized(this) {

customersServed++;

while(!servingCustomerLine)

wait();

}

}

} catch(InterruptedException e) {

System.out.println(this + "interrupted");

}

System.out.println(this + "terminating");

}

public synchronized void doSomethingElse() {

customersServed = 0;

servingCustomerLine = false;

}

public synchronized void serveCustomerLine() {

assert !servingCustomerLine:"already serving: " + this;

servingCustomerLine = true;

notifyAll();

}

public String toString() { return "Teller " + id + " "; }

public String shortString() { return "T" + id; }

// Используется приоритетной очередью:

public synchronized int compareTo(Teller other) {

return customersServed < other.customersServed ? -1 :

(customersServed == other.customersServed ? 0 : 1);

}

}

class TellerManager implements Runnable {

private ExecutorService exec;

private CustomerLine customers;

private PriorityQueue<Teller> workingTellers =

new PriorityQueue<Teller>();

private Queue<Teller> tellersDoingOtherThings =

new LinkedList<Teller>();

private int adjustmentPeriod;

private static Random rand = new Random(47);

public TellerManager(ExecutorService e,

CustomerLine customers, int adjustmentPeriod) {

exec = e;

this.customers = customers;

this.adjustmentPeriod = adjustmentPeriod;

// Начинаем с одного кассира:

Teller teller = new Teller(customers);

exec.execute(teller);

workingTellers.add(teller);

}

public void adjustTellerNumber() {

// Фактически это система управления. Регулировка числовых

// параметров позволяет выявить проблемы стабильности

// в механизме управления.

// Если очередь слишком длинна, добавить другого кассира:

if(customers.size() / workingTellers.size() > 2) {

// Если кассиры отдыхают или заняты

// другими делами, вернуть одного из них:

if(tellersDoingOtherThings.size() > 0) {

Teller teller = tellersDoingOtherThings.remove();

teller.serveCustomerLine();

workingTellers.offer(teller);

return;

}

// Иначе создаем (нанимаем) нового кассира

Teller teller = new Teller(customers);

exec.execute(teller);

workingTellers.add(teller);

return;

}

// Если очередь достаточно коротка, освободить кассира:

if(workingTellers.size() > 1 &&

customers.size() / workingTellers.size() < 2)

reassignOneTeller();

// Если очереди нет. достаточно одного кассира:

if(customers.size() == 0)

while(workingTellers.size() > 1)

reassignOneTeller();

}

// Поручаем кассиру другую работу или отправляем его отдыхать:

private void reassignOneTeller() {

Teller teller = workingTellers.poll();

teller.doSomethingElse();

tellersDoingOtherThings.offer(teller);

}

public void run() {

try {

while(!Thread.interrupted()) {

TimeUnit.MILLISECONDS.sleep(adjustmentPeriod);

adjustTellerNumber();

System.out.print(customers + " { ");

for(Teller teller : workingTellers)

System.out.print(teller.shortString() + " ");

System.out.println("}");

}

} catch(InterruptedException e) {

System.out.println(this + "interrupted");

}

System.out.println(this + "terminating");

}

public String toString() { return "TellerManager "; }

}

public class BankTellerSimulation {

static final int MAX_LINE_SIZE = 50;

static final int ADJUSTMENT_PERIOD = 1000;

public static void main(String[] args) throws Exception {

ExecutorService exec = Executors.newCachedThreadPool();

// Если очередь слишком длинна, клиенты уходят:

CustomerLine customers =

new CustomerLine(MAX_LINE_SIZE);

exec.execute(new CustomerGenerator(customers));

// TellerManager добавляет и убирает кассиров

// по мере необходимости:

exec.execute(new TellerManager(

exec, customers, ADJUSTMENT_PERIOD));

if(args.length > 0) // Необязательный аргумент

TimeUnit.SECONDS.sleep(new Integer(args[0]));

else {

System.out.println("Press 'Enter' to quit");

System.in.read();

}

exec.shutdownNow();

}

}

<spoiler text="Output:"> (Sample)

[429][200][207] { T0 T1 }

[861][258][140][322] { T0 T1 }

[575][342][804][826][896][984] { T0 T1 T2 }

[984][810][141][12][689][992][976][368][395][354] { T0 T1 T2 T3 }

Teller 2 interrupted

Teller 2 terminating

Teller 1 interrupted

Teller 1 terminating

TellerManager interrupted

TellerManager terminating

Teller 3 interrupted

Teller 3 terminating

Teller 0 interrupted

Teller 0 terminating

CustomerGenerator interrupted

CustomerGenerator terminating

</spoiler> Объекты Customer очень просты; они содержат только поле данных final int. Так как эти объекты никогда не изменяют своего состояния, они являются объектами, доступными только для чтения, и поэтому требуют синхронизации или использования volatile. Вдобавок каждая задача Teller удаляет из очереди ввода только один объект Customer и работает с ним до завершения, поэтому задачи все равно будут работать с Customer последовательно.

Класс CustomerLine представляет собой общую очередь, в которой клиенты ожидают обслуживания. Он реализован в виде очереди ArrayBlockingQueue с методом toString(), который выводит результаты в желаемом формате. Генератор CustomerGenerator присоединяется к CustomerLine и ставит объекты Customer в очередь со случайными интервалами.

Teller извлекает клиентов Customer из CustomerLine и обрабатывает их последовательно, подсчитывая количество клиентов, обслуженных за текущую смену. Если клиентов не хватает, его можно перевести на другую работу (doSomethingElse()), а при появлении большого количества клиентов — снова вернуть на обслуживание очереди методом serveCustomerLine(). Чтобы приказать следующему кассиру вернуться к очереди, метод compareTo() проверяет количество обслуженных клиентов, чтобы приоритетная очередь автоматически ставила в начало кассира, работавшего меньше других.

Вся основная деятельность выполняется в TellerManager. Этот класс следит за всеми кассирами и за тем, что происходит с клиентами. Одна из интересных особенностей данной имитации заключается в том, что она пытается подобрать оптимальное количество кассиров для заданного потока покупателей. Пример встречается в методе adjustTellerNumber() — управляющей системе для надежной, стабильной регулировки количества кассиров. У всех управляющих систем в той или иной мере присутствуют проблемы со стабильностью; слишком быстрая реакция на изменения снижает стабильность, а слишком медленная переводит систему в одно из крайних состояний.

Резюме

В этой главе я постарался изложить основы многопоточного программирования с использованием потоков Java. Прочитав ее, читатель должен понять следующее:

· Программу можно разделить на несколько независимых задач.

· Необходимо заранее предусмотреть всевозможные проблемы, возникающие при завершении задач.

· Задачи, работающие с общими ресурсами, могут мешать друг другу. Основным средством предотвращения конфликтов является блокировка.

· В неаккуратно спроектированных многозадачных системах возможны взаимные блокировки.

Очень важно понимать, когда рационально использовать параллельное выполнение, а когда этого делать не стоит. Основные причины для его использования:

· управление несколькими подзадачами, одновременное выполнение которых позволяет эффективнее распоряжаться ресурсами компьютера (включая возможность незаметного распределения этих задач по нескольким процессорам);

· улучшенная организация кода;

· удобство для пользователя.

Классический пример распределения ресурсов — использование процессора во время ожидания завершения операций ввода/вывода. Классический пример чуткого пользовательского интерфейса — отслеживание нажатий кнопки «Пре­рвать» во время продолжительного процесса загрузки.

Дополнительным преимуществом потоков является то, что они заменяют «тяжелое» переключение контекста процессов (порядка 1000 и более инструкций) «легким» переключением контекста выполнения (около 100 инструкций). Так как все потоки процесса разделяют одно и то же пространство памяти, легкое переключение затрагивает только выполнение программы и локальные переменные. С другой стороны, чередование процессов — тяжелое переключение контекста — требует обновления всего пространства памяти.

Основные недостатки многозадачности:

· Замедление программы, связанное с ожиданием освобождения блокированных ресурсов.

· Дополнительная нагрузка на процессор для управления потоками.

· Совершенно ненужная сложность, являющаяся следствием неудачных решений при проектировании программы.

· Аномальные ситуации: взаимные блокировки, конфликты доступа, гонки и т. д.

· Непоследовательное поведение на различных платформах. Например, при разработке некоторых примеров для данной книги я обнаружил ситуации гонки, быстро проявлявшиеся на некоторых компьютерах, но незаметные на других.

Пожалуй, основные трудности с потоками возникают тогда, когда несколько потоков одновременно пытаются использовать один и тот же ресурс — например, память объекта, и вы должны сделать так, чтобы этого ни в коем случае не произошло. Для этого нужно разумно использовать ключевое слово synchronized — полезный инструмент языка, который тем не менее необходимо хорошо понимать (без этого в программе может незаметно возникнуть опасность взаимной блокировки).

Вдобавок многозадачное программирование сродни искусству. Язык Java существует для того, чтобы вы могли свободно создавать столько объектов, сколько вам нужно для решения вашей задачи — по крайней мере, в теории это так. (Например, создание миллионов объектов для проведения проекционно-разностного анализа вряд ли будет иметь смысл в Java.) Однако оказывается, что количество потоков упирается в определенный «потолок», так как после превышения этой-границы потоки становятся неподатливыми. Это критическое число трудно определить, зачастую оно зависит от операционной системы и виртуальной машины Java, значение может находиться где-то в районе сотни, а может исчисляться тысячами. Если для решения своей задачи вам требуется небольшая группа потоков, это ограничение не актуально, но при разработке больших программ оно может создать затруднения.