Решение проблемы параллелизма и принцип работы планировщика языка Go

Go

Статья прошлой недели "Гонки данных и решения в параллельном программировании на Go«В конце я оставил вопрос для решения параллелизмом. За этот период несколько студентов оставили сообщение и рассказали свои идеи по реализации, а двое напрямую прислали мне код личным сообщением. Большое спасибо за активное участие. В сегодняшней статье я сначала расскажу о решении проблемы мышления в предыдущей статье и приведу полный и работоспособный код. После этого краткое введение в явление путем наблюдения за ходом выполнения программы.GoКак планировщик языкаgoroutineСоставьте расписание.

Отвечая на вопрос прошлой недели

Давайте сначала рассмотрим темы вопросов на мышление в статье прошлой недели:

Предположим, что имеется очень длинный срез, тип элемента среза — int, и элементы в срезе расположены не по порядку. С ограничением по времени в 5 секунд используйте несколько горутин, чтобы узнать, существует ли заданное значение в срезе, и прекратите выполнение всех горутин сразу после нахождения целевого значения или тайм-аута.

Например, если срез: [23, 32, 78, 43, 76, 65, 345, 762, ...... 915, 86], искомое целевое значение равно 345. Если целевое значение есть в фрагмент, программа выдает: «Нашла!» и немедленно отменяет задачу поиска, которая все еще выполняетсяgoroutine. Если целевое значение не найдено в течение времени ожидания, программа выводит: «Тайм-аут! Не найдено» и немедленно отменяет задачу поиска, которая все еще выполняется.goroutine.

Впервые упоминается в названииЗавершить выполнение всех горутин сразу после нахождения целевого значения или тайм-аута, выполнение этих двух функций требует помощи таймеров, каналов иcontextПросто сделай это. Первое, о чем я могу подумать, это использоватьcontext.WithCancelСоздайте объект контекста для передачи каждой выполняемой задаче.goroutine, внешний уведомляет всеgoroutineпрекратить работу.

func main() {
	timer := time.NewTimer(time.Second * 5)
	ctx, cancel := context.WithCancel(context.Background())
	resultChan := make(chan bool)
  ......
	select {
	case <-timer.C:
		fmt.Fprintln(os.Stderr, "Timeout! Not Found")
		cancel()
	case <- resultChan:
		fmt.Fprintf(os.Stdout, "Found it!\n")
		cancel()
	}
}

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

func SearchTarget(ctx context.Context, data []int, target int, resultChan chan bool) {
	for _, v := range data {
		select {
		case <- ctx.Done():
			fmt.Fprintf(os.Stdout, "Task cancelded! \n")
			return
		default:
		}
		// 模拟一个耗时查找，这里只是比对值，真实开发中可以是其他操作
		fmt.Fprintf(os.Stdout, "v: %d \n", v)
		time.Sleep(time.Millisecond * 1500)
		if target == v {
			resultChan <- true
			return
		}
	}

}

выполнение поискового заданияgoroutineЧтобы не блокировать задачу поиска, используемselectзаявление плюсdefaultКомбинация:

select {
case <- ctx.Done():
    fmt.Fprintf(os.Stdout, "Task cancelded! \n")
    return
default:
}

существуетgoroutineЕсли целевое значение найдено, он отправитtrueценность дляresultChan, пусть Господь ждет снаружиgoroutineПринимается сигнал о том, что целевое значение найдено.

resultChan <- true

через контекстDoneканал иresultChanряд,goroutineОни могут общаться друг с другом.

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

Полный исходный код выглядит следующим образом:

package main

import (
	"context"
	"fmt"
	"os"
	"time"
)

func main() {
	timer := time.NewTimer(time.Second * 5)
	data := []int{1, 2, 3, 10, 999, 8, 345, 7, 98, 33, 66, 77, 88, 68, 96}
	dataLen := len(data)
	size := 3
	target := 345
	ctx, cancel := context.WithCancel(context.Background())
	resultChan := make(chan bool)
	for i := 0; i < dataLen; i += size {
		end := i + size
		if end >= dataLen {
			end = dataLen - 1
		}
		go SearchTarget(ctx, data[i:end], target, resultChan)
	}
	select {
	case <-timer.C:
		fmt.Fprintln(os.Stderr, "Timeout! Not Found")
		cancel()
	case <- resultChan:
		fmt.Fprintf(os.Stdout, "Found it!\n")
		cancel()
	}

	time.Sleep(time.Second * 2)
}

