一行shell实现统计单词词频

写一个 bash 脚本以统计一个文本文件 words.txt 中每个单词出现的频率。

为了简单起见,你可以假设:

words.txt只包括小写字母和 ‘ ‘ 。
每个单词只由小写字母组成。
单词间由一个或多个空格字符分隔。
示例:

假设 words.txt 内容如下:

the day is sunny the the
the sunny is is
你的脚本应当输出(以词频降序排列):

the 4
is 3
sunny 2
day 1

代码:
cat words.txt tr -s ‘ ‘ ‘n’ sort uniq -c sort -rnk1 awk ‘{print $2,$1}’

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/word-frequency
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
————————————————

二十三式武功招式--总纲

扯淡

写程序犹如练武,一样需要内外兼修。

数据结构算法,操作系统原理,编译原理这些知识就犹如武侠中的内功心法,需要日夜旦夕苦练,经年累月方能有所小成。

而内功一旦有所成就,其它任何武功学起来就会轻松加愉快。

比如射雕中的郭靖,起初江南七怪教时,进展缓慢。自从全真教掌教马钰传授了一些呼吸吐纳的内功修练方法后,则进步神速。再如黑风双煞虽然有九阴真经下册,但也只学会了”九阴白骨掌”,始终无法达到五绝的水平,就是因为下册只有招式,没有上册的心法加持,难以更进一步。

说完了内功,再谈招式。招式是一些有着固定套路的功夫。招式可分为防守型和进攻型。针对不同的敌人,不同的兵器,不同的场景,可以采用一些固定的招工。你来一招”长虹贯日”,我还一招”有凤来仪”。如果不学扫式,对战起来就只能像一些市井之徒一样,乱打一通。而在程序里面,设计模式就如同招工一样,这23招都是无数高手在实战中总结出来的晶华,能够应对大多数的对战场景。但是招是死的,人是活的,好的招式最终还是要靠人去发挥其威力。

最后是兵器,编程语言就是兵器,我们有了内功和招式之后,还需要使用兵器。而兵器之中也有倚天剑,屠龙刀这种绝世神兵,即使是个小菜鸟,拿着这些兵器也能上来就发挥出唬人的威力。

习武的层次和写程序的层次也是一样的。起初我们可能沉迷于选择一些厉害的兵器,将一种兵器使用的得心应手之后。可能就会去练其它的兵器,并乐此不疲。练了几年之后,发现练来练去也无法提高了。这时候就需要去学习一些招式,所有的套路都练熟了之后。能否成为顶尖高手,比拼的就是内功修维了。这时候,我们最终想要达到的就是独孤求败这种不滞于物,草木皆可为剑的境界;以及独孤九剑这种随心而发,剑之所至,无招胜有招的境界。

这篇武功秘笈讲的是第2层修维,招式。即23种设计模式。

在架构设计,代码框架设计的过程中,我们始终逃不开的都是以下3类问题:对象创建,模块结构,组件行为交互。因此23种设计模式也是针对解决这3类问题的。因此这篇总纲就是先总体将23种招式化入这3种场景之中,供学习者抓住其要旨。

总纲

使用这23招的根本目的都是代码复用,以及方便扩展功能。而实现这一目标的关键就在于分离关注点,使得各组件能够独立地演化。

目的

创建型

结构型

行为型

范围

工厂方法(Factory Method)

适配器(Adapter使用继承)

解释器(Interpreter)

模板方法(Template Method)

对象

抽象工厂(Abstract Factory)

适配器(Adapter使用组合)

责任链(Chain of Responsibility)

构造者(Builder)

桥接模式(Bridge)

命令模式(Command)

原型模式(Prototype)

组合模式(Composite)

迭代器(Iterator)

单例(Singleton)

装饰器(Decorator)

仲裁者模式(Mediator)

门面模式(Façade)

备忘录模式(Memento)

享元模式(Flyweight)

观者者模式(Observer)

代理模式(Proxy)

状态模式(State)

策略模式(Strategy)

访问者模式(Visitor)

