首页
精选文章GMP查看全文GMP是Golang语言协程调度机制的模型。协程机制是对传统的多线程/进程机制的一种改良，虽然多进程/线程可以有效提升系统的并发能力，但是互联网等高并发场景下，需要并发处理的请求量级较大，每个请求创建一个线程会带来大量的内存等资源的消耗。 而且进程/线程切换的成本较高，对CPU产生了较大的浪费。 golang的语言的协程机制通过实现用户态线程（协程）的方式减少线程的资源消耗以及切换消耗，用户态线程在执行的时候动态绑定到系统线程上。 无论是多线程、多进程、多协程都涉及到多个任务的并发执行，而且任务数量往往多于CPU的核数，所以就有了任务调度的需求，当进程阻塞在IO、时间占用较长等场景下需要切换其他等待执行的进程。 在早期单进程时代是不需要调度器的，因为进程是串行执行的。 GMP是协程的调度机制，G代表的是go语言中的协程，M代表的是实际的线程，P代表的是Go的逻辑处理器。 协程通过调度器和系统线程进行绑定之后，才能真正执行代码逻辑，协程和线程的绑定关系可以分为1 : 1，N：1，M：N等几种模型。在Golang语言中G和P是多对一的关系，而P和M是一对一的关系。 G和P，以及P和M之间的关联关系不是固定的，例如P在运行过程中被销毁，之前绑定的G就会转移到其他的P上执行。 数据存储 调度机制意味着不是所有的任务都可以得到立即执行，而不能被执行包括被切换的协程需要有存储的机制。等待被调度执行的协程存储在运行队列，Golang的调度器把队列分为局部运行队列和全局运行队列，每个和P绑定一个长度为256的循环队列，每次把G放入该队列的时候从末尾插入，获取的时候从头部获取。 除了从本地队列获取执行线程外，P还有一个特殊的字段runnext可以标识下一个要执行的协程…CAP查看全文CAP理论是2000年由Eric Brewer教授提出的。即一个分布式系统不可能同时满足一致性，可用性，分区容忍性这三个需求，而最多只能同时满足2个。2002年MIT的Seth Gilbert和Nancy lynch证明了CAP的正确性。CAP中的C是consistency（一致性）的缩写，首先解释一下一致性，一致性概念在计算机领域至少有下列含义： 数据库事务（ACID）的一致性是指数据变更的过程中需要满足正确的状态约束，这些约束分是数据库层面的约束，比如外键关系，但有一部分约束是指业务层实现的约束，例如转账的过程中用户的账户金额不能小于0。 不同于AID是数据库层面需要提供的能力，C需要用户自己实现。 CAP中的一致性，指的是一个读操作从能读取到之前写操作的结果，在分布式场景下更多的指数据副本之间的一致性。这里的一致性从事件约束可以分为强一致性和最终一致性，强一致性是指用户每次都可以读取到最新的数据，最终一致性是指可以在确定的时间内查询到最新的数据。从实现的方式上可以分为顺序一致性和线性一致性。 可用性是指系统的可用性，每一次请求都能在一定的时间内响应。 分区容忍性主要解决的是脑裂问题，即网络出现分区的情况下的状态。 因为分布式理论天然需要支持分区容忍性，所以CAP的概念真正的本质是在网络分区的情况下，只能在一致性和可用性中选择一个特性。 分区容忍性 分布式环境下的集群节点必然是有不同区域的物理分布的，分布可能是大的城域网分区，也可能是不同机房的分区，甚至小到机房的不同机架。 分区即集群的节点因为联通问题分成了两部分，此时面临的问题是两个分区同时提供服务，即脑裂问题，脑裂问题会导致后续的数据无法合并，因此分区容忍性就是解决脑裂问题…希尔排序查看全文希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本，但希尔排序是非稳定排序算法。希尔排序是基于插入排序的以下两点性质而提出改进方法的： 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率； 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位； 希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。 插入排序的时间复杂度是O（n2），但是如果数据是有序的，插入排序的效率会大幅提升，可以达到O（n）的时间复杂度，所以数据的有序性对插入排序的性能影响较大。 希尔排序也是采用分治的思想通过多次迭代将数据变得相对有序，从而减少插入排序流程中需要比较的次数。 希尔排序会将数字进行多次分组，分组会从小到大依此进行，例如第一次分组是将元素分为两个一组，因为插入排序在小数据量时有较好的效率，之后，分组会逐渐变大，到4个一组，8个一组，直到n/2个一组，数据量较大时候，插入排序的性能会有所下降，但是因为之前的分组使得数据变得相对有序，会提高后续插入排序的效率。 比如10个数字的希尔排序。 第一次把数据分为分组，10除以2得出分为5组，之后对5组数据分别进行插入排序。 第二次把数据分为2组，10除以4得出，之后对这两组数据进行插入排序。 以此类推，第n次分组的组数为元素个数/2n，直到仅剩下一个分组，进行一轮完整的插入排序。 插入排序进行分组不是简单的逐段分割，而是跳跃式的分组，该分组方式可以使得数据相对有序，而且中间会有一定的插入空间，从而减少插入时候的移动数量。 |
热门分类开源Golang消息队列JavaJavascriptLinuxMysqlNLPPHP事务内存管理分布式理论分类存储常用存储开源软件操作系统画图网络编程数据库算法虚拟化前端存储理论常用算法微服务数据结构算法应用计算机原理中间件共识算法分布式分治动态规划容器并发排序架构组件绘图工具网络协议编程语言理论算法思想树缓存架构C++字符串算法工程思想搜索
算法题库精选内容 |
