Posted on

Goroutine调度器(二)：调度流程简述

我们都知道Go语言是原生支持语言级并发的，这个并发的最小逻辑单元就是goroutine。goroutine就类似于Go语言提供的一种“用户态线程”，当然这种“用户态线程”是跑在内核级线程之上的。当我们创建了很多的goroutine，并且它们都是跑在同一个内核线程之上的时候，就需要一个调度器来维护这些goroutine，确保所有的goroutine都使用CPU，并且是尽可能公平的使用CPU资源。

这个调度器的原理以及实现值得我们去深入研究一下。支撑整个调度器的主要有4个重要结构，分别是P、M、G、Sched，前三个定义在runtime.h中，Sched定义在proc.c中。

  • Sched结构就是调度器，它维护有存储M和G的队列以及调度器的一些状态信息等。
  • M代表内核级线程，一个M就是一个线程，goroutine就是跑在M之上的；M是一个很大的结构，里面维护小对象内存cache(mcache)、当前执行的goroutine、随机数发生器等等非常多的信息。
  • P全称是Processor，处理器，它的主要用途就是用来执行goroutine的，所以它也维护了一个goroutine队列，里面存储了所有需要它来执行的goroutine，这个P的角色可能有一点让人迷惑，一开始容易和M冲突，后面重点聊一下它们的关系。
  • G就是goroutine实现的核心结构了，G维护了goroutine需要的栈、程序计数器以及它所在的M等信息。

理解M、P、G三者的关系对理解整个调度器非常重要，我从网络上找了一个图来说明其三者关系：

地鼠用小车运着一堆待加工的砖。M就可以看作图中的地鼠，P就是小车，G就是小车里装的砖。一图胜千言啊，弄清楚了它们三者的关系，下面我们就开始重点聊地鼠是如何在搬运砖块的。 Continue reading "Goroutine调度器(二)：调度流程简述"

Posted on

Goroutine调度器(一)：P、M、G关系

在了解Go的运行时的scheduler之前，需要先了解为什么需要它，因为我们可能会想，OS内核不是已经有一个线程scheduler了嘛？
熟悉POSIX API的人都知道，POSIX的方案在很大程度上是对Unix process进场模型的一个逻辑描述和扩展，两者有很多相似的地方。 Thread有自己的信号掩码，CPU affinity等。但是很多特征对于Go程序来说都是累赘。 尤其是context上下文切换的耗时。另一个原因是Go的垃圾回收需要所有的goroutine停止，使得内存在一个一致的状态。垃圾回收的时间点是不确定的，如果依靠OS自身的scheduler来调度，那么会有大量的线程需要停止工作。 Continue reading "Goroutine调度器(一)：P、M、G关系"

Posted on

SkipList跳表

为什么选择跳表

目前经常使用的平衡数据结构有：B树，红黑树，AVL树，Splay Tree, Treep等。想象一下，给你一张草稿纸，一只笔，一个编辑器，你能立即实现一颗红黑树，或者AVL树出来吗？ 很难吧，这需要时间，要考虑很多细节，要参考一堆算法与数据结构之类的树，还要参考网上的代码，相当麻烦。用跳表吧，跳表是一种随机化的数据结构，目前开源软件 Redis 和 LevelDB 都有用到它，它的效率和红黑树以及 AVL 树不相上下，但跳表的原理相当简单，只要你能熟练操作链表，就能轻松实现一个 SkipList。 Continue reading "SkipList跳表"

Posted on

基于循环数组的无锁队列

引言

最近对于注重性能的应用程序,我们有了一种能显著提高程序性能的选择:多线程.线程的概念实际上已经存在了很长时间.在过去,多数计算机只有一个处理器,线程主要用于将一个大的任务拆分成一系列更小的执行单元.以使得当其中某些执行单元因为等待资源而被阻塞的时候剩余的执行单元能继续执行。举个示例,一个网络应用程序,它监听一个TCP端口,当有外部请求到达时,处理请求.对于一个单线程的应用程序来说,只能在处理完一个请求之后再处理另外的请求,显然这个应用程序对用户非常不友好,它为一个用户服务的时候别的用户就只能干等.而对于多线程解决方案,我们可以让另外的线程来处理接收到的请求,主线程继续等待在服务端口上接受新的请求.