下面是本篇秘笈23式的招式及其要旨所在

  • 抽象工厂Abstract Factory:提供一个创建一系列相关或相互依赖对象的接口,而无需指定它们具体的类

  • 适配器Adapter:将一个类的接口转换为客户希望的另外一个接口。使得原本由于接口不兼容而不能一起工作的类可以一起工作

  • 桥接模式Bridge:将抽象部分与它的实现部分分离,使它们都可以独立地变化

  • 建造者模式Builder:将一个复杂对象的构建与表示分离,使得同样的构建过程可以创建不同的表示

  • 责任链Chain of responsibility:为解除请求的发送者和接收者之间的耦合,而使多个对象都有机会处理这个请求。这些对象形成一条链,并沿着此链传递请求,直到有一个对象处理它

  • 命令模式Command:将一个请求封装成一个对象,从而使你可用不同的请求对客户进行参数化;对请求排队或记录日志,以及支持可取消的操作

  • 组合模式Composite:将对象组合成树形结构以表示“整体-部分”的层次结构。组合模式使得单个对象和复合对象的使用具有一致性

  • 装饰器模式Decorator:动态地给一个对象添加一些额外的职责。就扩展功能而言,装饰器比生成子类更灵活

  • 门面模式Facade:为子系统中的一组接口提供一个一致的界面,其定义了一个高层次的接口,这个接口使得这一子系统更加容易使用

  • 工厂方法Factory Method:定义一个用于创建对象的接口,让子类决定将哪一个类实例化,其使一个类的实例化延迟到子类

  • 享元模式Flyweight:运用共享技术有效地支持大量细粒度的对象

  • 解释器Interpreter:给定一个语言,定义它的文法的一种表示,并定义一个解释器,该解释器使用该表示来解释语言中的句子

  • 迭代器Iterator:提供一种方法顺序访问一个聚合对象中各个元素,而又不暴露该对象的内部表示

  • 仲裁者Mediator:用一个中介对象来封装一系列的对象交互。中介者使各对象不需要显式地相互引用,从而使其松耦合,而且可以独立地改变它们之间的交互

  • 备忘录Memnto:在不破坏封装的前提下,捕获一个对象的内部状态,并在该对象之外保存这个状态。这样以后就可以将对象恢复到保存的状态

  • 观者者Observer:定义对象间的一种一对多的依赖关系,以便当一个对象的状态发生变化时,所有依赖于它的对象都得到通知并自动刷新

  • 原型Prototype:用原型实例指定创建对象的种类,并且通过拷贝这个原型来创建新的对象

  • 代理Proxy:为其他对象提供一个代理以控制对这个对象的访问

  • 单例Singleton:保证一个类仅有一个实例,并提供一个访问它的全局访问点

  • 状态State:允许一个对象在内部状态改变时改变它的行为。对象看起来似乎修改了它所属的类

  • 策略Strategy:定义一系列的算法,把它们一个个封装起来,并且使它们可以相互替换。本模式使得算法的变化可独立于使用它的客户

  • 模板方法Template Method:定义一个操作中的算法的骨架,而将一些步骤延迟到子类中。使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤

  • 访问者Visitor:表示一个作用于某种对象结构中的各元素的操作。它可以使你在不改变各元素类的前提下定义作用于这些元素的新操作

既然是招式,必然要熟悉其应用的场景,而且要经过大量的实战练习。因此后面的秘笈将以实际的代码为基础进行讲解。

除了一些便于记忆的实际代码外还会加入优秀开源框架代码中的例子,以便能够参考高手是如何使用这些招式的。

gRPC C++源码剖析(二) ---------数据结构篇之闭包调度器

grpc_closure_scheduler
顾名思义,闭包调度器的作用就是对闭包进行调度。

下面是它的定义:

struct grpc_closure_scheduler {
  const grpc_closure_scheduler_vtable* vtable;
};

typedef struct grpc_closure_scheduler_vtable {
  void (run)(grpc_closure closure, grpc_error* error);
  void (sched)(grpc_closure closure, grpc_error* error);
  const char* name;
} grpc_closure_scheduler_vtable;

通过上一节的介绍,我们知道在创建闭包是会为其指定调度器,然后可以调用GRPC_CLOSURE_RUN(closure, error)在调度器上运行闭包或者调用GRPC_CLOSURE_SCHED(closure, error)在调度器上调度闭包。