func SearchTarget(ctx context.Context, data []int, target int, resultChan chan bool) {
	for _, v := range data {
		select {
		case <- ctx.Done():
			fmt.Fprintf(os.Stdout, "Task cancelded! \n")
			return
		default:
		}
		// 模拟一个耗时查找，这里只是比对值，真实开发中可以是其他操作
		fmt.Fprintf(os.Stdout, "v: %d \n", v)
		time.Sleep(time.Millisecond * 1500)
		if target == v {
			resultChan <- true
			return
		}
	}

}

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

Результат выполнения вышеуказанной программы выглядит следующим образом:

v: 1 
v: 88 
v: 33 
v: 10 
v: 345 
Found it!
v: 2 
v: 999 
Task cancelded! 
v: 68 
Task cancelded! 
Task cancelded!

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

Планировщик языков Go

Все приложения выполняются в операционной системе, а реальная работа (вычисления)CPU. Итак, говоря оGoЯзык планировщика, мы не можем обойти понятия операционной системы, процесса и потока. Поток является самой основной единицей планирования операционной системы, и планировщик Linux не различает планирование процессов и потоков.Они также имеют разные реализации в разных операционных системах, но в большинстве реализаций потоки принадлежат процессам.

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

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

Новые проблемы с большим количеством потоков

  • Высокое использование памяти
  • Запланировано высокое потребление ЦП

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

Один用户态线程должен связать内核态线程, но ЦП не знает, что есть用户态线程существование, он знает только, что он работает内核态线程(блок управления процессом печатной платы для Linux). Таким образом, мы еще уточним классификацию.Потоки ядра по-прежнему называются потоками, а пользовательские потоки называются сопрограммами. Поскольку сопрограмма может привязывать поток, также можно привязать несколько сопрограмм к одному или нескольким потокам, реализуя планировщик сопрограмм.

GoлингвистическийgoroutineКонцепция сопрограмм позволяет набору многократно используемых функций выполняться в наборе потоков.Даже если сопрограмма заблокирована, другие сопрограммы потока могут быть заблокированы.runtimeПланирование, переданное другим исполняемым потокам. Самое главное, что программисты не могут видеть эти низкоуровневые детали, что снижает сложность программирования и упрощает параллелизм.

Go, сопрограмма называетсяgoroutine, он очень легкий, т.goroutineЗанимает всего несколько КБ, и этих нескольких КБ достаточноgoroutineПосле запуска это может поддерживать большое количествоgoroutine, который поддерживает больше параллелизма. ХотяgoroutineСтек занимает всего несколько КБ, но на самом деле его можно масштабировать, если требуется больше памяти,runtimeбудет автоматическиgoroutineраспространять.

Теперь, когда мы знаемgoroutineОтношения с системным потоком, то наиболее важным моментом является реализация планировщика сопрограмм.

GoТекущий планировщик был переработан в 2012 году. Из-за проблем с производительностью предыдущего планировщика от него отказались после 4 лет использования. Обновленный планировщик используетG-M-PМодель используется до сих пор.

调度器G-M-P模型

  • G — горутина, задача, которую нужно выполнить;
  • M — представляет поток операционной системы, который планируется и управляется планировщиком операционной системы;
  • P — представляет собой процессор, который можно рассматривать как локальный планировщик, работающий в потоке;

G

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

goroutineсуществует только вGoвремя выполнения языка, этоGoПоток, предоставляемый языком в пользовательском режиме, как более детальная единица планирования ресурсов, при правильном использовании может более эффективно использовать ресурсы компьютера в сценариях с высокой степенью параллелизма.CPU.

M

Goв языковой модели параллелизмаMявляется потоком операционной системы. Планировщик может создать до 10 000 потоков, но большинство из этих потоков не будут выполнять пользовательский код (могут быть перехвачены системными вызовами), и самое большее будетGOMAXPROCSАктивные потоки могут работать нормально.

По умолчанию среда выполнения будетGOMAXPROCSУстановите количество ядер текущей машины, мы также можем использоватьruntime.GOMAXPROCSизменить максимальное количество потоков в программе. На четырехъядерном компьютере создаются четыре активных потока операционной системы, по одному на каждый поток в среде выполнения.runtime.mструктура.

В большинстве случаев мы будем использоватьGoНастройка по умолчанию, то есть количество активных потоков равноCPUВ этом случае планирование потоков и переключение контекста операционной системы не будут запускаться, а все планирование будет происходить в пользовательском режиме, который определяетсяGoСрабатывает языковой планировщик, что может сократить дополнительные накладные расходы.

