Let's design the Go scheduler from scratch. We'll start with the simplest and most understandable naive implementation, and then, step by step, we'll figure out its flaws and come up with ways to solve them, gradually making the overall model more complex.

This is one of the best ways to understand a complex system or concept—by going through the process of its step-by-step design. The system is complex and not easy to grasp, but we will break it down into simple steps that are very easy to understand. After that, the puzzle will fall into place in your mind, and the overall picture of the system will be just as simple and obvious to you.

Introduction and Why Study the Scheduler?

Concurrency is a very useful but very complex thing. Usually, when working with it, developers have to solve many problems, but the Go language has minimized these issues. Here, working with concurrent code is implemented very simply, clearly, and effectively.

Key entities that help with this:

Goroutines, which can run concurrently and independently of each other
The Scheduler, which manages them
Channels, which help exchange data between goroutines

I also have a detailed video about the internal workings of channels—I recommend watching it to see all this machinery from a different angle. In this article, we will discuss the scheduler and goroutines.

This article is not for beginners—I assume the reader is already familiar with Go. At a minimum:

You have completed the Tour of Go
You understand how to work with goroutines, at least at a basic level

This article also has a video version. I've tried my best to present my thoughts as effectively as possible in both formats, so just choose the one that suits you best. However, text and video have their pros and cons—some things are much easier to show visually in a video, while some concepts are better absorbed as text. Therefore, if you want to learn the material as effectively as possible, I would advise you to watch the video first and then read the article to reinforce your understanding.
By the way, the second half of the video is an additional practical part where I dissect the scheduler using my utility goschedviz. This is not in the current article, as it's quite difficult to present in text format. But if there's enough interest, I'm willing to write it up as a separate article.

Problem Statement

So, let's imagine we are engineers on the Go Team, and we have an ambitious task before us: to teach our programs to run concurrently and, if possible, in parallel. Yes, the terms "concurrent" and "parallel" are often confused, but later we will discuss their essence and the difference between them.

The main requirements for our concurrently running programs are:

All available processor cores must be utilized (if necessary)
Low cost in terms of performance and memory usage—we want to run thousands, hundreds of thousands of tasks concurrently!
The solution must be understandable and easy to use—the code should be intuitive

I also want to note that despite the length of the article, I have to make simplifications in many cases to make the material easier to digest and to prevent the article from turning into a book. In some places, I will draw your attention to this, and in others, I will not.

A Brief Primer on the Basics

To start designing the scheduler, we need to understand some basic concepts: the computer's processor and its cores, the operating system scheduler and system threads, and what concurrency and parallelism are. If you are familiar with all of this, feel free to skip to the next section.

If it seems that after reading this section you haven't remembered much and haven't fully grasped everything, that's normal. As we proceed, I will regularly return to individual concepts from here, and gradually everything will fall into place in your mind, understanding will come, and then it will all be remembered on its own.

How a Computer Works in Parallel

As you probably understand, our computer can perform several actions simultaneously (in parallel) only if its processor has multiple cores.

На рисунке у нас два ядра, а значит одновременно могут выполняться только две задачи, остальные ждут — In the picture, we have two cores, which means only two tasks can be executed simultaneously; the rest are waiting.

But there's good news—the processor is a very fast thing, so even with a single core, it can perform a huge number of actions almost simultaneously by quickly switching between them. For example, even on a computer with a single-core processor, you can "simultaneously" watch my videos on YouTube, write code, run it, and perform a number of other tasks. At any given moment, the processor will be executing only one task, but it will switch between them so quickly that it will seem to you as if it's doing everything at once.

Одноядерный процессор в один момент времени выполняет лишь одну задачу, но нам кажется, что много. — A single-core processor executes only one task at a time, but it seems to us like it's doing many.

Thoughts on the Parallelism of Events

In a way, parallelism is a function of time, or rather, of a time interval. For example, you might see two events that seem simultaneous to you. But in reality, they occurred with a difference of 0.02 ms. For our brain, these are simultaneous events, but for a slow-motion camera, for example, they are not. If the events occurred with a 2-second difference, even we would notice that they are not simultaneous.

Thus, everything depends on the size of the observation "window." For example, if the execution speed of an operation is 10ms, and our window is 100ms, we can say that 10 operations will be completed simultaneously within this time, regardless of the order. However, if we take a period of 10ms, the operations will be executed sequentially.

Камера увидела эти действия как последовательные, а наши глаза как одновременные — The camera saw these actions as sequential, while our eyes saw them as simultaneous.

Concurrency and Parallelism

Meanwhile, we have come to understand the difference between parallel and concurrent execution.

Concurrency is about the design of our program. Specifically, it's when we have several processes that can be executed independently of each other, in any order.

Parallelism is about the execution of the program, specifically—the execution of multiple tasks at the same moment in time.

Moreover, independent (concurrent) processes can be executed both simultaneously (in parallel) and sequentially. For example, a processor can constantly switch between them, but at any given moment, only one process is being executed. However, it can switch at any time, and this should not affect the correctness of the processes' execution.

