LINUX.ORG.RU

Банковские счета

 ,


0

1

Читанул на досуге главу SICP о банковских счетах. Я особо не вникал, могу тупить, но мне показалось, что проблема надуманая какая то. Там дальше обсуждается про проблемы доступа к общему ресурсу и прочее. Суть проблемы в том, что, пока один клиент снимает с общего счета, идет проверка второго запроса, и в итоге, банк может выдать больше чем надо, потому что в период между проверкой и снятием другой процесс может снять деньги. Как-то так. Я накидал вот такую простенькую реализацию:



(define account 100)

(define check 
  (lambda(n) (>= account n)))
(define withdraw
  (lambda(n)
    (if (check n) (set! account (- account n)) "NO MONEY")))

(define john-get withdraw)
(define jack-get withdraw)


Собственно, можно представить, что у нас есть некий центральный ресурс, на котором выполняется withdrow. На нем же находится и account. Это машина, которая обслуживает запросы в порядке их поступления. Соответственно, если мы вызвали withdraw она не сможет выполнять другую withdrow в тот же момент, следующий вызов встанет в очередь. А значит, между проверкой и снятием не может вклиниться другой процесс. И есть два банкомата. Допустим, оба клиента вызовом функции get пытаются снять деньги одновременно. Все равно первым придет либо запрос Джона либо Джека. Пока вызванная Джоном операция (ф-ция withdraw) работает, вызов Джека (на ту же операцию) ждет.

Это ситуация банальной очереди. Один кассир не будет обслуживать сразу двух клиентов. А оба клиента не могут встать на одну и ту же позицию в очереди. Кассир тут - и есть общий ресурс.

Так в чем же проблема, я не понимаю? В том что этот элементарный алгоритм мы можем реализовать через задницу, если постараемся, или о чем там они пишут?


А значит, между проверкой и снятием не может вклиниться другой процесс

Да, для однопоточной/однопроцессной обработки синхронизация не нужна. А как глава называется? Не написано ли там что-то о конкурентности и т.п.?;)

Sectoid ★★★★★
()
Ответ на: комментарий от Sectoid

Она называется абстрактно: «Параллелизм: время имеет значение». Сам процесс, который я описал, он же параллелен? Два банкомата могут реально одновременно, параллельно отправлять запрос, запрашивать одну и ту же операцию, но центральный ресурс все естественным путем разруливает, ибо по другому не может, он так работает.

phill
() автор топика

Рискну предположить, что из всех разжигателей в девелопменте ты и авторитетный одно лицо. Манера написания один в один.

unlog1c ★★★
()
Ответ на: комментарий от phill

Ну да. Распараллеливание на сервере это технология только для фантастических романов. В суровой реальности рулит естественный путь.

Weres ★★★
()
Ответ на: комментарий от phill

Параллелизм: время имеет значение

тебе не кажется, что слово «параллелизм» здесь на что-то намекает? Ты вообще с параллельным программированием сталкивался когда-нибудь?

но центральный ресурс все естественным путем разруливает

И как же реализуется этот «естественный путь»?;)

Sectoid ★★★★★
()

там про сферические счета в вакууме, реальные системы так не работают всё равно, сабжевые вопросы реляционной СУБД и транзакциями разруливаются

Harald ★★★★★
()
Ответ на: комментарий от Sectoid

сталкивался когда-нибудь?

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

phill
() автор топика
Ответ на: комментарий от Sectoid

тебе не кажется, что слово «параллелизм» здесь на что-то намекает?

Ну а что это в данном контексте может означать? 3 компа в одной сетке, это что не частный случай параллелизма?

phill
() автор топика

Собственно, можно представить, что у нас есть некий центральный ресурс, на котором выполняется withdrow.

можно

Это машина, которая обслуживает запросы в порядке их поступления.

в реальном мире - не факт.

Соответственно, если мы вызвали withdraw она не сможет выполнять другую withdrow в тот же момент, следующий вызов встанет в очередь.

в нагруженных системах так дела не делаются.

Пока вызванная Джоном операция (ф-ция withdraw) работает, вызов Джека (на ту же операцию) ждет.

а теперь - у тебя не два банкомата, а 100500, и клиенты пытаются проводить операции одновременно. В реальных условиях, т.е. как операция, так и связь занимают сильно ненулевое время. Всем стоять и тупить?