其实这2个方法就是对调度器run和sched方法的调用。

调度的作用就是为闭包提供运行环境,那么gRPC提供了哪些调度器,这些调度器的作用和应用场景有是哪些呢?

 
grpc_schedule_on_exec_ctx
这个调度器可能是用的最多的了,它的作用是在当前线程的ExecCtx上运行闭包。

有必要先了解一下ExecCtx。代码中对这个结构的作用说明是在调用栈上收集数据信息,是不是太抽象了。

考虑下面的场景:


A,B,C,D为4个依次调用的函数,B执行过程中调度了一个闭包1,并希望其在返回到A时执行。D同样调度了闭包2,也希望返回到A时再执行。这个时候就要使用这个调度器了grpc_schedule_on_exec_ctx.

要达到这种目的,我们要做的就是在A中声明ExecCtx,然后在B,D中调度绑定给grpc_schedule_on_exec_ctx调度器的闭包,然后在返回A时调用ExecCtx的Flush方法,这样就能达到目的了.ExecCtx内部维护了一个队列,用于存放调度给它的闭包。调用Flush方法时再依次从队列中取出闭包并运行。

在最新的gRPC版本中,简化了这种调度器的使用方法。gRPC框架为每个线程创建了这个ExecCtx,并存放在线程私有变量中,当需要时,只需要调用grpc_core::ExecCtx::Get()即可获取并使用。

可能你会问,搞这么复杂有什么意义呢?

我认为可能有以下2个好处:

1.可以使代码更加清晰

2.可以避免和缓解调用栈层次过深

你还有什么见解,欢迎来交流。

global_executor
全局调度器,这个调度器是在gRPC启动时创建的。它内部使用一个线程池,最多会创建CPU核心数相同的线程。

在这个调度器上调度的闭包会在这些全局线程中运行。

gRPC主要使用它来运行一些阻塞的任务,如dns解析。

要使用这个调度器,使用grpc_executor_scheduler这个接口

好了调度器的相关知识就介绍完了,理解调度器对我们理解gRPC的代码执行流有很大的帮助。
————————————————
版权声明:本文为CSDN博主「self-motivation」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/happyAnger6/article/details/102753742

gRPC C++源码剖析(二)---- 数据结构篇之闭包

上篇文章中提到了阅读gRPC源码的几大困难,其中数据结构是基础中的基础。

如果连这些数据结构的原理和作用都不了解的话,阅读起代码来肯定事倍功半。因此这篇文章对gRPC提供的数据结构进行讲解。

grpc_closure闭包
闭包是一些编程语言中提供的功能,如python. 

closure就是闭包的英文名称.

简单的理解,闭包函数将创建闭包时的上下文中的变量与自己绑定在一起,将变量的生存期和作用域延长到闭包函数结束。

概念有点儿抽象,下面是python中一个闭包的例子:

def add_n(n):
def real_add(m):
nonlocal n
n+=1
return n + m
return real_add

f = add_n(10)
print(f(5)) //输出16
print(f(5)) //输出17
注意real_add函数,它将函数体外的变量n与自己绑定,能够访问和修改它.

那么闭包有什么好处呢?

通过上面的例子,我们可以看到创建闭包时将变量与其绑定,在闭包实际运行时再使用它。

这样能够方便地在创建闭包时即将当前上下文中的变量传递给它,因为在运行闭包时并不容易再得到这个变量。

这个特性十分有利于在gRPC中方便的编写异步代码。

为了方便地使用闭包,gRPC提供了下面4个宏:

GRPC_CLOSURE_CREATE(cb, cb_arg, scheduler):创建一个闭包,返回创建后的闭包。参数分别为:回调函数,参数,调度器

GRPC_CLOSURE_INIT(closure, cb, cb_arg, scheduler):初始化一个闭包,第一个参数为要初始化的闭包。后面3个参数同上

GRPC_CLOSURE_RUN(closure, error):立即运行一个闭包,并传递错误状态.

GRPC_CLOSURE_SCHED(closure, error):调度一个闭包,并传递错误状态。

可以看出,创建闭包时将当前上下文的参数cb_arg传递给闭包对象保存,实际运行闭包时闭包就会使用这个创建时的参数。