在只有一个处理器的机器上,一个多线程应用程序可能无法达到我们对它的预期.因为所有的线程都要争抢处理器以获得执行机会.而它的性能说不定比一个用单线程方式去解决同样问题的程序还要差,因为线程之间的通讯和数据共享也有不小的开销.

而在一个对称多处理器机器上(SMP),一个多线程应用可以真正的实现多任务并行执行.每个线程都可以拥有单独的处理器以获得执行的机会,不需要再像单处理器一样,必须要等到处理器空闲才能获得执行机会.对一个有N个处理器的SMP系统来说,理论上一个N线程的应用程序只需要它的单线程版本的1/N的时间就可以完成相同的任务(实际上这个理论值是无法达到的,因为线程之间的通讯和数据共享有不小的开销).

SMP的机器在过去是非常昂贵的,只有一些大公司和组织才能负担得起.而现今,多核心处理器已经相当廉价(现今市场上的pc处理器至少都拥有一个以上的核心),所以让应用程序并行化以提高性能现在已经变得非常流行.

但是编写多线程应用程序显然不是一件简单的事.线程之间需要共享数据,互相通信,很快你就会发现又要面对以前就遇到过的老问题:死锁, 对共享数据的非法访问,多线程动态分配/释放内存等.如果你足够幸运,参与到一个对性能有极高要求的项目中,你将会遇到更多导致性能不达标的问题:

  • Cache颠簸(Cache trashing)
  • 在同步机制上的争抢.队列
  • 动态内存分配

本文主要介绍一种基于数组实现的无锁队列用于解决上述三个性能问题,特别是动态内存分配,因为此无锁队列最初的设计目的就是为了解决这个问题. Continue reading "基于循环数组的无锁队列"

Posted on

ES6新特性简介

1.变量声明const和let

我们都是知道在ES6以前，var关键字声明变量。无论声明在何处，都会被视为声明在函数的最顶部(不在函数内即在全局作用域的最顶部)。这就是函数变量提升例如:

1
2
3
4
5
6
7
  function aa() {
    if(bool) {
        var test = 'hello man'
    } else {
        console.log(test)
    }
  }

Continue reading "ES6新特性简介"
Posted on

缓存淘汰算法 - LRU

1. LRU
1.1. 原理

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

1.2. 实现

最常见的实现是使用一个链表保存缓存数据，详细算法实现如下：

1. 新数据插入到链表头部；

2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；

3. 当链表满的时候，将链表尾部的数据丢弃。 Continue reading "缓存淘汰算法 - LRU"

Posted on

Go学习整理笔记

最近重新梳理了一下Go学习中的一些要点，包括Go性能优化及底层源码要点，作此笔记，巩固基础。

一、并发

1、Go语言的goroutine类似于线程和协程的综合体，能最大限度提升执行效率，发挥多核处理能力；

2、通常情况下，用多进程来实现分布式负载均衡，减轻单进程垃圾回收压力；用多线程(LWP)抢夺更多的处理器资源；用协程来提高处理器时间片利用率；

3、相比较系统默认MB级别的线程栈，goroutine自定义栈初始仅需2KB，所以才能创建成千上万的并发任务。自定义栈采用按需分配策略，在需要时进行扩容，最大能到GB规模；

4、Go在运行时可能会创建很多线程，但任何时候仅有限的几个线程参与并发任务执行。该量默认与处理器核数相等，可用runtime.GOMAXPROCS函数或者环境变量修改；

5、通道：

         1)、通道(channel)相当于一个并发安全的队列；

         2)、goroutine leak是指goroutine处于发送或者接受阻塞状态，但一直未被唤醒，垃圾回收器并不收集此类资源，导致它们会在队列里长期休眠，形成资源泄露；

6、同步：

         1)、通道并不是用来取代锁的，它们有各自不同的使用场景。通道倾向于解决逻辑层次的并发处理架构，而锁则用来保护局部范围的数据安全；

         2)、将Mutex作为匿名字段时，相关方法必须实现为pointer-receiver模式，否则会因为复制导致锁机制失效；

         3)、应将Mutex锁粒度控制在最小范围内，及早释放；

7、建议：

         1)、对性能要求较高时，应避免使用defer Unlock；

         2)、读写并发时，用RWMutex性能会更好一些；

         3)、对单个数据读写保护，可尝试用原子操作；

         4)、执行严格测试，尽可能打开数据竞争检查；

Continue reading "Go学习整理笔记"