arkhnchul ★★
()

Суть в том, что операции зачисления/снятия бабла должны быть либо последовательны (неэффективно), либо атомарны (сложно сделать), либо синхронизованы должным образом.

Иначе, например:

На счете у юзера 100 баксов.
Поток 1 пытается снять 90 баксов.
Проверяет наличие средств - средства есть.
Поток 2 пытается снять 60 баксов.
Проверяет наличие средств - средства есть.
Поток 1 снимает бабло.
Поток 2 снимает бабло.

В итоге, юзер получает 150 баксов.

kovrik ★★★★★
()
Последнее исправление: kovrik (всего исправлений: 1)
Ответ на: комментарий от arkhnchul

Всем стоять и тупить?

Я где-то слышал, что банкомат может (по каким-то нормам) тупить по 30 секунд на любой операции (даже при переходе на другую менюшку). Вроде на хабре бывший банкоматчик статью писал.

ziemin ★★
()

Конкретно в твоем примере строка

    (if (check n) (set! account (- account n)) "NO MONEY")))

не является атомарной и в ней отсутствует синхронизация.

В Clojure, например, это решается такой штукой как STM (по ссылке как раз пример с банковскими аккаунтами разобран):
http://sw1nn.com/blog/2012/04/11/clojure-stm-what-why-how/

kovrik ★★★★★
()
Последнее исправление: kovrik (всего исправлений: 1)
Ответ на: комментарий от arkhnchul

а теперь - у тебя не два банкомата, а 100500, и клиенты пытаются проводить операции одновременно. В реальных условиях, т.е. как операция, так и связь занимают сильно ненулевое время. Всем стоять и тупить?

А как работает nodejs? Там ведь все запросы принимаются в одном лупе, но выдерживает, при этом, большие нагрузки?

phill
() автор топика

Get и set сами по себе атомарны, но вместе нет. Представь, что твой процесс прерывается планировщиком после (- account n), включается второй процесс, который выполняет всю функцию, списываются средства, при возвращении управления первому процессу set! запишет устаревшие данные, таким образом чувак получит халявную порцию денег. Решается это транзакциями, которые гарантируют атомарность всего блока.

mix_mix ★★★★★
()
Ответ на: комментарий от ziemin

Я где-то слышал, что банкомат может (по каким-то нормам) тупить по 30 секунд на любой операции (даже при переходе на другую менюшку). Вроде на хабре бывший банкоматчик статью писал.

может. Если ввести полностью синхронную обработку со всех банкоматов, то может и сильно больше.

arkhnchul ★★
()
Ответ на: комментарий от kovrik

не является атомарной и в ней отсутствует синхронизация.

А зачем в этом случае синхронизация, ведь больше одной операции за одно и то же время не выполниться, машина то однопоточная? Там и фишка вся в том, что синхронизация не нужна.

phill
() автор топика
Ответ на: комментарий от phill

дык там обработчик завершения запросов не ждет. Принял - запустил - следующий.

arkhnchul ★★
()
Ответ на: комментарий от mix_mix

Не, ну я же рассматривал однопоточную машину, там нет планировщика, который делит процессорное время между потоками.

phill
() автор топика
Ответ на: комментарий от phill

А как работает nodejs?

А она работает? Слабенько вбросил если чо.

nanoolinux ★★★★
()
Ответ на: комментарий от phill

Ну вот как я написал, так и решается:)

Ты написал бессмысленный бред, им ничего не решается.

Sectoid ★★★★★
()
Ответ на: комментарий от phill

Конкурентность, это, все таки не параллелизм

Да ну?;)

И глава в оригинале называется вот так:

3.4 Concurrency: Time Is of the Essence

В общем тролль (или невежда), уходи.

Sectoid ★★★★★
()
Ответ на: комментарий от unlog1c

А ещё anonimus и прочих до кучи. Это всё виртуалы макскомак, мне кажется

esandmann
()

Ещё читани PCL. Они там все банкиры

esandmann
()
Ответ на: комментарий от arkhnchul

