Shulou(Shulou.com)06/01 Report--

Today, I will talk to you about how to implement the concurrent model in Golang and JVM. Many people may not know much about it. In order to make you understand better, the editor summarizes the following contents. I hope you can get something according to this article.

It seems that I haven't updated my blog for a long time, mainly because I have been reading all kinds of books and source codes recently, and most of the records I have made are of the nature of reading notes, so they have not been sorted out on the blog. After that, I will sort out some things one after another.

Introduction

Recently, I finally decided to take out the lab of the mit-6.824 course, which has been collected for a long time. The most valuable thing about this course is that it has designed a series of lab, so that you can have a more in-depth understanding of some common problems faced by many distributed programs and how to solve them after a certain degree of controllable workload of coding. For example, distributed fault tolerance, concurrency, network underlying implementation, and so on. The targeted language for this course is golang. The reason goes without saying, because of the simplicity of golang, it is very suitable to replace languages such as C++ as the implementation language of lab.

In the process of implementation, one of the main problems I encountered is how to find a balance between CPU-intensive tasks, I-CPU-intensive tasks and making full use of multicore CPU to improve program performance. Of course, the easiest solution to think of is multithreading. However, due to the particularity of the distributed program, it may have a large number of network I / O or computing tasks. This inevitably requires the use of synchronous way to express asynchronous feelings, the solution is to put these calculations or IO into a new thread to do, specific thread scheduling to the operating system to complete (although we can use asynchronous IO, but asynchronous IO due to the existence of a large number of callback, not easy to program logic organization, so here do not consider the direct use of asynchronous IO). One problem with this is that there will be a large number of threads in the context, so the overhead of thread context switching can not be ignored. If we implement it in jvm, a large number of thread may quickly deplete the memory of the jvm heap, not only causing a heap overflow, but also increasing GC time and instability. Therefore, I have recently examined several common concurrent programming models and their corresponding common implementations.

Classification of common concurrent programming models

The concurrent programming model, as its name implies, is a related programming paradigm proposed to solve the problem of high concurrency and make full use of multi-core features to reduce CPU waiting to improve throughput. So far, I think the more common concurrent programming models can be roughly divided into two categories:

Active object based on message (event)

Implementation of Cooperative Program based on CSP Model

Yes, it seems that a great god has already done it, and academia is terrible!

First of all, the first problem is that when M finds that all the gorouine linked lists in P have been executed, it will steal goroutine from other P and execute it, and its strategy is a working secret fetching mechanism. When the other P has no executable goroutine, it looks for the goroutine of the runnable from the global waiting queue for execution, and if it cannot be found, M gives up the CPU schedule.

The second problem, such as blocking IO from reading local files, will trap systemcall into the kernel and inevitably block the calling thread, so what goroutine does here is to encapsulate all system calls that may be blocked into gorouine-friendly interfaces. The specific method is that before each system call, an OS Thread is obtained from a thread pool and the system call is executed, while the running gorouine changes its state to Gwaiting and gives control to scheduler to continue scheduling, and the return of the system call can be synchronized through channel. Therefore, there is no way for goroutine to be fully co-programmed here, because system calls always block threads. For more information, see the discussion on stackoverflow: links

Third, go supports simple preemptive scheduling, and there is a sysmon thread in goruntime that detects the various states of the goruntime. One of the responsibilities of sysmon is to detect whether there is a goroutine that has occupied CPU for a long time, and if it is found, it will be preempted.

The reason why goroutine cannot be implemented on JDK

Now that we have a general understanding of the principle of goroutine, we can see that one of the most important designs of goroutine is that it limits api at all language levels to goroutine, thus blocking the opportunity to execute code to interact with specific threads. So in goroutine, we can actually ignore threads and think of goroutine as a very cheap Thread that can be created in large quantities.

However, in Java or JVM languages (such as scala,clojure) that intend to interact with JDK, it is essentially impossible to fully implement goroutine (although clojure has async, it still does not integrate well with blocking api in JDK). Suppose that we implement a scheduler, a lightweight co-program and its related primitives (such as resume, pause, etc.) in Java based on Thread, and we can only assist in co-program scheduling based on our own encapsulated api. If you use Java to block api directly in the created protocol, the result is that the OS Thread used to schedule the protocol is blocked and cannot continue to run scheduler for scheduling.

To sum up, if we do not change the JDK Native implementation of the premise, we will not be able to completely implement a goroutine-like collaboration.

TODO

So, if we want to make JDK support coroutine, then we have to change JDK. Yes, I am so persistent! =. =

List some Related Work first:

JCSP CSP for Java Part 1 CSP for Java Part 2