上面提到的调度器在下文会详细介绍。

运行(GRPC_CLOSURE_RUN)和调度闭包(GRPC_CLOSURE_SCHED)的区别是:运行闭包立即运行。调度闭包是在指定的调度器上运行闭包,运行上下文可能是当前线程,也可能是另外的线程。

最后看gRPC源码中一个实际使用闭包的例子:

创建闭包
tcp_server_start()

{
    …
    grpc_tcp_listener* sp;
    …
            GRPC_CLOSURE_INIT(&sp->read_closure, on_read, sp,
                              grpc_schedule_on_exec_ctx);
}

在启动tcp监听时,创建一个read_closure闭包,并将当前的监听者信息绑定到闭包上。

运行闭包
当epoll循环监听到有连接接入时,会实际运行闭包.

        fd_become_readable(fd, pollset)—-> fd->read_closure->SetReady()—->GRPC_CLOSURE_SCHED((grpc_closure*)curr, GRPC_ERROR_NONE);;

这时候就会实际调用on_read函数

static void on_read(void* arg, grpc_error* err) {
  grpc_tcp_listener* sp = static_cast(arg);

}

on_read函数这时就能够使用创建时绑定的sp变量了.

怎么样,通过上面的讲解,应该知道了闭包的原理和作用了。再在源码中看到闭包相关代码,应该能够理解了吧!?

下一篇将介绍调度器
 
————————————————
版权声明:本文为CSDN博主「self-motivation」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/happyAnger6/article/details/102750612

gRPC C++ 源码剖析(一)----------入门

通过一段时间阅读gRPC c++的源码,对其实现原理算是初窥门境了。

在这里通过一系列循序渐进的文章把其中的经验和学习到东西分享出来,希望志同道合之人能够共同交流进步。

gRPC c++源码难吗?

个人认为gRPC c++源码算是质量比较高的源码了,google工程师们的抽象和设计能力都能够在其中有所体现。

可是阅读其源码还是有不少困难的,个人认为造成源码阅读困难的原因有以下几个:

  1. 是用C++写的

出于性能和灵活性的考虑,gRPC的核心代码是用C++写的,其中有部分代码还是C的。最新的gRPC代码已经将大部分C代码用C++重写了。

如果对C++语言不熟悉的话,就很容易被gRPC所使用的很多C++语言特性所迷惑,而不得其要旨。比如模板,智能指针,继承多态等等。

2.很多高级的抽象

gRPC的源码为了简化异步代码的编写,同时为了更好的代码复用。设计了许多高级的数据结构。如grpc_closure,grpc_closure_scheduler,ExecCtx,grpc_combiner,grpc_completion_queue等。如果不能很好地理解这些高级数据结构的作用和原理,阅读起代码来也会事倍功半。

3.大量的设计模式

为了提供跨平台能力,grpc核心代码采用了bridge设计模式,因此可以看到各种vtable,这也为阅读源代码增加了困难。

4.异步编程

grpc核心库采用reactor设计模式,如grpc_closure就是为了方便异步编程而设计的数据结构。

5.高性能

出于性能考虑,gRPC还使用了无锁队列这种高级数据结构,不熟悉其原理的读者可能会陷入各种原子操作的细节中。

阅读gRPC源码有哪些收获?

其实上面阅读源码的困难也就是收获,如何高效地在C中进行异步编程,如何抽象数据结构和使用设计模式,如何编写高性能代码,如何使用C++的高级特性等等。

说了这么多,是不是已经跃跃欲试了呢?让我们从下节开始吧!

list

从本篇文章开始,将介绍python提供的常用数据结构。

这些数据结构从不同的维度可以进行不同的划分。

按可变性划分:

  1. 可变数据结构:list,dict,set,bytearray
  2. 不可变数据结构:tuple,string,bytes

按是否可以存储不同类型的元素划分:

  1. 扁平数据结构:string,bytes,bytearray
  2. 容器数据结构:list,dict,set,tuple

后面将会陆续从序列,集合,映射,可调用对象这4类来逐一介绍。

介绍list之前,我们有必要了解一下什么是序列.