Ок, вы говорите о скорости. Но ведь все процессы, в любом случае, будут таботать с одним и тем же account. Значит нужно вводить блокировки, типа мютексов, семафоров и пр. Значит, нам, в данном случае, многопоточность все равно ничего не даст, ведь к account в одно время будет иметь доступ только один процесс.

phill
() автор топика
Ответ на: комментарий от phill

Значит нужно вводить блокировки, типа мютексов, семафоров и пр.

и панеслася.

arkhnchul ★★
()
Ответ на: комментарий от ziemin

банкомат может тупить по 30 секунд

Из этого факта абсолютно нельзя сделать никаких предположений о работе процессинг-центра.

В реальности там всё очень сложно. Транзакции могут висеть очень очень долго.

true_admin ★★★★★
()
Ответ на: комментарий от Weres

Распараллеливание на сервере

Ну там как делается? На каждый запрос создается нитка? Вот допустим, все юзеры, которые ломятся, хотят прочитать или изменить один файл. Если кто-то меняет файл, остальные должны видеть измененный. Как мы такое можем обеспечить? Только блокировкой доступа. Если один меняет, другой уже прочитать не может. Значит, толку в твоем распараллеливании в данном случае нет. Так же и в сабже.

phill
() автор топика
Ответ на: комментарий от phill

ведь к account в одно время будет иметь доступ только один процесс.

Можно, например, заморозить определённую сумму на счёту. Другие транзакции могут работать с оставшейся суммой.

true_admin ★★★★★
()
Ответ на: комментарий от phill

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

true_admin ★★★★★
()

В реальности состояния переключаются не мгновенно. Это тебе кажется, что операции над счетами атомарны, а реально «за кулисами» это может быть совсем не так. Поэтому в момент переключения может произойти что угодно.

stevejobs ★★★★☆
()
Ответ на: комментарий от phill

Неверное предположение, один блок данных могут править сразу несколько процессов. Как это происходит - придумано много стратегий.

stevejobs ★★★★☆
()
Ответ на: комментарий от phill

в ноде синхронные только _начала_ операций ввода-вывода. Сами операции параллельны. В конце выполнения паралелльной операции вызывается коллбэк назад в JS-код, и этот коллбэк уже снова синхронен. Иначе говоря хваленая скорость заключается в распараллеливании внешних по отношению к JS-машине операций, типа операций ввода-вывода (и стоит разработчику попроченных нервов в процессе написания лапши из колбеков)

stevejobs ★★★★☆
()
Последнее исправление: stevejobs (всего исправлений: 1)
Ответ на: комментарий от phill

как работает nodejs?

async io на коллбэках. Юзеровский код выполняется в один поток. Нода заточена под io-bound задачи, а не под cpu-bound.

«большие нагрузки» в данном случае это много соединений.

true_admin ★★★★★
()

>выполняется withdrow ... не сможет выполнять другую

Проблема не в том, что нельзя заблокировать остальных, а в том, что это убивает выигрыш от многопроцессорности.

DonkeyHot ★★★★★
()

Так в чем же проблема, я не понимаю?

Ну вот в этом, собственно, и есть проблема, ты ее решил, молодец.

hint: слово «проблема» не означает «нечто не решаемое». Это то, что надо учесть и разрулить.

anonymous
()
Ответ на: комментарий от phill

Значит, нам, в данном случае, многопоточность все равно ничего не даст, ведь к account в одно время будет иметь доступ только один процесс.

Да.

Еще блокировку можно пометить только для этого аккаунта, тогда другие процессы смогут работать с другими аккаунтами.

Еще бывают разные типы блокировок — например, запрет только на списание, но не запрещено пополнение счета и сальдо узнать.

Еще можно вести счет журнально (т.е. как обычно на бумаге)

anonymous
()

(den73 пароль лень искать)

Чтобы две функции withdraw не были вызваны из разных потоков исполнения одновременно, нужно что-то предпринять. А если они будут вызваны одновременно, то может случиться так:

процессор переключился в первый поток первый поток: вход в withdraw первый поток: check -> 5 рублей

процессор переключился во второй поток второй поток: вход в withdraw второй поток: check -> 5 рублей

процессор переключился в первый поток первый поток: set! - снять 4 рубля (теперь остался 1 рубль)

процессор переключился во второй поток второй поток: set! - снять 3 рубля (осталось -2 рубля)

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.