As shown in the figure above, we can see that there are two M, that is, two OS Thread threads, each corresponding to a P, each P is responsible for scheduling multiple G. In this way, the basic structure of the goroutine runtime is formed.

Let's analyze the specific code of G M P.

one

two

three

four

five

six

seven

eight

nine

ten

eleven

twelve

thirteen

fourteen

fifteen

sixteen

seventeen

eighteen

nineteen

twenty

twenty-one

twenty-two

twenty-three

twenty-four

twenty-five

twenty-six

twenty-seven

twenty-eight

twenty-nine

thirty

thirty-one

thirty-two

thirty-three

thirty-four

thirty-five

thirty-six

thirty-seven

thirty-eight

thirty-nine

forty

forty-one

forty-two

forty-three

forty-four

forty-five

forty-six

forty-seven

Struct G

{

Uintptr stackguard0;// is used for stack protection, but can be set to StackPreempt for preemptive scheduling

Uintptr stackbase; / / Top of Stack

Gobuf sched; / / execution context on which G suspends and resumes execution

Uintptr stackguard; / / is the same as stackguard0, but it will not be set to StackPreempt

Uintptr stack0; / / bottom of stack

Size of the uintptr stacksize; / / stack

Six states of int16 status; / / G

Identification id of int64 goid; / / G

Int8* waitreason; / / when status==Gwaiting is useful, the reason to wait may be to call time.Sleep or the like

G* schedlink; / / points to the next G of the linked list

Uintptr gopc; / / create the program counter PC of the Go statement of this goroutine. Specific functions and lines of code can be obtained through PC.

}

Struct P

{

The extended syntax of Lock; / / plan9 C, equivalent to Lock lock

Identification id of int32 id; / / P

Four states of uint32 status; / / P

P * link; / / points to the next P in the linked list

M * m; / / this value is nil in the status of the current binding of MJR.

MCache* mcache; / / memory pool

/ / G queue with Grunnable status

Uint32 runqhead

Uint32 runqtail

G* runq [256]

/ / G-linked list of Gdead status (through G's schedlink)

/ / gfreecnt is the number of nodes on the linked list

G* gfree

Int32 gfreecnt

}

Struct M

{

G* g0; / / M executes G by default

Void (* mstartfn) (void); / / function pointer executed by the OS thread

G* curg; / / currently running G

P * p; / / the currently associated P, which can be nil if G is not currently executed

P * nextp; / / P to be associated

Identification id of int32 id; / / M

M* alllink; / / is added to allm to prevent it from being garbage collected (GC)

M * schedlink; / / points to the next M in the linked list

}

Here, the three most important states of G are Grunnable Grunning Gwaiting. The specific state transition is Grunnable-> Grunning-> Gwaiting-> Grunnable. Goroutine saves and restores the context of the stack when the state changes. Let's open the definition of Gobuf in G next.

one

two

three

four

five

six

Struct Gobuf

{

Uintptr sp; / / stack pointer

Uintptr pc; / / Program counter PC

G* g; / / associated G

}

When it comes to saving the stack context, the most important thing is to save the contents of the Gobuf structure. Goroutine specifically uses void gosave (Gobuf*) and void gogo (Gobuf*) to save and restore the stack context, and the specific underlying implementation is assembly code, so the context swtich of goroutine will be very fast.

Next, let's take a specific look at the scheduling strategy of goroutine scheduler in several major scenarios.

Goroutine hands the execution of the scheduler to the specific M, that is, OS Thread. Each M executes a function, void schedule (void). What this function does is select the appropriate goroutine from each run queue and execute the corresponding func in the goroutine.

The specific schedule functions are as follows:

one

two

three

four

five

six

seven

eight

nine

ten

eleven

twelve

thirteen

fourteen

fifteen

sixteen

seventeen

eighteen

nineteen

twenty

twenty-one

twenty-two

twenty-three

twenty-four

twenty-five

twenty-six

twenty-seven

twenty-eight

twenty-nine

thirty

thirty-one

thirty-two

thirty-three

thirty-four

thirty-five

thirty-six

thirty-seven

thirty-eight

thirty-nine

/ / A round of scheduling: find the G that can be run, and execute

/ / never return

Static void schedule (void)

{

G * gp

Uint32 tick

Top:

Gp = nil

/ / check the global runnable queue from time to time to ensure fairness

/ / otherwise, the two goroutine are constantly reborn to each other, completely occupying the local runnable queue

Tick = m-> p-> schedtick

/ / Optimization skill, in fact, tick%61 = = 0

If (tick-((uint64) tick*0x4325c53fu) > 36) * 61 = = 0 & & runtime ·sched.runqsize > 0) {

Runtime ·lock (& runtime ·sched)

Gp = globrunqget (m-> p, 1); / / get available G from the global runnable queue

Runtime ·unlock (& runtime ·sched)

If (gp)

Resetspinning ()

}

If (gp = = nil) {

Gp = runqget (m-> p); / / if it is not found in the global queue, look in the local runnable queue of P

If (gp & & m-> spinning)

Runtime ·throw ("schedule: spinning with local work")

}

If (gp = = nil) {

Gp = findrunnable (); / / block until an available G is found

Resetspinning ()

}

/ / whether to enable the specified M to execute the G

If (gp- > lockedm) {

/ / give P to the specified m, and then block the new P

Startlockedm (gp)

Goto top

}

Execute (gp); / / execute G

}