之所以称为序列,是因为它们都有以下特性.

  • 能够通过索引来进行顺序访问
  • 内置的函数len()可以返回序列的长度。如果序列的长度为n,则可以通过0….n-1来访问每个元素
  • 支持切片操作a[i:j]
  • 序列类型有string,tuple,bytes,list,bytearray几种

好了,地基打好了,我们开始学习序列中的首个类型:list.

list是python中最常用的数据结构之一.基本上可以将其看作是一个可以动态增长且使用方便的数组.

list是一种容器,可以容纳任意的python对象.

要使用list,首先我们需要创建list.

构造list

  1. 空list:[]
  2. 直接构造list:[1,2,3]
  3. 使用列表生成式:[ x for x in iterable]
  4. 使用构造函数:list()或list(iterable)

关于4有几点说明:由iterable构造的list的元素顺序保持不变;可以使用任何可迭代对象来构造list,如list(‘abc’)返回[‘a’, ‘b’, ‘c’],list((1,2,3))返回[1,2,3].如果不指定任何参数,则返回一个空list.

使用list

list实现了序列具有的一些通用方法:

操作

结果

x in s

判断x是否在s中

x not in s

判断x是否不在s中

s + t

连接s,t

s * n or n * s

将s重复n次

s[i]

s中第i个元素,从0开始

s[i:j]

从i到j的切片

s[i:j:k]

以k为步长,从i到j的切片

len(s)

s的长度

min(s)

s中的最小元素

max(s)

s中的最大元素

s.index(x[, i[, j]])

x在s中的第一个位置,可以指定特定的区间[i,j]

s.count(x)

s中x出现的次数

另外,作为可变序列类型,list还具有可变序列的一些通用方法

Operation

Result

s[i] = x

设置第i个元素为x

s[i:j] = t

将i-j设置为可迭代的t

del s[i:j]

删除i到j,等价于 s[i:j] = []

s[i:j:k] = t

用可迭代的t替换i-j,步长为k

del s[i:j:k]

以k为步长删除i-j

s.append(x)

将x添加到s末尾,等价于 s[len(s):len(s)] = [x]

s.clear()

删除s中所有元素,等价于del s[:]

s.copy()

创建s的一个拷贝,等价于s[:]

s.extend(t) or s += t

用t扩充s,等价于s[len(s):len(s)] = t

s *= n

n个s

s.insert(i, x)

在位置i插入x.等价于s[i:i] = [x]

s.pop([i])

获取第i个元素并从s中m删除,不指定i则获取最后一个元素

s.remove(x)

从s中删除第一个等于x的元素

s.reverse()

就地翻转s

最后,list还支持以下方法:

  • sort(*key=Nonereverse=None)

就地排序list,默认使用’<’比较每个元素的大小。

  1. key:我们可以通过关键字参数key来指定排序函数,这个排序函数接受一个元素,根据其返回值决定元素的大小。如果中途发生错误,sort不会抛出异常,list可能处于一个中间状态.python2中有许多比较函数使用2个参数,如locale.strcoll.为了方便地将2.x中的这些函数转换为key可以使用的函数,我们可以使用functools.cmp_to_key来将2.x中的函数进行包装.
  2. reverse:是为逆序.

值得注意的是sort排序是稳定的,意味着会保持2个相同元素的相对位置.

其它

  1. 关于列表表达式:列表表达式可以使代码更具表达力如得到每个字符的ascii值: [ord(x) for x in ‘abc’]
  2. 将list当作栈LIFO来使用十分高效,通过append方法向list末尾添加元素,通过无参数的pop方法将最后一个元素弹出
  3. list不适合作为队列FIFO来使用,因为从头来添加和删除元素需要对剩余元素进行移动。此时应该使用适合在两头进行添加删除的collections.deque.

关于list,掌握这些已经相当够用了。

vim中删除一个单词

目标

假设光标目前处于行尾的e字符上,要删除最后一个单词”line”

this is a test in vim. I want to delete a word in the line.

解决方法

要删除最后一个单词,有以下几种选择。

  • 先用’b’命令把光标先移动到”l”上,然后执行dw删除整个单词.按键3个

  • 执行反向删除命令’db’(会剩余最后的”e”字符),再执行’x’删除单个字符.按键3个

  • 直接执行daw,删除单词并会删除一个空格,光标停留在下一个单词末尾上.按键3个