поток операционной системы вGoЯзык использует частные структурыruntime.mПредставлять

type m struct {
	g0   *g 
	curg *g
	...
}

вg0держит стек планированияgoroutine,curgпользователь работает в текущем потокеgoroutine,ПользовательgoroutineПосле выполнения поток переключается обратно наg0начальство,g0будет из темыMграницаPВстаньте в очередь ожидания наgoroutineк нитке.

P

Процессор в планировщикеPэто нить иgoroutineСредний уровень, он может предоставлять контекст, требуемый потоком, а также отвечает за планирование очереди ожидания в потоке через процессор.Pпланирования, каждый поток ядра может выполнять несколькоgoroutine, Это внутриgoroutineНемногоI/OСвоевременное переключение во время работы для улучшения использования потоков. Потому что планировщик создается при запускеGOMAXPROCSпроцессоры, поэтомуGoКоличество процессоров для языковой программы должно быть равноGOMAXPROCS, эти процессоры привязаны к разным потокам ядра и работают с использованием вычислительных ресурсов потока.goroutine.

Кроме того, в планировщике в планировщике есть глобальная очередь ожидания. Когда все очереди на локальных очередей, вновь созданныеgoroutineвойдет в глобальную очередь ожидания.PПосле того, как локальная очередь опустеет,MОн также возьмет партию ожидающих выполнения из глобальной очереди.goroutineпомещатьPв локальной очереди ожидания.

Схема модели GMP

GMP模型图示

  • Глобальная очередь: сохранить G в ожидании запуска.

  • Локальная очередь P: аналогична глобальной очереди, ожидание запуска хранится в G, количество сохраненных ограничено, не более 256. При создании нового G, G был добавлен к приоритету P локальной очереди, если очередь заполнена, будет перемещена половина локальной очереди в глобальную очередь G.

  • Список P: все P создаются при запуске программы и сохраняются в массиве с максимальным значением GOMAXPROCS (настраивается).

  • M: если поток хочет выполнить задачу, он должен получить P и получить G из локальной очереди P. Когда очередь P пуста, M также попытается взять партию G из глобальной очереди и поместить ее в очередь P. из локальной очереди или из локальных очередей других P. Украдите половину и поместите в локальную очередь своего P. M запускает G, и после выполнения G M получает следующий G от P и повторяет.

  • goroutineПланировщик и планировщик ОС объединены M, каждый M представляет поток ядра, а планировщик ОС отвечает за выделение потока ядра ЦП для выполнения.

Политика планировщика

Одной из стратегий планировщика является максимальное повторное использование существующих активных потоков и улучшение повторного использования потоков с помощью следующих двух механизмов:

  1. Механизм кражи работы, когда поток не имеет запущенного G, пытается украсть G из P, связанного с другими потоками, вместо того, чтобы уничтожить поток.
  2. Механизм HAND OFF, когда этот поток блокируется блокировкой системного вызова, поток освобождает связанный P, переводит P на выполнение другого незанятого потока.

GoСреда выполнения не имеет возможности аппаратного прерывания на уровне ядра операционной системы. Реализация планировщика, основанная на краже работы, по сути, является совместным планированием в порядке очереди. Чтобы решить проблему, связанную с тем, что время отклика может быть высокая, текущая среда выполнения реализует две разные стратегии планирования, совместное планирование и упреждающее планирование, гарантирующие, что в большинстве случаев разные G могут получить одинаковыеCPUвременной отрезок.

Совместное планирование основано на том, что направляемая сторона активно воздерживается, а система отслеживаетgoroutineЗапуск более 10 мс пройдетruntime.GoschedВызов берет на себя инициативу, чтобы предоставить возможность исполнения. Упреждающее планирование основано на том, что планировщик вынужден пассивно прерывать планировщик.

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

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

Чан Кунь /go wave/this-from…

Возвращаясь к решению проблемы параллелизма, упомянутой в первой части статьи, читатель @CDS дал более общий вариант реализации, поставивgoroutineЭта часть логики взаимного общения абстрагируется.После столкновений с похожими на мыслительные вопросы задачами остается только реализовать конкретные задачи.workerВот и все. Из-за сложности кода и длины занимаемого места он не подходит для объяснения идей решения проблем темы в статье.После получения его согласия я поместил ссылку на репозиторий GitHub его плана реализации в Оригинальное прочтение статьи официального аккаунта. Здесь вы можете клонировать его, если вам интересно.

Категории