Communicating Sequential Processes

A talk by Leonid Shevtsov. ? for help, p for notes. Talks catalog :: Back to site.

# Communicating Sequential Processes

## Леонид Шевцов

Dnipropetrovsk Lambda Club, 6/2016

&#35;каналы #гоу-блоки #конкурентность #состояние

???

- Постановка проблемы; о какой предметной области мы говорим?
- Подвод к каналам со стороны подпрограмм
- Концептуальное описание
- Сравнение с Unix Pipes
- Сравнение с другими технологиями: callback, Promise, FRP, actors
- Применения каналов
  - Синхронизация
  - Хранение состояния
  - Связь компонент (Domain по DDD)
  - Управление пулом ресурсов
  - Таймауты

---

# История

http://spinroot.com/courses/summer/Papers/hoare_1978.pdf

???

Статья Тони Хоара (того же, что и придумал quicksort и формальную верификацию правильности программ).

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

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

Проект требовал делать расчеты с максимальной утилизацией CPU. Вот и выплыла наружу и параллелизм, и просто конкурентность.

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

---

# Concurrency is not Parallelism

![](/uploads/images/csp_talk/quadritandem.jpg)

???

Почему-то и то, и то переводится на русский словом "параллельные вычисления". Но разница есть.

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

Пример: у вас с женой один велосипед, но вам нужно на работу, а ей на дачу. Несмотря на то, что ехать может только один, но велосипед будет решать и вашу задачу, и её, по очереди. Это конкурентность.

Параллелизм - это возможность в один момент времени выполнять несколько инструкций.

Продолжая пример, если у вас с женой появится два велосипеда, то вы можете ехать в два разных места одновременно.

Параллелизм подразумевает конкурентность. Если у вас шестнадцать велосипедов, но только один пользователь - параллелизма не будет.

Но конкурентность возможна и без параллелизма - например, виртуальная машина Javascript выполняется в один поток (параллелизма нет), но конкурентность есть - за счет событий.

CSP применим к конкурентным системам, и даже особо удобен для организации конкурентности _без_ параллелизма. Все же sequential processes, а не parallel.

---

![](/uploads/images/csp_talk/gopher.jpg)

???

Примеры будут на псевдо-Go, переводятся в другие языки они один-в-один, на Go выглядят наиболее естественно.

Для этого доклада достаточно знать, что Go - это C + CSP.

---

## Компоненты CSP

- Каналы (channels)
- Копрограммы (Гоу-блоки) (go blocks, go routines)
- Оператор выбора (`select` / `alt`)

---

# Каналы

???

Слово "канал" по-моему намекает на наличие длины, в наше время, наверное, понятнее было бы сказать "портал".

---

# Каналы

???

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

---

# Каналы

<br>

```shell
find | grep | sed | wc
```

_...an unforgettable orgy of one-liners as everybody joined in the excitement of plumbing._

???

Каждый, кто работал в Unix, знаком с каналами. Потому что Unix pipe - это почти канал.

Одна программа пишет в канал, другая читает. Ни одна из них не знает и не хочет знать, кто или что на другой стороне. Мощь шелл-скриптов Unix существует благодаря каналам!

---

![](/uploads/images/csp_talk/kenthompson.gif)

???

Кстати, пайпы придумал человек по имени Кен Томпсон. Что еще хорошего сделал Кен Томпсон? Стал соавтором языка Go!

---

# Копрограммы

```go
func worker(payloadChan) {
    for payload := range payloadChan {
        payload.outChan <- doWork(payload)
    }
}

payloadChan := make(chan)
outChan := make(chan)

for i := 1; i < 4; i++ {
    go worker(payloadChan, outChan)
}

func doAsyncWork(params) chan {
    outChan := make(chan)
    payloadChan <- {params, outChan}
    return outChan
}

myResult := <-doAsyncWork(myParams)
```

???

Копрограммы - это такие подпрограммы, которые общаются между собой исключительно через каналы.

В момент чтения/записи в канал копрограмма прекращает свое выполнение, пока на другой стороне канала не появится пара. Таким образом, копрограммы не крутятся бесконечно, а выполняются только "по потребности", при наличии ввода и вывода.

---

# Оператор выбора

```go
func stateKeeper(updateChan, outputChan) {
    state := <- updateChan
    for {
        select {
            state := <- updateChan:
            outputChan <- state:
        }
    }
}
```

???

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

---

# Зачем все это надо?

- Локальный цикл событий
- Фрактальность
- Синхронизация
- Хранение мутабельного состояния
- Связь компонент (Domain по DDD)
- Управление пулом ресурсов
- Таймауты

---

## Сравнение с другими похожими технологиями

- callback
- Promise
- FRP
- Actors

???

CSP - корень.

---

## Пример: таймаут

```go

func query() {
    select {
    result := <-backendChan:
        return result
    time.After(100 * time.Milliseconds):
        return "Too slow!"
    }
}
```

---

## Пример: управление пулом CPU

```go
func AcquireCPU() <-chan bool {
    jobChan := make(chan bool)
    jobQueue <- jobChan
    return jobChan
}
func ReleaseCPU() {
    <-cpuTokenPool
}
var jobQueue = make(chan chan bool, queueLimit)
const queueLimit = 10000
var cpuTokenPool = make(chan bool, workerThreadCount)
var workerThreadCount = runtime.GOMAXPROCS(0) - 1

func init() {
    go func() {
        for job := range jobQueue {
            cpuTokenPool <- true
            jobChan := (<-jobQueue)
            jobChan <- true
            close(jobChan)
        }
    }()
}
```

???

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

---

## Пул CPU: пример использования

<br>

```go
func hardWork(items) {
    for item := range items {
        go func(item) {
            <-AcquireCPU()
            defer ReleaseCPU()
            cpuHeavyCalculations()
        }(item)
    }
}

func unrelatedHardWork(workChan) {
    for work := range workChan {
        go func(work) {
            <-AcquireCPU()
            defer ReleaseCPU()
            doTheWork(work)
        }(work)
    }
}
```

???

Пример использования

---

![](/uploads/images/csp_talk/gopher.jpg)

???

Go это наше все.

Goroutine - очень эффективно. Встроенная поддержка, расширяющийся стек, можно держать очень много (если только они не хотят все сразу работать)

---

![](/uploads/images/csp_talk/clojure.png)

> I remain unenthusiastic about actors. They still couple the producer with the consumer.
> _Rich Hickey_

https://github.com/clojure/core.async

http://hueypetersen.com/posts/2013/08/02/the-state-machines-of-core-async/

???

Clojure также имеет поддержку всего того же.

Любопытна реализация.

---

# JavaScript

### https://github.com/ubolonton/js-csp

ES6 Generators

https://davidwalsh.name/es6-generators

???

На JS все это реализовано через ES6 генераторы, есть в новых браузерах и для Babel.

---

# Спасибо

- https://leonid.shevtsov.me

- github: @leonid-shevtsov

- twitter: @leonid_shevtsov