思考

在Vim中,要完成一件事,总是不止有一种方式。通常使用按键最少的方式(又名VimGolf).然而,上面3种方法的的VimGolf得分都为3,这时该如何选择呢。

这时一般要考虑3种方式对.最友好。即可以重复操作。很明显,第3种方式能够重复执行删除最后一个单词的操作。因此优先使用daw.

开篇词

网上已经有很多关于python的教程了,为什么我还要再搞一个?

其一,出于私心,自己需要系统地总结一下对python的掌握情况

其二,希望能以一种大家喜欢和容易的方式讲解python,每篇文章内容尽可能短而精,能够利用每天的碎片时间进行学习。这也是本系列教程<<地铁上学python>>的由来。

按照惯例,我们先来吹一波学习python的好处。

下图是2019年8月Tiobe编程语言的排行,可以看到Python已经超越C++排名第3,而且还在上升之中.证明Python的热度和应用势头依旧强劲。


其次,Python的生态系统十分繁荣,在很多领域Python都有很好的发展,如机器学习,数据挖掘,甚至树莓派系等等。

另外,Python开发效率高,代码简洁,易于上手,甚至已经被很多学校选为教学语言。在日常工作中,我们也可以利用Python编写很多小工具来提高工作效率。

最后,学习Python当然是因为人生苦短啊。

虽然学习Python有诸多好处,但是劣势也很明显,那就是速度慢。

虽然如此,业界也为Python提速做了很多努力,对性能高的部分可以用C编写。另外还有Cython这个工具,就是希望融合Python的高效和C的性能。

文章结尾再列举一些Python圈里常见的开源软件及他们的作用,以便你对Python的生态有个直观的了解.

机器学习: SciKit-Learn

深度学习:PyTorch

数据采集:Scrapy

数值计算:,Numpy , Pandas,Scipy

数据可视化:Matplotlib

Web开发:web.py,tornado,django,twisted,Flask

运维管理:Ansible

云计算:Openstack

怎么样,看到Python在各种领域的火热了吧,那马上开始和我一起学习Python吧!

Go为什么要做用户态调度

Go1.1中一个大的特性是Dmitry Vyukov实现的新的调度器. 新的调度器为并行的Go程序带来了巨大的性能提升.因此,我必须写这篇文章来介绍一下.

这里是原始的设计文档的链接.设计文档里有所有你想知道的细节,本篇文章通过更多的图片来使描述更加清晰.

为什么Go的运行时需要一个调度器?

在我们详细了解新的调度器之前,我们需要先来看看为什么的问题?

操作系统已经提供了线程调度的功能,为什么还要在用户态实现一个调度器?

POSIX线程API在很大程度上是对现有Unix进程模型的扩展,线程获得了许多和进程同样的控件.线程有它们自己的信号掩码,能够设置CPU亲和力,能够通过cgroups设置可以使用的资源.所有这些控制都增加了额外的开销,当你的程序使用100,000个线程时这些开销快速地增加,而这些对使用goroutines的go程序没有必要.

另外一个问题是:OS不能基于go模型对调度做出正确的决策.比如,Go的gc需要所有线程停止运行,而且内存必须处于一致的状态.这在Go中是通过等待运行的线程运行到某一点,我们知道这时内存处于一致的状态.

当你有很多可以在任意时间点调度的线程,那么你就需要等它们运行到一个一致状态的点.但是Go调度器可以知道内存一致的状态并只在此时进行调度.When you have many threads scheduled out at random points, chances are that you’re going to have to wait for a lot of them to reach a consistent state. The Go scheduler can make the decision of only scheduling at points where it knows that memory is consistent. This means that when we stop for garbage collection, we only have to wait for the threads that are being actively run on a CPU core.

Our Cast of Characters

There are 3 usual models for threading. One is N:1 where several userspace threads are run on one OS thread. This has the advantage of being very quick to context switch but cannot take advantage of multi-core systems. Another is 1:1 where one thread of execution matches one OS thread. It takes advantage of all of the cores on the machine, but context switching is slow because it has to trap through the OS.