In other words, concurrency is when we are working with many things at once, while parallelism is when we are doing many things at once.

In fact, this topic is complex and deep, and a discussion of it could turn into a separate post—by the way, I already have one! In it, I explained these concepts in more detail and also included links to interesting materials for further study.

In any case, even if you haven't fully grasped the essence of these concepts yet, that's normal—as you read the article, everything will gradually fall into place in your mind and become clearer.

Parallelism and Concurrency at the OS Level

So who handles task switching and decides which tasks will run on the core and which will wait? This is done by the operating system scheduler, and it manages threads.

A thread is a sequence of commands executed within a single process. In simple terms, it is the work that is being performed on the processor or waiting for its turn.

Each thread can be in one of three states:

Executing: currently executing on one of the cores
Runnable: ready to execute, waiting for its turn
Waiting: not ready to execute because it is waiting for some event. For example, this could be related to an I/O operation, interaction with the OS (syscall), etc.

Системные треды и их состояния — System Threads and Their States

Context Switching

The OS scheduler can switch threads at arbitrary times—detaching executing threads from the processor core and replacing them with Runnable threads. This is called context switching. We cannot influence the scheduler's decisions, nor can we make any predictions about them—it makes all decisions on its own. This approach is called preemptive multitasking.

For comparison, the Go scheduler uses cooperative multitasking—this means that goroutines (the equivalent of threads) decide for themselves when to yield resources to their waiting comrades. However, there is one caveat that was introduced in Go v1.14. We will return to this later.

The most important thing to understand here is that threads are expensive. Let's figure out why.

First, context switching takes a considerable amount of time: data in the processor caches needs to be updated, the thread's state needs to be saved, etc. The more threads we have in the Runnable state, the more frequent the context switches will be, and the slower the program will run. For example, if there are too many switches, they can collectively take as much time as the task execution itself (or even more):

Два примера переключения контекста между задачами. Хорошо: переключение произошло всего один раз; Плохо: переключение происходило очень часто, из-за чего суммарно мы потратили на него времени примерно столько же, сколько на выполнение задач. — Two examples of context switching between tasks. **Good**: the switch happened only once; **Bad**: switching occurred very frequently, resulting in us spending about as much time on it as on executing the tasks.

Second, each thread consumes a significant portion of our computer's memory: the stack of each thread can often take up to a couple of megabytes (it stores local variables, function call chains, etc.).

Now, knowing that threads are indeed expensive, we understand that we want to create as few of them as possible. The fewer threads, the less frequent the context switches, and the less memory we use. This is an important point that we will refer to very often in the future.

This is sufficient for understanding the rest of the material, but if you want to go deeper, I have a more detailed post on the topic of threads and processes.

Designing Our Own Scheduler for Go

So, we've finally reached the most interesting part. As a reminder, our main task is to teach our Go programs concurrency and parallelism. Let's say we have this code:

func main() {
  task1() // запускаем первую функцию и ждём её завершения
  task2() // после этого запускаем следующую
  
  // ...
}

The functions task1 and task2 will execute synchronously, that is, sequentially—task2 will only start after task1. has finished. But what we want is for task2 to start without waiting for task1 to finish, i.e., asynchronously—the very definition of concurrent execution. In terms of syntax, it's very simple—just add `go` before the function call:

func main() {
  go task1() // запускаем функцию и идём дальше, не дожидаясь её завершения
  go task2() // запускаем следующую и также идём дальше
  
  // do some other work..
}

Thus, our competing processes will be functions launched with the `go` prefix. And since we now have competition for resources—for processor time—we need some entity to manage this. Let's call this entity the Scheduler. And so we meet this guy!

What will it manage? We recall that the OS scheduler managed threads, so let's steal that concept! We'll call our equivalent of threads—goroutines. In a sense, they will be the same execution threads, but within our program.

In other materials, you may have also seen the terms kernel space and user space. Well—goroutine scheduling happens at the user space level, meaning it's managed by the Go scheduler (or more precisely, the Go Runtime), while thread scheduling happens at the kernel space level, meaning it's managed by the OS.

Since all our programs run within the OS, we will still need threads—goroutines will be executed on them. That is, when we need to execute a goroutine, we bind a thread to it, and it will run on that thread.

But why do we need to introduce goroutines at all if we have threads? Because, as we discussed above, threads are not always satisfactory in terms of efficiency. We can build goroutines to be much more lightweight in terms of memory and, most importantly, to have much cheaper context switching than threads. This is possible because they all live within a single process (our program) and share memory access, and switching between them occurs without the involvement of the OS kernel. In reality, there are many clever optimizations and nuances that we will discuss, but in short—understanding all the limitations of threads, we will design goroutines to use these threads as efficiently as possible.

In general, you could say that the Go scheduler is just a way to optimize the use of system threads—optimizing in terms of resource usage and the simplicity of the code for working with them. And the deeper you dive into this article, the more you will come to understand this.

So, let's summarize all this:

