Мой бизнес — авторемонт, и это немного отдаляет меня от компьютерных наук. С другой стороны, авторемонт — это удивительная область, в которой очень много программного обеспечения. Я имею в виду это не только в том смысле, что в автомобилях больше вычислительных элементов, хотя это тоже проблема.
Многие виды бизнеса можно вести только на бумаге, хотя это было бы обременительно. Однако у авторемонта есть несколько особых проблем.
Во-первых, время выполнения работ стандартизировано. Почти каждая работа, которая может быть выполнена почти с каждым автомобилем, имеет контрольное время, которое должно занять у компетентного специалиста. Это означает, что если ваша мастерская работает легально, то цена работы должна быть следующей: учетное время на выполнение работы * ставка труда мастерской + стоимость деталей, необходимых для выполнения работы * (1 + наценка мастерской на детали) + номинальные накладные расходы.
Во-вторых, каждый автомобиль отличается от другого, часто в причудливых формах. В старые времена существовали большие руководства по обслуживанию для каждого года для каждой марки и модели — они все еще существуют, но на практике их вытеснило программное обеспечение. Даже если вы можете самостоятельно разобраться, как сделать ту или иную работу, вам часто нужны спецификации — насколько сильно затянуть болт, сколько жидкости добавить и тому подобное.
В-третьих, если вы достаточно хорошо разбираетесь в диагностике и ремонте электрооборудования, вам понадобятся электрические схемы.
Да, ремонт автомобилей предшествовал появлению компьютеров, но в те времена автомобили были намного проще. Неудивительно, что имеющееся в настоящее время программное обеспечение для авторемонтной мастерской — не самое лучшее. Наша самая большая проблема — это параллелизм: Наше нынешнее программное обеспечение может работать в режиме клиент/сервер по локальной сети. Когда на одном компьютере выполняется заказ, другие компьютеры полностью блокируются.
Это заставило меня много думать о том, как следует обрабатывать параллелизм в данной ситуации, поскольку вскоре я начну писать наше собственное программное обеспечение для управления магазином.
Условия гонки
Основная проблема заключается в том, что мы называем «условиями гонки». Представьте, что у вас есть общая переменная x, изначально 0, и пять потоков выполняют x++. Что произойдет? Это сложно, потому что определение x++ выглядит примерно так:
load x into register1
add 1 to register1
store register1 into x
Конечное значение x может быть любым от 1 до 5, в зависимости от того, как чередуются инструкции. Например, если рассматривать только два потока, то можно сделать так:
thread 1: load x [r = 0]
thread 1: add 1 [r = 1]
thread 1: store x [x = 1]
thread 2: load x [r = 1]
thread 2: add 1 [r = 2]
thread 2: store x [x = 2]
В этом случае x равно 2. Инструкции также могут выглядеть следующим образом:
thread 1: load x [r = 0]
thread 2: load x [r = 0]
thread 1: add 1 [r = 1]
thread 2: add 1 [r = 1]
thread 1: store x [x = 1]
thread 2: store x [x = 1]
В этом случае x равен 1.
Это открывает множество других возможностей: блокировки взаимного исключения (мьютекс), семафоры, транзакции… Вы вводите специальные инструкции процессора, такие как «атомарная проверка и установка», которые могут делать следующее
if(x == 0) {
x = 1;
return true;
}
else {
return false;
}
за один цикл. Это позволяет вам начать делать такие вещи, как,
int lock = 0;
void foo() {
while(!atomic_check_and_set(lock)) {
sleep(100);
}
// Do some stuff, knowing that other threads won't interfere
lock = 0;
}
Это требует большого усердия для правильного выполнения; очень легко повесить вашу программу, неправильно обрабатывая блокировки. Именно поэтому внимание сместилось на более «безопасные» вещи, такие как обещания и рабочие очереди.
Есть еще одна проблема с блокировкой, о которой стоит упомянуть. Блокировка должна иметь некоторый уровень детализации, когда для разных данных существуют разные блокировки. Что если потоку нужно три блокировки? Более того, что если нескольким потокам нужны перекрывающиеся подмножества блокировок? Одна вещь, которую вы абсолютно точно не должны делать:
int lock1 = lock2 = lock3 = 0;
void foo() {
while(!atomic_check_and_set(lock1)) sleep(100);
while(!atomic_check_and_set(lock2)) sleep(100);
while(!atomic_check_and_set(lock3)) sleep(100);
// do stuff
lock1 = lock2 = lock3 = 0;
}
Если есть другая функция, которая выглядит следующим образом:
void bar() {
while(!atomic_check_and_set(lock3)) sleep(100);
while(!atomic_check_and_set(lock2)) sleep(100);
while(!atomic_check_and_set(lock1)) sleep(100);
// do stuff
lock1 = lock2 = lock3 = 0;
}
вы можете столкнуться с ситуацией, когда поток, выполняющий foo, возьмет lock1, а поток, выполняющий bar, возьмет lock3. Затем один из них возьмет lock2, но в этот момент оба потока зависнут на неопределенное время.
Шкалы времени
Проблема, выявленная нашим программным обеспечением для управления магазином, — это проблема временных шкал. Удержание блокировки в течение 200 мс — это нормально в небольших средах. Удержание блокировки в течение восьми часов выведет людей из себя. Это разница между скоростью «пакетной обработки» и скоростью пользовательского интерфейса.
Очевидный урок заключается в том, что вы должны избегать блокировок при ожидании пользовательского ввода. Кроме всего прочего, вы не знаете, находится ли пользователь вообще за компьютером!
Приведенная выше дискуссия о блокировках, по-видимому, сегодня называется «пессимистическим управлением параллелизмом». Альтернативой, которую предлагают, является «оптимистичный контроль параллелизма», при котором вы разрешаете одновременный доступ к памяти, но откатываетесь назад или объединяетесь в случае конфликтов.
Такой подход имеет смысл в ситуациях с очень высоким уровнем использования. В меньших масштабах, особенно в тех, где пользователи являются автомеханиками, я думаю, что это плохая идея — втягивать семантику слияния. Я имею в виду, что сами программисты уже испытывают значительные трудности с Git merge — подчинять автомехаников слиянию звучит бесчеловечно.
Живые обновления
Я решил подойти к этой проблеме не как программист, а как обычный человек. Почти все в вычислительной технике является своего рода метафорой реальной жизни: не зря основа большинства графических операционных систем называется «рабочий стол», а «файлы» хранятся в «папках». Даже более старый термин «каталог» — ну, для молодых людей, вы использовали каталоги для поиска телефонных номеров.
Основная причина этого заключается в том, что вы должны попытаться сделать вычисления интуитивно понятными. Это означает, что нужно иметь представление об интуиции: что люди сочтут интуитивно понятным? Объединение конфликтов в реальном мире невероятно утомительно и состоит из суждений и вопросов «у кого последняя инстанция?».
А как насчет более основного вопроса: каковы реальные ситуации, в которых мы имеем одновременный доступ к общему носителю информации? Я понял, что это происходит постоянно, это настолько распространено, что почти незаметно. А именно — ведение разговора. Люди управляют разговорами не с помощью сложных технических правил, а с помощью — за неимением лучших слов — вежливости и силы воли. Мы с вами говорим одновременно. Я прекращаю говорить, а вы? Если мы оба замолчим, кто начнет говорить? Если мы оба продолжаем говорить, кто моргнет первым?
Для целей параллельного доступа на эти вопросы не нужно отвечать — достаточно того, что люди управляют разговорами, и мы называем это управление «социальной конвенцией». Это заставило меня понять, что менее масштабный одновременный доступ можно обрабатывать с помощью обновлений в реальном времени, как в Google Docs.
То есть, фиксируйте изменения по мере их внесения, и пусть эти изменения немедленно отражаются для других пользователей. Да, пользователи могут создавать условия гонки, но это не техническая проблема — это социальная проблема. Пользователи будут инстинктивно видеть возможность возникновения условий гонки (даже не зная этого термина), потому что они будут видеть, над чем работают другие пользователи. Просоциальные пользователи будут избегать конфликтующих изменений; антисоциальные пользователи могут быть дисциплинированы.
Есть некоторые алгоритмические проблемы, связанные с этим, и я напишу о них позже. Например, вам все еще нужно делать трехстороннее слияние, и вам нужно держать курсор ввода текста в разумном месте. Но это решение возвращает блокировку к временным рамкам пакетной обработки, причем таким образом, который должен быть интуитивно понятен обычным людям.
Это, конечно, работа в процессе, но я думаю, что она достаточно интересна, чтобы о ней стоило написать.