Go tries to get the best of both worlds by using a M:N scheduler. It schedules an arbitrary number of goroutines onto an arbitrary number of OS threads. You get quick context switches and you take advantage of all the cores in your system. The main disadvantage of this approach is the complexity it adds to the scheduler.

为了完成调度任务,Go scheduler使用3个主要的实体:


The triangle represents an OS thread. It’s the thread of execution managed by the OS and works pretty much like your standard POSIX thread. In the runtime code, it’s called M for machine.

The circle represents a goroutine. It includes the stack, the instruction pointer and other information important for scheduling goroutines, like any channel it might be blocked on. In the runtime code, it’s called a G.

The rectangle represents a context for scheduling. You can look at it as a localized version of the scheduler which runs Go code on a single thread. It’s the important part that lets us go from a N:1 scheduler to a M:N scheduler. In the runtime code, it’s called P for processor. More on this part in a bit.


Here we see 2 threads (M), each holding a context (P), each running a goroutine (G). In order to run goroutines, a thread must hold a context.

The number of contexts is set on startup to the value of the GOMAXPROCS environment variable or through the runtime function GOMAXPROCS(). Normally this doesn’t change during execution of your program. The fact that the number of contexts is fixed means that only GOMAXPROCS are running Go code at any point. We can use that to tune the invocation of the Go process to the individual computer, such at a 4 core PC is running Go code on 4 threads.

The greyed out goroutines are not running, but ready to be scheduled. They’re arranged in lists called runqueues. Goroutines are added to the end of a runqueue whenever a goroutine executes a go statement. Once a context has run a goroutine until a scheduling point, it pops a goroutine off its runqueue, sets stack and instruction pointer and begins running the goroutine.

To bring down mutex contention, each context has its own local runqueue. A previous version of the Go scheduler only had a global runqueue with a mutex protecting it. Threads were often blocked waiting for the mutex to unlocked. This got really bad when you had 32 core machines that you wanted to squeeze as much performance out of as possible.

The scheduler keeps on scheduling in this steady state as long as all contexts have goroutines to run. However, there are a couple of scenarios that can change that.

Who you gonna (sys)call?

You might wonder now, why have contexts at all? Can’t we just put the runqueues on the threads and get rid of contexts? Not really. The reason we have contexts is so that we can hand them off to other threads if the running thread needs to block for some reason.

An example of when we need to block, is when we call into a syscall. Since a thread cannot both be executing code and be blocked on a syscall, we need to hand off the context so it can keep scheduling.


Here we see a thread giving up its context so that another thread can run it. The scheduler makes sure there are enough threads to run all contexts. M1 in the illustration above might be created just for the purpose of handling this syscall or it could come from a thread cache. The syscalling thread will hold on to the goroutine that made the syscall since it’s technically still executing, albeit blocked in the OS.

When the syscall returns, the thread must try and get a context in order to run the returning goroutine. The normal mode of operation is to steal a context from one of the other threads. If it can’t steal one, it will put the goroutine on a global runqueue, put itself on the thread cache and go to sleep.

The global runqueue is a runqueue that contexts pull from when they run out of their local runqueue. Contexts also periodically check the global runqueue for goroutines. Otherwise the goroutines on global runqueue could end up never running because of starvation.

This handling of syscalls is why Go programs run with multiple threads, even when GOMAXPROCS is 1. The runtime uses goroutines that call syscalls, leaving threads behind.

Stealing work

Another way that the steady state of the system can change is when a context runs out of goroutines to schedule to. This can happen if the amount of work on the contexts’ runqueues is unbalanced. This can cause a context to end up exhausting it’s runqueue while there is still work to be done in the system. To keep running Go code, a context can take goroutines out of the global runqueue but if there are no goroutines in it, it’ll have to get them from somewhere else.


hat somewhere is the other contexts. When a context runs out, it will try to steal about half of the runqueue from another context. This makes sure there is always work to do on each of the contexts, which in turn makes sure that all threads are working at their maximum capacity.

Where to go?

There are many more details to the scheduler, like cgo threads, the LockOSThread()function and integration with the network poller. These are outside the scope of this post, but still merit study. I might write about these later. There are certainly plenty of interesting constructions to be found in the Go runtime library.

原文链接

By Daniel Morsing

https://morsmachine.dk/go-scheduler