So here are a few questions:

What happens when M discovers that the goroutine linked list assigned to him has been executed? When goroutine is stuck in system call blocking, does M also block? What happens when a gorouine takes up CPU for a long time?

First, we assume that a coroutine mechanism based on an existing Thread model can be established in JDK, and that you can call some methods to create coroutine objects, assign coroutine tasks, and execute them. However, there are many existing blocking operations in JDK, and the calls to these blocking operations will directly block the thread, so that the thread-dependent coroutine will lose the ability to reschedule. You may have a lot of other ways to design, but the essential problem here is that no matter how you design, you can't get rid of the inconsistency between the co-program state and the thread state in JDK. Unless it is done as in Go, all blocking operations are performed by wrap to the level of the co-program. So, once we use JDK and thread-bound blocking API, this concurrency model is basically out of order.

So let's analyze the implementation principle of goroutine to explain why Java can't do the same kind of cooperation as goroutine.

Goroutine principle

Between the OS Thread of the operating system and the User Thread of the programming language, there are actually three thread correspondence models, namely: 1, 1, 1, 1, 1, 1, 1, 1, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 5, 5, 5, 5, 5, 5, 5, 4, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 and 4 respectively.

The relationship between the JVM thread and the operating system thread is specified at 1:1 in JVM specification, which means that the relationship between Thread and OS Thread in Java is 1:1. There are also patterns that implement the threading model as 1Rom N, but this is not flexible enough. The default implementation of goroutine google runtime is the MOS Thread N model, so it is more flexible to adjust the mapping between goroutine and OS Thread according to the specific operation type (operating system blocking or non-blocking operation).

In the goroutine implementation, there are three most important data structures, namely G M P:

G: represents a goroutine M: represents an OS Thread P: a P is bound to an M, representing the scheduler on this OS Thread

Among them, the most typical representative of the concurrency model of active objects based on messages (events) is Akka's actor. The concurrency model of actor is to abstract each computing sequence into an Actor object, and each Actor communicates through asynchronous message passing mechanism. In this way, the computational sequences that are sequentially blocked are dispersed into an Actor. Our operation in Actor should be as non-obstructive as possible. Of course, in akka, actor determines how to handle a certain actor message according to the specific Dispatcher. The default dispatcher is ForkJoinExecutor, which is only suitable for processing non-blocking and non-CPU-intensive messages; there are other Dispatcher in akka that can be used to deal with blocking or CPU-intensive messages, and the specific underlying implementation uses CachedThreadPool. With the combination of these two Dispatcher, we can build a complete concurrency model on jvm.

Based on the implementation of the cooperative program, the main representative here is goroutine. Golang's runtime implements goroutine and OS thread's goroutine N model, so the actual goroutine is a more lightweight implementation based on threads, so we can create a large number of goroutine in Golang without worrying about the overhead of expensive context swtich. Between goroutine, we can interact with each other through channel. Because go has wrap all the systemcall into the standard library, calls to these systemcall will proactively mark the goroutine as blocking state and save the scene for scheduler to execute. So in golang, in most cases we can safely use blocking operations in goroutine without worrying about concurrency being affected.

This concurrency model of goroutine has a very obvious advantage. We can simply use the popular blocking programming method to express asynchronous feelings, as long as we can use the go keyword properly. Compared with akka's actor, goroutine's program is more readable and better at locating errors.

Can Java be like goroutine?

Since goroutine is so easy to use, can we implement a set of concurrent model libraries similar to goroutine based on jdk? (here I raised a related question in Zhihu, see here for more details.) Unfortunately, it can't be realized based on JDK. Let's analyze the nature of the problem.

Below, I define the concurrency model of goroutine as the following points:

Lightweight co-programs based on Thread for message passing between protocols through channel only expose the co-programs and shield the interfaces of thread operations.

After reading the above, do you have any further understanding of how to discuss the implementation of the concurrency model in Golang and JVM? If you want to know more knowledge or related content, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.