The main resource for program execution is the processor cores.
There are few cores, but they have a lot of work, so the concept of threads is introduced: threads run on cores.
The OS scheduler manages threads and optimizes their work to ensure that cores do not sit idle.
OS threads are big and scary—not because they are poorly designed, but because there are limitations and specific features at the OS level, so we have few threads available.
There are few threads, but a lot of work within our program, so the concept of goroutines is introduced: goroutines run on threads.
The Go scheduler manages goroutines and optimizes their work to use threads as efficiently as possible—creating as few as possible and not letting them sit idle.

Moving on, our goroutines will obviously need states. Let's borrow them from threads as well:

Waiting — the goroutine is not ready to run because it is waiting for something
Runnable — ready to run as soon as a thread becomes available
Executing — running on some thread

Thus, we get the following diagram:

Горутины и их состояния — Goroutines and Their States

Doesn't this look familiar? It's an exact copy of the OS scheduler diagram I showed earlier, only the names of the entities are different. Indeed, at a very basic level, an analogy can be drawn here.

Next, we need to introduce two more entities:

Machine for execution (M, Machine)—will directly execute the goroutine.
Processor (P, Processor)—will place goroutines (G) into the Machine.

Don't confuse this Processor with a computer's processor or CPU cores—their names are similar, but their essence is completely different (this is not my whim, it's an official term).

Now the picture is as follows:

Процессор берёт горутину и кладёт её в Машину для выполнения — The Processor takes a goroutine and places it in the Machine for execution.

Essentially, a Machine is just a system thread. That is, when a Processor places a goroutine into a Machine, it is simply binding that goroutine to a thread. Since that's the case, I will henceforth refer to them as threads, not machines, as it's more convenient for me. I introduced the term "Machine" here only to help you better understand the connection between my article and other materials.

By the way, these are the very G, M, and P that you may have encountered in other articles and materials. Together, they form the so-called GMP model. This is what we will ultimately arrive at.

So, we have our set of basic entities. How will we use them to achieve concurrent and parallel execution? Let's figure it out. We will proceed iteratively—first, we'll come up with the simplest naive solution, and then we'll gradually complicate it, solving problems as they arise.

1. Create a thread for each call—The 1:1 Model

Модель 1:1 — для каждой новой горутины создаётся новый тред — 1:1 Model—a new thread is created for each new goroutine

The simplest thing to come up with is to create a separate thread for each goroutine and destroy these threads when they are no longer needed. That is, we pass all new goroutines to the Processor, which requests a new thread for each of them, and when a goroutine finishes its work, its thread is disposed of.

This is called the 1:1 Model, meaning as many threads as there are goroutines. The solution is quite workable—we will have both concurrency and parallelism, and we will definitely utilize all processor cores when necessary (because the OS scheduler will not allow threads to idle if there are free cores).

By the way, there is also a 1:N Model—this is when all goroutines (or their equivalents) always use only one OS thread. From the reasoning above, we understand that this is not suitable for us, as in this case, we lose the ability to run anything in parallel. But it's useful to know that this also exists.

Модель 1:N — у всегда есть только один тред, вне зависимости от количества горутин — 1:N Model—there is always only one thread, regardless of the number of goroutines

Essentially, the 1:1 model delegates all the work to the OS scheduler. But are we satisfied with this? Unfortunately, no. From the introductory primer, we remember that creating and destroying threads is too expensive, and we want to minimize this. Let's think about how.

2. Thread Pool

Okay, if creating and destroying threads is expensive, let's not destroy them, and instead of creating new ones, let's reuse existing ones whenever possible.

That is, as before, we will create new threads for goroutines, but now only when necessary. And when a thread becomes free (for example, a goroutine has finished its work), the Processor, instead of destroying it, will place it in a pool to keep it for other goroutines. A waiting thread will not perform work, and therefore will not occupy a processor core.

Три горутины в разных состояниях: Running - выполняется на треде, Runnable - берёт тред из пула, Done - возвращает использованный тред в пул — Three goroutines in different states: **Running** - executing on a thread, **Runnable** - takes a thread from the pool, **Done** - returns the used thread to the pool

Excellent, we have optimized our scheduler by getting rid of many expensive and unnecessary thread creation and destruction operations! Is everything good now?

No, it's still bad. Remember—not only is creating threads expensive, but their very existence is too, and we want to create hundreds... no, millions of goroutines! Alas, we cannot afford millions of threads. What should we do?

3. Limiting the Thread Pool Size—The M:N Model

If we don't want to create too many threads, it's obvious that we just need to limit their maximum number, so let's do that. The implementation scheme for this approach is still quite simple—when a new goroutine is launched, we do the following:

1. Check if there is a free thread in the pool. If there is, we take it to execute the goroutine.

В пуле есть свободные треды, берём оттуда — There are free threads in the pool, we take one from there.

2. If not, check how many threads are currently in use. If it's less than the limit we set, we create a new thread and give it the goroutine. When the goroutine finishes its work, we'll send this thread to the pool.

В пуле нет свободных тредов. Видим, что ранее мы создали всего 1 тред из 8 возможных, поэтому создаём новый. — There are no free threads in the pool. We see that we have previously created only 1 out of 8 possible threads, so we create a new one.

3. If the number of threads has reached the limit, the goroutine will wait until one of the previously created threads becomes free and returns to the pool. Once it's free, we'll assign the goroutine to it.

В пуле нет свободных тредов, и их лимит исчерпан — на них сейчас выполняются другие горутины. Текущей горутине придётся ждать. — There are no free threads in the pool, and their limit has been reached—other goroutines are currently running on them. The current goroutine will have to wait.

Thus, we have introduced the concept of waiting goroutines. But where will they wait? Let's just line them up in a queue and call this queue the Global Run Queue (GRQ). This way, every new goroutine that doesn't get a thread will be sent to the GRQ to wait its turn.

Горутине не достался тред, она отправляется ждать в Global Run Queue — The goroutine didn't get a thread, so it goes to wait in the Global Run Queue.

Since there are different types of queues, it's worth clarifying—we will use a FIFO queue (first in, first out), where the goroutines that arrived first are taken first. This is logical and fair—the earlier a goroutine arrives, the sooner it gets a thread.

LIFO queue (last in, first out) would be less fair and sometimes problematic. For example, we could have a situation where a goroutine that arrived first never gets executed because new goroutines are constantly arriving and being executed instead. LIFO queues have their advantages, but we won't dwell on that now.

Pool Size

Now let's think about what limit we want to set on the number of threads—that is, what the size of our pool will be. If we use too few threads, not all processor cores will be utilized—for example, if there are 8 cores and only 4 threads, 4 cores will be idle. But we don't want to create too many threads either, as it's expensive and inefficient. So what would be the optimal value?

The answer is on the surface—we will create exactly as many threads as we have available cores, and then no core will be idle. Creating more threads makes no sense, as some of them would definitely be idle waiting for a free core. That is, if we have 8 cores and 10 threads, even in the best-case scenario, 2 threads will be idle.

На схеме у нас два ядра CPU и, соответственно, два рабочих треда. Одновременно выполняться могут лишь две горутины, остальные ждут своей очереди. — In the diagram, we have two CPU cores and, accordingly, two worker threads. Only two goroutines can be executed simultaneously; the rest are waiting for their turn.

Important point: now that the number of threads is strictly limited, we can afford to assign a separate Processor (P) to each of them. That is, each Processor will now have its own thread. This doesn't affect the overall picture for now, but later, working with each thread will become more complex, and this approach will be very helpful.

Thus, we have arrived at a real model called M:N Threading. It consists of executing N goroutines on M threads.

By the way, we are already getting close to understanding the function runtime.GOMAXPROCS() — It sets the maximum number of Processors that our program will use. That is, by default, there will be exactly as many as there are available cores—runtime.NumCPU(), but if we want fewer, we can set their exact number as follows:

// Максимальное количество процессоров = 2,
// вне зависимости от количества ядер CPU
runtime.GOMAXPROCS(2)

This function also returns the current setting, and if you just want to see this value without changing it, you can call it with an argument of 0:

// Максимальное количество процессоров не изменится,
// а функция просто вернёт это значение
n := runtime.GOMAXPROCS(0)

Mutex for the Global Run Queue

Meanwhile, we have encountered another serious problem. If multiple parallel processes have access to a shared resource, we need a mechanism for synchronizing access. Otherwise, it could happen that two Processors try to take the same goroutine for execution and break something—for example, both might start executing that goroutine.

The behavior where multiple concurrent processes access a shared resource is called a race condition. In general, it is unpredictable and dangerous. It must be avoided at all costs.

To avoid this, we use the simplest synchronization primitive—a mutex (mutex, lock). If you are not familiar with it, I highly recommend getting acquainted—it is a very simple but important mechanism that is encountered very often. In simple terms, with its help, each Processor can temporarily lock the queue to work with it—in our case, to get a goroutine from it. While it is locked, no one else can interact with it. Thus, while one Processor is getting a goroutine from the GRQ, the other Processors will have to wait.

Процессор слева не может взять горутину из GRQ, потому что Процессор справа её заблокировал на время своей работы. — The Processor on the left cannot take a goroutine from the GRQ because the Processor on the right has locked it for the duration of its work.

By the way, we are already getting closer to the real Go scheduler, which also has:

A Global Run Queue with a mutex
The number of worker threads matches the number of CPU cores
Each processor has its own thread

You might ask: "Nikolai, is there something you don't like about this scheme either? Everything works perfectly! Right?" No! Or rather, not quite. If our computer has only 2 cores, then everything is great, the scheme will work well. But what if there are more cores? For example, 16, 32... 64? As the number of cores increases, so does the number of threads, but the queue remains a single one for everyone.

That is, even if we have a lot of Processors, at any given moment, only one of them can work with the queue. Introducing a mutex solved one of our problems but created another—working with the shared resource (GRQ) has slowed down significantly.

By the way, here you can realize a very important point in any system—in the design of any system, there are no free optimizations; it's almost always about tradeoffs: you optimize CPU work at the expense of memory; you optimize memory but increase the load on the CPU, etc.
And, as usual, I also have a more detailed post about this.

How will we solve this problem?

4. Local Queues

To solve the problem of locks... we need to get rid of locks! And to do that, we need to make it so that processors don't access the shared queue. To achieve this, we will give each Processor its own queue—a Local Run Queue (LRQ). Since each LRQ will be accessed by only one processor, no lock will be needed.

However, we are not getting rid of the GRQ with its mutex; we will still need it. We will place goroutines there that are not yet bound to any Processor, and from there, goroutines will eventually always end up in an LRQ and only then be executed. We will return to this later.

Now our entire scheme looks like this:

На этом изображении у нас ядра CPU и каждому из них соответствуют свой тред, свой Процессор и своя LRQ. Также тут изображена GRQ, которая не привязана ни к одному из Процессоров. — In this image, we have CPU cores, and each of them corresponds to its own thread, its own Processor, and its own LRQ. The GRQ is also depicted here, which is not tied to any of the Processors.

In the resulting scheme, we see goroutines in the Runnable state (in the queue) and Running state (being executed by a Processor). Have we forgotten anything? What about Waiting goroutines? As a reminder, these are the goroutines that are blocked by something and cannot be run. So where should we put them? Maybe we need a separate queue for them in the Processor—a Wait Queue?

Actually, the Processor won't have to keep track of Waiting goroutines; other entities will handle that. For example, if a goroutine is blocked due to reading from or writing to a channel, it will go into that channel's Wait Queue, and from there it will eventually end up in the GRQ and then an LRQ. I have a very detailed video about channels, where, among other things, I discuss this mechanism. Similar mechanisms also exist for mutexes, timers, and Network I/O.

Order of Checking Queues

Now we have two types of queues—LRQ and GRQ. Consequently, each Processor can get work from two places, which means we need to decide the order in which it will do so.

Obviously, the Processor will first look into the LRQ, as it is the fastest—that's precisely why we introduced it. But if it's empty, the Processor will then look into the GRQ.

However, another problem can arise here—if the LRQs of all processors are constantly being replenished, the Processors will always take work from there and never get to the GRQ. This is bad because the goroutines in the global queue will start to stagnate, so we should occasionally check it out of turn. But how often? Obviously, once every 61 times! That is, the algorithm for a Processor to get a goroutine is as follows:

1/61 of the time, check the GRQ, and if there are goroutines there, take one from there
If not, check the LRQ
If that's also empty, check the GRQ
... There will be more points here, but we'll talk about them later

You might ask—but why 1/61, what's this magic number? The most important thing here is that it's a prime number, which helps avoid synchronization of checks between different Ps, distributing them more evenly. Moreover, it's not too large and not too small—meaning the GRQ will be checked neither too often nor too rarely.

5. Work Stealing

So, our scheduler is getting more complex, but it's working better and becoming more like a real one. However, it's still far from ideal. What problem are we concerned with this time? You probably remember that from the very beginning, we were very concerned about the problem of idle cores. It seemed we had long since solved this problem, but no. Take a look at this diagram:

Горутины грустят, потому что им приходится ждать, хотя у нас есть свободный Процессор. А мы грустим, потому что у нас простаивает без работы целое ядро процессора. — The goroutines are sad because they have to wait, even though we have a free Processor. And we are sad because we have an entire processor core sitting idle.

So, one Processor has a lot of work, while another has none at all. What should we do? Let's teach the Processors to steal work from each other! Specifically, if a Processor's LRQ is empty, it will look into the LRQ of any other Processor and take a goroutine from there. Or even better—let it take half of the goroutines from there at once, so it doesn't have to come back again.

Процессор #2 был без работы, поэтому он украл половину горутин у соседа. Теперь ему есть чем заняться! — Processor #2 was idle, so it stole half of the goroutines from its neighbor. Now it has something to do!

This way, we will automatically balance the work among all our Processors. And the complete algorithm will now look like this:

1/61 of the time, check the GRQ, and if there are goroutines there, take one from there
If not, check the LRQ
If it's empty, try to steal from another Processor
If that fails, check the GRQ
... Here we will check the Network Poller, but more on that later

6. Handoff

How great our Scheduler has become! But let's find a problem here too. What if a goroutine performs a blocking operation, like a system call (syscall)? Then this goroutine will block an entire thread for us, and the processor core will be idle again, even though we have Runnable goroutines in the queue.

Горутина выполнила syscall и заблокировала тред - ядро CPU простаивает без работы — A goroutine made a syscall and blocked the thread - the CPU core is idle.

I want to emphasize again—not only the goroutine with its Processor is blocked, but the thread itself is also blocked by the system call. This means we can't just send this waiting goroutine to wait somewhere else and give the thread some other work. Therefore, we will have to send them somewhere together—both the thread and the goroutine.

Here it's important to understand what a system call (also known as syscall) is. If you don't know, this is another must-have topic for your knowledge base; be sure to delve deeper into it.
For now, let's put it this way—imagine you called a colleague and asked them a question. The question was difficult, the colleague fell into deep thought, and you are forced to wait. While they are thinking, you can't do other useful things; you are blocked by waiting. You will be free as soon as the colleague comes up with an answer and tells you.
So, the call to your colleague is the syscall, and you are the thread executing it.

So, if a thread is blocked by a system call, it can no longer perform work. In this state, it's not very useful to us, so we will simply detach it from the Processor, create a new thread, and attach that to the Processor. This mechanism is called a handoff.

Пока тред #1 ждёт ответа от системного вызова, его Процессор будет привязан к другому свободному треду — While thread #1 is waiting for a response from the system call, its Processor will be attached to another free thread.

Returning to the analogy of asking a colleague a question—while you are talking to them, your boss asks you to free up your work computer so another colleague can work on it (yes, your company is going through tough times and doesn't have enough computers for everyone...)

Well, the mechanism is not bad, but it's quite expensive, as it constantly creates new threads, which we tried very hard to avoid. Unfortunately, this is unavoidable here—a large number of syscalls will always generate a large number of threads. However, we can optimize the process a bit.

Sysmon

Some system calls are short-lived, meaning they block threads for a very short period. Creating a separate thread for them each time is inefficient, so we'll make a clever optimization:

If we know that a system call will block a thread for a long time, we will perform a handoff immediately.
In other cases, we will allow the thread to remain in a blocked state for some time, periodically checking if it has become free. If it exceeds a certain timeout (specifically, 10ms), we also initiate a handoff.

The process that performs these checks will run continuously in the background and is called Sysmon.

Sysmon следит за временем, и если sycall затянулся, он инициирует handoff — Sysmon monitors the time, and if a syscall takes too long, it initiates a handoff.

By the way, on which thread will Sysmon itself run? Obviously, we can't entrust this to the threads that execute goroutines, as they can go to sleep at any moment (which is exactly what we are trying to track). And they have enough of their own work to do anyway. So, we need to have a separate thread for monitoring that will do its job independently of the worker threads.

Wait a minute... We previously agreed to limit the number of threads—there shouldn't be more than the number of cores. Yes, that's still in effect, but it's worth clarifying that this agreement only applies to active threads processing goroutines. It doesn't apply to special threads performing specific tasks, nor to threads in the Waiting state. So, we're good here, no contradictions.

A hidden joke with a Star Wars reference

Я постараюсь больше ничего не менять... — I will try not to alter the deal any further...

So, we've detached the goroutine along with its thread and left them somewhere to wait for the return from the system call. What do we do when they're done waiting? First, for optimization reasons, we want to return the goroutine to the processor it was taken from. But only if that processor is currently free, i.e., not busy executing another goroutine. If it's busy, we'll look for other free processors. If there are no free ones, we'll send the goroutine to the GRQ.

By the way, you could say that we have now moved from the M:N Threading model to the M:P:N Threading model. That is, we still have N goroutines and M threads, but we also have P processors. Of course, we introduced the processor entity a long time ago, but previously, the total number of threads and processors used was the same, and now it's not.

Handoff is a cool mechanism, but it inevitably leads to the creation of new threads. Can we optimize the scheduler's work further to use it less often? Yes, we can—if the syscall can be executed asynchronously.

7. Network Poller

Blocking a thread during a system call is a limitation at the operating system level, meaning we can't fight it programmatically. But, fortunately, the OS itself usually provides mechanisms to bypass this limitation. Specifically, these are mechanisms for performing asynchronous system calls, for example: epoll (Linux), kqueue (macOS, BSD), IOCP (Windows). Most often, this applies to network operations. We won't go into these mechanisms in great detail here, but if you feel the urge, you now know where to dig.

Let's understand the essence. Previously, our threads acted like this:

A system call is made
The thread is blocked while waiting for a response
After receiving the response, the thread is unblocked
Work continues

The mechanisms listed above allow us to do this:

The thread initiates a system call and goes about its other business. The system call will be registered in a special system, and we can return to it later.
Periodically check if a response to the system call has arrived

Thus, working with the system call happens asynchronously.

Мы регистрируем syscall в epoll, благодаря чему наш тред остался свободен и может выполнять другие горутины — We register the syscall with epoll, which leaves our thread free to execute other goroutines.

To make it even clearer, let's return to the example of calling a colleague from the Handoff section.
Imagine that instead of a phone call, you decide to send your colleague a message in a messenger app. Now you don't have to waste time waiting; you just minimize the messenger and continue with your other tasks. You only need to periodically open the chat window with your colleague to check for a response. This is the essence of the mechanisms described above. That is, you are the thread, your dialogue with the colleague is the goroutine, and the messenger is this very mechanism (epoll, etc.).

Unfortunately, not all syscalls can be executed asynchronously—imagine that your colleague can't just give an answer to a question; you need to actively discuss the topic. In that case, you can't just wait; you will be blocked anyway.

So, we've got a cool tool, and now let's teach our scheduler how to use it. First, we'll need a component that will keep track of the system calls that need to be checked for responses—let's call it the Network Poller (netpoller).

If a goroutine is about to make a system call that can be executed asynchronously, instead of blocking the thread, we:

Register the operation in the Network Poller
Put the goroutine into the Waiting state and hand it over to the Netpoller
The Processor is freed up to execute other goroutines

Горутина выполнила асинхронный syscall, и мы передали её Network Poller'у — The goroutine performed an asynchronous syscall, and we handed it over to the Network Poller.

I want to emphasize the main feature of this mechanism again—waiting goroutines do not occupy a thread and can remain in this state for as long as needed without slowing down the program's execution.

When the syscall finishes, the goroutine transitions back to the runnable state, meaning it's ready to continue its work. When Processors run out of work, they will themselves turn to the Netpoller to pick up the freed goroutines. So, the work-finding algorithm for each Processor looks like this:

1/61 of the time, check the GRQ, and if there are goroutines there, take one from there
If not, check the LRQ
If it's empty, try to steal from another Processor
If that fails, check the GRQ
Check the Network Poller

У Процессора закончилась работа и он пошел к netpoller'у, чтобы посмотреть, нет ли там освободившихся горутин, которые можно снова брать в работу. — The Processor ran out of work and went to the netpoller to see if there were any freed goroutines that could be taken for execution.

There's still a small problem here—it might happen that the Processors always have enough work and they stop checking the netpoller altogether, or do it very rarely. This isn't very fair to the goroutines waiting there, so we'll teach Sysmon to perform such checks in the background. If the netpoller hasn't been accessed for more than 10ms, Sysmon will do it. In doing so, it will move the freed goroutines to the GRQ, and then the Processors themselves will perform balancing using the mechanisms we discussed above (remember that the GRQ is checked out of turn once every 61 iterations).

Now let's emphasize again that not all syscalls support asynchronous operation. For example, network operations do, but file operations do not. How can this knowledge be used in practice? Very simply:

// Это будет работать через netpoller
conn, _ := net.Dial("tcp", "example.com:80")
data, _ := conn.Read(buf)

// А это заблокирует тред
file, _ := os.Open("bigfile.dat") data, _ := file.Read(buf)

Therefore, when designing Go applications, it's important to understand this difference:

For network I/O operations, you can safely use goroutines—they will be efficiently processed via the netpoller (there are other limitations here, but different ones).
For file operations, you need to be much more careful, as they will block threads.

In fact, in both cases, we come to the conclusion that it's better to use a worker pool, but for different reasons and with different limitations.

Well, one less problem, so let's move on and solve the next one.

8. Goroutine Execution Order

So, we've come up with a very complex mechanism for distributing goroutines among Processors. It already works quite well, and goroutines are distributed very efficiently. Now let's discuss the order in which processors will execute their goroutines from the LRQ.

The simplest thing to come up with here is to just execute all goroutines in order (the word "queue" will be in your dreams tonight!). That is, the Processor takes the first goroutine from the LRQ, executes it, then takes the next one, executes it, and so on. If our goroutines are short-lived, this will work quite well.

Do you already see the problem here? What if we have long-running or even eternal goroutines? For example, nothing stops us from launching a hundred goroutines that will periodically check something throughout the program's execution. But since we have a limited number of cores and, consequently, Processors—say, 8—only 8 of all these goroutines will be executing; the rest will wait forever.

Текущая горутина выполняется очень долго, а остальные вынуждены простаивать, ожидая её — The current goroutine is running for a very long time, and the others are forced to idle while waiting for it.

This is bad, because every goroutine should get its share of processor time. How will we solve this? Very simply—at certain moments, the goroutine will check if it's time for it to pause and let others work.

We just need to decide at which moments it will do this and how it will know it's time to take a break. Let's start with the first part—the checks should be performed at moments that are safe and optimal for preemption. The best points for us are:

Before function calls (prologue): When a function is called, a stack frame is created (a dedicated area in memory where local variables, the return address, and other function data are stored). If an interruption occurs at the moment of the function call, all the necessary information is already saved in the frame, so the goroutine can be paused without the risk of losing data. When execution resumes, the goroutine will start from this function call, using the same variable values.
When performing blocking operations (our beloved syscalls, timers, etc.): at these moments, the goroutine will be waiting and idle anyway, so let someone else work.

Okay, so a goroutine has reached a check point. How will it know it's time to yield the Processor? Let's do it in the simplest, most straightforward way—we'll give each goroutine a flag, stackguard. When we need to interrupt a goroutine, we'll set this flag to a special value, stackPreempt. At the next check, the goroutine will see this value and understand that it's time to hand over control to the scheduler.

Now let's figure out who and when will tell the goroutine it needs to be interrupted. And here, our old friend Sysmon will help us again. Let's give it another task. In addition to checking for blocked syscalls, it will also check the execution time of active goroutines. If one of them runs for too long (more than 10ms), Sysmon will set its flag stackguard=stackPreempt so that it will be interrupted at the next check.

Горутина проверяет значение stackguard, которое устанавливает Sysmon. Если оно равно stackPreempt, то она передаёт управление планировщику — The goroutine checks the value of `stackguard`, which is set by Sysmon. If it equals `stackPreempt`, it hands over control to the scheduler.

This approach to scheduling is called cooperative multitasking—it's when processes themselves decide when to yield control to others. Unlike the preemptive multitasking of an operating system, where a thread can be interrupted at any moment, here goroutines themselves control the moment of yielding control.

Is everything good here? Overall, it's already quite good—the Go scheduler existed in this form for a long time and was called cooperative. But all this time, there was one very well-known problem that was finally solved only in Go version 1.14.

Forced Preemption of Greedy Goroutines in Go v1.14

Let's imagine the following situation. Suppose we have only one Processor—this is easy to achieve using the `runtime.GOMAXPROCS` function—and it is processing a goroutine. This goroutine is actively calculating something and doesn't want to yield control—for example, it's performing some calculations in an infinite loop:

func main() {
   // Устанавливаем количество процессоров = 1
   runtime.GOMAXPROCS(1)

   // запускаем "жадную" горутину, которая захватит процессор
   go func() {
       sum := 0
       for {
           sum++ // бесконечный цикл без вызовов функций
       }
   }()
   
   // Запускаем time.Sleep, чтобы передать управление жадной горутине
   // и не выйти раньше времени из main()
   time.Sleep(time.Second)
}

We have a serious problem—the goroutine has blocked the entire Processor and has no intention of giving it up! It doesn't call functions, which means it doesn't check stackguard, it doesn't perform blocking operations, it just steals all the resources, and our Sysmon can't do anything about it.

Sysmon попросил горутину уступить Процессор, установив флаг stackguard, но горутина занята работой и не проверяет его — Sysmon asked the goroutine to yield the Processor by setting the `stackguard` flag, but the goroutine is busy working and doesn't check it.

What should we do? We can't get through to the goroutine—no matter how we send it messages, it simply doesn't read them, being busy with other work without stopping. We need some mechanism that will interrupt it externally. Fortunately, the OS provides us with such a mechanism—signals.

Signals are a mechanism for notifying processes of events at the OS level. The key point for us is that when a signal is sent, the OS interrupts the process's execution and runs a special handler that the process itself has set. It is this handler that will save the goroutine's state and return control to the scheduler.
As you might have guessed, I also have a detailed post on this topic.

In Unix systems, the signal SIGURG is used for this. It was chosen because it is rarely used in ordinary programs (it was originally intended for notifying about urgent network events), which means we can safely use it for our own purposes.

Windows, by the way, is a separate story, and I really don't want to dive into it (there isn't even a separate detailed post this time...). Just keep in mind that the implementation is somewhat different, but the essence is roughly the same.

Now that we have a suitable mechanism, we can proceed as follows. If a goroutine doesn't voluntarily yield control for too long (~10ms), we will send it a signal and interrupt it forcibly.

Now we have two ways to preempt goroutines:

The main way—through checking `stackguard` at safe points. The goroutine decides for itself when to stop.
The backup way—through operating system signals, if the goroutine doesn't want to stop on its own.

However, the second method doesn't always work. In some parts of the code, interrupting a goroutine is dangerous—for example, during garbage collection or system calls. In such cases, we have to rely only on the first method.

This is the mechanism that was introduced in Go version 1.14, and the scheduler became cooperative-preemptive. You have probably heard about this, but perhaps you didn't understand it well or have even forgotten. But now you even know how it works.

By the way, don't confuse this mechanism with what we discussed in the handoff section. There, Sysmon also monitors the execution time of threads (also with a 10ms timeout), but for a different purpose—it checks if a thread has been released from a system call, and if not, it performs a handoff. In that case, we are only interested in blocked threads, whereas here we are monitoring actively running goroutines that do not want to yield control voluntarily.

Conclusion

Well, we have built an effective scheduler—it makes the most efficient use of available processor cores while minimizing the number of operating system threads.

And now it's very useful to look at and examine the final diagram in its entirety:

Общая схема внутреннего устройства планировщика Go — Overall diagram of the internal structure of the Go scheduler

And here is the original diagram in Excalidraw, if you want to study it more closely.

I advise you to spend a little more time, don't be lazy, and carefully go over all the elements of the diagram and the connections between them—this will help solidify your understanding of everything you've read above.

Thank you to everyone who read the article to the end—you've done a huge amount of work, and that deserves respect! Now is the perfect time to lie down and get some sleep (a nap will do too), so your brain can digest the information and build new neural connections. And then you can go to an interview to test your new knowledge in a real-world setting ;)

By the way, while preparing complex videos and articles (like this one), I usually write a series of preparatory posts on my Telegram channel, to make it even easier for subscribers to understand the material.

In general, I have a lot of different projects, and my Telegram channel is the main hub for staying up to date with all of it. In it, I post news about all aspects of my activities, gather feedback—ideas for new videos and articles, about new episodes of our podcast about Go, and more. And most importantly—I'm much more active on Telegram than on Habr or YouTube.

Also, a reminder, if you want a continuation of this article where I dissect the scheduler using my utility goschedviz, as in the video, then write in the comments. If there's enough interest, I'll do it.

The Go Scheduler — The Most Detailed Guide in Simple Terms